Redis 整数集合实现中的内存优化策略
Redis 整数集合概述
Redis 作为一款高性能的键值对数据库，在处理数据存储和读取方面有着出色的表现。其中，整数集合（intset）是 Redis 用于存储整数的一种紧凑数据结构，主要应用于集合对象只包含整数值元素，并且元素数量不多的场景。例如，当我们使用 SADD 命令向集合中添加少量整数元素时，如果满足上述条件，Redis 就会使用整数集合来存储这些元素。
整数集合的设计目标是在尽可能节省内存的前提下，高效地支持集合操作，如添加、删除和查找元素等。它是 Redis 中一种轻量级的数据结构，对于小而密集的整数集合数据存储和操作具有很大的优势。
整数集合的数据结构定义
在 Redis 的源码中，整数集合（intset）的数据结构定义如下：
typedef struct intset {
uint32_t encoding; // 编码方式，用于表示集合中元素的类型
uint32_t length; // 集合中元素的数量
int8_t contents[]; // 柔性数组，实际存储元素的地方
} intset;
encoding字段：该字段用于指定集合中元素的编码方式。Redis 通过encoding来判断元素的类型，从而决定如何在内存中存储和读取这些元素。encoding可能的取值有INTSET_ENC_INT16（表示 16 位有符号整数）、INTSET_ENC_INT32（表示 32 位有符号整数）和INTSET_ENC_INT64（表示 64 位有符号整数）。length字段：记录了整数集合中当前存储的元素个数。通过这个字段，我们可以直接获取集合的大小，从而在进行集合操作时，快速判断集合是否已满或者是否为空等情况。contents柔性数组：这是一个柔性数组，它紧跟在intset结构体的其他字段之后，实际存储整数集合中的元素。柔性数组的好处是可以根据实际需要动态分配内存，使得整个数据结构在存储元素时更加灵活和高效，同时也节省了内存空间。
内存优化策略 - 动态编码调整
编码调整的触发条件
Redis 的整数集合采用了动态编码调整策略，以达到内存优化的目的。当我们向整数集合中添加新元素时，如果新元素的类型大于当前集合的编码类型，就会触发编码调整。例如，当前集合的编码为 INTSET_ENC_INT16，表示集合中的元素都是 16 位有符号整数。如果我们要添加一个 32 位有符号整数，就需要将集合的编码调整为 INTSET_ENC_INT32。
编码调整的实现过程
在 Redis 源码中，添加元素的函数 intsetAdd 会处理编码调整的逻辑。下面是简化后的 intsetAdd 函数实现（只保留与编码调整相关的关键部分）：
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value); // 获取新元素的编码类型
uint32_t pos;
if (valenc > intrev32ifbe(is->encoding)) { // 新元素编码类型大于当前集合编码类型
return intsetUpgradeAndAdd(is, value); // 进行编码升级并添加元素
} else {
// 常规添加元素逻辑，这里省略
}
return is;
}
在 intsetUpgradeAndAdd 函数中，会先根据新的编码类型重新分配内存，然后将原集合中的元素按照新的编码类型重新存储，并将新元素插入到合适的位置。
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t newenc = _intsetValueEncoding(value);
uint32_t length = is->length;
intset *newis;
int prepend = value < 0? 1 : 0;
// 根据新编码类型计算新的整数集合大小
newis = intsetNew(newenc);
newis->length = length + 1;
newis->contents = zmalloc(intsetBlobLen(newenc, newis->length));
// 将原集合元素按照新编码类型重新存储
for (uint32_t j = 0; j < length; j++) {
int64_t member = intsetGet(is, j);
intsetSet(newis, intsetSearch(newis, member, &pos) + prepend, member);
}
// 插入新元素
intsetSet(newis, prepend? 0 : length, value);
zfree(is->contents);
zfree(is);
return newis;
}
这种动态编码调整策略的好处是，在集合中元素类型较小时，使用较小的编码类型存储元素，从而节省内存空间；当有更大类型的元素加入时，动态调整编码类型，保证集合能够正确存储所有元素，同时尽可能地优化内存使用。
内存优化策略 - 紧凑存储
有序存储与二分查找
整数集合中的元素是按照从小到大的顺序存储的。这种有序存储方式不仅有助于在添加和删除元素时保持集合的有序性，还为二分查找提供了便利。在 Redis 中，查找元素的函数 intsetSearch 采用了二分查找算法，其实现如下：
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
if (value > intsetGet(is,max)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
} else if (value < intsetGet(is,0)) {
if (pos) *pos = 0;
return 0;
}
}
while(max >= min) {
mid = (min+max)/2;
cur = intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
二分查找算法的时间复杂度为 O(log n)，其中 n 是集合中元素的数量。相比于无序存储需要遍历整个集合来查找元素（时间复杂度为 O(n)），有序存储结合二分查找大大提高了查找效率。这间接实现了内存优化，因为高效的查找意味着在相同的操作需求下，不需要为了提高查找效率而额外增加数据结构或者冗余信息，从而节省了内存。
无空洞存储
整数集合在删除元素时，会将后续元素向前移动，填补被删除元素的位置，确保集合中不存在空洞。在 Redis 源码中，删除元素的函数 intsetRemove 实现了这一逻辑：
intset *intsetRemove(intset *is, int64_t value, int *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 0;
if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is, value, &pos)) {
uint32_t len = intrev32ifbe(is->length);
// 移动后续元素填补空洞
if (pos < (len-1)) {
memmove(intsetGetPtr(is,pos), intsetGetPtr(is,pos+1),
(len - (pos+1)) * intsetElemSize(is->encoding));
}
is->length = intrev32ifbe(intrev32ifbe(is->length)-1);
if (success) *success = 1;
// 如果集合为空或者所有元素都可以用更小的编码表示，则尝试降级编码
if (is->length == 0) {
zfree(is->contents);
zfree(is);
return NULL;
} else if (valenc < intrev32ifbe(is->encoding) && intsetIsSupersetOfMinimal(is, valenc)) {
is = intsetDowngradeIfPossible(is);
}
}
return is;
}
通过这种无空洞存储方式，整数集合在内存中保持紧凑，避免了因空洞导致的内存浪费。同时，这也有助于在进行添加元素操作时，能够更有效地利用已有的内存空间，减少内存重新分配的次数，进一步优化内存使用。
内存优化策略 - 编码降级
编码降级的触发条件
当从整数集合中删除元素后，如果集合中的所有元素都可以用比当前编码更小的编码类型来表示，Redis 就会尝试进行编码降级。例如，当前集合的编码为 INTSET_ENC_INT32，如果删除一个元素后，剩余元素都可以用 INTSET_ENC_INT16 表示，就会触发编码降级。
编码降级的实现过程
在 intsetRemove 函数中，删除元素后会调用 intsetDowngradeIfPossible 函数来尝试编码降级。
static intset *intsetDowngradeIfPossible(intset *is) {
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t newenc = _intsetFindMinEncoding(is);
if (newenc < curenc) {
intset *newis = intsetNew(newenc);
newis->length = is->length;
newis->contents = zmalloc(intsetBlobLen(newenc, newis->length));
for (uint32_t j = 0; j < intrev32ifbe(newis->length); j++) {
int64_t member = intsetGet(is, j);
intsetSet(newis, j, member);
}
zfree(is->contents);
zfree(is);
return newis;
}
return is;
}
_intsetFindMinEncoding 函数用于找出集合中所有元素能够使用的最小编码类型。编码降级同样是为了进一步优化内存使用，将集合的编码类型调整为更紧凑的形式，从而减少内存占用。
实际应用场景中的内存优化示例
假设我们要使用 Redis 集合来存储用户的年龄信息，初始时添加的年龄数据都在 0 - 127 之间，此时 Redis 会使用 INTSET_ENC_INT16 编码的整数集合来存储这些数据。
127.0.0.1:6379> SADD age_set 25 30 40 50
(integer) 4
如果后续需要添加一个较大的年龄值，比如 200，此时就会触发编码调整，将集合编码升级为 INTSET_ENC_INT32。
127.0.0.1:6379> SADD age_set 200
(integer) 1
当我们删除一些较大的年龄值，使得集合中的元素又都可以用 INTSET_ENC_INT16 表示时，就会触发编码降级。
127.0.0.1:6379> SREM age_set 200
(integer) 1
通过这种动态的编码调整（包括升级和降级）以及紧凑存储策略，在实际应用中，Redis 的整数集合能够根据数据的特点，自动优化内存使用，在保证性能的前提下，最大限度地节省内存空间。无论是在内存资源有限的服务器环境，还是对于存储大量小而密集整数集合数据的应用场景，这种内存优化策略都具有重要的实际意义。
与其他数据结构在内存使用上的对比
与普通数组的对比
普通数组在存储整数时，如果不考虑类型的动态调整，通常会采用固定的元素类型，比如 int（在 32 位系统上一般为 32 位有符号整数）。假设我们要存储 100 个 16 位有符号整数，使用普通数组存储时，每个元素占用 4 个字节（假设 int 为 4 字节），总共需要 400 字节的内存空间。而 Redis 的整数集合在这种情况下，会使用 INTSET_ENC_INT16 编码，每个元素只占用 2 个字节，100 个元素只需要 200 字节的内存空间，相比普通数组节省了一半的内存。
与哈希表的对比
哈希表在存储整数时，通常会为每个键值对分配额外的空间来存储哈希值、指针等信息。以 C 语言中的哈希表实现为例，假设哈希表的负载因子为 0.75，存储 100 个整数键值对（键和值都为整数），除了整数本身占用的空间外，还需要为哈希表的元数据、哈希桶等分配额外的空间。而 Redis 的整数集合在只存储整数元素且元素数量不多的情况下，不需要额外的哈希计算和存储哈希桶等开销，内存使用更加紧凑。
通过与其他常见数据结构在内存使用上的对比，可以更清晰地看到 Redis 整数集合在存储小而密集的整数集合数据时，内存优化策略所带来的优势。它通过动态编码调整、紧凑存储和编码降级等策略，在不同的应用场景下，都能够有效地节省内存空间，为 Redis 在高性能和低内存占用方面的出色表现提供了有力支持。