本篇文章帶大家了解一下redis中的字典、哈希算法和rehash原理,希望對大家有所幫助!
redis 中的字典被廣泛用于實現(xiàn)Redis的各種功能,其中包括數(shù)據(jù)庫和哈希鍵。
字典的底層實現(xiàn)為哈希表,每個字典帶有兩個哈希表,一個平時使用,另一個在進(jìn)行rehash擴(kuò)充空間時才使用。【相關(guān)推薦:Redis視頻教程】
字典的結(jié)構(gòu)定義
typedef?struct?dict?{ //?類型特定函數(shù) dictType?*type; //?私有數(shù)據(jù) void?*privdata; //?哈希表,兩個元素 dictht?ht[2] //?rehash時記錄的索引下標(biāo),當(dāng)沒有rehash時,值為-1 int?rehashidx; }?dict;
==在進(jìn)行 rehash時,rehashidx每遷移一個索引的entry數(shù)據(jù)就會 + 1;==
其中,哈希表dictht 的結(jié)構(gòu)定義為:
typedef?struct?dictht?{ //?哈希表數(shù)組 dictEntry?**table; //?哈希表大小 unsigned?long?size; //?哈希表大小掩碼,用于計算索引值 unsigned?long?sizenask; //?該哈希表已有節(jié)點的數(shù)量 unsigned?long?uesd; }?dictht;
其中,table是一個數(shù)組,數(shù)組的每一個元素指向 dictEntry 類型的指針,dictEntry 類型里保存著一個鍵值對。
在這里也可以看出哈希表的節(jié)點是鏈表相連來解決哈希沖突問題的,也就是鏈地址法。
哈希沖突與哈希算法
? ? ? ? 為了實現(xiàn)從鍵到值的快速訪問,Redis使用了哈希表來保存所有鍵值對。鍵對應(yīng)Redis設(shè)置的Key,而值對應(yīng)的并不是值本身,而是指向具體值的指針。使用哈希表的最大好處就是可以用O(1)的時間復(fù)雜度快速找到鍵值對。但既然是哈希表,那么必然會有著哈希沖突的問題。
哈希沖突即指的是,當(dāng)兩個key的哈希值和哈希桶計算對應(yīng)關(guān)系時,正好落在了同一個哈希桶上。
Redis解決哈希沖突的方式是使用鏈?zhǔn)焦#?strong>拉鏈法。當(dāng)多個元素指向同一個哈希桶時,在同一個哈希桶中采用鏈表來保存對應(yīng)的數(shù)據(jù),它們之間依次用指針連接。
哈希算法
當(dāng)要將一個新的鍵值對添加到字典里面時,程序需要先根據(jù)鍵值對計算出哈希值和索引值,然后再根據(jù)索引值,將包含新鍵值對的哈希表節(jié)點放到哈希表數(shù)組的指定索引上面。
reHash 過程
? ? ? ? 在哈希表中有個負(fù)載因子(load factor)來控制哈希表保存的鍵值對數(shù)量。而這就需要rehash(重新散列)操作來完成。其中,負(fù)載因子的計算公式為:
//?負(fù)載因子?=?哈希表已保存的節(jié)點數(shù)量?/?哈希表大小 load_factor?=?ht[0].used?/?ht[0].size
哈希表擴(kuò)展與收縮的條件如下:
- 服務(wù)器目前沒有在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的負(fù)載因子大于等于1;
- 服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的負(fù)載因子大于等于5;
上述的條件有一個滿足,就會執(zhí)行rehash的過程。
如果服務(wù)器正在執(zhí)行BGSAVE ?或者 BGREWRITEAOF時,Redis會創(chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程
rehash的過程大概分為三步:
-
給哈希表2分配更大的空間,例如是當(dāng)前哈希表1的兩倍;
-
把哈希表1中的數(shù)據(jù)重新映射并拷貝到哈希表2中;
-
釋放哈希表1的空間;
其中,第一步分配空間的大小是由當(dāng)前的rehash操作類型 以及 當(dāng)前哈希表的鍵值對數(shù)量決定的。
-
當(dāng)執(zhí)行的是擴(kuò)展操作,分配的空間大小 為第一個大于等于(哈希表的鍵值對數(shù)量 * 2) 的2^n 值;
假設(shè) 當(dāng)前的鍵值對數(shù)量為4,那么 4 * 2 = 8,因為8 剛好等于2^3,即剛好等于第一個等于2^n的值,所以擴(kuò)展空間就為 8;
-
如果執(zhí)行的是收縮操作,分配的空間大小 為第一個大于等于(哈希表的鍵值對數(shù)量 ) 的2^n 值;
漸進(jìn)式reHash
? ? ? ? 當(dāng)哈希表數(shù)量多時,如果一下子將數(shù)據(jù)都復(fù)制過去,那么就很有可能對服務(wù)器造成影響。所以Redis是分多次進(jìn)行rehash的,也就是漸進(jìn)式rehash。
? ? ? ? 簡單來說就是在第二步操作時,Redis仍然正常處理客戶端請求,每處理一個請求時,從哈希表1中的第一個索引位置開始,順帶著將這個索引位置上所有的entries元素拷貝到哈希表2中;等下一次請求時,再順帶拷貝下一個索引位置的entries。
? ? ? ? 這樣就很巧妙地將一次性大量拷貝的開銷,分?jǐn)偟蕉啻翁幚碚埱蟮倪^程中了,避免了耗時操作,保證了數(shù)據(jù)的快速訪問。
rehash時期間的哈希表操作
? ? ? ? 在進(jìn)行 漸進(jìn)式rehash操作時,字典的刪除、查找、更新等操作會在兩個哈希表中執(zhí)行。例如要在字典中查找一個鍵的話,會先去原表中進(jìn)行查詢,如果找不到就會去新表查詢。
? ? ? ? 而字典的添加操作一律只會保存在新表中。
更多編程相關(guān)知識,請訪問:Redis視頻教程!!