Redis 为什么不用链表保存 List？QuickList 到底是什么？
上一篇我们讲了《Redis String 为什么不是 String？SDS 到底解决了什么问题？》，知道了 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 的原因。
为什么后来又出现了 ListPack？
Redis 并没有停止优化，后来官方发现：ZipList 本身还有不少设计缺陷。于是重新设计了一种结构：
ListPack相比 ZipList。
它：
- 编码更加简单。
- 避免连锁更新。
- 内存利用率更高。
- 更容易维护。
于是现在的 Redis 真正使用的是：
QuickList │ ▼ ListPack也就是说 QuickList 没变，只是里面保存的数据 从 ZipList 升级成了 ListPack
Redis 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 为什么不是 String？SDS 到底解决了什么问题？》
下一篇：《Redis 为什么使用跳表，而不是红黑树？》
如果这篇文章让你第一次知道Redis List 早就不是链表了，欢迎点赞、收藏。
你以前回答过"Redis List 底层是双向链表"吗？欢迎在评论区聊聊你的看法。
