分布式系统到底难在哪里：从逻辑时钟到 Raft 的四十年

把一个程序放到两台机器上，并不会自动得到一个分布式系统。

真正的问题从第二台机器加入的那一刻才开始：两台机器的时钟可能不同，消息可能晚到、重复甚至消失，一台机器可能突然宕机；更麻烦的是，你甚至无法立即判断对方究竟是坏了，还是单纯网络太慢。

Nicolae Vartolomei 整理的 Distributed Systems Classics 收录了从 1978 年 Lamport 逻辑时钟，到拜占庭将军、FLP、Viewstamped Replication、Paxos、Bitcoin、CRDT，再到 2014 年 Raft 的一系列经典论文。它们并不是一条简单的“旧算法被新算法取代”的技术树，而是在回答分布式系统里的几个不同问题：什么叫先后？什么叫整个系统的状态？机器坏了还能不能达成一致？如果机器还会骗人呢？如果一致性的成本太高，我们能不能干脆不要它？

理解这些问题，比直接背 Paxos 或 Raft 的流程重要得多。

分布式世界里没有一个共同的“现在”

假设服务器 A 在自己的日志里记录：

10:00:00.001  用户支付成功

服务器 B 记录：

10:00:00.000  库存扣减成功

能不能因此断定 B 的操作发生在 A 之前？

不能。

两台机器的物理时钟本来就可能差几毫秒甚至更多。哪怕使用 NTP，也只能让误差变小，不能让整个分布式系统获得一个绝对一致的“现在”。

Lamport 在 1978 年那篇著名的 Time, Clocks, and the Ordering of Events in a Distributed System 中，干脆换了一个问题：

与其问“它们真实发生在几点”，不如问“我们能不能确定一个事件一定发生在另一个事件之前？”

于是有了 happened-beforeHappened-before用于描述分布式事件因果先后关系的偏序：进程内顺序、消息发送到接收，以及这些关系的传递闭包共同确定事件之间的先后。查看详细解释 → 关系，通常写成：

$$a\to b$$

它只有几个非常简单的规则。

如果同一个进程里，事件 (a) 在 (b) 前面执行：

$$a\to b$$

如果 (a) 是发送一条消息，而 (b) 是接收到这条消息：

$$\text{send}\left(m\right)\to \text{receive}\left(m\right)$$

如果：

$$a\to b$$

并且：

$$b\to c$$

那么：

$$a\to c$$

这看起来几乎简单得不像一个理论，但意义非常大：分布式系统真正需要的往往不是精确时间，而是因果关系。 Lamport 的论文正是用这种关系给分布式事件建立了一个偏序。论文页面

接下来就可以给每个进程放一个逻辑计数器 (C)。

本地发生一个事件：

$$C\leftarrow C+1$$

发送消息时，把自己的 (C) 一起发出去。

如果收到一条时间戳为 (t) 的消息：

$$C\leftarrow \text{max}(C,t)+1$$

这样可以保证一个非常重要的性质：

$$a\to b\Rightarrow C\left(a\right)<C\left(b\right)$$

也就是：

如果我们已经知道 (a) 是 (b) 的原因之一，那么逻辑时间一定会把 (a) 排在前面。

但反过来不成立：

$$C\left(a\right)<C\left(b\right)$$

并不能证明：

$$a\to b$$

因为两个互不相关的事件完全可能恰好拿到不同的逻辑时间。

这也是理解分布式系统很重要的一步：“顺序”和“因果”不是同一个东西。

可新的问题马上来了。

假设现在有 100 台服务器不停处理消息。你想备份整个系统，那么应该保存哪个时刻？

不能简单地喊一句：

“大家现在一起截图！”

因为根本不存在那个统一的“现在”。

1985 年，Chandy 和 Lamport 的 Distributed Snapshots 就是在解决这个问题。它允许系统继续运行，同时通过特殊的 marker 消息记录各进程和通信信道的状态，最终拼出一个一致的全局快照。这项工作的典型用途包括 checkpoint、检测死锁以及判断计算是否已经结束。论文参考页

所谓“一致”，可以用一句非常直观的话描述：

如果快照中已经记录了“消息被接收”，那么也必须包含“这条消息被发送”。

形式化一点就是：

$$\text{receive}\left(m\right)\in S\Rightarrow \text{send}\left(m\right)\in S$$

否则你会得到一种荒唐的系统状态：

钱已经到账了，但付款这件事情从未发生。

所以从 Lamport Clock 到 Distributed Snapshot，分布式系统首先解决的并不是“怎么复制数据库”，而是更加基础的问题：

我们究竟怎样描述一个没有统一时间的世界？

机器不仅会坏，有时候还会“说谎”

如果服务器只是突然断电，其实已经够麻烦了。

但军用系统、金融系统或者开放网络里还存在更加棘手的问题：

服务器没有宕机，但它返回了错误的信息。

它可能被攻击，也可能程序已经损坏。

1982 年 Lamport、Shostak 和 Pease 用一个非常著名的故事描述了这个问题：一群拜占庭将军包围一座城市，他们必须统一决定进攻还是撤退，但其中一些将军可能是叛徒。叛徒不但可以撒谎，而且可以分别告诉不同的人完全不同的消息。论文页面

例如：

将军 A → B：进攻
将军 A → C：撤退

这和普通的服务器宕机完全不同。

宕机节点是：

“我不说话了。”

拜占庭节点则是：

“我不仅说话，我还故意让你们互相得到不同答案。”

在经典的、没有不可伪造签名的 Byzantine Generals 模型中，如果要容忍 (f) 个这样的恶意节点，需要：

$$n\ge 3f+1$$

例如想容忍 1 个叛徒，至少需要 4 个节点。

为什么大致是三倍？

因为你不仅要判断某人说的是真是假，还要判断“别人告诉你的、某人说的话”是真是假。节点数量太少时，两个诚实节点可能看到两个完全自洽、却完全相反的世界。

这就是后来 Byzantine Fault Tolerance，拜占庭容错的理论来源。

但在普通数据库集群里，工程师通常并不假设某台数据库会故意伪造数据。更常见的模型是：

机器会崩，但不会恶意撒谎。

这叫 crash fault。

听起来问题一下简单了很多。

可 1985 年的 FLP 论文又给这个领域泼了一盆冷水。

Fischer、Lynch 和 Paterson 证明：

在一个完全异步的分布式系统里，只要允许有一个进程可能崩溃，就不存在一个确定性的共识算法Consensus多个分布式参与者在故障和消息延迟存在时，对一个值或一段操作历史达成一致决定的问题。查看详细解释 →，能够保证在所有合法执行中最终一定做出决定。论文全文

可以非常粗略地写成：

$$\begin{array}{c}\text{完全异步 ＋ 确定性共识 ＋ 允许一次 crash}\\ ⟹\\ \text{无法保证所有执行最终结束}\end{array}$$

这里最容易误读。

FLP 不是说“分布式共识不可能”。

真正的问题在于完全异步系统中，一个节点迟迟没有回复时，你根本无法区分：

A：节点 B 挂了。

和：

A：节点 B 没挂，只是这条消息延迟了 30 年。

如果系统规定：

“没等到 B 就绝对不能继续。”

那么可能永远停在那里。

如果规定：

“等 5 秒就当 B 挂了。”

那么你已经偷偷增加了一个时间假设。

现实中的 Paxos、Raft 等算法并没有“推翻 FLP”。它们只是接受现实：安全性必须永远保证，但系统只需要在网络和节点恢复到足够正常的情况下保证继续前进。

这也是分布式系统里经常出现的两个词：

SafetySafety分布式算法中“坏事永远不会发生”的正确性性质，例如两个冲突值不能同时被正式提交。查看详细解释 →：不能发生坏事。

例如：

两个不同值不能同时被正式提交。

LivenessLiveness分布式算法中“好事最终会发生”的推进性质，例如请求在满足必要网络与节点条件后最终得到处理。查看详细解释 →：好事最终会发生。

例如：

请求最终能够被处理。

工程系统通常选择：

网络再烂，也不能把数据搞乱； 但网络烂到某种程度时，我允许系统暂时停下来。

既然不能相信一台机器，那就复制；可复制以后谁说了算？

假设数据库只有一台服务器：

余额 = 100

它死了，服务就没了。

最自然的想法就是复制：

Server A    余额 = 100
Server B    余额 = 100
Server C    余额 = 100

但客户现在花了 20 元。

谁负责决定：

余额 = 80

如果 A、B、C 同时接受写入，很快就会出现互相矛盾的历史。

于是工程上出现了一种非常自然的设计：

先选一个 Primary / Leader。

所有写操作先交给它：

Client
   ↓
Leader
  ↙ ↘
B   C

1988 年 Oki 和 Barbara Liskov 提出的 Viewstamped Replication，就是早期非常重要的主节点复制协议之一。它处理节点崩溃、消息延迟、网络分区等情况，并通过 view 的变化更换 primary。论文 DOI

这里逐渐出现了后来分布式系统最重要的工具之一：

quorum，多数派Quorum分布式协议中足以代表一次有效决定的节点集合；多数派 quorum 的任意两个集合必然相交。查看详细解释 →。

假设系统里有 (N) 个节点。

多数派大小：

$$q=\lfloor \frac{N}{2}\rfloor +1$$

那么任意两个多数派一定相交，因为：

$$2q>N$$

所以：

$$Q_1\cap Q_2\ne \varnothing$$

这条看起来像小学数学的东西，实际上支撑了大量分布式协议。

例如五台服务器：

$$N=5,q=3$$

哪怕第一轮由：

A B C

确认了一件事情，第二轮由：

C D E

确认另一件事情，两组里至少有一个共同节点 C。

因此历史不会完全断开。

这也是为什么很多分布式系统喜欢：

3 台
5 台
7 台

而不是随便堆很多机器。

机器越多，容错能力虽然增加，但每次要等的多数派也越来越大。

Paxos 和 Raft：大家如何对同一份历史达成一致

1998 年正式发表的 The Part-Time Parliament 描述了后来被称为 Paxos 的算法。Lamport 后来自己解释，这个算法最初来自一个非常实际的问题：怎样让一套复制服务在非拜占庭故障下保持一致，并且当多数节点正常时继续工作。论文页面

Paxos 最核心的问题其实非常简单：

一群服务器提出不同的值，最终怎样保证只有一个值被选中？

可以把节点想象成投票员。

一个 proposer 首先生成一个全局越来越大的 proposal number：

$$n$$

然后询问一群 acceptor：

“编号 (n) 的提案以后归我管行不行？”

acceptor 如果同意，就承诺：

“以后我不再接受编号小于 (n) 的提案。”

如果它以前已经接受过某个值，还必须把自己接受过的最高编号提案告诉新 proposer。

接下来 proposer 不能随便选。

如果这些回复里已经有人接受过值，它必须继承其中编号最高的已接受值。

最终，一个值只有被多数派接受，才算 chosen。

这里真正保证 Paxos 不把历史搞乱的，还是刚才那个非常朴素的事实：

$$Q_1\cap Q_2\ne \varnothing$$

任何两次多数派投票都会留下至少一个“见过过去”的节点。

所以一个已经被多数派选中的值，不会被后来一个完全无关的值悄悄覆盖。

Paxos 的理论其实没有它的名声那么神秘。Lamport 自己后来都觉得大家把它想得过于复杂，所以 2001 年专门写了 Paxos Made Simple；他甚至调侃里面最复杂的公式也不过类似：

$$n_1>n_2$$

真正困难的是：从“选一个值”扩展成“维护一整个不断增长的操作日志”，再处理 leader、重试、节点恢复、成员变化和持久化。 论文页面

真实数据库需要的并不是决定一次：

x = 42

而是不断决定：

log[1] = set x = 42
log[2] = transfer A → B 100
log[3] = delete user 7
...

所有副本只要按照同样的日志顺序执行同样的操作，就会获得相同状态。

这就是 replicated state machine，复制状态机思想。

而 Raft 在 2014 年试图解决的并不是“Paxos 不正确”，而是：

Paxos 太难教、太难理解、也太容易在工程实现时理解错。

Raft 因此非常刻意地把问题拆成三块：

Leader election → Log replication → Safety。

系统经历一个个 term。

每个 term 最多有一个 leader。

客户端请求先进入 leader：

Client
   ↓
Leader
   ↓
append log
   ↓
Followers

日志复制到多数节点后才能提交。

leader 死掉以后，followers 等待一段随机 election timeout，没有收到心跳就开始新一轮选举。

为什么要随机？

如果所有机器都严格在 150ms 后同时竞选：

A：投我！
B：投我！
C：投我！

大家可能不断平票。

随机成：

A：167ms
B：221ms
C：284ms

A 往往已经当选并发送心跳，B 和 C 就不用再选。

Raft 论文的核心目标甚至直接写在标题里：

In Search of an Understandable Consensus Algorithm

它得到的结果与 Multi-Paxos 类型的复制日志系统相当，但作者刻意限制算法状态空间，让人更容易建立正确的直觉。论文中的用户研究也发现学生学习 Raft 比学习 Paxos 更容易。论文页面

所以 Raft 并不是：

“Paxos 2.0。”

更准确地说，它们是在解决非常相似的共识和复制问题，但 Raft 把可理解性本身也当成设计目标。

如果我们不要求所有机器立刻一致呢？

看到这里，很容易形成一种错觉：

分布式系统最终目标就是让所有节点始终保持一致。

其实并不是。

强一致性非常昂贵。

你有上海、纽约、新加坡三个数据中心，如果每次用户点一下“点赞”，都必须等跨洲多数派确认：

上海
 ↓
美国
 ↓
新加坡
 ↓
确认
 ↓
点赞成功

用户大概早就退出 App 了。

于是另一条路线出现了：

有些数据根本没必要每次操作都先达成共识。

CRDTCRDTConflict-free Replicated Data Type允许多个副本独立更新，并通过满足特定数学性质的合并规则在交换到相同更新后自动收敛的数据类型。查看详细解释 → 就属于这种思路。

CRDT，全称 Conflict-free Replicated Data Type，它允许每个副本独立更新，甚至暂时互相断网；只要之后交换到了相同的一组更新，它们就能够按照确定的数学规则收敛到同一个结果。论文 PDF

以一个只能增长的计数器为例。

三台机器各保存一个向量：

$$x=(x_A,x_B,x_C)$$

A 自己增加计数时只修改：

$$x_A\leftarrow x_A+1$$

两个副本重新连接以后，合并方式是：

$${(x\bigsqcup y)}_i=\text{max}(x_i,y_i)$$

最后真正的计数值：

$$\text{value}\left(x\right)=\sum _i{x}_i$$

这里的合并操作 (⊔) 有几个非常漂亮的性质。

交换律：

$$x\bigsqcup y=y\bigsqcup x$$

结合律：

$$(x\bigsqcup y)\bigsqcup z=x\bigsqcup (y\bigsqcup z)$$

幂等律：

$$x\bigsqcup x=x$$

于是：

消息先来后到没关系；

同一条消息重复收到没关系；

不同节点先合并谁也没关系。

最后都会收敛。

这与 Paxos/Raft 的哲学完全不同。

Paxos/Raft 大致是在说：

“大家先商量好顺序，再执行。”

CRDT 则是在说：

“你们先各干各的，只要操作的数学结构允许，我们以后再合并。”

所以 CRDT 并不是“更先进的 Raft”。

它们解决的需求就不一样。

这份经典论文列表里还有一个看起来很突兀的东西：Bitcoin 白皮书。

为什么一份分布式系统经典论文列表会把比特币放进来？

因为它面对的是一个更加极端的问题：

节点不认识彼此、任何人都可以加入，而且参与者甚至可能故意作弊时，怎么让整个网络逐渐形成一份共同认可的历史？

Paxos 和 Raft 通常假定：

我们知道集群里有哪些服务器。

Bitcoin 不可以。

如果简单规定“一台机器一票”，攻击者可以创建一百万台虚假节点。

所以 Bitcoin 使用 Proof of Work，把投票权和计算成本绑定起来。

矿工需要寻找某个 nonce，使：

$$H\left(\text{block header}\right)<T$$

其中 (T) 是当前目标值。

找到这样的 hash 很难，但验证它非常容易。

节点随后倾向于接受累计工作量最大的链作为共同历史。Bitcoin 白皮书本身就是把这个机制用于解决 double-spending，并指出篡改旧区块意味着必须重新完成之后的工作量。

但 Bitcoin 和 Paxos/Raft 还有一个本质差异：

它没有传统共识协议那种立即、绝对的 finality。

两个矿工可能同时找到两个块：

      B1
     /
A —
     \
      B2

短时间内两个版本都可能存在。

等一边积累了更多工作：

A — B1 — C — D
 \
  B2

另一边才逐渐被抛弃。

所以 Bitcoin 给出的更像是：

随着确认数增加，历史被推翻的概率越来越低。

这是概率性的最终确定，而不是 Raft 那种“这一条一旦 commit，就绝不能换成另一条”。

因此把 Bitcoin 放进这条历史里非常有意义：它展示了当系统的信任模型发生变化以后，共识本身也必须换一种形态。

---

回头看这些论文，会发现分布式系统近四十年的核心问题其实一直没有变。

机器越来越快，网络从几十 Kbps 变成几十 Gbps，数据中心的规模也从几台机器变成几十万台机器，但最麻烦的事情仍然是：

我看到的世界，和你看到的世界，可能不是同一个世界。

Lamport 首先告诉我们：没有共同时间时，可以讨论因果。

Chandy 和 Lamport 告诉我们：没有共同“现在”，仍然可以构造一致的全局状态。

Byzantine Generals 告诉我们：节点不仅可能消失，还可能提供相互矛盾的信息。

FLP 告诉我们：有些限制不是算法写得不够聪明，而是模型本身决定的。

Viewstamped Replication、Paxos 和 Raft 继续回答：在现实的 crash fault 世界里，怎样让多个副本维护同一份历史。

CRDT 则反过来问：

如果“所有人立即同意”实在太贵，我们能不能设计一种根本不需要每次协商的数据结构？

Bitcoin 又把问题进一步推向开放网络：

如果连“有哪些参与者”都无法事先确定，又应该怎样建立一份共同历史？

所以这几十年的发展并不是一条“算法 A → 算法 B → 算法 C”的单线演进，而更像是一棵不断分叉的树：

这大概也是学习分布式系统最有价值的视角：

不要先背算法。

先问清楚系统到底允许发生什么：

• 机器会不会宕机？
• 网络最长能延迟多久？
• 节点会不会作恶？
• 必须立即看到最新数据吗？
• 允许暂时分叉吗？
• 需要多久才能恢复？

这些问题一旦确定，Paxos、Raft、CRDT 甚至 Bitcoin 为什么长成现在这个样子，就没有那么神秘了。

参考来源

• Nicolae Vartolomei：Distributed Systems Classics
• Leslie Lamport：Time, Clocks, and the Ordering of Events in a Distributed System
• K. Mani Chandy、Leslie Lamport：Distributed Snapshots
• Leslie Lamport、Robert Shostak、Marshall Pease：The Byzantine Generals Problem
• Michael J. Fischer、Nancy A. Lynch、Michael S. Paterson：Impossibility of Distributed Consensus with One Faulty Process
• Brian M. Oki、Barbara H. Liskov：Viewstamped Replication
• Leslie Lamport：The Part-Time Parliament
• Leslie Lamport：Paxos Made Simple
• Diego Ongaro、John Ousterhout：In Search of an Understandable Consensus Algorithm
• Marc Shapiro 等：Conflict-Free Replicated Data Types