如何使用

语法

1	SCAN cursor [MATCH pattern] [COUNT count] [TYPE type]

时间复杂度

一次调用是 O(1)，完整的迭代是 O(N)，包括不断调用直到返回 cursor 为 0；N 为集合内元素数量

SCAN 命令和相关的 SSCAN、HSCAN 和 ZSCAN 命令都是用于对元素集合进行增量迭代

SCAN 迭代当前所选 Redis 数据库中 keys
SSCAN 迭代 Set 的元素
HSCAN 迭代 Hash 的字段和它们对应的 value
ZSCAN 迭代 Sorted Set 和它们对应的 score

由于这些命令允许增量迭代，每次调用只返回少量元素，因此可以在生产中使用它们，而不会出现 KEYS 或 SMEMBERS 等命令的缺点，这些命令在针对大量 key 或元素调用时可能会长时间（甚至几秒钟）阻塞服务器

然而，尽管像 SMEMBERS 这样的阻塞命令能够在给定的时刻提供集合的所有元素，但 SCAN 命令族仅对返回的元素提供有限的保证，因为我们增量迭代的集合可能在迭代过程中发生变化（事实上现在 SCAN 使用的方式可以避免漏掉元素，但不能保证不重复元素，不过这种算法只有实践验证，并未得到数学层面的验证）

具体可以查看官方文档中 Scan guarantees 内容

使用示例

> set 1 1
> set 2 2
> set 3 3
> set 4 4

> SCAN 0
1) "0"
2) 1) "2"
   2) "3"
   3) "4"
   4) "1"

返回的 cursor 是 0，说明已经返回了所有的元素

返回的 keys 列表为 2、3、4、1

可以看到返回顺序并非添加顺序，因为 Redis keys 的底层也使用的哈希结构，非有序

设置 MATCH 参数

1
2
3

> SCAN 0 MATCH 1
1) "0"
2) 1) "1"

只会返回匹配的 key

设置 COUNT 参数

> SCAN 0 COUNT 2
1) "3"
2) 1) "2"
   2) "3"
 
> SCAN 3 COUNT 2
1) "0"
2) 1) "4"
   2) "1"

第一返回了 2 个 key，并且返回了下一个 cursor 为 3

第二次 cursor 返回 0，表示迭代完了所有的元素

为什么 SCAN 可能会在单个调用中返回所有元素？

在 COUNT 参数的文档说明中提到，有时这类命令可能会在一次调用中同时返回 Set、Hash 或 Sorted Set 的所有元素，而与 COUNT 的值无关

之所以会发生这种情况，是因为只有当我们正在扫描的聚合数据类型表示为哈希表（Hash Table）时，才可以实现基于光标的迭代器（cursor-based iterator），但是 Redis 使用了内存优化，受优化的影响，小的聚合数据类型使用紧凑的单分配压缩编码来表示，直到它们达到给定的项目数量或单个元素的给定最大大小

在这种情况下，SCAN 没有可返回的有意义的游标，并且必须一次迭代整个数据结构，因此它唯一合理的行为就是在调用中返回所有内容

还要注意，这种行为是 SSCAN、HSCAN 和 ZSCAN 特有的；SCAN 本身从不显示这种行为，因为 keys 的存储总是由哈希表实现

概括一下，即当聚合类型的 key 使用非哈希结构时（压缩列表等数据结构），游标的概念无意义

尝试一下

1
2
3

> HSET test_scan 1 1
> HSET test_scan 2 2
> HSET test_scan 3 3

创建了一个 Hash key，按照默认配置，当前的 key 使用的是压缩列表

> HSCAN test_scan 0 COUNT 1
1) "0"
2) 1) "1"
   2) "1"
   3) "2"
   4) "2"
   5) "3"
   6) "3"

可以看到哪怕命令中明确设置了 COUNT 参数为 1，还是返回了整个 key 所有的元素

实现原理

cursor 非递增

cursor 是哈希槽的坐标（经过运算），所以不断增加 cursor 一直调用，最终就可以查询到所有的元素

1
2
3

> set 1 1
> set 2 2
> set 3 3

> SCAN 0 COUNT 1
1) "2"
2) 1) "1"
   
> SCAN 2 COUNT 1
1) "1"
2) 1) "2"

> SCAN 1 COUNT 1
1) "3"
2) 1) "3"

> SCAN 3 COUNT 1
1) "0"
2) (empty list or set)

可以看到 cursor 的顺序 0 -> 2 -> 1 -> 3，并非是顺序递增（注意，这个实验结果和 Redis 当前存储 key 的哈希表 size 有关，如果哈希表已经扩容过，可能无法和当前结果一致，可以切换到新的 DB 上进行实验）

高位 + 1

将上面 cursor 值转换为二进制

00 -> 10 -> 01 -> 11

可以观察出这个序列是逐步高位加 1 的，进 1 则进到低位

逆二进制迭代

即 Scan 命令使用的是 reverse binary iteration 算法

简单来说就是将低位向高位的运算变为高位向低位，则同样的当二进制为 11...111 时，进一则变为 0

最终通过迭代扫描整个字典

Redis 实现相关代码

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

使用 Java 实现了一下，方便观察位运算的操作

public class ReverseBinaryIteration {

    private static final int SIZE_BIT_COUNT = 2;

    public static void main(String[] args) throws InterruptedException, IOException {
        boolean end = false;
        int next = 0;
        while (!end) {
            next = getReverseBinaryIterationNext(next);
            if (next == 0) {
                end = true;
            }
        }
    }

    public static int getReverseBinaryIterationNext(int current) {
        return Optional.of(current)
                // 将游标的 unmasked 比特都置为 1
                .map(i -> {
                    int res = setUnmasked(i);
                    System.out.println("setUnmasked : " + Integer.toBinaryString(res));
                    return res;
                })
                .map(i -> {
                    int res = reverseBits(i);
                    System.out.println("reverseBits : " + Integer.toBinaryString(res));
                    return res;
                })
                .map(i -> {
                    int res = ++i;
                    System.out.println("低位加 1 : " + Integer.toBinaryString(res));
                    return res;
                })
                .map(i -> {
                    int res = reverseBits(i);
                    System.out.println("reverseBits : " + Integer.toBinaryString(res));
                    return res;
                })
                .map(i -> {
                    System.out.println("最终结果 : " + Integer.toBinaryString(i));
                    System.out.println("---------------------------------------");
                    return i;
                })
                .get();
    }

    /**
     * 非有效位设置为 1
     * SIZE_BIT_COUNT 为模拟有效位
     */
    private static int setUnmasked(int num) {
        // 全是 1
        int mask = 0xffffffff;
        // 模拟有效位数的保留码
        int retain_mask = ((1 << SIZE_BIT_COUNT) - 1);
        // 保留有效位数
        mask &= ~retain_mask;
        // 或出结果
        return num | mask;
    }

    /**
     * 反转比特位
     */
    private static int reverseBits(int num) {
        int res = 0;
        for (int i = 0; i < 32 && num != 0; ++i) {
            res |= (num & 1) << (31 - i);
            num >>>= 1;
        }
        return res;
    }
}

代码中模拟 masked 位数为 2，即 4 个哈希槽，结果如下

setUnmasked : 11111111111111111111111111111100
reverseBits : 111111111111111111111111111111
低位加 1 : 1000000000000000000000000000000
reverseBits : 10
最终结果 : 10
---------------------------------------
setUnmasked : 11111111111111111111111111111110
reverseBits : 1111111111111111111111111111111
低位加 1 : 10000000000000000000000000000000
reverseBits : 1
最终结果 : 1
---------------------------------------
setUnmasked : 11111111111111111111111111111101
reverseBits : 10111111111111111111111111111111
低位加 1 : 11000000000000000000000000000000
reverseBits : 11
最终结果 : 11
---------------------------------------
setUnmasked : 11111111111111111111111111111111
reverseBits : 11111111111111111111111111111111
低位加 1 : 0
reverseBits : 0
最终结果 : 0
---------------------------------------

可以看到最终实现了高位加 1 的运算，0 -> 2 -> 1 -> 3 -> 0

模拟

在运行过程中，Redis 的哈希表会有哪些操作，这些操作是否会导致数据错误

哈希表不变

在哈希表不变的情况下，游标使用逆二进制迭代最终会扫描所有槽位

扩容完成

假设在上一次调用时，哈希表的槽位是 4，这次调用时槽位经过 resize 扩大到了 8

在扩容过程中，key 会被重新分配槽位，其哈希值不变，槽位计算方式为

1	hash(key)&(size-1)

假设一个 key 哈希为 6，之前计算槽位为 2(10)，那么扩容后即为 6(101)，即 2 和 6 称为同模

假设一个 key 哈希为 7，之前计算槽位为 3(11)，那么扩容后即为 7(111)，即 3 和 7 称为同模

如何保证在这个过程中游标不会略过修改后的槽位？

只需要保证

一个 key 扩容后的槽位不变或更大（必然）
当前游标在对应更大的 masked 位数时，只会比下一个游标更小（注意逆迭代）

假设当前游标到了槽位 2（即 10）

可以发现后面的 4、5、6、7 槽位按照逆二进制迭代的规则，都要大于槽位 2，也就是在后续遍历过程中不会遗漏数据

扩容中

Redis 使用渐进式 Hash，旧的哈希表依然是 4 槽位，新的哈希表是 8 槽位

那么根据扩容完成的情况

假设扫描槽位 2 时，需要同时扫描旧表中的 2 槽位和新表中的 2 和 6 槽位来避免数据遗漏

缩容

Redis 中的哈希结构还会自动进行缩容（负载因子小于 0.1）

（这里没看懂，但是看 issue 上的讨论，是可以避免缩容问题的）

看了参考的博客，看起来是在代码层面进行了重复的扫描来进行避免

卡马克快速逆平方根

这个逆二进制迭代算法就和卡马克快速逆平方根一样

求逆平方根的算法来自《雷神之锤 3》的作者卡马克，该算法并不复杂，其核心就是用牛顿迭代法来不断逼近，但卡马克真正厉害的地方，在于他选择了一个十分神秘的常数：0x5f3759df 来计算猜测值，第一次牛顿迭代算出的值已经非常接近，这样仅需两次牛顿迭代就可达到所需精度

普渡大学的数学家 Chris Lomont 看了以后觉得有趣，决定要研究卡马克弄出来的这个猜测值有什么奥秘

Lomont 在精心研究之后从理论上也推导出一个最佳猜测值：0x5f37642f，和卡马克的数字非常接近

传奇并没有在这里结束

Lomont 计算出结果以后非常满意，于是拿自己计算出的起始值和卡马克的神秘数字做比较，看哪个数字能够更快更精确的求得逆平方根，结果是卡马克赢了... 谁也不知道卡马克是怎么找到这个数字的

最后 Lomont 采用暴力方法一个数字一个数字试过来，终于找到一个比卡马克数字要好上那么一丁点的数字，虽然实际上这两个数字所产生的结果非常近似，这个暴力得出的数字是：0x5f375a86

Lomont 为此写下一篇论文，Fast Inverse Square Root

作者并没有数学上验证其准确性，只是通过一些测试用例测试没有问题

Those guarantees are correct. 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).

参考

SCAN | Redis

Redis Scan 原理解析与踩坑 - (lixueduan.com)

Add SCAN command by pietern · Pull Request #579 · redis/redis (github.com)

贫瘠之地

Redis SCAN 原理