一致性hash算法的应用与go语言实现
// 代码是一个简单demo, 不用于生产，在生产环境有许多需要优化地方
package main
import (
"crypto/sha256"
"encoding/hex"
"errors"
"fmt"
"hash/crc32"
"sort"
"strconv"
)
type HashFunc func(data []byte) string
// sha256
func sha256Hash(data []byte) string {
hash := sha256.Sum256(data)
hashString := hex.EncodeToString(hash[:])
return hashString
}
// crc32
func crc32Hash(data []byte) string {
crc := crc32.ChecksumIEEE(data)
return string(crc)
}
// ConsistentHash 一致性哈希算法的结构体
type ConsistentHash struct {
replicas int // 虚拟节点数量
Nodes map[string]string // 节点哈希表
SortedHashes []string // 已排序的哈希切片
hash HashFunc // 取hash函数
}
// New 初始化hash算法
func New(replicas int, hashFunc HashFunc) *ConsistentHash {
return &ConsistentHash{
replicas: replicas,
hash: hashFunc,
Nodes: make(map[string]string),
}
}
// AddNode 添加节点
func (c *ConsistentHash) AddNode(node string) {
if c.Nodes == nil {
c.Nodes = make(map[string]string)
}
for i := 0; i < c.replicas; i++ {
hash := c.hash([]byte(strconv.Itoa(i) + node))
c.Nodes[hash] = node
c.SortedHashes = append(c.SortedHashes, hash)
}
// 对节点的哈希值进行排序
sort.Slice(c.SortedHashes, func(i, j int) bool {
return c.SortedHashes[i] < c.SortedHashes[j]
})
}
// RemoveNode 移除节点
func (c *ConsistentHash) RemoveNode(node string) {
var newKeys []string
found := false
for _, hashVal := range c.SortedHashes {
// 如果存在该节点，就删除该节点
if c.Nodes[hashVal] == node {
found = true
continue
}
// 把剩余节点添加进新的集合中
newKeys = append(newKeys, hashVal)
}
// 如果不存在，就直接返回
if !found {
return
}
c.SortedHashes = newKeys
for hashVal := range c.Nodes {
if c.Nodes[hashVal] == node {
delete(c.Nodes, hashVal)
}
}
}
// GetNode 顺时针查找最近的节点
func (c *ConsistentHash) GetNode(key string) (string, error) {
if len(c.SortedHashes) == 0 {
return "", errors.New("sortedHash is nil")
}
hash := c.hash([]byte(key))
idx := sort.Search(len(c.SortedHashes), func(i int) bool {
return c.SortedHashes[i] >= hash
})
if idx == len(c.SortedHashes) {
idx = 0
}
return c.Nodes[c.SortedHashes[idx]], nil
}
// 测试如下
func main() {
cc := New(100, sha256Hash)
cc.AddNode("node1")
cc.AddNode("node2")
cc.AddNode("node3")
cc.AddNode("node4")
cc.AddNode("node5")
aa, _ := cc.GetNode("11")
fmt.Println(aa) // node1
aa, _ = cc.GetNode("22")
fmt.Println(aa) // node1
aa, _ = cc.GetNode("33")
fmt.Println(aa) // node4
aa, _ = cc.GetNode("44")
fmt.Println(aa) // node5
cc.RemoveNode("node4")
fmt.Println("--------------")
aa, _ = cc.GetNode("11")
fmt.Println(aa) // node1
aa, _ = cc.GetNode("22")
fmt.Println(aa) // node1
aa, _ = cc.GetNode("33")
fmt.Println(aa) // node3
aa, _ = cc.GetNode("44")
fmt.Println(aa) // node3
cc.RemoveNode("node2")
cc.RemoveNode("node1")
cc.RemoveNode("node5")
fmt.Println("--------------")
aa, _ = cc.GetNode("11")
fmt.Println(aa) // node3
aa, _ = cc.GetNode("22")
fmt.Println(aa) // node3
}