背景

在分布式緩存中，我們需要通過一組緩存節(jié)點(diǎn)來提高我們的緩存容量。比如我們有3個(gè)Redis節(jié)點(diǎn)：

最簡(jiǎn)單的路由規(guī)則是我們計(jì)算`Key`的哈希值，然后取模計(jì)算目標(biāo)節(jié)點(diǎn)，比如我們有5個(gè)Key，計(jì)算出以下哈希值及對(duì)應(yīng)的目標(biāo)節(jié)點(diǎn)：

如果我們這時(shí)候加入一個(gè)新的Redis節(jié)點(diǎn)，這時(shí)候路由變化如下：

可以看到，我們只是加入了一個(gè)節(jié)點(diǎn)，就導(dǎo)致了所有Key的目標(biāo)節(jié)點(diǎn)被改變了，這樣會(huì)導(dǎo)致大量緩存失效，這時(shí)請(qǐng)求可能就會(huì)都打到數(shù)據(jù)庫里，可能會(huì)導(dǎo)致數(shù)據(jù)庫被擊垮，這也就是緩存雪崩問題。

為了解決這個(gè)問題，一般我們會(huì)使用一致性哈希：

一致性哈希算法

一致性哈希算法經(jīng)常被用于請(qǐng)求路由中，在處理節(jié)點(diǎn)不變的情況下，它能夠把相同的請(qǐng)求路由到相同的處理節(jié)點(diǎn)上。同時(shí)還能在處理節(jié)點(diǎn)變動(dòng)時(shí)，讓相同請(qǐng)求盡可能的打到原先相同的處理節(jié)點(diǎn)上。

原理

一致性哈希的原理是把處理節(jié)點(diǎn)通過哈希映射到一個(gè)哈希環(huán)上，哈希環(huán)可以理解為一個(gè)連續(xù)編號(hào)的循環(huán)鏈表，一般會(huì)使用長(zhǎng)度為32位的哈希值，也就是哈希環(huán)可以映射2^32個(gè)值。如下圖所示：

圖中有三個(gè)Redis節(jié)點(diǎn)，通過哈希映射到環(huán)上的某個(gè)位置。Key也是通過哈希映射到環(huán)上的某個(gè)位置，然后向前尋找計(jì)算節(jié)點(diǎn)，第一個(gè)遇到的就是Key的目標(biāo)節(jié)點(diǎn)。

這時(shí)候如果我們加入一個(gè)新的Redis3節(jié)點(diǎn)，可以看到只有Key4的路由改變了，其他的Key的路由都保持不變：

也就是我們新加入的處理節(jié)點(diǎn)，只會(huì)影響前面的處理節(jié)點(diǎn)的路由。

改進(jìn)

可以看到上面的Redis節(jié)點(diǎn)在環(huán)上分布得并不均勻，這樣會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)的負(fù)載差距過大。為了讓Redis節(jié)點(diǎn)在環(huán)上分布得更加均勻，我們還可以再加入虛擬節(jié)點(diǎn)。讓一個(gè)Redis節(jié)點(diǎn)能夠映射到哈希環(huán)上的多個(gè)位置，這樣節(jié)點(diǎn)的分布會(huì)更加均勻。

可以看到因?yàn)槊總€(gè)Redis節(jié)點(diǎn)的映射位置變多了，因此更有可能會(huì)分布得更加均勻。圖里每個(gè)Redis節(jié)點(diǎn)只有兩個(gè)虛擬節(jié)點(diǎn)，主要是不太好畫，實(shí)際上我們可能會(huì)給每個(gè)Redis節(jié)點(diǎn)分配幾十個(gè)虛擬節(jié)點(diǎn)，這樣基本上就很均勻了。

實(shí)現(xiàn)方式

Golang官方的groupcache庫是一個(gè)嵌入式的分布式緩存庫，它里面有一個(gè)一致性哈希的實(shí)現(xiàn)：https://github.com/golang/groupcache/blob/master/consistenthash/consistenthash_test.go

下面的代碼對(duì)這個(gè)實(shí)現(xiàn)有一些修改。

結(jié)構(gòu)和接口

第一件需要做的事情，就是我們需要把節(jié)點(diǎn)進(jìn)行哈希得到一個(gè)整數(shù)值，這里默認(rèn)是使用crc32計(jì)算一個(gè)字節(jié)序列的哈希值，當(dāng)然也可以自己指定。

哈希環(huán)的結(jié)構(gòu)里面有一個(gè)ring數(shù)組，我們使用這個(gè)數(shù)組模擬一個(gè)哈希環(huán)，當(dāng)然數(shù)組并不會(huì)把最后一個(gè)元素鏈接到第一個(gè)元素，因此我們需要在邏輯上模擬。里面的nodes則是保存了哈希值到真實(shí)節(jié)點(diǎn)字符串的映射，這樣我們?cè)?code>ring數(shù)組里面找到對(duì)應(yīng)的哈希值時(shí)才能反過來找到真實(shí)節(jié)點(diǎn)。

// 哈希函數(shù)
type Hash func(data []byte) uint32

// 哈希環(huán)
// 注意，非線程安全，業(yè)務(wù)需要自行加鎖
type HashRing struct {
	hash Hash
	// 每個(gè)真實(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)

可以看到這個(gè)方法是把節(jié)點(diǎn)添加到哈希環(huán)里面，這里會(huì)為每個(gè)節(jié)點(diǎn)創(chuàng)建虛擬節(jié)點(diǎn)，這樣可以分布的更加均勻。

當(dāng)然這個(gè)方法存在一個(gè)問題，就是它沒有判斷加入的節(jié)點(diǎn)是否已經(jīng)存在，這樣可能會(huì)導(dǎo)致Ring上面存在相同的節(jié)點(diǎn)。

// 添加新節(jié)點(diǎn)到哈希環(huán)
// 注意，如果加入的節(jié)點(diǎn)已經(jīng)存在，會(huì)導(dǎo)致哈希環(huán)上面重復(fù)，如果不確定是否存在請(qǐng)使用Reset
func (m *HashRing) Add(nodes ...string) {
	for _, node := range nodes {
		// 每個(gè)節(jié)點(diǎn)創(chuàng)建多個(gè)虛擬節(jié)點(diǎn)
		for i := 0; i < m.replicas; i++ {
			// 每個(gè)虛擬節(jié)點(diǎn)計(jì)算哈希值
			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)了一個(gè)重置方法，也就是先清空哈希環(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對(duì)應(yīng)的節(jié)點(diǎn)

這個(gè)方法的功能是查詢Key應(yīng)該路由到哪個(gè)節(jié)點(diǎn)，也就是計(jì)算Key的哈希值，然后找到哈希值對(duì)應(yīng)的處理節(jié)點(diǎn)（這里需要考慮ring數(shù)組邏輯上是一個(gè)環(huán)），然后再根據(jù)這個(gè)哈希值去尋找真實(shí)處理節(jié)點(diǎn)的字符串。

// 獲取Key對(duì)應(yīng)的節(jié)點(diǎn)
func (r *HashRing) Get(key string) string {
	// 如果哈希環(huán)位空，則直接返回
	if r.Empty() {
		return ""
	}

	// 計(jì)算Key哈希值
	hash := int(r.hash([]byte(key)))

	// 二分查找第一個(gè)大于等于Key哈希值的節(jié)點(diǎn)
	idx := sort.Search(len(r.ring), func(i int) bool { return r.ring[i] >= hash })

	// 這里是特殊情況，也就是數(shù)組沒有大于等于Key哈希值的節(jié)點(diǎn)
	// 但是邏輯上這是一個(gè)環(huán)，因此第一個(gè)節(jié)點(diǎn)就是目標(biāo)節(jié)點(diǎn)
	if idx == len(r.ring) {
		idx = 0
	}

	// 返回哈希值對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)字符串
	return r.nodes[r.ring[idx]]
}

總結(jié)

這個(gè)一致性哈希的實(shí)現(xiàn)非常簡(jiǎn)單，功能上也非常簡(jiǎn)單（官方的實(shí)現(xiàn)甚至沒有Reset()方法），可以通過這個(gè)實(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論