分布式一致性之Paxos

Paxos追本溯源

Paxos是分布式专家Leslie Lamport的大作，他在分布式一致性领域做出了很多突出的贡献。Lamport最初在研究拜占庭将军问题，从理论上证明了在分布式领域，试图在异步和不可靠的通道上达成一致的状态是不可能的。而事实上，这种信道问题可以是不存在的或者说是可以避免的。于是Lamport基于此提出了Paxos，证明在信道可靠并且不要求liveness的情况下是可以达到分布式一致的。下面我们便来看看Paxos到底是什么。

Paxos问题描述

假设有一个进程集合，这些进程都能够提出自己决议，而且每个进程提出的决议有可能是不同的，在这种情况下Paxos算法要在众多的决议中给出唯一的选择。要达到Paxos所说的安全性，需要满足如下几个条件：1）只有被提议的值才能被选中；2）最终只有一个唯一值能被选中；3）在最终被决议前，任何参与者都不能获得决议结果。

试想你在参加一次会议，大家就某个问题确定一个最终方案，一般会怎么做？首先肯定要有人提出方案，参会者听到方案后经过大脑的处理并分析利弊，于是做出自己的判断接受或者不接受这个方案。当然其他参会者如果不同意也可以提出自己的方案，最终大家经过讨论，一致通过某个方案。这样一个简单的决议中，存在着三种角色：提议者、决议者、学习者，在Paxos算法中也同样对应着这三种角色，分别为proposer, acceptor, learner，当然每个人都可以身兼多个角色，但是为了方便问题的讨论Paxos还是把他们区分开来。

Paxos角色关系

下面我们就来看看Paxos算法是如何保证一个提议是最终被选择的。

Paxos推导过程

当acceptor只有一个的时候问题会变得很简单，它只要接受收到的proposal就可以，但我们还需要考虑可用性，所以一般都会有多个acceptor。在有多个acceptor的情况下怎样算通过决议呢，难道真的要所有的acceptor都统一战线才算成功吗？这里就要提到多数派（majority）特性，Paxos只要多数派接受了提议这个提议便被接受了，然后learner可以通过主动或者被动的方式获取投票的结果。Lamport在他的论文Paxos made simple中给出了算法的推导过程，我们现在来看看他是如何推导的。

通常情况下考虑到消息丢失或者发送失败等情况，我们希望acceptor能够在proposer只提出了一个proposal的情况下依然能正常工作，很自然的可以给出第一个保证：

P1. acceptor必须接受它收到的第一个proposal。

给出第一个保证的同时也带来了问题，不同的proposer同时提出了不同的提议，但是由于消息的到达顺序不一样导致不同的acceptor接受了不同的proposal，于是无法形成多数派，也就是说无法给出最终的决议，这就要求acceptor可以变更自己的选择，proposer不停的提出决议直到acceptor多数派达成一致。

无法形成多数派的情况

为了能最终达到统一的结果，需要给出第二个保证：

P2. 假如提议值v被选中，接下来更大编号的提议被选中，被选中的值也一定是v。

换个视角从proposer的角度去看，于是我们可以通过P2a来满足P2：

P2a. 假如提议值为v的某个提议被选中，那么被接受的更大编号的提议的值也一定是v。

我们的分布式系统是基于消息传递的，并且都是异步的会存在消息都是或者延迟，假设acceptor c由于以上提到的某种原因没有收到提议。这时一个新的proposer被唤醒并发出更大编号的提议，它的值与之前的提议都不同。回顾之前的保证P1,  c会接受它收到的第一个提议。这种情况就违背了P2a的保证。

在P2a保证下无法达到一致的情况

怎么办才能既保证P2a同时又不违背P1呢，我们可以进一步加强条件：

P2b. 假如提议值为v的某个提议被选中，那么proposer提出的更大编号的提议的值都必须是v。

P2b看似合理，但并好实现，我们在这里不试图去证明P2b的合理性，感兴趣的读者可以参考Lamport的大作Paxos made simple。通过证明过程，更进一步提出下面的保证：

P2c. 对于任意提议，它的编号是n，提议值是v，肯定存在由半数以上acceptor组成的集合S满足以下两个条件中任意一个 （1）S中不存在任何批准过编号小于n的提案的acceptor，（2）选取S中所有acceptor批准的编号小于n的提案，其中编号最大的那个提议的值。

满足P2c，proposer就要知道比n小的最大编号的提议。获取已经被大多数通过的决议比较容易，预测未来可能被接受的决议却很困难。避免以上的困难，只要acceptor保证不接受任何编号比n小的提议就够了，接下来我们来看看这个Paxos算法的过程。

Paxos算法描述

阶段一，prepare请求

1. proposer选择提议编号n，然后向超过半数的acceptor发送编号为n的prepare请求。

2. 如果acceptor收到编号为n的请求，且编号大于已经响应的所有prepare请求的编号，那么它就会将批准过的最大编号的提议反馈给proposer，同时acceptor承诺不会再批准任何编号小于n的提案。

阶段二，accept请求

1. 如果proposer收到大多数acceptor的响应，它就会发送一个针对编号n值为v的提议，v就是收到的响应中编号最大的提议的值；如果响应中不包含任何提议，那么它就是任意值。

2. acceptor收到编号为n的提议，如果尚未对编号比n大的prepare请求作出过响应，它就可以通过这个提议。

具体详细流程如下图所示：

Paxos算法

值得一提的是acceptor需要持久化minProposal，acceptedProposal和acceptedValue，这样在宕机恢复的时候能够保证自己状态的一致性。

写在最后

分布式一致性的实现方式可以有千万种，但是Paxos在保证系统高可用的情况下选择了一条捷径，使得分布式系统可以既安全又快速的达成一致，这就是它的伟大之处，也是它的作者Lamport对人类和分布式领域的巨大贡献。