整数集合(intset)用于有序、无重复地保存多个整数值,它会根据元素的值,自动选择该用什 么长度的整数类型来保存元素
举个例子,如果在一个 intset 里面,最长的元素可以用 int16_t 类型来保存,那么这个 intset 的所有元素都以 int16_t 类型来保存。
另一方面,如果有一个新元素要加入到这个 intset ,并且这个元素不能用 int16_t 类型来保存 ——比如说,新元素的长度为 int32_t ,那么这个 intset 就会自动进行“升级” :先将集合中现有的所有元素从 int16_t 类型转换为 int32_t 类型,接着再将新元素加入到集合中。 Intset 是集合键的底层实现之一,如果一个集合:
那么 Redis 就会使用 intset 来保存集合元素。
typedef struct intset {
// 保存元素所使用的类型的长度
uint32_t encoding;
// 元素个数
uint32_t length;
// 保存元素的数组
int8_t contents[];
} 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 数组是实际保存元素的地方,数组中的元素有以下两个特性:
具体逻辑在 intset.c/intsetAdd
函数。
并且, intsetAdd 需要维持 intset->contents 的以下性质:
当要添加新元素到 intset ,并且 intset 当前的编码并不适用于新元素的编码时,就需要对 inset 进行升级。
intset *is = intsetNew();
intsetAdd(is, 1, NULL);
// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [1]; // 所有值使用 int16_t 保存
intsetAdd(is, 65535, NULL);
// is->encoding = INTSET_ENC_INT32; // 升级
// is->length = 2;
// is->contents = [1, 65535]; // 所有值使用 int32_t 保存
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]; // 所有值使用 int64_t 保存
在添加 65535 和 4294967295 之后, encoding 属性的值,以及 contents 数组保存值的方式,都被改变了
在添加新元素时,如果 intsetAdd 发现新元素不能用现有的编码方式来保存,它就会将升级集合和添加新元素的任务转交给 intsetUpgradeAndAdd 来完成
假设有一个 intset ,里面包含三个用 int16_t 方式保存的数值,分别是 1 、 2 和 3 ,它的结 构如下:
intset->encoding = INTSET_ENC_INT16;
intset->length = 3;
intset->contents = [1, 2, 3];
其中, intset->contents 在内存中的排列如下:
现在,我们要要将一个长度为 int32_t 的值 65535 加入到集合中,执行步骤:
关于元素移动
在进行升级的过程中,需要对数组内的元素进行“类型转换”和“移动”操作。其中,移动不仅出现在升级(intsetUpgradeAndAdd)操作中,还出现其他对 contents 数组内容进行增删的操作上,比如 intsetAdd 和 intsetRemove ,因为这种移动操作需要处理 intset 中的所有元素,所以这些函数的复杂度都不低于 O(N)
pre_entry_length
pre_entry_length 记录了前一个节点的长度
,通过这个值,可以进行指针计算,从而跳转到上一个节点.根据编码方式的不同,
pre_entry_length
域可能占用 1 字节或者 5 字节:
以下则是一个长度为 5 字节的 pre_entry_length 域,域的第一个字节被设为 254 的二进制 1111 1110 ,而之后的四个字节则被设置为 10086 的二进制 10 0111 0110 0110 (多余的高位用 0 补完)
encoding 和 length
encoding 和 length 两部分一起决定了 content 部分所保存的数据的类型(以及长度)。其中, encoding 域的长度为两个 bit ,它的值可以是 00 、 01 、 10 和 11 :
content
content 部分保存着节点的内容,它的类型和长度由 encoding 和 length 决定。以下是一个保存着字符数组 hello world 的节点的例子
空白 ziplist 的表头、表尾和末端处于同一地址,添加节点分为两种情况:
将新节点添加到 ziplist 的末端需要执行以下四个步骤:
追加一个节点到现在的 ziplist 上面,首先程序首先要执行步骤 1 ,定位 ziplist 的末端:
然后执行步骤 2 ,程序需要计算新节点所需的空间: 假设我们要添加到节点里的值为字符数组 hello world ,那么保存这个值共需要 12 字节的空间:
另外,节点还需要 1 字节,用于保存前一个节点的长度 5 (二进制 101 )。 合算起来,为了添加新节点, ziplist 总共需要多分配 13 字节空间。以下是分配完成之后, ziplist 的样子:
更新新节点的各项属性(为了表示的简单, content 的内容使用字符而不是二进制来表示)
最后更新 头信息,ziplist 的 zlbytes 、 zltail 和 zllen 属性:
假设我们要将一个新节点 new 添加到节点 prev 和 next 之间:
新节点的插入会对 next 节点会产生影响,(因为 pre_entry_length 记录的值是上一个节点,此处 next 的上一个节点出现了变化)此处 next 的节点 pre_entry_length 值会出现三种情况的变化:
对于 1 和 3 情况比较好处理,直接更新对应的值就可以了。对于 2 的情况,如果 next 的节点长度发生了变化,必须检查 next 的后继节点——next+1 ,看它的 pre_entry_length 能否编码 next 的新长度,如果不能的话,程序又需要继续对 next+1 进行扩容,则 next+1 节点也要发生变化,紧接着 next +2 ,next+3 …
也就是说 ,在最差的情况下,程序必须沿着路径一个个检查后续的节点是否满足新长度的编码要求,直到遇到一个能满足要求的节点(如果有一个能满足,那么这个节点之后的其他节点也满足),或者到达 ziplist 的末端 zlend 为止,这种检查操作的复杂度为 O(N^2)
不过,因为只有在新添加节点的后面有连续多个长度接近 254 的节点时,这种连锁更新才会发生,所以可以普遍地认为,这种连锁更新发生的概率非常小,在一般情况下,将添加操作看成是 O(N) 复杂度也是可以的.
同样删除节点的操作也会有类似的问题。
遍历
可以对 ziplist 进行从前向后的遍历,或者从后先前的遍历。
当进行从前向后的遍历时,程序从指向节点 e1 的指针 p 开始,计算节点 e1 的长度(e1-size),然后将 p 加上 e1-size ,就将指针后移到了下一个节点 e2 。。。一直这样做下去,直到 p 遇到 ZIPLIST_ENTRY_END 为止,这样整个 ziplist 就遍历完了: