編碼屬性 | 描述 | object encoding命令返回值 |
---|---|---|
OBJ_ENCODING_ZIPLIST | 使用壓縮列表實現(xiàn)哈希對象 | ziplist |
OBJ_ENCODING_HT | 使用字典實現(xiàn)哈希對象 | 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;
當(dāng)我們創(chuàng)建一個哈希對象時,可以得到如下簡圖(部分屬性被省略):
dict
中定義了一個數(shù)組 ht[2]
,ht[2]
中定義了兩個哈希表:ht[0]
和 ht[1]
。而 Redis
在默認情況下只會使用 ht[0]
,并不會使用 ht[1]
,也不會為 ht[1]
初始化分配空間。
當(dāng)設(shè)置一個哈希對象時,具體會落到哈希數(shù)組(上圖中的 dictEntry[3]
)中的哪個下標,是通過計算哈希值來確定的。如果發(fā)生哈希碰撞(計算得到的哈希值一致),那么同一個下標就會有多個 dictEntry
,從而形成一個鏈表(上圖中最右邊指向 NULL
的位置),不過需要注意的是最后插入元素的總是落在鏈表的最前面(即發(fā)生哈希沖突時,總是將節(jié)點往鏈表的頭部放)。
當(dāng)讀取數(shù)據(jù)的時候遇到一個節(jié)點有多個元素,就需要遍歷鏈表,故鏈表越長,性能越差。為了保證哈希表的性能,需要在滿足以下兩個條件中的一個時,對哈希表進行 rehash
(重新散列)操作:
負載因子大于等于 1
且 dict_can_resize
為 1
時。負載因子大于等于安全閾值(dict_force_resize_ratio=5
)時。
PS:負載因子 = 哈希表已使用節(jié)點數(shù) / 哈希表大小(即:h[0].used/h[0].size
)。
擴展哈希和收縮哈希都是通過執(zhí)行 rehash
來完成,這其中就涉及到了空間的分配和釋放,主要經(jīng)過以下五步:
為字典 dict
的 ht[1]
哈希表分配空間,其大小取決于當(dāng)前哈希表已保存節(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
。
當(dāng) ht[0]
中所有的鍵值對都遷移到 ht[1]
之后,釋放 ht[0]
,并將 ht[1]
修改為 ht[0]
,然后再創(chuàng)建一個新的 ht[1]
數(shù)組,為下一次 rehash
做準備。
將字典中的屬性 rehashix
設(shè)置為 -1
,表示此次 rehash
操作結(jié)束,等待下一次 rehash
。
Redis
中的這種重新哈希的操作因為不是一次性全部 rehash
,而是分多次來慢慢的將 ht[0]
中的鍵值對 rehash
到 ht[1]
,故而這種操作也稱之為漸進式 rehash
。漸進式 rehash
可以避免集中式 rehash
帶來的龐大計算量,是一種分而治之的思想。
在漸進式 rehash
過程中,因為還可能會有新的鍵值對存進來,此時** Redis
的做法是新添加的鍵值對統(tǒng)一放入 ht[1]
中,這樣就確保了 ht[0]
鍵值對的數(shù)量只會減少**。
當(dāng)正在執(zhí)行 rehash
操作時,如果服務(wù)器收到來自客戶端的命令請求操作,則會先查詢 ht[0]
,查找不到結(jié)果再到ht[1]
中查詢。
關(guān)于 ziplist
的一些特性,之前的文章中有單獨進行過分析,想要詳細了解的,可以點擊這里。但是需要注意的是哈希對象中的 ziplist
和列表對象中 ziplist
的有一點不同就是哈希對象是一個 key-value
形式,所以其 ziplist
中也表現(xiàn)為 key-value
,key
和 value
緊挨在一起:
當(dāng)一個哈希對象可以滿足以下兩個條件中的任意一個,哈希對象會選擇使用 ziplist
編碼來進行存儲:
64
字節(jié)(這個閾值可以通過參數(shù) hash-max-ziplist-value
來進行控制)。512
個(這個閾值可以通過參數(shù) hash-max-ziplist-entries
來進行控制)。一旦不滿足這兩個條件中的任意一個,哈希對象就會選擇使用 hashtable
編碼進行存儲。
field
(哈希對象的 key
值)。field
(哈希對象的 key
值)。key
中域 field
的值設(shè)置為 value
,如果 field
已存在,則不執(zhí)行任何操作。key
中的域 field
對應(yīng)的 value
。key
中的多個域 field
對應(yīng)的 value
。key
中的一個或者多個 field
。key
中的域 field
的值加上增量 increment
,increment
可以為負數(shù),如果 field
不是數(shù)字則會報錯。key
中的域 field
的值加上增量 increment
,increment
可以為負數(shù),如果 field
不是 float
類型則會報錯。key
中的所有域。了解了操作哈希對象的常用命令,我們就可以來驗證下前面提到的哈希對象的類型和編碼了,在測試之前為了防止其他 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
,最后再輸入如下命令進行測試:
hmset key field1 value1 field2 value2 field3 value3 object encoding key
輸出之后得到如下結(jié)果:
可以看到,編碼已經(jīng)變成了 hashtable
。
本文主要介紹了 Redis
中 5
種常用數(shù)據(jù)類型中的哈希類型底層的存儲結(jié)構(gòu) hashtable
的使用,以及當(dāng) hash
分布不均勻時候 Redis
是如何進行重新哈希的問題,最后了解了哈希對象的一些常用命令,并通過一些例子驗證了本文的結(jié)論。
到此這篇關(guān)于Redis中哈希分布不均勻的解決辦法的文章就介紹到這了,更多相關(guān)Redis 哈希分布不均勻內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!