Redis SCAN 命令基于高位进位的游标遍历为何能避免重复与阻塞

REmote DIctionary Server (Redis) 提供 KEYS 命令用于查找匹配模式的键。但 KEYS 会一次性返回所有匹配的键，在键数量巨大时导致服务器阻塞，无法处理其他请求。SCAN 命令应运而生：它通过基于高位进位 (High-Carry) 的游标 (cursor) 进行迭代，每次返回有限数量的键，从根本上解决了阻塞问题，同时通过特殊设计最大限度地减少遍历过程中的重复与遗漏。本文从原理出发，逐步拆解其工作机制。

1. 阻塞问题的根源与 SCAN 的应对

KEYS 命令的阻塞源于它的全量扫描：Redis 是单线程模型，执行 KEYS 时必须遍历整个键空间，期间无法处理任何客户端命令。SCAN 命令采用游标式迭代：

1. 客户端 调用 SCAN cursor [MATCH pattern] [COUNT count]。
2. Redis 返回 一个新的游标（通常是一个整数）以及一批键。如果返回的游标为 0，表示遍历结束。
3. 下次迭代时，使用返回的新游标作为参数。

由于每次只处理一部分键，Redis 可以在两次 SCAN 调用之间处理其他命令，从而避免阻塞。

2. 游标遍历的潜在问题：重复与遗漏

游标式遍历的核心难题在于：遍历过程中，Redis 的哈希表可能发生扩容或缩容（rehash）。键在哈希表中的位置会随着表大小变化而改变。如果采用简单的顺序递增游标（如 0, 1, 2, ...），rehash 后可能出现：

• 大量重复扫描：例如，扩容后原小表中的多个槽位被映射到大表中的少部分槽位，导致这些槽位被反复访问。
• 遗漏键：缩容后，原大表中的部分槽位合并，若游标恰好跳过合并后的区域，则键丢失。

Redis 2.8 引入的 SCAN 使用 高位进位 策略来遍历哈希表，从根本上缓解了这些问题。

3. 高位进位遍历的原理

Redis 的内部哈希表大小始终是 2 的整数次幂。假设表大小为 $2^n$，则每个键的哈希值对 $2^n$ 取模后的结果落在 [0, 2^n-1] 区间。普通顺序遍历（从 0 递增到 2^n-1）在发生 rehash 时会产生大量错位。高位进位则采用一种特殊的序列：从 0 开始，每次将当前游标的二进制表示从最高位开始加 1，进位方向与普通加法相反。

3.1 规则与举例

以 $n=3$（表大小 8）为例，遍历顺序为：

0 → 4 → 2 → 6 → 1 → 5 → 3 → 7

二进制对比：

高位进位的运算等价于：将游标二进制位反转后执行 +1，再反转回来。例如：

• 游标 0 (000) → 反转得 000 → +1 得 001 → 反转得 100 (即 4)。
• 游标 4 (100) → 反转得 001 → +1 得 010 → 反转得 010 (即 2)。

这个过程可以用 Mermaid 流程图直观展示（注意节点标签严格使用半角引号）：

3.2 为何优先遍历高位？

在高位进位序列中，前 $2^{n-1}$ 次遍历的二进制最高位（第 n 位）均为 1（即 4,2,6,1 的二进制最高位 1 ？注意：对于 n=3，最高位是第3位（从高位数），4=100，2=010，6=110，1=001，实际上前4个遍历的最高位并不都是1。更精确的说法是：序列的数在二进制下的高位变化最快，即低位相对稳定。这种性质使得当哈希表从大小 $2^n$ 扩容到 $2^{n+1}$ 时，每个原来的槽位（对应 $2^n$ 个槽）会被映射到新表的两个连续槽中；因为游标的高位先被遍历，新表的“对半”区域被均匀覆盖，避免了大量重复。

4. 避免重复与遗漏的机制

4.1 哈希表扩容时的游标调整

当 Redis 在遍历过程中触发 rehash（扩容），旧表大小 $M = 2^n$，新表大小 $N = 2^{n+1}$。键在旧表中的索引为 hash % M，在新表中的索引为 hash % N。由于 $N = 2M$，旧槽 i 中的键会被重新分布到新槽 i 或 i + M 中。

如果使用普通顺序游标（如 0,1,2,...），假设当前游标为 x，此时触发扩容，则 Redis 会将 x 映射到新表中的对应位置。但顺序游标的映射会导致已经遍历过的旧槽中的部分键在新表中被再次遍历。例如，旧表大小 4，游标遍历到 2 时扩容为 8；旧槽 0 和 1 中的键在新表中可能落在 0~3 之间，而游标 2 对应的新区域 2 会包含来自旧槽 0 的部分键，造成重复。

高位进位游标则利用其二进制特性：在扩容时，当前游标 c 的二进制表示在原 $n$ 位基础上，新表需要 $n+1$ 位。Redis 将 c 视作新表中的游标（高位补 0），然后继续遍历。由于高位进位的顺序保证了新表的低半部分（对应旧表的 0 ~ M-1）和高半部分（对应旧表的 M ~ 2M-1）是交叉遍历的，且已遍历过的旧槽所对应的新槽在后续遍历中不会再次被访问。具体来说：

• 新表中槽位的索引的最高位（第 $n+1$ 位）用于区分旧表的前半和后半。
• 高位进位序列确保了在遍历新表时，每次改变的位是最高位或较高位，使得遍历天然“分区”地覆盖到所有旧槽的两个可能位置。

4.2 缩容时的处理

缩容情况类似：当表大小从 $2^n$ 缩小到 $2^{n-1}$ 时，新表大小仅为旧表的一半。每个旧槽 i 包含原槽 i 和 i+M/2 的键的并集。普通顺序游标可能跳过某些已合并的槽，导致遗漏。高位进位游标通过舍弃当前游标的最高位并映射到新表，保证了新表中的每个槽恰好被一次遍历覆盖，因为高位进位序列在缩容后自然变为小表的高位进位序列。

4.3 遍历中途键增删的影响

即使没有 rehash，SCAN 过程中键的增加或删除也可能导致重复或遗漏。SCAN 的文档明确指出：不保证不重复，但保证在遍历过程中，如果集合没有变化，则不会遗漏任何键。高位进位设计的主要优势在于 rehash 场景下大幅减少重复与遗漏的概率（但无法完全消除动态增删带来的不确定性）。实际使用中，客户端通常需要在业务层处理重复键（例如对结果取集合去重）。

5. 避免阻塞的实现细节

SCAN 避免阻塞的核心是每次调用只处理有限数量的哈希槽（由 COUNT 参数指定，默认 10）。Redis 在 SCAN 命令处理过程中，会扫描当前游标对应的哈希槽，直到收集到足够数量的键或遍历完该槽的所有冲突链表。由于单次操作耗时短，不会阻塞事件循环。

需要注意的是，COUNT 参数并非保证精确返回那么多个键，而是建议服务端尽力扫描这么多次（Redis 实际按哈希槽数而不是键数来迭代）。如果某个槽包含大量冲突键，SCAN 可能会在单次调用中返回非常多的键，但仍然远少于全量扫描。

5.1 游标的生命周期

游标是无状态的，Redis 不保存客户端的迭代进度。服务端仅根据当前游标值计算出下次要扫描的槽位。这得益于高位进位序列的确定性：给定当前游标，下一个游标可通过位运算唯一确定。即使客户端在两次 SCAN 之间重新连接，也能从断点继续。

6. 高位进位 vs 普通顺序：一个对比示例

假设哈希表大小从 4 扩容到 8，游标遍历顺序对比如下：

使用代码模拟可直观验证：在高位进位序列下，扩容后每个旧槽的键在新表中恰好被遍历一次（忽略动态变化），而普通顺序则会因游标范围错位产生大量重复扫描。

7. 实际使用建议

• 始终在循环中使用返回的新游标：不要自主递增游标，否则会导致无限循环或遗漏。
• 设置合理的 COUNT：例如 100 到 1000，避免单次返回过多键导致网络超时。
• 接受重复键：客户端应使用 SET 或业务去重逻辑处理。
• 搭配 MATCH 模式：SCAN 的模式匹配是在键被返回后进行的过滤，因此使用 COUNT 时仍需考虑匹配后的结果量。

8. 总结

Redis SCAN 命令通过游标式迭代解决了 KEYS 的阻塞问题，并通过高位进位遍历极大优化了哈希表扩容/缩容场景下的遍历效率，将重复和遗漏的概率降到最低。其核心设计思想是：用二进制的位逆序加法代替自然递增，利用哈希表大小是 2 的幂的性质，实现平滑的跨表遍历。理解这一机制，有助于你在生产环境中正确使用 SCAN 进行大规模数据扫描。