科普 | 分布式共识的工作原理，Part-3：使用同步假设的共识算法
(接上文）在分布式系统中，如何解决 FLP 不可能问题？
方法1：使用同步性假设
我知道你们在嘀咕：这究竟是啥？
让我们回头审视一下 FLP 不可能性问题。这里有个新的视角：FLP 不可能性表明，如果我们无法推进整个系统，就无法达成共识。换言之，如果消息是异步发送的，termination 条件就无法得到保证。回忆下，要达成共识的其中一项条件是“ termination ”，也就是说每个非故障节点最终必须选定某个输出值。
但是在异步通信网络里，我们不知道消息何时会被发送，我们怎么保证每个非故障进程都选定了一个输出值？
要澄清一下，这个发现没有证明共识不能达成。而且——因为消息异步传递，所以“不可能”在固定时间达成共识——这里说的“不可能”，指的是共识“并非总能”达成。这是个微妙但至关重要的细节。
这个规避 FLP 不可能问题的方法就是引入超时（timeout）的概念。如果在确认下个值的过程没有进展，我们会等到超时，然后重新进行共识的步骤。如我们所见，Paxos 和 Raft 使用的就是这类共识算法。
Paxos
Paxos 于 90 年代提出，是首个应用在真实世界、实用的、容错的一致性共识算法，它的正确性（correctness）被 Leslie Lamport 所证明。许多跨国互联网公司，如 Google 和 Amazon 也用其构建分布式服务，是个被广泛采用的共识算法之一。
Paxos 工作方式如下：
阶段1：准备请求
提案者选择新的提案号（n），然后向接收者发送“准备请求”。
当接收者收到准备请求 (“prepare,” n)，且 n 比已经接收到的其他准备请求大，接收者会发出消息 (“ack,” n, n’, v’) 或 (“ack,” n, ^ , ^)。
接收者承诺不会再接纳任何提案号小于 n 的准备请求。
如果有的话，接收者会发出具有最高提案号的提案值（v），反之则发出 ^ 。
阶段2：接收请求
如果提案者收到大多数接收者的响应，则可以发出带有提案号 n 和价值 v 的接收请求 (“accept,” n, v) 。
n 是准备请求中出现的数字。
v 是响应中具有最高提案号的提案值。
当收到接收请求(“accept,” n, v)，接收者就会采纳这个请求。除非接收者已经采纳了大于 n 的提案号。
阶段3：学习阶段
每当接收者采纳了一个提案，就会向所有学习者返回 (“accept,” n, v)。
学习者从多数接收者那儿得到 (“accept,” n, v)，选定最终的值 v，然后向其他学习者发送 (“decide,” v)。
学习者收到 (“decide,” v) 和最终决定的值 v。
哈！你被绕晕了没？现在你有许多信息要消化，但...稍等一等。
我们知道，每个分布式系统都有故障。在这个算法中，如果提案者故障（比如，出现丢包错误），则最终决定允许被延后。面对此类问题，Paxos 会重新在阶段 1 提交新的提案号，即使之前的操作还没有终止。
想要从上述错误中将程序引导回正常流程是一件非常复杂的事，因为进程会插手并驱动这整个流程，所以我不想深入讨论。
Paxos 之所以晦涩难懂的主因，就是它将许多实现细节留给读者自行想象：我们如何知道提案者发生故障？是否使用同步时钟设置超时条件，来判别提案者故障与否，让整个系统能进入下个循环？
为了提供部署的灵活性，Paxos 描述的许多主要特性都是开放式的。比如领导者选举、侦错、日志管理等等内容，都非常模糊甚至完全没有提到。
后来，这种设计选择成为 Paxos 最大的缺点之一。它不仅难以理解，而且难以实施。反过来说，这使得分布式系统的领域非常难以驾驭。
现在你可能开始好奇：似乎上面完全没用到同步假设，那为什么把 Paxos 归为这一类算法呢？
虽然在 Paxos 算法中没有明确的定义超时，但在实际部署时，发生超时之后选择新的提案者是满足 termination 的必要条件。否则，我们无法保证接收者会输出下一个值，这会导致系统停止运转。
Raft
2013 年，Ongaro 和 Ousterhout 为 Raft 复制状态机提出了一种新型共识算法，其核心目标是可理解性（不像 Paxos 那样难懂）。
我们从 Raft 中学到的一个非常重要且新颖的东西是使用共享超时机制处理 termination 的概念。在 Raft 中，如果节点宕机并重启后，在试图声明成为领导者（Leader）之前，需要至少等待一个超时周期，并且一定会有所进展。
等等……那么在 “拜占庭” 环境下又如何呢？
虽然诸如 Paxos 和 Raft 的传统共识算法能够使用某种程度的同步假设（即超时机制），在异步环境下正常运行，但是它们并不是拜占庭容错的。它们仅仅能够容忍宕机故障。
因为我们能够将处理过程设置/建模为工作或宕机（即，0 或 1 ）的状态，使得宕机故障能够更容易处理。进程不能作恶或说谎。因此，在一个宕机容错的系统中，分布式系统使用简单的“少数服从多数”的方式，就能够达成共识。
在一个开放且去中心化的系统中（例如：公有链），用户无法控制网络中的节点。相反，每个节点根据自己的目标行事，并且可能与其他节点的目标相冲突。
在拜占庭系统中，节点有着不同的动机，可以撒谎、协作或者任意行事，不能假设简单的“少数服从多数”的方式就足以达成共识。一半或者超过一半的节点可以联合起来作恶。
如果一个当选的领导人是拜占庭式的（即作恶节点），并且与其他节点的网络连接很通畅，那么它可能危及系统。回想一下我们刚刚说过的，我们必须为我们的系统建模，以容忍简单的错误或拜占庭错误。Raft 和 Paxos 是简单的容错共识机制，并不能容忍拜占庭错误。它们不是为了容忍恶意行为而设计的。
“拜占庭将军问题”
试图建立一个可靠的计算机系统，使其能够协调提供冲突信息的进程达成共识，便是所谓的“拜占庭将军问题”。一个拜占庭容错协议应该在部分节点作恶的情况下，能够达成其共同的目标（共识）。
Leslie Lamport、Robert Shostak 和 Marshall Pease 撰写的这篇 “拜占庭将军问题（Byzantine General’s Problem）” 的论文，提出了第一种解决拜占庭将军问题的证明：该论文指出一个有 x 个拜占庭节点的系统中，必须总共至少有 3x+1 个节点才能够达成共识。
具体原因如下：
如果 x 个节点有错误，那么系统需要在 n - x 个节点间通过协作的方式正确运行（因为 x 个节点可能有错误或者为拜占庭式节点，并且没有响应）。然而，我们必须能够处理没有响应的 x个节点可能不是出错的情况，这 x 个节点可能确实有响应。如果我们希望非故障节点数量大于故障节点数量，那么我们至少需要 n - x - x > x。因此，n > 3x + 1 是最优值。
然而，这篇论文所描述的算法仅适用于同步环境。真是懒蛋！看来我们只能让其中一个（拜占庭式或异步）成立，能在同时满足异步和拜占庭假设的分布式系统中运行的算法比这个还要更难设计。
为什么呢？
简而言之，构建一个既能满足异步环境又能保证拜占庭容错的共识算法……emmm，就像创造奇迹一样。
共识算法有像 Paxos 和 Raft 这样知名且广泛使用的，但也有大量的学术研究更多地关注解决拜占庭+异步环境的共识问题。
So……系好安全带！
我们要去实地考察一下……
到……
理论学术论文去！
Okay, Okay——我很抱歉这么说。但你不觉得很有意思吗！还记得我们之前提到的“创造奇迹”吗？我们来看看两种算法（DLS 和 PBFT），它们让我们比以往任何时候都更接近于打破拜占庭+异步环境困局。
DLS算法
Dwork、Lynch 和 Stockmeyer （因此该算法叫 “DLS” 算法）的论文 “部分同步环境下的共识算法（Consensus in the Presence of Partial Synchrony）” 介绍了一种拜占庭容错共识主要进展：其定义了在“部分同步系统”中达成共识的模型。
你还可能记得，在同步系统中，消息从一个处理器发送到另一个处理器所需的时间有一个已知的固定上界。在异步系统中，并没有消息传递的固定上界，而部分同步系统介于这两种极端之间。
这篇论文解释了两种部分同步系统：
假定消息传播存在固定上界，但上界并不是初始确定的（即，先验上界）。系统目标是在不获知实际上界的情况下达成共识。
假定消息传播的上界是已知的，但是只保证从某个未知的时间点（也称作 “全局标准时间（Global Standardization Time，GST）”）开始保持不变。目标是设计一个无论何时都能够达成共识系统。
DLS 算法是这样工作的：
系统运行的每一轮被分为 “尝试” 和 “锁定释放” 阶段。
每一轮都有一个提议者，并且在每一轮开始后，进程之间互相通讯，发布它们认为正确的数值。
如果至少有 n - x 个进程向提议者发送某个相同的值，则提议者向全网“发布”这个数值。
当一个进程收到提议者提出的数值时，它必须将这个值锁定，并且广播这个数值给其他进程。
如果提议者从 x+1 个进程中收到它们已经锁定了某个值，则提议者将该值提交为最终数值。
DLS 是一项重大突破，因为它创造一种新型网络假设类型（即，部分同步），并且证明在这种假设情况下能够达成共识。DLS 论文的另一个重要结论是将在拜占庭和异步设置中达成共识的关注点分为两部分：安全性（safety）和活性（liveness）。
（译者注：
安全性：错误的事情永远不会发生
活性：正确的事情一定会发生（尽管不知道何时发生））
安全性
这是描述我们之前讨论的 “一致性” 属性的另一个术语，即所有没有错误的进程能够就相同的输出达成共识。如果我们能够保证安全性，我们就能够保证整个系统保持同步。尽管存在故障节点或恶意节点，我们依旧希望所有节点就事务（或者说区块链中的交易）日志的总顺序能够达成共识。违反安全性意味着我们最终将得到两个或多个有效的事务日志。
活性
这是描述我们之前讨论的 “可终止性” 属性的另一个术语，即每个没有错误的节点最终就某个输出值达成共识。在区块链场景中，“活性” 意味着区块链持续增加合法的新区快。活性是非常重要的是，因为它是网络持续有效的唯一途径 —— 否则区块链系统将停滞。
从 FLP 不可能性问题我们知道，完全异步的系统无法达成共识。DLS 论文认为，假设系统环境为部分同步，那么就足以克服 FLP 不可能性问题，从而达到活性状态。
因此，该文证明 DLS 算法不需要任何同步假设就可以达到安全性状态。
很简单，对吧？如果还觉得困惑也不用担心。让我们再深入一点。
需要记住的是，如果系统中节点没有决定某个输出数值，那么系统就会停止。因此，使用同步假设（即超时机制）来保证 terminaton 是有意义的，因为只要其中一个同步假设被打破，网络就应该中止。
但是如果我们设计一个假设超时（以保证正确性）的算法，那么如果同步假设失效，就有产生两个合法事务日志的风险。
这比之前的选择危险的多。如果服务被破坏（即不安全），那么提供有用的服务（即活性）是没有意义的。基本上，有两个不同的区块链比让整个区块链网络停止更加糟糕。
分布式系统设计总是需要权衡利弊。如果想克服某些限制（例如，FLP 不可能问题），就必须在其他地方做出牺牲。在这种情况下，将关注点划分为安全性与活性是非常机智的。它使得我们能够构建一个在异步环境中安全的系统，但仍然需要某些超时机制以保证能够持续产生新的数据。
尽管 DLS 论文解决了各方面问题，但是 DLS 算法并没有在真实拜占庭环境中广泛实现或使用。这可能是由于 DLS 算法中的一个核心假设是使用同步处理器时钟来同步时间。事实上，同步时钟很容易受到攻击，并且在拜占庭容错环境中表现不佳。
PBFT 算法
另一种拜占庭容错算法，由 Miguel Castro 和 Barbara Liskov 于 1999 年发表，叫做 “实用拜占庭容错（Practical Byzantine Fault-Tolerance，PBFT）”。对于具有拜占庭行为的系统，PBFT 被认为是一种更实用的算法。
从这个意义上说，“实用” 意味着它能够在类如互联网的异步环境中工作，算法中的部分优化，使其比先前的共识算法更加快速。该论文指出，先前的共识算法虽然被证实 “理论上可行”，但要么太慢无法使用，要么需要为了安全性而假设完全同步。
正如我们所讲到的，先前共识算法的设计在异步环境下是非常危险的。
简而言之，PBFT 算法假设在 (n-1)/3 个节点发生故障的情况下，它依旧能够保障安全性与活性。正如我们之前讨论的，这是达成拜占庭容错所需处理的最小节点数。因此，该算法的弹性是最优的。
只要小于一定比例，无论有多少节点出错，该算法都能够保障安全性。换句话说，它无需为保障安全性而假设同步环境。然而，PBFT 算法的活性依赖于网络同步。最多容许 (n-1)/3 个节点出错，且消息延迟的增长速度不会超过某一具体时间限制。因此，PBFT 通过使用同步假设保证活性来绕过 FLP 不可能性问题。
PBFT 算法通过一系列 “视图” 运行，每个视图有一个 “主” 节点（即，领导者），其他节点称为 “备份”节点。下面是它具体工作流程：
在一台客户端上发生了一个新事务，并被广播给主节点。
主节点将该事务广播给所有 “备份” 节点。
各备份节点执行该事务，并给客户端发送一条回复消息。
客户端期望从备份节点收到 x + 1 个相同回复。这个相同的回复就是最终结果，并且系统的状态会发生相应转变。
如果领导者没有故障，那么协议就能正常工作。然而，检测恶意/坏的主节点并重新选取主节点的过程（也叫做“视图更改”）非常低效。例如，为了达成共识，PBFT 的信息交换量将达到 O(n^2) 级别，即每台计算机都需要与网络中其他所有计算机通讯。
插播：我会用另一篇独立的博客完整解释 PBFT 算法！以后再说 ;)。
尽管 PBFT 算法相较于之前的算法有了一定的改进，但在具有大量参与者的实际用例（例如：公有链）中，它仍不够实用。但是，与 Paxos 相比，至少在故障检测以及领导者选举这类事情上，它要更具体，更实用。
需要承认 PBFT 的贡献。它包含了一些重要的突破性思想，这些思想是新型共识协议（特别是在后区块链世界中）可以借鉴和使用的。
例如，Tendermint 就是一种受 PBFT 影响很深的新型共识算法。在它们的 “验证” 阶段，Tendermint 使用与 PBFT 相似的两次投票方式决定最终值。Tendermint 算法最主要的不同是比 PBFT 更加实用了。
Tendermint 每轮都会换一个新的领导者。如果本轮领导者在一段时间内没有响应，那么将跳过该领导者，算法将简单地进入具有新领导者的下一轮。实际上，这比每次改变视图或选新领导者都需要使用点对点连接通信的方式更有意义。
原文链接:
https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95
作者: Preethi Kasireddy
翻译&校对: stormpang、安仔 clint & 阿剑
本文由作者授权 EthFans 翻译及再出版。
你可能还会喜欢：
干货 | 共识算法的比较：Casper vs Tendermint