导语:

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其他算法都是残次品。

引子：

一支白军和三支蓝军在山谷中的不同位置驻扎，只有当两支以上的蓝军同时进攻白军的时候，才可获得胜利，蓝军之间通过通信兵传递进攻时间，将军批准后方可进攻。

但是通信兵为了避免被俘虏，可能在山谷逗留或者也可能出现意外（被击杀等）。那么是否存在一个协议，能使蓝军同步他们的进攻时间？

拜占庭将军问题

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。

那么我们的这个协议的前置条件一定是不存在拜占庭将军问题，也就是我们的通信兵不会叛变从而左右战争的局势。

paxos的诞生

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos作为比喻，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。

三种角色

交互过程

交互时序图

basic paxos

1.获取一个Proposal ID n，为了保证Proposal ID唯一，可采用时间戳+Server ID生成；

2.Proposer向所有Acceptors广播Prepare(n)请求；

3.Acceptor比较n和minProposal，如果n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；

4.Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value

 z；

5.到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；

6.Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal。

7.提议者接收到过半数请求后，如果发现有返回值result >n，表示有更新的提议，跳转到1；否则value达成一致。

注：

minProposal ： 最小的 Proposal ld接收到但是未accept的 Proposal id，如果是0表示未接收到任何 Proposal request

正常的三军问题

参谋1提出一个Prepare请求，三位将军收到提案后，进行了响应，因为之前没有接受过其他的提案，三位将军返回null，OK即可。

参谋1收到超过半数响应后，进入第二阶段，发送accept请求（包含提案编号、提案值-进攻时间），三位将军之前没有遇到其他提案，会接受这个值Accepted，提案达成了。

参谋2再提出一个Prepare请求，编号2，但三位将军已经接受过之前编号1的提案了，会将提案号和已经接受过的内容 返回给参谋2

这里参谋2收到多数响应，还会发送accept请求（编号2）。之前接受者已经接受过值了。那么这里的值，是所有接受者返回过来（进攻时间1）

异常的三军问题

参谋1提出一个Prepare请求（编号1），将军1和将军2收到提案后，进行了响应，但到将军3的通讯中断了（通讯兵被俘虏），但参谋1收到超过半数响应后，进入Accept阶段。

这时参谋2也提出一个Prepare请求（编号2），将军2和将军3收到提案后，但到将军1的通讯中断了（通讯兵被俘虏）没有收到，将军2会承诺不再接受比编号2小的提案了，注意将军2这时没有接受提案内容。将军2和将军3也构成了相应的多数派，参谋2进入Accept阶段。

参谋1发送accept请求，将军1没有什么问题，接受了提案的值，但将军2刚才已经接受了编号2的提案，不能再接受比2小的编号1提案，给拒绝了。有人拒绝，那么提案者就需要放弃这一轮的提案，重新再来。

参谋2也发送accept请求，指定编号2，进攻时间2，将军2和将军3之前都没有接受过值，便接受了提案的进攻时间2，满足了多数派，达成了一致

参谋1之前传达失败，重新提出Prepare请求（编号3）。将军1已经接受过编号1的提案了，返回编号1进攻时间1；将军2已经接受过编号2的提案了，返回编号2进攻时间2，进入accept阶段。

将军1和将军2已经接受过值了，参谋1选取编号大的提案的值（既然之前已经做出决策了，那么我们就遵循刚才的决策就好了），发送accept请求（编号3，进攻时间2），将军1和将军2之前没有接受过比这个议案编号更大的议案了，所以选择接受，返回成功，整个系统达成了共识。

推导过程

1）发布提案

最容易选定一个值的方法是只允许有一个 acceptor 代理 , 但是如果这个acceptor 出错 ，接下来的工作无法进行。

所以我们尝试另一种方法，即 使用多个 acceptor 来接受 ，我们保证如果某个值被足够大的集合所接受，那么这个值就被选定。

如何定义足够大？多数派原理，即 如果 2F + 1 的acceptor 接受了，那么 任意两个集合必然存在交集。

即使只有一个 proposer 发布了一个值，我们也希望这个值会被选定。这需要一个条件：

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

这里有个问题，如果多个proposer  在某个时间同时提出几个值，这几个值都可能被认定为多数派，那么就无法选定某个值。

从 P1 和“当且仅当大多数 acceptor 接受了某个值，这个值才是最终被选定的”这两个条件可以推出，必须允许 acceptor 接受多个提案。我们为 acceptor 可能收到的每个不同的提案分配一个自然数作为编号，这个编号是自增有序的，这样每个提案包括一个提案编号和一个值。

选定约束

P2. 如果某个值为 v 的提案被选定，那么所有被选定的编号比它大的提案中的值也是 v。

接受约束

P2a. 如果某个值为 v 的提案被选定，那么任意一个 acceptor 已经接受的所有编号比它大的提案，它们的值也是 v。

提案约束

P2b. 如果某个值为 v 的提案被选定，那么任意一个 proposer 提出的所有编号比它大的提案，它们的值也是 v。

所以我们就得到 P2b ->P2a ->P2 

为了明白怎样才能满足 P2b，让我们先来看下怎么证明它。假设某个编号为 m，值 为 v 的提案被选定了，接下来将证明任意编号为 n（n > m）的提案的值也是 v。通过对 n 使用归纳法，证明过程可以变得容易一点。

假设：编号从 m 到 n-1 的提案的值都是 v。

证明：编号为 n 的提案的值也是 v。

因为：如果被选定的提案编号为 m，那么必然有一个包含大多数 acceptor 的集合 C，C 中的每个 acceptor 都接受了它。

结合上面的归纳假设，从 m 被选定这个假设可以推出：

集合 C 中的每个 acceptor 都接受了编号从 m 到 n-1 中的某个提案，并且这些被接受了的提案的值都是 v。

如果一个集合 S 包含大多数 acceptor ，那么它和集合 C 至少有一个共同的成员。我们通过确保以下条件的不变性，就可以保证编号为 n 的提案的值是 v：

P2c. 对任意的 v 和 n，如果一个编号为 n，值为 v 的提案被发布了，那么存在一个包含大多数 acceptor 的集合 S，使得以下条件中的一个成立：
    a）S 中没有一个 acceptor 接受的提案编号小于 n；
    b）v 是 S 接受的所有编号小于 n 的提案中，编号最大的那个提案的值。

要么接受编号是最大的，要么如果接受的值对应的是最大的编号。

因此我们可以通过确保 P2c  的不变性来满足 P2b 。

为了确保 P2c 的不变性，如果某个 proposer 要发布编号为 n 的提案，那么它必须知道在所有编号小于 n 的提案中编号最大的那个提案的值，并且这个编号最大的提案必须将要或已经被大多数 acceptor 接受。获取已经被接受的提案很简单，预测将要被接受的提案却很难。为了避免对未来进行预测，proposer 承诺将来不会出现这样的情况。也就是说，proposer 要求 acceptor 不要接受任何编号小于 n 的提案。因此得到以下发布提案的算法：

1. 某个 proposer 选择一个提案编号 n 然后发送一个请求给某个集合中的每个 acceptor，请求它们回复：

• a）承诺不再接受编号小于 n 的提案；
• b）在已经接受的编号小于 n 的提案中编号最大的提案（如果有的话）。

这样的一个请求被称为编号为 n 的 prepare 请求。

1. 如果回复中没有提案，那么 proposer 可以选择任意的 v 值。
2. 如果某个 proposer 收到了大多数 acceptor 的上述回复，它就可以发布一个编号为 n，值为 v 的提案（v 必须是收到的回复中编号最大的提案的值）。

2）接受提案

acceptor 可以接收来自 proposer 的两种请求：prepare 请求和 accept 请求。acceptor 可以忽略任何请求而不影响安全性，因此，我们仅考虑它什么时候才可以回复请求。acceptor 可以回复任何 prepare 请求；但是仅当 acceptor 接受某个提案，才可以回复对应的 accept 请求。也就是说：

P1a. 当且仅当某个 acceptor 没有回复过任何编号大于 n 的 prepare 请求，它才可以接受编号为 n 的提案。

注意，P1a 包含 P1。

在提案编号唯一的假设前提下，我们有了一个完整的选择满足所需安全属性的值的算法。我们通过进行一个小优化来获得最终的算法。

假设某个 acceptor 收到一个编号为 n 的 prepare 请求。但是在此之前它已经回复过某个编号大于 n 的 prepare 请求，承诺不再接受任何编号为 n 的新提案。acceptor 没有理由回复新的 prepare 请求，因为它不会接受该 proposer 要发布的编号为 n 的提案。因此我们让 acceptor 忽略这样的 prepare 请求。我们也可以让 acceptor 忽略已接受的提案的 prepare 请求。

通过这个优化，一个 acceptor 只需要记录它接受过的编号最大的提案，以及已回复的编号最大的 prepare 请求的编号。

因为在出错的情况下也需要保证 P2c 的不变性，即使 acceptor 出错后重启也必须记录这些信息。（持久化）

结论

把 proposer 和 acceptor 的行为组合起来，我们得到下面的 2 阶段算法：

• 阶段 1
• （a）某个 proposer 选择一个编号为 n 的提案并发送一个编号为 n 的 prepare 请求给大多数 acceptor；
• （b）如果某个 acceptor 收到一个编号为 n 的 prepare 请求，n 比它已回复的任何 prepare 请求的编号都大，那么它回复该请求的内容包括：承诺不会接受任何编号小于 n 的提案，以及它已经接受的编号最大的提案（如果有的话）。
• 阶段 2
• （a）如果某个 proposer 收到大多数 acceptor 对于它编号为 n 的 prepare 请求的回复，那么它会发送一个 accept 请求给这些 acceptor。这个 accept 请求的内容是一个编号为 n，值为 v 的提案，其中 v 是在收到的回复中编号最大的提案的值。如果收到的回复中没有提案，则 v 可以为任意值；
• （b）如果某个 acceptor 收到包含编号为 n 的 accept 请求，它会接受该提案——除非它已经回复过另一个编号大于 n 的 prepare 请求。