Redis是一个开源的key-value存储系统，它使用六种底层数据结构构建了包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象的对象系统。今天我们就通过12张图来全面了解一下它的数据结构和对象系统的实现原理。
本文的内容如下：
首先介绍六种基础数据结构：动态字符串，链表，字典，跳跃表，整数集合和压缩列表。
其次介绍Redis的对象系统中的字符串对象（String）、列表对象（List）、哈希对象（Hash）、集合对象（Set）和有序集合对象（ZSet）。
最后介绍Redis的键空间和过期键(expire)实现。
数据结构1、简单动态字符串Redis使用动态字符串SDS来表示字符串值。下图展示了一个值为Redis的SDS结构:
len:表示字符串的真正长度（不包含NULL结束符在内）。
alloc:表示字符串的最大容量（不包含最后多余的那个字节）。
flags:总是占用一个字节。其中的最低3个bit用来表示header的类型。
buf:字符数组。
SDS的结构可以减少修改字符串时带来的内存重分配的次数，这依赖于内存预分配和惰性空间释放两大机制。
当SDS需要被修改，并且要对SDS进行空间扩展时，Redis不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用的空间。
如果修改后，SDS的长度(也就是len属性的值)将小于1MB，那么Redis预分配和len属性相同大小的未使用空间。
如果修改后，SDS的长度将大于1MB，那么Redis会分配1MB的未使用空间。
比如说，进行修改后SDS的len长度为20字节，小于1MB，那么Redis会预先再分配20字节的空间，SDS的buf数组的实际长度(除去最后一字节)变为20+20=40字节。当SDS的len长度大于1MB时，则只会再多分配1MB的空间。
类似的，当SDS缩短其保存的字符串长度时，并不会立即释放多出来的字节，而是等待之后使用。
2、链表链表在Redis中的应用非常广泛，比如列表对象的底层实现之一就是链表。除了链表对象外，发布和订阅、慢查询、监视器等功能也用到了链表。
Redis的链表是双向链表，示意图如上图所示。链表是最为常见的数据结构，这里就不在细说。
Redis的链表结构的dup、free和match成员属性是用于实现多态链表所需的类型特定函数：
dup函数用于复制链表节点所保存的值，用于深度拷贝。
free函数用于释放链表节点所保存的值。
match函数则用于对比链表节点所保存的值和另一个输入值是否相等。
3、字典字典被广泛用于实现Redis的各种功能，包括键空间和哈希对象。其示意图如下所示。
Redis使用MurmurHash2算法来计算键的哈希值，并且使用链地址法来解决键冲突，被分配到同一个索引的多个键值对会连接成一个单向链表。
4、跳跃表Redis使用跳跃表作为有序集合对象的底层实现之一。它以有序的方式在层次化的链表中保存元素，效率和平衡树媲美——查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。
跳表的示意图如上图所示，这里只简单说一下它的核心思想，并不进行详细的解释。
如示意图所示，zskiplistNode是跳跃表的节点，其ele是保持的元素值，score是分值，节点按照其score值进行有序排列，而level数组就是其所谓的层次化链表的体现。
每个node的level数组大小都不同，level数组中的值是指向下一个node的指针和跨度值(span)，跨度值是两个节点的score的差值。越高层的level数组值的跨度值就越大，底层的level数组值的跨度值越小。
level数组就像是不同刻度的尺子。度量长度时，先用大刻度估计范围，再不断地用缩小刻度，进行精确逼近。
当在跳跃表中查询一个元素值时，都先从第一个节点的最顶层的level开始。比如说，在上图的跳表中查询o2元素时，先从o1的节点开始，因为zskiplist的header指针指向它。
先从其level[3]开始查询，发现其跨度是2，o1节点的score是1.0，所以加起来为3.0，大于o2的score值2.0。所以，我们可以知道o2节点在o1和o3节点之间。这时，就改用小刻度的尺子了。就用level[1]的指针，顺利找到o2节点。
5、整数集合整数集合intset是集合对象的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合对象的底层实现。
如上图所示，整数集合的encoding表示它的类型，有int16t，int32t或者int64_t。其每个元素都是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序的排列，并且数组中不包含任何重复项。length属性就是整数集合包含的元素数量。
5、压缩列表压缩队列ziplist是列表对象和哈希对象的底层实现之一。当满足一定条件时，列表对象和哈希对象都会以压缩队列为底层实现。
压缩队列是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。它的属性值有：
zlbytes:长度为4字节，记录整个压缩数组的内存字节数。
zltail:长度为4字节，记录压缩队列表尾节点距离压缩队列的起始地址有多少字节，通过该属性可以直接确定尾节点的地址。
zllen:长度为2字节，包含的节点数。当属性值小于INT16_MAX时，该值就是节点总数，否则需要遍历整个队列才能确定总数。
zlend:长度为1字节，特殊值，用于标记压缩队列的末端。
中间每个节点entry由三部分组成：
previous_entry_length:压缩列表中前一个节点的长度，和当前的地址进行指针运算，计算出前一个节点的起始地址。
encoding：节点保存数据的类型和长度
content：节点值，可以为一个字节数组或者整数。
对象上面介绍了6种底层数据结构，Redis并没有直接使用这些数据结构来实现键值数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合这五种类型的对象，每个对象都使用到了至少一种前边讲的底层数据结构。
Redis根据不同的使用场景和内容大小来判断对象使用哪种数据结构，从而优化对象在不同场景下的使用效率和内存占用。
Redis的redisObject结构的定义如下所示。
typedefstructredisObject{
unsignedtype:4;
unsignedencoding:4;
unsignedlru:LRU_BITS;
intrefcount;
void*ptr;
}robj;
其中type是对象类型，包括REDISSTRING,REDISLIST,REDISHASH,REDISSET和REDIS_ZSET。
encoding是指对象使用的数据结构，全集如下。
1、字符串对象我们首先来看字符串对象的实现，如下图所示。
如果一个字符串对象保存的是一个字符串值，并且长度大于32字节，那么该字符串对象将使用SDS进行保存，并将对象的编码设置为raw，如图的上半部分所示。如果字符串的长度小于32字节，那么字符串对象将使用embstr编码方式来保存。
embstr编码是专门用于保存短字符串的一种优化编码方式，这个编码的组成和raw编码一致，都使用redisObject结构和sdshdr结构来保存字符串，如上图的下半部所示。
但是raw编码会调用两次内存分配来分别创建上述两个结构，而embstr则通过一次内存分配来分配一块连续的空间，空间中一次包含两个结构。
embstr只需一次内存分配，而且在同一块连续的内存中，更好的利用缓存带来的优势，但是embstr是只读的，不能进行修改，当一个embstr编码的字符串对象进行append操作时，redis会现将其转变为raw编码再进行操作。
2、列表对象列表对象的编码可以是ziplist或linkedlist。其示意图如下所示。
当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码：
列表对象保存的所有字符串元素的长度都小于64字节。
列表对象保存的元素数量数量小于个。
不能满足这两个条件的列表对象需要使用linkedlist编码或者转换为linkedlist编码。
3、哈希对象哈希对象的编码可以使用ziplist或dict。其示意图如下所示。
当哈希对象使用压缩队列作为底层实现时，程序将键值对紧挨着插入到压缩队列中，保存键的节点在前，保存值的节点在后。如下图的上半部分所示，该哈希有两个键值对，分别是name:Tom和age:25。
当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码:
哈希对象保存的所有键值对的键和值的字符串长度都小于64字节。
哈希对象保存的键值对数量小于个。
不能满足这两个条件的哈希对象需要使用dict编码或者转换为dict编码。
4、集合对象集合对象的编码可以使用intset或者dict。
intset编码的集合对象使用整数集合最为底层实现，所有元素都被保存在整数集合里边。
而使用dict进行编码时，字典的每一个键都是一个字符串对象，每个字符串对象就是一个集合元素，而字典的值全部都被设置为NULL。如下图所示。
当集合对象可以同时满足以下两个条件时，对象使用intset编码:
集合对象保存的所有元素都是整数值。
集合对象保存的元素数量不超过个。
否则使用dict进行编码。
5、有序集合对象有序集合的编码可以为ziplist或者skiplist。
有序集合使用ziplist编码时，每个集合元素使用两个紧挨在一起的压缩列表节点表示，前一个节点是元素的值，第二个节点是元素的分值，也就是排序比较的数值。
压缩列表内的集合元素按照分值从小到大进行排序，如下图上半部分所示。
有序集合使用skiplist编码时使用zset结构作为底层实现，一个zet结构同时包含一个字典和一个跳跃表。
其中，跳跃表按照分值从小到大保存所有元素，每个跳跃表节点保存一个元素，其score值是元素的分值。而字典则创建一个一个从成员到分值的映射，字典的键是集合成员的值，字典的值是集合成员的分值。通过字典可以在O(1)复杂度查找给定成员的分值。如下图所示。
跳跃表和字典中的集合元素值对象都是共享的，所以不会额外消耗内存。
当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码：
有序集合保存的元素数量少于个；
有序集合保存的所有元素的长度都小于64字节。
否则使用skiplist编码。
6、数据库键空间Redis服务器都有多个Redis数据库，每个Redis数据都有自己独立的键值空间。每个Redis数据库使用dict保存数据库中所有的键值对。
键空间的键也就是数据库的键，每个键都是一个字符串对象，而值对象可能为字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的一种对象。
除了键空间，Redis也使用dict结构来保存键的过期时间，其键是键空间中的键值，而值是过期时间，如上图所示。
通过过期字典，Redis可以直接判断一个键是否过期，首先查看该键是否存在于过期字典，如果存在，则比较该键的过期时间和当前服务器时间戳，如果大于，则该键过期，否则未过期。
—————END—————
识别图片