整数集合与压缩列表
程序员文章站
2022-05-28 16:54:11
...
在 Redis 中，当一个普通集合类型只包含整数值元素，并且元素数量不多时，就会使用整数集合（intset）作为集合键的底层实现，它可以保存类型为 int16_t、int32_t 或者 int64_t 的整数值，并且不会重复。这可通过类似下面的命令来看出。
整数集合在 Redis 中的结构定义如下。
其中要注意的是，尽管 contents 字段申明为 int8_t 类型，但实际上它并不保存任何 int8_t 类型的值，保存的值的真正类型完全取决于 encoding 属性的值：
1、如果 encoding 的值为 INTSET_ENC_INT16，则 contents 是一个 int16_t 类型的数组。
2、如果 encoding 的值为 INTSET_ENC_INT32，则 contents 是一个 int32_t 类型的数组。
3、如果 encoding 的值为 INTSET_ENC_INT64，则 contents 是一个 int64_t 类型的数组。
因此，当某个时候新添加的元素的数值范围超出了当前集合的 encoding 属性对应的类型所能表示的范围时，就需要对该整数集合进行升级操作后再添加新元素，这个过程涉及的步骤如下：
1、根据新元素的类型扩展整数集合底层数组的空间大小。
2、将原来的元素的类型都转换成新元素的类型，并将它们按原来的大小顺序放到扩展后的空间对应的位上。
3、将新元素添加到底层数组中合适的位置（要么放在最开头，要么放在最末尾）。
4、修改 encoding 属性的值，并将 length 属性的值自增 1。
整数集合一经升级，之后就不能再降级了。
压缩列表（ziplist）是 Redis 为节约内存而开发，它是由一系列特殊编码的连续内存块组成的顺序型数据结构。
列表键和哈希键的底层实现都用到了压缩列表。当一个列表键只包含少量列表项，并且每项要么是小整数值，要么是较短的字符串，或者当一个哈希键只包含少量键值对，并且每一个键值对要么是小整数值，要么是较短的字符串时，Redis 就会使用压缩列表来做列表键或者哈希键的底层实现。这两种情况都可分别用“OBJECT ENCODING”命令来验证。
一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。下图展示了压缩列表的各个组成部分和说明。
为理解这些部分，假设有下图这样一个压缩列表示例。
其中，
* 属性 zlbytes 的值为 0x50，表示压缩列表的总长为 80 字节。
* 属性 zltail 的值为 0x3c，表示若指针 p 指向压缩列表的起始地址，则使用 p + 60 即可计算出表尾节点 entry3 的地址。
* 属性 zllen 的值为 0x3，表示压缩列表包含 3 个节点。
接下来再来说说压缩列表节点的构成。
每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组的长度可以是以下三种长度的其中之一：
1、小于等于 63（2^6 - 1）字节。
2、小于等于 16 383（2^14 - 1）字节。
3、小于等于 4 294 967 295（2^32 - 1）字节。
而整数值则可以是以下六种长度的其中一种：
1、4 位长、介于 0 至 12 之间的无符号整数。
2、1 字节长的有符号整数。
3、3 字节长的有符号整数。
4、int16_t 类型整数。
5、int32_t 类型整数。
6、int64_t 类型整数。
每个节点都由 previous_entry_length、encoding 和 content 三个部分组成，其中：
* previous_entry_length 属性的长度可以是 1 字节或者 5 字节，它记录了压缩列表中前一个节点的长度。如果前一节点的长度小于 254 个字节，则该属性的长度为 1 字节，否则为 5 字节（其中第一字节会被设置成 0xFE（十进制 254），之后的 4 个字节则用于保存前一节点的长度）。根据该性质，程序可以根据当前节点的起始地址来计算出前一个节点的起始地址，压缩列表的从表尾向表头遍历操作就是使用这一原理实现的。
* encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。它有以下两种情况：
1、1 字节、2 字节或者 5 字节长，值的最高位为 00、01 或者 10 的是字节数组编码，表示该节点的 content 属性保存着字节数组，数组的长度由除去最高两位之后的其他位记录。
2、1 字节长，值的最高位以 11 开头的是整数编码，表示 content 属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。
下面两张表分别记录了可用的字节数组和整数编码。
* content 属性负责保存节点的值，节点值可以是字节数组或者整数，其类型和长度由 encoding 属性决定。
下图展示了一个保存字节数组的节点示例：
其中，属性 previous_entry_length 的值为 0xFE00002766，最高位字节 0xFE 表示它占用五个字节，之后的四个字节 0x00002766（十进制 10086）才是前一节点的实际长度。属性 encoding 的最高两位 00 表示节点保存的是一个字节数组，后六位 001011 表示该数组的长度是 11。属性 content 保存着节点的值“hello world”。
此外，由于 previous_entry_length 属性的长度与前一个节点的长度是否小于 254 字节有关，因此当一个压缩列表中存在多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN 时，如果在 e1 之前插入了一个长度大于 254 字节的新节点，将迫使程序对压缩列表执行空间重分配操作，以将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长，而新增的四个字节又造成 e1 节点的长度变成了介于 254 字节到 257 字节之间，这进而又需要扩展 e2 节点的 previous_entry_length 属性长度，如此下去直到 eN。
这种在特殊情况下产生的连续多次空间扩展操作在 Redis 中就被称为“连锁更新”（cascade update）。除添加新节点外，删除节点也可能会引发连锁更新。由于连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N)，因此连锁更新的最坏复杂度为 O(N^2)。幸运的是，尽管连锁更新的复杂度较高，但由于其条件特殊，实际中它真正造成性能问题的几率其实是很低的。
参考书籍：
1、《Redis 的设计与实现》第 6 章——整数集合。
2、《Redis 的设计与实现》第 7 章——压缩列表。
redis> SADD nums 1 3 5 7 9 3 7 (integer)5 redis> OBJECT ENCODING nums "intset"
整数集合在 Redis 中的结构定义如下。
typedef struct intset{
uint32_t encoding; // 编码方式
uint32_t length; // 集合中包含的元素数量
int8_t contents[]; // 按从小到大的顺序保存元素的底层数组
}intset;
其中要注意的是，尽管 contents 字段申明为 int8_t 类型，但实际上它并不保存任何 int8_t 类型的值，保存的值的真正类型完全取决于 encoding 属性的值：
1、如果 encoding 的值为 INTSET_ENC_INT16，则 contents 是一个 int16_t 类型的数组。
2、如果 encoding 的值为 INTSET_ENC_INT32，则 contents 是一个 int32_t 类型的数组。
3、如果 encoding 的值为 INTSET_ENC_INT64，则 contents 是一个 int64_t 类型的数组。
因此，当某个时候新添加的元素的数值范围超出了当前集合的 encoding 属性对应的类型所能表示的范围时，就需要对该整数集合进行升级操作后再添加新元素，这个过程涉及的步骤如下：
1、根据新元素的类型扩展整数集合底层数组的空间大小。
2、将原来的元素的类型都转换成新元素的类型，并将它们按原来的大小顺序放到扩展后的空间对应的位上。
3、将新元素添加到底层数组中合适的位置（要么放在最开头，要么放在最末尾）。
4、修改 encoding 属性的值，并将 length 属性的值自增 1。
整数集合一经升级，之后就不能再降级了。
压缩列表（ziplist）是 Redis 为节约内存而开发，它是由一系列特殊编码的连续内存块组成的顺序型数据结构。
列表键和哈希键的底层实现都用到了压缩列表。当一个列表键只包含少量列表项，并且每项要么是小整数值，要么是较短的字符串，或者当一个哈希键只包含少量键值对，并且每一个键值对要么是小整数值，要么是较短的字符串时，Redis 就会使用压缩列表来做列表键或者哈希键的底层实现。这两种情况都可分别用“OBJECT ENCODING”命令来验证。
一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。下图展示了压缩列表的各个组成部分和说明。
为理解这些部分，假设有下图这样一个压缩列表示例。
其中，
* 属性 zlbytes 的值为 0x50，表示压缩列表的总长为 80 字节。
* 属性 zltail 的值为 0x3c，表示若指针 p 指向压缩列表的起始地址，则使用 p + 60 即可计算出表尾节点 entry3 的地址。
* 属性 zllen 的值为 0x3，表示压缩列表包含 3 个节点。
接下来再来说说压缩列表节点的构成。
每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组的长度可以是以下三种长度的其中之一：
1、小于等于 63（2^6 - 1）字节。
2、小于等于 16 383（2^14 - 1）字节。
3、小于等于 4 294 967 295（2^32 - 1）字节。
而整数值则可以是以下六种长度的其中一种：
1、4 位长、介于 0 至 12 之间的无符号整数。
2、1 字节长的有符号整数。
3、3 字节长的有符号整数。
4、int16_t 类型整数。
5、int32_t 类型整数。
6、int64_t 类型整数。
每个节点都由 previous_entry_length、encoding 和 content 三个部分组成，其中：
* previous_entry_length 属性的长度可以是 1 字节或者 5 字节，它记录了压缩列表中前一个节点的长度。如果前一节点的长度小于 254 个字节，则该属性的长度为 1 字节，否则为 5 字节（其中第一字节会被设置成 0xFE（十进制 254），之后的 4 个字节则用于保存前一节点的长度）。根据该性质，程序可以根据当前节点的起始地址来计算出前一个节点的起始地址，压缩列表的从表尾向表头遍历操作就是使用这一原理实现的。
* encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。它有以下两种情况：
1、1 字节、2 字节或者 5 字节长，值的最高位为 00、01 或者 10 的是字节数组编码，表示该节点的 content 属性保存着字节数组，数组的长度由除去最高两位之后的其他位记录。
2、1 字节长，值的最高位以 11 开头的是整数编码，表示 content 属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。
下面两张表分别记录了可用的字节数组和整数编码。
* content 属性负责保存节点的值，节点值可以是字节数组或者整数，其类型和长度由 encoding 属性决定。
下图展示了一个保存字节数组的节点示例：
其中，属性 previous_entry_length 的值为 0xFE00002766，最高位字节 0xFE 表示它占用五个字节，之后的四个字节 0x00002766（十进制 10086）才是前一节点的实际长度。属性 encoding 的最高两位 00 表示节点保存的是一个字节数组，后六位 001011 表示该数组的长度是 11。属性 content 保存着节点的值“hello world”。
此外，由于 previous_entry_length 属性的长度与前一个节点的长度是否小于 254 字节有关，因此当一个压缩列表中存在多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN 时，如果在 e1 之前插入了一个长度大于 254 字节的新节点，将迫使程序对压缩列表执行空间重分配操作，以将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长，而新增的四个字节又造成 e1 节点的长度变成了介于 254 字节到 257 字节之间，这进而又需要扩展 e2 节点的 previous_entry_length 属性长度，如此下去直到 eN。
这种在特殊情况下产生的连续多次空间扩展操作在 Redis 中就被称为“连锁更新”（cascade update）。除添加新节点外，删除节点也可能会引发连锁更新。由于连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N)，因此连锁更新的最坏复杂度为 O(N^2)。幸运的是，尽管连锁更新的复杂度较高，但由于其条件特殊，实际中它真正造成性能问题的几率其实是很低的。
参考书籍：
1、《Redis 的设计与实现》第 6 章——整数集合。
2、《Redis 的设计与实现》第 7 章——压缩列表。
