我命由我不由天


  • 搜索
prometheus docker golang linux kubernetes

redis-跳跃表

发表于 2021-06-08 | 0 | 阅读次数 832

跳跃表

Redis的zset是一个复合结构,一方面需要一个hash结构来存储value和score的对应关系,另一方面需要提供按照score排序的功能,还需要能够指定score的范围来获取value列表的功能,这就需要另一个结构“跳跃列表”。

image.png
zset的内部实现是一个hash字典加一个跳跃列表。

基本机构

Redis的跳跃列表公有64层,容纳2^64个元素不成问题。每一个kv块对应的结构zslnode结构,kv header也是这个结构,只不过value字段时NULL值——无效的,score是Double.MIN_VALUE,用来垫底的。kv之间使用指针串起来形成了双向链表结构,它们是有序排列的,从小到大。不同的kv层高可能不一样,层数越高的kv越少,同一层的kv会使用指针串起来。每一个层元素的遍历都是从kv header出发

image.png

struct zslnode {
	string value;
	double score;
	zslnode*[] forwards; // 多层连接指针
	zslnode* backward;   // 回溯指针
}
struct zslforward {
	zslnode* item;
	long span; //跨度
}
struct zsl {
	string value;
	double score;
	zslforward*[] forwards; // 多层连接指针
	zslnode* backward;      // 回溯指针
}

查找过程

我们要定位到那个紫色的kv,需要从header的最高层开始遍历找到第一个节点(最后一个比“我”小的元素),然后从这个节点开始降一层再遍历找到第二个节点(最后一个比“我”小的元素),然后一直降到最底层进行遍历找到了期望的节点(最底层的最后一个比我“小”的元素)

image.png

随机层数

对于每一个新插入的节点,都需要调用一个随机算法给它分配一个合理的层数。直观上期望的目标是50%的概率被分配到Level1,25%的概率被分配到Level2,以此类推,每一层晋升率是50%。

Redis标准源码的晋升率只有25%,所以官方的跳跃表更扁平化,层高相对较低,在单个层上需要遍历的节点数会稍多一点。

因为层数一般不高,所以遍历的时候从顶层开始往下遍历会浪费,跳跃列表会记录当前的最高层数maxLevel,遍历时从这个maxLevel开始遍历,性能提高很多。

插入过程

首先我们在搜索合适插入点的过程中将“搜索路径”找出来,然后就可以开始创建新节点。创建的时候需要给这个节点随机分配一个层数,再讲搜索路径上的节点和这个新节点通过前向后向指针串起来。如果分配的新节点的高度高于当前跳跃表列表的最大高度,就需要更新一下跳跃列表的最大高度。

删除过程

删除过程和插入过程类似,都需要先把这个“搜索路径”找出来,然后对于每个层的相关节点重排一下前向后向指针,同时注意更新一下最高层maxLevel

更新过程

当我们调用zadd方法时,如果对应的value不存在,那就是插入过程。如果这个value已经存在,只是调整一下score的值,那就需要走一个更新流程。假设这个新的score值不会带来排序上的改变,那么久不需要调整位置,直接修改元素的score值就可以。但是如果排序位置改变了,那就要调整位置。

一个简单的策略是先删除元素,再插入元素,需要经过两次路径搜索。Redis就是这么干的。

如果score值一样

在一个极端的情况下,zset中所有的score值都是一样的,zset的查找性能会退化为O(n)么?所以zset的排序元素不止看score的值,还看value比较

元素排名

zset可以获取元素的排名。Redis在skiplist 的forward指针上进行了优化,给每个forward指针都增加了span属性,span是“跨度”的意思,表示从前一个节点沿着当前层的forward指针跳到当前这个节点中间会跳过多少个节点。Redis在插入、删除操作会小心翼翼更新span值。

我们计算一个元素的排名时,只需要将“搜索路径”经过的所有节点的跨度span值进行叠加就可以算出元素的最终rank值。

  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/redis-跳跃表
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
redis-quicklist
客户端与服务器连接的过程
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号