Redis中哈希分佈不均勻的解決辦法
Redis
是一個鍵值對數據庫,其鍵是通過哈希進行存儲的。整個 Redis
可以認為是一個外層哈希,之所以稱為外層哈希,是因為 Redis
內部也提供瞭一種哈希類型,這個可以稱之為內部哈希。當我們采用哈希對象進行數據存儲時,對整個 Redis
而言,就經過瞭兩層哈希存儲。
哈希對象
哈希對象本身也是一個 key-value
存儲結構,底層的存儲結構也可以分為兩種:ziplist
(壓縮列表) 和 hashtable
(哈希表)。這兩種存儲結構也是通過編碼來進行區分:
編碼屬性 | 描述 | object encoding命令返回值 |
---|---|---|
OBJ_ENCODING_ZIPLIST | 使用壓縮列表實現哈希對象 | ziplist |
OBJ_ENCODING_HT | 使用字典實現哈希對象 | hashtable |
hashtable
Redis
中的 key-value
是通過 dictEntry
對象進行包裝的,而哈希表就是將 dictEntry
對象又進行瞭再一次的包裝得到的,這就是哈希表對象 dictht
:
typedef struct dictht { dictEntry **table;//哈希表數組 unsigned long size;//哈希表大小 unsigned long sizemask;//掩碼大小,用於計算索引值,總是等於size-1 unsigned long used;//哈希表中的已有節點數 } dictht;
註意:上面結構定義中的 table
是一個數組,其每個元素都是一個 dictEntry
對象。
字典
字典,又稱為符號表(symbol table),關聯數組(associative array)或者映射(map),字典的內部嵌套瞭哈希表 dictht
對象,下面就是一個字典 ht
的定義:
typedef struct dict { dictType *type;//字典類型的一些特定函數 void *privdata;//私有數據,type中的特定函數可能需要用到 dictht ht[2];//哈希表(註意這裡有2個哈希表) long rehashidx; //rehash索引,不在rehash時,值為-1 unsigned long iterators; //正在使用的迭代器數量 } dict;
其中 dictType
內部定義瞭一些常用函數,其數據結構定義如下:
typedef struct dictType { uint64_t (*hashFunction)(const void *key);//計算哈希值函數 void *(*keyDup)(void *privdata, const void *key);//復制鍵函數 void *(*valDup)(void *privdata, const void *obj);//復制值函數 int (*keyCompare)(void *privdata, const void *key1, const void *key2);//對比鍵函數 void (*keyDestructor)(void *privdata, void *key);//銷毀鍵函數 void (*valDestructor)(void *privdata, void *obj);//銷毀值函數 } dictType;
當我們創建一個哈希對象時,可以得到如下簡圖(部分屬性被省略):
rehash 操作
dict
中定義瞭一個數組 ht[2]
,ht[2]
中定義瞭兩個哈希表:ht[0]
和 ht[1]
。而 Redis
在默認情況下隻會使用 ht[0]
,並不會使用 ht[1]
,也不會為 ht[1]
初始化分配空間。
當設置一個哈希對象時,具體會落到哈希數組(上圖中的 dictEntry[3]
)中的哪個下標,是通過計算哈希值來確定的。如果發生哈希碰撞(計算得到的哈希值一致),那麼同一個下標就會有多個 dictEntry
,從而形成一個鏈表(上圖中最右邊指向 NULL
的位置),不過需要註意的是最後插入元素的總是落在鏈表的最前面(即發生哈希沖突時,總是將節點往鏈表的頭部放)。
當讀取數據的時候遇到一個節點有多個元素,就需要遍歷鏈表,故鏈表越長,性能越差。為瞭保證哈希表的性能,需要在滿足以下兩個條件中的一個時,對哈希表進行 rehash
(重新散列)操作:
負載因子大於等於 1
且 dict_can_resize
為 1
時。負載因子大於等於安全閾值(dict_force_resize_ratio=5
)時。
PS:負載因子 = 哈希表已使用節點數 / 哈希表大小(即:h[0].used/h[0].size
)。
rehash 步驟
擴展哈希和收縮哈希都是通過執行 rehash
來完成,這其中就涉及到瞭空間的分配和釋放,主要經過以下五步:
為字典 dict
的 ht[1]
哈希表分配空間,其大小取決於當前哈希表已保存節點數(即: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
的值設置為 0
,表示正在執行 rehash
操作。
將 ht[0]
中所有的鍵值對依次重新計算哈希值,並放到 ht[1]
數組對應位置,每完成一個鍵值對的 rehash
之後 rehashix
的值需要自增 1
。
當 ht[0]
中所有的鍵值對都遷移到 ht[1]
之後,釋放 ht[0]
,並將 ht[1]
修改為 ht[0]
,然後再創建一個新的 ht[1]
數組,為下一次 rehash
做準備。
將字典中的屬性 rehashix
設置為 -1
,表示此次 rehash
操作結束,等待下一次 rehash
。
漸進式 rehash
Redis
中的這種重新哈希的操作因為不是一次性全部 rehash
,而是分多次來慢慢的將 ht[0]
中的鍵值對 rehash
到 ht[1]
,故而這種操作也稱之為漸進式 rehash
。漸進式 rehash
可以避免集中式 rehash
帶來的龐大計算量,是一種分而治之的思想。
在漸進式 rehash
過程中,因為還可能會有新的鍵值對存進來,此時** Redis
的做法是新添加的鍵值對統一放入 ht[1]
中,這樣就確保瞭 ht[0]
鍵值對的數量隻會減少**。
當正在執行 rehash
操作時,如果服務器收到來自客戶端的命令請求操作,則會先查詢 ht[0]
,查找不到結果再到ht[1]
中查詢。
ziplist
關於 ziplist
的一些特性,之前的文章中有單獨進行過分析,想要詳細瞭解的,可以點擊這裡。但是需要註意的是哈希對象中的 ziplist
和列表對象中 ziplist
的有一點不同就是哈希對象是一個 key-value
形式,所以其 ziplist
中也表現為 key-value
,key
和 value
緊挨在一起:
ziplist 和 hashtable 的編碼轉換
當一個哈希對象可以滿足以下兩個條件中的任意一個,哈希對象會選擇使用 ziplist
編碼來進行存儲:
- 哈希對象中的所有鍵值對總長度(包括鍵和值)小於等於
64
字節(這個閾值可以通過參數hash-max-ziplist-value
來進行控制)。 - 哈希對象中的鍵值對數量小於等於
512
個(這個閾值可以通過參數hash-max-ziplist-entries
來進行控制)。
一旦不滿足這兩個條件中的任意一個,哈希對象就會選擇使用 hashtable
編碼進行存儲。
哈希對象常用命令
- hset key field value:設置單個
field
(哈希對象的key
值)。 - hmset key field1 value1 field2 value2 :設置多個
field
(哈希對象的key
值)。 - hsetnx key field value:將哈希表
key
中域field
的值設置為value
,如果field
已存在,則不執行任何操作。 - hget key field:獲取哈希表
key
中的域field
對應的value
。 - hmget key field1 field2:獲取哈希表
key
中的多個域field
對應的value
。 - hdel key field1 field2:刪除哈希表
key
中的一個或者多個field
。 - hlen key:返回哈希表key中域的數量。
- hincrby key field increment:為哈希表
key
中的域field
的值加上增量increment
,increment
可以為負數,如果field
不是數字則會報錯。 - hincrbyfloat key field increment:為哈希表
key
中的域field
的值加上增量increment
,increment
可以為負數,如果field
不是float
類型則會報錯。 - hkeys key:獲取哈希表
key
中的所有域。 - hvals key:獲取哈希表中所有域的值。
瞭解瞭操作哈希對象的常用命令,我們就可以來驗證下前面提到的哈希對象的類型和編碼瞭,在測試之前為瞭防止其他 key
值的幹擾,我們先執行 flushall
命令清空 Redis
數據庫。
然後依次執行如下命令:
hset address country china type address object encoding address
得到如下效果:
可以看到當我們的哈希對象中隻有一個鍵值對的時候,底層編碼是 ziplist
。
現在我們將 hash-max-ziplist-entries
參數改成 2
,然後重啟 Redis
,最後再輸入如下命令進行測試:
hmset key field1 value1 field2 value2 field3 value3 object encoding key
輸出之後得到如下結果:
可以看到,編碼已經變成瞭 hashtable
。
總結
本文主要介紹瞭 Redis
中 5
種常用數據類型中的哈希類型底層的存儲結構 hashtable
的使用,以及當 hash
分佈不均勻時候 Redis
是如何進行重新哈希的問題,最後瞭解瞭哈希對象的一些常用命令,並通過一些例子驗證瞭本文的結論。
到此這篇關於Redis中哈希分佈不均勻的解決辦法的文章就介紹到這瞭,更多相關Redis 哈希分佈不均勻內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!