渐进式解析 Redis 源码 - 整数集合 intset

Redis 作为内存存储系统，在内存节约方面肯定会有所特点，而且 Redis 在这方面要求极其苛刻，比较明显的就是 整数集合intset 和 压缩列表ziplist 两个结构

这次我们就以 整数集合 intset 作为主题 ~~~

整数集合intset 是 集合键的底层实现之一，当一个集合只包含整数元素，而且集合的元素数量不多时（限制值默认 server.set_max_intset_entries = OBJ_SET_MAX_INTSET_ENTRIES = 512），Redis 就会使用整数集合作为集合键的底层实现

整数集合结构

整数集合在 Redis 中用于保存整数值的集合抽象数据结构，它可以保存 int16_t / int32_t / int64_t 三种类型的整数值，并且保证没有重复；整数集合的结构体如下：

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

• 整数集合的每个元素都是 contents[] 数组里面一个 元素，并且按照 大小 升序排列，而且要求数组数字的唯一性，不允许重复
• length 记录了整数集合的 元素个数，也就是 contents[] 数组的长度，所以长度获取复杂度为 O(1)
• 数据类型方面，虽然结构体数组声明的类型为 int8_t，但是存储的时候并不是 int8_t 类型，而是取决于 encoding 属性值，以下为各种属性值对应数字大小范围
  • INTSET_ENC_INT16，那么 contents[] 数组的类型就是 int16_t，那么 数组的内存长度就是 sizeof(int16_t) * length，数组内数字大小范围为 -32 768 ~ 32 767
  • INTSET_ENC_INT32，那么 contents[] 数组的类型就是 int32_t，那么 数组的内存长度就是 sizeof(int32_t) * length，数组内数字大小范围为 -2 147 483 648 ~ 2 147 483 647
  • INTSET_ENC_INT64，那么 contents[] 数组的类型就是 int64_t，那么 数组的内存长度就是 sizeof(int64_t) * length，数组内数字大小范围为 -9 223 372 036 854 775 808 ~ 9 223 372 036 854 775 807

整数集合升级

整数集合涉及一个升级问题，比如原本存储的数据都是 int16_t 类型长度的，后面添加了一个 int32_t 长度的数字，那么就需要 先对整个数据结构进行升级，再添加新数字，不过需要注意的是 整数集合不提供降级功能；升级步骤如下：

• 根据新元素类型，扩展 contents[] 空间大小，并为新元素分配空间
• 将现有 contents[] 里的所有元素数字类型都转换成新元素类型，并将转换后的元素遵循 有序原则放置好
• contents[] 中添加新元素

下面我们就 Redis 整数集合一些 典型的 API 进行解析~~~

源码解析

由于有些方法里的代码量比较大，我们这里按照 典型的代码片段进行解析，同志们可以根据文章提示的代码位置 和 代码里面的关键词 在源码中搜素，可能数据结构一些元素 看不太懂什么意思，没关系，先混个脸熟，后面看完回头再看过来就明白了

数字添加函数 intsetAdd()

/* intset.h: line 204 */

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // 新数值类型
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    // 如果新值类型大于原数据结构类型，则对结构进行升级操作，并插入数值
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        // 查找插入位置，因为 数组元素是 秉承从小到大的顺序排列的
        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);
    // 长度 ++
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

上面涉及的 集合升级函数为 intsetUpgradeAndAdd()

/* intset.h: line 157 */

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 当前数值类型
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 新数值的类型
    uint8_t newenc = _intsetValueEncoding(value);
    // 集合长度
    int length = intrev32ifbe(is->length);
    // 判断新数值如果小于0 则添加到 首部，否则添加到 尾部
    // 这里不用考虑原数据的问题，因为既然需要升级了，新数值 肯定比 原数值最大数大 或者 比原数值最小的小
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // encoding 属性修改为 新的类型值
    is->encoding = intrev32ifbe(newenc);
    // 调整数组大小
    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. */
    // 遍历数组，将数组元素重新放置到 新位置，不过这里采用的是 从后往前遍历的方式，放置数字元素的 相互覆盖
    while(length--)
        // 依次将数组元素放置到新的位置
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    // 根据上面的 正负值判断，新数值 插入 数组头 或者 数组尾
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 集合长度++
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

另外还有一个在插入操作中很重要的函数，就是 查找插入位置函数 intsetSearch()

/* intset.h: line 115 */

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;

    /* The value can never be found when the set is empty */
    // 如果是空数组
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        // 如果大于数组最后一个值则位置为最后一个位置
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
        // 如果小于数组第一个值，则位置为 0
            if (pos) *pos = 0;
            return 0;
        }
    }
    // 二分查找法 遍历数组，对比值 大小，所以复杂度为 log n
    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;
    }
}

另外还有一些 API，不过逻辑比较简单，这里就不一一解读了

intsetRemove() 从整数集合中移除指定元素，O(n)
intsetFind() 检查指定值是否存在于集合中，O(log n)
intsetRandom() 从整数集合中随机返回一个元素，O(1)
intsetGet()取出给定给定索引上的元素，O(1)
intsetLen() 获取整数集合元素个数，O(1)
intsetBlobLen() 返回整数集合占用的内存字节数，O(1)

---

本文作者： wettper
本文链接： http://www.web-lovers.com/redis-source-intset.html
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信