Redis设计与实现 学习笔记 第七章 压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，且每个列表项要么是小整数值，要么是短字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

例如，以下命令将创建一个压缩列表实现的列表键：

另外，当一个哈希键只包含少量键值对，且每个键值对的键和值要么是小整数，要么是短字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

例如，以下命令将创建一个压缩列表实现的哈希键：

7.1 压缩列表的构成

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意个节点（entry），每个节点可以保存一个字节数组或一个整数值。

图7-2展示了一个压缩列表：

1.zlbytes属性值为0x50（十进制80），表示压缩列表的总长为80字节。

2.zltail属性值为0x3c（十进制60），如果我们有一个指向列表起始地址的指针p，那么p+60就是表尾节点entry3的地址。

3.zllen属性值为0x3（十进制3），表示压缩列表包含3个节点。

7.2 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或一个整数值，其中，字节数组可以是以下三种长度之一：
1.长度小于等于63（2${}^6$-1）字节的字节数组；

2.长度小于等于16383（2${}^{1}4$-1）字节的字节数组；

3.长度小于等于4294967296（2${}^{3}2$-1）字节的字节数组；

而整数值可以是以下六种长度之一：
1.4位长，介于0到12之间的无符号整数。

2.1字节长的有符号整数；

3.3字节长的有符号整数；

4.int16_t类型整数；

5.int32_t类型整数；

6.int64_t类型整数；

每个压缩列表节点都由previous_entry_length、encoding、content三部分组成：

7.2.1 previous_entry_length

节点的previous_entry_length属性记录了压缩列表中前一个节点的长度。previous_entry_length属性的长度可以为：
1.如果前一节点的长度小于254字节，那么previous_entry_length属性长为1字节：前一节点的长度就保存在这一个字节里。

2.如果前一节点的长度大于等于254字节，那么previsou_entry_length属性长为5字节：第一字节被设置为0xFE（十进制254），之后四字节则用于保存前一节点的长度。

图7-5展示了一个包含1字节长的previous_entry_length属性的压缩列表节点，表示前一节点的长度为5字节：

图7-6展示了一个包含5字节长的previous_entry_length属性的压缩列表节点，表示前一节点的长度为10086字节：

我们可以通过当前节点的起始地址，以及前一个节点的长度previous_entry_length，来计算出前一个节点的起始地址。

压缩列表的从表尾到表头遍历操作就是使用这一原理实现的，只要我们有了一个指向某节点起始地址的指针，就能通过这个指针一直向前回溯，最终到达压缩列表的表头节点。

图7-8展示了一个从表尾节点到表头节点遍历的完整过程：

7.2.2 encoding

节点的encoding属性记录了节点的content属性所保存的数据类型及长度（下表中，_表示留空，其他字母表示实际的二进制数据）：

从上表中可以看到，encoding属性的长度可以是1、2、5字节；属性值以00、01、10开头时表示字节数组编码，以11开头时表示整数编码。

7.2.3 content

节点的content属性负责保存节点的值，节点值可以是一个字节数组或整数。

图7-9展示了一个保存字节数组的节点：

1.编码的最高两位00表示节点保存的是一个字节数组；

2.编码的后六位表示字节数组的长度为11；

3.content属性保存着字节数组。

7.3 连锁更新

考虑这样一种情况：在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点e1至eN：

因为e1至eN的所有节点长度都小于254字节，所以记录这些节点的长度只需1字节长的previous_entry_length属性。

这时我们将一个长度大于等于254字节的新节点new设置为压缩列表的表头节点：

因为e1的previous_entry_length属性仅长1字节，没办法保存新节点new的长度，所以程序将对压缩列表执行空间重分配操作，并将e1节点的previous_entry_length属性从原来的1字节扩展为5字节长。

现在，麻烦的事情来了，e1在为previous_entry_length属性新增4字节的空间后，e1的长度就介于254至257字节之间，而这种长度使用1字节长的previous_entry_length属性是没办法保存的。

因此，为了让e2的previous_entry_length属性能记录下e1的长度，程序需要再次对压缩列表执行空间重分配操作，并将e2的previous_entry_length属性从原来的1字节扩展为5字节长。

依此类推，程序需要不断地对压缩列表执行空间重分配操作，直到eN为止。

Redis将这种在特殊情况下产生的连续多次空间扩展操作称为“连锁更新”（cascade update），图7-13展示了这一过程：

考虑图7-14所示的压缩列表：

如果e1至eN都是大小介于250至253字节的节点，big节点的长度大于等于254字节，而small节点的长度小于254字节，那么当我们将small节点从压缩列表中删除后，为了让e1的previous_entry_length属性可以记录big节点的长度，程序将扩展e1的空间，并由此引发之后的连锁更新。

因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(N)，所以连续更新的最坏复杂度为O(N${}^2$)。

尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：
1.首先，压缩列表里要恰好有多个连续的、长度介于250至253字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见（可能会有用户利用这一点进行攻击）；

2.其次，及时出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响；

因此，ziplistPush等命令的平均复杂度仅为O(N)，在实际中，可以放心使用这些函数，而不必担心会影响压缩列表的性能。

7.4 压缩列表API

7.5 重点回顾

1.压缩列表是一种为节约内存而开发的顺序型数据结构。

2.压缩列表被用作列表键和哈希键的底层实现之一。

3.压缩列表可以包含多个节点，每一个节点可以保存一个字节数组或整数值。

4.添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率不高。

原文地址：https://blog.csdn.net/tus00000/article/details/142874781

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！