Paxos made simple 翻译尝试

【这篇论文我翻译下来，首先感觉还是不好懂，很多地方结论的得出不够清楚，需要读者自己思考其中的原因。要理解Paxos算法，个人建议先搜索下介绍算法的中文文章，大致了解下Paxos算法要做什么，然后就再读下论文，应该会有所感悟。】

Paxos Made Simple

Leslie Lamport

01 Nov 2001

说明

【说明这部分是我自己加的，下面这几个词大量出现与论文的主体部分，提前了解它们的含义有助于后面对于算法原理和流程的理解。】

议案(proposal):由提议人提出，由审批人进行初审和复审，包括议案编号和议案内容。
内容(value):议案的内容。
编号(id):议案的编号，全局唯一。
提议人(proposer):提出议案，接收审批人的初审和复审意见。
审批人(acceptoer):接收议案，根据规则决定初审和复审结果，返回给提议人。
执行人(learner):一旦议案成为决议，就要通知所有执行人。
初审(accept):议案的第一轮审核，通过后可以进行复审。
复审(chossen):议案的第二轮审核，通过后将成为决议。

摘要

Paxos算法，当用简明英语表述时，灰常简单。【大神的第一篇论文用在虚构的希腊岛屿Paxos上的人们通过议会表决法律来解释Paxos算法，群众纷纷表示太难理解了。大神表示你们这群渣渣不懂我的幽默，既然如此，我就用简明英语再表述一遍，哼！】

1 介绍

Paxos算法的目标是实现一个具有容错能力的分布式系统。人们觉得这一算法哪一理解，也许对许多读者来说，算法最初使用希腊语表述的。[5]事实上，这一算法是分布式算法中最简单直观的算法之一。【Google Chubby的作者Mike Burrows:there is only one consensus protocol, and that’s Paxos– all other approaches are just broken versions of Paxos.】这一算法的核心是论文[5]中提到的一致性算法“synod”。下一章我们将看到这一算法如何严格遵守我们制定的规则。最后一章会通过将一致性算法应用于构建分布式系统的确定状态机（这是分布式理论的文章最常常引用的论文的内容[4]）来对Paxos算法进行完整的解释。

2 一致性算法

2.1问题的提出

假设我们有一组服务器，他们都可以提出议案。一致性算法要保证被提出的多个议案中最终只有一个议案可以通过审核成为决议。如果没有议案提出，就不会产生决议。如果一个议案成为决议，那么所有process都应当知道这个决议。那么，要保证一致性就要满足：

所有被提出的议案中只有一个议案可以成为决议
只有一个议案成为决议，且
服务器永远不知道一个议案成为了决议，除非这个议案真的成为了决议

这一过程的运行时间并不重要，但要保证最终将会有某个议案成为决议，并且，一旦议案成为决议，所有服务器都能够知道这一决议。

我们用三类代理人代表一致性算法中的三个角色：提议人、审批人和执行人。在具体实现中，单个服务器可以扮演多种代理人，我们不需要关心他们之间的对应关系。【同一台服务器，可以即是提议人，又是审批人或执行人。】

假设代理间通过消息通信。这里我们使用传统的异步、非拜占庭模型【不考虑拜占庭问题，代理间通信可能丢失或重复，但不会被篡改】：

服务器运行效率不确定，可能停机或重启。因为当决议产生后所有服务器都有可能停机重启，所以服务器必须能够做到即使停机重启也可以记住某些信息，否则停机重启的问题将无法解决。
消息传递时间任意，消息可以重复发送，允许丢失，但不允许修改。

2.2 选择决议

只有一个审批人的状况是最简单的。提议人向审批人发送议案，审批人选择接收到的第一个议案作为决议。这个方案无法解决单机失效问题，如果审批人停机，整个系统将被阻塞。

因此，我们来尝试另一种选择决议的方式：让多个审核人共同参与决议的产生。提议人向一部分审核人发送议案，审核人可能会初审通过这一议案。当足够多的审核人初审通过这一议案时，议案就可以进行复审了。多少人算足够多？为了保证只有一个议案成为决议，足够多的人必须包括审核人的多数派，即半数以上的审批人。因为任何两个多数派集合中至少有一个成员是公共的，因此只要保证一个审批人同一时间最多只能初审通过一条议案【这里指的是审批人承认这一议案通过初审，当该议案进行复审时，也会通过复审的状态】，就可以保证最终只有一个议案可以成为决议。 (在大量论文中都涉及了多数派的研究，最早出现于[3])

在不存在服务器停机或消息丢失的前提下，我们希望即使只发起了一个议案，这个议案仍可以成为决议。因此我们需要满足以下条件：

P1.对于接收到的第一个议案，审核人必须初审通过。

但是这一条件会产生一个问题。不同提议人几乎同时提出不同的议案，导致每个审批人都初审通过了一个议案，但是没有一个议案同时被半数以上的审批人初审通过。即使只有两个议案，审批人有2n+1个，且他们分别被n个审批人初审通过，那么最后一个审批人的停机就可能导致无法产生决议。

条件P1以及决议的产生必须经过多数派审核这一条件表明审批人应当可以先后初审通过多条议案。我们通过为每一个议案分配一个编号来追踪不同的议案，这样一个议案就包括议案编号和议案内容两部分。为了防止混淆，我们要求不同议案的编号也必须不同。关于这点如何保证依赖于具体实现，我们这里只是假设他成立。【google的编号生成算法在附录，有兴趣的可以看下】当一项议案被审批人中的多数派初审通过后，这项议案的内容将进入复审阶段。

我们允许多个议案进入复审阶段，但是我们必须保证这些议案的内容是相同的。通过引入议案编号，我们可以保证以下条件：

P2.如果一个编号为n内容为v的议案【下文用议案（n,v）替代】进入复审阶段，那么所有进入复审阶段的议案编号大于n的议案，他们的议案内容也为v。

【条件P2以及后续P2的强化条件都在保证一件事：多个提议人可以提出多个议案，议案编号各不相同，但是这些议案的内容最终都会一样】

由于议案编号是有序的，条件P2严格保证了只有一个议案内容可以成为决议。

要进入复审阶段并最终成为决议，议案必须被至少一个审批人初审通过。因此要满足条件P2,我们只要满足以下条件：

P2a.如果议案（n,v）进入复审阶段，那么所有通过初审的编号大于n的议案的议案内容为v。

我们仍需要满足条件P1以保证会有决议产生。因为通信是异步的，一个议案可能被任何尚未收到过议案的审批人初审通过，这违背了条件P2a。要保证P1和P2a同时有效，需要把P2a加强为以下条件：

P2b.如果议案（n,v）进入复审阶段，那么任何提议人提出的编号大于n的议案，议案内容为v。

因为一个议案首先要由提议人提出才有可能被审批人初审通过，所以条件P2b保证了条件P2a也就保证条件P2.

在找到方法满足P2b前，我们先研究如何使这一条件成立。假设议案（m,v）进入复审阶段，如何使议案编号为n且n>m的任意议案的议案内容为v 。我们使用对n使用数学归纳法证明，这样我们要证明议案n的内容为v，就要需要额外的假设条件：任意编号在m和n-1区间内的议案的内容为v。因为议案（m,v）已经进入复审阶段，那么必然有一个多数派的审批人集合C，集合中的每个审批人都对议案m初审通过。把这一结论与额外条件结合，议案m进入复审阶段表明：

每个集合C中的审批人都初审通过一个编号在m和n-1区间内的议案，并且所有编号在m和n1-1区间内的议案内容为v。

【要理解这一部分，需要了解算法的具体执行过程。对于编号m到n-1的议案，议案的内容为v，提议人是怎么样决定议案内容的呢？提议人必然是通过向集合C中的某些成员发送初审请求并通过初步审核后，从回复信息中获知这一信息的。这就是上半句话的解释】

因为任意审批人多数派的集合S和集合C至少有一个成员相同，那么只要保证以下条件成立，议案n的内容就可以保证为v：

P2c.对任意内容v和编号n，议案（n,v）如果被某个提议人发出，那么必然有一个审批人的多数派集合S，他们要么

（a） S中的任何审批人都没有收到过编号小于n的议案，或者

（b）集合S中所有审批人初审通过的编号小于n的议案中编号最大的那个议案的议案内容为v。

我们可以证明满足条件P2c即可满足条件P2b。

要保证条件P2c，当一个提议人想要发出一个编号为n的议案时，他必须知道已经或将要通过多数派审批人初步审核的编号小于n的议案中编号最大的那个议案的内容。要知道已经通过初审的议案很简单，但是预测未来的初审结果很难。为了规避预测未来这一难题，审批人必须保证不会有允许这样的初审结果出现。也就是说，提议人要求审批人一旦初审通过编号为n的议案将不得再初审通过编号小于n的议案。因此发出议案的算法如下：

1. 一个提议人生成一个新的议案编号n并发给一半以上的任意审批人，要求他们回复：

（a）保证不再审核通过【包括初审和复审】编号小于n的议案，且

（b）如果已经初审通过了议案，把编号小于n且编号最大的那个议案的编号和内容回复给我。

这一过程称为编号为n的议案的初审请求。

2. 如果提议人收到了半数以上的初审通过回复，那么他将发起一个议案，议案的编号为n，内容为v，【请注意，此时才决定议案内容，之前初步审核只是要确认议案编号是否可用】如果审批人的回复中包括议案，v就是这些议案中编号最大的那个议案的内容，如果审批人的回复中不包括议案，那么提议人可以自己设置一个议案内容。

提议人向多数派审批人发送已经通过初审的议案（初审的多数派和这次审核的多数派成员可以不同），我们称第二次审核的过程为复审。

以上就是提议人的算法，审批人呢？他接受两种审批请求：初审请求和复审请求。审批人可以拒绝任意请求而不会对系统造成损害，我们应当说清楚在什么情况下审批人可以回复一个请求。在不违背初审通过时的承诺【保证不再审核通过编号小于n的议案】的前提下，他既可以初审通过又可以复审通过一个议案。换句话说：

P1a.一个审批人可以初审或复审通过一个议案（n,v），当且仅当他从未初审通过一个编号大于n的议案。

【当审批人从未收到任何议案时，他可以初审通过收到的任何议案，这符合条件P1.所以】P1a包含了P1.

我们现在拥有完整的决议产生算法并且满足我们设定的条件——议案编号唯一。最终算法仍需要一些优化。

假设审批人收到了一个编号为n的初审请求，但是他已经初审通过了编号大于n的议案，因此已经保证过不对编号为n的议案做出回应。因为他不会初审通过这一议案，所以他没有必要对初审请求做出回应。因此我们让审批人忽略这一初审请求，同时，审批人也会忽略再次收到的已经初审通过的议案的初审请求。

这一优化要求审批人必须且只需记住他收到过的编号最高的议案以及他初审通过的编号最高的议案。因为P2c条件在某些角色停机的情况下仍要保证有效，审批人即使在停机重启后仍要记的这些信息。注意提议人可以随时放弃当前的议案或者忘掉之前提出过的议案，但是他必须保证议案的编号唯一且递增。

把提议人和审批人的算法结合在一起，我们得到下面两个阶段的算法：

阶段1

（a）提议人生成议案编号n，向半数以上审批人发送编号为n的初审请求。

（b）如果审批人收到的初审请求编号n大于他之前初审通过的议案编号，将回复两个信息：一个是保证不再对编号小于n的议案做出回应【包括初审和复审】，二是如果之前初审通过了议案，将其中编号最大的议案的编号和内容回复给提议人。

阶段2

（a）如果提议人收到了半数以上的审批人的初审通过回复，他将会以议案（n,v）发送复审请求。对于议案内容v，如果审批人的初审回复中包含议案，那么v就是这些议案中编号最大的那个议案的内容，如果初审回复中不包含议案，提议人可以自行决定议案内容v。

（b）如果审批人收到了编号为n的议案的复审请求，只要他没有初审通过编号大于n的议案【从而做出过保证】，他会复审通过这一议案。

提议人可以在遵守算法规则的前提下提出多个议案。他可以在协议的任意阶段随时放弃某个议案。（算法不会因此出现问题，即使审核请求或回复在议案被抛弃后才接收到）如果其他提议人开始发起编号更高的议案，也许放弃当前编号较低的议案是个好主意。【不管编号更高的议案能否通过多数派的初审，都意味着当前编号的议案不会得到半数以上的通过回复，发送请求和等待回复将是浪费时间】因此，如果审批人因为保证过不再回复编号较小的议案而忽略某些议案时，他应当通知提议人：你的议案编号太小了，放弃当前议案，选一个更大的编号，重新发送申请。这是一个性能方面的优化，不会影响算法的正常运行。

2.3产生决议后如何通知执行人

要随时知道一个决议是否产生了，执行人必须能随时获悉是否有一个议案被半数以上审批人复审通过。首先想到的算法是，让审批人每次复审通过一条议案，就给所有执行人发送一条消息。这使得执行人可以实时了解当前审核情况，但是这要求每个审批人和每个执行人通信，通信规模是两者数量的乘积。

非拜占庭问题的假设使得执行人获得消息变得简单。我们可以选出一个执行人代表，所有审批人都与执行人代表进行通信，而当决议产生时，执行人代表再把决议通知其他执行人。这里需要一轮额外的通信以通知所有执行人当前决议。而且这一做法更不可靠，因为执行人代表也可能停机。但是他的通信量仅仅是两者数量之和。

更进一步，我们可以让审批人和多个执行人代表通信，每个执行人代表都可以在决议产生后通知其他执行人。多个执行人代表可以使系统更加稳定但是通信的复杂度也会提高。

由于允许通信失败，执行人可能无法得知进入复审阶段议案的内容。执行人可以向所有审批人询问当前初审通过的议案，但是某个审批人停机就可能导致没有一个议案被半数以上审批人初审通过。在这一情况下，只有当新的议案进入复审阶段时，执行人才能知晓议案内容。如果执行人需要知道当前是否有进入复审阶段的议案的内容，他可以要求提议人根据上面的算法发起一个议案。【这个新议案的议案编号足够大，发起初审请求后能够得到半数以上审批人的回复，他们的回复中如果有议案，议案编号最大的那个议案内容就是目前进入复审阶段的议案内容。提议人可以继续发起复审请求，也可以放弃当前议案。最终产生的决议内容是不会发生变化的。】

2.4保证算法的进行

很容易就可以想到一个场景，两个提议人轮流发起编号递增的提议并通过初步审核，虽然按照算法规则，他们的提议内容是相同的，但是由于复审请求时，审批人已经初审通过了另一个编号更高的议案，导致自己的复审请求无法通过，因此永远无法产生决议。提议人p的议案n1通过初审，然后提议人q的议案n2通过初审，n2>n1；提议人p的复审请求将被忽略，因为审批人已经保证过不再回复编号小于n2的议案。然后提议人p将议案编号提高为n3，n3>n2，并通过初步审核，导致q的复审请求也被忽略。这样重复下去，永远无法产生决议。【活锁】

要保证算法进行下去，必须选出一个提议人代表，只有他可以发出议案。如果提议人代表可以和半数以上的审核人成功通信，并且他提出的议案编号比所有已经提出过的议案的编号都大，他就可以成功让议案变成决议。如果通过审核人的忽略回复得知已经存在某些编号更高的议案，提议人代表会放弃当前议案，增大议案编号然后重新进行步骤一的初步审核，最终，提议人代表能够选出一个足够大的编号用于产生决议。

如果分布式系统中足够多的部分正常工作（至少一个提议人、半数以上审批人、工作正常的通信网络），通过选举选出一个提议人代表就可以保证系统正常运行。Fischer,lynch和Patterson[1]的著名研究结果表明，可靠地选举算法要么是随机的，要么是实时的-比如使用超时机制。【另一篇文章中关于FLP理论与Paxos算法的讨论：其实仔细回忆Paxos论文会发现，Paxos中存在活锁，理论上的活锁会导致Paxos算法无法满足Termination属性，也就不算一个正确的一致性算法。Lamport在自己的论文中也提到“FLP结果表明，不存在完全满足一致性的异步算法..."，因此他建议通过Leader来代替Paxos中的Proposer，而Leader则通过随机或其他方式来选定（Paxos中假如随机过程会极大降低FLP发生的概率）。也就是说Paxos算法其实也不算理论上完全正确的，只是在工程实现中避免了一些理论上存在的问题。但这丝毫不影响Paxos的伟大性！】但是，不管选举成功还是失败，系统安全性都可以得到保障。

2.5实现

Paxos算法[5]建立在一组通过网络通信的服务器上。在此一致性算法中，每个服务器都可以是提议人、审批人或执行人。算法选举出一个提议人代表防止活锁出现、选出一个执行人代表降低通信复杂度。Paxos一致性算法中的审核请求和审核回复都以普通消息的形式发送（审核回复带有相应的议案编号防止出现消息发送失败、延迟或重复时导致提议人的混乱）。持久化存储保证即使停机后仍可以保存数据，用来保存审核人必须记住的信息。审核人在发送审核回复消息前，会先在持久化存储中存储这些消息。

最后要描述的是实现任意两个议案编号不相同的机制。不同的提议人从互不相交的集合中选择编号，因此两个提议人不会生成相同的编号。每个提议人都会存储他们发出过的最大的议案编号，当他们再次开始步骤一的初步审核申请时，会选择一个比之前议案编号更大的编号。

3有限状态机的实现

实现分布式系统的一个方案是由一组客户端向中心服务器发送指令。中心服务器作为确定状态自动机按一定顺序执行接收的指令。状态机根据当前状态和接收到的指令产生输出结果和新的状态。例如，分布式银行系统的客户端可能是出纳员，而状态机的状态可能是所有账户余额的集合。提现操作会向状态机发出指令，当且仅当账户余额不小于提现金额时，减少账户余额数量【新的状态】，并返回提现前后的余额【输出】。

单个中心服务器无法解决单机失效问题。因此我们使用一组中心服务器，每个服务器都是一个独立的状态机。因为状态机属于确定状态自动机，所以当输入命令的内容和顺序相同时，这些状态的状态变化和输出也是相同的。因此客户端的指令发送给任何服务器都是有效的。

要保证所有服务器执行相同的状态机指令序列，我们执行多轮paxos一致性算法，第i轮产生的决议作为指令序列中第i条状态机指令。每个服务器都将作为提议人、审核人和执行人参与到算法中。我们假设服务器组不发生变动，每一轮算法执行都是用同一组服务器。

通常，某个服务器会被选出作为提议人代表，在每一轮算法执行时，只有代表可以提出议案。客户端向代表发送指令，由提议人代表决定指令应该何时执行。如果代表决定某条指令应当成为指令队列中第135条指令，他会把这条指令作为议案内容发送给审核人，最终形成决议。一般情况下总是可以成功的。但也有失败的可能，如果出现通信失败、停机或者另一个服务器误以为自己也是提议人代表，并且希望另一条指令成为第135条指令。但是Paxos算法保证至多只有一条指令可以成为第135条指令。

产生这一结果的关键是，在Paxos一致性算法中，决议必须要经过复审才可以产生。回想一下，当议案通过初审时，提议人自己也不确定议案内容是什么，他必须根据审批人的回复来决定要么使用之前的议案内容、要么自己决定议案内容。

现在我将描述正常情况下Paxos状态机如何工作。稍后，再来讨论可能出现的风险。考虑上一个代表停机，新的代表刚刚选出的情况。（系统启动状态是一个特殊状态，此时还没有任何议案提出）

新的提议人代表，作为执行人，应当知道已经产生的指令队列中的大部分指令。假设他知道指令1-134号，138号和139号，即第1轮到134轮，138轮和139轮算法执行的结果。（我们稍后会看到这种指令空缺是如何产生的）然后他开始执行空缺的135-137轮算法以及139轮以后的算法的初审阶段。假设只有135轮和140轮的议案初审通过的回复中包含指令信息，其他轮的初审回复不包含指令信息【这里是指135轮和140轮之前已经进行过，在初审通过的返回信息中包含了之前已经进入复审阶段的议案，而进入复审阶段的议案是包含议案内容的，因此不需要等待客户端发送指令请求来决定议案内容，可以直接发起复审请求】。提议人代表之后会执行135轮和140轮的复审阶段，最终产生135号指令和140号指令。

提议人代表以及所有从提议人代表处了解到所有指令的服务器都可以执行1-135号指令。但是，138号-140号指令不能执行，因为136号和137号指令还没有产生。提议人可以用接下来收到的两条客户端指令请求作为136号和137号指令。但是为了立即弥补指令空缺，我们用‘no-op’指令作为136号和137号指令的议案内容，这一指令不会对状态机状态产生影响。一旦这两条no-op指令被选出为决议，指令138号-140号就可以执行了。

第1号-140号指令都已经产生。提议人代表也已经完成了所有编号大于140的指令的初审阶段，提议人代表可以自由决定复审阶段应当使用的议案内容。他把接下来收到的第一个客户端指令请求作为141号指令进行复审。接着把收到的下一条客户端指令作为142号，以此类推。

提议人代表不需要等待141号指令产生就可以发起142号指令的复审请求。有可能提议人发出的所有141号指令复审请求都发送失败，可能142号指令已经产生了，执行人还不知道141号指令的内容是什么。当执行人没有收到关于141号指令的复审请求回复时，他会再次发送请求。如果一切正常，141号指令就会成功产生。然而，这次仍有可能失败，导致指令队列中出现空缺。综上，如果一个提议人可以一次产生长度为α的指令队列，那么当指令1到指令i产生后，他可以继续产生指令i+1到i+α。最坏的情况是产生一个α-1大小的指令空缺。【i+1轮到i+α-1轮的算法执行都没有成功，i+α轮执行成功】

新产生的提议人代表要执行无限多次初审请求【初审请求为了确定议案的编号，不需要知道议案的内容，也就是说在收到初审通过的回复前，提议人也不知道指令内容是什么，由于整个系统中只有一个提议人发送请求，初审请求一般是一次通过的】，在上面的场景中，提议人要执行135轮-137轮以及139轮之后算法的初审阶段。通过在审核回复中添加额外的信息【当前算法执行轮数】，提议人就可以在不同算法执行轮中使用相同的议案编号。在初审阶段，仅当某个议案进入复审阶段时，审批人在回复给其他提议人的初审通过消息中会附带该议案的议案编号和议案内容。因此，审批人对于每一轮算法执行过程中的消息回复都可以非常精简。【仅包括算法执行轮数和已经进入复审的议案内容】即使执行无穷多次初审阶段也不会造成任何问题。

由于提议人代表停机并选择新的提议人是非常罕见的情况，产生状态机指令序列的效率，也就是在指令/决议上达成一致的效率仅仅取决于算法执行的复审阶段。可以证明，在允许失效的情况下【停机、消息发送失败】，Paxos算法比其他任何算法都更加高效。因此，Paxos算法绝对是一致性算法的最佳选择。

以上讨论假设提议人代表在系统中一直在线，除了当前代表停机和选出新代表间的短暂时间。在特殊情况下，新代表的选举也可能失败。如果没有提议人代表在线，就无法产生新的指令。如果多个服务器都认为自己是代表，那么他们会在算法执行的每一轮都提出议案，导致活锁，同样使得指令无法产生。然而算法的安全性是可以保证的，两个服务器也许会提出不同的议案，但是他们的议案内容必然是相同的。选出单个的提议人代表只是为了避免活锁的出现。

如果服务器组可以变动，必须有办法确定哪些服务器参与了某一轮算法的执行。最简单的方法是通过改变状态机状态来实现。当前服务器组作为状态信息的一部分，当服务器发生变化时，可以通过状态机指令修改状态来记录。在执行完第i条指令后，通过标明将要参与第i+α轮算法执行的服务器组，就可以保证执行人代表可以提前发布α条指令的初审请求。这样就实现了一个简单地arbitrarily sophisticated reconfiguration algorithm。

参考文献

[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
[3] Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978.
[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.
[5] Leslie Lamport. The part-time parliament. ACM Transactions on Com- puter Systems, 16(2):133–169, May 1998.