Golang官方中的一致性哈希組件怎么實現

這篇“Golang官方中的一致性哈希組件怎么實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Golang官方中的一致性哈希組件怎么實現”文章吧。

背景

在分布式緩存中，我們需要通過一組緩存節點來提高我們的緩存容量。比如我們有3個Redis節點：

最簡單的路由規則是我們計算`Key`的哈希值，然后取模計算目標節點，比如我們有5個Key，計算出以下哈希值及對應的目標節點：

如果我們這時候加入一個新的Redis節點，這時候路由變化如下：

可以看到，我們只是加入了一個節點，就導致了所有Key的目標節點被改變了，這樣會導致大量緩存失效，這時請求可能就會都打到數據庫里，可能會導致數據庫被擊垮，這也就是緩存雪崩問題。

為了解決這個問題，一般我們會使用一致性哈希：

一致性哈希算法

一致性哈希算法經常被用于請求路由中，在處理節點不變的情況下，它能夠把相同的請求路由到相同的處理節點上。同時還能在處理節點變動時，讓相同請求盡可能的打到原先相同的處理節點上。

原理

一致性哈希的原理是把處理節點通過哈希映射到一個哈希環上，哈希環可以理解為一個連續編號的循環鏈表，一般會使用長度為32位的哈希值，也就是哈希環可以映射2^32個值。如下圖所示：

圖中有三個Redis節點，通過哈希映射到環上的某個位置。Key也是通過哈希映射到環上的某個位置，然后向前尋找計算節點，第一個遇到的就是Key的目標節點。

這時候如果我們加入一個新的Redis3節點，可以看到只有Key4的路由改變了，其他的Key的路由都保持不變：

也就是我們新加入的處理節點，只會影響前面的處理節點的路由。

改進

可以看到上面的Redis節點在環上分布得并不均勻，這樣會導致每個節點的負載差距過大。為了讓Redis節點在環上分布得更加均勻，我們還可以再加入虛擬節點。讓一個Redis節點能夠映射到哈希環上的多個位置，這樣節點的分布會更加均勻。

可以看到因為每個Redis節點的映射位置變多了，因此更有可能會分布得更加均勻。圖里每個Redis節點只有兩個虛擬節點，主要是不太好畫，實際上我們可能會給每個Redis節點分配幾十個虛擬節點，這樣基本上就很均勻了。

實現方式

結構和接口

第一件需要做的事情，就是我們需要把節點進行哈希得到一個整數值，這里默認是使用crc32計算一個字節序列的哈希值，當然也可以自己指定。

哈希環的結構里面有一個ring數組，我們使用這個數組模擬一個哈希環，當然數組并不會把最后一個元素鏈接到第一個元素，因此我們需要在邏輯上模擬。里面的nodes則是保存了哈希值到真實節點字符串的映射，這樣我們在ring數組里面找到對應的哈希值時才能反過來找到真實節點。

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

// 哈希環
// 注意，非線程安全，業務需要自行加鎖
type HashRing struct {
	hash Hash
	// 每個真實節點的虛擬節點數量
	replicas int
	// 哈希環，按照節點哈希值排序
	ring []int
	// 節點哈希值到真實節點字符串，哈希映射的逆過程
	nodes map[int]string
}

添加節點

可以看到這個方法是把節點添加到哈希環里面，這里會為每個節點創建虛擬節點，這樣可以分布的更加均勻。

當然這個方法存在一個問題，就是它沒有判斷加入的節點是否已經存在，這樣可能會導致Ring上面存在相同的節點。

// 添加新節點到哈希環
// 注意，如果加入的節點已經存在，會導致哈希環上面重復，如果不確定是否存在請使用Reset
func (m *HashRing) Add(nodes ...string) {
	for _, node := range nodes {
		// 每個節點創建多個虛擬節點
		for i := 0; i < m.replicas; i++ {
			// 每個虛擬節點計算哈希值
			hash := int(m.hash([]byte(strconv.Itoa(i) + node)))
			// 加入哈希環
			m.ring = append(m.ring, hash)
			// 哈希值到真實節點字符串映射
			m.nodes[hash] = node
		}
	}
	// 哈希環排序
	sort.Ints(m.ring)
}

重置節點

為了解決上面的問題，我們額外實現了一個重置方法，也就是先清空哈希環，再添加。當然這樣就必須每次都指定完整的節點列表。

// 先清空哈希環再設置
func (r *HashRing) Reset(nodes ...string) {
	// 先清空
	r.ring = nil
	r.nodes = map[int]string{}
	// 再重置
	r.Add(nodes...)
}

獲取Key對應的節點

這個方法的功能是查詢Key應該路由到哪個節點，也就是計算Key的哈希值，然后找到哈希值對應的處理節點（這里需要考慮ring數組邏輯上是一個環），然后再根據這個哈希值去尋找真實處理節點的字符串。

// 獲取Key對應的節點
func (r *HashRing) Get(key string) string {
	// 如果哈希環位空，則直接返回
	if r.Empty() {
		return ""
	}

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

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

	// 這里是特殊情況，也就是數組沒有大于等于Key哈希值的節點
	// 但是邏輯上這是一個環，因此第一個節點就是目標節點
	if idx == len(r.ring) {
		idx = 0
	}

	// 返回哈希值對應的真實節點字符串
	return r.nodes[r.ring[idx]]
}

以上就是關于“Golang官方中的一致性哈希組件怎么實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。