分布式核心问题

随着摩尔定律遇到瓶颈，越来越多情况下要依靠分布式架构，才能实现海量数据处理能力和可扩展计算能力。

区块链系统，首先是一个分布式系统。传统单节点结构演变到分布式系统，碰到的首要问题就是一致性的保障。很显然，如果分布式集群无法保证处理结果保持一致的话，那人和建立于其上的业务系统都无法正常工作。

此处将介绍分布式系统领域的核心问题，包括一致性、共识的定义，基本的原理和算法，另外介绍一些评估分布式系统可靠性的指标。

一致性问题

一致性问题是分布式领域最为基础也是最为重要的问题。如果分布式系统能实现“一致”，对外就可以呈现为一个完美的、可扩展的“虚拟节点”，相对物理节点具备更优越的性能和稳定性。这也是分布式系统希望能实现的最终目标。

问题与挑战

• 节点之间的网络通信是不可靠的，包括消息延迟、乱序和内容错误等。
• 节点的处理时间无法保障，结果可能出现错误，甚至节点自身可能发生宕机。
• 同步调用可以简化设计，但会严重降低分布式系统的可扩展性，甚至使其退化为单点系统。

一致性要求

• 可终止性（termination）：一致的结果在有限时间内能完成
• 约同性（agreement）：不同节点最终完成决策的结果是相同的
• 合法性（validity）：决策的结果必须是某个节点提出的提案

共识算法

共识（consensus）在很多时候会与一致性（consistency）术语放在一起讨论。严谨地讲，两者含义并不完全相同。

一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一直行、线性一致性，描述了多个节点对数据状态的维护能力。而共识则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。因此，一致性描述的是结果状态，共识则是一种手段。达成某种共识并不意味着就保障了一致性。

实践中，要保障系统满足不同程度的一致性，核心过程我那个网需要通过共识算法来达成。共识算法解决的是对某个天大家达成一致意见的过程。

问题与挑战

如果分布式系统中哥哥单节点都能保证以十分完美的性能（瞬间相应、超高吞吐）无故障运行，节点之间通信瞬时送达，则实现共识过程并不十分复杂，简单地通过广播进行瞬时投票和应答即可。

然而现实中，这样的“理想”情况并不存在。不同节点之间通信存在延迟（光速物理限制，通信处理延迟），并且任意环节都可能存在故障（系统规模越大，发生故障可能性越高）。如通信网络会发生中断、节点发生故障、甚至存在恶意节点故意伪造消息，破坏系统正常工作流程。

一般来说，把出现故障（crash 或 fail-stop，即不响应）但不会伪造信息的情况成为“非拜占庭错误”（non-Byzantine Fault）或“故障错误”（Crash Fault）；伪造信息恶意响应的情况称为“拜占庭错误”（Byzantine Fault），对应节点为拜占庭节点。

常见算法

根据解决的是非拜占庭错误情况还是拜占庭错误情况，共识算法可以分为 Crash Fault Tolerance（CFT）类算法和 Byzantine Fault Tolerance（BFT）类算法。

针对常见的非拜占庭错误情况，已经存在一些经典的解决算法，包括 Paxos、Raft 及其变种等。这类容错算法往往性能比较好，处理较快，容忍不超过一半的故障节点。

对于要能容忍拜占庭错误的情况，一般包括 PBFT（Practical Byzantine Fault Tolerance）为代表的确定性系列算法、PoW 为代表的概率算法等。对于确定性算法，一旦达成对某个结果的共识就不可逆转，即共识是最终结果；对于概率类算法，共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，成为事实上的最终结果。拜占庭类容错算法往往性能较差，容忍不超过1/3的故障节点。

此外，XFT（Cross Fault Tolerance）等最近提出的改进算法可以提供类似 CFT 的处理响应速度，并能在大多数节点正常工作时提供 BFT 保障。

理论界限

FLP 不可能原理：即便在网络通信可靠情况下，可扩展的分布式系统的共识问题，其通用解法的理论下限是——没有下限（无解）。

FLP 不可能原理

定义

在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

FLP 不可能原理实际上告诉人们，不要浪费时间，去为异步分布式系统设计在任意场景下都能实现共识的算法。

正确理解

要理解 FLP，首先要搞清楚“异步”的含义。在分布式系统中，同步和异步这两个属于存在特殊的含义。

同步是指系统中的各个节点的时钟误差存在上线；并且消息传递必须在一定时间内完成，否则认为失败；同时各个节点完成处理消息的时间是一定的。对于同步系统，可以很容易地判断消息是否丢失。

异步是指系统中各个节点可能存在较大的时钟差异，同时消息传输时间是任意长的，各节点对消息进行处理的时间也可能是任意长的，这就造成无法判断某个消息迟迟没有响应是哪里出了问题（节点故障还是传输故障？）。不幸的是，现实生活中的系统往往都是异步系统。

FLP不可能性在原始论文中以图论的形式进行了严格证明。要理解这一基本原理并不复杂，一个不严谨的例子如下。

三个人在不同房间进行投票（投票结果是0或者1）。彼此可以通过电话进行沟通，但经常有人会时不时睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。此时，A 和 B 将永远无法在有限时间内获知最终的结果，究竟是 C 没有应答还是应答的时间过长。如果可以重新投票，则类似情形可以在每次取得结果前发生，这将导致共识过程永远无法完成。

FLP 原理实际上说明对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。即便对于非拜占庭错误的前提下，包括 Paxos、Raft 等算法也都存在无法达成共识的情况，只是在工程实践中这种情况出现的概率很小。

那么，FLP 不可能原理是否意味着研究共识算法压根没有意义？

先别这么悲观。学术界做研究，往往考虑地是数学和物理意义上最极端的情形，很多时候现实生活要美好得多（感谢这个世界如此鲁棒！）。例如，上面例子中描述的最坏情形，每次都发生的概率其实并没有那么大。工程实现上多尝试几次，很大可能就成功了。

科学告诉你什么是不可能的；工程则告诉你，付出一些代价，可以把它变成可行。这就是科学和工程不同的魅力。

那么，退一步讲，在付出一些代价的情况下，我们在共识的达成上，能做到多好？回答这一问题的是另一个很出名的原理：CAP 原理。

提示：科学告诉你去赌场赌博从概率上总会是输钱的；工程则告诉你，如果你愿意接受最终输钱的风险，中间说不定能偶尔小赢几笔呢！

CAP 原理

CAP 原理最早是 2000 年由 Eric Brewer 在 ACM 组织的一个研讨会上提出猜想，后来 Lynch 等人进行了证明。该原理被认为是分布式系统领域的重要原理之一。

定义

CAP 原理：分布式计算系统不可能同时确保以下三个特性：一致性（Consistency）、可用性（Availability）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证。

这里，一致性、可用性和分区容忍性的含义如下：

• 一致性：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性；

• 可用性：在有限时间内，任何非失败节点都能应答请求；

• 分区容忍性：网络可能发生分区，即节点之间的通信不可保障。

比较直观地理解如下，当网络可能出现分区的时候，系统是无法同时保证一致性和可用性的。要么，节点收到请求后因为没有得到其他节点的确认而不应答（牺牲可用性），要么节点只能应答非一致的结果（牺牲一致性）。

由于大多数时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（多数场景下），要么牺牲掉可用性。

注意：网络分区是可能存在的，出现分区情况后很可能会导致发生“脑裂”，多个新出现的主节点可能会尝试关闭其他主节点。

应用场景

既然 CAP 三种特性不可同时得到保障，则设计系统时必然要弱化对某个特性的支持。那么可能出现下面三个应用场景。

弱化一致性

对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才最终更新成功，期间不保证一致性。例如网站静态页面内容、实时性较弱的查询类数据库等，简单分布式同步协议如 Gossip，以及 CouchDB、Cassandra 数据库等，都是为此设计的。

弱化可用性

对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。MongoDB、Redis、MapReduce 等是为此设计的。Paxos、Raft 等共识算法，主要处理这种情况。在 Paxos 类算法中，可能存在着无法提供可用结果的情形，同时允许少数节点离线。

弱化分区容忍性

现实中，网络分区出现概率较小，但较难完全避免。两阶段的提交算法，某些关系型数据库及 ZooKeeper 主要考虑了这种设计。实践中，网络可以通过双通道等机制增强可靠性，达到高稳定的网络通信。

ACID 原则

ACID 原则指的是：Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性），用了四种特性的缩写。

ACID 也是一种比较出名的描述一致性的原则，通常出现在分布式数据库领域。具体来说，ACID 原则描述了分布式数据库需要满足的一致性需求，同时允许付出可用性的代价。

ACID 特征如下：

• Atomicity：每次操作是原子的，要么成功，要么不执行；

• Consistency：数据库的状态是一致的，无中间状态；

• Isolation：各种操作彼此之间互相不影响；

• Durability：状态的改变是持久的，不会失效。

与 ACID 相对的一个原则是 BASE（Basic Availability，Soft-state，Eventual Consistency）原则，牺牲掉对一致性的约束（但实现最终一致性），来换取一定的可用性。

注意：ACID 和 BASE 在英文中分别是“酸”和“碱”，看似对立，实则是分别对 CAP 三特性的不同取舍。

Paxos 算法与 Raft 算法

Paxos 问题是指分布式的系统中存在故障（crash fault），但不存在恶意（corrupt）节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。这也是分布式共识领域最为常见的问题。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

Paxos 算法

1990 年由 Leslie Lamport 在论文《The Part-time Parliament》中提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos 算法被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。Leslie Lamport 作为分布式系统领域的早期研究者，因为相关成果获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

Paxos 是第一个广泛应用的共识算法，其原理基于“两阶段提交”算法并进行泛化和扩展，通过消息传递来逐步消除系统中的不确定状态，是后来不少共识算法（如 Raft、ZAB 等）设计的基础。Paxos 算法基本思想并不复杂，但最初论文描述得比较难懂，后来在 2001 年 Leslie Lamport 还专门写了论文《Paxos Made Simple》予以解释。

算法的基本原理是将节点分为三种逻辑角色，在实现上同一个节点可以担任多个角色：

• Proposer（提案者）：提出一个提案，等待大家批准（chosen）为结案（value）。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色；

• Acceptor（接受者）：负责对提案进行投票，接受（accept）提案。往往由服务端担任该角色；

• Learner（学习者）：获取批准结果，并可以帮忙传播，不参与投票过程。可能为客户端或服务端。

算法需要满足Safety和Liveness两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的：

• Safety 约束：保证决议（value）结果是对的，无歧义的，不会出现错误情况。

· 只有是被 Proposers 提出的提案才可能被最终批准；

· 在一次执行中，只批准（chosen）一个最终决议。被多数接受（accept）的结果成为决议；

• Liveness约束：保证决议过程能在有限时间内完成。

· 决议总会产生，并且学习者能获得被批准的决议。

基本过程是多个提案者先争取到提案的权利（得到大多数接受者的支持）；得到提案权利的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。

Paxos 不保证系统随时处在一致的状态。但由于每次达成一致的过程中至少有超过一半的节点参与，这样最终整个系统都会获知共识的结果。一个潜在的问题是 Proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新一轮提案的 Proposer 都恰好故障，又或者两个 Proposer 恰好依次提出更新的提案，则导致活锁，系统永远无法达成一致（实际发生概率很小）。

Paxos 能保证在超过一半的节点正常工作时，系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案，会发现在满足各种约束情况下，算法过程会十分类似于 Paxos 的过程。

下面，由简单情况逐步推广到一般情况来探讨算法过程。

单个提案者+多接受者

如果系统中限定只有某个特定节点是提案者，那么共识结果很容易能达成（只有一个方案，要么达成，要么失败）。提案者只要收到了来自多数接受者的投票，即可认为通过，因为系统中不存在其他的提案。

但此时一旦提案者故障，则系统无法工作。

多个提案者+单个接受者

限定某个节点作为接受者。这种情况下，共识也很容易达成，接受者收到多个提案，选第一个提案作为决议，发送给其他提案者即可。

缺陷也是容易发生单点故障，包括接受者故障或首个提案者节点故障。

以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。

当提案者和接受者都推广到多个的情形，会出现一些挑战。

多个提案者+多个接受者

既然限定单提案者或单接受者都会出现故障，那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。

一种情况是同一时间片段（如一个提案周期）内只有一个提案者，这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生，例如按照时间、序列、或者大家猜拳（出一个参数来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案，怎么对他们进行区分呢？这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的，提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大（往往意味着是接受新提出的，因为旧提案者故障概率更大）的提案。

如何为提案分配序号呢？一种可能方案是每个节点的提案数字区间彼此隔离开，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

同时允许多个提案意味着很可能单个提案人无法集齐足够多的投票；另一方面，提案者即便收到了多数接受者的投票，也不敢说就一定通过。因为在此过程中投票者无法获知其他投票人的结果，也无法确认提案人是否收到了自己的投票。因此，需要实现两个阶段的提交过程。

两阶段的提交

提案者发出提案申请之后，会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了，一种结果是没被接受。没被接受的话，可以过会再重试。即便收到来自大多数接受者的答复，也不能认为就最终确认了。因为这些接受者并不知道自己刚答复的提案是否可以构成大多数的一致意见。

很自然，需要引入新的一个阶段，即提案者在第一阶段拿到所有的反馈后，需要再次判断这个提案是否得到大多数的支持，如果支持则需要对其进行最终确认。

Paxos里面对这两个阶段分别命名为准备（Prepare）阶段和提交（Commit）阶段。准备阶段通过锁来解决对哪个提案内容进行确认的问题，提交阶段解决大多数确认最终值的问题。

准备阶段：

• 提案者发送自己计划提交的提案的编号到多个接收者，试探是否可以锁定多数接收者的支持；

• 接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（如果还未接受过任何提案，则为空）给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。

提交阶段：

• 提案者如果收到大多数的回复（表示大部分人听到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功。则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求；

• 接受者收到“接受消息”后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。

一旦多数接受者接受了共同的提案值，则形成决议，成为最终确认。

Raft算法

Paxos 算法的设计并没有考虑到一些优化机制，同时论文中也没有给出太多实现细节，因此后来出现了不少性能更优化的算法和实现，包括Fast Paxos、Multi-Paxos 等。最近出现的 Raft 算法，算是对 Multi-Paxos 的重新简化设计和实现，相对也更容易理解。

Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出。Raft 算法面向对多个决策达成一致的问题，分解了 Leader 选举、日志复制和安全方面的考虑，并通过约束减少了不确定性的状态空间。

Raft 算法包括三种角色：Leader（领导者）、Candidate（候选领导者）和 Follower（跟随者），决策前通过选举一个全局的 Leader 来简化后续的决策过程。Leader 角色十分关键，决定日志（log）的提交。日志只能由 Leader 向 Follower 单向复制。

典型的过程包括以下两个主要阶段：

• Leader 选举：开始所有节点都是 Follower，在随机超时发生后未收到来自 Leader 或 Candidate 消息，则转变角色为 Candidate，提出选举请求。最近选举阶段（Term）中得票超过一半者被选为 Leader；如果未选出，随机超时后进入新的阶段重试。Leader 负责从客户端接收 log，并分发到其他节点；

• 同步日志：Leader 会找到系统中日志最新的记录，并强制所有的 Follower 来刷新到这个记录，数据的同步是单向的。

注意：此处日志并非是指输出消息，而是各种事件的发生记录。

拜占庭问题与算法

拜占庭问题（Byzantine Problem）更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭容错（Byzantine Fault Tolerant，BFT）算法讨论的是在拜占庭情况下对系统如何达成共识。

两将军问题

在拜占庭将军问题之前，就已经存在两将军问题（Two Generals Paradox）：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致？根据 FLP 不可能原理，这个问题无通用解。

拜占庭问题

拜占庭问题又叫拜占庭将军问题（Byzantine Generals Problem），是 Leslie Lamport 等科学家于 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图干扰共识的达成。拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。

论文中指出，对于拜占庭问题来说，假如节点总数为N，叛变将军数为F，则当 N ≥ 3F+1 时，问题才有解，由 BFT 算法进行保证。

例如，N = 3，F = 1 时。

提案人不是叛变者，提案人发送一个提案出来，叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。

提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。

更一般的，当提案人不是叛变者，提案人提出提案信息 1，则对于合作者来看，系统中会有 N-F 份确定的信息 1，和 F 份不确定的信息（可能为 0 或 1，假设叛变者会尽量干扰一致的达成），N - F > F，即 N > 2F 情况下才能达成一致。

当提案人是叛变者，会尽量发送相反的提案给 N - F 个合作者，从收到1的合作者看来，系统中会存在（N - F）/ 2 个信息 1，以及（N - F）/ 2 个信息 0；从收到 0 的合作者看来，系统中会存在（N - F）/ 2 个信息 0，以及（N - F）/ 2 个信息 1；另外存在 F - 1 个不确定的信息。合作者要想达成一致，必须进一步对所获得的消息进行判定，询问其他人某个被怀疑对象的消息值，并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。

Leslie Lamport 等人在论文《Reaching agreement in the presence of faults》中证明，当叛变者不超过 1/3 时，存在有效的拜占庭容错算法（最坏需要 F+1 轮交互）。反之，如果叛变者过多，超过 1/3，则无法保证一定能达到一致结果。

那么，当存在多于 1/3 的叛变者时，有没有可能存在解决方案呢？

设想 F 个叛变者和 L 个忠诚者，叛变者故意使坏，可以给出错误的结果，也可以不响应。某个时候 F 个叛变者都不响应，则 L 个忠诚者取多数即能得到正确结果。当 F 个叛变者都给出一个恶意的提案，并且 L 个忠诚者中有 F 个离线时，剩下的 L-F 个忠诚者此时无法分别是否混入了叛变者，仍然要确保取多数能得到正确结果，因此，L - F > F，即 L > 2F 或 N - F > 2F，所以系统整体规模 N 要大于 3F。

能确保达成一致的拜占庭系统节点数至少为 4，此时最多允许出现 1 个坏的节点。

拜占庭容错算法

拜占庭容错算法（Byzantine Fault Tolerant，BFT）是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能故障情况下如何达成共识。拜占庭容错算法最早的讨论在 1980 年 Leslie Lamport 等人发表的论文《Polynomial Algorithms for Byzantine Agreement》，之后出现了大量的改进工作。长期以来，拜占庭问题的解决方案都存在复杂度过高的问题，直到PBFT算法的提出。

1999 年，Castro 和 Liskov 于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出的 Practical Byzantine Fault Tolerant（PBFT）算法，基于前人工作进行了优化，首次将拜占庭容错算法复杂度从指数级降低到了多项式级，目前已得到广泛应用。其可以在失效节点不超过总数 1/3 的情况下同时保证 Safety 和 Liveness。

PBFT算法采用密码学相关技术（RSA 签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。

算法的基本过程如下：

• 首先通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）；
• 在某个视图中，客户端将请求（REQUEST，operation，timestamp，client）发送给主节点，主节点负责广播请求到所有其他副本节点；
• 所有节点处理完成请求，将处理结果（REPLY，view，timestamp，client，id_node，response）返回给客户端。客户端检查是否收到了至少 f+1 个来自不同节点的相同结果，作为最终结果。

主节点广播过程包括三个阶段的处理：预准备（pre-prepare）阶段、准备（prepare）阶段和提交（commit）阶段。预准备和准备阶段确保在同一个视图内请求发送的顺序正确；准备和提交阶段则确保在不同视图之间的确认请求是保序的；

• 预准备阶段：主节点为从客户端收到的请求分配提案编号，然后发出预准备消息（PRE-PREPARE，view，n，digest，message）给各副本节点，其中 message 是客户端的请求消息，digest 是消息的摘要；

• 准备阶段：副本节点收到预准备消息后，检查消息合法，如检查通过则向其他节点发送准备消息（PREPARE，view，n，digest，id），带上自己的 id 信息，同时接收来自其他节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少 2f + 1 个验证过的消息才进入准备状态；

• 提交阶段：广播 commit 消息，告诉其他节点某个提案n在视图v里已经处于准备状态。如果集齐至少 2f + 1 个验证过的 commit 消息，则说明提案通过。

具体实现上还包括视图切换、checkpoint 机制等，可自行参考论文内容，在此不再赘述。

新的解决思路

拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且要完成最终一致性确认过程十分困难，容易受干扰。

比特币的区块链网络在设计时提出了创新的 PoW（Proof of Work）概率算法思路，针对这两个环节进行了改进。

首先，限制一段时间内整个网络中出现提案的个数（通过增加提案成本）；其次是放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓展。系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出相应的经济代价（超过整体系统一半的计算力）。

后来的各种 PoX 系列算法，也都是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。

可靠性指标

可靠性（availability），或者说可用性，是描述系统可以提供服务能力的重要指标。高可靠的分布式系统往往需要各种复杂的机制来进行保障。

通常情况下，服务的可用性可以用服务承诺（Service Level Agreement，SLA）、服务指标（Service Level Indicator，SLI）、服务目标（Service Level Objective，SLO）等方面进行衡量。

几个9的指标

很多领域里谈到服务的高可靠性，都喜欢用几个 9 的指标来进行衡量。几个 9，其实是概率意义上粗略反映了系统能提供服务的可靠性指标，最初是电信领域提出的概念。

下表给出同指标下每年允许服务出现不可用时间的参考值。

一般来说，单点的服务器系统至少应能满足两个 9；普通企业信息系统三个 9 就肯定足够了（大家可以统计下自己企业内因系统维护每年要停多少时间），系统能达到四个 9 已经是领先水平了（参考 AWS 等云计算平台）。电信级的应用一般需要能达到五个 9，这已经很厉害了，一年里面最多允许出现五分钟左右的服务不可用。六个 9 以及以上的系统，就更加少见了，要实现往往意味着极高的代价。

两个核心时间

一般地，描述系统出现故障的可能性和故障出现后的恢复能力，有两个基础的指标：MTBF 和 MTTR

• MTBF（Mean Time Between Failures）：平均故障间隔时间，即系统可以无故障运行的预期时间；

• MTTR（Mean Time to Repair）：平均修复时间，即发生故障后，系统可以恢复到正常运行的预期时间。

MTBF 衡量了系统发生故障的频率，如果一个系统的MTBF很短，则往往意味着该系统可用性低；而 MTTR 则反映了系统碰到故障后服务的恢复能力，如果系统的 MTTR 过长，则说明系统一旦发生故障，需要较长时间才能恢复服务。

一个高可用的系统应该是具有尽量长的 MTBF 和尽量短的 MTTR。

提高可靠性

如何提升系统的可靠性呢？有两个基本思路：一是让系统中的单个组件都变得更可靠；二是干脆消灭单点。

IT 从业人员大都有类似的经验，普通笔记本电脑，基本上是过一阵可能就要重启一下；而运行 Linux/Unix 系统的专用服务器，则可能连续运行几个月甚至几年时间都不出问题。另外，普通的家用路由器，跟生产级别路由器相比，更容易出现运行故障。这些都是单个组件可靠性不同导致的例子，可以通过简单升级单点的软硬件来改善可靠性。

然而，依靠单点实现的可靠性毕竟是有限的。要想进一步地提升，那就只好消灭单点，通过主从、多活等模式让多个节点集体完成原先单点的工作。这可以从概率意义上改善服务对外的整体可靠性，这也是分布式系统的一个重要用途。

小结

分布式系统是计算机科学中十分重要的一个研究领域。随着现代计算机集群规模的不断增长，所处理的数据量越来越大，同时对于性能、可靠性的要求越来越高，分布式系统相关技术已经变得越来越重要，起到的作用也越来越关键。

分布式系统中如何保证共识是个经典的技术问题，无论在学术上还是工程上都存在很高的研究价值。令人遗憾地是，理想的（各项指标均最优）解决方案并不存在。在现实各种约束条件下，往往需要通过牺牲掉某些需求，来设计出满足特定场景的协议。通过本文的学习，读者可以体会到在工程应用中的类似设计技巧。

实际上，工程领域中不少问题都不存在一劳永逸的通用解法；而实用的解决思路是，合理地在实际需求和条件限制之间进行灵活的取舍。