前言

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

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

1. 基本概念

Paxos算法是Leslie Lamport 于1990年提出的：
一种基于消息传递且具有高度容错的共识（consensus）算法。

• 共识：简单讲大家有很多建议，需要统一意见，达成共识（选出其中一个）
• 消息传递：请求 + 响应，分布式系统中主要基于网络消息进行通信。
• 高度容错：不管是网络消息重复或丢失、还是某一些服务器挂掉了，也不会受到影响。

1.1 少数服从多数

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

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

两个多数派交集

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

多数同意即可选出

1.2 角色

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

• Proposer：提案者，可多个；负责提出提案(proposal)，每个提案中会包含一个值(value)；
• Acceptor：接收者，可多个；可以选择接受（accept） Proposer提出的提案。
  当某个提案被 多数派 所接受后，我们将这个提案称之为被选定（chosen）；当某个提案被选定时，也就意味着value被最终选定。
• Leaner：学习者，可多个；当value被选定后，learner可以学习（获取）并应用这个value。

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

• 一个服务器ID：如 1、2、 3，从这三台服务器中选出一个老大；
• 一条命令：如 set key 1、set key 2，从中选一个执行；
• 一条日志：如 某一个时期有多条日志，选择最终应用的某条日志。日志可包含任何信息。

注：通常一台服务器 或者 一个进程可包含一个或多个角色。

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

1.3 要解决的问题

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

1. 值（value）只有被提出才能被选定；
2. 只会有一个value被选定（共识）；
3. Leaner 只能学习被选定的value。

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

2. Paxos的推导

P1

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

P1：Acceptor 需要接受（accept）其第一次收到的提案。

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

选出V1

P2

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

1. 直接拒绝，即一个Acceptor只能接受（accept）一个提案。
2. 选择接受，即一个Acceptor可以接受（accept）多个提案

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

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

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

P2：一旦一个 value 为 v 的提案被选定（chosen），那么之后选定（chosen）的提案，其value也必须为v。

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

关于分布式系统中的先后顺序，我们可以通过为每个提案分配一个唯一的递增编号，在提案之间建立一个全序关系，这里的“之后”指的就是编号更大的提案。

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

2.3 P2a

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

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

P2a：一旦 提案 <m, v> 被选定，那么之后被Acceptor接受（accept）的提案，其value必须为v。

P2b

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

• 根据P2a：因为已有提案被选定，Acceptor不能再接受这个value不同的提案；
• 根据P1：这个Acceptor则需要接受这个第一次收到的提案的。此时P1和P2a冲突。

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

P2b：一旦 提案 <m, v> 被选定，那么之后任何 Proposer 提出的提案的value必须为v。

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

P2c

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

注：提案<n, v> 之前的提案，其实就是指 编号小于n的提案。

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

P2c：如果要提出提案<n, v>,则Acceptors中的一个多数派S必须满足以下两种情况之一：

• 要么S中均没有接受过小于n的提案；
• 要么这些个小于n的提案中，编号最大的那个提案的值为v。

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

1. S中均没有接受过小于n的提案，此时v没要求，随便提。
2. S中有一些Acceptor接受过小于n的提案，取编号最大（最新）的那个提案的值作为本次提案的值。

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

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

• 如果之前的未被选定，我们偏向于选出最新（编号最大）的提案；
• 如果之前的已被选定，则后面的提案是基于前面最大的，这样可以保证value的"延续"。即一个value被选定后，后面的value均和前面的这个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为P2的一个子集

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

• 第一阶段：Proposer提出Prepare请求（编号n），获取Acceptors中多数派S的接受情况；

• 第二阶段：根据S + P2c选择value；Proposer提出Accept请求（编号n + value），当得到多数Acceptor所接受（accept）后，认为提案被选定。

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

P1a

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

考虑一种情况：

1. 第一阶段时，Proposer通过prepare请求，获取到Acceptor的一个多数派S的接受情况。假设S中均无接受（accept）过任何提案。
2. Proposer基于P2c的第一种情况，提出了自己的提案<n, v>（v为任意值）。
3. 此时集合S中的一个Acceptor收到了一个小于n的提案<n-1, v'>的accept请求：
   • 根据P1，需要accept，因为是第一次收到提案。
   • 根据P2c，不能accept，因为一旦接受，Proposer收到集合S就遭到破坏，P2c就违背了。

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

P1a：只有Acceptor没有回应过编号大于n的prepare请求时，才能接受（accept）编号为n的提案。

关于Prepare请求的一个小优化

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

1. 假设一个Acceptor收到了一个编号为 N 的Prepare请求，并做出了正常响应。根据P1a，该Acceptor不能再接受（accept）任何小于 N 的提案。
2. 当该Acceptor在收到小于 N 的Prepare请求时，是可以选择直接忽略该Prepare请求的，因为就算Prepare放行，到了第二阶段该Acceptor也不会接受的。这样可以尽可能提高第二阶段过半数接受（accept）的成功率。

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

1. 已经接受（accept）的最大提案（<max_accepted_id, max_accepted_value>）；
2. 已经正常响应Prepare请求的最大编号(max_prepared_id）。

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

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

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

3. Paxos完整算法

3.1 算法陈述

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

1. max_prepared_id：Acceptor 已经正常响应Prepare请求的最大提案编号
2. <max_accepted_id, max_accepted_value>：Acceptor 已经接受（accept）的最大提案

阶段一（Prepare请求）：

1. Proposer：生成提案编号N，然后向Acceptors多数派发送Prepare请求（含编号N）；
2. Acceptor：收到编号为N的Prepare请求，如果N大于 max_prepared_id，则：
   • max_prepared_id更新为N；承诺不再接受（accept）编号小于N的提案；
   • 将 <max_accepted_id, max_accepted_value>响应给Proposer；

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

阶段二（Accept请求）：

1. Proposer：选择其中编号最大的提案value作为本次提案的value（如果没有则自由定义值），向Acceptors多数派发送Accept请求（含编号N和value）；
2. Acceptor：收到提案<N, value> 的Accept请求，如果N大于或等于 max_prepared_id，则：
   • <max_accepted_id, max_accepted_value>更新为 <N, value>；
   • 正常响应Proposer，表示该提案已被接受（Accept）

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

3.2 全局递增的唯一编号

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

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

1. 时间戳 + Proposer的IP端口的hash值；
2. 时间戳 + 分配到某个Proposer的ID（如：0、1、2）。

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

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

1. 确定一个编号生成算法，算法需要保证各个机器不会生成重复的编号：
   如：【M * Proposer数量 + Proposer ID】；初始时，M = 0；
2. 当Acceptor响应拒绝时，把当前自己当前的max_prepared_id也带上；
3. 当Proposer收不到超半数的成功响应信息、需要生成新的编号时：从所有拒绝信息中，获取其中最大的提案id，然后根据生成算法，生成一个比这个更大的新编号即可。
   如Proposer数量=3，当前Proposer ID = 2；某个Proposer收到了拒绝信息中提案id包含 [1, 3, 7]，此时只要M = 2 时，即可获取到 2 * 3 + 2 = 8 ( >7) 的编号。

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

3.3 活锁-永远选不出值

假设有两个Proposer，一个Acceptor：

1. P0发起prepare(0)，Acceptor收到，max_prepared_id更新为0，响应pok；
2. P1发起prepare(1)，Acceptor收到，max_prepared_id更新为1，响应pok；
3. P0发起accept(0,v)，Acceptor收到，发现小于当前的max_prepared_id(1)，拒绝；
4. P0生成更大提案编号2，发起prepare(2)，Acceptor收到，max_prepared_id更新为2，响应pok；
5. P1发起accept(1,v)，Acceptor收到，发现小于当前的max_prepared_id(2)，拒绝；
6. P1生成更大提案编号3，发起prepare(3)...

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

解决方案主要有两种：

1. Proposer重新发起Prepare前，随机等待一段时间。因为每个Proposer等待的时间不一样，等待时间短的会有较大的几率被最终选出。
2. 将Proposer数量定为一个。提案者只有一个，没有争抢，自然不会有活锁了。这个其实就是我们常说的Leader。

值得一提的是，当只有一个Proposer时（即Leader），第一阶段的Prepare是可以省略的，这将会带来较大的性能提升。另外编号生成、value应用的顺序性等实现会相对方便。Multi-Paxos、Raft等衍生的协议均有Leader的概念。

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

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

参考资料

• Paxos Made Simple
• Implementing Replicated Logswith Paxos
• 维基百科-Paxos算法
• 《从Paxos到Zookeeper 分布式一致性原理与实践》