1. 简介

用于实现高容错性分布式系统的Paxos算法，一直以来总是被认为是难以理解的，或许是因为对很多人来说，初始版本就像是”希腊语"一样（最初的论文是以希腊故事展开的形式）[5]。实际上，它也算是最浅显易见的分布式算法之一了。它的核心就是一个一致性算法——论文[5]中的“synod”算法。在下一个章节可以看到，它基本上是根据一个一致性算法所必需满足的条件自然而然地推断出来的。最后一个章节，我们通过将Paxos算法作为构建一个实现了状态机的分布式系统的一致性实现，来完整地描述它。这种使用状态机方法的论文[4]应该早已广为人知，因为它可能已经是分布式系统理论研究领域被引用最广泛的了。

2. 一致性算法

2.1 问题描述

假设有一组可以提出提案的进程集合。一个一致性算法需要保证：

• 在这些被提出的提案中，只有一个会被选定。
• 如果没有提案被提出，则不会有被选定的提案。
• 当一个提案被选定后，进程应该能获取被选定提案的信息。

对于一致来说，安全性（Safety）需求是这样的：

• 只有被提出的提案才能被选定。
• 只能有一个值被选中（chosen），同时
• 进程不能认为某个提案被选定，除非它真的是被选定的那个。

我们不会尝试去精确地描述活性（Liveness）需求。但是从总体上看，最终的目标是保证有一个提案被选定，并且当提案被选定后，进程最终也能获取到被选定提案的信息。

在这个一致性算法中，有三个参与角色，我们分别用Proposer，Acceptor和Learner来表示。在具体实现中，一个进程可能充当不止一种角色，但是在这里我们并不关心它们之间的映射关系。

假设不同的参与者之间可以通过发消息来进行通信，我们使用普通的非拜占庭模式的异步模型：

• 每个参与者以任意的速度运行，可能会因停止而执行失败，也可能会重启。当一个提案被选定后，所有的参与者都有可能失败然后重启，除非这些参与者可以记录某些信息，否则是不可能存在一个解法的。
• 消息在传输中可能花费任意时间，可能会重复，也可能丢失，但不会被损坏（不会被篡改，即不会发生拜占庭问题）。

2.2 提案的选定

选定提案最简单的方式就是只有一个Acceptor存在。Proposer发送提案给Acceptor，Acceptor会选择它接收到的第一个提案作为被选提案。虽然简单，这个解决方案却很难让人满意，因为当Acceptor出错时，整个系统就无法工作了。

因此，我们应该选择其他方式来选定提案，比如可以用多个Acceptor来避免一个Acceptor的单点问题。这样的话，Proposer向一个Acceptor集合发送提案，某个Acceptor可能会通过（accept）这个提案。当有足够多的Acceptor通过它时，我们就认为这个提案被选定了。那么怎样才算是足够多呢？为了确保只一个提案被选定，我们可以让这个集合大到包含了Acceptor集合中的多数成员。因为任意两个多数集（majority）至少包含一个公共成员，如果我们再规定一个Acceptor只能通过一个提案，那么就能保证只有一个提案被选定（这是很多论文都研究过的多数集的一个普通应用[3]）。

假设没有失败和消息丢失的情况，如果我们希望在每个Proposer只能提出一个提案的前提下仍然可以选出一个提案来，这就意味着如下需求：

    P1. 一个Acceptor必须通过它收到的第一个提案。

但是这个需求会引发另外的问题。如果有多个提案被不同的Proposer同时提出，这会导致虽然每个Acceptor都通过了一个提案，但是没有一个提案是由多数人通过的。甚至即使只有两个提案被提出，如果每个都被差不多一半的Acceptor通过了，哪怕只有一个Acceptor出错都可能导致无法确定该选定哪个提案。

P1再加一个提案被选定需要由半数以上Acceptor通过的这个需求，暗示着一个Acceptor必须要能通过不止一个提案。我们为每个提案分配一个编号来记录一个Acceptor通过的那些提案，于是一个提案就包含一个提案编号以及它的value值。为了避免造成混淆，需要保证不同的提案具有不同编号。如何实现这个功能依赖于具体的实现细节，在这里我们假设已经实现了这种保证。当一个具有value值的提案被多数Acceptor通过后，我们就认为该value被选定了。同时我们也认为该提案被选定了。

我们允许多个提案被选定，但是我们必须保证所有被选定的提案具有相同的值value。通过对提案编号的约定，它需要满足以下保证：

  P2. 如果具有value值v的提案被选定了，那么所有比它编号高的提案的value值也必须是v。

因为编号是完全有序的，所以条件P2就保证了只有一个value值被选定这一关键安全性属性。

一个提案能被选定，必须要被至少一个Acceptor通过，所以我们可以通过满足如下条件来满足P2:

    P2a. 如果一个具有value值v的提案被选定了，那么被Acceptor通过的所有编号比它高的提案的value值也必须是v。

我们仍然需要P1来保证有提案会被选定。因为通信是异步的，一个提案可能会在某个Acceptor c还没收到任何提案时就被选定了。假设有个新的Proposer上线了，然后提出了一个具有不同value值的更高编号的提案，根据P1, 需要c通过这个提案，但这是与P2a相矛盾的。因此为了同时满足P1和P2a，需要对P2a进行强化：

    P2b. 如果具有value值v的提案被选定了，那么所有比它编号更高的被Proposer提出的提案的value值也必须是v。

一个提案被Acceptor通过之前肯定是由某个Proposer提出，因此P2b就隐含P2a，进而隐含了P2。

为了发现如何保证P2b，我们来看看如何证明它成立。我们假设某个具有编号m和value值v的提案被选定了，需要证明任意具有编号n（n > m）的提案都具有value值v。我们可以通过对n使用数学归纳法来简化证明，这样我们可以在额外的假设下——即编号在m..(n-1)之间的提案具有value值v，来证明编号为n的提案具有value值v，其中i..j表示从i到j的集合。因为编号为m的提案已经被选定了，这就意味着存在一个多数Acceptor组成的集合C，C中的每个成员都通过了这个提案。结合归纳的假设，m被选定意味着：

    C中的每一个Acceptor都通过了一个编号在m..(n-1)之间的提案，并且每个编号在m..(n-1)之间的被Acceptor通过的提案都具有value值v。

由于任何包含多数Acceptor的集合S都至少包含一个C中的成员，我们可以通过保持如下不变性来确保编号为n的提案具有value值v：

    P2c. 对于任意v和n，如果一个编号为n，value值为v的提案被提出，那么肯定存在一个由多数Acceptor组成的集合S满足以下条件中的一个：

     a. S中不存在任何Acceptor通过了编号小于n的提案，或

     b. v是S中所有Acceptor已经通过的编号小于n的具有最大编号的提案的value值。

通过维护P2c的不变性我们就可以满足P2b的条件了。

为了维护P2c的不变性，一个Proposer在提出编号为n的提案时，如果存在一个将要或者已经被多数Acceptor通过的编号小于n的最大编号提案，Proposer需要知道它的信息。获取那些已经被通过的提案很简单，但是预测未来会被通过的却很困难。为了避免去预测未来，Proposer通过提出承诺不会有那样的通过情况来控制它。换句话说，Proposer会请求那些Acceptor不要再通过任何编号小于n的提案了。这就导致了如下的提案生成算法：

1. Proposer选择一个新的提案编号n，然后向某个Acceptor集合中的成员发送请示，要求它作出如下回应：

        （a）保证不再通过任何编号小于n的提案，以及

        （b）当前它已经通过的编号小于n的最大编号提案，如何存在的话。

     我们把这样的请求称为编号为n的prepare请求。

2. 如果Proposer收到来自集合中多数成员的响应结果，那么它可以提出编号为n，value值为v的提案，这里v是所有响应中最大编号提案的value值，如果响应中不包含任何提案，那么这个值就由Proposer自由决定。

Proposer通过向某个Acceptor集合发送需要被通过的提案请求来产生一个提案（这里的Acceptor集合不一定是响应最初请求的集合）。我们把这个叫做accept请求。

目前我们描述了Proposer端的算法。那么Acceptor端是怎样的呢？它可能会收到来自Proposer端的两种请求：prepare请求和accept请求。Acceptor可以忽略任意请求而不用担心破坏算法的安全性。因此我们只需要说明它在什么情况下可以对一个请求作出响应。它可以在任何时候响应prepare请求也可以在不违反现有承诺的情况下响应accept请求。换句话说：

    P1a. 一个Acceptor可以通过一个编号为n的提案，只要它还未响应任何编号大于n的prepare请求。

可以看出P1a包含了P1。

现在我们就获得了一个满足安全性需求的完整提案选定算法——假设在提案编号唯一的前提下。只要再做点小优化，就能得到最终的算法了。

假设一个Acceptor收到了一个编号为n的prepare请求，但是它已经对编号大于n的prepare请求作出了响应，因此它肯定不会再通过任何新的编号为n的提案。那么它就没有必要对这个请求作出响应，因为它肯定不会通过编号为n的提案，于是我们会让Acceptor忽略这样的prepare请求，我们也会让它忽略那些它已经通过的提案的prepare请求。

通过这个优化，Acceptor只需要记住它已经通过的提案的最大编号以及它已经响应过prepare请求的提案的最大编号。因为必须要在出错的情况下也保证P2c的不变性，所以Acceptor要在故障和重启的情况下也能记住这些信息。Proposer可以随时丢弃提案以及它的所有信息——只要它可以保证不会提出具有相同编号的提案即可。

把Proposer和Acceptor的行为结合起来，我们就能得到算法的如下两阶段执行过程：

Phase 1:

• Proposer选择一个提案编号n，然后向Acceptor的多数集发送编号为n的prepare请求。
• 如果一个Acceptor收到一个编号为n的prepare请示，且n大于它所有已响应请求的编号，那么它就会保证不会再通过任意编号小于n的提案，同时将它已经通过的最大编号提案（如果存在的话）一并作为响应。

Phase 2:

• 如果Proposer收到多数Acceptor对它prepare请求（编号为n）的响应，那么它就会发送一个编号为n，value值为v的提案的accept请求给每个Acceptor，这里v是收到的响应中最大编号提案的值，如果响应中不包含任何提案，那么它就可以是任意值。
• 如果Acceptor收到一个编号为n的提案的accept请求，只要它还未对编号大于n的prepare作出响应，它就可以通过这个提案。

一个Proposer可以提出多个提案，只要它能遵循以上算法约定。它可以在任意时刻丢弃某个提案（即使针对该提案的请求或响应在提案丢弃后很久才到达，正确性依然可以保证）。如果有Proposer已经在尝试提交更大编号的提案，那么丢弃也未尝不是一件好事。因此，如果一个Acceptor因为已经收到更高编号的prepare请求而忽略某个prepare或者accept请求，它应该通知对应的Proposer，然后该Proposer可以丢弃这个提案。这是一个不影响正确性的性能优化。

2.3 获取选定值

为了获取被选定的值，一个Learner必须要能知道一个提案已经被多数Acceptor通过了。最直观的算法是，让每个Acceptor在通过一个提案时就通知所有Learner，把通过的提案告知它们。这可以让Learner尽快找到被选定的值，但这需要每个Acceptor和Learner之间互相通信——通信次数等于二者数量的乘积。

在假设非拜占庭错误的前提下，一个Learner可以很容易地通过另一个Learner了解一个值已经被选定了。我们可以让所有Acceptor将它们的通过信息发送给一个特定的Learner，当一个value被选定时，由它来通知其他Learner。这种方法需要额外一个步骤才能通知到所有Learner，而且它也不是可靠的，因为那个特定的Learner可能会发生一些故障。但是这种情况下的通信次数，只需要二者数量之和。

更一般地，Acceptor可以将它们的通过信息发送给一个特定的Learner集合，它们中的任何一个都可以在某个value被选定后通知所有Learner。这个集合中的Learner越多，可靠性就越好，通信复杂度也相应更高。

因为消息可能会丢失，一个value被选定后，可能没有Learner会发现。Learner可以向Acceptor询问它们通过了哪些提案，但是任一Acceptor出错，都有可能导致无法分辨是否有多数Acceptor通过了某个提案。在这种情况下，只有当一个新的提案被选定时，Learner才能发现被选定的value。如果一个Learner想知道是否已经选定一个value，它可以让Proposer利用上面的算法提出一个提案。

2.4 处理流程

很容易可以构造出这样一种情况，两个Proposer持续地提出序号递增的提案，但是没有提案会被选定。Proposer p为编号为n1的提案完成Phase 1, 然后另一个Proposer q为编号为n2(n2>n1)的提案完成Phase 1。Proposer p对于编号n1的Phase 2的accept请求会被忽略，因为Acceptor承诺不再通过任何编号小于n2的提案。这样Proposer p就会用一个新的编号n3(n3>n2)重新开始并完成Phase 1，这又导致了Proposer q对于Phase 2的accept请求被忽略，如此往复。

为了保证进度，必须选择一个特定的Proposer作为唯一的提案提出者。如果这个Proposer可以和多数Acceptor进行通信，并且可以使用比已用编号更大的编号来进行提案的话，那么它提出的提案就可以成功被通过。如果知道有某些编号更高的请求，它可以通过舍弃当前的提案并重新开始，这个Proposer最终一定会选到一个足够大的提案编号。

如果系统中有足够的组件（Proposer, Acceptor以及通信网络）工作良好，通过选举一个特定的Proposer，活性（Liveness）就能够达到。著名的FLP理论[1]指出，一个可靠的Proposer选举算法要么利用随机性要么利用实时性来实现——比如使用超时机制。然而无论选举是否成功，安全性（Safety）都可以得到保证。

2.5 算法实现

Paxos算法[5]假设了一组进程网络。在它的一致性算法中，每个进程都扮演着Proposer, Acceptor以及Learner的角色。该算法选择了一个Leader来扮演那个特定的Proposer和Learner。Paxos一致性算法就是上面描述的那个，请求和响应都以普通消息的方式发送（响应消息通过对应的提案编号来标识以避免混淆）。使用可靠的存储保存Acceptor需要记住的信息来防止出错。Acceptor在真正发送响应之前，会将它记录到可靠的存储中。

剩下的就是描述如果保证不会用到重复编号的机制了。不同的Proposer从不相交的编号集合中选择自己的编号，这样任何两个Proposer就不会用到相同的编号了。每个Proposer都记录（在可靠存储中）它使用过的最大编号，然后用比这更大编号的提案开始Phase 1。

3. 状态机实现

有一种实现分布式系统的简单方式，就是使用一组客户端集合向中央服务器发送指令。服务器可以看成一个以某种顺序执行客户端指令的确定性状态机。这个状态机有个当前状态，通过接收一个指令当作输入来产生一个输出和新状态。比如，分布式银行系统的客户端可能是一些出纳员，状态机的状态则由所有用户的账户余额组成。一个取款操作，通过执行一个减少账户余额的状态机指令（当且仅当余额大于取款数目时）实现，然后将新旧余额作为输出。

使用单点中央服务器的系统在该服务器故障的情况下，整个系统都将运行失败。因此我们用一组服务器来代替它，每个服务器都独立实现了该状态机。因为这个状态机是确定性的，如果所有服务器都以同样的顺序执行指令，那么它们将产生相同的状态机状态和输出。一个提出指令的客户端，可以使用任意服务器为它产生的输出。

为了保证所有服务器都能执行相同的状态机指令序列，我们需要实现一系列独立的Paxos一致性算法实例，第i个实例选定的值作为序列中的第i个状态机指令。在算法的每个实例中，每个服务器担任所有角色（Proposer，Acceptor和Learner）。现在，我们假设服务器的集合是固定的，这样所有的一致性算法实例都具有相同的参与者集合。

在正常执行中，一个服务器被选举成为Leader，它会在所有一致性算法实例当中扮演特定的Proposer（唯一的提案提出者）。客户端给Leader发送指令，它来决定每条指令出现在序列当中的位置。如果Leader决定某个客户端指令应该是第135个，它会尝试让该指令成为第135个一致性算法实例选定的value值。这通常都会成功，但是在一些故障或者有另外的服务器也认为自己是Leader并且对第135个指令持有异议时，它可能会失败。但是一致性算法可以保证，最多只有一条指令会被选定为第135条。

这个方法的关键在于，在Paxos一致性算法中，被提出的value值只在Phase 2才会被选定。回忆一下，在Proposer完成Phase 1时，要么提案的value值被确定了，要么Proposer可以自由提出任意值。

我们现在描述了Paxos状态机实现是怎样在正常情况下运行的，接下来我们看看会有哪些出错的情况，看下之前的Leader故障以及新的Leader被选举出来后会发生什么（系统启动是一种特殊情况，此时还没有提案被提出）。

新的Leader被选举出来后，首先要成为所有一致性算法实例的Learner，需要知道目前已经选定的大部分指令。假设它知道指令1-134，138以及139——也就是一致性算法实例1-134，138以及139选定的值（后面我们会看到这样的指令缺口是如何产生的）。接下来它会执行135-137以及139以后的算法实例的Phase 1（下面会描述如何来做）。假设执行结果表明，实例135和140的提案值已被确定，但是其他执行实例的提案值是没有限制的。那么Leader可以执行实例135和140的Phase 2，进而选定第135和140条指令。

Leader以及其他已经获取Leader所有已知指令的服务器，现在可以执行指令1-135。然而它还不能执行指令138-140，因为指令136和137还未被选定。Leader可以将接下来两条客户端请求的指令当作指令136和137。同时我们也可以提出一个特殊的“no-op”指令来立即填补这个空缺但保持状态不变（通过执行一致性算法实例136和137的Phase 2来完成）。一旦该“no-op”指令被选定，指令138-140就可以被执行了。

指令1-140目前已经被选定了。Leader也已经完成了所有大于140的一致性算法实例的Phase 1，而且它可以在Phase 2中自由地为这些实例指定任意值。它为下一个从客户端接收的指令分配序号141， 并在Phase 2中将它作为第141个一致性算法实例的value值。它将接收到的下一个客户端指令作为指令142, 并以此类推。

Leader可以在它提出的指令141被选定前提出指令142。它发送的关于指令141的提案信息可能全部丢失，因此在所有其他服务器获知Leader选定的指令141之前，指令142就可能已被选定。当Leader无法收到实例141的Phase 2的期望回应时，它会重传这些信息。如果一切顺利的话，它的提案指令将被选定。但是仍然可能会失败，造成在选定的指令序列中出现缺口。一般来说，假设Leader可以提前确定a个指令，这意味着指令1到i被选定之后，它就可以提出i+1到i+a的指令了。这样就可能形成长达a-1的指令缺口。

一个新选定的Leader需要为无数个一致性算法实例执行Phase 1——在上面的场景中，就是135-137以及所有大于139的执行实例。通过向其他服务器发送一条合适的消息，就可以让所有执行实例使用同一个提案编号（计数器）。在Phase 1中，只要一个Acceptor已经收到来自某Proposer的Phase 2消息，那么它就不止回应一个简单的“OK”（在上面的场景中，就是针对135和140的情况）。因此一个服务器（作为Acceptor时）可以用一条适当的短消息对所有实例作出回应。执行这样无限多的实例的Phase 1也不会有问题。

由于Leader的故障和新Leader的选举是很少见的情况，那么执行一条状态机指令的主要开销，即在指令值上达成一致性的开销，就是执行一致性算法中Phase 2的开销。可以证明，在允许失效的情况下，Paxos一致性算法的Phase 2在所有一致性算法中具有最小可能的时间复杂度[2]。因此Paxos算法基本上是最优的。

在系统正常运行的情况下，我们假设总是只有一个Leader，只有在当前Leader故障及选举出新Leader之间的短时间内才会违背这个假设。在特殊情况下，Leader选举可能失败。如果没有服务器扮演Leader，那么就没有新指令被提出。如果同时有多个服务器认为自己是Leader，它们在一个一致性算法执行实例中可能提出不同value值，这可能导致没有任何值能被选定。但是安全性（Safety）是可以保证的——不可能有两个不同的值被选定为第i条状态机指令。单个Leader的选举只是为了保证流程能往下进行。

如果服务器的集合是变化的，那么必须有某种方法可以决定哪些服务器来实现哪一些一致性算法实例。最简单的方式就是通过状态机本身来完成。当前的服务器集合可以是状态的一部分，同时也可以通过状态机指令来改变。我们通过执行完第i条指令后的状态，可以让Leader预定a条指令，指定执行i+a条指令的服务器集合。这样就简单实现了一个复杂的重配置算法。

参考文献

[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] (1, 2, 3, 4) Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, May 1998.