Redis中哈希分布不均勻該怎么辦
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號”
優(yōu)質(zhì)文章，第一時間送達(dá)
? 作者?|? 雙子孤狼
來源 |? urlify.cn/iqiA3m
76套java從入門到精通實(shí)戰(zhàn)課程分享
前言
Redis?是一個鍵值對數(shù)據(jù)庫，其鍵是通過哈希進(jìn)行存儲的。整個?Redis?可以認(rèn)為是一個外層哈希，之所以稱為外層哈希，是因?yàn)?Redis?內(nèi)部也提供了一種哈希類型，這個可以稱之為內(nèi)部哈希。當(dāng)我們采用哈希對象進(jìn)行數(shù)據(jù)存儲時，對整個?Redis?而言，就經(jīng)過了兩層哈希存儲。
哈希對象
哈希對象本身也是一個?key-value?存儲結(jié)構(gòu)，底層的存儲結(jié)構(gòu)也可以分為兩種：ziplist（壓縮列表） 和?hashtable（哈希表）。這兩種存儲結(jié)構(gòu)也是通過編碼來進(jìn)行區(qū)分：
| 編碼屬性 | 描述 | object encoding命令返回值 |
|---|---|---|
| OBJ_ENCODING_ZIPLIST | 使用壓縮列表實(shí)現(xiàn)哈希對象 | ziplist |
| OBJ_ENCODING_HT | 使用字典實(shí)現(xiàn)哈希對象 | hashtable |
hashtable
Redis?中的?key-value?是通過?dictEntry?對象進(jìn)行包裝的，而哈希表就是將?dictEntry?對象又進(jìn)行了再一次的包裝得到的，這就是哈希表對象?dictht：
typedef?struct?dictht?{
????dictEntry?**table;//哈希表數(shù)組
????unsigned?long?size;//哈希表大小
????unsigned?long?sizemask;//掩碼大小，用于計算索引值，總是等于size-1
????unsigned?long?used;//哈希表中的已有節(jié)點(diǎn)數(shù)
}?dictht;
注意：上面結(jié)構(gòu)定義中的?table?是一個數(shù)組，其每個元素都是一個?dictEntry?對象。
字典
字典，又稱為符號表（symbol table），關(guān)聯(lián)數(shù)組（associative array）或者映射（map），字典的內(nèi)部嵌套了哈希表?dictht?對象，下面就是一個字典?ht?的定義：
typedef?struct?dict?{
????dictType?*type;//字典類型的一些特定函數(shù)
????void?*privdata;//私有數(shù)據(jù)，type中的特定函數(shù)可能需要用到
????dictht?ht[2];//哈希表(注意這里有2個哈希表)
????long?rehashidx;?//rehash索引，不在rehash時，值為-1
????unsigned?long?iterators;?//正在使用的迭代器數(shù)量
}?dict;
其中?dictType?內(nèi)部定義了一些常用函數(shù)，其數(shù)據(jù)結(jié)構(gòu)定義如下：
typedef?struct?dictType?{
????uint64_t?(*hashFunction)(const?void?*key);//計算哈希值函數(shù)
????void?*(*keyDup)(void?*privdata,?const?void?*key);//復(fù)制鍵函數(shù)
????void?*(*valDup)(void?*privdata,?const?void?*obj);//復(fù)制值函數(shù)
????int?(*keyCompare)(void?*privdata,?const?void?*key1,?const?void?*key2);//對比鍵函數(shù)
????void?(*keyDestructor)(void?*privdata,?void?*key);//銷毀鍵函數(shù)
????void?(*valDestructor)(void?*privdata,?void?*obj);//銷毀值函數(shù)
}?dictType;
當(dāng)我們創(chuàng)建一個哈希對象時，可以得到如下簡圖（部分屬性被省略）：
rehash 操作
dict?中定義了一個數(shù)組?ht[2]，ht[2]?中定義了兩個哈希表：ht[0]?和?ht[1]。而?Redis?在默認(rèn)情況下只會使用?ht[0]，并不會使用?ht[1]，也不會為?ht[1]?初始化分配空間。
當(dāng)設(shè)置一個哈希對象時，具體會落到哈希數(shù)組（上圖中的?dictEntry[3]）中的哪個下標(biāo)，是通過計算哈希值來確定的。如果發(fā)生哈希碰撞（計算得到的哈希值一致），那么同一個下標(biāo)就會有多個?dictEntry，從而形成一個鏈表（上圖中最右邊指向?NULL的位置），不過需要注意的是最后插入元素的總是落在鏈表的最前面（即發(fā)生哈希沖突時，總是將節(jié)點(diǎn)往鏈表的頭部放）。
當(dāng)讀取數(shù)據(jù)的時候遇到一個節(jié)點(diǎn)有多個元素，就需要遍歷鏈表，故鏈表越長，性能越差。為了保證哈希表的性能，需要在滿足以下兩個條件中的一個時，對哈希表進(jìn)行?rehash（重新散列）操作：
負(fù)載因子大于等于?
1?且?dict_can_resize?為?1?時。負(fù)載因子大于等于安全閾值（
dict_force_resize_ratio=5）時。
PS：負(fù)載因子 = 哈希表已使用節(jié)點(diǎn)數(shù) / 哈希表大小（即：h[0].used/h[0].size）。
rehash 步驟
擴(kuò)展哈希和收縮哈希都是通過執(zhí)行?rehash?來完成，這其中就涉及到了空間的分配和釋放，主要經(jīng)過以下五步：
為字典?
dict?的?ht[1]?哈希表分配空間，其大小取決于當(dāng)前哈希表已保存節(jié)點(diǎn)數(shù)（即：ht[0].used）：如果是擴(kuò)展操作則?
ht[1]?的大小為?2 的n次方中第一個大于等于ht[0].used * 2屬性的值（比如used=3，此時ht[0].used * 2=6，故2的3次方為8就是第一個大于used * 2的值（2 的 2 次方 < 6 且 2 的 3 次方 > 6））。如果是收縮操作則?
ht[1]?大小為 2 的 n 次方中第一個大于等于?ht[0].used?的值。將字典中的屬性?
rehashix?的值設(shè)置為?0，表示正在執(zhí)行?rehash?操作。將?
ht[0]?中所有的鍵值對依次重新計算哈希值，并放到?ht[1]?數(shù)組對應(yīng)位置，每完成一個鍵值對的?rehash之后?rehashix?的值需要自增?1。當(dāng)?
ht[0]?中所有的鍵值對都遷移到?ht[1]?之后，釋放?ht[0]?，并將?ht[1]?修改為?ht[0]，然后再創(chuàng)建一個新的?ht[1]?數(shù)組，為下一次?rehash?做準(zhǔn)備。將字典中的屬性?
rehashix?設(shè)置為?-1，表示此次?rehash?操作結(jié)束，等待下一次?rehash。
漸進(jìn)式 rehash
Redis?中的這種重新哈希的操作因?yàn)椴皇且淮涡匀?rehash，而是分多次來慢慢的將?ht[0]?中的鍵值對?rehash?到?ht[1]，故而這種操作也稱之為漸進(jìn)式?rehash。漸進(jìn)式?rehash?可以避免集中式?rehash?帶來的龐大計算量，是一種分而治之的思想。
在漸進(jìn)式?rehash?過程中，因?yàn)檫€可能會有新的鍵值對存進(jìn)來，此時**?Redis?的做法是新添加的鍵值對統(tǒng)一放入?ht[1]中，這樣就確保了?ht[0]?鍵值對的數(shù)量只會減少**。
當(dāng)正在執(zhí)行?rehash操作時，如果服務(wù)器收到來自客戶端的命令請求操作，則會先查詢?ht[0]，查找不到結(jié)果再到ht[1]?中查詢。
ziplist
關(guān)于?ziplist?的一些特性，之前的文章中有單獨(dú)進(jìn)行過分析，想要詳細(xì)了解的，可以點(diǎn)擊這里。但是需要注意的是哈希對象中的?ziplist?和列表對象中?ziplist?的有一點(diǎn)不同就是哈希對象是一個?key-value?形式，所以其?ziplist?中也表現(xiàn)為?key-value，key?和?value?緊挨在一起：
ziplist 和 hashtable 的編碼轉(zhuǎn)換
當(dāng)一個哈希對象可以滿足以下兩個條件中的任意一個，哈希對象會選擇使用?ziplist?編碼來進(jìn)行存儲：
哈希對象中的所有鍵值對總長度（包括鍵和值）小于等于?
64字節(jié)（這個閾值可以通過參數(shù)?hash-max-ziplist-value?來進(jìn)行控制）。哈希對象中的鍵值對數(shù)量小于等于?
512?個（這個閾值可以通過參數(shù)?hash-max-ziplist-entries?來進(jìn)行控制）。
一旦不滿足這兩個條件中的任意一個，哈希對象就會選擇使用?hashtable?編碼進(jìn)行存儲。
哈希對象常用命令
hset key field value：設(shè)置單個?
field（哈希對象的?key?值）。hmset key field1 value1 field2 value2 ：設(shè)置多個?
field（哈希對象的?key?值）。hsetnx key field value：將哈希表?
key?中域?field?的值設(shè)置為?value，如果?field?已存在，則不執(zhí)行任何操作。hget key field：獲取哈希表?
key?中的域?field?對應(yīng)的?value。hmget key field1 field2：獲取哈希表?
key?中的多個域?field?對應(yīng)的?value。hdel key field1 field2：刪除哈希表?
key?中的一個或者多個?field。hlen key：返回哈希表key中域的數(shù)量。
hincrby key field increment：為哈希表?
key?中的域?field?的值加上增量?increment?，increment?可以為負(fù)數(shù)，如果?field?不是數(shù)字則會報錯。hincrbyfloat key field increment：為哈希表?
key?中的域?field?的值加上增量?increment，increment?可以為負(fù)數(shù)，如果?field?不是?float?類型則會報錯。hkeys key：獲取哈希表?
key?中的所有域。hvals key：獲取哈希表中所有域的值。
了解了操作哈希對象的常用命令，我們就可以來驗(yàn)證下前面提到的哈希對象的類型和編碼了，在測試之前為了防止其他?key?值的干擾，我們先執(zhí)行?flushall?命令清空?Redis?數(shù)據(jù)庫。
然后依次執(zhí)行如下命令：
hset?address?country?china
type?address
object?encoding?address
得到如下效果：
可以看到當(dāng)我們的哈希對象中只有一個鍵值對的時候，底層編碼是?ziplist。
現(xiàn)在我們將?hash-max-ziplist-entries?參數(shù)改成?2，然后重啟?Redis，最后再輸入如下命令進(jìn)行測試：
hmset?key?field1?value1?field2?value2?field3?value3
object?encoding?key
輸出之后得到如下結(jié)果：
可以看到，編碼已經(jīng)變成了?hashtable。
總結(jié)
本文主要介紹了?Redis?中?5?種常用數(shù)據(jù)類型中的哈希類型底層的存儲結(jié)構(gòu)?hashtable?的使用，以及當(dāng)?hash?分布不均勻時候?Redis?是如何進(jìn)行重新哈希的問題，最后了解了哈希對象的一些常用命令，并通過一些例子驗(yàn)證了本文的結(jié)論。
粉絲福利：Java從入門到入土學(xué)習(xí)路線圖
??????
??長按上方微信二維碼?2 秒
感謝點(diǎn)贊支持下哈?