鲁班 - 系统设计大全

19.4 一致性哈希

一句话

一致性哈希把节点和 key 都映射到一个哈希环上，key 顺时针找到第一个节点；增删节点只影响相邻的一段弧，平均只迁移 1/(N+1) 的数据——代价是环的元数据，以及「节点少时分布很不均」。

环：一条规则解决增删

                    hash 空间 [0, 2^64)
                        0
                  ┌─────┴─────┐
             N3 ●─┘           └─● N1
                │     key k     │
                │       ↓       │   k 顺时针遇到的第一个节点 = N1
             N2 ●───────────────┘
                      2^64-1

三条规则：

  1. 每个物理节点用 hash(node_id) 映射成环上的一个（或多个）token；
  2. 每个 key 用 hash(key) 映射到环上一点；
  3. 从 key 的位置顺时针找第一个 token，该 token 所属节点就是它的分片。

增删节点时：

  • 增加节点：新 token 插入环，只接管「它到前一个 token」这段弧上的 key；
  • 删除节点：它的弧交给顺时针后继，其他 key 不动；
  • 迁移量：节点等权时，新增一个节点平均接管 1/(N+1) 的 key。

一个可运行的最小实现

package main

import (
	"fmt"
	"sort"
)

func hash(s string) uint64 {
	var h uint64 = 1469598103934665603
	for i := 0; i < len(s); i++ {
		h ^= uint64(s[i])
		h *= 1099511628211
	}
	// splitmix64 finalizer：避免相似 token 聚簇
	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) *ring {
	r := &ring{}
	for n := 0; n < nodes; n++ {
		for i := 0; i < vnodes; i++ {
			r.toks = append(r.toks, hash(fmt.Sprintf("node-%d#%d", n, i)))
			r.owners = append(r.owners, n)
		}
	}
	idx := make([]int, len(r.toks))
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(a, b int) bool { return r.toks[idx[a]] < r.toks[idx[b]] })
	toks := make([]uint64, len(idx))
	owners := make([]int, len(idx))
	for i, j := range idx {
		toks[i], owners[i] = r.toks[j], r.owners[j]
	}
	r.toks, r.owners = toks, owners
	return r
}

func (r *ring) owner(key string) int {
	h := hash(key)
	i := sort.Search(len(r.toks), func(i int) bool { return r.toks[i] >= h })
	if i == len(r.toks) {
		i = 0 // 绕回环首
	}
	return r.owners[i]
}

func main() {
	const keys = 100000
	three := newRing(3, 1)
	var load [3]int
	for i := 0; i < keys; i++ {
		load[three.owner(fmt.Sprintf("key-%d", i))]++
	}
	fmt.Printf("3 节点 × 1 token：负载份额 %d/%d/%d\n", load[0], load[1], load[2])

	four := newRing(4, 1)
	moved := 0
	for i := 0; i < keys; i++ {
		k := fmt.Sprintf("key-%d", i)
		if three.owner(k) != four.owner(k) {
			moved++
		}
	}
	fmt.Printf("增加第 4 个节点：迁移 %.1f%% 的 key（理想 25%%）\n", float64(moved)*100/keys)
}

输出：

3 节点 × 1 token：负载份额 64729/28251/7020
增加第 4 个节点：迁移 32.9% 的 key（理想 25%）

两个数字都要会读：

  • 负载份额 64.7% / 28.3% / 7.0%：3 个 token 把环切成 3 段，段长随机，所以极不均匀。这不是实现 bug，是「节点少 + 每节点 1 个 token」的固有方差——虚拟节点（19.5）就是治它的。
  • 迁移 32.9%：单次实验偏离 25%，因为新节点的 token 落在哪段弧是随机的；多轮平均会收敛到约 25%（30 轮平均 29.4%，见 19.5 的表）。

⚠️ 哈希函数必须有良好的雪崩性。用 FNV-1a 直接哈希 node-2#0…node-2#9 这类「只差后缀」的 token，值会挤在一起，同一节点的 vnode 聚成一段弧，负载能到 93%/4%/3%（19.5 有这组实测）。要么换 xxHash/MurmurHash，要么加 finalizer。

它到底「一致」在哪

一致性哈希的 consistent 指映射的稳定性，不是 CAP 里的一致性（Consistency）：

「一致」 含义
一致性哈希的 consistent 增删节点时，大多数 key 的映射不变（单调性）
CAP 的一致性 读能否看到最新写（16.2 线性一致性）

两者没有任何关系。一个用一致性哈希分片的缓存，完全可能是最终一致的；一个线性一致的系统，也完全可以不用一致性哈希。

副本怎么放

单副本只解决「数据分到哪」，还要解决「副本放哪」：

key k → N1（主）
      → 顺时针下一个不同物理节点 N2（副本 1）
      → 再下一个 N3（副本 2）

两个细节：

  1. 跳过同一物理节点的多个 vnode：否则 3 副本可能落在同一台机器上；
  2. 机架/可用区感知：顺时针找节点时跳过同机架/同 AZ，直到凑齐副本数（否则机房断电一起挂）。

副本放置本质上是「在环上找一个满足约束的节点序列」，约束包括：不同物理节点、不同机架、不同可用区、不同地域。环只是提供了「从哪开始找」的确定性起点。

与其它「最小迁移」方案对比

方案 增删节点迁移 元数据 查找成本 权重 备注
取模 % N 几乎全部 无 O(1) 无 扩容灾难
一致性哈希（环） 1/(N+1) N × v 个 token O(log(Nv)) ✅ vnode 加权 本文
Rendezvous / HRW 1/(N+1) 无 O(N)（可用树优化） ✅ 加权打分 每个 key 算所有节点分数取最大
Jump Consistent Hash 1/(N+1) 无 O(log N) ❌ 等权 桶必须编号 0..N-1，内存 O(1)
Maglev Hashing 约 1/(N+1) 查找表（大小 M） O(1) ✅ 表内加权 Google 负载均衡器方案

Rendezvous（HRW）哈希

不用环：对每个 key 计算 score = hash(key, node)，选分数最大的节点。

  • 加节点：只有「新节点分数最高」的 key 会迁移，期望 1/(N+1)；
  • 删节点：只有它拥有的 key 迁移；
  • 没有 token 元数据，节点名变化不影响其他节点；
  • 计算要遍历所有节点（O(N)），N 大时用层次结构/树优化。

它的分布比「1 token 的环」更均匀（每个 key 独立比较所有节点，没有弧长方差），所以在节点不多、想省元数据的场景很受欢迎。缺点是每次查找要算 N 次哈希。

Jump Consistent Hash

Lamping 与 Veach（2014）的算法：桶编号 0..N-1，用伪随机跳跃直接算出 key 属于哪个桶。

  • 时间 O(log N)，空间 O(1)；
  • 增删桶只迁移 1/(N+1)；
  • 限制：桶必须连续编号、等权，不能按名字映射，也不支持任意权重。

适合「分片就是编号」的场景（如按 shard id 分库），不适合「节点随时上下线、名字固定」的集群。

Maglev Hashing

Google 的负载均衡器方案：为每个节点生成一张查找表（大小 M），key 哈希到表位置直接查。

  • 查找 O(1)，迁移小；
  • 表大小 M 决定粒度与内存；
  • 支持权重（通过表内条目分配）。

适合 L4 负载均衡这种「超高性能、节点集合偶尔变化」的场景。

反模式

反模式 后果
用 1 个 token/节点就上线 负载 65/28/7，热点片先挂
用弱哈希（无雪崩）生成 token 同节点 vnode 聚簇，虚拟节点失效
用会变的字段（IP、主机名）做节点标识 重启/换 IP 后 token 变化，触发大规模迁移
副本顺时针找节点不跳过同机 3 副本落一台机器，机器挂全丢
节点权重相同但机器规格不同 小机器被压垮，大机器空闲
把一致性哈希当「强一致」 它只解决分布，不解决读写一致性
key 范围查询用一致性哈希 环不保存顺序，范围查询要全环扫描

自检

Q1 3 个节点、每节点 1 个 token，负载是 64.7%/28.3%/7.0%。这是哈希函数坏了吗？

▸ 答案：不是。环被 3 个随机 token 切成 3 段，段长服从随机分布，方差很大；3 段里出现 65%/7% 很常见。哈希函数只保证「token 均匀落在环上」，不保证「少量 token 切出的段等长」。解决办法是每个物理节点放多个虚拟节点（19.5），把「3 段」变成「几百段」，用大数定律把方差压下去。

Q2 一致性哈希增加一个节点，为什么平均只迁移 1/(N+1)？为什么单次可能差很多？

▸ 答案：新节点插入环后只接管「它到前驱」这一段弧；等权节点各占约 1/(N+1) 的环长，所以期望迁移 1/(N+1)。单次实验中，新 token 落在哪段弧是随机的，弧长可能远大于或远小于平均值（示例里是 32.9%）；token 越多（虚拟节点越多），单次波动越小。

Q3 一致性哈希的「一致」和 CAP 的「C」是一回事吗？

▸ 答案：不是。一致性哈希的 consistent 指「增删节点时映射尽量不变」（单调性），是分布算法；CAP 的 C 指「读能否看到最新写」，是一致性模型。两者正交：用一致性哈希分片的系统可以实现任何一致性等级，也可以完全不用一致性哈希而做到线性一致。

Q4 Rendezvous 哈希和一致性哈希环，各自适合什么场景？

▸ 答案：Rendezvous 不需要维护环/token，节点增减只影响自己那部分 key，分布也更均匀（没有弧长方差），但每次查找要算 O(N) 个哈希，适合节点数不多（几十到几百）、想省元数据的场景。环需要维护 token 表，查找 O(log T)，但支持虚拟节点、权重、副本顺时针放置，适合节点多、需要精细控制权重的集群（如 Dynamo/Cassandra 风格）。节点数很大且要 O(1) 查找时，还会选 Maglev 这类查表方案。

Q5 一个 3 副本的环，为什么「顺时针取 3 个节点」不够，还要考虑机架/可用区？

▸ 答案：顺时针取 3 个不同物理节点只保证「不是同一台机器」，但如果这 3 台在同一个机架或同一个可用区，机架断电/ AZ 故障会同时带走 3 副本，等于单副本。副本放置要按故障域排列：先跨机器，再跨机架，再跨可用区/地域；环提供确定性起点，约束由放置策略叠加。这就是「一致性哈希 + 故障域感知」的组合。

跨篇相关：分区键与负载不均见 19.1 分区键设计；取模扩容的迁移代价见 19.2 哈希分区；虚拟节点如何压平方差见 19.5 虚拟节点；有界负载的变种见 19.6 有界负载一致性哈希；节点增减后的数据搬迁见 19.7 再平衡与数据迁移；缓存层的一致性哈希实践见 41.2 本地缓存与分布式缓存；会话粘性路由的实测见 37.2 无状态化；CAP 与一致性的关系见 17.1 CAP 的由来与准确表述；服务发现与客户端路由见 48.2 服务发现。