Golang 实现基于一致性哈希的请求路由分发算法

一致性哈希，这个由Da vid Karger在1997年提出的环形哈希算法，经过这么多年，依然是分布式系统里应对扩缩容的核心方案。它的基本思路很容易理解：把节点和数据都映射到0到2³²−1这个哈希环上，然后让数据沿着环顺时针走，遇到的第一个节点就是它的归宿。这样一来，增加或删除节点时，受影响的只有邻近的一小段数据，这正是它平衡性、单调性和分散性这几个优点的来源。不过，需要记住的是，算法的灵魂在于环的结构和虚拟节点机制，而不是哈希函数本身选得多花哨。

直接拿 hash/crc32 的值再去对节点数取模，那可不是一致性哈希，那还是普通的哈希取模。真正想让路由稳定、扩缩容时不雪崩，就必须老老实实建环、加虚拟节点，然后用 sort.Search 去查找。

为什么不能用 keyHash % len(nodes) 做路由

想象一下，你的节点从3台变成了4台，结果呢？大约75%的请求都会重新映射。这意味着什么？缓存会全部失效，数据库被瞬间打穿，下游服务直接过载。这不是理论推演，而是压测里真实可见的秒级雪崩。一致性哈希的目标很明确：加一台机器，最多只影响1%左右的key，其余请求纹丝不动。

两种方式的根本区别在于结构。取模是线性分片，而一致性哈希是把所有节点和数据都“钉”在一个闭合的环上，数据顺时针找到它遇到的第一个节点。新增或删除节点，影响的只是环上那一小段邻近的key。

• 别被“哈希”两个字带偏了方向，算法成败的关键不在于哈希函数有多强，而在于有没有环结构和顺时针定位的逻辑
• 环的数据类型必须是 []uint32，不要用 int32，否则负数会让绕环逻辑出问题
• 返回值必须用 i % len(ring) 来做回绕处理，因为 sort.Search 返回的是索引，不是环上的值

该用哪个哈希函数：选 crc32.ChecksumIEEE，别碰 md5 或 hash/fnv

在这个场景里，crc32.ChecksumIEEE([]byte(key)) 是唯一推荐的选择。它输出的天然就是 uint32，分布很均匀，没有内存分配，而且在各种语言（Ja va、Python、JS）里默认实现都一致。Go标准库自带最优的查表实现，调用起来也简洁，没有panic的风险。

其他常见的选择，其实都是坑：

• crc32.Checksum([]byte(key), nil) 会直接 panic，要么传一个表进去，要么改用 ChecksumIEEE
• hash/fnv.New32a() 没有seed控制，容易被恶意的key扎堆攻击，不适合用在生产环境的路由上
• fmt.Sprintf("%s", key) 加上 md5.Sum 的组合，字符串转换的开销很大，而且md5本身是加密级别的，完全没必要
• maphash.Hash 虽然快，但输出是 uint64，需要手动截断或者对2³²取模，反而容易引入误差，不推荐用于环坐标

虚拟节点怎么设：20–60 个足够，别硬写 100

虚拟节点并不是越多越好。从实测数据来看，每个物理节点配上20到60个虚拟节点，就已经能把负载的标准差压在±5%以内。一旦超过100个，查找延迟会从大约20ns飙升到80ns，CPU cache miss率陡增，初始化耗时也会明显增加。

生成虚拟节点的hash值时，必须采用确定性的方式，绝对不能依赖 math/rand：

• 正确做法：crc32.ChecksumIEEE([]byte(nodeName + "-" + strconv.Itoa(i)))
• 错误做法：用 rand.Uint32()，或者用没设seed的 rand.New(rand.NewSource(time.Now().UnixNano()))。在多goroutine并发下，这种写法极易产出重复值，导致节点在环上扎堆。
• 拼接虚拟节点名时，尽量避开 fmt.Sprintf。在QPS过万的情况下，用 unsafe.String 或者预先分配 []byte 的方式会更快。

sort.Search 查环的三个必兜底边界

环在数学上是首尾相接的，但 []uint32 是线性数组。sort.Search 只管找索引，不会帮你处理环形语义。这三个边界条件，漏掉任何一个，线上就会panic或者返回空值。

• 环为空：必须加判断 if len(ring) == 0 { return "", errors.New("ring is empty") }，不能直接进 sort.Search
• key hash 大于环上的所有节点：sort.Search 会返回 len(ring)，这时候需要用 ring[i%len(ring)] 回绕到环的首节点
• 多个虚拟节点 hash 碰撞在同一位置：虽然 sort.Search 仍然能正确返回第一个大于等于key的索引，但在添加节点时，最好主动跳过重复值，避免冗余。

典型的、安全的查找写法是这样：i := sort.Search(len(ring), func(j int) bool { return ring[j] >= keyHash }); return ring[i%len(ring)]。最后的这个取模操作不是偷懒，它是由环路结构决定的数学必然。