一致性哈希的三种实现与均匀性实测

缓存集群从 10 个节点扩到 11 个，如果分片用 hash(key) % N，命中率会掉到 1/11 左右——几乎所有 key 都换了节点。这是一致性哈希存在的唯一理由：把"扩容一次、缓存全部重建"变成"搬走一小部分 key"。

这篇把三种实现都写出来（可运行），然后在同一套测量方法下对比：100 万个 key、10 个节点下的分布均匀性；10 → 11 和 10 → 9 时的 key 迁移比例；以及查表与建表成本。测量环境：Go 1.25.0 windows/amd64，12 代 i9-12900H（20 逻辑核），go test -bench 单线程。数字是示例环境的结果，方法你可以直接搬走。

一、三种实现

① 经典哈希环 + 虚拟节点

把节点和 key 都映射到同一个 32 位哈希空间（想象成一个圆），key 归属"顺时针方向第一个节点"。

type ringPoint struct { // 环上的一个虚拟节点
	hash  uint32
	owner string
}
type Ring struct{ v []ringPoint }

// murmur3 的 32 位收尾混合：把 crc32 输出里的结构性相关性打散
func fmix32(h uint32) uint32 {
	h ^= h >> 16
	h *= 0x85ebca6b
	h ^= h >> 13
	h *= 0xc2b2ae35
	h ^= h >> 16
	return h
}

func hashKey(s string) uint32 { return fmix32(crc32.ChecksumIEEE([]byte(s))) }

// Add 给一个节点加 vnodes 个虚拟节点：位置是 hash("name#i")
func (r *Ring) Add(name string, vnodes int) {
	for i := 0; i < vnodes; i++ {
		r.v = append(r.v, ringPoint{hashKey(name + "#" + strconv.Itoa(i)), name})
	}
}

// Build 按哈希值排序——这一步才是"环"
func (r *Ring) Build() { sort.Slice(r.v, func(i, j int) bool { return r.v[i].hash < r.v[j].hash }) }

// Get 顺时针找第一个虚拟节点；sort.Search 找不到时返回 len(v)，取模即回绕到环首
func (r *Ring) Get(key string) string {
	h := hashKey(key)
	i := sort.Search(len(r.v), func(i int) bool { return r.v[i].hash >= h }) % len(r.v)
	return r.v[i].owner
}

节点若只在环上占一个点，它负责的弧长就是随机的，10 个节点里最大的那圈可能吃掉大半个 key 空间——我实测 vnodes=1 时最多的节点拿了 96.51% 的 key。虚拟节点就是把这个节点"拆成 v 份"撒到环上，v 越大弧长之和越接近 1/N。

但有个和教科书说法不太一样的地方：虚拟节点数不是决定均匀性的唯一变量，哈希的雪崩性会把偏差锁在一个上限上。同一批 key、同一批节点名，只改虚拟节点键的写法（加 salt）或换哈希函数：

配置	最大偏离	标准差
crc32，vnodes=100（4 个 salt）	1.81~3.28pp	1.08~1.94pp
crc32 + fmix32 / sha256，vnodes=100（salt 0/1）	1.22~2.37pp	0.74~1.26pp
crc32，vnodes=500（4 个 salt）	2.66~5.48pp	1.47~2.59pp
crc32 + fmix32 / sha256，vnodes=500（salt 0/1）	0.50~0.90pp	0.30~0.45pp

看后两行：换成雪崩性好的哈希之后，偏差开始按 1/√v 收敛（vnodes=500 实测标准差 0.30~0.45pp，和 10%/√500 ≈ 0.45pp 对得上）；而用 crc32 原始输出当环锚点，vnodes 从 100 加到 500 偏差不降反升，换个 salt 就从 2.66pp 跳到 5.48pp，fnv1a 32 更差（vnodes=100 时 6.31pp）。原因可以单独量出来：取 7000 个 cache-XX#i 字符串，按哈希高位切 1024 个等宽桶，crc32 的卡方只有 412（自由度 1023），而 crc32+fmix32 是 1009、sha256 前 4 字节是 1040。crc32 不是"太随机"，而是太规整：CRC 是 GF(2) 上的线性变换，结构化输入的输出落在过于规则的格子里，两组规整格子错开就是上面那种 ±3pp 的漂移。所以我现在的默认写法是 fmix32(crc32(x))，环只在节点变更时重建，这点开销可以忽略。

② Jump Consistent Hash

// JumpHash 是 Lamping & Veach 论文附录里的原始实现，key 必须是 64 位哈希
func JumpHash(key uint64, numBuckets int32) int32 {
	var b int64 = -1
	var j int64
	for j < int64(numBuckets) {
		b = j
		key = key*2862933555777941757 + 1
		j = int64(float64(b+1) * (float64(1<<31) / float64((key>>33)+1)))
	}
	return int32(b)
}

func nodeOf(key string, n int32) int32 { // key 先做一次 64 位 FNV-1a
	h := uint64(14695981039346656037)
	for i := 0; i < len(key); i++ {
		h = (h ^ uint64(key[i])) * 1099511628211
	}
	return JumpHash(h, n)
}

十几行、零内存、不用建表。它的数学结构是：从桶 0 开始不断"跳"到更大的候选桶，直到跳出范围，返回最后一次落在范围内的桶号——所以它要求 桶编号必须是连续的一段 0..n-1，你没法问它"从 {a,b,c} 里选一个"。这直接决定了扩缩容语义：

• 加桶（n → n+1）：只有本来就该落到新桶的 key 会动，实测 9.03%（理想 1/11 ≈ 9.09%）。
• 删末尾桶（n → n-1）：只有原来落在最后一个桶的 key 会动，实测 10.04%。
• 删中间节点：桶号必须连续，只能把后面的桶整体前移一位，"编号变了"的桶上的 key 全部重算，实测 48.91% 迁移。

所以 Jump 的正确用法是两级映射：用 Jump 做 key → 分片号（分片数固定，比如 1024，只增不减），再用一张小表做 分片 → 节点；节点上下线只改小表，每个分片对应约 1/1024 的 key，迁移粒度又细又可控——Redis Cluster 那类设计就是这个思路。权重在 Jump 里只能用"重复注册"表达：后端列表里某个节点出现 k 次，它就拿到 k/Σk 的份额。

③ Maglev

Maglev 是 Google 那篇负载均衡器论文里的查表法：先给每个后端生成一个覆盖整张表的置换，再按轮转顺序填一张大小为 M 的查找表；查询就是一次取模 + 一次数组访问。

type Maglev struct {
	table []int32 // 长度 m，值是后端下标
	m     int
}

// hashKey2 是第二把独立哈希：只用一把的话 off 与 skip 会相关，置换质量会变差
func hashKey2(s string) uint32 { // FNV-1a 32
	h := uint32(2166136261)
	for i := 0; i < len(s); i++ {
		h = (h ^ uint32(s[i])) * 16777619
	}
	return h
}

// NewMaglev：m 必须是质数（保证 skip 与 m 互质，置换才能覆盖整张表），且 m > 后端数
func NewMaglev(entries []string, m int) *Maglev {
	n := len(entries)
	perm := make([][]int32, n)
	for i, e := range entries {
		off := int64(hashKey(e) % uint32(m))       // 起点
		skip := int64(hashKey2(e)%uint32(m-1)) + 1 // 步长 1..m-1
		p := make([]int32, m)
		for j := 0; j < m; j++ { // 必须用 int64：j*skip 在 m=65537 时会溢出 int32
			p[j] = int32((off + int64(j)*skip) % int64(m))
		}
		perm[i] = p
	}
	table := make([]int32, m)
	for i := range table {
		table[i] = -1 // -1 表示空槽
	}
	next := make([]int32, n)
	remaining := m
	for remaining > 0 {
		// 关键：每一轮让所有后端依次各占一个槽位，直到表填满
		for i := 0; i < n && remaining > 0; i++ {
			c := perm[i][next[i]]
			for table[c] >= 0 {
				next[i]++
				c = perm[i][next[i]]
			}
			table[c] = int32(i)
			next[i]++
			remaining--
		}
	}
	return &Maglev{table: table, m: m}
}

func (mg *Maglev) Get(key string) int32 { return mg.table[hashKey(key)%uint32(mg.m)] }

我第一版把"每一轮让所有后端各占一个槽位"写成了"每个槽位挑一个后端"，结果是 0 号后端把整张表占满——实测 100.00% 的 key 全落在 cache-00，均匀性表里一眼就能看出来。填表循环的写法就是它的全部正确性所在。三个要点：M 取质数，否则 skip 与 M 不互质、置换覆盖不满整张表、会留空槽；M 要远大于后端数（65537 是常见选择，M 越大扰动越小但表越大）；它同时追求均匀和最小扰动——轮转填表让每个后端拿到的槽位数只差 1，实测最大偏离 0.06pp（相对理想份额 10% 就是 0.6%，与论文"偏差在 1% 以内"的说法一致），加一个后端时被重排的槽位只有 9.25%。

二、均匀性实测

测量方法：取 N 个 key 逐个查表，统计每个节点拿到多少，再算"最大偏离"（占比与理想值之差的最大绝对值）和占比的标准差。

func measure(keys, nodes []string, get func(string) string) (minPct, maxPct, dev, stddev float64) {
	counts := make(map[string]int64, len(nodes))
	for _, n := range nodes {
		counts[n] = 0 // 先全部置 0：从 map 里遍历时，吃 0 个 key 的节点会被漏掉
	}
	for _, k := range keys {
		counts[get(k)]++
	}
	ideal, minPct := 100/float64(len(nodes)), math.Inf(1)
	var sum, sq float64
	for _, c := range counts {
		s := float64(c) * 100 / float64(len(keys))
		sum, sq = sum+s, sq+s*s
		minPct, maxPct = math.Min(minPct, s), math.Max(maxPct, s)
		dev = math.Max(dev, math.Abs(s-ideal))
	}
	mean := sum / float64(len(nodes))
	return minPct, maxPct, dev, math.Sqrt(sq/float64(len(nodes)) - mean*mean)
}

100 万个 key（user:0user:999999）分到 10 个节点（cache-00cache-09），理想占比 10.00%。环这里用的是 crc32 原始输出（也就是上面表里 vnodes=100 那一行的条件），换成 fmix32 后偏差会再小一档：

实现	最小占比	最大占比	最大偏离	标准差
环 vnodes=1	0.09%	96.51%	86.51pp	28.84pp
环 vnodes=10	1.41%	49.22%	39.22pp	15.85pp
环 vnodes=50	5.77%	12.24%	4.23pp	1.69pp
环 vnodes=100	6.72%	12.80%	3.28pp	1.94pp
环 vnodes=500	8.06%	12.66%	2.66pp	1.47pp
Jump Consistent Hash	9.95%	10.05%	0.05pp	0.03pp
Maglev（M=65537）	9.94%	10.05%	0.06pp	0.03pp

换成随机十六进制 key（sess:<16 位 hex>）结果几乎一样（环 vnodes=100 是 3.22pp，Jump 0.04pp，Maglev 0.06pp），所以差异不是 key 形态造成的。表里最有信息量的是 vnodes 从 100 加到 500：用 crc32 原始输出时，虚拟节点加 5 倍，最大偏离几乎没动——在这组实测里虚拟节点的收益在 vnodes≈50~100 后就进入平缓区，再往上只是增加内存和建环成本（除非同时把哈希换成雪崩性好的，那时才会继续往 0.45pp 收敛）。

三、扩缩容扰动实测

同一批 key，比较节点集合变化前后 key 的归属，统计需要迁移的比例。理想下界是 1/(n+1) ≈ 9.09%（环同样用 crc32 原始哈希；换成 fmix32 后更均匀，实测迁移比例也会升到约 10.1%，更接近理想值）：

操作	迁移 key 比例	说明
环 vnodes=100：10 → 11	7.05%	新节点接管自己那圈弧
Jump：10 → 11	9.03%	只有落到新桶的 key 会动
Maglev：10 → 11	9.25%	被新后端抢走槽位的旧后端
环 vnodes=100：删中间节点	12.80%	被删节点的弧交给邻居
Jump：删末尾桶（10 → 9）	10.04%	代价最小，但只能删最后一个
Jump：删中间节点（重新编号）	48.91%	桶号必须连续，后面的桶全要挪
Maglev：删中间节点	10.35%	被抢走槽位的旧后端

环的 7.05% 和 12.80% 都不是常数，而是"被增删节点的实际占比"——12.80% 正好是均匀性表里那个最大占比的节点（环 vnodes=100 的最大占比就是 12.80%）。也就是说：环的均匀性差多少，扩缩容的迁移量就偏离理想值多少。想更接近 9.09%，得先解决哈希和虚拟节点数。Jump 的 9.03% 几乎贴着理论下限，代价是只能从末尾增删桶。Maglev 的 9.25%/10.35% 也贴着理想值，它把"均匀"和"最小扰动"做成了构造性质而不是统计性质——这也是它在 L4 负载均衡器里流行的原因（一次内存访问的查表，比环的二分查找更可预测）。

四、查表与建表成本

go test -bench "Benchmark" -benchmem，Go 1.25.0，单线程：

操作	ns/op	B/op	allocs/op
环 Get（100 vnodes，二分查找）	76.25	14	1
Jump Get（fnv64a + 十几行循环）	21.60	0	0
Maglev Get（取模 + 一次数组访问）	26.09	14	1
环建环（10 节点 × 100 vnodes）	168561	90419	3028
Maglev 建表（10 后端，M=65537）	3043011	2974122	24

查表那 1 次分配来自 crc32.ChecksumIEEE([]byte(key)) 里的 []byte 转换（14 B/op）。crc32.Update 也要 []byte，所以想零分配只有两条路：key 全程保持 []byte，或者自己写直接遍历 string 字节的哈希循环——Jump 那行 0 allocs 就是这么来的。多 50ns 不是大事，但每个 key 一个临时 []byte 在高 QPS 下会直接变成 GC 压力，这才是它真正的代价。建表成本则差两个数量级：环 168 µs / 90 KB，Maglev 3.0 ms / 3.0 MB（M=65537），后者还要注意多实例各复制一份。

五、实践里的四件事

缓存命中率就等于"没迁移的比例"。 扩容 10 → 11 时 hash % N 的命中率是 1/11 ≈ 9%；上面三种实现最差的一档（Jump 9.03%）命中率仍有约 91%，环是 100% - 7.05% ≈ 93%。这个差别不是"优化"，是"能不能扛住一次扩容"。

权重是"这台节点比别的能装多少"。 三种实现我实测的结果（权重 4/2/1/1/1/1/1/1/1/1，总和 14，理想是 28.57% / 14.29% / 其余各 7.14%）：环用"虚拟节点数 = 权重 × 500"，相对期望权重的最大偏差 0.76pp；Jump 用"后端列表里重复注册"（14 个桶），0.05pp；Maglev 同样用重复注册（槽位按 ⌈M/n⌉ 分给每个条目），0.05pp。环的权重精度受虚拟节点总数约束，Jump/Maglev 用重复注册反而更精确，代价是后端列表变长、Maglev 建表成本随条目上升。另外注意：调权重也是一次数据迁移，别在高峰做。

热点 key 跟虚拟节点没有关系。 一个 100 万 QPS 的 key 落在哪个节点就压垮哪个节点，虚拟节点加多少都不影响——它只影响"这个节点负责多少 key"，不影响"某个 key 有多热"。热点要靠本地缓存、key 拆分（hotkey#0..n）或按前缀分片解决。一致性哈希管的是"哪些 key 归我"，不是"我这儿每秒多少请求"，这是最常被混淆的地方。

一致性哈希解决的是重分布，不是负载均衡。 上面所有表测的都是 key 数的分布，不是请求数 / CPU / 连接数的分布：key 数完全均匀时请求负载照样可能严重倾斜（访问频率不是均匀分布），节点规格不同还要靠权重。它保证的只有一件事——节点集合变化时尽量少的 key 需要搬家。均衡是另一个问题，得另外解决。

六、选型建议

维度	环 + 虚拟节点	Jump Consistent Hash	Maglev
节点数是否稳定	任意增删	只适合从末尾增删；中间删要重编号	任意增删
加一个节点迁移比例（10→11 实测）	7.05%（≈该节点占比）	9.03%	9.25%
均匀性（实测最大偏离）	2.5~3.3pp（取决于 vnodes 与哈希）	0.05pp	0.06pp
权重	直接支持（虚拟节点数按权重分配）	靠重复注册（建议配两级映射）	靠重复注册
查表成本（实测）	76 ns，二分查找	21.6 ns，零分配	26.1 ns，一次数组访问
建表成本（实测）	168 µs / 90 KB	0	3.0 ms / 3.0 MB
实现复杂度	中：排序 + 二分 + 虚拟节点	极低：约 10 行	中高：置换生成 + 填表
我什么时候用	需要权重、节点任意上下线、key 空间不可控	key → 固定分片数的两级映射	需要 O(1) 可预测查表 + 最小扰动，且能接受建表开销

小结

三种实现的分工很清楚：Jump 最简单、最均匀、查表最快，但被"桶号必须连续"绑住，适合做固定分片数的第一级映射；Maglev 把均匀和最小扰动做成了构造性质，代价是建表和 3 MB 内存；哈希环最灵活（任意增删、权重直观），但均匀性是统计性的，必须自己测虚拟节点数和哈希函数。这次实测最出乎意料的不是三者差距，而是环的偏差主要来自哈希的雪崩性——crc32 直接取 32 位当环锚点时，vnodes 从 100 加到 500，偏差不降反升，换个 salt 就从 2.66pp 跳到 5.48pp。所以无论选哪种，落地前都该做两件事：用真实 key 分布跑一遍均匀性，再跑一遍扩缩容的迁移比例——这两张表几十行代码就能出来，比任何文章里的结论都可靠。