為什么需要一致性哈希
Hash塌忽，一般翻譯做散列，或音譯為哈希，是把任意長度的輸入（又叫做預(yù)映射pre-image）通過散列算法變換成固定長度的輸出架曹，該輸出就是散列值取逾。這種轉(zhuǎn)換是一種壓縮映射说莫，也就是得运，散列值的空間通常遠小于輸入的空間姑蓝，不同的輸入可能會散列成相同的輸出鹅心，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)纺荧。
在分布式緩存服務(wù)中旭愧，經(jīng)常需要對服務(wù)進行節(jié)點添加和刪除操作，我們希望的是節(jié)點添加和刪除操作盡量減少數(shù)據(jù)-節(jié)點之間的映射關(guān)系更新宙暇。
假如我們使用的是哈希取模( hash(key)%nodes ) 算法作為路由策略:
哈希取模的缺點在于如果有節(jié)點的刪除和添加操作榕茧，對 hash(key)%nodes 結(jié)果影響范圍太大了，造成大量的請求無法命中從而導(dǎo)致緩存數(shù)據(jù)被重新加載客给。
基于上面的缺點提出了一種新的算法：一致性哈希用押。一致性哈希可以實現(xiàn)節(jié)點刪除和添加只會影響一小部分數(shù)據(jù)的映射關(guān)系靶剑，由于這個特性哈希算法也常常用于各種均衡器中實現(xiàn)系統(tǒng)流量的平滑遷移蜻拨。
一致性哈希工作原理
首先對節(jié)點進行哈希計算，哈希值通常在 2^32-1 范圍內(nèi)桩引。然后將 2^32-1 這個區(qū)間首尾連接抽象成一個環(huán)并將節(jié)點的哈希值映射到環(huán)上缎讼，當(dāng)我們要查詢 key 的目標(biāo)節(jié)點時，同樣的我們對 key 進行哈希計算坑匠，然后順時針查找到的第一個節(jié)點就是目標(biāo)節(jié)點血崭。
根據(jù)原理我們分析一下節(jié)點添加和刪除對數(shù)據(jù)范圍的影響。
-
節(jié)點添加
image只會影響新增節(jié)點與前一個節(jié)點（新增節(jié)點逆時針查找的第一個節(jié)點）之間的數(shù)據(jù)。
-
節(jié)點刪除
image只會影響刪除節(jié)點與前一個節(jié)點（刪除節(jié)點逆時針查找的第一個節(jié)點）之間的數(shù)據(jù)夹纫。
這樣就完了嗎咽瓷？還沒有，試想一下假如環(huán)上的節(jié)點數(shù)量非常少舰讹，那么非常有可能造成數(shù)據(jù)分布不平衡茅姜，本質(zhì)上是環(huán)上的區(qū)間分布粒度太粗。
怎么解決呢月匣？不是粒度太粗嗎钻洒？那就加入更多的節(jié)點，這就引出了一致性哈希的虛擬節(jié)點概念锄开，虛擬節(jié)點的作用在于讓環(huán)上的節(jié)點區(qū)間分布粒度變細素标。
一個真實節(jié)點對應(yīng)多個虛擬節(jié)點，將虛擬節(jié)點的哈希值映射到環(huán)上萍悴，查詢 key 的目標(biāo)節(jié)點我們先查詢虛擬節(jié)點再找到真實節(jié)點即可糯钙。
代碼實現(xiàn)
基于上面的一致性哈希原理，我們可以提煉出一致性哈希的核心功能：
- 添加節(jié)點
- 刪除節(jié)點
- 查詢節(jié)點
我們來定義一下接口：
ConsistentHash interface {
Add(node Node)
Get(key Node) Node
Remove(node Node)
}
現(xiàn)實中不同的節(jié)點服務(wù)能力因硬件差異可能各不相同退腥，于是我們希望在添加節(jié)點時可以指定權(quán)重。反應(yīng)到一致性哈希當(dāng)中所謂的權(quán)重意思就是我們希望 key 的目標(biāo)節(jié)點命中概率比例再榄，一個真實節(jié)點的虛擬節(jié)點數(shù)量多則意味著被命中概率高狡刘。
在接口定義中我們可以增加兩個方法：支持指定虛擬節(jié)點數(shù)量添加節(jié)點，支持按權(quán)重添加困鸥。本質(zhì)上最終都會反應(yīng)到虛擬節(jié)點的數(shù)量不同導(dǎo)致概率分布差異嗅蔬。
指定權(quán)重時：實際虛擬節(jié)點數(shù)量 = 配置的虛擬節(jié)點 * weight/100
ConsistentHash interface {
Add(node Node)
AddWithReplicas(node Node, replicas int)
AddWithWeight(node Node, weight int)
Get(key Node) Node
Remove(node Node)
}
接下來考慮幾個工程實現(xiàn)的問題：
-
虛擬節(jié)點如何存儲？
很簡單疾就，用列表（切片）存儲即可澜术。
-
虛擬節(jié)點 - 真實節(jié)點關(guān)系存儲
map 即可。
-
順時針查詢第一個虛擬節(jié)點如何實現(xiàn)
讓虛擬節(jié)點列表保持有序猬腰，二分查找第一個比 hash(key) 大的 index鸟废，list[index] 即可。
-
虛擬節(jié)點哈希時會有很小的概率出現(xiàn)沖突姑荷，如何處理呢盒延？
沖突時意味著這一個虛擬節(jié)點會對應(yīng)多個真實節(jié)點，map 中 value 存儲真實節(jié)點數(shù)組鼠冕，查詢 key 的目標(biāo)節(jié)點時對 nodes 取模添寺。
-
如何生成虛擬節(jié)點
基于虛擬節(jié)點數(shù)量配置 replicas，循環(huán) replicas 次依次追加 i 字節(jié) 進行哈希計算懈费。
go-zero 源碼解析
core/hash/consistenthash.go
花了一天時間把 go-zero 源碼一致性哈希源碼看完计露，寫的真好啊，各種細節(jié)都考慮到了。
go-zero 使用的哈希函數(shù)是 MurmurHash3票罐，GitHub：https://github.com/spaolacci/murmur3
go-zero 并沒有進行接口定義叉趣，沒啥關(guān)系，直接看結(jié)構(gòu)體 ConsistentHash：
// Func defines the hash method.
// 哈希函數(shù)
Func func(data []byte) uint64
// A ConsistentHash is a ring hash implementation.
// 一致性哈希
ConsistentHash struct {
// 哈希函數(shù)
hashFunc Func
// 確定node的虛擬節(jié)點數(shù)量
replicas int
// 虛擬節(jié)點列表
keys []uint64
// 虛擬節(jié)點到物理節(jié)點的映射
ring map[uint64][]interface{}
// 物理節(jié)點映射胶坠，快速判斷是否存在node
nodes map[string]lang.PlaceholderType
// 讀寫鎖
lock sync.RWMutex
}
key 和虛擬節(jié)點的哈希計算
在進行哈希前要先將 key 轉(zhuǎn)換成 string
// 可以理解為確定node字符串值的序列化方法
// 在遇到哈希沖突時需要重新對key進行哈希計算
// 為了減少沖突的概率前面追加了一個質(zhì)數(shù)prime來減小沖突的概率
func innerRepr(v interface{}) string {
return fmt.Sprintf("%d:%v", prime, v)
}
// 可以理解為確定node字符串值的序列化方法
// 如果讓node強制實現(xiàn)String()會不會更好一些君账？
func repr(node interface{}) string {
return mapping.Repr(node)
}
這里 mapping.Repr 里會判斷 fmt.Stringer 接口，如果符合沈善，就會調(diào)用其 String 方法乡数。go-zero 代碼如下：
// Repr returns the string representation of v.
func Repr(v interface{}) string {
if v == nil {
return ""
}
// if func (v *Type) String() string, we can't use Elem()
switch vt := v.(type) {
case fmt.Stringer:
return vt.String()
}
val := reflect.ValueOf(v)
if val.Kind() == reflect.Ptr && !val.IsNil() {
val = val.Elem()
}
return reprOfValue(val)
}
添加節(jié)點
最終調(diào)用的是 指定虛擬節(jié)點添加節(jié)點方法
// 擴容操作，增加物理節(jié)點
func (h *ConsistentHash) Add(node interface{}) {
h.AddWithReplicas(node, h.replicas)
}
添加節(jié)點 - 指定權(quán)重
最終調(diào)用的同樣是 指定虛擬節(jié)點添加節(jié)點方法
// 按權(quán)重添加節(jié)點
// 通過權(quán)重來計算方法因子闻牡，最終控制虛擬節(jié)點的數(shù)量
// 權(quán)重越高净赴，虛擬節(jié)點數(shù)量越多
func (h *ConsistentHash) AddWithWeight(node interface{}, weight int) {
replicas := h.replicas * weight / TopWeight
h.AddWithReplicas(node, replicas)
}
添加節(jié)點 - 指定虛擬節(jié)點數(shù)量
// 擴容操作，增加物理節(jié)點
func (h *ConsistentHash) AddWithReplicas(node interface{}, replicas int) {
// 支持可重復(fù)添加
// 先執(zhí)行刪除操作
h.Remove(node)
// 不能超過放大因子上限
if replicas > h.replicas {
replicas = h.replicas
}
// node key
nodeRepr := repr(node)
h.lock.Lock()
defer h.lock.Unlock()
// 添加node map映射
h.addNode(nodeRepr)
for i := 0; i < replicas; i++ {
// 創(chuàng)建虛擬節(jié)點
hash := h.hashFunc([]byte(nodeRepr + strconv.Itoa(i)))
// 添加虛擬節(jié)點
h.keys = append(h.keys, hash)
// 映射虛擬節(jié)點-真實節(jié)點
// 注意hashFunc可能會出現(xiàn)哈希沖突罩润，所以采用的是追加操作
// 虛擬節(jié)點-真實節(jié)點的映射對應(yīng)的其實是個數(shù)組
// 一個虛擬節(jié)點可能對應(yīng)多個真實節(jié)點玖翅，當(dāng)然概率非常小
h.ring[hash] = append(h.ring[hash], node)
}
// 排序
// 后面會使用二分查找虛擬節(jié)點
sort.Slice(h.keys, func(i, j int) bool {
return h.keys[i] < h.keys[j]
})
}
刪除節(jié)點
// 刪除物理節(jié)點
func (h *ConsistentHash) Remove(node interface{}) {
// 節(jié)點的string
nodeRepr := repr(node)
// 并發(fā)安全
h.lock.Lock()
defer h.lock.Unlock()
// 節(jié)點不存在
if !h.containsNode(nodeRepr) {
return
}
// 移除虛擬節(jié)點映射
for i := 0; i < h.replicas; i++ {
// 計算哈希值
hash := h.hashFunc([]byte(nodeRepr + strconv.Itoa(i)))
// 二分查找到第一個虛擬節(jié)點
index := sort.Search(len(h.keys), func(i int) bool {
return h.keys[i] >= hash
})
// 切片刪除對應(yīng)的元素
if index < len(h.keys) && h.keys[index] == hash {
// 定位到切片index之前的元素
// 將index之后的元素（index+1）前移覆蓋index
h.keys = append(h.keys[:index], h.keys[index+1:]...)
}
// 虛擬節(jié)點刪除映射
h.removeRingNode(hash, nodeRepr)
}
// 刪除真實節(jié)點
h.removeNode(nodeRepr)
}
// 刪除虛擬-真實節(jié)點映射關(guān)系
// hash - 虛擬節(jié)點
// nodeRepr - 真實節(jié)點
func (h *ConsistentHash) removeRingNode(hash uint64, nodeRepr string) {
// map使用時應(yīng)該校驗一下
if nodes, ok := h.ring[hash]; ok {
// 新建一個空的切片,容量與nodes保持一致
newNodes := nodes[:0]
// 遍歷nodes
for _, x := range nodes {
// 如果序列化值不相同，x是其他節(jié)點
// 不能刪除
if repr(x) != nodeRepr {
newNodes = append(newNodes, x)
}
}
// 剩余節(jié)點不為空則重新綁定映射關(guān)系
if len(newNodes) > 0 {
h.ring[hash] = newNodes
} else {
// 否則刪除即可
delete(h.ring, hash)
}
}
}
查詢節(jié)點
// 根據(jù)v順時針找到最近的虛擬節(jié)點
// 再通過虛擬節(jié)點映射找到真實節(jié)點
func (h *ConsistentHash) Get(v interface{}) (interface{}, bool) {
h.lock.RLock()
defer h.lock.RUnlock()
// 當(dāng)前沒有物理節(jié)點
if len(h.ring) == 0 {
return nil, false
}
// 計算哈希值
hash := h.hashFunc([]byte(repr(v)))
// 二分查找
// 因為每次添加節(jié)點后虛擬節(jié)點都會重新排序
// 所以查詢到的第一個節(jié)點就是我們的目標(biāo)節(jié)點
// 取余則可以實現(xiàn)環(huán)形列表效果割以，順時針查找節(jié)點
index := sort.Search(len(h.keys), func(i int) bool {
return h.keys[i] >= hash
}) % len(h.keys)
// 虛擬節(jié)點->物理節(jié)點映射
nodes := h.ring[h.keys[index]]
switch len(nodes) {
// 不存在真實節(jié)點
case 0:
return nil, false
// 只有一個真實節(jié)點金度，直接返回
case 1:
return nodes[0], true
// 存在多個真實節(jié)點意味這出現(xiàn)哈希沖突
default:
// 此時我們對v重新進行哈希計算
// 對nodes長度取余得到一個新的index
innerIndex := h.hashFunc([]byte(innerRepr(v)))
pos := int(innerIndex % uint64(len(nodes)))
return nodes[pos], true
}
}
項目地址
https://github.com/zeromicro/go-zero
歡迎使用 go-zero 并 star 支持我們！
微信交流群
關(guān)注『微服務(wù)實踐』公眾號并點擊 交流群 獲取社區(qū)群二維碼严沥。
