zset
zset一方面它是一个 set,保证了内部value 的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重。
zset的底层是由字典和跳表实现。
字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提供zset按照score排序的功能、指定score范围获取value列表的功能。
struct zset {dict *dict; // all values value=>scorezskiplist *zsl;
}
跳表
跳表数据结构包含的属性:
- header:表示kv head的地址
- maxLevel:最高层级
struct zskiplist {zslnode* header; // 跳跃列表头指针int maxLevel; // 跳跃列表当前的最高层map<string, zslnode*> ht; // hash 结构的所有键值对
}
以下就是跳表的示意图:
每一个kv按照score有序排列的,不同的 kv 层高可能不一样,层数越高的 kv 越少。也就是不同 kv 的level[ ]长度不一样。同一层的 kv 会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。
为什么需要这么设计呢?如果只有一层,也就是一个双链表,所有元素按照score排序,我们如果想要快速定位到某个score,我们就需要从头指针依次遍历,时间复杂度为O(n)。如果我们设计成跳表这个多层结构,效果类似于二分查找,时间复杂度为O(lg(n))。
每一个结点包含的属性如下:
struct zslnode {string value;double score;zslforward*[] level; // 多层连接指针zslnode* backward; // 回溯指针
}
struct zslforward {zslnode* forward;long span; // 跨度
}
查找
如果当前节点的下一个节点包含的值比目标元素值小,则继续向右查找。如果下一个节点的值比目标值大,就转到当前层的下一层去查找。
比如说要查找21,当查找到6这个结点时,6比21小,继续向右查找,因为此时在6结点level[3],level[3]的下一个结点是nil,不符合,那么就转到6的level[2],level[2]的下一个结点是(6->level[2].forward)25,比目标值大,继续转到6的level[1],level[1]的下一个结点是9,9比21小,继续向右查找……
注意: zset 的排序元素不只看 score 值,如果score 值相同还需要再比较 value 值 (字符串比较)。为了防止如果每个元素的score值都相同的话,查找时间复杂度变成O(n)。
插入
当客户端使用 zset add 命令时,redis底层插入元素的过程:
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {// 存储搜索路径zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;// 存储经过的节点跨度unsigned int rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));x = zsl->header;// 逐步降级寻找目标节点,得到「搜索路径」for (i = zsl->level-1; i >= 0; i--) {rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&compareStringObjects(x->level[i].forward->obj,obj) < 0))) {// 累计搜索路径中经过各结点的跨度。也就是最后查询到的元素的rank值。rank[i] += x->level[i].span;x = x->level[i].forward;}update[i] = x;}/**正式进入插入过程**/// 随机一个层数level = zslRandomLevel();if (level > zsl->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,obj);// 重排一下前向指针for (i = 0; i < level; i++) {x->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x;x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1;}for (i = level; i < zsl->level; i++) {update[i]->level[i].span++;}// 重排一下后向指针x->backward = (update[0] == zsl->header) ? NULL : update[0];if (x->level[0].forward)x->level[0].forward->backward = x;elsezsl->tail = x;zsl->length++;return x;
}
- 通过 kv head 这个结点获得最高层的结点地址。
- 逐层降级寻找目标结点,所经过的结点存储在搜索路径update[]数组中。
- 创建一个新结点。
- 为这个结点算一个随机层数,表示这个结点的level[]最大是第几层。
- 遍历update数组,为这个新创建的结点的每层level设置好前后指针。
删除
删除过程和插入过程类似,都需先把这个「搜索路径」找出来。然后对于每个层的相关节点都重排一下前向后向指针就可以了。同时还要注意更新一下最高层数 maxLevel。
更新
当我们调用 zadd 方法时,如果对应的 value 不存在,那就是【插入过程】。
如果这个value 已经存在了,只是调整一下 score 的值,
- 假设这个新的score 值不会带来排序位置上的改变,那么就不需要调整位置,直接修改元素的 score 值就可以了。
- 如果新的score值让排序位置改变了,那就要调整位置。如何调整位置?直接将这个元素删了,然后插入。这一点可以优化,因为如果直接删,然后再插入,需要两次路径搜索,对于改变score值后仍不需要调整位置的情况就可以优化。
字典
dict数据结构可以应用在:
- hash 结构的数据
- 整个 Redis 数据库的所有 key 和 value
- 带过期时间的 key 集合
- zset 集合中存储 value 和 score 值的映射关系
struct RedisDb {dict* dict; // all keys key=>valuedict* expires; // all expired keys key=>long(timestamp)
}
struct zset {dict *dict; // all values value=>scorezskiplist *zsl;
}
dict数据结构包含的属性:
struct dict {...dictht ht[2]; // 两个dictht结构,也就是两个hashtable
}
struct dictht {dictEntry** table; // 二维,第一维是数组,第二维是链表。数组中存储的是第二维链表的第一个元素的指针。long size; // 第一维数组的长度long used; // hash 表中的元素个数...
}
struct dictEntry {void* key;void* val;dictEntry* next; // 链接下一个 entry
}
rehash
rehash条件:
Dict在每次新增键值对时都会检查负载因子(LoadFactor = used/size) ,满足以下两种情况时会触发哈希表扩容:
哈希表的 LoadFactor >= 1,并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程;
哈希表的 LoadFactor > 5 ;
rehash过程:(渐进式rehash)
-
计算新hash表的realeSize,值取决于当前要做的是扩容还是收缩:
- 如果是扩容,则新size为第一个大于等于dict.ht[0].used + 1的2^n
- 如果是收缩,则新size为第一个大于等于dict.ht[0].used的2^n (不得小于4)
-
按照新的realeSize申请内存空间,创建dictht,并赋值给dict.ht[1]
-
设置dict.rehashidx = 0,标示开始rehash
-
将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1](注意,这里不是一次性就将所有entry移到ht[1]中。)
每次执行新增、查询、修改、删除操作时,都检查一下dict.rehashidx是否大于-1,如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1],并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]。—渐进式哈希
-
将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空哈希表,释放原来的dict.ht[0]的内存。
-
将rehashidx赋值为-1,代表rehash结束。
-
在rehash过程中,新增操作,则直接写入ht[1],查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增,随着rehash最终为空。
rehash时机:
rehash将ht[0]的数据搬迁到ht[1]是在客户端执行命令中时发生的。也就是渐进性哈希。如果客户端闲下来,redis则通过定时任务对字典进行搬迁。
string
Redis 中的字符串是可以修改的字符串,在内存中它是以字节数组的形式存在的。这个字符串叫「SDS」,也就是 Simple Dynamic String。它的结构是一个带长度信息的字节数组。
SDS
struct SDS<T> {T capacity; // 数组容量T len; // 数组长度byte flags; // 特殊标识位,不理睬它byte[] content; // 数组内容
}
如上图所示,capacity 表示所分配数组的长度,len 表示字符串的实际长度。
embstr vs raw
Redis 的字符串有两种存储方式,在长度特别短时,使用 emb 形式存储 (embeded),当长度超过 44 时,使用 raw 形式存储。
所有redis对象都有下面这个结构头,包括我们现在研究的SDS对象也会有这个对象头。
struct RedisObject {int4 type; // 4bits 不同的对象具有不同的类型int4 encoding; // 4bits 同一个类型的 type 会有不同的存储形式encoding(4bit),int24 lru; // 24bits int32 refcount; // 4bytes 每个对象都有个引用计数,当引用计数为零时,对象就会被销毁,内存被回收。void *ptr; // 8bytes,64-bit system ptr 指针将指向对象内容 (body) 的具体存储位置。
} robj;
这样一个 RedisObject 对象头需要占据 16 字节的存储空间。
我们再看 SDS 结构体的大小:
struct SDS {int8 capacity; // 1byteint8 len; // 1byteint8 flags; // 1bytebyte[] content; // 内联数组,长度为 capacity
}
一个SDS对象头至少是3字节,那么一整个SDS对象至少是3+16=19字节,也就是说分配一个字符串最小空间占用为19字节。
- embstr 存储形式将 RedisObject 对象头和 SDS 对象连续存在一起,使用 malloc 方法一次分配。
- raw 存储形式需要两次malloc,两个对象头在内存地址上一般是不连续的。
内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等,为了能容纳一个完整的 embstr 对象,**jemalloc 最少会分配 32 字节的空间,如果字符串再稍微长一点,那就是 64 字节的空间。**如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。
也就是如果分配的是64字节的空间,那么扣掉SDS对象头和redis对象头,剩下64 - 19 = 45字节给字符串,而字符串是以字节\0 结尾的,因此字符串长度最大为44字节,如果超过44字节,那么用raw形式存储。
oc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等,为了能容纳一个完整的 embstr 对象,**jemalloc 最少会分配 32 字节的空间,如果字符串再稍微长一点,那就是 64 字节的空间。**如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。
也就是如果分配的是64字节的空间,那么扣掉SDS对象头和redis对象头,剩下64 - 19 = 45字节给字符串,而字符串是以字节\0 结尾的,因此字符串长度最大为44字节,如果超过44字节,那么用raw形式存储。
参考
《Redis深度历险:核心原理和应用实践》
https://www.jianshu.com/p/09c3b0835ba6