Redis数据结构-IntSet

在《Reids数据结构》这篇文章中，我们说到了Redis中的Set数据类型底层是使用的intset或者hashtable数据结构，本文简单说下intset，关于hashtable可以看看这篇文章：《Redis数据结构-HashTable》。

Redis在什么时候使用intset呢？

简单说如果Set中的元素都是整数类型且元素个数小于等于配置项set-max-intset-entries，那就用intset，反之hashtable。

下面我们将set-max-intset-entries修改为3方便测试：

127.0.0.1:6379> config set set-max-intset-entries 3
OK
127.0.0.1:6379> SADD k1 1 2 3
(integer) 3
127.0.0.1:6379> OBJECT ENCODING k1
"intset"
127.0.0.1:6379> SADD intset 4
(integer) 1
127.0.0.1:6379> OBJECT ENCODING intset
"hashtable"

可以看到当k1的元素个数超过3之后，编码方式从intset变为了hashtable。

同理集合中包含非整数元素也会使用hashtable：

127.0.0.1:6379> config set set-max-intset-entries 3
OK
127.0.0.1:6379> SADD k2 1 2 a
(integer) 3
127.0.0.1:6379> OBJECT ENCODING k2
"hashtable"

结构设计

在源码intset.h第35行可以看到intset的结构是这样的：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
  1. encoding：编码方式，共支持三种范围：
    1. INTSET_ENC_INT16：占用2个字节，存储范围为[-2^16^,2^16^-1]。
    2. INTSET_ENC_INT32：占用4个字节，存储范围为[-2^32^,2^32^-1]。
    3. INTSET_ENC_INT64：占用8个字节，存储范围为[-2^64^,2^64^-1]。
  2. length：存储元素个数。
  3. contents[]：指向实际存储数值的连续内存区域（也就是一个数组），intset的每个元素都是contents[]数组的一个数组项，每个项在数组中升序排列，且数组中不包含任何重复项。（虽然这里将contents[]属性声明为int8_t类型的数组，但实际上contents[]数组并不保存任何int8_t类型的值，contents[]数组的真正类型取决于encoding属性的值）。

常用操作

intset的升级（扩容）

前面说到了contents[]的元素类型是由encoding来决定的，那么假设当前contents[]里的元素类型是int32（INTSET_ENC_INT32），然后插入一个新的数据，但是类型是int64（INTSET_ENC_INT64），会发生什么呢？

在源码intset.c第159行有个函数intsetUpgradeAndAdd，这个函数就是用来执行intset的升级的：

/* 升级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);
    /* 从后往前升级，这样就不会覆盖值。比如原本集合有1、2、3、4、5、6INTSET_ENC_INT16，新加入的65538则需要用INTSET_ENC_INT32。 
     * 注意：“prepend”变量用于确保intset的开头或结尾有一个空的位置。 */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    /* 将待添加的value添加到首部或者尾部, 因为是扩容所以value是大于原有最大值或小于最小值。 */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    /* 长度加1*/
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

如果在一个int32类型的intset中新增一个int64类型的值，那么整个intset里面的元素类型都会变成int64，这个过程主要分为三步：

  1. 根据新增的元素的类型，扩展contents[]的空间大小，并为新元素分配空间。
  2. 将contents[]当前的所有元素，都转换为和新增元素相同的类型，然后将类型转换后的元素放置到正确的位上，且在放置的过程中还要保证原本数组的有序性。
  3. 最后修改encoding以及length长度加1。

注意：intset升级后不会再次降级，这里主要是考虑到资源消耗问题，没有必要在降级。

添加

intset的添加元素操作的源码在intset.c第206行的*intsetAdd函数：

/* 在 intset 中插入一个整数 */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    /*获取合适的编码方式*/
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;
    /* 如果需要升级编码，则进行升级。
     * 如果我们需要升级，我们知道这个值应该被追加（如果 > 0）或预置（如果 < 0）， 
     * 因为它在现有值的范围之外。 */
    if (valenc > intrev32ifbe(is->encoding)) {
        /* 这里执行intset的升级以及添加 */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* 如果集合中已经存在值，则中止。使用了二分查询。
         * 这个调用将使用正确的位置填充“pos”，以便在找不到值时插入值。*/
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        /*调整集合大小*/
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    /* 真正执行写入集合的函数 */
    _intsetSet(is,pos,value);
    /* 长度加1*/
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

删除

删除操作的源码在intset.c第236行的intsetRemove函数中：

/* 从intset中删除整数 */
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
    /* 当给定值处于当前集合的编码范围且存在集合当中 */
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);
        /* 可以删除 */
        if (success) *success = 1;
        /* 用尾部覆盖值并更新长度 */
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);
        /*长度减1*/
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

查找

一般查找操作（比如返回一个元素）、判断是否存在、查找位置的操作都是调用intset.c第56行的函数_intsetGetEncoded：

/* 返回给定编码的位置pos的值 */
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;
    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;
    }
}

创建一个intset

要创建一个intset，调用的是intset.c第98行中的*intsetNew函数：

/* 创建一个空的intset */
intset *intsetNew(void) {
    /* 分配内存 */
    intset *is = zmalloc(sizeof(intset));
    /* 默认编码是INTSET_ENC_INT16 */
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    /* 长度初始为0 */
    is->length = 0;
    return is;
}