摘要：全部視頻每日學習記錄使用錄像設備記錄每天的學習字典是啥，即字典，也被稱為哈希表。通常情況下，一個長這樣在這個哈希表中，每個存儲單元被稱為一個桶。完成之后，新哈希表就會被置為，為線上提供服務。

baiyan

全部視頻：【每日學習記錄】使用錄像設備記錄每天的學習

dict，即字典，也被稱為哈希表hashtable。在redis的五大數據結構中，有如下兩種情形會使用dict結構：

hash：數據量小的時候使用ziplist，量大時使用dict
zset：數據量小的時候使用ziplist，數據量大的時候使用skiplist + dict

結合以上兩種情況，我們可以看出，dict也是一種較為復雜的數據結構，通常用在數據量大的情形中。通常情況下，一個dict長這樣：

在這個哈希表中，每個存儲單元被稱為一個桶（bucket）。我們向這個dict(hashtable)中插入一個"name" => "baiyan"的key-value對，假設對這個key “name”做哈希運算結果為3，那么我們尋找這個hashtable中下標為3的位置并將其插入進去，得到如圖所示的情形。我們可以看到，dict最大的優勢就在于其查找的時間復雜度為O(1)，是任何其它數據結構所不能比擬的。我們在查找的時候，首先對key ”name“進行哈希運算，得到結果3，我們直接去dict索引為3的位置進行查找，即可得到value ”baiyan“，時間復雜度為O(1)，是相當快的。

在redis中，在普通字典的基礎上，為了方便進行擴容與縮容，增加了一些描述字段。還是以上面的例子為基礎，在redis中存儲結構如下圖所示：

dictht的結構如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

在dictht中，真正存儲數據的地方是**table這個dictEntry類型二級指針。我們可以把它拆分來看，首先第一個指針可以代表一個一維數組，即哈希表。而后面的指針代表，在每個一維數組（哈希表）的存儲單元中，存儲的都是一個dictEntry類型的指針，這個指針就指向我們存儲key-value對的dictEntry類型結構的所在位置，如上圖所示。
存儲最終key-value對的dictEntry的結構如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

一個存儲key-value對的entry，最主要還是這里的key和value字段。由于存儲在dict中的key和value可以是字符串、也可以是整數等等，所以在這里均用一個void * 指針來表示。我們注意到最后有一個也是同類型dictEntry的next指針，它就是用來解決我們經常說的哈希沖突問題。

當我們對不同的key進行哈希運算之后結果相同時，就碰到了哈希沖突的問題。常用的兩種哈希沖突的解決方案有兩種：開放定址法與鏈地址法。redis使用的是后者。通過這個next指針，我們就可以將哈希值相同的元素都串聯起來，解決哈希沖突的問題。注意在redis的源碼實現中，在往dict插入元素的時使用的是鏈表的頭插法，即將新元素插到鏈表的頭部，這樣就不用每次遍歷到鏈表的末尾進行插入，降低了插入的時間復雜度。

假設我們一直往dict中插入元素，那么這個哈希表的所有bucket都會被占滿，而且在鏈地址法解決哈希沖突的過程中，每個bucket后面的鏈表會非常長。這樣一來，這個鏈表的時間復雜度就會逐漸退化成O(n)。對于整體的dict而言，其查詢效率就會大大降低。為了解決數據量過大導致dict性能下降的問題，我們需要對其進行擴容，來滿足后續插入元素的存儲需要。

在通常情況下，我們會對哈希表做一個2倍的擴容，即由2->4，4->8等等。假設我們的一個dict中已經存儲了好多數據，我們還需要向這個dict中插入一大堆數據。在后續插入大量數據的過程中，由于我們需要解決dict性能下降的問題，我們需要對其進行擴容。由于擴容的時候，需要對所有key-value對重新進行哈希運算，并重新分配到相應的bucket位置上，我們稱這個過程為為rehash。

在rehash過程中，需要做大量的哈希運算操作，其開銷是相當大、而且花費的時間是相當長的。由于redis是單進程、單線程的架構，在執行rehash的過程中，由于其開銷大、時間長，會導致redis進程阻塞，進而無法為線上提供數據存儲服務，對外部會返回redis服務不可用。為了解決一次性rehash所導致的redis進程阻塞的問題，利用分而治之的編程思想，將一次rehash操作分散到多個步驟當中去減小rehash給redis進程帶來的資源占用。舉一個例子，可能會在后續的get、set操作中，進行一次rehash操作。為了實現這種操作，redis其實設計了兩個哈希表，一個就是我們之前講過的對外部提供存取服務的哈希表，而另一個就專門用來做rehash操作。這種分而治之的思想，將一次大數據量的rehash操作分散到多次完成，叫做漸進式rehash：

目前是剛剛要進行rehash的狀態。我們可以看到，在之前畫的圖的基礎上，我們加入了一個新的結構dict，其中的ht[2]字段就負責指向兩個哈希表。下面一個哈希表的大小為之前的大小8*2=16，沒有任何元素。關于dict的結構如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehash進程標識。如果值為-1則不在rehash，否則在進行rehash */
    unsigned long iterators; /* number of iterators currently running */
} dict;

注意其中的rehashidx字段，它代表我們進行rehash的進程。注意我們每次進行get或set等命令的時候，rehash就會進行一次，即把一個在原來哈希表ht[0]上的元素挪到新哈希表ht[1]中，注意一次只移動一個元素，移動完成之后，rehashidx就會+1，直到原來哈希表上所有的元素都挪到新哈希表上為止。rehash完成之后，新哈希表ht[1]就會被置為ht[0]，為線上提供服務。而原來的哈希表ht[0]就會被銷毀。rehash的源碼如下：

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];
        /* 將老的哈希表ht[0]中的元素移動到新哈希表ht[1]中 */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* 計算新哈希表ht[1]的索引下標*/
            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++;
    }

    /* 檢查是否rehash完成，若完成則置rehashidx為-1 */
    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;
}

如果在rehash的過程中（例如容量由4擴容到8），如果需要查找一個元素。首先我們會計算哈希值（假設為3）去找老的哈希表ht[0]，如果我們發現位置3上已經沒有了元素，說明這個元素已經被rehash過了，到新的哈希表上對應的位置3或7上尋找即可。

試想這么一種情況：在rehash之前，我們使用SCAN命令對dict進行第一次遍歷；而rehash結束之后我們進行第二次SCAN遍歷，會發生什么情況？
在討論這個問題之前，我們先熟悉一下SCAN命令。我們知道在我們執行keys這種返回所有key值的命令，由于所有key加在一塊是相當多的，如果一次性全部把它遍歷完成，能夠讓單進程的redis阻塞相當長的時間，在這段時間里都無法對外提供服務。為了解決這個問題，SCAN命令橫空出世。它并不是一次性將所有的key都返回，而是每次返回一部分key并記錄一下當前遍歷的進度，這里用一個游標去記錄。下次再次運行SCAN命令的時候，redis會從游標的位置開始繼續往下遍歷。SCAN命令實際上也是一種分而治之的思想，這樣一次遍歷一小部分，直到遍歷完成。SCAN命令官方解釋如下：

SCAN 命令是一個基于游標的迭代器： SCAN 命令每次被調用之后， 都會向用戶返回一個新的游標，用戶在下次迭代時需要使用這個新游標作為 SCAN 命令的游標參數， 以此來延續之前的迭代過程。

SCAN命令的使用方法如下：

redis 127.0.0.1:6379> scan 0
1) "17"
2)  1) "key:12"
    2) "key:8"
    3) "key:4"
    4) "key:14"
    5) "key:16"
    6) "key:17"
    7) "key:15"
    8) "key:10"
    9) "key:3"
    10) "key:7"
    11) "key:1"

redis 127.0.0.1:6379> scan 17
1) "0"
2) 1) "key:5"
   2) "key:18"
   3) "key:0"
   4) "key:2"
   5) "key:19"
   6) "key:13"
   7) "key:6"
   8) "key:9"
   9) "key:11"

在上面這個例子中，第一次迭代使用0作為游標，表示開始一次新的迭代。第二次迭代使用的是第一次迭代時返回的游標，也即是命令回復第一個元素的值17 。


從上面的示例可以看到， SCAN 命令的回復是一個包含兩個元素的數組，第一個數組元素是用于進行下一次迭代的新游標，而第二個數組元素則是一個數組，這個數組中包含了所有被迭代的元素。
在第二次調用 SCAN 命令時，命令返回了游標0，這表示迭代已經結束，整個數據集（collection）已經被完整遍歷過了。
以0作為游標開始一次新的迭代，一直調用 SCAN 命令，直到命令返回游標0，我們稱這個過程為一次完整遍歷。

回到正題，我們來解決之前的問題。 我們簡化一下dict的結構，只留下兩個基本的哈希表結構，我們現在有4個元素：12、13、14、15，假設哈希算法為取余。

假設現在我們在沒有rehash之前，對其使用SCAN命令，基于我們之前講過的知識點，由于SCAN是基于游標的增量遍歷，我們假設這個SCAN命令只遍歷到游標為1的位置就停止了：

我們得到第一次遍歷的結果為：12

開始進行rehash。

rehash結束，我們再次使用SCAN命令對其進行遍歷。由于上次返回的游標為1，我們從1的位置繼續遍歷，只不過這次要在新的哈希表中進行遍歷了：

第二次SCAN命令遍歷的結果為：12、13、14、15

那么我們將兩次SCAN的結果合起來，為12、12、13、14、15。我們發現，元素12被多遍歷了一次，與我們的預期不符。所以我們得出結論：在rehash過程中執行SCAN命令會導致遍歷結果出現冗余。

為了解決擴容和縮容進行rehash的過程中重復遍歷的問題，redis對哈希表的下標做出了如下變化（v就是哈希表的下標）：

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

首先將游標倒置，加一后，再倒置，也就是我們所說的“高位++”的操作。這里的這幾步操作是來通過前一個下標，計算出哈希表下一個bucket的下標。舉一個例子：最開始00這個bucket不用動，之前經過正常的低位++之后，00的后面應該為01。然而現在是高位++，原來01的位置的下標就會變成10.......以此類推。最終，哈希表的下標就會由原來順序的00、01、10、11變成了00、10、01、11，如圖所示：

這樣就能夠保證我們多次執行SCAN命令就不會重復遍歷了嗎？接下來就是見證奇跡的時刻：

首先還是沒進行rehash之前，對其進行SCAN。同樣的，我們假設這個SCAN命令只遍歷到游標為1的位置就停止了：

我們得到第一次遍歷的結果：12

開始進行rehash

rehash結束，我們再次使用SCAN命令對其進行遍歷。注意這里，上次返回的游標為2，我們從2的位置繼續遍歷，也是要在新的哈希表中進行遍歷了：

我們可以看到，經過一個小的下標的修改，就能夠解決rehash所帶來的SCAN重復遍歷的問題。對dict進行遍歷的源碼如下：

unsigned long dictScan(dict *d,
                      unsigned long v,
                      dictScanFunction *fn,
                      dictScanBucketFunction* bucketfn,
                      void *privdata)
{
   dictht *t0, *t1;
   const dictEntry *de, *next;
   unsigned long m0, m1;

   if (dictSize(d) == 0) return 0;

   // 如果SCAN的時候沒有進行rehash
   if (!dictIsRehashing(d)) {
       t0 = &(d->ht[0]);
       m0 = t0->sizemask;

       /* Emit entries at cursor */
       if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
       de = t0->table[v & m0];
       while (de) { //遍歷同一個bucket上后面掛接的鏈表
           next = de->next;
           fn(privdata, de);
           de = next;
       }

       /* Set unmasked bits so incrementing the reversed cursor
        * operates on the masked bits */
       v |= ~m0;

       /* Increment the reverse cursor */
       v = rev(v); //反轉v
       v++; //反轉之后即為高位++
       v = rev(v); //再反轉回來，得到下一個游標值

    // 如果SCAN的時候正在進行rehash
   } else { 
       t0 = &d->ht[0];
       t1 = &d->ht[1];

       /* 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) { //遍歷同一個bucket上后面掛接的鏈表
           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) { //遍歷同一個bucket上后面掛接的鏈表
               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++; //反轉之后即為高位++
           v = rev(v); //再反轉回來，得到下一個游標值

           /* Continue while bits covered by mask difference is non-zero */
       } while (v & (m0 ^ m1));
   }

   return v;
}

有關rehash過程對SCAN的影響，限于篇幅僅僅展示這種情況。更多的情形請參考：Redis scan命令原理