因为不会Redis的scan命令，我被开除了

那个深夜，我登上了公司的服务器，在 Redis 命令行里敲入 keys* 后，线上开始报警，服务瞬间被卡死。

图片来自 Pexels

我只能举起双手，焦急地等待几千万 key 被慢慢扫描，束手无策万念俱灰的时候，我收到了 Leader 的短信：你明天不用来上班了。

虽然上面是我的臆想，事实上很多公司的运维也会禁用这些命令，来防止开发出错。

但我在群里依然看到有同学在问“为什么 Redis 不能用 keys?我觉得挺好的呀”时，为了不让上面的情况发生，我决定写下这篇文章。

如何才能优雅地遍历 Redis?作为一种可以称为数据库的组件，这是多么理所应当的要求。

终于，Redis 在 2.8.0 版本新增了众望所归的 scan 操作，从此再也不用担心敲入了 keys*，然后等着定时炸弹的引爆。

学会使用 scan 并不困难，那么问题又来了，它是如何遍历的?当遍历过程中加入了新的 key，当遍历过程中发生了扩容，Redis 是如何解决的?

抱着深入学习的态度，以及为了能够将来在面试官面前谈笑风生，让我们一起来借此探索 Redis 的设计原理。

开门见山，首先让我们来总结一下 scan 的优缺点。

优点如下：

• 提供键空间的遍历操作，支持游标，复杂度 O(1)，整体遍历一遍只需要 O(N)。
• 提供结果模式匹配。
• 支持一次返回的数据条数设置，但仅仅是个 hints，有时候返回更多。
• 弱状态，所有状态只需要客户端维护一个游标。

缺点如下：

• 无法提供完整的快照遍历，也就是中间如果有数据修改，可能有些涉及改动的数据遍历不到。
• 每次返回的数据条数不一定，极度依赖内部实现。
• 返回的数据可能有重复，应用层需要能够处理重入逻辑。

所以 scan 是一个能够满足需求，但也不是完美无瑕的命令。下面来介绍一下原理，scan 到底是如何实现的?

scan，hscan 等命令主要都是借用了通用的 scan 操作函数：scanGenericCommand 。

scanGenericCommand 函数分为以下几步：

• 解析 count 和 match 参数，如果没有指定 count，默认返回 10 条数据。
• 开始迭代集合，如果是 key 保存为 ziplist 或者 intset，则一次性返回所有数据，没有游标(游标值直接返回 0)。

由于 Redis 设计，只有数据量比较小的时候才会保存为 ziplist 或者 intset，所以此处不会影响性能。

游标在保存为 hash 的时候发挥作用，具体入口函数为 dictScan，下文详细描述。

• 根据 match 参数过滤返回值，并且如果这个键已经过期也会直接过滤掉(Redis 中键过期之后并不会立即删除)。

当迭代一个哈希表时，存在三种情况：

• 从迭代开始到结束,哈希表没有进行 rehash。
• 从迭代开始到结束,哈希表进行了 rehash，但是每次迭代时，哈希表要么没开始 rehash，要么已经结束了 rehash。
• 从迭代开始到结束，某次或某几次迭代时哈希表正在进行 rehash。

在这三种情况之下，sacn 是如何实现的?首先需要知道的前提是：Redis 中进行 rehash 扩容时会存在两个哈希表，ht[0] 与 ht[1]，rehash 是渐进式的，即不会一次性完成。

新的键值对会存放到 ht[1] 中并且会逐步将 ht[0] 的数据转移到 ht[1]。全部 rehash 完毕后，ht[1] 赋值给 ht[0] 然后清空ht[1]。

模拟问题

①迭代过程中，没有进行 rehash

这个过程比较简单，一般来说只需要最简单粗暴的顺序迭代就可以了，这种情况下没什么好说的。

②迭代过程中，进行过 rehash

但是字典的大小是能够进行自动扩容的，我们不得不考虑以下两个问题：

第一，假如字典扩容了，变成 2 倍的长度，这种情况下，能够保证一定能遍历所有最初的 key，但是却会出现大量重复。

举个例子：比如当前的 key 数组大小是 4，后来变为 8 了。假如从下表 0，1，2，3 顺序扫描时，如果数组已经发生扩容。

那么前面的 0，1，2，3 slot 里面的数据会发生一部分迁移到对应的 4，5，6，7 slot 里面去，当扫描到 4，5，6，7 的 slot 时，无疑会出现值重复的情况。

需要知道的是，Redis 按如下方法计算一个当前 key 扩容后的 slot：hash(key)&(size-1)。

如图，当字典大小从 4 扩容到 8 时，原先在 0 slot 的数据会分散到 0(000) 与 4(100) 两个 slot，对应关系表如下：

第二， 如果字典缩小了，比如从 16 缩小到 8， 原先 scan 已经遍历了 0，1，2，3 ，如果数组已经缩小。

这样后来迭代停止在 7 号 slot，但是 8，9，10，11 这几个 slot 的数据会分别合并到 0，1，2，3 里面去，从而 scan 就没有扫描出这部分元素出来，无法保证可用性。

③迭代过程中，正在进行 rehash

上面考虑的情况是，在迭代过程的间隙中，rehash 已经完成。那么会不会出现迭代进行中，切换游标时，rehash 也正在进行?当然可能会发生。

如果返回游标 1 时正在进行 rehash，那么 ht[0](扩容之前的表)中的 slot1 中的部分数据可能已经 rehash 到 ht[1](扩容之后的表)中的 slot1 或者 slot4。

此时必须将 ht[0] 和 ht[1] 中的相应 slot 全部遍历，否则可能会有遗漏数据，但是这么做好像也非常麻烦。

解决方法

为了解决以上两个问题，Redis 使用了一种称为：reverse binary iteration 的算法。

源码如下：

unsigned?long?dictScan(dict?*d,?unsigned?long?v,?dictScanFunction?*fn,?void?*privdata){?if?(!dictIsRehashing(d))?{?????????t0?=?(d->ht[0]);?????????m0?=?t0->sizemask;?/*?Emit?entries?at?cursor?*/?while?(de)?{?????????????fn(privdata,?de);?????????????de?=?de->next;?}?}?else?{?????????m0?=?t0->sizemask;?????????m1?=?t1->sizemask;?????????de?=?t0->table[v?&?m0];?while?(de)?{?????????????fn(privdata,?de);?????????????de?=?de->next;?}?do?{?????????????de?=?t1->table[v?&?m1];?while?(de)?{?????????????????fn(privdata,?de);?????????????????de?=?de->next;?}?????????????v?=?(((v?|?m0)?+?1)??&?~m0)?|?(v?&?m0);?}?while?(v?&?(m0?^?m1));?}?????v?|=?~m0;?????v?=?rev(v);?????v++;?????v?=?rev(v);?return?v;?}?

一起来理解下核心源码，第一个 if，else 主要通过 dictIsRehashing 这个函数来判断是否正在 rehash。

sizemask 指的是字典空间长度，假如长度为 16，那么 sizemask 的二进制为 00001111。m0 代表当前字典的长度，v 代表游标所在的索引值。

接下来关注这个片段：

v?|=?~m0;?v?=?rev(v);?v++;?v?=?rev(v);?

这段代码初看好像有点摸不着头脑，怎么多次在多次 rev?我们来看下在字典长度从 4 rehash 到 8 时，scan 是如何迭代的。

当字典长度为 4 时，m0 等于 4，二进制表示为 00000011，那么 ~m0 为 11111100，v 初始值为 0，那么 v |=~m0为11111100。

接下来看图：

可以看到，第一次 dictScan 后，游标从 0 变成了 2，四次遍历分别为 0→2→1→3，四个值都遍历到了。

在字典长度为 8 时，遍历情况如下：

遍历顺序为：0→4→2→6→1→5→3→7。

是不是察觉了什么?遍历顺序是不是顺序是一致的?如果还没发现，不妨再来看看字典长度为 16 时的遍历情况，以及三次顺序的对比：

让我们设想这么一个情况，字典的大小本身为 4，开始迭代，当游标刚迭代完 slot0 时，返回的下一个游标是 slot2。

此时发现字典的大小已经从 4 rehash 到 8，那么不妨继续从 size 为 8 的 hashtable 中 slot2 处继续迭代。

有人会说，不是把 slot4 遗漏掉了吗?注意之前所说的扩容方式：hash(key)&(size-1)，slot0 和 slot4 的内容是相同的，巧妙地避开了重复，当然，更不会遗漏。

如果你看到这里，你可能会发出和我一样的感慨：我 X，这算法太牛 X 了。

没错，上面的算法是由 Pieter Noordhuis 设计实现的，Redis 之父 Salvatore Sanfilippo 对该算法的评价是“Hard to explain but awesome。”

字典扩大的情况没问题，那么缩小的情况呢?可以仿照着自己思考一下具体步骤。答案是可能会出现重复迭代，但是不会出现遗漏，也能够保证可用性。

迭代过程中，进行过 rehash 这种情况下的迭代已经比较完美地解决了，那么迭代过程中，正在进行 rehash 的情况是如何解决的呢?

我们继续看源码，之前提到过 dictIsRehashing 这个函数用来判断是否正在进行 rehash。

那么主要就是关注这段源码：

m0?=?t0->sizemask;?m1?=?t1->sizemask;?de?=?t0->table[v?&?m0];?while?(de)?{?????????????fn(privdata,?de);?????????????de?=?de->next;?}?do?{?????????????de?=?t1->table[v?&?m1];?while?(de)?{?????????????????fn(privdata,?de);?????????????????de?=?de->next;?}?????????????v?=?(((v?|?m0)?+?1)??&?~m0)?|?(v?&?m0);?}?while?(v?&?(m0?^?m1));?

m0 代表 rehash 前的字典长度，假设为 4，即 00000011，m1 代表 rehash 后的字典长度，假设为 8，即 00000111。

首先当前游标 &m0 可以得到较小字典中需要迭代的 slot 的索引，然后开始循环迭代。

然后开始较大字典的迭代，首先我们关注一下循环条件：

v?&?(m0?^?m1)?

m0，m1 二者经过异或操作后的值为 00000100，可以看到只留下了最高位的值。

游标 v 与之做 & 操作，将其作为判断条件，即判断游标 v 在最高位是否还有值。

当高位为 0 时，说明较大字典已经迭代完毕。(因为较大字典的大小是较小字典的两倍，较大字典大小的最高位一定是 1)

到此为止，我们已经将 scan 的核心源码通读一遍了，相信很多其间的迷惑也随之解开。

不仅在写代码的时候更自信了，假如日后被面试官问起相关问题，那绝对可以趁机表现一番，想想还有点小激动。