共計 4282 個字符，預計需要花費 11 分鐘才能閱讀完成。

自動寫代碼機器人，免費開通

這篇文章將為大家詳細講解有關怎么在 Redis 中使用 SCAN 命令實現有限保證，文章內容質量較高，因此丸趣 TV 小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

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 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，很難看出規律，轉換成二進制觀察一下：

00 – 10 – 01 – 11

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

SCAN 源碼

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

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

m0 = t0- sizemask;
//  將游標的 umask 位的 bit 都置為 1
v |= ~m0;
//  反轉游標
v = rev(v);
//  反轉后 +1，達到高位加 1 的效果
//  再次反轉復位
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 命令實現有限保證就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

向 AI 問一下細節