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 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

Python基础回顾基本数据类型和运算容器分支和循环函数、生成器和类map, reduce和filter列表生成(list comprehension)字符串文件操作和pickle异常多进程(mult

Python shell输入import this 可以看到The Zen of Python 基本数据类型和运算 基本数据类型 Python中最基本的数据类...

49170
来自专栏决胜机器学习

Redis专题(二) ——Redis数据类型(2)

Redis专题(二)——Redis数据类型(2) (原创内容,转载请注明来源,谢谢) 四、列表类型(List) 列表类型可以存储一个有序的字符串列表,其存储...

35260
来自专栏贺贺的前端工程师之路

split的坑-字符串分割

昨天在调代码的时候,遇到了一个很大的坑儿,让我不得不记录下来,莫非是我写js代码太久了的缘故?大概也许可能吧...

26330
来自专栏我是攻城师

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

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

16030
来自专栏noteless

[三] java虚拟机 JVM字节码 指令集 bytecode 操作码 指令分类用法 助记符

计算机指令就是指挥机器工作的指示和命令,程序就是一系列按一定顺序排列的指令,执行程序的过程就是计算机的工作过程。

49920
来自专栏一“技”之长

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

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

7410
来自专栏待你如初见

Day01

不推荐使用强制的类型转换,它容易丢失数据,除非不得已,并且你确定不会出现数据丢失才可以使用。

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

复杂的链表的深度拷贝

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

7710
来自专栏Coding迪斯尼

Reactjs开发自制编程语言Monkey的编译器:语法解析

16120
来自专栏青玉伏案

窥探Swift之使用Web浏览器编译Swift代码以及Swift中的泛型

   有的小伙伴会问:博主,没有Mac怎么学Swift语言呢,我想学Swift,但前提得买个Mac。非也,非也。如果你想了解或者初步学习Swift语言的话,你可...

19750

扫码关注云+社区

领取腾讯云代金券