Redis 为什么不用链表保存 ListQuickList 到底是什么上一篇我们讲了《Redis String 为什么不是 StringSDS 到底解决了什么问题》知道了 Redis 并没有直接使用 C 语言原生字符串而是重新设计了 SDS。今天继续来看 Redis 的另一个经典数据结构 —— List。很多人学习 Redis 时都会看到一句话Redis List 底层是双向链表。这句话曾经是对的但如果你今天还这样回答面试官大概率会被追问。因为Redis 早就不用传统链表保存 List 了。其实链表并没有我们想象中那么优秀。链表最大的优点是什么大学数据结构课上我们都学过链表。它最大的特点就是插入快、删除快、不用移动元素例如A - B - C插入一个 D。A - B - D - C只需要修改几个指针即可。时间复杂度O(1)看起来非常优秀所以很多人都会认为List 不就应该用链表吗Redis 最开始也是这么想的。为什么后来放弃了链表链表虽然插入快但它有两个非常致命的问题。第一非常浪费内存来看一个节点。Node ├── prev ├── next └── value真正的数据只有value另外两个指针完全是为了维护链表关系。假设保存100 万个元素那么就会多出200 万个指针在 64 位系统上每个指针通常占 8 字节意味着仅仅维护指针就可能消耗十几 MB 的内存对于 Redis 这种内存数据库来说这是非常昂贵的成本。第二CPU 不喜欢链表Redis 的性能并不仅仅来自算法还来自 CPU。来看两个数组。A B C D E F G它们连续存放 CPU 读取 A 的时候通常会把后面的B C D E一起加载进缓存下一次访问几乎不用访问内存。这就是CPU Cache但是链表呢可能变成A ------ 北京 B ------ 上海 C ------ 广州每个节点都在不同位置CPU 每访问一个节点都可能重新访问内存Cache 命中率非常低虽然理论时间复杂度一样实际速度却慢很多。Redis 想到了一个折中的办法既然连续内存访问快链表插入快那有没有可能**把两者结合起来**于是 Redis 想出了 ZipList它长这样---------------------------------- | A | B | C | D | E | F | G | ----------------------------------所有元素连续存储这样内存占用更少。CPU Cache 命中率更高。遍历速度非常快。很多小 List性能比链表好得多。ZipList 为什么又被淘汰了看到这里很多人会觉得那直接一直用 ZipList 不就好了问题来了如果现在A B C D E中间插入一个元素。A B X C D E后面的数据都要整体移动元素越多移动成本越高。另外ZipList 还有一个经典问题连锁更新Cascade Update。例如前一个节点长度变化后一个节点保存长度的字段也可能变化。于是一个节点变后面很多节点都要重新调整最坏情况下可能导致整个 ZipList 都发生更新这也是 Redis 后来放弃 ZipList 的重要原因。QuickList 是怎么诞生的Redis 的思路非常简单既然链表内存浪费ZipList 插入又慢那就不要让链表保存数据而是链表保存 ZipList最终变成--------- --------- --------- | ZipList | -- | ZipList | -- | ZipList | --------- --------- ---------每个节点不是一个元素而是一小段连续内存这就是QuickList它兼顾了两者优点。节点之间插入删除。仍然很快。每个节点内部连续存储。CPU Cache 命中率很高。指针数量大幅减少。内存占用更低这也是 Redis 3.2 开始采用 QuickList 的原因。为什么后来又出现了 ListPackRedis 并没有停止优化后来官方发现ZipList 本身还有不少设计缺陷。于是重新设计了一种结构ListPack相比 ZipList。它编码更加简单。避免连锁更新。内存利用率更高。更容易维护。于是现在的 Redis 真正使用的是QuickList │ ▼ ListPack也就是说 QuickList 没变只是里面保存的数据 从 ZipList 升级成了 ListPackRedis List 为什么一直在演进如果把整个过程串起来其实非常清晰最开始Redis 使用LinkedList后来发现 内存浪费Cache 不友好于是改成 ZipList后来又发现插入效率下降还有连锁更新。于是Redis 再次升级QuickList最后为了进一步优化内部又把ZipList ↓ ListPack整个演进过程如下LinkedList │ ▼ ZipList │ ▼ QuickList │ ▼ QuickList ListPack这也是为什么很多老文章已经过时了因为 Redis 的底层实现一直在不断优化。Redis 为什么最终选择 QuickList现在我们回到最开始的问题为什么不用链表保存 List答案其实很简单链表虽然插入快但是太占内存。Cache 命中率低。遍历性能一般。而连续内存虽然遍历快但插入代价又太高QuickList 正好结合了两者的优点既保留了链表灵活插入的能力又利用连续内存提高了遍历效率。因此它成为 Redis List 最终的实现方案这也是 Redis 一直坚持的设计思想没有绝对最好的数据结构只有最适合当前场景的数据结构。总结很多人记住了一句话Redis List 底层是链表。但真正理解 Redis 的人会知道这只是历史。Redis 为了性能经历了LinkedList ↓ ZipList ↓ QuickList ↓ QuickList ListPack每一次升级都不是推倒重来。而是在不断寻找内存占用、CPU Cache、插入效率、遍历性能之间的最佳平衡。这也是 Redis 能一直保持高性能的重要原因。上一篇《Redis String 为什么不是 StringSDS 到底解决了什么问题》下一篇《Redis 为什么使用跳表而不是红黑树》如果这篇文章让你第一次知道Redis List 早就不是链表了欢迎点赞、收藏。你以前回答过Redis List 底层是双向链表吗欢迎在评论区聊聊你的看法。