Redis底层数据结构

简单动态字符串（SDS）

相较于C字符串的优点：

常数复杂度获取字符串长度。
杜绝缓冲区溢出。C字符串不记录自身长度容易造成缓冲区溢出，SDS修改时，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。
减少修改字符串时带来的内存重分配次数。SDS采用空间预分配（增长操作）和惰性释放（缩短操作）
二进制安全。C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。SDS可以保存任意格式的二进制数据。
兼容部分C字符串函数，避免了不必要的代码重复。

链表

链表被广泛用于实现Redis的各种功能，比如列表、发布与订阅、慢查询、监视器等。

listNode结构：

多个listNode可以通过prev和next指针组成双端链表。

list结构：

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数：

dup函数用于复制链表节点所保存的值；
free函数用于释放链表节点所保存的值；
match函数则用于对比链表节点所保存的值和另一个输入值是否相等。
一个list结构和三个listNode结构组成的链表：

链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表

字典

Redis的字典使用哈希表作为底层实现，哈希表结构如下：

一个大小为4的空哈希表（没有包含任何键值对）。

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。

Redis中的字典的结构：

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。

privdata属性则保存了需要传给那些类型特定函数的可选参数。

渐进式rehash

为了避免rehash对服务器性能造成影响，服务器不是一次性将哈希表中所有键值对全部rehash到新的哈希表，而是分多次、渐进式地将完成rehash。

以下是哈希表渐进式rehash的详细步骤：

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。新添加到字典的键值对一律会被保存到ht[1]里面。

跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。Redis使用跳跃表作为有序集合键的底层实现之一。

zskiplistNode结构如下：

level：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在下面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。

backward指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。

score：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。

obj：各个节点中的o1、o2和o3是节点所保存的成员对象。

zskiplist结构如下：

header：指向跳跃表的表头节点。

tail：指向跳跃表的表尾节点。

level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。

length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

带有zskiplist结构的跳跃表

整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。整数集合结构如下：

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。不支持降级操作。

升级整数集合并添加新元素共分为三步进行：

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
将新元素添加到底层数组里面。

压缩列表

压缩列表（ziplist）是列表和哈希的底层实现之一。当一个列表只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表的底层实现。压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。压缩表组成部分：

zlbytes：记录整个压缩列表占用的内存字节数。在对压缩列表进行内存重分配或者计算zlend的位置时使用。

zltails：记录压缩列表表尾结点距离压缩列表的起始地址有多少字节。通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾结点的地址。

zllen：记录了压缩列表包含的节点数量。

entryX：压缩列表所包含的节点。

zlend：用于标记压缩列表的末端。

下图展示一个压缩列表的示例：

压缩列表节点：由previous_entry_length、encoding、content三个部分组成。

previous_entry_length：记录了压缩列表中前一个节点的长度。程序可以通过指针减去当前节点的previous_entry_length，来计算出前一个节点的起始地址。

encoding：记录了节点的content属性所保存数据的类型以及长度。

content：保存节点的值。节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。

连锁更新

在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点e1至eN，e1至eN的所有节点的previous_entry_length属性都是1字节长的（因为所有节点的长度都小于254字节）。这时，如果我们将一个长度大于等于254字节的新节点new设置为压缩列表的表头节点，那么new将成为e1的前置节点，后面的e1,、e2、e3的previous_entry_length都需要程序对压缩列表执行空间重分配，扩展其长度。Redis将这种在特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”。

添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

快速列表

quicklist中每一个节点都是一个quicklistNode对象，其数据结构定义为：

typedef struct quicklistNode {
    struct quicklistNode *prev;//前一个节点
    struct quicklistNode *next;//后一个节点
    unsigned char *zl;//当前指向的ziplist或者quicklistLZF
    unsigned int sz;//当前ziplist占用字节
    unsigned int count : 16;//ziplist中存储的元素个数，16字节(最大65535个)
    unsigned int encoding : 2; //是否采用了LZF压缩算法压缩节点 1：RAW 2:LZF
    unsigned int container : 2; //存储结构，NONE=1, ZIPLIST=2
    unsigned int recompress : 1; //当前ziplist是否需要再次压缩(如果前面被解压过则为true，表示需要再次被压缩)
    unsigned int attempted_compress : 1;//测试用 
    unsigned int extra : 10; //后期留用
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;//列表头节点
    quicklistNode *tail;//列表尾节点
    unsigned long count;//ziplist中一共存储了多少元素，即:每一个quicklistNode内的count相加
    unsigned long len; //双向链表的长度，即quicklistNode的数量
    int fill : 16;//填充因子
    unsigned int compress : 16;//压缩深度 0-不压缩
} quicklist;

根据这两个结构，我们可以得到Redis3.2之后的列表对象的一个简图：

对象

Redis基于底层数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。Redis的对象系统还实现了基于引用计数技术的内存回收机制和对象共享机制。

Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能的情况下，空转时长较大的那些键可能会优先被服务器删除。

对象的类型与编码

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。键总是一个字符串对象，而值则可以是字符串对象（string）、列表对象（list）、哈希对象（hash）、集合对象（set）或者有序集合对象（zset）的其中一种。Redis中对象（redisObject）结构表示如下：

类型：包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象。可使用TYPE key命令查看值对象的类型。

编码：记录了对象所使用的编码。可使用OBJECT ENCODING key查看值对象的编码。

ptr指针：指向对象的底层实现数据结构。

下图展示了每种类型的对象可以使用的编码。

使用OBJECT ENCODING key命令可以查看一个数据库键的值对象的编码

通过encoding属性来设定对象所使用的编码，极大地提升了Redis的灵活性和效率，因为Redis可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

在列表对象包含的元素比较少时，Redis使用压缩列表作为列表对象的底层实现：因为压缩列表比双端链表更节约内存，并且在元素数量较少时，在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中。随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失时，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面。

字符串对象

字符串对象的编码可以是int、raw或者embstr。

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void* 转换成long），并将字符串对象的编码设置为int。
如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw。
如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值。

embstr编码是专门用于保存短字符串的一种优化编码方式，通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构，而raw编码会调用两次内存分配函数来分别创建。释放embstr编码字符串也只需要一次调用。

字符串对象保存各种不同类型的值所使用的编码方式如图所示：

编码的转换

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象。
Redis没有为embstr编码的字符串对象编写任何相应的修改程序，所以embstr编码的字符串对象实际上是只读的。
当对修改embstr编码的字符串对象时，会先将对象的编码从embstr转换成raw，然后再执行修改命令。
embstr编码的字符串对象在修改之后，总会变成一个raw编码的字符串对象。

字符串命令的实现

下图列举了一些字符串命令在不同编码的字符串对象下的实现方法。

列表对象

在Redis3.2之前，列表对象的编码可以是ziplist或者linkedlist。在Redis3.2之后，统一用quicklist来存储列表对象。执行RPUSH命令，那么服务器将创建一个列表对象作为numbers键的值，下面将分别展示ziplist、linkedlist数据结构。

quicklist存储了一个双向列表，每个列表的节点是一个ziplist，所以实际上quicklist就是linkedlist和ziplist的结合

ziplist编码对象如图所示：

linkedlist编码的列表对象如图所示：

上图简化了字符串对象的表示方式。

编码转换

当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码：

列表对象保存的所有字符串元素的长度都小于64字节；
列表对象保存的元素数量小于512个；不能满足这两个条件的列表对象需要使用linkedlist编码。

可通过list-max-ziplist-value选项和list-max-ziplist-entries选项修改以上两个条件的上限值

哈希对象

哈希对象的编码可以是ziplist或者hashtable。

ziplist编码的哈希对象使用压缩列表作为底层实现，新的键、值会以两个相邻的压缩列表节点推入到压缩列表表尾。举个例子，如果我们执行以下命令：

redis> HSET profile name tom
redis> HSET profile age 25
redis> HSET profile career Programmer

对象所使用的压缩列表如图

hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存。还是拿上面的命令举例，其结构如图所示：

编码转换

当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码，否则使用hashtable编码。

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
哈希对象保存的键值对数量小于512个。

可通过hash-max-ziplist-value选项和hash-max-ziplist-entries选项修改以上两个条件的上限值

集合对象

集合对象的编码可以是intset或者hashtable。

intset编码的集合对象包含的所有元素都被保存在整数集合里面；
hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。

下图分别为intset编码集合对象以及hashtable编码集合对象结构：

编码的转换

当集合对象可以同时满足以下两个条件时，对象使用intset编码，否则使用hashtable编码：

集合对象保存的所有元素都是整数值；
集合对象保存的元素数量不超过512个。

可通过set-max-intset-entries选项修改以上条件上限值

有序集合对象

有序集合的编码可以是ziplist或者skiplist。

ziplist编码的有序集合，使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。集合元素按分值从小到大进行排序。
skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典（dict）和一个跳跃表（zsl）。这两种数据结构都会通过指针来共享相同元素的成员和分值，不会浪费额外的内存。

zsl跳跃表按分值从小到大保存了所有集合元素：跳跃表节点的object属性保存了元素的成员，score属性则保存了元素的分值，以便程序可以对有序集合进行范围型操作，比如ZRANK、ZRANGE等命令。

dict字典为有序集合创建了一个从成员到分值的映射：字典的键保存了元素的成员，值保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值，比如ZSCORE命令。

编码的转换

当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码，否则使用skiplist编码：

有序集合保存的元素数量小于128个；
有序集合保存的所有元素成员的长度都小于64字节。

可通过zset-max-ziplist-entries和zset-max-ziplist-value选项修改以上两个条件的上限值

类型检查与命令多态

Redis中用于操作键的命令基本上可以分为两种类型：

可以对任何类型的键执行（命令多态），比如说DEL、EXPIRE、RENAME、TYPE、OBJECT等。redis会根据键的值对象所使用的编码来选择正确的命令。
只能对特定类型的键执行，比如SET、GET、RPUSH、LPOP、ZADD、ZCARD等。redis通过redisObject结构的type属性来检查键的值对象是否为执行命令所需的类型，如不匹配则不执行。（类型检查）

内存回收与对象共享

Redis通过在对象系统中构建了一个引用计数技术实现的内存回收机制。每个对象的引用计数信息由redisObject结构的refcount属性记录
Redis会在初始化服务器时，创建0-9999的字符串对象，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。

可以通过修改redis.h/REDIS_SHARED_INTEGERS来修改创建共享字符串对象的数量

为什么Redis不共享包含字符串的对象？

一个共享对象保存的值越复杂，验证共享对象和目标对象是否相同所需的复杂度就会越高，消耗的CPU时间也会越多。

如果共享对象是保存字符串值的字符串对象，那么验证操作的复杂度为O（N）；
如果共享对象是包含了多个值（或者对象的）对象，比如列表对象或者哈希对象，那么验证操作的复杂度将会是O（N²）。

因此，尽管共享更复杂的对象可以节约更多的内存，但受到CPU时间的限制，Redis只对包含整数值的字符串对象进行共享。

为什么Redis引用计数不会出现循环引用？

redis对象之间没有深层次的嵌套，顶多有一个指向底层的实现数据结构的指针，并且redis只共享0-9999的数值字符串对象，对于别的对象，ptr指针是不会去寻找是否有相同的，然后指向，所以不存在循环引用。

对象的空转时长

redisObject除了前面介绍过的type、encoding、ptr和refcount四个属性之外，还包含最后一个属性为lru属性，当用于LRU时表示最后一次访问时间，当用于LFU时，高16位记录分钟级别的访问时间，低8位记录访问频率0到255。

当服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru时，当服务器占用的内存数超过maxmemory所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。

Bitmap、Stream、Geo、HyperLogLog待更新

参考

《Redis设计与实现》（黄健宏）
https://blog.csdn.net/zwx900102/article/details/109595508

留言