一、Paxos协议简介

Paxos算法由Leslie Lamport在1990年提出，它是少数在工程实践中被证实的强一致性、高可用、去中心的分布式协议。Paxos协议用于在多个副本之间在有限时间内对某个决议达成共识。Paxos协议运行在允许消息重复、丢失、延迟或乱序，但没有拜占庭式错误的网络环境中，它利用“大多数 (Majority)机制”保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

拜占庭式错误释义：
一般地把出现故障但不会伪造信息的情况称为“非拜占庭错误”(Non-Byzantine Fault)或“故障错误”(Crash Fault)；而伪造信息恶意响应的情况称为“拜占庭错误”(Byzantine Fault)。

1、核心概念

• Proposal：提案（提案 = 提案编号acceptNumber + 提案值acceptValue）;
• Proposal Number：提案编号;
• Proposal Value：提案值;

2、参与角色

• Proposer（提案者）：处理客户端请求，主动发起提案；
• Acceptor (投票者)：被动接受提案消息，参与投票并返回投票结果给Proposer以及发送通知给Learner；
• Learner（学习者）：不参与投票过程，记录投票相关信息，并最终获得投票结果；

在实际的分布式业务场景中，一个服务器节点或进程可以同时扮演其中的一种或几种角色，而且在分布式环境中往往同时存在多个Proposer、多个Acceptor和多个Learner。

3、基础逻辑

Paxos算法是指一个或多个提案者针对某项业务提出提案，并发送提案给投票者，由投票者投票并最终达成共识的算法。

”达成共识“过程的特点：
（1）、可以由一个或多个提案者参与；
（2）、由多个投票者参与；
（3）、可以发起一轮或多轮投票；
（4）、最终的共识结果是一个值，且该值为提案者提出的其中某个值；

二、Basic Paxos

1、两个阶段

Basic Paxos算法分为两个阶段：Prepare阶段和Accept阶段。

(1). Prepare阶段

该阶段又分为两个环节：

• a、Proposer发起广播消息给集群中的Acceptor发送一个提案编号为n的prepare提案请求。
• b、Acceptor收到提案编号为n的prepare提案请求，则进行以下判断：
  如果该Acceptor之前接受的prepare请求编号都小于n或者之前没有接受过prepare请求，那么它会响应接受该编号为n的prepare请求并承诺不再接受编号小于n的Accept请求，Acceptor向Proposer的响应数据包含三部分内容：接受编号n的提案状态信息，之前接受过的最大提案编号和相应提案值；如果该Acceptor之前接受过至少一个编号大于n的prepare请求，则会拒绝该次prepare请求。

通过以上prepare阶段处理流程可以知道：

• a、prepare请求发送时只包含提案编号，不包含提案值；
• b、集群中的每个Acceptor会存储自己当前已接受的最大提案编号和提案值。

假设分布式环境中有一个Proposer和三个Acceptor，且三个Acceptor都没有收到过Prepare请求，Prepare阶段示意图如下：

假设分布式环境中有两个Proposer和三个Acceptor，ProposerB成功发送prepare请求，在发送Accept请求时出现故障宕机，只成功给Acceptor1发送了accept请求并得到响应。当前各个Acceptor的状态分别为：
Acceptor1，同意了ProposerB发送的提案编号2的Accept请求，当前提案值为：orange；
Acceptor2，接受了ProposerB发送的提案编号2的Prepare请求；
Acceptor3，接受了ProposerB发送的提案编号2的Prepare请求；
此时ProposerA发起Prepare请求示意图如下：

流程说明：

• a、ProposerA发起prepare(1)的请求，由于该编号小于提案编号2，所以请求被拒绝；
• b、ProposerA发起prepare(3)的请求，该编号大于编号2，则被接受，Accetpor1返回Promised(3,2,'orange')，表示接受编号3的提案请求，并将之前接受过的最大编号提案和提案值返回。
• c、Acceptor2和Acceptor3均返回Promised(3)，表示接受编号3的提案请求。

(2). Accept阶段

如果Proposer接收到了超过半数节点的Prepare请求的响应数据，则发送accept广播消息给Acceptor。如果Proposer在限定时间内没有接收到超过半数的Prepare请求响应数据，则会等待指定时间后再重新发起Prepare请求。

Proposer发送的accept广播请求包含什么内容：

• a、accept请求包含相应的提案号；
• b、accept请求包含对应的提案值。如果Proposer接收到的prepare响应数据中包含Acceptor之前已同意的提案号和提案值，则选择最大提案号对应的提案值作为当前accept请求的提案值，这种设计的目的是为了能够更快的达成共识。而如果prepare返回数据中的提案值均为空，则自己生成一个提案值。

Acceptor接收到accept消息后的处理流程如下：

• a、判断accept消息中的提案编号是否小于之前已同意的最大提案编号，如果小于则抛弃，否则同意该请求，并更新自己存储的提案编号和提案值。
• b、Acceptor同意该提案后发送响应accepted消息给Proposer，并同时发送accepted消息给Learner。Learner判断各个Acceptor的提案结果，如果提案结果已超过半数同意，则将结果同步给集群中的所有Proposer、Acceptor和所有Learner节点，并结束当前提案。
  当Acceptor之前没有接受过Prepare请求时的响应流程图：
  

当Acceptor之前已存在接受过的Prepare和Accept请求时的响应流程图：

该示例中prepare请求返回数据中已经包含有之前的提案值（1,'apple'）和（2,'banana'），Proposer选择之前最大提案编号的提案值作为当前的提案值。

2、关于提案编号和提案值

• 提案编号

在Paxos算法中并不自己生成提案编号，提案编号是由外部定义并传入到Paxos算法中的。
我们可以根据使用场景按照自身业务需求，自定义提案编号的生成逻辑。提案编号只要符合是“不断增加的数值型数值”的条件即可。
比如：
在只有一个Proposer的环境中，可以使用自增ID或时间戳作为提案编号；
在两个Proposer的环境中，一个Proposer可以使用1、3、5、7...作为其编号，另一个Proposer可以使用2、4、6、8...作为其提案编号；
在多Proposer的环境中，可以为每个节点预分配固定ServerId(ServerId可为1、2、3、4...)，使用自增序号 + '.' + ServerId或timestamp + '.' + ServerId的格式作为提案编号，比如：1.1、1.2、2.3、3.1、3.