Redis底層探秘（三）：字典

Redis底層探秘（三）：字典

       字典，又稱為符号表（symbol table）、關聯數組（associative array）或映射（map），是一種用于儲存鍵值對的抽象資料結構。

       字典經常作為一種資料結構内置在很多進階程式設計語言裡面，但redis所使用的C語言并沒有内置這種資料結構，是以Redis建構了自己的字典實作。

       字典在redis中的應用相當廣泛，比如redis的資料庫就是使用字典來作為底層實作的，對資料庫的增、删、查、改操作也是建構在對字典的操作之上的。

       除了用來實作資料庫之外，字典還是哈希鍵的底層實作之一，當一個哈希鍵包含的鍵值對比較多，又或者鍵值對中的元素都是比較長的字元串時，Redis就會使用字典作為哈希鍵的底層實作。

字典的實作

       Redis的字典使用哈希表作為底層實作，一個哈希表裡面可以有多個哈希表節點，而每個哈希表節點就儲存了一個字典中的一個鍵值對。

       接下來我們分别介紹redis 的哈希表、哈希表節以及字典的實作。

　　哈希表

dict.h/ dictht結構定義如下

typedef struct dictht {
    dictEntry **table;//哈希表數組
    unsigned long size;//哈希表大小
    unsigned long sizemask;//哈希表大小掩碼，用于計算索引值，總是等于size-1
    unsigned long used;//該哈希表已有節點的數量
} dictht;      

       table屬性是一個數組，數組中的每個元素都是一個指向dict.h/ dictEntry結構的指針，每個dictEntry結果儲存着一個鍵值對。size屬性記錄了哈希表的大小，也即是table數組的大小，而used屬性則記錄了哈希表目前已有節點（鍵值對）的數量。sizemask屬性的值總是等于size-1，這個屬性和哈希值一起決定了一個鍵應該被放到table數組的哪個索引上面。下圖是一個空哈希表。

　　哈希表節點

哈希表節點用dictEntry結構表示，每個dictEntry結構都儲存着一個鍵值對

typedef struct dictEntry {
    //鍵
void *key;
    //值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
} v;
//指向下個哈希表節點，形成連結清單
    struct dictEntry *next;
} dictEntry;      

       key屬性儲存着鍵值對中的鍵，而v屬性儲存着鍵值對中的值，其中鍵值對的值可以是一個指針，或者是一個uint64整數或者是一個int64_t整數。

       next屬性是指向另一個哈希表節點的指針，這個指針可以将多個哈希值相同的鍵值對連接配接在一起，以此來解決鍵沖突（collision）的問題。

       下圖展示了将兩個索引值相同的鍵k1和k0連接配接在一起。

　　字典

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

typedef struct dict {
    //類型特定函數
dictType *type;
    //私有資料
void *privdata;
//哈希表
dictht ht[2];
//rehash索引，當rehash不在進行時，值為-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;      

       type屬性和privdata屬性是針對不同類型的鍵值對，為建立多态字典而設定的

type：一個指向ditcType結構的指針，每個ditcType結構儲存了一簇用于操作特定類型鍵值對的函數，redis回味用途不同的字典設定不同的類型特定函數。

privdata：儲存了需要傳給那些類型特定函數的的可選參數。

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);//計算哈希值的函數
    void *(*keyDup)(void *privdata, const void *key);//複制鍵的函數
    void *(*valDup)(void *privdata, const void *obj);//複制值的函數
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);//對比鍵的韓式
    void (*keyDestructor)(void *privdata, void *key);//銷毀鍵的函數
    void (*valDestructor)(void *privdata, void *obj);//銷毀值的函數
} dictType;      

       ht屬性是一個包含兩個項的數組，數組中的每個項都是一個dictht哈希表，一般情況下，字典隻使用ht[0]哈希表，ht[1]哈希表隻會在對ht[0]哈希表記性rehash時使用。

       除了ht[1]之外，另一個和rehash有關的屬性就是rehashidx，它記錄了rehash目前的進度，如果目前沒有在進行rehash，那麼它的值-1。

下圖是一個普通狀态下的字典

雜湊演算法

       當要講一個新的鍵值對添加到字典裡面時，程式需要先根據鍵值對的鍵計算出哈希值和索引值，然後再根據索引值，将包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。

       redis計算哈希值和索引值的方法如下：

#使用字典設定的哈希函數，計算key的哈希值

hash=dict->type->hashFunction(key);

#使用哈希表的sizemask屬性和哈希值，計算出索引值

#根據情況不同，ht[x]可以是ht[0]或者ht[1]

index=hash&dict->ht[x].sizemask;

       對于上圖所示的空字典來說，如果我們要将一個鍵值對k0和v0添加到字典裡面，那麼程式會先使用語句：

hash=dict->type->hashFunction(k0);

計算鍵k0的哈希值。

假設計算得出的哈希值為8，那麼程式會繼續使用語句：

index=hash&dict->ht[0].sizemask=8&3=0;

　　計算出鍵k0的索引值0，這表示包含鍵值對k0和v0的節點應該被防止到哈希表數組的索引0位置上。如下圖所示。

       當字典被用作資料庫的底層實作，或者哈希鍵的底層實作時，redis使用Murmurhash2算法來計算鍵的哈希值。Murmurhash2算法最初由austin applebyu于2008年發明，優點在于，即使輸入的鍵是有規律的，算法仍能給出以空格很好的随機分布性，并且算法的計算速度也非常快。

　　解決鍵沖突

       當有兩個或以上數量的鍵被配置設定到了哈希表數組的同一個索引上面時，我們稱這些鍵發生了沖突。

       redis的哈希表使用連位址發（）來解決鍵沖突，每個哈希表節點都有一個next指針，多個哈希表節點可以用next指針構成一個單向連結清單，被配置設定到同一個索引上的多個節點可以用這個單向連結清單連接配接起來，這就解決了鍵沖突的問題。

       因為dictEntey節點組成的連結清單沒有指向連結清單表尾的指針，是以為了速度考慮從，程式總是将新節點添加到連結清單的表頭位置（複雜度為0（1）），排在其他已有節點的前面。下圖為k2加入到哈希表中出現沖突，加入到連結清單頭之後的情況。

　　rehash

       随着操作的不斷執行，哈希表儲存的鍵值對會逐漸地增多或者減少，為了讓哈希表的負載因子（load factor）維持在一個合理的範圍之内，當哈希表儲存的鍵值對數量太多或者太少時，程式需要對哈希表的大小進行相應的擴充或者收縮。

       擴充和收縮哈希表的工作可以通過執行rehash（重新散列）操作來完成，redis對字典的哈希表執行rehash的步驟如下：

1、為字典的ht[1]哈希表配置設定空間，這個哈希表的空間大小取決于要執行的操作，以及ht[0]目前包含的鍵值對數量（也即是h[0].userd屬性的值）；

       如果執行的是擴充操作，那麼ht[1]的大小為第一個大于等于h[0].userd*2的2^n(2的n次幂)。

       如果執行的是收縮操作，那麼ht[1]的大小為第一個大于等于h[0].userd的2^n(2的n次幂)。

2、将儲存在ht[0]中的所有鍵值對rehash到ht[1]上面；rehash指的是重新計算鍵的哈希值和索引值，然後将鍵值對防止到ht[1]哈希表指定位置上。

3、當ht[0]包含的所有鍵值對都遷移到ht[1]之後（ht[0]變為空表），釋放ht[0]，将ht[1]設定為ht[0]，并在ht[1]建立一個空白哈希表，為下一次rehash做準備。

       舉個例子，如下圖

1、ht[0].used目前的值為4，4*2=8，而8（2^3）恰好是第一個大于等于4的2的n次方，是以程式會将ht[1]

哈希表的大小設定為8。下圖展示了ht[1]配置設定空間之後，字典的樣子。

2、 将ht[0]包含的四個鍵值對都rehash到ht[1]，如下圖

3、 釋放ht[0]，并将ht[1]設定為ht[0]，然後為ht[1]配置設定一個空白哈希表，如下圖，至此，哈希表的擴充操作執行完畢。

　　哈希表的擴充和收縮

       當一下條件的任意一個被滿足時，程式會自動開始對哈希表執行擴充操作：

1 伺服器目前沒有在執行BGSAVE指令或者BGREWRITEAOF指令，并且哈希表的負載因子大于等于1.

2 伺服器牧目前正在執行BGSAVE指令或者BGREWRITEAOF指令，并且哈希表的複制因子大于等于5.

       其中哈希表的複制因子可以通過公式：

# 負載因子=哈希表已儲存節點數量/哈希表大小

load_factor=ht[0].userd/ht[0].size

例如，對于一個大小為4，包含4個鍵值對的哈希表來說，這個哈希表的負載因子為：

load_factor=4/4=1

       另一方面，當哈希表的負載因子小于0.1時，程式自動開始對哈希表執行收縮操作。

　　漸進式rehash

       擴充或收縮哈希表需要将ht[0]裡面的所有鍵值對rehash到ht[1]裡面，但是，這個rehash動作并不是一次性、集中式地完成的，而是分多次、漸進式地完成的。

       這樣做的原因在于如果哈希表中儲存的鍵值對過多，一次性轉移的話，龐大的計算了可能會導緻伺服器在一段時間内停止服務。

       是以，為了避免rehash對伺服器性能造成影響，伺服器不是一次性将ht[0]裡面的所有鍵值對全部rehash到ht[1]，而是分多次、漸進式的進行。

       以下是哈希表漸進式rehash的詳細步驟：

1 為ht[1]配置設定空間，讓字典同時持有ht[0]和ht[1]兩個哈希表。

2 在字典中維持一個索引計數器變量rehashidx，并将它的值設定為0，表示rehash工作正式開始。

3 在rehash進行期間，每次對字典執行添加、删除、查找或者更新時，程式除了執行指定的操作以外，還順帶将ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當rehash工作完成之後，程式将将rehashidx屬性的值增一。

4 随着字典操作的不斷執行，最終在某個時間點上，ht[0]的所有鍵值對都會被都會被rerhash至ht[1]，這時程式程式将rehashidx屬性的值設為-1，表示rehash操作已完成。

       漸進式rehash的好處在于它采取分而治之的方式，将rehash鍵值對所需的計算工作均攤到對字典的每個添加、删除、查找和更新操作上，進而避免了集中式rehash而帶來的龐大計算量。

漸進式rehash執行期間的哈希表操作

       因為在進行漸進式rehash的過程中，字典會同時使用ht[0]和ht[1]兩個哈希表，是以在漸進式rehash進行期間，字典的删除、查找、更新等操作會在兩個哈希表上進行。例如，要在字典裡面查找一個鍵的話，程式會現在ht[0]裡面進行查找，如果沒找到的話，就會繼續到ht[1]裡面進行查找，諸如此類。

       另外，在漸進式rehash執行期間，新增加到字典的鍵值對一律會被儲存到ht[1]裡面，而ht[0]則不再進行任何添加操作，這一措施保證了ht[0]包含的鍵值對數量隻會減少不會增加，并随着rehash 操作的執行而最終變成空表。

字典API