联兴 | 欣赏《分布式共识机制运行原理》

本文重点介绍由空间分离的计算机形成的分布式系统。

注意：在本文中，节点、计算机、组件和进程可能相互指代。 网络和系统也可以相互引用。

2.分布式系统的特点

每个分布式系统都有自己的特点，包括：

2.1 并发

系统中的进程并发运行，这意味着多个事件同时发生。 换句话说，网络中的每台计算机都独立地同时执行事件，这需要协作。

Lamport, L (1978)。 分布式系统中的时间、时钟和事件排序

2.2 没有统一的时间安排

分布式系统需要某种方法来确定事件发生的顺序，以便它发挥作用。 然而，由于一组在不同地理位置的计算机同时运行，有时很难判断事件的先后顺序。 换句话说，没有单一的时间系统来确定网络上所有计算机的时间顺序。

在 Leslie Lamport 的论文“Time, Clocks, and Chronological Order in Distributed Systems”中，他展示了一种推断事件顺序的方法，可以归纳为以下几点：

1.信息只有发送才能接收。

2. 每台计算机都有自己的事件序列。

通过确定事件的顺序，我们可以得到系统中的部分事件顺序。 Lamport 的论文描述了一种算法，该算法要求系统中的每台计算机都从其他计算机接收信号。 这样，就可以从偏序中推导出完备序。

但是，如果事件的顺序完全以这种方式确定，则可能会因外部用户的观察而产生偏差。 因此，本文也表示，这种异常情况是允许的。

Lamport 最后讨论了如何通过使用正确同步的物理时钟来防止这种异常情况。

但特别是：协调独立时钟是一个非常复杂的计算机科学问题。 即使一串时钟最初设置准确，一段时间后时钟也会开始出现错误。 这是由于“时钟漂移”导致时钟以略微不同的速率滴答的现象。

从本质上讲，Lamport 的论文表明，事件的时间和顺序是实现空间分离的分布式计算机系统的根本障碍。

2.3 组件的故障独立性

理解分布式系统的一个重要方面是承认分布式系统中的组件可能会失败。 所以它被称为“容错分布式计算”。

没有故障的系统是不可能的。 无论是进程崩溃、信息丢失、失真、重复、网络分区延迟或丢失消息，甚至进程因恶意攻击而完全崩溃，真实的系统都可能受到某些缺陷或不足的影响。

一个不受故障影响的系统是不可能的。

这些失败大致可以分为三类：

考虑到这些问题，协议的设计使得具有故障组件的系统仍然可以实现共同目标并提供有用的服务。

考虑到每个系统都会发生故障，构建分布式系统时必须考虑的一个核心问题是，当系统偏离正常运行时，故障是由于非恶意行为（即崩溃或遗漏）还是恶意行为（即拜占庭故障），系统能否继续正常工作。

从广义上讲，构建分布式系统有两种模式：

1）单一容错

在一个单一的容错系统中，系统的所有部分只有两种情况比特币分布式的实现原理，要么严格遵守协议，要么失败。 这种系统肯定能处理节点下线或故障的问题，但不一定能处理节点的异常或恶意行为。

2A) 拜占庭容错

单一的容错系统不适用于不受控制的系统。 在分布式系统中，节点由独立参与者控制并通过开放、分散的互联网进行通信，协议的设计必须考虑到参与者表现出拜占庭行为的可能性。 因此，在拜占庭容错系统中，我们假设节点可能出错或出现恶意行为。

2B) BAR容错

虽然大多数系统的设计都是为了满足拜占庭容错，但也有专家认为这些设计过于笼统，没有考虑到“理性”错误的可能性，节点可能会因为个人兴趣而偏离原来的行为。 也就是说，节点可以是可靠的，也可以是不可靠的，这取决于动机。 如果激励足够诱人，即使是大多数节点也会变得不可靠。

理论上，这被定义为 BAR 模型，它同时考虑了拜占庭错误和理性错误。 BAR 模型假设了三种类型的参与者：

2.4 信息传输

分布式系统中的通信和协作是通过计算机之间的信息传递来完成的。 信息传输可以根据任何协议完成，无论是 HTTP 还是 RPC，甚至是为特定目的构建的自定义协议。 有两种信息传输环境：

1）同步

在同步系统中，假定消息在固定的已知时间内传递。

同步信息传输在理想状态下并不是很复杂，因为当信息发出后，接收方会在一定时间范围内收到，用户在某种意义上获得了一种保证。 这允许用户在建立协议时固定消息到达时间的上限。

但这种环境在真正的分布式系统中并不实用，因为计算机可能会宕机、掉线，信息可能会丢失、重复、延迟或无法接收。

2）异步

在异步消息传递系统中，我们假设网络将永远延迟消息传递，无序地复制或传递消息。 也就是说，无法确定信息传输时间的上限。

3、分布式系统中的共识机制是什么意思？

至此，我们了解了分布式系统的特点：

接下来我们将重点讨论如何在分布式系统中达成共识。 但值得重申的是：分布式计算有数百种硬件和软件架构。

最常见的形式是复制状态机

3.1 状态复制器

状态复制器是一种确定性状态机，可以跨机器复制并且表现得像单个状态机。 这些计算机中的任何一台都可能发生故障，但状态复制器仍会运行。

在状态复制器中，如果交易有效，一组输入值将导致系统状态切换到下一个交易。 事务是数据库中的原子操作。 所以它要么完全完成，要么从未完成。 保存在状态复制器中的一组事务称为事务日志。

从一个有效状态到下一个有效状态的切换逻辑称为“状态切换逻辑”。

也就是说，状态复制器是一系列从相同初始值开始的分布式计算机。 每个状态转换都需要所有进程来决定。 共识意味着所有计算机必须就下一个输出值达成一致。

反过来，这会在系统中的每台计算机上维护一致的事务日志（即“实现共同目标”）。 状态复制器必须持续接受新的交易记录（例如，提供有效的服务），而不管以下任何情况：

1.部分电脑出现故障。

2.网络不可靠，信息无法传递，延迟传递，或乱序传递

3、没有统一的时间安排来确定事件的先后顺序。

这是分布式算法的基本目标。

3.2 共识问题

如果满足以下条件，则算法达成共识：

从广义上讲，共识算法通常假设系统中存在三种类型的参与者：

提议者，通常被称为领导者或协调者。

Acceptors，节点，听取提议者的意见并以相应的值做出回应。

学习者，系统中接收最终值的其他节点，

一个共识算法通常有以下三个步骤：

第一步：选举

第二步：投票

第三步：决定

值得注意的是，每种共识算法都有不同的：

尽管如此，只要我们能够利用这个标准化的流程来构建一个能够保证这些条件的算法，那么我们就可以实现一个共识的分布式系统。

很简单比特币分布式的实现原理，不是吗？

3.3 FLP 不可能

并不真地。 . . 但这是可以预料的。

回想一下我们如何区分同步和异步系统：

这种区别是至关重要的。

共识在同步环境中是可行的，因为所有消息都在特定时间范围内到达。 因此，在这种类型的系统中，我们可以让不同的节点轮流提出新的交易，对其进行投票，并跳过任何没有在时限内提供提案的节点。

但如前所述，除了受控系统（由原子钟控制的数据中心）之外，假设系统在同步环境中运行是不现实的。 实际上，大多数环境不支持同步环境。 所以必须基于异步环境来设计。

如果交付截止日期的假设在异步环境中不成立，那么实现“完成”就困难得多。 请记住，达成共识的条件之一是“最终性”，所有非故障节点必须决定输出某个值。

这就是所谓的“FLP 不可能”。

即使是单个故障节点也会阻止确定性异步节点达成共识。

在 Fisher、Lynch 和 Paterson (FLP) 1985 年的论文“The Impossibility of Distributed Consensus in the Presence of Abnormal Nodes”中，他们讨论了故障节点如何阻止确定性异步节点达成共识。 简而言之，节点故障发生的时间是不可知的，因此有可能恰好在无法达成共识的时间点发生故障。

这一结果对于分布式计算领域来说是一个巨大的挫折。 尽管如此，科学家们仍在继续努力寻找避免 FLP 不可能实现的方法。

从顶层设计的角度来看，有两种方法可以避免FLP的不可能性：

使用同步性假设

使用不确定性

4. 方法一：使用同步性假设

让我们回顾一下不可能的结果。 这样想：FLP 不可能的结果表明，如果我们不能在系统中取得进展，我们就无法达成共识。 也就是说，如果信息的传递是异步的，就不能保证“完成”。 Finality 是达成共识的必要条件，这意味着每个非故障节点最终都必须决定一些输出值。

但是如果我们不确定信息是否会在异步网络中传输成功，我们如何保证每个非故障节点都能输出一定的值呢？

需要明确的是，调查结果并未表明无法达成共识。 只是说由于异步的原因，无法在固定时间内达成一致。 So Impossible 在这里仅仅意味着“不总是可能的”。 这个细节既微妙又重要。

避免这种情况的一种方法是使用超时设置。 如果确定下一个值没有进展，则等待超时并重新开始所有步骤。 这就是像 Paxos 和 Raft 这样的共识算法所做的。

4.1 帕克索斯

Paxos 在 1990 年代推出，是第一个真实世界的、实用的、容错的共识算法。 它也是第一个被广泛采用的共识算法，Leslie Lamport 验证了它的正确性，全球互联网公司如谷歌和亚马逊也用它来构建分布式服务。

Paxos的机制如下：

第 1 阶段：准备请求

提议者选择一个编号为（n）的新提议，并向接受者发送请求。

接收者收到准备请求 ("prepare," n)，如果 n 大于接收者已响应的任何请求的数量，则接收者发出 ("acknowledge, "n,n',v') 或 ("承认，“n，^，^）。

acceptor 承诺不接受任何编号小于 n 的提案。

接受者从他们接受的编号最高的提案 (n) 中提出值 (v)。 否则，他们会回应^

第二阶段：接受请求

如果提议者收到大多数接受者的回应，他可以发出一个接受请求，其中包括一个数字 n 和一个值 v ("Accept," n, v)

n 是准备请求中的数字 n

v 是编号最高的提案中的值。

如果没有响应编号更高的提案，接受者将在收到（“接受”n，v）后接受该提案。

第三阶段：学习阶段

当acceptor接受proposal时，它发送("accept" n, v)给所有的learner。

学习者从大多数接收者那里接收（“接受”n，v），同意 v，然后发送（“同意”v）给其他学习者。

其他学习者收到（“同意”v），并同意 v。

来源：

众所周知，所有的分布式系统都有故障。 在该算法中，如果提议者异常（例如存在遗漏失败），那么决策可能会延迟。 尽管之前的尝试并没有结束，但 Paxos 在第一阶段通过使用新的版本号解决了这个问题。

我不会详细介绍这个过程，在这种情况下节点恢复正常运行非常复杂，因为节点会介入并推动解决过程向前发展。

Paxos难懂的主要原因是它的实现细节需要读者自己脑补：如何知道proposer有异常？ 是不是需要同步时钟建立一个超时时间来判断proposer异常需要进入下一轮？

为了提供实施灵活性，关键领域的一些规范是开放的。 诸如领导者选举、故障检测和日志管理之类的事情是模糊的或完全未定义的。

这种设计选择最终成为 Paxos 最大的缺点之一。 它不仅晦涩难懂，而且实施起来也很困难。 这反过来又使得分布式系统领域难以掌握。

现在，您可能想知道同步性假设从何而来。

在Paxos中，虽然算法中没有规定超时设置，但是在实现过程中，经过几个超时时间后的proposer选择是关闭的必要条件。 否则，接收器无法保证输出下一个值，系统可能会停顿。

4.2 木筏

Ongaro 和 Ousterhout 于 2013 年发布了 Raft，这是一种基于状态复制器的共识算法，其核心目标是可理解性（与 Paxos 相反）。

Raft 提出的重要创新是利用共享超时的设置来实现“finality”。 在 Raft 中，如果 crash 重启，需要等待一个超时时间来重新选举 leader 并保证贡献。

4.3 “拜占庭环境”

虽然 Paxos 和 Raft 等传统共识算法能够在使用某种程度的同步假设（即超时）的异步环境中正常运行，但它们仅对崩溃具有容错性，而不是拜占庭容错性。

节点崩溃故障更容易排除故障，因为我们可以将节点工作或崩溃模拟为 0 或 1。节点不能恶意行为或作弊。 所以在容错系统中，分布式系统只需要大多数人达成共识。

在一个开放的、去中心化的系统中（如区块链公链），用户无法控制其他节点。 每个节点根据自己的利益做出决策，这可能会与其他节点发生冲突。

节点在拜占庭系统中有不同的激励机制，可以作弊，可以合作，可以任意行动，仅仅达成共识是不够的。 一半或更多被认为可靠的节点可以相互合作说谎。

例如，在拜占庭系统中，领导者可以与其他节点建立强连接，这可能危及整个系统。 回想一下，系统模型只能容忍简单故障或拜占庭故障。 Raft和Paxos是简单容错而不是拜占庭容错。 它们并非旨在容忍恶意行为。

4.4 “拜占庭将军”问题

“拜占庭将军”难题是研究如何建立一个可靠的计算机系统，可以处理提供有争议信息的节点。 拜占庭容错协议不仅要能够抵抗节点的恶意行为，还要完成共同的目标。

在 Leslie Lamport、Robert Shostak 和 Marshall Pease 的论文“拜占庭将军问题”中，首次证明了“拜占庭将军问题”的解决方案：如果系统中有 x 个拜占庭节点，则必须有至少有 3x+1 个节点达成共识。

原因如下：

如果x个节点发生故障，系统需要与nx个节点协作以维持正常协作（x个节点可能出现简单故障/拜占庭故障或无响应）。 但也有可能x个节点都没有响应，也不是故障。 如果希望非故障节点数大于故障节点数，需要满足nxx>x。 即n>3x+1是最优的情况。

但是，该论文中演示的算法仅适用于同步环境。 我们似乎只能解决拜占庭或异步问题中的一个。 一个同时满足拜占庭容错和异步环境的设计看起来很难。

为什么？

简而言之，构建一个既兼容异步环境又兼容拜占庭容错的共识算法就像创造了一个奇迹。

像 Paxos 和 Raft 这样的算法是众所周知的并被广泛使用。 但是也有很多学术研究专注于解决拜占庭容错+异步环境。

4.5 DLS算法

Dwork、Lynch 和 Stockmeyer（“DLS”）的论文“Consensus Mechanisms in Partially Synchronous Systems”在拜占庭容错共识机制方面取得了重大进展：它提出了一种在部分同步系统中达成共识的模型。

如前所述，在同步系统中，消息从一个节点发送到另一个节点所需的时间有一个已知的固定上限。 在异步系统中，没有固定的上限。 部分同步系统介于这两个极端之间。

该论文解释了部分同步假设的两个版本：

DLS算法的工作机制如下：

轮次分为“尝试”和“解锁”阶段：

每一轮都有一个提议者，从每个节点开始提供他们认为有价值的东西。

如果至少 Nx 个节点都通过该值，则提议者提议该值。

当节点收到提议者提议的值时，它必须锁定该值并传播消息。

如果proposer收到信息说x+1个节点都锁定了同一个值，那么就确定这个值作为最终值。

DLS 是一个重要的突破，因为它创建了新的网络假设类别并证明了共识是可能的。 DLS 论文的另一个重要成果是将拜占庭和异步环境中的共识要素分为安全性和生存性两部分。

安全

这是前面讨论的共识的另一种表述，其中所有非故障节点都同意相同的输出值。 如果安全性能得到保证，系统可以保持统一的步调。 为了排除故障和恶意行为者，我们希望所有节点就事务日志的顺序达成一致。 没有安全保证意味着最终将至少有两个事务日志。

可行性

这是前面讨论的最终性的另一种表达，即所有非故障节点最终决定了某个输出值。 在区块链中，“生存能力”是指不断产生有效区块。 生存能力非常重要，因为它是网络继续运行的唯一途径，否则它将停滞不前。

在 FLP impossibility 中，共识机制无法在完全异步的系统中实现。 DLS论文认为，只要建立部分同步假设以满足生存性条件，就可以克服FLP不可能性。

因此，本文证明了该算法可以在没有同步环境前提的情况下实现安全条件。

说得深一点，如果节点不决定输出某个值，系统就会关闭。 因此，如果“完成”由某些同步假设（例如，超时）保证并且其中之一失败，则系统也可能会停止。

但是，如果我们设计一个带有（保证正确性）超时的算法，如果同步假设不成立，则存在多个有效事务日志的风险。

设计分布式系统总是涉及权衡取舍。

这可能比之前的选项更可怕。 如果服务被破坏（例如没有安全性），那么保持服务活动（生存能力）就没有意义了。 基本上，两个不同区块链的存在比整个区块链停滞更糟糕。

分布式系统总是有取舍的。 如果你想克服一些限制（比如 FLP 不可能），你必须牺牲其他一些东西。 在这种情况下，将要素分离为安全性和生存性是非常明智的。 它允许我们构建一个在异步环境中安全的系统，但仍然需要某种形式的超时来继续生成新值。

DLS 论文虽然很详细，但是并没有被广泛使用，也没有解决现实世界的拜占庭问题。 这可能是因为 DLS 算法中的一个核心假设是使用同步处理器时钟来获得共同的时间概念。 实际上，同步时钟容易受到许多攻击，并且在拜占庭容错环境中表现不佳。

4.6 PBFT算法

另一种拜占庭容错算法是 Miguel Castro 和 Barbara Liskov 于 1999 年发表的“Practical Byzantine Fault Tolerance”（PBFT），被认为是解决拜占庭难题的更实用的算法。

“实用”是指它可以在像互联网这样的异步系统中运行，并且通过一些优化，比原来的共识算法更快。 该论文认为，以前的算法虽然“理论上可行”，但要么太慢而无用，要么为安全起见假定同步。 这在异步环境中是非常危险的。

简而言之，PBFT 在假设 (n-1)/3 个节点发生故障的情况下保证了安全性和生存性。 这是允许拜占庭容错的最小节点数。 因此，该算法的弹性是最优的。

无论有多少故障节点，该算法都能保证安全。 也就是说，它的安全性不需要以同步为前提。 但生存能力确实需要同步性。 至少(n-1)/3个节点可以失效，信息的延迟不能高于一定的时限。 因此，PBFT 通过使用同步假设来保证活性来规避 FLP 不可能。

PBFT算法经过一系列的评审，每一次评审都有一个主节点（比如leader），其他的作为“备份”。 工作机制是这样的：

当新交易发生时，它首先传播到主节点。

主节点传播到所有其他备份节点。