压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。
原文是这么说的，但是这本书是基于 Redis 2.9 来写的，而我用的是 Redis 6.2，发现上面说到的情况并不是使用了 ziplist，而是使用了 quicklist. 当然，这并不影响我们了解 ziplist.
127.0.0.1:6379> rpush numlst 1 3 5 "haha"
(integer) 4
127.0.0.1:6379> object encoding numlst
"quicklist"
The struct of ziplist
压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
|---|
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字节 | 记录整个压缩列表占用的内存字节数 |
| zltail | uint32_t | 4 字节 | 记录压缩列表表尾节点举例压缩列表的起始地址有多少字节 |
| zllen | uint16_t | 2 字节 | 记录了压缩列表包含的节点数量。当 zllen 的值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出 |
| entryX | 列表节点 | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定 |
| zlend | uint8_t | 1 字节 | 特殊值 0xFF，用于标记压缩列表的末端 |
The struct of ziplist node
前面说到，每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下三种长度之一：
- 长度 <= 63 (2^6 - 1) 字节的字节数组；
- 长度 <= 16383 (2^14 - 1) 字节的字节数组；
- 长度 <= 4294967295 (2^32 - 1) 字节的字节数组；
而整数值则可以是以下 6 种长度之一：
- 4 位长，介于 0 至 12 之间的无符号整数；（为啥不是 15 ？）
- 1 字节长的有符号整数；（也就是 int8_t）
- 3 字节长的有符号整数；
- int16_t 类型整数；
- int32_t 类型整数；
- int64_t 类型整数；
typedef struct zlentry {
void* previous_entry_length;
void* encoding;
void* content;
} zlentry;
-
previous_entry_length属性以字节为单位，记录压缩列表中前一个节点的长度。previous_entry_length属性的长度可以是 1 字节或者 5 字节：
① 如果前一节点的长度小于 254 字节，那么previous_entry_length属性的长度为 1 字节
② 如果前一节点的长度 >= 254 字节，那么previous_entry_length属性的长度为 5 字节：其中属性的第一个字节会被设置为 0xFE，而之后的 4 个字节则用于保存前一节点的长度。
因为节点的previous_entry_length属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始位置来计算出前一个节点的起始位置。压缩列表的从表尾向表头遍历就是使用这一原理实现的。
连锁更新
发生连锁更新的条件：在一个压缩列表中，有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN，如果我们将一个长度 >= 254 字节的新节点 new 设置为压缩列表的表头节点，那么从 e1 节点开始，每个节点的 previous_entry_length 都需要被扩展成为 5 字节，这就是连锁更新。
除了添加新节点可能会引发连锁更新之外，删除节点也可能会引发连锁更新。
因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重新分配，而每次分配的最坏复杂度为 O(N)，所以连锁更新的最坏复杂度为 O(N^2)。
尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：
- 首先，压缩列表里恰好有多个连续的，长度介于 250 字节至 253 字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；
- 其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响。
网友评论