你有没有想过一个问题：Redis的List类型，底层到底是怎么存数据的？很多人会脱口而出：“链表嘛。”那么，为什么Redis不直接用一个简单的双向链表，而要专门设计一个名为 quicklist 的复杂结构呢？这个问题值得深入探究，它背后隐藏着Redis工程团队为解决内存与性能矛盾所做的精妙权衡。
一、从一个“翻车”的设计说起
早期Redis的List底层确实使用了双向链表（adlist）。每个节点独立分配内存，通过prev和next指针串联，逻辑简单直观。但它存在一个无法忽视的硬伤：内存碎片化极其严重。
双向链表的内存现实：
[节点A]──→[节点B]──→[节点C]──→[节点D]
↑ ↑ ↑ ↑
堆上某处 堆上某处 堆上某处 堆上某处
每个节点：prev指针(8B) + next指针(8B) + value指针(8B) + 实际数据
存1000个小字符串，光指针开销就是 1000 × 24 = 24000 字节
实际数据可能才几千字节，指针比数据还多
为了解决这个问题，Redis引入了ziplist——将多个元素紧凑地塞进一块连续内存，彻底省掉指针开销。然而，ziplist又带来了新麻烦：每次插入或删除都可能触发整块内存的realloc，并伴随着恐怖的“连锁更新（cascade update）”问题。数据量一大，性能会急剧下降。
两种结构，各有各的死穴。Redis的工程师没有二选一，而是做了一个更聪明的决定：将两者的优点结合起来，让它们的缺点相互对冲。这个融合的产物就是quicklist。
二、quicklist是什么？一句话说清楚
quicklist = 双向链表 × listpack
每个链表节点不再只存储一个元素，而是存储一个 listpack（一种紧凑型的小数组）。一个listpack内部可以容纳多个元素。
quicklist 整体结构：
head tail
↓ ↓
[node1] ←──→ [node2] ←──→ [node3] ←──→ [node4]
↓ ↓ ↓ ↓
[lp: e1,e2,e3] [lp: e4,e5] [lp: e6,e7,e8] [lp: e9,e10]
每个 node 内部是一个 listpack（连续内存块）
多个 node 通过双向链表串联
这种设计的优势显而易见：
- listpack内部紧凑存储，没有指针浪费，内存利用率高。
- 链表节点数量大幅减少，prev/next指针的固定开销被大量元素稀释。
- 单个listpack体积可控，即使发生realloc，代价也很小，避免了全量数据迁移的风险。
一举三得，完美中和了纯链表和纯ziplist的缺陷。
三、还不够：再加一层LZF压缩
如果仅仅是“链表套listpack”，Redis的优化还不算极致。它在quicklist之上又叠加了第三层设计：LZF压缩。
思路非常直接：对于一个很长的List，两端的节点经常被访问（例如执行LPUSH、RPOP），而中间的节点则可能长时间处于“冷”状态。既然这些中间节点访问频率低，为什么不把它们压缩起来以节省内存呢？
compress depth = 2 时的内存状态：
[node1] [node2] | [node3] [node4] ... [nodeN-3] [nodeN-2] | [nodeN-1] [nodeN]
不压缩 不压缩 | 压缩 压缩 压缩 压缩 | 不压缩 不压缩
←── 热区 ──────→|←──────────── 冷区（LZF压缩） ──────────→|←─── 热区 ──────→
compress depth 这个参数决定了链表两端各保留多少个不压缩的“热”节点，中间部分则全部使用LZF压缩存储。当需要访问中间被压缩的节点时，Redis会实时将其解压，操作完成后再视情况压缩回去。
至此，quicklist的三层设计哲学完全展现：链表结构提供灵活性 + listpack紧凑存储提升内存效率 + LZF冷数据压缩进一步节省空间。 每一层都在解决上一层遗留的问题，每一层都是工程实践中最务实的权衡。
四、节点分裂与合并：动态平衡的艺术
深入quicklist源码，有一个操作细节非常精妙，即 _quicklistSplitNode —— 节点分裂。
什么时候需要分裂？当你要向一个已经存满（达到fill参数限制）的listpack中间插入新元素时。此时，这个listpack已无空间容纳新成员。解决方案是：将这个listpack从中间“劈开”，变成两个独立的quicklist节点，然后再执行插入操作。
分裂前：
[node]: [e1][e2][e3][e4][e5] ← listpack已满，要在e3后面插入新元素
分裂过程：
step1: 以 e3 为界，创建左节点 [e1][e2][e3]
step2: 创建右节点 [e4][e5]
step3: 原节点从链表中移除
step4: 左右节点插入链表
step5: 在左节点尾部 或 右节点头部 插入新元素
分裂后：
[node_left]: [e1][e2][e3][new] ←──→ [node_right]: [e4][e5]
分裂解决了插入问题，但可能会产生大量只包含少数元素的“小节点”，这又违背了quicklist减少节点数量的初衷。因此，Redis还会在适当时机尝试 _quicklistMergeNodes（节点合并） ，将相邻的小容量listpack合并成一个节点。
分裂为了插入，合并为了整理。这一张一弛的动态管理逻辑，确保了quicklist在频繁操作下依然能维持较高的内存利用率和操作效率，是系统设计思维的绝佳体现。如果你想深入理解这类工程权衡，可以参考云栈社区上关于后端架构的讨论。
五、listpack：被低估的主角
在讨论quicklist时，很多人把listpack当作一个配角一笔带过。但实际上，listpack本身就是一个非常重要的数据结构革新。
listpack是Redis 7.0中用来替代ziplist的新结构，它根治了ziplist“连锁更新”这个老大难问题。
listpack 内存布局：
total_bytes(4B) num_elements(2B) entry...entry end(1B=0xFF)
───────────────────────────────────────────────────────────────
│ 总字节数 │ 元素个数 │ 各元素编码 │ 结束标志 │
───────────────────────────────────────────────────────────────
每个 entry 的结构：
encoding + data + backlen
其中 backlen 记录当前 entry 的总长度
→ 向前遍历时只需读 backlen，不依赖前驱节点长度
→ 彻底消灭了 ziplist 的连锁更新
listpack的每个entry都在尾部自带一个 backlen 字段，用于记录当前entry的总长度。当需要向前遍历时，直接读取前一个entry的 backlen 就能找到其起始位置，不再需要依赖前驱节点的长度信息。正是这个小改动，彻底斩断了连锁更新的传播链。这不仅仅是优化，更是对一个经典工程缺陷的根本性修复。作为数据库与中间件领域的核心组件，理解listpack的设计至关重要。
六、quicklist：最能锻炼工程思维的数据结构
学习SDS，你能理解精巧的内存布局设计；学习Dict，你能掌握渐进式重哈希的妙处；学习Intset，你会明白什么是按需编码的优化。
但quicklist带给你的思考维度是不同的。它将链表、紧凑数组、数据压缩这三种独立的技术组合在一起，每一层都解决一个特定问题，组合之后又催生了新的挑战（如节点分裂与合并），进而需要更上层的逻辑来管理。这种 “组合式设计” 和 “解决新问题” 的循环，正是复杂系统演进的缩影。
掌握quicklist后，当你在工作中面临没有完美解决方案的困境时，你的第一反应可能会变成：能否将两个各有优劣的方案组合起来，让它们的优点叠加，缺点互相抵消？ 这种从单一结构思维跃升到系统组合思维的能力，是研究quicklist最大的收获。
结语
从单纯的双向链表，到引入ziplist，再到融合两者优点并加入压缩层诞生quicklist，最后用更先进的listpack替代ziplist，Redis List的底层演进史，就是一部不断在时间、空间、实现复杂度之间寻求最佳平衡点的工程哲学史。
理解quicklist，不仅是理解一个数据结构，更是学习一种解决复杂系统问题的思维方法。如果你对这类深度剖析数据结构与系统设计的内容感兴趣，欢迎在云栈社区与更多开发者交流探讨。
💬 你觉得quicklist三层设计（链表+listpack+LZF压缩）里，哪一层最让你觉得巧妙？
发表于 1 小时前
|
查看: 2|
回复: 0
