分段 · list-max-listpack-size · 压缩深度

quicklist：链表串起来的 listpack

Redis 的 list 要求两端 LPUSH / RPOP 都是 $O(1)$ ，还要能按下标取值、按范围切片。双向链表满足前者而在后者上很差，一整块 listpack 反过来。quicklist 的做法是把两者叠起来：链表的每个节点里装一个 listpack。

这个结构在教科书上叫 unrolled linked list，链表那一系列讲过它的动机。本页讲工业实现里多出来的那些参数。

1 · 链表与整块 listpack 的各自短板

每个节点只装一个元素的双向链表，内存账很难看。一个 listNode 要 prev、next、value 三个指针，64 位机上 24 字节，加上分配器的块头，装一个十来字节的短字符串要付三倍以上的额外开销。更麻烦的是访问模式：顺序遍历是一串指针追逐，每一跳都可能是一次 cache miss。

一整块 listpack 走到另一个极端。内存紧凑、顺序遍历全在一段连续地址上，但插入与删除要 memmove 插入点之后的全部字节。装 5000 个短字符串的 listpack 是 53897 字节，往中间插一个元素平均要搬 2 万多字节。

切段把两笔账都压下来：段内连续，段间用指针。段的大小成了唯一的调节旋钮，它在「每次插入搬多少」与「多付多少元数据」之间取值。

2 · `list-max-listpack-size` 的正负两套口径

这个参数的取值分正负两套语义，quicklistNodeLimit 里分道：

取正数：限制单个节点的元素个数。此外还有一道兜底，节点字节数不得超过 SIZE_SAFETY_LIMIT，也就是 8192。这道兜底常被漏掉——quicklistNodeExceedsLimit 在元素数没超时仍会检查 sizeMeetsSafetyLimit。
取负数：限制单个节点的字节数，-1 到 -5 依次对应 4096、8192、16384、32768、65536。

出厂值是 -2，也就是每节点 8 KB。

准入判断在 _quicklistNodeAllowInsert 里，它拿 node->sz + sz + SIZE_ESTIMATE_OVERHEAD 去比上限。那个常数是 8，用来把新元素的 encoding 与 backlen 估进去；注释写明这是故意高估，宁可让节点略小于上限。

还有一条旁路：单个元素本身就超过上限时（正数 fill 下是 8192，负数 fill 下是对应档次），isLargeElement 判它太大，给它单独开一个 plain node，节点里直接存裸字节而不套 listpack。

图 2-1 · 5000 个短字符串按不同 list-max-listpack-size 切成的节点链，每个方块是一个节点。可切换正负两套口径与压缩深度，观察节点数、每节点字节与被压缩的节点。

实测 5000 个 item-N 形式的短字符串：出厂的 -2 切成 7 个节点，-1 切成 14 个，128 切成 40 个，32 切成 157 个。同一批数据的节点数差了二十倍。

3 · 分段粒度的代价曲线

切得越细，每次插入要搬的字节越少，而元数据开销越大。两侧都能算出来。

数据侧的额外开销是每段多一份 listpack 的固定头部，7 字节。40 个节点比单块多 273 字节，157 个节点多 1092 字节，都恰好是 $(\textit{节点数} - 1) \times 7$ 。

真正的大头在链表侧。quicklistNode 有 prev、next、entry 三个指针加一个 size_t sz，再加一组位域。按 LP64 的对齐算：三个指针 24 字节、sz 8 字节已经占满 32，位域那 4 字节还要补一轮对齐，实际是 40 字节。

注 · quicklist.h 的头部注释写的是 quicklistNode is a 32 byte struct，并说明用位域压到 32 字节。上面的算法给出 40。差别出在 sz 上：它现在是 size_t（8 字节），若按 unsigned int（4 字节）算才凑得出 32。这条注释看起来是字段加宽之后没跟着更新的，不过这只是从字段声明推的，没有在真机上 sizeof 验证过。

按 40 字节一个节点算，5000 个元素这批数据的元数据开销：-2 下 7 个节点共 280 字节，占数据量的 0.52%；32 下 157 个节点共 6280 字节，占 11.65%；再切到 8，625 个节点 25000 字节，占 46.38%，几乎和数据一样重。

图 3-1 · 分段粒度的两侧代价：横轴是每节点上限，一条曲线是单次插入的平均搬迁字节，另一条是节点结构体加 listpack 头部的元数据开销。可改元素个数与元素长度。

另一侧的曲线相反。平均节点 7706 字节时，往节点中间插一个元素平均搬 3853 字节；切到 157 个节点，平均节点 350 字节，平均搬 175 字节。两条曲线交叉的位置随元素大小移动，出厂值 -2 落在偏「省元数据」的一侧，代价是单次插入的搬迁量在 KB 量级。

这个默认值的合理性来自 list 的典型用法：绝大多数 list 是当队列用的，只在两端 LPUSH / RPOP，而两端操作不触发中间的 memmove。真要在中间频繁 LINSERT 的场景，把 list-max-listpack-size 调成较小的正数更合适。

4 · 压缩深度

list-compress-depth 出厂为 0，表示不压缩。取 $N$ 时，链表两端各 $N$ 个节点保持原样，中间的全部用 LZF 压缩。

依据同样是访问模式。当 list 用作队列，热点永远在两端；中间那些节点可能几小时都没人碰，压着更划算。取值 1 意味着只有头尾两个节点是可直接读的，其余全压。

代价是随机访问变贵。LINDEX 落到一个被压缩的节点上时，quicklistDecompressNodeForUse 先解压，用完再由 quicklistRecompressOnly 压回去。位域里的 recompress 就是记这件事的：这个节点是被临时解压的，用完要压回去。

5000 个元素、出厂 -2 切成 7 个节点时，压缩深度取 1 会压掉中间 5 个；切成 157 个节点时压掉 155 个。节点越小压缩比越差，LZF 对几百字节的块本来就不容易压出多少——细分段与开压缩这两项调优互相拖后腿。

5 · 参考文献

Stancliff, M. quicklist.c / quicklist.h. redis/src（Redis 7.4）：_quicklistNodeAllowInsert、quicklistNodeLimit、optimization_level。
Shao, Z., Reppy, J. H., & Appel, A. W. (1994). Unrolled linked lists. Proceedings of the 1994 ACM Conference on LISP and Functional Programming, 156–165.
Liblzf. LZF 压缩算法：Redis 内置的快速压缩，用于 list-compress-depth 与 RDB。
Redis. redis.conf 中 list-max-listpack-size 与 list-compress-depth 两节的配置注释。