19.5 虚拟节点
一句话
虚拟节点（vnode）让每个物理节点在环上占多个 token，把「一个节点一段弧」变成「一个节点很多小段」，负载标准差约按
1/√v下降，还能按容量加权；代价是元数据、查找成本与更细的迁移粒度。
为什么需要：1 个 token 的环有多歪
19.4 的实测：3 个节点、每节点 1 个 token，负载是 64.7% / 28.3% / 7.0%。最忙的节点干了 64.7% 的活，最闲的只干 7%——这不是哈希函数坏，而是「3 个随机点切一个圆」的固有方差。
虚拟节点的做法：每个物理节点生成 v 个 token：
物理节点 N1 → hash("N1#0"), hash("N1#1"), …, hash("N1#(v-1)")
物理节点 N2 → hash("N2#0"), hash("N2#1"), …, hash("N2#(v-1)")
环上有 N × v 个 token，key 仍然顺时针找第一个 token，但归属按 token 反查物理节点。于是每个物理节点拥有「v 段小弧」而不是「1 段大弧」，大数定律把方差压下去。
实测：v 从 1 加到 1000
模拟：3 个物理节点，每节点 v 个 token，10 万个 key，30 轮不同随机种子取平均；统计最大/平均负载、变异系数（CV = 标准差/均值），以及增加第 4 个节点时的迁移比例。
package main
import (
"fmt"
"math"
"sort"
)
func hash(s string) uint64 {
var h uint64 = 1469598103934665603
for i := 0; i < len(s); i++ {
h ^= uint64(s[i])
h *= 1099511628211
}
h ^= h >> 30
h *= 0xbf58476d1ce4e5b9
h ^= h >> 27
h *= 0x94d049bb133111eb
h ^= h >> 31
return h
}
type ring struct {
toks []uint64
owners []int
}
func newRing(nodes, vnodes int, salt string) *ring {
type pair struct {
t uint64
o int
}
var ps []pair
for n := 0; n < nodes; n++ {
for i := 0; i < vnodes; i++ {
ps = append(ps, pair{hash(fmt.Sprintf("%s-%d#%d", salt, n, i)), n})
}
}
sort.Slice(ps, func(a, b int) bool { return ps[a].t < ps[b].t })
r := &ring{}
for _, p := range ps {
r.toks = append(r.toks, p.t)
r.owners = append(r.owners, p.o)
}
return r
}
func (r *ring) owner(key string) int {
i := sort.Search(len(r.toks), func(i int) bool { return r.toks[i] >= hash(key) })
if i == len(r.toks) {
i = 0
}
return r.owners[i]
}
func evaluate(before, after *ring, nodes, keys int) (maxRatio, cv, moved float64) {
load := make([]float64, nodes)
m := 0
for i := 0; i < keys; i++ {
k := fmt.Sprintf("key-%d", i)
o := before.owner(k)
load[o]++
if o != after.owner(k) {
m++
}
}
mean := float64(keys) / float64(nodes)
variance := 0.0
for _, v := range load {
if v > maxRatio {
maxRatio = v
}
variance += (v - mean) * (v - mean)
}
return maxRatio / mean, math.Sqrt(variance/float64(nodes)) / mean, float64(m) * 100 / float64(keys)
}
func main() {
const keys = 100000
const trials = 30
fmt.Printf("%-9s %-12s %-12s %-14s\n", "每节点token", "最大/平均", "变异系数", "扩容 3→4 迁移")
for _, v := range []int{1, 10, 100, 1000} {
var sumMax, sumCV, sumMoved float64
for t := 0; t < trials; t++ {
salt := fmt.Sprintf("t%d", t)
b := newRing(3, v, salt)
a := newRing(4, v, salt)
mx, cv, mv := evaluate(b, a, 3, keys)
sumMax += mx
sumCV += cv
sumMoved += mv
}
fmt.Printf("%-9d %-12.2f %-12.2f %-8s\n", v, sumMax/trials, sumCV/trials,
fmt.Sprintf("%.1f%%", sumMoved/trials))
}
}
输出（Go 1.27，Apple M1）：
每节点token 最大/平均 变异系数 扩容 3→4 迁移
1 1.98 0.75 29.4%
10 1.26 0.21 23.6%
100 1.09 0.08 24.8%
1000 1.03 0.02 24.8%
| 观察 | 解释 |
|---|---|
| v=1 → v=10：最大/平均 1.98 → 1.26 | 3 段变 30 段，方差明显下降 |
| v=10 → v=100：1.26 → 1.09 | 继续下降，但收益递减 |
| v=100 → v=1000：1.09 → 1.03 | 只剩 3 个点的随机波动，接近理论下限 |
| CV 0.75 → 0.21 → 0.08 → 0.02 | 与 1/√v 的预测吻合：0.75/√10 ≈ 0.24，0.75/√100 ≈ 0.075 |
| 迁移始终约 24%–29% | 迁移期望由「新增节点份额 1/(N+1)=25%」决定，与 v 无关；v 只是让单次波动更小 |
🔑 v 的收益是降方差，不是降迁移量。迁移量由「新增多少节点」决定；v 让迁移更细、更均匀，但不会让
1/(N+1)变小。
v 选多少
| 规模 | 推荐 v | token 总数 | 查找深度 | 内存量级 |
|---|---|---|---|---|
| 3–10 节点 | 100–200 | 300–2,000 | 9–11 次比较 | KB 级 |
| 10–100 节点 | 100–500 | 1,000–50,000 | 10–16 次 | 百 KB–MB |
| 100–1,000 节点 | 50–200 | 5,000–200,000 | 12–18 次 | MB 级 |
| 超大规模 | 考虑有界负载/固定槽位 | —— | —— | —— |
经验规则：
- 目标是最忙节点不超过平均的 1.1 倍 → 3 个节点要 v≈100；节点越多，v 可以适当减少（总 token 数仍上升）；
- v 翻 4 倍，误差减半（
1/√v）；从 100 加到 400 的收益远小于从 1 加到 10； - 元数据是 O(N×v)：1000 节点 × 1000 vnode = 100 万 token，光 token 表就几十 MB，且每次节点变更都要传播。
权重：让 v 正比于容量
虚拟节点最实用的能力是异构集群：2 倍内存/CPU 的机器拿 2 倍 token，承担 2 倍流量。
// base 是基准 token 数；容量为 maxGB 的机器拿 base 个，容量减半拿一半
func vnodesFor(capacityGB, maxGB, base int) int {
v := base * capacityGB / maxGB
if v < 10 {
v = 10 // 太小会退化成 1 token 的方差
}
return v
}
注意两点：
- 权重不是万能的：热点 key 仍然只落在一个节点，v 再多也拆不开一个 key（要加盐/副本/缓存）；
- 权重变化 = token 变化：扩容一台机器时改 v 会触发迁移；要么滚动调整，要么用固定槽位 + 槽位分配权重。
虚拟节点 vs 固定槽位
两种思路都在「虚拟化物理节点」，但形态不同：
| 维度 | 虚拟节点（动态 token） | 固定槽位（预分片） |
|---|---|---|
| 代表 | Cassandra、Riak 等 | Redis Cluster（16384 槽）、多数分库分表中间件 |
| 槽位/token 数 | 随节点数 × v 动态增长 | 固定（如 16384） |
| 权重 | ✅ v 正比容量 | ⚠️ 需要槽位分配表 |
| 扩容粒度 | 一段弧（可很小） | 一个槽 |
| 元数据 | token 表 O(Nv) | 槽 → 节点表 O(槽数) |
| 查找 | 二分 O(log Nv) | 直接索引 O(1) |
| 迁移控制 | 环上逐段搬 | 按槽搬，易做幂等与断点续传 |
固定槽位相当于「v 已经固定、且所有节点共享同一组槽」的极端虚拟节点；它的好处是映射表简单、迁移单位稳定，坏处是槽数固定后权重调整不灵活。
坑：弱哈希会让虚拟节点失效
把 19.4 代码里的 splitmix64 finalizer 去掉，同一份实验（3 节点、v=10、1 万个 key）得到：
4% / 3% / 93%
原因：node-2#0、node-2#1 … 只差最后一个字符，FNV-1a 的雪崩不足，10 个 token 的哈希值挤在环上相邻的一小段，等于又退回「1 段大弧」。虚拟节点对哈希质量比单 token 更敏感：token 越多、字符串越相似，聚簇越明显。
三条防线：
- 用 xxHash/MurmurHash/CityHash 这类雪崩好的哈希；
- 或者给 FNV/CRC 加一个 splitmix64/murmur 的 finalizer；
- 上线前做一次分布检查：同一节点 v 个 token 的最大间隔 / 平均间隔，异常就换哈希。
反模式
| 反模式 | 后果 |
|---|---|
| 只用 1 个 token/节点 | 负载 65/28/7，热点片先崩 |
| v 设得很小（如 3）却节点很多 | 方差仍大，扩容波动剧烈 |
| 用弱哈希生成 token | 同节点 token 聚簇，v 白加（实测 93%/4%/3%） |
| 用 IP/主机名做 token 标识 | 重启换 IP 触发全环重映射 |
| 认为 v 能解决热点 key | 同一个 key 仍只落一个节点 |
| 一次性加很多节点 | 迁移洪峰打满网络/磁盘 |
| 权重按机器数平均，不看容量 | 小机器过载，大机器空闲 |
| 不做有界负载控制 | 某节点仍可能显著高于平均，需要 19.6 的约束 |
自检
Q1 为什么 v 从 1 加到 10 收益很大，从 100 加到 1000 收益很小？
▸ 答案：负载标准差约与 1/√v 成正比。v 从 1 到 10，√v 从 1 到 3.16，误差降到约 1/3；从 100 到 1000，√v 从 10 到 31.6，只再降约 1/3，但 token 数翻了 10 倍、元数据与传播成本也翻 10 倍。收益递减，所以通常选 100–200 就够，节点少时再加大。
Q2 虚拟节点能减少扩容迁移量吗？
▸ 答案：不能。扩容迁移量由「新增节点应承担多少份额」决定：3→4 是 25%，10→11 是 9.1%，与 v 无关。v 改变的是：① 单次迁移的波动更小；② 迁移粒度更细（一段小弧而不是一大段）；③ 负载更均匀。期望迁移量始终约 1/(N+1)。
Q3 为什么弱哈希会让虚拟节点「白加」？怎么发现？
▸ 答案：虚拟节点的 token 是 hash(node#i)，同一节点的字符串只差后缀；雪崩差的哈希会让这些 token 落在环上相近位置，v 个 token 只覆盖一小段弧，效果等同 1 个 token。发现方法：上线前统计同一节点相邻 token 的弧长分布，若最大/平均间隔远大于 1，或负载分布出现「某节点 90%+」，就是聚簇。修法：换好哈希或加 finalizer，并复测。
Q4 100 台机器、每台 v=1000，token 总数与查找成本是多少？这个配置合理吗？
▸ 答案：token 总数 10 万；二分查找约 log2(100000) ≈ 17 次比较，单次查找仍很快。但 10 万 token 的元数据要存、要随节点变更传播，每次上下线要更新/复制这份表，内存几十 MB 量级。对 100 台机器，v=100–200 通常就能把最大/平均压到 1.1 以内，v=1000 属于过度配置；除非节点频繁小幅变动、需要极平滑的迁移。
Q5 一个异构集群（32C/128G 与 8C/32G 混部），怎么用虚拟节点分配负载？有什么前提？
▸ 答案：按容量比例设 v，例如基准 100，大机器 v=400、小机器 v=100（4:1）。前提：① 负载确实与 CPU/内存成正比（IO/网络瓶颈的机器按瓶颈资源加权）；② 热点 key 不集中在某一台（v 不能拆 key，需要加盐/副本）；③ 节点标识稳定，权重变化走滚动调整，避免一次性大规模迁移；④ 监控实际负载而非只看 token 比例，容量模型会因业务变化失准。
跨篇相关：环的基本规则与迁移量见 19.4 一致性哈希；分区键与热点见 19.1 分区键设计；固定槽位与取模扩容见 19.2 哈希分区；范围分区打散见 19.3 范围分区；有界负载的硬约束见 19.6 有界负载一致性哈希；节点变更后的迁移流程见 19.7 再平衡与数据迁移；缓存分片实践见 41.2 本地缓存与分布式缓存；一致性哈希的会话路由实测见 37.2 无状态化；分布式数据库的 token 方案见 44.19 分布式数据库（待补）。