Paxos算法在分布式领域具有非常重要的地位，虽然非常重要，但是也因算法复杂而著名
Quorum机制
在学习Paxos算法之前，我们先来看分布式系统中的Quorum选举算法，在各种一致性算法中都可以看到Quorum机制的身影，主要数学思想来源于抽屉原理，用一句话解释那就是，在N个副本中，一次更新成功的如果有W个，那么我在读取数据的时候是要从大于N - W个副本中读取，这样就能至少读到一个更新的数据了。
和Quorum机制对应的是WARO，也就是Write All Read one，是一种简单的副本控制协议，当Client请求向某副本写数据时（更新数据），只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。
WARO有限保证读服务，因为所有的分本更新成功，才能使为更新成功，从而保证了所有的副本一直，这样的话，只需要都任何一个读本上的数据即可。写服务的可用性就较低了，因为只要有一个副本更新失败，此次写操作就视为失败了，假设有N个副本，N - 1个都宕机了，剩下的那个副本尽管任然能提供读服务，写服务也不会成功。
WARO说白了就是牺牲了更新服务的可用性，最大程度增强了读服务的一致性（在CAP概念中有点类似与AP的强一致性），而Quorum就是在更新服务和读服务的一个折中。
Quorum定义
Quorum假设有N个副本，更新操作在W个副本中更新成功以后，才认为此次更新操作成功，把这次成功提交的更新操作对应的数据叫做：“成功提交的数据”。对于读操作而言，至少需要读 R 个副本才能读到此次更新的数据，其中 W+R>N，即W和R有重叠，一般的话W+R=N+1
N = 存储数据副本的数量
W = 更新成功所需要的副本
R = 一次数据对象读取要访问的副本数量
Quorum就是限定了一次需要读取至少N+1-w的副本数据，听起来有点抽象嗷，比如说，我们一共有10个副本，一次成功更新了4个，那么我至少要读取7个，就可以保证我们读到了最新的数据。
Quorum的应用
Quorum机制无法保证强一致性，也就是无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据，Quorum机制的使用需要配合一个获取最新成功提交的版本号的metadata服务，这样可以确定最新已经成功提交的版本号，然后从已经独到的数据中就可以确认最新写入的数据。
Quorum是分布式系统中常用的一种机制，用来保证数据冗余和最终一致性的投票算法，在Paxos Raft和ZooKeeper的Zab算法中，都可以看到Quorum机制的运用。
Paxos节点的角色和交互
了解了Quorum机制，我们接下来学习Paxos算法，首先来看一下Paxos算法中的节点交互。
Paxo的节点角色
在Paxos协议中，有三类节点角色，分别为Proposer，Acceptor和Learner，另外还有一个Client，作为产生议题者
Proposer提案者
Proposer可以有多个，在流程开始时，Proposer提出议案，也就是value，所谓value，在工程中可以是任何操作，比如“修改某个变量的值为某个新值”，Paxos协议中同意将这些操作抽象为value。
Acceptor批准者
在集群中，Acceptor有N个，Acceptor之间完全对等独立，Proposer提出的value必须获得超过半数，即N/2 + 1的Acceptor批准后才能通过。
Learner学习者
Learner不参与选举，而是学习被批准的value，在Paxos中，Learner主要参与相关的状态机同步流程，这里的Learner的流程就参考了Quorum的议会机制，某个value需要获得W = N/2 + 1的Acceptor的批准，Learner需要至少读取N/2 + 1 个Acceptor，最多读取N个Acceptor的结果后，才能至少学习到一个用过的value
Client产生议题者
Client角色，作为产生议题者，实际上是不参与选举过程的，比如发起修改请求的来源等
Proposer与Acceptor之间的交互
Proposer和Acceptor是Paxos算法中的核心部分，算法其本身就是描述在一个由多个Proposer和多个Acceptor构成的系统当中，如何让多个Acceptor针对Proposer提出的多种提案达成一致的一个过程，而Learner只是“学习”最终被批准的提案，
Proposer与Acceptor之间的交互主要有4类信息通信，如图
这四类消息对应于Paxos算法的两个阶段的4个过程
选举过程可以分为两个部分，准备阶段和选举阶段，可以查看下面的时序图：
Phase 1 准备阶段(P1)
Proposer生成全局唯一且递增的ProposalID，向Paxos集群的所有机器发送Prepare请求，这里不携带value，只携带N即ProposalID。
Acceptor 收到 Prepare 请求后，判断收到的 ProposalID 是否比之前已响应的所有提案的 N 大，如果是，则：
在本地持久化N，可记为Max_N；
回复请求，并带上已经Accept的提案中N最大的value，如果此时还没有已经Accept的提案，则返回value为空；
做出承诺，不会.Accept任何小于Max_N的提案
如果否，则不回复或者回复 Error。
推导：
先来先服务，合情合理。但这样产生一个问题，如果多个Proposers同时提出Proposal，很可能会导致无法达成一致，因为没有Proposal被超过一半Acceptors的接受，因此，Acceptor必须能够接受多个Proposal，不同的Proposal由不同的编号进行区分，当某个Proposal被超过一半的Acceptors接受后，这个Proposal就被选定了。
既然允许Acceptors接受多个Proposal就有可能出现多个不同值都被最终选定的情况，这违背了Safety要求，为了保证Safety要求，Paxos进一步提出：
Phase2选举阶段(P2)
只要算法同时满足P1和P2，就保证了Safety。P2是一个比较宽泛的约定，完全没有算法细节，我们对其进一步延伸：
为了方便描述，我们把Phase2选举阶段继续拆分为P2a、P2b、P2c
经过一段时间后，Proposer收集到一下Prepare回复，有下列几种情况：
P2a：Proposer 发送 Accept
若回复数量 > 一半的 Acceptor 数量，且所有回复的 value 都为空时，则 Porposer 发出 accept 请求，并带上自己指定的 value。
若回复数量>一半的Acceptor数量，且有的回复value不为空时，则Porposer发出accept请求，并带上回复中ProposalID最大的value，作为自己的提案内容
若回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，再转到准备阶段执行。
推导：
如果值为v的Proposal被选定（Chosen），则对所有的Acceptors，它们接受（Accept）的任何具有更高编号的Proposal值也一定为v。
如果满足P2a则一定满足P2，显然，因为只有首先被接受才有可能被最终选定。但是P2a依然难以实现，因为acceptor很有可能并不知道之前被选定的Proposal（恰好不在接受它的多数派中），因此进一步延伸：
P2b：Acceptor 应答 Accept
Accept请求后，判断：
若收到的 N >= Max_N（一般情况下是等于），则回复提交成功，并持久化 N 和 value；
若收到的 N < Max_N，则不回复或者回复提交失败。
推导：
如果值为v的Proposal被选定（Chosen），则对所有的Proposer，它们提出的的任何具有更高编号的Proposal值也一定为v。
P2c: Proposer 统计投票
经过一段时间后，Proposer 会收集到一些 Accept 回复提交成功的情况，比如：
当回复数量 > 一半的 Acceptor 数量时，则表示提交 value 成功，此时可以发一个广播给所有的 Proposer、Learner，通知它们已 commit 的 value；
当回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，转到准备阶段执行。
当收到一条提交失败的回复时，则尝试更新生成更大的 ProposalID，也会转到准备阶段执行。
推导：
为了提出值为v且编号为n的Proposal，必须存在一个包含超过一半Acceptors的集合S，满足(1) 没有任何S中的Acceptors曾经接受（Accept）过编号比n小的Proposal，或者(2) v和S中的Acceptors所接受过(Accept)的编号最大且小于n的Proposal值一致。
满足P2c即满足P2b即满足P2a即满足P2。至此Paxos提出了Proposer的执行流程，以满足P2c
Paxos算法的伪代码如下：
1.获取一个Proposer ID n， 为了保证Proposal ID唯一，可采用时间戳+Server ID生成，或者可为每个Proposer分配一个标识j(0-4)，那么每一个Proposer每次提出决议的编号可以为5 * i + j，i表示提出议案的次数。
2.Proposer向所有Acceptors广播Prepare(n)请求。
3.Acceptor比较n和minProposal，如果n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
4.Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value；
5.到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；
6.Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，进行本地持久化后，返回；否则，返回minProposal。
7.提议者接收到过半数请求后，如果发现有返回值result >n，表示有更新的提议，跳转到1；否则value达成一致。
普通的Paxos算法也会遇到一些问题，如图所示：
两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）
Muti-Paxos算法
原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。
实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了两点改进：
- 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。
- 在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。
Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。
Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。
Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。
Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。
参考
《Paxos算法详解》- 祥光
《分布式技术原理与实战45讲》- 蒋越