SCAN命令可以為用戶保證：從完整遍歷開始直到完整遍歷結束期間，一直存在于數據集內的所有元素都會被完整遍歷返回，但是同一個元素可能會被返回多次。如果一個元素是在迭代過程中被添加到數據集的，又或者是在迭代過程中從數據集中被刪除的，那么這個元素可能會被返回，也可能不會返回。

這是如何實現的呢，先從Redis中的字典dict開始。Redis的數據庫是使用dict作為底層實現的。

字典數據類型

Redis中的字典由dict.h/dict結構表示：

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;

字典由兩個哈希表dictht構成，主要用做rehash，平常主要使用ht[0]哈希表。

哈希表由一個成員為dictEntry的數組構成，size屬性記錄了數組的大小，used屬性記錄了已有節點的數量，sizemask屬性的值等于size - 1。數組大小一般是2n，所以sizemask二進制是0b11111...，主要用作掩碼，和哈希值一起決定key應該放在數組的哪個位置。

求key在數組中的索引的計算方法如下：

index = hash & d->ht[table].sizemask;

也就是根據掩碼求低位值。

rehash的問題

字典rehash時會使用兩個哈希表，首先為ht[1]分配空間，如果是擴展操作，ht[1]的大小為第一個大于等于2倍ht[0].used的2n，如果是收縮操作，ht[1]的大小為第一個大于等于ht[0].used的2n。然后將ht[0]的所有鍵值對rehash到ht[1]中，最后釋放ht[0]，將ht[1]設置為ht[0]，新創建一個空白哈希表當做ht[1]。rehash不是一次完成的，而是分多次、漸進式地完成。

舉個例子，現在將一個size為4的哈希表ht[0](sizemask為11, index = hash & 0b11)rehash至一個size為8的哈希表ht[1](sizemask為111, index = hash & 0b111)。

ht[0]中處于bucket0位置的key的哈希值低兩位為00，那么rehash至ht[1]時index取低三位可能為000(0)和100(4)。也就是ht[0]中bucket0中的元素rehash之后分散于ht[1]的bucket0與bucket4，以此類推，對應關系為：

 ht[0] -> ht[1] ----------------  0 -> 0,4   1 -> 1,5  2 -> 2,6  3 -> 3,7

如果SCAN命令采取0->1->2->3的順序進行遍歷，就會出現如下問題：

•擴展操作中，如果返回游標1時正在進行rehash，ht[0]中的bucket0中的部分數據可能已經rehash到ht[1]中的bucket[0]或者bucket[4]，在ht[1]中從bucket1開始遍歷，遍歷至bucket4時，其中的元素已經在ht[0]中的bucket0中遍歷過，這就產生了重復問題。
•縮小操作中，當返回游標5，但縮小后哈希表的size只有4，如何重置游標？

SCAN的遍歷順序

SCAN命令的遍歷順序，可以舉一個例子看一下：

127.0.0.1:6379[3]> keys *1) "bar"2) "qux"3) "baz"4) "foo"127.0.0.1:6379[3]> scan 0 count 11) "2"2) 1) "bar"127.0.0.1:6379[3]> scan 2 count 11) "1"2) 1) "foo"127.0.0.1:6379[3]> scan 1 count 11) "3"2) 1) "qux" 2) "baz"127.0.0.1:6379[3]> scan 3 count 11) "0"2) (empty list or set)

可以看出順序是0->2->1->3，很難看出規律，轉換成二進制觀察一下：

00 -> 10 -> 01 -> 11

二進制就很明了了，遍歷采用的順序也是加法，但每次是高位加1的，也就是從左往右相加、從高到低進位的。

SCAN源碼

SCAN遍歷字典的源碼在dict.c/dictScan，分兩種情況，字典不在進行rehash或者正在進行rehash。

不在進行rehash時，游標是這樣計算的：

m0 = t0->sizemask;// 將游標的umask位的bit都置為1v |= ~m0;// 反轉游標v = rev(v);// 反轉后+1，達到高位加1的效果v++;// 再次反轉復位v = rev(v);

當size為4時，sizemask為3(00000011)，游標計算過程：

   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時的游標狀態轉移為0->2->1->3。

同理,size為8時的游標狀態轉移為0->4->2->6->1->5->3->7，也就是000->100->010->110->001->101->011->111。

再結合前面的rehash：

  ht[0] -> ht[1]  ----------------   0  ->  0,4    1  ->  1,5   2  ->  2,6   3  ->  3,7

可以看出，當size由小變大時，所有原來的游標都能在大的哈希表中找到相應的位置，并且順序一致，不會重復讀取并且不會遺漏。

當size由大變小的情況，假設size由8變為了4，分兩種情況，一種是游標為0,2,1,3中的一種，此時繼續讀取，也不會遺漏和重復。

但如果游標返回的不是這四種，例如返回了7，7&11之后變為了3，所以會從size為4的哈希表的bucket3開始繼續遍歷，而bucket3包含了size為8的哈希表中的bucket3與bucket7，所以會造成重復讀取size為8的哈希表中的bucket3的情況。

所以，redis里rehash從小到大時，SCAN命令不會重復也不會遺漏。而從大到小時，有可能會造成重復但不會遺漏。

當正在進行rehash時，游標計算過程：

  /* 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));

算法會保證t0是較小的哈希表，不是的話t0與t1互換，先遍歷t0中游標所在的bucket，然后再遍歷較大的t1。

求下一個游標的過程基本相同，只是把m0換成了rehash之后的哈希表的m1，同時還加了一個判斷條件:

v & (m0 ^ m1)

size4的m0為00000011，size8的m1為00000111，m0 ^ m1取值為00000100，即取二者mask的不同位，看游標在這些標志位是否為1。

假設游標返回了2，并且正在進行rehash，此時size由4變成了8，二者mask的不同位是低第三位。

首先遍歷t0中的bucket2，然后遍歷t1中的bucket2，公式計算出的下一個游標為6(00000110)，低第三位為1，繼續循環，遍歷t1中的bucket6，然后計算游標為1，結束循環。

所以正在rehash時，是兩個哈希表都遍歷的，以避免遺漏的情況。

總結

以上所述是小編給大家介紹的Redis SCAN命令實現有限保證的原理,希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對武林網網站的支持！
如果你覺得本文對你有幫助，歡迎轉載，煩請注明出處，謝謝！