怎么在Redis中使用SCAN命令实现有限保证

共计 4282 个字符，预计需要花费 11 分钟才能阅读完成。

自动写代码机器人，免费开通

这篇文章将为大家详细讲解有关怎么在 Redis 中使用 SCAN 命令实现有限保证，文章内容质量较高，因此丸趣 TV 小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

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 = 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 命令实现有限保证就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。

向 AI 问一下细节