那個(gè)深夜，我登上了公司的服務(wù)器，在 redis 命令行里敲入 keys* 后，線(xiàn)上開(kāi)始報(bào)警，服務(wù)瞬間被卡死。
圖片來(lái)自 Pexels
我只能舉起雙手，焦急地等待幾千萬(wàn) key 被慢慢掃描，束手無(wú)策萬(wàn)念俱灰的時(shí)候，我收到了 Leader 的短信：你明天不用來(lái)上班了。
雖然上面是我的臆想，事實(shí)上很多公司的運(yùn)維也會(huì)禁用這些命令，來(lái)防止開(kāi)發(fā)出錯(cuò)。
但我在群里依然看到有同學(xué)在問(wèn)“為什么 Redis 不能用 keys?我覺(jué)得挺好的呀”時(shí)，為了不讓上面的情況發(fā)生，我決定寫(xiě)下這篇文章。
如何才能優(yōu)雅地遍歷 Redis?作為一種可以稱(chēng)為數(shù)據(jù)庫(kù)的組件，這是多么理所應(yīng)當(dāng)?shù)囊蟆?/p>
終于，Redis 在 2.8.0 版本新增了眾望所歸的 scan 操作，從此再也不用擔(dān)心敲入了 keys*，然后等著定時(shí)炸彈的引爆。
學(xué)會(huì)使用 scan 并不困難，那么問(wèn)題又來(lái)了，它是如何遍歷的?當(dāng)遍歷過(guò)程中加入了新的 key，當(dāng)遍歷過(guò)程中發(fā)生了擴(kuò)容，Redis 是如何解決的?
抱著深入學(xué)習(xí)的態(tài)度，以及為了能夠?qū)?lái)在面試官面前談笑風(fēng)生，讓我們一起來(lái)借此探索 Redis 的設(shè)計(jì)原理。
開(kāi)門(mén)見(jiàn)山，首先讓我們來(lái)總結(jié)一下 scan 的優(yōu)缺點(diǎn)。
優(yōu)點(diǎn)如下：
- 提供鍵空間的遍歷操作，支持游標(biāo)，復(fù)雜度 O(1)，整體遍歷一遍只需要 O(N)。
- 提供結(jié)果模式匹配。
- 支持一次返回的數(shù)據(jù)條數(shù)設(shè)置，但僅僅是個(gè) hints，有時(shí)候返回更多。
- 弱狀態(tài)，所有狀態(tài)只需要客戶(hù)端維護(hù)一個(gè)游標(biāo)。
缺點(diǎn)如下：
- 無(wú)法提供完整的快照遍歷，也就是中間如果有數(shù)據(jù)修改，可能有些涉及改動(dòng)的數(shù)據(jù)遍歷不到。
- 每次返回的數(shù)據(jù)條數(shù)不一定，極度依賴(lài)內(nèi)部實(shí)現(xiàn)。
- 返回的數(shù)據(jù)可能有重復(fù)，應(yīng)用層需要能夠處理重入邏輯。
所以 scan 是一個(gè)能夠滿(mǎn)足需求，但也不是完美無(wú)瑕的命令。下面來(lái)介紹一下原理，scan 到底是如何實(shí)現(xiàn)的?
scan，hscan 等命令主要都是借用了通用的 scan 操作函數(shù)：scanGenericCommand 。
scanGenericCommand 函數(shù)分為以下幾步：
- 解析 count 和 match 參數(shù)，如果沒(méi)有指定 count，默認(rèn)返回 10 條數(shù)據(jù)。
- 開(kāi)始迭代集合，如果是 key 保存為 ziplist 或者 intset，則一次性返回所有數(shù)據(jù)，沒(méi)有游標(biāo)(游標(biāo)值直接返回 0)。
由于 Redis 設(shè)計(jì)，只有數(shù)據(jù)量比較小的時(shí)候才會(huì)保存為 ziplist 或者 intset，所以此處不會(huì)影響性能。
游標(biāo)在保存為 hash 的時(shí)候發(fā)揮作用，具體入口函數(shù)為 dictScan，下文詳細(xì)描述。
- 根據(jù) match 參數(shù)過(guò)濾返回值，并且如果這個(gè)鍵已經(jīng)過(guò)期也會(huì)直接過(guò)濾掉(Redis 中鍵過(guò)期之后并不會(huì)立即刪除)。
當(dāng)?shù)粋€(gè)哈希表時(shí)，存在三種情況：
- 從迭代開(kāi)始到結(jié)束,哈希表沒(méi)有進(jìn)行 rehash。
- 從迭代開(kāi)始到結(jié)束,哈希表進(jìn)行了 rehash，但是每次迭代時(shí)，哈希表要么沒(méi)開(kāi)始 rehash，要么已經(jīng)結(jié)束了 rehash。
- 從迭代開(kāi)始到結(jié)束，某次或某幾次迭代時(shí)哈希表正在進(jìn)行 rehash。
在這三種情況之下，sacn 是如何實(shí)現(xiàn)的?首先需要知道的前提是：Redis 中進(jìn)行 rehash 擴(kuò)容時(shí)會(huì)存在兩個(gè)哈希表，ht[0] 與 ht[1]，rehash 是漸進(jìn)式的，即不會(huì)一次性完成。
新的鍵值對(duì)會(huì)存放到 ht[1] 中并且會(huì)逐步將 ht[0] 的數(shù)據(jù)轉(zhuǎn)移到 ht[1]。全部 rehash 完畢后，ht[1] 賦值給 ht[0] 然后清空ht[1]。
模擬問(wèn)題
①迭代過(guò)程中，沒(méi)有進(jìn)行 rehash
這個(gè)過(guò)程比較簡(jiǎn)單，一般來(lái)說(shuō)只需要最簡(jiǎn)單粗暴的順序迭代就可以了，這種情況下沒(méi)什么好說(shuō)的。
②迭代過(guò)程中，進(jìn)行過(guò) rehash
但是字典的大小是能夠進(jìn)行自動(dòng)擴(kuò)容的，我們不得不考慮以下兩個(gè)問(wèn)題：
第一，假如字典擴(kuò)容了，變成 2 倍的長(zhǎng)度，這種情況下，能夠保證一定能遍歷所有最初的 key，但是卻會(huì)出現(xiàn)大量重復(fù)。
舉個(gè)例子：比如當(dāng)前的 key 數(shù)組大小是 4，后來(lái)變?yōu)?8 了。假如從下表 0，1，2，3 順序掃描時(shí)，如果數(shù)組已經(jīng)發(fā)生擴(kuò)容。
那么前面的 0，1，2，3 slot 里面的數(shù)據(jù)會(huì)發(fā)生一部分遷移到對(duì)應(yīng)的 4，5，6，7 slot 里面去，當(dāng)掃描到 4，5，6，7 的 slot 時(shí)，無(wú)疑會(huì)出現(xiàn)值重復(fù)的情況。
需要知道的是，Redis 按如下方法計(jì)算一個(gè)當(dāng)前 key 擴(kuò)容后的 slot：hash(key)&(size-1)。
如圖，當(dāng)字典大小從 4 擴(kuò)容到 8 時(shí)，原先在 0 slot 的數(shù)據(jù)會(huì)分散到 0(000) 與 4(100) 兩個(gè) slot，對(duì)應(yīng)關(guān)系表如下：
第二， 如果字典縮小了，比如從 16 縮小到 8， 原先 scan 已經(jīng)遍歷了 0，1，2，3 ，如果數(shù)組已經(jīng)縮小。
這樣后來(lái)迭代停止在 7 號(hào) slot，但是 8，9，10，11 這幾個(gè) slot 的數(shù)據(jù)會(huì)分別合并到 0，1，2，3 里面去，從而 scan 就沒(méi)有掃描出這部分元素出來(lái)，無(wú)法保證可用性。
③迭代過(guò)程中，正在進(jìn)行 rehash
上面考慮的情況是，在迭代過(guò)程的間隙中，rehash 已經(jīng)完成。那么會(huì)不會(huì)出現(xiàn)迭代進(jìn)行中，切換游標(biāo)時(shí)，rehash 也正在進(jìn)行?當(dāng)然可能會(huì)發(fā)生。
如果返回游標(biāo) 1 時(shí)正在進(jìn)行 rehash，那么 ht[0](擴(kuò)容之前的表)中的 slot1 中的部分?jǐn)?shù)據(jù)可能已經(jīng) rehash 到 ht[1](擴(kuò)容之后的表)中的 slot1 或者 slot4。
此時(shí)必須將 ht[0] 和 ht[1] 中的相應(yīng) slot 全部遍歷，否則可能會(huì)有遺漏數(shù)據(jù)，但是這么做好像也非常麻煩。
解決方法
為了解決以上兩個(gè)問(wèn)題，Redis 使用了一種稱(chēng)為：reverse binary iteration 的算法。
源碼如下：
unsignedlongdictScan(dict*d,unsignedlongv,dictScanFunction*fn,void*privdata){if(!dictIsRehashing(d)){t0=(d->ht[0]);m0=t0->sizemask;/*Emitentriesatcursor*/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);returnv;}
一起來(lái)理解下核心源碼，第一個(gè) if，else 主要通過(guò) dictIsRehashing 這個(gè)函數(shù)來(lái)判斷是否正在 rehash。
sizemask 指的是字典空間長(zhǎng)度，假如長(zhǎng)度為 16，那么 sizemask 的二進(jìn)制為 00001111。m0 代表當(dāng)前字典的長(zhǎng)度，v 代表游標(biāo)所在的索引值。
接下來(lái)關(guān)注這個(gè)片段：
v|=~m0;v=rev(v);v++;v=rev(v);
這段代碼初看好像有點(diǎn)摸不著頭腦，怎么多次在多次 rev?我們來(lái)看下在字典長(zhǎng)度從 4 rehash 到 8 時(shí)，scan 是如何迭代的。
當(dāng)字典長(zhǎng)度為 4 時(shí)，m0 等于 4，二進(jìn)制表示為 00000011，那么 ~m0 為 11111100，v 初始值為 0，那么 v |=~m0為11111100。
接下來(lái)看圖：
可以看到，第一次 dictScan 后，游標(biāo)從 0 變成了 2，四次遍歷分別為 0→2→1→3，四個(gè)值都遍歷到了。
在字典長(zhǎng)度為 8 時(shí)，遍歷情況如下：
遍歷順序?yàn)椋?→4→2→6→1→5→3→7。
是不是察覺(jué)了什么?遍歷順序是不是順序是一致的?如果還沒(méi)發(fā)現(xiàn)，不妨再來(lái)看看字典長(zhǎng)度為 16 時(shí)的遍歷情況，以及三次順序的對(duì)比：
讓我們?cè)O(shè)想這么一個(gè)情況，字典的大小本身為 4，開(kāi)始迭代，當(dāng)游標(biāo)剛迭代完 slot0 時(shí)，返回的下一個(gè)游標(biāo)是 slot2。
此時(shí)發(fā)現(xiàn)字典的大小已經(jīng)從 4 rehash 到 8，那么不妨繼續(xù)從 size 為 8 的 hashtable 中 slot2 處繼續(xù)迭代。
有人會(huì)說(shuō)，不是把 slot4 遺漏掉了嗎?注意之前所說(shuō)的擴(kuò)容方式：hash(key)&(size-1)，slot0 和 slot4 的內(nèi)容是相同的，巧妙地避開(kāi)了重復(fù)，當(dāng)然，更不會(huì)遺漏。
如果你看到這里，你可能會(huì)發(fā)出和我一樣的感慨：我 X，這算法太牛 X 了。
沒(méi)錯(cuò)，上面的算法是由 Pieter Noordhuis 設(shè)計(jì)實(shí)現(xiàn)的，Redis 之父 Salvatore Sanfilippo 對(duì)該算法的評(píng)價(jià)是“Hard to explain but awesome。”
字典擴(kuò)大的情況沒(méi)問(wèn)題，那么縮小的情況呢?可以仿照著自己思考一下具體步驟。答案是可能會(huì)出現(xiàn)重復(fù)迭代，但是不會(huì)出現(xiàn)遺漏，也能夠保證可用性。
迭代過(guò)程中，進(jìn)行過(guò) rehash 這種情況下的迭代已經(jīng)比較完美地解決了，那么迭代過(guò)程中，正在進(jìn)行 rehash 的情況是如何解決的呢?
我們繼續(xù)看源碼，之前提到過(guò) dictIsRehashing 這個(gè)函數(shù)用來(lái)判斷是否正在進(jìn)行 rehash。
那么主要就是關(guān)注這段源碼：
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 前的字典長(zhǎng)度，假設(shè)為 4，即 00000011，m1 代表 rehash 后的字典長(zhǎng)度，假設(shè)為 8，即 00000111。
首先當(dāng)前游標(biāo) &m0 可以得到較小字典中需要迭代的 slot 的索引，然后開(kāi)始循環(huán)迭代。
然后開(kāi)始較大字典的迭代，首先我們關(guān)注一下循環(huán)條件：
v&(m0^m1)
m0，m1 二者經(jīng)過(guò)異或操作后的值為 00000100，可以看到只留下了最高位的值。
游標(biāo) v 與之做 & 操作，將其作為判斷條件，即判斷游標(biāo) v 在最高位是否還有值。
當(dāng)高位為 0 時(shí)，說(shuō)明較大字典已經(jīng)迭代完畢。(因?yàn)檩^大字典的大小是較小字典的兩倍，較大字典大小的最高位一定是 1)
到此為止，我們已經(jīng)將 scan 的核心源碼通讀一遍了，相信很多其間的迷惑也隨之解開(kāi)。
不僅在寫(xiě)代碼的時(shí)候更自信了，假如日后被面試官問(wèn)起相關(guān)問(wèn)題，那絕對(duì)可以趁機(jī)表現(xiàn)一番，想想還有點(diǎn)小激動(dòng)。
