在 redis 實際使用中，會遇到一個問題：如何從海量的 key 中找出滿足特定前綴的 key 列表來男娄？
1. 不要使用 keys*
redis 提供了一個簡單暴力的指令 keys 用來列出所有滿足特定正則字符串規(guī)則的 key丁恭。
keys xxx*
這個指令有致命的弊端幽纷，在實際環(huán)境中最好不要使用：
這個指令沒有 offset涂屁、limit 參數(shù)甸怕，是要一次性吐出所有滿足條件的 key甘穿，由于 redis 是單線程的，其所有操作都是原子的蕾各，而 keys 算法是遍歷算法扒磁，復(fù)雜度是 O(n)，如果實例中有千萬級以上的 key式曲，這個指令就會導(dǎo)致 Redis 服務(wù)卡頓妨托，所有讀寫 Redis 的其它的指令都會被延后甚至?xí)瑫r報錯，可能會引起緩存雪崩甚至數(shù)據(jù)庫宕機吝羞。
我們可以通過配置設(shè)置禁用這些命令兰伤，在 redis.conf 中，在 SECURITY 這一項中钧排，我們新增以下命令：
rename-command flushall ""
rename-command flushdb ""
rename-command config ""
rename-command keys ""
另外敦腔，對于FLUSHALL命令，需要設(shè)置配置文件中appendonly no恨溜，否則服務(wù)器是無法啟動符衔。
Redis 為了解決這個問題找前，它在 2.8 版本中加入了scan。scan 相比 keys 具備有以下特點：
- 復(fù)雜度雖然也是 O(n)判族，但是它是通過游標(biāo)分步進行的躺盛，不會阻塞線程;
- 提供 limit 參數(shù)，可以控制每次返回結(jié)果的最大條數(shù)形帮，limit 只是一個 hint槽惫，返回的結(jié)果可多可少;
- 同 keys 一樣，它也提供模式匹配功能;
- 服務(wù)器不需要為游標(biāo)保存狀態(tài)辩撑，游標(biāo)的唯一狀態(tài)就是 scan 返回給客戶端的游標(biāo)整數(shù);
- 返回的結(jié)果可能會有重復(fù)界斜，需要客戶端去重復(fù)，這點非常重要;
- 遍歷的過程中如果有數(shù)據(jù)修改合冀，改動后的數(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ù)庫中的數(shù)據(jù)庫鍵水慨。
- SSCAN 命令用于迭代集合鍵中的元素得糜。
- HSCAN 命令用于迭代哈希鍵中的鍵值對。
- ZSCAN 命令用于迭代有序集合中的元素（包括元素成員和元素分值）
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"
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"
從上面的過程可以看到雖然提供的 limit 是 1000，但是返回的結(jié)果只有 10 個左右贝润。因為這個 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 都存儲在一個很大的字典中打掘，這個字典的結(jié)構(gòu)和 Java 中的 HashMap 一樣华畏，是一維數(shù)組 + 二維鏈表結(jié)構(gòu)，第一維數(shù)組的大小總是 2^n(n>=0)尊蚁，擴容一次數(shù)組大小空間加倍亡笑，也就是 n++。
scan 指令返回的游標(biāo)就是第一維數(shù)組的位置索引横朋，我們將這個位置索引稱為槽 (slot)仑乌。如果不考慮字典的擴容縮容，直接按數(shù)組下標(biāo)挨個遍歷就行了。limit 參數(shù)就表示需要遍歷的槽位數(shù)晰甚，之所以返回的結(jié)果可能多可能少衙传，是因為不是所有的槽位上都會掛接鏈表，有些槽位可能是空的压汪，還有些槽位上掛接的鏈表上的元素可能會有多個粪牲。每一次遍歷都會將 limit 數(shù)量的槽位上掛接的所有鏈表元素進行模式匹配過濾后，一次性返回給客戶端止剖。
scan 遍歷順序
scan 的遍歷順序非常特別。它不是從第一維數(shù)組的第 0 位一直遍歷到末尾落君，而是采用了高位進位加法來遍歷穿香。之所以使用這樣特殊的方式進行遍歷，是考慮到字典的擴容和縮容時避免槽位的遍歷重復(fù)和遺漏绎速。
高位進位法從左邊加皮获，進位往右邊移動，同普通加法正好相反纹冤。但是最終它們都會遍歷所有的槽位并且沒有重復(fù)洒宝。
字典擴容
Java 中的 HashMap 有擴容的概念，當(dāng) loadFactor 達到閾值時萌京，需要重新分配一個新的 2 倍大小的數(shù)組雁歌，然后將所有的元素全部 rehash 掛到新的數(shù)組下面。rehash 就是將元素的 hash 值對數(shù)組長度進行取模運算知残，因為長度變了靠瞎，所以每個元素掛接的槽位可能也發(fā)生了變化。又因為數(shù)組的長度是 2^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 位擴容到 16 位净神，那么 3 號槽位 011 將會被 rehash 到 3 號槽位和 11 號槽位何吝，也就是說該槽位鏈表中大約有一半的元素還是 3 號槽位，其它的元素會放到 11 號槽位强挫，11 這個數(shù)字的二進制是 1011岔霸，就是對 3 的二進制 011 增加了一個高位 1。
抽象一點說俯渤，假設(shè)開始槽位的二進制數(shù)是 xxx呆细，那么該槽位中的元素將被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典長度由 16 位擴容到 32 位，那么對于二進制槽位 xxxx 中的元素將被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中絮爷。
對比擴容縮容前后的遍歷順序
觀察這張圖趴酣，我們發(fā)現(xiàn)采用高位進位加法的遍歷順序，rehash 后的槽位在遍歷順序上是相鄰的坑夯。
假設(shè)當(dāng)前要即將遍歷 110 這個位置 (橙色)岖寞，那么擴容后，當(dāng)前槽位上所有的元素對應(yīng)的新槽位是 0110 和 1110(深綠色)柜蜈，也就是在槽位的二進制數(shù)增加一個高位 0 或 1仗谆。這時我們可以直接從 0110 這個槽位開始往后繼續(xù)遍歷，0110 槽位之前的所有槽位都是已經(jīng)遍歷過的淑履，這樣就可以避免擴容后對已經(jīng)遍歷過的槽位進行重復(fù)遍歷隶垮。
再考慮縮容，假設(shè)當(dāng)前即將遍歷 110 這個位置 (橙色)秘噪，那么縮容后狸吞，當(dāng)前槽位所有的元素對應(yīng)的新槽位是 10(深綠色)，也就是去掉槽位二進制最高位指煎。這時我們可以直接從 10 這個槽位繼續(xù)往后遍歷蹋偏，10 槽位之前的所有槽位都是已經(jīng)遍歷過的，這樣就可以避免縮容的重復(fù)遍歷至壤。不過縮容還是不太一樣威始，它會對圖中 010 這個槽位上的元素進行重復(fù)遍歷，因為縮融后 10 槽位的元素是 010 和 110 上掛接的元素的融合崇渗。
漸進式 rehash
Java 的 HashMap 在擴容時會一次性將舊數(shù)組下掛接的元素全部轉(zhuǎn)移到新數(shù)組下面字逗。如果 HashMap 中元素特別多，線程就會出現(xiàn)卡頓現(xiàn)象宅广。Redis 為了解決這個問題葫掉，它采用漸進式 rehash。
它會同時保留舊數(shù)組和新數(shù)組跟狱，然后在定時任務(wù)中以及后續(xù)對 hash 的指令操作中漸漸地將舊數(shù)組中掛接的元素遷移到新數(shù)組上俭厚。這意味著要操作處于 rehash 中的字典，需要同時訪問新舊兩個數(shù)組結(jié)構(gòu)驶臊。如果在舊數(shù)組下面找不到元素挪挤，還需要去新數(shù)組下面去尋找。
scan 也需要考慮這個問題关翎，對與 rehash 中的字典扛门，它需要同時掃描新舊槽位，然后將結(jié)果融合后返回給客戶端纵寝。
