Redis SCAN 命令实现了有限保证的原则

terry 2年前 (2023-09-26) 阅读数 52 #数据库

SCAN 命令可以向用户保证：从一次全量遍历开始到一次全量遍历结束，数据集中一直存在的所有元素都将被完全遍历。并返回，但同一个元素可以多次返回。如果在迭代期间将元素添加到数据集或在迭代期间从数据集中删除元素，则可能会或可能不会返回该元素。

如何实施？让我们从 Redis 中的字典听写开始。 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;

字典由两个dicttht哈希表组成，主要用于重新哈希。通常主要使用哈希表ht[0]。

哈希表由一个数组组成，其成员为 dictEntry。 size属性记录了数组的大小，使用的属性是现有节点的数量，sizemask属性的值等于size - 1。数组的大小一般为2n，所以sizemask的二进制值为0b11111 ... ，主要用作掩码，与哈希值一起指定键应放置在字段中的位置。

查找数组中关键索引的计算方法如下：

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

这意味着根据 mask 查找低值。

哈希问题

字典哈希使用两个哈希表。首先，为ht[1]分配空间。如果是扩容操作，ht[1]的大小大于等于2倍第一个ht[0].used 2n，如果是收缩操作，ht[1]的大小是第一个2n大于或等于 ht[0].used 。然后将所有键值对 ht[0] 重新制作为 ht[1] ，最后释放 ht[0] ，将 ht[1] 设置为 ht[0] ，并创建一个新的空哈希表 ht[1] 。 Rehash并不是一次全部完成，而是分多次、依次完成。

现在，例如，将大小为 4 的哈希表 ht[0]（sizemask 为 11，index = hash & 0b11）迭代到大小为 8 的哈希表 ht[1]（sizemask 为 111，index = hash & 0b11） 0b111）。

ht[0]中第0段的key的哈希值低两位是00，所以翻转到ht[1]时，索引的低三位可以是000(0)和100 （4）。这意味着重新处理后，ht[0]中的bucket0中的元素分散在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处正在进行刷新，segment0中的一些数据会在ht[0]中返回，可能已经被处理到bucket[in ht[1] 0]或bucket[4]中，从ht[1]中的bucket1开始遍历，当转到bucket4中的元素时它已经在ht[0]中的bucket0中被遍历过，这会导致重复问题。
•收缩操作时返回游标5，但收缩后哈希表大小仅为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 中。有两种情况：字典不被重新散列或者被重新散列。

不进行重新处理时，光标计算过程如下：

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

当尺寸为4时，尺寸掩码为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)

光标状态的转变当过渡大小为 4 时，为 0->2->1->3。

同样，当size为8时，光标状态变为0->4->2->6->1->5->3->7，所以000->100->010->110 ->001->101->011->111。

结合之前的迭代：

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

，可以看出，当尺寸由小变大时，所有原来的游标都能在大哈希表中找到对应的位置，而且顺序是一致的，并且有不会重复阅读。抓住它，不要错过它。

当尺寸由大变小时，假设尺寸由8变4，有两种情况。一是光标为0、2、1、3之一，此时不会再继续读取。会出现遗漏和重复的情况。

但是如果游标不返回这四种类型，比如返回7、7、11，那么就会变成3，所以会继续从大小为4的bucket3哈希表走，bucket3包含表中大小为8的bucket3和bucket7的哈希，因此大小为8的哈希表中的bucket3会被重复读取。

所以当redis中的rehash从小到大增长时，SCAN命令不会重复或遗漏。从大到小，可以有重复，但不能有遗漏。

进行重新哈希时，游标计算过程：

  /* 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处游标所在的段，然后遍历更大的哈希表。 t1。

查找下一个游标的过程基本相同，只是将m0替换为rehash后的哈希表的m1，并且还增加了一个判断条件：

v & (m0 ^ m1)

size4 m0为00000011，m1 size8为00000111，m0^m1的值为00000100，即取两个掩码的不同位，看这些指示位中光标是否为1。

假设光标返回到 2 并且正在进行恢复。此时大小从4变为8。两个掩码的差异位是低第三位。

首先在 t0 中传递 Bucket2，然后在 t1 中传递 Bucket 2。公式计算出的下一个游标为6（00000110），第三个最低位为1。继续循环，在t1中传入bucket6，然后计算出游标为1。结束循环。

因此，当执行重新哈希时，会遍历两个哈希表以避免遗漏。