背景

一致性哈希（Consistent Hashing）的出现，源于大规模分布式系统中面临的一个核心问题：

当我们将数据或缓存分布在多个节点（机器）上时，如何让 key 分布合理、节点可扩缩容，并保持缓存命中率稳定？

传统哈希的缺陷（背景问题）

nodeIndex = hash(key) % N

• N 是节点数量

• key 是数据标识，比如 user_123
  问题来了：

如果你增加或减少节点（比如从 3 台变成 4 台），由于 N 变化，所有 key 的哈希结果都会变，导致所有缓存数据失效，重新缓存。

这种现象叫：

❌ “缓存雪崩”问题
一加节点，90% 的 key 映射变了 → 90% 缓存 miss → 都去查数据库 → 系统崩溃

系统无法平滑扩容 / 宕机恢复

一致性哈希的提出背景

一致性哈希最早是在 1997 年 MIT 论文《Consistent Hashing and Random Trees》 中被提出。

后来被 Amazon Dynamo、Cassandra、Riak、Memcached 分布式客户端（如 Ketama） 等广泛采用。

核心目的：
节点变化时，只重分布极少量的数据，提升系统稳定性和扩展性。

Code

package main

import (
	"crypto/md5"
	"fmt"
	"sort"
	"strconv"
)

// 哈希函数：返回 uint32 的哈希值
func hashKey(key string) uint32 {
	hash := md5.Sum([]byte(key))
	return (uint32(hash[0]) << 24) | (uint32(hash[1]) << 16) | (uint32(hash[2]) << 8) | uint32(hash[3])
}

// 一致性哈希结构
type ConsistentHash struct {
	replicas    int                 // 虚拟节点数量
	hashCircle  []uint32            // 排序后的虚拟节点 hash 环
	hashMap     map[uint32]string   // hash -> 节点名
	nodeStorage map[string][]string // 节点 -> 存储的 keys
}

func NewConsistentHash(replicas int) *ConsistentHash {
	return &ConsistentHash{
		replicas:    replicas,
		hashMap:     make(map[uint32]string),
		nodeStorage: make(map[string][]string),
	}
}

// 添加真实节点，同时添加虚拟节点
func (c *ConsistentHash) AddNode(node string) {
	for i := 0; i < c.replicas; i++ {
		virtualKey := node + "#" + strconv.Itoa(i)
		hash := hashKey(virtualKey)
		c.hashCircle = append(c.hashCircle, hash)
		c.hashMap[hash] = node
	}
	sort.Slice(c.hashCircle, func(i, j int) bool {
		return c.hashCircle[i] < c.hashCircle[j]
	})
}

// 获取 key 所属节点
func (c *ConsistentHash) GetNode(key string) string {
	if len(c.hashCircle) == 0 {
		return ""
	}
	hash := hashKey(key)
	// 二分查找
	idx := sort.Search(len(c.hashCircle), func(i int) bool {
		return c.hashCircle[i] >= hash
	})
	if idx == len(c.hashCircle) {
		idx = 0
	}
	return c.hashMap[c.hashCircle[idx]]
}

// 模拟存储 key 到节点
func (c *ConsistentHash) StoreKey(key string) {
	node := c.GetNode(key)
	c.nodeStorage[node] = append(c.nodeStorage[node], key)
	fmt.Printf("key '%s' 存储到节点 '%s'\n", key, node)
}

// 打印每个节点存储的 key
func (c *ConsistentHash) PrintStorage() {
	for node, keys := range c.nodeStorage {
		fmt.Printf("节点 %s 存储了 %d 个 key: %v\n", node, len(keys), keys)
	}
}

func main() {
	ch := NewConsistentHash(3) // 每个节点 3 个虚拟节点

	// 添加缓存节点
	ch.AddNode("CacheA")
	ch.AddNode("CacheB")
	ch.AddNode("CacheC")

	// 模拟存储多个 key
	keys := []string{"user_1", "user_2", "user_3", "user_4", "user_5", "user_123"}
	for _, k := range keys {
		ch.StoreKey(k)
	}

	// 查看各节点存储情况
	fmt.Println("\n分布情况：")
	ch.PrintStorage()

	name := ch.GetNode("user_1")
	fmt.Printf("user_1 存储在节点 %s\n", name)

}

🧩 总结

一致性哈希的背景就是为了解决分布式系统中，节点动态变化时，数据/缓存迁移代价高的问题，目标是让系统能：

稳定运行

平滑扩容

高命中率

动态容错