Redis入门2-底层结构

Redis Comments

前面描述了底层数据结构，与之对应的底层数据结构实现：

img

简单动态字符串

Redis 自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。SDS是一种可以被修改的字符串

当执行命令：

1
2
redis> SET msg "hello world"
OK

Redis 将在数据库中创建了一个新的键值对，其中：

  • 键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串 "msg" 的 SDS 。
  • 键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串 "hello world" 的 SDS 。

除了用来保存数据库中的字符串值之外，AOF 模块中的 AOF 缓冲区，以及客户端状态中的输入缓冲区，都是由 SDS 实现的

SDS定义

每个 sds.h/sdshdr 结构表示一个 SDS 值：

1
2
3
4
5
6
7
8
9
struct sdshdr {     
  // 记录 buf 数组中已使用字节的数量    
  // 等于 SDS 所保存字符串的长度    
  int len;     
  // 记录 buf 数组中未使用字节的数量   
  int free;     
  // 字节数组，用于保存字符串    
  char buf[]; 
};
  • free 属性的值为 0 ，表示这个 SDS 没有分配任何未使用空间。
  • len 属性的值为 5 ，表示这个 SDS 保存了一个五字节长的字符串。
  • buf 属性是一个 char 类型的数组，数组的前五个字节分别保存了 'R' 、 'e' 、 'd' 、 'i' 、 's' 五个字符，而最后一个字节则保存了空字符 '\0' 。

img

SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面，并且为空字符分配额外的 1 字节空间，以及添加空字符到字符串末尾等操作都是由 SDS 函数自动完成的，这个空字符对于 SDS 的使用者来说是完全透明的。

遵循空字符结尾这一惯例的好处是，SDS 可以直接重用一部分 C 字符串函数库里面的函数。

举个例子，如果我们有一个指向图 2-1 所示 SDS 的指针 s ，那么我们可以直接使用 stdio.h/printf 函数，通过执行以下语句：

  • 这个 SDS 和之前展示的 SDS 一样，都保存了字符串值 "Redis" 。
  • 这个 SDS 和之前展示的 SDS 的区别在于，这个 SDS 为 buf 数组分配了五字节未使用空间，所以它的 free 属性的值为 5（图中使用五个空格来表示五字节的未使用空间）
img

其中 保存空字符的 1 字节空间不计算在 SDS 的 len 和 free 属性里面

SDS与C字符串的区别

C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组的最后一个元素总是空字符 '\0' 。

比如说，图 2-3 就展示了一个值为 "Redis" 的 C 字符串

C 语言使用的这种简单的字符串表示方式，并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求，接下来将说明 SDS 比 C 字符串更适用于 Redis 的原因

常数复杂度获取字符串长度

因为 C 字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为 O(N) 。

举个例子，图 2-4 展示了程序计算一个 C 字符串长度的过程

和 C 字符串不同，因为 SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为 O(1) 。

举个例子，对于图 2-5 所示的 SDS 来说，程序只要访问 SDS 的 len 属性，就可以立即知道 SDS 的长度为 5 字节：

又比如说，对于图 2-6 展示的 SDS 来说，程序只要访问 SDS 的 len 属性，就可以立即知道 SDS 的长度为 11 字节。

设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的，使用 SDS 无须进行任何手动修改长度的工作。

通过使用 SDS 而不是 C 字符串，Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ，即使对一个非常长的字符串键反复执行 STRLEN 命令，也不会对系统性能造成任何影响，因为 STRLEN 命令的复杂度仅为 O(1)

杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外，C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出 (buffer overflow)

举个例子，<string.h>/strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾：

1
char *strcat(char *dest, const char *src);

因为 C 字符串不记录自身的长度，所以 strcat 假定用户在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出。

举个例子，假设程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2 ，其中 s1 保存了字符串 "Redis" ，而 s2 则保存了字符串 "MongoDB" ，如图 2-7 所示

如果一个程序员决定通过执行：

1
strcat(s1, " Cluster");

将 s1 的内容修改为 "Redis Cluster" ，但粗心的他却忘了在执行 strcat 之前为 s1 分配足够的空间，那么在 strcat 函数执行之后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改，如图 2-8 所示

与 C 字符串不同，SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。

举个例子，SDS 的 API 里面也有一个用于执行拼接操作的 sdscat 函数，它可以将一个 C 字符串拼接到给定 SDS 所保存的字符串的后面，但是在执行拼接操作之前，sdscat 会先检查给定 SDS 的空间是否足够，如果不够的话，sdscat 就会先扩展 SDS 的空间，然后才执行拼接操作

比如说，如果我们执行：

1
sdscat(s, " Cluster");

其中 SDS 值 s 如图 2-9 所示，那么 sdscat 将在执行拼接操作之前检查 s 的长度是否足够，在发现 s 目前的空间不足以拼接 " Cluster" 之后，sdscat 就会先扩展 s 的空间，然后才执行拼接 " Cluster" 的操作，拼接操作完成之后的 SDS 如图 2-10 所示。

注意图 2-10 所示的 SDS ：sdscat 不仅对这个 SDS 进行了拼接操作，它还为 SDS 分配了 13 字节的未使用空间，并且拼接之后的字符串也正好是 13 字节长，分配的空间 SDS 的空间分配策略有关

减少修改带来的内存重分配次数

正如前两个小节所说，因为 C 字符串并不记录自身的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）。

因为 C 字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个 C 字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作：

  • 如果是增长字符串的操作，比如拼接操作(append)，那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小 ——如果忘了这一步就会产生缓冲区溢出。
  • 如果是缩短字符串的操作，比如截断操作(trim)，那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间 ——如果忘了这一步就会产生内存泄漏。

问题1：如果是分配，那么每次分配多少呢?

问题2：如果是释放不再使用的空间，那么什么时候释放呢，或者使用什么策略？

举个例子，如果我们持有一个值为 "Redis" 的 C 字符串 s ，那么为了将 s 的值改为 "Redis Cluster" ，在执行：

1
strcat(s, " Cluster");

之前，我们需要先使用内存重分配操作，扩展 s 的空间。

之后，如果我们又打算将 s 的值从 "Redis Cluster" 改为 "Redis Cluster Tutorial" ，那么在执行：

1
strcat(s, " Tutorial");

之前，我们需要再次使用内存重分配扩展 s 的空间，诸如此类。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作：

  • 在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的。
  • 但是 Redis 作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，如果这种修改频繁地发生的话，可能还会对性能造成影响。

为了避免 C 字符串的这种缺陷，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联：在 SDS 中，buf 数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录。

通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略

空间预分配

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

额外分配的未使用空间数量由以下公式决定：

  • 如果对 SDS 进行修改之后，SDS 的长度（也即是 len 属性的值）将小于 1 MB ，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS len 属性的值将和 free 属性的值相同。举个例子，如果进行修改之后，SDS 的 len 将变成 13 字节，那么程序也会分配 13 字节的未使用空间，SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
  • 如果对 SDS 进行修改之后，SDS 的长度将大于等于 1 MB ，那么程序会分配 1 MB 的未使用空间。举个例子，如果进行修改之后，SDS 的 len 将变成 30 MB ，那么程序会分配 1 MB 的未使用空间，SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

举个例子，对于图 2-11 所示的 SDS 值 s 来说，如果我们执行：

1
sdscat(s, " Cluster");

那么 sdscat 将执行一次内存重分配操作，将 SDS 的长度修改为 13 字节，并将 SDS 的未使用空间同样修改为 13 字节，如图 2-12 所示。

如果这时，我们再次对 s 执行：

1
sdscat(s, " Tutorial");

那么这次 sdscat 将不需要执行内存重分配：因为未使用空间里面的 13 字节足以保存 9 字节的 " Tutorial" ，执行 sdscat 之后的 SDS 如图 2-13 所示

在扩展 SDS 空间之前，SDS API 会先检查未使用空间是否足够，如果足够的话，API 就会直接使用未使用空间，而无须执行内存重分配。

通过这种预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

惰性空间释放

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

举个例子，sdstrim 函数接受一个 SDS 和一个 C 字符串作为参数，从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。

比如对于图 2-14 所示的 SDS 值 s 来说，执行：

1
sdstrim(s, "XY");   // 移除 SDS 字符串中的所有 'X' 和 'Y'

会将 SDS 修改成图 2-15 所示的样子

注意执行 sdstrim 之后的 SDS 并没有释放多出来的 8 字节空间，而是将这 8 字节空间作为未使用空间保留在了 SDS 里面，如果将来要对 SDS 进行增长操作的话，这些未使用空间就可能会派上用场。

举个例子，如果现在对 s 执行：

1
sdscat(s, " Redis");

那么完成这次 sdscat 操作将不需要执行内存重分配：因为 SDS 里面预留的 8 字节空间已经足以拼接 6 个字节长的 " Redis" ，如图 2-16 所示。

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

什么时候或者有什么接口进行内存释放

二进制安全

C 字符串中的字符必须符合某种编码（比如 ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾 ——这些限制使得 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

有个问题：到底是怎么存进去并计算长度的

如果是先计算长度，然后再存进去，那么可能出现长度误判，导致整体长度不够的情况

如果是先存进去再计算长度(不可能，需要先分配空间)

原来它用的是二进制数据？

举个例子，如果有一种使用空字符来分割多个单词的特殊数据格式，如图 2-17 所示，那么这种格式就不能使用 C 字符串来保存，因为 C 字符串所用的函数只会识别出其中的 "Redis" ，而忽略之后的 "Cluster" 。

虽然数据库一般用于保存文本数据，但使用数据库来保存二进制数据的场景也不少见，因此，为了确保 Redis 可以适用于各种不同的使用场景，SDS 的 API 都是二进制安全的(binary-safe): 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设 ——数据在写入时是什么样的，它被读取时就是什么样。

将 SDS 的 buf 属性称为字节数组的原因 ——Redis 不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

比如说，使用 SDS 来保存之前提到的特殊数据格式就没有任何问题，因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，如图 2-18 所示

通过使用二进制安全的 SDS ，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据

兼容部分C函数

虽然 SDS 的 API 都是二进制安全的，但它们一样遵循 C 字符串以空字符结尾的惯例：这些 API 总会将 SDS 保存的数据的末尾设置为空字符，并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符，这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。

举个例子，如图 2-19 所示，如果我们有一个保存文本数据的 SDS 值 sds ，那么我们就可以重用 <string.h>/strcasecmp 函数，使用它来对比 SDS 保存的字符串和另一个 C 字符串：

1
strcasecmp(sds->buf, "hello world");

这样 Redis 就不用自己专门去写一个函数来对比 SDS 值和 C 字符串值了。

与此类似，我们还可以将一个保存文本数据的 SDS 作为 strcat 函数的第二个参数，将 SDS 保存的字符串追加到一个 C 字符串的后面：

1
strcat(c_string, sds->buf);

这样 Redis 就不用专门编写一个将 SDS 字符串追加到 C 字符串之后的函数了。

通过遵循 C 字符串以空字符结尾的惯例，SDS 可以在有需要时重用 <string.h> 函数库，从而避免了不必要的代码重复。

总结

C 字符串 SDS
获取字符串长度的复杂度为 O(N) 。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。 API 是安全的，不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。 修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。 可以使用一部分 <string.h> 库中的函数。

接口实现：https://www.cnblogs.com/yinbiao/p/10740212.html

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis 服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（output buffer）

链表和链表节点的实现

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

1
2
3
4
5
6
7
8
typedef struct listNode {     
  // 前置节点    
  struct listNode *prev;     
  // 后置节点    
  struct listNode *next;     
  // 节点的值    
  void *value;
} listNode;

多个 listNode 可以通过 prev 和 next 指针组成双端链表，如图 3-1 所示

虽然仅仅使用多个 listNode 结构就可以组成链表，但使用 adlist.h/list 来持有链表的话，操作起来会更方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct list {
    // 表头节点
    listNode *head;
 
    // 表尾节点
    listNode *tail;
 
    // 链表所包含的节点数量
    unsigned long len;
  
    // 节点值复制函数
    void *(*dup)(void *ptr);
  
    // 节点值释放函数
    void (*free)(void *ptr);
  
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

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

  • dup 函数用于复制链表节点所保存的值；
  • free 函数用于释放链表节点所保存的值；
  • match 函数则用于对比链表节点所保存的值和另一个输入值是否相等

图 3-2 是由一个 list 结构和三个 listNode 结构组成的链表：

Redis 的链表实现的特性可以总结如下：

  • 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
  • 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ，对链表的访问以 NULL 为终点。
  • 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
  • 带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1) 。
  • 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

总结

  • 链表被广泛用于实现 Redis 的各种功能，比如列表键，发布与订阅，慢查询，监视器，等等。
  • 每个链表节点由一个 listNode 结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以 Redis 的链表实现是双端链表。
  • 每个链表使用一个 list 结构来表示，这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ，所以 Redis 的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数，Redis 的链表可以用于保存各种不同类型的值。

字典

在字典中，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值），这些关联的键和值就被称为键值对。

举个例子，当执行命令：

1
2
redis> SET msg "hello world"
OK

在数据库中创建一个键为 "msg" ，值为 "hello world" 的键值对时，这个键值对就是保存在代表数据库的字典里面的。

除了用来表示数据库之外，字典还是哈希键的底层实现之一：当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现。

举个例子，website 是一个包含 10086 个键值对的哈希键，这个哈希键的键都是一些数据库的名字，而键的值就是数据库的主页网址：

1
2
3
4
5
6
7
8
9
redis> HLEN website(integer) 10086 
redis> HGETALL website
1) "Redis"
2) "Redis.io"
3) "MariaDB"
4) "MariaDB.org"
5) "MongoDB"
6) "MongoDB.org"
# ...

website 键的底层实现就是一个字典，字典中包含了 10086 个键值对：

  • 其中一个键值对的键为 "Redis" ，值为 "Redis.io" 。
  • 另一个键值对的键为 "MariaDB" ，值为 "MariaDB.org" ；
  • 还有一个键值对的键为 "MongoDB" ，值为 "MongoDB.org" ；

除了用来实现数据库和哈希键之外，Redis 的不少功能也用到了字典，在后续的章节中会不断地看到字典在 Redis 中的各种不同应用

字典的实现

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

接下来的三个小节将分别介绍 Redis 的哈希表、哈希表节点、以及字典的实现

Hash表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht {
 
    // 哈希表数组
    dictEntry **table;
 
    // 哈希表大小
    unsigned long size;
 
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
 
    // 该哈希表已有节点的数量
    unsigned long used;
 
} dictht;

table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小，也即是 table 数组的大小，而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

sizemask 属性的值总是等于 size - 1 ，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

图 4-1 展示了一个大小为 4 的空哈希表（没有包含任何键值对）

字典的实现 - 图1

哈希表节点

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry {
 
    // 键
    void *key;
 
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
 
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
 
} dictEntry;

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

next 属性是指向另一个哈希表节点的指针，可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题

举个例子，图 4-2 就展示了如何通过 next 指针，将两个索引值相同的键 k1 和 k0 连接在一起。

字典的实现 - 图2

字典
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {
 
    // 类型特定函数
    dictType *type;
 
    // 私有数据
    void *privdata;
 
    // 哈希表
    dictht ht[2];
 
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
 
} dict;

type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的：

  • type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
  • 而 privdata 属性则保存了需要传给那些类型特定函数的可选参数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct dictType {
 
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
 
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
 
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
 
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
 
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
 
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
 
} dictType;

ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外，另一个和 rehash 有关的属性就是 rehashidx ：它记录了 rehash 目前的进度，如果目前没有在进行 rehash ，那么它的值为 -1 。

图 4-3 展示了一个普通状态下（没有进行 rehash）的字典

字典的实现 - 图3

Hash算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

Redis 计算哈希值和索引值的方法如下：

1
2
3
4
5
6
# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
 
# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

哈希算法 - 图1

举个例子，对于图 4-4 所示的字典来说，如果我们要将一个键值对 k0 和 v0 添加到字典里面，那么程序会先使用语句：

1
hash = dict->type->hashFunction(k0);

计算键 k0 的哈希值。

假设计算得出的哈希值为 8 ，那么程序会继续使用语句：

1
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;

计算出键 k0 的索引值 0 ，这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上，如图 4-5 所示。

哈希算法 - 图2

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。

MurmurHash 算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

MurmurHash 算法目前的最新版本为 MurmurHash3 ，而 Redis 使用的是 MurmurHash2 ，关于 MurmurHash 算法的更多信息可以参考该算法的主页：http://code.google.com/p/smhasher/ 。

解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，称这些键发生了冲突（collision）。

Redis 的哈希表使用链地址法（separate chaining）来解决键冲突：每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。

举个例子，假设程序要将键值对 k2 和 v2 添加到图 4-6 所示的哈希表里面，并且计算得出 k2 的索引值为 2 ，那么键 k1 和 k2 将产生冲突，而解决冲突的办法就是使用 next 指针将键 k2 和 k1 所在的节点连接起来，如图 4-7 所示。

解决键冲突 - 图1

解决键冲突 - 图2

因为 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为 O(1)），排在其他已有节点的前面

链表使用的是双向链表所以可以直接添加到链表结尾，但是字典的链表中并只有一个指向next的指针，所以如果发生hash冲突，则直接添加到链表头部

rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

负载因子是什么时候定义的，怎么去判断什么时候去rehash呢？

rehash过程中会停掉插入和获取吗，新来的值怎么办？ 查询的时候会同时查询 hash[0] 和 hash[1] 吗

扩展和收缩哈希表的工作可以通过执行 rehash （重新散列）操作来完成，Redis 对字典的哈希表执行 rehash 的步骤如下：

  • 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也即是 ht[0].used属性的值）：

    • 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
    • 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。

  • 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。

  • 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），释放 ht[0] ，将 ht[1] 设置为 ht[0] ，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。 举个例子，假设程序要对图 4-8 所示字典的 ht[0] 进行扩展操作，那么程序将执行以下步骤：

    rehash - 图1

  • ht[0].used 当前的值为 4 ，4 * 2 = 8 ，而 8 （2^3）恰好是第一个大于等于 4 的 2 的 n 次方，所以程序会将 ht[1] 哈希表的大小设置为 8 。图 4-9 展示了 ht[1] 在分配空间之后，字典的样子。

    rehash - 图2

  • 将 ht[0] 包含的四个键值对都 rehash 到 ht[1] ，如图 4-10 所示。

    rehash - 图3

  • 释放 ht[0] ，并将 ht[1] 设置为 ht[0] ，然后为 ht[1] 分配一个空白哈希表，如图 4-11 所示。 至此，对哈希表的扩展操作执行完毕，程序成功将哈希表的大小从原来的 4 改为了现在的 8 。

    rehash - 图4

hash表的拓展和收缩

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

  • 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1 ；
  • 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5 ； 其中哈希表的负载因子可以通过公式：
1
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小load_factor = ht[0].used / ht[0].size

计算得出。比如说，这个哈希表的负载因子为：

1
2
3
4
5
# 对于一个大小为 `4` ，包含 `4` 个键值对的哈希表来说
load_factor = 4 / 4 = 1

# 对于一个大小为 `512` ，包含 `256` 个键值对的哈希表来说
load_factor = 256 / 512 = 0.5

根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同

因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存

渐进式rehash

扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面，但rehash 动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。原因在于，如果哈希表里保存大量键值对，要一次性将这些键值对全部 rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

以下是哈希表渐进式 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 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量

同时在两个ht都存在数据，那么 增删改查 在哪个进行操作的，怎么判断哪个ht才是目的地

图 4-12 至图 4-17 展示了一次完整的渐进式 rehash 过程，注意观察在整个 rehash 过程中，字典的 rehashidx 属性是如何变化的

渐进式 rehash - 图1

渐进式 rehash - 图2

渐进式 rehash - 图3

渐进式 rehash - 图4

渐进式 rehash - 图5

渐进式 rehash - 图6

渐进式 rehash 执行期间的哈希表操作

因为在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行：比如说，要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。

另外，在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作：这一措施保证了 ht[0] 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表

总结

  • 字典被广泛用于实现 Redis 的各种功能，其中包括数据库和哈希键。

  • Redis 中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个用于平时使用，另一个仅在进行 rehash 时使用。

  • 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。

  • 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。

  • 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面，并且这个 rehash 过程并不是一次性地完成的，而是渐进式地完成的

跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点

为什么使用跳表而不是平衡树

  1. 平衡树的操作比跳表更加的复杂
  2. 平衡树的插入与删除需要子树的调整，而跳表只需要删除相邻节点
  3. 平衡树每个节点包含2个指针(左右子树)，而跳表每个节点包含的指针数平均为1/(1-p)，p表示的是密度
  4. 查找单个key的平均时间复杂度都是O(logn)

Redis 使用跳跃表作为有序集合键的底层实现之一：如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合键的底层实现。

举个例子，fruit-price 是一个有序集合键，这个有序集合以水果名为成员，水果价钱为分值，保存了 130 款水果的价钱：

1
2
3
4
5
6
7
8
9
10
redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) "6.5"
5) "apple"
6) "8"
 
redis> ZCARD fruit-price
(integer) 130

fruit-price 有序集合的所有数据都保存在一个跳跃表里面，其中每个跳跃表节点都保存了一款水果的价钱信息，所有水果按价钱的高低从低到高在跳跃表里面排序：

  • 跳跃表的第一个元素的成员为 "banana" ，它的分值为 5 ；
  • 跳跃表的第二个元素的成员为 "cherry" ，它的分值为 6.5 ；
  • 跳跃表的第三个元素的成员为 "apple" ，它的分值为 8 ；

和链表、字典等数据结构被广泛地应用在 Redis 内部不同，Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在 Redis 里面没有其他用途。

跳表的结构如下

img

Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义，其中 zskiplistNode 结构用于表示跳跃表节点，而 zskiplist 结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针，等等

图 5-1 展示了一个跳跃表示例，位于图片最左边的是 zskiplist 结构，该结构包含以下属性：

  • header ：指向跳跃表的表头节点
  • tail ：指向跳跃表的表尾节点
  • level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）
  • length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）

位于 zskiplist 结构右方的是四个 zskiplistNode 结构，该结构包含以下属性：

  • 层(level)：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
  • 后退(backward)指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • 分值(score)：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
  • 成员对象(obj)：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

注意表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性都不会被用到，所以图中省略了这些部分，只显示了表头节点的各个层。

跳表实现

跳跃表节点的实现由 redis.h/zskiplistNode 结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
 
    // 分值
    double score;
 
    // 成员对象
    robj *obj;
 
    // 层
    struct zskiplistLevel {
 
        // 前进指针
        struct zskiplistNode *forward;
 
        // 跨度
        unsigned int span;
 
    } level[];
 
} zskiplistNode;
层

跳跃表节点的 level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。

每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的“高度”。

图 5-2 分别展示了三个高度为 1 层、 3 层和 5 层的节点，因为 C 语言的数组索引总是从 0 开始的，所以节点的第一层是 level[0] ，而第二层是 level[1] ，以此类推。

跳跃表的实现 - 图2

前进指针

每个层都有一个指向表尾方向的前进指针（level[i].forward 属性），用于从表头向表尾方向访问节点。

图 5-3 用虚线表示出了程序从表头向表尾方向，遍历跳跃表中所有节点的路径：

  • 首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中的第二个节点。
  • 在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。
  • 在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。
  • 当程序再次沿着第四个节点的前进指针移动时，它碰到一个 NULL ，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历

跨度

层的跨度（level[i].span 属性）用于记录两个节点之间的距离：

  • 两个节点之间的跨度越大，它们相距得就越远。
  • 指向 NULL 的所有前进指针的跨度都为 0 ，因为它们没有连向任何节点。

初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样 ——遍历操作只使用前进指针就可以完成了，跨度实际上是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

举个例子，图 5-4 用虚线标记了在跳跃表中查找分值为 3.0 、成员对象为 o3 的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为 3 ，所以目标节点在跳跃表中的排位为 3 。

再举个例子，图 5-5 用虚线标记了在跳跃表中查找分值为 2.0 、成员对象为 o2 的节点时，沿途经历的层：在查找节点的过程中，程序经过了两个跨度为 1 的节点，因此可以计算出，目标节点在跳跃表中的排位为 2

后退指针

节点的后退指针（backward 属性）用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

图 5-6 用虚线展示了如果从表尾向表头遍历跳跃表中的所有节点：程序首先通过跳跃表的 tail 指针访问表尾节点，然后通过后退指针访问倒数第二个节点，之后再沿着后退指针访问倒数第三个节点，再之后遇到指向 NULL 的后退指针，于是访问结束

分值与成员

节点的分值（score 属性）是一个 double 类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。

节点的成员对象（obj 属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。

举个例子，在图 5-7 所示的跳跃表中，三个跳跃表节点都保存了相同的分值 10086.0 ，但保存成员对象 o1 的节点却排在保存成员对象 o2 和 o3 的节点之前，而保存成员对象 o2 的节点又排在保存成员对象 o3 的节点之前，由此可见，o1 、 o2 、 o3 三个成员对象在字典中的排序为 o1 <= o2 <= o3 。

跳跃表

虽然仅靠多个跳跃表节点就可以组成一个跳跃表，如图 5-8 所示。

但通过使用一个 zskiplist 结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，又或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息，如图 5-9 所示。

zskiplist 结构的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct zskiplist {
 
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
 
    // 表中节点的数量
    unsigned long length;
 
    // 表中层数最大的节点的层数
    int level;
 
} zskiplist;

header 和 tail 指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为 O(1) 。

通过使用 length 属性来记录节点的数量，程序可以在 O(1) 复杂度内返回跳跃表的长度。

level 属性则用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。

跳跃更新

跳表的插入删除与普通的查找过程一样，但是出现了一个问题，他是如何维护这些索引的？不然就有可能出现两个索引节点之间的数据非常多！

整体步骤如下：

  1. 查找并获取最底层链表中第一个小于等于num的位置插入

  2. 随机产生该节点的层数

    • 它肯定有第1层的指针

    • 如果节点在第i层有指针，那么他在第i+1层有指针的概率是p，那么就有

      1
      2
      3
      4
      5
      6
      7
      8
      static int random_level() {
      	int level = 1;
      	while(rand() < SKIPLIST_P_VAL && level < MAX_LEVEL) level++;
      	return level;
      }

      //SKIPLIST_P_VAL = 1/4
      //MAX_LEVEL = 32

总结

  • 跳跃表是有序集合的底层实现之一，除此之外它在 Redis 中没有其他应用。
  • Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成，其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度），而 zskiplistNode 则用于表示跳跃表节点。
  • 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
  • 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

整数集合

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

举个例子，如果创建一个只包含五个元素的集合键，并且集合中的所有元素都是整数值，那么这个集合键的底层实现就会是整数集合：

1
2
3
4
5
redis> SADD numbers 1 3 5 7 9
(integer) 5
 
redis> OBJECT ENCODING numbers
"intset"

整数集合的实现

整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构，它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值，并且保证集合中不会出现重复元素。

每个 intset.h/intset 结构表示一个整数集合：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {
 
    // 编码方式
    uint32_t encoding;
 
    // 集合包含的元素数量
    uint32_t length;
 
    // 保存元素的数组
    int8_t contents[];
 
} intset;

contents 数组是整数集合的底层实现：整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

通过什么决定排序？

length 属性记录了整数集合包含的元素数量，也即是 contents 数组的长度。

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值 ——contents 数组的真正类型取决于 encoding 属性的值：

  • 如果 encoding 属性的值为 INTSET_ENC_INT16 ，那么 contents 就是一个 int16_t 类型的数组，数组里的每个项都是一个 int16_t 类型的整数值（最小值为 -32,768 ，最大值为 32,767 ）。
  • 如果 encoding 属性的值为 INTSET_ENC_INT32 ，那么 contents 就是一个 int32_t 类型的数组，数组里的每个项都是一个 int32_t 类型的整数值（最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。
  • 如果 encoding 属性的值为 INTSET_ENC_INT64 ，那么 contents 就是一个 int64_t 类型的数组，数组里的每个项都是一个 int64_t 类型的整数值（最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）

这是怎么实现的？

图 6-1 展示了一个整数集合示例：

  • encoding 属性的值为 INTSET_ENC_INT16 ，表示整数集合的底层实现为 int16_t 类型的数组，而集合保存的都是 int16_t 类型的整数值。
  • length 属性的值为 5 ，表示整数集合包含五个元素。
  • contents 数组按从小到大的顺序保存着集合中的五个元素。
  • 因为每个集合元素都是 int16_t 类型的整数值，所以 contents 数组的大小等于 sizeof(int16_t) *5 = 16* 5 = 80 位。

图 6-2 展示了另一个整数集合示例：

  • encoding 属性的值为 INTSET_ENC_INT64 ，表示整数集合的底层实现为 int64_t 类型的数组，而数组中保存的都是 int64_t 类型的整数值。
  • length 属性的值为 4 ，表示整数集合包含四个元素。
  • contents 数组按从小到大的顺序保存着集合中的四个元素。
  • 因为每个集合元素都是 int64_t 类型的整数值，所以 contents 数组的大小为 sizeof(int64_t) *4 = 64* 4 = 256 位。

虽然 contents 数组保存的四个整数值中，只有 -2675256175807981027 是真正需要用 int64_t 类型来保存的，而其他的 1 、 3 、 5 三个值都可以用 int16_t 类型来保存，不过根据整数集合的升级规则，当向一个底层为 int16_t 数组的整数集合添加一个 int64_t 类型的整数值时，整数集合已有的所有元素都会被转换成 int64_t 类型，所以 contents 数组保存的四个整数值都是 int64_t 类型的，不仅仅是 -2675256175807981027

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

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

  • 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
  • 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
  • 将新元素添加到底层数组里面。举个例子，假设现在有一个 INTSET_ENC_INT16 编码的整数集合，集合中包含三个 int16_t 类型的元素，如图 6-3 所示。

因为每个元素都占用 16 位空间，所以整数集合底层数组的大小为 3 * 16 = 48 位，图 6-4 展示了整数集合的三个元素在这 48 位里的位置

现在，假设我们要将类型为 int32_t 的整数值 65535 添加到整数集合里面，因为 65535 的类型 int32_t 比整数集合当前所有元素的类型都要长，所以在将 65535 添加到整数集合之前，程序需要先对整数集合进行升级。

升级首先要做的是，根据新类型的长度，以及集合元素的数量（包括要添加的新元素在内），对底层数组进行空间重分配。

整数集合目前有三个元素，再加上新元素 65535 ，整数集合需要分配四个元素的空间，因为每个 int32_t 整数值需要占用 32 位空间，所以在空间重分配之后，底层数组的大小将是 32 * 4 = 128 位，如图 6-5 所示。

虽然程序对底层数组进行了空间重分配，但数组原有的三个元素 1 、 2 、 3 仍然是 int16_t 类型，这些元素还保存在数组的前 48 位里面，所以程序接下来要做的就是将这三个元素转换成 int32_t 类型，并将转换后的元素放置到正确的位上面，而且在放置元素的过程中，需要维持底层数组的有序性质不变。

首先，因为元素 3 在 1 、 2 、 3 、 65535 四个元素中排名第三，所以它将被移动到 contents 数组的索引 2 位置上，也即是数组 64 位至 95 位的空间内，如图 6-6 所示。

接着，因为元素 2 在 1 、 2 、 3 、 65535 四个元素中排名第二，所以它将被移动到 contents 数组的索引 1 位置上，也即是数组的 32 位至 63 位的空间内，如图 6-7 所示。

之后，因为元素 1 在 1 、 2 、 3 、 65535 四个元素中排名第一，所以它将被移动到 contents 数组的索引 0 位置上，也即是数组的 0 位至 31 位的空间内，如图 6-8 所示

然后，因为元素 65535 在 1 、 2 、 3 、 65535 四个元素中排名第四，所以它将被添加到 contents 数组的索引 3 位置上，也即是数组的 96 位至 127 位的空间内，如图 6-9 所示

最后，程序将整数集合 encoding 属性的值从 INTSET_ENC_INT16 改为 INTSET_ENC_INT32 ，并将 length 属性的值从 3 改为 4 ，设置完成之后的整数集合如图 6-10 所示

因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为 O(N) 。

其他类型的升级操作，比如从 INTSET_ENC_INT16 编码升级为 INTSET_ENC_INT64 编码，或者从 INTSET_ENC_INT32 编码升级为 INTSET_ENC_INT64 编码，升级的过程都和上面展示的升级过程类似。

升级之后新元素的摆放位置

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素：

  • 在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头（索引 0 ）；
  • 在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾（索引 length-1 ）

升级的好处

  1. 提升灵活度

    一般只使用 int16_t 类型的数组来保存 int16_t 类型的值，只使用 int32_t 类型的数组来保存 int32_t 类型的值，诸如此类。

    整数集合通过自动升级底层数组来适应新元素，可以随意地将 int16_t 、 int32_t 或者 int64_t 类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活。

  2. 节约内存

    让一个数组可以同时保存 int16_t 、 int32_t 、 int64_t 三种类型的值，最简单的做法就是直接使用 int64_t 类型的数组作为整数集合的底层实现。即使添加到整数集合里面的都是 int16_t 类型或者 int32_t 类型的值，数组都需要使用 int64_t 类型的空间去保存它们，从而出现浪费内存的情况。

    整数集合的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

    如果一直只向整数集合添加 int16_t 类型的值，那么整数集合的底层实现就会一直是 int16_t 类型的数组，只有在将 int32_t 类型或者 int64_t 类型的值添加到集合时，程序才会对数组进行升级

降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

举个例子，对于图 6-11 所示的整数集合来说，即使我们将集合里唯一一个真正需要使用 int64_t 类型来保存的元素 4294967295 删除了，整数集合的编码仍然会维持 INTSET_ENC_INT64 ，底层数组也仍然会是 int64_t 类型的，如图 6-12 所示

总结

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
  • 整数集合只支持升级操作，不支持降级操作。

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。

比如说，执行以下命令将创建一个压缩列表实现的列表键：

1
2
3
4
redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6 
redis> OBJECT ENCODING lst
"ziplist"

因为列表键里面包含的都是 1 、 3 、 5 、 10086 这样的小整数值，以及 "hello" 、 "world" 这样的短字符串。

另外，当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做哈希键的底层实现。

举个例子，执行以下命令将创建一个压缩列表实现的哈希键：

1
2
3
4
redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK 
redis> OBJECT ENCODING profile
"ziplist"

因为哈希键里面包含的所有键和值都是小整数值或者短字符串。

本章将对压缩列表的定义以及相关操作进行详细的介绍

压缩列表

压缩列表是 Redis 为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

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

图 7-1 展示了压缩列表的各个组成部分，表 7-1 则记录了各个组成部分的类型、长度、以及用途。

img

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量：当这个属性的值小于 UINT16_MAX （65535）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

图 7-2 展示了一个压缩列表示例：

  • 列表 zlbytes 属性的值为 0x50 （十进制 80），表示压缩列表的总长为 80 字节。
  • 列表 zltail 属性的值为 0x3c （十进制 60），这表示如果我们有一个指向压缩列表起始地址的指针 p ，那么只要用指针 p 加上偏移量 60 ，就可以计算出表尾节点 entry3 的地址。
  • 列表 zllen 属性的值为 0x3 （十进制 3），表示压缩列表包含三个节点

图 7-3 展示了另一个压缩列表示例：

  • 列表 zlbytes 属性的值为 0xd2 （十进制 210），表示压缩列表的总长为 210 字节。
  • 列表 zltail 属性的值为 0xb3 （十进制 179），这表示如果我们有一个指向压缩列表起始地址的指针 p ，那么只要用指针 p 加上偏移量 179 ，就可以计算出表尾节点 entry5 的地址。
  • 列表 zllen 属性的值为 0x5 （十进制 5），表示压缩列表包含五个节点。

压缩列表节点构成

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下三种长度的其中一种：

  • 长度小于等于 63 （2^{6}-1）字节的字节数组；
  • 长度小于等于 16383 （2^{14}-1） 字节的字节数组；
  • 长度小于等于 4294967295 （2^{32}-1）字节的字节数组；

而整数值则可以是以下六种长度的其中一种：

  • 4 位长，介于 0 至 12 之间的无符号整数；
  • 1 字节长的有符号整数；
  • 3 字节长的有符号整数；
  • int16_t 类型整数；
  • int32_t 类型整数；
  • int64_t 类型整数。

每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成，如图 7-4 所示

previous_entry_length

节点的 previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。

previous_entry_length 属性的长度可以是 1 字节或者 5 字节：

  • 如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节：前一节点的长度就保存在这一个字节里面。
  • 如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性的长度为 5 字节：其中属性的第一字节会被设置为 0xFE （十进制值 254），而之后的四个字节则用于保存前一节点的长度。

图 7-5 展示了一个包含一字节长 previous_entry_length 属性的压缩列表节点，属性的值为 0x05 ，表示前一节点的长度为 5 字节

图 7-6 展示了一个包含五字节长 previous_entry_length 属性的压缩节点，属性的值为 0xFE00002766 ，

  • 值的最高位字节 0xFE 表示这是一个五字节长的 previous_entry_length 属性，
  • 之后的四字节 0x00002766 （十进制值 10086 ）才是前一节点的实际长度

因为节点的 previous_entry_length 属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。

举个例子，如果我们有一个指向当前节点起始地址的指针 c ，那么我们只要用指针 c 减去当前节点 previous_entry_length 属性的值，就可以得出一个指向前一个节点起始地址的指针 p ，如图 7-7 所示。

压缩列表的从表尾向表头遍历操作就是使用这一原理实现的：只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的 previous_entry_length 属性，程序就可以一直向前一个节点回溯，最终到达压缩列表的表头节点。

图 7-8 展示了一个从表尾节点向表头节点进行遍历的完整过程：

  • 首先，我们拥有指向压缩列表表尾节点 entry4 起始地址的指针 p1（指向表尾节点的指针可以通过指向压缩列表起始地址的指针加上 zltail 属性的值得出）；

    img

  • 通过用 p1 减去 entry4 节点 previous_entry_length 属性的值，我们得到一个指向 entry4 前一节点 entry3 起始地址的指针 p2 ；

  • 通过用 p2 减去 entry3 节点 previous_entry_length 属性的值，我们得到一个指向 entry3 前一节点 entry2 起始地址的指针 p3 ；

  • 通过用 p3 减去 entry2 节点 previous_entry_length 属性的值，我们得到一个指向 entry2 前一节点 entry1 起始地址的指针 p4 ，entry1 为压缩列表的表头节点；

  • 最终，我们从表尾节点向表头节点遍历了整个列表。

encoding

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

  • 一字节、两字节或者五字节长，值的最高位为 00 、 01 或者 10 的是字节数组编码：这种编码表示节点的 content 属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录；
  • 一字节长，值的最高位以 11 开头的是整数编码：这种编码表示节点的 content 属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录；

表 7-2 记录了所有可用的字节数组编码，而表 7-3 则记录了所有可用的整数编码。表格中的下划线 _ 表示留空，而 b 、 x 等变量则代表实际的二进制数据，为了方便阅读，多个字节之间用空格隔开。

表7-2:

编码 编码长度 content 属性保存的值
00bbbbbb 1 字节 长度小于等于 63 字节的字节数组。
01bbbbbb xxxxxxxx 2 字节 长度小于等于 16383 字节的字节数组。
10**__** aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 长度小于等于 4294967295 的字节数组。

表7-3:

编码 编码长度 content 属性保存的值
11000000 1 字节 int16_t 类型的整数。
11010000 1 字节 int32_t 类型的整数。
11100000 1 字节 int64_t 类型的整数。
11110000 1 字节 24 位有符号整数。
11111110 1 字节 8 位有符号整数。
1111xxxx 1 字节 使用这一编码的节点没有相应的 content 属性，因为编码本身的 xxxx 四个位已经保存了一个介于 0 和 12 之间的值，所以它无须 content 属性。
content

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

图 7-9 展示了一个保存字节数组的节点示例：

  • 编码的最高两位 00 表示节点保存的是一个字节数组；
  • 编码的后六位 001011 记录了字节数组的长度 11 ；
  • content 属性保存着节点的值 "hello world" 。

图 7-10 展示了一个保存整数值的节点示例：

  • 编码 11000000 表示节点保存的是一个 int16_t 类型的整数值；
  • content 属性保存着节点的值 10086 。

连锁更新

前面说过，每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

  • 如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

考虑这样一种情况：在一个压缩列表中，有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN ，如图 7-11 所示。

因为 e1 至 eN 的所有节点的长度都小于 254 字节，所以记录这些节点的长度只需要 1 字节长的 previous_entry_length 属性，换句话说，e1 至 eN 的所有节点的 previous_entry_length 属性都是 1 字节长的。

如果将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点，那么 new 将成为 e1 的前置节点，如图 7-12 所示。

因为 e1 的 previous_entry_length 属性仅长 1 字节，它没办法保存新节点 new 的长度，所以程序将对压缩列表执行空间重分配操作，并将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。

现在，麻烦的事情来了 ——e1 原本的长度介于 250 字节至 253 字节之间，在为 previous_entry_length 属性新增四个字节的空间之后，e1 的长度就变成了介于 254 字节至 257 字节之间，而这种长度使用 1 字节长的 previous_entry_length 属性是没办法保存的。

因此，为了让 e2 的 previous_entry_length 属性可以记录下 e1 的长度，程序需要再次对压缩列表执行空间重分配操作，并将 e2 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。

正如扩展 e1 引发了对 e2 的扩展一样，扩展 e2 也会引发对 e3 的扩展，而扩展 e3 又会引发对 e4 的扩展……为了让每个节点的 previous_entry_length 属性都符合压缩列表对节点的要求，程序需要不断地对压缩列表执行空间重分配操作，直到 eN 为止。

Redis 将这种在特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”（cascade update），图 7-13 展示了这一过程。

除了添加新节点可能会引发连锁更新之外，删除节点也可能会引发连锁更新。

考虑图 7-14 所示的压缩列表，如果 e1 至 eN 都是大小介于 250 字节至 253 字节的节点，big 节点的长度大于等于 254 字节（需要 5 字节的 previous_entry_length 来保存），而 small 节点的长度小于 254 字节（只需要 1 字节的 previous_entry_length 来保存），那么当我们将 small 节点从压缩列表中删除之后，为了让 e1 的 previous_entry_length 属性可以记录 big 节点的长度，程序将扩展 e1 的空间，并由此引发之后的连锁更新

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N) ，所以连锁更新的最坏复杂度为 O(N^2) 。

要注意的是，尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：

  • 首先，压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；
  • 其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响：比如说，对三五个节点进行连锁更新是绝对不会影响性能的；

因为以上原因，ziplistPush 等命令的平均复杂度仅为 O(N) ，在实际中，我们可以放心地使用这些函数，而不必担心连锁更新会影响压缩列表的性能。

总结

  • 压缩列表是一种为节约内存而开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

参考链接

  1. https://www.bookstack.cn/read/redisbook/

  2. https://www.cnblogs.com/yinbiao/p/10740212.html

  3. https://www.jianshu.com/p/9d8296562806

  4. https://blog.csdn.net/qq_42604176/article/details/110550937