整数集合-压缩列表

本文总阅读量次

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

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

比如说， 执行以下命令将创建一个压缩列表实现的列表键：

1
2
3
4
5
redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6

redis> OBJECT ENCODING lst
"ziplist"

因为列表键里面包含的都是 1 、 3 、 5 、 10086 这样的小整数值， 以及 “hello” 、 “world” 这样的短字符串。

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

举个例子， 执行以下命令将创建一个压缩列表实现的哈希键：

1
2
3
4
5
redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK

redis> OBJECT ENCODING profile
"ziplist"

因为哈希键里面包含的所有键和值都是小整数值或者短字符串。

本章将对压缩列表的定义以及相关操作进行详细的介绍。

压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

一个压缩列表可以包含任意多个节点（entry）， 每个节点可以保存一个字节数组或者一个整数值。

图 7-1 展示了压缩列表的各个组成部分， 表 7-1 则记录了各个组成部分的类型、长度、以及用途。

img

表 7-1 压缩列表各个组成部分的详细说明

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

图 7-2 展示了一个压缩列表示例：

  • 列表 zlbytes 属性的值为 0x50 （十进制 80）， 表示压缩列表的总长为 80 字节。
  • 列表 zltail 属性的值为 0x3c （十进制 60）， 这表示如果我们有一个指向压缩列表起始地址的指针 p ， 那么只要用指针 p 加上偏移量 60 ， 就可以计算出表尾节点 entry3 的地址。
  • 列表 zllen 属性的值为 0x3 （十进制 3）， 表示压缩列表包含三个节点。

img

图 7-3 展示了另一个压缩列表示例：

  • 列表 zlbytes 属性的值为 0xd2 （十进制 210）， 表示压缩列表的总长为 210 字节。
  • 列表 zltail 属性的值为 0xb3 （十进制 179）， 这表示如果我们有一个指向压缩列表起始地址的指针 p ， 那么只要用指针 p 加上偏移量 179 ， 就可以计算出表尾节点 entry5 的地址。
  • 列表 zllen 属性的值为 0x5 （十进制 5）， 表示压缩列表包含五个节点。

img

连锁更新

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

如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。
现在， 考虑这样一种情况： 在一个压缩列表中， 有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN ， 如图 7-11 所示。

img

因为 e1 至 eN 的所有节点的长度都小于 254 字节， 所以记录这些节点的长度只需要 1 字节长的 previous_entry_length 属性， 换句话说， e1 至 eN 的所有节点的 previous_entry_length 属性都是 1 字节长的。

这时， 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点， 那么 new 将成为 e1 的前置节点， 如图 7-12 所示。

img

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

现在， 麻烦的事情来了 —— e1 原本的长度介于 250 字节至 253 字节之间， 在为 previous_entry_length 属性新增四个字节的空间之后， e1 的长度就变成了介于 254 字节至 257 字节之间， 而这种长度使用 1 字节长的 previous_entry_length 属性是没办法保存的。

因此， 为了让 e2 的 previous_entry_length 属性可以记录下 e1 的长度， 程序需要再次对压缩列表执行空间重分配操作， 并将 e2 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。

正如扩展 e1 引发了对 e2 的扩展一样， 扩展 e2 也会引发对 e3 的扩展， 而扩展 e3 又会引发对 e4 的扩展……为了让每个节点的 previous_entry_length 属性都符合压缩列表对节点的要求， 程序需要不断地对压缩列表执行空间重分配操作， 直到 eN 为止。

Redis 将这种在特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”（cascade update）， 图 7-13 展示了这一过程。

img

img

img

img

img

除了添加新节点可能会引发连锁更新之外， 删除节点也可能会引发连锁更新。

考虑图 7-14 所示的压缩列表， 如果 e1 至 eN 都是大小介于 250 字节至 253 字节的节点， big 节点的长度大于等于 254 字节（需要 5 字节的 previous_entry_length 来保存）， 而 small 节点的长度小于 254 字节（只需要 1 字节的 previous_entry_length 来保存）， 那么当我们将 small 节点从压缩列表中删除之后， 为了让 e1 的 previous_entry_length 属性可以记录 big 节点的长度， 程序将扩展 e1 的空间， 并由此引发之后的连锁更新。

img

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

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

  • 首先， 压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发， 在实际中， 这种情况并不多见；
  • 其次， 即使出现连锁更新， 但只要被更新的节点数量不多， 就不会对性能造成任何影响： 比如说， 对三五个节点进行连锁更新是绝对不会影响性能的；

因为以上原因， ziplistPush 等命令的平均复杂度仅为 O(N) ， 在实际中， 我们可以放心地使用这些函数， 而不必担心连锁更新会影响压缩列表的性能。

压缩列表 API

表 7-4 列出了所有用于操作压缩列表的 API 。

表 7-4 压缩列表 API

函数 作用 算法复杂度
ziplistNew 创建一个新的压缩列表。 O(1)
ziplistPush 创建一个包含给定值的新节点， 并将这个新节点添加到压缩列表的表头或者表尾。 平均 O(N) ，最坏 O(N^2) 。
ziplistInsert 将包含给定值的新节点插入到给定节点之后。 平均 O(N) ，最坏 O(N^2) 。
ziplistIndex 返回压缩列表给定索引上的节点。 O(N)
ziplistFind 在压缩列表中查找并返回包含了给定值的节点。 因为节点的值可能是一个字节数组， 所以检查节点值和给定值是否相同的复杂度为 O(N) ， 而查找整个列表的复杂度则为 O(N^2) 。
ziplistNext 返回给定节点的下一个节点。 O(1)
ziplistPrev 返回给定节点的前一个节点。 O(1)
ziplistGet 获取给定节点所保存的值。 O(1)
ziplistDelete 从压缩列表中删除给定的节点。 平均 O(N) ，最坏 O(N^2) 。
ziplistDeleteRange 删除压缩列表在给定索引上的连续多个节点。 平均 O(N) ，最坏 O(N^2) 。
ziplistBlobLen 返回压缩列表目前占用的内存字节数。 O(1)
ziplistLen 返回压缩列表目前包含的节点数量。 节点数量小于 65535 时 O(1) ， 大于 65535 时 O(N) 。

因为 ziplistPush 、 ziplistInsert 、 ziplistDelete 和 ziplistDeleteRange 四个函数都有可能会引发连锁更新， 所以它们的最坏复杂度都是 O(N^2) 。

整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

　　它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

复制代码

1
2
3
4
5
6
7
8
1 typedef struct intset {
2     // 编码方式
3     uint32_t encoding;
4     // 集合包含的元素数量
5     uint32_t length;
6     // 保存元素的数组
7     int8_t contents[];
8 } intset;

复制代码

img

　　contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

升级：

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面。

　　根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

　　将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上（从后往前），而且在放置元素的过程中，需要继续位置底层数组的有序性质不变。

　　将新元素添加到底层数组里面。

　　将encoding属性更改。

　　整数集合添加新元素的时间复杂度为O(N)。

　　因为引发升级的元素要么最大要么最小，所有它的位置要么是0要么是length-1。

升级的好处：

　　提升整数集合的灵活性，可以随意将int16，int32，int64的值放入集合。

　　尽可能地节约内存

降级：

　　整数集合不支持降级操作