Redis设计与实现之整数集合

一、内存映射数据结构

二、整数集合

1、整数集合的应用

2、数据结构和主要操作

3、intset运行实例

创建新intset

添加新元素到 intset

添加新元素到 intset（不需要升级）

添加新元素到 intset (需要升级)

4、升级

升级实例

5、关于升级

第一，从较短整数到较长整数的转换，并不会更改元素里面的值。

第二，集合编码元素的方式，由元素中长度最大的那个值来决定。

6、关于元素移动

7、其他操作

读取

写入

删除

降级

三、小结

一、内存映射数据结构

虽然内部数据结构非常强大，但是创建一系列完整的数据结构本身也是一件相当耗费内存的工作，当一个对象包含的元素数量并不多，或者元素本身的体积并不大时，使用代价高昂的内部数据结构并不是最好的办法。

为了解决这一问题， Redis在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构。

内存映射数据结构是一系列经过特殊编码的字节序列，创建它们所消耗的内存通常比作用类似的内部数据结构要少得多，如果使用得当，内存映射数据结构可以为用户节省大量的内存。

不过，因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多，所以内存映射数据结构所占用的 CPU时间会比作用类似的内部数据结构要多。

这一部分将对 Redis目前正在使用的两种内存映射数据结构进行介绍。

二、整数集合

整数集合（ intset）用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。

举个例子，如果在一个 intset里面，最长的元素可以用 int16_t 类型来保存，那么这个 intset的所有元素都以 int16_t 类型来保存。

另一方面，如果有一个新元素要加入到这个 intset，并且这个元素不能用 int16_t 类型来保存——比如说，新元素的长度为 int32_t ，那么这个 intset就会自动进行“升级”：先将集合中现有的所有元素从 int16_t 类型转换为 int32_t 类型，接着再将新元素加入到集合中。

根据需要， intset可以自动从 int16_t 升级到int32_t 或int64_t ，或者从 int32_t 升级到int64_t 。

1、整数集合的应用

Intset是集合键的底层实现之一，如果一个集合：

1.只保存着整数元素；

2.元素的数量不多；

那么 Redis就会使用 intset来保存集合元素。

2、数据结构和主要操作

以下是intset.h/intset 类型的定义：

typedef structintset {

    //保存元素所使用的类型的长度

    uint32_t encoding;

    //元素个数

    uint32_t length;

    //保存元素的数组

    int8_tcontents[];

} intset;

encoding 的值可以是以下三个常量的其中一个（定义位于 intset.c ）：

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

contents 数组是实际保存元素的地方，数组中的元素有以下两个特性：

•没有重复元素；

•元素在数组中从小到大排列；

contents 数组的int8_t类型声明比较容易让人误解，实际上， intset并不使用 int8_t类型来保存任何元素，结构中的这个类型声明只是作为一个占位符使用：在对 contents 中的元素进行读取或者写入时，程序并不是直接使用 contents 来对元素进行索引，而是根据 encoding的值，对 contents 进行类型转换和指针运算，计算出元素在内存中的正确位置。在添加新元素，进行内存分配时，分配的容量也是由 encoding 的值决定。

下表列出了处理 intset的一些主要操作，以及这些操作的算法复杂度：

3、intset运行实例

让我们跟踪一个 intset的创建和添加过程，籍此了解 intset的运作方式。

创建新intset

intset.c/intsetNew 函数创建一个新的 intset，并为它设置初始化值：

intset*is=intsetNew();

// intset->encoding = INTSET_ENC_INT16;

// intset->length 0;

// intset->contents = [];

注意encoding 使用INTSET_ENC_INT16 作为初始值。

添加新元素到 intset

创建intset之后，就可以对它添加新元素了。

添加新元素到 intset的工作由 intset.c/intsetAdd 函数完成，它需要处理以下三种情况：

1.元素已存在于集合，不做动作；

2.元素不存在于集合，并且添加新元素并不需要升级；

3.元素不存在于集合，但是要在升级之后，才能添加新元素；

并且，intsetAdd 需要维持 intset->contents 的以下性质：

1.确保数组中没有重复元素；

2.确保数组中的元素按从小到大排序；

整个intsetAdd 的执行流程可以表示为下图：

以下两个小节分别演示添加操作在升级和不升级两种情况下的执行过程。

添加新元素到 intset（不需要升级）

如果 intset现有的编码方式适用于新元素，那么可以直接将新元素添加到 intset，无须对 intset进行升级。

以下代码演示了将三个 int16_t 类型的整数添加到集合的过程，以及在添加过程中，集合的状态：

intset*is=intsetNew();

intsetAdd(is, 10,NULL);

// is->encoding = INTSET_ENC_INT16;

// is->length = 1;

// is->contents = [10];

intsetAdd(is, 5,NULL);

// is->encoding = INTSET_ENC_INT16;

// is->length = 2;

// is->contents = [5, 10];

intsetAdd(is, 12, NULL);

// is->encoding = INTSET_ENC_INT16;

// is->length = 3;

// is->contents = [5, 10, 12]

因为添加的三个元素都可以表示为 int16_t ，因此 is->encoding 一直都是 INTSET_ENC_INT16 。

另一方面，is->length 和 is->contents 的值则随着新元素的加入而被修改。

添加新元素到 intset (需要升级)

当要添加新元素到 intset ，并且 intset 当前的编码并不适用于新元素的编码时，就需要对 inset 进行升级。

以下代码演示了带升级的添加操作的执行过程:

intset *is = intsetNew();
intsetAdd(is, 1, NULL);
// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [1];
intsetAdd(is, 65535, NULL);
// is->encoding = INTSET_ENC_INT32;
// is->length = 2;
// is->contents = [1, 65535];
intsetAdd(is, 70000, NULL);
// is->encoding = INTSET_ENC_INT32;
// is->length = 3;
// is->contents = [1, 65535, 70000];
intsetAdd(is, 4294967295, NULL);
// is->encoding = INTSET_ENC_INT64;
// is->length = 4;
// is->contents = [1, 65535, 70000, 4294967295];
// 所有值使用 int16_t 保存
// 升级
// 所有值使用 int32_t 保存
// 升级
// 所有值使用 int64_t 保存

在添加 65535 和 4294967295 之后，encoding 属性的值，以及 contents 数组保存值的方式，都被改变了。

4、升级

在添加新元素时，如果 intsetAdd 发现新元素不能用现有的编码方式来保存，它就会将升级集

合和添加新元素的任务转交给 intsetUpgradeAndAdd 来完成:

intsetUpgradeAndAdd 需要完成以下几个任务:

对新元素进行检测，看保存这个新元素需要什么类型的编码;
将集合encoding属性的值设置为新编码类型，并根据新编码类型，对整个contents数组进行内存重分配。
调整contents数组内原有元素在内存中的排列方式，让它们从旧编码调整为新编码。
将新元素添加到集合中。

整个过程中，最复杂的就是第三步，让我们用一个例子来理解这个步骤。

升级实例

假设有一个 intset ，里面包含三个用 int16_t 方式保存的数值，分别是 1 、2 和 3 ，它的结构如下:

intset->encoding = INTSET_ENC_INT16;
intset->length = 3;
intset->contents = [1, 2, 3];

其中，intset->contents 在内存中的排列如下:

bit     0  15  31  47 
value   | 1 | 2 | 3 |

现在，我们要要将一个长度为 int32_t 的值 65535 加入到集合中，intset 需要执行以下步骤:

1. 将encoding属性设置为INTSET_ENC_INT32。
2. 根据encoding属性的值，对contents数组进行内存重分配。

重分配完成之后，contents 在内存中的排列如下:

bit     0  15  31 47  63  95  127 
value   | 1 | 2 | 3 | ? | ? | ? |

3.因为原来的 3 个 int16_t 值还“挤在”contents 前面的 48 个位里，所以程序需要对它们

进行移动和类型转换，从而让它们适应集合的新编码方式。首先是移动 3 :

接着移动2:

最后，移动 1 :

4.最后，将新值 65535 添加到数组:

将 intset->length 设置为 4 。

至此，集合的升级和添加操作完成，现在的 intset 结构如下:

intset->encoding = INTSET_ENC_INT32;
intset->length = 4;
intset->contents = [1, 2, 3, 65535];

5、关于升级

关于升级操作，还有两点需要提醒一下:

第一，从较短整数到较长整数的转换，并不会更改元素里面的值。

在 C 语言中，从长度较短的带符号整数到长度较长的带符号整数之间的转换(比如从 int16_t 转换为 int32_t )总是可行的(不会溢出)、无损的。

另一方面，从较长整数到较短整数之间的转换可能是有损的(比如从 int32_t 转换为 int16_t )。

因为 intset 只进行从较短整数到较长整数的转换(也即是，只“升级” ，不“降级” )，因此， “升级”操作并不会修改元素原有的值。

第二，集合编码元素的方式，由元素中长度最大的那个值来决定。

就像前面演示的例子一样，当要将一个 int32_t 编码的新元素添加到集合时，集合原有的所有 int16_t 编码的元素，都必须转换为 int32_t 。

尽管这个集合真正需要用 int32_t 长度来保存的元素只有一个，但整个集合的所有元素都必须转换为这种类型。

6、关于元素移动

在进行升级的过程中，需要对数组内的元素进行“类型转换”和“移动”操作。

其中，移动不仅出现在升级(intsetUpgradeAndAdd)操作中，还出现其他对 contents 数组内容进行增删的操作上，比如 intsetAdd 和 intsetRemove ，因为这种移动操作需要处理 intset 中的所有元素，所以这些函数的复杂度都不低于 O(N) 。

7、其他操作

以下是一些关于 intset 其他操作的讨论。

读取

有两种方式读取 intset 的元素，一种是 _intsetGet ，另一种是 intsetSearch :
• _intsetGet 接受一个给定的索引 pos ，并根据 intset->encoding 的值进行指针运算，

计算出给定索引在 intset->contents 数组上的值。
• intsetSearch 则使用二分查找算法，判断一个给定元素在 contents 数组上的索引。

写入

除了前面介绍过的 intsetAdd 和 intsetUpgradeAndAdd 之外，_intsetSet 也对集合进行写入操作:它接受一个索引 pos ，以及一个 new_value ，将 contents 数组 pos 位置的值设为 new_value 。

删除

删除单个元素的工作由 intsetRemove 操作，它先调用 intsetSearch 找到需要被删除的元素在 contents 数组中的索引，然后使用内存移位操作，将目标元素从内存中抹去，最后，通过内存重分配，对 contents 数组的长度进行调整。

降级

Intset 不支持降级操作。

Intset 定位为一种受限的中间表示，只能保存整数值，而且元素的个数也不能超过 redis.h/REDIS_SET_MAX_INTSET_ENTRIES (目前版本值为 512 )这些条件决定了它被保存的时间不会太长，因此对它进行太复杂的操作，没有必要。

当然，如果内存确实十分紧张的话，给 intset 添加降级功能也是可以实现的，不过这可能会让 intset 的代码增长一倍。

三、小结

Intset 用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。
当一个位长度更长的整数值添加到 intset 时，需要对 intset 进行升级，新 intset 中每个元素的位长度都等于新添加值的位长度，但原有元素的值不变。
升级会引起整个 intset 进行内存重分配，并移动集合中的所有元素，这个操作的复杂度 O(N)
Intset 只支持升级，不支持降级。
Intset 是有序的，程序使用二分查找算法来实现查找操作，复杂度为 O(lgN) 。