理解Paxos算法

1. 背景

Paxos是一种分布式一致性算法，该算法由Leslie Lamport在论文[The part-time parliament][1]中提出，论文最早于1990年提交到ACM TOCS，最后发表却已是1998年了。为了形象地描述一致性算法，Lamport精心设计了一种场景，即希腊小岛Paxos上的兼职议会，并描述议会所面临的问题以及解决的过程，逐步推导并证明完整的议会协议，议会协议其实就是分布式一致性协议（也称算法），虽然Paxos岛是虚构的，但并不影响人们以Paxos来命名该算法。

或许是Lamport以希腊小岛民主投票的类比法描述一致性算法让人不易看懂，而他又不愿听取ACM TOCS主编的建议对论文做修改，所以该论文提交之后一直未被发表，直到若干年后Butler Lampson和Nancy Lynch等人发现了Paxos算法的价值。图灵奖获得者Butler Lampson于1996年在其论文[How to Build a Highly Availability System using Consensus][3]中描述了如何用Paxos构建一个容错的系统，次年Nancy Lynch（FLP理论[4]作者之一）在论文[Revisiting the paxos algorithm][5]中重点阐述了Paxos算法。而ACM TOCS也最终于1998年发表了Lamport的论文[The part-time parliament][1]。

也许Lamport本人也认同大家觉得基于希腊故事描述的Paxos算法难以理解，后来他在2001年发表了论文[Paxos made simple][2]，用简单明了的方式重新描述了Paxos算法。

2. 适用场景

探讨一致性算法通常需要先明确分布式环境的网络模型和失效模型，Paxos算法适用于异步网络和非拜占庭的Crash-Recover失效模型，它们具有如下特点：

1) 首先进程能够按照程序逻辑执行，并返回正确结果（不会是拜占庭式的任意错误）

2) 但是进程处理事件的速度不可预测，甚至会Crash

3) 进程Crash之后能够重启，并接着之前的状态继续提供服务

4) 进程可以访问一个不受Crash影响的持久化存储（即日志可以保存下来）

5) 消息传送速度同样不可预测，消息可能被丢失，也可能被重发，但内容不会损坏

简单来说，Paxos算法所要解决的问题是在这样的分布式环境下实现“多个进程对某个变量的取值达成一致”。

Paxos算法典型应用之一是构建分布式容错数据库[6]：位于多个副本节点的进程，对一系列输入值重复执行Paxos算法，就能够在每个副本上构建出关于这些输入值的相同日志，如果这些日志是一系列数据库操作，且所有副本都执行这些相同的操作序列，最终所有副本都会具有相同的数据库内容。

3. 算法演化

Lamport论文[1,2]从数学的角度，提出一致性的相关要求、假设、满足的条件以及条件的公式化表示，进而给出引理、定理并证明，最后推导出议会协议的初级版、基础版和完整版，过程严谨且具有学术性和理论性。

Paxos算法定义了三种角色：Acceptor、Proposer和Learner，其中Proposer是提议发起者，负责接收客户端请求，并将客户端的请求发送到Paxos集群中，以便决定这个值是否可以被批准；Acceptor是提议批准者，负责处理接收到的提议；Learner是学习者，只能学习到已经被批准的值，不能学习没有被批准的值。每一个进程都可以扮演其中任意一种角色。   

Paxos完整算法核心过程包含prepare和accept两个阶段，可大致描述为：

1) prepare阶段：Proposer向Acceptor发起提议权申请请求（Prepare消息），Acceptor负责批准Proposer申请的提议权，如果同意就回复Promise消息

2) accept阶段：Proposer一旦获得提议权即可进一步提交变量取值（Accept消息），Acceptor负责批准Proposer提交的变量取值，如果接受就回复Accepted消息

如前所述，Paxos算法是针对“多个进程对某个变量取值达成一致”这一问题的一种解决方法，而由浅入深的、由简到繁的求解过程以及过程中的优化策略，将有助于更好的理解算法。我们从一个最简单的解决方案开始，逐步优化并最终得到Paxos算法。

3.1 单Acceptor

最简单的方法就是采用单个Acceptor，所有Proposer发送提议给这个Acceptor，它选择并处理最先收到的提议。然而单Acceptor面临单点失效的风险，一旦Acceptor宕机，系统将无法继续提供服务。

3.2 多Acceptor

3.2.1 Acceptor多数派

显然多个Acceptor是必须的。在多Acceptor情况下，总有Acceptor会宕机，所以无法要求“所有”Acceptor都同意某变量取值，事实上只要“多数”Acceptor都同意某变量取值，那么一致性最终也是可以保证的。所谓的“多数”至少要达到“半数以上”分析如下：

采用反证法。假设有两个Proposer，Proposer 1仅给其中一半Acceptor提交变量取值V1， Proposer 2给另外一半Acceptor提交变量取值V2，理论上两个Acceptor半集会分别同意两个Proposer的申请，如果这样的话，这些Acceptor对变量取值没有达成一致（一半认为是V1，另一半认为是V2）。

在Paxos算法中称为“半数以上”Acceptor称为“多数派”，通俗来讲就是Proposer获得了多数Acceptor的支持。

“超过半数”是必须的，但仅仅满足“超过半数”还不够，还必须要求：

R1：一个Acceptor最多只能批准一个提议值

换句话说，一个Acceptor不能同时批准两个Proposer提交的不同提议值。分析如下：

因为存在多个Proposer同时向超过半数以上的Acceptor提交取值。假设Acceptor数量为2N+1，有两个Acceptor集合，集合中Acceptor数量相同，都是N+1，显然两个Acceptor集合至少有一个共同的Acceptor，现在有两个Proposer，Proposer 1给其中一个Acceptor集合提交变量取值V1，Proposer2给另一个Acceptor集合提交变量取值V2，如果Acceptor允许同意两个Proposer的变量取值，意味着有两个“超过半数”的Acceptor集合分别同意了两个Proposer的两个值，如果这样的话，这些Acceptor对变量取值没有达成一致。

基于上述分析，如果能确保两个Proposer提交的提议值是相同的，那么Acceptor对变量取值也能达成一致。xiany地R1要求可降级为：

R2：一个Acceptor可以批准多个提议，但必须保证这些提议值是相同。

问题是如何确保两个Proposer提交的提议值能够相同，可参考3.4小节分析。

3.2.2 两阶段提交

在单Acceptor情况下只需要“一阶段提交”即可。然而在分布式系统中，一个节点并不知道其它节点的操作是成功还是失败，即Acceptor互相不知道对方的操作状态（当然，Acceptor之间也可以进行通信以互相知晓，但这会极大增加协议交互的复杂度），如果没有一个独立于Acceptor之外的进程进行协调，提议到底有没有被多数Acceptor批准是无从获知的，Proposer扮演的就是协调者的角色。

即使有Proposer作为协调者，“一阶段提交”仍然不可行。“一阶段提交”是指Proposer和Acceptor之间最多只有一次交互（一个请求和对应的响应）：即Proposer直接向Acceptor提交提议值，Acceptor要么同意（同时提交本地操作记录）要么拒绝。因为Acceptor不知道其他Acceptor是同意还是拒绝，是否有超过半数Acceptor同意只有Proposer收到Acceptor响应时才知道，所以很有可能出现这种情况：大多数Acceptor拒绝了Proposer的取值，只有剩下不到一半Acceptor同意，很显然这些Acceptor在变量取值上没有达成一致，可是同意变量取值的Acceptor却已更新了自己的操作记录，如果要这些Acceptor进行回滚，还得Proposer进一步去通知，这不但增加了协议交互（就不只一个阶段了），而且协议这样设计也不是很合理。

图1 两阶段提交状态转换

如图1所示，“两阶段提交”是在“一阶段提交”基础上引入一个中间状态“Prepared”，目的在于：让Acceptor的多数派都进入Accepted状态或Aborted状态。“两阶段提交”的大致含义是：Proposer首先需要征询多数Acceptor的意见，即“是否同意我的提议”，并根据回复消息统计同意的Acceptor数量，只有超过半数Acceptor同意，Proposer才可以继续向多数Acceptor提交变量取值。

3.3 单Proposer

图2 单Proposer模式下的两阶段提交

如果只有一个Proposer，那么两阶段提交的设计会相对比较简单，如图2所示：

阶段1（prepare阶段）

1) Proposer向Acceptor多数派（此处为Acceptor1和Acceptor3）发起prepare，携带参数{x=v}，表示变量x取值为v。整个消息用prepare{x=v}表示，下同。

2) Acceptor收到prepare消息后，执行本机操作（比如将x=v写入本地日志），成功则返回Yes，失败则返回No。

阶段2（accept阶段）

3) Proposer收集Acceptor返回的消息，发现回复Yes的Acceptor超过半数，于是接着向Acceptor多数派发送accept消息，以请求接受本次变量取值。

4) 如果Proposer统计发现回复Yes的Acceptor未超过半数，那么它不会继续发送accept请求。

prepare阶段目的是为了形成多数派（即得到多数Acceptor的支持），从而在accept阶段Acceptor可以放心批准Proposer提交的提议（不必担心因为没有形成多数派而进行回滚）。

3.4 多Proposer

单Proposer不仅存在单点故障的风险，而且系统性能也会受到限制：因为所有客户端的请求都只能通过一个Proposer发起。

以下是优化Proposer单点故障的两种方案：

1) 主备方案：一旦主Proposer宕机，立即启备Proposer

2) 多副本方案：多个Proposer同时提供服务

Paxos采用第 2) 种方案。

多Proposer情况下每个Proposer都可以提议，如果同时有几个Proposer提出几个不同的提议，很可能出现每个Acceptor都批准一个提议但是没有一个提议被Acceptor多数派批准的情况。相当于几个Proposer“瓜分”了Acceptors的“投票”。这意味着，多个Proposer同时提议的情况下，要形成一个多数派将无法保证。

如果允许Proposer从Acceptor手里“抢占”别人的“投票”，将有助于形成一个多数派来支持自己的提议，Paxos采用了“抢占”策略，但“抢占”也得遵守规则，抢占规则的制定需要在两个关键问题上做选择。

首先，是否获得了“多数派”支持只有Proposer自己知道，其它Proposer是不知道的（理论上Proposer直接通过协商也能够知道，但这会增加协议交互的复杂度），所以没有获得“多数派”支持的Proposer仍然会继续“抢占”。那么第一个问题就是：一旦某个Acceptor进入accept阶段并批准了某个提议值，该Acceptor是否还要同意新的prepare请求呢？答案是肯定的。因为在crash失效模型和异步网络环境下，进程会crash，消息会丢失。也就是说，获得多数派支持的Proposer在继续发accept请求给Acceptor过程中可能会crash，Acceptor可能会crash，accept请求消息在网络传输过程可能会丢失，这些异常情况的发生最终导致只有部分Acceptor甚至没有一个Acceptor收到accept请求，从而影响算法进展。所以要允许新的Proposer形成多数派，只要“后继有人”，就不用担心异常情况阻止算法进展。

更进一步地有第二个问题：如果先前已有Proposer发起accept请求并携带了提议值，并获得若干Acceptor的批准，这个时候如果有新的Proposer获得多数派支持并发起accept请求，那么是否允许该Proposer“推翻”前者的提议值而提出自己的提议值，答案是不允许。理由也很简单：如果Proposer不认同前面Proposer（提交的提议值），那么它（提交的提议值）也不会被更后面的Proposer认同，如此下去，大家提交的提议值都不一样，很难达成一致。

Paxos采用的就是“后者认同前者（而不是推翻）”的策略，为了支持该策略，对两阶段协议作出相应调整：

如果Acceptor之前有收到Proposer在accept请求消息中提交的提议值，那么对于新的Proposer发过来的prepare请求，需要在回复promise消息时把该提议值带上；没有则不要。

Proposer判断promise消息，如果已有提议值，那么应该“认同”该提议值，并在accept请求中提交该提议值（意思是就不要“另起炉灶”了）

“后者认同前者”的意义在于：因为Acceptor批准什么取决于Proposer提交了什么，如果Proposer提交的值都不同，那么Acceptor将不可能批准相同的提议。反之，如果能确保不同Proposer提交的提议都能相同，那么Acceptor批准的提议自然也就相同。

3.4.1 抢占

“抢占”的直观理解就是用新的（prepare请求）代替旧的（prepare请求），对应到Acceptor的处理就是：Acceptor在收到“新的”提议权申请后，可以让之前“旧的”提议权失效，并不再接收旧Proposer的accept请求。prepare请求的“新旧”可以用一个全局单调递增的编号n区分，编号越大表示请求越新。

prepare阶段是为了形成多数派，prepare请求并不需要携带变量取值（带了也没用处），所以，prepare请求消息主要参数就是一个编号。

图3 “抢占”示例

图3是“抢占”的一个示例， Proposer1编号为n1的请求首先获得Acceptor的同意，但是被Proposer编号为n2的请求抢占，导致Proposer1之后发给Acceptor的accept请求(5号消息)被拒绝。“抢占”可以相互交替。Proposer2继而发起编号为n3的请求，“抢占”了Proposer2编号为n2的请求，导致Proposer发给Acceptor的accept请求（10号消息）被拒绝。最后，Proposer1编号为n3的accept请求（携带变量取值v1）获得批准。

“抢占”可能会造成活锁。Proposer1被Proposer2抢占，Proposer1重新发起请求抢占Proposer2，Proposer2被抢占后由发起请求抢占Proposer1……如此循环。

3.4.2 完整算法

多Proposer、多Acceptor情况下，完整的两阶段算法执行过程如下：

阶段1：prepare阶段

1) Proposer向Acceptors发起prepare{n}请求，以获取多数派的支持

2) Acceptor收到并处理prepare{n}请求：

        2.1) 如果编号n大于之前收到的请求编号，它首先让编号小于n的请求失效，且不再接收它们的accept请求，同时批准本次编号为n的请求，并回复promise{ok，Value}，以承诺不再接受编号小于n的请求。

                2.1.1）如果Acceptor之前从未收到任何accept消息，那么在构造Promise消息时参数{Value}值设为NULL，表示变量还没有提议值

                2.1.2）如果Acceptor之前已收到过一个或多个accept{i,V}消息，Acceptor选取编号最大的accept消息，并将其中V作为promise消息{V}的值，表示已有提议值

        2.2) 如果编号n小于Acceptor小于之前收到的请求编号，Acceptor将忽略该请求

3) Proposer接收并统计promise{ok}消息：

        3.1) 如果同意的Acceptor超过半数，意味着形成了多数派，结束prepare阶段，进入accept阶段

        3.2) 如果同意的Acceptor没有超过半数，意味着没有形成多数派，只能再来，即Proposer重新发起更大编号的prepare请求

阶段2：accept阶段

1) 获得多数派支持的Proposer进一步向Acceptor发起accept{n, V}请求，以提交变量取值

        1.1) 如果Proposer在第一阶段收到的所有promise{V}中V都为NULL，那么Proposer可以提交自己的提议值，设置accept{n, V}消息中V为自己的提议值

        1.2) 如果这些promise{V}中存在V不为NULL，那么基于后者认同前者的原则，选取编号最大的promise消息中的V_Max_n，将accept{n, V}消息中V设为Promise{V}中的V_Max_n

2) Acceptor接收并处理accept{n, V}请求：如果Acceptor没有批准过编号大于n的提议，那么它将批准本次accept{n, V}请求并回复accepted消息，

4. 总结

理解Paxos算法的挑战之一是同时存在多个Proposer和多个Acceptor的情况下，增加了算法的复杂度。Paxos算法设计有若干关键点，如下：

1) Acceptor多数派

2) “一阶段提交”为何不可行

3) 单Proposer和多Proposer情况下的“两阶段提交”有何不同

4) 多Proposer情况下的如何确保形成多数派（“抢占”策略）

5) “抢占”规则如何制定

本文以直观的方式对这些关键点进行阐述，对理解Paxos算法会起到一定的帮助作用。

参考

[1] Lamport, L. The part-time parliament. ACM Transactions on ComputerSystems 16, 2 (1998), 133–169.

[2] Lamport, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001),18–25.

[3] Lampson, B. W. How to build a highly available systemusing consensus. In 10th International Workshop on Distributed Algorithms (WDAG96) (1996), Babaoglu and Marzullo, Eds., vol. 1151, Springer-Verlag,BerlinGermany, pp. 1–17.

[4] Michael J Fisher. Nancy A Lynch. Michael S Paterson. Impossibilityof distributed consensus with one faulty process

[5] Prisco, R. D., Lampson, B. W., and Lynch, N. A.Revisiting the paxos algorithm. In 11th International Workshop on DistributedAlgorithms (WDAG 96) (1997), pp. 111–125.

[6] Tushar Chandra, Robert Griesemer, Joshua Redstone.Paxos Made Live - An Engineering Perspective. ACM PODC 2007.

[7] LiHaiLei. Paxos和分布式系统. http://www.tudou.com/programs/view/e8zM8dAL6hM/