Redis 源码剖析与实战
蒋德钧
中科院计算所副研究员
17049 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
Redis 源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

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 源码剖析与实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(22)

  • 最新
  • 精选
  • Kaito
    1、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 数据类型用到了 listpack
    6
    41
  • lzh2nix
    从ziplist--->quickList这在计算机里也是一个常见的设计模式。 为了防止单个数据表太大,我们将其拆分成多个数据表,也叫 [分桶设计],数据库中的sharding,以及将一个大粒度的锁拆分成多个小粒度的锁都是类似的思想。
    12
  • 一步
    listpack 解决了 ziplist 连锁更新的问题,但是还是没有解决元素多的时候,查询复杂度高的问题
    4
  • 曾轼麟
    回答老师的提问,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的最大值
    2
    3
  • Geek_0cfc2d
    老师,有个问题想请教一下: listpack 中如果不考虑逆序查询,entry 其实使用 encoding+data 就可以,那 entry 中最后一个 len 其实是为了逆序遍历而加入的,这样理解对吗?
    1
  • 胡玲玲
    请问ziplist、quicklist、listpack 这三者是如何协助redis的数据类型的呢
    1
  • dawn
    如果数据存在连续内存里,针对插入和删除操作,只要不是最后一个节点,不都需要给后续的节点重新分配内存地址嘛,listpack并没有解决这个问题啊?而quicklist解决这个问题是方式,实际上是用了链表而非连续空间,牺牲了空间来解决这个事的,那还不如直接全上链表,根据类型归类也挺麻烦的
    归属地:江苏
  • 🤐
    作为一个写JAVA的,有点理解不了这里
  • 孤独患者
    quicklist,如果更新某个节点数据,导致节点内存变大了,那是不是当前节点的后续节点都要往后移动呢?因为内存是连续的
    1
  • 柏油
    在连锁更新代码块中,只看到调用了一次ziplistResize进行内存重分配;在这之前会将所有连锁更新影响的entry找出来,并重新计算len,这样就可以一次性计算得到所有需要的内存大小,也就是只有一次ziplistResize内存重新分配。不过,可能会调用多次memmove来调整元素的位置。 文章中: “ziplist 新增某个元素或修改某个元素时,可能会导致后续元素的 prevlen 占用空间都发生变化,从而引起连锁更新问题,导致每个元素的空间都要重新分配” 每个元素都会进行内存重分配是不是有问题?还望解答
    1
收起评论
显示
设置
留言
22
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部