在 Redis 的众多数据结构中，List（列表）是非常常用的一种。早期版本的 Redis 使用 ziplist 和 linkedlist 两种编码方式来实现 List，但在 Redis 3.2 之后，引入了一种新的底层结构——quicklist，它结合了 ziplist 和 linkedlist 的优点，成为 List 类型的默认实现。本文将深入剖析 quicklist 的底层结构，帮助你在面试中从容应对相关问题。
为什么需要 quicklist
在理解 quicklist 之前，有必要先回顾一下它要解决的问题。
ziplist（压缩列表） 是一块连续的内存空间，所有元素紧凑地排列在一起。它的优点是内存利用率极高，没有额外的指针开销。但它也有明显的缺点：插入和删除操作可能触发连锁更新（cascade update），在最坏情况下时间复杂度退化为 O(n²)；而且当元素数量较多时，ziplist 会变得非常庞大，内存重新分配的成本很高。
linkedlist（双向链表） 的优点是插入和删除操作非常高效，时间复杂度为 O(1)。但它的缺点是每个节点都需要额外的 prev 和 next 指针，内存开销大；而且每个节点都是独立的内存块，容易产生内存碎片。
quicklist 的设计思路就是：将多个 ziplist 通过双向链表串联起来。这样既保留了 ziplist 的内存紧凑性，又通过链表的分段避免了单个 ziplist 过大带来的性能问题。
quicklist 的整体结构
quicklist 的核心定义在 quicklist.h 中，其结构可以简化为：
typedef struct quicklist {
quicklistNode *head; // 头节点
quicklistNode *tail; // 尾节点
unsigned long count; // 所有 ziplist 中的元素总数
unsigned long len; // quicklistNode 的个数
int fill : 16; // 每个节点的填充因子
unsigned int compress : 16; // 压缩深度
} quicklist;
可以看到，quicklist 本身就是一个双向链表，持有 head 和 tail 指针，同时记录了节点数量和元素总数。
每个链表节点的结构如下：
typedef struct quicklistNode {
struct quicklistNode *prev; // 前驱节点
struct quicklistNode *next; // 后继节点
unsigned char *zl; // 指向 ziplist
unsigned int sz; // ziplist 的字节大小
unsigned int count : 16; // ziplist 中的元素个数
unsigned int encoding : 2; // 编码方式：RAW 或 LZF
unsigned int container : 2; // 容器类型：NONE 或 ZIPLIST
unsigned int recompress : 1; // 是否被解压过
unsigned int attempted_compress : 1; // 是否尝试过压缩
unsigned int extra : 10; // 预留字段
} quicklistNode;
每个 quicklistNode 内部持有一个 ziplist 指针 zl，这就是 quicklist 的基本单元。整个结构示意图如下：
quicklist
|
+-- head --> [quicklistNode] <--> [quicklistNode] <--> [quicklistNode] --> tail
| | |
[ziplist] [ziplist] [ziplist]
quicklist 的关键参数
fill：填充因子
fill 参数控制每个 quicklistNode 中 ziplist 的最大容量。它可以在 redis.conf 中通过 list-max-ziplist-size 配置，取值为负数时有特殊含义：
- -1：每个 ziplist 最大 4KB
- -2：每个 ziplist 最大 8KB（默认值）
- -3：每个 ziplist 最大 16KB
- -4：每个 ziplist 最大 32KB
- -5：每个 ziplist 最大 64KB
如果取正数，则表示每个 ziplist 最多包含多少个元素。例如 fill = 128 表示每个 ziplist 最多存 128 个元素。
这个参数的设计非常关键：ziplist 太小，链表节点过多，内存碎片和指针开销增大；ziplist 太大，插入删除时内存重新分配的成本变高。默认值 8KB 是一个经过权衡的经验值。
compress：压缩深度
compress 参数控制是否对中间节点进行 LZF 压缩，通过 list-compress-depth 配置。其含义是：
- 0：不压缩（默认值）
- 1：首尾各 1 个节点不压缩，中间的节点压缩
- 2：首尾各 2 个节点不压缩，中间的节点压缩
- 以此类推
为什么要保留首尾节点不压缩？因为 List 的常用操作（如 LPUSH、RPUSH、LPOP、RPOP）大多集中在两端，保持两端节点未压缩可以避免频繁的解压和压缩操作。而中间节点访问频率低，压缩后可以节省大量内存。
quicklist 的常用操作
插入操作
当执行 LPUSH 或 RPUSH 时，quicklist 会检查头节点或尾节点的 ziplist 是否还有空间（根据 fill 参数判断）。如果有空间，直接插入到 ziplist 中；如果没有空间，则新建一个 quicklistNode，将新元素插入到新的 ziplist 中，并将该节点加入链表。
删除操作
当执行 LPOP 或 RPOP 时，直接从头部或尾部的 ziplist 中删除元素。如果删除后 ziplist 为空，则删除该 quicklistNode 节点。
查找操作
由于 quicklist 是链表结构，查找某个索引位置的元素需要遍历链表。但 Redis 做了一些优化：如果索引在前半部分，从头节点开始遍历；如果在后半部分，从尾节点开始遍历。找到对应的 quicklistNode 后，再在 ziplist 内部进行查找。
quicklist 与 ziplist 的转换
需要注意的是，quicklist 中的每个节点并不一定始终是 ziplist。当 ziplist 过大或经过 LZF 压缩后，节点可能以 RAW 编码存储。encoding 字段标识了当前节点的编码方式：
- ZIPLIST：节点持有一个未压缩的 ziplist
- LZF：节点持有的数据是经过 LZF 压缩的
当需要访问被压缩的节点时，Redis 会先解压，访问完毕后再根据 recompress 标志决定是否重新压缩。
面试常见追问
1. quicklist 和 ziplist、linkedlist 的关系是什么？
quicklist 是两者的结合体：宏观上是双向链表（linkedlist），微观上每个节点是 ziplist。它取两者之长，避两者之短。
2. 为什么 Redis 3.2 要用 quicklist 替代 linkedlist 和 ziplist？
因为纯 linkedlist 内存开销太大，纯 ziplist 在元素多时性能退化严重。quicklist 在内存和性能之间取得了更好的平衡。
3. quicklist 中每个 ziplist 的大小如何确定？
由 fill 参数控制，默认每个 ziplist 不超过 8KB。这个值可以根据实际场景调整，追求内存效率可以调小，追求性能可以调大。
4. quicklist 的压缩机制是怎样的？
通过 compress 参数控制，首尾节点不压缩以保证操作效率，中间节点使用 LZF 算法压缩以节省内存。
总结
quicklist 是 Redis 为 List 类型设计的一种精巧的底层结构。它以双向链表为骨架，以 ziplist 为血肉，通过 fill 和 compress 两个参数实现了内存与性能的灵活权衡。理解 quicklist 的结构，不仅能帮助你在面试中脱颖而出，更能在实际开发中合理配置 Redis，优化 List 类型的使用效率。
未经允许不得转载：任鹏个人博客 » Redis 的 quicklist 底层结构是怎样的
