Redis Set类型解析

Redis的Set是一个无序的、元素唯一的集合。它支持高效的添加、删除、判断元素是否存在等操作，以及多个集合之间的交集、并集、差集运算。其强大的能力源于其精巧的内部实现。

Redis Set的底层实现主要使用了两种数据结构：

intset（整数集合）：当集合中的元素都是整数且元素数量较少时使用，以节省内存。
dict（字典，即哈希表）：这是Set的默认和主力实现，可以存储任意类型的值。

这种根据条件选择不同底层结构的机制称为编码（Encoding）。Set类型的编码可以通过 OBJECT ENCODING your_set_key 命令查看。

核心源码文件

Set的实现主要涉及以下文件：

src/t_set.c：Set类型的所有命令的实现，如 SADD, SISMEMBER, SINTER 等。
src/intset.c 和 src/intset.h：整数集合 (intset) 的实现。
src/dict.c 和 src/dict.h：字典 (dict) 的实现（与Hash类型共用）。

底层实现之一：intset (整数集合)

设计目标

为了在特定场景下（元素全是整数且数量少）极致地节省内存。intset 是一块连续的内存空间，类似于一个数组。

数据结构定义 (来自 `intset.h`)

typedef struct intset {
    uint32_t encoding; // 编码方式：决定数组元素的类型
    uint32_t length;   // 集合包含的元素数量
    int8_t contents[]; // 柔性数组，保存实际的值。元素按值的大小升序排列
} intset;

encoding 的值可以是：

INTSET_ENC_INT16：contents 是 int16_t 类型的数组。
INTSET_ENC_INT32：contents 是 int32_t 类型的数组。
INTSET_ENC_INT64：contents 是 int64_t 类型的数组。

关键特性

升级 (Upgrade)：这是 intset 最核心的特性。
- 何时升级？ 当新添加的元素无法用当前编码（整数类型）表示时。例如，当前是 INTSET_ENC_INT16（范围 -32768~32767），但要添加一个 40000（需要 int32_t）。
- 如何升级？ (源码在 intset.c/intsetUpgradeAndAdd)
  - 根据新元素的类型，重新分配 intset 的内存空间。
  - 将原有元素从后向前依次转换为新的数据类型，并放入正确的位置。从后向前可以避免覆盖尚未转换的元素。
  - 修改 encoding 属性，并添加新元素。
- 好处：灵活性高且节省内存。需要存小整数时就用小类型，只有必要时才升级，避免了从一开始就使用最大的 int64_t。
有序性：contents 数组中的元素是按照值的大小升序排列的。
- 好处：这使得 intset 的查找操作 (intsetFind) 可以使用二分查找，时间复杂度为 O(log N)。虽然不如哈希表的 O(1)，但在元素数量少时，效率依然很高。
- 插入过程：先通过二分查找找到待插入的位置，然后移动后续元素，空出位置后再插入，以维持有序性。

底层实现之二：dict (字典/哈希表)

当Set无法满足 intset 的条件时，就会转换为 dict。转换发生在以下情况（源码见 t_set.c）：

尝试向一个 intset 编码的Set添加一个非整数（比如字符串）。
尝试向一个 intset 编码的Set添加一个整数，但此时元素数量超过了配置的阈值 set-max-intset-entries (默认 512)。

dict 是一个标准的哈希表（与Hash类型使用的结构完全相同）。在Set中使用时：

key：是集合的元素本身。
value：是一个空指针（NULL）。

为什么用哈希表？
哈希表提供了平均 O(1) 时间复杂度的查找、插入和删除操作，非常高效。虽然它比 intset 耗内存，但在存储大量或非整数数据时，这是性能与空间的最佳权衡。

编码转换 (Encoding Conversion)

Set会根据条件在两种编码间自动转换。转换是单向的，通常是从节省内存的 intset 转换为功能更强大的 dict。

转换过程的逻辑主要在 t_set.c/setTypeAdd 函数中（这是 SADD 命令的底层实现）：

// (伪代码，简化逻辑)
int setTypeAdd(robj *subject, sds value) {
    if (subject->encoding == OBJ_ENCODING_INTSET) {
        if (value_is_an_integer) {
            // 尝试添加到 intset
            intset_is = subject->ptr;
            if (intsetAdd(intset_is, value, &success)) {
                // 添加成功！
                subject->ptr = intset_is; // 更新指针（因为intsetAdd可能重新分配内存）
                return 1;
            }
        }
        // 如果执行到这里，说明：
        // 1. 要添加的不是整数，或
        // 2. 虽然是整数，但添加失败（极少见，如内存分配失败）
        // 那么需要将编码转换为 HT (dict)
        setTypeConvert(subject, OBJ_ENCODING_HT);
    }

    // 如果是 HT 编码，或者刚从上面转换过来
    if (subject->encoding == OBJ_ENCODING_HT) {
        // 调用 dictAdd 将元素作为 key 添加到哈希表中，value 设为 NULL
        return dictAdd(subject->ptr, value, NULL) == DICT_OK;
    }
}

setTypeConvert 函数负责具体的转换工作：

创建一个新的空字典。
遍历 intset 中的每一个整数元素。
将每个整数元素转换为 sds（简单动态字符串）类型（因为dict的key是sds）。
将这个 sds 作为 key，NULL 作为 value，插入到新字典中。
将原Redis对象的编码 encoding 改为 OBJ_ENCODING_HT，并将指针 ptr 指向新创建的字典。
释放原来的 intset 内存。

核心命令的实现分析

以几个典型命令为例：

`SADD` (添加元素)

根据 key 找到对应的集合对象。
调用上面提到的 setTypeAdd 函数。
setTypeAdd 会根据当前编码决定是操作 intset 还是 dict，并在必要时触发编码转换。

`SISMEMBER` (判断元素是否存在)

查找集合对象。
如果编码是 intset (OBJ_ENCODING_INTSET)：
- 先判断要查找的值是不是整数，如果不是，直接返回 0（不存在）。
- 如果是整数，则在 intset 上执行二分查找 (intsetFind)。
如果编码是 dict (OBJ_ENCODING_HT)：
- 直接调用 dictFind 在哈希表中查找这个 key。找到即存在。

`SINTER` (求交集)

这是比较复杂的命令，源码在 t_set.c/sinterGenericCommand。

排序：先对所有输入集合进行检查，并将其中元素数量最小的集合排在第一个。这是一种优化策略，可以减少后续比较的次数。
遍历最小集合：遍历这个最小集合中的每一个元素。
检查其他集合：对于最小集合中的每个元素，检查它是否也存在于所有其他集合中（使用 SISMEMBER 的逻辑）。
收集结果：如果该元素在所有集合中都存在，则将其放入结果集中。
返回最终的结果集。

注意：交集运算的过程是临时性的，会遍历所有涉及的集合，CPU开销与所有集合的大小乘积成正比，大集合求交集可能很慢。

`SUNION` (求并集) 和 `SDIFF` (求差集)

实现思路类似，但策略不同：

并集：通常使用一个字典作为临时结构，遍历所有集合，将所有元素去重后加入。
差集：以第一个集合为基准，遍历其中的元素，只保留那些不在后续任何集合中出现的元素。

内存管理与迭代

内存管理：无论是 intset 还是 dict，都负责管理其内部元素的内存。当使用 dict 时，元素（作为key）是使用 sds 来存储的。
迭代：Set提供了迭代器，可以安全地遍历集合中的所有元素。对于 intset，迭代就是顺序遍历数组；对于 dict，迭代需要遍历哈希桶，跳过空桶。

总结

Redis Set的实现体现了Redis在设计和性能优化上的核心思想：

空间与时间的权衡：根据数据的具体情况，智能地选择最合适的底层数据结构。intset 用CPU换空间（二分查找），dict 用空间换时间（O(1)操作）。
平滑升级：intset 的升级机制使得小集合可以极度节省内存，而在集合变大或类型不适时，又能无缝切换到性能更高的结构。
算法优化：在实现集合运算时，通过先排序最小集合等策略，尽可能地优化最坏情况下的性能。
抽象层：t_set.c 中的函数（如 setTypeAdd, setTypeIsMember) 提供了一个抽象层，上层命令无需关心底层的编码细节，使得代码更加清晰和可维护。