逐步了解Paxos

Lamport老爷子的那篇 《Paxos Made Simple》 论述实在太跳脱，像极了高数答案中的“显然”，“易证”一般，以致于刚开始了解Paxos的人看得一脸懵逼。

本文希望能够通过简单的图文，为大家简单逐步介绍Paxos涉及的相关概念、推导过程、以及算法整体介绍（含编号生成规则、活锁、Leader的引出）等。

小明 一家五口 ，想要春节到某个地方游玩，家里人有不同的建议，如果要选出【一个】游玩的地方，基于投票的“ 少数服从多数 ”是一个比较合理的做法。

“多数”意味着超过一半，两个“多数”之间肯定会有交集 。比如[小明, 爸爸, 妈妈] 是一个多数派，[小明, 爷爷, 奶奶]也是一个多数派 。此时这两个多数派之间的交集就是小明：

当有一个“多数”均同意去A时，就可以认为结果出来了，因为剩下那些人肯定凑不够一个“多数”：

我们先来了解下共识算法中常涉及到的几个角色：

值（value） 可代表的意思是丰富的，它可以是：

本文主要关注选值的一个过程（主要由Proposer和Acceptor参与），Leaner不做过多介绍。

划分角色后，我们可以定义出算法需要解决或保证的几个点（即安全性-Safety）：

第1、3点显得“理所当然”，实现相对简单。
而第2点【只会有一个value选定】，成为了Paxos最核心要解决的问题。

当Acceptor 第一次收到提案 时，因为没有更多的参考信息，直接接受（accept）是一个很自然的动作。于是我们可以给Acceptor的行为定下这么一个约束：

针对只有一个提案时（暂不考虑消息丢失）的情况，基于P1，一个value可以被轻松选出：

当有多个提案时，基于P1，当Acceptor收到 第二个 提案时，Acceptor可以选择：

当 只能接受（accept）一个提案时 ：如果恰好一半 Acceptor 接受（accept）的提案具有 value v1，另一半接受的提案具有 value v2，将无法形成多数派，即无法选出任何一个 value：

如果 只能接受一个 提案无法达成多数派选出value的话，那么我们可以尝试 一个Acceptor可以接受（accept）多个提案 。
可如果 一个Acceptor可以接受多个提案 的话，不是会出现 多个提案被选定 吗？如下图：

当这些个提案的value不一样时，最终就会出现多个value被选出 ，这不是我们所期望的。
于是我们二话不说，定下这么一个约束P2：

尽管可以通过多个提案，但是因为 后面提案的value和之前选定的一样 ，自然可以保证 最终【只会有一个value选出】 。

我们这里用 <编号, value>来表示一个提案。
当v1 = v2时，尽管<m1, v1> 和 <m2, v2> 两个提案都被选定，但因为他们的value是一样的，最终依然是【只会有一个value选出】，这是符合我们预期的。

P2只是一个简单的描述，像是老板交到我们手上的需求，真正的可以落地的方案还是得继续分析分析。这里的落地指的是 Proposer、Acceptor的具体行为是什么 ，或者说他们该怎么干才能保证只选出一个值。

提案被选定，意味着有多个Acceptor接受了该提案。于是可以针对 Acceptor的行为 进行约束：

由于通信是异步的， 一个提案被选定（chosen）时，可能会有Acceptor还没收到过任何提案 。如果此时有一个Proposer往这个Acceptor发出另外一个不同value的提案时：

解决这个问题很简单，从源头抓起：当提出提案m2时，只要保证[ v2 = v1 ] 即可。
于是我们转向约束Proposer的行为：

虽然<m1,v1> 和 <m2, v2>都被选定，但因为他们的value是一样的，最终依然是【只会有一个value选出】。

可以看到，P2b对Proposer新提案的要求，其实都是 基于之前的提案 来的： 之前有提案选定（chosen）了，则需要提出相同的value。否则，新提案的value没什么要求，可以任意值 。

基于P2b，我们可以提出对Proposer的行为做出完整的约束（无论之前的提案选定与否）：

换一种描述，本次提案<n, v> 中的 value v，是根据Acceptors中的一个多数派S来决定的 ：

第一种情况：【S中均没有接受过小于n的提案】
这表明 之前的提案中，没有已经被选定的 。这是显然易见的：如果之前有提案已经被选定，那Acceptors中必然有一个多数派C是 全部都接受 （accept）该提案的了。S和C两个多数派之间肯定有交集。 此时提案的value可以为任意值 ，如直接提出<m1,v1>。

第二种情况：【S中有一些Acceptor接受过小于n的提案】
如果之前的提案已经有被accept了，说明这些个提案 有可能 已经被选定（chosen）了，比较安全且符合预期（P2b）的办法，就是直接基于这些提案的value提出自己的提案。之所以 取编号最大的值 ：

举个例子： 基于<m1,v1>已提出 （可能被选定或 未被选定）。
当 <m2,v2> 想要提出时，主要分以下几种情形：

基于 <m1, v1> 已选定，<m2,v2>已提出 ：
当 <m3,v3> 想要提出时，显然属于P2c的第二种情况，我们看看多数派S的不同情形：

同理，基于<m1, v1> 已选定，当 m4,m5... 提出时，其提案的Value也会为v1，从而最终选出的value为v1。

当然，当m2以任意值v2提出时，<m2, v2>也有可能走在<m1,v1>前面，最先成为被chosen的提案，后续的提案自然基于v2来进行了，最终选出的value为v2.

可以看到，满足P2c后，便可以保证P2b；而保证P2b，就能保证P2a、P2；
即：P2c ⇒ P2b ⇒ P2a ⇒ P2：

基于P2c，我们已经可以看到Paxos的雏形了，主要包括两个阶段：

Proposer行为已经基本完备，我们下面再看下Acceptor怎么“接”这些prepare/accept请求。

回顾P1中对Acceptor的行为约束：【Acceptor 需要接受（accept）其第一次收到的提案】。

考虑一种情况：

P1和P2c冲突，因此我们要增强对Acceptor的行为约束： 当Acceptor正常响应编号为n的prepare请求时也应作出 承诺 ： 不会再接受（accept）那些编号小于n的提案 ，从而保证集合S一直都是正确的。即约束P1a：

基于P1a + P2c，完整Paxos算法已经基本成型.
这里再提一个关于Acceptor对Prepare请求的小优化，即尽可能忽略Prepare请求：

另外忽略这样的Prepare请求还有个好处，就是Acceptor仅需要保存：

对于 之前已经接受 （accept）的提案，就 没有记录的必要 了，因为Acceptor会直接忽略小于 max_prepared_id 的Prepare请求。

如果不忽略，则需要找到小于Prepare请求编号 且 已经接受（accept）的最大编号的提案（用于服务P2c），相应地Acceptor需要记录之前接受（accept）过的所有提案。

至此，完整的Paxos算法呼之欲出。

先约定Acceptor需要保存信息的命名：

阶段一（Prepare请求） ：

当Proposer收到Acceptors超半数的Prepare正常（成功）的响应后：进行阶段二；
如果收不到超半数的正常响应，则生成新的编号，则重新进行阶段一。

阶段二（Accept请求） ：

当Proposer收到Acceptors超半数的Accept正常（成功）响应后：该提案被选定。
如果收不到超半数的正常响应，则生成新的编号，重新进行阶段一。

在不依赖中间件的前提下，生成一个全局唯一的递增序号其实并不复杂。

比如可以通过 时间戳 + 各个Proposer的标识 生成，如：

生成提案编号时，只要获取本机器当前的时间戳，再拼上Proposer的区分标识即可。 前提是各个机器之间的时间是一致的 。当然了，短暂的时间不一致通常不会造成非常恶劣的后果。

还有一些不依赖时间的，可以通过【相对更大】的一种方式生成的（如Google的Chubby）：

这种编号的生成类似于拍卖的叫价，在前一个叫价的基础上，新叫价会高一点。

假设有两个Proposer，一个Acceptor：

此时就出现了活锁。 这个锁可能会解除；也有可能一直都在循环 。

解决方案主要有两种：

使用Leader的前提是：要选出一个Leader。选Leader这个操作如果使用Paxos算法实现的话，多个服务器争抢Leader，其实就是相当于有多个Proposer存在了，这时只能使用第一种解决方案处理了。

工程实现上，Proposer往往并不是完全公平的，所以Leader选举方式通常会根据具体场景决定。
有些衍生协议（以Raft为例）为了简化场景，单纯使用 随机等待 + Acceptor只能接受一个提案的方式（即上文推导中的P1）来进行Leader选举也是可行的，只是有可能出现上文中提到的，V1和V2可能都无法获取多数票，这时会选择再各等一个随机时间，然后进行下一轮选举。