詳解Golang官方中的一致性哈希組件
背景
在分布式緩存中,我們需要通過一組緩存節(jié)點(diǎn)來提高我們的緩存容量。比如我們有3個Redis節(jié)點(diǎn):
最簡單的路由規(guī)則是我們計算`Key`的哈希值,然后取模計算目標(biāo)節(jié)點(diǎn),比如我們有5個Key,計算出以下哈希值及對應(yīng)的目標(biāo)節(jié)點(diǎn):
Key的哈希值 | 模3的余 | 目標(biāo)節(jié)點(diǎn) |
---|---|---|
10 | 1 | Redis1 |
4 | 1 | Redis1 |
6 | 0 | Redis0 |
8 | 2 | Redis2 |
15 | 0 | Redis0 |
如果我們這時候加入一個新的Redis節(jié)點(diǎn),這時候路由變化如下:
Key的哈希值 | 模3的余 | 目標(biāo)節(jié)點(diǎn)(舊) | 模4的余 | 目標(biāo)節(jié)點(diǎn)(新) | 是否變化 |
---|---|---|---|---|---|
10 | 1 | Redis1 | 2 | Redis2 | 是 |
4 | 1 | Redis1 | 0 | Redis0 | 是 |
6 | 0 | Redis0 | 2 | Redis2 | 是 |
8 | 2 | Redis2 | 0 | Redis0 | 是 |
15 | 0 | Redis0 | 3 | Redis3 | 是 |
可以看到,我們只是加入了一個節(jié)點(diǎn),就導(dǎo)致了所有Key的目標(biāo)節(jié)點(diǎn)被改變了,這樣會導(dǎo)致大量緩存失效,這時請求可能就會都打到數(shù)據(jù)庫里,可能會導(dǎo)致數(shù)據(jù)庫被擊垮,這也就是緩存雪崩問題。
為了解決這個問題,一般我們會使用一致性哈希:
一致性哈希算法
一致性哈希算法經(jīng)常被用于請求路由中,在處理節(jié)點(diǎn)不變的情況下,它能夠把相同的請求路由到相同的處理節(jié)點(diǎn)上。同時還能在處理節(jié)點(diǎn)變動時,讓相同請求盡可能的打到原先相同的處理節(jié)點(diǎn)上。
原理
一致性哈希的原理是把處理節(jié)點(diǎn)通過哈希映射到一個哈希環(huán)上,哈希環(huán)可以理解為一個連續(xù)編號的循環(huán)鏈表,一般會使用長度為32位的哈希值,也就是哈希環(huán)可以映射2^32
個值。如下圖所示:
圖中有三個Redis節(jié)點(diǎn),通過哈希映射到環(huán)上的某個位置。Key也是通過哈希映射到環(huán)上的某個位置,然后向前尋找計算節(jié)點(diǎn),第一個遇到的就是Key的目標(biāo)節(jié)點(diǎn)。
這時候如果我們加入一個新的Redis3節(jié)點(diǎn),可以看到只有Key4的路由改變了,其他的Key的路由都保持不變:
也就是我們新加入的處理節(jié)點(diǎn),只會影響前面的處理節(jié)點(diǎn)的路由。
改進(jìn)
可以看到上面的Redis節(jié)點(diǎn)在環(huán)上分布得并不均勻,這樣會導(dǎo)致每個節(jié)點(diǎn)的負(fù)載差距過大。為了讓Redis節(jié)點(diǎn)在環(huán)上分布得更加均勻,我們還可以再加入虛擬節(jié)點(diǎn)。讓一個Redis節(jié)點(diǎn)能夠映射到哈希環(huán)上的多個位置,這樣節(jié)點(diǎn)的分布會更加均勻。
可以看到因?yàn)槊總€Redis節(jié)點(diǎn)的映射位置變多了,因此更有可能會分布得更加均勻。圖里每個Redis節(jié)點(diǎn)只有兩個虛擬節(jié)點(diǎn),主要是不太好畫,實(shí)際上我們可能會給每個Redis節(jié)點(diǎn)分配幾十個虛擬節(jié)點(diǎn),這樣基本上就很均勻了。
實(shí)現(xiàn)方式
Golang官方的groupcache
庫是一個嵌入式的分布式緩存庫,它里面有一個一致性哈希的實(shí)現(xiàn):https://github.com/golang/groupcache/blob/master/consistenthash/consistenthash_test.go
下面的代碼對這個實(shí)現(xiàn)有一些修改。
結(jié)構(gòu)和接口
第一件需要做的事情,就是我們需要把節(jié)點(diǎn)進(jìn)行哈希得到一個整數(shù)值,這里默認(rèn)是使用crc32
計算一個字節(jié)序列的哈希值,當(dāng)然也可以自己指定。
哈希環(huán)的結(jié)構(gòu)里面有一個ring數(shù)組
,我們使用這個數(shù)組模擬一個哈希環(huán),當(dāng)然數(shù)組并不會把最后一個元素鏈接到第一個元素,因此我們需要在邏輯上模擬。里面的nodes
則是保存了哈希值到真實(shí)節(jié)點(diǎn)字符串的映射,這樣我們在ring數(shù)組
里面找到對應(yīng)的哈希值時才能反過來找到真實(shí)節(jié)點(diǎn)。
// 哈希函數(shù) type Hash func(data []byte) uint32 // 哈希環(huán) // 注意,非線程安全,業(yè)務(wù)需要自行加鎖 type HashRing struct { hash Hash // 每個真實(shí)節(jié)點(diǎn)的虛擬節(jié)點(diǎn)數(shù)量 replicas int // 哈希環(huán),按照節(jié)點(diǎn)哈希值排序 ring []int // 節(jié)點(diǎn)哈希值到真實(shí)節(jié)點(diǎn)字符串,哈希映射的逆過程 nodes map[int]string }
添加節(jié)點(diǎn)
可以看到這個方法是把節(jié)點(diǎn)添加到哈希環(huán)里面,這里會為每個節(jié)點(diǎn)創(chuàng)建虛擬節(jié)點(diǎn),這樣可以分布的更加均勻。
當(dāng)然這個方法存在一個問題,就是它沒有判斷加入的節(jié)點(diǎn)是否已經(jīng)存在,這樣可能會導(dǎo)致Ring上面存在相同的節(jié)點(diǎn)。
// 添加新節(jié)點(diǎn)到哈希環(huán) // 注意,如果加入的節(jié)點(diǎn)已經(jīng)存在,會導(dǎo)致哈希環(huán)上面重復(fù),如果不確定是否存在請使用Reset func (m *HashRing) Add(nodes ...string) { for _, node := range nodes { // 每個節(jié)點(diǎn)創(chuàng)建多個虛擬節(jié)點(diǎn) for i := 0; i < m.replicas; i++ { // 每個虛擬節(jié)點(diǎn)計算哈希值 hash := int(m.hash([]byte(strconv.Itoa(i) + node))) // 加入哈希環(huán) m.ring = append(m.ring, hash) // 哈希值到真實(shí)節(jié)點(diǎn)字符串映射 m.nodes[hash] = node } } // 哈希環(huán)排序 sort.Ints(m.ring) }
重置節(jié)點(diǎn)
為了解決上面的問題,我們額外實(shí)現(xiàn)了一個重置方法,也就是先清空哈希環(huán),再添加。當(dāng)然這樣就必須每次都指定完整的節(jié)點(diǎn)列表。
// 先清空哈希環(huán)再設(shè)置 func (r *HashRing) Reset(nodes ...string) { // 先清空 r.ring = nil r.nodes = map[int]string{} // 再重置 r.Add(nodes...) }
獲取Key對應(yīng)的節(jié)點(diǎn)
這個方法的功能是查詢Key應(yīng)該路由到哪個節(jié)點(diǎn),也就是計算Key的哈希值,然后找到哈希值對應(yīng)的處理節(jié)點(diǎn)(這里需要考慮ring數(shù)組邏輯上是一個環(huán)),然后再根據(jù)這個哈希值去尋找真實(shí)處理節(jié)點(diǎn)的字符串。
// 獲取Key對應(yīng)的節(jié)點(diǎn) func (r *HashRing) Get(key string) string { // 如果哈希環(huán)位空,則直接返回 if r.Empty() { return "" } // 計算Key哈希值 hash := int(r.hash([]byte(key))) // 二分查找第一個大于等于Key哈希值的節(jié)點(diǎn) idx := sort.Search(len(r.ring), func(i int) bool { return r.ring[i] >= hash }) // 這里是特殊情況,也就是數(shù)組沒有大于等于Key哈希值的節(jié)點(diǎn) // 但是邏輯上這是一個環(huán),因此第一個節(jié)點(diǎn)就是目標(biāo)節(jié)點(diǎn) if idx == len(r.ring) { idx = 0 } // 返回哈希值對應(yīng)的真實(shí)節(jié)點(diǎn)字符串 return r.nodes[r.ring[idx]] }
總結(jié)
這個一致性哈希的實(shí)現(xiàn)非常簡單,功能上也非常簡單(官方的實(shí)現(xiàn)甚至沒有Reset()方法),可以通過這個實(shí)現(xiàn)理解一致性哈希的原理。也可以直接在業(yè)務(wù)中使用它,如果功能不夠再根據(jù)需求進(jìn)行擴(kuò)展。
上面代碼地址:https://github.com/jiaxwu/gommon/blob/main/consistenthash/consistenthash.go
到此這篇關(guān)于詳解Golang官方中的一致性哈希組件的文章就介紹到這了,更多相關(guān)Golang一致性哈希內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Golang中omitempty關(guān)鍵字的具體實(shí)現(xiàn)
本文主要介紹了Golang中omitempty關(guān)鍵字的具體實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-01-01Go語言學(xué)習(xí)之new函數(shù)的用法詳解
這篇文章主要為大家詳細(xì)介紹了Go語言中new()函數(shù)的相關(guān)知識以及具體用法,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價值,感興趣的小伙伴可以了解一下2023-05-05