那個深夜，我登上了公司的服務器，在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 函數分為4步：
- 解析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].
模擬問題
0x00 迭代過程中，沒有進行rehash
這個過程比較簡單，一般來說只需要最簡單粗暴的順序迭代就可以了，這種情況下沒什麼好說的。
0x01 迭代過程中，進行過rehash
但是字典的大小是能夠進行自動擴容的，我們不得不考慮以下兩個問題：
第一，假如字典擴容了，變成2倍的長度，這種情況下，能夠保證一定能遍歷所有最初的key，但是卻會出現大量重複。舉個例子：
比如當前的key數組大小是4，後來變為8了。假如從下表0，1，2，3順序掃描時，如果數組已經發生擴容，那麼前面的0，1，2，3slot裡面的數據會發生一部分遷移到對應的4，5，6，7slot裡面去，當掃描到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就沒有掃描出這部分元素出來，無法保證可用性。
0x10 迭代過程中，正在進行rehash
上面考慮的情況是，在迭代過程的間隙中，rehash已經完成。那麼會不會出現迭代進行中，切換遊標時，rehash也正在進行？當然可能會發生。
如果返回遊標1時正在進行rehash，那麼ht[0]（擴容之前的表）中的slot1中的部分數據可能已經rehash到 ht[1]（擴容之後的表）中的slot1或者slot4，此時必須將ht[0]和ht[1]中的相應slot全部遍歷,否則可能會有遺漏數據，但是這麼做好像也非常麻煩。
解決方法
為了解決以上兩個問題，Redis使用了一種稱為：reverse binary iteration的算法。源碼如下：
<code>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;}/<code>一起來理解下核心源碼，第一個if，else主要通過dictIsRehashing這個函數來判斷是否正在rehash；sizemask指的是字典空間長度，假如長度為16，那麼sizemask的二進制為00001111。m0 代表當前字典的長度，v代表遊標所在的索引值。接下來關注這個片段：
<code>v |= ~m0;v = rev(v);v++;v = rev(v);/<code>
這段代碼初看好像有點摸不著頭腦，怎麼多次在多次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，此時發現字典的大小已經從4rehash到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，那麼主要就是關注這段源碼：
<code> 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));/<code>m0代表rehash前的字典長度，假設為4，即00000011，m1代表rehash後的字典長度，假設為8，即00000111。
首先當前遊標 &m0可以得到較小字典中需要迭代的slot的索引，然後開始循環迭代。
然後開始較大字典的迭代，首先我們關注一下循環條件：
<code>v & (m0 ^ m1)/<code>
m0,m1二者經過異或操作後的值為00000100，可以看到只留下了最高位的值。遊標v與之做 &操作，將其作為判斷條件，即判斷遊標v在最高位是否還有值。當高位為0時，說明較大字典已經迭代完畢。（因為較大字典的大小是較小字典的兩倍，較大字典大小的最高位一定是1）
到此為止，我們已經將scan的核心源碼通讀一遍了，相信很多其間的迷惑也隨之解開。不僅在寫代碼的時候更自信了，假如日後被面試官問起相關問題，那絕對可以趁機表現一番，想想還有點小激動。
轉載：https://mp.weixin.qq.com/s/s7143MZPz3HpZqr8TT23gA
閱讀更多 瀟灑的程序員 的文章
