Redis源码学习之压缩列表

压缩列表是列表对象、哈希对象和有序集合对象的底层实现之一。以列表对象为例,当列表节点都是比较小的整数或者比较短的字符串的时候,Redis就会选择压缩列表来做底层实现。其实,压缩列表就是一个字节数组,我们知道,在虚拟存储器中以连续的形式存放数据,可以避免产生内存碎片,提高存储器利用率,而压缩列表正是因此而设计的。当然,这种存储结构也有其局限性,这也是为什么高级对象是有选择的使用它的原因。

压缩列表的实现

1.数据结构

前文中提到,压缩列表就是一块连续的内存空间,是一个字节数组。

所有的操作都是基于这块内存进行编排,比如压缩列表初始化会申请一块空间:

注释中可以看出,一个空的压缩列表占用了11个字节的内存空间。

  1. 前4个字节分配给zlbytes,表示整个压缩列表所占字节数(空列表就是11)
  2. 接着4个字节分配给zltail,表示从压缩列表第一个字节距离表尾节点的字节数(空列表是10)
  3. 两个字节分配给zllen,表示压缩列表的节点个数(空列表是0),由于只有两个字节的空间,所以最大只能存储到65535,如果节点数大于65535,那么只能遍历整个列表求长度了,复杂度将从O(1)升至O(N);
  4. 最后的一个字节作为表尾标志位,写死为0xFF。

所以,一个空列表在存储器中是这样分布的:

这里的一个小方格代表1个字节,我们可以看到指针p指向压缩列表头部,将zltail中的值取出来与p相加就是尾节点了,由于目前是空列表,所以指向的是zlend。

2.节点

节点分为3个区块,分别为前置节点长度prevEntryLength,当前节点编码及长度encoding,以及当前节点内容content。例如,一个前置节点长度为255,当前节点长度16384的节点在内存中是这样分布的:

其中,content部分比较简单,就是存储了具体的数据,可以叫做节点体部。而prevEntryLength和encoding所占字节数是根据其本身存储的数据大小而变化的,这两部分放到可以称为节点头部。下面我们着重说一下这两个部分的设计。

  1. prevEntryLength 为什么要单独存放每个节点的前置节点大小呢?主要是压缩列表实现的也是一个双端链表,不仅要能够从头向尾遍历,也要能够反过来进行列表遍历,有了前置节点长度,我就可以先通过zltail找到尾节点,然后通过【当前节点指针减去前置节点所占字节数】一步一步向前遍历了。编码代码如下:

为了便于理解,我对源码稍作了修改。这里可以看出,prevEntryLength有两种情况: i.第一种占用1个字节空间,即当前置节点长度小于254的时候,直接把长度存到这个字节里即可,这里可能会有点迷惑,1个字节是8位,无符号整数范围是[0,255],所以最大应该可以存255,为什么这里特意避开呢?主要是因为前文说到了zlend标志位已经占用0xFF(255)了,所以这里再用会产生冲突,导致程序判断错误,同理0xFE(254)也被当前判断占用,所以这两个数字被放进了另一种情况, ii.第二种占用5个字节空间,这里的第一个字节会放进标志位0xFE(254),后面4个字节存放实际长度,比如我之前给出的例子中,5个字节是[254,255,0,0,0]就是这样的出来的。 相对应的解码代码如下,传入preEncodeLength起始地址,即可解析出长度所占字节数以及长度数值。

  1. encoding 这部分主要表示当前节点content部分的长度,以及这个长度值所使用的编码。这里也有两种情况,通过判断存储的数据是整数类型还是字符串类型。 i.如果是整数类型,判断其编码类型的代码如下:

可以看出encoding用一个字节作为编码类型的存储空间。其中,当存入的节点数值在[0,12]这个区间时,直接将该值融合到这一个字节的后4位,也就不需要content部分了。例如,前置节点长度为1,当前节点值为11的节点内存分布如下图所示:

可以看出,这种情况下,整个节点只需要两个字节的内存空间。如果节点值大于12,比如前置节点长度为1,当前节点值为128的节点,我们会判断出他在8位有符号整数中会溢出,在16位有符号整数范围内,因此encoding编码为0b11110000,content占用两个字节空间,分布如下:

可见,该节点占用4个字节空间,比简单使用类型int64(8字节)节省了5个字节(抛出前置节点长度部分)。所以这也是为什么压缩列表更适合存储数值较小的节点了。 ii.如果是字符串类型,判断其编码类型代码如下:

可以看出,通过字符串长度将其分为3种情况,对应encoding部分占用1个字节、2个字节和5个字节。比如前置节点长度为1,当前节点值为字符串hello的内存布局示意图为:

可以看出,该节点总共占用7个字节。 iii.encoding部分解码代码如下:

iiii.将头部转换为zlEntry结构,我们可以通过把连续空间中的字节拆分转换为一个节点结构,这样更加直观的看到各个字段的值:

以前文中的前置节点长度为255,当前节点长度为16384为例,编写测试用例如下:

输出为: prevrawlen:255 prevrawlensize:5 length:16384 lensize:5 headersize:10 encoding:128 p:0 iiii.对比后可以发现,整数值长度部分编码字节的前两位为11,字符串值长度部分编码类型是00、01、或10,再通过该直接剩余部分或者其他字节获取真实长度。

  1. 级联更新 想象这样一种场景,从某一段开始,连续的若干个节点的前置节点长度均为253字节,如下图所示:

此时我在节点1前面插入一个长度为254字节的节点值会发生什么样的事情呢?

由于插入节点由253变成254,导致节点1的前置节点长度从253变成254,从前文知道,253的前置节点长度编码只需要1个字节空间,而254需要5个字节空间,所以节点1需要进行内存重分配。节点1增长的这4个字节又会导致节点2的内存重分配,节点2导致节点3,直到节点n,Redis将其称之为【级联更新】(CascadeUpdate),形象一点更像是多米诺骨牌,一个节点的变更导致后面连接的节点都变更,因为内存分配的复杂度是O(n),那么发生级联更新将导致该插入操作的复杂度达到O(n^2)。同理,删除操作也有可能导致这样的情况发生。

总结

压缩列表可以说是Redis追求内存节约的极致,大量的字节、位操作虽然牺牲了代码的可读性,却降低了内存开销,减少了内存碎片的产生。在使用的时候我们也要小心级联更新现象的发生,让它在最适合的业务场景中发挥其作用。总的来说,压缩列表的实现有以下几个特点:

  1. 为节省内存而生的顺序型存储结构
  2. 基于位和字节构建内部协议
  3. 以程序复杂度换取内存的空间压缩
  4. ​有可能触发级联更新

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LeetCode 7. Reverse Integer分析代码

802
来自专栏zingpLiu

常用七种排序的python实现

算法复杂度分为时间复杂度和空间复杂度。其中, 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

895
来自专栏Python中文社区

Python生成器的使用技巧详解

之前我们介绍了列表解析式,他的优点很多,比如运行速度快、编写简单,但是有一点我们不要忘了,他是一次性生成整个列表。如果整个列表非常大,这对内存也同样会造成很大压...

1323
来自专栏desperate633

LeetCode 6. ZigZag Conversion分析代码

这道题就是要根据z字形遍历,我们模拟一遍过程可以发现遍历的规律,可以用循环解决,先遍历下去,又向上。然后重复这个步骤,向下,向上!

791
来自专栏前端布道

图解javascript this指向什么?

JavaScript 是一种脚本语言,支持函数式编程、闭包、基于原型的继承等高级功能。JavaScript一开始看起来感觉会很容易入门,但是随着使用的深入,你会...

4169
来自专栏书山有路勤为径

复杂的链表的深度拷贝

Copy List with Random Pointer 已知一个复杂的链表,节点中有一个指向本链表任意某个节点的碎甲指针(也可以为空),求这个链表的深度拷...

691
来自专栏飞雪无情的博客

Go语言参数传递是传值还是传引用

其实对于传值和传引用,是一个比较古老的话题,做研发的都有这个概念,但是可能不是非常清楚。对于我们做Go语言开发的来说,也想知道到底是什么传递。

1693
来自专栏决胜机器学习

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十七)——内部排序综述 (原创内容,转载请注明来源,谢谢) 一、稳定性 假设Ki=Kj(1<=i,j<=n,i!=j),且排在序列前的序列中R...

34112
来自专栏我是攻城师

Python之numpy的ndarray数组使用方法介绍

NumPy的全名为Numeric Python,是一个开源的Python科学计算库,它包括:

1313
来自专栏一“技”之长

JavaScript基础之四——选择与循环结构

    选择结构与循环结构是编程中处理逻辑的核心结构,JavaScript中支持if-else和switch-case选择结构,支持for,for-in,do-...

621

扫码关注云+社区