1.来源

Paxos算法是莱斯利·兰伯特（Leslie Lamport）于1990年提出的一种基于消息传递的一致性算法。

1.1.故事

在古希腊，有一个叫做Paxos的小岛，岛上通过议会的形式来通过法令，议会中议员通过信使来传递消息。议员和信使都是兼职的，他们随时有可能离开会议厅，并且信使可能会重复的传递消息，也可能丢失消息。因此议会要保证在这种情况下法令仍然能够正确地产生，并且不会出现冲突。

1.2.波折

1990年，The Part-Time Parliament，完成并投稿，无人能懂，被拒
1996年，上述论文被重审，Nancy Lynch公布修改版Revisiting the Paxos Algorithm
1998年，The Part-Time Parliament终于被ACM TOCS接收
2001年，Lamport本人重新讲述原文，发表了论文Paxos Made Simple

2.分布式事务的CAP理论

• 一致性（Consistency）
• 可用性（Availability）
• 分区容错性（Partition Tolerance)

三者不可兼得

3.常见一致性协议

• 两阶段提交
• 三阶段提交
• ZAB协议
• Paxos协议
• Raft协议

3.1.限定

• 只有被提出的提案才能被选定
• 在被提出的提案中，只有一个提案会被选定
• 如果没有被提出，那么就不会有被选定的提案
• 当一个提案被选定后，进程可以获取被选定的提案信息
• 任一进程认为被选定的那个提案，必须是真的被选定的那个

4.Paxos算法

4.1.角色

Proposer（选举中对某个职位提出候选人的倡议者）

• 发送Prepare请求给Acceptor
• 发送Accept请求给Acceptor

Acceptor（对倡议者提出的候选人进行投票的参与者）

• 接收Prepare请求，并回复Prepare请求
• 接收Accept请求，并发送Result给Learner

Learner（类似于没有投票权的群众）

• 接收Result

4.2.通信方式

• 不同角色之间可以通过发送消息来进行通信，那么：每个角色以任意的速度执行，可能因出错而停止，也可能会重启
• 一个value被选定后，所有的角色可能失败然后重启，除非那些失败后重启的角色能记录某些信息，否则等他们重启后无法确定被选定的值
• 消息在传递过程中可能出现任意时长的延迟，可能会重复，也可能丢失。但是消息不会被损坏，即消息内容不会被篡改

4.3.推导

4.3.1.一个Acceptor

假设只有一个Acceptor（可以有多个Proposer），只要Acceptor接受它收到的第一个提案，则该提案被选定，该提案里的value就是被选定的value。这样就保证只有一个value会被选定。

缺陷：唯一的Acceptor宕机，就彻底崩溃了

4.3.2.多个Acceptor

4.3.2.1.约定

• P1：一个Acceptor必须接受它收到的第一个提案
  一个提案被选定需要被半数以上的Acceptor接受，那么一个Acceptor必须能够接受不止一个提案
  • P1a：一个Acceptor只要尚未响应过任何编号大于M的Prepare请求，那么他就可以接受这个编号为M的提案
• P2：如果某个value为v的提案被选定了，那么每个编号更高的被选定提案的value必须也是v
  • P2a：如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v
  • P2b：如果某个value为v的提案被选定了，那么之后任何Proposer提出的编号更高的提案的value必须也是v
  • P2c：对于任意的M和V，如果提案[M, V]被提出，那么存在一个半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个：
    • S中每个Acceptor都没有接受过提案
    • S中Acceptor接受过的最大编号的提案的value为V

4.3.2.2.推论

4.3.2.2.1.满足P2b

Proposer生成提案之前，应该先去“学习”已经被选定或者可能被选定的value，然后以该value作为自己提出的提案的value。如果没有value被选定，Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个“Prepare请求”实现的。

4.3.2.2.2.满足P1a

如果Acceptor收到一个编号为M的Prepare请求，在此之前它已经响应过编号大于M的Prepare请求。该Acceptor不可能接受编号为M的提案。因此，该Acceptor可以忽略编号为M的Prepare请求。当然，也可以回复一个error，让Proposer尽早知道自己的提案不会被接受。

4.3.2.3.提案生成

• Proposer选择一个新的提案编号M，然后向某个Acceptor集合（半数以上）发送Prepare请求，要求该集合中的每个Acceptor做出如下响应：
  • 向Proposer承诺保证不再接受任何编号小于M的提案
  • 如果Acceptor已经接受过提案，那么就向Proposer响应已经接受过的编号小于M的最大编号的提案
• 如果Proposer收到了半数以上的Acceptor的响应，那么它就可以生成编号为M，Value为V的提案[M,V]。其中V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案，那么此时V就可以由Proposer自己选择。
• 生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。称该请求为Accept请求。

4.3.2.4.接收提案

• Acceptor接收到Prepare请求编号M，
  • 当前响应的最大编号>M，则忽略或回复error
  • 当前响应的最大编号<M，
    • 当前已接受[N,B]的Accept请求，则回复M，B
    • 当前未接受，则记录M，返回ACK
• Acceptor接收到Accept请求[M,V]
  • 当前响应的最大编号>M，则忽略或回复error
  • 当前响应的最大编号<M，
    • 当前未接受，则记录[M,V]，并通知Learner，V
    • 当前已接受[N,B]的Accept请求，则
      • N>M，则忽略或回复error
      • N<M，则记录[M,V]，并通知Learner，V

4.3.2.5.流程

• 阶段1
  • Proposer选择一个提案编号M，然后向半数以上的Acceptor发送编号为M的Prepare请求
  • 如果一个Acceptor收到一个编号为M的Prepare请求，且M大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于M的提案
• 阶段2
  • 如果Proposer收到半数以上Acceptor对其发出的编号为M的Prepare请求的响应，那么它就会发送一个针对[M,V]提案的Accept请求给半数以上的Acceptor
  • 如果Acceptor收到一个针对编号为M的提案的Accept请求，只要该Acceptor没有对编号大于M的Prepare请求做出过响应，它就接受该提案，并通知Learner
• 阶段3
  • Learner收到Acceptor对其发送的结果V，如果收到半数以上，那么认为V被选定；如果没有收到半数以上