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. ​有可能触发级联更新