Paxos算法-基于消息传递的一致性算法
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被选定；如果没有收到半数以上
