前言

熟悉Redis的人都知道，它是單線程的。因此在使用一些時(shí)間復(fù)雜度為O(N)的命令時(shí)要非常謹(jǐn)慎。可能一不小心就會(huì)阻塞進(jìn)程，導(dǎo)致Redis出現(xiàn)卡頓。

有時(shí)，我們需要針對(duì)符合條件的一部分命令進(jìn)行操作，比如刪除以test_開頭的key。那么怎么獲取到這些key呢？在Redis2.8版本之前，我們可以使用keys命令按照正則匹配得到我們需要的key。但是這個(gè)命令有兩個(gè)缺點(diǎn)：

• 沒(méi)有l(wèi)imit，我們只能一次性獲取所有符合條件的key，如果結(jié)果有上百萬(wàn)條，那么等待你的就是“無(wú)窮無(wú)盡”的字符串輸出。
• keys命令是遍歷算法，時(shí)間復(fù)雜度是O(N)。如我們剛才所說(shuō)，這個(gè)命令非常容易導(dǎo)致Redis服務(wù)卡頓。因此，我們要盡量避免在生產(chǎn)環(huán)境使用該命令。

在滿足需求和存在造成Redis卡頓之間究竟要如何選擇呢？面對(duì)這個(gè)兩難的抉擇，Redis在2.8版本給我們提供了解決辦法——scan命令。

相比于keys命令，scan命令有兩個(gè)比較明顯的優(yōu)勢(shì)：

• scan命令的時(shí)間復(fù)雜度雖然也是O(N)，但它是分次進(jìn)行的，不會(huì)阻塞線程。
• scan命令提供了limit參數(shù)，可以控制每次返回結(jié)果的最大條數(shù)。

這兩個(gè)優(yōu)勢(shì)就幫助我們解決了上面的難題，不過(guò)scan命令也并不是完美的，它返回的結(jié)果有可能重復(fù)，因此需要客戶端去重。至于為什么會(huì)重復(fù)，相信你看完本文之后就會(huì)有答案了。

關(guān)于scan命令的基本用法，可以參看Redis命令詳解：Keys一文中關(guān)于SCAN命令的介紹。

SCAN 命令

SCAN命令的有SCAN,SSCAN,HSCAN,ZSCAN。

SCAN的話就是遍歷所有的keys

其他的SCAN命令的話是SCAN選中的集合。

SCAN命令是增量的循環(huán)，每次調(diào)用只會(huì)返回一小部分的元素。所以不會(huì)有KEYS命令的坑。

SCAN命令返回的是一個(gè)游標(biāo)，從0開始遍歷，到0結(jié)束遍歷。

今天我們主要從底層的結(jié)構(gòu)和源碼的角度來(lái)討論scan是如何工作的。

Redis的結(jié)構(gòu)

Redis使用了Hash表作為底層實(shí)現(xiàn)，原因不外乎高效且實(shí)現(xiàn)簡(jiǎn)單。說(shuō)到Hash表，很多Java程序員第一反應(yīng)就是HashMap。沒(méi)錯(cuò)，Redis底層key的存儲(chǔ)結(jié)構(gòu)就是類似于HashMap那樣數(shù)組+鏈表的結(jié)構(gòu)。其中第一維的數(shù)組大小為2n(n>=0)。每次擴(kuò)容數(shù)組長(zhǎng)度擴(kuò)大一倍。

scan命令就是對(duì)這個(gè)一維數(shù)組進(jìn)行遍歷。每次返回的游標(biāo)值也都是這個(gè)數(shù)組的索引。limit參數(shù)表示遍歷多少個(gè)數(shù)組的元素，將這些元素下掛接的符合條件的結(jié)果都返回。因?yàn)槊總€(gè)元素下掛接的鏈表大小不同，所以每次返回的結(jié)果數(shù)量也就不同。

SCAN的遍歷順序

關(guān)于scan命令的遍歷順序，我們可以用一個(gè)小栗子來(lái)具體看一下。

127.0.0.1:6379> keys *
1) "db_number"
2) "key1"
3) "myKey"
127.0.0.1:6379> scan 0 MATCH * COUNT 1
1) "2"
2) 1) "db_number"
127.0.0.1:6379> scan 2 MATCH * COUNT 1
1) "1"
2) 1) "myKey"
127.0.0.1:6379> scan 1 MATCH * COUNT 1
1) "3"
2) 1) "key1"
127.0.0.1:6379> scan 3 MATCH * COUNT 1
1) "0"
2) (empty list or set)

我們的Redis中有3個(gè)key，我們每次只遍歷一個(gè)一維數(shù)組中的元素。如上所示，SCAN命令的遍歷順序是

0->2->1->3

這個(gè)順序看起來(lái)有些奇怪。我們把它轉(zhuǎn)換成二進(jìn)制就好理解一些了。

00->10->01->11

我們發(fā)現(xiàn)每次這個(gè)序列是高位加1的。普通二進(jìn)制的加法，是從右往左相加、進(jìn)位。而這個(gè)序列是從左往右相加、進(jìn)位的。這一點(diǎn)我們?cè)趓edis的源碼中也得到印證。

在dict.c文件的dictScan函數(shù)中對(duì)游標(biāo)進(jìn)行了如下處理

v = rev(v);
v++;
v = rev(v);

意思是，將游標(biāo)倒置，加一后，再倒置，也就是我們所說(shuō)的“高位加1”的操作。

這里大家可能會(huì)有疑問(wèn)了，為什么要使用這樣的順序進(jìn)行遍歷，而不是用正常的0、1、2……這樣的順序呢，這是因?yàn)樾枰紤]遍歷時(shí)發(fā)生字典擴(kuò)容與縮容的情況（不得不佩服開發(fā)者考慮問(wèn)題的全面性）。

我們來(lái)看一下在SCAN遍歷過(guò)程中，發(fā)生擴(kuò)容時(shí)，遍歷會(huì)如何進(jìn)行。加入我們?cè)嫉臄?shù)組有4個(gè)元素，也就是索引有兩位，這時(shí)需要把它擴(kuò)充成3位，并進(jìn)行rehash。

原來(lái)掛接在xx下的所有元素被分配到0xx和1xx下。在上圖中，當(dāng)我們即將遍歷10時(shí)，dict進(jìn)行了rehash，這時(shí)，scan命令會(huì)從010開始遍歷，而000和100（原00下掛接的元素）不會(huì)再被重復(fù)遍歷。

再來(lái)看看縮容的情況。假設(shè)dict從3位縮容到2位，當(dāng)即將遍歷110時(shí)，dict發(fā)生了縮容，這時(shí)scan會(huì)遍歷10。這時(shí)010下掛接的元素會(huì)被重復(fù)遍歷，但010之前的元素都不會(huì)被重復(fù)遍歷了。所以，縮容時(shí)還是可能會(huì)有些重復(fù)元素出現(xiàn)的。

Redis的rehash

rehash是一個(gè)比較復(fù)雜的過(guò)程，為了不阻塞Redis的進(jìn)程，它采用了一種漸進(jìn)式的rehash的機(jī)制。

/* 字典 */
typedef struct dict {
 // 類型特定函數(shù)
 dictType *type;
 // 私有數(shù)據(jù)
 void *privdata;
 // 哈希表
 dictht ht[2];
 // rehash 索引
 // 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
 int rehashidx; /* rehashing not in progress if rehashidx == -1 */
 // 目前正在運(yùn)行的安全迭代器的數(shù)量
 int iterators; /* number of iterators currently running */
} dict;

在Redis的字典結(jié)構(gòu)中，有兩個(gè)hash表，一個(gè)新表，一個(gè)舊表。在rehash的過(guò)程中，redis將舊表中的元素逐步遷移到新表中，接下來(lái)我們看一下dict的rehash操作的源碼。

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
 int empty_visits = n*10; /* Max number of empty buckets to visit. */
 if (!dictIsRehashing(d)) return 0;

 while(n--  d->ht[0].used != 0) {
 dictEntry *de, *nextde;

 /* Note that rehashidx can't overflow as we are sure there are more
  * elements because ht[0].used != 0 */
 assert(d->ht[0].size > (unsigned long)d->rehashidx);
 while(d->ht[0].table[d->rehashidx] == NULL) {
  d->rehashidx++;
  if (--empty_visits == 0) return 1;
 }
 de = d->ht[0].table[d->rehashidx];
 /* Move all the keys in this bucket from the old to the new hash HT */
 while(de) {
  uint64_t h;

  nextde = de->next;
  /* Get the index in the new hash table */
  h = dictHashKey(d, de->key)  d->ht[1].sizemask;
  de->next = d->ht[1].table[h];
  d->ht[1].table[h] = de;
  d->ht[0].used--;
  d->ht[1].used++;
  de = nextde;
 }
 d->ht[0].table[d->rehashidx] = NULL;
 d->rehashidx++;
 }

 /* Check if we already rehashed the whole table... */
 if (d->ht[0].used == 0) {
 zfree(d->ht[0].table);
 d->ht[0] = d->ht[1];
 _dictReset(d->ht[1]);
 d->rehashidx = -1;
 return 0;
 }

 /* More to rehash... */
 return 1;
}

通過(guò)注釋我們就能了解到，rehash的過(guò)程是以bucket為基本單位進(jìn)行遷移的。所謂的bucket其實(shí)就是我們前面所提到的一維數(shù)組的元素。每次遷移一個(gè)列表。下面來(lái)解釋一下這段代碼。

• 首先判斷一下是否在進(jìn)行rehash，如果是，則繼續(xù)進(jìn)行；否則直接返回。
• 接著就是分n步開始進(jìn)行漸進(jìn)式rehash。同時(shí)還判斷是否還有剩余元素，以保證安全性。
• 在進(jìn)行rehash之前，首先判斷要遷移的bucket是否越界。
• 然后跳過(guò)空的bucket，這里有一個(gè)empty_visits變量，表示最大可訪問(wèn)的空bucket的數(shù)量，這一變量主要是為了保證不過(guò)多的阻塞Redis。
• 接下來(lái)就是元素的遷移，將當(dāng)前bucket的全部元素進(jìn)行rehash，并且更新兩張表中元素的數(shù)量。
• 每次遷移完一個(gè)bucket，需要將舊表中的bucket指向NULL。
• 最后判斷一下是否全部遷移完成，如果是，則收回空間，重置rehash索引，否則告訴調(diào)用方，仍有數(shù)據(jù)未遷移。

由于Redis使用的是漸進(jìn)式rehash機(jī)制，因此，scan命令在需要同時(shí)掃描新表和舊表，將結(jié)果返回客戶端。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。