Redis 整数集合 API 的功能详解

Redis 整数集合简介

Redis 中的整数集合（intset）是一种紧凑的数据结构，用于存储整数。它主要被用作集合键的底层实现之一，当一个集合只包含整数值元素，并且元素数量不多时，Redis 就会使用整数集合作为该集合键的底层实现。

整数集合的设计目的是为了在节省内存的同时，能够高效地进行一些集合操作。它的内部实现是一个有序的数组，并且根据集合中存储元素的类型不同，动态地调整数组中每个元素占用的空间大小。

整数集合的结构定义

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

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

encoding：表示整数集合的编码方式，它决定了 contents 数组中每个元素占用的字节数。Redis 支持三种编码方式：INTSET_ENC_INT16（每个元素占用 2 字节）、INTSET_ENC_INT32（每个元素占用 4 字节）和 INTSET_ENC_INT64（每个元素占用 8 字节）。
length：记录整数集合中当前包含的元素数量。
contents：这是一个柔性数组，实际存储整数集合中的元素。由于是柔性数组，其大小由整数集合实际包含的元素数量和编码方式决定。

整数集合的编码升级

整数集合的一个重要特性是它能够进行编码升级。当向整数集合中添加一个新元素，而当前编码方式无法容纳该元素时，整数集合会自动进行编码升级。

例如，假设当前整数集合使用 INTSET_ENC_INT16 编码，此时如果要添加一个大于 INT16_MAX 的整数，整数集合就会升级到 INTSET_ENC_INT32 编码。

编码升级的具体步骤如下：

分配新的内存空间：根据新的编码方式，计算出需要分配的新内存大小，然后为整数集合重新分配内存。新的内存大小要能够容纳原有的所有元素以及新添加的元素。
将原有的元素复制到新的内存空间：按照新的编码方式，将原 contents 数组中的元素逐个复制到新的内存空间中，并进行相应的类型转换。
添加新元素：将新元素添加到已复制好元素的新内存空间中。
更新编码方式和长度：将 encoding 更新为新的编码方式，并将 length 增加 1。

编码升级有一个重要的好处，就是它能够在不需要对现有元素进行重新排序的情况下，适应不同大小的整数存储需求，同时保持集合元素的有序性。

Redis 整数集合 API 详解

1. 创建整数集合

在 Redis 的源码实现中，并没有直接提供给用户创建整数集合的 API 函数，因为整数集合主要是作为集合键的底层实现，由 Redis 内部在合适的场景下自动创建和管理。不过，我们可以通过模拟 Redis 的底层逻辑来手动创建一个整数集合。以下是一个简单的 C 语言示例代码，展示如何手动创建一个整数集合：

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

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

intset* createIntset() {
    intset *is = (intset*)malloc(sizeof(intset) + sizeof(int16_t));
    if (is == NULL) {
        return NULL;
    }
    is->encoding = INTSET_ENC_INT16;
    is->length = 0;
    return is;
}

在上述代码中，createIntset 函数模拟了创建一个初始的整数集合。它首先为整数集合结构体分配内存，包括结构体本身以及第一个元素的空间（这里假设初始编码为 INTSET_ENC_INT16）。然后初始化编码方式和元素长度。

2. 添加元素

Redis 提供了 intsetAdd 函数用于向整数集合中添加元素。该函数的主要逻辑如下：

检查是否需要编码升级：如果新元素的类型超出了当前整数集合的编码范围，则进行编码升级。
检查元素是否已存在：遍历整数集合，检查要添加的元素是否已经存在。由于整数集合是有序的，所以可以使用二分查找来提高查找效率。如果元素已存在，则直接返回，不进行添加操作。
插入元素：如果元素不存在，则根据整数集合的有序性，找到合适的插入位置，将元素插入到 contents 数组中，并更新 length。

以下是简化的 intsetAdd 函数实现示例：

int intsetAdd(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (valenc > intrev32ifbe(is->encoding)) {
        // 编码升级
        return intsetUpgradeAndAdd(is, value);
    } else {
        // 使用二分查找元素位置
        if (intsetSearch(is, value, &pos)) {
            return 0; // 元素已存在
        }
        is = intsetResize(is, is->length + 1);
        if (pos < is->length) {
            memmove(is->contents + (pos + 1) * intrev32ifbe(is->encoding),
                    is->contents + pos * intrev32ifbe(is->encoding),
                    (is->length - pos) * intrev32ifbe(is->encoding));
        }
        _intsetSet(is, pos, value);
        is->length++;
        return 1;
    }
}

在这段代码中，_intsetValueEncoding 函数用于获取新元素的编码方式，intsetSearch 函数用于二分查找元素位置，intsetResize 函数用于调整整数集合的内存大小，_intsetSet 函数用于设置指定位置的元素值。

3. 删除元素

Redis 提供了 intsetRemove 函数用于从整数集合中删除元素。其主要步骤如下：

查找元素位置：使用二分查找确定要删除元素在 contents 数组中的位置。如果元素不存在，则直接返回。
删除元素：将元素从 contents 数组中移除，并将后面的元素向前移动填补空位。更新 length。
检查是否可以编码降级：在删除元素后，检查当前整数集合中的所有元素是否都可以用比当前编码方式更紧凑的编码来表示。如果可以，则进行编码降级。

以下是简化的 intsetRemove 函数实现示例：

int intsetRemove(intset *is, int64_t value, int *success) {
    uint32_t pos;
    if (!intsetSearch(is, value, &pos)) {
        if (success) *success = 0;
        return 0;
    }
    is->length--;
    if (pos < is->length) {
        memmove(is->contents + pos * intrev32ifbe(is->encoding),
                is->contents + (pos + 1) * intrev32ifbe(is->encoding),
                (is->length - pos) * intrev32ifbe(is->encoding));
    }
    is = intsetResize(is, is->length * intrev32ifbe(is->encoding));
    // 检查编码降级
    if (success) *success = 1;
    return 1;
}

在上述代码中，首先通过 intsetSearch 查找元素位置，如果找到则进行删除操作，然后调整整数集合的内存大小。最后可以在适当的位置添加检查编码降级的逻辑（这里未完整实现编码降级部分）。

4. 查找元素

Redis 提供了 intsetSearch 函数用于在整数集合中查找元素。由于整数集合是有序的，所以使用二分查找算法可以高效地进行查找。

以下是 intsetSearch 函数的简化实现：

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 {
            if (pos) *pos = mid;
            return 1;
        }
    }
    if (pos) *pos = min;
    return 0;
}

在这段代码中，通过二分查找的方式，不断缩小查找范围，直到找到目标元素或者确定元素不存在。如果找到元素，则返回 1，并通过 pos 参数返回元素的位置；如果未找到，则返回 0，并通过 pos 参数返回应该插入的位置。

5. 获取元素数量

通过访问整数集合结构体中的 length 字段，可以获取整数集合中当前包含的元素数量。在 Redis 的源码中，没有单独提供获取元素数量的函数，因为直接访问该字段就可以满足需求。以下是在 C 语言中获取整数集合元素数量的示例：

uint32_t getIntsetLength(intset *is) {
    return is->length;
}

6. 获取指定位置的元素

Redis 提供了 _intsetGet 宏来获取整数集合中指定位置的元素。它根据整数集合的编码方式，从 contents 数组中正确地提取出元素值。

以下是 _intsetGet 宏的定义：

#define _intsetGet(is,pos) ({\
    assert((pos) < intrev32ifbe((is)->length));\
    switch(intrev32ifbe((is)->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));\
    }})

在使用时，可以像下面这样获取指定位置的元素：

int64_t element = _intsetGet(is, 2);

这里 is 是整数集合指针，2 表示要获取的元素位置。

整数集合 API 的应用场景

集合键的底层实现：如前所述，当 Redis 的集合键只包含整数值元素且元素数量不多时，整数集合作为底层实现可以节省大量内存。例如，在一些统计用户 ID 集合、商品 ID 集合等场景中，如果这些 ID 都是整数类型且数量有限，Redis 会自动使用整数集合来存储，提高存储效率。
有序整数集合操作：由于整数集合内部是有序的，它可以方便地用于一些需要有序整数集合的场景。比如，在排行榜系统中，如果只记录整数类型的分数，并且不需要复杂的排序逻辑（因为整数集合本身就是有序的），可以利用整数集合的 API 进行高效的添加、删除和查询操作。

整数集合 API 的性能分析

添加操作：平均情况下，添加元素的时间复杂度为 O(logN)，因为在查找元素是否存在时使用了二分查找。如果需要进行编码升级，由于需要重新分配内存和复制元素，时间复杂度会增加到 O(N)，但这种情况相对较少发生。
删除操作：删除元素的时间复杂度也是 O(logN)，主要是查找元素位置的时间开销。在删除元素后如果需要移动元素，时间复杂度为 O(N)，但这只在删除中间位置元素时会发生，删除末尾元素时时间复杂度仍为 O(logN)。如果需要进行编码降级，时间复杂度会增加到 O(N)，同样这种情况相对较少。
查找操作：查找元素的时间复杂度为 O(logN)，因为使用了二分查找算法，这使得在整数集合中查找元素非常高效。

总结

Redis 的整数集合 API 提供了一套高效且内存友好的操作方式，用于处理整数集合数据。通过动态的编码调整、有序的存储结构以及优化的查找和插入算法，整数集合在许多场景下都能发挥出色的性能。无论是作为 Redis 集合键的底层实现，还是在自定义的整数集合应用中，理解和掌握这些 API 的功能和实现原理，都有助于开发出高效、稳定的应用程序。同时，通过对其性能的分析，可以更好地在实际应用中根据需求进行优化和调整。