一致性哈希与负载均衡
把数据分配到多台机器上，需要一个“用 key 算机器”的规则。最直觉的写法是对机器台数取模，可一旦台数变化，几乎所有 key 的归属都会改变，缓存大面积失效、数据库瞬间被打穿。一致性哈希解决的就是“扩缩容时尽量少搬数据”这个问题，它既用于缓存分片，也用于网关层的负载均衡。
取模哈希的扩容之痛
假设有 3 台缓存节点，用 hash(key) % 3 决定归属。新增第 4 台后端数变成 4，公式变成 hash(key) % 4：
| 变化 | 公式变化 | 仍落在原节点的 key | 需要迁移的 key |
|---|---|---|---|
| 3 台 → 4 台 | %3 → %4 | 约 1/4 | 约 3/4 |
| 4 台 → 5 台 | %4 → %5 | 约 1/5 | 约 4/5 |
| N 台 → N+1 台 | %N → %(N+1) | 约 1/(N+1) | 约 N/(N+1) |
结论很糟：扩容本该是“加机器分担压力”，取模却让绝大多数 key 换了归属。缓存场景下这些 key 全部未命中，请求瞬间压到数据库，这是缓存雪崩的一种常见成因。
一致性哈希环
一致性哈希把哈希值空间首尾相接成一个环（以 32 位哈希为例，范围 0 ~ 2^32-1）：
- 把每个节点（节点名或
IP:端口）哈希后放到环上； - 把 key 也哈希到环上；
- 沿环顺时针找到的第一个节点，就是该 key 的归属节点。
这样扩容时只影响环上相邻的一段：
环上顺序: node-a → node-b → node-c → (回到 node-a)
新增 node-d 落在 node-b 之前：
原本属于 node-b 的一段 key 交给 node-d，其余 key 不受影响
理论上平均只迁移约 1/N 的 key（N 为节点数），比取模的 N/(N+1) 好一个数量级。
虚拟节点解决倾斜
只有 3~5 个物理节点时，它们在环上的位置近似随机，弧长可能相差数倍，导致某台机器扛了大部分流量；节点下线时，它的全部流量又只压给顺时针的下一个节点。
做法是给每个物理节点分配大量虚拟节点（常见 100~200 个），虚拟节点名一般用 节点名#序号，各自哈希后散布到环上：
| 方案 | 负载均衡度 | 单节点下线的影响 | 代价 |
|---|---|---|---|
| 无虚拟节点 | 差，容易倾斜 | 全部压给下一个节点 | 无 |
| 有虚拟节点 | 好，趋近均匀 | 分摊到多个节点 | 环变大、查找与内存开销略增 |
虚拟节点越多越均匀，但环的查找结构（通常是排序数组 + 二分查找）也越大，需要按节点规模权衡。
与取模对比
| 维度 | 取模哈希 | 一致性哈希 |
|---|---|---|
| 扩容迁移量 | 约 N/(N+1) 的 key | 约 1/N 的 key |
| 实现复杂度 | 极简 | 需维护环与虚拟节点 |
| 负载均匀性 | key 足够多时均匀 | 依赖虚拟节点数量 |
| 节点故障影响 | 该节点数据全部失效 | 只影响它负责的区间 |
| 典型场景 | 分片数固定的分库分表 | 缓存分片、网关路由、有状态服务 |
分库分表通常提前规划好分片数并保持不变，所以取模仍然够用；节点会动态增减的缓存与网关场景，才更依赖一致性哈希。
应用一：缓存分片
自建分片（多个独立实例 + 客户端哈希）可以直接用一致性哈希。Redis Cluster 走的是另一条路线：把 key 空间划分为 16384 个哈希槽，槽固定分配给节点，客户端按 CRC16(key) % 16384 定位槽再找节点，扩容以槽为单位迁移。思路与一致性哈希一致——把“分布均匀”和“迁移粒度”分开处理。
应用二：网关负载均衡
Nginx 的 hash 指令加 consistent 参数即启用一致性哈希（ketama 思路）；Envoy 提供 ring hash、maglev 等哈希负载均衡策略，用于把同一会话尽量固定到同一后端：
# Nginx 配置片段，字段含义以官方文档为准
upstream backend {
hash $request_uri consistent; # 同一 URI 尽量固定落到同一后端
server 10.0.0.1:8080;
server 10.0.0.2:8080;
}
注意：一致性哈希只保证“同样的 key 尽量走同样的节点”，节点增减时仍会有少量请求被重定向。因此后端服务本身要做到无状态或能安全重定向，不能把会话数据只放在某一台上。
一个最小实现
下面用 Go 展示环的核心逻辑（省略并发保护与完整工程结构）：
// 以下片段需放入 main 函数中运行
type Ring struct {
keys []int // 升序排列的哈希值
owners map[int]string // 哈希值 → 节点名
}
// Get 返回 key 顺时针方向遇到的第一个节点
func (r *Ring) Get(key string) string {
if len(r.keys) == 0 {
return ""
}
h := int(crc32.ChecksumIEEE([]byte(key)))
i := sort.SearchInts(r.keys, h) // 第一个 >= h 的位置
if i == len(r.keys) {
i = 0 // 走到环末尾就绕回起点
}
return r.owners[r.keys[i]]
}
func main() {
r := &Ring{owners: map[int]string{}}
for _, node := range []string{"node-a", "node-b", "node-c"} {
for v := 0; v < 150; v++ { // 每台物理节点 150 个虚拟节点
name := fmt.Sprintf("%s#%d", node, v)
hv := int(crc32.ChecksumIEEE([]byte(name)))
r.keys = append(r.keys, hv)
r.owners[hv] = node
}
}
sort.Ints(r.keys)
fmt.Println(r.Get("user:1001")) // 输出：某台节点名，如 node-b
}
生产环境不建议手写这套结构：并发读写、节点健康检查、权重与副本都容易出错，直接用语言生态里成熟的客户端或代理组件更稳。
小结：取模哈希在节点数变化时几乎全量重排；一致性哈希把节点和 key 放到同一个环上，扩容只迁移约 1/N 的数据，再配合虚拟节点解决倾斜。选型原则是——节点数固定用取模，节点会变用一致性哈希。