【最完整系列】Redis-结构篇-跳跃列表

注意:本系列文章分析的 Redis 源码版本:https://github.com/Sidfate/redis ,是文章发布时间的最新版。

大家知道 redis 五种常用的数据结构有:字符串(string), 散列(hash), 列表(list), 集合(set)和有序集合(sorted set) 。相对而言 sorted set(以下简称为zset) 用的相对较少,它他的实现结构却很有趣,这种结构被称为 跳跃列表 skiplist ,后面我还会结合一个日常生活的例子来解释它。

首先简单介绍下 zset 是个啥有什么用,已经了解的童鞋可以直接到下一章节。

有序集合的数据类型,类似于集合(set)和散列表(hash)之间的混合。有序集合和集合一样,元素是唯一的。并且有序集合中的每个元素都可以对应一个score值,所以它也像一个散列表。另外,有序集合中的元素可以根据score值进行排序遍历。

zset

看了上面的介绍,你可能已经猜到了,zset 是 2 种数据结构的结合,在源码的注释中是这么解释的:

Zset 是使用了 2 个数据结构来保存相同元素的有序集合,同时还能保证复杂度为 O(log(N)) 的插入和删除操作。Zset 中的元素被添加到一个散列表中,保存着 Redis对象 – score 的映射关系。同时,这些元素被添加到一个跳跃列表 skiplist 中,将 score 映射到 Redis对象(对象根据 score 排序)。

注意下这句: “同时还能保证复杂度为 O(log(N)) 的插入和删除操作”,有没有一种婆婆介绍儿子的赶脚,言语间透露的自豪感,请记住它,下面我还会提到。散列表(hash),在之前的文章中已经分析过了,具体可以查看我的文章《【最完整系列】Redis-结构篇-字典》,所以不再说明了,接下来着重分析下 skiplist。

skiplist

跳跃列表在很早之前就已经被发明了,有兴趣的可以看下[它的历史](Skip Lists: A Probabilistic Alternative to Balanced Trees)。首先从名字上看它是一个 list,并且我们之前说过它还是有序的。一般来说,有序链表长这个样子:

最左侧节点为空的头节点,a 是我自己取得名字,方便做区分。

思考下,我们插入一个新的元素 “23” 需要怎么做,首先要遍历链表,比较节点元素直到找到一个大于 “23” 的元素,所以复杂度为 O(N),删除某个元素也是一个道理,你们发现没,其实添加和删除后就是一个查询的过程。

为此,如果我们稍做优化,小小地改变一下链表的结构,为相邻的节点增加一个指针,指向下下个节点:

上图中可以发现形成了一个新链表 b(7 – 19 – 26),节点个数为原先链表,这时候我们重新去查询 “23” :

  1. 遍历链表 b,查询到第一个大于 23 的元素 “26”
  2. 回到链表 a,发现 21 比 23 小,所以插入到 “21” 和 “26” 节点之间。

你们有没有发现,是不是很类似于二分查找,最终我们减少了查询的次数,我们甚至还可以再分一次创建一个新链表 c:

这时候的查询步骤变成了:

  1. 遍历链表 c,只有一个元素 “19“,发现 23 大于 19,所以在 “19“ 后面找。
  2. 回到链表 b,查询到第一个大于 23 的元素 “26” 。
  3. 回到链表 a,发现 21 比 23 小,所以插入到 “21” 和 “26” 节点之间。

可以发现我们遍历的元素个数在逐渐减少,可想而知如果包含的元素个数足够大,查询的效率也会大幅提升。下面我举一个日常生活的例子来说明这种做法的优势:

我们在有序链表中查询一个元素的过程就好比在酒店里坐电梯。假如酒店有10层楼高,1-5层是普通套房,住的人多;6-10层是高级套房,住的人少。我住在9楼(嘿嘿嘿),那么我坐电梯下去 1 层的时候很可能在各个低层会停留(因低层住的人多),这对于高层客人肯定不爽。后面酒店改了,新造了电梯,分成了单双停靠,对我来说肯定是比之前更快了,但是1、3、5层还是会经常停靠,高层客人还是不满意。在之后酒店做绝了,直接造了一个1-5层不停留直达高层的电梯,这下舒服了,客户评价马上上去了。

如果你看懂了上面的例子,其实也发现了这个做法的一个劣势:需要造更多的 “电梯“,也就是需要创建更多的链表,黑话叫 “空间换时间”。

我们的 skiplist 正是在上面这种多层链表基础上设计而来的。实际上,按照上面生成链表的方式,上面每一层链表的节点个数,是下面一层的节点个数的一半,类似于一个二分查找,使得查找的时间复杂度可以降低到 O(log n) (还记得我之前让你记住的那个复杂度吗?)。但是,这种方法在插入数据的时候有很大的问题。新插入一个节点之后,就会破坏了上下相邻两层链表上节点个数 2:1 的比例关系。要维持这种对应关系,就必须把新插入的节点后面的所有节点(也包括新插入的节点)重新进行调整,这会让时间复杂度又降低成了 O(n),删除节点也一样。

shiplist 当然也考虑到这个问题,为此,它不要求上下相邻两层链表之间的节点个数有严格的比例关系,而是每个节点随机一个层数 level 。比如,一个节点随机出的层数是 3,那么就把它链入到第 1 层到第 3 层这三层链表中。为了表达清楚,下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程:

为了减少一部分童鞋的疑惑,我先总结一下上图过程的 3 个特点:

  • 第一层链表永远保存着最完整的元素数据。
  • 位于第n层的元素,也肯定在 1~n-1层 之中。
  • 新插入一个元素不会影响其它元素的层数。

前方高晕预警,以下内容涉及一些概率学和数学知识,摘自发明者的论文。可以直接跳过查看下一章节。

比较有意思的一点是元素的层数随机,这意味着 skiplist 是一个 “概率型” 的数据结构。实际上决定层数的随机计算对跳表的查找性能有着很大影响,这并不是一个普通的服从均匀分布的随机数,它的计算过程如下:

  1. 指定一个节点最大的层数 MaxLevel,指定一个概率 p, 层数 level 默认为 1 。
  2. 生成一个 0~1 的随机数 r,若 r < p,且 level < MaxLevel ,则执行 level++。
  3. 重复第 2 步,直至生成的 r > p 为止,此时的 level 就是要插入的层数。

伪代码如下:

randomLevel()
    level = 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

在 Redis 的 skiplist 实现中,p=1/4 ,MaxLevel=64。

源码结构

Redis 在 skiplist 的基础结构上做了一些变化来满足自己的需求,首先 show you source code:

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

ZSKIPLIST_MAXLEVELZSKIPLIST_P 2个常量就是我们上一章节最后提到的部分。

属性含义
header头指针
tail尾指针
length链表长度,即链表包含的节点总数,不包含头指针。
levelskiplist 的总层数

为什么 zskiplistNode 的前向指针 backward 只有一个?

我发现基本上没有文章提到这一点,但是我觉得还是有必要解释下的。首先节点只有一个后向指针,也就意味着只有第一层的链表是一个双向链表,之前我们的例子里的链表都是单向的,为什么要把第一层变成双向呢?原因之一是第一层的数据最完整,原因之二是:试想一下,我们有一个元素的 score 为 8,其第一层的相邻节点 score 为 7 和 10,现在我们想要更新这个元素的 score 为 9,理论上我们要删除在插入,但其实这个元素的位置根本不需要改动,这种情况下可以先判断第一层相邻节点的大小,如果还是在区间内,就直接更新值,省去了删除插入的步骤。

level 中 span 的意义?

解释这个问题需要图片帮助,首先放一个 skiplist 的图:

箭头中上的数字就是 span 的值,span有很多好处,例如我们要找score为 3 的排名,直接取头指针中 L5 的span = 3 就行了,如果存在需要多层查询的情况就是累加的过程,反之还可以通过长度-累加值的操作计算逆序的排名。

属性含义
ele数据本体。这里可以看到它是一个 sds 结构,sds 是 redis 中的字符串结构。关于 sds 结构的结构的详情你参考我的文章《【最完整系列】Redis-结构篇-字符串》。
score数据对应的分数。
backward指向链表前一个节点的指针(前向指针)。
level[]zskiplistLevel 数组,存放指向各层链表后一个节点的指针(后向指针)。
level[].forward表示单层的后向指针。
level[].span表示当前的指针跨越了多少个节点。

总结下 redis 针对 skiplist 做出的 3 点调整:

  • 数据不允许重复。
  • 在比较时,不仅比较分数(相当于 skiplist 的 key),还比较数据本身。在 Redis 的 skiplist 实现中,数据本身的内容唯一标识这份数据,而不是由 key 来唯一标识。另外,当多个元素分数相同的时候,还需要根据数据内容来进字典排序。
  • 有一个后向指针,所有第一层链表是一个双向链表。

Redis Zset 采用 skiplist 而不是平衡树的原因

扩展一下,看看作者是怎么说的:

  1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

    也不是非常耗费内存,实际上取决于生成层数函数里的概率 p,取决得当的话其实和平衡树差不多。

  2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

    因为有序集合经常会进行 ZRANGE 或 ZREVRANGE 这样的范围查找操作,跳表里面的双向链表可以十分方便地进行这类操作。

  3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

    实现简单,ZRANK 操作还能达到 O(logN) 的时间复杂度。

https://juejin.im/post/5e3409576fb9a02ffc376a80

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论