另外, 关于新创建的结点, 其level[]数组长度的随机算法, 在接口zslInsert的实现中, 核心代码片断如下:
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { //... level = zslRandomLevel(); // 随机生成新结点的, level[]数组的长度 if (level > zsl->level) { // 若生成的新结点的level[]数组的长度比当前表中所有结点的level[]的长度都大 // 那么头结点中需要新增几个指向该结点的指针 // 并刷新ziplist中的level字段 for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; } x = zslCreateNode(level,score,ele); // 创建新结点 //... 执行插入操作 } // 按幂次定律生成小于32的随机数的函数 // 宏 ZSKIPLIST_MAXLEVEL 的定义为32, 宏 ZSKIPLIST_P 被设定为 0.25 // 即 // level == 1的概率为 75% // level == 2的概率为 75% * 25% // level == 3的概率为 75% * 25% * 25% // ... // level == 31的概率为 0.75 * 0.25^30 // 而 // level == 32的概率为 0.75 * sum(i = 31 ~ +INF){ 0.25^i } int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; } 2.5 intset这是一个用于存储在序的整数的数据结构, 也底层数据结构中最简单的一个, 其定义与实现在src/intest.h与src/intset.c中, 关键定义如下:
typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[]; } intset; #define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))inset结构中的encoding的取值有三个, 分别是宏INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64. length代表其中存储的整数的个数, contents指向实际存储数值的连续内存区域. 其内存布局如下图所示:
intset中各字段, 包括contents中存储的数值, 都是以主机序(小端字节序)存储的. 这意味着Redis若运行在PPC这样的大端字节序的机器上时, 存取数据都会有额外的字节序转换开销
当encoding == INTSET_ENC_INT16时, contents中以int16_t的形式存储着数值. 类似的, 当encoding == INTSET_ENC_INT32时, contents中以int32_t的形式存储着数值.
但凡有一个数值元素的值超过了int32_t的取值范围, 整个intset都要进行升级, 即所有的数值都需要以int64_t的形式存储. 显然升级的开销是很大的.
intset中的数值是以升序排列存储的, 插入与删除的复杂度均为O(n). 查找使用二分法, 复杂度为O(log_2(n))
intset的代码实现中, 不预留空间, 即每一次插入操作都会调用zrealloc接口重新分配内存. 每一次删除也会调用zrealloc接口缩减占用的内存. 省是省了, 但内存操作的时间开销上升了.
intset的编码方式一经升级, 不会再降级.
总之, intset适合于如下数据的存储:
所有数据都位于一个稳定的取值范围中. 比如均位于int16_t或int32_t的取值范围中
数据稳定, 插入删除操作不频繁. 能接受O(lgn)级别的查找开销
2.6 ziplistziplist是Redis底层数据结构中, 最苟的一个结构. 它的设计宗旨就是: 省内存, 从牙缝里省内存. 设计思路和TLV一致, 但为了从牙缝里节省内存, 做了很多额外工作.
ziplist的内存布局与intset一样: 就是一块连续的内存空间. 但区域划分比较复杂, 概览如下图:
和intset一样, ziplist中的所有值都是以小端序存储的
zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数
zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作
zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占16位, 所以蛋疼的地方就来了: 如果ziplist中entry的数目小于65535, 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到.
zlend是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255
在画图展示entry的内存布局之前, 先讲一下entry中都存储了哪些信息:
每个entry中存储了它前一个entry所占用的字节数. 这样支持ziplist反向遍历.