，因为我不知道Redis的scan命令。半夜，我登录了公司的服务器。在Redis命令行输入keys*后，在线启动告警，服务瞬间卡住。图片来自Pexels。只能举起双手，焦急地等待着那千万个钥匙被慢慢扫描。正在我束手无策的时候，收到领导发来的短信：明天不用上班了。以上虽然是我的想象，但实际上很多公司的运维也会禁用这些命令，防止开发出错。但是还是看到群里有同学问“Redis为什么不能用key？我觉得挺好的”，为了防止以上情况的发生，我决定写这篇文章。如何优雅地遍历Redis？作为一个可以称为数据库的组件，这是一个合理的要求。最后，Redis在2.8.0版本中加入了万众期待的scan操作，这样你就不用担心敲键盘*等待定时炸弹引爆了。学会使用scan并不难，那么问题又来了，它是如何遍历的呢？当遍历过程中增加了新的key，遍历过程中发生了扩容，Redis是如何解决的？本着深入学习的态度，也为了以后能够在面试官面前有说有笑，让我们一起来探讨一下Redis的设计原理吧。切入正题，首先让我们总结一下扫描的优缺点。优点如下：提供键空间遍历操作，支持游标，复杂度O(1)，整体遍历只需要O(N)。提供生成的模式匹配。支持设置一次返回的数据条数，但只是提示，有时会返回更多。弱状态，所有状态只需要客户端维护一个游标。缺点是：不能提供完整的快照遍历，即如果中间有数据修改，部分参与修改的数据可能无法遍历。每次返回的数据条数不一定，极度依赖内部实现。返回的数据可能会重复，需要应用层能够处理重入逻辑。所以scan是一个可以满足需求的命令，但并不完美。下面介绍一下原理。扫描是如何实现的？scan、hscan等命令主要借用通用扫描操作函数：scanGenericCommand。scanGenericCommand函数分为以下几步：解析count和match参数，如果不指定count，默认返回10条数据。开始迭代集合。如果key保存为ziplist或intset，则一次性返回所有数据，不带游标（游标值直接返回0）。由于Redis的设计，只有当数据量比较少的时候才会保存为ziplist或者intset，所以这里不会影响性能。游标在保存为散列时发挥作用。具体的入口函数是dictScan，下面会详细介绍。根据match参数过滤返回值，如果key已经过期，则直接过滤掉（Redis中的key过期后不会立即删除）。在迭代哈希表时，有以下三种情况：从迭代开始到迭代结束，哈希表都没有重新哈希。从迭代开始到结束，哈希表都进行了rehash，但是每次迭代，哈希表要么没有开始rehash，要么已经结束rehash。从迭代的开始到结束，哈希表在一次或多次迭代中被重新哈希。这三种情况，sacn是如何实现的呢？首先要知道的是，rehash扩容的时候Redis中会有两个hash表，ht[0]和ht[1]，rehash是渐进的，也就是不会一口气做完。新的键值对会存储在ht[1]中，ht[0]中的数据会逐渐转移到ht[1]中。全部rehash完成后，ht[1]赋值给ht[0]，然后ht[1]清零。模拟题①迭代过程中，不进行rehash的过程比较简单。一般来说，只需要最简单粗暴的顺序迭代即可。既然如此，那就无话可说了。②在迭代过程中，进行了rehash，但字典的大小可以自动扩展。我们要考虑以下两个问题：第一，如果字典扩充到原来的两倍长度，这种情况下，肯定可以遍历所有原来的key，但是会出现很多重复。例如：比如当前key数组大小为4，后来改为8。如果从下表0、1、2、3依次扫描，如果数组已经扩容。那么之前的slot0,1,2,3中的部分数据会迁移到对应的slot4,5,6,7中。当扫描到slot4,5,6,7时，无疑会有值重复的情况。需要知道的是，Redis在当前key扩容后计算一个slot，如下：hash(key)&(size-1)。如图所示，当字典大小从4扩充到8时，原来0号槽中的数据会被分配到0(000)和4(100)两个槽中。对应关系表如下：二、字典缩减，比如从16条缩减到8条，如果数组已经缩减，则原扫描已经遍历了0,1,2,3。这样后面的迭代就停在了7号槽，但是8、9、10、11号槽的数据会分别合并到0、1、2、3号槽中，这样scan就不会扫描出来了这些元素，并不能保证可用性。③在迭代过程中，rehash正在进行上面考虑的情况是在迭代过程的间隙，已经完成了rehash。那么会不会出现在切换游标的时候迭代在进行，rehash也在进行呢？当然有可能发生。如果返回游标1时正在进行重新散列，则ht[0]（扩展前的表）中的slot1中的某些数据可能已重新散列到ht[1]（扩展后的表）中的slot1或slot4。此时必须遍历ht[0]和ht[1]中所有对应的槽位，否则可能会丢失数据，不过这样做好像很麻烦。解决方案为了解决以上两个问题，Redis使用了一种算法，叫做：反向二元迭代。源码如下：unsignedlongdictScan(dict*d,unsignedlongv,dictScanFunction*fn,void*privdata){if(!dictIsRehashing(d)){t0=(d->ht[0]);m0=t0->sizemask;/*光标处的发射体*/while(de){fn(privdata,de);de=de->next;}}else{m0=t0->sizemask;m1=t1->sizemask;de=t0->表[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);returnv;}下面一起来了解一下核心源码。第一个if,else主要是利用函数dictIsRehashing来判断是否在进行rehashing。sizemask是指字典空间的长度。如果长度为16，那么sizemask的二进制值为00001111。m0表示当前字典的长度，v表示光标所在的索引值。接下来，注意这个片段：v|=~m0;v=rev(v);v++;v=rev(v);这段代码乍一看有点乱，为什么要rev多次呢？下面看看字典长度从4rehash到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。这时候发现字典的size已经从4重新hash到8了，那我们还不如继续从size为8的hashtable中的slot2开始迭代。有人会说，slot4不就是吗省略？注意前面提到的扩容方式：hash(key)&(size-1)，slot0和slot4的内容是一样的，巧妙的避免了重复，当然不会遗漏更多。看到这里，你可能会表达和我一样的感慨：我是X，这个算法太牛逼了。没错，上面的算法就是由PieterNoordhuis设计实现的。Redis之父SalvatoreSanfilippo评价该算法“难以解释但很棒”。字典扩容没问题，那么缩水情况呢？你可以自己模仿想想具体的步骤。答案是可能会反复迭代，但不会有遗漏，可用性也能得到保证。在迭代过程中，已经完美解决了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可以得到在较小的字典中需要迭代的槽的索引，然后开始循环迭代。然后开始迭代更大的字典。首先我们注意循环条件：v&(m0^m1)m0,m1异或后的值为00000100，可以看到只剩下最高值了。游标v对其进行&运算，并将其作为判断条件，即判断游标v在最高位置是否还有值。当高位为0时，表示迭代了较大的字典。（因为大字典的大小是小字典的两倍，所以大字典的大小的最高位一定是1）至此，我们已经阅读了scan的核心源码，相信很多困惑将得到解决。打开。不仅写代码的时候更有自信，以后如果被面试官问到相关问题，你绝对可以趁机表现一下，想想就有点小激动。
