因為不會Redis的scan命令，我被開除了
那個深夜，我登上了公司的服務器，在 Redis 命令行里敲入 keys* 后，線上開始報警，服務瞬間被卡死。
我只能舉起雙手，焦急地等待幾千萬 key 被慢慢掃描，束手無策萬念俱灰的時候，我收到了 Leader 的短信：你明天不用來上班了。
雖然上面是我的臆想，事實上很多公司的運維也會禁用這些命令，來防止開發出錯。
但我在群里依然看到有同學在問“為什么 Redis 不能用 keys?我覺得挺好的呀”時，為了不讓上面的情況發生，我決定寫下這篇文章。
如何才能優雅地遍歷 Redis?作為一種可以稱為數據庫的組件，這是多么理所應當的要求。
終于，Redis 在 2.8.0 版本新增了眾望所歸的 scan 操作，從此再也不用擔心敲入了 keys*，然后等著定時炸彈的引爆。
學會使用 scan 并不困難，那么問題又來了，它是如何遍歷的?當遍歷過程中加入了新的 key，當遍歷過程中發生了擴容，Redis 是如何解決的?
抱著深入學習的態度，以及為了能夠將來在面試官面前談笑風生，讓我們一起來借此探索 Redis 的設計原理。
開門見山，首先讓我們來總結一下 scan 的優缺點。
優點如下：
- 提供鍵空間的遍歷操作，支持游標，復雜度 O(1)，整體遍歷一遍只需要 O(N)。
- 提供結果模式匹配。
- 支持一次返回的數據條數設置，但僅僅是個 hints，有時候返回更多。
- 弱狀態，所有狀態只需要客戶端維護一個游標。
缺點如下：
- 無法提供完整的快照遍歷，也就是中間如果有數據修改，可能有些涉及改動的數據遍歷不到。
- 每次返回的數據條數不一定，極度依賴內部實現。
- 返回的數據可能有重復，應用層需要能夠處理重入邏輯。
所以 scan 是一個能夠滿足需求，但也不是完美無瑕的命令。下面來介紹一下原理，scan 到底是如何實現的?
scan，hscan 等命令主要都是借用了通用的 scan 操作函數：scanGenericCommand 。
scanGenericCommand 函數分為以下幾步：
- 解析 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]。
模擬問題
①迭代過程中，沒有進行 rehash
這個過程比較簡單，一般來說只需要最簡單粗暴的順序迭代就可以了，這種情況下沒什么好說的。
②迭代過程中，進行過 rehash
但是字典的大小是能夠進行自動擴容的，我們不得不考慮以下兩個問題：
第一，假如字典擴容了，變成 2 倍的長度，這種情況下，能夠保證一定能遍歷所有最初的 key，但是卻會出現大量重復。
舉個例子：比如當前的 key 數組大小是 4，后來變為 8 了。假如從下表 0，1，2，3 順序掃描時，如果數組已經發生擴容。
那么前面的 0，1，2，3 slot 里面的數據會發生一部分遷移到對應的 4，5，6，7 slot 里面去，當掃描到 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 就沒有掃描出這部分元素出來，無法保證可用性。
③迭代過程中，正在進行 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。
接下來看圖：
可以看到，第一次 dictScan 后，游標從 0 變成了 2，四次遍歷分別為 0→2→1→3，四個值都遍歷到了。
在字典長度為 8 時，遍歷情況如下：
遍歷順序為：0→4→2→6→1→5→3→7。
是不是察覺了什么?遍歷順序是不是順序是一致的?如果還沒發現，不妨再來看看字典長度為 16 時的遍歷情況，以及三次順序的對比：
讓我們設想這么一個情況，字典的大小本身為 4，開始迭代，當游標剛迭代完 slot0 時，返回的下一個游標是 slot2。
此時發現字典的大小已經從 4 rehash 到 8，那么不妨繼續從 size 為 8 的 hashtable 中 slot2 處繼續迭代。
有人會說，不是把 slot4 遺漏掉了嗎?注意之前所說的擴容方式：hash(key)&(size-1)，slot0 和 slot4 的內容是相同的，巧妙地避開了重復，當然，更不會遺漏。
如果你看到這里，你可能會發出和我一樣的感慨：我 X，這算法太牛 X 了。
沒錯，上面的算法是由 Pieter Noordhuis 設計實現的，Redis 之父 Salvatore Sanfilippo 對該算法的評價是“Hard to explain but awesome。”
字典擴大的情況沒問題，那么縮小的情況呢?可以仿照著自己思考一下具體步驟。答案是可能會出現重復迭代，但是不會出現遺漏，也能夠保證可用性。
迭代過程中，進行過 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 的核心源碼通讀一遍了，相信很多其間的迷惑也隨之解開。
不僅在寫代碼的時候更自信了，假如日后被面試官問起相關問題，那絕對可以趁機表現一番，想想還有點小激動。
