什么时候该用一致性哈希#

决策规则： 如果集群成员会变化且节点数在 10 个以上，使用一致性哈希。对于规模固定的小集群，hash % N 已经足够；对于节点数少于 20、但需要频繁扩缩容的微型集群，最高随机权重哈希可能更简单。

问题根源：为什么 hash % N 无法平滑扩容#

最简单的数据分配方式是：

1
server = hash(key) % N

N 固定时，键可以均匀分布，查询复杂度也是 O(1)。但 N 一旦变化，几乎所有键都会被重新映射：

1
增加一台服务器（12 → 13）：12/13 = 92% 的键需要重新映射
2
增加一台服务器（100 → 101）：100/101 = 99% 的键需要重新映射

这种大规模重映射会触发级联故障：每个被重新映射的键都会变成缓存未命中，后端存储被瞬间压垮，最终造成超时和用户可见的错误。

一致性哈希如何工作#

服务器和键都会被哈希到一个固定大小的环上，位置范围为 0 到 2³²−1。Amazon 的 Dynamo 论文将这种结构描述为高可用键值存储的经典分区机制。

查找某个键所属的服务器只需三步：

1. 对键做哈希，将它映射到环上的一个位置。
2. 从该位置开始沿顺时针方向行走。
3. 遇到的第一台服务器就是这个键的所有者。

当一台服务器加入环上的 P 点时，只有原本属于顺时针方向下一台服务器的部分键需要迁移到 P；其他键仍留在原服务器上。假设共有 K 个键、N 台服务器，增加一台服务器时大约只会重映射 K/(N+1) 个键——这已经是理论上的最小值。相比之下，hash % N 会重映射全部键中的 N/(N+1)。

1
哈希环顺序：Server A (0x1A3F) → Server B (0x5E02) → Server C (0x9B7D) → Server A
2

3
user:42    (0x3C11) ──顺时针──> Server B
4
session:99 (0x7F20) ──顺时针──> Server C
5
cart:17    (0x0E55) ──顺时针──> Server A（越过环尾后回绕）

下面是一个朴素的 Go 实现：

1
package chash
2

3
import (
4
  "hash/crc32"
5
  "sort"
6
  "sync"
7
)
8

9
type Ring struct {
10
  mu     sync.RWMutex
11
  nodes  map[uint32]string // 哈希位置 → 节点 ID
12
  sorted []uint32          // 用于二分查找的有序位置
13
}
14

15
func New() *Ring {
16
  return &Ring{nodes: make(map[uint32]string)}
17
}
18

19
func (r *Ring) GetNode(key string) string {
20
  r.mu.RLock()
21
  defer r.mu.RUnlock()
22
  if len(r.sorted) == 0 {
23
    return ""
24
  }
25

26
  h := crc32.ChecksumIEEE([]byte(key))
27

28
  // 二分查找：找到第一个大于等于 h 的节点位置
29
  idx := sort.Search(len(r.sorted), func(i int) bool {
30
    return r.sorted[i] >= h
31
  })
32

33
  // 超过环尾时回绕到环首
34
  if idx == len(r.sorted) {
35
    idx = 0
36
  }
37

38
  return r.nodes[r.sorted[idx]]
39
}
40

41
func (r *Ring) AddNode(nodeID string) {
42
  r.mu.Lock()
43
  defer r.mu.Unlock()
44
  h := crc32.ChecksumIEEE([]byte(nodeID))
45
  r.nodes[h] = nodeID
46
  r.sorted = append(r.sorted, h)
47
  sort.Slice(r.sorted, func(i, j int) bool { return r.sorted[i] < r.sorted[j] })
48
}

这个实现的问题在于：只有 3 个物理节点时，环上也只有 3 段。哈希函数几乎不可能让节点等距分布，因此负载会很不均匀，例如一台节点处理 60%，另一台却只处理 10%。

虚拟节点：让负载均匀分布#

生产系统会把每台物理服务器映射到环上的多个位置，通常每台设置 150～300 个虚拟节点。Dynamo 为了同样的目的引入了这种“每台物理节点持有多个 token”的设计。它能抚平分布差异，避免朴素实现中单一位置造成的负载倾斜。

没有虚拟节点时，3 台物理服务器只会产生 3 个环上位置。哈希函数很难把它们均匀分布在 40 多亿个位置上，于是负载方差可能非常大：一台处理 60%，另一台只有 10%。加入虚拟节点后，每台物理服务器都会在环上拥有许多副本。

1
朴素哈希环：3 个物理节点，3 个位置
2
A（约 60%） → B（约 30%） → C（约 10%） → A
3

4
虚拟节点哈希环：3 个物理节点 × 每台 150 个虚拟节点
5
A1…A150、B1…B150、C1…C150 均匀散布在整个环上

对于一个拥有 10 台物理节点、每台 150 个虚拟节点的集群：

• 环上共有 1,500 个位置。
• 每台物理节点占据约 150 个位置。
• 键会均匀分布到全部 150 个位置上。
• 每个位置大约处理 0.1% 的键。
• 标准差约为 4%，属于较好水平；目标通常是 ±4%～5%。

下面是带虚拟节点的 Java 实现：

1
import java.nio.charset.StandardCharsets;
2
import java.util.*;
3
import java.util.zip.CRC32;
4

5
public class ConsistentHashRing {
6
    private final SortedMap<Long, String> ring = new TreeMap<>();
7
    private final int vnodes;
8

9
    public ConsistentHashRing(int vnodeCount) {
10
        this.vnodes = vnodeCount;
11
    }
12

13
    private long hash(String key) {
14
        CRC32 crc = new CRC32();
15
        crc.update(key.getBytes(StandardCharsets.UTF_8));
16
        return crc.getValue();
17
    }
18

19
    public void addNode(String nodeId) {
20
        for (int i = 0; i < vnodes; i++) {
21
            String vnode = nodeId + ":" + i;
22
            ring.put(hash(vnode), nodeId);
23
        }
24
    }
25

26
    public void removeNode(String nodeId) {
27
        for (int i = 0; i < vnodes; i++) {
28
            ring.remove(hash(nodeId + ":" + i));
29
        }
30
    }
31

32
    public String getNode(String key) {
33
        if (ring.isEmpty()) return null;
34

35
        long h = hash(key);
36
        SortedMap<Long, String> tail = ring.tailMap(h);
37
        long nodeHash = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
38
        return ring.get(nodeHash);
39
    }
40
}

每台物理节点会向环中加入 vnodes 个条目；移除物理节点时，也会一次性移除它的全部虚拟副本。

有限负载一致性哈希#

Google 在 2016 年提出了一项改进：把每个节点能够承载的键数限制在 K/N × (1 + epsilon)。如果一个键被哈希到已经过载的节点，就继续尝试顺时针方向的下一台节点，从而避免任何单个节点成为热点。

实践中可以取 epsilon = 0.25，即每台节点最多容纳理论平均值的 125%。对于一个拥有 100 台节点、1,000 万个键的集群，平均每台节点持有 10 万个键；过载节点最多可以容纳 12.5 万个键，超过后便将键交给顺时针方向的下一台节点。

生产环境检查清单#

• 使用 MurmurHash3、xxHash 或 FNV-1a，而不是 CRC32 或密码学哈希。CRC32 会让连续输入产生聚集，密码学哈希则没有必要。
• 缓存环可以为每台物理节点设置 150～256 个虚拟节点，150 是安全的基线。Cassandra 4.0 起默认使用 16 个，旧版为 256 个；超过 256 后收益会逐渐减小。
• 使用读写锁保护所有哈希环操作。写操作（增加、移除节点）需要阻塞读操作（查找节点）。
• 测试负载分布：采样环上位置并计算标准差，目标为 ±4%～5%。
• 规划重平衡窗口。增加节点会触发约 K/(N+1) 个键迁移，批量扩容应安排在非高峰期。
• 监控单节点热键。一致性哈希分散的是键，而不是访问负载；某个每秒被访问 1,000 次的键仍然只会命中一台节点。
• 优雅处理节点故障：故障节点的键应迁移到顺时针下一台节点；有副本时则迁移到接下来的 N 个副本节点。

1
package consistenthash
2

3
import (
4
    "hash/fnv"
5
    "sort"
6
    "strconv"
7
    "sync"
8
)
9

10
type Ring struct {
11
    mu     sync.RWMutex
12
    vnodes int
13
    slots  []uint32          // 排序后的槽位
14
    owners map[uint32]string // 槽位 → 物理节点
15
}
16

17
func NewRing(vnodes int) *Ring {
18
    return &Ring{vnodes: vnodes, owners: make(map[uint32]string)}
19
}
20

21
func hash(s string) uint32 {
22
    h := fnv.New32a()
23
    _, _ = h.Write([]byte(s))
24
    return h.Sum32()
25
}
26

27
func (r *Ring) AddNode(node string) {
28
    r.mu.Lock()
29
    defer r.mu.Unlock()
30
    for i := 0; i < r.vnodes; i++ {
31
        slot := hash(node + ":" + strconv.Itoa(i))
32
        r.slots = append(r.slots, slot)
33
        r.owners[slot] = node
34
    }
35
    sort.Slice(r.slots, func(i, j int) bool { return r.slots[i] < r.slots[j] })
36
}
37

38
func (r *Ring) GetNode(key string) string {
39
    r.mu.RLock()
40
    defer r.mu.RUnlock()
41
    if len(r.slots) == 0 {
42
        return ""
43
    }
44
    h := hash(key)
45
    // 二分查找：找到第一个大于等于 h 的槽位；没有则回绕到 slots[0]。
46
    idx := sort.Search(len(r.slots), func(i int) bool { return r.slots[i] >= h })
47
    if idx == len(r.slots) {
48
        idx = 0
49
    }
50
    return r.owners[r.slots[idx]]
51
}

1
func (r *Ring) RemoveNode(node string) {
2
    r.mu.Lock()
3
    defer r.mu.Unlock()
4
    keep := r.slots[:0]
5
    for _, s := range r.slots {
6
        if r.owners[s] != node {
7
            keep = append(keep, s)
8
        } else {
9
            delete(r.owners, s)
10
        }
11
    }
12
    r.slots = keep
13
    // 删除操作会保留原有顺序，因此无需重新排序。
14
}

1
func TestRing_LoadDistribution(t *testing.T) {
2
    r := NewRing(150) // 150 个虚拟节点是生产环境中的常用平衡点
3
    nodes := []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}
4
    for _, n := range nodes {
5
        r.AddNode(n)
6
    }
7

8
    counts := make(map[string]int)
9
    const N = 1_000_000
10
    for i := 0; i < N; i++ {
11
        counts[r.GetNode(strconv.Itoa(i))]++
12
    }
13

14
    expected := float64(N) / float64(len(nodes))
15
    var sumSqDiff float64
16
    for _, c := range counts {
17
        d := float64(c) - expected
18
        sumSqDiff += d * d
19
    }
20
    stdDev := math.Sqrt(sumSqDiff/float64(len(nodes))) / expected
21
    if stdDev > 0.06 { // 6%：对于 10 个节点、每个 150 个虚拟节点已经较为宽松
22
        t.Errorf("load distribution stddev %.4f > 0.06; check vnode count", stdDev)
23
    }
24
}

1
type RebalanceEvent struct {
2
    Type       string // "node_added" | "node_removed"
3
    Node       string
4
    Migrated   int    // 迁入或迁出的键数量
5
    OccurredAt time.Time
6
}
7

8
// AddNodeWithEvent 包装 AddNode，并在哈希环形成新布局后发送事件。
9
func (r *Ring) AddNodeWithEvent(node string, sink chan<- RebalanceEvent) {
10
    r.AddNode(node)
11
    sink <- RebalanceEvent{
12
        Type: "node_added", Node: node, OccurredAt: time.Now(),
13
    }
14
}

1
ring:
2
  vnodes_per_node: 150          # 150 = 均衡缓存环；16 = Cassandra 风格
3
  hash_function: murmur3        # CRC32 会让连续键产生聚集
4
  rebalance_batch_size: 100     # 拓扑变化时允许的最大并发迁移数
5
  rebalance_off_peak_only: true # 业务高峰期间跳过重平衡

Jump Consistent Hash：当哈希环显得过重#

Lamping 和 Veach 于 2014 年在 Google 发表了 Jump Consistent Hash。整个算法只有 7 行，不分配内存，查询吞吐量比基于哈希环的实现高 5～10 倍。

它的限制是只支持从 0 到 N−1 连续编号的桶。假设有 100 个桶，你无法单独移除 7 号桶而不重新编号，因为算法假定桶 ID 连续。

它的数学原理是一段概率游走：桶数量从 1 增长到 N 的过程中，算法使用由键决定的确定性随机序列，判断这个键是否“跳到”新桶。期望跳转次数为 O(ln N)，所以即使有 1,000 个桶，循环通常也只执行约 5 次。

1
// JumpHash 为给定的键返回 [0, numBuckets) 范围内的桶编号。
2
// 来源：Lamping & Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm" (2014)
3
func JumpHash(key uint64, numBuckets int32) int32 {
4
    var b, j int64 = -1, 0
5
    for j < int64(numBuckets) {
6
        b = j
7
        key = key*2862933555777941757 + 1
8
        j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
9
    }
10
    return int32(b)
11
}

当桶只会追加、不会任意删除时，例如分片数据库的 shard ID，或手动重平衡的 Kafka partition ID，并且你需要亚微秒级查询，适合使用 Jump Hash。节点可能故障、需要从任意位置替换时则应避免使用，因为重新编号的成本会抵消这个算法的简洁优势。Google 在节点 ID 稳定的内部桶分配层中使用了 Jump Hash。

真实系统中的调优：Memcached、DynamoDB 与 Cassandra#

后端工程师常见的三种生产级哈希环，实际差异比教科书描述得更大。它们的调优选择也揭示了各自真正优化的目标。

Memcached（libketama）： 每台节点使用 160 个虚拟节点，并以 MD5 派生 32 位位置。pylibmc、spymemcached 和 mcrouter 中的 libketama 算法早于有限负载一致性哈希，因此不会限制节点负载，热键落在哪里就会一直打到哪里。生产部署通常会在每个应用服务器上增加一级进程内 LRU，在进入哈希环查找之前先吸收热键流量。Twemproxy 和 mcrouter 都实现了兼容 libketama 的分布方式，从而让不同客户端库做出一致的路由决定。

DynamoDB： 内部实现未公开，但最初的 Dynamo 论文描述了每台节点 128 个 token、沿顺时针方向保存 3 个副本的方案。当前托管版 DynamoDB 完全隐藏了哈希环；当某个分区持续超过 3,000 RCU 或 1,000 WCU 时，自适应容量会自动拆分热分区。换句话说，AWS 通过把哈希环做成黑盒并提供自动拆分分区的 OnDemand 模式，让用户不再需要调整虚拟节点。

Cassandra： 4.0 将每台节点的虚拟节点数量从 256 降到了 16。原因是重平衡成本：虚拟节点越多，引导新节点加入集群所需的时间会超线性增长，因为流式传输子系统必须为每一组“源虚拟节点—目标虚拟节点”协商数据传输。在 100 节点集群中，每台使用 256 个虚拟节点时，一次节点引导会涉及 25,600 个源数据范围；降低到 16 后只涉及 1,600 个。数据仍然是分散的，但引导过程从数天缩短到数小时。

有限负载与“两次随机选择”#

这两种算法都在解决朴素一致性哈希负载不均的问题，但权衡不同。如何选择取决于你能否接受逐键状态，以及尾延迟目标有多严格。

有限负载一致性哈希（Mirrokni 等，Google，2016）： 把每个节点限制在 K/N × (1 + epsilon) 个键；溢出后沿顺时针方向寻找下一台节点。每个请求的成本是一次哈希环查询，最坏情况下再进行最多 1/epsilon 次顺时针探测。epsilon = 0.25 时，最坏会多探测 4 次；负载率低于 80% 时，实践中的平均值约为 1.05 次查询。

两次随机选择（Power of Two Choices）： 使用两个独立哈希函数为键选择两个候选节点，然后选择负载较低的一个，成本永远是两次查询。相比随机放置，它能显著降低方差：最大负载从 O(log N / log log N) 降至 O(log log N)。这一思想源于 Mitzenmacher 1996 年的工作，也被应用在 Maglev 和 Vimeo 的 Vitess 中。

下面是 50 节点哈希环在每秒 100 万个键下的一组具体数据：

当键的写入频率远高于读取频率时，有限负载方案更合适，因为计数器只在插入键时更新，而不是每次查询都更新。当读流量占主导，并且你希望成本稳定为两次查询时，两次随机选择更合适。当你控制数据平面，例如 Google 的 L4 负载均衡器，并且能够承担拓扑变化时重建查找表的成本，Maglev 更合适。

下面是在虚拟节点哈希环上实现的最小“两次随机选择”节点选择器。h1 和 h2 使用不同的种子，使两次结果同时碰撞的概率很低：

1
type LoadAwareRing struct {
2
    *Ring
3
    load map[string]*atomic.Int64 // 节点 → 当前负载键数量
4
}
5

6
func (r *LoadAwareRing) PickNode(key string) string {
7
    a := r.GetNode(key + ":a")
8
    b := r.GetNode(key + ":b")
9
    if r.load[a].Load() <= r.load[b].Load() {
10
        return a
11
    }
12
    return b
13
}

对 r.load 的两次读取可能与并发更新发生竞争，但最坏的结果只是选到略差的节点，不会选到不安全的节点。若需要严格记账，可以把原子计数器换成分片计数器，同时接受额外的缓存行抖动。

常见问题#

参考资料与出处#

• BackendBytes Engineering Team：Consistent Hashing: The Algorithm Behind Every Scalable Distributed System
• David Karger 等：Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web（1997）
• Giuseppe DeCandia 等：Dynamo: Amazon’s Highly Available Key-value Store（2007）
• Michael Mitzenmacher、Rasmus Pagh、Stefan V. Tetali 等：Consistent Hashing with Bounded Loads
• John Lamping、Eric Veach：A Fast, Minimal Memory, Consistent Hash Algorithm
• Apache Cassandra：Token allocation