6、Redis系统-数据结构-03-压缩列表
三、压缩列表（Ziplist）
压缩列表是 Redis 为了节约内存而开发的一种内存紧凑型数据结构。它由连续的内存块组成，类似于数组。压缩列表主要用于 Redis 中 List 对象、Hash 对象和 Zset 对象在元素数量较少或元素值不大的情况下作为底层数据结构。
压缩列表的特点
- 内存紧凑：压缩列表通过紧凑的内存布局，占用一块连续的内存空间，不仅可以利用 CPU 缓存，还会针对不同长度的数据进行相应编码，从而有效地节省内存开销。
- 高效存储：压缩列表在表头包含三个字段，可以快速定位第一个元素和最后一个元素，查找效率较高。
然而，压缩列表也有一些缺点：
- 元素数量限制：不能保存过多的元素，否则查询效率会降低。
- 内存重新分配：新增或修改元素时，压缩列表需要重新分配内存，甚至可能引发连锁更新的问题，影响性能。
1. 结构设计
压缩列表由多个节点组成，每个节点存储一个数据元素。其表头和节点的具体结构如下：
表头结构
压缩列表的表头包含三个字段：
- zlbytes：记录整个压缩列表占用的内存字节数。
- zltail：记录压缩列表尾部节点距离起始地址的字节数，也就是列表尾的偏移量。
- zllen：记录压缩列表包含的节点数量。
压缩列表的结束标记是一个固定值 0xFF（十进制 255），用于标记压缩列表的结束点。
节点结构
压缩列表的每个节点包含三部分内容：
- prevlen：记录前一个节点的长度，目的是为了实现从后向前遍历。
- encoding：记录当前节点实际数据的类型和长度。类型主要有两种：字符串和整数。
- data：记录当前节点的实际数据，类型和长度由
encoding决定。
节点的 prevlen 和 encoding 的设计
-
prevlen 的空间大小根据前一个节点的长度值决定：
- 如果前一个节点的长度小于 254 字节，那么
prevlen属性需要用 1 字节的空间来保存这个长度值。 - 如果前一个节点的长度大于等于 254 字节，那么
prevlen属性需要用 5 字节的空间来保存这个长度值。
- 如果前一个节点的长度小于 254 字节，那么
-
encoding 的空间大小根据数据是字符串还是整数，以及字符串的长度有关：
- 如果当前节点的数据是整数，
encoding会使用 1 字节的空间进行编码。 - 如果当前节点的数据是字符串，根据字符串的长度大小，
encoding会使用 1 字节、2 字节或 5 字节的空间进行编码。encoding编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度。
- 如果当前节点的数据是整数，
这种设计思想正是为了节省内存，通过根据数据的大小和类型进行不同的空间分配，实现内存的高效利用。
2. 连续更新
当压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。
具体来看，当我们在压缩列表中插入一个长度大于等于 254 字节的新节点，可能会引发连锁更新问题。例如，将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点：
- 由于 e1 节点的
prevlen属性只有 1 个字节大小，无法保存新节点的长度，此时需要对压缩列表的空间进行重新分配，并将 e1 节点的prevlen属性从 1 字节扩展为 5 字节。 - e1 的扩展导致其长度大于等于 254 字节，原本 e2 保存 e1 的
prevlen属性也必须从 1 字节扩展至 5 字节。 - 扩展 e2 会引发对 e3 的扩展，扩展 e3 又会引发对 e4 的扩展，直到压缩列表的结尾。
这种在特殊情况下产生的连续多次空间扩展操作被称为「连锁更新」，类似多米诺骨牌效应，第一张牌倒下后，推动了第二张牌倒下，依次类推。
3. 压缩列表的缺陷
由于压缩列表需要进行空间扩展操作，这就需要重新分配内存，因此连锁更新一旦发生，会导致压缩列表占用的内存空间多次重新分配，直接影响到压缩列表的访问性能。
因此，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加，或元素变大，会导致内存重新分配，最糟糕的是会引发「连锁更新」的问题。
详细解释
压缩列表（ziplist）是 Redis 为了节约内存而开发的一种紧凑型数据结构。它由连续的内存块组成，类似于数组。压缩列表主要用于 Redis 中元素数量较少或元素值不大的 List 对象、Hash 对象和 Zset 对象。
结构设计
表头结构
压缩列表的表头包含三个字段：
- zlbytes：记录整个压缩列表占用的内存字节数。
- zltail：记录压缩列表尾部节点距离起始地址的字节数，也就是列表尾的偏移量。
- zllen：记录压缩列表包含的节点数量。
压缩列表的结束标记是一个固定值 0xFF（十进制 255），用于标记压缩列表的结束点。
节点结构
压缩列表的每个节点包含三部分内容：
- prevlen：记录前一个节点的长度，目的是为了实现从后向前遍历。
- encoding：记录当前节点实际数据的类型和长度。类型主要有两种：字符串和整数。
- data：记录当前节点的实际数据，类型和长度由
encoding决定。
节点的 prevlen 和 encoding 的设计
-
prevlen 的空间大小根据前一个节点的长度值决定：
- 如果前一个节点的长度小于 254 字节，那么
prevlen属性需要用 1 字节的空间来保存这个长度值。 - 如果前一个节点的长度大于等于 254 字节，那么
prevlen属性需要用 5 字节的空间来保存这个长度值。
- 如果前一个节点的长度小于 254 字节，那么
-
encoding 的空间大小根据数据是字符串还是整数，以及字符串的长度有关：
- 如果当前节点的数据是整数，
encoding会使用 1 字节的空间进行编码。 - 如果当前节点的数据是字符串，根据字符串的长度大小，
encoding会使用 1 字节、2 字节或 5 字节的空间进行编码。encoding编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度。
- 如果当前节点的数据是整数，
这种设计思想正是为了节省内存，通过根据数据的大小和类型进行不同的空间分配，实现内存的高效利用。
连续更新
当压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。
具体来看，当我们在压缩列表中插入一个长度大于等于 254 字节的新节点，可能会引发连锁更新问题。例如，将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点：
- 由于 e1 节点的
prevlen属性只有 1 个字节大小，无法保存新节点的长度，此时需要对压缩列表的空间进行重新分配，并将 e1 节点的prevlen属性从 1 字节扩展为 5 字节。 - e1 的扩展导致其长度大于等于 254 字节，原本 e2 保存 e1 的
prevlen属性也必须从 1 字节扩展至 5 字节。 - 扩展 e2 会引发对 e3 的扩展，扩展 e3 又会引发对 e4 的扩展，直到压缩列表的结尾。
这种在特殊情况下产生的连续多
次空间扩展操作被称为「连锁更新」，类似多米诺骨牌效应，第一张牌倒下后，推动了第二张牌倒下，依次类推。
压缩列表的缺陷
由于压缩列表需要进行空间扩展操作，这就需要重新分配内存，因此连锁更新一旦发生，会导致压缩列表占用的内存空间多次重新分配，直接影响到压缩列表的访问性能。
因此，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加，或元素变大，会导致内存重新分配，最糟糕的是会引发「连锁更新」的问题。
原文地址：https://blog.csdn.net/qq_29434541/article/details/140246655
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！