NoSql之Redis整数集合(intset)源码探究

1 为什么需要intset

动态字符串，双端链表，字典，跳跃表等，这些数据结构都非常强大实用，但是在内存消耗方面也非常“巨大”。
Redis的数据都是存放在内存上面的，所以对内存的使用要求及其苛刻，Redis会想方设法的来节省内存。
假设有一组集合1,2,3,6,5，如果采用上述的数据结构来存储的话，必然会付出昂贵的内存代价，因此，Redis在这种小数据量的条件下，会使用内存映射来代替内部数据结构。这就使得整数集合（intset）和压缩（ziplist）这两类节省内存的数据结构应运而生了。
Intset是集合键的底层实现之一，如果一个集合满足

• 只保存整数值元素
• 此集合的元素数量不多

这两个条件，那么Redis就会采用intset来保存这个数据集。intset的数据结构如下：

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

• 1

• encoding属性表示该整数集合的编码模式
• length属性记录了集合包含的元素数量,即contents数组的长度.
• contents数组是整数集合的底层实现:每个元素都是此数组的一个数组项(item),各个项在数组中按值的大小升序排列,且不包含重复项.

虽然contents被声明为int8_t类型的数组,但实际上数组并不保存int8_t类型的值,数组真正保存的类型取决于encoding属性的值:

• INTSET_ENC_INT16 (sizeof(int16_t))
  数据以int16_t类型存放，每个占2个字节，能存放-32768~32767范围内的整数
• INTSET_ENC_INT32 (sizeof(int32_t))
  数据以int32_t类型存放，每个占4个字节，能存放-2^32~2^32-1范围内的整数
• INTSET_ENC_INT64 (sizeof(int64_t))
  数据以int64_t类型存放，每个占8个字节，能存放-2^64~2^64-1范围内的整数

在读取和写入的时候，均按照指定的encoding编码模式读取和写入。

inset中最值得一提的就是升级操作。当intset中添加的整数超过当前编码类型的时候，intset会自定升级到能容纳该整数类型的编码模式，如1,2,3,4，创建该集合的时候，采用int16_t的类型存储，现在需要像集合中添加一个整数40000，超出了当前集合能存放的最大范围，这个时候就需要对该整数集合进行升级操作，将encoding字段改成int32_6类型，并对contents字段内的数据进行重排列。
因为每次向整数集合添加新元素都可能会引起升级， 而每次升级都需要对底层数组中已有的所有元素进行类型转换， 所以向整数集合添加新元素的时间复杂度为 O(N) 。

2 源代码

Redis提供intsetUpgradeAndAdd函数来对整数集合进行升级然后添加数据.

/* 升级整数集合并添加元素. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 获取当前编码格式
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 获取需要升级到的编码格式
    uint8_t newenc = _intsetValueEncoding(value);
    // 获取原整数集中的整数个数
    int length = intrev32ifbe(is->length);
    // 由于待添加的元素一定是大于或者小于整数集中所有元素，故此处需要判断添加到新数据集的头部或者尾部
    // 如果value为正，则添加到新数据集的尾部；反之则添加到首部
    int prepend = value < 0 ? 1 : 0;
 
    /* 设定新的编码格式 */
    is->encoding = intrev32ifbe(newenc);
    // 对原数据集进行扩容
    is = intsetResize(is,intrev32ifbe(is->length)+1);
 
    /* 采用从后往前的重编码顺序进行升级，这样就能避免覆盖数据
 *将原数据集中的数据依次赋值到新数据集中
 *_intsetGetEncoded(is,length,curenc)获取数据集is的第length位上的数据，curenc为原数据集的编码格式
 *_intsetSet将数据集is的第length+prepend位上设定为上一函数返回的值
 *注意到prepend变量用于确保我们在intset的开头或结尾都有一个空闲空间
 */
    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;
}

• 1

/* 将value设定到整数集合is的第pos位.使用配置的编码方式 */
static void _intsetSet(intset *is, int pos, int64_t value) {
    // 获取整数集合is的编码格式
    uint32_t encoding = intrev32ifbe(is->encoding);
 
    // 针对不同的编码格式做相应的处理
    if (encoding == INTSET_ENC_INT64) {
        // 将对应的pos位设置成value
        ((int64_t*)is->contents)[pos] = value;
        // 如果必要，对新值进行大小端转换
        memrev64ifbe(((int64_t*)is->contents)+pos);
    } else if (encoding == INTSET_ENC_INT32) {
        ((int32_t*)is->contents)[pos] = value;
        memrev32ifbe(((int32_t*)is->contents)+pos);
    } else {
        ((int16_t*)is->contents)[pos] = value;
        memrev16ifbe(((int16_t*)is->contents)+pos);
    }
}

• 1

/* 获取整数集is中，按照enc编码格式的第pos位上的元素. */
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;
 
    // 针对不同的编码格式做相应的处理
    // (enc*)is->contents获取整数集中的数据部分
    // (enc*)is->contents+pos获取第pos位上的元素
    // memrevEncifbe(&vEnc)如有必要对拷贝出来的值进行大小端转换
    if (enc == INTSET_ENC_INT64) {
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
        memrev64ifbe(&v64);
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}

• 1

3 升级的好处

• 提升整数集合的灵活性
  因为 C 语言是静态类型语言， 为了避免类型错误， 我们通常不会将两种不同类型的值放在同一个数据结构里面。
  但是， 因为整数集合可以通过自动升级底层数组来适应新元素， 所以我们可以随意地将 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 类型的值添加到集合时， 程序才会对数组进行升级。

Redis不提供降级操作，所以一旦对数组进行了升级，编码就会一直保持升级后的状态。

4 常用API