详解Redis SCAN命令实现有限保证的原理

SCAN命令可以为用户保证:从完整遍历开始直到完整遍历结束期间,一直存在于数据集内的所有元素都会被完整遍历返回,但是同一个元素可能会被返回多次。如果一个元素是在迭代过程中被添加到数据集的,又或者是在迭代过程中从数据集中被删除的,那么这个元素可能会被返回,也可能不会返回。

这是如何实现的呢,先从Redis中的字典dict开始。Redis的数据库是使用dict作为底层实现的。

字典数据类型

Redis中的字典由dict.h/dict结构表示:

typedef struct dict {
 dictType *type;
 void *privdata;
 dictht ht[2];
 long rehashidx; /* rehashing not in progress if rehashidx == -1 */
 unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
 dictEntry **table;
 unsigned long size;
 unsigned long sizemask;
 unsigned long used;
} dictht;

字典由两个哈希表dictht构成,主要用做rehash,平常主要使用ht[0]哈希表。

哈希表由一个成员为dictEntry的数组构成,size属性记录了数组的大小,used属性记录了已有节点的数量,sizemask属性的值等于size - 1。数组大小一般是2n,所以sizemask二进制是0b11111...,主要用作掩码,和哈希值一起决定key应该放在数组的哪个位置。

求key在数组中的索引的计算方法如下:

index = hash & d->ht[table].sizemask;

也就是根据掩码求低位值。

rehash的问题

字典rehash时会使用两个哈希表,首先为ht[1]分配空间,如果是扩展操作,ht[1]的大小为第一个大于等于2倍ht[0].used的2n,如果是收缩操作,ht[1]的大小为第一个大于等于ht[0].used的2n。然后将ht[0]的所有键值对rehash到ht[1]中,最后释放ht[0],将ht[1]设置为ht[0],新创建一个空白哈希表当做ht[1]。rehash不是一次完成的,而是分多次、渐进式地完成。

举个例子,现在将一个size为4的哈希表ht[0](sizemask为11, index = hash & 0b11)rehash至一个size为8的哈希表ht[1](sizemask为111, index = hash & 0b111)。

ht[0]中处于bucket0位置的key的哈希值低两位为00,那么rehash至ht[1]时index取低三位可能为000(0)和100(4)。也就是ht[0]中bucket0中的元素rehash之后分散于ht[1]的bucket0与bucket4,以此类推,对应关系为:

 ht[0] -> ht[1]
 ----------------
  0 -> 0,4
  1 -> 1,5
  2 -> 2,6
  3 -> 3,7

如果SCAN命令采取0->1->2->3的顺序进行遍历,就会出现如下问题:

•扩展操作中,如果返回游标1时正在进行rehash,ht[0]中的bucket0中的部分数据可能已经rehash到ht[1]中的bucket[0]或者bucket[4],在ht[1]中从bucket1开始遍历,遍历至bucket4时,其中的元素已经在ht[0]中的bucket0中遍历过,这就产生了重复问题。
•缩小操作中,当返回游标5,但缩小后哈希表的size只有4,如何重置游标?

SCAN的遍历顺序

SCAN命令的遍历顺序,可以举一个例子看一下:

127.0.0.1:6379[3]> keys *
1) "bar"
2) "qux"
3) "baz"
4) "foo"
127.0.0.1:6379[3]> scan 0 count 1
1) "2"
2) 1) "bar"
127.0.0.1:6379[3]> scan 2 count 1
1) "1"
2) 1) "foo"
127.0.0.1:6379[3]> scan 1 count 1
1) "3"
2) 1) "qux"
 2) "baz"
127.0.0.1:6379[3]> scan 3 count 1
1) "0"
2) (empty list or set)

可以看出顺序是0->2->1->3,很难看出规律,转换成二进制观察一下:

00 -> 10 -> 01 -> 11

二进制就很明了了,遍历采用的顺序也是加法,但每次是高位加1的,也就是从左往右相加、从高到低进位的。

SCAN源码

SCAN遍历字典的源码在dict.c/dictScan,分两种情况,字典不在进行rehash或者正在进行rehash。

不在进行rehash时,游标是这样计算的:

m0 = t0->sizemask;
// 将游标的umask位的bit都置为1
v |= ~m0;
// 反转游标
v = rev(v);
// 反转后+1,达到高位加1的效果
v++;
// 再次反转复位
v = rev(v);

当size为4时,sizemask为3(00000011),游标计算过程:

   v |= ~m0 v = rev(v) v++  v = rev(v)
00000000(0) -> 11111100 -> 00111111 -> 01000000 -> 00000010(2)
00000010(2) -> 11111110 -> 01111111 -> 10000000 -> 00000001(1)
00000001(1) -> 11111101 -> 10111111 -> 11000000 -> 00000011(3)
00000011(3) -> 11111111 -> 11111111 -> 00000000 -> 00000000(0)

遍历size为4时的游标状态转移为0->2->1->3。

同理,size为8时的游标状态转移为0->4->2->6->1->5->3->7,也就是000->100->010->110->001->101->011->111。

再结合前面的rehash:

  ht[0] -> ht[1]
  ----------------
   0  ->  0,4
   1  ->  1,5
   2  ->  2,6
   3  ->  3,7

可以看出,当size由小变大时,所有原来的游标都能在大的哈希表中找到相应的位置,并且顺序一致,不会重复读取并且不会遗漏。

当size由大变小的情况,假设size由8变为了4,分两种情况,一种是游标为0,2,1,3中的一种,此时继续读取,也不会遗漏和重复。

但如果游标返回的不是这四种,例如返回了7,7&11之后变为了3,所以会从size为4的哈希表的bucket3开始继续遍历,而bucket3包含了size为8的哈希表中的bucket3与bucket7,所以会造成重复读取size为8的哈希表中的bucket3的情况。

所以,redis里rehash从小到大时,SCAN命令不会重复也不会遗漏。而从大到小时,有可能会造成重复但不会遗漏。

当正在进行rehash时,游标计算过程:

  /* Make sure t0 is the smaller and t1 is the bigger table */
    if (t0->size > t1->size) {
      t0 = &d->ht[1];
      t1 = &d->ht[0];
    }
    m0 = t0->sizemask;
    m1 = t1->sizemask;
    /* Emit entries at cursor */
    if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
    de = t0->table[v & m0];
    while (de) {
      next = de->next;
      fn(privdata, de);
      de = next;
    }
    /* Iterate over indices in larger table that are the expansion
     * of the index pointed to by the cursor in the smaller table */
    do {
      /* Emit entries at cursor */
      if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
      de = t1->table[v & m1];
      while (de) {
        next = de->next;
        fn(privdata, de);
        de = next;
      }
      /* Increment the reverse cursor not covered by the smaller mask.*/
      v |= ~m1;
      v = rev(v);
      v++;
      v = rev(v);
      /* Continue while bits covered by mask difference is non-zero */
    } while (v & (m0 ^ m1));

算法会保证t0是较小的哈希表,不是的话t0与t1互换,先遍历t0中游标所在的bucket,然后再遍历较大的t1。

求下一个游标的过程基本相同,只是把m0换成了rehash之后的哈希表的m1,同时还加了一个判断条件:

v & (m0 ^ m1)

size4的m0为00000011,size8的m1为00000111,m0 ^ m1取值为00000100,即取二者mask的不同位,看游标在这些标志位是否为1。

假设游标返回了2,并且正在进行rehash,此时size由4变成了8,二者mask的不同位是低第三位。

首先遍历t0中的bucket2,然后遍历t1中的bucket2,公式计算出的下一个游标为6(00000110),低第三位为1,继续循环,遍历t1中的bucket6,然后计算游标为1,结束循环。

所以正在rehash时,是两个哈希表都遍历的,以避免遗漏的情况。

总结

以上所述是小编给大家介绍的Redis SCAN命令实现有限保证的原理,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

(0)

相关推荐

  • Redis中scan命令的深入讲解

    前言 熟悉Redis的人都知道,它是单线程的.因此在使用一些时间复杂度为O(N)的命令时要非常谨慎.可能一不小心就会阻塞进程,导致Redis出现卡顿. 有时,我们需要针对符合条件的一部分命令进行操作,比如删除以test_开头的key.那么怎么获取到这些key呢?在Redis2.8版本之前,我们可以使用keys命令按照正则匹配得到我们需要的key.但是这个命令有两个缺点: 没有limit,我们只能一次性获取所有符合条件的key,如果结果有上百万条,那么等待你的就是"无穷无尽"的字符串输出

  • Redis中Scan命令的基本使用教程

    前言 Redis中有一个经典的问题,在巨大的数据量的情况下,做类似于查找符合某种规则的Key的信息,这里就有两种方式, 一是keys命令,简单粗暴,由于Redis单线程这一特性,keys命令是以阻塞的方式执行的,keys是以遍历的方式实现的复杂度是 O(n),Redis库中的key越多,查找实现代价越大,产生的阻塞时间越长. 二是scan命令,以非阻塞的方式实现key值的查找,绝大多数情况下是可以替代keys命令的,可选性更强 以下写入100000条key***:value***格式的测试数据(

  • php redis扩展支持scan命令实现方法

    在使用阿里云的kvstore的时候,刚开始是属于公测,不收费,后来要成商业模式,收费了,8块钱一小时,太贵了,于是想到了删除部分无用的数据,但是数据量过于庞大,又不是使用keys * 来匹配(使用keys * 会直接把你redis卡死的),后期了解到了scan可以游标的找到所有的keys,于是开始捣鼓(发现我好多废话).. 开干.. [codesyntax lang="python"] # git clone https://github.com/phpredis/phpredis #

  • redis 用scan指令 代替keys指令(详解)

    众所周知,当redis中key数量越大,keys 命令执行越慢,而且最重要的会阻塞服务器,对单线程的redis来说,简直是灾难,终于找到了替代命令scan. SCAN cursor [MATCH pattern] [COUNT count] SCAN 命令及其相关的 SSCAN 命令. HSCAN 命令和 ZSCAN 命令都用于增量地迭代(incrementally iterate)一集元素(a collection of elements): SCAN 命令用于迭代当前数据库中的数据库键. S

  • 详解Redis SCAN命令实现有限保证的原理

    SCAN命令可以为用户保证:从完整遍历开始直到完整遍历结束期间,一直存在于数据集内的所有元素都会被完整遍历返回,但是同一个元素可能会被返回多次.如果一个元素是在迭代过程中被添加到数据集的,又或者是在迭代过程中从数据集中被删除的,那么这个元素可能会被返回,也可能不会返回. 这是如何实现的呢,先从Redis中的字典dict开始.Redis的数据库是使用dict作为底层实现的. 字典数据类型 Redis中的字典由dict.h/dict结构表示: typedef struct dict { dictTy

  • 详解Redis命令和键_动力节点Java学院整理

    Redis命令用于在redis服务器上执行某些操作. 要在Redis服务器上运行的命令,需要一个Redis客户端. Redis客户端在Redis的包,这已经我们前面安装使用过了. 语法 Redis客户端的基本语法如下: $redis-cli 例子 下面举例说明如何使用Redis客户端. 要启动redis客户端,打开终端,输入命令Redis命令行:redis-cli.这将连接到本地服务器,现在就可以运行各种命令了. $redis-cli redis 127.0.0.1:6379> redis 12

  • 详解redis数据结构之sds

    详解redis数据结构之sds 字符串在redis中使用非常广泛,在redis中,所有的数据都保存在字典(Map)中,而字典的键就是字符串类型,并且对于很大一部分字典值数据也是又字符串组成的.以下是sds的具体存储结构: 从图中可以看出,sds的属性有三个:len.free和buf数组.这里len字段是用来保存sds字符串中所包含字符数目的,free字段则是用来保存buf数组中空余的部分的长度的,而buf数组则是实际用来保存字符串的.比如如下结构保存了"Hello World!"这个字

  • 详解Redis 数据类型

    Redis支持五种数据类型:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted set:有序集合). String(字符串) string 是 redis 最基本的类型,你可以理解成与 Memcached 一模一样的类型,一个 key 对应一个 value. string 类型是二进制安全的.意思是 redis 的 string 可以包含任何数据.比如jpg图片或者序列化的对象. string 类型是 Redis 最基本的数据类型,string 类

  • 详解Redis的慢查询日志

    Redis慢查询日志帮助开发和运维人员定位系统存在的慢操作.慢查询日志就是系统在命令执行前后计算每条命令的执行时间,当超过预设阀值,就将这条命令的相关信息(慢查询ID,发生时间戳,耗时,命令的详细信息)记录下来. Redis客户端一条命令分为如下四部分执行: 需要注意的是,慢查询日志只是统计步骤3)执行命令的时间,所以慢查询并不代表客户端没有超时问题.需要注意的是,慢查询日志只是统计步骤3)执行命令的时间,所以慢查询并不代表客户端没有超时问题. 一.慢查询的配置参数: 慢查询的预设阀值 slow

  • 详解redis数据结构之压缩列表

     详解redis数据结构之压缩列表 redis使用压缩列表作为列表键和哈希键的底层实现之一.当一个列表键只包含少量的列表项,并且每个列表项都是由小整数值或者是短字符串组成,那么redis就会使用压缩列表存储列表项:同理,当一个哈希表包含的键值对都是由小整数值或者是短字符串组成,并且存储的键值对数目不多时,redis也会使用压缩列表来存储哈希表.以下是压缩列表存储结构: zlbytes长度为4个字节,记录了整个压缩列表所占用的字节数 zltail长度为4个字节,记录了压缩列表起始位置到压缩列表尾节

  • Git 命令详解及常用命令整理

    Git 命令详解及常用命令 Git作为常用的版本控制工具,多了解一些命令,将能省去很多时间,下面这张图是比较好的一张,贴出了看一下: 关于git,首先需要了解几个名词,如下: Workspace //工作区 Index / Stage //暂存区 Repository //仓库区(或本地仓库) Remote //远程仓 一.新建代码库 // 在当前目录新建一个Git代码库 $ git init // 新建一个目录,将其初始化为Git代码库 $ git init [project-name] //

  • linux 中的ls命令参数详解及ls命令的使用实例

    一.ls命令参数详解 可以通过阅读 ls 的说明书页(man ls)来获得选项的完整列表. -a – 全部(all).列举目录中的全部文件,包括隐藏文件(.filename).位于这个列表的起首处的 .. 和 . 依次是指父目录和你的当前目录. -l – 长(long).列举目录内容的细节,包括权限(模式).所有者.组群.大小.创建日期.文件是否是到系统其它地方的链接,以及链接的指向. -F – 文件类型(File type).在每一个列举项目之后添加一个符号.这些符号包括:/ 表明是一个目录:

  • 详解git merge命令应用的三种情景

    一.git merge 命令应用的三种情景 1.1 "快进"(无冲突) master分支 假设现在只有一个默认的 master 分支,并提交了3次,B0.B1和B2都是提交对象. 首先要清楚,每次产生的提交对象会包含一个指向上次提交对象(父对象)的指针,所以图中B0.B1和B2之间的箭头是指针指向父对象的意思,真正的提交顺序还是B0到B1再到B2.同时 master 指针指向最新的提交B2. 另外Git中还有一个名为 HEAD 的特殊指针,它是一个指针,指向当前所在的本地分支(可以将

  • 详解Linux time 命令的使用

    1.命令简介 time 用于统计命令执行所消耗的时间及相关系统资源等信息.time 可以显示的资源有四大项,分别是: Time resources Memory resources IO resources Command info 2.命令格式 time [options] command [arguments...] 3. 选项说明 -f FORMAT, --format=FORMAT:使用指定格式输出.如果没有指定输出格式,采用环境变量 TIME 指定的格式 -p, --portabili

随机推荐

其他