第 16 章

拜占庭将军——1982年，为什么三个人竟然无法保证做出同一个决定？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1978—2014年 · 分布式时钟、拜占庭容错、FLP 不可能性、Paxos、Raft1982年7月，一篇计算机科学论文正式发表。它没有用数据库、处理器或服务器作为标题，而是讲了一个古代军事故事。一群拜占庭将军，率领各自的军队包围一座城市。他们必须统一决定：进攻，还是撤退。如果所有忠诚将军一起进攻，就有机会获胜。如果所有人一起撤退，至少还能保存实力。最危险的情况是：一部分将军进攻，另一部分将军撤退。而他们之间只能通过信使传递消息。更麻烦的是，其中某位将军可能是叛徒。他不仅可能撒谎，而且可能对不同的人说完全不同的话。于是，故事变成一道数学问题：在某些参与者会故意发送矛盾消息的情况下，其他参与者能否保证达成一致？提出这道问题的是三位计算机科学家：Leslie Lamport、Robert Shostak 和 Marshall Pease。他们的论文叫作：The Byzantine Generals Problem——《拜占庭将军问题》。^{[Microsoft Research][lamport.azurewebsites.net]}而它真正研究的，根本不是古代战争。将军是计算机，信使是网络通信，叛徒是可能发送错误或恶意消息的故障节点。这一次，我们将进入算法世界中最难理解、也最有工程价值的领域之一：分布式共识。

第一幕：为什么把一台服务器变成三台，问题反而更复杂？

上一章，我们研究了一致性哈希。它能帮助我们决定一条记录应该存储在哪台服务器。假设现在有三台 PostgreSQL 服务器：A、B、C。它们都保存同一个账户余额。

一个拥有三个副本的账户

节点 A

¥1,000

节点 B

¥1,000

节点 C

¥1,000

现在用户发出一条请求：“扣除100元。”如果一切正常，最终三个副本都应当记录余额900元。但如果执行过程中，网络突然中断呢？A 已经完成扣款。B 尚未收到消息。C 收到消息，却在写入磁盘前宕机。这时三个副本的状态可能不同。于是问题来了：到底哪个结果才是真实的？客户端收到成功响应了吗？如果客户端重试，会不会扣款两次？如果 A 和 B 同时接受不同的写入，又应该如何确定顺序？你可能想到：“既然有三台机器，那就少数服从多数。”但是，我们马上就会发现：多数投票很有用，却并不能自动解决所有分布式一致性问题。尤其当某个节点不只是宕机，而是会说谎时。

第二幕：Lamport 为什么用“拜占庭将军”，而不是直接讲计算机？

Leslie Lamport

1941年出生 · 2013年度 ACM 图灵奖得主对分布式系统、并发计算、逻辑时钟、形式化验证和共识算法作出基础性贡献。

Lamport 很早就意识到，分布式计算中许多令人困惑的错误，并不是因为程序员不会写循环或条件判断。而是因为多台机器之间不存在一个天然共享、立即可见的全局状态。在他的著名论文 Time, Clocks, and the Ordering of Events in a Distributed System（1978）中，他已经深入研究了：如果不同计算机没有完全同步的物理时钟，怎样判断事件之间的先后关系？这项工作产生了著名的 Lamport Logical Clock（逻辑时钟）。但即便我们能够描述事件顺序，也还没有解决一个更棘手的问题：如果某个节点主动提供虚假信息呢？

一个特别有趣的真实历史

Lamport 后来在自己的网站上解释，他觉得某些重要的分布式问题没有得到足够关注。与此同时，Dijkstra 的“哲学家就餐问题”却因为一个生动的故事广为传播。于是 Lamport 得出一个近乎调皮的结论：想让计算机科学家认真对待一道抽象题，给它讲一个吸引人的故事，也许很有用。他与合作者最终采用了拜占庭将军的背景。这个名称非常成功。几十年之后，即使没有研究过原论文的工程师，也经常听说过 Byzantine Fault Tolerance（拜占庭容错）。这个命名背景来自 Lamport 本人对论文的回顾，而不是我们替他编造的心理活动。^{[Microsoft Research]}

第三幕：三位将军，一个叛徒，为什么会出现数学上的“不可能”？

现在进入本章最重要的谜题。假设有三名将军：一名指挥官 C。两名副官 A 和 B。指挥官需要发出进攻或撤退的命令。我们希望系统满足两个要求：一致性：如果 A、B 都忠诚，他们必须执行相同命令。有效性：如果指挥官忠诚，所有忠诚副官必须服从指挥官的真实命令。但现在允许三人之中有一名叛徒。

情况一：指挥官是叛徒

指挥官向 A 说：“进攻！”却向 B 说：“撤退！”

查看 SVG 配图原件

16-004.svg · 点击查看大图

A 和 B 可以互相交换自己听到的命令。于是 A 听到了：指挥官说进攻。B 说指挥官要求撤退。但 A 如何判断：究竟是指挥官在撒谎，还是 B 在撒谎？如果 A 直接相信指挥官，可能违反一致性。如果 A 直接相信 B，可能违反有效性。如果再问一次，叛徒也可以继续发送精心安排的矛盾信息。问题不是简单的“还没有找到一个聪明的投票规则”。而是三人系统中的忠诚节点可能处在无法区分的消息场景中。

情况二：指挥官忠诚，B 是叛徒

指挥官向 A 和 B 都发出“进攻”。但 B 对 A 撒谎：“指挥官告诉我的是撤退。”你会发现，对 A 而言：它听到的消息，可能和上一种情况完全一样。如果一个确定性算法在两种场景中必须做出不同决定，却无法从 A 接收到的信息区分这两种场景，就会陷入矛盾。这正是 Lamport、Shostak 和 Pease 论文中的经典不可能性证明思路。^{[lamport.azurewebsites.net]}

结论：三个人容忍不了一个这样的叛徒

在原论文的同步、完全连接、口头消息模型及相应假设下：如果允许最多

f

个拜占庭故障，想保证协议正确，需要至少：

\boxed{n\geq3f+1}

个参与者。所以：

最多容忍的叛徒数 $f$	至少需要的总人数
0	1
1	4
2	7
3	10
4	13

这里的“四个人容忍一个叛徒”，不是说任意四台服务器、随便投一次票，就可以抵抗所有恶意行为。它是建立在原论文明确通信模型和协议条件之上的数学结论。尤其要注意：原论文随后还研究了不可伪造签名消息的另一种模型，其可实现条件不同，不能把

3f+1

当作所有拜占庭容错协议和所有通信模型下普遍适用的唯一规则。

第四幕：为什么拜占庭故障，比普通服务器宕机危险得多？

这是理解分布式系统的第一道分水岭。

Crash Fault：机器停止工作

假设服务器 B 突然断电。它不再响应消息。这当然很麻烦。但至少它不会同时对 A 说“余额是1000”，对 C 说“余额是500”。对于这种停止响应的故障，我们常使用 Crash Fault（崩溃故障）模型。

Byzantine Fault：机器可能任意错误

现在假设 B 依然在线。它可以：向 A 返回一份数据。向 C 返回另一份数据。伪造自己计算的结果。故意不发送某些消息。或者以不符合协议的方式运行。这种更广泛的故障模型就是 Byzantine Fault。它不一定意味着真实服务器遭到黑客攻击。硬件缺陷、程序错误、数据损坏等，也可能在某些情况下表现出矛盾或任意错误行为。区别是：算法在设计时，必须考虑节点可能不遵守协议。

实验一：一名叛徒可以如何让两位忠诚将军困惑？

三将军的困境

消息不可区分

指挥官是叛徒，对两个副官发送不同命令。

副官 A 收到的信息

指挥官直接告诉 A进攻

B 告诉 A撤退

副官 B 的真实情况

收到指挥官命令撤退

是否忠诚是

请观察副官 A 的视角在两个场景里，A 都直接收到“进攻”，又都听 B 说“撤退”。它没有可靠的证据判定哪一个人是叛徒。

这个模拟只展示了不可能性证明中一个关键的局部视角，并没有模拟原论文的全部消息轮次。但是它已经揭示出真正的难点：分布式节点只能依据自己收到的信息决策，不能像上帝一样看到所有参与者的真实状态。

第五幕：1985年，一篇论文证明：有些共识问题根本无法保证结束

三年后，又出现了一项足以让分布式系统工程师不安的研究。1985年，三位研究者：Michael J. Fischer、Nancy Lynch、Michael S. Paterson在 Journal of the ACM 发表论文：Impossibility of Distributed Consensus with One Faulty Process《存在一个故障进程时分布式共识的不可能性》。这就是著名的 FLP 不可能性定理。^{[cs.cornell.edu]}先问一个简单问题。

如果服务器迟迟没有响应，它究竟是坏了，还是网络太慢？

假设有三台服务器。A 向 B 发送一条消息。十秒过去，B 还没有响应。A 应该怎么办？第一种解释：B 已经崩溃了。第二种解释：网络拥塞，消息还在路上。第三种解释：B 正在工作，只是执行得很慢。从 A 此刻掌握的信息看，这三种解释可能完全无法区分。如果 A 永远等待 B，那么系统可能永远无法继续。如果 A 立即认定 B 已经死亡，那么可能在 B 仍然正常时作出错误推断。于是，Fischer、Lynch 和 Paterson 证明了一项重要结果：在完全异步的消息传递模型中，即使只允许一个进程发生崩溃故障，也不存在能够在所有允许的执行情况下同时保证共识安全要求与最终决定的确定性协议。这里有几个必须读清楚的条件。首先，研究的是完全异步系统：消息可以延迟任意长时间，没有一个普遍可信的固定时限。其次，允许一个进程崩溃。第三，结论涉及确定性算法在所有允许执行中的终止保证。FLP 并不是说现实中的分布式系统永远无法达成共识。现实系统可以利用随机化、实际网络中的时间假设、故障检测器等机制，让协议在适当条件下取得进展。但它告诉我们一个非常重要的边界：不能在毫无时间保证、允许故障的环境中，仅靠一个确定性算法，就要求所有执行都必然及时得出共识。而且，FLP 讨论的崩溃故障，与之前拜占庭将军问题中的任意撒谎故障，是不同的模型。这一点绝对不能混淆。

第六幕：1989年，Lamport 编造了一座岛屿，却真的发明了 Paxos

1989年，Lamport 已经在分布式系统领域工作多年。他开始研究：如果许多计算机都保存同一份状态日志，怎样保证它们对日志中的决定达成一致？他构思出后来著名的 Paxos 算法。但这次，他又决定使用一个故事。故事发生在一个叫 Paxos 的希腊岛屿上。岛上的议员经常外出旅行。消息可能被延迟。部分议员可能暂时无法参与会议。但议会记录必须保持一致。这不是一段真实发生的古希腊议会制度史，而是 Lamport 为解释分布式协议设计的数学寓言。1989年，他写出了论文 The Part-Time Parliament。但论文直到1998年才正式发表。^{[apice.unibo.it]}

为什么 Paxos 如此难懂？

因为它处理的是一种反直觉的问题。可能有多个人同时提出不同的值。有人可能收到部分消息后就崩溃。后来又有其他人发起新的提议。协议不仅要让多数参与者接受某个决定，还必须保证：一旦某个值被真正选定，后续任何合法的提议过程都不能再选定另一个冲突的值。这就是共识协议的安全性核心。在经典 Paxos 中，参与者通常扮演几个逻辑角色：Proposer（提议者）。Acceptor（接受者）。Learner（学习者）。一项提议带有编号。提议者先通过 Prepare / Promise 阶段获得承诺，再通过 Accept 阶段争取接受。而为了保护已经可能被选定的值，后续编号更高的提议有时必须继承先前被接受的值。这最后一点极其重要。如果简单地说：“有五个人，三个人同意，就随便覆盖旧值。”那并不是 Paxos。Paxos 的数学证明，正是围绕不同多数集合必然相交，以及新提议必须尊重已经可能决定的历史展开的。

2001年，发明者不得不再写一篇解释

2001年，Lamport 参加分布式计算学术会议时，发现很多人仍然认为 Paxos 很难理解。他后来回忆，自己已经厌倦了这种说法。于是，他现场向几位同行口头解释算法。回家之后，又专门写出：Paxos Made Simple（《Paxos 简明解释》）。这篇文章发表于2001年12月的 ACM SIGACT News。Lamport 甚至强调，算法本身没有人们想象中那么复杂。^{[Microsoft Research]}阅读 Lamport 2001年《Paxos Made Simple》原始论文不过，一个真实而略带讽刺的后续也值得一提。Lamport 后来指出，自己2001年的文章中存在一句有歧义的表述。有研究者在2015年提醒他，一些开源实现恰好误解了那句话，从而实现出不正确的 Paxos。这再次说明：共识算法最危险的地方，不在于代码量特别大，而在于一个很小的状态转换错误，就可能破坏系统最关键的安全不变量。 ^{[lamport.azurewebsites.net]}

第七幕：2014年，两位研究者决定重新设计一种“容易理解”的共识算法

时间来到2014年。两位斯坦福大学研究者：Diego Ongaro 和 John Ousterhout发表：In Search of an Understandable Consensus Algorithm《寻找一种易于理解的共识算法》。他们提出 Raft。这篇论文获得2014年 USENIX ATC 最佳论文奖。^[USENIX]Raft 并不是简单地宣称：“我们的算法比 Paxos 更正确。”实际上，Paxos 已经具有成熟的数学基础。Raft 的重要目标是：重新组织共识算法的结构，使工程师更容易理解、实现和验证。它把主要问题拆成几个部分：Leader Election（领导者选举）。Log Replication（日志复制）。Safety（安全性）。Membership Changes（成员变更）。这是一种重要的算法设计思想。复杂系统并不一定需要一个全新的数学目标。有时，我们真正需要的，是一种更清晰的机制分解，让每个状态和规则都容易检查。

Raft 的三个节点角色

Follower：跟随者。Candidate：候选者。Leader：领导者。正常情况下，一个 Raft 集群在同一任期中最多存在一位合法领导者。Follower 按领导者提供的日志复制指令同步。如果它长时间没有收到有效的领导者心跳，就可能进入候选者状态，发起选举。但能否赢得选举，还要看投票和日志新旧程度等规则。这也意味着：Raft 的选举不仅是在数人头。它还必须保证一位缺少已提交历史日志的候选者，不能轻易成为破坏安全性的领导者。

第八幕：三台服务器为什么能容忍一台宕机，而两台却不行？

现在终于回到我们最初的数据库集群。假设使用 Raft 这类多数派共识机制。集群有

N

个投票节点。要形成多数派，需要至少：

Q=\left\lfloor\frac N2\right\rfloor+1

个投票节点。因此：

投票节点数	多数派数量	最多可容忍的不可用节点数
1	1	0
2	2	0
3	2	1
4	3	1
5	3	2
7	4	3

所以一个非常反直觉的结论是：从三台服务器增加到四台，并不会提高常见多数派模型下可容忍的故障节点数量。三台可以容忍一台宕机。四台也只能容忍一台宕机。五台才能容忍两台。这也是为什么许多系统更倾向于使用3、5、7这样的奇数规模投票集群。

实验二：你来制造网络分区

Raft 多数派实验室

Crash Fault Model

点击节点，让它上线或下线

当前在线节点数量

3 / 3

需要的多数派

2

当前可否形成多数派

可以

在这组简化模型下，在线节点数量达到多数派门槛。如果网络互通、日志和选举条件也满足，集群可以继续推进共识。

这里模拟的是节点可用数量与多数门槛，不是完整 Raft 网络执行。真实协议还必须检查任期、日志匹配、选举资格以及已提交状态。

为什么必须使用多数派？因为在同一固定投票配置中，任意两个严格多数集合一定有交集。例如三个节点：多数派可能是 A+B。也可能是 B+C。也可能是 A+C。但无论哪两个多数派，都至少共享一个节点。这个重叠，为安全继承已有决定提供了重要基础。注意，交集本身还不足以构成一套正确的协议。我们还需要持久化投票、任期、日志匹配和禁止覆盖已提交历史等规则。但如果没有这种相交性质，就很容易形成两个互不知情、分别决定不同结果的群体。

第九幕：Raft 不是一句“多数同意”，而是一套严格的日志规则

假设有三台服务器：A、B、C。A 当前是 Leader。客户端发送请求：

SET balance = 900

Raft 不会只让 A 修改一下本地内存就告诉客户端成功。典型流程是：

Leader 把操作追加到自己的日志中。
向 Followers 发送日志复制消息。
Followers 检查日志的前置位置和任期是否匹配。
当当前任期的日志条目满足 Raft 的提交规则后，Leader 将其标记为已提交。
已提交日志按照顺序应用到状态机。
Leader 向客户端返回成功，并继续告知其他节点提交进度。

其中必须明确一个容易被忽略的细节。在 Raft 中，Leader 并不能仅仅因为某个旧任期的条目已经复制到多数节点，就直接宣布那个旧条目已提交。Raft 的提交规则对当前任期的日志有更严格要求，以保证领导者切换后的安全。这也是为什么真实 Raft 论文中，需要大量篇幅证明 Leader Completeness、Log Matching 等性质。

Raft 日志复制的简化过程

查看 SVG 配图原件

16-008.svg · 点击查看大图

为什么日志一定需要顺序？

假设我们有两条操作：

1. SET balance = 1000
2. SUBTRACT balance 100

如果某台机器先执行第2条，再执行第1条，结果可能不一样。所以仅仅保证“最终都收到了这些操作”，还不够。我们必须保证：所有正确副本以相同顺序执行相同的确定性操作。这就叫作**复制状态机（Replicated State Machine）**的基本思想。如果初始状态相同，执行的已提交命令序列也相同，并且状态转换是确定性的，那么各副本就能得到一致的结果。

Raft 的简化状态模型

下面不是完整协议，而是说明节点角色可能怎样转换。

from enum import Enum

class Role(Enum):
    FOLLOWER = 1
    CANDIDATE = 2
    LEADER = 3


class Node:
    def __init__(self):
        self.term = 0
        self.role = Role.FOLLOWER
        self.voted_for = None

    def on_election_timeout(self):
        self.term += 1
        self.role = Role.CANDIDATE
        self.voted_for = "self"

    def become_leader(self):
        self.role = Role.LEADER

但真实 Raft 绝不能仅凭调用 become_leader() 就成为有效领导者。它还要验证：是否获得当前任期的多数选票。候选者日志是否满足投票的新旧程度要求。是否收到更高任期的消息。当前配置中哪些节点具有投票资格。以及持久化状态是否已经安全写入。如果漏掉这些检查，就可能产生看起来很像 Raft、但安全性已经被破坏的实现。这恰恰说明：分布式共识是一种必须依靠不变量证明的算法，而不是简单的状态机代码模板。

第十幕：拜占庭容错与 Raft，不能混为一谈

这是整章最重要的一次概念澄清。我们前面讲了1982年的拜占庭将军问题。随后讲了 Paxos 和 Raft。它们都与共识有关，但故障模型不同。Raft 主要针对 Crash Fault，即节点崩溃、失联、重启，以及符合协议模型的消息延迟与丢失等情况。它不承诺抵抗任意恶意节点。例如，假设某个 Raft Follower 被攻击者完全控制。它可以故意发送伪造任期、错误日志或者违反协议的投票行为。这些都超出了经典 Raft 的故障模型。拜占庭容错协议则专门处理这类更广泛的任意错误行为。因此，不能说：“三节点 Raft 可以容忍一个故障，所以三节点就能抵抗一个拜占庭叛徒。”这是错误的。

两类模型的核心区别

问题	Crash Fault Consensus	Byzantine Fault Tolerance
节点可能停止响应	是	是
节点可能向不同人撒谎	不在标准模型中	在模型中
常见容错节点数关系	$2f+1$	常见经典模型 $3f+1$
典型协议	Paxos、Raft	PBFT 等 BFT 协议
工程代价	相对较低	通常需要更复杂通信及验证

这里的

3f+1

应理解为经典无签名拜占庭协议及许多常见 BFT 协议中的节点规模门槛；不是所有拜占庭模型通用的绝对下界。而即使使用数字签名，也仍然需要考虑网络时间假设、协议终止条件、节点成员与密钥管理。从实际工程角度看：如果你的服务器由同一个可信组织运营，主要担心宕机、断网和机器重启，Raft 往往是更直接的研究方向。如果参与节点属于相互不信任的组织，或者确实必须容忍恶意行为，就需要进一步研究拜占庭容错协议。

第十一幕：为什么现实中的数据库离不开这些理论？

现在，我们终于把上一章和这一章连起来了。一致性哈希回答：一条数据应该映射到哪个节点或哪个分片？Raft 这类共识协议回答：同一个复制组里的多个副本，如何就操作顺序和提交结果保持一致？副本复制回答：一台机器坏了，其他机器如何继续保存和提供数据？而事务协议回答：如果一个操作同时修改多个分片，该怎样保证整体事务语义？它们是不同层次的问题。

一个真实的例子：etcd

在 Kubernetes 生态中，etcd 是重要的分布式键值存储系统。其 Raft 实现维护复制日志、领导者选举和成员变更等机制。etcd-io/raft 的公开项目文档明确列出了这些功能，包括日志复制、领导权转移、成员变更、日志压缩以及线性一致性读相关机制。^[GitHub]但 Kubernetes 并不是因为有了 Raft，就不再需要处理其他问题。Kubernetes 控制器仍然要应对网络延迟、任务重试、幂等性和状态收敛。这也说明：共识协议负责建立某些关键状态的共同决定，却不能让整个复杂业务自动变成一致、正确且没有重复操作的系统。对于数据库开发也是一样。假设客户端向服务端发送：

UPDATE account
SET balance = balance - 100
WHERE id = 1;

服务器执行成功，却在返回结果之前断网。客户端不知道请求到底有没有完成。如果直接重试，很可能再次扣款。即使数据库集群使用了 Raft，也不意味着这条业务请求天然具备“恰好执行一次”的语义。通常还需要客户端请求 ID、幂等键、事务边界、操作去重等机制。

第十二幕：一张图理解三十多年的共识算法发展

1978年 · Lamport 的逻辑时钟研究没有统一全局时钟时，怎样描述分布式事件之间的先后关系。

1982年 · 拜占庭将军问题Lamport、Shostak 和 Pease 系统研究存在任意错误节点时的交互一致性与容错边界。

1985年 · FLP 不可能性定理Fischer、Lynch 和 Paterson 证明：在完全异步且允许崩溃故障的模型中，确定性共识不能保证所有允许执行都终止。

1989年构思、1998年发表 · PaxosLamport 通过编号提议与相交多数集合，使分布式参与者能够安全选择共同值。

第 16 章配图 14 — 94rain · 来源 · CC BY-SA 4.0

2014年 · RaftOngaro 和 Ousterhout 通过领导者选举、日志复制和清晰的安全规则，提出更容易教学和实现的共识算法。

终章挑战：三台服务器中，哪一边能够继续写入？

现在有三台服务器 A、B、C。它们组成一个 Raft 集群。某次网络分区之后：A 与 B 还能通信。C 与 A、B 完全失联。假设 A、B 日志条件正常，并且能够选出有效领导者。此时，哪一边可以提交新的 Raft 日志？

你来判断网络分区后的共识能力

A+B 和 C 都能独立提交写入只有 A+B 可以，C 不可以只有 C 可以，因为它独立存在所有节点必须同时在线，否则谁都不能写

尾声：分布式系统最深刻的困难，是你永远看不见整个世界

1982年，Lamport、Shostak 和 Pease 用一个古代将军故事，解释了现代分布式计算最棘手的问题之一。1985年，FLP 定理进一步证明，在某些通信与故障假设下，不可能设计出满足所有理想要求的确定性共识协议。1989年，Lamport 构思 Paxos，后来逐步成为可靠复制系统的重要理论基础。2014年，Ongaro 与 Ousterhout 提出 Raft，试图让安全共识的机制更加清晰、易于理解。这些研究揭示了一种与我们此前学习的算法截然不同的困难。在单机程序里，我们通常能够直接检查变量值。在数组中寻找一个元素，我们能够访问整个数组。在二叉树里搜索，我们知道每一步访问哪个节点。但在分布式系统中：每台机器只能看到自己掌握的信息，而它无法始终判断，自己没有收到的消息究竟是不存在、丢失了，还是仍然在路上。这就是为什么分布式共识需要如此严谨的数学模型。

第十六章知识总结

概念	核心思想
Consensus	多个节点就同一决定达成一致
Crash Fault	节点停止工作或无法正常响应
Byzantine Fault	节点可能发送任意错误或矛盾信息
$3f+1$	经典无签名拜占庭模型下的节点规模要求
FLP	完全异步且允许故障时的确定性终止不可能性
Paxos	借助编号提议、承诺与相交多数集合保护已决定值
Raft	通过领导者选举与日志复制实现可理解的崩溃容错共识
Quorum	能够形成多数派的节点集合
Replicated State Machine	多个副本按相同顺序执行确定性命令
Safety / Liveness	分别关注不发生错误，以及最终能取得进展

本章历史原始资料

Lamport、Shostak、Pease（1982）：《The Byzantine Generals Problem》Fischer、Lynch、Paterson（1985）：FLP 不可能性论文 Lamport（1998）：《The Part-Time Parliament》Lamport（2001）：《Paxos Made Simple》Ongaro、Ousterhout（2014）：《In Search of an Understandable Consensus Algorithm》etcd-io/raft：可研究的实际 Raft 实现

下一章预告

第十七章：布隆过滤器——1970年，为什么计算机敢说“肯定没有”，却只能说“可能存在”？

1970年，Burton Howard Bloom 发表了一篇论文：Space/Time Trade-offs in Hash Coding with Allowable Errors《允许错误的哈希编码中的空间与时间权衡》。他研究了一种特别有意思的结构：只使用很少的存储空间，就能快速判断某个元素是否可能存在于一个集合中。它有一个看起来很矛盾的特点：如果回答“不存在”，在标准模型下它一定正确。如果回答“存在”，却可能判断错误。为什么设计一种明知道可能回答错误的数据结构，反而可以大幅节省内存？下一章，我们将从 Bloom 1970年的真实论文出发，研究布隆过滤器（Bloom Filter）的发明、哈希函数与位数组之间的关系，以及数据库、缓存和大规模网络系统为什么愿意接受这种可控的误判。而最令人意外的是：通过一个简洁的概率公式，我们竟然可以在创建数据结构之前，就大致算出它需要多少内存，以及误判率会有多高。