衡水网站建设联系电话,如何能让网站尽快备案通过,云服务平台,太原市建设工程招投标信息网站zset
zset一方面它是一个 set#xff0c;保证了内部value 的唯一性#xff0c;另一方面它可以给每个 value 赋予一个 score#xff0c;代表这个 value 的排序权重。
zset的底层是由字典和跳表实现。
字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提…zset
zset一方面它是一个 set保证了内部value 的唯一性另一方面它可以给每个 value 赋予一个 score代表这个 value 的排序权重。
zset的底层是由字典和跳表实现。
字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提供zset按照score排序的功能、指定score范围获取value列表的功能。
struct zset {dict *dict; // all values valuescorezskiplist *zsl;
}跳表
跳表数据结构包含的属性
header表示kv head的地址maxLevel最高层级
struct zskiplist {zslnode* header; // 跳跃列表头指针int maxLevel; // 跳跃列表当前的最高层mapstring, 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].forward25比目标值大继续转到6的level[1]level[1]的下一个结点是99比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[i1];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 keyvaluedict* expires; // all expired keys keylong(timestamp)
}struct zset {dict *dict; // all values valuescorezskiplist *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 SDST {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; // 8bytes64-bit system ptr 指针将指向对象内容 (body) 的具体存储位置。
} robj;这样一个 RedisObject 对象头需要占据 16 字节的存储空间。
我们再看 SDS 结构体的大小
struct SDS {int8 capacity; // 1byteint8 len; // 1byteint8 flags; // 1bytebyte[] content; // 内联数组长度为 capacity
}一个SDS对象头至少是3字节那么一整个SDS对象至少是31619字节也就是说分配一个字符串最小空间占用为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
