06 | 从ziplist到quicklist，再到listpack的启发
蒋德钧
你好，我是蒋德钧。
在前面的第 4 讲，我介绍 Redis 优化设计数据结构来提升内存利用率的时候，提到可以使用压缩列表（ziplist）来保存数据。所以现在你应该也知道，ziplist 的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，以达到节省内存的目的。
但是，在计算机系统中，任何一个设计都是有利有弊的。对于 ziplist 来说，这个道理同样成立。
虽然 ziplist 节省了内存开销，可它也存在两个设计代价：一是不能保存过多的元素，否则访问性能会降低；二是不能保存过大的元素，否则容易导致内存重新分配，甚至可能引发连锁更新的问题。所谓的连锁更新，简单来说，就是 ziplist 中的每一项都要被重新分配内存空间，造成 ziplist 的性能降低。
因此，针对 ziplist 在设计上的不足，Redis 代码在开发演进的过程中，新增设计了两种数据结构：quicklist 和 listpack。这两种数据结构的设计目标，就是尽可能地保持 ziplist 节省内存的优势，同时避免 ziplist 潜在的性能下降问题。
今天这节课，我就来给你详细介绍下 quicklist 和 listpack 的设计思想和实现思路，不过在具体讲解这两种数据结构之前，我想先带你来了解下为什么 ziplist 的设计会存在缺陷。这样一来，你在学习 quicklist 和 listpack 时，可以和 ziplist 的设计进行对比，进一步就能更加容易地掌握 quicklist 和 listpack 的设计考虑了。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
Redis数据结构设计的优化思路通过取舍内存开销和访问性能之间的平衡，从ziplist到quicklist再到listpack的演进，展现了Redis优化设计数据结构的思路。文章首先介绍了ziplist的设计特点和不足，指出了查找复杂度高和潜在的连锁更新风险。随后，文章详细介绍了quicklist和listpack的设计思想和实现思路，旨在保持ziplist节省内存的优势的同时避免其潜在的性能下降问题。通过对比这三种数据结构的设计，读者可以更好地理解它们之间的区别和优劣势，为应对相关面试题和开发高效的数据结构提供了有益的参考。文章内容涵盖了Redis数据结构的优化设计思想，对读者了解Redis内存优化具有一定的指导意义。文章深入探讨了ziplist在新插入元素时可能引起的连锁更新问题，以及对应的内存分配操作，进而引出了quicklist和listpack的设计思想，为读者提供了对Redis数据结构优化设计的深入理解和思考。Redis的数据结构设计在内存开销和访问性能之间进行了取舍，从ziplist到quicklist再到listpack的演进，展现了Redis优化设计数据结构的思路。文章深入探讨了ziplist在新插入元素时可能引起的连锁更新问题，以及对应的内存分配操作，进而引出了quicklist和listpack的设计思想，为读者提供了对Redis数据结构优化设计的深入理解和思考。Redis在内存紧凑型列表的设计与实现上，从ziplist到quicklist，再到listpack，展现了在内存空间开销和访问性能之间的设计取舍，这一系列的设计变化，是非常值得学习的。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《Redis 源码剖析与实战》，新⼈⾸单¥59
《Redis 源码剖析与实战》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(22)
- 最新
- 精选
Kaito1、ziplist 设计的初衷就是「节省内存」，在存储数据时，把内存利用率发挥到了极致： - 数字按「整型」编码存储，比直接当字符串存内存占用少 - 数据「长度」字段，会根据内容的大小选择最小的长度编码 - 甚至对于极小的数据，干脆把内容直接放到了「长度」字段中（前几个位表示长度，后几个位存数据） 2、但 ziplist 的劣势也很明显： - 寻找元素只能挨个遍历，存储过长数据，查询性能很低 - 每个元素中保存了「上一个」元素的长度（为了方便反向遍历），这会导致上一个元素内容发生修改，长度超过了原来的编码长度，下一个元素的内容也要跟着变，重新分配内存，进而就有可能再次引起下一级的变化，一级级更新下去，频繁申请内存 3、想要缓解 ziplist 的问题，比较简单直接的方案就是，多个数据项，不再用一个 ziplist 来存，而是分拆到多个 ziplist 中，每个 ziplist 用指针串起来，这样修改其中一个数据项，即便发生级联更新，也只会影响这一个 ziplist，其它 ziplist 不受影响，这种方案就是 quicklist： qucklist: ziplist1(也叫quicklistNode) <-> ziplist2 <-> ziplist3 <-> ... 4、List 数据类型底层实现，就是用的 quicklist，因为它是一个链表，所以 LPUSH/LPOP/RPUSH/RPOP 的复杂度是 O(1) 5、List 中每个 ziplist 节点可以存的元素个数/总大小，可以通过 list-max-ziplist-size 配置： - 正数：ziplist 最多包含几个数据项 - 负数：取值 -1 ~ -5，表示每个 ziplist 存储最大的字节数，默认 -2，每个ziplist 8KB ziplist 超过上述任一配置，添加新元素就会新建 ziplist 插入到链表中。 6、List 因为更多是两头操作，为了节省内存，还可以把中间的 ziplist「压缩」，具体可看 list-compress-depth 配置项，默认配置不压缩 7、要想彻底解决 ziplist 级联更新问题，本质上要修改 ziplist 的存储结构，也就是不要让每个元素保存「上一个」元素的长度即可，所以才有了 listpack 8、listpack 每个元素项不再保存上一个元素的长度，而是优化元素内字段的顺序，来保证既可以从前也可以向后遍历 9、listpack 是为了替代 ziplist 为设计的，但因为 List/Hash/Set/ZSet 都严重依赖 ziplist，所以这个替换之路很漫长，目前只有 Stream 数据类型用到了 listpack2021-08-07644
lzh2nix从ziplist--->quickList这在计算机里也是一个常见的设计模式。 为了防止单个数据表太大，我们将其拆分成多个数据表，也叫 [分桶设计]，数据库中的sharding，以及将一个大粒度的锁拆分成多个小粒度的锁都是类似的思想。2021-08-1512
奕listpack 解决了 ziplist 连锁更新的问题，但是还是没有解决元素多的时候，查询复杂度高的问题2021-08-085
曾轼麟回答老师的提问，ziplist 能支持的最大整数是多大？ 分析步骤： 1、按照问题范围，首先我去查看了zipTryEncoding的实现（ziplist.c），其中在给encoding赋值的时候划分了：极小值，int8，int16，int24，int32和int64 2、此外发现当value大于int32最大值的时候，会统一使用ZIP_INT_64B去编码 3、但是在zipTryEncoding开头处发现了一个判断，entrylen >= 32的时候是不允许编码，意思就是传入的数据如果entrylen大于32直接跳过不编码为int 4、最后调用string2ll尝试将string value编码为long long(转换成功为1失败为0) 5、若转换成功，编码类型放到encoding中，值放到v中 根据第三步个人判断，传入的int值大小不会超过32位，那么最大值应该就是int32的最大值2021-08-0823- Geek_0cfc2d老师，有个问题想请教一下： listpack 中如果不考虑逆序查询，entry 其实使用 encoding+data 就可以，那 entry 中最后一个 len 其实是为了逆序遍历而加入的，这样理解对吗？2022-02-2311
- 胡玲玲请问ziplist、quicklist、listpack 这三者是如何协助redis的数据类型的呢2021-08-071
dawn如果数据存在连续内存里，针对插入和删除操作，只要不是最后一个节点，不都需要给后续的节点重新分配内存地址嘛，listpack并没有解决这个问题啊？而quicklist解决这个问题是方式，实际上是用了链表而非连续空间，牺牲了空间来解决这个事的，那还不如直接全上链表，根据类型归类也挺麻烦的2022-08-29归属地：江苏
🤐作为一个写JAVA的，有点理解不了这里2022-07-24
孤独患者quicklist，如果更新某个节点数据，导致节点内存变大了，那是不是当前节点的后续节点都要往后移动呢？因为内存是连续的2022-06-151
柏油在连锁更新代码块中，只看到调用了一次ziplistResize进行内存重分配；在这之前会将所有连锁更新影响的entry找出来，并重新计算len，这样就可以一次性计算得到所有需要的内存大小，也就是只有一次ziplistResize内存重新分配。不过，可能会调用多次memmove来调整元素的位置。 文章中： “ziplist 新增某个元素或修改某个元素时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配” 每个元素都会进行内存重分配是不是有问题？还望解答2022-01-051
收起评论
