Redis系列(八)底层数据结构之紧凑列表

• 前言
• 定义
• 总结
• 参考文章
• 联系我

前言

Redis 已经是大家耳熟能详的东西了&＃xff0c;日常工作也都在使用&＃xff0c;面试中也是高频的会涉及到&＃xff0c;那么我们对它究竟了解有多深刻呢&＃xff1f;

我读了几本 Redis 相关的书籍&＃xff0c;尝试去了解它的具体实现&＃xff0c;将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中底层的 listpack&＃xff08;紧凑列表&＃xff09; 的实现方法。 它是 Redis 的 Stream 用到的数据结构之一。

定义

Redis 设计 listpack 的目的就是取代 ziplist, 在 Redis 系列&＃xff08;三&＃xff09;底层数据结构之压缩列表 中我们提到&＃xff0c;ziplist 在极小的概率下有可能发生级联更新&＃xff0c;当连续规模较大的级联更新发生时&＃xff0c;对 Redis 的性能有比较大的影响。

虽然我们都知道这是极小的概率&＃xff0c;但是这种设计缺陷却不能被 Redis 的大佬作者所接受&＃xff0c;因此在 5.0 版本中新引入了一个数据结构&＃xff0c;名叫 listpack, 大家都将它翻译为 紧凑列表.

它的定义和 ziplist 极其相似&＃xff0c;只是通过一些新的设计&＃xff0c;来解决 ziplist 中的痛点问题。因此本文的讲解基于读者已经了解 ziplist.

ziplist的定义如下&＃xff1a;
注意&＃xff1a;这是 ziplist 的定义

struct ziplist<T>{// 整个压缩列表占用字节数int32 zlbytes;// 最后一个节点到压缩列表起始位置的偏移量&＃xff0c;可以用来快速的定位到压缩列表中的最后一个元素int32 zltail_offset;// 压缩列表包含的元素个数int16 zllength;// 元素内容列表&＃xff0c;用数组存储&＃xff0c;内存上紧挨着T[] entries;// 压缩列表的结束标志位&＃xff0c;值永远为 0xFF.int8 zlend;
}


listpack 的定义和上方基本一致&＃xff0c;只是去掉了 zltail_offset 属性。

让我们回想一下&＃xff0c;ziplist 中用这个属性做什么&＃xff1f;用来方便的找到最后一个节点&＃xff0c;然后方便进行反向的遍历。新的 listpack 当然是解决了这个问题&＃xff0c;才能放心的删除掉这个属性。

listpack节点的定义如下&＃xff1a;

int<var> encoding;
optional byte[] content;
int<var> length;


相比于 ziplist 的定义&＃xff0c;它有两点改动&＃xff1a;

1. 记录的长度不再是前一个节点的长度&＃xff0c;而是自己的长度。
2. 将记录自己的长度放到了节点的尾部。

这样做的好处是&＃xff1a;

1. 不再需要 zltail_offset 属性也可以快速定位到最后一个节点。用listpac 的总长度-最后一个节点的长度.
2. 每个节点记录自己的长度&＃xff0c;当本节点的值发生了改变&＃xff0c;只需要更改自己的长度即可。不再需要更改别的节点的属性&＃xff0c;也就彻底的解决掉了级联更新问题。

总结

listpack 是 Redis 设计用来取代掉 ziplist 的数据结构&＃xff0c;它通过每个节点记录自己的长度&＃xff0c;且放在节点的尾部&＃xff0c;来彻底解决掉了 ziplist 存在的级联更新的问题。

listpack 在 5.0 版本引入&＃xff0c;但是由于 ziplist 在 Reids 内部的使用太过于广泛&＃xff0c;有一些兼容问题&＃xff0c;我们可以预见这将是一个逐步的替换过程。

同样在 5.0 版本引入的 Stream 数据结构中&＃xff0c;就使用了 listpack 而不是 ziplist.

参考文章

《Redis 的设计与实现&＃xff08;第二版&＃xff09;》

《Redis 深度历险&＃xff1a;核心原理和应用实践》

完。

联系我

最后&＃xff0c;欢迎关注我的个人公众号【 呼延十 】&＃xff0c;会不定期更新很多后端工程师的学习笔记。
也欢迎直接公众号私信或者邮箱联系我&＃xff0c;一定知无不言&＃xff0c;言无不尽。

以上皆为个人所思所得&＃xff0c;如有错误欢迎评论区指正。

欢迎转载&＃xff0c;烦请署名并保留原文链接。

联系邮箱&＃xff1a;huyanshi2580&＃64;gmail.com

更多学习笔记见个人博客或关注微信公众号 <呼延十 >------>呼延十