3 分布式系统抽象

讨论编程语言时，我们使用通用术语并用函数、运算符、类、变量和指针来定义我们的程序。通用的词汇可以帮助我们避免每次都为了描述某些东西而发明新词。我们的定义越精确、越没有歧异，听众也就越容易理解。

在开始学习算法之前，我们首先要了解分布式系统中的词汇：这些定义你会经常在演讲、书籍和论文中遇到。

链路

网络是不可靠的：消息会丢失、延迟或被打乱。记住这一点之后，我们来尝试构建几种通信协议。我们从最不可靠的协议开始，确定它们可能处于的状态，然后找出可以为协议增加的东西使它提供更好的保证。

公平损失链路

我们可以从两个进程开始，它们之间以链路相连。进程可以相互发送消息，如图2所示。任何通信介质都是不完美的，消息可能丢失或延迟。

看看我们能得到什么样的保证。消息M被发送之后（从发送方的角度来看），它可能处于以下状态之一：

1. 还未送达进程B（但会在某个时间点送达）
2. 在途中丢失且不可恢复
3. 成功送达远程进程

注意，发送方没有任何方法确定消息是否已经送达。在分布式系统的术语中，这种链路称为公平损失（fair-loss）。这种链路具有以下属性：

公平损失

    如果发送方和接收方都是正确的，且发送方无限多次重复发送，则消息最终会被送达注3。

有限重复

    发送的消息不会被送达无限次。

不会无中生有

    链路不会自己生成消息。换句话说，它不会传递一个从未发送过的消息。

公平损失链路是一种很有用的抽象，它是构建具有更强保证的通信协议的基石。我们可以假设该链路不会在通信双方之间系统性地丢弃消息，也不会创建新消息。但与此同时，我们也不能完全依靠它。这可能让你想起了用户数据报协议（UDP），UDP允许我们从一个进程发送消息到另一个进程，但在协议层面上不提供可靠的传输语义。

消息确认

为了改善这一情况、更清晰地获得消息状态，我们可以引入确认（acknowledgment）机制：接收方通知发送方消息已送达。为此，我们需要双向通信信道，并增加一些措施以区分不同的消息，例如序列号—单调递增的唯一消息标识符。

每个消息只要有唯一标识符就足够了。序列号只是唯一标识符的一种特殊情况，即使用计数器来获取标识符，从而实现唯一性。当使用哈希算法来唯一地标识消息时，我们应当考虑可能的冲突，并确保能消除歧义。

现在，进程A可以发送消息M(n)，其中n是单调递增的消息计数器。B收到消息后立即向A发送确认ACK(n)。图8-3展示了这种通信形式。

确认消息，就像原始消息一样，也有可能在途中丢失。消息可能处于的状态数会稍有变化。在A收到确认之前，该消息仍处于我们前面提到的三种状态之一，但是，一旦A收到确认，就可以确信该消息已送达B。

消息重传

增加确认机制仍不足以保证通信协议完全可靠：发送的消息仍可能会丢失，远程进程也可能在确认之前发生故障。为了解决该问题并提供送达保证，我们可以尝试重传（retransmit）。重传是指发送方重试可能失败的操作。我们之所以说可能失败，是因为发送方并不能真的知道有没有失败，因为我们要讨论的链路不使用确认机制。

进程A发送消息M之后，它将等到超时T被触发，然后尝试再次发送同一条消息。假设进程之间的链路完好无损，进程间的网络分区不会无限持续下去，并且并非所有数据包都丢失，我们可以认为，从发送方的角度看，消息要么尚未送达进程B，要么已经成功送达。由于A一直在尝试发送消息，可以认为传输过程中不会发生不可恢复的消息丢失。

在分布式系统的术语中，这种抽象称为顽固链路（stubborn link）。之所以称为顽固，是因为发件人会无限期地反复发送消息，但是，由于这种抽象非常不切实际，因此我们需要将重试与确认结合起来。

重传的问题

每当我们发送消息时，在收到远程进程的确认之前，我们无从得知消息的状态：可能已被处理，可能马上就要处理，也可能已经丢失，甚至可能在收到消息之前远程进程就崩溃了—上述的任意状态都是可能的。我们可以重试操作、再次发送消息，但这可能导致消息重复。只有当我们要执行的操作是幂等时，处理重复消息才是安全的。

幂等（idempotent）的操作可以执行多次而产生相同的结果，且不会产生其他副作用。例如，服务器关机操作可以是幂等的，第一次调用将发起关机，而所有后续调用都不会产生任何其他影响。

如果每个操作都是幂等的，那我们可以少考虑一些传递语义，更多地依赖重传来实现容错，并以完全反应式的方式构建系统：为某些信号触发相应的操作，而不会引起预期之外的副作用。但是，操作不一定是幂等的，简单地假设它们幂等可能会导致集群范围的副作用。例如，向客户的信用卡收费不是幂等操作，绝对不可以重复收费多次。

在存在部分故障和网络分区的情况下，幂等性尤其重要，因为我们无法总是确定远程操作的确切状态—是成功还是失败，还是会马上被执行—我们只能等待更长的时间。保证每个操作都是幂等的是不切实际的，因此我们需要在不改变实际操作语义的情况下，提供与幂等性等价的保证。为此，我们可以使用去重来避免多次处理消息。

消息顺序

不可靠的网络给我们带来了两个问题：一是消息可能会乱序到达；二是由于重传某些消息可能会多次送达。我们已经引入了序列号，利用这些消息标识符我们可以在接收方确保先进先出（FIFO）的顺序。由于每条消息都有一个序列号，因此接收方可以跟踪下列信息：

nconsecutive表示最大连续序列号：所有小于或等于该序列号的消息都已经收到，这些消息可以按顺序放到正确的位置上。

nprocessed表示最大已处理序列号：所有小于或等于该序列号的消息都已经按照原来的顺序被处理。此序列号可以用于去重。

如果收到的消息序列号不连续，接收方会将其放入重新排序缓冲区。例如，它在接收到序列号为3的消息后收到消息5，那我们就知道4还是缺失的，因此我们将5放在一旁，直到4到来，然后就能构造出原本的消息顺序。由于通信构建在公平损失链路之上，可以认为nconsecutive和nmax_seen之间的消息最终一定会送达。

接收方可以安全地丢弃收到的序列号小于等于nconsecutive的消息，因为这些消息确定已经送达了。

去重的工作原理是检查带有序列号n的消息是否已被处理（已被传给网络栈的更上层），丢弃已处理的消息。

在分布式系统的术语中，这种类型的链路称为完美链路，它提供以下保证[CACHIN11]：

可靠传递

正确的进程A发送一次到正确的进程B的每个消息最终都会被传递。

没有重复

消息不会被传送多次。

不会无中生有

与其他种类的链路一样，它只能传递实际由发送者发送过的消息。

这可能会让你想起TCP注4协议（但是，TCP仅在单个会话内保证可靠传递）。当然，上述模型仅仅是一种用于说明原理的简化表示。TCP中处理消息确认的模型更为复杂，它按组进行确认以减少协议层面的开销。另外，TCP具有选择性确认、流控、拥塞控制、错误检测等很多其他功能，这些不在我们的讨论范围之内。

严格一次传递

分布式系统中只有两个难题：1）保证消息顺序；2）严格一次传递。 —Mathias Verraes

关于是否可以做到严格一次传递（exactly-once delivery）这个问题已经有很多讨论。这里，语义和精确的措辞非常重要。由于链路故障可能导致传递消息的第一次尝试无法成功，因此大多数实际的系统都采用至少一次传递（at-least-once delivery），它确保了发送方将重试直到收到确认为止，否则就认为对方没有收到该消息。还有一种传递语义是最多一次（at-most-once）：发送方仅仅发送消息而不期待得到任何确认。

TCP协议的原理是将消息分成数据包，一个一个传输，然后在接收端将它们拼接到一起。TCP可能会尝试重传某些数据包，并且可能有不止一次的传输会成功。由于TCP用序列号标记每个数据包，即使某些数据包被发送多次，它也可以对其进行去重，确保接收方只会看到并处理一次该消息。在TCP中，此保证仅对单个会话有效：如果消息被确认并处理，但是发送方在收到确认消息前连接就中断了，则应用程序并不知道此传递成功，取决于其逻辑，它可能会尝试再次发送消息。

这意味着严格一次处理是个有趣的问题，因为重复的传送（或数据包传输）没有副作用，仅仅是链路尽力而为的产物。举个例子，如果数据库节点仅接收到记录但还没将它持久化。在这种情况下传递已经完成了，但除非该记录可以被查到（换句话说，除非消息被传递并且处理了），否则这次传递毫无用处。

为了确保严格一次传递，各节点需要一个共同知识[HALPERN90]：每个节点都知道某件事，每个节点都知道其他所有节点也都知道这件事。用简化的术语来说，节点必须在记录状态上达成共识：两个节点都认为该记录已经或者还未被持久化。正如本章之后会说的，这在理论上是不可能的，但在实践中，我们仍通过放宽协调的要求来使用这一概念。

各种关于是否是严格一次发送的误解，大多是因为从不同协议和抽象层次上考虑该问题，以及对“传递”的不同定义。要想建立可靠的链路，不可能不重复传送某些消息。但是，我们可以通过仅处理每个消息一次并忽略重复消息，使得从发送方的角度来看是严格一次发送。

现在，在建立了实现可靠通信的方法之后，我们可以继续前进，探寻实现分布式系统中进程间一致性和共识的方法。

4 两将军问题

一个被广泛称为两将军问题的思想实验，是对分布式系统一致性的最著名的描述之一。

这个思想实验表明，如果链路可能发生故障并且通信是异步的，则不可能在通信的双方之间达成共识。尽管TCP具有完美链路的性质，但是务必记住：完美链路尽管被称为完美链路，并不能保证完美的传递。它们也不能保证参与方一直活着，而只关心传输本身。

想象现在有两支军队，分别由两位将军领导，准备进攻一座要塞城市。两支军队分别位于城市的两侧，只有在同时进攻的情况下才能获胜。

两位将军通过信使进行通信。他们已经制定了攻击计划，现在唯一需要达成共识的就是是否执行计划。该问题的变体包括：其中一位将军的级别较高，但需要确保攻击是有协调的；或者两位将军需要就确切时间达成共识。这些细节不会改变问题的定义：将军们需要达成一项共识。

将军们只需要对“他们都会发起进攻”这一事实达成共识。否则，攻击将无法成功。将军A发出一条消息MSG(N)，表明如果对方也同意的话，就在指定的时间发起进攻。

将军A送出信使之后，他不知道信使是否已经到达：信使可能会被抓而无法传达消息。当将军B收到消息时，他必须发送确认ACK(MSG(N))。图8-4展示了一条消息由一方发送并由另一方确认。

传递确认消息的信使也可能会被抓而无法传达消息。B无从得知信使是否已成功送达确认消息。

为了确认这一点，B必须等待ACK(ACK(MSG(N)))，一个二阶的确认，用于确认A收到了确认。

无论将军们互相发送多少确认，他们始终距离安全地发起攻击还差一个ACK。将军们注定要怀疑最后一个确认消息是否已送达目的地。

注意我们没有做任何时序上的假设：将军间的通信是完全异步的。并没有一个上限约束将军必须在多长时间内做出回应。

5 FLP不可能定理

Fisher、Lynch和Paterson在论文中描述了一个著名的问题：FLP不可能问题[FISCHER85]（FLP是作者姓氏的首字母），论文讨论了一种共识形式：各进程启动时有一个初始值，并尝试就新值达成共识。算法完成后，所有正常进程上的新值必须相同。

如果网络完全可靠，很容易对特定值达成共识。但实际上，系统容易出现各式各样的故障，例如消息丢失、重复、网络分区，以及进程缓慢或崩溃。

共识协议描述了这样一个系统：给定初始状态的多个进程，它将所有进程带入决定状态。一个正确的共识协议必须具备以下三个属性：

一致性

协议达成的决定必须是一致的：每个进程都做出了决定且所有进程决定的值是相同的。否则我们就尚未达成共识。

有效性

达成共识的值必须由某一个参与者提出，这意味着系统本身不能“提出”值。这也意味着这个值不是无关紧要（trivial）的：进程不能总是决定某个预定义的默认值。

终止性

只有当所有进程都达到决定状态时，协议才算完成。

文献[FISCHER85]假定处理过程是完全异步的，进程之间没有共享的时间概念。这样的系统中的算法不能基于超时，并且一个进程无法确定另一个进程是崩溃了还是仅仅运行太慢。论文表明，在这些假设下，不存在任何协议能保证在有限时间内达成共识。完全异步的共识算法甚至无法容忍一个远程进程无通知地突然崩溃。

如果我们不给进程完成算法步骤设定一个时间上限，那么就无法可靠地检测出进程故障，也不存在确定性的共识算法。

但是，FLP不可能定理并不意味着我们要收拾东西回家（由于达成共识是不可能的）。它仅仅意味着我们不能总是在有限的时间内在一个异步系统中达成共识。实践中，系统至少会表现出一定程度的同步性，而要想解决共识问题还需要一个更完善的模型。

6 系统同步性

从FLP不可能定理中可以看出时序假设是分布式系统的关键特征之一。在异步系统中，我们不知道进程运行的相对速度，也不能保证在有限时间内或以特定顺序传递消息。进程可能要花无限长的时间来响应，而且无法总是可靠地检测到进程故障。

对异步系统的主要批评在于上述假设不切实际：进程不可能具有任意不同的处理速度，链路传递消息的时间也不会无限长。依赖时间能够简化推理，并提供时间上限的保证。

在异步模型中不一定能解决共识问题[FISCHER85]。而且，不一定能设计出高效的异步算法。对于某些任务，切实可行的解决方案很可能需要依赖时间[ARJOMANDI83]。

我们可以放宽一些假设，认为系统是同步的。为此我们引入了时间的概念。在同步模型下对系统进行推理要容易得多。它假定各进程的处理速度相近、传输延迟是有限的，并且消息传递不会花任意长的时间。

同步系统也可以表示为同步的进程本地时钟：两个进程本地时间源之间的时间差存在上限[CACHIN11]。

在同步模型中设计系统可以使用超时机制。我们可以构建更复杂的抽象，例如领导者选举、共识、故障检测以及基于它们的其他抽象。这使得最佳情况的场景更加健壮，但是如果时序假设不成立则可能导致故障。例如：Raft共识算法（参见14.4节）中，可能最终有多个进程认为它们是领导者，为了解决该问题，我们强制滞后的进程接受其他进程成为领导者；故障检测算法（参见第9章）可能会错误地将活动进程标记为故障，反之亦然。设计系统时，我们必须考虑这些可能性。

异步和同步模型的性质可以组合使用，我们可以将系统视为部分同步的。部分同步的系统具有同步系统的某些属性，但是消息传递、时钟漂移和相对处理速度的边界范围可能并不精确，并且仅在大多数时候成立[DWORK88]。

同步是分布式系统的基本属性：它对性能、扩展性和一般可解性有影响，并且有许多对系统正常工作来说是必要的因素。本书中讨论的一些算法就工作在同步系统的假设下。

7 故障模型

我们一直在提到故障这个词，但到目前为止，它还是一个十分宽泛的概念，可能包含多种含义。就像我们可以做出不同的时序假设那样，我们也可以假设存在不同种类的故障。故障模型准确地描述了分布式系统中的进程可能以怎样的方式崩溃，并基于这些假设来开发算法。例如，我们可以假设进程可能崩溃并且永远无法恢复，或者可以预期它将在一段时间后恢复，或者它可能会失控并且产生错误的值。

分布式系统中，进程互相依赖以共同执行算法，因此故障可能导致整个系统的执行错误。

我们将讨论分布式系统中现有的多种故障模型，例如崩溃、遗漏和任意故障。这个列表并非面面俱到，但它涵盖了在实际中的大多数重要场景。

7.1 崩溃故障

通常，我们期望进程正确执行算法的所有步骤。最简单的崩溃方式是进程停止执行接下来的算法步骤，并且不再发送任何消息给其他进程。换句话说，该进程崩溃了。大多数情况下，我们使用崩溃–停止（crash-stop）进程抽象的假设，它规定一旦进程崩溃就会保持这种状态。

该模型不假定该进程无法恢复，也不阻拦或试图阻止恢复。这仅仅意味着该算法的正确性或活动性不依赖于恢复过程。实际上，并没有什么东西会去阻止进程恢复、追上系统状态以及参与下一次的算法执行。

失败的进程无法再继续参与当前这一轮的协作。为恢复的进程分配一个新的、不同的ID不会使模型等价于崩溃–恢复模型（之后会讨论），因为大多数算法使用预定义的进程列表，并且依据最多可容忍的故障数明确定义了故障的语义[CACHIN11]。

崩溃–恢复（crash-recovery）是另一种的进程抽象。在这个抽象中，进程停止执行算法步骤，但会在稍后恢复并尝试执行剩下的步骤。要想让恢复成为可能，需要在系统中引入持久状态以及恢复协议[SKEEN83]。允许崩溃–恢复的算法需要考虑所有可能的恢复状态，因为恢复的进程会尝试从最后一个已知的步骤开始继续执行。

想利用恢复的算法必须同时考虑状态和进程ID。在这种情况下，崩溃恢复也可以看作是遗漏故障的一种特殊情况，因为从另一个进程的角度看，不可达的进程与崩溃再恢复的进程没什么区别。

7.2 遗漏故障

另一个故障模式是遗漏故障（omission fault）。该模型假设故障进程跳过了某些算法步骤，或者无法执行这些步骤，或者执行过程对其他参与者不可见，或者无法与其他参与者通信。遗漏故障中包含了由于网络链路故障、交换机故障或网络拥塞而导致的网络分区。网络分区可以表示为单个进程或进程组之间的消息遗漏。进程崩溃可以模拟为遗漏所有该进程收发的消息。

如果进程的运行速度慢于其他参与者，发送响应比预期迟得多，那么对于系统的其余部分来说，这个节点看起来丢三落四的。慢节点没有完全停止，而是发送结果太慢，常常与其他节点不同步。

如果本应执行某些步骤的算法跳过了这些步骤或者执行结果不可见时，就发生了遗漏故障。例如，消息在送往接收方的途中丢失，而发送方就像消息发送成功时那样，没有再次发送而是继续运行，即使消息已经不可恢复地丢失了。遗漏故障也可能是由间歇性停顿、网络过载、队列满等引起的。

7.3 任意故障

最难以解决的故障种类是任意故障或拜占庭故障（Byzantine fault）：进程继续执行算法步骤，但是以与违背算法的方式（例如，共识算法中的进程决定一个从未由任何参与者提出过的值）。

此类故障可能是由于软件bug或运行不同版本算法的进程，在这种情况下，故障很容易被发现和理解。如果我们无法控制所有进程，并且其中一个进程有意地误导其他进程，则发现和理解故障会变得非常困难。

你可能在航空航天工业中听说过拜占庭式的容错：飞机和航天器的系统不会直接使用子部件传来的值，而是会对结果进行交叉验证。另一个广泛的应用是加密货币[GILAD17]，那里没有中央权威，节点被多方控制，并且敌对的参与者有强烈的动机通过提供错误响应来欺骗系统。

7.4 故障处理

我们可以通过构成进程组、在算法中引入冗余来掩盖故障：即使其中一个进程发生故障，用户也不会注意到[CHRISTIAN91]。

故障可能会带来一些性能损失：正常的执行依赖于进程可响应，而且系统必须回退到较慢的执行路径来处理故障和纠正错误。故障往往可以通过一些方式来避免，例如：代码审查、广泛的测试、引入超时重试机制确保消息送达，以及确保各算法步骤在本地按顺序执行。

我们这里介绍的大多数算法都基于崩溃-故障模型，并通过引入冗余来解决故障。这些假设帮助我们创造性能更好、更易于理解和实现的算法。

8 小结

我们讨论了一些分布式系统的术语，并介绍了一些基本概念。我们讨论了分布式系统的固有困难和复杂性，这是由于系统组件不可靠性导致的：链路可能无法传递消息、进程可能崩溃、网络可能发生分区。