Redis数据结构4：REDIS_ZIPLIST

REDIS_ZIPLIST

zipList(压缩列表)是一种紧凑型的数据结构，占用一片连续的内存，本质上是一个字节数组。能提高CPU缓存的利用效率，并且针对不同数据结构进行不同编码，节省内存开销。

编码结构

zipList的字节数组主要由5个部分组成：zlbytes、zltail、zllen、zltail和entry。

• zlbytes 记录了整个zipList占用的内存大小。
• zltail 记录了整个zipList尾结点距离起始地址的字节数，也可认为是列表尾的offset(偏移量)。
• zllen 记录了压缩列表的entry数量。
• zlend 记录了zipList的结束点，固定值为0xFF(十进制下的255)。

entry

entry是zipList的有效存储模块，其中entry又分为三部分：prevlen、encoding和data。

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

对于entry来说：

如果前一个entry的长度小于254字节，那么prelen就会采用1个字节。

如果前一个entry的长度大于254，prelen就采用5个字节：第一个字节会被设置为0xFE(十进制的254），之后的四个字节则用于保存前一个节点的长度。

对于encoding来说：

encoding的空间大小跟数据是字符串还是整数，以及字符串的长度有关。

• 如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码，也就是 encoding 长度为 1 字节。通过 encoding 确认了整数类型，就可以确认整数数据的实际大小了，比如如果 encoding 编码确认了数据是 int16 整数，那么 data 的长度就是 int16 的大小。
• 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码，encoding 编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度，即 data 的长度。

连锁更新问题

连锁更新问题是指：在极端情况下，在修改 entry 的 data 时，data长度过高，zipList需要重新分配内存空间。

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

该问题主要是因为 prevlen 会根据前一个节点的长度进行不同的空间大小分配。

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

现在设一个zipList中有多个连续且长度在 250～253 之间的节点，这些节点的长度都小于254，prelen 使用1个字节的空间保存长度值。我们设这第一个元素为E1。

这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点。因为原E1的prelen只有一个字节，无法保存新插入的结点，那么此时prelen需要从1扩大到5字节。

而此时E1的长度也大于了254，那么后续节点都需要逐步扩大prelen，扩大prelen又导致了新的后节点变化。像多米诺骨牌一样产生的连续多次空间扩展。

反之，在删除节点时也可能导致连锁更新。

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N)，所以连锁更新的最坏复杂度为 O(N^2)。

但因为大规模连锁更新的情况过于极端，且小规模连锁更新并不影响性能，所以不必过于担心。

Redis也并未对此种情况提出相应解决方案。