面試官：Redis中哈希分布不均勻該怎么辦

你知道的越多，不知道的就越多，業(yè)余的像一棵小草！

成功路上并不擁擠，因?yàn)閳?jiān)持的人不多。

編輯：業(yè)余草

zhouwenxing.github.io

推薦：https://www.xttblog.com/?p=5193

前言

Redis 是一個(gè)鍵值對(duì)數(shù)據(jù)庫，其鍵是通過哈希進(jìn)行存儲(chǔ)的。整個(gè) Redis 可以認(rèn)為是一個(gè)外層哈希，之所以稱為外層哈希，是因?yàn)?Redis 內(nèi)部也提供了一種哈希類型，這個(gè)可以稱之為內(nèi)部哈希。當(dāng)我們采用哈希對(duì)象進(jìn)行數(shù)據(jù)存儲(chǔ)時(shí)，對(duì)整個(gè) Redis 而言，就經(jīng)過了兩層哈希存儲(chǔ)。

哈希對(duì)象

哈希對(duì)象本身也是一個(gè) key-value 存儲(chǔ)結(jié)構(gòu)，底層的存儲(chǔ)結(jié)構(gòu)也可以分為兩種：ziplist（壓縮列表） 和 hashtable（哈希表）。這兩種存儲(chǔ)結(jié)構(gòu)也是通過編碼來進(jìn)行區(qū)分：

hashtable

Redis 中的 key-value 是通過 dictEntry 對(duì)象進(jìn)行包裝的，而哈希表就是將 dictEntry 對(duì)象又進(jìn)行了再一次的包裝得到的，這就是哈希表對(duì)象 dictht：

typedef struct dictht {
    dictEntry **table;//哈希表數(shù)組
    unsigned long size;//哈希表大小
    unsigned long sizemask;//掩碼大小，用于計(jì)算索引值，總是等于size-1
    unsigned long used;//哈希表中的已有節(jié)點(diǎn)數(shù)
} dictht;

注意：上面結(jié)構(gòu)定義中的 table 是一個(gè)數(shù)組，其每個(gè)元素都是一個(gè) dictEntry 對(duì)象。

字典

字典，又稱為符號(hào)表（symbol table），關(guān)聯(lián)數(shù)組（associative array）或者映射（map），字典的內(nèi)部嵌套了哈希表 dictht 對(duì)象，下面就是一個(gè)字典 ht 的定義：

typedef struct dict {
    dictType *type;//字典類型的一些特定函數(shù)
    void *privdata;//私有數(shù)據(jù)，type中的特定函數(shù)可能需要用到
    dictht ht[2];//哈希表(注意這里有2個(gè)哈希表)
    long rehashidx; //rehash索引，不在rehash時(shí)，值為-1
    unsigned long iterators; //正在使用的迭代器數(shù)量
} dict;

其中 dictType 內(nèi)部定義了一些常用函數(shù)，其數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);//計(jì)算哈希值函數(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);//對(duì)比鍵函數(shù)
    void (*keyDestructor)(void *privdata, void *key);//銷毀鍵函數(shù)
    void (*valDestructor)(void *privdata, void *obj);//銷毀值函數(shù)
} dictType;

當(dāng)我們創(chuàng)建一個(gè)哈希對(duì)象時(shí)，可以得到如下簡(jiǎn)圖（部分屬性被省略）：

rehash 操作

dict 中定義了一個(gè)數(shù)組 ht[2]，ht[2] 中定義了兩個(gè)哈希表：ht[0] 和 ht[1]。而 Redis 在默認(rèn)情況下只會(huì)使用 ht[0]，并不會(huì)使用 ht[1]，也不會(huì)為 ht[1] 初始化分配空間。

當(dāng)設(shè)置一個(gè)哈希對(duì)象時(shí)，具體會(huì)落到哈希數(shù)組（上圖中的 dictEntry[3]）中的哪個(gè)下標(biāo)，是通過計(jì)算哈希值來確定的。如果發(fā)生哈希碰撞（計(jì)算得到的哈希值一致），那么同一個(gè)下標(biāo)就會(huì)有多個(gè) dictEntry，從而形成一個(gè)鏈表（上圖中最右邊指向 NULL 的位置），不過需要注意的是最后插入元素的總是落在鏈表的最前面（即發(fā)生哈希沖突時(shí)，總是將節(jié)點(diǎn)往鏈表的頭部放）。

當(dāng)讀取數(shù)據(jù)的時(shí)候遇到一個(gè)節(jié)點(diǎn)有多個(gè)元素，就需要遍歷鏈表，故鏈表越長(zhǎng)，性能越差。為了保證哈希表的性能，需要在滿足以下兩個(gè)條件中的一個(gè)時(shí)，對(duì)哈希表進(jìn)行 rehash（重新散列）操作：

• 負(fù)載因子大于等于 1 且 dict_can_resize 為 1 時(shí)。
• 負(fù)載因子大于等于安全閾值（dict_force_resize_ratio=5）時(shí)。

PS：負(fù)載因子 = 哈希表已使用節(jié)點(diǎn)數(shù) / 哈希表大小（即：h[0].used/h[0].size）。

rehash 步驟

擴(kuò)展哈希和收縮哈希都是通過執(zhí)行 rehash 來完成，這其中就涉及到了空間的分配和釋放，主要經(jīng)過以下五步：

1. 為字典 dict 的 ht[1] 哈希表分配空間，其大小取決于當(dāng)前哈希表已保存節(jié)點(diǎn)數(shù)（即：ht[0].used）：

• 如果是擴(kuò)展操作則 ht[1] 的大小為 2 的 n 次方中第一個(gè)大于等于 ht[0].used * 2 屬性的值（比如 used=3，此時(shí)ht[0].used * 2=6，故 2 的 3 次方為 8 就是第一個(gè)大于 used * 2 的值（2 的 2 次方 < 6 且 2 的 3 次方 > 6））。`
• 如果是收縮操作則 ht[1] 大小為 2 的 n 次方中第一個(gè)大于等于 ht[0].used 的值。

2. 將字典中的屬性 rehashix 的值設(shè)置為 0，表示正在執(zhí)行 rehash 操作。

3. 將 ht[0] 中所有的鍵值對(duì)依次重新計(jì)算哈希值，并放到 ht[1] 數(shù)組對(duì)應(yīng)位置，每完成一個(gè)鍵值對(duì)的 rehash之后 rehashix 的值需要自增 1。

4. 當(dāng) ht[0] 中所有的鍵值對(duì)都遷移到 ht[1] 之后，釋放 ht[0] ，并將 ht[1] 修改為 ht[0]，然后再創(chuàng)建一個(gè)新的 ht[1] 數(shù)組，為下一次 rehash 做準(zhǔn)備。

5. 將字典中的屬性 rehashix 設(shè)置為 -1，表示此次 rehash 操作結(jié)束，等待下一次 rehash。

漸進(jìn)式 rehash

Redis 中的這種重新哈希的操作「因?yàn)椴皇且淮涡匀?rehash，而是分多次來慢慢的將 ht[0] 中的鍵值對(duì) rehash 到 ht[1]，故而這種操作也稱之為漸進(jìn)式 rehash」。漸進(jìn)式 rehash 可以避免集中式 rehash 帶來的龐大計(jì)算量，是一種分而治之的思想。

在漸進(jìn)式 rehash 過程中，因?yàn)檫€可能會(huì)有新的鍵值對(duì)存進(jìn)來，此時(shí)** Redis 的做法是新添加的鍵值對(duì)統(tǒng)一放入 ht[1] 中，這樣就確保了 ht[0] 鍵值對(duì)的數(shù)量只會(huì)減少**。

當(dāng)正在執(zhí)行 rehash操作時(shí)，如果服務(wù)器收到來自客戶端的命令請(qǐng)求操作，則「會(huì)先查詢 ht[0]，查找不到結(jié)果再到ht[1] 中查詢」。

ziplist

關(guān)于 ziplist 的一些特性，之前的文章中有單獨(dú)進(jìn)行過分析，想要詳細(xì)了解的，可以看這篇文章《從根上理解ziplist為什么要犧牲速度而進(jìn)行壓縮！》。但是需要注意的是哈希對(duì)象中的 ziplist 和列表對(duì)象中 ziplist 的有一點(diǎn)不同就是哈希對(duì)象是一個(gè) key-value 形式，所以其 ziplist 中也表現(xiàn)為 key-value，key 和 value 緊挨在一起：

ziplist 和 hashtable 的編碼轉(zhuǎn)換

當(dāng)一個(gè)哈希對(duì)象可以滿足以下兩個(gè)條件中的任意一個(gè)，哈希對(duì)象會(huì)選擇使用 ziplist 編碼來進(jìn)行存儲(chǔ)：

• 哈希對(duì)象中的所有鍵值對(duì)總長(zhǎng)度（包括鍵和值）小于等于 64字節(jié)（這個(gè)閾值可以通過參數(shù) hash-max-ziplist-value 來進(jìn)行控制）。
• 哈希對(duì)象中的鍵值對(duì)數(shù)量小于等于 512 個(gè)（這個(gè)閾值可以通過參數(shù) hash-max-ziplist-entries 來進(jìn)行控制）。

一旦不滿足這兩個(gè)條件中的任意一個(gè)，哈希對(duì)象就會(huì)選擇使用 hashtable 編碼進(jìn)行存儲(chǔ)。

哈希對(duì)象常用命令

• hset key field value：設(shè)置單個(gè) field（哈希對(duì)象的 key 值）。
• hmset key field1 value1 field2 value2 ：設(shè)置多個(gè) field（哈希對(duì)象的 key 值）。
• hsetnx key field value：將哈希表 key 中域 field 的值設(shè)置為 value，如果 field 已存在，則不執(zhí)行任何操作。
• hget key field：獲取哈希表 key 中的域 field 對(duì)應(yīng)的 value。
• hmget key field1 field2：獲取哈希表 key 中的多個(gè)域 field 對(duì)應(yīng)的 value。
• hdel key field1 field2：刪除哈希表 key 中的一個(gè)或者多個(gè) field。
• hlen key：返回哈希表key中域的數(shù)量。
• hincrby key field increment：為哈希表 key 中的域 field 的值加上增量 increment ，increment 可以為負(fù)數(shù)，如果 field 不是數(shù)字則會(huì)報(bào)錯(cuò)。
• hincrbyfloat key field increment：為哈希表 key 中的域 field 的值加上增量 increment，increment 可以為負(fù)數(shù)，如果 field 不是 float 類型則會(huì)報(bào)錯(cuò)。
• hkeys key：獲取哈希表 key 中的所有域。
• hvals key：獲取哈希表中所有域的值。

了解了操作哈希對(duì)象的常用命令，我們就可以來驗(yàn)證下前面提到的哈希對(duì)象的類型和編碼了，在測(cè)試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。

然后依次執(zhí)行如下命令：

hset address country china
type address
object encoding address

得到如下效果：

可以看到當(dāng)我們的哈希對(duì)象中只有一個(gè)鍵值對(duì)的時(shí)候，底層編碼是 ziplist。

現(xiàn)在我們將 hash-max-ziplist-entries 參數(shù)改成 2，然后重啟 Redis，最后再輸入如下命令進(jìn)行測(cè)試：

hmset key field1 value1 field2 value2 field3 value3
object encoding key

輸出之后得到如下結(jié)果：

可以看到，編碼已經(jīng)變成了 hashtable。

總結(jié)

本文主要介紹了 Redis 中 5 種常用數(shù)據(jù)類型中的哈希類型底層的存儲(chǔ)結(jié)構(gòu) hashtable 的使用，以及當(dāng) hash 分布不均勻時(shí)候 Redis 是如何進(jìn)行重新哈希的問題，最后了解了哈希對(duì)象的一些常用命令，并通過一些例子驗(yàn)證了本文的結(jié)論。