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

51CTO技术栈 2019-12-13

2107

“

那个深夜，我登上了公司的服务器，在 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));