Redis 整数集合升级的触发机制分析

Redis 整数集合的基本结构

Redis 的整数集合（intset）是一种紧凑且高效的数据结构，主要用于存储整数类型的元素集合。它的设计目标是在内存使用上尽可能地节省空间，同时又能保证对集合元素的快速访问和操作。

整数集合的结构定义

在 Redis 的源码中，整数集合的结构体定义如下：

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length;   // 集合中元素的数量
    int8_t contents[]; // 柔性数组，存放集合中的元素
} intset;

encoding：该字段用于表示整数集合中元素所使用的编码方式。Redis 定义了三种编码方式，分别是 INTSET_ENC_INT16（16 位有符号整数）、INTSET_ENC_INT32（32 位有符号整数）和 INTSET_ENC_INT64（64 位有符号整数）。
length：记录整数集合中元素的数量。
contents：这是一个柔性数组，它实际存放了整数集合中的所有元素。柔性数组的好处是可以在结构体定义时不指定数组的大小，在实际使用时根据需要动态分配内存，这样可以有效减少内存碎片，并根据实际存储的元素灵活调整内存占用。

整数集合的特性

有序性：整数集合中的元素是按照从小到大的顺序存储的。这种有序性为一些操作（如二分查找）提供了便利，使得在查找元素时可以实现 O(log n) 的时间复杂度。
唯一性：整数集合中的元素是唯一的，不会出现重复的元素。当尝试向集合中插入一个已存在的元素时，插入操作会被忽略。

整数集合的编码方式

INTSET_ENC_INT16

当整数集合中的所有元素都可以用 16 位有符号整数表示时，会使用 INTSET_ENC_INT16 编码。在这种编码下，每个元素占用 2 个字节。例如，如果集合中的元素范围在 -32768 到 32767 之间，就适合使用这种编码。使用 INTSET_ENC_INT16 编码可以最大程度地节省内存空间，因为每个元素占用的字节数最少。

INTSET_ENC_INT32

如果集合中出现了无法用 16 位有符号整数表示的元素，但所有元素都可以用 32 位有符号整数表示，那么整数集合会采用 INTSET_ENC_INT32 编码。在这种编码下，每个元素占用 4 个字节。例如，当集合中出现了大于 32767 或者小于 -32768 的元素，但所有元素都在 -2147483648 到 2147483647 之间时，就会使用 INTSET_ENC_INT32 编码。

INTSET_ENC_INT64

当集合中存在无法用 32 位有符号整数表示的元素，即元素的范围超出了 -2147483648 到 2147483647 时，整数集合会升级到 INTSET_ENC_INT64 编码。在这种编码下，每个元素占用 8 个字节。

整数集合升级的触发机制

插入操作引发升级

整数集合的升级是在插入新元素时触发的。当执行插入操作时，Redis 会检查新元素是否可以用当前整数集合的编码方式存储。如果不能，就会触发升级操作。

升级的具体过程

检查新元素：在插入新元素之前，Redis 首先会检查新元素的大小，判断它是否可以用当前整数集合的编码方式存储。例如，如果当前整数集合使用 INTSET_ENC_INT16 编码，而要插入的新元素大于 32767 或者小于 -32768，那么就无法用当前编码存储。
确定新编码：一旦发现新元素无法用当前编码存储，Redis 会确定一个新的编码方式，使得新元素以及集合中现有的所有元素都能够被存储。这个新编码方式的选择原则是能够容纳集合中所有元素的最小编码。例如，如果当前编码是 INTSET_ENC_INT16，而新元素需要用 32 位整数存储，那么新编码就会被确定为 INTSET_ENC_INT32。
重新分配内存：确定新编码后，Redis 会根据新编码方式重新计算整数集合所需的内存大小，并重新分配内存。因为新编码下每个元素占用的字节数可能会增加，所以需要更大的内存空间来存储所有元素。例如，从 INTSET_ENC_INT16 升级到 INTSET_ENC_INT32 时，每个元素的大小从 2 字节变为 4 字节，集合所需的总内存也会相应增加。
数据迁移：重新分配内存后，Redis 会将原集合中的所有元素按照新编码方式重新存储到新的内存空间中。同时，新元素也会被插入到合适的位置，以保持集合的有序性。在数据迁移过程中，元素的顺序会被保持，并且重复元素会被忽略。

代码示例分析

以下是简化后的 Redis 整数集合插入操作的代码示例，用于说明升级的触发过程：

intset *intsetAdd(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;

    if (success) *success = 1;

    /* 如果新元素的编码大于当前集合的编码，需要升级 */
    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is, value);
    } else {
        /* 检查元素是否已存在 */
        if (intsetSearch(is, value, &pos)) {
            if (success) *success = 0;
            return is;
        }

        is = intsetResize(is, is->length+1);
        if (pos < is->length) intsetMoveTail(is, pos, pos+1);
    }

    _intsetSet(is, pos, value);
    is->length++;
    return is;
}

intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint32_t i, size = is->length;
    uint8_t oldenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);

    /* 确定新编码 */
    intset *newis = intsetNewByEncoding(newenc);
    newis->length = size+1;
    newis->encoding = intrev32ifbe(newenc);

    for (i = 0; i < size; i++) {
        int64_t v = _intsetGet(is, i);
        _intsetSet(newis, i, v);
    }

    if (newenc == oldenc) {
        pos = size;
    } else {
        pos = intsetSearch(newis, value, NULL);
    }

    _intsetSet(newis, pos, value);
    zfree(is);
    return newis;
}

在 intsetAdd 函数中，首先通过 _intsetValueEncoding 函数获取新元素的编码 valenc，然后将其与当前集合的编码进行比较。如果 valenc 大于当前集合的编码，就调用 intsetUpgradeAndAdd 函数进行升级和插入操作。

在 intsetUpgradeAndAdd 函数中，首先确定新的编码 newenc，然后创建一个新的整数集合 newis，其编码为 newenc。接着，将原集合中的所有元素迁移到新集合中，并确定新元素的插入位置 pos，最后将新元素插入到新集合中，并释放原集合的内存。

升级对性能和内存的影响

性能影响

插入性能：升级操作会带来一定的性能开销。因为升级过程涉及到重新分配内存和数据迁移，这两个操作的时间复杂度都与集合中元素的数量有关。在最坏情况下，重新分配内存和数据迁移的时间复杂度为 O(n)，其中 n 是集合中元素的数量。所以，当集合中元素数量较多时，升级操作可能会比较耗时。不过，由于整数集合通常用于存储相对较小的集合，这种性能开销在大多数情况下是可以接受的。
查找性能：升级操作本身不会直接影响查找性能。因为整数集合始终保持有序性，查找操作可以通过二分查找实现 O(log n) 的时间复杂度。但是，升级后每个元素占用的字节数可能会增加，这可能会导致缓存命中率下降，从而间接影响查找性能。不过，这种影响相对较小，特别是在现代硬件和操作系统的缓存机制下。

内存影响

内存增长：升级操作必然会导致内存的增长。因为升级后每个元素占用的字节数会增加，例如从 INTSET_ENC_INT16 升级到 INTSET_ENC_INT32 时，每个元素的大小从 2 字节变为 4 字节。虽然 Redis 在设计上尽量减少内存碎片，但是升级操作可能会导致内存使用量显著增加。因此，在使用 Redis 整数集合时，需要根据实际应用场景合理预估元素的范围，尽量避免频繁的升级操作，以控制内存使用。
内存释放：Redis 在整数集合升级后，会释放原集合的内存，并重新分配新的内存。这一过程可以有效避免内存泄漏问题。但是，由于内存分配和释放的操作可能会导致内存碎片的产生，长期来看，频繁的升级和元素删除操作可能会影响内存的整体使用效率。

避免不必要升级的策略

预定义合适的编码

在应用程序初始化 Redis 整数集合时，可以根据预期存储的元素范围，预先选择合适的编码方式。例如，如果已知要存储的整数范围在 -32768 到 32767 之间，就可以直接创建使用 INTSET_ENC_INT16 编码的整数集合；如果预计会有较大的整数，就选择 INTSET_ENC_INT32 或 INTSET_ENC_INT64 编码。这样可以从一开始就避免因为元素超出范围而触发升级操作。

批量插入

相比于单个元素的插入，批量插入操作可以减少升级的次数。因为在批量插入时，Redis 可以一次性检查所有要插入的元素，确定是否需要升级。如果所有元素都可以用当前编码存储，就不会触发升级。即使需要升级，也只需要进行一次升级操作，而不是每个元素插入时都检查和可能升级。例如，假设有一个应用程序需要插入 100 个元素，如果逐个插入，可能会因为某个元素超出当前编码范围而多次触发升级；而批量插入时，只需要一次判断和一次升级（如果需要）。

数据过滤

在将数据插入 Redis 整数集合之前，可以在应用程序层面进行数据过滤。例如，如果应用程序知道某个集合只应该存储特定范围内的整数，就可以在插入前检查元素是否在这个范围内。对于超出范围的元素，可以选择不插入，或者进行特殊处理（如记录日志等）。这样可以避免不必要的升级操作，同时也能保证集合数据的合理性。

升级与其他操作的关系

与删除操作的关系

删除操作不触发降级：在 Redis 整数集合中，删除元素不会触发降级操作。即使删除元素后，集合中的所有元素都可以用更低的编码方式存储，Redis 也不会自动将集合降级。这是因为降级操作同样需要重新分配内存和数据迁移，会带来额外的性能开销。而且，考虑到未来可能还会插入需要更高编码的元素，如果频繁进行降级和升级操作，会严重影响性能和内存使用效率。
删除操作对升级的影响：删除操作本身不会直接影响升级的触发机制。但是，如果删除元素后，集合中的元素范围发生了变化，可能会对后续插入操作是否触发升级产生影响。例如，原本因为某个较大元素而采用了 INTSET_ENC_INT32 编码的集合，当删除这个较大元素后，再次插入一个较小元素时，可能就不需要升级了。

与查找操作的关系

升级不影响查找逻辑：整数集合升级后，其查找操作的逻辑仍然保持不变，都是基于有序性进行二分查找。升级只是改变了元素的存储编码和占用字节数，不会影响元素的有序性。因此，无论是升级前还是升级后，查找操作的时间复杂度始终为 O(log n)。
查找性能与升级的间接关联：如前文所述，升级可能会因为元素占用字节数增加而影响缓存命中率，进而间接影响查找性能。但是，这种影响相对较小，并且在实际应用中，还需要综合考虑其他因素，如缓存策略、硬件配置等。

实际应用场景中的升级考虑

计数器应用

在一些计数器应用场景中，可能会使用 Redis 整数集合来存储不同的计数值。例如，统计网站每天的访问量，每个计数值就是一个整数。如果一开始预计访问量不会太大，可能会选择 INTSET_ENC_INT16 编码。但随着业务的发展，访问量可能会超出 16 位整数的范围，这时就会触发升级。在这种场景下，需要提前对业务增长有一定的预估，尽量选择合适的编码，避免频繁升级。同时，也可以考虑定期清理过期的计数值，以减少集合中的元素数量，降低升级带来的性能和内存压力。

标签系统

在标签系统中，每个标签可以用一个整数 ID 来表示。这些 ID 会被存储在 Redis 整数集合中。如果标签 ID 的分配范围比较稳定，并且可以用较小的编码表示，那么可以选择合适的编码以避免升级。但如果标签 ID 的分配是动态的，可能会出现较大的 ID，就需要考虑升级的情况。在这种场景下，可以通过批量插入标签 ID 的方式，减少升级的次数。同时，对于一些不再使用的标签 ID，可以及时从集合中删除，以优化内存使用。

游戏排行榜

在游戏排行榜应用中，玩家的分数通常会存储在 Redis 整数集合中。随着游戏的发展，玩家的分数可能会不断提高，超出最初设定的编码范围。例如，一开始可能预计玩家分数不会超过 16 位整数，但随着更多玩家参与和游戏难度的调整，分数可能会增大。这时就会触发整数集合的升级。为了应对这种情况，可以在设计排行榜系统时，对分数的增长趋势有一定的预判，选择合适的初始编码。并且，对于一些长时间不活跃玩家的分数，可以定期清理，以控制集合的大小，减少升级带来的影响。