Redis数据结构之intset-白红宇

Redis数据结构之intset

阅读量：5283 次

发布时间：2019-06-14

本文共 6734 字，大约阅读时间需要 22 分钟。

本文及后续文章，Redis版本均是v3.2.8

上篇文章，我们说到redis object数据结构，其有5中数据类型：OBJ_STRING，OBJ_LIST， OBJ_SET，OBJ_ZSET，OBJ_HASH。集合对象set有着广泛的实际业务应用场景，它包含的元素无序并且不能重复及集合间的交、并、差等基础的操作。本篇就来说说Redis暴露给我们使用的set集合对象的底层实现-intset。

其实，可以理解为有序整型集合

intset是一个由整数组成的有序集合，从而便于进行二分查找，用于快速地判断一个元素是否属于这个集合。

它在内存分配上与ziplist有些类似，是连续的一整块内存空间，而且对于大整数和小整数采取了不同的编码，尽量对内存的使用进行了优化。

一、intset数据结构定义

typedef struct intset {

uint32_t encoding; //编码类型

uint32_t length; //intset大小，元素个数

int8_t contents[]; //数据存储区，按照升序排序数组

} intset;

/* Note that these encodings are ordered, so:

* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

从上述intset结构定义中看到其包含如下字段：

encoding：数据编码，用于表示intset中的每个数据元素用几个字节来表示。其取值如上列出的三种值：

encoding	元素类型	元素占用字节
INTSET_ENC_INT16	int16_t	2
INTSET_ENC_INT32	int32_t	4
INTSET_ENC_INT64	int64_t	8

因此，intset中存储的整数最多只能占用64bit。

length：表示intset中的元素个数。encoding和length两个字段构成了intset的头部（header）。

contents：是一个柔性数组（flexible array member），根据元素大小升序存储，表示intset的header后面紧跟着数据元素。这个数组的总字节数等于(encoding * length)/8。柔性数组在Redis的很多数据结构的定义中都出现过（例如sds, quicklist, skiplist），用于表达一个偏移量。contents需要单独为其分配空间，这部分内存不包含在intset结构当中。

intset可能会随着数据的添加而改变它的数据编码：

最开始，新创建的intset使用占内存最小的INTSET_ENC_INT16（值为2）作为数据编码。

每添加一个新元素，则根据元素大小决定是否对数据编码进行升级。

二、intset基本操作

1、创建集合

/* Create an empty intset. */

intset *intsetNew(void) {

intset *is = zmalloc(sizeof(intset));

is->encoding = intrev32ifbe(INTSET_ENC_INT16);

is->length = 0;

return is;

}

2、查找元素

/* Determine whether a value belongs to this set */

uint8_t intsetFind(intset *is, int64_t value) {

  /*判断待查元素编码是否符合条件，不符合直接返回false，否则进入intsetSearch进行实际查找*/

uint8_t valenc = _intsetValueEncoding(value);

return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);

}

/* Search for the position of "value". Return 1 when the value was found and

* sets "pos" to the position of the value within the intset. Return 0 when

* the value is not present in the intset and sets "pos" to the position

* where "value" can be inserted. */

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. */

  /* _intsetGet函数仅仅获取set集合中pos位置的值，如果待查元素大于集合尾部元素，则直接返回待查元素位置为集合长度*/

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;

}

}

  /*二分查找*/

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;

}

}

  /*找到元素返回1，否则返回0，pos为元素位置*/

if (value == cur) {

if (pos) *pos = mid;

return 1;

} else {

if (pos) *pos = min;

return 0;

}

}

从上述代码中，我们知道

intsetFind：在指定的intset中查找指定的元素value，找到返回1，没找到返回0。

_intsetValueEncoding：函数会根据要查找的value落在哪个范围而计算出相应的数据编码。

如果value所需的数据编码比当前intset的编码要大，则它肯定在intset所能存储的数据范围之外，所以这时会直接返回0；否则调用intsetSearch执行一个二分查找算法。

intsetSearch在指定的intset中查找指定的元素value，如果找到，则返回1并且将参数pos指向找到的元素位置；如果没找到，则返回0并且将参数pos指向能插入该元素的位置。

intsetSearch是对于二分查找算法的一个实现，它大致分为三个部分：
- 特殊处理intset为空的情况。
- 特殊处理两个边界情况：当要查找的value比最后一个元素还要大或者比第一个元素还要小的时候。实际上，这两部分的特殊处理，在二分查找中并不是必须的，但它们在这里提供了特殊情况下快速失败的可能。
- 真正执行二分查找过程。注意：如果最后没找到，插入位置在min指定的位置。

代码中出现的intrev32ifbe是为了在需要的时候做大小端转换的。前面我们提到过，intset里的数据是按小端（little endian）模式存储的，因此在大端（big endian）机器上运行时，这里的intrev32ifbe会做相应的转换。

这个查找算法的总的时间复杂度为O(log n)。

3、添加元素

/* Insert an integer in the intset */

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {

/*为了节省空间, 判断添加的元素需要编码为何种数据类型, 比如int16, int32, int64*/

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. */

  /*如果intset编码位数无法容纳新元素，则需要重新更新整个intset编码*/

if (valenc > intrev32ifbe(is->encoding)) {

/* This always succeeds, so we don't need to curry *success. */

  /* 更新编码并添加新元素，动态申请更大的空间以足够存储扩展后的length+1个元素 */

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. */

  /*搜索新添加元素是否已经存在，存在则返回失败；这里也就是set中无重复元素的原因*/

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);

}

  /*pos位置处赋值*/

_intsetSet(is,pos,value);

is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

return is;

}

从上述添加元素的代码中，我们知道

intsetAdd在intset中添加新元素value。如果value在添加前已经存在，则不会重复添加，这时参数success被置为0；如果value在原来intset中不存在，则将value插入到适当位置，这时参数success被置为0。

如果要添加的元素value所需的数据编码比当前intset的编码要大，那么则调用intsetUpgradeAndAdd将intset的编码进行升级后再插入value。

调用intsetSearch，如果能查到，则不会重复添加。

如果没查到，则调用intsetResize对intset进行内存扩充，使得它能够容纳新添加的元素。因为intset是一块连续空间，因此这个操作会引发内存的realloc。这有可能带来一次数据拷贝。同时调用intsetMoveTail将待插入位置后面的元素统一向后移动1个位置，这也涉及到一次数据拷贝。值得注意的是，在intsetMoveTail中是调用memmove完成这次数据拷贝的。memmove保证了在拷贝过程中不会造成数据重叠或覆盖。

intsetUpgradeAndAdd的实现中也会调用intsetResize来完成内存扩充。在进行编码升级时，intsetUpgradeAndAdd的实现会把原来intset中的每个元素取出来，再用新的编码重新写入新的位置。

注意一下intsetAdd的返回值，它返回一个新的intset指针。它可能与传入的intset指针is相同，也可能不同。调用方必须用这里返回的新的intset，替换之前传进来的旧的intset变量。类似这种接口使用模式，在Redis的实现代码中是很常见的，比如我们之前在介绍sds和ziplist的时候都碰到过类似的情况。

intsetAdd算法总的时间复杂度为O(n)。

三、intset整数集合的升级操作

此时contents数组占用的空间为16*3=48位。

升级后的整数集合为：

contents数组中的元素存放顺序为：

新创建的intset只有一个header，总共6个字节。其中encoding = 2, length = 3。

当添加65535的时候，它不再能用2个字节来表示了（2个字节能表达的数据范围是-215~215-1，而32768等于215，超出范围了），因此encoding必须升级到INTSET_ENC_INT32（值为4），即用4个字节表示一个元素。

在添加每个元素的过程中，intset始终保持从小到大有序。

因此升级的步骤为：

1）根据新元素的类型，扩展底层数组的空间大小，并分配空间

2）将底层所有元素都转换成新元素相同的类型，并将转换后的元素放到新分配的空间中。在放置元素的过程中，需要维持底层数组的有序性质不变

3）将新元素加入到底层数组中

由于新加入的元素导致升级，因此新元素的大小一定比之前所有的元素都大，因此将新元素存放在contents数组的最后一项即可。