在 go-zero 的分布式緩存系統(tǒng)分享里屁药，Kevin 重點講到過一致性hash的原理和分布式緩存中的實踐轴捎。本文來詳細講講一致性hash的原理和在 go-zero 中的實現(xiàn)憋他。
以存儲為例进陡，在整個微服務(wù)系統(tǒng)中释牺，我們的存儲不可能說只是一個單節(jié)點萝衩。
- 一是為了提高穩(wěn)定，單節(jié)點宕機情況下没咙，整個存儲就面臨服務(wù)不可用猩谊；
- 二是數(shù)據(jù)容錯，同樣單節(jié)點數(shù)據(jù)物理損毀祭刚，而多節(jié)點情況下牌捷，節(jié)點有備份，除非互為備份的節(jié)點同時損毀涡驮。
那么問題來了宜鸯，多節(jié)點情況下，數(shù)據(jù)應(yīng)該寫入哪個節(jié)點呢遮怜？
hash
所以本質(zhì)來講：我們需要一個可以將輸入值“壓縮”并轉(zhuǎn)成更小的值淋袖，這個值通常狀況下是唯一、格式極其緊湊的锯梁，比如uint64：
- 冪等：每次用同一個值去計算 hash 必須保證都能得到同一個值
這個就是 hash 算法完成的即碗。
但是采取普通的 hash 算法進行路由，如：key % N 陌凳。有一個節(jié)點由于異常退出了集群或者是心跳異常剥懒，這時再進行 hash route ，會造成大量的數(shù)據(jù)重新 分發(fā)到不同的節(jié)點 合敦。節(jié)點在接受新的請求時候初橘，需要重新處理獲取數(shù)據(jù)的邏輯：如果是在緩存中，容易引起 緩存雪崩。
此時就需要引入 consistent hash 算法了保檐。
consistent hash
我們來看看 consistent hash 是怎么解決這些問題的：
rehash
先解決大量 rehash 的問題：
如上圖耕蝉，當(dāng)加入一個新的節(jié)點時，影響的key只有 key31夜只，新加入（剔除）節(jié)點后垒在，只會影響該節(jié)點附近的數(shù)據(jù)。其他節(jié)點的數(shù)據(jù)不會收到影響扔亥，從而解決了節(jié)點變化的問題场躯。
這個正是：單調(diào)性。這也是 normal hash 算法無法滿足分布式場景的原因旅挤。
數(shù)據(jù)傾斜
其實上圖可以看出：目前多數(shù)的key都集中在 node 1 上踢关。如果當(dāng) node 數(shù)量比較少的情況下，可以回引發(fā)多數(shù) key 集中在某個 node 上粘茄，監(jiān)控時發(fā)現(xiàn)的問題就是：節(jié)點之間負載不均耘成。
為了解決這個問題，consistent hash 引入了 virtual node 的概念驹闰。
既然是負載不均，我們就人為地構(gòu)造一個均衡的場景出來撒会，但是實際 node 只有這么多嘹朗。所以就使用 virtual node 劃分區(qū)域，而實際服務(wù)的節(jié)點依然是之前的 node诵肛。
具體實現(xiàn)
先來看看 Get()：
Get
先說說實現(xiàn)的原理：
- 計算
key的hash - 找到第一個匹配的
virtual node的 index屹培，并取到對應(yīng)的h.keys[index]：virtual node hash 值 - 對應(yīng)到這個
ring中去尋找一個與之匹配的actual node
其實我們可以看到 ring 中獲取到的是一個 []node 。這是因為在計算 virtual node hash 怔檩，可能會發(fā)生hash沖突褪秀，不同的 virtual node hash 對應(yīng)到一個實際node。
這也說明：node 與 virtual node 是一對多的關(guān)系薛训。而里面的 ring 就是下面這個設(shè)計：
這個其實也就表明了一致性hash的分配策略：
-
virtual node作為值域劃分媒吗。key去獲取node，從劃分依據(jù)上是以virtual node作為邊界 -
virtual node通過hash乙埃，在對應(yīng)關(guān)系上保證了不同的 node 分配的key是大致均勻的闸英。也就是 打散綁定 - 加入一個新的 node，會對應(yīng)分配多個
virtual node介袜。新節(jié)點可以負載多個原有節(jié)點的壓力甫何，從全局看，較容易實現(xiàn)擴容時的負載均衡遇伞。
Add Node
看完 Get 其實大致就知道整個一致性hash的設(shè)計：
type ConsistentHash struct {
hashFunc Func // hash 函數(shù)
replicas int // 虛擬節(jié)點放大因子
keys []uint64 // 存儲虛擬節(jié)點hash
ring map[uint64][]interface{} // 虛擬節(jié)點與實際node的對應(yīng)關(guān)系
nodes map[string]lang.PlaceholderType // 實際節(jié)點存儲【便于快速查找辙喂，所以使用map】
lock sync.RWMutex
}
好了這樣，基本的一個一致性hash就實現(xiàn)完備了。
具體代碼：https://github.com/tal-tech/go-zero/blob/master/core/hash/consistenthash.go
使用場景
開頭其實就說了巍耗，一致性hash可以廣泛使用在分布式系統(tǒng)中：
- 分布式緩存秋麸。可以在
redis cluster這種存儲系統(tǒng)上構(gòu)建一個cache proxy芍锦，自由控制路由竹勉。而這個路由規(guī)則就可以使用一致性hash算法 - 服務(wù)發(fā)現(xiàn)
- 分布式調(diào)度任務(wù)
以上這些分布式系統(tǒng)中，都可以在負載均衡模塊中使用娄琉。
項目地址
https://github.com/tal-tech/go-zero
歡迎使用 go-zero 并 star 支持我們次乓！
微信交流群
關(guān)注『微服務(wù)實踐』公眾號并點擊 交流群 獲取社區(qū)群二維碼。
