面試官：Redis中哈希分布不均勻該怎么辦
你知道的越多，不知道的就越多，業(yè)余的像一棵小草！
成功路上并不擁擠，因為堅持的人不多。
編輯：業(yè)余草
zhouwenxing.github.io
推薦：https://www.xttblog.com/?p=5193
前言
Redis 是一個鍵值對數(shù)據(jù)庫，其鍵是通過哈希進行存儲的。整個 Redis 可以認為是一個外層哈希，之所以稱為外層哈希，是因為 Redis 內(nèi)部也提供了一種哈希類型，這個可以稱之為內(nèi)部哈希。當我們采用哈希對象進行數(shù)據(jù)存儲時，對整個 Redis 而言，就經(jīng)過了兩層哈希存儲。
哈希對象
哈希對象本身也是一個 key-value 存儲結(jié)構(gòu)，底層的存儲結(jié)構(gòu)也可以分為兩種：ziplist（壓縮列表） 和 hashtable（哈希表）。這兩種存儲結(jié)構(gòu)也是通過編碼來進行區(qū)分：
hashtable
Redis 中的 key-value 是通過 dictEntry 對象進行包裝的，而哈希表就是將 dictEntry 對象又進行了再一次的包裝得到的，這就是哈希表對象 dictht：
typedef struct dictht {
dictEntry **table;//哈希表數(shù)組
unsigned long size;//哈希表大小
unsigned long sizemask;//掩碼大小，用于計算索引值，總是等于size-1
unsigned long used;//哈希表中的已有節(jié)點數(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;
當我們創(chuàng)建一個哈希對象時，可以得到如下簡圖（部分屬性被省略）：
rehash 操作
dict 中定義了一個數(shù)組 ht[2]，ht[2] 中定義了兩個哈希表：ht[0] 和 ht[1]。而 Redis 在默認情況下只會使用 ht[0]，并不會使用 ht[1]，也不會為 ht[1] 初始化分配空間。
當設(shè)置一個哈希對象時，具體會落到哈希數(shù)組（上圖中的 dictEntry[3]）中的哪個下標，是通過計算哈希值來確定的。如果發(fā)生哈希碰撞（計算得到的哈希值一致），那么同一個下標就會有多個 dictEntry，從而形成一個鏈表（上圖中最右邊指向 NULL 的位置），不過需要注意的是最后插入元素的總是落在鏈表的最前面（即發(fā)生哈希沖突時，總是將節(jié)點往鏈表的頭部放）。
當讀取數(shù)據(jù)的時候遇到一個節(jié)點有多個元素，就需要遍歷鏈表，故鏈表越長，性能越差。為了保證哈希表的性能，需要在滿足以下兩個條件中的一個時，對哈希表進行 rehash（重新散列）操作：
負載因子大于等于 1且dict_can_resize為1時。負載因子大于等于安全閾值（ dict_force_resize_ratio=5）時。
PS：負載因子 = 哈希表已使用節(jié)點數(shù) / 哈希表大小（即：h[0].used/h[0].size）。
rehash 步驟
擴展哈希和收縮哈希都是通過執(zhí)行 rehash 來完成，這其中就涉及到了空間的分配和釋放，主要經(jīng)過以下五步：
為字典
dict的ht[1]哈希表分配空間，其大小取決于當前哈希表已保存節(jié)點數(shù)（即：ht[0].used）：如果是擴展操作則 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。當
ht[0]中所有的鍵值對都遷移到ht[1]之后，釋放ht[0]，并將ht[1]修改為ht[0]，然后再創(chuàng)建一個新的ht[1]數(shù)組，為下一次rehash做準備。將字典中的屬性
rehashix設(shè)置為-1，表示此次rehash操作結(jié)束，等待下一次rehash。
漸進式 rehash
Redis 中的這種重新哈希的操作「因為不是一次性全部 rehash，而是分多次來慢慢的將 ht[0] 中的鍵值對 rehash 到 ht[1]，故而這種操作也稱之為漸進式 rehash」。漸進式 rehash 可以避免集中式 rehash 帶來的龐大計算量，是一種分而治之的思想。
在漸進式 rehash 過程中，因為還可能會有新的鍵值對存進來，此時** Redis 的做法是新添加的鍵值對統(tǒng)一放入 ht[1] 中，這樣就確保了 ht[0] 鍵值對的數(shù)量只會減少**。
當正在執(zhí)行 rehash操作時，如果服務(wù)器收到來自客戶端的命令請求操作，則「會先查詢 ht[0]，查找不到結(jié)果再到ht[1] 中查詢」。
ziplist
關(guān)于 ziplist 的一些特性，之前的文章中有單獨進行過分析，想要詳細了解的，可以看這篇文章《從根上理解ziplist為什么要犧牲速度而進行壓縮！》。但是需要注意的是哈希對象中的 ziplist 和列表對象中 ziplist 的有一點不同就是哈希對象是一個 key-value 形式，所以其 ziplist 中也表現(xiàn)為 key-value，key 和 value 緊挨在一起：
ziplist 和 hashtable 的編碼轉(zhuǎn)換
當一個哈希對象可以滿足以下兩個條件中的任意一個，哈希對象會選擇使用 ziplist 編碼來進行存儲：
哈希對象中的所有鍵值對總長度（包括鍵和值）小于等于 64字節(jié)（這個閾值可以通過參數(shù)hash-max-ziplist-value來進行控制）。哈希對象中的鍵值對數(shù)量小于等于 512個（這個閾值可以通過參數(shù)hash-max-ziplist-entries來進行控制）。
一旦不滿足這兩個條件中的任意一個，哈希對象就會選擇使用 hashtable 編碼進行存儲。
哈希對象常用命令
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可以為負數(shù)，如果field不是數(shù)字則會報錯。hincrbyfloat key field increment：為哈希表 key中的域field的值加上增量increment，increment可以為負數(shù)，如果field不是float類型則會報錯。hkeys key：獲取哈希表 key中的所有域。hvals key：獲取哈希表中所有域的值。
了解了操作哈希對象的常用命令，我們就可以來驗證下前面提到的哈希對象的類型和編碼了，在測試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。
然后依次執(zhí)行如下命令：
hset address country china
type address
object encoding address
得到如下效果：
可以看到當我們的哈希對象中只有一個鍵值對的時候，底層編碼是 ziplist。
現(xiàn)在我們將 hash-max-ziplist-entries 參數(shù)改成 2，然后重啟 Redis，最后再輸入如下命令進行測試：
hmset key field1 value1 field2 value2 field3 value3
object encoding key
輸出之后得到如下結(jié)果：
可以看到，編碼已經(jīng)變成了 hashtable。
總結(jié)
本文主要介紹了 Redis 中 5 種常用數(shù)據(jù)類型中的哈希類型底層的存儲結(jié)構(gòu) hashtable 的使用，以及當 hash 分布不均勻時候 Redis 是如何進行重新哈希的問題，最后了解了哈希對象的一些常用命令，并通過一些例子驗證了本文的結(jié)論。