redis中scan命令的基本實(shí)現(xiàn)方法

前言

在一個(gè)天朗氣清的日子，小灰登上了線上的redis打算查詢數(shù)據(jù)。然而他只記得前綴而不知道整個(gè)鍵是多少，于是在命令行敲入了“keys xxx*”命令。

瞬間服務(wù)卡死，報(bào)警郵件堆滿了郵箱，而小灰，只能目瞪狗呆的等待著即將降臨的case study。

基本上，keys *命令都是在線上是被運(yùn)維禁止的。

redis的鍵在鍵值對(duì)大小大于hash-max-ziplist-value且個(gè)數(shù)小于hash-max-ziplist-entries的時(shí)候，是存放在散列表數(shù)據(jù)結(jié)構(gòu)中的，在運(yùn)行keys命令的時(shí)候，需要遍歷數(shù)據(jù)庫(kù)鍵空間，把所有鍵都取出來(lái)后與keys后面的pattern匹配。

在鍵很多的情況下，redis可能的卡頓會(huì)在秒級(jí)以上，導(dǎo)致所有流量都打到數(shù)據(jù)庫(kù)，使得數(shù)據(jù)庫(kù)雪崩。

那我們?cè)趺床拍軌蛟诓檎业侥繕?biāo)鍵呢？在redis2.8.0的時(shí)候加入了scan命令，可以分批次掃描redis鍵。雖然在應(yīng)用的時(shí)候會(huì)使得要查詢到全部符合要求的key的時(shí)間變長(zhǎng)，但是大大大大減少了redis卡頓的幾率

在這里先補(bǔ)充一下背景：

redis中的字典rehash是漸進(jìn)式哈希，即不是一次性把所有的鍵都遷移到新的哈希表，而是在下面兩種情況下遷移數(shù)據(jù)：
每次哈希表操作的時(shí)候，如果當(dāng)前正在rehash，則遷移一個(gè)節(jié)點(diǎn)；
服務(wù)空閑時(shí)，會(huì)rehash一百個(gè)節(jié)點(diǎn)。

scan命令可以保證在（沒有鍵修改的）字典正在rehash的過程中做到以下兩點(diǎn)：

• 不出現(xiàn)重復(fù)數(shù)據(jù)
• 不遺漏數(shù)據(jù)
  

那scan命令是怎么做到在rehash過程中都能不重復(fù)不遺漏地遍歷所有節(jié)點(diǎn)的呢？讓我們來(lái)一起走讀一下源碼。

Let's GO!

在使用scan命令的時(shí)候，我們每次傳入一個(gè)游標(biāo)（從0開始），然后下一輪繼續(xù)使用本輪redis返回的游標(biāo)。scan字典的核心函數(shù)是dictScan，而dictScan的更新游標(biāo)的核心代碼如下：

v |= ~m0;//或者m1
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);

其中m0、m1為當(dāng)前哈希表大小減一，rev是二進(jìn)制逆序。

看到這里，不知道在座的各位是不是也是跟我一樣是下面這個(gè)表情

讓我們來(lái)模擬一下問題，就清楚了。

我們假設(shè)現(xiàn)在在一個(gè)四個(gè)節(jié)點(diǎn)的哈希表中遍歷，如下圖，游標(biāo)的遍歷節(jié)點(diǎn)為：0 -> 2 -> 1 -> 3 ：

再來(lái)模擬8節(jié)點(diǎn)的情況：

看到這里是不是稍微明白了，上面那段代碼就是在當(dāng)前的有效位數(shù)（比如四節(jié)點(diǎn)則有效位數(shù)2）范圍內(nèi)，從左到右進(jìn)一位。

假設(shè)在遍歷了0，返回2之后，字典進(jìn)行了擴(kuò)容，則接下來(lái)應(yīng)該訪問 2 -> 6 -> 1 -> 5 -> 3 -> 7。

小灰：咦，那4不是遺漏了嗎？

4已經(jīng)在第一輪遍歷0的時(shí)候，把擴(kuò)容后的4的數(shù)據(jù)也訪問了。

所以，假設(shè)擴(kuò)容前有效位為m，因?yàn)閞edis的哈希表擴(kuò)容每次都是當(dāng)前節(jié)點(diǎn)滿了（ use==size）的時(shí)候擴(kuò)容為大于size的2^N，所以擴(kuò)容后有效位則為m+1。

上面那段代碼其實(shí)是保持低位的m位不變，高位一個(gè)為0一個(gè)為1。這樣就保證了擴(kuò)容后，跳過了的節(jié)點(diǎn)已經(jīng)在之前被訪問過，因?yàn)樘^的節(jié)點(diǎn)是被訪問過的節(jié)點(diǎn)分出來(lái)的。

縮容同理，可以自己推一下。

看到這里，是不是覺得redis的scan游標(biāo)設(shè)計(jì)的很巧妙呢？

小灰：原來(lái)如此，看來(lái)我又可以去查數(shù)據(jù)了呢！

最后附上完整的rehash過程中scan的代碼：

// 指向兩個(gè)哈希表
t0 = d->ht[0];
t1 = d->ht[1];

/* Make sure t0 is the smaller and t1 is the bigger table */
// 確保 t0 比 t1 要小
if (t0->size > t1->size) {
 t0 = d->ht[1];
 t1 = d->ht[0];
}

// 記錄掩碼
m0 = t0->sizemask;
m1 = t1->sizemask;

/* Emit entries at cursor */
// 指向桶，并迭代桶中的所有節(jié)點(diǎn)
de = t0->table[v  m0];
while (de) {//迭代第一張小hash表
 next = de->next;
 fn(privdata, de);
 de = next;
}

/* Iterate over indices in larger table that are the expansion
 * of the index pointed to by the cursor in the smaller table */
do {//迭代第二張大hash表
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, t1->table[v  m1]);
 de = t1->table[v  m1];
 while (de) {
  next = de->next;
  fn(privdata, de);
  de = next;
 }

 //計(jì)算一個(gè)哈希表節(jié)點(diǎn)索引的方法 是 hash(key)mask。哈希表容量為 8，則 mask 為 111，因此，節(jié)點(diǎn)的索引值就取決于哈希值的低 3 bit，
 // 設(shè)索引值是 abc。如果哈希表容量為 16，則 mask 為 1111，該節(jié)點(diǎn)的哈希值不變，而索引值是 ?abc，其中 ? 取 0 或 1 中的一個(gè)，
 // 也就是說(shuō)，該節(jié)點(diǎn)在容量為 16 的哈希表中，索引要么是 0abc 要么是 1abc。以此類推，如果哈希表容量為32，
 // 則該節(jié)點(diǎn)的索引可能是 00abc，01abc，10abc 或者 11abc 中的一個(gè)。/* Increment the reverse cursor not covered by the smaller mask.*/
 v |= ~m1;//用于保留 v 的低 n 位數(shù)，其余位全置為 1
 //下面這一段，最終得到的新 v，就是向最高位加 1，且向低位方向進(jìn)位
 v = rev(v);//將 v 的二進(jìn)制位進(jìn)行翻轉(zhuǎn)，所以，v的低 n 位數(shù)成了高 n 位數(shù)，并且進(jìn)行了翻轉(zhuǎn)
 v++;
 v = rev(v);//再次二進(jìn)制翻轉(zhuǎn)

 /* Continue while bits covered by mask difference is non-zero */
} while (v  (m0 ^ m1));//終止條件是 v的高位區(qū)別位沒有1了，其實(shí)就是說(shuō)到頭了。

總結(jié)

到此這篇關(guān)于redis中scan命令的基本實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)redis中scan命令實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！