Redis List 数据结构演进史

从压缩列表到快速列表的链表进化

Redis 2.0

ziplist 实现 List

2010 年,List 类型诞生。底层采用 ziplist 压缩列表, 元素连续存储,内存紧凑,适合小数据量场景。

// ziplist 结构
|zlbytes|zltail|zllen|elem1|elem2|...|zlend|

• zlbytes: 总字节数 (4 bytes)
• zltail: 尾偏移量 (4 bytes)
• zllen: 元素数 (2 bytes)
• zlend: 结束标记 (0xFF)
连续内存 O(1) LPUSH/RPOP 小数据友好
Redis 2.2

linkedlist 登场

引入 linkedlist(双向链表)作为大数据量 List 的底层实现。 当列表元素增长超过 ziplist 阈值时,自动转换为链表。

// linkedlist 节点
listNode *prev 8 bytes
void *value 8 bytes
listNode *next 8 bytes
每节点: 24 bytes + 指针开销
O(1) 头插/尾插 双向遍历 无长度限制
Redis 2.4

ziplist ↔ linkedlist 转换

完善编码转换机制。当列表元素 ≤ list-max-ziplist-entries 时使用 ziplist, 超过阈值时转换为 linkedlist。

// 转换条件 (Redis 2.4)
ziplist: 元素数 ≤ 512
linkedlist: 元素数 > 512
自动编码切换 阈值可配置
Redis 3.2 ⭐ 重大变革

quicklist 统一天下

革命性突破!引入 quicklist 作为 List 的唯一底层实现。 它是 ziplist 和 linkedlist 的完美结合:每个节点是一个 ziplist, ziplist 之间用双向链表连接。

// quicklistNode
quicklistNode *prev
quicklistNode *next
unsigned char *zl
size
count
// quicklist
quicklistNode *head
quicklistNode *tail
count
fill
compress
ziplist + linkedlist LZF 压缩 参数可调
Redis 4.0

quicklist 优化

优化 quicklist 的 push/pop 操作,减少内存碎片。 引入新的参数 list-compress-depth 控制压缩深度。

// list-compress-depth
0: 不压缩
1: 头部和尾部各 1 个不压缩
2: 头尾各 2 个不压缩
...
目的: 减少 CPU 开销,保留热点访问
LZF 深度压缩 内存优化 尾部压缩
Redis 7.0+ ⭐ 底层升级

listpack 替换 ziplist

Redis 7.0 将 quicklist 内部的 ziplist 替换为 listpack。 解决了 ziplist 删除元素时的级联更新问题,性能更稳定。

// listpack vs ziplist
ziplist:
  每个节点存前节点长度
  → 删除中间节点需更新后续所有节点

listpack:
  只存总长度,逆向遍历
  → 删除任意节点只需更新长度字段
listpack 编码 无级联更新 向后兼容

quicklist 数据结构可视化

quicklist = linkedlist(连接) + ziplist/listpack(存储)

quicklist 结构示意
HEAD ←──────────────────────────────────→ TAIL
zl[0]
zl[1]
zl[2]
zl[n]
↑ prev/next 双向指针 ↑
// 单个 ziplist/listpack 内部
|zlbytes|zltail|zllen|elem1|elem2|elem3|...|zlend|

连续内存,CPU 缓存友好
每个 ziplist 默认 ≤ 8KB
// 链表连接
quicklistNode.prev → 前一个 ziplist
quicklistNode.next → 后一个 ziplist

双向遍历,O(1) 头尾操作

List 底层实现对比

内存效率

ziplist ★★★★★
linkedlist ★★☆☆☆
quicklist ★★★★☆

操作复杂度

LPUSH/RPOP O(1)
LINDEX O(n)
LINSERT O(n)

级联更新

ziplist ❌ 存在
linkedlist ✅ 无
listpack ✅ 无

适用场景

quicklist 主流选择
ziplist 元素<64 & 数量少
listpack 7.0+ 内部存储

演进总结

Redis List 的演进是一部"取长补短"的历史:

ziplist(紧凑但 O(n) 删除)+ linkedlist(灵活但费内存)= quicklist(完美平衡)

核心设计哲学:
分而治之 — 大链表拆成多个小 ziplist
双向遍历 — linkedlist 保留首尾指针
按需压缩 — LZF 减少冷数据内存

最终实现:O(1) 头尾操作 + 紧凑内存存储 + 无级联更新