您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis的scan命令

时间:2020-02-25 13:33:30  来源:  作者:

那个深夜,我登上了公司的服务器,在 redis 命令行里敲入 keys* 后,线上开始报警,服务瞬间被卡死。

因为不会Redis的scan命令,我被开除了

 


图片来自 Pexels

我只能举起双手,焦急地等待几千万 key 被慢慢扫描,束手无策万念俱灰的时候,我收到了 Leader 的短信:你明天不用来上班了。

虽然上面是我的臆想,事实上很多公司的运维也会禁用这些命令,来防止开发出错。

但我在群里依然看到有同学在问“为什么 Redis 不能用 keys?我觉得挺好的呀”时,为了不让上面的情况发生,我决定写下这篇文章。

如何才能优雅地遍历 Redis?作为一种可以称为数据库的组件,这是多么理所应当的要求。

终于,Redis 在 2.8.0 版本新增了众望所归的 scan 操作,从此再也不用担心敲入了 keys*,然后等着定时炸弹的引爆。

学会使用 scan 并不困难,那么问题又来了,它是如何遍历的?当遍历过程中加入了新的 key,当遍历过程中发生了扩容,Redis 是如何解决的?

抱着深入学习的态度,以及为了能够将来在面试官面前谈笑风生,让我们一起来借此探索 Redis 的设计原理。

开门见山,首先让我们来总结一下 scan 的优缺点。

优点如下:

  • 提供键空间的遍历操作,支持游标,复杂度 O(1),整体遍历一遍只需要 O(N)。
  • 提供结果模式匹配。
  • 支持一次返回的数据条数设置,但仅仅是个 hints,有时候返回更多。
  • 弱状态,所有状态只需要客户端维护一个游标。

缺点如下:

  • 无法提供完整的快照遍历,也就是中间如果有数据修改,可能有些涉及改动的数据遍历不到。
  • 每次返回的数据条数不一定,极度依赖内部实现。
  • 返回的数据可能有重复,应用层需要能够处理重入逻辑。

所以 scan 是一个能够满足需求,但也不是完美无瑕的命令。下面来介绍一下原理,scan 到底是如何实现的?

scan,hscan 等命令主要都是借用了通用的 scan 操作函数:scanGenericCommand 。

scanGenericCommand 函数分为以下几步:

  • 解析 count 和 match 参数,如果没有指定 count,默认返回 10 条数据。
  • 开始迭代集合,如果是 key 保存为 ziplist 或者 intset,则一次性返回所有数据,没有游标(游标值直接返回 0)。

由于 Redis 设计,只有数据量比较小的时候才会保存为 ziplist 或者 intset,所以此处不会影响性能。

游标在保存为 hash 的时候发挥作用,具体入口函数为 dictScan,下文详细描述。

  • 根据 match 参数过滤返回值,并且如果这个键已经过期也会直接过滤掉(Redis 中键过期之后并不会立即删除)。

当迭代一个哈希表时,存在三种情况:

  • 从迭代开始到结束,哈希表没有进行 rehash。
  • 从迭代开始到结束,哈希表进行了 rehash,但是每次迭代时,哈希表要么没开始 rehash,要么已经结束了 rehash。
  • 从迭代开始到结束,某次或某几次迭代时哈希表正在进行 rehash。

在这三种情况之下,sacn 是如何实现的?首先需要知道的前提是:Redis 中进行 rehash 扩容时会存在两个哈希表,ht[0] 与 ht[1],rehash 是渐进式的,即不会一次性完成。

新的键值对会存放到 ht[1] 中并且会逐步将 ht[0] 的数据转移到 ht[1]。全部 rehash 完毕后,ht[1] 赋值给 ht[0] 然后清空ht[1]。

模拟问题

①迭代过程中,没有进行 rehash

这个过程比较简单,一般来说只需要最简单粗暴的顺序迭代就可以了,这种情况下没什么好说的。

②迭代过程中,进行过 rehash

但是字典的大小是能够进行自动扩容的,我们不得不考虑以下两个问题:

第一,假如字典扩容了,变成 2 倍的长度,这种情况下,能够保证一定能遍历所有最初的 key,但是却会出现大量重复。

举个例子:比如当前的 key 数组大小是 4,后来变为 8 了。假如从下表 0,1,2,3 顺序扫描时,如果数组已经发生扩容。

那么前面的 0,1,2,3 slot 里面的数据会发生一部分迁移到对应的 4,5,6,7 slot 里面去,当扫描到 4,5,6,7 的 slot 时,无疑会出现值重复的情况。

需要知道的是,Redis 按如下方法计算一个当前 key 扩容后的 slot:hash(key)&(size-1)。

如图,当字典大小从 4 扩容到 8 时,原先在 0 slot 的数据会分散到 0(000) 与 4(100) 两个 slot,对应关系表如下:

因为不会Redis的scan命令,我被开除了

 

第二, 如果字典缩小了,比如从 16 缩小到 8, 原先 scan 已经遍历了 0,1,2,3 ,如果数组已经缩小。

这样后来迭代停止在 7 号 slot,但是 8,9,10,11 这几个 slot 的数据会分别合并到 0,1,2,3 里面去,从而 scan 就没有扫描出这部分元素出来,无法保证可用性。

③迭代过程中,正在进行 rehash

上面考虑的情况是,在迭代过程的间隙中,rehash 已经完成。那么会不会出现迭代进行中,切换游标时,rehash 也正在进行?当然可能会发生。

如果返回游标 1 时正在进行 rehash,那么 ht[0](扩容之前的表)中的 slot1 中的部分数据可能已经 rehash 到 ht[1](扩容之后的表)中的 slot1 或者 slot4。

此时必须将 ht[0] 和 ht[1] 中的相应 slot 全部遍历,否则可能会有遗漏数据,但是这么做好像也非常麻烦。

解决方法

为了解决以上两个问题,Redis 使用了一种称为:reverse binary iteration 的算法。

源码如下:

unsignedlongdictScan(dict*d,unsignedlongv,dictScanFunction*fn,void*privdata){if(!dictIsRehashing(d)){t0=(d->ht[0]);m0=t0->sizemask;/*Emitentriesatcursor*/while(de){fn(privdata,de);de=de->next;}}else{m0=t0->sizemask;m1=t1->sizemask;de=t0->table[v&m0];while(de){fn(privdata,de);de=de->next;}do{de=t1->table[v&m1];while(de){fn(privdata,de);de=de->next;}v=(((v|m0)+1)&~m0)|(v&m0);}while(v&(m0^m1));}v|=~m0;v=rev(v);v++;v=rev(v);returnv;}

一起来理解下核心源码,第一个 if,else 主要通过 dictIsRehashing 这个函数来判断是否正在 rehash。

sizemask 指的是字典空间长度,假如长度为 16,那么 sizemask 的二进制为 00001111。m0 代表当前字典的长度,v 代表游标所在的索引值。

接下来关注这个片段:

v|=~m0;v=rev(v);v++;v=rev(v);

这段代码初看好像有点摸不着头脑,怎么多次在多次 rev?我们来看下在字典长度从 4 rehash 到 8 时,scan 是如何迭代的。

当字典长度为 4 时,m0 等于 4,二进制表示为 00000011,那么 ~m0 为 11111100,v 初始值为 0,那么 v |=~m0为11111100。

接下来看图:

因为不会Redis的scan命令,我被开除了

 

可以看到,第一次 dictScan 后,游标从 0 变成了 2,四次遍历分别为 0→2→1→3,四个值都遍历到了。

在字典长度为 8 时,遍历情况如下:

因为不会Redis的scan命令,我被开除了

 

遍历顺序为:0→4→2→6→1→5→3→7。

是不是察觉了什么?遍历顺序是不是顺序是一致的?如果还没发现,不妨再来看看字典长度为 16 时的遍历情况,以及三次顺序的对比:

因为不会Redis的scan命令,我被开除了

 

让我们设想这么一个情况,字典的大小本身为 4,开始迭代,当游标刚迭代完 slot0 时,返回的下一个游标是 slot2。

此时发现字典的大小已经从 4 rehash 到 8,那么不妨继续从 size 为 8 的 hashtable 中 slot2 处继续迭代。

有人会说,不是把 slot4 遗漏掉了吗?注意之前所说的扩容方式:hash(key)&(size-1),slot0 和 slot4 的内容是相同的,巧妙地避开了重复,当然,更不会遗漏。

如果你看到这里,你可能会发出和我一样的感慨:我 X,这算法太牛 X 了。

没错,上面的算法是由 Pieter Noordhuis 设计实现的,Redis 之父 Salvatore Sanfilippo 对该算法的评价是“Hard to explain but awesome。”

字典扩大的情况没问题,那么缩小的情况呢?可以仿照着自己思考一下具体步骤。答案是可能会出现重复迭代,但是不会出现遗漏,也能够保证可用性。

迭代过程中,进行过 rehash 这种情况下的迭代已经比较完美地解决了,那么迭代过程中,正在进行 rehash 的情况是如何解决的呢?

我们继续看源码,之前提到过 dictIsRehashing 这个函数用来判断是否正在进行 rehash。

那么主要就是关注这段源码:

m0=t0->sizemask;m1=t1->sizemask;de=t0->table[v&m0];while(de){fn(privdata,de);de=de->next;}do{de=t1->table[v&m1];while(de){fn(privdata,de);de=de->next;}v=(((v|m0)+1)&~m0)|(v&m0);}while(v&(m0^m1));

m0 代表 rehash 前的字典长度,假设为 4,即 00000011,m1 代表 rehash 后的字典长度,假设为 8,即 00000111。

首先当前游标 &m0 可以得到较小字典中需要迭代的 slot 的索引,然后开始循环迭代。

然后开始较大字典的迭代,首先我们关注一下循环条件:

v&(m0^m1)

m0,m1 二者经过异或操作后的值为 00000100,可以看到只留下了最高位的值。

游标 v 与之做 & 操作,将其作为判断条件,即判断游标 v 在最高位是否还有值。

当高位为 0 时,说明较大字典已经迭代完毕。(因为较大字典的大小是较小字典的两倍,较大字典大小的最高位一定是 1)

到此为止,我们已经将 scan 的核心源码通读一遍了,相信很多其间的迷惑也随之解开。

不仅在写代码的时候更自信了,假如日后被面试官问起相关问题,那绝对可以趁机表现一番,想想还有点小激动。



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Tags: Redis  点击:(18)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  Tags: Redis  点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  Tags: Redis  点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  Tags: Redis  点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: Redis  点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  Tags: Redis  点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: Redis  点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  Tags: Redis  点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  Tags: Redis  点击:(77)  评论:(0)  加入收藏
Nginx来限制访问控制的方法有多种,nginx主要有2个模块控制,但是那些不支持自定义,非常死,在大多数场景下并不实用。今天分享一个:利用openresty+lua+redis 实现封杀频繁恶意访问I...【详细内容】
2021-08-12  Tags: Redis  点击:(119)  评论:(0)  加入收藏
▌简易百科推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Java识堂    Tags:Redis   点击:(18)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  富集云科技有限公司    Tags:Redis   点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  弈秋的美好生活    Tags:redis   点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  川石信息    Tags:Redis   点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  JavaEdge    Tags:Redis   点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  faesuite    Tags:Redis   点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  语霖    Tags:Redis   点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  深夜敲代码    Tags:Redis   点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  小李说IT    Tags:Redis   点击:(77)  评论:(0)  加入收藏
当查询Redis中没有的数据时,该查询会下沉到数据库层,同时数据库层也没有该数据,当这种情况大量出现或被恶意攻击时,接口的访问全部透过Redis访问数据库,而数据库中也没有这些数据...【详细内容】
2021-07-30  随便t    Tags:缓存穿透   点击:(91)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条