在 redis 實(shí)際使用中，會(huì)遇到一個(gè)問(wèn)題：如何從海量的 key 中找出滿足特定前綴的 key 列表來(lái)？
1. 不要使用 keys*
redis 提供了一個(gè)簡(jiǎn)單暴力的指令 keys 用來(lái)列出所有滿足特定正則字符串規(guī)則的 key。
keys xxx*
這個(gè)指令有致命的弊端，在實(shí)際環(huán)境中最好不要使用：
這個(gè)指令沒(méi)有 offset、limit 參數(shù)，是要一次性吐出所有滿足條件的 key，由于 redis 是單線程的，其所有操作都是原子的，而 keys 算法是遍歷算法，復(fù)雜度是 O(n)，如果實(shí)例中有千萬(wàn)級(jí)以上的 key，這個(gè)指令就會(huì)導(dǎo)致 Redis 服務(wù)卡頓，所有讀寫(xiě) Redis 的其它的指令都會(huì)被延后甚至?xí)瑫r(shí)報(bào)錯(cuò)，可能會(huì)引起緩存雪崩甚至數(shù)據(jù)庫(kù)宕機(jī)。
我們可以通過(guò)配置設(shè)置禁用這些命令，在 redis.conf 中，在 SECURITY 這一項(xiàng)中，我們新增以下命令：
rename-command flushall ""
rename-command flushdb ""
rename-command config ""
rename-command keys ""
另外，對(duì)于FLUSHALL命令，需要設(shè)置配置文件中appendonly no，否則服務(wù)器是無(wú)法啟動(dòng)。
Redis 為了解決這個(gè)問(wèn)題，它在 2.8 版本中加入了scan。scan 相比 keys 具備有以下特點(diǎn)：
- 復(fù)雜度雖然也是 O(n)，但是它是通過(guò)游標(biāo)分步進(jìn)行的，不會(huì)阻塞線程;
- 提供 limit 參數(shù)，可以控制每次返回結(jié)果的最大條數(shù)，limit 只是一個(gè) hint，返回的結(jié)果可多可少;
- 同 keys 一樣，它也提供模式匹配功能;
- 服務(wù)器不需要為游標(biāo)保存狀態(tài)，游標(biāo)的唯一狀態(tài)就是 scan 返回給客戶端的游標(biāo)整數(shù);
- 返回的結(jié)果可能會(huì)有重復(fù)，需要客戶端去重復(fù)，這點(diǎn)非常重要;
- 遍歷的過(guò)程中如果有數(shù)據(jù)修改，改動(dòng)后的數(shù)據(jù)能不能遍歷到是不確定的;
- 單次返回的結(jié)果是空的并不意味著遍歷結(jié)束，而要看返回的游標(biāo)值是否為零;
2. scan 使用
SCAN 命令及其相關(guān)的 SSCAN 命令、 HSCAN 命令和 ZSCAN 命令都用于增量地迭代（incrementally iterate）一集元素（a collection of elements）：
- SCAN 命令用于迭代當(dāng)前數(shù)據(jù)庫(kù)中的數(shù)據(jù)庫(kù)鍵。
- SSCAN 命令用于迭代集合鍵中的元素。
- HSCAN 命令用于迭代哈希鍵中的鍵值對(duì)。
- ZSCAN 命令用于迭代有序集合中的元素（包括元素成員和元素分值）
scan 參數(shù)提供了三個(gè)參數(shù)，第一個(gè)是 cursor 整數(shù)值，第二個(gè)是 key 的正則模式，第三個(gè)是遍歷的 limit hint。第一次遍歷時(shí)，cursor 值為 0，然后將返回結(jié)果中第一個(gè)整數(shù)值作為下一次遍歷的 cursor。一直遍歷到返回的 cursor 值為 0 時(shí)結(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"
127.0.0.1:6379> scan 13976 match key99* count 1000
1) "1996"
2) 1) "key9982"
2) "key9997"
3) "key9963"
4) "key996"
5) "key9912"
127.0.0.1:6379> scan 1996 match key99* count 1000
1) "12594"
2) 1) "key9939"
2) "key9941"
3) "key9967"
從上面的過(guò)程可以看到雖然提供的 limit 是 1000，但是返回的結(jié)果只有 10 個(gè)左右。因?yàn)檫@個(gè) limit 不是限定返回結(jié)果的數(shù)量，而是限定服務(wù)器單次遍歷的字典槽位數(shù)量(約等于)。
Jedis scan方法的封裝
public static Set getKeysByPattern(String pattern) {
Jedis jedis = init();
Set<String> retSet = new HashSet<>();
int scanCount = 20;
String scanRet = "0";
try {
do {
ScanParams scanParams = new ScanParams();
scanParams.match(pattern + "*");
scanParams.count(scanCount);
ScanResult<String> scanResult = jedis.scan(scanRet, scanParams);
scanRet = scanResult.getStringCursor();
retSet.addAll(scanResult.getResult());
} while (!scanRet.equals("0"));
} catch (Exception e) {
e.printStackTrace();
} finally {
if (null != jedis) {
relase(jedis);
}
}
return retSet;
}
4. 相關(guān)原理
注：以下內(nèi)容摘自作者老錢的大海撈針 —— Scan
字典的結(jié)構(gòu)
在 Redis 中所有的 key 都存儲(chǔ)在一個(gè)很大的字典中，這個(gè)字典的結(jié)構(gòu)和 Java 中的 HashMap 一樣，是一維數(shù)組 + 二維鏈表結(jié)構(gòu)，第一維數(shù)組的大小總是 2^n(n>=0)，擴(kuò)容一次數(shù)組大小空間加倍，也就是 n++。
scan 指令返回的游標(biāo)就是第一維數(shù)組的位置索引，我們將這個(gè)位置索引稱為槽 (slot)。如果不考慮字典的擴(kuò)容縮容，直接按數(shù)組下標(biāo)挨個(gè)遍歷就行了。limit 參數(shù)就表示需要遍歷的槽位數(shù)，之所以返回的結(jié)果可能多可能少，是因?yàn)椴皇撬械牟畚簧隙紩?huì)掛接鏈表，有些槽位可能是空的，還有些槽位上掛接的鏈表上的元素可能會(huì)有多個(gè)。每一次遍歷都會(huì)將 limit 數(shù)量的槽位上掛接的所有鏈表元素進(jìn)行模式匹配過(guò)濾后，一次性返回給客戶端。
scan 遍歷順序
scan 的遍歷順序非常特別。它不是從第一維數(shù)組的第 0 位一直遍歷到末尾，而是采用了高位進(jìn)位加法來(lái)遍歷。之所以使用這樣特殊的方式進(jìn)行遍歷，是考慮到字典的擴(kuò)容和縮容時(shí)避免槽位的遍歷重復(fù)和遺漏。
高位進(jìn)位法從左邊加，進(jìn)位往右邊移動(dòng)，同普通加法正好相反。但是最終它們都會(huì)遍歷所有的槽位并且沒(méi)有重復(fù)。
字典擴(kuò)容
Java 中的 HashMap 有擴(kuò)容的概念，當(dāng) loadFactor 達(dá)到閾值時(shí)，需要重新分配一個(gè)新的 2 倍大小的數(shù)組，然后將所有的元素全部 rehash 掛到新的數(shù)組下面。rehash 就是將元素的 hash 值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算，因?yàn)殚L(zhǎng)度變了，所以每個(gè)元素掛接的槽位可能也發(fā)生了變化。又因?yàn)閿?shù)組的長(zhǎng)度是 2^n 次方，所以取模運(yùn)算等價(jià)于位與操作。
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。
接下來(lái)我們看看 rehash 前后元素槽位的變化。
假設(shè)當(dāng)前的字典的數(shù)組長(zhǎng)度由 8 位擴(kuò)容到 16 位，那么 3 號(hào)槽位 011 將會(huì)被 rehash 到 3 號(hào)槽位和 11 號(hào)槽位，也就是說(shuō)該槽位鏈表中大約有一半的元素還是 3 號(hào)槽位，其它的元素會(huì)放到 11 號(hào)槽位，11 這個(gè)數(shù)字的二進(jìn)制是 1011，就是對(duì) 3 的二進(jìn)制 011 增加了一個(gè)高位 1。
抽象一點(diǎn)說(shuō)，假設(shè)開(kāi)始槽位的二進(jìn)制數(shù)是 xxx，那么該槽位中的元素將被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典長(zhǎng)度由 16 位擴(kuò)容到 32 位，那么對(duì)于二進(jìn)制槽位 xxxx 中的元素將被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。
對(duì)比擴(kuò)容縮容前后的遍歷順序
觀察這張圖，我們發(fā)現(xiàn)采用高位進(jìn)位加法的遍歷順序，rehash 后的槽位在遍歷順序上是相鄰的。
假設(shè)當(dāng)前要即將遍歷 110 這個(gè)位置 (橙色)，那么擴(kuò)容后，當(dāng)前槽位上所有的元素對(duì)應(yīng)的新槽位是 0110 和 1110(深綠色)，也就是在槽位的二進(jìn)制數(shù)增加一個(gè)高位 0 或 1。這時(shí)我們可以直接從 0110 這個(gè)槽位開(kāi)始往后繼續(xù)遍歷，0110 槽位之前的所有槽位都是已經(jīng)遍歷過(guò)的，這樣就可以避免擴(kuò)容后對(duì)已經(jīng)遍歷過(guò)的槽位進(jìn)行重復(fù)遍歷。
再考慮縮容，假設(shè)當(dāng)前即將遍歷 110 這個(gè)位置 (橙色)，那么縮容后，當(dāng)前槽位所有的元素對(duì)應(yīng)的新槽位是 10(深綠色)，也就是去掉槽位二進(jìn)制最高位。這時(shí)我們可以直接從 10 這個(gè)槽位繼續(xù)往后遍歷，10 槽位之前的所有槽位都是已經(jīng)遍歷過(guò)的，這樣就可以避免縮容的重復(fù)遍歷。不過(guò)縮容還是不太一樣，它會(huì)對(duì)圖中 010 這個(gè)槽位上的元素進(jìn)行重復(fù)遍歷，因?yàn)榭s融后 10 槽位的元素是 010 和 110 上掛接的元素的融合。
漸進(jìn)式 rehash
Java 的 HashMap 在擴(kuò)容時(shí)會(huì)一次性將舊數(shù)組下掛接的元素全部轉(zhuǎn)移到新數(shù)組下面。如果 HashMap 中元素特別多，線程就會(huì)出現(xiàn)卡頓現(xiàn)象。Redis 為了解決這個(gè)問(wèn)題，它采用漸進(jìn)式 rehash。
它會(huì)同時(shí)保留舊數(shù)組和新數(shù)組，然后在定時(shí)任務(wù)中以及后續(xù)對(duì) hash 的指令操作中漸漸地將舊數(shù)組中掛接的元素遷移到新數(shù)組上。這意味著要操作處于 rehash 中的字典，需要同時(shí)訪問(wèn)新舊兩個(gè)數(shù)組結(jié)構(gòu)。如果在舊數(shù)組下面找不到元素，還需要去新數(shù)組下面去尋找。
scan 也需要考慮這個(gè)問(wèn)題，對(duì)與 rehash 中的字典，它需要同時(shí)掃描新舊槽位，然后將結(jié)果融合后返回給客戶端。
