分布式系统

一台服务器一年宕机几次也许还能接受；一千台服务器的集群里，几乎每天都有机器坏掉。可我们希望整个系统像一台永不宕机的机器：存进去的数据不丢，读出来的永远是最新的。这篇回答这个看似矛盾的要求怎么实现。故事从”把活分出去”开始，然后不断碰到同一个敌人：你永远无法确定另一台机器到底是死了，还是只是慢。

前置：网络：TCP 与应用层、数据库系统（事务、日志）、并发与同步

局部故障：分布式和单机的根本区别

在单机程序里，故障通常是全有或全无：要么程序在跑，要么整台机器挂了。分布式系统的标志是局部故障：一部分机器坏了，其余的还在跑，而且它们不一定知道谁坏了。

你给另一台机器发了请求，迟迟没有回复。可能是请求在网络上丢了；可能对方收到了、处理了，只是回复丢了；可能对方正在做一次很长的 GC 暂停；也可能它真的宕机了。从你这边看，这几种情况完全一样，都是”没回音”。唯一的工具是超时，但超时设短了会把慢机器误判为死机，设长了又会让系统在真故障时卡很久。这个不确定性是分布式系统几乎所有难题的根源。

为了讨论什么能做到，先约定故障模型。这里默认：机器可能崩溃停止（crash-stop，之后可能重启并带回磁盘上的数据），网络可能丢包、延迟、乱序、甚至分区（一部分机器之间暂时完全不通），但没有人撒谎。如果机器可能被攻破、发出任意错误消息，就是拜占庭故障，需要代价高得多的协议，区块链属于这一类，一般的数据中心系统不考虑它。

时钟也靠不住，机器间会漂移甚至回跳，所以下文 Raft 用逻辑上的任期号而不是墙上时间排序。

停一下，检查理解单选

节点 A 向节点 B 发出"给账户加 100"的请求，超时后没有收到回复。A 能得出哪个结论？

B 已经宕机，应当把请求转给备份节点B 没有执行这个操作，重发是安全的无法确定 B 是否执行了这个操作网络出现了分区，应当停止服务

检查答案

MapReduce：先绕开难题

既然故障这么麻烦，第一个大获成功的分布式系统选择了把难题绕开。2004 年 Google 的 MapReduce 让程序员只写两个纯函数：map 把一份输入变成若干 (key, value)，reduce 把同一个 key 的所有 value 合并。用单机多进程模拟一遍词频统计：

from collections import defaultdict
from multiprocessing import Pool
import re
docs = ["the cat sat on the mat", "the dog ate the cat food", "a cat and a dog"]
def map_fn(doc):                       # 每个 map 任务只看自己那份输入
    return [(w, 1) for w in re.findall(r"\w+", doc)]
def reduce_fn(item):
    k, vs = item; return k, sum(vs)
if __name__ == "__main__":
    with Pool(3) as p:
        pairs = [kv for part in p.map(map_fn, docs) for kv in part]
        groups = defaultdict(list)     # shuffle：同一个 key 送到同一个 reducer
        for k, v in pairs: groups[k].append(v)
        print(sorted(p.map(reduce_fn, groups.items()), key=lambda x: -x[1])[:4])

[('the', 4), ('cat', 3), ('dog', 2), ('a', 2)]

真实系统里 map 输出按 hash(key) % R 分桶写到本地磁盘，reduce 再从所有 map worker 拉取自己的桶，这一步叫 shuffle，通常是网络流量最大的阶段。

它为什么能轻松容错？因为 map 和 reduce 都是确定性的纯函数，只读输入、只写输出。一个 worker 挂了，master 把它的任务交给别人重跑一遍，结果完全一样。被误判为死的慢 worker 后来也交了结果怎么办？输出先写临时文件，完成后原子地重命名，两份相同的结果谁赢都一样。

MapReduce 的教训是：只要计算是确定性、无副作用的，容错就只是”重做”。局限也在这里：它不能存储会被修改的状态。一个要接受写入的数据库，不能”出错了重跑一遍”。

停一下，检查理解单选

MapReduce 中一个 map worker 在任务完成后宕机，它的输出存在本地磁盘上。master 应该怎么做？

什么都不做，任务已经完成了把这个 map 任务重新分配给其他 worker 重跑，因为 reduce 还需要读取它的输出让所有 reduce 任务跳过这个 map 的输出，结果会略有误差终止整个作业，因为状态已经不一致

检查答案

RPC：远程调用不是本地调用

大多数分布式系统内部的通信方式是 RPC（远程过程调用）：客户端调用一个看起来像本地函数的 kv.Put(key, value)，框架把参数序列化、通过网络发给服务器，服务器执行后把返回值发回来。

外表像本地调用，语义却完全不同，因为第一节那个问题：超时了，不知道对方执没执行。框架有几种选择：

• 最多一次（at-most-once）：不重试。可能没执行，但绝不会执行两次。
• 至少一次（at-least-once）：超时就重试，直到收到回复。保证执行了，但可能执行多次。
• 恰好一次（exactly-once）：至少一次加上服务器端去重。

如果操作是幂等的，比如 Put(x, 5)，执行两次和一次效果相同，至少一次就够了。但 Append(x, "a") 或”加 100”不是幂等的，重试会造成重复。标准做法是给每个请求带上（客户端 ID，序号），服务器记录每个客户端最近处理过的序号和结果；收到重复请求时直接返回缓存的结果而不再执行。这张去重表本身也是状态，服务器重启或主备切换时必须一起保存和转移，否则去重就失效了。

停一下，检查理解单选

客户端调用 Append("log", "x")，超时后重试，最终日志里出现了两个 x。最合理的修复是什么？

把超时时间调长，让第一次请求有足够时间返回改成最多一次语义，超时后不再重试每个请求带上客户端 ID 和递增序号，服务器记录已处理的序号，遇到重复直接返回之前的结果改用 UDP，避免 TCP 重传导致的重复

检查答案

复制：两台机器，谁说了算

要让存储在机器坏掉后不丢，就得复制：同一份数据放在多台机器上。最直接的方案是主备复制：所有请求发给主节点（primary），主节点执行后把操作转发给备份（backup），备份确认后主节点才回复客户端。主节点挂了，备份接手。

这里的关键要求是：主和备必须以同样的顺序执行同样的操作，得到同样的状态。这叫复制状态机：只要状态机是确定性的，输入序列相同，状态就相同。所以复制的问题变成了”让多台机器对一个操作序列达成一致”。

麻烦出在”主节点挂了，备份接手”这句话上。备份怎么知道主挂了？只能靠超时。如果其实是主备之间的网络断了，而主节点仍在为一部分客户端服务，备份却以为它死了，自己也升为主，就出现了两个主节点，各自接受写入，数据从此分叉。这叫脑裂（split brain）。

早期系统的做法是引入一个第三方仲裁者（比如一个”视图服务器”）来决定谁是主。但仲裁者自己也是单点，它挂了谁来仲裁？问题绕了一圈又回来了。根本的出路是多数派（quorum）：用 2f+1 台机器，任何决定都需要至少 f+1 台同意。两个多数派一定有交集，所以网络无论怎么分区，最多只有一侧能凑够多数，脑裂在原理上被排除了。代价是需要更多机器：容忍 1 台故障要 3 台，容忍 2 台要 5 台，而且少数派那一侧必须停止服务。

停一下，检查理解单选

一个复制组有 5 台机器，网络分区把它们分成 3 台和 2 台两侧。使用多数派协议时，会发生什么？

两侧都继续接受写入，分区恢复后再合并只有 3 台那一侧能凑够多数，继续服务；2 台那一侧无法提交新写入两侧都停止服务，直到分区恢复2 台那一侧如果包含原来的主节点，就由它继续服务

检查答案

Raft：用多数派维护一份日志

Raft 是把多数派思想做成完整协议的代表，etcd、TiKV 都在用。它维护一份复制的日志，每条日志是一个要应用到状态机的操作。它把问题拆成三块。

选主。每个节点是 follower、candidate 或 leader 之一。时间被划分成递增的任期（term），每个任期最多一个 leader。leader 定期发心跳；follower 在一段选举超时内没听到心跳，就把任期加 1、变成 candidate、给自己投票并向所有人要票。每个节点在一个任期里只投一票，先到先得；拿到多数票的就成为 leader。任何节点看到比自己大的任期号，立刻退回 follower。任期号代替了不可靠的墙上时钟，旧 leader 恢复过来，一看到更大的任期就知道自己过时了。

如果几个 follower 同时超时，各自给自己投票，票就会被瓜分，谁都凑不够多数，只能等下一轮。Raft 的应对朴素而有效：每个节点的选举超时在一个区间里随机选。模拟 5 个节点，假设最早超时的节点只要比第二个早 5 ms（大约一次 RTT，够它把投票请求送到别人那里），就能当选：

import random
def rounds_to_elect(n, lo, hi, trials=2000, rtt=5):
    total = 0
    for _ in range(trials):
        r = 0
        while True:
            r += 1
            t = sorted(random.uniform(lo, hi) for _ in range(n))
            # 最早超时者在别人超时前（差 > 一次 RTT）拿到多数票才算选成
            if t[1] - t[0] > rtt or r >= 1000: break
        total += r
    return total / trials
random.seed(0)
for lo, hi in [(150, 160), (150, 200), (150, 300)]:
    print(f"timeout {lo}-{hi}ms: avg rounds = {rounds_to_elect(5, lo, hi):.2f}")

timeout 150-160ms: avg rounds = 32.61
timeout 150-200ms: avg rounds = 1.68
timeout 150-300ms: avg rounds = 1.19

随机区间太窄时，平均要三十多轮才选出 leader；放宽到 150–300 ms（Raft 论文推荐的量级），基本一轮成功。区间也不能太宽，否则 leader 挂后要等很久才有新选举。

日志复制。客户端只和 leader 交互。leader 把命令追加到自己的日志，通过 AppendEntries 发给所有 follower。每条请求带着前一条日志的（索引，任期），follower 发现自己在那个位置的日志对不上就拒绝，leader 往前退一格再试，直到找到双方一致的位置，然后用自己的日志覆盖 follower 之后的部分。一条日志被多数节点存下之后就算已提交，leader 才把它应用到状态机并回复客户端。

安全性。leader 会覆盖 follower 的日志，那么一个日志落后的节点当上 leader，岂不是会覆盖掉已经提交的条目？Raft 用一条投票规则堵住这个洞：投票者只把票投给日志至少和自己一样新的 candidate（先比最后一条的任期，再比长度）。已提交的条目存在于多数派上，任何 candidate 要当选也得拿到多数派的票，两个多数派有交集，交集里至少有一个节点持有这条条目，它不会把票投给缺少这条条目的 candidate。所以新 leader 一定包含所有已提交的条目。

还有一个细节：leader 只直接提交当前任期的条目，旧任期的条目随之间接提交，论文图 8 给出了违反这条会出错的反例。

实际系统还需要快照来截断日志，并且任期、投票和日志必须先持久化再回复，否则重启后可能在同一任期投两次票。

停一下，检查理解多选

关于 Raft，下列哪些说法正确？

随机化的选举超时让多个节点同时成为 candidate、瓜分选票的情况变得罕见一条日志只有在被多数节点存储后才算已提交，leader 此时才回复客户端日志落后的节点不可能成为 leader，因为它永远收不到心跳节点按墙上时钟比较谁的日志更新，时钟更晚的胜出

检查答案

一致性模型：什么叫”像一台机器”

有了 Raft，我们可以在它之上搭一个复制的 KV 存储。但”像一台机器”到底指什么，需要说清楚。最强、也最符合直觉的标准是线性一致性（linearizability）：每个操作看起来在它的调用和返回之间的某个瞬间原子地生效，并且所有客户端看到的是同一个全局顺序。具体后果是：一旦某个写入返回成功，之后开始的任何读都必须看到它（或更新的值）。

这比看起来难：follower 可能还没收到最新日志；leader 也可能已被分区隔开而不自知。所以线性一致的读要么也走一遍日志，要么 leader 先和多数派确认自己仍是 leader。

较弱的模型换来性能和可用性，最弱的常用模型是最终一致性只保证”如果不再有新写入，所有副本最终会收敛到同一个值”，期间谁读到什么都可能。DNS（见 网络：从链路到 IP）和很多缓存系统就是最终一致的。

CAP 定理把这个取舍讲得很尖锐：当网络分区（P）发生时，系统只能在一致性（C，指线性一致）和可用性（A，每个请求都能得到非错误的回复）之间二选一。Raft 选择了 C：少数派一侧拒绝服务。Dynamo、Cassandra 这类系统选择了 A：两侧都接受写入，事后用版本向量或”最后写入者胜”来合并冲突。分区毕竟是少数时刻，PACELC 补充了另一半：没有分区时（Else），还要在延迟（L）和一致性（C）之间取舍，因为强一致的每次写入都要等跨机器的多数确认。

停一下，检查理解单选

一个基于 Raft 的 KV 存储，为了降低 leader 负载，允许 follower 直接用本地状态回答读请求。这会破坏什么？

持久性：follower 的数据可能丢失线性一致性：follower 可能还没应用最新提交的写入，读到旧值可用性：follower 回答读请求时 leader 无法处理写入什么都不破坏，因为 follower 的日志最终会和 leader 一致

检查答案

分片：一组复制不够大的时候

一个 Raft 组的所有写入都要经过同一个 leader，而且每台机器都存全量数据，吞吐和容量都被一台机器卡住。扩展的办法是分片（sharding）：把 key 空间切成很多份，每份交给一个独立的 Raft 组。一个配置服务（它本身也是一个 Raft 组）记录哪个分片归哪个组。

怎么把 key 映射到分片？最朴素的 hash(key) % N 有个致命问题：机器数从 4 变成 5，几乎所有 key 的归属都变了，要大规模搬数据。一致性哈希把节点和 key 都哈希到一个环上，每个 key 归顺时针方向遇到的第一个节点；每个物理节点在环上放很多个虚拟节点，让负载更均匀。实际测一下 1 万个 key：

import hashlib, bisect
h = lambda s: int(hashlib.md5(s.encode()).hexdigest(), 16)
keys = [f"key{i}" for i in range(10000)]
mod = lambda n: {k: h(k) % n for k in keys}
a, b = mod(4), mod(5)
print("hash % N, 4->5 nodes moved:", sum(a[k] != b[k] for k in keys) / len(keys))
def ring(nodes, vnodes=100):
    pts = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
    hs = [p for p, _ in pts]
    return lambda k: pts[bisect.bisect(hs, h(k)) % len(pts)][1]
r4, r5 = ring(["n0","n1","n2","n3"]), ring(["n0","n1","n2","n3","n4"])
print("consistent hash, 4->5 moved:", sum(r4(k) != r5(k) for k in keys) / len(keys))

hash % N, 4->5 nodes moved: 0.8027
consistent hash, 4->5 moved: 0.2121

取模要搬 80% 的数据；一致性哈希只搬了 21%，接近理论最小值 1/5，搬走的正好是新节点该接管的那部分。也可以按 key 的范围分片（TiKV、Bigtable），利于范围扫描。

分片带来最后一个难题：一个事务要同时修改两个分片上的数据（比如从 A 分片的账户转账到 B 分片），怎么保证原子性？经典答案是两阶段提交（2PC）。协调者先向所有参与者发 prepare，每个参与者把修改写进日志、锁住相关数据，然后投票”可以提交”或”不行”；全部同意，协调者写下提交决定并通知所有人 commit，否则通知 abort。它的弱点是阻塞：参与者投了”可以”之后就不能单方面反悔，如果协调者此时宕机，参与者只能拿着锁一直等。现代系统（Spanner、CockroachDB）的解法是让协调者和每个参与者本身都是 Raft 组，单台机器宕机不再导致整个协调者失联，2PC 就变得可用了。分片之间的事务还需要并发控制，这和 数据库系统 里的 2PL、MVCC 是同一套思想，只是跨了机器。

停一下，检查理解单选

两阶段提交中，一个参与者已经回复了"可以提交"，随后协调者宕机，再也没有消息。这个参与者应该怎么做？

等待超时后自行提交，因为它已经同意了等待超时后自行回滚，释放锁只能继续持有锁等待，直到从协调者或其他参与者处得知最终决定重新发起一轮 prepare，自己担任协调者

检查答案

记住这三件事

1. 分布式的根本难题是局部故障：超时无法区分慢和死，所以要靠确定性重做、请求去重这类设计来容忍不确定。
2. 多数派是防脑裂的基石：Raft 用任期、随机超时和”日志至少一样新”的投票规则，让多台机器维护一份一致的日志。
3. 一致性是可以选的强度：线性一致性最直观但要付延迟与可用性的代价；扩展靠分片，跨分片的原子性靠两阶段提交加复制。

延伸阅读

• MIT 6.5840 Distributed Systems 课程讲义与论文列表（pdos.csail.mit.edu/6.824）
• Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm（USENIX ATC 2014），以及 raft.github.io 的可视化
• Dean & Ghemawat, MapReduce: Simplified Data Processing on Large Clusters（OSDI 2004）
• Martin Kleppmann, Designing Data-Intensive Applications，第 5–9 章
• Herlihy & Wing, Linearizability: A Correctness Condition for Concurrent Objects（1990）
• Corbett et al., Spanner: Google’s Globally-Distributed Database（OSDI 2012）