一致性哈希 (Consistent Hashing) 算法, 主要應(yīng)用在分布式系統(tǒng)中, 尤其是緩存, 解決負(fù)載均衡碳蛋、熱點(diǎn)、數(shù)據(jù)傾斜等問(wèn)題.
一.目的
將服務(wù)器節(jié)點(diǎn) Node, 映射到一個(gè)較長(zhǎng)的環(huán)上, 當(dāng)查找數(shù)據(jù)時(shí), 在環(huán)上順時(shí)針查找, 該數(shù)據(jù)的 Key 所臨近的服務(wù)器節(jié)點(diǎn) Node, 最后再到服務(wù)器節(jié)點(diǎn)上去查找源數(shù)據(jù).
二.個(gè)人對(duì)算法的理解
1.取一個(gè)環(huán), 作為哈希環(huán).
長(zhǎng)度一般是 2 的 32 次方 (4,294,967,296), 即 int32 的數(shù)值范圍.
2.定一個(gè)哈希規(guī)則, 哈希結(jié)果的值范圍在要跟哈希環(huán)的長(zhǎng)度適配. 比如環(huán)長(zhǎng)度為 2 的 32 次方, 則選用 CRC32 規(guī)則; Redis-Cluster Slots 的個(gè)數(shù)是 2 的 14 次方 (16384), 使用的規(guī)則是 CRC16.
3.使用哈希規(guī)則對(duì)服務(wù)器節(jié)點(diǎn) Node 進(jìn)行哈希運(yùn)算. 比如對(duì)服務(wù)器節(jié)點(diǎn)的 IP须眷、HostName 等, 進(jìn)行 CRC32 哈希運(yùn)算.
4.將哈希運(yùn)算的結(jié)果, 對(duì)哈希環(huán)的長(zhǎng)度進(jìn)行取余運(yùn)算, 然后將余數(shù)映射到哈希環(huán)上.
5.對(duì)查找數(shù)據(jù)的 Key 進(jìn)行 CRC32 哈希運(yùn)算, 并對(duì)哈希環(huán)的長(zhǎng)度進(jìn)行哈希取余操作, 然后順時(shí)針查找臨近的 Node. (Key 比如 user 表的 user id)
三.主要缺點(diǎn)
1.無(wú)法滿(mǎn)足負(fù)載均衡.
如果節(jié)點(diǎn)個(gè)數(shù)比較少, 極端假設(shè)有兩個(gè)節(jié)點(diǎn), 一個(gè)節(jié)點(diǎn) A 的 Hash 值為 0, 另一個(gè)節(jié)點(diǎn) B 的 Hash 值為 10, 而一般哈希環(huán)的長(zhǎng)度一般都相當(dāng)長(zhǎng) (如 int32 范圍), 導(dǎo)致的結(jié)果是 A 負(fù)載 11 ~ int32最大數(shù)值, 而僅僅負(fù)載 1~10.
2.新增節(jié)點(diǎn)導(dǎo)致大量數(shù)據(jù)遷移.
如果新增一個(gè)節(jié)點(diǎn) C, Hash 值為 3,000,000,000, 那么 11 ~3,000,000,000 對(duì)應(yīng)的這么大量的數(shù)據(jù), 會(huì)從 A 遷移到 C 來(lái).
新增的節(jié)點(diǎn), 只為一個(gè)節(jié)點(diǎn)分?jǐn)倝毫? 并不是都為其他節(jié)點(diǎn)分?jǐn)傄徊糠值呢?fù)載壓力.
四.解決的關(guān)鍵思想
節(jié)點(diǎn)越多, 分布越均勻.
負(fù)載越近似均衡, 數(shù)據(jù)傾斜越少.
如果沒(méi)有實(shí)際節(jié)點(diǎn), 那就通過(guò)新增虛擬節(jié)點(diǎn).
于是, 基于虛擬節(jié)點(diǎn)的一致性哈希誕生.
五.用 go 語(yǔ)言實(shí)現(xiàn), 基于虛擬節(jié)點(diǎn)的一致性哈希
1.接口抽象和結(jié)構(gòu)體定義
根據(jù)迪米勒原則, 抽象以下接口
type IConsistentHash interface {
AddNode(node Node) error
RemoveNode(node Node) error
GetNode(key string) Node
}
真實(shí)節(jié)點(diǎn) Node, 作為值類(lèi)型.
type Node struct {
Name string // 服務(wù)器名稱(chēng)
IP string // IP
Port int // 端口
}
虛擬節(jié)點(diǎn), 將用 map 來(lái)與真實(shí)節(jié)點(diǎn)的關(guān)聯(lián), RingIndexs 切片的索引就是虛擬節(jié)點(diǎn)的 ID.
type virtualNode struct {
// 節(jié)點(diǎn)的 Hash 在哈希環(huán)上的索引
RingIndexs []uint32
}
基于虛擬節(jié)點(diǎn)的一致性哈希.
type ConsistentHash struct {
virtualNodeAmount int // 虛擬節(jié)點(diǎn)個(gè)數(shù)
nodeMap map[Node]*virtualNode // 真實(shí)節(jié)點(diǎn) 映射 虛擬節(jié)點(diǎn)
hashVals []uint32 // 所用虛擬節(jié)點(diǎn)的 Hash 值, 主要用于檢索
hashValMap map[uint32]Node // 虛擬節(jié)點(diǎn) Hash 值, 映射真實(shí)節(jié)點(diǎn)
}
2.具體實(shí)現(xiàn)
2.1 虛擬節(jié)點(diǎn) Key 的構(gòu)造
func (*ConsistentHash) node2Str(n Node) string {
// fmt.Sprintf("%s<%s:%d>", n.Name, n.IP, n.Port)
return strings.Join([]string{
n.Name, "<", n.IP, ":", strconv.Itoa(n.Port), ">",
}, "")
}
func (c *ConsistentHash) genKey(nodeStr string, i int) string {
// nodeA#0, nodeA#1, nodeA#2, ...
// nodeB#0, nodeB#1, nodeB#2, ...
return strings.Join([]string{nodeStr, strconv.Itoa(i)}, "#")
}
2.2 哈希算法
因?yàn)樗惴?hash 范圍正是環(huán)的長(zhǎng)度范圍, 所以不對(duì) math.MaxInt32 取余.
func (c *ConsistentHash) hashAlg(str string) uint32 {
var bytes = []byte(str)
return crc32.ChecksumIEEE(bytes)
}
2.3 對(duì)所有虛擬節(jié)點(diǎn)的 Hash 值的排序
快排算法, 時(shí)間復(fù)雜度: O(NlogN), N 為虛擬節(jié)點(diǎn)的個(gè)數(shù)
func (c *ConsistentHash) sort() {
hashVals := make([]uint32, 0, len(c.hashValMap))
// concat all RingIndexs
for _, vn := range c.nodeMap {
hashVals = append(hashVals, vn.RingIndexs...)
}
sort.Slice(hashVals, func(i, j int) bool {
return hashVals[i] < hashVals[j]
})
c.hashVals = hashVals
}
2.5 接口實(shí)現(xiàn)-新增和刪除節(jié)點(diǎn)
在新增節(jié)點(diǎn)時(shí), 自動(dòng)創(chuàng)建虛擬節(jié)點(diǎn), 在刪除節(jié)點(diǎn)時(shí), 將節(jié)點(diǎn)對(duì)應(yīng)的所有虛擬節(jié)點(diǎn)進(jìn)行拔除.
并在修改節(jié)點(diǎn)后, 重新對(duì)所有虛擬節(jié)點(diǎn)的 Hash 值進(jìn)行排序.
var (
ErrNodeExisted = errors.New("Node is Existed")
ErrNodeNotFound = errors.New("Node is not Found")
)
func (c *ConsistentHash) AddNode(node Node) error {
if _, ok := c.nodeMap[node]; ok {
return ErrNodeExisted
}
s := c.node2Str(node)
vn := &virtualNode{
RingIndexs: make([]uint32, 0, c.virtualNodeAmount),
}
for i := 0; i < c.virtualNodeAmount; i++ {
hash := c.hashAlg(c.genKey(s, i))
vn.RingIndexs = append(vn.RingIndexs, hash)
c.hashValMap[hash] = node
}
c.nodeMap[node] = vn
c.sort()
return nil
}
func (c *ConsistentHash) RemoveNode(node Node) error {
if _, ok := c.nodeMap[node]; !ok {
return ErrNodeNotFound
}
delete(c.nodeMap, node)
s := c.node2Str(node)
for i := 0; i < c.virtualNodeAmount; i++ {
hash := c.hashAlg(c.genKey(s, i))
if _, ok := c.hashValMap[hash]; ok {
delete(c.hashValMap, hash)
}
}
c.sort()
return nil
}
2.6 接口實(shí)現(xiàn)-獲取節(jié)點(diǎn)
使用折半算法, 對(duì)節(jié)點(diǎn)進(jìn)行查找
func (c *ConsistentHash) GetNode(key string) Node {
// c.sort()
hash := c.hashAlg(key)
l, r := 0, len(c.hashVals)-1
for l < r {
m := (l + r) / 2
if hash > c.hashVals[m] {
l = m + 1
} else if hash < c.hashVals[m] {
r = m - 1
} else {
ringIndex := c.hashVals[m]
log.Printf("[ConsistentHash/GetNode] key-HashVal:%v, ringIndex:%v.\n", hash, ringIndex)
return c.hashValMap[ringIndex]
}
}
index := l
if hash > c.hashVals[index] {
index = (l + 1) % len(c.hashVals)
}
ringIndex := c.hashVals[index]
log.Printf("[ConsistentHash/GetNode] key-HashVal:%v, ringIndex:%v.\n", hash, ringIndex)
return c.hashValMap[ringIndex]
}
3.測(cè)試
3.1 測(cè)試代碼
主要驗(yàn)證獲取的節(jié)點(diǎn)是否正確, 以及對(duì)新增和刪除節(jié)點(diǎn)的操作是否正確.
真實(shí)節(jié)點(diǎn)個(gè)數(shù): 10
虛擬節(jié)點(diǎn)個(gè)數(shù): 16
import (
"testing"
)
var nodes = []Node{
{Name: "appA.service.order", IP: "192.168.1.100", Port: 5000},
{Name: "appA.service.pay", IP: "192.168.1.101", Port: 5000},
{Name: "appA.service.history", IP: "192.168.1.102", Port: 5000},
{Name: "appA.service.detail", IP: "192.168.1.103", Port: 5000},
{Name: "appA.service.comment", IP: "192.168.1.104", Port: 5000},
{Name: "appA.service.mq", IP: "192.168.1.105", Port: 5000},
{Name: "appA.service.mysql", IP: "192.168.1.106", Port: 5000},
{Name: "appA.service.gateway", IP: "192.168.1.107", Port: 5000},
{Name: "appB.service.geo", IP: "192.168.1.108", Port: 5000},
{Name: "appC.service.cdn", IP: "192.168.1.109", Port: 5000},
}
var user_id = "123456"
func TestConsistentHash_GetNode(t *testing.T) {
c := NewConsistentHash(16, nodes...)
node := c.GetNode(user_id)
t.Logf("GetNode: %+v\n", node)
for node, vn := range c.nodeMap {
t.Logf("%+v, %+v\n", node.IP, vn.RingIndexs)
}
t.Log(c.hashVals)
}
func TestConsistentHash(t *testing.T) {
c := NewConsistentHash(16, nodes...)
node := c.GetNode(user_id)
t.Logf("GetNode: %+v\n", node)
err := c.RemoveNode(node)
t.Log("RemoveNode Err:", err)
err = c.AddNode(node)
t.Log("AddNode Err:", err)
node = c.GetNode(user_id)
t.Logf("GetNode: %+v\n", node)
}
3.2 測(cè)試結(jié)果
排序花颗、新增節(jié)點(diǎn)惠拭、刪除節(jié)點(diǎn)扩劝、獲取節(jié)點(diǎn), 貌似都 Okay.
=== RUN TestConsistentHash_GetNode
2021/06/25 [ConsistentHash/GetNode] key-HashVal:158520161, ringIndex:256098299.
consistenthash_test.go:26: GetNode: {Name:appA.service.pay IP:192.168.1.101 Port:5000}
...
consistenthash_test.go:30: [9950081 24722963 133830552 137264098 147812920 256098299 262321697 ...]
--- PASS: TestConsistentHash_GetNode (0.00s)
=== RUN TestConsistentHash
2021/06/25 [ConsistentHash/GetNode] key-HashVal:158520161, ringIndex:256098299.
consistenthash_test.go:37: GetNode: {Name:appA.service.pay IP:192.168.1.101 Port:5000}
consistenthash_test.go:39: RemoveNode Err: <nil>
consistenthash_test.go:41: AddNode Err: <nil>
2021/06/25 [ConsistentHash/GetNode] key-HashVal:158520161, ringIndex:256098299.
consistenthash_test.go:43: GetNode: {Name:appA.service.pay IP:192.168.1.101 Port:5000}
--- PASS: TestConsistentHash (0.00s)
PASS
ok
