當前位置:成語大全網 - 新華字典 - Redis 之用 scan 模糊匹配 key

Redis 之用 scan 模糊匹配 key

在 redis 實際使用中,會遇到壹個問題:如何從海量的 key 中找出滿足特定前綴的 key 列表來?

redis 提供了壹個簡單暴力的指令 keys 用來列出所有滿足特定正則字符串規則的 key。

這個指令有致命的弊端,在實際環境中最好不要使用:

我們可以通過配置設置禁用這些命令,在 redis.conf 中,在 SECURITY 這壹項中,我們新增以下命令:

另外,對於FLUSHALL命令,需要設置配置文件中appendonly no,否則服務器是無法啟動。

Redis 為了解決這個問題,它在 2.8 版本中加入了 scan 。scan 相比 keys 具備有以下特點:

SCAN 命令及其相關的 SSCAN 命令、 HSCAN 命令和 ZSCAN 命令都用於增量地叠代(incrementally iterate)壹集元素(a collection of elements):

scan 參數提供了三個參數,第壹個是 cursor 整數值 ,第二個是 key 的正則模式 ,第三個是 遍歷的 limit hint 。第壹次遍歷時,cursor 值為 0,然後將返回結果中第壹個整數值作為下壹次遍歷的 cursor。壹直遍歷到返回的 cursor 值為 0 時結束。

從上面的過程可以看到雖然提供的 limit 是 1000,但是返回的結果只有 10 個左右。因為這個 limit 不是限定返回結果的數量,而是限定服務器單次遍歷的字典槽位數量(約等於)。

在 Redis 中所有的 key 都存儲在壹個很大的字典中,這個字典的結構和 Java 中的 HashMap 壹樣,是壹維數組 + 二維鏈表結構,第壹維數組的大小總是 2^n(n>=0),擴容壹次數組大小空間加倍,也就是 n++。

scan 指令返回的遊標就是第壹維數組的位置索引,我們將這個位置索引稱為槽 (slot)。如果不考慮字典的擴容縮容,直接按數組下標挨個遍歷就行了。limit 參數就表示需要遍歷的槽位數,之所以返回的結果可能多可能少,是因為不是所有的槽位上都會掛接鏈表,有些槽位可能是空的,還有些槽位上掛接的鏈表上的元素可能會有多個。每壹次遍歷都會將 limit 數量的槽位上掛接的所有鏈表元素進行模式匹配過濾後,壹次性返回給客戶端。

scan 的遍歷順序非常特別。它不是從第壹維數組的第 0 位壹直遍歷到末尾,而是采用了高位進位加法來遍歷。之所以使用這樣特殊的方式進行遍歷,是考慮到字典的擴容和縮容時避免槽位的遍歷重復和遺漏。

高位進位法從左邊加,進位往右邊移動,同普通加法正好相反。但是最終它們都會遍歷所有的槽位並且沒有重復。

Java 中的 HashMap 有擴容的概念,當 loadFactor 達到閾值時,需要重新分配壹個新的 2 倍大小的數組,然後將所有的元素全部 rehash 掛到新的數組下面。rehash 就是將元素的 hash 值對數組長度進行取模運算,因為長度變了,所以每個元素掛接的槽位可能也發生了變化。又因為數組的長度是 2^n 次方,所以取模運算等價於位與操作。

這裏的 7, 15, 31 稱之為字典的 mask 值,mask 的作用就是保留 hash 值的低位,高位都被設置為 0。

接下來我們看看 rehash 前後元素槽位的變化。

假設當前的字典的數組長度由 8 位擴容到 16 位,那麽 3 號槽位 011 將會被 rehash 到 3 號槽位和 11 號槽位,也就是說該槽位鏈表中大約有壹半的元素還是 3 號槽位,其它的元素會放到 11 號槽位,11 這個數字的二進制是 1011,就是對 3 的二進制 011 增加了壹個高位 1。

抽象壹點說,假設開始槽位的二進制數是 xxx,那麽該槽位中的元素將被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典長度由 16 位擴容到 32 位,那麽對於二進制槽位 xxxx 中的元素將被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。

觀察這張圖,我們發現采用高位進位加法的遍歷順序,rehash 後的槽位在遍歷順序上是相鄰的。

假設當前要即將遍歷 110 這個位置 (橙色),那麽擴容後,當前槽位上所有的元素對應的新槽位是 0110 和 1110(深綠色),也就是在槽位的二進制數增加壹個高位 0 或 1。這時我們可以直接從 0110 這個槽位開始往後繼續遍歷,0110 槽位之前的所有槽位都是已經遍歷過的,這樣就可以避免擴容後對已經遍歷過的槽位進行重復遍歷。

再考慮縮容,假設當前即將遍歷 110 這個位置 (橙色),那麽縮容後,當前槽位所有的元素對應的新槽位是 10(深綠色),也就是去掉槽位二進制最高位。這時我們可以直接從 10 這個槽位繼續往後遍歷,10 槽位之前的所有槽位都是已經遍歷過的,這樣就可以避免縮容的重復遍歷。不過縮容還是不太壹樣,它會對圖中 010 這個槽位上的元素進行重復遍歷,因為縮融後 10 槽位的元素是 010 和 110 上掛接的元素的融合。

Java 的 HashMap 在擴容時會壹次性將舊數組下掛接的元素全部轉移到新數組下面。如果 HashMap 中元素特別多,線程就會出現卡頓現象。Redis 為了解決這個問題,它采用漸進式 rehash。

它會同時保留舊數組和新數組,然後在定時任務中以及後續對 hash 的指令操作中漸漸地將舊數組中掛接的元素遷移到新數組上。這意味著要操作處於 rehash 中的字典,需要同時訪問新舊兩個數組結構。如果在舊數組下面找不到元素,還需要去新數組下面去尋找。

scan 也需要考慮這個問題,對與 rehash 中的字典,它需要同時掃描新舊槽位,然後將結果融合後返回給客戶端。