第 7 章 压缩列表

压缩列表（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），每个节点可以保存一个字节数组或者一个整数值。

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 字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；
• 其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响。