Paxos协议要点

• Paxos协议*有三种角色：Proposer、Acceptor、Learner，具体实现中一个进程可担当多个角色。

• Paxos协议的目的：针对同一主题，每个Proposer都可提出若干提案，所有的Acceptor和Learner必须从这些提案中一致的选定某个提案。

• 某个提案被选定成功的定义：此提案被超过半数Acceptor 批准。

• Paxos的第一个Prepare阶段的目的是确定Proposer如何生成提案。这实际上涉及到Paxos协议的推导，可参考《从Paxos到Zookeeper 分布式一致性原理与实践》。即Prepare阶段是提案生成阶段。

  提案生成算法如下，此算法保证了如果某个提案[M0, V0]被选定后，之后Proposer提出的任何编号大于M0的提案，其值一定是V0。
  

• Paxos的第二个Accept阶段的目的是将生成的提案发送给所有Acceptor批准，如果超过半数Acceptor都批准了，则此提案被选定成功。即Accept阶段是提案选定阶段。

• 一个提案已经被超过半数Acceptor批准，但是Proposer可能并不知道提案已经被选定成功，因为Accept阶段，大多数Acceptor返回的响应可能在网络中丢失。但是所幸的是Prepare阶段的提案生成算法保证了Proposer新的提案的值一定为已经选定的提案的值。

• Acceptor对于Prepare和Accept请求的响应原则：Acceptor可以成功响应编号大于当前Acceptor记录过最大编号的提案请求（Prepare和Accept请求）。响应过程可参考以下流程图。

Paxos算法陈述

Paxos算法流程图

• K为提案编号
• MaxN为Acceptor所记录的最大提案编号
• AcceptN为Acceptor所批准的提案编号
• AcceptV为Acceptor所批准的提案的值。
  

Paxos协议缺陷

多个Proposer竞相提案，陷入死循环：

解决方法：选举主Proposer，只有主Proposer才能进行提案，即Multi-Paxos、Raft等协议。