redis底层数据结构

Redis的简介

• Redis是一个开源（BSD许可），内存存储的数据结构服务器,可用作数据库，高速缓存和消息队列代理
• 它支持字符串、哈希表、列表、集合、有序集合，位图，hyperloglogs等数据类型
• 内置复制、Lua脚本、LRU收回、事务以及不同级别磁盘持久化功能，同时通过Redis Sentinel提供高可用，通过Redis Cluster提供自动分区。

简言之，Redis是一种面向“键/值”对数据类型的内存数据库，可以满足我们对海量数据的快速读写需求。

5种基础数据类型，分别是：String、List、Set、Zset、Hash，三种特殊的数据类型 分别是 HyperLogLogs（基数统计）， Bitmaps (位图) 和 geospatial （地理位置)

下面我们看下这些数据类型的底层数据结构。

SDS（简单动态字符串）

Redis 没有直接使用 C 语言传统的字符串标识，而是自己构建了一种名为简单动态字符串 SDS(simple dynamic string）的抽象类型，并将 SDS 作为 Redis 的默认字符串。

SDS 结构

Redis 使用不同版本的 sdshdr 结构来节省内存空间，每个版本都有不同的头部大小，并根据字符串长度选择合适大小的结构来存储字符串数据。这样，当存储较小的字符串时，不会浪费过多的内存空间。

属性含义：

• len：表示当前字符串的已使用长度，即实际存储的字符串的长度。
• alloc：表示当前字符串的总分配长度（包括头部和结尾的空字符）。在需要扩展字符串时，alloc 可能会大于 len，以提供预留空间，避免频繁的内存重新分配。
• flags：用于表示字符串的类型信息，目前只使用了低 3 位，其余 5 位暂时未使用。
• buf[] ：是一个柔性数组（flexible array member），用来存储字符串的实际数据。在定义结构时没有指定数组长度，这使得 SDS 可以根据实际字符串长度动态调整其大小。

SDS优势

相较于C语言中的传统字符串表示，SDS具有以下优势：

链表

链表提供了高效的节点排重能力，以及顺序性的节点访问方式，而且可以通过增加节点来灵活地调整链表的长度。它是一种常用的数据结构，被内置在很多高级语言中。因为C语言并没有内置这种数据结构，所以 Redis 构建了自己的链表实现。

链表结构

每个链表节点使用一个adlist.h/listNode结构来表示

• prev 前置节点
• next 后置节点
• value 节点的值

多个 listNode 结构组成一个链表

• head 节点头指针
• tail 节点尾指针
• dup 用于复制链表节点所保存的值
• free 用于释放链表节点所保存的值
• match 用于对比链表节点所保存的值和另一个输入的值是否相等
• len 链表计数器
• Redis 链表的特性;

链表特点

Redis 链表有以下特点：

字典

字典中一个键（key）可以和一个值关联（value），这种关联的键和值我们称之为键值对。所以字典的每个键都是独一无二的，我们可以根据键在 O(1) 的时间复杂度下找到与之相关联的值。字典也是很多高级语言都内置的一种数据结构，但是 C语言并没有内置这种数据结构，因此 Redis 自己构建了字典的实现。

字典结构

• dictEntry：字典的键值对结构，具有相同的定义。
• dictType：字典的类型结构，也与之前提供的定义相同。
• dict：字典的主结构，包含了字典的类型信息、两个哈希表、重哈希相关的字段、暂停 rehash 的标志、哈希表的大小指数以及可变大小的元数据。

rehash过程

• 在正常服务请求阶段，所有的键值对写入哈希表 ht_table[0]。
• 当进行 rehash 时，键值对被迁移到哈希表 ht_table[1]中。
• 当迁移完成后，ht_table[0]的空间会被释放，并把 ht_table[1]的地址赋值给 ht_table[0]，ht_table[1]的表大小设置为 0。这样一来，又回到了正常服务请求的阶段，ht_table[0]接收和服务请求，ht_table[1]作为下一次 rehash 时的迁移表。

触发rehash时机：

• 若当前字典满足以下条件之一，则强制进行扩容：
  • 字典的全局设置允许扩容（dict_can_resize == DICT_RESIZE_ENABLE）且元素数量已经等于当前哈希表大小（即已达到 1:1 的负载因子）。
  • 字典的全局设置不允许扩容（dict_can_resize != DICT_RESIZE_FORBID）且负载因子超过安全阈值（dict_force_resize_ratio）。

字典优点

跳跃表

跳跃表是一种有序的链性数据结构，通过维护层级 (level) 来达到快速访问节点的目的。平均查找复杂度为 O(logN)，最坏 O(N)。因为是链性结构，还支持顺序性操作。
关于 Redis 为什么采用跳跃表而不采用红黑树之前我写过一篇文章，所以就不在这细诉了，我觉得其主要原因不外乎两点，一是红黑树不易于实现，而且在频繁的添加修改之后，为了维持树的平衡还要进行左右旋转。二是红黑树查找虽然是 O(logN)，但是在进行区间查找中往往就做到不 O(logN) 了，甚至需要遍历整个树。跳表就不需要了，它只需要找到第一个节点然后根据链性结构的特点向下走就可以了。Redis 有序集合一般就是用的这种实现。

zskiplistNode 为跳跃表节点:

• sds 元素
• score 分值
• backward 后退指针
• level 层级

zskiplist 为跳跃表:

• header 头结点
• tail 尾节点
• length 节点数量
• level 最大节点的层数

整数集合

当一个集合的元素只包含整数值元素，并且集合的元素不多时，Redis 就会使用整数集合作为集合的底层实现。

• encoding 编码方式
• length 集合元素个数
• contents 保存集合数据的数组

当集合数据类型大于 int8_t 所表示的最大空间时，Redis 会自动为该集合升级。一旦升级，不支持降级。

跳表其实是一种多层的有序链表。我们看看跳表实现的具体数据结构。

首先，因为 Sorted Set 中既要保存元素，也要保存元素的权重，所以对应到跳表结点的结构定义中，就对应了 sds 类型的变量 ele，以及 double 类型的变量 score。

此外，为了便于从跳表的尾结点进行倒序查找，每个跳表结点中还保存了一个后向指针（*backward），指向该结点的前一个结点。

然后，因为跳表是一个多层的有序链表，每一层也是由多个结点通过指针连接起来的。因此在跳表结点的结构定义中，还包含了一个 zskiplistLevel 结构体类型的 level 数组。level 数组中的每一个元素对应了一个 zskiplistLevel 结构体，也对应了跳表的一层。而 zskiplistLevel 结构体定义了一个指向下一结点的前向指针（*forward），这就使得结点可以在某一层上和后续结点连接起来。

最后，因为跳表中的结点都是按序排列的，所以，对于跳表中的某个结点，我们可以把从头结点到该结点的查询路径上，各个结点在所查询层次上的*forward指针跨度，做一个累加。这个累加值就可以用来计算该结点在整个跳表中的顺序，另外这个结构特点还可以用来实现 Sorted Set 的 rank 操作，比如 ZRANK、ZREVRANK 等。好，了解了跳表结点的定义后，我们可以来看看跳表的定义。在跳表的结构中，定义了跳表的头结点和尾结点、跳表的长度，以及跳表的最大层数，如下所示。

因为跳表的每个结点都是通过指针连接起来的，所以我们在使用跳表时，只需要从跳表结构体中获得头结点或尾结点，就可以通过结点指针访问到跳表中的各个结点。那么，当我们在 Sorted Set 中查找元素时，就对应到了 Redis 在跳表中查找结点，而此时，查询代码是否需要像查询常规链表那样，逐一顺序查询比较链表中的每个结点呢？其实是不用的，因为这里的查询代码，可以使用跳表结点中的 level 数组来加速查询。

跳表结点查询

事实上，当查询一个结点时，跳表会先从头结点的最高层开始，查找下一个结点。而由于跳表结点同时保存了元素和权重，所以跳表在比较结点时，相应地有两个判断条件：当查找到的结点保存的元素权重，比要查找的权重小时，跳表就会继续访问该层上的下一个结点。当查找到的结点保存的元素权重，等于要查找的权重时，跳表会再检查该结点保存的 SDS 类型数据，是否比要查找的 SDS 数据小。如果结点数据小于要查找的数据时，跳表仍然会继续访问该层上的下一个结点。但是，当上述两个条件都不满足时，跳表就会用到当前查找到的结点的 level 数组了。跳表会使用当前结点 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

总结

跳表是一个多层的有序链表，在跳表中进行查询操作时，查询代码可以从最高层开始查询。层数越高，结点数越少，同时高层结点的跨度会比较大。

因此，在高层查询结点时，查询一个结点可能就已经查到了链表的中间位置了。这样一来，跳表就会先查高层，如果高层直接查到了等于待查元素的结点，那么就可以直接返回。如果查到第一个大于待查元素的结点后，就转向下一层查询。下层上的结点数多于上层，所以这样可以在更多的结点中进一步查找待查元素是否存在。

跳表的这种设计方法就可以节省查询开销，同时，跳表设计采用随机的方法来确定每个结点的层数，这样就可以避免新增结点时，引起结点连锁更新问题。

压缩列表

压缩列表是一种为节约内存而开发的顺序性数据结构。常常被用作列表、哈希的底层实现。是由一系列特殊编码的连续内存块组成的。这块空间的起始部分是大小固定的 10 字节元数据，其中记录了 ziplist 的总字节数、最后一个元素的偏移量以及列表元素的数量，而这 10 字节后面的内存空间则保存了实际的列表数据。在 ziplist 的最后部分，是一个 1 字节的标识（固定为 255），用来表示 ziplist 的结束，如下图所示：

在 ziplist 中，编码技术主要应用在列表项中的 prevlen 和 encoding 这两个元数据上。而当前项的实际数据 data，则正常用整数或是字符串来表示。所以这里，我们就先来看下 prevlen 的编码设计。ziplist 中会包含多个列表项，每个列表项都是紧挨着彼此存放的，

ziplist 的不足主要在于一旦 ziplist 中元素个数多了，它的查找效率就会降低。而且如果在 ziplist 里新增或修改数据，ziplist 占用的内存空间还需要重新分配；更糟糕的是，ziplist 新增某个元素或修改某个元素时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，这就会导致 ziplist 的访问性能下降。

quicklist

quicklist 的设计，其实是结合了链表和 ziplist 各自的优势。简单来说，一个 quicklist 就是一个链表，而链表中的每个元素又是一个 ziplist。我们来看下 quicklist 的数据结构，这是在quicklist.h文件中定义的，而 quicklist 的具体实现是在quicklist.c文件中。首先，quicklist 元素的定义，也就是 quicklistNode。因为 quicklist 是一个链表，所以每个 quicklistNode 中，都包含了分别指向它前序和后序节点的指针prev和next。同时，每个 quicklistNode 又是一个 ziplist，所以，在 quicklistNode 的结构体中，还有指向 ziplist 的指针*zl。此外，quicklistNode 结构体中还定义了一些属性，比如 ziplist 的字节大小、包含的元素个数、编码格式、存储方式等。下面的代码显示了 quicklistNode 的结构体定义，你可以看下。

quicklist 作为一个链表结构，在它的数据结构中，是定义了整个 quicklist 的头、尾指针，这样一来，我们就可以通过 quicklist 的数据结构，来快速定位到 quicklist 的链表头和链表尾。此外，quicklist 中还定义了 quicklistNode 的个数、所有 ziplist 的总元素个数等属性。quicklist 的结构定义如下所示

然后，从 quicklistNode 和 quicklist 的结构体定义中，我们就能画出下面这张 quicklist 的示意图。

listpack

listpack 也叫紧凑列表，它的特点就是用一块连续的内存空间来紧凑地保存数据，同时为了节省内存空间，listpack 列表项使用了多种编码方式，来表示不同长度的数据，这些数据包括整数和字符串。和 listpack 相关的实现文件是listpack.c，头文件包括listpack.h和listpack_malloc.h。

我们先来看下 listpack 的创建函数 lpNew，因为从这个函数的代码逻辑中，我们可以了解到 listpack 的整体结构。lpNew 函数创建了一个空的 listpack，一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中，它默认是 6 个字节，其中 4 个字节是记录 listpack 的总字节数，2 个字节是记录 listpack 的元素数量。此外，listpack 的最后一个字节是用来标识 listpack 的结束，其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样，LP_EOF 的值也是 255。

整体结构如下：

和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样，保存其前一个列表项的长度，它只会包含三个方面内容，分别是当前元素的编码类型（entry-encoding）、元素数据 (entry-data)，以及编码类型和元素数据这两部分的长度 (entry-len)。

总结

Redis 内部是由一系列对象组成的，字符串对象、列表对象、哈希表对象、集合对象有序集合对象。
字符串对象是唯一一个可以应用在上面所以对象中的，所以我们看到向一些 keys exprice 这种命令可以在针对所有 key 使用，因为所有 key 都是采用的字符串对象。 列表对象默认使用压缩列表为底层实现，当对象保存的元素数量大于 512 个或者是长度大于64字节的时候会转换为双端链表。
哈希对象也是优先使用压缩列表键值对在压缩列表中连续储存着，当对象保存的元素数量大于 512 个或者是长度大于64字节的时候会转换为哈希表。
集合对象可以采用整数集合或者哈希表，当对象保存的元素数量大于 512 个或者是有元素非整数的时候转换为哈希表。
有序集合默认采用压缩列表，当集合元素数量大于 128 个或者是元素成员长度大于 64 字节的时候转换为跳跃表。