分布式一致性Paxos算法学习笔记(四):算法回顾

这段时间一直在赶论文，唉，真是昏天黑地……… 在写论文的时候居然把Paxos算法里的提案和决议搞混了！赶紧看blog里是不是也弄错了，还好之前的几篇都没错，这才松了口气。所以决定第四篇笔记对Paxos算法做个回顾。

1.  几个重要的概念

实例(instance)：每一个Paxos的实例都将执行Paxos算法的两个阶段过程，并最终选出唯一的决议(value)。

提案(proposal)：未经批准的决议称为提案，由于在Paxos算法中，每一个Proposer在一个没有关闭(closed，即还没最终选出决议)的实例中都可以提出自己的提案，因此在一个实例的执行过程中，可能会出现多个提案。而最终只能有一个提案被批准通过，成为该实例的决议(value)。

决议(value)：被最终批准通过的提案中的value称为决议，一个Paxos实例只能选出一个决议。决议和实例是一一对应的。

2.  两阶段过程

paxos的两阶段过程就不再描述了，有图有真相！如下图：

3.   各角色的行为描述

Learner行为描述：

learner的主要任务就是监听来自acceptors的消息，用以最终确认并学习决议(value)，即被批准的提案。当learner收到来自大多数(majority)acceptors的接受消息后，就可以确定该实例(instance)的value已经被最终无歧义的确认。这个时候便可以执行决议里的操作。

决议序列在所有learner上顺序都是一致的，每一个提案的发起将会触发一次Paxos过程，每个这样的过程是一个Paxos的实例。而在实际应用中常使用单增的整数来标识每一个实例，即iid(instance id)。iid从1开始，而所有从1开始到当前iid的实例都必须是已经被确认过的，即这些决议都已经被执行过。比如：learner A已经确认了前10个实例，这时iid为11的决议还没有被通过，而iid为12和13的提案已经得到大多数acceptors的接受。此时就会产生一个决议序列缺口(gap)，在这种情况下，A不能跳过11直接确认12和13，而是去询问acceptors是否已经通过11的决议。只有当iid为11的决议被确认后，iid为12和13的决议才能被确认学习。

Acceptor行为描述：

acceptor会维护一个状态记录表，表的每一行维护这样四个数据, iid表示实例id。B是一个整数，用来表示同意或接受过的该提案的最高编号。V表示该提案对应的决议，里面保存着客户端发送过来的数据。VB表示已经接受过的提案的编号。

(Phase 1.b) 接收Prepare(i，b)消息，i为实例id号，b为提案编号。对于同一个i，如果b>B，那么回复Promise(i, b, V, VB)，并设B=b；否则，回复Reject(i，b)，其中b=B。

(Phase 2.b) 接收Accept(i, b, v)，如果b

其中：Promise(i, b, V, VB)表示向proposer保证对于该实例不再接受编号不大于b的相同iid的提案；Accepted表示向learner和proposer发送该提案被通过的消息。

Proposer行为描述：

(Phase1.a) 向所有的acceptors发送Prepare(i, b)请求；

(Phase2.a) 如果收到Reject(i，b)消息，那么重新发送Prepare(i，b+n)，n为一个整型值，不同的proposer具有不同的n值，使得proposer之间保持一个偏序关系，保证不同的proposer不会使用相同的b值，即提案编号；

(Phase2.a) 如果收到acceptors集合的任意一个majority的Promise(i, b, V, VB)回复，那么如果所有的V均为空，proposer可以自由选取一个v(value)，一般为用户提出的请求，回发Accept(i, b, v)；否则回发Accept(i，b，V)；

(Phase2.b) 如果收到Nack(b)，回到(Phase1.a)发送Prepare(i，b+n)；

(Phase2.b) 如果收到任意一个majority所有成员的Accepted(i，b，v)消息(表明投票已经完成)。这个过程learner也能收到Accepted消息，learner查看i是否为当前需要确认的iid，如果是则立即执行这个被批准的决议v；否则将该Accepted保存下来。

Phase2.b阶段完成后，各个角色上对应该实例的状态都将变为closed状态，即该实例已经选出决议，proposer不能再提出新的提案。这样保证一个实例只能选出一个决议。在实际应用过程中，为了简化实现，常常在proposers中选举出一个leader，来充当协调者。当leader选举出来后，系统中只能由leader向acceptors发出Prepare请求，也就是说这能由leader发起提案，而其它的proposers则只干一件事，即定时检测系统中的leader是否还在工作，如果在一定时间内收不到leader的心跳消息，则剩下的proposers发起新一轮leader竞选，选取新的leader。

4.  算法运行实例

考虑下面两种异常情况发生时，paxos算法是否还能保持一致性。虽然是“有图有真相”但实在太难画了，还是用文字描述吧。

异常情况一：

系统中只有一个客户(client)称为C，两个proposers分别为P1和P2，三个acceptors分别为A1，A2和A3，以及三个learner分别为L1，L2和L3。初始化时默认P1为leader。

C发送请求v到当前的leader，即P1。

Phase 1a：P1发送实例id为1，决议编号(b)为101的Prepare消息，即Prepare(1，101)。由于网络问题，该消息丢失，P1没有收到任何acceptors的Promise消息。因此P1将决议编号增加到201，重新发送Prepare消息，Prepare(1，201)。

Phase 1b：三个acceptor相继收到Prepare消息，由于编号201是acceptors接收到的实例1的最高的提案编号，因此acceptors更新自己的状态保存相应信息后发送Promise(1，201，NULL)。NULL表明实例1之前没有收到任何提案。

Phase 2a：proposer收到来自A1、A3的Promise消息，并发现没有value被提出，于是选用client发来的请求v1作为value，以201做编号想acceptors发送Accept(i，201，v1)消息。

Phase 2b：此时acceptors并没有接受到实例1的比201更高编号的提案，因此接受Accept消息。在更新自己的状态后，向所有的learner发送Accepted(i，201，v1)消息，表示批准v1成为实例1的决议，决议编号最终确定为201。当learner接收到来自一个majority(大多数)的acceptors的Accepted消息后，确认实例1的决议已经被最终批准，立即学习决议的内容v1，完成client的请求。这个Accepted消息同时也将被P1、P2和C接收到。如果第二阶段(Phase 2)在一定的超时时间内没有完成，即没有收到Accepted消息，则P1将从Phase 1开始使用301作为提案编号再次发送Prepare消息。

异常情况二：

讨论一种更复杂的情况：系统中有两个proposers分别是P1和P2，三个acceptors分别为A1、A2和A3，一个客户C。C、P1和P2为了接收到accepted消息分别启动LC、L1和L2。

当前系统中P1被选为leader，在系统运行一段时间后，paxos实例已经成功的运行了i-1次，也就是说已有i-1个决议被批准。此时，P1已经成功的执行了实例i的Phase1(阶段一)，已经发送带有C提交的Vi请求的Accept消息。A1、A2收到有效的Accept消息，接受该请求后更新了自己的状态。这个时候请求Vi已经被唯一选定做为实例i的决议，因为已经有一个majority的acceptors批准Vi。但就在A1、A2批准Vi后很短的时间里(没有来得及发Accepted消息)，A1、A2相继崩溃。同时更糟的是P1也由于网络错误变得不可用，而A3也没有收到P1的Accept消息，虽然它还能正常运行，当完全不知道系统发生了什么。A3上的实例i还处于初始状态，没有任何提案。

经过一段时间后，P2获得接管权成为leader，由于P2运行在一个leaner上，因此知道前i-1次实例都已经关闭。P2发起实例i的Phase1，但此时系统中并没有足够的acceptors去响应这个Prepare消息，P2只能在每一个超时时间过去后增加提案的编号重新发送Prepare消息。又过了一段时间，A1恢复，这样系统里有足够的acceptors(majority形成)。A1和A3回复Prepare消息，从A1的Promise消息中P2知道实例i曾经有一个value值为Vi提案，此时根据提案选取原则(picking a value)P2必须选取Vi作为提案的内容，发起阶段二(Phase2)，发送Accept(i，b，Vi)消息。A1和A3批准该Accept消息，将其记录下来后发送Accepted(i，b，Vi)给learners，这样一来Vi将被最终确认为实例i的决议。

这个例子可以看出，不管多么恶劣的场景，Paxos算法也能保证一点：只要任意一个majority的acceptors批准该实例的决议后，该实例将变成关闭(closed)状态。也就是说不管多么恶劣的情况发生，Paxos算法都能做到一个实例只可能选出一个对应的决议。这有力的保证了一致性的第二点要求(在一次 Paxos 算法的执行实例中，只批准一个 Value)。

5.  后续：“分布式一致性Paxos算法学习笔记（五）：libpaxos源码分析及跨平台移植”

libpaxos是SourceForge上paxos算法的开源代码，以动静态库的方式提供。作者Marco对这个项目也比较用心，写了好几篇测试性能的论文，毕业设计也是以libpaxos为题材，还是值得一看的。

References：

[1]Marco Primi. Paxos made code Implementing a high throughput AtomicBroadcast. 2009.5