幸运蛋蛋pc开奖
这篇文章主要介绍了Redis SCAN命令实现有限保证的原理,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值 ,需要的朋友可以参考下

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

这是如何实现的呢,先从Redis中的?#20540;鋎ict开始。Redis的数据库是使用dict作为底层实现的。

?#20540;?#25968;据类型

Redis中的?#20540;?#30001;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;

?#20540;?#30001;两个哈希表dictht构成,主要用做rehash,平常主要使用ht[0]哈希表。

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

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

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

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

rehash的问题

?#20540;鋜ehash时会使用两个哈希表,首先为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?#20445;?#20854;中的元素已经在ht[0]中的bucket0中遍历过,这就产生了重?#27425;?#39064;。
•缩小操作中,当返回游标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遍历?#20540;?#30340;源码在dict.c/dictScan,分两种情况,?#20540;?#19981;在进行rehash或者正在进行rehash。

不在进行rehash?#20445;?#28216;标是这样计算的:

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

当size为4?#20445;瑂izemask为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由小变大?#20445;?#25152;有原来的游标都能在大的哈希表中找到相应的位置,并且顺序一致,不会重复读取并?#20063;?#20250;遗漏。

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

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

所以,redis里rehash?#26377;?#21040;大?#20445;琒CAN命令不会重复也不会遗漏。而从大到小?#20445;?#26377;可能会造成重复但不会遗漏。

当正在进行rehash?#20445;?#28216;标计算过程:

  /* 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的不同位,?#20174;?#26631;在这些标志位是否为1。

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

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

所以正在rehash?#20445;?#26159;两个哈希表都遍历的,以避免遗漏的情况。

总结

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

最新资讯
阿里张勇:是技术让商业上的一些不可能变成可能

阿里张勇:是技术让商业

张勇提到,“口红一哥”李佳琦代表的是一?#20013;?#30340;销售方式
张勇谈新型制造?#24213;?#22411;:和合作伙伴一起找到门店价值

张勇谈新型制造?#24213;?#22411;

张勇表示,新消费方面,绝大部分甚至100%的商家都有感知,因
微博巩固行业领先地位 利润超华尔街预期

微博巩固行业领先地位

截至2019年9月底,微博月活跃用户达到4.97亿,日活跃用户
阿里网络18.4亿元认购美年健康股票 获4.06%股份

阿里网络18.4亿元认购

阿里网络以18.4亿元认购美年健康非公开发行股?#20445;?#33719;得4.
阿里张勇:双11一定不是一成不变的 创新是关键词

阿里张勇:双11一定不是

在张勇看来,从“一不小心?#22791;?#20102;双11后,没过?#25913;?#23601;看到一
迅雷Q3营收4380万美元 陈磊:云计算成收入增长驱动力

迅雷Q3营收4380万美元

迅雷第三季度营业收入为4380万美元。包括云计算在内的
最新文章
Linux下redis的安装与使用图文教程

Linux下redis的安装与

这篇文章主要介绍了Linux下redis的安装与使用,结合图
Redis利用Pipeline加速查询速度的方法

Redis利用Pipeline加

这篇文章主要给大家介绍了关于Redis利用Pipeline加速
谈谈Redis分布式锁的正确实现方法

谈谈Redis分布式锁的

这篇文章主要给大家介绍了关于Redis分布式锁的正确实
window手动操作清理redis缓存的技巧总结

window手动操作清理re

在本篇文章中小编给大家分享了关于window环境手动操作
redis与mongodb的区别总结

redis与mongodb的区别

在本篇文章里小编给大家分享的是关于redis与mongodb的
使用Redis实现延时任务的解决方案

使用Redis实现延时任

这篇文章主要介绍了使用Redis实现延时任务的解决方案,
幸运蛋蛋pc开奖 黑龙江时时彩开奖号码 一个解密游戏爱丽丝 下载决战2019二八杠 七码后二倍投 鸿祥娱乐下载 峰人开心农场怎么样 对刷套利稳赚不赔 手机上捕鱼赢钱技巧 竞彩足球混合过关规则 电子游戏平台网址大全