← 全部文章ENGINEERING NOTES

十几行 Go 实现加权 Rendezvous Hash:不存映射表的 sticky 路由

本文目录
  1. 为什么不用取模
  2. 代码
  3. 为什么成立
  4. 一个坑:FNV 的尾部扩散很弱
  5. 小结

cpa-plugin-key-chain-router(下文简称 KCR)是我给 CLIProxyAPI 写的路由插件,负责为每个请求挑一个上游 credential。其中 sticky 策略的要求是:同一个 session 尽量一直落在同一个 credential 上,好让上游的提示词缓存命中;同时还要按权重分流,而且插件里不想维护一张 session → credential 的映射表。

这篇只讲它背后的那十几行代码:加权 Rendezvous Hash。

为什么不用取模

最直接的做法是 hash(session) % n。问题在于 n 一变,几乎所有 session 都会换到别的 credential 上,缓存全部失效。一致性哈希环可以解决这个问题,但要维护环和虚拟节点,按权重分流还得调虚拟节点的数量。

Rendezvous Hash(也叫 HRW,最高随机权重)更简单:让每个候选和 key 一起算一个分数,谁分数最高就选谁。没有环,也没有状态。

代码

KCR 里的打分函数:

func rendezvousScoreV4(key string, c *PolicyCandidate) float64 {
	h := fnv.New64a()
	_, _ = h.Write([]byte(key))
	_, _ = h.Write([]byte{0})
	_, _ = h.Write([]byte(c.ID))
	x := h.Sum64()
	u := (float64(x) + 1) / (float64(math.MaxUint64) + 1)
	w := c.Weight
	if w <= 0 {
		w = 1
	}
	return math.Pow(u, 1/float64(w))
}

选择时不是只取第一名,而是把候选整体排序:

sort.SliceStable(cs, func(i, j int) bool {
	if cs[i].Priority != cs[j].Priority {
		return cs[i].Priority > cs[j].Priority
	}
	return rendezvousScoreV4(sticky, cs[i]) > rendezvousScoreV4(sticky, cs[j])
})

sticky 取自请求里的 session_id 或 X-Session-Id 这类头,取不到就退回到下游 API Key 的指纹。中间写入的那个 0 字节是分隔符,避免 "ab"+"c" 和 "a"+"bc" 算出同一个哈希。

为什么成立

增删候选只影响相关的 session。 每个候选的分数只取决于 key 和它自己的 ID。删掉 b,原本 b 得分最高的 session 会改选第二名,其他 session 的第一名不变。新增 d,也只有 d 恰好得分最高的那部分 session 会被分给它。

u^(1/w) 让胜率正比于权重。 把哈希映射成 (0, 1] 上近似均匀的 u,那么 X = u^(1/w) 的分布函数是 P(X ≤ x) = x^w。设总权重为 W,候选 i 胜出的概率是:

∫₀¹ w_i·x^(w_i−1) · ∏_{j≠i} x^(w_j) dx = w_i · ∫₀¹ x^(W−1) dx = w_i / W

这和加权抽样里 Efraimidis–Spirakis 算法用的是同一个技巧。

排序后的顺序本身就是 failover 链。 第一名失败时,KCR 按顺序重试第二名。对同一个 session,这个顺序每次都一样,所以故障转移之后也还是“粘”的。

我用 10 万个 session、权重 1:2:3 的三个候选跑了一下(ID 用插件实际生成的 cand- 加 10 位随机十六进制格式),结果是 16.8% / 35.6% / 47.6%。删掉权重 2 的候选后,被迁走的恰好只有原来属于它的那部分 session。

一个坑:FNV 的尾部扩散很弱

同样的实验,如果把候选 ID 换成 a、b、c,结果会变成 100% 落在权重最大的 c 上。

原因在于 FNV-1a 每吃一个字节,做的是“异或后乘以质数”。如果几个 ID 只在最后一个字节上不同,它们的哈希值只差“质数 × 一个很小的数”。64 位 FNV 的质数约等于 2⁴⁰,所以这几个 u 只在大约第 24 位二进制小数之后才有差别,几乎相等,最后完全由权重决定胜负。前面那组 1:2:3 的结果偏离理论值约 2 个百分点,也是同一个原因。

KCR 生成的 ID 前缀之后就是随机字符,所以生产环境不会退化成全选一个。但更稳妥的做法是在 Sum64() 之后加一步混合,比如 MurmurHash3 的 fmix64:

func fmix64(x uint64) uint64 {
	x ^= x >> 33
	x *= 0xff51afd7ed558ccd
	x ^= x >> 33
	x *= 0xc4ceb9fe1a85ec53
	x ^= x >> 33
	return x
}

加上之后,单字母 ID 也能得到 16.6% / 33.6% / 49.8%,新增权重 2 的候选时迁走 25.1% 的 session,和理论值 2/8 基本一致。

另外,math.Pow(u, 1/w) 也可以换成 math.Log(u) / w。两者对同一个 key 给出的排序完全相同,后者省掉一次 pow,Ceph CRUSH 的 straw2 用的就是这种写法。

小结

想要“同一个 key 稳定落在同一个节点、节点变动影响最小、还能按权重分流”,而候选又只有几个到几十个时,加权 Rendezvous Hash 往往比一致性哈希环更省事:一个打分函数加一次排序就够了。要注意的只有一点:分数来自哈希,哈希的扩散质量会直接决定分流是否准确。

— 文章结束 —返回文章归档 ↑

讨论

点击后加载 giscus 讨论。登录与发表由你自行操作。