Redis源码剖析与实战
蒋德钧
中科院计算所副研究员
新⼈⾸单¥59.9
2088 人已学习
课程目录
已更新 7 讲 / 共 33 讲
0/4登录后,你可以任选4讲全文学习。
课前导读 (2讲)
开篇词 | 阅读Redis源码能给你带来什么?
免费
01 | 带你快速攻略Redis源码的整体架构
数据结构模块 (5讲)
02 | 键值对中字符串的实现,用char*还是结构体?
03 | 如何实现一个性能优异的Hash表?
04 | 内存友好的数据结构该如何细化设计?
05 | 有序集合为何能同时支持点查询和范围查询?
06 | 从ziplist到quicklist,再到listpack的启发
Redis源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

05 | 有序集合为何能同时支持点查询和范围查询?

你好,我是蒋德钧。
有序集合(Sorted Set)是 Redis 中一种重要的数据类型,它本身是集合类型,同时也可以支持集合中的元素带有权重,并按权重排序。
而曾经就有一位从事 Redis 开发的同学问我:为什么 Sorted Set 能同时提供以下两种操作接口,以及它们的复杂度分别是 O(logN)+M 和 O(1) 呢?
ZRANGEBYSCORE:按照元素权重返回一个范围内的元素。
ZSCORE:返回某个元素的权重值。
实际上,这个问题背后的本质是:为什么 Sorted Set 既能支持高效的范围查询,同时还能以 O(1) 复杂度获取元素权重值?
这其实就和 Sorted Set 底层的设计实现有关了。Sorted Set 能支持范围查询,这是因为它的核心数据结构设计采用了跳表,而它又能以常数复杂度获取元素权重,这是因为它同时采用了哈希表进行索引。
那么,你是不是很好奇,Sorted Set 是如何把这两种数据结构结合在一起的?它们又是如何进行协作的呢?今天这节课,我就来给你介绍下 Sorted Set 采用的双索引的设计思想和实现。理解和掌握这种双索引的设计思想,对于我们实现数据库系统是具有非常重要的参考价值的。
好,接下来,我们就先来看看 Sorted Set 的基本结构。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/1000字
划线
笔记
复制
该试读文章来自付费专栏《Redis源码剖析与实战》,如需阅读全部文章,
请订阅文章所属专栏新⼈⾸单¥59.9
立即订阅
登录 后留言

精选留言(7)

  • Kaito
    1、ZSet 当数据比较少时,采用 ziplist 存储,每个 member/score 元素紧凑排列,节省内存

    2、当数据超过阈值(zset-max-ziplist-entries、zset-max-ziplist-value)后,转为 hashtable + skiplist 存储,降低查询的时间复杂度

    3、hashtable 存储 member->score 的关系,所以 ZSCORE 的时间复杂度为 O(1)

    4、skiplist 是一个「有序链表 + 多层索引」的结构,把查询元素的复杂度降到了 O(logN),服务于 ZRANGE/ZREVRANGE 这类命令

    5、skiplist 的多层索引,采用「随机」的方式来构建,也就是说每次添加一个元素进来,要不要对这个元素建立「多层索引」?建立「几层索引」?都要通过「随机数」的方式来决定

    6、每次随机一个 0-1 之间的数,如果这个数小于 0.25(25% 概率),那就给这个元素加一层指针,持续随机直到大于 0.25 结束,最终确定这个元素的层数(层数越高,概率越低,且限制最多 64 层,详见 t_zset.c 的 zslRandomLevel 函数)

    7、这个预设「概率」决定了一个跳表的内存占用和查询复杂度:概率设置越低,层数越少,元素指针越少,内存占用也就越少,但查询复杂会变高,反之亦然。这也是 skiplist 的一大特点,可通过控制概率,进而控制内存和查询效率

    8、skiplist 新插入一个节点,只需修改这一层前后节点的指针,不影响其它节点的层数,降低了操作复杂度(相比平衡二叉树的再平衡,skiplist 插入性能更优)

    关于 Redis 的 ZSet 为什么用 skiplist 而不用平衡二叉树实现的问题,原因是:

    - skiplist 更省内存:25% 概率的随机层数,可通过公式计算出 skiplist 平均每个节点的指针数是 1.33 个,平衡二叉树每个节点指针是 2 个(左右子树)
    - skiplist 遍历更友好:skiplist 找到大于目标元素后,向后遍历链表即可,平衡树需要通过中序遍历方式来完成,实现也略复杂
    - skiplist 更易实现和维护:扩展 skiplist 只需要改少量代码即可完成,平衡树维护起来较复杂

    课后题:在使用跳表和哈希表相结合的双索引机制时,在获得高效范围查询和单点查询的同时,你能想到有哪些不足之处么?

    这种发挥「多个数据结构」的优势,来完成某个功能的场景,最大的特点就是「空间换时间」,所以内存占用多是它的不足。

    不过也没办法,想要高效率查询,就得牺牲内存,鱼和熊掌不可兼得。

    不过 skiplist 在实现时,Redis 作者应该也考虑到这个问题了,就是上面提到的这个「随机概率」,Redis 后期维护可以通过调整这个概率,进而达到「控制」查询效率和内存平衡的结果。当然,这个预设值是固定写死的,不可配置,应该是 Redis 作者经过测试和权衡后的设定,我们这里只需要知晓原理就好。
    2021-08-05
    15
  • skiplist + hashmap 实现的有序集合和常规的 double linked list + hashmap 所实现的 LRU 有些类似,都是使用链表结构进行核心的流程运转,hashmap 则是辅助链表使得能够在 O(1) 的时间复杂度内获取元素。这种组合式的数据结构还是很值得借鉴的。

    leveldb 中也使用了 skiplist 来实现了 Memory Write Buffer,并且使用 CAS 操作实现了一个无锁的 skiplist,感兴趣的小伙伴也可以看看。实现上都差不多,都是使用 array + random 的方式存储和开辟新的层节点。
    2021-08-05
    1
  • Milittle
    补一条:如果用ziplist存储sorted set,那么zscore也是遍历查询的,这个可以从:void zaddCommand(client *c)一路看下去,这里说一点感想:大家如果不知道一个数据结构的创建,可以从redisCommandTable里面的命令函数一路看下去,可以找到不少东西。
    2021-08-06
  • 曾轼麟
    首先回答老师提出的问题,索引机制有哪些不足之处?首先我们知道(zset = dict + skiplist),那么可能会存在以下几个问题:
    1、首先zset空间利用肯定是一大不足之处,毕竟是空间换时间
    2、由于引入了dict,而dict底层是链式hash,当发生扩容的时候,对于整个zset其实是一种开销。
    3、当zset进行大范围“有序”删除的时候开销会很大,跳表本身范围删除可以很快,本质可以只修改指针。但是当跳表删除后,还需要同步删除dict里面的数据,这时就会导致大开销了。(此外删除的时候有可能也会触发缩容rehash)


    每次阅读老师的文章,都能有意外收获,本次阅读我得出以下的几个观点和结论:
    1、redis作为一款优化到极致的中间件,不会单纯使用一种数据类型去实现一个功能,而会根据当前的情况选择最合适的数据结构,比如zset就是dict + skiplist,甚至当元素较少的时候zsetAdd方法会优先选择ziplist而不直接使用skiplist,以到达节约内存的效果(当小key泛滥的时候很有效果),当一种数据结构存在不足的情况下,可以通过和其它数据结构搭配来弥补自身的不足(软件设计没有银弹,只有最合适)。
    2、redis仰仗c语言指针的特性,通过层高level数组实现的skiplist从内存和效率上来说都是非常优秀的,我对比了JDK的ConcurrentSkipListMap的实现(使用了大量引用和频繁的new操作),指针的优势无疑显现出来了
    3、很多时候让我们感到惊艳的功能设计,可能本质只是一个很简单的原理,比如skiplist的随机率层高。既保证每层的数量相对为下一层的一半,又保证了代码执行效率


    最后借着评论我提出一个我发现的疑问:
    我本次在阅读redis skiplist源码的时候,发现skiplist的最大层高上限,曾经在2020-02-02被 Murillo 大神修改过,从64修改成了32,但是我一直无法理解这一目的,在网上也没找到相应的答案,想问一下这个修改是出于什么样的目的呢?
    2021-08-06
  • 胡玲玲
    评论区都是神仙- -
    2021-08-05
  • 冷峰
    双索引要使用更多的内存,只是以内存换时间
    2021-08-05
  • Milittle
    1. 多浪费了存储空间。
    2. 增加了编码的难度。
    3. 有可能会导致一个数据结构的数据更新了,但是另外一个没有更新的问题(可能概率较小,但是也有可能)
    2021-08-05
收起评论
7
返回
顶部