计算机基础手册分布式系统

一致性哈希与分片：数据该放在哪台机器上¶

一个 KV 缓存集群扩容一台机器，如果用取模分片，本章实测有 88% 的键要换地方——缓存全部失效，后端瞬间被打穿。一致性哈希把这个数字降到理论最优的 11%。这一章讲清楚分片的三种做法（取模、一致性哈希、最高随机权重）、虚拟节点解决的是什么问题、"有界负载"怎么在亲和性和均衡之间取舍，以及这些东西在推理系统里的落点：前缀缓存路由、分布式 KV 存储、专家并行的专家分布。

自测：能答上来就可以跳过本章

用 hash(key) % n 分片，把机器从 8 台加到 9 台，大约多少比例的键要迁移？理想情况是多少？
一致性哈希为什么需要虚拟节点？虚拟节点太少和太多各有什么问题？
一致性哈希怎么处理"某个键特别热"造成的倾斜？
最高随机权重（rendezvous hashing）和一致性哈希比，好在哪？
推理系统里哪些地方用到了这些？

自测参考答案（先自己答，再展开对照）

取模分片要迁移约 88.8%（本章实测）——因为除数变了，几乎所有键的归属都变了。理想情况只需要迁移 1/9 ≈ 11.1%：新机器该拿走的那一份。
一台机器在环上只放一个点时，各机器之间分到的弧长差别很大，本章实测最重的机器是平均的 2.34 倍、最轻的只有 0.49 倍。每台机器放多个虚拟节点，相当于多次采样，负载被抹平：100 个虚拟节点时最重 1.24 倍，500 个时 1.05 倍。太多的代价是内存和查找成本（环上的点数 = 机器数 × 虚拟节点数），以及扩缩容时要更新更多点。
单靠哈希解决不了：热键的哈希值是固定的，它永远落在同一台。办法是有界负载——沿环顺延到下一台没超过负载上限的机器。上限越紧，负载越均衡，但亲和性（还去原来那台）越差，本章实测上限设成平均的 1.25 倍时亲和性还有 91%，设成 1.05 倍就只剩 79%。
不需要环和虚拟节点，实现只有几行；负载天然均匀（本章实测最重 1.024 倍）；按权重分配很自然；删除一台机器时只有它的键会迁移。代价是每次路由要对所有候选机器算一次哈希，机器多时比环的二分查找慢，适合候选集不大的场景（副本选择、几十台机器的缓存集群）。
前缀缓存的缓存感知路由（同一会话/同一前缀发给同一实例）、分布式 KV 存储（Mooncake Store 这类按 key 分片的 KV 池）、专家并行里专家到 GPU 的映射、以及任何"把请求按某个 ID 粘到固定实例"的场景（多轮对话、LoRA 适配器亲和）。

取模分片的问题¶

最朴素的分片：节点 = hash(key) % n。它的问题只有一个，但很致命：

modulo.py

# 取模分片：加一台机器，多少个键要换地方？
import hashlib


def h(key):
    return int.from_bytes(hashlib.blake2b(key.encode(), digest_size=8).digest(), "big")


keys = [f"session-{i}" for i in range(100000)]
print("机器数变化    需要迁移的键")
for n in (4, 8, 16, 32):
    moved = sum(1 for k in keys if h(k) % n != h(k) % (n + 1))
    print(f"{n:3d} -> {n + 1:3d}    {moved / len(keys):6.1%}")
print("\n理想情况：加一台机器只需要迁移 1/(n+1)：", ", ".join(f"{1 / (n + 1):.1%}" for n in (4, 8, 16, 32)))

输出

机器数变化    需要迁移的键
  4 ->   5     80.2%
  8 ->   9     88.8%
 16 ->  17     94.2%
 32 ->  33     97.0%

理想情况：加一台机器只需要迁移 1/(n+1)： 20.0%, 11.1%, 5.9%, 3.0%

除数一变，几乎所有键的归属都变了。对缓存集群来说，这意味着扩容瞬间缓存命中率归零，所有请求穿透到后端；对有状态的存储来说，意味着要搬运几乎全部数据。

一致性哈希¶

把哈希值域想象成一个环（0 到 2^64）。每台机器在环上占若干个点，每个键也哈希到环上一点，顺时针找到的第一个机器点就是它的归属。加一台机器时，它只从环上相邻的机器手里接过一段弧，其他键不动。

先动手感受一下：加一台机器要搬多少 key，虚拟节点数又是怎么把负载拉平的。

ring.py

# 一致性哈希环：每台机器在环上放 vnodes 个虚拟节点，键顺时针找到的第一个虚拟节点就是它的归属
import bisect
import hashlib
from collections import Counter


def h(s):
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")


class Ring:
    def __init__(self, nodes, vnodes=1):
        self.vnodes = vnodes
        self.points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
        self.keys = [p for p, _ in self.points]

    def route(self, key):
        i = bisect.bisect(self.keys, h(key))
        return self.points[i % len(self.points)][1]


keys = [f"session-{i}" for i in range(100000)]
print("每台机器的虚拟节点数   负载最重/最轻   加一台机器要迁移的键")
for vnodes in (1, 10, 100, 500):
    before = Ring([f"node{i}" for i in range(8)], vnodes)
    after = Ring([f"node{i}" for i in range(9)], vnodes)
    load = Counter(before.route(k) for k in keys)
    moved = sum(1 for k in keys if before.route(k) != after.route(k))
    hi, lo = max(load.values()), min(load.values())
    print(f"{vnodes:12d} {hi / (len(keys) / 8):16.2f} / {lo / (len(keys) / 8):.2f} {moved / len(keys):14.1%}")
print("\n加第 9 台机器时，理想的迁移比例是 1/9 =", f"{1 / 9:.1%}")

输出

每台机器的虚拟节点数   负载最重/最轻   加一台机器要迁移的键
           1             2.34 / 0.49           8.8%
          10             1.20 / 0.74          11.1%
         100             1.24 / 0.86          11.7%
         500             1.05 / 0.98          11.2%

加第 9 台机器时，理想的迁移比例是 1/9 = 11.1%

两件事一起看：

迁移量：无论多少个虚拟节点，加第 9 台机器时迁移的键都在 11% 左右，接近理论最优的 1/9。这就是一致性哈希的全部意义。
均衡度：每台机器只放一个点时，环被切得很不均匀，最重的机器是平均的 2.34 倍。虚拟节点是解法：每台机器在环上撒 100～500 个点，相当于多次采样，最重的机器降到 1.05～1.24 倍。

选多少个虚拟节点，是"均衡度"和"环的规模"之间的权衡：环上的点数 = 机器数 × 虚拟节点数，每次路由是一次二分查找（O(log 点数)），扩缩容时要插入或删除相应的点。几十台机器的集群里，每台 100～500 个虚拟节点是常见选择。

虚拟节点还有一个好处：可以按机器的容量分配数量（性能好的机器多放几个），实现加权分片。

热键与有界负载¶

一致性哈希只保证"键均匀时负载均匀"。推理服务里键往往并不均匀：热门的系统提示词、被反复访问的会话、爆款的 LoRA 适配器。热键的哈希值是固定的，它永远落在同一台机器上。

有界负载的一致性哈希（consistent hashing with bounded loads）加一条规则：如果顺时针找到的机器负载已经超过上限（比如平均负载的 1.25 倍），就继续往下找，直到找到一台没超的。

bounded.py

# 有界负载的一致性哈希：沿环顺延，直到找到一台负载没超过上限的机器
import bisect
import hashlib
from collections import Counter


def h(s):
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")


class Ring:
    def __init__(self, nodes, vnodes=100):
        self.points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
        self.keys = [p for p, _ in self.points]

    def route(self, key, load=None, cap=None):
        i = bisect.bisect(self.keys, h(key))
        for step in range(len(self.points)):                  # 顺时针找第一台没超过上限的
            node = self.points[(i + step) % len(self.points)][1]
            if load is None or load[node] < cap:
                return node
        return self.points[i % len(self.points)][1]


nodes = [f"node{i}" for i in range(8)]
ring = Ring(nodes)
# 会话的热度差异很大：少数会话占了大部分请求
reqs = [f"session-{i % 20}" for i in range(4000)] + [f"session-{i}" for i in range(2000)]
for name, factor in [("不限上限", None), ("上限 = 平均 × 1.25", 1.25), ("上限 = 平均 × 1.05", 1.05)]:
    load = Counter({n: 0 for n in nodes})
    cap = None if factor is None else int(len(reqs) / len(nodes) * factor)
    hit = 0
    for r in reqs:
        node = ring.route(r, None if cap is None else load, cap)
        hit += node == ring.route(r)                          # 是否还落在"本来该去"的那台
        load[node] += 1
    hi = max(load.values()) / (len(reqs) / len(nodes))
    print(f"{name:18s} 最重的机器是平均的 {hi:.2f} 倍，亲和性（还去原来那台）{hit / len(reqs):5.1%}")

输出

不限上限               最重的机器是平均的 1.69 倍，亲和性（还去原来那台）100.0%
上限 = 平均 × 1.25     最重的机器是平均的 1.25 倍，亲和性（还去原来那台）90.9%
上限 = 平均 × 1.05     最重的机器是平均的 1.05 倍，亲和性（还去原来那台）79.2%

上限越紧，负载越均衡，但越多的请求被"改派"到了别的机器，亲和性（还去原来那台）越差——对前缀缓存来说，改派就意味着缓存未命中、要重新 prefill。所以上限是一个业务参数：缓存收益大就放松（1.25～1.5），负载敏感就收紧（1.05～1.1）。

配套的两个细节：

改派要有记忆：同一个会话第一次被改派到某台机器之后，后续请求也应该去那里（否则它会在两台机器之间来回，两边都建缓存）。常见做法是把"会话 → 实例"的映射缓存一小段时间。
改派要有滞后：负载在阈值附近抖动时，不要每个请求都重新决定，否则会出现羊群效应。

最高随机权重（rendezvous hashing）¶

还有一种更简单的分片方法：对每个候选机器算一个分数 hash(key + node)，取分数最高的那台。

rendezvous.py

# 最高随机权重（rendezvous hashing）：对每个候选机器算一个分数，取最高的那台。
# 不需要环和虚拟节点，天然支持按权重分配，删除一台机器时只有它的键会迁移
import hashlib
from collections import Counter


def score(key, node):
    return int.from_bytes(hashlib.blake2b(f"{key}@{node}".encode(), digest_size=8).digest(), "big")


def route(key, nodes, weights=None):
    if weights is None:
        return max(nodes, key=lambda n: score(key, n))
    # 带权重时用 -weight / ln(score)：分数越高、权重越大越容易被选中
    import math
    return max(nodes, key=lambda n: -weights[n] / math.log(score(key, n) / 2 ** 64))


keys = [f"session-{i}" for i in range(50000)]
eight = [f"node{i}" for i in range(8)]
nine = eight + ["node8"]
seven = eight[:-1]

load = Counter(route(k, eight) for k in keys)
print(f"8 台均分：最重 {max(load.values()) / (len(keys) / 8):.3f} 倍，最轻 {min(load.values()) / (len(keys) / 8):.3f} 倍")
print(f"加到 9 台：迁移 {sum(1 for k in keys if route(k, eight) != route(k, nine)) / len(keys):.1%}（理想 {1 / 9:.1%}）")
print(f"减到 7 台：迁移 {sum(1 for k in keys if route(k, eight) != route(k, seven)) / len(keys):.1%}（理想 {1 / 8:.1%}）")

w = {n: (3 if n == "node0" else 1) for n in eight}            # node0 的容量是别人的 3 倍
load = Counter(route(k, eight, w) for k in keys)
print(f"\n按权重（node0 权重 3，其余 1）：node0 拿到 {load['node0'] / len(keys):.1%}，理想 {3 / 10:.1%}")

输出

8 台均分：最重 1.024 倍，最轻 0.984 倍
加到 9 台：迁移 11.1%（理想 11.1%）
减到 7 台：迁移 12.8%（理想 12.5%）

按权重（node0 权重 3，其余 1）：node0 拿到 29.9%，理想 30.0%

负载天然均匀：不需要虚拟节点，8 台机器时最重的只比平均高 2.4%；
迁移量最优：加机器时迁移 1/(n+1)，删机器时只有那台机器上的键会动；
加权很自然：用 -权重 / ln(分数) 作为比较值，就能按权重分配（上面 node0 权重为 3 时拿到了 29.9%，理想是 30%）；
还能直接选前 k 个：按分数排序取前 k 台，就是这个键的 k 个副本，而且删掉其中一台时其余副本不变。

代价是每次路由要对所有候选机器算哈希，O(n)。候选机器几十台时完全没问题（几十次哈希是纳秒级），上千台时就该用环了。实践中常见的组合是：外层用一致性哈希定位到一个"分片组"，组内用最高随机权重选副本。

在推理系统里的落点¶

场景	怎么用	要注意什么
缓存感知路由	按会话 ID 或前缀哈希路由到固定实例，命中前缀缓存省掉整个 prefill	用有界负载避免热会话打爆一台；实例扩缩容时只有 1/N 的会话失去缓存（见前缀缓存）
分布式 KV 存储	KV 块按 key 分片存到多台机器（Mooncake Store、LMCache 等）	块的 key 通常是"前缀哈希"，天然可以做内容寻址；副本用最高随机权重选（见 KV 传输引擎与分布式 KV 存储）
专家并行	专家到 GPU 的映射；热门专家要复制到多张卡上	这里的"键"是专家编号，数量少而固定，通常用显式的映射表加负载均衡算法，而不是哈希（见大规模 EP 部署）
多 LoRA 服务	同一个适配器的请求发给同一实例，避免重复加载	适配器数量多、热度差异大，适合有界负载
分片的指标与日志	按实例 ID 分片写入	时间序列的写入通常按时间 + 实例哈希双重分片，避免热点

有一个前提要强调：分片的前提是"键的选择对"。前缀缓存路由按"前 N 个 token 的哈希"分片比按"会话 ID"更好，因为不同会话可能共享同一个系统提示词；而按"用户 ID"分片则会把同一个用户的所有对话粘在一台机器上，好处是缓存局部性，坏处是大客户会造成倾斜。

分片之外：再平衡与元数据¶

真实系统还要处理两件事：

再平衡的过程。迁移不是瞬间完成的：要么"双写 + 逐步搬运 + 切换读"，要么允许一段时间内读旧位置（miss 了再回源）。对缓存类的数据（KV 块、前缀缓存），最省事的做法是干脆不迁移——让旧位置自然过期，新请求在新位置重新建缓存，代价是一段时间的命中率下降。
谁知道当前的分片方案。所有客户端必须对"现在有哪些机器"达成一致，否则会路由到不同的地方。常见做法是把成员列表放在一个强一致的元数据服务里（etcd、ZooKeeper），客户端监听变化；这就需要下一章的共识算法。

怎么讲清楚

讲分片：先说取模的问题——扩容一台，8 台到 9 台有约 89% 的键要迁移，缓存全失效。一致性哈希把键和机器都哈希到一个环上，顺时针找第一个机器点，加机器只影响相邻的一段弧，迁移量降到理论最优的 1/(n+1)；均衡靠虚拟节点（每台 100～500 个，最重的机器从 2.3 倍降到 1.05 倍），虚拟节点数量还能当权重用。热键用有界负载解决：超过负载上限就顺延到下一台，上限越紧越均衡、亲和性越差，是一个业务参数。另一个选择是最高随机权重：对每台机器算 hash(key+node) 取最大，不需要虚拟节点、负载天然均匀、支持权重和"取前 k 个副本"，代价是 O(n) 的路由开销，适合候选集不大的场景。最后落到推理：缓存感知路由、分布式 KV 存储、多 LoRA 亲和，都是这套东西，并且要配合一个强一致的成员列表。

练习¶

1. 算迁移量。 一个 16 台机器的前缀缓存集群，要扩容到 20 台。用一致性哈希时大约有多少比例的会话会改变归属？如果这些会话的下一次请求都要重新 prefill、每次 300 ms，扩容瞬间对 p99 有什么影响？怎么缓解？

参考答案

迁移比例约为新增容量占比：4/20 = 20% 的会话会改到新机器上。它们的下一次请求会丢失前缀缓存，TTFT 多 300 ms——如果这 20% 集中在扩容后的几秒内到达，p99 会明显变差。

缓解：（1）分批加入新机器（一次加一台，间隔几分钟），把冲击摊开；（2）新机器加入后先不接流量，或者给它一个逐步提升的权重（虚拟节点数量从少到多）；（3）允许"回源"：新机器发现本地没有缓存时，尝试从旧归属的实例拉取 KV（有分布式 KV 存储时可行）；（4）接受它——扩容通常发生在负载上升期，这点代价换来的是整体容量。

2. 虚拟节点的数量。 一个 200 台机器的集群，每台 500 个虚拟节点。环上有多少个点？路由一次要几次比较？如果改用最高随机权重呢？各自的内存开销是多少量级？

参考答案

环上 100000 个点，二分查找约 17 次比较，内存按每个点 16 字节算约 1.6 MB。最高随机权重要对 200 台各算一次哈希（200 次），比二分慢一个数量级，但不需要存环，内存只有机器列表。

所以大集群用环、小集群用最高随机权重；也可以两层：先用环定位到分片组（几十个组），组内用最高随机权重选具体机器和副本。

3. 设计缓存路由。 设计一个前缀缓存的路由策略：输入是请求的前 512 个 token 和当前各实例的队列深度，输出是目标实例。写出伪代码，并说明三个参数怎么选。

参考答案

key = hash(前 512 个 token 的前缀分块)         # 分块哈希，让共享系统提示词的请求落在一起
候选 = 一致性哈希环上从 key 顺时针的前 3 台
对候选按 (估计命中长度, -队列深度) 排序
若最优候选的队列深度 > 平均 × C：顺延到下一个候选
记录 会话 -> 选中实例，TTL 内的后续请求直接复用

三个参数：（1）前缀截断长度（512）：太短会把不同请求误判为同前缀，太长会让只差结尾的请求分到不同实例；按业务的系统提示词长度定。（2）负载上限系数 C：缓存收益大（长系统提示词）就放松到 1.5，延迟敏感就收紧到 1.1。（3）会话映射的 TTL：要略大于典型的多轮对话间隔（比如 5 分钟），太长会在扩缩容后继续指向旧实例。

4. 判断一个说法。 "我们用一致性哈希做 KV 存储的分片，所以扩容不用迁移数据。" 这句话对吗？

参考答案

不完全对。一致性哈希保证的是需要迁移的数据量最小（1/(n+1)），不是"不用迁移"。对持久化的存储，那 1/(n+1) 的数据必须真的搬过去，否则新机器上查不到、旧机器上的数据永远不会被访问到。

只有对可重建的缓存（KV Cache 块、前缀缓存）才可以不迁移：新位置没有就重新算一遍，旧位置的数据自然过期。区别在于数据是不是"丢了还能再生成"。

小结¶

取模分片扩容时几乎全部键都要迁移（8→9 台约 89%）；一致性哈希把它降到理论最优的 1/(n+1)。
虚拟节点解决的是分布不均：每台 100～500 个，最重的机器从 2.3 倍降到 1.05～1.24 倍；数量还能当权重用。
热键靠有界负载解决：超上限就顺延，上限越紧越均衡、亲和性越差；改派要有记忆和滞后。
最高随机权重实现更简单、负载天然均匀、支持权重与多副本，代价是 O(n) 路由，适合候选集不大的场景。
推理系统里的落点：缓存感知路由、分布式 KV 存储、多 LoRA 亲和；可重建的缓存可以不迁移，持久数据必须迁移。
分片方案本身要有一个强一致的成员列表，这就需要共识算法。

本章练习题（1 道）

在浏览器里直接写代码、跑测试；也可以在本地用 python practice/judge.py 判题。

228. 一致性哈希环与有界负载（中等）

发现错误或有更好的写法？在 GitHub 上编辑此页提交问题