第 8 章
quicklist：listpack + 双端链表的混合设计
第八章：quicklist——listpack 与双端链表的混合设计
8.1 设计背景与演进
8.1.1 Redis List 的历史演进
Redis 的 List 数据类型在内部实现上经历了三个阶段的演进：
阶段一（Redis 2.x）：ziplist
LPUSH key a b c d e ... (100个元素)
▼
[zlbytes][zltail][zllen][e1][e2]...[e100][0xFF]
└─────────────── 一块连续内存 ─────────────────┘
优点：内存紧凑，无指针开销
缺点：
1. LINSERT/LSET 需要 memmove 整块内存，O(n) 字节移动
2. ziplist 增长时 realloc，可能触发内存拷贝
3. 大列表场景：单次 realloc 可能移动 MB 级数据
阶段二：linkedlist（双端链表）
head ──► [node1] ──► [node2] ──► ... ──► [node100] ──► NULL
└── sds └── sds └── sds
优点：O(1) 头尾插入，无 memmove
缺点：
1. 每个节点单独 malloc：内存碎片，分配器开销
2. 每个节点有 prev/next 两个指针：8字节×2=16字节额外开销
3. 内存不连续：缓存行不友好
4. 小列表时指针开销 > 数据本身
阶段三（Redis 3.2+）：quicklist（当前方案）
head tail
│ │
▼ ▼
[QL节点1] ──► [QL节点2] ──► [QL节点3] ──► [QL节点4]
│listpack│ │listpack│ │listpack│ │listpack│
│ (LZF?) │ │ (LZF?) │ │ (LZF?) │ │ (LZF?) │
└────────┘ └────────┘ └────────┘ └────────┘
两端节点不压缩（LPUSH/RPOP 频繁访问）
中间节点 LZF 压缩（访问少，节省内存）
每个 listpack 不超过配置大小（默认 8KB）
8.2 quicklistNode 与 quicklist 完整结构
8.2.1 C 结构定义（quicklist.h）
/* quicklist 节点 */
typedef struct quicklistNode {
struct quicklistNode *prev; /* 前驱节点 */
struct quicklistNode *next; /* 后继节点 */
unsigned char *entry; /* 指向 listpack（或压缩数据）的指针 */
size_t sz; /* listpack 的字节大小（压缩前） */
unsigned int count : 16; /* 该节点中的元素数量（最多 65535） */
unsigned int encoding : 2; /* RAW=1（未压缩）, LZF=2（LZF 压缩） */
unsigned int container : 2; /* PLAIN=1（裸数据）, PACKED=2（listpack） */
unsigned int recompress : 1; /* 访问后是否需要重新压缩 */
unsigned int attempted_compress : 1; /* 曾尝试压缩但太小，不再尝试 */
unsigned int dont_compress : 1;/* 临时标记：禁止压缩（正在访问中） */
unsigned int extra : 9; /* 预留位 */
} quicklistNode;
/* quicklist 容器 */
typedef struct quicklist {
quicklistNode *head; /* 头节点 */
quicklistNode *tail; /* 尾节点 */
unsigned long count; /* 所有 listpack 中的元素总数 */
unsigned long len; /* quicklistNode 节点总数 */
signed int fill : QL_FILL_BITS; /* 每个节点的最大容量配置 */
unsigned int compress : QL_COMP_BITS; /* 两端各保留多少节点不压缩 */
unsigned int bookmark_count : QL_BM_BITS; /* bookmark 数量 */
quicklistBookmark bookmarks[]; /* bookmark 数组（用于 SCAN/迭代） */
} quicklist;
8.2.2 内存布局全景图
quicklist struct（48字节）：
┌──────────────────────────────────────────────────────────────┐
│ head ptr(8) │ tail ptr(8) │ count(8) │ len(8) │ fill+comp(4) │
└──────────────────────────────────────────────────────────────┘
│ │
▼ ▼
┌─────────────────┐ ┌─────────────────┐
│ quicklistNode 1 │ ←──────► │ quicklistNode 4 │
│ prev=NULL │ │ next=NULL │
│ next────────────┼──────► │ prev────────────│
│ entry ptr ──────┼──► │ entry ptr ──────┼──►
│ sz=6000 │ │ sz=4000 │
│ count=498 │ │ count=330 │
│ encoding=RAW │ │ encoding=LZF │
└─────────────────┘ └─────────────────┘
│ │
▼ ▼
┌────────────────────┐ ┌─────────────────────┐
│ listpack (6KB) │ │ LZF 压缩数据 │
│ [lp header] │ │ 原始: 4000字节 │
│ [elem1]...[elem498│ │ 压缩后: ~2400字节 │
│ [0xFF end] │ │ 压缩比: ~0.6 │
└────────────────────┘ └─────────────────────┘
8.3 fill 参数详解
8.3.1 list-max-listpack-size 配置
fill 字段（signed int）控制每个 quicklistNode 最多存多少数据：
正数含义：每个节点最多 fill 个元素
fill=128：每个 listpack 最多128个元素（元素大小不限）
负数含义：每个节点的 listpack 大小上限
fill=-1：每个 listpack 最大 4,096 字节 ( 4KB)
fill=-2：每个 listpack 最大 8,192 字节 ( 8KB) ← 默认
fill=-3：每个 listpack 最大 16,384 字节 (16KB)
fill=-4：每个 listpack 最大 32,768 字节 (32KB)
fill=-5：每个 listpack 最大 65,536 字节 (64KB)
对应 C 代码：
/* quicklist.c */
REDIS_STATIC int
_quicklistNodeAllowInsert(const quicklistNode *node,
const int fill, const size_t sz) {
if (unlikely(!node || !node->entry))
return 0;
if (unlikely(QL_NODE_IS_PLAIN(node) || isLargeElement(sz)))
return 0;
/* 按元素数量限制（fill > 0） */
if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(
node->sz + sz + SIZE_ESTIMATE_OVERHEAD, fill)))
return 1;
/* 按字节大小限制（fill < 0） */
else if (!sizeMeetsSafetyLimit(node->sz + sz + SIZE_ESTIMATE_OVERHEAD))
return 0;
else if ((int)node->count < fill)
return 1;
return 0;
}
/* 判断字节大小是否满足 fill 负数的限制 */
REDIS_STATIC int
_quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz, const int fill) {
if (fill >= 0) return 0;
size_t offset = (-fill) - 1;
static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};
if (offset < 5)
return sz <= optimization_level[offset];
return 0;
}
8.3.2 默认值 -2（8KB）的合理性
分析：fill=-2，每个 listpack 最大 8KB
典型 List 元素大小：
- 短字符串（URL、key名）：50-200字节
- JSON 小对象：200-1000字节
- 日志行：100-500字节
8KB per listpack：
50字节元素 → 约164个元素/节点
200字节元素 → 约40个元素/节点
500字节元素 → 约16个元素/节点
为什么 8KB 合适：
1. L1 cache line = 64字节，8KB = 128 cache lines（可以整块预取）
2. 内存页 = 4KB，8KB = 2个连续页（减少 TLB miss）
3. listpack 修改时 realloc 的代价：8KB 内的 memmove 约 0.5μs
4. 节点数量：单个 listpack 内 LINDEX O(n) 遍历的最坏代价可控
8.4 LZF 压缩
8.4.1 list-compress-depth 配置
compress=0：不压缩任何节点（默认）
compress=1：两端各1个节点不压缩，其余压缩
compress=2：两端各2个节点不压缩，其余压缩
compress=N：两端各N个节点不压缩，其余压缩
示意（compress=1，7个节点）：
[node1] ──► [node2] ──► [node3] ──► [node4] ──► [node5] ──► [node6] ──► [node7]
↑不压缩 ↑LZF ↑LZF ↑LZF ↑LZF ↑LZF ↑不压缩
(LPUSH端) (RPOP端)
8.4.2 LZF 算法原理
LZF 是一种基于哈希的 LZ77 变体，为速度而非最大压缩率设计：
/* lzf_compress.c（简化版原理） */
int lzf_compress(const void *const in_data, unsigned int in_len,
void *out_data, unsigned int out_len) {
/*
* 哈希表：key=3字节内容的哈希，val=上次见到该内容的位置
*
* 算法：
* 1. 扫描输入，对每个位置计算3字节哈希
* 2. 查哈希表，如果找到匹配：
* a. 输出 back-reference（距离 + 匹配长度）
* b. 跳过匹配的字节
* 3. 如果没有匹配：输出原始字节（literal）
* 4. 更新哈希表
*/
const uint8_t *ip = (const uint8_t *)in_data;
uint8_t *op = (uint8_t *)out_data;
static uint8_t *htab[HSIZE]; /* 哈希表：存上次匹配位置的指针 */
for (;;) {
/* 计算当前3字节的哈希 */
v = FRST(ip);
v = NEXT(v, ip);
h = IDX(v);
ref = htab[h]; /* 查找上次该内容的位置 */
htab[h] = ip; /* 更新哈希表 */
if (ref > in_data && (ip - ref) < MAX_OFF /* 距离在范围内 */
&& ref[0] == ip[0] && ref[1] == ip[1] /* 确认匹配 */
&& ref[2] == ip[2]) {
/* 找到匹配：编码 back-reference */
/* 输出：[距离高3位 | 长度-2] + [距离低8位] */
len = 3;
while (len < MAX_REF && ip[len] == ref[len]) len++;
/* 输出 back-reference，跳过 len 字节 */
} else {
/* 无匹配：输出 literal 字节 */
*op++ = *ip++;
}
}
}
8.4.3 压缩实际效果
测试：Redis List 存储 1000 条 Nginx 日志行（平均 180 字节/行）
无压缩（fill=-2, compress=0）：
节点数：7个（7×8KB）
总内存：~182KB（含 quicklist 结构开销）
有压缩（fill=-2, compress=1）：
两端各1个节点不压缩：共 2 个节点 RAW
中间 5 个节点 LZF 压缩：
日志文本压缩率约 3:1（重复 URL、时间格式、HTTP状态码）
5个节点 ×8KB × 1/3 ≈ 13KB（压缩后）
总内存：2×8KB + 13KB ≈ 29KB
节省：(182-29)/182 ≈ 84% 内存节省！
注意：压缩/解压 CPU 代价
LZF 压缩速度：约 400MB/s（8KB block）
LZF 解压速度：约 800MB/s（8KB block）
8KB 压缩耗时：约 20μs
适用于访问模式：大量数据在中间，两端频繁进出
8.4.4 压缩节点的访问流程
/* quicklist.c — 访问压缩节点时先解压 */
REDIS_STATIC void quicklistDecompressNode(quicklistNode *node) {
if (node->encoding == QUICKLIST_NODE_ENCODING_RAW) return;
/* 解压到临时缓冲区 */
void *data;
size_t len = lzf_decompress(node->entry, node->sz, &data, node->sz_orig);
zfree(node->entry);
node->entry = data;
node->encoding = QUICKLIST_NODE_ENCODING_RAW;
}
/* 访问后重新压缩 */
REDIS_STATIC void quicklistRecompressOnly(quicklist *quicklist,
quicklistNode *node) {
if (node->recompress) {
quicklistCompressNode(node);
node->recompress = 0;
}
}
解压-访问-重压缩的完整流程确保透明性：调用方看到的始终是标准 listpack 接口。
8.5 LPUSH/RPUSH 操作流程
/* quicklist.c */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
if (unlikely(isLargeElement(sz))) {
/* 超大元素：创建 PLAIN 节点（不用 listpack） */
__quicklistInsertPlainNode(quicklist, quicklist->head, value, sz, 0);
return 1;
}
if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
/* 头节点有空间：直接插入 listpack */
quicklist->head->entry = lpPrepend(quicklist->head->entry, value, sz);
quicklistNodeUpdateSz(quicklist->head);
} else {
/* 头节点已满：创建新头节点 */
quicklistNode *node = quicklistCreateNode();
node->entry = lpPrepend(lpNew(0), value, sz);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
quicklist->count++;
quicklist->head->count++;
return (orig_head != quicklist->head);
}
操作复杂度：
LPUSH/RPUSH：
头/尾节点有空间：O(1) listpack prepend/append
头/尾节点已满：O(1) 创建新节点 + O(1) listpack prepend
LPOP/RPOP：
从 listpack 删除第一个/最后一个元素：O(1)
若节点变空：O(1) 删除节点
LLEN：
直接读取 quicklist.count：O(1)
8.6 LINSERT 与 LINDEX：O(n) 的隐患
/* 查找特定索引的元素 */
quicklistEntry quicklistIndex(quicklist *quicklist, long long idx) {
quicklistNode *n;
long long accum = 0;
quicklistIter *iter;
/* 正向或反向迭代 */
if (idx >= 0) {
/* 从头部遍历 */
n = quicklist->head;
while (n) {
if (accum + n->count > idx) {
/* 目标在此节点内，解压并在 listpack 中遍历 */
quicklistDecompressNodeForUse(n);
return listpackIndex(n->entry, idx - accum);
}
accum += n->count;
n = n->next;
}
}
/* ... */
}
O(n) 操作的真实代价：
场景：10000 个元素的 List（fill=-2, compress=1）
节点数 ≈ 10000/164 ≈ 61 个节点（每节点约164个50字节元素）
LINDEX 5000（访问中间元素）：
1. 遍历约 30 个节点找到目标节点：O(30) 节点遍历
2. 目标节点 LZF 解压：~20μs
3. listpack 内遍历约 82 个元素：O(82) 元素遍历
4. 重新压缩：~20μs
总计：约 45μs（对单线程 Redis 是明显的阻塞）
结论：quicklist 对随机访问没有优化，LINDEX/LINSERT/LSET 是 O(n) 操作
如果业务需要大量随机访问，Redis List 不是正确选择（考虑 Hash）
8.7 迭代器与 SCAN 支持
/* quicklist 迭代器 */
typedef struct quicklistIter {
quicklist *quicklist; /* 目标 quicklist */
quicklistNode *current; /* 当前节点 */
unsigned char *zi; /* 当前节点内 listpack 的当前元素指针 */
long offset; /* 当前元素在节点内的偏移 */
int direction; /* AL_START_HEAD 或 AL_START_TAIL */
} quicklistIter;
/* 创建迭代器 */
quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction) {
quicklistIter *iter = zmalloc(sizeof(*iter));
iter->quicklist = quicklist;
iter->current = (direction == AL_START_HEAD) ? quicklist->head : quicklist->tail;
iter->zi = NULL;
iter->offset = 0;
iter->direction = direction;
return iter;
}
LRANGE 命令通过迭代器实现，避免了 LINDEX 的逐次查找开销：
LRANGE key 0 -1（全量遍历）：
迭代器从头节点开始，顺序遍历每个 quicklistNode
对压缩节点：解压 → 遍历 listpack → 标记 recompress=1
遍历完成后检查 recompress 标记，重新压缩
时间复杂度：O(n)，但每次访问节点的 listpack 内元素是连续内存访问
8.8 性能基准
环境：Redis 7.0，list-max-listpack-size=-2，list-compress-depth=0
操作 元素数量 QPS（约） 延迟 P99
─────────────────────────────────────────────────
LPUSH 10K 2.1M/s 0.08ms
RPUSH 10K 2.1M/s 0.08ms
LPOP 10K 2.0M/s 0.09ms
LRANGE 0 99 10K 180K/s 0.5ms
LRANGE 0 999 10K 30K/s 2.8ms
LINDEX 中间 10K 450K/s 0.3ms
LINDEX 中间 100K 80K/s 1.5ms
（注：QPS 受 Redis 单线程限制，与 pipelining 无关）
8.9 小结
quicklist 是一个经典的工程折中：
| 场景 | 纯 listpack | 纯 linkedlist | quicklist |
|---|---|---|---|
| 头尾操作 | O(1)但realloc | O(1) | O(1) |
| 随机访问 | O(n) | O(n) | O(n) |
| 内存效率 | 最高（连续） | 最低（碎片） | 中等 |
| 缓存友好 | 最好 | 最差 | 较好 |
| 大数据压缩 | 不支持 | 不支持 | 支持（LZF） |
| 实现复杂度 | 低 | 低 | 高 |
quicklist 的核心价值在于：通过限制每个 listpack 节点的大小，将 memmove 的代价上界限制在一个可控范围（8KB）内，同时通过 LZF 压缩中间节点，在内存和性能之间取得了实用的平衡。