Redis 整数集合降级的实现步骤
2021-11-043.9k 阅读
Redis 整数集合简介
在 Redis 中，整数集合（intset）是一种用于存储整数的数据结构，它被设计用来高效地存储和管理一组整数。整数集合具有紧凑的内存布局，当集合中所有元素都可以用相同类型的整数表示时，它能有效地节省内存。
整数集合的定义在 Redis 源码的 intset.h 文件中，其结构如下：
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组，以有序且唯一的方式存储
int8_t contents[];
} intset;
- encoding：表示整数集合中元素的编码方式，它决定了
contents数组中每个元素所占用的字节数。常见的编码有INTSET_ENC_INT16（每个元素占用 2 字节）、INTSET_ENC_INT32（每个元素占用 4 字节）和INTSET_ENC_INT64（每个元素占用 8 字节）。 - length：记录整数集合中元素的个数。
- contents：这是一个柔性数组，实际存储整数集合中的元素。这些元素以升序排列，并且没有重复值。
例如，当使用 INTSET_ENC_INT16 编码时，contents 数组中的每个元素都是 16 位有符号整数。如果集合中有三个元素 1、3、5，那么 contents 数组将依次存储 1、3、5，且占用的内存空间为 2 * 3 = 6 字节（不包括 intset 结构体本身的开销）。
整数集合的升级机制
在 Redis 中，整数集合的升级是为了适应新添加元素的类型需求。当向整数集合中添加一个新元素，而当前集合的编码方式无法容纳该元素时，整数集合会自动进行升级。
以向一个当前编码为 INTSET_ENC_INT16 的整数集合中添加一个大于 32767（16 位有符号整数的最大值）的元素为例。在这种情况下，集合需要升级到 INTSET_ENC_INT32 编码，以便能够存储该新元素。
升级的具体步骤如下：
- 计算新编码所需空间：首先，Redis 会计算升级后集合所需的总空间。假设原集合有
n个元素，编码从INTSET_ENC_INT16升级到INTSET_ENC_INT32，那么新的contents数组所需空间为4 * (n + 1)字节（加上新元素的空间）。 - 扩展内存：Redis 会为整数集合分配新的内存空间，将原
contents数组中的元素复制到新的内存空间，并按照新的编码方式进行存储。例如，对于原INTSET_ENC_INT16编码的元素1，在升级到INTSET_ENC_INT32后，它在新数组中的存储方式会从 2 字节扩展为 4 字节。 - 添加新元素：将新元素添加到扩展后的
contents数组中，并保持数组的有序性。
下面是 Redis 源码中 intsetAdd 函数中关于升级部分的简化代码示例（为了突出升级逻辑，省略了部分错误处理和其他细节）：
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
// 检查是否需要升级
if (valenc > intrev32ifbe(is->encoding)) {
// 升级集合
is = intsetUpgradeAndAdd(is, value);
if (success) *success = 1;
return is;
} else {
// 不需要升级，直接添加元素的逻辑
//...
}
}
intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
uint32_t pos;
intset *newis;
// 计算新编码
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t newenc = _intsetValueEncoding(value);
// 计算新集合的长度
uint32_t length = intrev32ifbe(is->length);
// 分配新集合的内存
newis = intsetNew(newenc);
newis->length = length + 1;
// 复制原集合元素到新集合
for (uint32_t j = 0; j < length; j++) {
int64_t e = intsetGet(is, j);
intsetAddRaw(newis, e, &pos);
}
// 添加新元素
intsetAddRaw(newis, value, &pos);
// 释放原集合内存
zfree(is);
return newis;
}
从上述代码可以看出，intsetUpgradeAndAdd 函数负责执行升级和添加新元素的操作。它先创建一个新的整数集合（newis），按照新的编码方式分配内存，然后将原集合的元素复制到新集合，最后添加新元素并释放原集合的内存。
整数集合降级的需求背景
虽然 Redis 的整数集合在大多数情况下通过升级机制能够很好地适应数据存储需求，但在某些特殊场景下，整数集合可能会出现过度升级的情况。例如，一个原本使用 INTSET_ENC_INT16 编码的整数集合，由于临时添加了一个较大的元素而升级到 INTSET_ENC_INT32。但之后，如果集合中的较大元素被移除，而剩余元素都可以用 INTSET_ENC_INT16 编码表示，此时集合就处于一种内存浪费的状态，因为每个元素都占用了比实际需要更多的字节数。
在这种情况下，就需要整数集合进行降级操作，以释放多余的内存空间，提高内存使用效率。整数集合的降级可以使集合回到更紧凑的编码方式，从而在存储相同数量元素时占用更少的内存。例如，从 INTSET_ENC_INT32 降级到 INTSET_ENC_INT16，每个元素的存储字节数从 4 字节减少到 2 字节，对于一个包含大量元素的集合，这将显著节省内存。
整数集合降级的难点分析
- 数据一致性维护：在进行降级操作时，需要确保集合中所有元素都能在新的编码方式下正确表示。这意味着要检查集合中的每个元素是否都符合新编码的取值范围。例如，从
INTSET_ENC_INT32降级到INTSET_ENC_INT16，集合中的所有元素都必须在-32768到32767之间，否则降级操作就不能进行，以保证数据的完整性和一致性。 - 内存重新分配与数据迁移：降级过程涉及到内存的重新分配和数据的迁移。需要为新编码方式的整数集合分配合适的内存空间，并将原集合中的元素按照新编码方式复制到新的内存位置。这个过程需要精确计算内存大小，避免内存泄漏或数据丢失。例如，从
INTSET_ENC_INT32降级到INTSET_ENC_INT16，需要重新计算每个元素在新数组中的存储位置，并正确复制数据。 - 编码切换的原子性：为了保证 Redis 数据结构的正确性，编码切换操作需要是原子性的。即要么整个降级操作成功完成，集合成功切换到新的编码方式；要么在出现任何错误时，集合保持原有的编码和数据状态，不会出现部分数据在新编码、部分数据在原编码的不一致情况。
整数集合降级的实现步骤
- 检查降级条件：首先，Redis 需要检查当前整数集合是否满足降级条件。这包括检查所有元素是否都能在目标降级编码方式下表示。例如，对于从
INTSET_ENC_INT32降级到INTSET_ENC_INT16，需要遍历集合中的每个元素，确保其值在-32768到32767之间。
int canDowngrade(intset *is) {
uint32_t length = intrev32ifbe(is->encoding);
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t targetenc = curenc == INTSET_ENC_INT32? INTSET_ENC_INT16 : curenc == INTSET_ENC_INT64? INTSET_ENC_INT32 : 0;
if (targetenc == 0) return 0;
for (uint32_t i = 0; i < length; i++) {
int64_t value = intsetGet(is, i);
if (!_intsetValueFitsEncoding(value, targetenc)) {
return 0;
}
}
return 1;
}
上述代码中，canDowngrade 函数遍历整数集合中的每个元素，调用 _intsetValueFitsEncoding 函数检查每个元素是否能在目标降级编码方式下表示。如果所有元素都满足条件，则返回 1，表示可以降级；否则返回 0。
- 分配新内存：如果满足降级条件，Redis 会为新编码方式的整数集合分配内存。计算新集合所需的内存大小，其公式为
新编码每个元素字节数 * 元素个数。例如，从INTSET_ENC_INT32降级到INTSET_ENC_INT16，且集合中有n个元素，那么新集合所需内存为2 * n字节（假设不考虑intset结构体本身的额外开销）。
intset *createDowngradedIntset(intset *is) {
uint32_t length = intrev32ifbe(is->length);
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t targetenc = curenc == INTSET_ENC_INT32? INTSET_ENC_INT16 : curenc == INTSET_ENC_INT64? INTSET_ENC_INT32 : 0;
intset *newis = intsetNew(targetenc);
newis->length = length;
return newis;
}
createDowngradedIntset 函数根据目标降级编码方式创建一个新的整数集合，并设置其长度与原集合相同。
- 数据迁移：将原集合中的元素按照新编码方式复制到新分配的内存空间中。在复制过程中，需要注意元素的字节序和数据转换。例如，从
INTSET_ENC_INT32到INTSET_ENC_INT16的转换，需要将 32 位整数转换为 16 位整数，并确保数据的正确性。
void migrateData(intset *src, intset *dst) {
uint32_t length = intrev32ifbe(src->length);
for (uint32_t i = 0; i < length; i++) {
int64_t value = intsetGet(src, i);
intsetAddRaw(dst, value, NULL);
}
}
migrateData 函数遍历原集合（src）中的每个元素，获取其值并通过 intsetAddRaw 函数将其添加到新集合（dst）中。
- 释放原内存并更新指针：完成数据迁移后，释放原整数集合占用的内存，并将指向原集合的指针更新为指向新的降级后的集合。
intset *downgradeIntset(intset *is) {
if (!canDowngrade(is)) return is;
intset *newis = createDowngradedIntset(is);
migrateData(is, newis);
zfree(is);
return newis;
}
downgradeIntset 函数是整数集合降级的主函数，它首先检查是否可以降级，然后创建新的降级集合，迁移数据，最后释放原集合内存并返回新集合。
代码示例完整实现
下面是一个完整的 Redis 整数集合降级的代码示例，包含上述所有步骤的实现：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
intset *intsetNew(uint8_t enc) {
intset *is = zmalloc(sizeof(intset) + sizeof(int8_t));
is->encoding = intrev32ifbe(enc);
is->length = 0;
return is;
}
int intrev32ifbe(uint32_t v) {
return v;
}
uint8_t _intsetValueEncoding(int64_t v) {
if (v < (INT32_MIN) || v > (INT32_MAX))
return INTSET_ENC_INT64;
else if (v < (INT16_MIN) || v > (INT16_MAX))
return INTSET_ENC_INT32;
else
return INTSET_ENC_INT16;
}
int _intsetValueFitsEncoding(int64_t v, uint8_t enc) {
switch (enc) {
case INTSET_ENC_INT16:
return v >= (INT16_MIN) && v <= (INT16_MAX);
case INTSET_ENC_INT32:
return v >= (INT32_MIN) && v <= (INT32_MAX);
case INTSET_ENC_INT64:
return 1;
default:
return 0;
}
}
intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
// 省略具体实现，见前文介绍
}
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
// 省略具体实现，见前文介绍
}
int canDowngrade(intset *is) {
// 省略具体实现，见前文介绍
}
intset *createDowngradedIntset(intset *is) {
// 省略具体实现，见前文介绍
}
void migrateData(intset *src, intset *dst) {
// 省略具体实现，见前文介绍
}
intset *downgradeIntset(intset *is) {
// 省略具体实现，见前文介绍
}
int intsetGet(intset *is, uint32_t pos) {
uint32_t encoding = intrev32ifbe(is->encoding);
if (pos >= intrev32ifbe(is->length)) return 0;
switch (encoding) {
case INTSET_ENC_INT16:
return *(int16_t*)&is->contents[pos * sizeof(int16_t)];
case INTSET_ENC_INT32:
return *(int32_t*)&is->contents[pos * sizeof(int32_t)];
case INTSET_ENC_INT64:
return *(int64_t*)&is->contents[pos * sizeof(int64_t)];
default:
return 0;
}
}
void intsetAddRaw(intset *is, int64_t value, uint32_t *pos) {
// 省略具体实现，负责在不检查编码和是否重复的情况下添加元素
}
void printIntset(intset *is) {
uint32_t length = intrev32ifbe(is->length);
for (uint32_t i = 0; i < length; i++) {
int64_t value = intsetGet(is, i);
printf("%lld ", (long long)value);
}
printf("\n");
}
int main() {
intset *is = intsetNew(INTSET_ENC_INT16);
uint8_t success;
is = intsetAdd(is, 1, &success);
is = intsetAdd(is, 3, &success);
is = intsetAdd(is, 5, &success);
is = intsetAdd(is, 32768, &success); // 导致升级到 INTSET_ENC_INT32
printf("After upgrade, encoding: %d, elements: ", intrev32ifbe(is->encoding));
printIntset(is);
// 模拟移除较大元素，假设移除 32768
// 这里省略实际移除元素的代码，直接进行降级检查和操作
if (canDowngrade(is)) {
is = downgradeIntset(is);
printf("After downgrade, encoding: %d, elements: ", intrev32ifbe(is->encoding));
printIntset(is);
} else {
printf("Can't downgrade.\n");
}
return 0;
}
在上述代码中，main 函数首先创建一个初始编码为 INTSET_ENC_INT16 的整数集合，并添加一些元素。然后添加一个会导致升级的元素 32768，模拟集合升级。接着，假设移除了导致升级的元素后，检查是否可以降级并执行降级操作，最后输出降级前后集合的编码和元素。
降级操作对 Redis 性能和内存的影响
- 性能影响：降级操作本身会带来一定的性能开销。因为它涉及到内存的重新分配和数据的迁移，这两个操作都需要消耗 CPU 时间。特别是对于包含大量元素的整数集合，数据迁移的时间开销可能会比较明显。然而，由于 Redis 是单线程模型，在执行降级操作时，会阻塞其他命令的执行。因此，在生产环境中，如果整数集合非常大，应该谨慎执行降级操作，或者选择在系统负载较低的时间段进行。
- 内存影响：降级操作的主要目的是节省内存。通过将整数集合从较高编码方式降级到较低编码方式，每个元素占用的字节数减少，从而减少整个集合占用的内存空间。对于存储大量整数的集合，这种内存节省可能非常显著。例如，从
INTSET_ENC_INT32降级到INTSET_ENC_INT16，在元素数量较多时，可以节省约一半的内存空间，这对于内存资源有限的系统来说是非常有价值的。
实际应用场景中的考虑
- 缓存数据场景：在缓存数据时，如果整数集合用于存储一些临时数据，并且数据的范围可能会发生变化，那么需要考虑降级操作。例如，缓存中存储用户的年龄信息，初始时年龄范围都在 16 位整数可表示范围内，但可能由于某些特殊情况，临时添加了一个超出范围的年龄值，导致集合升级。当这些特殊情况消失后，执行降级操作可以释放多余的内存，提高缓存的内存使用效率。
- 计数器场景：在使用整数集合作为计数器的场景中，如果计数器的值在某个时间段内突然增大，导致整数集合升级，但之后又恢复到较小的值范围，此时降级操作可以优化内存使用。例如，在统计网站页面访问量时，可能在某个热门事件期间，访问量急剧增加，使整数集合升级。事件结束后，执行降级操作可以减少内存占用。
在实际应用中，需要根据具体的数据访问模式和内存使用情况，合理地决定是否执行整数集合的降级操作，以达到性能和内存使用的最佳平衡。同时，由于降级操作会带来一定的性能开销，在高并发的生产环境中，应该进行充分的测试和评估，确保降级操作不会对系统的整体性能产生负面影响。