从压缩列表到快速列表的链表进化
2010 年,List 类型诞生。底层采用 ziplist 压缩列表, 元素连续存储,内存紧凑,适合小数据量场景。
引入 linkedlist(双向链表)作为大数据量 List 的底层实现。 当列表元素增长超过 ziplist 阈值时,自动转换为链表。
完善编码转换机制。当列表元素 ≤ list-max-ziplist-entries 时使用 ziplist, 超过阈值时转换为 linkedlist。
革命性突破!引入 quicklist 作为 List 的唯一底层实现。 它是 ziplist 和 linkedlist 的完美结合:每个节点是一个 ziplist, ziplist 之间用双向链表连接。
优化 quicklist 的 push/pop 操作,减少内存碎片。 引入新的参数 list-compress-depth 控制压缩深度。
Redis 7.0 将 quicklist 内部的 ziplist 替换为 listpack。 解决了 ziplist 删除元素时的级联更新问题,性能更稳定。
quicklist = linkedlist(连接) + ziplist/listpack(存储)
Redis List 的演进是一部"取长补短"的历史:
ziplist(紧凑但 O(n) 删除)+
linkedlist(灵活但费内存)=
quicklist(完美平衡)
核心设计哲学:
分而治之 — 大链表拆成多个小 ziplist
双向遍历 — linkedlist 保留首尾指针
按需压缩 — LZF 减少冷数据内存
最终实现:O(1) 头尾操作 +
紧凑内存存储 +
无级联更新