在分布式系统中存储海量数据或路由网络请求时，最核心的问题之一是如何决定一条数据或请求映射到哪台机器。
传统的 hash(key) % N 方案虽然简单，但当节点数 $N$ 发生变化（如扩容、缩容或宕机）时，几乎所有数据的映射位置都会改变，引发大量数据迁移、缓存雪崩和集群抖动。
一致性哈希（Consistent Hashing） 解决了这一难题：当节点数发生变化时，平均只有 $K/N$ 的数据需要迁移（其中 $K$ 是总键数，$N$ 是节点数）。该算法广泛应用于请求路由、负载均衡以及分布式存储分片与副本定位。
经典方案的缺陷：取模法的代价
假设集群包含 4 个节点，采用 hash(key) % 4 分配规则：
| key | hash | node |
|---|---|---|
| user:1 | 102 | node-2 |
| user:2 | 203 | node-3 |
| user:3 | 304 | node-0 |
| user:4 | 405 | node-1 |
当新增 1 个节点使得 $N=5$ 时，上述数据的映射结果全部改变。
对于 $N$ 个节点的集群，增加或减少 1 个节点会导致约 $\frac{N-1}{N}$ 比例的键重新映射。随着 $N$ 的增大，失效比例无限趋近于 100%。在成百上千台机器的大规模集群中，这会导致几乎全量的数据重新平衡，带来极大的网络与磁盘 IO 压力。
一致性哈希与 Token Ring
一致性哈希的核心思想是将哈希函数的输出空间映射为一个首尾相接的闭环（Ring）。
基本流程
- 节点映射：对每个节点标识做哈希，将其放置到环上的某个位置。
- 数据映射：对数据的分区键（Partition Key）做哈希，同样映射到环上。
- 顺时针寻址：从数据在环上的位置出发，顺时针方向遇到的第一个节点即为该数据的归属节点。
在分布式数据库 Apache Cassandra 中，该闭环被称为 Token Ring。每个节点被分配一个或多个 Token（即环上的位置），数据按 Partition Key 的哈希值落入对应的 Token 区间。
Cassandra 默认使用 Murmur3Partitioner（org.apache.cassandra.dht.Murmur3Partitioner），输出范围是 $[-2^{63}, 2^{63})$，具有良好的均匀分布特性与较低的碰撞率。
写入与副本定位路径
INSERT INTO users (id, name, email) VALUES (?, ?, ?)
↓
分区键 id 经 Murmur3 哈希得到 token
↓
根据 token 在环上顺时针定位主节点
↓
写入主节点，并按 Replication Factor 依次写入后续 N-1 个副本节点
节点扩缩容与数据迁移
节点增加
当新增 node-D 并落在 node-A 与 node-B 之间时，仅需要将 node-A 到 node-D 区间的数据从 node-B 迁移至 node-D，环上其他节点完全不受影响。
一致性哈希将数据迁移量从 $\frac{N-1}{N}$ 降低到了 $\frac{1}{N}$。扩缩容时仅需在新节点及其相邻节点间传输数据（Streaming）。
节点移除
节点宕机或下线时，原先由该节点负责的区间改由其顺时针方向的后继节点接管。
以 Cassandra 为例，系统配合 Hinted Handoff 机制：若节点短时间内宕机，写入请求由协调节点暂存 Hint，待目标节点恢复后进行回放；若长时间未恢复，则触发全局数据重平衡与修复。
多副本机制（Replication Factor）
一致性哈希天然支持分布式多副本容错。
为保证高可用，数据不仅需要存放在主节点（Primary Replica），还需要复制到多个副本节点（Secondary Replicas）。在 Token Ring 上，选定 Primary Replica 后，沿顺时针方向依次选择后续的 $RF - 1$ 个物理节点放置副本（$RF$ 为 Replication Factor）。
虚拟节点（VNodes）：倾斜问题与性能代价
数据倾斜与虚拟节点
若物理节点数量较少，节点在环上的哈希位置可能分布不均，导致“负载倾斜”——部分节点承担过多数据，而部分节点空闲。
解决方案：为每个物理节点在环上分配多个虚拟节点（Virtual Nodes / VNodes）。
// 物理节点 node-A 在环上拥有多个 Token
token-A0 = hash("node-A#0")
token-A1 = hash("node-A#1")
token-A2 = hash("node-A#2")
引入虚拟节点的优势：
- 负载均衡：虚拟节点数量增多使 Token 在环上的分布更加均匀。
- 异构支持：根据物理机配置调整 VNode 数量，高配机器分配更多 Token。
- 快速故障恢复：节点宕机后，其负载由环上其他多个物理节点共同分担，避免压垮单一后继节点。
传统哈希环的性能瓶颈
在微秒级/纳秒级高吞吐路由场景下，传统哈希环面临以下限制：
- 查找复杂度为 $O(\log(M \times N))$：
- 环上的 Token 通常保存在有序数组或红黑树（TreeMap）中。定位节点需要执行**二分查找（Binary Search）**寻找首个大于等于该哈希值的节点。
- 当物理节点数 $N=100$、每个物理节点分配 $M=256$ 个 VNode 时，环上包含 25,600 个 Token，查找开销显著增加。
- 内存与 CPU Cache 不友好：
- 规模庞大的 Token 数组在二分查找过程中会导致内存跨度跳转，极易引发 CPU Cache Miss，无法使用硬件级的预取（Prefetching）优化。
最小 Go 实现
以下为包含虚拟节点支持的一致性哈希算法实现：
package consistenthash
import (
"hash/crc32"
"sort"
"strconv"
)
// HashFunc 将 []byte 映射到 uint32
type HashFunc func(data []byte) uint32
// ConsistentHash 一致性哈希结构体
type ConsistentHash struct {
hash HashFunc // 哈希函数
replicas int // 每个物理节点的虚拟节点数
keys []int // 环上所有虚拟节点的哈希值（有序）
hashMap map[int]string // 虚拟节点哈希 → 物理节点标识
}
func New(replicas int, fn HashFunc) *ConsistentHash {
if fn == nil {
fn = crc32.ChecksumIEEE
}
return &ConsistentHash{
hash: fn,
replicas: replicas,
keys: []int{},
hashMap: make(map[int]string),
}
}
// Add 添加物理节点，同时注册 replicas 个虚拟节点
func (ch *ConsistentHash) Add(keys ...string) {
for _, key := range keys {
for i := 0; i < ch.replicas; i++ {
virtualKey := strconv.Itoa(i) + key
hash := int(ch.hash([]byte(virtualKey)))
ch.keys = append(ch.keys, hash)
ch.hashMap[hash] = key
}
}
sort.Ints(ch.keys)
}
// Get 返回 key 归属的物理节点标识
func (ch *ConsistentHash) Get(key string) string {
if len(ch.keys) == 0 {
return ""
}
hash := int(ch.hash([]byte(key)))
// 二分查找第一个 ≥ hash 的虚拟节点（顺时针查找）
idx := sort.Search(len(ch.keys), func(i int) bool {
return ch.keys[i] >= hash
})
// 若超出边界则回绕至环首
if idx == len(ch.keys) {
idx = 0
}
return ch.hashMap[ch.keys[idx]]
}
// GetN 返回包含副本在内的 N 个不同物理节点
func (ch *ConsistentHash) GetN(key string, n int) []string {
hash := int(ch.hash([]byte(key)))
idx := sort.Search(len(ch.keys), func(i int) bool {
return ch.keys[i] >= hash
})
if idx == len(ch.keys) {
idx = 0
}
seen := make(map[string]bool)
result := make([]string, 0, n)
for len(result) < n && len(result) < len(ch.hashMap) {
node := ch.hashMap[ch.keys[idx%len(ch.keys)]]
if !seen[node] {
seen[node] = true
result = append(result, node)
}
idx++
}
return result
}
现代工业界衍生算法与演进
为了克服传统哈希环二分查找及难以精确控制迁移的缺点，工业界发展出了多种路由与分片方案。
哈希槽 / 虚拟槽（Hash Slots）
- 典型代表：Redis Cluster（16384 Slots）、Couchbase（1024 vBuckets）
- 核心思路：引入中间解耦层，将映射过程拆分为两步： $$\text{Key} \xrightarrow{\text{固定哈希算法}} \text{Slot ID} \xrightarrow{\text{显式路由表}} \text{Node}$$
机制与路由
- 槽位固定分割：逻辑上将整个空间切分为 $N_{\text{slots}}$ 个固定槽位（如 Redis Cluster 为 $16384 = 2^{14}$）。
- Key 映射到 Slot： $$\text{Slot ID} = \text{CRC16}(\text{key}) \pmod{16384}$$
- Slot 映射到 Node：集群维护一张全局槽映射表。例如 Node A 负责
0~5460，Node B 负责5461~10922，Node C 负责10923~16383。
槽位扩缩容与数据在线迁移（Slot Resharding）
集群在线增减节点时，数据的重新分片（Resharding）是以槽（Slot）为单位在节点间流式传输的，核心分为三个阶段：
- 状态标记（State Marking）：
- 目标节点（Target Node）执行：
CLUSTER SETSLOT <slot> IMPORTING <source_node_id> - 源节点（Source Node）执行：
CLUSTER SETSLOT <slot> MIGRATING <target_node_id>
- 目标节点（Target Node）执行：
- 数据迁移（Data Migration）：
- 源节点循环调用
CLUSTER GETKEYSINSLOT <slot> <count>批量获取该槽位内的 Key。 - 源节点对每个 Key 发起
MIGRATE <target_ip> <target_port> "" 0 <timeout> KEYS key1 key2...，原子化完成序列化、网络传输与目标节点恢复。
- 源节点循环调用
- 状态广播（Epoch Notification）：
- 当槽内所有 Key 迁移完毕，源节点与目标节点向集群广播
CLUSTER SETSLOT <slot> NODE <target_node_id>。 - 配置纪元（
configEpoch）增加，全局节点更新 Slot Mapping Table。
- 当槽内所有 Key 迁移完毕，源节点与目标节点向集群广播
迁移中间态与重定向机制（MOVED vs ASK）
在槽位迁移过程中，客户端访问正在迁移的槽位时，通过 MOVED 和 ASK 重定向实现无缝透明路由：
MOVED重定向（永久指针更新）：- 触发条件：槽位所有权已彻底完成变更（不在本地节点）。
- 客户端行为：重新向目标节点发起请求，并更新客户端本地 Slot Mapping 表缓存。
ASK重定向（临时探针引导）：- 触发条件：槽位处于迁移中间态且目标 Key 已迁至目标节点。
- 客户端行为：先向目标节点发送
ASKING命令（解除目标节点IMPORTING校验锁），再发送读写请求。不会更新客户端本地 Slot Mapping 缓存。
显式手动/工具切槽与非自动计算特性
与一致性哈希环（根据 Node 标识哈希隐式确定区间）不同，Redis Cluster 不会自动计算并重新分配新节点的 Slot。
- 显式控制权：添加新节点后，新节点默认不拥有任何 Slot，必须由外部工具（如
redis-cli --cluster reshard）或 Operator 运维人员显式指定“从哪些旧节点抽出哪些 Slot 划分给新节点”。 - 设计哲学：这种显式切槽策略赋予了运维极高的灵活性（例如按物理机配置硬件异构加权分配槽位），但同时也意味着拓扑再平衡依赖外部编排指令。
极端故障场景：主从全挂时 Slot 的处理机制
如果某个分片（Master 及其所有 Slave 副本）全部宕机挂掉，这部分 Slot 的处理取决于 Redis 的配置与运维干预：
- 默认行为（
cluster-require-full-coverage yes）：- 当检测到有任何一个 Slot 处于无主可用的孤立状态时，整个 Redis 集群拒绝服务，所有读写请求返回
CLUSTERDOWN The cluster is down。 - 设计目的：保证数据强一致性，防止集群在缺失部分数据切片的情况下继续写入脏数据。
- 当检测到有任何一个 Slot 处于无主可用的孤立状态时，整个 Redis 集群拒绝服务，所有读写请求返回
- 高可用开启（
cluster-require-full-coverage no）：- 允许部分 Slot 丢失或不可用，其余正常 Slot 对应的节点继续提供服务。
- 落入失联 Slot 的请求返回报错，但整个集群不宕机。
- 恢复机制：为什么默认只能人工干预（CP 定理选择）：
- 防止数据静默丢失：若 Redis 自动将孤立 Slot 指派给健康节点，会导致 Slot 内原有的历史数据被隐式擦除。Redis 选择抛出
CLUSTERDOWN锁定集群，优先保障数据安全性（偏向 CP）。 - 防止脑裂数据覆盖：主从全挂可能仅为网络分区（Split-Brain），自动重指派极易引发后续多主冲突。
- 恢复路线选择：
- 传统人工恢复：DBA 手动修复/拉起节点恢复备份，或执行
redis-cli --cluster fix/CLUSTER ADDSLOTS强制重指派孤立 Slot（接受失联数据永久丢失以恢复集群服务）。 - 云原生控制面恢复：在 Kubernetes 环境中，由 Redis Operator 监听 Pod 状态，自动重建节点并挂载云盘（PV）载入 AOF 恢复；若物理持久化损坏，由 Operator 自动化脚本发送重指派指令。
- 传统人工恢复：DBA 手动修复/拉起节点恢复备份，或执行
- 防止数据静默丢失：若 Redis 自动将孤立 Slot 指派给健康节点，会导致 Slot 内原有的历史数据被隐式擦除。Redis 选择抛出
工程限制与生产注意事项
- BigKey 阻塞风险：
MIGRATE指令在源节点与目标节点上为单线程同步阻塞操作。若槽内包含超大 Key，可能导致传输期间主线程卡顿乃至触发 Cluster 心跳超时。 - Hash Tag 关联迁移：使用 Hash Tag 时，必须保证同 Tag 的所有 Key 被一次性同步完成，避免打散在不同节点引发事务失效。
Hash Tag 机制
为支持跨 Key 批量操作与事务，当 Key 包含 {...}（如 user:{1001}:profile）时，仅对括号内的子串计算哈希，确保相关联的数据落入同一个 Slot。
package main
import (
"fmt"
"strings"
)
func crc16(key string) uint16 {
var crc uint16 = 0xFFFF
for _, b := range []byte(key) {
crc ^= uint16(b)
for i := 0; i < 8; i++ {
if (crc & 0x0001) != 0 {
crc = (crc >> 1) ^ 0xA001
} else {
crc >>= 1
}
}
}
return crc
}
// GetSlot 获取 key 归属的 Slot ID (支持 Hash Tag)
func GetSlot(key string) uint16 {
start := strings.Index(key, "{")
if start != -1 {
end := strings.Index(key[start+1:], "}")
if end != -1 {
key = key[start+1 : start+1+end]
}
}
return crc16(key) % 16384
}
func main() {
key1 := "user:profile:10086"
key2 := "user:{10086}:profile"
key3 := "user:{10086}:orders"
fmt.Printf("Key: %-25s -> Slot: %d\n", key1, GetSlot(key1))
fmt.Printf("Key: %-25s -> Slot: %d\n", key2, GetSlot(key2))
fmt.Printf("Key: %-25s -> Slot: %d\n", key3, GetSlot(key3))
}
Maglev 算法（Maglev Hashing）
- 典型代表：Google Maglev 四层负载均衡器、Envoy Proxy
- 核心优势：实现真正的 $O(1)$ 查找，具备良好的均匀度与防抖能力。
算法流程
预先生成大小为质数 $M$ 的查找表（Lookup Table，例如 $M = 65537$）：
- 偏好序列生成：对每个节点 $i$，利用两个哈希函数生成在 $[0, M-1]$ 上的全排列： $$P_i[j] = (offset_i + j \times skip_i) \pmod M$$ $$offset_i = h_1(N_i) \pmod M, \quad skip_i = (h_2(N_i) \pmod{M - 1}) + 1$$
- 轮流抢占填表：各节点按其偏好序列轮流填充 Lookup Table，直至全表填满。
- 定位寻址：路由时直接通过 $\text{Hash}(\text{key}) \pmod M$ 访问查找表，瞬间完成节点检索。
package main
import "fmt"
type Maglev struct {
m int // 查找表大小 (质数)
nodes []string // 后端节点
lookupTable []int // 查找表
}
func NewMaglev(nodes []string, m int) *Maglev {
mag := &Maglev{m: m, nodes: nodes}
mag.populate()
return mag
}
func hashSeed(node string, seed uint64) int {
var h uint64 = seed
for _, c := range []byte(node) {
h = (h ^ uint64(c)) * 1099511628211
}
return int(h)
}
func (m *Maglev) populate() {
n := len(m.nodes)
permutation := make([][]int, n)
for i, node := range m.nodes {
offset := hashSeed(node, 1337) % m
if offset < 0 {
offset += m
}
skip := (hashSeed(node, 42) % (m - 1)) + 1
if skip < 0 {
skip += m - 1
}
perm := make([]int, m)
for j := 0; j < m; j++ {
perm[j] = (offset + j*skip) % m
}
permutation[i] = perm
}
m.lookupTable = make([]int, m)
for i := range m.lookupTable {
m.lookupTable[i] = -1
}
next := make([]int, n)
filled := 0
for filled < m {
for i := 0; i < n; i++ {
c := permutation[i][next[i]]
for m.lookupTable[c] >= 0 {
next[i]++
c = permutation[i][next[i]]
}
m.lookupTable[c] = i
next[i]++
filled++
if filled == m {
break
}
}
}
}
func (m *Maglev) GetRoute(key string) string {
hashVal := hashSeed(key, 9999) % m
if hashVal < 0 {
hashVal += m
}
return m.nodes[m.lookupTable[hashVal]]
}
最高随机权重算法（Rendezvous Hashing / HRW）
- 原理：针对 key 遍历所有节点 $N_i$，计算得分 $\text{Score}_i = \text{hash}(key + N_i)$，选取得分最高的节点。
- 特点：无全局状态（无需环或槽位表），节点变动时具备最小迁移特性，但节点数量极大时计算耗时更高。
跳跃一致性哈希（Jump Consistent Hash）
- 典型代表：Google 内存分片工具
- 原理：摒弃哈希环与虚拟节点，采用线性同余伪随机数生成器与概率反解推演节点跳转位置。时间复杂度平均为 $O(\ln N)$。
在桶数从 $n$ 扩充到 $n+1$ 时，要求概率为 $\frac{1}{n+1}$ 的键跳槽到新桶 $n$。利用概率公式推演临界点：
$$j = \lfloor (b + 1) \cdot \frac{1}{r} \rfloor$$
算法仅用数行位运算即可完成推演：
- 核心优势：零内存占用，计算速度极快。
- 致命约束：节点 ID 必须严格连续（$0, 1, \dots, N-1$），仅支持尾部追加或缩减，不支持随机删除。
package main
import (
"fmt"
)
// JumpHash 返回 key 对应的节点 ID (0 到 numBuckets-1)
func JumpHash(key uint64, numBuckets int32) int32 {
var b int64 = -1
var j int64 = 0
for j < int64(numBuckets) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) * (float64(uint64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}
func main() {
numBuckets := int32(5)
sessionKeys := []uint64{10086, 123456789, 987654321}
fmt.Println("--- 初始 5 个节点时的会话路由 ---")
for _, key := range sessionKeys {
fmt.Printf("Key: %10d -> Node: %d\n", key, JumpHash(key, numBuckets))
}
numBuckets = 6
fmt.Println("\n--- 尾部扩容到 6 个节点时的会话路由 ---")
for _, key := range sessionKeys {
fmt.Printf("Key: %10d -> Node: %d\n", key, JumpHash(key, numBuckets))
}
}
算法方案对比与选型
| 算法 / 机制 | 代表系统 | 时间复杂度 | 内存开销 | 核心特性 / 适用场景 |
|---|---|---|---|---|
| 一致性哈希环 | Cassandra, DynamoDB | $O(\log(M \times N))$ | 中等 | 无中心节点，天然支持多副本放置，适用于分布式存储 |
| 虚拟槽 (Hash Slots) | Redis Cluster, Couchbase | $O(1)$ 查表 | 极小 | 映射关系解耦，支持显式槽位迁移与倾斜调整 |
| Maglev Hashing | Google Maglev, Envoy | $O(1)$ 直查 | 较大（Lookup Table） | 极抗节点抖动，支持权重分配，适用于网关与 LB |
| HRW (Rendezvous) | Cache Clusters | $O(N)$ | 无 | 无状态，无全局表格，适用于节点较少的场景 |
| Jump Consistent Hash | Google 内核工具 | $O(\ln N)$ | 零内存 | 速度极快，但要求节点 ID 严格连续，仅支持尾部扩缩容 |
核心结论
- 有状态分布式存储（如 Cassandra、Redis Cluster）：选型偏向一致性哈希环或虚拟槽，以便于管理数据副本和进行连续 Range / Slot 级别的数据流式迁移。
- 无状态网络路由 / 负载均衡（如 Maglev、Jump Hash）：追求极致的 $O(1)$ 查表与低内存消耗，用公式推演或提前构建的静态表取代复杂的动态拓扑维护。