Paxos 简介
当多个节点同时参与完成一件事情时候，需要对过程中的事件达成一致，而Paxos就是在不可靠的计算机网络中用来保证一致性（可靠性）的算法。 除了 Paxos 之外，还有保持多个副本来保证可靠性的方法，比如主从异步复制。而 Paxos 则属于多数派写的算法， 即仿照选举的过程中少数服从多数的方法，只要一个系统中一半以上节点正常即可保证整个系统的一致性和可靠性。可以将Paxos看成一种特殊的主从复制机制， 类似红黑树和二叉搜索树的关系。
Paxos 基本假设和概念
Paxos 算法工作先决条件是数据存储没有错误和丢失(消息可以丢失和乱序)， 在此基础上， Paxos 有几个概念：
- Proposer : 发起请求并请求Acceptor接受
- Acceptor ：作为Paxos存储节点，接受和存储数据，一半以上节点Acceptor组成Quorums。而且消息必须发给一个Quorums或者被一个Quorums发出
- Quorums : 至少一半(n/2 + 1) Acceptors, 保证了消息的可靠性
- Proposal Number 和 Agreed Value : Agreed Value是每次Proposer要写的数据，Proposal Number是每次Proposer的一个全局唯一的值， 并且单调递增。
Typical Deployment
在Paxos中, 每个参与的节点都会充当Proposer和Acceptor 。Proposer给Quorums发送Proposal Number 和 Agreed Value , 然后Acceptors根据Proposal Number来决定是否接受Agreed Value。如果Proposer不能和至少一个Quorum通信则不能发起Paxos过程。
Basic Paxos
这是最基本的Paxos协议，完成一次Paxos需要两个Round，每个Round分为两个Phase：
- Phase 1a : Prepare : Proposer给至少一个Quorum发送Proposal Number， Proposer Number要比之前该Proposer用的都大。
- Phase 1b : Promise : 如果Proposal Number比Acceptor之前收到的任何Proposal Number都大，则返回之前收到的Proposal Number和Agreed Value，并承诺之后不接受任何其他Proposal。否则，Acceptors应该ignore， 可以不应答也可以返回Nack告诉Proposer放弃该Proposal。
- Phase 2a : Accept Request ：如果收到至少一个Quorum的应答，则可以发送Agreed Value。如果返回的Agreed Value都是空则可以任意选择自己要写入的Agreed Value，否则选择Proposal Number最大的Agreed Value。
- Phase 2b : Accepted : Acceptors接受之前Promised的Proposal Number的Agreed Value， 拒绝其他Proposal。
上述Paxos过程可以用下面的图表示：
Proposal x Acceptor 1,2,3
Prepare proposalNum ----------> 1, 2,
Promise <---------- 1 lastProposalNum, lastAgreeVal
2 lastProposalNum, lastAgreeVal
AcceptReq agreeVal ----------> 1, 2,
Accepted 1, 2, agreeVal
Multi Paxos
上面的Basic Paxos每次都需要2个round， 4个delay来完成一次Paxos。而Multi Paxos则省掉了上面的Phase 1过程， 也就是相当于只有一个Proposer, 上面已经提到过， Paxos可以看成加了约束来保证可靠性的主从复制机制， 而Multi Paxos更加说明这一点。
Fast Paxos
上面的Multi Paxos一次Paxos只需要2个delay，但是却只能有一个Proposer。Fast Paxos则结合上面两个协议， 在没有冲突时类似Multi Paxos协议，Proposer只进行Phase 2， 当有冲突发生时则回退到Basic Paxos。有区别的是为了保证可靠性Fast Paxos中的Quorum不再是n/2+1, 而变成了n * 3/4。