Paxos是什么？

世界上只有一种分布式一致性协议那就是Paxos,其它的算法都是Paxos的改进或简化。

Paxos理解困境

由于理解Paxos比较复杂，使其推广上比较困难，下面就来尝试一下用通俗易懂的语言来描述Paxos.

Paxos解决什么问题？

在一个分布式系统如何就某个值（决议）达成一致，该值可以是任意的二进制的数据。一旦确定，将不再会被更改。
备注: 典型的应用场景就是Zookeeper的Leader选举。

Paxos的两个原则：

安全原则---保证不能做错的事
1. 只能有一个值被批准，不能出现第二个值把第一个覆盖的情况
2. 每个节点只能学习到已经被批准的值，不能学习没有被批准的值
存活原则---只要有多数服务器存活并且彼此间可以通信最终都要做到的事
1. 最终会批准某个被提议的值
2. 一个值被批准了，其他服务器最终会学习到这个值

Paxos的两个组件

Proposer
提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。
Acceptor
提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值

Paxos一步步理解：

假设每一台服务器都是一个提议者 （Proposer），也是一个批准者（Acceptor）。

理解paxos的关键在于假设一个时刻只有一台机器在做，理解了一台机器算法原理后，再去证明多台机器同时做也是可行的。

Copy

一个批准者

首先从最简单的方式开始，假设只有一个批准者，让它做决定是否批准一个值。

如上图，提议者分别提议一个值，然后批准者批准一个值作为最终的值。

单点问题

这种简单的方式存在单点问题，如果唯一的批准者crash了，就没有办法知道哪个值被选择了，就需要等待它重启，这一条违反了存活原则，剩除的4台服务器存活，但已经没有办法工作了。

谁被批准

有个潜在问题，批准者无法确定哪个值最终被批准。

多个批准者

为了解决这个问题，就必须要有一个批准者的集合。然后只有其中的多数批准了一个值，这个值才可以确实是被最终被批准的。为了达到目的也需要一些技巧。

批准第一个达到的值

首先规定每个批准者必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值

但是有一个问题，因为没有值被多数批准，无法批准一个最终的值出来。这就需要批准者批准了一个值之后还要根据某种规则批准不同的值。

批准每个提议的值

接下来规定Acceptor批准每个提议的值，但是这也会带来一个问题，可能会批准出多个值

如图，S1发出提议，A，B，C批准A为最终批准的值。E随后发出提议，C，D，E批准，E又为最终批准的值。此时A，B最终批准A，C，D，E最终批准E，这就违背了我们的一致性原则，最终只有一个值被选择。

二段提交原则

要解决这个问题，就要E在发送自己的提议之前，优先检查有没有已经被批准的值，如果有应该提议已经被批准的值而放弃自己的值，也就是放弃自己的A改为提议E，这样最终只有一个值被批准就是E。这个就是经典的二段提交原则。

Copy

如图，A在发送提议之前，检查没有值被批准，因此提议A。但同时在所有Acceptor批准之前，S5也要进行提议，这个时候也检查出没有值被批准，所以它也把自己的E作为提议发送给acceptor。接下来S5的提议优先到达C，D，E，这些Acceptor先批准了E，达到多数所以E最终被批准了。但是随后A，B，C接收到了A进行批准。所以又出现了批准出多个值的问题。

提议排序

这个问题要解决，就需要一旦Acceptor批准了某个值，其他有冲突的值都应该被拒绝。也就是说B随后到达的A应该被拒绝，为了做到这一点。需要对Proposer进行排序，将排序在前的赋予高优先级，Acceptor批准优先级高的值，拒绝排序在后的值。
为了将提议进行排序，可以为每个提议赋予一个唯一的ID，规定这个ID越大，优先级越高
在提议者发送提议之前，就需要生成一个唯一的ID，而且需要比之前使用的或者生成的都要大

提议ID生成算法

在Google的Chubby论文中给出了这样一种方法：假设有n个proposer，每个编号为ir(0<=ir<n)，proposor编号的任何值s都应该大于它已知的最大值，并且满足：s %n=ir == data-spm-anchor-id=ata.13261165.0.i24.48164976xSOcwl> s = m*n + ir
proposer已知的最大值来自两部分：proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值
以3个proposer P1、P2、P3为例，开始m=0,编号分别为0，1，2
1. P1提交的时候发现了P2已经提交，P2编号为1 > P1的0，因此P1重新计算编号：new P1 = 1*3+0 = 4
2. P3以编号2提交，发现小于P1的4，因此P3重新编号：new P3 = 1*3+2 = 5

到此阶段，要保证Paxos的两个原则已经都满足了，Paxos也就顺利的实现了。

二阶段提交总结

prepare 阶段：
1. Proposer 选择一个提案编号 n 并将 prepare 请求发送给 Acceptors 中的一个多数派；
2. Acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 Acceptor 将自己上次接受的提案回复给 Proposer，并承诺不再回复小于 n 的提案；

acceptor阶段：
1. 当一个 Proposer 收到了多数 Acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 Acceptors 发送 accept 请求，包括编号 n 和根据 prepare阶段 决定的 value（如果根据 prepare 没有已经接受的 value，那么它可以自由决定 value）。
2. 在不违背自己向其他 Proposer 的承诺的前提下，Acceptor 收到 accept 请求后即接受这个请求。
prepare阶段有两个目的，第一检查是否有被批准的值，如果有，就改用批准的值。第二如果之前的提议还没有被批准，则阻塞掉他们以便不让他们和我们发生竞争，当然最终由提议ID的大小决定。整个过程如下图

来源：https://www.cnblogs.com/aspirant/p/13307940.html