Paxos made simple - 《Apaas平台》

论文地址：Paxos made simple – Lamport 2001

昨天我们看了兼职议会，兰波特的第一篇论文介绍了Paxos算法，它采用了寓言的形式。在今天的选择中，兰波特放弃了寓言，用通俗易懂的英语表达了Paxos算法。

用于实现容错分布式系统的Paxos算法一直被认为很难理解，可能是因为最初的演示对许多读者来说是希腊语。事实上，它是最简单和最明显的分布式算法之一。它的核心是一个共识算法，即兼职议会的“synod”算法。

本文的结构是熟悉的：首先Lamport解释了核心一致性协议，该协议使一组参与者能够就他们之间的一个值达成一致；然后他展示了如何实现分布式系统，通过为他们所做的每个决策运行consenus协议的一个实例，使一组服务器逐步锁定。

共识算法的核心是一个简单的事实，即它可能值得首先讨论。想象一下，一组硬币都被扔了，现在平躺在桌子上。如果大多数硬币都显示“正面”，那么就不可能有大多数硬币同时显示“反面”！我们可以将其推广到任何集合，其中成员可以自由地从V中选择某个值。如果大多数成员选择某个值V:V，则不可能有大多数成员同意V以外的任何值。现在让S的成员各自选择一个新值，并假设大多数成员选择某个新值V’。新多数派中至少有一名成员也必须是先前多数派的成员。这直接从多数的定义出发：如果从S中减去原来多数中的一组成员，则（根据定义）剩下的成员不足以构成多数。因此，任何新的多数形成，必须这样做，包括一个成员从以前的多数。

一致性算法
假设一组进程可以提出值。一致性算法确保在建议的值中选择一个。如果没有建议值，则不应选择任何值。如果选择了一个值，那么进程应该能够学习选择的值。共识的安全要求是：

只能选择已建议的值，
只选择一个值，并且
一个过程永远不会知道某个值是被选择的，除非它确实被选择了。
假设一个异步的、非拜占庭式的通信模型。

在一致性算法中要扮演三个角色：提议者、接受者和学习者。一个进程可以扮演多个角色。

就某个值达成一致的建议由建议编号和候选值组成。每个提案都有一个不同的提案编号，但多个提案可以提出相同的值。同意接受一项提议（提议的价值）需要大多数接受人的同意。如我们先前所见，不包括先前多数的至少一个承兑人，就不可能形成随后的多数。

核心共识协议有一个非常明确的推导过程，它逐步说明了为什么它需要保持原样。此推理链的结果是对提案编号和提案价值的限制，提案人可以在任何新提案中提出：在发出带有提案编号的提案之前
n、一个提议者必须向大多数接受者询问数量最多的提议的价值，了解已经接受的提议是很容易的；预测未来的接受是很难的。而不是试图预测未来，提出者控制它，提取一个承诺，将不会有任何这样的接受。换言之，提案人要求接受人不再接受编号少于n的提案。

提议者和接受者的联合作用产生以下两阶段协议：

准备阶段
提议者选择一个提议编号n，并向大多数接受者发送一个编号n的准备请求。“如果我提出一个编号为n的提案，我必须提出的价值有什么限制吗？”
如果承兑人收到编号为n的准备请求，其中n大于其已答复的任何准备请求，则承兑人应承诺不接受编号小于n的任何更多提案，并承诺接受编号最高的提案（如有）。（因此，接受者需要将他们接受的编号最高的提案以及它在准备请求中响应的最大n的高水印值保持为可靠状态）。

接受阶段

前提条件：提案人已收到大多数接受人对其编号为n的准备请求的承诺答复。
投标人发送一个接受建议书的消息（n，v），其中v是承诺回复中编号最高的接受建议书的建议书价值，或者如果未返回先前的接受，投标人选择的任何价值。
如果接受方收到编号为n的提案的接受消息，则接受该提案，除非它已对值大于n的准备请求作出响应（多个提案可能同时循环）。

学习者
我们说有三个角色：提议者、接受者和学习者。学习者是需要发现大多数接受者最终选择的建议实际上是什么的人。（请记住，这些角色通常组合在一个代理中）。

最明显的算法是让每个接受者，无论何时接受一个建议，都对所有的学习者做出响应，并将建议发送给他们。这使得学习者能够尽快找到一个选择的值，但是它要求每个接受者对每个学习者做出响应，响应的数量等于接受者数量和学习者数量的乘积。

一个不太可靠但会减少交流的模型是，让一个或多个被提名的“杰出学习者”接受者向其发送接受通知，然后将这些通知广播给其他学习者。

作业进程
为了保证进展，必须选择一位杰出的提案人作为唯一尝试提出提案的人。如果杰出的提案人能够成功地与大多数接受人沟通，并且如果它使用的提案数量大于任何已使用的提案，那么它将成功地发布一个已被接受的提案。通过放弃一个提案，并在得知某个提案编号较高的请求时重试，杰出的提案人最终将选择一个足够高的提案编号

实现分布式状态机
到目前为止，我们只研究了共识协议的一个实例或一轮。这使得一组参与者能够就单个值达成一致。从这个构建块中，我们可以构建更有趣的分布式系统。让分布式系统中给定节点的状态用一系列值（或该序列的纯函数）表示——节点是一个状态机。如果由于一轮paxos协议，序列中的每个值都得到了每个节点的同意，并且序列本身（它们出现的顺序）也得到了同意，那么我们就建立了一个模型来实现分布式系统中一组节点之间的一致性。因为有多轮Paxos协议，这有时被称为多轮Paxos。

Paxos算法假设一个进程网络。在其一致性算法中，每个过程都扮演着提议者、接受者和学习者的角色。该算法选择一个领导者，领导者扮演杰出的提议者和杰出的学习者的角色。

每个进程（节点）正在运行相同的状态机。因为这是确定性的，所以如果所有服务器都执行相同的命令序列，那么它们都会产生相同的状态序列和输出。

为了保证所有服务器执行相同的状态机命令序列，我们实现了Paxos一致性算法的独立实例（轮）序列，第i个实例（轮）选择的值是序列中的第i个状态机命令。每个服务器在算法的每个实例中扮演所有角色（提议者、接受者和学习者）。

客户机将命令发送给负责确定命令总体顺序的领导。所选的命令被赋予下一个可用的序列号，领导运行一个Paxos共识协议的实例，建议将该命令作为下一个“值”，由参与者商定。大多数情况下，这将成功，每个参与者中的状态机都可以前进。paxos协议的每一轮都包含许多往返消息，领导者不必在开始下一轮之前等待每一轮的完成，只要有客户机命令进入，领导者就可以继续分配新的序列号和发起回合。因此，我们通常会有多轮一致性算法并行运行——每轮都会就“序列号s处的命令是c”达成一致。

由于任何消息都可能被延迟或未送达，我们最终可能会在记录约定命令的日志/分类账中出现空白。例如，领导人（如果前任领导人失败，可能是新当选的领导人）可能知道第1轮至第135轮和第138轮至第140轮的结果，但还不知道第136轮和第137轮的结果。此时，状态机可以执行多达135个命令，但还不能执行138-140个，因为序列中缺少命令。在第136轮和第137轮中运行协议的第1阶段，要么显示这些轮的“最高数量的提案接受值”（领导随后提出），要么表明没有接受方接受任何提案。在后一种情况下，领导通过提出一个特殊的“禁止操作”命令来进行，该命令使分类帐间隙得以关闭，并且现在执行序列（138-140）中的后续命令。

由于领导人失败和新领导人的选举应该是罕见的事件，执行状态机命令的有效成本，即就命令/值达成一致意见的有效成本，是仅执行一致意见算法第2阶段的成本。结果表明，Paxos一致性算法的第二阶段在存在故障的情况下达到一致性的代价比任何算法都要小。因此，Paxos算法本质上是最优的。

最后一个转折点是，如果这些多个paxos轮次中涉及的服务器集也会随着时间的推移而改变呢？兰波特简单地说！:

如果服务器集可以更改，那么必须有某种方法来确定哪些服务器实现了共识算法的哪些实例。最简单的方法是通过状态机本身。当前的服务器集可以成为状态的一部分，并且可以使用普通的状态机命令进行更改。我们可以通过让执行一致算法的实例i+α的服务器集由执行第i状态机命令后的状态指定，让leader提前获得α命令。这允许简单地实现任意复杂的重新配置算法。