Redis 整数集合升级带来的性能提升

Redis 整数集合概述

Redis 的整数集合（intset）是一种紧凑的数据结构，用于保存类型为 int16_t、int32_t 或 int64_t 的整数值，且集合中的元素是唯一且有序的。它在 Redis 的 set 数据结构实现中，当集合元素全为整数且数量不多时会被使用。

整数集合的结构定义如下：

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

其中，encoding 字段用于标识集合中元素所使用的编码方式，可能的取值有 INTSET_ENC_INT16（16 位整数编码）、INTSET_ENC_INT32（32 位整数编码）和 INTSET_ENC_INT64（64 位整数编码）。length 字段记录集合中元素的数量，而 contents 是一个柔性数组，实际存储集合中的整数元素。

整数集合的编码方式

1. INTSET_ENC_INT16 当整数集合中所有元素都可以用 16 位有符号整数表示时，会采用 INTSET_ENC_INT16 编码。在这种编码下，contents 数组中的每个元素都是 int16_t 类型。例如，若集合中有元素 10、20、30，则它们在数组中按顺序存储，每个元素占用 2 个字节。

2. INTSET_ENC_INT32 如果新加入的元素无法用 16 位整数表示，但可以用 32 位有符号整数表示，整数集合会升级到 INTSET_ENC_INT32 编码。此时，contents 数组中的元素变为 int32_t 类型，每个元素占用 4 个字节。例如，若原本集合是 [10, 20, 30]（采用 INTSET_ENC_INT16 编码），当加入元素 32768（无法用 16 位表示）时，集合会升级到 INTSET_ENC_INT32 编码。

3. INTSET_ENC_INT64 同理，当有元素无法用 32 位整数表示，而需要 64 位有符号整数表示时，整数集合会升级到 INTSET_ENC_INT64 编码，contents 数组中的元素变为 int64_t 类型，每个元素占用 8 个字节。

整数集合升级机制

1. 升级触发条件 整数集合的升级是在向集合中添加新元素时触发的。当新元素的类型无法用当前集合的编码方式存储时，就会进行升级。例如，当前集合采用 INTSET_ENC_INT16 编码，若要添加一个大于 32767 或小于 -32768 的整数，就会触发升级。

2. 升级过程

   • 重新分配内存：根据新的编码方式，计算出所需的新内存大小。例如，从 INTSET_ENC_INT16 升级到 INTSET_ENC_INT32，由于每个元素占用字节数从 2 变为 4，新的 contents 数组大小需要重新计算。假设原集合有 n 个元素，原 contents 数组大小为 2 * n 字节，升级后 contents 数组大小变为 4 * n 字节。然后使用 realloc 函数重新分配内存，将原数据复制到新内存区域。
   • 转换元素类型：重新分配内存后，需要将原集合中的所有元素转换为新编码方式对应的类型。例如，从 INTSET_ENC_INT16 升级到 INTSET_ENC_INT32，要将每个 int16_t 类型的元素转换为 int32_t 类型。这一步通过循环遍历 contents 数组，对每个元素进行类型转换实现。
   • 添加新元素：完成元素类型转换后，将新元素按照有序的原则插入到 contents 数组的合适位置。

整数集合升级带来的性能提升本质分析

1. 节省内存空间 在初始阶段，当元素都可以用较小的编码方式（如 INTSET_ENC_INT16）存储时，使用这种紧凑的编码可以有效节省内存。然而，随着元素范围的扩大，如果不进行升级，就需要使用更大的数据结构（如 int64_t 数组）来存储所有元素，即使大部分元素其实可以用较小的类型表示。通过升级机制，在元素类型范围较小时使用较小的编码，当范围超出时逐步升级，避免了一开始就使用过大的内存空间。例如，若集合最初只有 10 个 int16_t 类型的元素，使用 INTSET_ENC_INT16 编码，内存占用为 2 * 10 = 20 字节。若后续添加一个 int32_t 类型的元素，升级到 INTSET_ENC_INT32 编码后，内存占用变为 4 * (10 + 1) = 44 字节。相比一开始就使用 int32_t 数组存储所有元素（内存占用 4 * 10 = 40 字节，添加新元素后变为 4 * 11 = 44 字节），在初始阶段节省了内存。

2. 提高操作效率

   • 查找操作：由于整数集合是有序的，在进行查找操作时可以使用二分查找算法。升级后，虽然元素占用的字节数可能增加，但因为集合的有序性保持不变，二分查找的时间复杂度仍然是 $O(\log n)$，其中 n 是集合元素的数量。而且，升级后的内存布局可能更利于 CPU 缓存的利用，从而加快查找速度。例如，在 INTSET_ENC_INT16 编码下，元素紧密排列，但当 CPU 缓存行大小固定时，可能一次缓存行读取无法包含足够多的有用信息。升级到 INTSET_ENC_INT32 编码后，虽然每个元素变大，但可能一次缓存行读取能包含更多的查找相关数据，减少内存访问次数，提高查找效率。
   • 插入和删除操作：在插入操作时，升级后的集合虽然可能需要更多的内存移动（因为元素变大），但由于有序性，插入位置的确定仍然是高效的。例如，在 INTSET_ENC_INT16 编码集合中插入一个新元素，需要移动一定数量的 int16_t 类型元素；升级到 INTSET_ENC_INT32 编码后，虽然移动的字节数增加，但仍然可以通过二分查找快速确定插入位置。删除操作同理，通过二分查找确定元素位置后，进行元素移动删除，升级后的集合在操作逻辑上并没有增加太多复杂性，且可能因内存布局优化而提高效率。

代码示例

下面通过一段 C 代码示例来模拟 Redis 整数集合的升级过程：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// 定义整数集合结构
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

// 创建一个新的整数集合
intset* intsetNew(void) {
    intset* is = (intset*)malloc(sizeof(intset) + sizeof(int16_t));
    is->encoding = INTSET_ENC_INT16;
    is->length = 0;
    return is;
}

// 获取整数集合中元素的大小
size_t intsetEncodingSize(uint32_t encoding) {
    return encoding == INTSET_ENC_INT16? sizeof(int16_t) :
           encoding == INTSET_ENC_INT32? sizeof(int32_t) :
           encoding == INTSET_ENC_INT64? sizeof(int64_t) : 0;
}

// 升级整数集合
void intsetUpgrade(intset* is, int64_t value) {
    uint32_t oldencoding = is->encoding;
    uint32_t newencoding = value > INT32_MAX || value < INT32_MIN? INTSET_ENC_INT64 : INTSET_ENC_INT32;
    uint32_t oldlen = is->length;
    uint32_t newlen = oldlen + 1;
    size_t oldelemsize = intsetEncodingSize(oldencoding);
    size_t newelemsize = intsetEncodingSize(newencoding);

    // 重新分配内存
    is = (intset*)realloc(is, sizeof(intset) + newelemsize * newlen);

    // 转换元素类型
    for (int i = oldlen - 1; i >= 0; i--) {
        int64_t elem;
        switch (oldencoding) {
            case INTSET_ENC_INT16:
                elem = *(int16_t*)&is->contents[i * oldelemsize];
                break;
            case INTSET_ENC_INT32:
                elem = *(int32_t*)&is->contents[i * oldelemsize];
                break;
            case INTSET_ENC_INT64:
                elem = *(int64_t*)&is->contents[i * oldelemsize];
                break;
        }
        switch (newencoding) {
            case INTSET_ENC_INT16:
                *(int16_t*)&is->contents[(i + 1) * newelemsize] = (int16_t)elem;
                break;
            case INTSET_ENC_INT32:
                *(int32_t*)&is->contents[(i + 1) * newelemsize] = (int32_t)elem;
                break;
            case INTSET_ENC_INT64:
                *(int64_t*)&is->contents[(i + 1) * newelemsize] = elem;
                break;
        }
    }

    // 设置新的编码和长度
    is->encoding = newencoding;
    is->length = newlen;
}

// 添加元素到整数集合
void intsetAdd(intset* is, int64_t value) {
    if (is->length == 0) {
        // 集合为空，直接添加
        switch (is->encoding) {
            case INTSET_ENC_INT16:
                *(int16_t*)&is->contents[0] = (int16_t)value;
                break;
            case INTSET_ENC_INT32:
                *(int32_t*)&is->contents[0] = (int32_t)value;
                break;
            case INTSET_ENC_INT64:
                *(int64_t*)&is->contents[0] = value;
                break;
        }
        is->length = 1;
    } else {
        // 检查是否需要升级
        if ((is->encoding == INTSET_ENC_INT16 && (value > INT16_MAX || value < INT16_MIN)) ||
            (is->encoding == INTSET_ENC_INT32 && (value > INT32_MAX || value < INT32_MIN))) {
            intsetUpgrade(is, value);
        }

        // 找到插入位置
        size_t pos = 0;
        size_t elemsize = intsetEncodingSize(is->encoding);
        for (pos = 0; pos < is->length; pos++) {
            int64_t elem;
            switch (is->encoding) {
                case INTSET_ENC_INT16:
                    elem = *(int16_t*)&is->contents[pos * elemsize];
                    break;
                case INTSET_ENC_INT32:
                    elem = *(int32_t*)&is->contents[pos * elemsize];
                    break;
                case INTSET_ENC_INT64:
                    elem = *(int64_t*)&is->contents[pos * elemsize];
                    break;
            }
            if (value < elem) {
                break;
            }
        }

        // 移动元素并插入
        for (int i = is->length; i > pos; i--) {
            for (int j = 0; j < elemsize; j++) {
                is->contents[i * elemsize + j] = is->contents[(i - 1) * elemsize + j];
            }
        }
        switch (is->encoding) {
            case INTSET_ENC_INT16:
                *(int16_t*)&is->contents[pos * elemsize] = (int16_t)value;
                break;
            case INTSET_ENC_INT32:
                *(int32_t*)&is->contents[pos * elemsize] = (int32_t)value;
                break;
            case INTSET_ENC_INT64:
                *(int64_t*)&is->contents[pos * elemsize] = value;
                break;
        }
        is->length++;
    }
}

// 打印整数集合内容
void intsetPrint(intset* is) {
    size_t elemsize = intsetEncodingSize(is->encoding);
    for (int i = 0; i < is->length; i++) {
        switch (is->encoding) {
            case INTSET_ENC_INT16:
                printf("%d ", *(int16_t*)&is->contents[i * elemsize]);
                break;
            case INTSET_ENC_INT32:
                printf("%d ", *(int32_t*)&is->contents[i * elemsize]);
                break;
            case INTSET_ENC_INT64:
                printf("%ld ", *(int64_t*)&is->contents[i * elemsize]);
                break;
        }
    }
    printf("\n");
}

int main() {
    intset* is = intsetNew();
    intsetAdd(is, 10);
    intsetAdd(is, 20);
    intsetAdd(is, 30);
    printf("After adding 10, 20, 30: ");
    intsetPrint(is);

    intsetAdd(is, 32768);
    printf("After adding 32768: ");
    intsetPrint(is);

    free(is);
    return 0;
}

在上述代码中，intsetNew 函数用于创建一个新的整数集合，intsetEncodingSize 函数用于获取当前编码下元素的大小。intsetUpgrade 函数实现了整数集合的升级逻辑，包括重新分配内存和转换元素类型。intsetAdd 函数用于向集合中添加元素，会先检查是否需要升级，然后找到合适的插入位置并插入元素。intsetPrint 函数用于打印集合中的元素。在 main 函数中，演示了创建集合、添加元素以及因添加元素导致集合升级的过程。

升级对 Redis 整体性能的影响

1. 内存管理方面

   • 动态内存分配优化：Redis 在处理整数集合升级时，通过 realloc 函数动态调整内存大小。这种动态内存分配策略在集合元素数量和类型动态变化的场景下，避免了静态分配内存带来的浪费或不足问题。例如，在一个计数器应用中，初始计数值较小，可以用 INTSET_ENC_INT16 编码存储。随着业务增长，计数值超出 int16_t 范围，整数集合升级，动态调整内存，保证内存使用的高效性。
   • 内存碎片控制：虽然 realloc 可能会产生内存碎片，但 Redis 在设计上尽量减少这种影响。整数集合升级时，通常是在已有内存块的基础上进行扩展，而不是频繁地重新分配全新的大块内存。这有助于减少内存碎片的产生，提高内存的整体利用率。例如，当从 INTSET_ENC_INT16 升级到 INTSET_ENC_INT32 时，realloc 尝试在原内存块的基础上增加所需的内存空间，而不是完全重新分配一个新的大内存块。

2. 数据操作性能方面

   • 与其他数据结构的协同：在 Redis 中，整数集合常用于 set 数据结构的底层实现之一。当 set 元素满足整数集合的条件时，使用整数集合存储。升级后的整数集合在与 set 的其他操作（如交集、并集、差集运算）协同工作时，由于其有序性和合理的内存布局，能提高这些操作的效率。例如，计算两个有序整数集合的交集时，可以利用它们的有序性，通过双指针法高效地找到共同元素，升级后的内存布局可能更利于这种算法的执行，减少内存访问次数。
   • 多线程环境下的性能：在 Redis 多线程模型中，虽然主线程主要负责处理命令，但后台线程可能会涉及到内存管理等操作。整数集合升级过程中的内存分配和元素转换操作，在多线程环境下需要考虑线程安全。Redis 通过合理的锁机制或无锁数据结构设计，确保在多线程环境下整数集合升级不会影响整体性能。例如，在后台线程进行内存分配和元素转换时，使用互斥锁保护共享资源，避免数据竞争，保证操作的原子性，从而不影响主线程对其他命令的处理效率。

实际应用场景中的性能体现

1. 统计计数场景

   • 网站访问量统计：假设要统计网站每天的独立访客数量，每个访客的标识可以用整数表示。在初始阶段，访客数量较少，整数集合采用 INTSET_ENC_INT16 编码即可存储所有访客标识。随着访客数量的增加，当有访客标识超出 int16_t 范围时，整数集合升级。这种升级机制在保证准确统计的同时，有效地利用了内存。相比一开始就使用大尺寸数据类型存储所有标识，节省了内存空间。而且，在查询某个访客是否已访问过网站时，由于整数集合的有序性，通过二分查找可以快速确定，提高了查询效率。
   • 商品销量统计：对于电商平台的商品销量统计，每个商品的销量用整数表示。在商品销售初期，销量可能较小，整数集合采用较小的编码方式存储销量数据。随着商品销量的增长，整数集合升级。在分析销量排行榜等场景下，整数集合的有序性使得排名计算变得高效，升级后的内存布局可能进一步优化计算过程，提高性能。

2. 游戏排行榜场景 在游戏中，玩家的积分、等级等数据常用整数表示。游戏服务器可以使用 Redis 的整数集合来存储玩家的排名信息。初始阶段，玩家数量较少且积分范围较小时，采用 INTSET_ENC_INT16 编码。随着玩家数量增多和积分范围扩大，整数集合升级。在查询玩家排名或更新玩家积分时，利用整数集合的有序性和升级带来的性能优化，能够快速完成操作。例如，当一个玩家的积分更新后，需要重新确定其在排行榜中的位置。由于整数集合的有序性，可以快速找到插入或更新的位置，升级后的内存布局可能减少内存访问次数，提高更新效率。

与其他数据结构性能对比

1. 与普通数组对比

   • 内存使用：普通数组在存储整数时，通常需要预先确定数组的大小和元素类型。如果一开始选择较大的元素类型（如 int64_t），即使大部分元素可以用较小类型表示，也会浪费大量内存。而 Redis 的整数集合通过动态升级机制，根据元素实际情况选择合适的编码方式，在内存使用上更加灵活高效。例如，存储 100 个 int16_t 类型的整数，普通数组若选择 int64_t 类型存储，会占用 8 * 100 = 800 字节；而整数集合采用 INTSET_ENC_INT16 编码，只占用 2 * 100 = 200 字节。当有元素超出 int16_t 范围时，整数集合升级，虽然内存占用会增加，但相比普通数组一开始就使用大类型存储，仍然可能更节省内存。
   • 查找效率：普通数组进行查找操作通常需要遍历整个数组，时间复杂度为 $O(n)$。而整数集合由于有序，可以使用二分查找，时间复杂度为 $O(\log n)$。在元素数量较多时，整数集合的查找效率优势明显。例如，在包含 1000 个元素的集合中查找一个元素，普通数组平均需要比较 500 次，而整数集合最多只需比较约 10 次（$\log_2{1000} \approx 10$）。

2. 与哈希表对比

   • 唯一性和有序性：哈希表可以快速判断元素是否存在，时间复杂度接近 $O(1)$，但它不保证元素的有序性，且在实现唯一性时可能需要额外的处理。而整数集合天然保证元素的唯一性和有序性，在需要有序数据的场景下具有优势。例如，在实现一个有序的用户 ID 集合时，哈希表无法直接提供有序性，若要实现有序，需要额外的排序操作。而整数集合在添加元素时自动维护有序性，在查询排名等场景下更方便。
   • 内存使用：哈希表通常需要更多的内存来存储哈希桶、指针等额外信息。对于整数集合，当元素数量较少且可以用较小编码方式存储时，内存占用相对较小。例如，存储 10 个整数，哈希表可能因为哈希桶的分配和指针等开销，占用比整数集合更多的内存。但当元素数量非常大且分布均匀时，哈希表的查找优势更加明显，整数集合的有序性维护可能会带来一定的性能开销。

整数集合升级的潜在问题及优化

1. 潜在问题

   • 升级开销：整数集合升级过程涉及内存重新分配和元素类型转换，这会带来一定的性能开销。在高并发场景下，频繁的升级操作可能会影响 Redis 的整体性能。例如，在一个实时统计系统中，短时间内大量新数据涌入，导致整数集合频繁升级，可能会使系统响应时间变长。
   • 内存抖动：虽然 Redis 尽量控制内存碎片，但升级过程中的动态内存分配和释放可能会导致内存抖动。如果在短时间内整数集合频繁升级和降级（虽然 Redis 目前没有降级机制，但假设存在类似场景），会频繁地申请和释放内存，使内存分配器的性能下降，影响系统整体性能。

2. 优化措施

   • 批量操作优化：对于可能导致升级的操作，可以采用批量处理的方式。例如，在向整数集合添加多个元素时，先检查所有要添加的元素，确定是否需要升级，然后一次性进行升级和元素添加操作，减少升级次数。在实时统计系统中，可以设置一个缓冲区，收集一定数量的新数据后，统一进行添加操作，避免单个元素添加导致的频繁升级。
   • 预分配策略：在某些场景下，可以根据业务预估，提前进行一定程度的内存预分配。例如，在已知业务数据会逐渐增长且可能超出当前编码范围时，可以提前分配较大的内存空间，减少后续升级时的内存重新分配次数。但这种策略需要对业务数据有较为准确的预估，否则可能会造成内存浪费。

通过深入了解 Redis 整数集合的升级机制及其带来的性能提升，我们可以更好地在实际应用中利用这一数据结构，优化系统性能，提高内存使用效率。无论是在统计计数、排行榜等场景，还是与其他数据结构对比时，整数集合的升级机制都展现出独特的优势，同时我们也需要关注其潜在问题并采取相应的优化措施。