来自：指月 https://www.lixueduan.com

原文：https://www.lixueduan.com/post/redis/redis-scan/

主要分析了 Redis Scan 命令基本使用和具体实现，包括 Count 参数与 Scan 总耗时的关系，以及核心的逆二进制迭代算法分析。

1. 概述

由于 Redis 是单线程在处理用户的命令，而 Keys 命令会一次性遍历所有 Key，于是在 命令执行过程中，无法执行其他命令。这就导致如果 Redis 中的 key 比较多，那么 Keys 命令执行时间就会比较长，从而阻塞 Redis。

所以很多教程都推荐使用 Scan 命令来代替 Keys，因为 Scan 可以限制每次遍历的 key 数量。

Keys 的缺点：

  • 1）没有limit，我们只能一次性获取所有符合条件的key，如果结果有上百万条，那么等待你的就是“无穷无尽”的字符串输出。
  • 2）keys命令是遍历算法，时间复杂度是O(N)。如我们刚才所说，这个命令非常容易导致Redis服务卡顿。因此，我们要尽量避免在生产环境使用该命令。

相比于keys命令，Scan命令有两个比较明显的优势：

  • 1）Scan命令的时间复杂度虽然也是O(N)，但它是分次进行的，不会阻塞线程。
  • 2）Scan命令提供了 count 参数，可以控制每次遍历的集合数。

可以理解为 Scan 是渐进式的 Keys。

Scan 命令语法如下：

SCAN cursor [MATCH pattern] [COUNT count]
  • cursor - 游标。
  • pattern - 匹配的模式。
  • count - 指定每次遍历多少个集合。
    • 可以简单理解为每次遍历多少个元素
    • 根据测试，推荐 Count大小为 1W。

Scan 返回值为数组，会返回一个游标+一系列的 Key

大致用法如下：

SCAN命令是基于游标的，每次调用后，都会返回一个游标，用于下一次迭代。当游标返回0时，表示迭代结束。

第一次 Scan 时指定游标为 0，表示开启新的一轮迭代，然后 Scan 命令返回一个新的游标，作为第二次 Scan 时的游标值继续迭代，一直到 Scan 返回游标为0，表示本轮迭代结束。

通过这个就可以看出，Scan 完成一次迭代，需要和 Redis 进行多次交互。

Scan 命令注意事项：

    • 返回的结果可能会有重复，需要客户端去重复，这点非常重要;
    • 遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的;
    • 单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零;
推荐内容
 

2. Scan 踩坑

使用时遇到一个 特殊场景，跨区域远程连接 Redis 并进行模糊查询，扫描所有指定前缀的 Key。

最开始也没多想，直接就是开始 Scan，然后 Count 参数指定的是 1000。

Redis 中大概几百万 Key。

最后发现这个接口需要几十上百秒才返回。

什么原因呢？

Scan 命令中的 Count 指定一次扫描多少 Key，这里指定为 1000，几百万Key就需要几千次迭代，即和 Redis 交互几千次，然后因为是远程连接，网络延迟比较大，所以耗时特别长。

最后将 Count 参数调大后，减少了交互次数，就好多了。

Count 参数越大，Redis 阻塞时间也会越长，需要取舍。

极限一点，Count 参数和总 Key 数一致时，Scan 命令就和 Keys 效果一样了。

Count 大小和 Scan 总耗时的关系如下图：

scan_time_vs_count

图源：keydb

可以发现 Count 越大，总耗时就越短，不过越后面提升就越不明显了。

所以推荐的 Count 大小为 1W 左右。

如果不考虑 Redis 的阻塞，其实 Keys 比 Scan 会快很多，毕竟一次性处理，省去了多余的交互。

3. Scan原理

Redis使用了Hash表作为底层实现，原因不外乎高效且实现简单。类似于HashMap那样数组+链表的结构。其中第一维的数组大小为2n(n>=0)。每次扩容数组长度扩大一倍。

Scan命令就是对这个一维数组进行遍历。每次返回的游标值也都是这个数组的索引。Count 参数表示遍历多少个数组的元素，将这些元素下挂接的符合条件的结果都返回。因为每个元素下挂接的链表大小不同，所以每次返回的结果数量也就不同。

演示

关于 Scan 命令的遍历顺序，我们可以用一个小栗子来具体看一下：

127.0.0.1:6379> keys *
1) "db_number"
2) "key1"
3) "myKey"
127.0.0.1:6379> scan 0 MATCH * COUNT 1
1) "2"
2) 1) "db_number"
127.0.0.1:6379> scan 2 MATCH * COUNT 1
1) "1"
2) 1) "myKey"
127.0.0.1:6379> scan 1 MATCH * COUNT 1
1) "3"
2) 1) "key1"
127.0.0.1:6379> scan 3 MATCH * COUNT 1
1) "0"
2) (empty list or set)

如上所示，SCAN命令的遍历顺序是：0->2->1->3

这个顺序看起来有些奇怪，我们把它转换成二进制：00->10->01->11

可以看到每次这个序列是高位加1的。

普通二进制的加法，是从右往左相加、进位。而这个序列是从左往右相加、进位的。

相关源码：

v = rev(v);
v++;
v = rev(v);

将游标倒置，加一后，再倒置，也就是我们所说的“高位加1”的操作。

相关源码

先贴一下代码：

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de;
    unsigned long m0, m1;

    if (dictSize(d) == 0) return 0;

    if (!dictIsRehashing(d)) {//没有在做rehash，所以只有第一个表有数据的
        t0 = &(d->ht[0]);
        m0 = t0->sizemask;
        //槽位大小-1,因为大小总是2^N,所以sizemask的二进制总是后面都为1,
        //比如16个slot的字典，sizemask为00001111

        /* Emit entries at cursor */
        de = t0->table[v & m0];//找到当前这个槽位，然后处理数据
        while (de) {
            fn(privdata, de);//将这个slot的链表数据全部入队，准备返回给客户端。
            de = de->next;
        }

    } else {
        t0 = &d->ht[0];
        t1 = &d->ht[1];

        /* 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 */
        de = t0->table[v & m0];//处理小一点的表。
        while (de) {
            fn(privdata, de);
            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 {//扫描大点的表里面的槽位，注意这里是个循环，会将小表没有覆盖的slot全部扫描一次的
            /* Emit entries at cursor */
            de = t1->table[v & m1];
            while (de) {
                fn(privdata, de);
                de = de->next;
            }

            /* Increment bits not covered by the smaller mask */
            //下面的意思是，还需要扩展小点的表，将其后缀固定，然后看高位可以怎么扩充。
            //其实就是想扫描一下小表里面的元素可能会扩充到哪些地方，需要将那些地方处理一遍。
            //后面的(v & m0)是保留v在小表里面的后缀。
            //((v | m0) + 1) & ~m0) 是想给v的扩展部分的二进制位不断的加1，来造成高位不断增加的效果。
            v = (((v | m0) + 1) & ~m0) | (v & m0);

            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));//终止条件是 v的高位区别位没有1了，其实就是说到头了。
    }

    /* Set unmasked bits so incrementing the reversed cursor
	     * operates on the masked bits of the smaller table */
    v |= ~m0;
    //按位取反，其实相当于v |= m0-1 , ~m0也就是11110000,
    //这里相当于将v的不相干的高位全部置为1，待会再进行翻转二进制位，然后加1，然后再转回来

    /* Increment the reverse cursor */
    v = rev(v);
    v++;
    v = rev(v);
    //下面将v的每一位倒过来再加1，再倒回去，这是什么意思呢，
    //其实就是要将有效二进制位里面的高位第一个0位设置置为1，因为现在是0嘛

    return v;
}

reverse binary iteration

Redis Scan 命令最终使用的是 reverse binary iteration 算法，大概可以翻译为 逆二进制迭代，具体算法细节可以看一下这个Github 相关讨论

这个算法简单来说就是：

依次从高位（有效位）开始，不断尝试将当前高位设置为1，然后变动更高位为不同组合，以此来扫描整个字典数组。

其最大的优势在于，从高位扫描的时候，如果槽位是2N个,扫描的临近的2个元素都是与2(N-1)相关的就是说同模的，比如槽位8时，0%4 == 4%4， 1%4 == 5%4 ， 因此想到其实hash的时候，跟模是很相关的。

比如当整个字典大小只有4的时候，一个元素计算出的整数为5， 那么计算他的hash值需要模4，也就是hash(n) == 5%4 == 1 , 元素存放在第1个槽位中。当字典扩容的时候，字典大小变为8， 此时计算hash的时候为5%8 == 5 ， 该元素从1号slot迁移到了5号，1和5是对应的，我们称之为同模或者对应。

同模的槽位的元素最容易出现合并或者拆分了。因此在迭代的时候只要及时的扫描这些相关的槽位，这样就不会造成大面积的重复扫描。

3 种情况

迭代哈希表时，有以下三种情况：

  • 从迭代开始到结束，哈希表不 Rehash；
  • 从迭代开始到结束，哈希表Rehash，但每次迭代，哈希表要么不开始 Rehash，要么已经结束 Rehash；
  • 从一次迭代开始到结束，哈希表在一次或多次迭代中 Rehash。
    • 即再 Rehash 过程中，执行 Scan 命令，这时数据可能只迁移了一部分。

因此，游标的实现需要兼顾以上三种情况。上述三种情况下游标实现的要求如下：

第一种情况比较简单。假设redis的hash表大小为4，第一个游标为0，读取第一个bucket的数据，然后游标返回2，下次读取bucket 2 ，依次遍历。

第二种情况更复杂。假设redis的hash表大小为4，如果rehash后大小变成8。如果如上返回游标(即返回2)，则显示下图：

redis-scale

假设bucket 0读取后返回到cursor 2，当客户端再次Scan cursor 2时，hash表已经被rehash，大小翻倍到8，redis计算一个key bucket如下：

hash(key)&(size-1)

即如果大小为4，hash(key)&11，如果大小为8，hash(key)&111。所以当size从4扩大到8时，2 号bucket中的原始数据会被分散到2 (010) 和 6 (110) 这两个 bucket中。

从二进制来看，size为4时，在hash(key)之后，取低两位，即hash(key)&11，如果size为8，bucket位置为hash(key) & 111，即取低三个位。

所以依旧不会出现漏掉数据的情况。

第三种情况，如果返回游标2时正在进行rehash，则Hash表1的bucket 2中的一些数据可能已经rehash到了的Hash表2 的bucket[2]或bucket[6]，那么必须完全遍历 哈希表2的 bucket 2 和 6，否则可能会丢失数据。

Redis 全局有两个Hash表，扩容时会渐进式的将表1的数据迁移到表2，查询时程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找。

详细信息可以查看：Redis教程(四)—全局数据结构

游标计算

具体游标计算代码如下：

Scan 命令中的游标，其实就是 Redis 内部的 bucket。

v |= ~m0; // 将游标v的unmarsked 比特都置为1
v = rev(v);// 反转v
v++; //这个是关键，加1，对一个数加1，其实就是将这个数的低位的连续1变为0，然后将最低的一个0变为1，其实就是将最低的一个0变为1
v = rev(v);//再次反转，即得到下一个游标值

代码逻辑非常简单，计算过程如下：

scan-rbi

图源：developpaper

  • 大小为 4 时，游标状态转换为 0-2-1-3。
  • 当大小为 8 时，游标状态转换为 0-4-2-6-1-5-3-7。

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

总结一下：redis在rehash 扩容的时候，不会重复或者漏掉数据。但缩容，可能会造成重复但不会漏掉数据。

缩容处理

之所以会出现重复数据，其实就是为了保证缩容后数据不丢。

假设当前 hash 大小为 8：

  • 1）第一次先遍历了 0 号槽，返回游标为 4；
  • 2）准备遍历 4 号槽，然后此时发生了缩容，4 号槽的元素也进到 0 号槽了。
  • 3）但是0 号槽之前已经被遍历过了，此时会丢数据吗？

答案就在源码中：

do {//扫描大点的表里面的槽位，注意这里是个循环，会将小表没有覆盖的slot全部扫描一次的
    /* Emit entries at cursor */
    de = t1->table[v & m1];
    while (de) {
        fn(privdata, de);
        de = de->next;
    }

    /* Increment bits not covered by the smaller mask */
    //下面的意思是，还需要扩展小点的表，将其后缀固定，然后看高位可以怎么扩充。
    //其实就是想扫描一下小表里面的元素可能会扩充到哪些地方，需要将那些地方处理一遍。
    //后面的(v & m0)是保留v在小表里面的后缀。
    //((v | m0) + 1) & ~m0) 是想给v的扩展部分的二进制位不断的加1，来造成高位不断增加的效果。
    v = (((v | m0) + 1) & ~m0) | (v & m0);

    /* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));//终止条件是 v的高位区别位没有1了，其实就是说到头了。

具体计算方法：

  v = (((v | m0) + 1) & ~m0) | (v & m0);

右边的下半部分是v，左边的上半部分是v。 (v&m0) 取出v的低位，例如size=4时v&00000011

左半边(v|m0) + 1 将V 的低位设置为1，然后+1 将进位到v 的高位，再次&m0，V 的高位将被取出。

假设游标返回2并且正在rehashing，大小从4变为8，那么M0 = 00000011 v = 00000010

根据公式计算的下一个光标是 ((00000010 | 00000011) +1) & (11111111100) | (00000010 & 00000011) = (00000100) & (11111111100) | (00000000010) = (000000000110) 正好是 6。

4. 小结

  • Scan Count 参数限制的是遍历的 bucket 数，而不是限制的返回的元素个数
    • 由于不同 bucket 中的元素个数不同，其中满足条件的个数也不同，所以每次 Scan 返回元素也不一定相同
  • Count 越大，Scan 总耗时越短，但是单次耗时越大，即阻塞Redis 时间边长
    • 推荐 Count 大小为 1W左右
    • 当 Count = Redis Key 总数时，Scan 和 Keys 效果一致
  • Scan 采用 逆二进制迭代法来计算游标，主要为了兼容Rehash的情况
  • Scan 为了兼容缩容后不漏掉数据，会出现重复遍历。
    • 即客户端需要做去重处理

核心就是 逆二进制迭代法，比较复杂，而且算法作者也没有具体证明，为什么这样就能实现，只是测试发现没有问题，各种情况都能兼容。

具体算法细节可以看一下这个Github 相关讨论

antirez: Hello @pietern! I’m starting to re-evaluate the idea of an iterator for Redis, and the first item in this task is definitely to understand better your pull request and implementation. I don’t understand exactly the implementation with the reversed bits counter…
I wonder if there is a way to make that more intuitive… so investing some more time into this, and if I fail I’ll just merge your code trying to augment it with more comments…
Hard to explain but awesome.
pietern： Although I don’t have a formal proof for these guarantees, I’m reasonably confident they hold. I worked through every hash table state (stable, grow, shrink) and it appears to work everywhere by means of the reverse binary iteration (for lack of a better word).

所以只能说这个算法很巧妙。就像卡马克快速逆平方根算法：

float Q_rsqrt( float number ) 
{ 
    long i; 
    float x2, y; 
    const float threehalfs = 1.5F ;
    x2 = number * 0.5F ; 
    y = number ; 
    i = * ( long * ) &y; // evil floating point bit level hacking 
    i = 0x5f3759df - ( i >> 1 ); // what the fuck? 
    y = * ( float * ) &i; 
    y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration 
//  y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
    return y ;
}

其中的这个0x5f3759df数就很巧妙。

5. 参考

http://antirez.com/news/63

https://developpaper.com/redis-scan-command-principle/

https://www.cnblogs.com/thrillerz/p/4527510.html

https://www.jianshu.com/p/abe5d8ae4852

https://zhuanlan.zhihu.com/p/46353221

https://docs.keydb.dev/blog/2020/08/10/blog-post/