SCAN命令可以為用戶保證：從完整遍歷開始直到完整遍歷結(jié)束期間，一直存在于數(shù)據(jù)集內(nèi)的所有元素都會(huì)被完整遍歷返回，但是同一個(gè)元素可能會(huì)被返回多次。如果一個(gè)元素是在迭代過程中被添加到數(shù)據(jù)集的，又或者是在迭代過程中從數(shù)據(jù)集中被刪除的，那么這個(gè)元素可能會(huì)被返回，也可能不會(huì)返回。
這是如何實(shí)現(xiàn)的呢，先從Redis中的字典dict開始。Redis的數(shù)據(jù)庫(kù)是使用dict作為底層實(shí)現(xiàn)的。
字典數(shù)據(jù)類型
Redis中的字典由dict.h/dict結(jié)構(gòu)表示：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
字典由兩個(gè)哈希表dictht構(gòu)成，主要用做rehash，平常主要使用ht[0]哈希表。
哈希表由一個(gè)成員為dictEntry的數(shù)組構(gòu)成，size屬性記錄了數(shù)組的大小，used屬性記錄了已有節(jié)點(diǎn)的數(shù)量，sizemask屬性的值等于size - 1。數(shù)組大小一般是2n，所以sizemask二進(jìn)制是0b11111...，主要用作掩碼，和哈希值一起決定key應(yīng)該放在數(shù)組的哪個(gè)位置。
求key在數(shù)組中的索引的計(jì)算方法如下：
index = hash d->ht[table].sizemask;
也就是根據(jù)掩碼求低位值。
rehash的問題
字典rehash時(shí)會(huì)使用兩個(gè)哈希表，首先為ht[1]分配空間，如果是擴(kuò)展操作，ht[1]的大小為第一個(gè)大于等于2倍ht[0].used的2n，如果是收縮操作，ht[1]的大小為第一個(gè)大于等于ht[0].used的2n。然后將ht[0]的所有鍵值對(duì)rehash到ht[1]中，最后釋放ht[0]，將ht[1]設(shè)置為ht[0]，新創(chuàng)建一個(gè)空白哈希表當(dāng)做ht[1]。rehash不是一次完成的，而是分多次、漸進(jìn)式地完成。
舉個(gè)例子，現(xiàn)在將一個(gè)size為4的哈希表ht[0](sizemask為11, index = hash 0b11)rehash至一個(gè)size為8的哈希表ht[1](sizemask為111, index = hash 0b111)。
ht[0]中處于bucket0位置的key的哈希值低兩位為00，那么rehash至ht[1]時(shí)index取低三位可能為000(0)和100(4)。也就是ht[0]中bucket0中的元素rehash之后分散于ht[1]的bucket0與bucket4，以此類推，對(duì)應(yīng)關(guān)系為：
ht[0] -> ht[1]
----------------
0 -> 0,4
1 -> 1,5
2 -> 2,6
3 -> 3,7
如果SCAN命令采取0->1->2->3的順序進(jìn)行遍歷，就會(huì)出現(xiàn)如下問題：
•擴(kuò)展操作中，如果返回游標(biāo)1時(shí)正在進(jìn)行rehash，ht[0]中的bucket0中的部分?jǐn)?shù)據(jù)可能已經(jīng)rehash到ht[1]中的bucket[0]或者bucket[4]，在ht[1]中從bucket1開始遍歷，遍歷至bucket4時(shí)，其中的元素已經(jīng)在ht[0]中的bucket0中遍歷過，這就產(chǎn)生了重復(fù)問題。
•縮小操作中，當(dāng)返回游標(biāo)5，但縮小后哈希表的size只有4，如何重置游標(biāo)？
SCAN的遍歷順序
SCAN命令的遍歷順序，可以舉一個(gè)例子看一下：
127.0.0.1:6379[3]> keys *
1) "bar"
2) "qux"
3) "baz"
4) "foo"
127.0.0.1:6379[3]> scan 0 count 1
1) "2"
2) 1) "bar"
127.0.0.1:6379[3]> scan 2 count 1
1) "1"
2) 1) "foo"
127.0.0.1:6379[3]> scan 1 count 1
1) "3"
2) 1) "qux"
2) "baz"
127.0.0.1:6379[3]> scan 3 count 1
1) "0"
2) (empty list or set)
可以看出順序是0->2->1->3，很難看出規(guī)律，轉(zhuǎn)換成二進(jìn)制觀察一下：
00 -> 10 -> 01 -> 11
二進(jìn)制就很明了了，遍歷采用的順序也是加法，但每次是高位加1的，也就是從左往右相加、從高到低進(jìn)位的。
SCAN源碼
SCAN遍歷字典的源碼在dict.c/dictScan，分兩種情況，字典不在進(jìn)行rehash或者正在進(jìn)行rehash。
不在進(jìn)行rehash時(shí)，游標(biāo)是這樣計(jì)算的：
m0 = t0->sizemask;
// 將游標(biāo)的umask位的bit都置為1
v |= ~m0;
// 反轉(zhuǎn)游標(biāo)
v = rev(v);
// 反轉(zhuǎn)后+1，達(dá)到高位加1的效果
v++;
// 再次反轉(zhuǎn)復(fù)位
v = rev(v);
當(dāng)size為4時(shí)，sizemask為3(00000011)，游標(biāo)計(jì)算過程：
v |= ~m0 v = rev(v) v++ v = rev(v)
00000000(0) -> 11111100 -> 00111111 -> 01000000 -> 00000010(2)
00000010(2) -> 11111110 -> 01111111 -> 10000000 -> 00000001(1)
00000001(1) -> 11111101 -> 10111111 -> 11000000 -> 00000011(3)
00000011(3) -> 11111111 -> 11111111 -> 00000000 -> 00000000(0)
遍歷size為4時(shí)的游標(biāo)狀態(tài)轉(zhuǎn)移為0->2->1->3。
同理,size為8時(shí)的游標(biāo)狀態(tài)轉(zhuǎn)移為0->4->2->6->1->5->3->7，也就是000->100->010->110->001->101->011->111。
再結(jié)合前面的rehash：
ht[0] -> ht[1]
----------------
0 -> 0,4
1 -> 1,5
2 -> 2,6
3 -> 3,7
可以看出，當(dāng)size由小變大時(shí)，所有原來的游標(biāo)都能在大的哈希表中找到相應(yīng)的位置，并且順序一致，不會(huì)重復(fù)讀取并且不會(huì)遺漏。
當(dāng)size由大變小的情況，假設(shè)size由8變?yōu)榱?，分兩種情況，一種是游標(biāo)為0,2,1,3中的一種，此時(shí)繼續(xù)讀取，也不會(huì)遺漏和重復(fù)。
但如果游標(biāo)返回的不是這四種，例如返回了7，711之后變?yōu)榱?，所以會(huì)從size為4的哈希表的bucket3開始繼續(xù)遍歷，而bucket3包含了size為8的哈希表中的bucket3與bucket7，所以會(huì)造成重復(fù)讀取size為8的哈希表中的bucket3的情況。
所以，redis里rehash從小到大時(shí)，SCAN命令不會(huì)重復(fù)也不會(huì)遺漏。而從大到小時(shí)，有可能會(huì)造成重復(fù)但不會(huì)遺漏。
當(dāng)正在進(jìn)行rehash時(shí)，游標(biāo)計(jì)算過程：
/* Make sure t0 is the smaller and t1 is the bigger table */
if (t0->size > t1->size) {
t0 = d->ht[1];
t1 = d->ht[0];
}
m0 = t0->sizemask;
m1 = t1->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, t0->table[v m0]);
de = t0->table[v m0];
while (de) {
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 {
/* 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;
}
/* Increment the reverse cursor not covered by the smaller mask.*/
v |= ~m1;
v = rev(v);
v++;
v = rev(v);
/* Continue while bits covered by mask difference is non-zero */
} while (v (m0 ^ m1));
算法會(huì)保證t0是較小的哈希表，不是的話t0與t1互換，先遍歷t0中游標(biāo)所在的bucket，然后再遍歷較大的t1。
求下一個(gè)游標(biāo)的過程基本相同，只是把m0換成了rehash之后的哈希表的m1，同時(shí)還加了一個(gè)判斷條件:
v (m0 ^ m1)
size4的m0為00000011，size8的m1為00000111，m0 ^ m1取值為00000100，即取二者mask的不同位，看游標(biāo)在這些標(biāo)志位是否為1。
假設(shè)游標(biāo)返回了2，并且正在進(jìn)行rehash，此時(shí)size由4變成了8，二者mask的不同位是低第三位。
首先遍歷t0中的bucket2，然后遍歷t1中的bucket2，公式計(jì)算出的下一個(gè)游標(biāo)為6(00000110)，低第三位為1，繼續(xù)循環(huán)，遍歷t1中的bucket6，然后計(jì)算游標(biāo)為1，結(jié)束循環(huán)。
所以正在rehash時(shí)，是兩個(gè)哈希表都遍歷的，以避免遺漏的情況。
總結(jié)
以上所述是小編給大家介紹的Redis SCAN命令實(shí)現(xiàn)有限保證的原理,希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！
您可能感興趣的文章:- Redis中scan命令的深入講解
- php redis擴(kuò)展支持scan命令實(shí)現(xiàn)方法
- Redis中Scan命令的基本使用教程
- Redis Scan命令的基本使用方法
- Redis中Scan命令的踩坑實(shí)錄
- redis中scan命令的基本實(shí)現(xiàn)方法
