Redis源码剖析和注释（五）--- 整数集合(intset)

https://blog.****.net/men_wen/article/details/70145752

Redis 整数集合(intset)

介绍
整数集合（intset）是集合键底层实现之一。集合键另一实现是值为空的散列表（hash table），虽然使用散列表对集合的加入删除元素，判断元素是否存在等等操作时间复杂度为O(1)，但是当存储的元素是整型且元素数目较少时，如果使用散列表存储，就会比较浪费内存，因此整数集合（intset）类型因为节约内存就存在。

散列表的实现

在redis集合键命令：redis集合键命令详解

127.0.0.1:6379> SADD set1 1 2 3
(integer) 3
127.0.0.1:6379> SADD set1 1
(integer) 0
127.0.0.1:6379> SMEMBERS set1
1) "1"
2) "2"
3) "3"
127.0.0.1:6379> SISMEMBER set1 2
(integer) 1
127.0.0.1:6379> SREM set1 1
(integer) 1
127.0.0.1:6379> SMEMBERS set1
1) "2"
2) "3"

整数集合结构的实现
redis根目录下的intset.h文件

typedef struct intset {
    uint32_t encoding;  //编码格式，有如下三种格式，初始值默认为INTSET_ENC_INT16
    uint32_t length;    //集合元素数量
    int8_t contents[];  //保存元素的数组，元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小，并且数组中的元素从小到大排列。
} intset;               //整数集合结构

#define INTSET_ENC_INT16 (sizeof(int16_t))   //16位，2个字节，表示范围-32,768~32,767
#define INTSET_ENC_INT32 (sizeof(int32_t))   //32位，4个字节，表示范围-2,147,483,648~2,147,483,647
#define INTSET_ENC_INT64 (sizeof(int64_t))   //64位，8个字节，表示范围-9,223,372,036,854,775,808~9,223,372,036,854,775,807

升级
intset整数集合之所以有三种表示编码格式的宏定义，是因为根据存储的元素数值大小，能够选取一个最”合适”的类型存储，”合适”可以理解为：既能够表示元素的大小，又可以节省空间。

因此，当新添加的元素，例如：65535，超过当前集合编码格式所能表示的范围，就要进行升级操作。

我们使用刚才命令中的集合，它在结构如下图：

Redis源码剖析和注释（五）--- 整数集合(intset)

我们根据代码和图一起理解升级的过程。

3.1获得新元素的编码格式
当前新元素要插入到集合中时，首先就要判获得新元素的编码格式，所以调用_intsetValueEncoding()来返回一个”适合”该元素的编码格式。65535的最”适合”的编码格式是INTSET_ENC_INT32。

/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) {    //返回合适v的编码方式
    if (v < INT32_MIN || v > INT32_MAX)             //如果超出32位所能表示数值的范围则返回INTSET_ENC_INT64
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)        //如果超出16位所能表示数值的范围则返回INTSET_ENC_INT32
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;                    //否则返回用16位表示的INTSET_ENC_INT16
}

3.2 调整内存空间
当得到新元素的编码格式后，就要将集合中所有元素的编码格式都要变成升级后的编码格式，因此，需要调整集合数组contents的内存空间大小，调用intsetResize()函数。

/* Resize the intset */
static intset *intsetResize(intset *is, uint32_t len) { //调整集合的内存空间大小
    uint32_t size = len*intrev32ifbe(is->encoding);     //计算数组的大小
    is = zrealloc(is,sizeof(intset)+size);  
    //分配空间，如果新空间的大小比原来的空间大，那么数组的元素会被保留
    return is;
}

intrev32ifbe()是一个宏定义，定义和实现在redis根目录下的endianconv.h和endianconv.c中根据主机字节序用来做整数大小端的转换。
已经获知65535的编码格式，因此调整内存空间的大小等于编码格式的大小乘以集合元素的个数。如果图：
Redis源码剖析和注释（五）--- 整数集合(intset)

注意：encoding成员已经发生变化，但是length并没有更新。

3.3 根据编码格式设置对应的值
调整好内存空间后就根据编码格式来设置集合元素的值和最后将新元素添加到集合中，都调用_intsetSet()函数。

/* Set the value at pos, using the configured encoding. */
//根据集合is设置的编码方式，设置下标为pos的值为value
static void _intsetSet(intset *is, int pos, int64_t value) {    
    uint32_t encoding = intrev32ifbe(is->encoding); //获取集合设置的编码方式

    if (encoding == INTSET_ENC_INT64) {             //如果是64位
        ((int64_t*)is->contents)[pos] = value;      //设置下标pos的值为value
        memrev64ifbe(((int64_t*)is->contents)+pos); //如果需要转换大小端
    } else if (encoding == INTSET_ENC_INT32) {      //如果是32位
        ((int32_t*)is->contents)[pos] = value;      //设置下标pos的值为value
        memrev32ifbe(((int32_t*)is->contents)+pos); //如果需要转换大小端
    } else {
        ((int16_t*)is->contents)[pos] = value;      //设置下标pos的值为value
        memrev16ifbe(((int16_t*)is->contents)+pos); //如果需要转换大小端
    }
}

memrev16ifbe()是一个宏定义，定义和实现在redis根目录下的endianconv.h和endianconv.c中根据主机字节序用来做内存大小端的转换。
将集合中原来的元素和新插入的元素以”合适”的编码格式INTSET_ENC_INT32写到数组中，顺序过程如下图：
Redis源码剖析和注释（五）--- 整数集合(intset)

最后要更新length。

3.4 升级实现源码

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { //根据value的编码方式，对整数集合is的编码格式升级
    uint8_t curenc = intrev32ifbe(is->encoding);    //当前集合的编码方式
    uint8_t newenc = _intsetValueEncoding(value);   //得到value合适的编码方式
    int length = intrev32ifbe(is->length);          //集合元素数量
    int prepend = value < 0 ? 1 : 0;                //如果value小于0，则要将value添加到数组最前端，因此为移动1个编码长度
    //集合的编码格式要升级，也就是内存增大
    //因为 value 的编码比集合原有的其他元素的编码都要大，所以value如果是负数，就是最小值，如果是正数则是最大值
    //索引value要么放在数组集合的最前端，要么最后端，根据prepend判断

    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);    //更新集合is的编码方式
    is = intsetResize(is,intrev32ifbe(is->length)+1);   //根据新的编码方式重新设置内存空间大小

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    //_intsetGetEncoded()得到下标为length的值
    //_intsetSet设置下标为prepend+length的值为_intsetGetEncoded返回的值
    //但是，编码格式已经发生改变，数组元素没变但是内存大小改变
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    if (prepend)    //value是负数，要放在最前端
        _intsetSet(is,0,value); //设置下标为0的值为value
    else
        _intsetSet(is,intrev32ifbe(is->length),value);  //value为正数，设置最末尾+1的值为value
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);  //数组元素加1
    return is;
}

3.5 升级的特点
提升灵活性：因为C语言是静态类型的语言，通常在在数组中只是用一种类型保存数据，例如，要么只用int16_t类型，要么只用int32_t类型。通过自动升级底层数组来适应不同类型的新元素，不必担心类型的错误。
节约内存：整数集合既可以让集合保存三种不同类型的值，又可以确保升级操作只在有需要的时候进行，这样就节省了内存。
不支持降级：一旦对数组进行升级，编码就会一直保存升级后的状态。
4.整数集合的其他操作
源代码注释下载：redis源码注释

Redis源码剖析和注释（五）--- 整数集合(intset)

相关推荐