Redis压缩列表

Redis 中的压缩列表不是基础数据结构，而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同。

压缩列表详解

说明

听到 “压缩” 两个字，直观的反应就是节省内存。之所以说这种存储结构节省内存，是相较于数组的存储思路而言的。我们知道，数组要求每个元素的大小相同，如果我们要存储不同长度的字符串，那我们就需要用最大长度的字符串大小作为元素的大小(假设是 20 个字节)。存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。

数组的优势占用一片连续的空间可以很好的利用 CPU 缓存访问数据。如果我们想要保留这种优势，又想节省存储空间我们可以对数组进行压缩。

但是这样有一个问题，我们在遍历它的时候由于不知道每个元素的大小是多少，因此也就无法计算出下一个节点的具体位置。这个时候我们可以给每个节点增加一个 length 的属性。

那么，此时数组就如下图所示：

如此。我们在遍历节点的之后就知道每个节点的长度(占用内存的大小)，就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。

压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结枃。一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或者一个整数值，如下图：

zlbytes：存储一个无符号整数，固定四个字节长度，用于存储压缩列表所占用的字节，当重新分配内存的时候使用，不需要遍历整个列表来计算内存大小。

zltail：存储一个无符号整数，固定四个字节长度，代表指向列表尾部的偏移量，偏移量是指压缩列表的起始位置到指定列表节点的起始位置的距离。

zllen：压缩列表包含的节点个数，固定两个字节长度，源码中指出当节点个数大于 2^16-2 个数的时候，该值将无效，此时需要遍历列表来计算列表节点的个数。

entryX：列表节点区域，长度不定，由列表节点紧挨着组成。

zlend：一字节长度固定值为 255，用于表示列表结束。

示例

如上图，展示了一个总长为 80 字节，包含 3 个节点的压缩列表。如果我们有一个指向压缩列表起始地址的指针 p，那么表为节点的地址就是 P+60。

压缩列表节点构成

压缩列表的节点如下图所示：

previous_entry_length：previous_entry_length 记录了前一个节点的长度，程序可以通过指针运算，根据当前节点的起始地址拉算出前一个节点的其实地址。

压缩列表从表尾向表头的遍历就是使用这一原理实现的。

encoding：encoding 记录了节点的 content 属性所保存的数据类型及长度。

content：content 负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由 encoding 属性决定。

连锁更新

每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

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

假设在一个压缩列表中，有多个连续的、长度介于 250 到 253 字节之间的节点 e1 至 eN：

因为 e1 至 eN 所有节点长度都小于 254 字节，所以这些节点长度的 previous_entry_length 都是 1 字节的。这时，如果在压缩列表头添加一个长度大于等于 254 字节的新节点：

因为 e1 的 previous_entry_length 属性仅长 1 字节，无法保存新节点的程度，所以程序将对压缩列表进行空间重分配，并将 e1 的 previous_entry_length 从原来的 1 字节长扩展为 5 字节长。

这时 e1 的 previous_entry_length 属性新增了四个字节，e1 的长度大于等于 254 字节了，这样用 1 字节长的 previous_entry_length 就无法保存。

因此，e2 的 previous_entry_length 属性也会被扩展。依次类推，后面所有节点都会被扩展，造成连锁更新。

类似地，删除节点操作也可能会引发连锁更新：

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

尽管连锁更新复杂度较高，但真正造成性能问题的几率很低：

• 压缩列表里恰好有多个连续的、长度介于 250 到 253 字节之间的节点。
• 即便出现连锁更新，只要被更新节点数目不多，影响就不大。

所以添加删除节点的操作平均复杂度仅为 O(N)。

Redis压缩列表

压缩列表(zip1ist)是列表和哈希的底层实现之一。

当一个列表只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表的底层实现。

当一个哈希只包含少量键值对，比且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做哈希的底层实现。

常用操作的时间复杂度

操作	时间复杂度
创建一个新的压缩列表	O(1)
创建一个包含给定值的新节点,并将这个新节点添加到压缩列表的表头或者表尾	平均 O(N)，最坏O(N^2)(可能发生连锁更新)
将包含给定值的新节点插人到给定节点之后	平均 O(N)，最坏O(N^2)(可能发生连锁更新)
返回压缩列表给定索引上的节点	O(N)
在压缩列表中査找并返回包含了给定值的节点	因为节点的值可能是一个字节数组,所以检查节点值和给定值是否相同的复杂度为 O(N),而查找整个列表的复杂度则为(N^2)
返回给定节点的下一个节点	O(1)
返回给定节点的前一个节点	O(1)
获取给定节点所保存的值	O(1)
从压缩列表中删除给定的节点	平均 O(N)，最坏 O(N^2)(可能发生连锁更新)
删除压缩列表在给定索引上的连续多个	平均 O(N)，最坏 O(N^2)(可能发生连锁更新)
返回压缩列表目前占用的内存字节数	O(1)
返回压缩列表目前包含的节点数量	点数量小于 65535 时为 O(1),大于 65535 时为 O(N)

总结

1. 压缩列表是 Redis 为节约内存自己设计的一种顺序型数据结构。
2. 压缩列表被用作列表键和哈希键的底层实现之一。
3. 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
4. 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。