那個深夜，我登上了公司的服務器，在 Redis 命令行里敲入 keys* 后，線上開始報警，服務瞬間被卡死。

[[285581]]
圖片來自 Pexels 

我只能舉起雙手，焦急地等待幾千萬 key 被慢慢掃描，束手無策萬念俱灰的時候，我收到了 Leader 的短信：你明天不用來上班了。

[[285582]] 

雖然上面是我的臆想，事實上很多公司的運維也會禁用這些命令，來防止開發(fā)出錯。

但我在群里依然看到有同學在問“為什么 Redis 不能用 keys?我覺得挺好的呀”時，為了不讓上面的情況發(fā)生，我決定寫下這篇文章。

如何才能優(yōu)雅地遍歷 Redis?作為一種可以稱為數(shù)據(jù)庫的組件，這是多么理所應當?shù)囊蟆?/p>

終于，Redis 在 2.8.0 版本新增了眾望所歸的 scan 操作，從此再也不用擔心敲入了 keys*，然后等著定時炸彈的引爆。

學會使用 scan 并不困難，那么問題又來了，它是如何遍歷的?當遍歷過程中加入了新的 key，當遍歷過程中發(fā)生了擴容，Redis 是如何解決的?

抱著深入學習的態(tài)度，以及為了能夠?qū)碓诿嬖嚬倜媲罢勑︼L生，讓我們一起來借此探索 Redis 的設計原理。

[[285583]] 

開門見山，首先讓我們來總結(jié)一下 scan 的優(yōu)缺點。

優(yōu)點如下：

• 提供鍵空間的遍歷操作，支持游標，復雜度 O(1)，整體遍歷一遍只需要 O(N)。
• 提供結(jié)果模式匹配。
• 支持一次返回的數(shù)據(jù)條數(shù)設置，但僅僅是個 hints，有時候返回更多。
• 弱狀態(tài)，所有狀態(tài)只需要客戶端維護一個游標。

缺點如下：

• 無法提供完整的快照遍歷，也就是中間如果有數(shù)據(jù)修改，可能有些涉及改動的數(shù)據(jù)遍歷不到。
• 每次返回的數(shù)據(jù)條數(shù)不一定，極度依賴內(nèi)部實現(xiàn)。
• 返回的數(shù)據(jù)可能有重復，應用層需要能夠處理重入邏輯。

所以 scan 是一個能夠滿足需求，但也不是完美無瑕的命令。下面來介紹一下原理，scan 到底是如何實現(xiàn)的?

scan，hscan 等命令主要都是借用了通用的 scan 操作函數(shù)：scanGenericCommand 。

scanGenericCommand 函數(shù)分為以下幾步：

• 解析 count 和 match 參數(shù)，如果沒有指定 count，默認返回 10 條數(shù)據(jù)。
• 開始迭代集合，如果是 key 保存為 ziplist 或者 intset，則一次性返回所有數(shù)據(jù)，沒有游標(游標值直接返回 0)。

由于 Redis 設計，只有數(shù)據(jù)量比較小的時候才會保存為 ziplist 或者 intset，所以此處不會影響性能。

游標在保存為 hash 的時候發(fā)揮作用，具體入口函數(shù)為 dictScan，下文詳細描述。

• 根據(jù) match 參數(shù)過濾返回值，并且如果這個鍵已經(jīng)過期也會直接過濾掉(Redis 中鍵過期之后并不會立即刪除)。

當?shù)粋€哈希表時，存在三種情況：

• 從迭代開始到結(jié)束,哈希表沒有進行 rehash。
• 從迭代開始到結(jié)束,哈希表進行了 rehash，但是每次迭代時，哈希表要么沒開始 rehash，要么已經(jīng)結(jié)束了 rehash。
• 從迭代開始到結(jié)束，某次或某幾次迭代時哈希表正在進行 rehash。

在這三種情況之下，sacn 是如何實現(xiàn)的?首先需要知道的前提是：Redis 中進行 rehash 擴容時會存在兩個哈希表，ht[0] 與 ht[1]，rehash 是漸進式的，即不會一次性完成。

新的鍵值對會存放到 ht[1] 中并且會逐步將 ht[0] 的數(shù)據(jù)轉(zhuǎn)移到 ht[1]。全部 rehash 完畢后，ht[1] 賦值給 ht[0] 然后清空ht[1]。

[[285584]] 

模擬問題

①迭代過程中，沒有進行 rehash

這個過程比較簡單，一般來說只需要最簡單粗暴的順序迭代就可以了，這種情況下沒什么好說的。

②迭代過程中，進行過 rehash

但是字典的大小是能夠進行自動擴容的，我們不得不考慮以下兩個問題：

第一，假如字典擴容了，變成 2 倍的長度，這種情況下，能夠保證一定能遍歷所有最初的 key，但是卻會出現(xiàn)大量重復。

舉個例子：比如當前的 key 數(shù)組大小是 4，后來變?yōu)?8 了。假如從下表 0，1，2，3 順序掃描時，如果數(shù)組已經(jīng)發(fā)生擴容。

那么前面的 0，1，2，3 slot 里面的數(shù)據(jù)會發(fā)生一部分遷移到對應的 4，5，6，7 slot 里面去，當掃描到 4，5，6，7 的 slot 時，無疑會出現(xiàn)值重復的情況。

需要知道的是，Redis 按如下方法計算一個當前 key 擴容后的 slot：hash(key)&(size-1)。

如圖，當字典大小從 4 擴容到 8 時，原先在 0 slot 的數(shù)據(jù)會分散到 0(000) 與 4(100) 兩個 slot，對應關(guān)系表如下：

 

第二， 如果字典縮小了，比如從 16 縮小到 8， 原先 scan 已經(jīng)遍歷了 0，1，2，3 ，如果數(shù)組已經(jīng)縮小。

這樣后來迭代停止在 7 號 slot，但是 8，9，10，11 這幾個 slot 的數(shù)據(jù)會分別合并到 0，1，2，3 里面去，從而 scan 就沒有掃描出這部分元素出來，無法保證可用性。

③迭代過程中，正在進行 rehash

上面考慮的情況是，在迭代過程的間隙中，rehash 已經(jīng)完成。那么會不會出現(xiàn)迭代進行中，切換游標時，rehash 也正在進行?當然可能會發(fā)生。

如果返回游標 1 時正在進行 rehash，那么 ht[0](擴容之前的表)中的 slot1 中的部分數(shù)據(jù)可能已經(jīng) rehash 到 ht[1](擴容之后的表)中的 slot1 或者 slot4。

此時必須將 ht[0] 和 ht[1] 中的相應 slot 全部遍歷，否則可能會有遺漏數(shù)據(jù)，但是這么做好像也非常麻煩。

解決方法

為了解決以上兩個問題，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 這個函數(shù)來判斷是否正在 rehash。

sizemask 指的是字典空間長度，假如長度為 16，那么 sizemask 的二進制為 00001111。m0 代表當前字典的長度，v 代表游標所在的索引值。

接下來關(guān)注這個片段：

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。 

是不是察覺了什么?遍歷順序是不是順序是一致的?如果還沒發(fā)現(xiàn)，不妨再來看看字典長度為 16 時的遍歷情況，以及三次順序的對比：

 

讓我們設想這么一個情況，字典的大小本身為 4，開始迭代，當游標剛迭代完 slot0 時，返回的下一個游標是 slot2。

此時發(fā)現(xiàn)字典的大小已經(jīng)從 4 rehash 到 8，那么不妨繼續(xù)從 size 為 8 的 hashtable 中 slot2 處繼續(xù)迭代。

有人會說，不是把 slot4 遺漏掉了嗎?注意之前所說的擴容方式：hash(key)&(size-1)，slot0 和 slot4 的內(nèi)容是相同的，巧妙地避開了重復，當然，更不會遺漏。

如果你看到這里，你可能會發(fā)出和我一樣的感慨：我 X，這算法太牛 X 了。

沒錯，上面的算法是由 Pieter Noordhuis 設計實現(xiàn)的，Redis 之父 Salvatore Sanfilippo 對該算法的評價是“Hard to explain but awesome。”

[[285587]] 

字典擴大的情況沒問題，那么縮小的情況呢?可以仿照著自己思考一下具體步驟。答案是可能會出現(xiàn)重復迭代，但是不會出現(xiàn)遺漏，也能夠保證可用性。

迭代過程中，進行過 rehash 這種情況下的迭代已經(jīng)比較完美地解決了，那么迭代過程中，正在進行 rehash 的情況是如何解決的呢?

我們繼續(xù)看源碼，之前提到過 dictIsRehashing 這個函數(shù)用來判斷是否正在進行 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 前的字典長度，假設為 4，即 00000011，m1 代表 rehash 后的字典長度，假設為 8，即 00000111。

首先當前游標 &m0 可以得到較小字典中需要迭代的 slot 的索引，然后開始循環(huán)迭代。

然后開始較大字典的迭代，首先我們關(guān)注一下循環(huán)條件：

v & (m0 ^ m1) 

m0，m1 二者經(jīng)過異或操作后的值為 00000100，可以看到只留下了最高位的值。

游標 v 與之做 & 操作，將其作為判斷條件，即判斷游標 v 在最高位是否還有值。

當高位為 0 時，說明較大字典已經(jīng)迭代完畢。(因為較大字典的大小是較小字典的兩倍，較大字典大小的最高位一定是 1)

到此為止，我們已經(jīng)將 scan 的核心源碼通讀一遍了，相信很多其間的迷惑也隨之解開。

[[285588]] 

不僅在寫代碼的時候更自信了，假如日后被面試官問起相關(guān)問題，那絕對可以趁機表現(xiàn)一番，想想還有點小激動。