首发于我的公众号：寒食君
那个深夜，我登上了公司的服务器，在Redis 命令行里敲入keys * 后，线上开始报警，服务瞬间被卡死，我只能举起双手，焦急地等待几千万key被慢慢扫描，束手无策万念俱灰的时候，我收到了leader的短信：你明天不用来上班了。
image
虽然上面是我的臆想，事实上很多公司的运维也会禁用这些命令，来防止开发出错。但我在群里依然看到有同学在问“为什么Redis不能用keys？我觉得挺好的呀”时，为了不让上面的情况发生，我决定写下这篇文章。
如何才能优雅地遍历Redis？作为一种可以称为数据库的组件，这是多么理所因当的要求。终于，Redis在2.8.0版本新增了众望所归的scan操作,从此再也不用担心敲入了keys*, 然后等着定时炸弹的引爆。
学会使用scan并不困难，那么问题又来了，它是如何遍历的？当遍历过程中加入了新的key，当遍历过程中发生了扩容，Redis是如何解决的？抱着深入学习的态度，以及为了能够将来在面试官面前谈笑风生，让我们一起来借此探索Redis的设计原理。
image
引言
开门见山，首先让我们来总结一下scan的优缺点。
优点：
- 提供键空间的遍历操作，支持游标，复杂度O(1), 整体遍历一遍只需要O(N)
- 提供结果模式匹配
- 支持一次返回的数据条数设置，但仅仅是个hints，有时候返回更多
- 弱状态，所有状态只需要客户端需要维护一个游标
缺点：
- 无法提供完整的快照遍历，也就是中间如果有数据修改，可能有些涉及改动的数据遍历不到
- 每次返回的数据条数不一定，极度依赖内部实现
- 返回的数据可能有重复，应用层需要能够处理重入逻辑
所以scan是一个能够满足需求,但也不是完美无瑕的命令。
下面来介绍一下原理,scan到底是如何实现的？scan,hscan等命令主要都是借用了通用的scan操作函数：scanGenericCommand 。
scanGenericCommand 函数分为4步：
- 解析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].
image
模拟问题
0x00 迭代过程中，没有进行rehash
这个过程比较简单，一般来说只需要最简单粗暴的顺序迭代就可以了，这种情况下没什么好说的。
0x01 迭代过程中，进行过rehash
但是字典的大小是能够进行自动扩容的，我们不得不考虑以下两个问题：
第一，假如字典扩容了，变成2倍的长度，这种情况下，能够保证一定能遍历所有最初的key，但是却会出现大量重复。举个例子：
比如当前的key数组大小是4，后来变为8了。假如从下表0，1，2，3顺序扫描时，如果数组已经发生扩容，那么前面的0，1，2，3slot里面的数据会发生一部分迁移到对应的4，5，6，7slot里面去，当扫描到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就没有扫描出这部分元素出来，无法保证可用性。
0x10 迭代过程中，正在进行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。接下来看图：
image.png
可以看到，第一次dictScan后，游标从0变成了2，四次遍历分别为 0 -> 2 -> 1 -> 3，四个值都遍历到了。
在字典长度为8时，遍历情况如下：
遍历顺序为：0 -> 4 -> 2 -> 6 -> 1 -> 5 -> 3 -> 7
是不是察觉了什么？遍历顺序是不是顺序是一致的？如果还没发现，不妨再来看看字典长度为16时的遍历情况，以及三次顺序的对比：
让我们设想这么一个情况，字典的大小本身为4，开始迭代，当游标刚迭代完slot0时，返回的下一个游标时slot2，此时发现字典的大小已经从4rehash到8，那么不妨继续从size为8的hashtable中slot2处继续迭代。有人会说，不是把slot4遗漏掉了吗？
注意之前所说的扩容方式：hash(key)&(size-1)，slot0和slot4的内容是相同的，巧妙地避开了重复，当然，更不会遗漏。
如果你看到这里，你可能会发出和我一样的感慨：我X，这算法太牛X了。没错，上面的算法是由Pieter Noordhuis设计实现的，Redis之父Salvatore Sanfilippo对该算法的评价是”Hard to explain but awesome。“
image
字典扩大的情况没问题，那么缩小的情况呢？可以仿照着自己思考一下具体步骤。答案是可能会出现重复迭代，但是不会出现遗漏，也能够保证可用性。
迭代过程中，进行过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的核心源码通读一遍了，相信很多其间的迷惑也随之解开。不仅在写代码的时候更自信了，假如日后被面试官问起相关问题，那绝对可以趁机表现一番，想想还有点小激动。
image
网友评论