1. 首页
  2. IT资讯

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

“u003Cpu003E那个深夜,我登上了公司的服务器,在Redis 命令行里敲入 keys* 后,线上开始报警,服务瞬间被卡死,我只能举起双手,焦急地等待几千万key被慢慢扫描,束手无策万念俱灰的时候,我收到了leader的短信:你明天不用来上班了。u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002F1e17ec62cd26442a8cd73a2861dbf4af” img_width=”300″ img_height=”450″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E虽然上面是我的臆想,事实上很多公司的运维也会禁用这些命令,来防止开发出错。但我在群里依然看到有同学在问“为什么Redis不能用 keys?我觉得挺好的呀”时,为了不让上面的情况发生,我决定写下这篇文章。u003Cu002Fpu003Eu003Cpu003E如何才能优雅地遍历Redis?作为一种可以称为数据库的组件,这是多么理所因当的要求。终于,Redis在2.8.0版本新增了众望所归的 scan操作,从此再也不用担心敲入了keys*, 然后等着定时炸弹的引爆。u003Cu002Fpu003Eu003Cpu003E学会使用 scan并不困难,那么问题又来了,它是如何遍历的?当遍历过程中加入了新的key,当遍历过程中发生了扩容,Redis是如何解决的?抱着深入学习的态度,以及为了能够将来在面试官面前谈笑风生,让我们一起来借此探索Redis的设计原理。u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002F4964d6630c5e40e48b71dc08904be911″ img_width=”300″ img_height=”300″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E引言u003Cu002Fpu003Eu003Cpu003E开门见山,首先让我们来总结一下 scan的优缺点。u003Cu002Fpu003Eu003Cpu003E优点:u003Cu002Fpu003Eu003Cul class=”list-paddingleft-2″u003Eu003Cliu003E提供键空间的遍历操作,支持游标,复杂度O(1), 整体遍历一遍只需要O(N)u003Cu002Fliu003Eu003Cliu003E提供结果模式匹配u003Cu002Fliu003Eu003Cliu003E支持一次返回的数据条数设置,但仅仅是个hints,有时候返回更多u003Cu002Fliu003Eu003Cliu003E弱状态,所有状态只需要客户端需要维护一个游标u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cpu003E缺点:u003Cu002Fpu003Eu003Cul class=”list-paddingleft-2″u003Eu003Cliu003E无法提供完整的快照遍历,也就是中间如果有数据修改,可能有些涉及改动的数据遍历不到u003Cu002Fliu003Eu003Cliu003E每次返回的数据条数不一定,极度依赖内部实现u003Cu002Fliu003Eu003Cliu003E返回的数据可能有重复,应用层需要能够处理重入逻辑u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cpu003E所以scan是一个能够满足需求,但也不是完美无瑕的命令。u003Cu002Fpu003Eu003Cpu003E下面来介绍一下原理,u003Cstrongu003Escan到底是如何实现u003Cu002Fstrongu003E的?scan,hscan等命令主要都是借用了通用的scan操作函数:scanGenericCommand 。u003Cu002Fpu003Eu003Cpu003EscanGenericCommand 函数分为4步:u003Cu002Fpu003Eu003Cul class=”list-paddingleft-2″u003Eu003Cliu003E解析count和match参数.如果没有指定count,默认返回10条数据u003Cu002Fliu003Eu003Cliu003E开始迭代集合,如果是key保存为ziplist或者intset,则一次性返回所有数据,没有游标(游标值直接返回0).由于Redis设计,只有数据量比较小的时候才会保存为ziplist或者intset,所以此处不会影响性能.游标在保存为hash的时候发挥作用,具体入口函数为dictScan,下文详细描述。u003Cu002Fliu003Eu003Cliu003E根据match参数过滤返回值,并且如果这个键已经过期也会直接过滤掉(Redis中键过期之后并不会立即删除)u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cpu003E当迭代一个哈希表时,存在u003Cstrongu003E三种情况u003Cu002Fstrongu003E:u003Cu002Fpu003Eu003Col start=”1″u003Eu003Cliu003E从迭代开始到结束,哈希表没有进行rehashu003Cu002Fliu003Eu003Cliu003E从迭代开始到结束,哈希表进行了rehash,但是每次迭代时,哈希表要么没开始rehash,要么已经结束了rehashu003Cu002Fliu003Eu003Cliu003E从迭代开始到结束,某次或某几次迭代时哈希表正在进行rehashu003Cu002Fliu003Eu003Cu002Folu003Eu003Cpu003E在这三种情况之下,sacn是如何实现的?u003Cu002Fpu003Eu003Cpu003E首先u003Cstrongu003E需要知道的前提u003Cu002Fstrongu003E是:Redis中进行rehash扩容时会存在两个哈希表,ht[0]与ht[1],rehash是渐进式的,即不会一次性完成。新的键值对会存放到ht[1]中并且会逐步将ht[0]的数据转移到ht[1].全部rehash完毕后,ht[1]赋值给ht[0]然后清空ht[1].u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002F18554afa70fd4f568af4b27134a19785″ img_width=”298″ img_height=”289″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003Eu003Cstrongu003E模拟问题u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E0x00 迭代过程中,没有进行rehashu003Cu002Fpu003Eu003Cpu003E这个过程比较简单,一般来说只需要最简单粗暴的顺序迭代就可以了,这种情况下没什么好说的。u003Cu002Fpu003Eu003Cpu003E0x01 迭代过程中,进行过rehashu003Cu002Fpu003Eu003Cpu003E但是字典的大小是能够进行自动扩容的,我们不得不考虑以下两个问题:u003Cu002Fpu003Eu003Cpu003E第一,假如字典扩容了,变成2倍的长度,这种情况下,能够保证一定能遍历所有最初的key,但是却会出现大量重复。举个例子:u003Cu002Fpu003Eu003Cpu003E比如当前的key数组大小是4,后来变为8了。假如从下表0,1,2,3顺序扫描时,如果数组已经发生扩容,那么前面的0,1,2,3slot里面的数据会发生一部分迁移到对应的4,5,6,7slot里面去,当扫描到4,5,6,7的slot时,无疑会出现值重复的情况。u003Cu002Fpu003Eu003Cpu003E需要知道的是,Redis按如下方法计算一个当前key扩容后的slot:u003Cstrongu003Ehash(key)&(size-1)u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E如图,当从字典大小从4扩容到8时,原先在0 slot的数据会分散到0(000)与4(100)两个slot,对应关系表如下:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp9.pstatp.comu002Flargeu002Fpgc-imageu002Fd6f130d6a26545c1898ddf3e830462c1″ img_width=”232″ img_height=”148″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E第二, 如果字典缩小了,比如从16缩小到8, 原先scan已经遍历了0,1,2,3 ,如果数组已经缩小。这样后来迭代停止在7号slot,但是8,9,10,11这几个slot的数据会分别合并到0,1,2,3里面去,从而scan就没有扫描出这部分元素出来,无法保证可用性。u003Cu002Fpu003Eu003Cpu003E0x10 迭代过程中,正在进行rehashu003Cu002Fpu003Eu003Cpu003E上面考虑的情况是,在迭代过程的间隙中,rehash已经完成。那么会不会出现迭代进行中,切换游标时,rehash也正在进行?当然可能会发生。u003Cu002Fpu003Eu003Cpu003E如果返回游标1时正在进行rehash,那么ht[0](扩容之前的表)中的slot1中的部分数据可能已经rehash到 ht[1](扩容之后的表)中的slot1或者slot4,此时必须将ht[0]和ht[1]中的相应slot全部遍历,否则可能会有遗漏数据,但是这么做好像也非常麻烦。u003Cu002Fpu003Eu003Cpu003Eu003Cstrongu003E解决方法u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E为了解决以上两个问题,Redis使用了一种称为:reverse binary iteration的算法。源码如下:u003Cu002Fpu003Eu003Cpreu003Eunsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata){ if (!dictIsRehashing(d)) { t0 = (d->ht[0]); m0 = t0->sizemask; u002F* Emit entries at cursor *u002F 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;}u003Cu002Fpreu003Eu003Cpu003E一起来理解下核心源码,第一个if,else主要通过dictIsRehashing这个函数来判断是否正在rehash;sizemask指的是字典空间长度,假如长度为16,那么sizemask的二进制为00001111。m0 代表当前字典的长度,v代表游标所在的索引值。接下来关注这个片段:u003Cu002Fpu003Eu003Cpreu003Ev |= ~m0;v = rev(v);v++;v = rev(v);u003Cu002Fpreu003Eu003Cpu003E这段代码初看好像有点摸不着头脑,怎么多次在多次rev?我们来看下在字典长度从4 rehash到8时,scan是如何迭代的。u003Cu002Fpu003Eu003Cpu003E当字典长度为4时,m0等于4,二进制表示为00000011,那么~m0为11111100,v初始值为0,那么 v |= ~m0为11111100。接下来看图:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002F217d3455a9054b4c999cf3e93b8e0af0″ img_width=”751″ img_height=”319″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E可以看到,第一次dictScan后,游标从0变成了2,四次遍历分别为 0 -> 2 -> 1 -> 3,四个值都遍历到了。u003Cu002Fpu003Eu003Cpu003E在字典长度为8时,遍历情况如下:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002Ffc0e404d663d40c2ba70ae3f48ed85a8″ img_width=”492″ img_height=”645″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E遍历顺序为:0 -> 4 -> 2 -> 6 -> 1 -> 5 -> 3 -> 7u003Cu002Fpu003Eu003Cpu003E是不是察觉了什么?遍历顺序是不是顺序是一致的?如果还没发现,不妨再来看看字典长度为16时的遍历情况,以及三次顺序的对比:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002Fd08c62435f3546748a98d3cb066e550a” img_width=”520″ img_height=”800″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E让我们设想这么一个情况,字典的大小本身为4,开始迭代,当游标刚迭代完slot0时,返回的下一个游标时slot2,此时发现字典的大小已经从4rehash到8,那么不妨继续从size为8的hashtable中slot2处继续迭代。有人会说,不是把slot4遗漏掉了吗?u003Cu002Fpu003Eu003Cpu003E注意之前所说的扩容方式:u003Cstrongu003Ehash(key)&(size-1)u003Cu002Fstrongu003E,slot0和slot4的内容是相同的,巧妙地避开了重复,当然,更不会遗漏。u003Cu002Fpu003Eu003Cpu003E如果你看到这里,你可能会发出和我一样的感慨:我X,这算法太牛X了。没错,上面的算法是由Pieter Noordhuis设计实现的,Redis之父Salvatore Sanfilippo对该算法的评价是u003Cstrongu003E”Hard to explain but awesome。“u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp9.pstatp.comu002Flargeu002Fpgc-imageu002F680dd31950694a12a73bec5bd9dd1ab0″ img_width=”190″ img_height=”190″ alt=”因为不会Redis的scan命令,我被开除了” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E字典扩大的情况没问题,那么缩小的情况呢?可以仿照着自己思考一下具体步骤。答案是可能会出现重复迭代,但是不会出现遗漏,也能够保证可用性。u003Cu002Fpu003Eu003Cpu003Eu003Cstrongu003E迭代过程中,进行过rehashu003Cu002Fstrongu003E这种情况下的迭代已经比较完美地解决了,那么u003Cstrongu003E迭代过程中,正在进行rehashu003Cu002Fstrongu003E的情况是如何解决的呢?u003Cu002Fpu003Eu003Cpu003E我们继续看源码,之前提到过dictIsRehashing这个函数用来判断是否正在进行rehash,那么主要就是关注这段源码:u003Cu002Fpu003Eu003Cpreu003E 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));u003Cu002Fpreu003Eu003Cpu003Em0代表rehash前的字典长度,假设为4,即00000011,m1代表rehash后的字典长度,假设为8,即00000111。u003Cu002Fpu003Eu003Cpu003E首先当前游标 &m0可以得到较小字典中需要迭代的slot的索引,然后开始循环迭代。u003Cu002Fpu003Eu003Cpu003E然后开始较大字典的迭代,首先我们关注一下循环条件:u003Cu002Fpu003Eu003Cpreu003Ev & (m0 ^ m1)u003Cu002Fpreu003Eu003Cpu003Em0,m1二者经过异或操作后的值为00000100,可以看到只留下了最高位的值。游标v与之做 &操作,将其作为判断条件,即判断游标v在最高位是否还有值。当高位为0时,说明较大字典已经迭代完毕。(因为较大字典的大小是较小字典的两倍,较大字典大小的最高位一定是1)u003Cu002Fpu003Eu003Cpu003E到此为止,我们已经将scan的核心源码通读一遍了,相信很多其间的迷惑也随之解开。不仅在写代码的时候更自信了,假如日后被面试官问起相关问题,那绝对可以趁机表现一番,想想还有点小激动。u003Cbru002Fu003Eu003Cu002Fpu003Eu003Cpu003E转载:https:u002Fu002Fmp.weixin.qq.comu002Fsu002Fs7143MZPz3HpZqr8TT23gAu003Cu002Fpu003E”

原文始发于:因为不会Redis的scan命令,我被开除了

主题测试文章,只做测试使用。发布者:程序员,转转请注明出处:http://www.cxybcw.com/26358.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code