Redis之字典

字典本身就是很常見的數(shù)據(jù)結(jié)構(gòu)之一，在Redis中尸饺，Redis數(shù)據(jù)庫就是使用字典來作為底層實(shí)現(xiàn)的进统，除了用來表示數(shù)據(jù)庫之外助币，字典還是哈希鍵的底層實(shí)現(xiàn)之一。

建議閱讀：
1螟碎、字典部分源碼研究見： wenmingxing Redis源碼研究之dict

I眉菱、字典的實(shí)現(xiàn)

Redis的字典使用哈希表作為底層實(shí)現(xiàn)。

1.1 哈希表

Redis字典所使用的哈希表結(jié)構(gòu)定義如下：

typedef struct dictht {

    // 哈希表數(shù)組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩碼掉分，用于計(jì)算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節(jié)點(diǎn)的數(shù)量
    unsigned long used;

} dictht;

table屬性是一個數(shù)組俭缓，數(shù)組中的每個元素都指向一個dictEntry結(jié)構(gòu)的指針，每個dictEntry結(jié)構(gòu)保存著一個鍵值對酥郭。

size屬性記錄了哈希表的大小华坦，即table數(shù)組的大小，而used屬性則記錄了哈希表目前已有鍵值對的數(shù)量不从。

sizemask屬性的值總是等于size-1惜姐，這個屬性和哈希值一起決定一個鍵應(yīng)該被放到table數(shù)組的哪個索引上。

下圖展示了一個大小為4的空哈希表：

1.2 哈希表節(jié)點(diǎn)

哈希表節(jié)點(diǎn)使用dictEntry結(jié)構(gòu)表示椿息，每個dictEntry結(jié)構(gòu)都保存一個鍵值對：

typedef struct dictEntry {

    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節(jié)點(diǎn)歹袁，形成鏈表
    struct dictEntry *next;

} dictEntry;

key屬性保持著鍵值對中的鍵，而v屬性則保存著鍵值對中的值寝优，其中鍵值對中的值可以是一個指針条舔，或者是一個整數(shù)。

next屬性是指向另一個哈希表節(jié)點(diǎn)的指針倡勇，這個指針可以將多個哈希值相同的鍵值對連接在一起逞刷，來解決鍵沖突問題（以鏈表的方式解決沖突問題）。

如下圖表示一個完成的哈希表：

1.3 字典

Redis中的字典結(jié)果如下：

typedef struct dict {

    // 類型特定函數(shù)
    dictType *type;

    // 私有數(shù)據(jù)
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當(dāng) rehash 不在進(jìn)行時妻熊，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type屬性和privdata屬性是針對不同類型的鍵值對，而創(chuàng)建多態(tài)字典而設(shè)置的：
type屬性是一個指向dictType結(jié)構(gòu)的指針仑最，每個dictType結(jié)構(gòu)保存了一組用于操作特定類型鍵值對的函數(shù)扔役，Redis會為用途不同的字典設(shè)置不同類型的特定函數(shù)。
而privadata屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)警医。

ht屬性是一個包含了兩個項(xiàng)的數(shù)組亿胸，數(shù)組中每個項(xiàng)都是一個dictht哈希表，一般情況下预皇，字典只使用ht[0]哈希表侈玄，而ht[1]哈希表只對ht[0]哈希表進(jìn)行rehash時使用。

另一個與rehash有關(guān)的就是rehashidx屬性吟温，它積累了rehash目前的進(jìn)度序仙，如果沒有進(jìn)行rehash，則它的值為-1鲁豪。

下圖為一個普通狀態(tài)下的字典結(jié)構(gòu)：

II潘悼、哈希算法

將一個新的鍵值對添加到字典里面的時候律秃，程序需要先根據(jù)鍵值對上面的鍵來計(jì)算出哈希值和索引值，然后再根據(jù)索引值治唤，將包含新鍵值對的哈希表節(jié)點(diǎn)放到哈希數(shù)組的指定索引上面棒动。

Redis計(jì)算哈希值和索引值的方法如下：

# 使用字典設(shè)置的哈希函數(shù)，計(jì)算鍵 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 屬性和哈希值宾添，計(jì)算出索引值
# 根據(jù)情況不同船惨， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

下面舉例說明一個完整的添加鍵值對<k0, v0>過程：

首先程序會先使用語句hash = dict->type->hashFunction(k0);計(jì)算的處k0的哈希值。
假設(shè)計(jì)算出的哈希值為8缕陕，則程序繼續(xù)index = hash & dict->ht[0].sizemask = 8 & 3 = 0;計(jì)算得到k0的索引值為0粱锐，這表示包含這個鍵值對的節(jié)點(diǎn)應(yīng)該放置到哈希表數(shù)組的索引0位置上。

tip： Redis使用MurmurHash2算法來計(jì)算鍵的哈希值榄檬。

III卜范、解決鍵沖突

Redis哈希表使用鏈地址法來解決鍵沖突，每個哈希表節(jié)點(diǎn)都有一個next指針鹿榜，多個哈希表節(jié)點(diǎn)可以用next構(gòu)成一個單向鏈表海雪，被分配到同一個索引上的節(jié)點(diǎn)可以用這個單向鏈表連接起來，從而解決鍵沖突問題舱殿。

下面的例子說明一個解決鍵沖突的實(shí)例：

另外因?yàn)閐ictEntry節(jié)點(diǎn)組成的鏈表沒有指向鏈表表尾的指針奥裸，為了考慮速度，程序總是將新節(jié)點(diǎn)添加到鏈表的表頭位置（這樣添加節(jié)點(diǎn)的時間復(fù)雜度為O(1)）沪袭。

IV湾宙、rehash

隨著操作的不斷進(jìn)行，哈希表保存的鍵值對會逐漸增多或減少冈绊，為了讓哈希表負(fù)載因子維持在一個合理范圍之內(nèi)侠鳄，當(dāng)哈希表保存的鍵值對太多或太少時，程序要對哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或收縮死宣。

Redis對字典的哈希表執(zhí)行rehash的步驟如下：

為字典的ht[1]哈希表分配空間伟恶，這個空間大小取決于要執(zhí)行的操作：
如果執(zhí)行的是擴(kuò)展操作，則ht[1]的大小為第一個大于等于等于ht[0].used*2的2^n毅该；
如果執(zhí)行的收縮操作博秫，則ht[1]的大小為第一個大于等于ht[0].used的2^n；
將保存在ht[0]中的所有鍵值對rehash到ht[1]上面：rehash指的是重新計(jì)算鍵的哈希值和索引值眶掌，然后將鍵值對放置到ht[1]的指定位置上挡育。
當(dāng)ht[0]包含的所有鍵值對都遷移到ht[1]之后，釋放ht[0]朴爬，將ht[1]設(shè)置為ht[0]即寒，并在ht[1]新創(chuàng)建一個空白哈希表，為下一次rehash做準(zhǔn)備。

下面為一個rehash的實(shí)例：

2*4 = 8(2^3)：

重新計(jì)算索引蒿叠，并復(fù)制：

哈希表的擴(kuò)展與收縮
當(dāng)以下條件中任意一個被滿足時明垢，程序會自動開始對哈希表執(zhí)行擴(kuò)展操作：

服務(wù)器目前沒有執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于1市咽。
服務(wù)器正在執(zhí)行BGSAVE或BGREWRITEAOF命令痊银，并且哈希表負(fù)載因子大于等于5。

區(qū)分這兩種情況的目的在于施绎，因?yàn)閳?zhí)行BGSAVE與BGREWRITEAOF過程中溯革，Redis都需要創(chuàng)建子進(jìn)程，而大多數(shù)操作系統(tǒng)都采用寫時復(fù)制技術(shù)來優(yōu)化子進(jìn)程使用效率谷醉，所以在子進(jìn)程存在期間致稀，服務(wù)器會提高執(zhí)行擴(kuò)展操作所需的負(fù)載因子，從而盡可能避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展操作俱尼，這可以避免不必要的內(nèi)存寫入抖单，最大限度的節(jié)約空間。

另一方面遇八，當(dāng)哈希表負(fù)載因子小于0.1時矛绘，程序自動開始對哈希表執(zhí)行收縮操作。

V刃永、漸進(jìn)式rehash

Redis中的rehash動作并不是一次性货矮、集中式完成的，而是分多次斯够、漸進(jìn)式的完成的囚玫。

這樣做的目的是，如果服務(wù)器中包含很多鍵值對读规，要一次性的將這些鍵值對全部rehash到ht[1]的話抓督，龐大的計(jì)算量可能導(dǎo)致服務(wù)器在一段時間內(nèi)停止服務(wù)于。

為了避免這種影響束亏，Redis采用了漸進(jìn)式Redis：

為ht[1]分配空間本昏，讓字典同時持有ht[0]和ht[1]兩個哈希表。
在字典中維持一個索引計(jì)數(shù)器變量rehashidx枪汪，并將它置為0，表示rehash工作開始怔昨。
在rehash進(jìn)行期間雀久，每次對字典執(zhí)行添加、刪除趁舀、查找或者更新操作時赖捌，程序除了執(zhí)行指定操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]中，當(dāng)rehash工作完成之后越庇，程序?qū)ehashidx屬性的值+1罩锐。
隨著字典操作的不斷進(jìn)行，最終在某個時間點(diǎn)上卤唉，ht[0]的所有鍵值對都被rehash到ht[1]上涩惑，這時將rehashidx屬性設(shè)為-1，表示rehash完成桑驱。

漸進(jìn)式rehash的好處在于其采取分而治之的方式竭恬，將rehash鍵值對所需要的計(jì)算工作均攤到字典的每個添加、刪除熬的、查找和更新操作上痊硕，從而避免了集中式rehash而帶來的龐大計(jì)算量。

下面為一個漸進(jìn)式rehash的實(shí)例：

漸進(jìn)式rehash執(zhí)行期間的哈希表操作
因?yàn)樵跐u進(jìn)式rehash的過程中押框，字典會同時使用ht[0]和ht[1]兩個哈希表岔绸，所以在漸進(jìn)式rehash進(jìn)行期間，字典的刪除橡伞、查找盒揉、更新等操作都是在兩個表上進(jìn)行的。

例如骑歹，查找操作會先在ht[0]上進(jìn)行预烙，如果沒找到再在ht[1]上進(jìn)行。

添加操作的鍵值對會一律保存到ht[1]中道媚，這一措施保證ht[0]包含的鍵值對只會減少不會增加扁掸。

VI、字典API

【參考】
[1] 《Redis的設(shè)計(jì)與實(shí)現(xiàn)》

歡迎轉(zhuǎn)載最域，轉(zhuǎn)載請注明出處wenmingxing Redis之字典