Redis字典實現、Hash鍵沖突及漸進式rehash詳解
本筆記參考《Redis設計與實現》 P24~ 37
Redis字典實現
哈希表節點結構
typedef struct dictEntry { // 鍵 void *key; // 值 : 可以是一個指針,或者是一個uint64/int64 的整數 union { void *val; uint64_t u64; int64_t s64 } v; // 指向下一個哈希表節點,形成鏈表 : 該指針可以將多個哈希值相同的鍵值對連接在一起,以此解決鍵沖突的問題。 struct dictEntry *next; } dictEntry;
哈希表結構
typedef struct dictht { // 哈希表數據 dictEntry **table; // 哈希表集合大小 unsigned long size; // 哈希表大小掩碼,用於計算索引值 // 總是等於 size - 1 unsigned long sizemask; // 哈希表已有節點數量 unsigned long used; } dictht;
字典
typedef struct dict { // 類型特定函數 dicType *type; // 私有數據 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 當rehash不在進行時, 值為-1 int rehashidx; } dict;
type屬性和privdata屬性針對不同類型的鍵值對,為多態字典而設置。
ht是包含兩個項的數組,每個元素都是一個dictht哈希表,一般情況下字典之是喲個ht[0],ht[1]會在對ht[0]進行rehash的時候使用。
rehashidx記錄瞭rehash目前的進度,如果目前沒有在進行rehash,值為-1。
哈希算法
- 使用字典設置的哈希函數,計算key的hashvalue
hash = dict->type->hashFunction(key);
- 使用哈希表的sizemask屬性和哈希值,計算出索引值
- 根據不同的情況,ht[x]可以是ht[0]或ht[1]
index = hash & dict->ht[x].sizemask;
redis使用的是MurmurHash算法,優點是:輸入的鍵是有規律的時候,算法仍然能給出很好的隨機分佈性,計算速度也快。
解決hash沖突
當有兩個或以上的key分配到瞭hash table數組的同一個index上,稱為發生瞭collision。
Redis采用鏈地址法解決沖突,每個hash table節點都有一個next指針,多個hash table節點可以用next指針構成一個單向鏈表。為瞭速度考慮,程序總是會將新節點插入到鏈表頭位置。
rehash
隨著操作不斷執行,哈希表保存的key value對會逐漸增加和減少。哈希表有一個統計參數load factor,即負載因子,公式如下:
# 負載因子 = 哈希表已經保存的節點數量 / 哈希表大小 load_factor = ht[0].used / ht[0].size;
為瞭維持負載因子在一個合理的范圍,程序會對哈希表的大小進行相應的擴展或收縮,條件如下:
1、服務器目前沒有執行BGSAVE命令或者BGREWRITEAOF命令,並且哈希表的負載因子 >= 1
2、服務器正在執行BGSAVE命令或者BGREWRITEAOF命令,且負載因子 >= 5
- 在執行BGSAVE命令或者BGREWRITEAOF命令過程中,Redis需要創建當前服務器進程的子進程,大多的OS采用寫時復制技術優化子進程的使用效率,所以子進程存在期間,**服務器會提高執行擴展操作的負載因子,避免在子進程存在期間進行哈希表的擴展操作,避免不必要的內存寫入操作,最大限度節約內存。**當負載因子小於0.1時,程序自動對哈希表進行收縮操作。
- 此時就會進行擴展收縮,規則如下:
- 這裡就是rehash(重新散列)操作瞭:
- 1、為字典的ht[1]哈希表分配內存空間,空間大小取決於要執行的操作,以及ht[0]當前包含的鍵值對數量(ht[0].used)
- 如果是擴展操作,ht[1]的大小為 >= ht[0].used * 2的 2的冪次方
- 如果是收縮操作,ht[1]的大小為 >= ht[0].used 的 2的冪次方
- 2、將保存在ht[0]中的所有鍵值對rehash到ht[1]上:即重新計算key的hashValue以及indexValue,然後將鍵值對放到ht[1]的指定位置
- 3、當ht[0]包含的所有鍵值對都遷移到ht[1]之後,ht[0]變為空表,釋放ht[0],將ht[1]置為ht[0],在ht[1]重新分配一個空白的哈希表,為下一次rehash做準備
漸進式hash
rehash的動作並不是一次性集中完成的,而是分多次漸進完成。
如果哈希表中村的鍵值對數量很多,一次性將鍵值對全部rehash到ht[1]的計算量十分龐大,可能會導致服務器在一段時間內停止服務。
漸進式rehash采取分而治之的方法,將rehash鍵值對所需要的計算工作分攤到每次對字典的CRUD操作上,從而避免瞭集中式rehash帶來的龐大計算量。
詳細步驟如下:
1、為ht[1]分配空間,讓字典同時持有ht[0]和ht[1]兩個哈希表
2、在字典中維護一個索引計數器:rehashidx,將值設置為0,表示rehash工作正式開始。
3、在rehash進行期間,每次對字典的CRUD操作,程序除瞭執行指定操作以外,順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]上,當rehash操作完成後,程序將rehashidx值++
4、重復迭代操作執行後,ht[0]的數據全部rehash到ht[1]上,將rehashidx設為-1,表明rehash操作已經完成
需要註意的地方
在rehash的過程中,對於字典的刪除、查找、更新操作會在兩個哈希表上執行。如想要查找一個鍵,現在ht[0]中找,沒有找到再去ht[1]
對於insert操作來說,新添加到字典的鍵值對會一律保存到ht[1]中,不然還得多一次搬運。
到此這篇關於Redis字典實現、Hash鍵沖突以及漸進式rehash的文章就介紹到這瞭,更多相關Redis 漸進式rehash內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!