11. 什么是压缩列表(ziplist)

压缩列表(ziplist) 是哈希键的底层实现之一，当一个哈希键只包含少量键值对，并且每个键值对的键和值是小整数值或者长度较短的字符串时，Redis 就会使用压缩列表来做哈希键的底层实现。
例子：

127.0.0.1:6379> HMSET hs "name" "wifi" "age" 18 "sex" "man"
OK
127.0.0.1:6379> OBJECT ENCODING hs
"ziplist"

在 Redis 3.2 之前，压缩列表也是列表建的底层实现之一的，后面用快速列表(quicklist)代替了压缩列表(ziplist)。
例子：

127.0.0.1:6379> RPUSH list 1 3 5 7 9
(integer) 5
127.0.0.1:6379> OBJECT ENCODING list
"quicklist"

2. 压缩列表的构成

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

在了解压缩列表的优点之前，需要先知道压缩列表具体是长什么样子的。

2.1 压缩列表的组成

如图所示：

具体作用：

zlbytes：记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用；
zltail：记录压缩列表表尾节点到表头节点的字节数：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址；
zllen：记录了压缩列表中包含的节点数量。
- 当 zlen < UINT16_MAX(65535) 时，zlen = 压缩列表包含的节点数量 ；
- 当 zlen = UINT16_MAX(65535) 时，压缩列表中的节点数量需要通过遍历整个压缩列表才能得到。
entryX：压缩列表中包含的各个节点，节点的长度由节点保存的内容决定；
zlend：特殊值 0xFF(255)，用于标记压缩列表的末端。

举个列子：

zlbytes = 0x50 = 80：表示压缩列表的总长为 80 字节；
zltail = 0x3c = 60：表示表尾节点距离表头节点 60 字节；
zllen = 0x3 = 3：表示压缩列表包含 3 个节点。

到这里，压缩列表看起来和普通数组没什么两样，无非就是多了几个属性值而已。继续往下看，看压缩列表节点的组成来发现压缩列表与数组的不同之处。

2.2 压缩列表节点的组成

首先看压缩列表节点的组成示意图：

2.2.1 previous_entry_length

previous_entry_length：以字节为单位，记录了压缩列表中前一个节点的长度。
- 如果 previous_entry_length = 1 字节：表示前一个节点的长度小于 254 字节；
- 如果 previous_entry_length = 5 字节：表示前一个节点的长度大于等于 254 字节。
  - previous_entry_length 的第一个字节：会被设置为 0xFE(254)；
  - previous_entry_length 的后四个字节：会被用于保存前一节点的长度。

例如

previous_entry_length = 0x05：表示前一个节点的长度为 5 字节；
previous_entry_length = 0xFE00002766：
- 0xFE：表示这是一个 5 字节长的 previous_entry_length 属性；
- 0x00002766：表示前一个节点的长度为 10086 字节。

当有了 previous_entry_length 属性后，很容易知道，我们可以完成从表尾向表头遍历的操作。只需要用后一节点的指针 – previous_entry_length = 前一节点的指针位置。
同时，我们也知道了，压缩列表中的每个节点的长度是可以不一样的。

2.2.2 encoding

encoding 记录了节点 content 属性所保存数据的类型和长度

如果 encoding 的长度为：1、2、5 字节长，且值的最高位为：00、01、10 时。表示 content 属性保存的值为字节数组，字节数组的长度为：编码除去最高两位之后的其他位记录；
如果 encoding 的长度为：1 字节长，且值的最高位为：11 时。表示 content 属性保存的值为整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。

2.2.2.1 字节数组编码

编码	编码长度	content 属性保存的值
00bbbbbb	1 字节	长度小于等于 63 字节的字节数组
00bbbbbb xxxxxxxx	2 字节	长度小于等于 16 383 字节的字节数组
00_ _ _ _ _ _ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx	5 字节	长度小于等于 4 294 967 295 字节的字节数组

2.2.2.2 整数编码

编码	编码长度	content 属性保存的值
11000000	1 字节	int16_t 类型的整数
11010000	1 字节	int132_t 类型的整数
11100000	1 字节	int64_t 类型的整数
11110000	1 字节	24 位有符号整数
11111110	1 字节	8 位的整数
1111xxxx	1 字节	使用这一编码的节点没有相应的 content 属性，因为编码本身的 xxxx 四个位已经保存了一个介于 0 和 12 之间的值，所以它无须 content 属性

2.2.3 content

content 负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

2.2.4 例子

3. 压缩列表和数组的区别

3.1 内存

我们知道，数组要求每个元素的大小相同，如果我们要存储不同长度的字符串，那我们就需要用最大长度的字符串大小作为元素的大小（假设是20个字节）。存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。而压缩列表，则可以根据元素自身大小，合理地分配内存，减少内存浪费。

3.2 数据类型

由压缩列表节点的组成中知道，压缩列表节点可以存储字节数组和整数，而不用像普通数组一样，只能够存储单一类型的元素。

4. 压缩列表存在的“问题”

在讲述 previous_entry_length 属性时提到，previous_entry_length 用 1/5 字节来及记录前一个节点的长度，其中存在一种“极端”的情况：
在一个压缩列表中，有多个连续的、长度介于 250 – 253 字节之间的节点，因为这些节点都小于 254 字节，所以在 previous_entry_length 中都用 1 字节进行记录。如下图：

这时候，我往 entry1 前面插入一个新的节点 newEntry，且它的长度大于等于 254 字节。这时候会带来以下影响：

entry1 的 previous_entry_length 从 1 字节变成 5 字节；
entry1 的字节长度由 250 ~ 253 + 4 = 254 ~ 257 字节；
entry1 往后的字节都面临着同样的情况，也就是说，它们的 previous_entry_length 都会从 1 变成 5 字节，连锁反应。

除了添加节点可能引发连锁更新以外，删除头结点，也可能出现连锁更新的情况。当然，这些都是相对极端的情况下才会发生的。

5. 添加元素

由上述内容我们知道，ziplist 是紧凑存储的，没有额外的冗余空间。这意味着插入一个新的元素就需要调用 realloc 扩展内存。取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的拷贝。

如果 ziplist 占据内存太大，无论是重新分配内存还是拷贝内存，都会有很大的消耗。所以，ziplist 不适合存储大型字符串，存储的元素也不宜过多。

6. 压缩列表的 API

函数	作用	算法复杂度
ziplistPush	创建一个包含给定值的新节点，并将这个新节点添加到压缩列表的表头或者表尾	平均 O(N)，最坏 O(N²)
ziplistInsert	将包含给定值的新节点插入到给定节点之后	平均 O(N)，最坏 O(N²)
ziplistIndex	返回压缩列表给定索引上的节点	平均 O(N)
ziplistFind	在压缩列表中查找并返回包含了给定值的节点	因为节点的值可能是一个字节数组，所以检查节点值和给定值是否相同的复杂度为 O(N)，而查找整个列表的复杂度则为 O(N²)
ziplistDelete	从压缩列表中删除给定的节点	平均 O(N)，最坏 O(N²)
ziplistDeleteRange	删除压缩列表在给定索引上的连续多个节点	平均 O(N)，最坏 O(N²)
ziplistLen	返回压缩列表目前包含的节点数量	节点数量小于 65 535 时，为 O(1)。大于 65 535 时，为 O(N)