文章目录

• 前言
• 一、整数集合？
• • 1. 背景
  • 2. 应用
• 二、原理分析
• • 1. 基本使用
  • 2. 数据存储
  • • 2.1 升级
    • 2.2 为何不降级？
  • 3. 效率
  • • 3.1 时间复杂度：
    • 3.2 节省空间？
• 三、源码分析
• • 1. 数据结构
  • 2. 常用API
  • 3. 基本操作
  • • 3.1 查询元素
    • 3.2 添加元素
    • 3.3 删除元素
• 总结

前言

整数集合（intset）是一个有序的、存储整型数据的结构。我们知道 redis 是一个内存数据库，所以必须考虑如何能够高效地利用内存。

当 redis 集合类型的元素都是整数并且都处在64位有符号整数范围之内时，使用该结构体存储。

一、整数集合？

1. 背景

本质上和我们之前聊到的 ziplist, quicklist, listpack 类似，都是为了 节省内存 而生；

不同的是 intset 实现上更为简单，没有复杂的编码算法（空间压缩），从名字上可以得到两个信息 int + set，即 整型 + set集合 用来保存整型数据的 set 集合。

到这里，你可能想到 redis 中 set 数据类型的实现；没错，在 set 底层的实现中，就有 intset 这种数据结构来存储整型数据。

我们知道，int 类型根据数据的大小可以划分为 int16、int32、int64 几种，分别占用 2个、4个、8个字节；

假设，我们现在有一个 set 集合的整型数据，数值都小于 65536，这个时候让你来选择底层存储，你会考虑使用哪种类型存储？按照最节省内存的方式，这些数值都可以用 int16 来存储；如果再新增一个元素 10000000，又该怎么存呢？

很显然，int16已经不够存储，这时候得换做 int32 来存储，那之前用 int16 存储的数据需要改类型吗？在 redis 的 intset 结构中，答案为 要改变。

为什么要改变？直接用 int16 和 int32 分别存储（也就是在一个 intset 支持多种 int）不是更加节省内存吗？来，带着疑问一起接着往下看 ～

2. 应用

intset 这种结构在 redis 的应用主要用于支持 set 集合的底层实现之一，并且仅限于整型元素，也就是说当 set 集合出现了一个字符串元素时，其底层结构将改变为 hashtable。

总的来说，intset 需要满足一定条件才会应用于 set 集合底层实现：

• 元素都是整形
• 集合长度需要小于指定长度

set 集合的底层实现使用了 hashtable 和 intset 两种数据结构，当然，不会同时使用，在一定条件下会发生切换：

• 一种情况为当元素个数超过一定数量之后（默认值为512），即使元素类型仍然是整型，也会将编码转换为 hashtable，该值由如下配置项决定：set-max-intset-entries 512
• 另一种情况为当增加非整型变量时，例如在集合中增加元素 ’a’ 后，set 的底层编码从 intset 转换为 hashtable：

二、原理分析

1. 基本使用

前面已经提到，intset 作为 set 集合的底层数据结构，注意，是底层数据结构；而只有 set、list 这样的数据类型才有具体的使用意义。

因此，谈到 intset 的基本使用，我们且看它在底层如何扮演角色。

在客户端输入如下命令并查看其编码：

127.0.0.1:6379> sadd testSet 1 2 3 4 5
(integer) 1
127.0.0.1:6379> object encoding testSet
"intset"

可以看到，此时 set 底层数据结构采用的是 intset。当我们往里面添加一个字符串，来看看变化：

127.0.0.1:6379> sadd testSet hello
(integer) 1
127.0.0.1:6379> object encoding testSet
"hashtable"

此时，底层采用 hashtable 结构，与咱们上面聊的编码切换条件对应上。

2. 数据存储

intset 是 redis 用于保存整数值的集合抽象数据结，它可以保存 int16_t、int32_t 、int64_t 类型的整型数据，并且可以保证集合中不会出现重复数据。每个整数集合使用一个 intset 类型的数据结构表示。intset结构体如下：

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

其中，encoding 表示编码，有 int16_t、int32_t 、int64_t 三种取值；length 表示 intset 集合的元素个数；contents 则存储具体的数据。

2.1 升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行：

• 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
• 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
• 将新元素添加到底层数组里面

升级有哪些好处？

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。

提升灵活性

因为C语言是静态类型语言，为了避免类型错误，我们通常不会将两种不同类型的值放在同一个数据结构里面。

例如，我们一般只使用 int16_t 类型的数组来保存 int16_t 类型的值，只使用 int32_t 类型的数组来保存 int32_t 类型的值，诸如此类。

但是，因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将 int16_t、int32_t 或者 int64_t 类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活

节约内存

当然，要让一个数组可以同时保存 int16_t、int32_t、int64_t 三种类型的值，最简单的做法就是直接使用 int64_t 类型的数组作为整数集合的底层实现。

不过，这样一来，即使添加到整数集合里面的都是 int16_t 类型或者 int32_t 类型的值，数组都需要使用 int64_t 类型的空间去保存它们，从而出现浪费内存的情况。

而整数集合现在的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

例如，如果我们一直只向整数集合添加 int16_t 类型的值，那么整数集合的底层实现就会一直是 int16_t 类型的数组，只有在我们要将 int32_t 类型或者 int64_t 类型的值添加到集合时，程序才会对数组进行升级。

2.2 为何不降级？

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。为何不支持降级操作？

笔者查了很多资料，都并未明确说出原因。按笔者开始的想法，能升则能降；升级，就是将每个元素变大一些，那降级自然就是将每个元素变小一些；

比如，当前集合为 int64, 删除一个元素后，所有元素都小于 int64，那么就可以将所有元素降级为 int32。

这里有一个 “关键” 问题，如何判断当前集合所有元素小于 int64？对于插入元素来说，我们可以很好的判断是否需要升级，因此从 intset 结构里就能拿到当前的 encoding，也就自然能判断了；

别忘了，我们维护的 intset 集合是一个有序集合，最后一个元素就是 intset 最大的，所以，也很容易判断当前最合适的 int 长度；那，为什么不降级呢？

笔者看了下源码，发现一个细节，当新增元素时，都会使用系统函数 zrealloc 重新分配内存空间；而删除元素时，并不会使用，仅仅将后面的元素依次往前挪动，覆盖删除的元素空间即可。

如果降级，必然意味着一次 zrealloc 调用，这算一次可观的消耗，不划算。升级怎么就可以了？ 因为插入本身就需要一次 zrealloc 调用重新分配空间，从这个角度来看，并没有额外消耗。

3. 效率

3.1 时间复杂度：

查询：inset 维护的是一个有序的整数集合，增删查等操作都会使用二分搜索定位目标位置，这过程的时间复杂度为 O(logN)。

插入：因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为 O(N)。

删除：指定元素被删除后，需要将其后的元素往前挪动，因此时间复杂度为 O(N)。

聊时间复杂度的优劣，需要放到对应的场景去评判；我们知道，intset 应用于 set 集合底层实现，同样，实现 set 集合的另一个底层结构是 hashtable，也叫做字典，就时间复杂度而言，intset 相比于 字典 能占到优势吗？

相信，大家都应该熟悉 哈希字典 这种结构，其 增删查 等操作的时间复杂度为 O(1)，因此，intset 就这一角度来看是没有任何优势的。也正是这样，intset 集合的长度需要做限制。

3.2 节省空间？

相比较用 字典 来存储，有什么优势？前面我们聊到，intset 就是为了节省内存而设计，因此，在内存这方面定然优于 字典。

字典，是 key - value 结构；而 set 集合实际上只使用了 key 这个字段，也就是说集合中的元素都通过 key 来存储，而 value 则为 null；

我们从 t_set.c 的源码片段来看看：

    dict *ht = subject->ptr;
    dictEntry *de = dictAddRaw(ht,value,NULL);
    if (de) {
        // key 以 sds 字符串存储
        dictSetKey(ht,de,sdsdup(value));
        // value 设置为 null 
        dictSetVal(ht,de,NULL);
        return 1;
    }

可以看到，实际处理上将元素转化为 sds 字符串存储；

比如，元素65535，如果用字符串存储的话需要5个字节，而按整型存储则只需2个字节即可，从这方面来看，将整型转化为字符串存储并不划算，而 intset 存储整型数据优势明显。

综上，通过时间和空间复杂度对比，可以看到，intset 相较于字典是一种时间换空间的结构。

三、源码分析

1. 数据结构

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

encoding：编码类型，决定每个元素占用几个字节

• int16_t：每个元素占 2 个字节。
• int32_t：每个元素占 4 个字节。
• int64_t：每个元素占 8 个字节

length：元素个数。即一个 intset 中包括多少个元素。

contents：存储具体元素。根据 encoding 字段决定多少个字节表示一个元素。

2. 常用API

// 创建集合，O(1)
intset *intsetNew(void); 
// 添加元素，O(N)
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
// 移除给定元素，O(N)
intset *intsetRemove(intset *is, int64_t value, int *success);
// 查询给定元素，O(logN)
uint8_t intsetFind(intset *is, int64_t value);
// 从整数集合中随机返回一个元素，O(1)
int64_t intsetRandom(intset *is);
// 取出底层数组在给定索引上的元素，O(1)
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
// 返回集合中元素个数，O(1)
uint32_t intsetLen(const intset *is);
// 返回集合占用的内存字节数，O(1)
size_t intsetBlobLen(intset *is);

3. 基本操作

3.1 查询元素

1）intsetFind：

uint8_t intsetFind(intset *is, int64_t value) {
    // 查询元素 value 的编码，即长度
    uint8_t valenc = _intsetValueEncoding(value);
    // 具体搜索交给 intsetSearch 处理
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

2）intsetSearch：

因为 intset 是一个有序集合，因此，内部搜索算法使用的二分法搜索，时间复杂度 O(logN)。

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 {
        // 先检查最大和最小的元素，如果 value 大于最大或者小于最小元素，则肯定不在集合中
        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 = ((unsigned int)min + (unsigned int)max) >> 1;
        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;
    }
}

参数 pos 作为引用返回，如果找到，则返回元素在 intset 集合中的位置下标；反之，没有找到的话，返回可以插入此 value 的位置下标。

3.2 添加元素

1）intsetAdd：

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

    if (valenc > intrev32ifbe(is->encoding)) {
        // 插入 value 长度大于当前集合 encoding 长度，需要整体升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 先二分找到插入位置，pos 引用返回下标
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        // 因为新增了元素，所以需要重新分配一块空间
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 如果插入位置在中间，要先把空间腾出来，也就是从pos之后元素往后挪一个
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    // 将 pos 位置赋值为 value
    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

可以看到，如果不需要升级，该方法即可完成插入操作；

2）intsetUpgradeAndAdd：

如果插入 value 长度大于当前 intset 的长度，需要先进行整体升级

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    // 判断正负数
    int prepend = value < 0 ? 1 : 0;

    is->encoding = intrev32ifbe(newenc);
    // 重新分配空间
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    // 挪动并升级原来集合中的元素
    // 注意，是从最后一个位置开始挪动，否则可能导致元素覆盖
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

   // 在集合第一个位置插入（负数） 
    if (prepend)
        _intsetSet(is,0,value);
    else // 在集合的末尾插入（正数）
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

如果待插入元素小于0，说明需要插入 intset 的头部；如果待插入元素大于0，需要插入 intset 的尾部。

既然执行了扩容，说明待插入元素不是最大值就是最小值。

3.3 删除元素

1）intsetRemove：

intset *intsetRemove(intset *is, int64_t value, int *success) {
    // 获取待删除元素编码
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
    
    // 待删除元素编码必须小于intset编码，并且该元素存在才会执行删除操作
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);

        /* We know we can delete */
        if (success) *success = 1;

        // 如果删除元素位于intset中间，则通过intsetMoveTail覆盖掉该元素空间
        // 如果位于intset末尾，则intset收缩内存后直接将其丢弃
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

可以看到，如果删除元素位于集合中间，则通过 intsetMoveTail 移动待删除元素之后的元素，覆盖待删除元素内存空间即可。

移动之后，将集合空间进行缩容处理。

2）intsetMoveTail：
将尾部的一些元素往前挪动，覆盖删除的元素空间。

static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    uint32_t bytes = intrev32ifbe(is->length)-from;
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }
    memmove(dst,src,bytes);
}

总结

intset 用于 Redis 中集合类型的数据结构。intset 存储整型数据，并且是少量集合元素，就是一种特定场景下的专用数据结构。元素有序，并且不重复。

• 整数集合是集合键的底层实现之一。
• 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
• 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
• 整数集合只支持升级操作，不支持降级操作。

综上：intset 作用对象是 整数集合 & 小量元素集合，其最大的特点是节省内存空间。