GroupBlog

移步掘金：Redis–数据存储设计与实现

0 引言

本篇博客是对“黄健宏先生-《Redis设计与实现》”一书中第一章内容的梳理与总结，如果想要了解更多更详尽的内容，还请大家翻阅此书。

1 思维导图

2 一切皆对象

Redis 使用键值对的格式存储数据，并且键和值都以对象（Redis Object）来表示。所有的键对象都是字符串对象，而值对象则分为思维导图中的 5 种。

3 字符串对象

字符串对象是指数据库键所对应的值是字符串对象（即用来存储字符串）。Redis 共有 3 种字符串对象的实现方式。

3.1 底层实现之整数值对象

如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 来表示，则字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面（将 void* 转换成 long）。

3.2 底层实现之简单动态字符串

如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于 44 字节，那么字符串对象将使用简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为 raw。本文最后会对 SDS 进行一个简单的介绍。

3.3 底层实现之embstr

如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于 44 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。本文最后会对 embstr 进行一个简单的介绍。

P.S.：用 float、double 表示的浮点数在 Redis 中是作为字符串值来保存的。如果要保存一个浮点数，程序会先将浮点数转换为字符串，然后再保存。

3.4 编码的转换

整数值对象和 embstr 编码的对象在一定条件下会被转换成 SDS 编码的对象。

对于整数值对象来说，如果这个对象执行了一些操作，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串编码将由整数值对象变为 SDS。

embstr 编码的字符串对象在 Redis 中是只读的，因此当对 embstr 编码的字符串执行任何修改命令时，程序都会先将 embstr 字符串转为 SDS，然后再执行修改命令，因此在对 embstr 字符串对象执行修改后，其总会变成一个 SDS 的字符串对象。

4 列表对象

列表对象的编码可以是压缩列表或者双端链表。对于双端链表不再介绍，本文最后会对压缩列表进行一个简单的介绍。

4.1 编码的转换

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

保存的所有字符串元素都小于 64 字节
列表保存的元素数量小于 512 个

zipList 与 linkedList 的最大区别就是 zipList 不存储指向上一个节点和指向下一个节点的指针，而是存储的上一个节点的长度以及当前节点的长度，牺牲了部分读写性能来换取高效的内存利用率，是一种典型的时间换空间的思想。

在 Redis 3.2 版本后，列表的底层统一采用 quickList 实现。

5 哈希对象

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

5.1 底层实现之ziplist

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

哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节（不会引起连锁更新）
哈希对象保存的键值对数量小于 512 个

对于使用 ziplist 编码的哈希对象来说，当使用 ziplist 编码所需的两个条件中的任意一个不能被满足的时候，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有键值对都会被转移并保存到字典里。

举个栗子，创建一个 ziplist 作为哈希键的值：

redis> HSET profile name 'Tom'
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career 'Programmer'
(integer) 1

profile 键的值对象将如下图所示：

如上图所示，当使用 ziplist 作为哈希对象的底层实现时，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。

当哈希对象使用 ziplist 作为底层实现时，考虑增删改查对应的时间复杂度（这里只是对各操作时间复杂度的主观判断，不代表 Redis 就是这样实现的）：

增加节点：O(n)，由于增加节点的过程中需要对 ziplist 进行遍历以判断是否已存在新增节点，因此时间复杂度为 O(n)
删除节点：O(n)，首先需要定位到待删除节点，然后进行内存移位，覆盖待删除节点的数据，最后进行内存重分配，收缩多余空间
修改节点、查找节点：O(n)，同增加节点操作

5.2 底层实现之dict

详见 8.4 字典（dict）。

6 集合对象

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

关于 intset 的介绍详见 8.5 整数集合（intSet）。

当 hashtable 作为集合对象的底层实现时，字典的每个键都是一个字符串，每个字符串就代表一个集合元素，而字典的值则全部被设置为 NULL。

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

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

7 有序集合对象

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

7.1 底层实现之ziplist

使用 ziplist 的有序集合对象，每个集合元素使用两个紧挨在一起的压缩列表节点保存，第一个节点保存元素的成员，第二个元素保存元素的分值。压缩列表内的集合元素按分值从小到大排序。

考虑使用 ziplist 的有序集合对象增删改查的时间复杂度（时间换空间）：

增：O(n)，元素定位需要 O(n)，元素移位需要 O(n)
删：O(n)，元素定位需要 O(n)，元素移位需要 O(n)
改：O(n)，元素定位需要 O(n)
查：O(n)，元素定位需要 O(n)

7.2 底层实现之skiplist

skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个 zset 同时包含一个字典和一个跳表：

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

zsl 按分值从小到大保存了集合的所有元素，每个跳表节点都保存了一个集合元素。dict 为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：键保存元素的成员，值保存了元素的分值。虽然 zset 结构同时使用跳表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳表和字典也不会产生任何重复成员或分值，因此不会浪费额外的内存。

有序集合同时使用跳表和字典两种数据结构，提高了部分性能。举个栗子，如果只使用字典来实现有序集合，那么虽然元素的读写性能为 O(1)，但是字典会以无序的方式来保存集合元素，所以每次在执行范围型操作（ZRANK，ZRANGE）时，程序需要先对字典保存的元素进行排序，完成这种排序至少需要 O(NlogN) 时间复杂度，以及额外的 O(n) 内存空间（需要创建一个数组来保存排序后的元素）；另一方面，如果只使用跳表来实现有序集合，虽然执行范围型操作的所有优点都会被保留，但根据成员查到对应分值这一操作的时间复杂度将上升至 O(logN)。因此为了让有序集合的查找和范围操作都尽可能快的执行，Redis 选择了同时使用两种数据结构来实现有序集合。

7.3 编码的转换

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

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

不能同时满足以上两个条件的有序集合将使用 skiplist 编码。

8 Redis底层数据结构简要介绍

8.1 简单动态字符串（SDS）

8.1.1 定义

Redis 使用如下数据结构表示一个 SDS：

struct sdshdr {
   
    // buf 已占用长度 = SDS 所保存字符串的长度
    int len;
    // buf 剩余可用长度
    int free;
    // 实际保存字符串数据的地方
    char buf[];
};

8.1.2 SDS与C字符串的区别

SDS 更能满足 Redis 对字符串在安全性、效率以及功能方面的要求，主要表现为以下几个方面：

SDS 获取字符串长度，时间复杂度为 (O)1，获取 C 字符串长度为 (O)n
杜绝缓存区溢出
- C 字符串在进行字符串拼接（strcat 函数）时，会默认你已经给需要拼接的字符串（dest）分配了足够多的内存，可以容纳 src 字符串中的所有内容，一旦这个假定不成立，就会产生缓存区溢出。而由于 SDS 维护了 free 属性，因此在进行字符串拼接时 SDS 会检查未使用的空间是否满足修改所需的要求，如果不满足的话，SDS 会自动将空间扩展至执行修改所需的大小，因此杜绝了缓存区溢出
减少修改字符串时带来的内存重分配次数
- 空间预分配：当扩展后的字符串长度（len 的值）小于 1MB，那么程序分配和 len 属性同样大小的未使用空间（free = len）；当扩展后的字符串长度大于等于 1MB，那么程序直接分配 1MB 的未使用空间。通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数
- 惰性空间释放：当需要缩短字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，等待将来使用。通过惰性空间释放策略，SDS 避免了缩短字符串所需的内存重分配操作，并为将来可能有的增长操作提供了优化

8.2 embstr

embstr 编码是专门用于保存短字符串的一种优化编码方式，也是使用 redisObject 以及 SDS 来表示字符串对象。

与 raw 编码（SDS）不同的是，raw 编码会调用两次内存分配函数来分别创建 redisObject 结构与 SDS 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含 redisObject 和 SDS 两个结构，如下图：

使用 embstr 编码的字符串对象来保存短字符串有如下好处：

创建 / 释放字符串对象，相比 raw 编码方式，少一次内存分配 / 释放次数
连续的存储空间可以更好的利用缓存带来的优势（连续的数据块访问会比散列的访问速度更快，并且使用 embstr 可以直接命中 CPU cache，少了物理内存的索引查询及访问）

8.3 压缩列表（zipList）

$\color{red}{问题：}$

$\color{red}{压缩列表中的节点如果发生更新的话，会引起连锁更新的问题么？还是说压缩列表只支持增删查，不支持改操作？}$

8.3.1 压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或一个整数值。

下图展示了一个 zipList 的典型分布结构：

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                         ZIPLIST_ENTRY_TAIL

图中各个域的作用如下：

域	类型	长度	用途
zlbytes	uint32_t	4 字节	整个 zipList 占用的内存字节数，对 zipList 进行内存重分配，或者计算 zlend 的位置时使用
zltail	uint32_t	4 字节	到达 zipList 表尾节点的偏移量。通过这个偏移量，可以在不遍历整个 zipList 的前提下，弹出表尾节点
zllen	uint16_t	2 字节	zipList 中节点的数量。当这个值小于 UINT16_MAX（65535）时，这个值就是 zipList 中节点的数量；当这个值等于 UINT16_MAX 时，节点的数量需要遍历整个 zipList 才能计算得出
entryN	列表节点	不定	zipList 所保存的节点，各个节点的长度根据内容而定
zlend	uint8_t	1 字节	255 的二进制值 1111 1111（UINT8_MAX），用于标记 zipList 的末端

因为 ziplist header 部分的长度是固定的（4 字节 + 4 字节 + 2 字节），因此将指针移动到表头节点的复杂度为常数时间；除此之外，因为表尾节点的地址可以通过 zltail 计算得出，因此将指针移动到表尾节点的复杂度也为常数时间。

8.3.2 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值，关于可保存的字节数组以及整数值的长度，这里不再赘述。

每个压缩列表节点都由 previous_entry_length、encoding、length、content 四部分组成。

area        |<------------------- entry -------------------->|

            +------------------+----------+--------+---------+
component   | pre_entry_length | encoding | length | content |
            +------------------+----------+--------+---------+

8.3.2.1 previous_entry_length

pre_entry_length 记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。

area        |<---- previous entry --->|<--------------- current entry ---------------->|

                                                         |<--- 1/2/5 byte -->|
size          5 bytes                   1 byte             ?          ?        ?
            +-------------------------+-----------------------------+--------+---------+
component   | ...                     | pre_entry_length | encoding | length | content |
            |                         |                  |          |        |         |
value       |                         | 0000 0101        |    ?     |   ?    |    ?    |
            +-------------------------+-----------------------------+--------+---------+
            ^                         ^
address     |                         |
            p = e - 5                 e

根据编码方式的不同，pre_entry_length 域可能占用 1 字节或者 5 字节：

1 字节：如果前一节点的长度小于 254 字节，便使用一个字节保存它的值
5 字节：如果前一节点的长度大于等于 254 字节，那么将第 1 个字节的值设为 254，然后用接下来的 4 个字节保存实际长度

8.3.2.2 encoding和length

encoding 和 length 两部分一起决定了 content 部分所保存的数据类型及长度。encoding 和 length 实际上可以理解为一个域，这个域中的前两个 bit 位表示 encoding，余下的 bit 位表示 length。

encoding 的值可以是 00、01、10 和 11：

00、01 和 10 表示 content 部分保存着字符数组
11 表示 content 部分保存着整数

encoding 与 length 完整的编码形式如下（encoding 与 length 域所占的字节数并不固定）：

编码	编码长度	content 内容
00bbbbbb	1 byte	长度小于等于 63 字节的字符数组
01bbbbbb xxxxxxxx	2 byte	长度小于等于 16383 字节的字符数组
10____ aaaaaaaa bbbbbbbb cccccccc dddddddd	5 byte	长度小于等于 4294967295 的字符数组
11000000	1 byte	int16_t 类型的整数
…	…	…

表格中的下划线 _ 表示留空，而变量 a、b、c、d、x 等则代表 0、1 bit 位（二进制值）。为了方便阅读，多个字节之间用空格隔开。

8.3.2.3 content

content 部分保存着节点的内容，类型和长度由 encoding 和 length 决定。以下是一个保存着字符数组 hello world 的节点的例子：

area      |<---------------------- entry ----------------------->|

size        ?                  2 bit      6 bit    11 byte
          +------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       |
          |                  |          |        |               |
value     | ?                |    00    | 001011 | hello world   |
          +------------------+----------+--------+---------------+

encoding 域的值 00 表示节点保存着一个长度小于等于 63 字节的字符数组，length 域给出了这个字符数组的准确长度——11 字节（二进制 001011），content 则保存着字符数组 hello world 本身（为了方便表示，content 部分使用字符而不是二进制表示）。

8.3.3 连锁更新

关于压缩列表的增删改查操作不再赘述，压缩列表中有详细介绍。需要考虑的是这样一种插入场景：将一个新节点添加到某个/某些节点的前面。

举个例子，假设要将一个新节点 new 添加到节点 prev 和 next 之间，程序的操作步骤应如下：

1.在插入前计算新插入节点的大小，对原有 ziplist 进行内存重分配

+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |
|   prev   |   ???    |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+

           |<-------->|
              expand
              space

2.设置 new 节点的值，并将其插入到指定的位置，这里的时间复杂度为(O)n

             set value,
             property,
             length,
             etc.
                |
                v
+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |
|   prev   |   new    |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+

执行完插入操作后的 ziplist 如上图。这里需要考虑一个问题，虽然插入了 new 节点，但 next 节点的 pre_entry_length 域编码的仍然是 prev 节点的长度，所以程序需要将 new 节点的长度编码进 next 节点的 pre_entry_length 域里，此时会出现三种可能：

next 的 pre_entry_length 域的长度正好能够编码 new 的长度
next 的 pre_entry_length 只有 1 字节长，但编码 new 的长度需要 5 字节
next 的 pre_entry_length 有 5 字节长，但编码 new 的长度只需要 1 字节

对于情况 1 和 3，程序直接更新 next 的 pre_entry_length 域。然而，因为 next 的空间长度改变了，所以程序又必须检查 next 的后继节点——next + 1，看它的 pre_entry_length 能否编码 next 的新长度，如果不能的话，程序又需要继续对 next + 1 进行扩容……（以此类推）

也就是说，在某个/某些节点的前面添加新节点之后，程序必须沿着路径挨个检查后续的节点，是否满足新长度的编码要求，直到遇到一个能满足要求的节点（如果有一个能满足，则这个节点之后的其他节点也满足），或者到达 ziplist 的末端 zlend 为止，这种检查操作的复杂度为 $O(N^2)$ 。

不过，因为只有在新添加节点的后面有连续多个长度接近 254 的节点时，这种连锁更新才会发生，所以可以普遍地认为，这种连锁更新发生的概率非常小，在一般情况下，将添加操作看成是 O(N) 复杂度也是可以的。

P.S.：在第三种情况中，程序实际上是可以执行类似于情况二的动作的。它可以挨个地检查新节点之后的节点，尝试收缩它们的空间长度，不过 Redis 决定不这么做，因为在一些情况下，比如前面提到的，有连续多个长度接近 254 的节点时，可能会出现重复的扩展——收缩——再扩展——再收缩的抖动（flapping）效果，这会让操作的性能变得非常差。

8.4 字典（dict）

Redis 中的字典相比普通的哈希表有许多独特的设计之处，因此这里需要单拎出来讲一下，但不详细展开，只记录重点。

上图表示了 Redis 中一个普通状态下（没有进行 rehash）的字典。

因为 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新的节点添加到链表的表头位置，时间复杂度为 O(1)。

8.4.1 rehash

Redis 对字典执行 rehash 的步骤如下：

为字典的 ht[1] 哈希表分配空间，如果是扩展操作，则大小为第一个大于等于 ht[0].used*2 的 2 的 n 次方幂；如果是收缩操作，那么 ht[1].size 为第一个大于等于 ht[0].used 的 2 的 n 次方幂
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面
当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备

需要注意的一点是，Redis 会在 BGSAVE 命令或 BGREWRITEAOF 命令正在执行期间，提高 rehash 的负载因子。这是因为在执行 BGSAVE 或 BGREWRITEAOF命令时，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高 rehash 的负载因子，从而尽可能的避免在子进程存在期间进行 rehash 操作，避免不必要的内存写入，最大限度的节约内存。

8.4.2 渐进式rehash

Redis 的 rehash 并不是一次性的、集中式的完成，而是分多次、渐进式的完成。

如果 ht[0] 里只保存着 4 个键值对，那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1]；但是如果哈希表保存的键值对数量不是四个，而是四亿个，那么要一次性将这些键值对全部 rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

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

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

下图展示了一次完整的渐进式 rehash 过程，注意观察在整个 rehash 过程中，字典的 rehashidx 是如何变化的。

1.准备开始 rehash：

2.rehash 索引 0 上的键值对：

3.rehash 索引 1 上的键值对：

4.rehash 索引 2 上的键值对：

5.rehash 索引 3 上的键值对：

6.rehash 执行完毕：

在渐进式 rehash 的过程中，如果要在字典里查找一个键，会先在 ht[0] 里面查找，如果没找到会继续到 ht[1] 里面进行查找。另外，在渐进式 rehash 的过程中，新添加的键值对只会被保存在 ht[1] 中，ht[0] 不会再进行任何添加操作，因此 ht[0] 中的键值对数量会只减不增，最终随着 rehash 的操作而变成空表。