分布式共识如何运作？

MartinFowler推荐的文章，论述区块链技术的关键概念，以及中本共识为何如此重要？

分布式系统可能难以理解，主要是因为围绕它们的知识也是分布式的。现在，经过多次考验和磨难，我终于准备好向您解释分布式系统的基础知识。

区块链迫使工程师和科学家重新审视并质疑分布式计算中根深蒂固的范式。

我还想讨论区块链技术对该领域的深远影响。区块链迫使工程师和科学家重新审视并质疑分布式计算中根深蒂固的范式。也许没有其他技术能够比区块链更快地促进这一研究领域的进展。

分布式系统绝不是新的。科学家和工程师花费了数十年时间研究这一主题。但是区块链与它们有什么关系呢？好吧，如果分布式系统首先不存在，那么区块链所做的所有贡献都是不可能的。

本质上，区块链是一种新型的分布式系统。它始于 比特币 的出现，并从此在分布式计算领域产生了持久的影响。因此，如果您想真正了解区块链的工作原理，那么掌握分布式系统的原理至关重要。

不幸的是，很多关于分布式计算的文献要么难以理解，要么分散在太多的学术论文中。为了使问题更复杂，有数百种架构，所有架构都满足不同的需求。将其归结为易于理解的框架非常困难。

因为这个领域很广，我不得不仔细选择我可以覆盖的东西。我还必须进行概括以掩盖一些复杂性。请注意，我的目标不是让你成为该领域的专家。相反，我想给你足够的知识，以启动你的分布式系统和共识的旅程。

阅读完这篇文章之后，你将更加掌握：

• 什么是分布式系统，
• 分布式系统的属性，
• 在分布式系统中达成共识意味着什么，
• 理解基础共识算法（例如DLS和PBFT），以及
• 为什么Nakamoto Consensus是一个大问题。

我希望你已经准备好学习，因为课程正在开课。

什么是分布式系统？

分布式系统涉及一组不同的进程（例如，计算机）将消息彼此传递且协调以实现共同目标（即，解决计算问题）。

分布式系统是一组协同工作以实现统一目标的计算机。

简而言之，分布式系统是一组共同努力实现统一目标的计算机。虽然这些过程是分开的，但系统对最终用户来说只是一台计算机。

正如我所提到的，分布式系统有数百种架构。例如，单个计算机也可以被视为分布式系统：中央控制单元，存储器单元和输入 - 输出通道是协作以完成目标的单独过程。

在这篇文章中，我们将专注于分布式系统，其中进程代表的是空间分离的计算机(节点服务器)

分布式系统的属性

每个分布式系统都有一组特定的特征。这些包括：

A）并发

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

这需要协调。

协调就需要时间，时钟和事件排序

B）缺乏全球时钟

要使分布式系统工作，我们需要一种方法来确定事件的顺序。但是，在一组同时运行的计算机中，有时不可能说两个事件中的一个事先发生，因为计算机在空间上是分开的。换句话说，没有一个全局时钟可以确定网络中所有计算机上发生的事件序列。

在“ 分布式系统中的时间，时钟和事件排序”一文中 ，Leslie Lamport展示了如何通过记住以下因素来推断一个事件是否在另一个事件之前发生：

1. 消息在收到之前发送。
2. 每台计算机都有一系列事件。

通过确定哪个事件发生在另一个事件之前，我们可以获得系统中事件的 部分排序 。Lamport的论文描述了一种算法，该算法要求每台计算机都能监听系统中每台其他计算机。通过这种方式，可以 基于该部分 排序 完全排序 事件。

但是，如果我们将顺序完全基于每台计算机监听到的事件，我们可能会遇到此顺序与系统外部用户所感知的不同的情况。因此，该算法会发生异常行为。

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

但是等等 - 有一个巨大的警告：协调独立的时钟是一个非常复杂的计算机科学问题。即使您最初准确地设置了一堆时钟，时钟也会在一段时间后开始出现差异。这是由于“ 时钟漂移” ，这是一种时钟以稍微不同的速率计算时间的现象。

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

C）组件的独立故障

理解分布式系统的一个关键方面是承认分布式系统中的组件存在故障。这就是它被称为“容错分布式计算”的原因。

系统没有故障是不可能的。真正的系统存在许多可能的缺陷或缺陷，无论这是一个进程崩溃; 消息丢失，扭曲或重复; 延迟或丢弃消息的网络分区; 甚至一个进程完全失控，并根据一些恶意计划发送消息。

系统没有故障是不可能的。

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

• 崩溃 - 失败：组件在没有警告的情况下停止工作（例如，计算机崩溃）。
• 省略：组件发送消息但其他节点未接收到消息（例如，消息被丢弃）。
• 拜占庭：该组件表现得任意。这种类型的故障在受控环境（例如，Google或Amazon数据中心）中无关紧要，在这些环境中可能没有恶意行为。相反，这些错误发生在所谓的“对抗性上下文”中。基本上，当一组分散的独立行动者充当网络中的节点时，这些行动者可能选择以“拜占庭”的方式行事。这意味着他们会恶意选择更改，阻止或不发送消息。

考虑到这一点，目标是设计协议，允许具有故障组件的系统仍然实现共同目标并提供有用的服务。

鉴于每个系统都有故障，我们在构建分布式系统时必须考虑的核心因素是，即使其部件偏离正常行为，它是否能够存活，无论是否由于非恶意行为（即崩溃失败或遗漏错误）或恶意行为（即拜占庭故障）。

从广义上讲，制作分布式系统时需要考虑两种类型的模型：

1）简单的容错

在一个简单的容错系统中，我们假设系统的所有部分都执行以下两种操作之一：它们要么完全遵循协议，要么失败。这种类型的系统绝对应该能够处理脱机或失败的节点。但它不必担心节点表现出任意或恶意行为。

2A）拜占庭容错

简单的容错系统在不受控制的环境中不是很有用。在一个分散的系统中，节点由独立的参与者控制，在开放的，无权限的互联网上进行通信，我们还需要设计选择恶意或“拜占庭”的节点。因此，在拜占庭容错系统中，我们假设节点可以失败或恶意。

2B）BAR容错

尽管大多数真实系统都设计为能够承受拜占庭故障，但 一些专家认为 这些设计过于笼统，并未考虑“理性”故障，如果符合自身利益，节点可能会出现偏差。 。换句话说，取决于激励，节点可以是诚实的和不诚实的。如果激励措施足够高，那么即使是大多数节点也可能不诚实地行事。

更正式地说，这被定义为BAR模型 - 一个指定拜占庭和理性失败的模型。BAR模型假设有三种类型的角色：

• 拜占庭：拜占庭节点是恶意的，并试图搞砸你。
• 利他主义：诚实的节点总是遵循协议。
• Rational理性： Rational节点只有在适合它们时才遵循协议。

D）消息传递

如前所述，分布式系统中的计算机通过一台或多台其他计算机之间的“消息传递”进行通信和协调。消息可以使用任何消息传递协议传递，无论是HTTP，RPC还是为特定实现构建的自定义协议。消息传递环境有两种类型：

1）同步

在同步系统中，假设消息将在某个固定的已知时间内传送。

同步消息传递在概念上不那么复杂，因为用户有一个保证：当他们发送消息时，接收组件将在特定时间范围内获得它。这允许用户使用固定的上限来建模他们的协议，该上限是消息到达其目的地所需的时间。

但是，在真实的分布式系统中，这种类型的环境并不十分实用，因为计算机可能会崩溃或脱机，并且可能会丢弃，复制，延迟或无序接收消息。

2）异步

在异步消息传递系统中，假设网络可能无限延迟消息，复制消息或无序传递消息。换句话说，消息接收的时间长度没有固定的上限。

在分布式系统中达成共识意味着什么

到目前为止，我们已经了解了分布式系统的以下属性：

• 进程的并发性
• 缺乏全球时钟
• 有问题的流程
• 消息传递

接下来，我们将专注于理解在分布式系统中实现“共识”意味着什么。但首先，重申我们之前提到的内容非常重要：数百种用于分布式计算的硬件和软件架构。

最常见的形式称为复制状态机。

复制状态机

复制状态机是一种确定性状态机，它在许多计算机上复制，但作为单个状态机运行。这些计算机中的任何一台都可能出现故障，但状态机仍然可以运行。

在复制状态机中，如果事务有效，则一组输入将导致系统状态转换到下一个事务。事务是对数据库的原子操作。这意味着操作要么全部完成，要么根本不完成。在复制状态机中维护的事务集称为“事务日志”。

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

换句话说，复制状态机是一组分布式计算机，它们都以相同的初始值开始。对于每个状态转换，每个进程决定下一个值。达到“共识”意味着所有计算机必须共同商定该值的输出。

反过来，这在系统中的每台计算机上维护一致的事务日志（即，它们“实现共同的目标”）。复制的状态机必须不断地将新事务接受到该日志中（即，“提供有用的服务”）。尽管如此，它必须这样做：

1. 有些计算机出现故障。
2. 网络不可靠，消息可能无法传递，延迟或出现故障。
3. 没有全局时钟来帮助确定事件的顺序。

我的朋友们，这是任何一致性算法的基本目标。

共识问题的定义

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

• 协议：所有非故障节点决定相同的输出值。
• 终止：所有非故障节点最终决定某些输出值。

注意：不同的算法具有上述条件的不同变化。例如，有些人将协议属性划分为Consistency和Totality。有些人有一个有效性或完整性或效率的概念。但是，这种细微差别超出了本文的范围。

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

1. 提议者，通常称为领导者或协调员。
2. 接受者，监听提议者请求并响应值的过程。
3. 学习者，系统中的其他过程，学习决定的最终价值

通常，我们可以通过三个步骤定义一致性算法：

第1步：选举

• 进程选择一个领导进程（即领导者）来做出决策。
• 领导者提出下一个有效的输出值。

第2步：投票

• 无故障进程会监听领导者提出的值，对其进行验证，并将其作为下一个有效值提出。

第3步：决定

• 无故障进程必须就单个正确的输出值达成共识。如果它收到满足某些标准阈值数量的相同投票，则进程将决定使用该值。
• 否则，以上步骤重新开始。

重要的是要注意每个共识算法都有不同：

• 术语（例如，轮次，阶段），
• 如何处理投票的程序，以及
• 决定最终值的标准（例如，有效性条件）。

尽管如此，如果我们可以使用这个通用过程来构建一个保证上面定义的一般条件的算法，那么我们就有了一个能够达成共识的分布式系统。

很简单吧？

FLP不可能

回想一下我们如何描述同步系统和异步系统之间的区别：

• 在同步环境中，消息在固定的时间范围内传递
• 在异步环境中，无法保证传递消息。

这种区别很重要。

在同步环境中达成共识是可能的，因为我们可以假设消息传递所需的最长时间。因此，在这种类型的系统中，我们可以允许系统中的不同节点轮流提出新的交易，轮询多数投票，并且如果在最大时限内没有提供提议，则跳过任何节点。

但是，如前所述，假设我们在同步环境中运行在消息延迟可预测的受控环境之外是不实际的，例如具有同步原子钟的数据中心。

实际上，大多数环境不允许我们进行同步假设。所以我们必须为异步环境设计。

如果我们不能在异步环境中假设最大的消息传递时间，那么即使不是不可能，实现终止也要困难得多。请记住，达成共识必须满足的条件之一是“终止”，这意味着每个非故障节点必须决定某些输出值。

这被正式称为“FLP不可能性结果。” 它是如何得到这个名字的？好吧，我很高兴你问这个问题！

某个发生错误的进程即使在确定性异步过程中也是不可能达成共识的。

研究员Fischer，Lynch和Paterson（又名FLP）在他们1985年发表的论文“ 分裂共识与一个错误进程的不可能性 ”中表明上述观点，也就是说，由于进程可能在不可预测的时间内失败，因此它们也可能在阻止达成共识的恰当时机恰好发生错误失败。

这个结果对分布式计算空间来说是一个巨大的失败。尽管如此，科学家们还是继续努力寻找绕过FLP不可能性的方法。

在较高的层面上，有两种方法来规避FLP不可能性：

1. 使用同步假设。
2. 使用非决定论。

让我们现在深入了解每一个。

方法1：使用同步假设

让我们重新审视我们的不可能性结果。这是考虑它的另一种方式：FLP不可能性结果基本上表明，如果我们不能在系统中取得协调的进展与结果，那么我们就无法达成共识。换句话说，如果是采取异步传递消息，则无法保证获得最终结果。回想一下，结果如果是一个必需条件，这意味着每个非故障节点最终必须决定一些输出值。

但是，如果我们不知道异步网络何时会传递消息，我们如何才能保证每个非故障流程都能决定一个结果值？

需要明确的是，这一发现并未表明共识无法实现。相反，由于异步，无法在固定时间内达成共识。说共识是“不可能”只是意味着共识“并非总是可行的。”这是一个微妙但至关重要的细节。

避免这种情况的一种方法是使用 超时 。如果在确定下一个值时没有进展，我们会等到超时，然后再重新开始步骤。正如我们即将看到的那样，这就是像Paxos和Raft这样的共识算法。

Paxos

Paxos 于20世纪90年代推出，是第一个真实的，实用的，容错的一致性算法。它是Leslie Lamport首次被广泛采用的共识算法之一，并被谷歌和亚马逊等全球互联网公司用于构建分布式服务。

Paxos的工作方式如下：

阶段1：准备请求

1. 提议者选择新的提案版本号（n）并向接受者发送“准备请求”。
2. 如果接受者收到准备请求（“prepare”，n），其n大于他们已经回复的任何准备请求，接受者发出（“ack"，n，n，v）或（“ack"， n，^，^）。
3. 受理人回应时承诺不再接受编号小于n的任何提案。
4. 接受者建议他们已接受的最高数量提案的值（v）（如果有的话）。否则，他们用^回应。

阶段2：接受请求

• 如果提议者收到来自大多数接受者的响应，那么它可以发出一个接受请求（“accept”，n，v），其数量为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中，虽然算法中没有明确的超时，但在实际实现时，在一些超时时间之后选择一个新的提议者是实现终止所必需的。否则，我们无法保证接受器会输出下一个值，系统可能会停止运行。

Raft

2013年，Ongaro和Ousterhout发布了一种名为 Raft 的复制状态机的新共识算法，其核心目标是可理解性（与Paxos不同）。

我们从Raft学到的一个重要新事物是使用共享超时来处理最终结果的概念。在Raft中，如果你崩溃并重新启动，你需要等待至少一个超时时间才能让自己被宣布为领导者，并保证你取得进步。

但是等等......“拜占庭”环境怎么样？

虽然传统的共识算法（例如Paxos和Raft）能够使用某种程度的同步假设（即超时）在异步环境中茁壮成长，但它们不是拜占庭容错的。它们只是崩溃容错的。

崩溃故障更容易处理，因为我们可以将进程建模为工作或崩溃 - 0或1.进程不能恶意行事并撒谎。因此，在崩溃容错系统中，可以构建分布式系统，其中简单多数足以达成共识。

在开放和分散的系统（例如公共区块链）中，用户无法控制网络中的节点。相反，每个节点都会针对其各自的目标做出决策，这可能与其他节点的目标冲突。

在拜占庭系统中，节点具有不同的激励，可以撒谎，协调或任意行动，你不能假设简单的多数足以达成共识。半数或更多的所谓诚实节点可以相互协调以便撒谎。

例如，如果当选的领导者是拜占庭并且与其他节点保持强大的网络连接，则可能危及系统。回想一下我们如何说我们必须对我们的系统建模，以容忍简单的故障或拜占庭故障。Raft和Paxos是简单的容错但不是拜占庭容错。它们不是为容忍恶意行为而设计的。

'拜占庭将军的问题'

试图建立一个可以处理提供冲突信息的进程的可靠计算机系统正式被称为“ 拜占庭一般问题 ”。拜占庭容错协议应该能够实现其共同目标，即使是针对节点的恶意行为。

论文“ 拜占庭将军问题 ”由Leslie Lamport, Robert Shostak, 和Marshall Pease提供的第一手证据，以解决拜占庭将军的问题：它表明，一个系统X拜占庭节点必须有至少3个+ 1的总节点，以达到共识。

原因如下：

如果x节点出现故障，则系统需要在与n减x节点协调后才能正常运行（因为x节点可能有故障/拜占庭并且没有响应）。但是，我们必须为不响应的x可能没有错误做准备; 它可能是X是不回应。如果我们希望非故障节点的数量超过故障节点的数量，我们至少需要n减x减x> x。因此，n> 3x + 1是最佳的。

但是，本文中演示的算法仅适用于同步环境。而拜占庭+异步的环境似乎更难设计。

为什么？

简而言之，建立一个能够承受异步环境和拜占庭环境的共识算法......好吧，这就像创造奇迹一样。

像Paxos和Raft这样的算法是众所周知的并且被广泛使用。但也有很多学术工作更侧重于解决拜占庭+异步设置中的共识问题。

所以扣上你的安全带......

我们正在实地考察......

到...的土地

理论学术论文！

（见下页）