标签：异步 故障 共识 如何 算法 分布式系统 节点 分布式

英文原文链接：https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95

---

How Does Distributed Consensus Work?

目录

• How Does Distributed Consensus Work?
  • 什么是分布式系统？
  • 分布式系统的属性
  • 在分布式系统中达成共识意味着什么

区块链技术关键突破概述——以及为什么中本聪共识如此重要。

分布式系统可能难以理解，主要是因为围绕它们的知识是分布式的。但别担心，我很清楚其中的讽刺意味。在自学分布式计算时，我多次摔倒在地。现在，经过多次尝试和磨难，我终于准备好向您解释分布式系统的基础知识了。

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

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

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

本质上，区块链是一种新型的分布式系统。它始于比特币的出现，此后在分布式计算领域产生了持久的影响。所以，如果你想真正了解区块链是如何工作的，那么掌握分布式系统的原理是必不可少的。

不幸的是，许多关于分布式计算的文献要么难以理解，要么分散在太多的学术论文中。更复杂的是，有数百种架构，所有这些都服务于不同的需求。将其归结为一个易于理解的框架是相当困难的。

因为领域广阔，我必须仔细选择我可以涵盖的内容。我还必须进行概括以掩盖一些复杂性。请注意，我的目标不是让您成为该领域的专家。相反，我想为您提供足够的知识，帮助您开启分布式系统和共识之旅。

阅读完这篇文章后，您将更深入地了解：

• 什么是分布式系统，
• 分布式系统的属性，
• 在分布式系统中达成共识意味着什么，
• 对基础共识算法（例如 DLS 和 PBFT）的理解，
• 以及为什么中本聪共识很重要。

我希望你已经准备好学习了，因为现在上课了。

什么是分布式系统？

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

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

简而言之，分布式系统是一组计算机一起工作以实现一个统一的目标。尽管这些过程是分开的，但系统对于最终用户来说就像一台计算机。

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

以飞机为例，这些离散单元协同工作，将您从 A 点带到 B 点：

在这篇文章中，我们将关注分布式系统，其中进程是空间分离的计算机。

注意：我可以将术语“节点”、“对等体”、“计算机”或“组件”与“进程”互换使用。就本文而言，它们的含义相同。同样，我可以将术语“网络”与“系统”互换使用。

分布式系统的属性

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

A）并发

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

这需要协调

B) 缺少全局时钟

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

在论文“Time, Clocks and Ordering of Events in a Distributed System”中，Leslie Lamport 展示了我们如何通过记住以下因素来推断一个事件是否先于另一事件发生：

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

通过确定哪个事件先于另一个事件发生，我们可以获得系统中事件的部分排序。 Lamport 的论文描述了一种算法，该算法要求每台计算机都能听到系统中其他计算机的声音。这样，事件就可以基于这种部分排序进行完全排序。

但是，如果我们完全根据每台计算机听到的事件来确定顺序，我们可能会遇到这种顺序与系统外部用户所感知的不同的情况。因此，该论文表明该算法仍然可以允许异常行为。

最后，Lamport 讨论了如何通过使用适当同步的物理时钟来防止此类异常。

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

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

C) 组件的独立故障

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

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

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

这些故障大致可分为三类：

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

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

鉴于每个系统都有故障，我们在构建分布式系统时必须考虑的一个核心问题是它是否能够在其部分偏离正常行为的情况下仍然存在，无论这是由于非恶意行为（即崩溃失败或遗漏故障）造成的或恶意行为（即拜占庭错误）。

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

1）简单的容错

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

2A）拜占庭容错

一个简单的容错系统在不受控制的环境中不是很有用。在一个由独立参与者控制的节点在开放、无许可的互联网上进行通信的去中心化系统中，我们还需要为选择恶意或“拜占庭”的节点进行设计。因此，在拜占庭容错系统中，我们假设节点可能发生故障或恶意。

2B) BAR 容错

尽管大多数真实系统的设计都是为了抵御拜占庭式故障，但一些专家认为，这些设计过于笼统，没有考虑到“理性”故障，如果节点出于自身利益这样做，可能会偏离。换句话说，节点既可以诚实也可以不诚实，这取决于激励措施。如果激励足够高，那么即使是大多数节点也可能会做出不诚实的行为。

更正式地说，这被定义为 BAR 模型——一个指定了拜占庭和理性失败的模型。 BAR 模型假设了三种类型的参与者：

• Byzantine：拜占庭式节点是恶意的，并试图搞砸你。
• Altruistic：诚实的节点始终遵循协议。
• Rational：理性节点仅在适合它们的情况下遵循协议。

D) 消息传递

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

1）同步

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

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

但是，这种类型的环境在现实世界的分布式系统中不太实用，在这种系统中，计算机可能会崩溃或脱机，并且消息可能会被丢弃、复制、延迟或乱序接收。

2）异步

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

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

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

• Concurrency of processes
• Lack of a global clock
• Faulty processes
• Message passing

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

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

Replicated State Machine

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

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

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

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

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

1. 有些电脑有问题。
2. 网络不可靠，消息可能无法传递、延迟或乱序。
3. 没有全局时钟来帮助确定事件的顺序。

我的朋友们，这是任何共识算法的基本目标。

共识问题，定义

一个算法如果满足以下条件，就可以达成共识：

Agreement：所有非故障节点决定相同的输出值。

Termination：所有非故障节点最终决定某个输出值。

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

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

1. Proposers（提议者），通常称为领导者或协调者。
2. Acceptors（接收者），侦听来自提议者的请求并以值响应的进程。
3. Learners（学习者），系统中的其他进程学习最终决定的值。

一般来说，我们可以通过三个步骤来定义一个共识算法：

Step 1: Elect

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

Step 2: Vote

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

Step 3: Decide

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

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

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

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

很简单，对吧？

FLP impossibility

… 并不真地。但你可能已经看到了！

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

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

这种区别很重要。

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

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

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

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

这被正式称为“FLP 不可能结果”。这个名字是怎么来的？好吧，我很高兴你问！

即使是单个故障进程也无法在确定性异步进程之间达成共识。

研究人员 Fischer、Lynch 和 Paterson（又名 FLP）在他们 1985 年的论文“Impossibility of Distributed Consensus with One Faulty Process,”中展示了即使是一个错误的进程也无法在确定性异步过程之间达成共识。基本上，由于进程可能在不可预测的时间失败，它们也有可能在阻止共识发生的确切时机失败。

这个结果对于分布式计算空间来说是一个巨大的打击。尽管如此，科学家们仍在继续努力寻找规避 FLP 不可能性的方法。

在高层次上，有两种方法可以规避 FLP 不可能性：

• 使用同步假设
• 使用非确定性。

现在让我们深入研究每一个。

方法 1：使用同步假设

我知道你在想什么：这到底是什么意思？

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

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

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

避免这种情况的一种方法是使用超时。如果在决定下一个值时没有取得任何进展，我们会等到超时，然后重新开始这些步骤。正如我们即将看到的，这就是像 Paxos 和 Raft 这样的共识算法本质上所做的。

Paxos

Paxos 于 1990 年代推出，是第一个现实世界的、实用的、容错的共识算法。它是最早被 Leslie Lamport 证明是正确的广泛采用的共识算法之一，并已被谷歌和亚马逊等全球互联网公司用于构建分布式服务。

Paxos 的工作原理是这样的：

Phase 1: Prepare request

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

Phase 2: Accept request

1. 如果提议者收到大多数接受者的响应，那么它可以发出一个接受请求（“accept”，n，v），编号为 n，值为 v。
2. n 是出现在准备请求中的数字。
3. v 是响应中编号最高的提案的值。
4. 如果接受者收到一个接受请求（“accept,”n，v），它会接受该提议，除非它已经响应了一个编号大于 n 的准备请求。

Phase 3: Learning phase

1. 每当接受者接受提议时，它都会响应所有学习者（“accpet”，n，v）。
2. 学习者从大多数接受者那里接收 (“accept,” n, v)，决定 v，并将 (“decide,” v) 发送给所有其他学习者。
3. 学习者收到（“decide” v）和决定的 v。

呸！迷茫了吗？我知道有很多信息需要消化。

但是等等……还有更多！

正如我们现在所知，每个分布式系统都有故障。在该算法中，如果提议者失败（例如，因为存在 omission 错误），则可能会延迟决策。 Paxos 通过在第 1 阶段开始使用新版本号来解决这个问题，即使之前的尝试从未结束。

我不会详细介绍，但在这种情况下恢复正常操作的过程非常复杂，因为预计流程会介入并推动解决过程向前发展。

Paxos 如此难以理解的主要原因是它的许多实现细节留给读者解释：我们如何知道提议者何时失败？我们是否使用同步时钟来设置超时时间来决定提议者何时失败并且我们需要进入下一个等级？

标签：异步,故障,共识,如何,算法,分布式系统,节点,分布式
From： https://www.cnblogs.com/yangyi215/p/17368051.html