6、Redis系统-数据结构-03-压缩列表

三、压缩列表（Ziplist）

压缩列表是 Redis 为了节约内存而开发的一种内存紧凑型数据结构。它由连续的内存块组成，类似于数组。压缩列表主要用于 Redis 中 List 对象、Hash 对象和 Zset 对象在元素数量较少或元素值不大的情况下作为底层数据结构。

压缩列表的特点

1. 内存紧凑：压缩列表通过紧凑的内存布局，占用一块连续的内存空间，不仅可以利用 CPU 缓存，还会针对不同长度的数据进行相应编码，从而有效地节省内存开销。
2. 高效存储：压缩列表在表头包含三个字段，可以快速定位第一个元素和最后一个元素，查找效率较高。

然而，压缩列表也有一些缺点：

1. 元素数量限制：不能保存过多的元素，否则查询效率会降低。
2. 内存重新分配：新增或修改元素时，压缩列表需要重新分配内存，甚至可能引发连锁更新的问题，影响性能。

1. 结构设计

压缩列表由多个节点组成，每个节点存储一个数据元素。其表头和节点的具体结构如下：

表头结构

压缩列表的表头包含三个字段：

• zlbytes：记录整个压缩列表占用的内存字节数。
• zltail：记录压缩列表尾部节点距离起始地址的字节数，也就是列表尾的偏移量。
• zllen：记录压缩列表包含的节点数量。

压缩列表的结束标记是一个固定值 0xFF（十进制 255），用于标记压缩列表的结束点。

节点结构

压缩列表的每个节点包含三部分内容：

• prevlen：记录前一个节点的长度，目的是为了实现从后向前遍历。
• encoding：记录当前节点实际数据的类型和长度。类型主要有两种：字符串和整数。
• data：记录当前节点的实际数据，类型和长度由 encoding 决定。

节点的 prevlen 和 encoding 的设计

1. prevlen 的空间大小根据前一个节点的长度值决定：

   • 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值。
   • 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值。

2. encoding 的空间大小根据数据是字符串还是整数，以及字符串的长度有关：

   • 如果当前节点的数据是整数，encoding 会使用 1 字节的空间进行编码。
   • 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节、2 字节或 5 字节的空间进行编码。encoding 编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度。

这种设计思想正是为了节省内存，通过根据数据的大小和类型进行不同的空间分配，实现内存的高效利用。

2. 连续更新

当压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

具体来看，当我们在压缩列表中插入一个长度大于等于 254 字节的新节点，可能会引发连锁更新问题。例如，将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点：

1. 由于 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时需要对压缩列表的空间进行重新分配，并将 e1 节点的 prevlen 属性从 1 字节扩展为 5 字节。
2. e1 的扩展导致其长度大于等于 254 字节，原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节。
3. 扩展 e2 会引发对 e3 的扩展，扩展 e3 又会引发对 e4 的扩展，直到压缩列表的结尾。

这种在特殊情况下产生的连续多次空间扩展操作被称为「连锁更新」，类似多米诺骨牌效应，第一张牌倒下后，推动了第二张牌倒下，依次类推。

3. 压缩列表的缺陷

由于压缩列表需要进行空间扩展操作，这就需要重新分配内存，因此连锁更新一旦发生，会导致压缩列表占用的内存空间多次重新分配，直接影响到压缩列表的访问性能。

因此，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加，或元素变大，会导致内存重新分配，最糟糕的是会引发「连锁更新」的问题。

详细解释

压缩列表（ziplist）是 Redis 为了节约内存而开发的一种紧凑型数据结构。它由连续的内存块组成，类似于数组。压缩列表主要用于 Redis 中元素数量较少或元素值不大的 List 对象、Hash 对象和 Zset 对象。

结构设计

表头结构

压缩列表的表头包含三个字段：

• zlbytes：记录整个压缩列表占用的内存字节数。
• zltail：记录压缩列表尾部节点距离起始地址的字节数，也就是列表尾的偏移量。
• zllen：记录压缩列表包含的节点数量。

压缩列表的结束标记是一个固定值 0xFF（十进制 255），用于标记压缩列表的结束点。

节点结构

压缩列表的每个节点包含三部分内容：

• prevlen：记录前一个节点的长度，目的是为了实现从后向前遍历。
• encoding：记录当前节点实际数据的类型和长度。类型主要有两种：字符串和整数。
• data：记录当前节点的实际数据，类型和长度由 encoding 决定。

节点的 prevlen 和 encoding 的设计

1. prevlen 的空间大小根据前一个节点的长度值决定：

   • 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值。
   • 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值。

2. encoding 的空间大小根据数据是字符串还是整数，以及字符串的长度有关：

   • 如果当前节点的数据是整数，encoding 会使用 1 字节的空间进行编码。
   • 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节、2 字节或 5 字节的空间进行编码。encoding 编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度。

这种设计思想正是为了节省内存，通过根据数据的大小和类型进行不同的空间分配，实现内存的高效利用。

连续更新

当压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

具体来看，当我们在压缩列表中插入一个长度大于等于 254 字节的新节点，可能会引发连锁更新问题。例如，将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点：

1. 由于 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时需要对压缩列表的空间进行重新分配，并将 e1 节点的 prevlen 属性从 1 字节扩展为 5 字节。
2. e1 的扩展导致其长度大于等于 254 字节，原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节。
3. 扩展 e2 会引发对 e3 的扩展，扩展 e3 又会引发对 e4 的扩展，直到压缩列表的结尾。

这种在特殊情况下产生的连续多

次空间扩展操作被称为「连锁更新」，类似多米诺骨牌效应，第一张牌倒下后，推动了第二张牌倒下，依次类推。

压缩列表的缺陷

由于压缩列表需要进行空间扩展操作，这就需要重新分配内存，因此连锁更新一旦发生，会导致压缩列表占用的内存空间多次重新分配，直接影响到压缩列表的访问性能。

因此，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加，或元素变大，会导致内存重新分配，最糟糕的是会引发「连锁更新」的问题。