Inset详解

[toc]

Intset：顾名思义，它是整数的集合，是Redis中set的一种实现方式，基于整数数组实现，具有长度可变、有序等特征。

特点：

  • 确保元素的唯一性
  • 具备升级机制，节省内存空间
  • 底层数组是有序的，因此采用二分查找
    • 也因此，它不适合存储大量数据
      • 没有基于哈希的Set快
      • 需要连续的内存空间
intset结构体
1
2
3
4
5
typedef struct intset {
    uint32_t encoding;	// 编码方式，支持16、32、64位有符号整数（2B、4B、8B）
    uint32_t length;	// 元素个数
    int8_t contents[];	// 整数数组，保存了集合的数据
} intset;

为了方便查找，Redis会将intset中的所有整数按照升序依次保存在contents数组中，如下图：

image-20240919195303556

此时占用的空间为：4(encoding)+4(length)+2*3(contents) = 14字节

可以看出，寻找一个元素的地址：addr = startAddr + sizeof(element) * index，index为元素下标

Intset升级

可以看出，当encoding为INTSET_ENC_INT16时，支持的最大整数只有2^15-1，若此时插入新数据50000，就超出最大范围，此时就触发了intset

的升级机制，它会自动升级编码至合适的大小。假设一个intset包含5、10、20三个元素，现加入元素50000。

它的升级具体流程如下：

  • 升级编码到INTSET_ENC_INT32，每个整数占四个字节，因此范围等同于int，并按照新的编码方式及元素个数扩容数组。

  • 逆序将数组中的元素拷贝到正确的位置上。（如果正序就会发生数据覆盖）

    • 正确位置计算方式：addr = startAddr + sizeof(element) * index，这里新的sizeof(element)为4

image-20240919200907228

修改前：

image-20240919201231239

修改后：

image-20240919201246295

源码分析
intset插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {	
    // is:插入的intset，value：要插入的元素，success:接收插入结果的指针
    uint8_t valenc = _intsetValueEncoding(value);	// 获取当前value的编码
    uint32_t pos;									// 插入的位置
    if (success) *success = 1;
    
    // 检查插入的值是否在编码范围内
    if (valenc > intrev32ifbe(is->encoding)) {
        //	超出编码范围，intset升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 如果value已经存在，直接抛弃，修改success指针
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
		//	value不存在，数组扩容并插入
        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;
}
intset扩容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {	// 扩容并插入元素
    uint8_t curenc = intrev32ifbe(is->encoding);	// 扩容前的encoding
    uint8_t newenc = _intsetValueEncoding(value);	// value的编码，用于判断升级到哪种编码
    int length = intrev32ifbe(is->length);		// 元素个数
    int prepend = value < 0 ? 1 : 0;			// 判断新元素放在队首还是队尾

    // 更改intset的encoding
    is->encoding = intrev32ifbe(newenc);
    //	调整数组大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    //	逆序遍历，调整元素位置
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    //	插入新元素，由于新元素超出编码范围，因此不是插入队头就是队尾，由prepend决定
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    //	修改数组长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
intset查找

因为intset存储是有序的，因此采用了典型的二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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,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;
    }
}