一致性哈希

一致性哈希解决一个具体问题：⁠成员变化时，如何让大多数 key 保持原来的归属？ 这里的“一致性”描述映射变化的性质，与数据库的线性一致性不是同一个概念。

先把两个层次分开：映射算法回答“现在应该放在哪”；迁移协议保证“从原来的位置搬过去时，读写仍然正确”。修改哈希函数或成员列表不会自动把数据搬过去。

为什么直接取模容易引起大范围重映射

设 bucket = hash(key) % N。从 3 个桶增加到 4 个桶时，同一个哈希值的余数可能改变。例如 5 从桶 2 变成桶 1，6 从桶 0 变成桶 2，而 1 仍在桶 1。不是所有 key 都移动，但变化远多于新桶需要接收的数据。

在哈希值均匀、桶编号保持不变的假设下，从 N 到 N+1，连续 N(N+1) 个整数中只有 N 个保持相同余数，因此约 N/(N+1) 的 key 改变归属。理想的均衡扩容只需让新桶接收约 1/(N+1) 的 key；这就是要缩小的差距。这里计算的是 key 数量，若对象大小不同，字节量并不同比例。

哈希环：归属由顺时针的第一个 token 决定

把哈希空间想象成首尾相接的圆。节点拥有环上的 token，key 的哈希值顺时针遇到的第一个 token 决定其归属；越过最大值后回到最小值。若前一个 token 为 p，当前 token 为 q，通常把区间写成 (p, q]。

为了便于计算，下面使用 0 到 99 的小空间：A、B、C 的 token 分别为 20、60、90。新增 D 的 token 为 40 后，原本归 B 的 (20, 40] 改归 D，其余主归属不变。

查询可以维护一个排序后的 token 数组，用二分查找找到不小于 key 哈希值的第一个 token；如果不存在就选数组首项。必须统一 key 编码、哈希算法、token 排序以及端点规则，否则不同客户端会算出不同归属。

这个例子只讨论单份数据的主归属。复制系统还要选择后续副本，跳过属于同一物理节点的 token，并满足机架或可用区隔离。成员变化可能影响副本集合，即使主归属没有变化，也可能需要补副本。

把边界、回绕和物理副本去重写成代码

以下实现直接接收 0–99 的哈希位置，便于遍历全部位置核对变化。环在初始化时排序，查询用二分定位；相同 token 直接拒绝，避免不同客户端用不同规则处理碰撞。

from bisect import bisect_left

class Ring:
    def __init__(self, entries):
        self.entries = sorted(entries)
        self.positions = [position for position, _ in self.entries]
        if (not self.positions or len(set(self.positions)) != len(self.positions)
                or any(not 0 <= p < 100 for p in self.positions)):
            raise ValueError("需要非空、无重复且位于 0–99 的 token")
        self.node_count = len({node for _, node in self.entries})

    def replicas(self, position, count=1):
        if not 0 <= position < 100 or not 1 <= count <= self.node_count:
            raise ValueError("位置或物理副本数不合法")
        start = bisect_left(self.positions, position)
        result = []
        for step in range(len(self.entries)):
            node = self.entries[(start + step) % len(self.entries)][1]
            if node not in result:
                result.append(node)
                if len(result) == count:
                    return result
        raise AssertionError("有效环应该有足够的物理副本")

before = Ring([(20, "A"), (60, "B"), (90, "C")])
after = Ring([(20, "A"), (40, "D"), (60, "B"), (90, "C")])
assert before.replicas(20) == ["A"]  # 右端点属于当前 token
assert before.replicas(21) == ["B"]
assert before.replicas(99) == ["A"]  # 越过末尾后回绕
moved = [p for p in range(100) if before.replicas(p) != after.replicas(p)]
assert moved == list(range(21, 41))
assert all(after.replicas(p) == ["D"] for p in moved)
assert before.replicas(10, 2) == ["A", "B"]
assert after.replicas(10, 2) == ["A", "D"]
vnodes = Ring([(20, "A"), (40, "A"), (60, "B"), (90, "C")])
assert vnodes.replicas(10, 3) == ["A", "B", "C"]

新增 D 后恰好移动 20 个位置，而不是四节点平均份额 25 个：实际迁移量由 D 插入的位置决定。副本数为 2 时，位置 10 的主节点仍为 A，第二副本却由 B 变成 D。因此只统计主归属变化会漏算副本补齐工作。

最后一条断言确保同一物理节点的两个虚拟 token 不会充当两份独立副本。这个实现只去重物理节点，没有跨机架或可用区约束；若要求故障域分散，选到的后续节点还要继续满足放置策略。成员表更新和数据复制也没有包含在查询函数里，返回 D 不代表 D 已经拥有数据。

新增 D，究竟哪些 key 换了归属？

下面把环展开成按哈希位置排列的格子，便于直接数出变化范围。D 插到 B 前面，只接管 (A,D]；恰好等于 D 的位置归 D，恰好等于 A 的位置仍归 A。调整 token 后对照改变的格子数，可避免把理想均匀份额误当成每次真实插入都精确满足的比例。

虚拟节点：把大区间变成多个小区间

每台物理机器只放一个随机 token，容易出现一台占据很长区间、另一台只占很短区间的情况。让每台机器拥有多个 token，可以把容量拆成许多分散的份额。节点容量不同时，也可以分配不同数量或大小的份额。

虚拟节点降低随机区间大小造成的偏差，但不保证请求负载均匀：一个 key 若占据大部分访问，无论它的哈希多均匀，仍然只落到一个主归属上。更多 token 还会增加路由元数据、区间维护和恢复任务的数量。

工程上有两种不同设计：新增机器时生成新的 token，或者提前建立大量逻辑分区、再把部分分区重新分配给新机器。它们都能细化迁移粒度，但成员变化、token 稳定性和元数据维护方式不同。不要把某个产品某个版本的 vnode 默认数当作算法常数。

Rendezvous Hash：让候选节点逐个竞争

Rendezvous Hash，也叫 HRW，对每个候选节点计算确定性分数：score = H(key, stable_node_id)，选择最大者。实现需要稳定的节点标识、无歧义的输入编码以及分数相同时的确定性排序规则。

为什么成员变化只影响一部分 key？删除节点 X 时，原来赢家不是 X 的 key，其候选分数和赢家都没变；添加 X 时，只有 X 击败原赢家的 key 改变归属。在独立、均匀分数和相同节点权重的理想假设下，新增节点接收的期望份额为 1/(N+1)。

加权不能简单写成“哈希值除以权重后取最大”，那反而会压低大权重节点的分数。一种明确的加权构造是：把每个节点的哈希结果映射为 Uᵢ∈(0,1)，计算 Tᵢ = -ln(Uᵢ) / wᵢ，选择 T 最小的节点，其中 wᵢ>0。因为 P(Tᵢ>t)=exp(-wᵢt)，各独立候选的指数竞争使节点获胜概率为 wᵢ / Σw。这是在给定随机模型下的推导；实际实现还需处理哈希质量与浮点边界。

HRW 不需要哈希环，但仍需要一致的成员列表和权重。朴素实现每次查询遍历 N 个节点，计算成本为 O(N)；“无环状态”不等于“没有集群元数据”。

HRW 的稳定性来自旧候选分数不变

下面使用带长度前缀的 UTF-8 字段编码，避免 ("ab","c") 与 ("a","bc") 拼接后产生相同输入。分数使用 SHA-256，分数碰撞时再按稳定节点 ID 比较；示例展示等权分配，不包含上面的加权变体。

from hashlib import sha256

def encoded(key, node):
    fields = [part.encode("utf-8") for part in (key, node)]
    return b"".join(len(field).to_bytes(4, "big") + field for field in fields)

def winner(key, nodes):
    if not nodes:
        raise ValueError("没有候选节点")
    return max(nodes, key=lambda node: (sha256(encoded(key, node)).digest(), node))

assert encoded("ab", "c") != encoded("a", "bc")
for i in range(5000):
    key = f"order-{i}"
    old = winner(key, ["A", "B", "C"])
    added = winner(key, ["A", "B", "C", "D"])
    assert added == old or added == "D"
    assert winner(key, ["C", "B", "A"]) == old
    removed = winner(key, ["A", "C"])
    assert old == "B" or removed == old

扩容时，旧节点 A、B、C 的分数没有变化，D 只能胜出或不胜出，不会让 A 的 key 无缘无故改归 B。删除 B 时，原先属于 A、C 的 key 仍保持归属。若每次部署重新生成节点 ID、改变 key 编码或哈希种子，这个推理前提就被破坏，即使机器一台未变，也可能大面积重映射。

5000 个样本用于检查实现的这些性质；期望迁移份额 1/4 来自独立均匀分数的模型，不意味着任意 5000 个业务 key 恰好有 1250 个迁移，更不意味着迁移字节或热点请求占比正好四分之一。

Jump Consistent Hash：只记录桶数

Jump Hash 把 key 映射到连续编号的桶 0…N-1。它利用确定性的跳跃过程找到最终桶，不需要保存 token 数组，期望计算量为 O(log N)，算法额外空间为 O(1)。

关键约束是桶编号连续：从 N 增加到 N+1，新增的是末尾桶 N；缩容则移除末尾桶。它并不直接解决“任意物理机器退出且其他机器编号不变”的问题。可以在桶与物理机器之间再加映射层，但这层元数据和迁移策略需要单独设计。算法和完整实现见 Jump Hash 原论文。

选型速查

上述迁移比例都需要均衡等前提。环上只加入一个任意位置的 token，移动多少由实际区间决定，并非固定 1/N。容量权重变化、故障域调整、热点处理也会引入额外迁移。

继续阅读：分片策略讨论选择什么 key；动态再平衡讨论如何安全迁移。

参考

• Dynamo 原论文：分区、虚拟节点与复制的结合。
• Jump Consistent Hash 原论文：连续桶编号下的算法与分析。

Keywords: consistent hashing, hash ring, vnode, rendezvous hashing, HRW, jump hash