通過 Go 搞懂一致性hash的原理和實(shí)現(xiàn)

在 go-zero 的分布式緩存系統(tǒng)分享里，Kevin 重點(diǎn)講到過一致性hash的原理和分布式緩存中的實(shí)踐。本文來詳細(xì)講講一致性hash的原理和在 go-zero 中的實(shí)現(xiàn)。

以存儲(chǔ)為例，在整個(gè)微服務(wù)系統(tǒng)中，我們的存儲(chǔ)不可能說只是一個(gè)單節(jié)點(diǎn)。

• 一是為了提高穩(wěn)定，單節(jié)點(diǎn)宕機(jī)情況下，整個(gè)存儲(chǔ)就面臨服務(wù)不可用；
• 二是數(shù)據(jù)容錯(cuò)，同樣單節(jié)點(diǎn)數(shù)據(jù)物理?yè)p毀，而多節(jié)點(diǎn)情況下，節(jié)點(diǎn)有備份，除非互為備份的節(jié)點(diǎn)同時(shí)損毀。

那么問題來了，多節(jié)點(diǎn)情況下，數(shù)據(jù)應(yīng)該寫入哪個(gè)節(jié)點(diǎn)呢？

hash

所以本質(zhì)來講：我們需要一個(gè)可以將輸入值“壓縮”并轉(zhuǎn)成更小的值，這個(gè)值通常狀況下是唯一、格式極其緊湊的，比如uint64：

• 冪等：每次用同一個(gè)值去計(jì)算 hash 必須保證都能得到同一個(gè)值

這個(gè)就是 hash 算法完成的。

但是采取普通的 hash 算法進(jìn)行路由，如：key % N 。有一個(gè)節(jié)點(diǎn)由于異常退出了集群或者是心跳異常，這時(shí)再進(jìn)行 hash route ，會(huì)造成大量的數(shù)據(jù)重新 分發(fā)到不同的節(jié)點(diǎn) 。節(jié)點(diǎn)在接受新的請(qǐng)求時(shí)候，需要重新處理獲取數(shù)據(jù)的邏輯：如果是在緩存中，容易引起 緩存雪崩。

此時(shí)就需要引入 consistent hash 算法了。

consistent hash

我們來看看 consistent hash 是怎么解決這些問題的：

rehash

先解決大量 rehash 的問題：

如上圖，當(dāng)加入一個(gè)新的節(jié)點(diǎn)時(shí)，影響的key只有 key31，新加入（剔除）節(jié)點(diǎn)后，只會(huì)影響該節(jié)點(diǎn)附近的數(shù)據(jù)。其他節(jié)點(diǎn)的數(shù)據(jù)不會(huì)收到影響，從而解決了節(jié)點(diǎn)變化的問題。

這個(gè)正是：?jiǎn)握{(diào)性。這也是 normal hash 算法無法滿足分布式場(chǎng)景的原因。

數(shù)據(jù)傾斜

其實(shí)上圖可以看出：目前多數(shù)的key都集中在 node 1 上。如果當(dāng) node 數(shù)量比較少的情況下，可能引發(fā)多數(shù) key 集中在某個(gè) node 上，監(jiān)控時(shí)發(fā)現(xiàn)的問題就是：節(jié)點(diǎn)之間負(fù)載不均。

為了解決這個(gè)問題，consistent hash 引入了 virtual node 的概念。

既然是負(fù)載不均，我們就人為地構(gòu)造一個(gè)均衡的場(chǎng)景出來，但是實(shí)際 node 只有這么多。所以就使用 virtual node 劃分區(qū)域，而實(shí)際服務(wù)的節(jié)點(diǎn)依然是之前的 node。

具體實(shí)現(xiàn)

先來看看 Get()：

Get

先說說實(shí)現(xiàn)的原理：

1. 計(jì)算 key 的hash
2. 找到第一個(gè)匹配的 virtual node 的 index，并取到對(duì)應(yīng)的 h.keys[index] ：virtual node hash 值
3. 對(duì)應(yīng)到這個(gè) ring 中去尋找一個(gè)與之匹配的 actual node

其實(shí)我們可以看到 ring 中獲取到的是一個(gè) []node 。這是因?yàn)樵谟?jì)算 virtual node hash ，可能會(huì)發(fā)生hash沖突，不同的 virtual node hash 對(duì)應(yīng)到一個(gè)實(shí)際node。

這也說明：node 與 virtual node 是一對(duì)多的關(guān)系。而里面的 ring 就是下面這個(gè)設(shè)計(jì)：

這個(gè)其實(shí)也就表明了一致性hash的分配策略：

1. virtual node 作為值域劃分。key 去獲取 node ，從劃分依據(jù)上是以 virtual node 作為邊界
2. virtual node 通過 hash ，在對(duì)應(yīng)關(guān)系上保證了不同的 node 分配的key是大致均勻的。也就是 打散綁定
3. 加入一個(gè)新的 node，會(huì)對(duì)應(yīng)分配多個(gè) virtual node。新節(jié)點(diǎn)可以負(fù)載多個(gè)原有節(jié)點(diǎn)的壓力，從全局看，較容易實(shí)現(xiàn)擴(kuò)容時(shí)的負(fù)載均衡。

Add Node

看完 Get 其實(shí)大致就知道整個(gè)一致性hash的設(shè)計(jì)：

type ConsistentHash struct {
  hashFunc Func       // hash 函數(shù)
  replicas int       // 虛擬節(jié)點(diǎn)放大因子
  keys     []uint64     // 存儲(chǔ)虛擬節(jié)點(diǎn)hash
  ring     map[uint64][]interface{}     // 虛擬節(jié)點(diǎn)與實(shí)際node的對(duì)應(yīng)關(guān)系
  nodes    map[string]lang.PlaceholderType // 實(shí)際節(jié)點(diǎn)存儲(chǔ)【便于快速查找，所以使用map】
  lock     sync.RWMutex
}

好了這樣，基本的一個(gè)一致性hash就實(shí)現(xiàn)完備了。

具體代碼：https://github.com/tal-tech/go-zero/blob/master/core/hash/consistenthash.go

使用場(chǎng)景

開頭其實(shí)就說了，一致性hash可以廣泛使用在分布式系統(tǒng)中：

1. 分布式緩存。可以在 redis cluster 這種存儲(chǔ)系統(tǒng)上構(gòu)建一個(gè) cache proxy，自由控制路由。而這個(gè)路由規(guī)則就可以使用一致性hash算法
2. 服務(wù)發(fā)現(xiàn)
3. 分布式調(diào)度任務(wù)

以上這些分布式系統(tǒng)中，都可以在負(fù)載均衡模塊中使用。

項(xiàng)目地址

https://github.com/tal-tech/go-zero

歡迎使用 go-zero 并 star 支持我們！

推薦閱讀

• 韓信大招：一致性哈希