什么是一致性哈希
一致性哈希（Consistent Hashing）是一种分布式系统中常用的算法，用于在节点（如缓存服务器）之间均匀分配数据。它的核心思想是将所有可能的哈希值组织成一个环形结构，并将数据和节点通过哈希值映射到这个环上。这样在添加或删除节点时，只需重新分配极少量的数据，从而实现负载均衡和高可用性。
简单说：将节点均匀的分布，由一个环形结构，来将这些节点映射，实现负载均衡和高可用效果。
一致性hash原理
- 哈希环：将哈希值空间组织成一个环。
- 节点映射：将每个节点（如服务器）通过哈希函数映射到环上的某个点。
- 数据映射：将每个数据（如缓存对象）通过同样的哈希函数映射到环上的某个点。
- 数据存储：数据被存储到顺时针方向最近的节点中。
- 节点变化：当添加或删除节点时，只需重新分配很少的数据。例如，添加节点只会影响其顺时针方向的第一个节点之间的数据。
实现步骤
- 构建一个哈希环状结构
- 增删改查
package main
import (
"crypto/md5"
"fmt"
"hash"
"sort"
"strconv"
"sync"
)
// 哈希环结构体
//包括副本数量（replicas）、哈希函数（hashFunc）、节点映射（nodes）、排序后的键（sortedKeys）和读写锁（mu）
type HashRing struct {
replicas int
hashFunc hash.Hash
nodes map[int]string
sortedKeys []int
mu sync.RWMutex
}
// 创建一个新的HashRing实例，默认使用md5哈希函数。
func NewHashRing(replicas int, hashFunc hash.Hash) *HashRing {
if hashFunc == nil {
hashFunc = md5.New()
}
return &HashRing{
replicas: replicas,
hashFunc: hashFunc,
nodes: make(map[int]string),
sortedKeys: []int{},
}
}
// 添加节点，并为每个节点生成replicas个副本，将它们添加到哈希环中。
func (h *HashRing) AddNode(node string) {
h.mu.Lock()
defer h.mu.Unlock()
for i := 0; i < h.replicas; i++ {
hashKey := h.hashKey(fmt.Sprintf("%s%d", node, i))
h.nodes[hashKey] = node
h.sortedKeys = append(h.sortedKeys, hashKey)
}
sort.Ints(h.sortedKeys)
}
//删除节点，并从哈希环中移除该节点的所有副本。
func (h *HashRing) RemoveNode(node string) {
h.mu.Lock()
defer h.mu.Unlock()
for i := 0; i < h.replicas; i++ {
hashKey := h.hashKey(fmt.Sprintf("%s%d", node, i))
delete(h.nodes, hashKey)
h.removeSortedKey(hashKey)
}
}
//根据键找到对应的节点，通过哈希键在排序后的键数组中查找合适的位置。
func (h *HashRing) GetNode(key string) string {
h.mu.RLock()
defer h.mu.RUnlock()
if len(h.nodes) == 0 {
return ""
}
hashKey := h.hashKey(key)
idx := h.searchKey(hashKey)
return h.nodes[h.sortedKeys[idx]]
}
// 计算字符串的哈希值。
func (h *HashRing) hashKey(key string) int {
h.hashFunc.Reset()
h.hashFunc.Write([]byte(key))
hashBytes := h.hashFunc.Sum(nil)
hashInt, _ := strconv.Atoi(fmt.Sprintf("%x", hashBytes)[:8])
return hashInt
}
// 在排序后的键数组中查找哈希键的位置。
func (h *HashRing) searchKey(hashKey int) int {
idx := sort.Search(len(h.sortedKeys), func(i int) bool {
return h.sortedKeys[i] >= hashKey
})
if idx == len(h.sortedKeys) {
return 0
}
return idx
}
// 从排序后的键数组中移除指定的键。
func (h *HashRing) removeSortedKey(key int) {
idx := h.searchKey(key)
h.sortedKeys = append(h.sortedKeys[:idx], h.sortedKeys[idx+1:]...)
}
// 测试代码
func main() {
hashRing := NewHashRing(3, nil)
hashRing.AddNode("node1")
hashRing.AddNode("node2")
hashRing.AddNode("node3")
fmt.Println("Node for key 'my-key-1':", hashRing.GetNode("my-key-1"))
fmt.Println("Node for key 'my-key-2':", hashRing.GetNode("my-key-2"))
fmt.Println("Node for key 'my-key-3':", hashRing.GetNode("my-key-3"))
hashRing.RemoveNode("node2")
fmt.Println("Node for key 'my-key-1' after removing node2:", hashRing.GetNode("my-key-1"))
fmt.Println("Node for key 'my-key-2' after removing node2:", hashRing.GetNode("my-key-2"))
fmt.Println("Node for key 'my-key-3' after removing node2:", hashRing.GetNode("my-key-3"))
}
