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

  • 时间:
  • 浏览:19

SCAN号令能够为用户包管:从完全遍历起头曲到完全遍历完毕时期,1曲存正在于数据散内的一切元素城市被完全遍历前往,可是统一个元素能够会被前往屡次。若是1个元素是正在迭代进程中被增加到数据散的,又或是正在迭代进程中从数据集合被删除的,那末那个元素能够会被前往,也能够没有会前往。

那是若何真现的呢,先从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 == ⑴ */
 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]哈希表。

哈希表由1个成员为dictEntry的数组组成,size属性记载了数组的巨细,used属性记载了已有节面的数目,sizemask属性的值即是size - 1。数组巨细1般是2n,以是sizemask2进造是0b11111...,次要用做掩码,战哈希值1起决议key应当放正在数组的哪一个地位。

供key正在数组中的索引的计较办法以下:

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

也便是按照掩码供低位值。

rehash的成绩

字典rehash时会利用两个哈希表,起首为ht[1]分派空间,若是是扩大操纵,ht[1]的巨细为第1个年夜于即是2倍ht[0].used的2n,若是是膨胀操纵,ht[1]的巨细为第1个年夜于即是ht[0].used的2n。然后将ht[0]的一切键值对rehash到ht[1]中,最初开释ht[0],将ht[1]设置为ht[0],新创立1个空缺哈希表当作ht[1]。rehash没有是1次完成的,而是分屡次、渐进式天完成。

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

ht[0]中处于bucket0地位的key的哈希值低两位为00,那末rehash至ht[1]时index与低3位能够为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号令的遍历挨次,能够举1个例子看1下:

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,很好看出纪律,转换成2进造视察1下:

00 -> 10 -> 01 -> 11

2进造便很了然了,遍历采取的挨次也是减法,但每次是下位减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由小变年夜时,一切本来的游标皆能正在年夜的哈希表中找到响应的地位,而且挨次1致,没有会反复读与而且没有会漏掉。

当size由年夜变小的状况,假定size由8变成了4,分两种状况,1种是游标为0,2,1,3中的1种,此时持续读与,也没有会漏掉战反复。

但若是游标前往的没有是那4种,比方前往了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。

供下1个游标的进程根本不异,只是把m0换成了rehash以后的哈希表的m1,同时借减了1个判定前提:

v & (m0 ^ m1)

size4的m0为00000011,size8的m1为00000111,m0 ^ m1与值为00000100,即与2者mask的差别位,看游标正在那些标记位是不是为1。

假定游标前往了2,而且正正在停止rehash,此时size由4酿成了8,2者mask的差别位是低第3位。

起首遍历t0中的bucket2,然后遍历t1中的bucket2,公式计较出的下1个游标为6(00000110),低第3位为1,持续轮回,遍历t1中的bucket6,然后计较游标为1,完毕轮回。

以是正正在rehash时,是两个哈希表皆遍历的,以免漏掉的状况。

总结

以上所述是小编给各人引见的Redis SCAN号令真现无限包管的本理,期望对各人有所帮忙,若是各人有任何疑问请给我留行,小编会实时复兴各人的。正在此也十分感激各人对剧本之家网站的撑持!
若是您以为本文对您有帮忙,欢送转载,烦请说明出处,开开!