一文理解Redis底层数据结构

Redis的5种常见数据结构：字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)。这些都是Redis对外暴露的数据结构，本文将介绍这些数据结构的底层数据结构的实现。

Redis底层数据结构有六种：

• 简单动态字符串（SDS）
• 列表
• 字典
• 整数集合
• 跳跃表
• 压缩列表
• 快速列表

简单动态字符串（SDS）

SDS是"simple dynamic string"的缩写。Redis中所有场景中出现的字符串，基本都是由SDS来实现的。

使用场景：

• 所有非数字的key。例如：set msg "hello world"中的key msg.
• 字符串数据类型的值。例如：set msg "hello world"中的msg的值"hello wolrd"
• 非字符串数据类型中的“字符串值”。例如：RPUSH fruits "apple" "banana" "cherry"中的"apple" "banana" "cherry"

SDS结构图：

• len：记录当前已使用的字节数（不包括'\0'），获取SDS长度的复杂度为O(1)（C 语言中获取字符串长度的时间复杂度为 O(N)）。此外，len值还避免了二进制安全与缓存区溢出的问题。
• alloc：记录当前字节数组总共分配的字节数量（不包括'\0'）。
• flags：标记当前字节数组的属性，是sdshdr8还是sdshdr16等。
• buf：字节数组，用于保存字符串，包括结尾空白字符'\0'。

// flags值定义(为了节约头部空间，在Redis3.2开始，增加flag字段。SDS由一种数据结构变成了5种数据结构，会根据SDS存储的内容长度来选择不同的结构，以达到节省内存的效果)
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

注：

1. 二进制安全：通俗的讲，C语言中，用“\0”表示字符串的结束，如果字符串本身就有“\0”字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，这就是二进制安全。
2. 因为C字符串不记录自身的长度，所以strcat会假定用户在执行这个函数时，已经为dest分配足够多的内存了，可以容纳src字符串中的所有内容，而一旦这个假设不成立，就会产生缓存区溢出。

频繁内存分配问题处理

每次增长或者缩短一个字符，程序都需要对保存这个字符串的数组进行一次内存重新分配操作。因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作。

为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

1. 空间预分配

空间预分配用于优化SDS的字符串增长操作。当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。其中，额外分配的未使用空间数量由以下公式决定：

• 如果对SDS进行修改之后，SDS的长度将小于1MB，那么程序分配和len属性同样大小的未使用空间。
• 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。

在扩展SDS空间之前，SDS API会先检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间，而无需执行内存重分配。通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

1. 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作。当SDS的API需要缩短SDS保存的字符串时，程序不会立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录下来，并等待将来使用。

通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能的增长操作提供了优化。

与此同时，SDS也提供了响应的API可以在有需要时，真正的释放SDS里面的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

列表

列表在Redis中应用的非常广，列表的底层实现就是链表。此外，Redis的发布与订阅、慢查询、监视器等功能也用到了链表。

列表特点：

• 双端链表：带有指向前置节点和后置节点的指针，获取这两个节点的复杂度为O(1)。
• 无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL结束。
• 链表长度计数器：带有len属性，获取链表长度的复杂度为O(1)。
• 多态：链表节点使用 void*指针保存节点值，可以保存不同类型的值。

列表结构图：

列表的数据结构（adlist.h/listNode与adlist.h/list）：

listNode：

• prev：前置节点。
• next：后置节点。
• value：节点值。

list：

• head：链表头节点。
• tail：链表尾节点。
• len：链表所包含的节点数量。
• dup：函数，用于复制ptr值，实现深度复制。
• free：函数，用于释放对应类型结构的内存。
• match：函数，用于对比链表节点所保存的值和另一个输入值是否相等。

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键都是唯一的，可以通过键查找与之关联的值，并对其修改或删除。

Redis的键值对存储就是用字典实现的，散列（Hash）的底层实现之一也是字典。

字典的结构图（与JDk中的HashMap结构很相似）：

字典的数据结构（dict.h/dictht与dict.h/dict）：

dict：

• type：针对不同类型的键值对，用于创建多类型的字典
• privdata：针对不同类型的键值对，用于创建多类型的字典
• ht：两个元素的数组，包含两个dictht哈希表，一般字典只使用ht[0]哈希表，ht[1]哈希表会在对ht[0]哈希表进行rehash（重哈希）的时候使用，即当哈希表的键值对数量超过负载数量过多的时候，会将键值对迁移到ht[1]上
• rehashidx：rehashidx也是跟rehash相关的，rehash的操作不是瞬间完成的，rehashidx记录着rehash的进度，图中没有进行rehash，它的值为-1

dictht：

• table：哈希链表（包含了一个节点类型为dictEntry的链表）
• size：哈希链表大小
• sizemask：哈希链表大小掩码，用于计算索引值，等于size-1
• used：哈希链表已有节点的数量

dictEntry：

• key：键
• next：下一个dictEntry节点
• value：union类型，支持不同类型的值

渐进式hash

字典类型容量变化过程叫做rehash。需要满足一定的条件才能触发扩容机制：

1. 服务器当前没有进行BGWRITEAOF或者BGSAVE命令，且当前键值对个数超过一维数组的大小，才会触发扩容。
2. 如果当前键值对个数超过一维数组大小的五倍，无论是否在进行BGWRITEAOF或者BGSAVE命令，都会强制扩容。
3. 如果当前键值对个数少于一维数组大小的十分之一，则触发缩容过程。缩容不会考虑当前服务器是否在进行BGWRITEAOF或者BGSAVE命令。

渐进式hash的过程，简单来说类似数据库的迁移，读的时候先读ht[0]，读不到读ht[1]；写的时候只写ht[1]；ht[0]数据慢慢地往ht[1]上搬。

当ht[0]的所有键值都迁至ht[1]之后，ht[0]变为空表，释放ht[0]。并将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，将rehashidx属性的值设为-1，表示rehash操作已完成。

具体步骤如下：

1. 为字典的备用哈希表分配空间：如果执行的是扩展操作，那么备用哈希表的大小为第一个大于等于(已用节点个数)*2的2n（2的n次方幂） 如果执行的是收缩操作，那么备用哈希表的大小为第一个大于等于(已用节点个数)的2n
2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始（为-1时表示没有进行rehash）。
3. rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当一次rehash工作完成之后，程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数，在1ms的时间内，进行rehash处理，每次仅处理少量的转移任务(100个元素)。随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

这里比较下Redis的渐进hash与JDk中HashMap的resize过程。如果对HashMap不了解，可以查看《详解并发下的HashMap以及JDK8的优化》。

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素 整数集合是集合（Set）的底层实现之一，如果一个集合只包含整数值元素，且元素数量不多时，会使用整数集合作为底层实现

整数集合的结构图：

整数集合的数据结构（inset.h/inset）：

intset：

• encoding：决定contents数组的真正类型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64。
• length：记录整数集合的元素数量，即contents数组长度
• contents：整数集合的每个元素在数组中按值的大小从小到大排序，且不包含重复项。

整数集合的升级

当想要添加一个新元素到整数集合中时，并且新元素的类型比整数集合现有的所有元素的类型都要长，整数集合需要先进行升级，才能将新元素添加到整数集合里面。每次想整数集合中添加新元素都有可能会引起升级，每次升级都需要对底层数组已有的所有元素进行类型转换。

升级添加新元素：

• 根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
• 把数组现有的元素都转换成新元素的类型，并将转换后的元素放到正确的位置，且要保持数组的有序性。
• 添加新元素到底层数组。

整数集合的升级策略可以提升整数集合的灵活性，并尽可能的节约内存。另外，整数集合不支持降级，一旦升级，编码就会一直保持升级后的状态。

跳跃表

一个普通的单链表查询一个元素的时间复杂度为O(N)，即便该单链表是有序的。使用跳跃表（SkipList）是来解决查找问题的，它是一种有序的数据结构，不属于平衡树结构，也不属于Hash结构，它通过在每个节点维持多个指向其他节点的指针，而达到快速访问节点的目的 跳跃表是有序集合（Sorted Set）的底层实现之一，如果有序集合包含的元素比较多，或者元素的成员是比较长的字符串时，Redis会使用跳跃表做有序集合的底层实现。

跳跃表其实可以把它理解为多层的链表，它有如下的性质：

• 多层的结构组成，每层是一个有序的链表
• 最底层（level 1）的链表包含所有的元素
• 跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为 O(logn)
• 跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

有关跳跃表的讲解，可以查看《有关跳跃表的干货都在这里》

跳跃表的结构图：

• 每个跳跃表节点的层数在1-32之间
• 一个跳跃表中，节点按照分值大小排序，多个节点的分值是可以相同的，相同时，节点按成员对象大小排序
• 每个节点的成员变量必须是唯一的

压缩列表

压缩列表（ziplist）是为了节约内存而设计的，是由一系列特殊编码的连续内存块组成的顺序性（sequential）数据结构，一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者一个整数值。

压缩列表是列表（List）和散列（Hash）的底层实现之一，一个列表只包含少量列表项，并且每个列表项是小整数值或比较短的字符串，会使用压缩列表作为底层实现（在3.2版本之后是使用quicklist实现）。

压缩列表的结构图：

一个压缩列表可以包含多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

压缩列表的数据结构：

• zlbytes：记录整个压缩列表占用的内存字节数，在压缩列表内存重分配，或者计算zlend的位置时使用。
• zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过该偏移量，可以不用遍历整个压缩列表就可以确定表尾节点的地址。
• zllen：记录压缩列表包含的节点数量，但该属性值小于UINT16_MAX（65535）时，该值就是压缩列表的节点数量，否则需要遍历整个压缩列表才能计算出真实的节点数量。
• entryX：压缩列表的节点。
• zlend：特殊值0xFF（十进制255），用于标记压缩列表的末端。

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数字或者一个整数值。压缩列表节点的数据结构：

• previous_entry_ength：记录压缩列表前一个字节的长度。
• encoding：节点的encoding保存的是节点的content的内容类型。
• content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定。

快速列表

考虑到链表的附加空间相对太高，prev和next指针就要占去16个字节（64bit系统的指针是8个字节）。另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。因此Redis3.2版本开始对列表数据结构进行了改造，使用快速列表（quicklist）代替了压缩列表和列表。

快速列表的结构图：

快速列表的数据结构：

quicklistNode：

• prev: 指向链表前一个节点的指针。
• next: 指向链表后一个节点的指针。
• zl: 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
• sz: 表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
• count: 表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。
• encoding: 表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
• container: 是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
• recompress: 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
• attempted_compress: 这个值只对Redis的自动化测试程序有用。
• extra: 其它扩展字段。

quickList：

• head: 指向头节点（左侧第一个节点）的指针。
• tail: 指向尾节点（右侧第一个节点）的指针。
• count: 所有ziplist数据项的个数总和。
• len: quicklist节点的个数。
• fill: 16bit，ziplist大小设置，存放list-max-ziplist-size参数的值。
• compress: 16bit，节点压缩深度设置，存放list-compress-depth参数的值。

压缩深度

quicklist默认的压缩深度是0，也就是不压缩。压缩的实际深度由配置参数list-compress-depth决定。为了支持快速的push/pop操作，quicklist的首尾两个ziplist不压缩，此时深度就是1；如果深度为2，就表示quicklist的首尾第一个 ziplist以及首尾第二个ziplist都不压缩。

zipList长度

quicklist 内部默认单个ziplist长度为8k字节，超出了这个字节数，就会新起一个ziplist。ziplist的长度由配置参数list-max-ziplist-size决定。

编码

上面介绍了Redis的主要底层数据结构，包括简单动态字符串（SDS）、链表、字典、跳跃表、整数集合、压缩列表。但是Redis并没有直接使用这些数据结构来构建数据库，而是基于这些数据结构创建不同的编码，然后由不同条件下的不同编码来实现Redis的这些数据类型：字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)。

接下来就介绍Redis五种数据结构对应的编码。

字符串对象的编码

上面介绍了SDS，但这只是字符串对象的其中一种实现。字符串对象的编码可能有三种：int、raw、embstr。

1. int 如果一个字符串对象，保存的值是一个整数值，并且这个整数值在long的范围内，那么Redis用整数值来保存这个信息，并且将字符串编码设置为 int。
2. raw 如果字符串对象保存的是一个字符串, 并且长度大于32个字节，它就会使用前面讲过的SDS（简单动态字符串）数据结构来保存这个字符串值，并且将字符串对象的编码设置为raw。
3. embstr 如果字符串对象保存的是一个字符串，但是长度小于32个字节，它就会使用embstr来保存了，embstr编码不是一个数据结构，而是对SDS的一个小优化，当使用SDS 的时候，程序需要调用两次内存分配，来给字符串对象和SDS各自分配一块空间，而embstr只需要一次内存分配，因为他需要的空间很少，所以采用连续的空间保存，即将SDS的值和字符串对象的值放在一块连续的内存空间上。这样能在短字符串的时候提高一些效率。

浮点数如何保存：

Redis的字符串数据类型是支持保存浮点数，并且支持对浮点数进行加减操作，但是Redis在底层是把浮点数转换成字符串值，然后按照上述编码规则。对浮点数进行操作时，也是从字符串转换成浮点数进行计算，然后再转换成字符串进行保存的。

编码转换条件：

如果对一个int编码的字符串对象，修改它成非整数值，则对象就会使用raw编码。而Redis没有为embstr编码提供任何的修改操作，embstr编码的值是只读的，只要发生修改，立刻将编码转换成raw。

列表对象的编码

在 Redis 3.2 版本之前，列表对象底层由 压缩列表和双向链表配合实现，当元素数量较少的时候，使用压缩列表，当元素数量增多，就开始使用普通的双向链表保存数据。

但是这种实现方式不够好，双向链表中的每个节点，都需要保存前后指针，这个内存的使用量 对于Redis这个内存数据库来说极其不友好。

因此在 3.2 之后的版本，Redis新实现了一个数据结构，叫做快速列表（quicklist）。所有列表的底层实现都是这个数据结构了。它的底层实现基本上就是将 双向链表和压缩列表进行了结合，用双向的指针将压缩列表进行连接，这样不仅避免了压缩列表存储大量元素的性能压力，同时避免了双向链表连接指针占用空间过多的问题。

集合对象的编码

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

当集合中的所有元素都是整数，且元素的数量不大于512个的时候，使用intset编码。

当元素不符合全部为整数值且元素个数小于512时，集合对象使用的编码方式为 hashtable。

有序集合对象的编码

有序集合对象的编码可以是ziplist以及skiplist。

当使用ziplist编码时，有序集合对象的实现数据结构为压缩列表。当条件变化，ziplist编码会转换成skiplist编码。

当使用skiplist编码的时候，内部使用zset 来实现数据的保存，zset的定义如下：

typedef struct zset{
  zskiplist *zsl;
  dict *dict;
}zset;

为什么需要同时使用跳跃表以及字典呢？

• 当只使用字典来实现，可以以O(1)的时间复杂度获取成员的分值，但是由于字典是无序的，当需要进行范围性操作的时候，需要对字典中的所有元素进行排序，这个时间复杂度至少需要 O(nlogn)。
• 当只使用跳跃表来实现，可以在O(logn)的时间进行范围排序操作，但是如果要获取到某个元素的分值，时间复杂度也是O(logn)。

因此，将字典和跳跃表结合进行使用，可以在O(1)的时间复杂度下完成查询分值操作，而对一些范围操作使用跳跃表可以达到O(logn)的时间复杂度。

散列对象

散列对象的编码可以是ziplist或者hashtable.

ziplist编码下的哈希对象，使用了压缩列表作为底层实现数据结构，用两个连续的压缩列表节点来表示哈希对象中的一个键值对。实现方式类似于上面的有序集合的场景。

哈希结构本身在结构上和字典颇为相似，因此哈希对象中的每一个键值对都是字典中的一个键值对。

• 字典的每一个键都是一个字符串对象，对象中保存了键值对的键。
• 字典的每一个值都是一个字符串对象，对象中保存了键值对的值。

总结

参考文档：

1. 《Redis设计与实现》
2. https://github.com/redis/redis
3. 《Redis 深度历险：核心原理和应用实践》