前言

字典， 又稱符號(hào)表（symbol table）、關(guān)聯(lián)數(shù)組（associative array）或者映射（map）， 是一種用于保存鍵值對(duì)（key-value pair）的抽象數(shù)據(jù)結(jié)構(gòu)。

在字典中， 一個(gè)鍵（key）可以和一個(gè)值（value）進(jìn)行關(guān)聯(lián)（或者說(shuō)將鍵映射為值）， 這些關(guān)聯(lián)的鍵和值就被稱為鍵值對(duì)。

字典中的每個(gè)鍵都是獨(dú)一無(wú)二的， 程序可以在字典中根據(jù)鍵查找與之關(guān)聯(lián)的值， 或者通過(guò)鍵來(lái)更新值， 又或者根據(jù)鍵來(lái)刪除整個(gè)鍵值對(duì)， 等等。

字典經(jīng)常作為一種數(shù)據(jù)結(jié)構(gòu)內(nèi)置在很多高級(jí)編程語(yǔ)言里面， 但 Redis 所使用的 C 語(yǔ)言并沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)， 因此 Redis 構(gòu)建了自己的字典實(shí)現(xiàn)。

字典在 Redis 中的應(yīng)用相當(dāng)廣泛， 比如 Redis 的數(shù)據(jù)庫(kù)就是使用字典來(lái)作為底層實(shí)現(xiàn)的， 對(duì)數(shù)據(jù)庫(kù)的增、刪、查、改操作也是構(gòu)建在對(duì)字典的操作之上的。

因此，了解字典對(duì)我們了解Redis數(shù)據(jù)庫(kù)有很大的幫助。同時(shí)可以跟Java的HashMap進(jìn)行對(duì)比，看看孰好孰壞。

字典的定義

 1 typedef struct dict {
 2 
 3     // 類(lèi)型特定函數(shù)
 4     dictType *type;
 5 
 6     // 私有數(shù)據(jù)
 7     void *privdata;
 8 
 9     // 哈希表
10     dictht ht[2];
11 
12     // rehash 索引
13     // 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
14     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
15 
16 } dict;

主要看ht，和rehashidx兩個(gè)參數(shù)。

ht 屬性是一個(gè)包含兩個(gè)項(xiàng)的數(shù)組， 數(shù)組中的每個(gè)項(xiàng)都是一個(gè) dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會(huì)在對(duì) ht[0] 哈希表進(jìn)行 rehash 時(shí)使用。

除了 ht[1] 之外， 另一個(gè)和 rehash 有關(guān)的屬性就是 rehashidx ： 它記錄了 rehash 目前的進(jìn)度， 如果目前沒(méi)有在進(jìn)行 rehash ， 那么它的值為 -1 。

 1 typedef struct dictht {
 2 
 3     // 哈希表數(shù)組
 4     dictEntry **table;
 5 
 6     // 哈希表大小
 7     unsigned long size;
 8 
 9     // 哈希表大小掩碼，用于計(jì)算索引值
10     // 總是等于 size - 1
11     unsigned long sizemask;
12 
13     // 該哈希表已有節(jié)點(diǎn)的數(shù)量
14     unsigned long used;
15 
16 } dictht;

table 屬性是一個(gè)數(shù)組， 數(shù)組中的每個(gè)元素都是一個(gè)指向 dict.h/dictEntry 結(jié)構(gòu)的指針， 每個(gè) dictEntry 結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。

size 屬性記錄了哈希表的大小， 也即是 table 數(shù)組的大小

sizemask 屬性的值總是等于 size-1 ， 這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到 table 數(shù)組的哪個(gè)索引上面。(不是很清楚，為什么要單獨(dú)定義一個(gè)mask，而不直接size-1)；

而 used 屬性則記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對(duì)）的數(shù)量。

 1 typedef struct dictEntry {
 2 
 3     // 鍵
 4     void *key;
 5 
 6     // 值
 7     union {
 8         void *val;
 9         uint64_t u64;
10         int64_t s64;
11     } v;
12 
13     // 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
14     struct dictEntry *next;
15 
16 } dictEntry;

key 屬性保存著鍵值對(duì)中的鍵， 而 v 屬性則保存著鍵值對(duì)中的值， 其中鍵值對(duì)的值可以是一個(gè)指針， 或者是一個(gè) uint64_t 整數(shù)， 又或者是一個(gè) int64_t 整數(shù)。

next 屬性是指向另一個(gè)哈希表節(jié)點(diǎn)的指針， 這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一次， 以此來(lái)解決鍵沖突（collision）的問(wèn)題。

可以明顯的看出來(lái)，redis是通過(guò)鏈表來(lái)解決hash沖突的。

因此，redis的字典大概如下：

Rehash

隨著操作的不斷執(zhí)行， 哈希表保存的鍵值對(duì)會(huì)逐漸地增多或者減少， 為了讓哈希表的負(fù)載因子（load factor）維持在一個(gè)合理的范圍之內(nèi)， 當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或者太少時(shí)， 程序需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮。

也就是我們常說(shuō)的，擴(kuò)容，再次hash。

Redis rehash過(guò)程：

• 為字典的 ht[1] 哈希表分配空間。一般為原字典的兩倍，即 ht[0] * 2；
• 將保存在 ht[0] 中的所有鍵值對(duì) rehash 到 ht[1] 上面
• 當(dāng) ht[0] 包含的所有鍵值對(duì)都遷移到了 ht[1] 之后 （ht[0] 變?yōu)榭毡恚?釋放 ht[0] ， 將 ht[1] 設(shè)置為 ht[0] ， 并在 ht[1] 新創(chuàng)建一個(gè)空白哈希表， 為下一次 rehash 做準(zhǔn)備。

但其實(shí)rehash是非常的耗時(shí)間的。假設(shè)ht[0]非常的大呢？ 40W，400W，甚至4000W呢？

一次rehash甚至可能導(dǎo)致redis宕機(jī)，所以出現(xiàn)了漸進(jìn)式hash。

漸進(jìn)式Rehash

這個(gè) rehash 動(dòng)作并不是一次性、集中式地完成的， 而是分多次、漸進(jìn)式地完成的。為了避免 rehash 對(duì)服務(wù)器性能造成影響， 服務(wù)器不是一次性將 ht[0] 里面的所有鍵值對(duì)全部 rehash 到 ht[1] ， 而是分多次、漸進(jìn)式地將 ht[0] 里面的鍵值對(duì)慢慢地 rehash 到 ht[1] 。

• 為 ht[1] 分配空間， 讓字典同時(shí)持有 ht[0] 和 ht[1] 兩個(gè)哈希表。
• 在字典中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx ， 并將它的值設(shè)置為 0 ， 表示 rehash 工作正式開(kāi)始。
• 在 rehash 進(jìn)行期間， 每次對(duì)字典執(zhí)行添加、刪除、查找或者更新操作時(shí)， 程序除了執(zhí)行指定的操作以外， 還會(huì)順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對(duì) rehash 到 ht[1] ， 當(dāng) rehash 工作完成之后， 程序?qū)?nbsp;rehashidx 屬性的值增一。
• 隨著字典操作的不斷執(zhí)行， 最終在某個(gè)時(shí)間點(diǎn)上， ht[0] 的所有鍵值對(duì)都會(huì)被 rehash 至 ht[1] ， 這時(shí)程序?qū)?nbsp;rehashidx 屬性的值設(shè)為 -1 ， 表示 rehash 操作已完成。

擴(kuò)容代碼大致如下：

 1 int dictRehash(dict *d, int n) {
 2     int empty_visits = n*10; /* Max number of empty buckets to visit. */
 3 
 4     // 判斷是否正在擴(kuò)容
 5     if (!dictIsRehashing(d)) return 0;
 6 
 7     while(n-- && d->ht[0].used != 0) {
 8         dictEntry *de, *nextde;
 9 
10         /* Note that rehashidx can't overflow as we are sure there are more
11          * elements because ht[0].used != 0 */
12         assert(d->ht[0].size > (unsigned long)d->rehashidx);
13 
14         // 找到一個(gè)不為空的桶，進(jìn)行遷移
15         while(d->ht[0].table[d->rehashidx] == NULL) {
16             d->rehashidx++;
17             if (--empty_visits == 0) return 1;
18         }
19         // 找到這個(gè)桶第一個(gè)指針節(jié)點(diǎn)
20         de = d->ht[0].table[d->rehashidx];
21         // 將這個(gè)桶中的所有的key節(jié)點(diǎn)轉(zhuǎn)移到新的數(shù)組中。while循環(huán)鏈表
22         while(de) {
23             uint64_t h;
24 
25             nextde = de->next;
26             /* Get the index in the new hash table */
27             h = dictHashKey(d, de->key) & d->ht[1].sizemask;
28             de->next = d->ht[1].table[h];
29             d->ht[1].table[h] = de;
30             d->ht[0].used--;
31             d->ht[1].used++;
32             de = nextde;
33         }
34         // 舊的桶節(jié)點(diǎn)置為null，并且rehashidx+1
35         d->ht[0].table[d->rehashidx] = NULL;
36         d->rehashidx++;
37     }
38 
39     /* Check if we already rehashed the whole table... */
40     if (d->ht[0].used == 0) {
41         zfree(d->ht[0].table);
42         d->ht[0] = d->ht[1];
43         _dictReset(&d->ht[1]);
44         d->rehashidx = -1;
45         return 0;
46     }
47 
48     /* More to rehash... */
49     return 1;
50 }

在進(jìn)行漸進(jìn)式 rehash 的過(guò)程中， 字典會(huì)同時(shí)使用 ht[0] 和 ht[1] 兩個(gè)哈希表， 所以在漸進(jìn)式 rehash 進(jìn)行期間， 字典的刪除（delete）、查找（find）、更新（update）等操作會(huì)在兩個(gè)哈希表上進(jìn)行： 比如說(shuō)， 要在字典里面查找一個(gè)鍵的話， 程序會(huì)先在 ht[0]里面進(jìn)行查找， 如果沒(méi)找到的話， 就會(huì)繼續(xù)到 ht[1] 里面進(jìn)行查找， 諸如此類(lèi)。

另外， 在漸進(jìn)式 rehash 執(zhí)行期間， 新添加到字典的鍵值對(duì)一律會(huì)被保存到 ht[1] 里面， 而 ht[0] 則不再進(jìn)行任何添加操作： 這一措施保證了 ht[0] 包含的鍵值對(duì)數(shù)量會(huì)只減不增， 并隨著 rehash 操作的執(zhí)行而最終變成空表。

所遇到問(wèn)提

問(wèn)題一：

要在字典里面查找一個(gè)鍵的話， 程序會(huì)先在 ht[0]里面進(jìn)行查找， 如果沒(méi)找到的話， 就會(huì)繼續(xù)到 ht[1] 里面進(jìn)行查找， 諸如此類(lèi)。

這一點(diǎn)其實(shí)我比較有疑惑？為何要先去ht[0]中查找，找不到再去ht[1]中查找，這樣豈不是效率低下，查找了兩張表。不能根據(jù)hash值和rehashidx進(jìn)行比較判斷么？只查一張表不行么？

為此我翻閱了不少資料：

這是redis官方其他人的pull request：https://github.com/antirez/redis/pull/5692    暫時(shí)還沒(méi)有merge

同時(shí)這是我和一位大佬的討論：https://github.com/Junnplus/blog/issues/35   最終得出結(jié)論

還是看源碼：(源碼真是一個(gè)好東西)

 1 for (table = 0; table <= 1; table++) {
 2     // 找到key的index
 3     idx = h & d->ht[table].sizemask;
 4     // 拿到key值對(duì)應(yīng)的value
 5     he = d->ht[table].table[idx];
 6     while(he) {
 7         if (key==he->key || dictCompareKeys(d, key, he->key))
 8             return he;
 9         he = he->next;
10     }
11     if (!dictIsRehashing(d)) return NULL;
12 }

其實(shí)只有兩種情況

• key在ht[0]，還沒(méi)有遷移
• key在ht[1]，已經(jīng)遷移了。

針對(duì)第一種情況，他在第一層的循環(huán)已經(jīng)找到了key值，并且返回(第八行)，不再繼續(xù)后面操作，因此不存在效率問(wèn)題。

第二種情況，看第五行，he此時(shí)為null，根本不會(huì)循環(huán)鏈表。然后第二次循環(huán)才能找到key。而第一次是做了一次hash，復(fù)雜度為O(1)。效率幾乎是沒(méi)有損失，因此也不存在效率問(wèn)題。

綜上：我得出的結(jié)論是。可以拿idx和rehashidx進(jìn)行對(duì)比，同時(shí)也可以像redis這樣寫(xiě)，不會(huì)損失效率。redis可能為了代碼的簡(jiǎn)潔以及統(tǒng)一，不想寫(xiě)那么多的判斷條件，因此沒(méi)有比較idx和rehashidx。

當(dāng)我認(rèn)為提前結(jié)束會(huì)更好，畢竟不用后續(xù)判斷了，也比較清楚。類(lèi)似這個(gè)request：https://github.com/antirez/redis/pull/5692/files

問(wèn)題二：

假如在redis準(zhǔn)備進(jìn)行rehash的時(shí)候，他需要為ht[1]申請(qǐng)一塊內(nèi)存，這塊內(nèi)存可是ht[0]的兩倍哦，那次是計(jì)算機(jī)內(nèi)存不存會(huì)如何？

梳理一下哈希表大小和內(nèi)存申請(qǐng)大小的對(duì)應(yīng)關(guān)系：

正常狀態(tài)下，redis為ht[1]分配完內(nèi)存后，會(huì)持續(xù)一段時(shí)間進(jìn)行rehash。rehash完畢后，就會(huì)釋放ht[0]內(nèi)存了。類(lèi)似如下圖：

內(nèi)存先上升，后下降。

但此時(shí)內(nèi)存不存的話，Redis會(huì)進(jìn)行大量的Key驅(qū)逐，也就是會(huì)淘汰掉很久未使用的key，跟LRU有點(diǎn)類(lèi)似。

那么此時(shí)可能就會(huì)影響到了業(yè)務(wù)，這是非常大的問(wèn)題呢。

那么針對(duì)在Redis滿容驅(qū)逐狀態(tài)下，如何避免因Rehash而導(dǎo)致Redis抖動(dòng)的這種問(wèn)題。

• 我們?cè)赗edis Rehash源碼實(shí)現(xiàn)的邏輯上，加上了一個(gè)判斷條件，如果現(xiàn)有的剩余內(nèi)存不夠觸發(fā)Rehash操作所需申請(qǐng)的內(nèi)存大小，即不進(jìn)行Resize操作；
• 通過(guò)提前運(yùn)營(yíng)進(jìn)行規(guī)避，比如容量預(yù)估時(shí)將Rehash占用的內(nèi)存考慮在內(nèi)，或者通過(guò)監(jiān)控定時(shí)擴(kuò)容。

參考文獻(xiàn)：

《redis設(shè)計(jì)與實(shí)現(xiàn)》  http:///preview/dict/incremental_rehashing.html

《美團(tuán)針對(duì)Redis Rehash機(jī)制的探索和實(shí)踐》  https://tech.meituan.com/2018/07/27/redis-rehash-practice-optimization.html

《Redis源碼分析》  https://github.com/Junnplus/blog/issues/35