Redis List 底层三种数据结构原理剖析

1. Redis List 是什么

作为 Java 开发者的你，看到这个词并不陌生。在 Java 开发中几乎每天都会使用这个数据结构。

Redis 的 List 与 Java 中的 LinkedList 类似，是一种线性的有序结构，可以按照元素被推入列表中的顺序来存储元素，能满足先进先出的需求，这些元素既可以是文字数据，又可以是二进制数据。

你可以把他当做队列、栈来使用。

2. 修炼心法

我叫 Redis，在 C 语言中，并没有现成的链表结构，所以 antirez 为我专门设计了一套实现方式。

关于 List 类型的底层数据结构，可谓英雄辈出，antirez 大佬一直在优化，创造了多种数据结构来保存。

从一开始早期版本使用 linkedlist（双端列表）和 ziplist（压缩列表）作为 List 的底层实现，到 Redis 3.2 引入了由 linkedlist + ziplist 组成的 quicklist，再到 7.0 版本的时候使用 listpack 取代 ziplist。

MySQL：“为何弄了这么多数据结构呀？”

antirez 所做的这一切都是为了在内存空间开销与访问性能之间做取舍和平衡，跟着我去吃透每个类型的设计思想和不足，你就明白了。

linkedlist（双端列表）

在 Redis 3.2 版本之前，List 的底层数据结构由 linkedlist 或者 ziplist 实现，优先使用 ziplist 存储。

当列表对象满足以下两个条件的时候，List 将使用 ziplist 存储，否则使用 linkedlist。

• List 的每个元素的占用的字节小于 64 字节。
  
• List 的元素数量小于 512 个。
  

链表的节点使用 adlist.h/listNode结构来表示。

typedef struct listNode {
    // 前驱节点
    struct listNode *prev;
    // 后驱节点
    struct listNode *next;
    // 指向节点的值
    void *value;
} listNode;

listNode 之间通过 prev 和 next 指针组成双端链表。除此之外，我还提供了 adlist.h/list 结构提供了头指针 head、尾指针 tail 以及一些实现多态的特定函数。

typedef struct list {
    // 头指针
    listNode *head;
    // 尾指针
    listNode *tail;
    // 节点值的复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值比对是否相等
    int (*match)(void *ptr, void *key);
    // 链表的节点数量
    unsigned long len;
} list;

linkedlist 的结构如图 2-5 所示。

图 2-5

图 2-5

Redis 的链表实现的特性总结如下。

• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后继节点的复杂度都是 O(1)。
  
• 无环：表头节点的 prev 指针和尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为结束。
  
• 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的头节点和尾节点的复杂度为 O(1)。
  
• 使用 list 结构的 len 属性来对记录节点数量，获取链表中节点数量的复杂度为 O(1)。
  

MySQL：“看起来没啥问题呀，为啥还要 ziplist 呢？”

你知道的，我在追求快和节省内存的方向上无所不及，有两个原因导致了 ziplist 的诞生。

• 普通的 linkedlist 有 prev、next 两个指针，当存储数据很小的情况下，指针占用的空间会超过数据占用的空间，这就离谱了，是可忍孰不可忍。
  
• linkedlist 是链表结构，在内存中不是连续的，遍历的效率低下。
  

ziplist（压缩列表）

为了解决上面两个问题，antirez 创造了 ziplist 压缩列表，是一种内存紧凑的数据结构，占用一块连续的内存空间，提升内存使用率。

当一个列表只有少量数据的时候，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么我就会使用 ziplist 来做 List 的底层实现。

ziplist 中可以包含多个 entry 节点，每个节点可以存放整数或者字符串，结构如图 2-6 所示。

图 2-6

图 2-6

• zlbytes，占用 4 个字节，记录了整个 ziplist 占用的总字节数。
  
• zltail，占用 4 个字节，指向最后一个 entry 偏移量，用于快速定位最后一个 entry。
  
• zllen，占用 2 字节，记录 entry 总数。
  
• entry，列表元素。
  
• zlend，ziplist 结束标志，占用 1 字节，值等于 255。
  

因为 ziplist 头尾元数据的大小是固定的，并且在 ziplist 头部 zllen 记录了最后一个元素的位置，所以，当在 ziplist 中查找第一个或最后一个元素的时候，能以 O(1) 时间复杂度找到。

而查找中间元素时，只能从列表头或者列表尾遍历，时间复杂度就是 O(N)。

接下来看真正存储数据的 entry 结构长啥样。

图 2-7

图 2-7

正常来说有三部分构成 <prevlen> <encoding> <entry-data>。

prevlen

记录前一个 entry 占用字节数，能实现逆序遍历就是靠这个字段确定往前移动多少字节拿到上一个 entry 首地址。

这部分会根据上一个 entry 的长度进行变长编码（为了节省内存操碎了心），变长方式如下。

• 前一个 entry 的字节大小小于 254（255 用于 zlend），prevlen 长度为 1 字节，值等于上一个 entry 的长度。
  
• 前一个 entry 的字节大小大于等于 254，prevlen 占用 5 字节，第一个字节设置为 254 作为一个标识，后面四字节组成一个 32 位的 int 值，用于存放上一个 entry 的字节长度。
  

encoding

简言之用于表示当前 entry 的类型和长度，当前 entry 的长度和值是根据保存的是 int 还是 string 以及数据的长度共同来决定。

前两位用于表示类型，当前两位值为 “11” 则表示 entry 存放的是 int 类型数据，其他表示存储的是 string。

entry-data

实际存放数据的区域，需要注意的是，如果 entry 中存储的是 int 类型，encoding 和 entry-data 会合并到 encoding 中，没有 entry-data 字段。

此刻结构就变成了 <prevlen> <encoding>。

MySQL：“为什么说 ziplist 省内存？”

1. 与 linkedlist 相比，少了 prev、next 指针。
   
2. 通过 encoding 字段针对不同编码来细化存储，尽可能做到按需分配，当 entry 存储的是 int 类型时，encoding 和 entry-data 会合并到 encoding ，省掉了 entry-data 字段。
   
3. 每个 entry-data 占据内存大小不一样，为了解决遍历问题，增加了 prevlen 记录上一个 entry 长度。遍历数据时间复杂度是 O(1)，但是数据量很小的情况下影响不大。
   

MySQL：“听起来很完美，为啥还搞什么 quicklist ”

既要又要还要的需求是很难实现的，ziplist 节省了内存，但是也有不足。

• 不能保存过多的元素，否则查询性能会大大降低，O(N) 时间复杂度。
  
• ziplist 存储空间是连续的，当插入新的 entry 时，内存空间不足就需要重新分配一块连续的内存空间，引发连锁更新的问题。
  

连锁更新

每个 entry 都用 prevlen 记录了上一个 entry 的长度，从当前 entry B 前面插入一个新的 entry A 时，会导致 B 的 prevlen 改变，也会导致 entry B 大小发生变化。entry B 后一个 entry C 的 prevlen 也需要改变。以此类推，就可能造成了连锁更新。

图 2-8

图 2-8

连锁更新会导致 ziplist 的内存空间需要多次重新分配，直接影响 ziplist 的查询性能。于是乎在 Redis 3.2 版本引入了 quicklist。

quicklist

quicklist 是综合考虑了时间效率与空间效率引入的新型数据结构。结合了原先 linkedlist 与 ziplist 各自的优势，本质还是一个链表，只不过链表的每个节点是一个 ziplist。

数据结构定义在 quicklist.h 文件中，链表由 quicklist 结构体定义，每个节点由 quicklistNode 结构体定义（源码版本为 6.2，7.0 版本使用 listpack 取代了 ziplist）。

quicklist 是一个双向链表，所以每个 quicklistNode 都有前序指针（*prev）、后序指针（*next）。每个节点是 ziplist，所以还有一个指向 ziplist 的指针 *zl。

typedef struct quicklistNode {
    // 前序节点指针
    struct quicklistNode *prev;
    // 后序节点指针
    struct quicklistNode *next;
    // 指向 ziplist 的指针
    unsigned char *zl;
    // ziplist 字节大小
    unsigned int sz;
    // ziplst 元素个数
    unsigned int count : 16;
    // 编码格式，1 = RAW 代表未压缩原生ziplist，2=LZF 压缩存储
    unsigned int encoding : 2;
    // 节点持有的数据类型，默认值 = 2 表示是 ziplist
    unsigned int container : 2;
    // 节点持有的 ziplist 是否经过解压， 1 表示已经解压过，下一次操作需要重新压缩。
    unsigned int recompress : 1;
    // ziplist 数据是否可压缩，太小数据不需要压缩
    unsigned int attempted_compress : 1;
    // 预留字段
    unsigned int extra : 10;
} quicklistNode;

quicklist 作为链表，定义了 头、尾指针，用于快速定位表表头和链表尾。

typedef struct quicklist {
    // 链表头指针
    quicklistNode *head;
    // 链表尾指针
    quicklistNode *tail;
    // 所有 ziplist 的总 entry 个数
    unsigned long count;
    // quicklistNode 个数
    unsigned long len;
    int fill : QL_FILL_BITS;
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    // 柔性数组，给节点添加标签，通过名称定位节点，实现随机访问的效果
    quicklistBookmark bookmarks[];
} quicklist;

结合 quicklist 和 quicklistNode定义，quicklist 链表结构如下图所示。

图 2-9

图 2-9

从结构上看，quicklist 就是 ziplist 的升级版，优化的关键点在于控制好每个 ziplist 的大小或者元素个数。

• quicklistNode 的 ziplist 越小，可能会造成更多的内存碎片，极端情况下是每个 ziplist 只有一个 entry，退化成了 linkedlist。
  
• quicklistNode 的 ziplist 过大，极端情况下一个 quicklist 只有一个 ziplist，退化成了 ziplist。连锁更新的性能问题就会暴露无遗。
  

合理配置很重要，Redis 提供了 list-max-ziplist-size -2，

当 list-max-ziplist-size为负数时表示限制每个 quicklistNode 的 ziplist 的内存大小，超过这个大小就会使用 linkedlist 存储数据，每个值有以下含义：

• -5：每个 quicklist 节点上的 ziplist 大小最大 64 kb <--- 正常环境不推荐
  
• -4：每个 quicklist 节点上的 ziplist 大小最大 32 kb <--- 不推荐
  
• -3：每个 quicklist 节点上的 ziplist 大小最大 16 kb <--- 可能不推荐
  
• -2：每个 quicklist 节点上的 ziplist 大小最大 8 kb <--- 不错
  
• -1：每个 quicklist 节点上的 ziplist 大小最大 4kb <--- 不错
  

默认值为 -2，也是官方最推荐的值，当然你可以根据自己的实际情况进行修改。

MySQL：“搞了半天还是没能解决连锁更新的问题嘛”

别急，饭要一口口吃，路要一步步走，步子迈大了容易扯着蛋。

ziplist 是紧凑型数据结构，可以有效利用内存。但是每个 entry 都用 prevlen 保留了上一个 entry 的长度，所以在插入或者更新时可能会出现连锁更新影响效率。

于是 antirez 又设计出了“链表 + ziplist” 组成的 quicklist 来避免单个 ziplist 过大，降低连锁更新的影响范围。

可毕竟还是使用了 ziplist，本质上无法避免连锁更新的问题，于是乎在 5.0 版本设计出另一个内存紧凑型数据结构 listpack，于 7.0 版本替换掉 ziplist。

listpack

出现 listpack 的原因是因为用户上报了一个 Redis 崩溃的问题，但是 antirez 并没有找到崩溃的明确原因，猜测可能是 ziplist 结构导致的连锁更新导致的，于是就想设计一种简单、高效的数据结构来替换 ziplist 这个数据结构。

MySQL：“listpack 是啥？”

listpack 也是一种紧凑型数据结构，用一块连续的内存空间来保存数据，并且使用多种编码方式来表示不同长度的数据来节省内存空间。

源码文件 listpack.h对 listpack 的解释：A lists of strings serialization format，意思是一种字符串列表的序列化格式，可以把字符串列表进行序列化存储，可以存储字符串或者整形数字。

先看 listpack 的整体结构。

图 2-10

图 2-10

一共四部分组成，tot-bytes、num-elements、elements、listpack-end-byte。

• tot-bytes，也就是 total bytes，占用 4 字节，记录 listpack 占用的总字节数。
  
• num-elements，占用 2 字节，记录 listpack elements 元素个数。
  
• elements，listpack 元素，保存数据的部分。
  
• listpack-end-byte，结束标志，占用 1 字节，值固定为 255。
  

MySQL：“好家伙，这跟 ziplist 有啥区别？别以为换了个名字，换个马甲我就不认识了”

听我说完！确实有点像，listpack 也是由元数据和数据自身组成。最大的区别是 elements 部分，为了解决 ziplist 连锁更新的问题，element 不再像 ziplist 的 entry 保存前一项的长度。

图 2-11

图 2-11

• encoding-type，元素的编码类型，会不同长度的整数和字符串编码。
  
• element-data，实际存放的数据。
  
• element-tot-len，encoding-type + element-data 的总长度，不包含自己的长度。
  

每个 element 只记录自己的长度，不像 ziplist 的 entry，记录上一项的长度。当修改或者新增元素的时候，不会影响后续 element 的长度变化，解决了连锁更新的问题。

从 linkedlist、 ziplist 到“链表 + ziplist” 构成的 quicklist，再到 listpack 结构。可以看到，设计的初衷都是能够高效的使用内存，同时避免性能下降。