在平時線上 Redis 維護(hù)工作中，有時候需要從 Redis 實(shí)例成千上萬的 key 中找出特定前綴的 key 列表來手動處理數(shù)據(jù)，可能是修改它的值，也可能是刪除 key。這里就有一個問題，如何從海量的 key 中找出滿足特定前綴的 key 列表來？

Redis 提供了一個簡單暴力的指令 keys 用來列出所有滿足特定正則字符串規(guī)則的 key。

127.0.0.1:6379> set codehole1 a
OK
127.0.0.1:6379> set codehole2 b
OK
127.0.0.1:6379> set codehole3 c
OK
127.0.0.1:6379> set code1hole a
OK
127.0.0.1:6379> set code2hole b
OK
127.0.0.1:6379> set code3hole b
OK
127.0.0.1:6379> keys *
1) "codehole1"
2) "code3hole"
3) "codehole3"
4) "code2hole"
5) "codehole2"
6) "code1hole"
127.0.0.1:6379> keys codehole*
1) "codehole1"
2) "codehole3"
3) "codehole2"
127.0.0.1:6379> keys code*hole
1) "code3hole"
2) "code2hole"
3) "code1hole"

這個指令使用非常簡單，提供一個簡單的正則字符串即可，但是有很明顯的兩個缺點(diǎn)。

1. 沒有 offset、limit 參數(shù)，一次性吐出所有滿足條件的 key，萬一實(shí)例中有幾百 w 個 key 滿足條件，當(dāng)你看到滿屏的字符串刷的沒有盡頭時，你就知道難受了。
2. keys 算法是遍歷算法，復(fù)雜度是 O(n)，如果實(shí)例中有千萬級以上的 key，這個指令就會導(dǎo)致 Redis 服務(wù)卡頓，所有讀寫 Redis 的其它的指令都會被延后甚至?xí)瑫r報錯，因?yàn)?Redis 是單線程程序，順序執(zhí)行所有指令，其它指令必須等到當(dāng)前的 keys 指令執(zhí)行完了才可以繼續(xù)。

面對這兩個顯著的缺點(diǎn)該怎么辦呢？

Redis 為了解決這個問題，它在 2.8 版本中加入了大海撈針的指令——scan。scan 相比 keys 具備有以下特點(diǎn):

1. 復(fù)雜度雖然也是 O(n)，但是它是通過游標(biāo)分步進(jìn)行的，不會阻塞線程;
2. 提供 limit 參數(shù)，可以控制每次返回結(jié)果的最大條數(shù)，limit 只是一個 hint，返回的結(jié)果可多可少;
3. 同 keys 一樣，它也提供模式匹配功能;
4. 服務(wù)器不需要為游標(biāo)保存狀態(tài)，游標(biāo)的唯一狀態(tài)就是 scan 返回給客戶端的游標(biāo)整數(shù);
5. 返回的結(jié)果可能會有重復(fù)，需要客戶端去重復(fù)，這點(diǎn)非常重要;
6. 遍歷的過程中如果有數(shù)據(jù)修改，改動后的數(shù)據(jù)能不能遍歷到是不確定的;
7. 單次返回的結(jié)果是空的并不意味著遍歷結(jié)束，而要看返回的游標(biāo)值是否為零;

scan 基礎(chǔ)使用

在使用之前，讓我們往 Redis 里插入 10000 條數(shù)據(jù)來進(jìn)行測試

import redis

client = redis.StrictRedis()
for i in range(10000):
    client.set("key%d" % i, i)

好，Redis 中現(xiàn)在有了 10000 條數(shù)據(jù)，接下來我們找出以 key99 開頭 key 列表。

scan 參數(shù)提供了三個參數(shù)，第一個是 cursor 整數(shù)值，第二個是 key 的正則模式，第三個是遍歷的 limit hint。第一次遍歷時，cursor 值為 0，然后將返回結(jié)果中第一個整數(shù)值作為下一次遍歷的 cursor。一直遍歷到返回的 cursor 值為 0 時結(jié)束。

127.0.0.1:6379> scan 0 match key99* count 1000
1) "13976"
2)  1) "key9911"
    2) "key9974"
    3) "key9994"
    4) "key9910"
    5) "key9907"
    6) "key9989"
    7) "key9971"
    8) "key99"
    9) "key9966"
   10) "key992"
   11) "key9903"
   12) "key9905"
127.0.0.1:6379> scan 13976 match key99* count 1000
1) "1996"
2)  1) "key9982"
    2) "key9997"
    3) "key9963"
    4) "key996"
    5) "key9912"
    6) "key9999"
    7) "key9921"
    8) "key994"
    9) "key9956"
   10) "key9919"
127.0.0.1:6379> scan 1996 match key99* count 1000
1) "12594"
2) 1) "key9939"
   2) "key9941"
   3) "key9967"
   4) "key9938"
   5) "key9906"
   6) "key999"
   7) "key9909"
   8) "key9933"
   9) "key9992"
......
127.0.0.1:6379> scan 11687 match key99* count 1000
1) "0"
2)  1) "key9969"
    2) "key998"
    3) "key9986"
    4) "key9968"
    5) "key9965"
    6) "key9990"
    7) "key9915"
    8) "key9928"
    9) "key9908"
   10) "key9929"
   11) "key9944"

從上面的過程可以看到雖然提供的 limit 是 1000，但是返回的結(jié)果只有 10 個左右。因?yàn)檫@個 limit 不是限定返回結(jié)果的數(shù)量，而是限定服務(wù)器單次遍歷的字典槽位數(shù)量(約等于)。如果將 limit 設(shè)置為 10，你會發(fā)現(xiàn)返回結(jié)果是空的，但是游標(biāo)值不為零，意味著遍歷還沒結(jié)束。

127.0.0.1:6379> scan 0 match key99* count 10
1) "3072"
2) (empty list or set)

字典的結(jié)構(gòu)

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

image.png

scan 指令返回的游標(biāo)就是第一維數(shù)組的位置索引，我們將這個位置索引稱為槽 (slot)。如果不考慮字典的擴(kuò)容縮容，直接按數(shù)組下標(biāo)挨個遍歷就行了。limit 參數(shù)就表示需要遍歷的槽位數(shù)，之所以返回的結(jié)果可能多可能少，是因?yàn)椴皇撬械牟畚簧隙紩旖渔湵?，有些槽位可能是空的，還有些槽位上掛接的鏈表上的元素可能會有多個。每一次遍歷都會將 limit 數(shù)量的槽位上掛接的所有鏈表元素進(jìn)行模式匹配過濾后，一次性返回給客戶端。

scan 遍歷順序

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

首先我們用動畫演示一下普通加法和高位進(jìn)位加法的區(qū)別。

image

從動畫中可以看出高位進(jìn)位法從左邊加，進(jìn)位往右邊移動，同普通加法正好相反。但是最終它們都會遍歷所有的槽位并且沒有重復(fù)。

字典擴(kuò)容

Java 中的 HashMap 有擴(kuò)容的概念，當(dāng) loadFactor 達(dá)到閾值時，需要重新分配一個新的 2 倍大小的數(shù)組，然后將所有的元素全部 rehash 掛到新的數(shù)組下面。rehash 就是將元素的 hash 值對數(shù)組長度進(jìn)行取模運(yùn)算，因?yàn)殚L度變了，所以每個元素掛接的槽位可能也發(fā)生了變化。又因?yàn)閿?shù)組的長度是 2^n 次方，所以取模運(yùn)算等價于位與操作。

a mod 8 = a & (8-1) = a & 7
a mod 16 = a & (16-1) = a & 15
a mod 32 = a & (32-1) = a & 31

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

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

假設(shè)當(dāng)前的字典的數(shù)組長度由 8 位擴(kuò)容到 16 位，那么 3 號槽位 011 將會被 rehash 到 3 號槽位和 11 號槽位，也就是說該槽位鏈表中大約有一半的元素還是 3 號槽位，其它的元素會放到 11 號槽位，11 這個數(shù)字的二進(jìn)制是 1011，就是對 3 的二進(jìn)制 011 增加了一個高位 1。

image.png

抽象一點(diǎn)說，假設(shè)開始槽位的二進(jìn)制數(shù)是 xxx，那么該槽位中的元素將被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典長度由 16 位擴(kuò)容到 32 位，那么對于二進(jìn)制槽位 xxxx 中的元素將被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。

對比擴(kuò)容縮容前后的遍歷順序

image.png

觀察這張圖，我們發(fā)現(xiàn)采用高位進(jìn)位加法的遍歷順序，rehash 后的槽位在遍歷順序上是相鄰的。

假設(shè)當(dāng)前要即將遍歷 110 這個位置 (橙色)，那么擴(kuò)容后，當(dāng)前槽位上所有的元素對應(yīng)的新槽位是 0110 和 1110(深綠色)，也就是在槽位的二進(jìn)制數(shù)增加一個高位 0 或 1。這時我們可以直接從 0110 這個槽位開始往后繼續(xù)遍歷，0110 槽位之前的所有槽位都是已經(jīng)遍歷過的，這樣就可以避免擴(kuò)容后對已經(jīng)遍歷過的槽位進(jìn)行重復(fù)遍歷。

再考慮縮容，假設(shè)當(dāng)前即將遍歷 110 這個位置 (橙色)，那么縮容后，當(dāng)前槽位所有的元素對應(yīng)的新槽位是 10(深綠色)，也就是去掉槽位二進(jìn)制最高位。這時我們可以直接從 10 這個槽位繼續(xù)往后遍歷，10 槽位之前的所有槽位都是已經(jīng)遍歷過的，這樣就可以避免縮容的重復(fù)遍歷。不過縮容還是不太一樣，它會對圖中 010 這個槽位上的元素進(jìn)行重復(fù)遍歷，因?yàn)榭s融后 10 槽位的元素是 010 和 110 上掛接的元素的融合。

漸進(jìn)式 rehash

Java 的 HashMap 在擴(kuò)容時會一次性將舊數(shù)組下掛接的元素全部轉(zhuǎn)移到新數(shù)組下面。如果 HashMap 中元素特別多，線程就會出現(xiàn)卡頓現(xiàn)象。Redis 為了解決這個問題，它采用漸進(jìn)式 rehash。

它會同時保留舊數(shù)組和新數(shù)組，然后在定時任務(wù)中以及后續(xù)對 hash 的指令操作中漸漸地將舊數(shù)組中掛接的元素遷移到新數(shù)組上。這意味著要操作處于 rehash 中的字典，需要同時訪問新舊兩個數(shù)組結(jié)構(gòu)。如果在舊數(shù)組下面找不到元素，還需要去新數(shù)組下面去尋找。

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

更多的 scan 指令

scan 指令是一系列指令，除了可以遍歷所有的 key 之外，還可以對指定的容器集合進(jìn)行遍歷。比如 zscan 遍歷 zset 集合元素，hscan 遍歷 hash 字典的元素、sscan 遍歷 set 集合的元素。

它們的原理同 scan 都會類似的，因?yàn)?hash 底層就是字典，set 也是一個特殊的 hash(所有的 value 指向同一個元素)，zset 內(nèi)部也使用了字典來存儲所有的元素內(nèi)容，所以這里不再贅述。

大 key 掃描

有時候會因?yàn)闃I(yè)務(wù)人員使用不當(dāng)，在 Redis 實(shí)例中會形成很大的對象，比如一個很大的 hash，一個很大的 zset 這都是經(jīng)常出現(xiàn)的。這樣的對象對 Redis 的集群數(shù)據(jù)遷移帶來了很大的問題，因?yàn)樵诩涵h(huán)境下，如果某個 key 太大，會數(shù)據(jù)導(dǎo)致遷移卡頓。另外在內(nèi)存分配上，如果一個 key 太大，那么當(dāng)它需要擴(kuò)容時，會一次性申請更大的一塊內(nèi)存，這也會導(dǎo)致卡頓。如果這個大 key 被刪除，內(nèi)存會一次性回收，卡頓現(xiàn)象會再一次產(chǎn)生。

在平時的業(yè)務(wù)開發(fā)中，要盡量避免大 key 的產(chǎn)生。

如果你觀察到 Redis 的內(nèi)存大起大落，這極有可能是因?yàn)榇?key 導(dǎo)致的，這時候你就需要定位出具體是那個 key，進(jìn)一步定位出具體的業(yè)務(wù)來源，然后再改進(jìn)相關(guān)業(yè)務(wù)代碼設(shè)計(jì)。

那如何定位大 key 呢？

為了避免對線上 Redis 帶來卡頓，這就要用到 scan 指令，對于掃描出來的每一個 key，使用 type 指令獲得 key 的類型，然后使用相應(yīng)數(shù)據(jù)結(jié)構(gòu)的 size 或者 len 方法來得到它的大小，對于每一種類型，保留大小的前 N 名作為掃描結(jié)果展示出來。

上面這樣的過程需要編寫腳本，比較繁瑣，不過 Redis 官方已經(jīng)在 redis-cli 指令中提供了這樣的掃描功能，我們可以直接拿來即用。

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys

如果你擔(dān)心這個指令會大幅抬升 Redis 的 ops 導(dǎo)致線上報警，還可以增加一個休眠參數(shù)。

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys -i 0.1

上面這個指令每隔 100 條 scan 指令就會休眠 0.1s，ops 就不會劇烈抬升，但是掃描的時間會變長。