理解分布式共识(2018)
分布式系统可能很难理解，主要是因为它们周围的知识是分布式的。但别担心，我很清楚其中的讽刺意味。在自学分布式计算时，我多次摔倒在地。现在，在经历了许多考验和磨难之后，我终于准备好向你们解释分布式系统的基础知识了。
区块链迫使工程师和科学家重新审视和质疑分布式计算中根深蒂固的范式。
我还想讨论一下区块链技术对该领域产生的深刻影响。区块链迫使工程师和科学家重新审视和质疑分布式计算中根深蒂固的范式。也许没有其他技术比区块链更快地推动了这一研究领域的进步。
分布式系统绝不是什么新鲜事。科学家和工程师花了几十年的时间来研究这个课题。但是区块链和他们有什么关系呢？嗯，如果没有分布式系统，区块链做出的所有贡献都是不可能的。
从本质上讲，区块链是一种新型的分布式系统。它始于比特币的出现，此后在分布式计算领域产生了持久的影响。因此，如果你想真正了解区块链是如何工作的，对分布式系统原理的深刻把握是必不可少的。
不幸的是，许多关于分布式计算的文献要么难以理解，要么分散在太多的学术论文中。更复杂的是，有数百种架构，所有这些架构都服务于不同的需求。将其归结为一个简单易懂的框架是相当困难的。
因为这个领域很广阔，我不得不谨慎地选择我能覆盖的领域。我还不得不做一些概括，以掩盖一些复杂性。请注意，我的目标不是让你成为该领域的专家。相反，我想给你足够的知识来启动你的分布式系统和共识之旅。
分布式系统涉及一组不同的进程(例如，计算机)彼此传递消息并协调以实现共同目标(即，解决计算问题)。
分布式系统是一组协同工作以实现统一目标的计算机。
简单地说，分布式系统就是一组计算机为了实现统一的目标而协同工作。虽然这两个过程是分开的，但对于最终用户来说，系统看起来就像一台计算机。
正如我提到的，分布式系统有数百种架构。例如，一台计算机也可以看作是一个分布式系统：中央控制单元、存储单元和输入输出通道是相互协作以完成某一目标的独立进程。
在飞机的情况下，这些独立的单元协同工作，将您从A点带到B点：
在这篇文章中，我们将重点介绍分布式系统，在分布式系统中，进程是空间上分离的计算机。
注意：我可以将术语“节点”、“对等”、“计算机”或“组件”与“进程”互换使用。对于这篇文章来说，它们的意思都是一样的。同样，我可以将术语“网络”与“系统”互换使用。
系统中的进程同时运行，这意味着多个事件同时发生。换句话说，网络中的每台计算机与网络中的其他计算机同时独立地执行事件。
要让分布式系统正常工作，我们需要一种方法来确定事件的顺序。然而，在同时运行的一组计算机中，有时不可能说两个事件中的一个首先发生，因为计算机在空间上是分开的。换句话说，不存在单一的全局时钟来决定网络中所有计算机上发生的事件的顺序。
在《分布式系统中的时间、时钟和事件顺序》一文中，Leslie Lamport展示了我们如何通过记住以下因素来推断一个事件是否发生在另一个事件之前：
通过确定哪个事件在另一个事件之前发生，我们可以获得系统中事件的部分排序。兰波特的论文描述了一种算法，该算法要求每台计算机都能监听系统中所有其他计算机的信息。通过这种方式，可以基于这种部分排序对事件进行完全排序。
但是，如果我们将顺序完全基于每台计算机听到的事件，我们可能会遇到这样的情况：该顺序与系统外部的用户所感知的不同。因此，本文表明，该算法仍然可以允许异常行为。
最后，兰波特讨论了如何通过使用适当同步的物理时钟来防止此类异常。
但等等， - ，有一个很大的警告：协调原本独立的时钟是一个非常复杂的计算机科学问题。即使您最初精确地设置了一组时钟，时钟在一段时间后也会开始不同。这是由于“时钟漂移”现象造成的，即时钟以略有不同的速率计时。
从本质上讲，兰波特的论文证明，在空间上分散的分布式计算机系统中，事件的时间和顺序是根本的障碍。
理解分布式系统的一个关键方面是承认分布式系统中的组件有故障。这就是为什么它被称为“容错分布式计算”。
一个没有故障的系统是不可能的。真正的系统可能存在许多缺陷或缺陷，无论是进程崩溃；消息丢失、扭曲或重复；网络分区延迟或丢弃消息；甚至是进程完全混乱并根据某种恶意计划发送消息。
省略：该组件发送一条消息，但其他节点没有接收到该消息(例如，该消息被丢弃)。
拜占庭：组件的行为是任意的。这种类型的故障在可能没有恶意行为的受控环境(例如Google或Amazon数据中心)中是无关紧要的。相反，这些错误发生在所谓的“对抗性环境”中。基本上，当一组分散的独立行为者充当网络中的节点时，这些行为者可能会选择以“拜占庭式”的方式行事。这意味着他们恶意选择更改、阻止或根本不发送消息。
考虑到这一点，我们的目标是设计协议，使具有故障组件的系统仍能实现共同目标并提供有用的服务。
鉴于每个系统都有故障，在构建分布式系统时，我们必须考虑的一个核心问题是，无论是由于非恶意行为(即崩溃失败或遗漏故障)还是恶意行为(即拜占庭故障)，在构建分布式系统时，即使其部分偏离正常行为，它是否仍能存活。
一般而言，在构建分布式系统时有两种类型的模型需要考虑：
在一个简单的容错系统中，我们假设系统的所有部分执行以下两种操作之一：它们要么完全遵循协议，要么失败。这种类型的系统应该绝对能够处理节点脱机或故障。但它不必担心节点表现出任意或恶意行为。
简单的容错系统在不受控制的环境中用处不大。在一个分散的系统中，节点由在开放、未经许可的互联网上通信的独立参与者控制，我们还需要为选择恶意或“拜占庭”的节点进行设计。因此，在拜占庭容错系统中，我们假设节点可能出现故障或恶意。
尽管大多数真实系统的设计都是为了承受拜占庭式的故障，但一些专家认为，这些设计过于笼统，没有考虑到“理性”故障，即节点如果这样做符合自身利益，就可能出现偏差。换句话说，节点可以是诚实的，也可以是不诚实的，这取决于激励。如果激励足够高，那么即使大多数节点也可能会做出不诚实的行为。
更正式地说，这被定义为酒吧模型 - ，它同时规定了拜占庭式和理性式的失败。酒吧模型假定有三种类型的参与者：
正如我前面提到的，分布式系统中的计算机通过一台或多台其他计算机之间的“消息传递”进行通信和协调。可以使用任何消息传递协议传递消息，无论是HTTP、RPC还是为特定实现构建的自定义协议。有两种类型的消息传递环境：
在同步系统中，假定消息将在一段固定的已知时间内传递。
同步消息传递在概念上不那么复杂，因为用户有一个保证：当他们发送消息时，接收组件将在特定的时间范围内收到该消息。这允许用户用消息到达目的地所需时间的固定上限来建模他们的协议。
然而，这种类型的环境在现实世界的分布式系统中并不是很实用，在现实世界中，计算机可能会崩溃或脱机，消息可能会被丢弃、复制、延迟或无序接收。
在异步消息传递系统中，假设网络可能无限延迟消息、复制消息或无序发送消息。换句话说，接收一条消息需要多长时间没有固定的上限。
接下来，我们将重点了解在分布式系统中达成“共识”意味着什么。但首先，重要的是要重申我们前面提到的：用于分布式计算的硬件和软件体系结构有数百种。
复制状态机是确定性状态机，可跨多台计算机复制，但充当单个状态机。这些计算机中的任何一个都可能出现故障，但状态机仍将运行。
在复制状态机中，如果事务有效，一组输入将导致系统状态转换到下一个状态。事务是对数据库的原子操作。这意味着这些操作要么完全完成，要么永远不会完成。在复制状态机中维护的一组事务称为“事务日志”。
从一个有效状态转换到下一个有效状态的逻辑称为“状态转换逻辑”。
换句话说，复制状态机是一组分布式计算机，它们都以相同的初始值开始。对于每个状态转换，每个进程都决定下一个值。达成“共识”意味着所有的计算机必须集体同意这个值的输出。
反过来，这会在系统中的每台计算机上维护一致的事务日志(即，它们“实现了共同的目标”)。复制的状态机必须不断地将新事务接收到该日志中(即，“提供有用的服务”)。它必须这样做，尽管事实是：
网络不可靠，消息可能无法传递、延迟或出现故障。
注：不同的算法对上述条件有不同的变化。例如，有些人将协议属性分为一致性和整体性。有些人有有效性、完整性或效率的概念。然而，这些细微差别超出了本文的讨论范围。
学习者，系统中学习最终决定值的其他过程。
无故障流程监听领导提出的值，对其进行验证，并将其作为下一个有效值提出。
非故障流程必须就单个正确的输出值达成共识。如果它收到满足某些标准的相同选票的阈值数量，则进程将决定该值。
尽管如此，如果我们能够使用这个通用过程来构建一个算法来保证上面定义的一般条件，那么我们就拥有了一个能够达成共识的分布式系统。
在同步环境中达成共识是可能的，因为我们可以假设消息传递所需的最长时间。因此，在这种类型的系统中，我们可以允许系统中的不同节点轮流提出新的事务，轮询多数票，并跳过任何在最大时间限制内没有提出建议的节点。
但是，如前所述，假设我们在同步环境中操作，在消息延迟可预测的受控环境之外是不现实的，例如具有同步原子时钟的数据中心。
实际上，大多数环境都不允许我们做出同步假设。因此，我们必须针对异步环境进行设计。
如果我们不能假设异步环境中的最大消息传递时间，那么实现终止就会困难得多，如果不是不可能的话。请记住，要达成共识，必须满足的条件之一是“终止”，这意味着每个未出错的节点都必须决定某个输出值。
这被正式称为“FLP不可能结果”。它是怎么得名的？嗯，我很高兴你这么问！
即使是一个单一的故障流程，也不可能在确定性的异步流程之间达成共识。
研究人员Fischer、Lynch和Paterson(又名FLP)在1985年的论文《一个有故障的过程中不可能达成分布式共识》中展示了，即使是一个有故障的过程也不可能在确定性的异步过程中达成共识。基本上，因为流程可能在不可预测的时间失败，所以它们也有可能在阻止达成共识的确切时间失败。
这一结果对分布式计算空间来说是一个巨大的挫折。尽管如此，科学家们仍在继续努力寻找绕过FLP不可能的方法。
让我们重新审视一下我们不可能的结果。这里有另一种思考方式：FLP不可能的结果本质上表明，如果我们不能在一个体系中取得进展，那么我们就不能达成共识。换句话说，如果消息是异步传递的，则无法保证终止。回想一下，终止是必需的条件，这意味着每个非故障节点最终都必须决定某个输出值。
但是，如果我们不知道消息将在何时由于异步网络传递，我们如何保证每个没有错误的进程都会决定一个值呢？
需要明确的是，这一发现并不是说无法达成共识。相反，由于不同步，不可能在固定的时间内达成共识。说共识是“不可能的”，只是意味着共识“并不总是可能的”。这是一个微妙但至关重要的细节。
规避此问题的一种方法是使用超时。如果在决定下一个值方面没有取得任何进展，我们将等到超时，然后重新开始这些步骤。正如我们即将看到的，这就是像Paxos和RAFT这样的共识算法所做的事情。
Paxos于20世纪90年代推出，是第一个现实世界中实用的容错一致性算法。这是莱斯利·兰波特(Leslie Lamport)证明是正确的首批被广泛采用的共识算法之一，并已被谷歌(Google)和亚马逊(Amazon)等全球互联网公司用来构建分布式服务。
提出者选择新的提案版本号(N)，并向接受者发送“准备请求”。
如果接受者接收到比他们已经响应的任何准备请求的n大的准备请求(“PREPARE，”n)，接受者就发出(“ack，”n，n‘，v’)或(“ack，”n，^，^)。
接受者的回应是承诺不再接受任何编号小于n的提案。
接受者建议他们所接受的最高编号提案的值(V)(如果有的话)。否则，他们会回复^。
如果提出者收到来自大多数接受者的响应，则它可以发出数字为n、值为v的接受请求(“Accept”，n，v)。
如果接受者接收到接受请求(“Accept，”n，v)，则它接受该提议，除非它已经用大于n的数字响应了准备请求。
当接受者接受一个提议时，它会回应所有的学习者(“接受”，n，v)。
学习者从大多数接受者那里接收(“接受”，n，v)，决定v，然后发送(“决定，”v)给所有其他学习者。
哟！困惑了吗？我知道这是一个相当多的信息需要消化。
正如我们现在所知道的，每个分布式系统都有故障。在该算法中，如果提议者失败(例如，因为存在遗漏错误)，那么决策可能会被推迟。Paxos通过在第一阶段使用一个新的版本号来解决这个问题，即使之前的尝试从未结束。
我不会详细介绍，但在这种情况下恢复正常操作的过程相当复杂，因为预计过程会介入并推动解决过程向前发展。
Paxos如此难以理解的主要原因是，它的许多实现细节都有待读者的解读：我们如何知道提案何时失败？我们是否使用同步时钟来设置超时时段，以决定何时提案失败，我们需要进入下一个级别？🤷。
为了在实现上提供灵活性，关键领域中的几个规范是不限成员名额的。领导人选举、故障检测和日志管理等内容模糊或完全没有定义。
这种设计选择最终成为Paxos最大的缺点之一。它不仅令人难以置信地难以理解，而且也难以实现。反过来，这使得分布式系统领域的导航变得异常困难。
在Paxos中，虽然超时在算法中并不明确，但当涉及到实际实现时，需要在超时一段时间后选举新的提名人来实现终止。否则，我们不能保证接受者会输出下一个值，系统可能会停止。
2013年，Ongaro和Ousterhout发布了一种名为RAFT的复制状态机的新共识算法，其核心目标是可理解性(与Paxos不同)。
我们从RAFT学到的一个重要的新东西是使用共享超时来处理终止的概念。在RAFT中，如果你崩溃并重新启动，你至少要等待一段暂停时间，然后才能试图让自己被宣布为领导者，你肯定会取得进展。
虽然传统的一致性算法(如Paxos和RAFT)能够在使用某种程度的同步假设(即超时)的异步环境中茁壮成长，但它们并不具有拜占庭式的容错能力。它们只具有崩溃容错能力。
崩溃故障更容易处理，因为我们可以将进程建模为正在工作或崩溃的 - 0或1。进程不能恶意操作和撒谎。因此，在崩溃容错系统中，可以构建一个简单多数就足以达成共识的分布式系统。
在开放去中心化的系统(如公共区块链)中，用户对网络中的节点没有控制权。取而代之的是，每个节点针对其各自的目标做出决策，这可能与其他节点的决策相冲突。
在拜占庭式的系统中，节点有不同的动机，可以任意撒谎、协调或行动，你不能假设简单的多数就足以达成共识。一半或更多被认为诚实的节点可以相互协调以撒谎。
例如，如果一位当选的领导人是拜占庭式的，并且与其他节点保持着强大的网络连接，这可能会危及系统。回想一下，我们曾说过，我们必须对我们的系统进行建模，要么容忍简单的错误，要么容忍拜占庭式的错误。RAFT和Paxos是简单的容错，但不是拜占庭式的容错。它们的设计不是为了容忍恶意行为。
试图建立一个可靠的计算机系统来处理提供相互冲突的信息的过程被正式地称为“拜占庭将军的问题”
.
