Paxos算法

“一个再怎么高高在上的理论，再怎么被神化的技术方案，就算再好，如果无法落地，就意味着没有任何价值”

一：一致性协议的由来

Paxos、Raft一致性协议，有些地方也称之为一致性算法，但不管称呼怎么变化，它们代表的意义是相同的，即作为CAP理论的落地者。

不过在聊Paxos、Raft这些著名的一致性协议前，我们先来聊聊为何需要它们。

回到起初集中式的单机部署方案，因为现实中存在太多不可控因素，如硬件损坏、自然环境影响、网络故障、系统/进程崩溃……，这些因素都会导致部署在该机器上的程序无法正常运转，也无力处理到来的外部请求。

这就是所谓的单点故障问题，如果一个系统未曾解决单点故障，意味着它还不够健壮、不够可靠、不够稳定！

如何保证高可用？最有效的手段就是选择集群模式部署

对业务系统这种无状态的服务来说，使用集群方案一本万利，可对于存储型的服务来说，虽然保证了可用性，但也带来了新的问题。

因为如果使用集群方案，意味着所有数据都将以副本形式存储在其余节点上，这种形式虽然提高了系统的可用性，可多节点之间的数据如何保证一致性呢？

这个问题在前几篇中反复提及，可聊来聊去，无非就是在说同步、半同步、异步复制这三种方案，一致性真有这么简单吗？实则不然，大家不妨看看这些问题：

• 集群中拥有多个节点，如何解决多个节点写入时的冲突
• 集群内某些节点出现故障时，怎么保证对外服务的可用性
• 集群发生故障转移时，如何保证新主拥有旧主的所有数据
• 集群内发生网络分区问题时，如何避免集群出现脑裂问题
• 使用读写分离时，如何保障多节点间读到的数据完全一致
• …

二：Paxos协议

Paxos算法由Lamport（莱斯利·兰伯特）提出，它是现有保证分布式一致性最有效的手段，也是诸多分布式一致性协议的“老祖宗”。

Paxos是基于消息传递且具有高度容错性的一致性算法，它被广泛运用于各类分布式存储系统。

当然，Paxos算法最早出现在兰伯特《The Part-Time Parliament》这篇论文里

Paxos算法实际有两个大类，即：

• Basic-Paxos：兰伯特论文中提到的Paxos算法，只具备单决策能力；
• Multi-Paxos：《Paxos Made Simple》论文最后拓展提到的算法，具备多决策能力。

1：拜占庭将军问题

拜占庭是古代东罗马帝国的都城，而拜占庭将军问题，是指守卫边境的一群将军，需要通过信使来与都城完成信息交换，以决定是否共同进攻敌人的场景：

然而，这些将军中可能存在叛徒，有可能发送虚假信息以干扰首都的决策。

此外，信使也可能不可靠，导致信息丢失或被篡改。

因此，拜占庭将军问题关注的是：如何在“有内奸、信使不可靠”的情况下，确保首都决策的正确性。

上述场景套到分布式系统里，身处四方的将军们，就是系统内一个个节点，而负责交换信息的信使，就是网络。

各节点发出的数据可能不一致，网络传输数据时有可能中断丢失、重发乱序、被篡改等，而这就是分布式系统里的拜占庭将军问题。

Paxos算法需要解决的就是拜占庭将军问题，即：如何在不可靠的分布式系统中，快速且正确地使各节点能够达成一致状态。

拜占庭将军问题，该如何保证决策的正确性？答案是根据大多数将军的共识进行决策！

即使将军里有内奸、通信可能被篡改

但同一件事，如果大部分将军都秉持同一个说法，那就可以认为这个信息是可靠的，也可以用来作为下达决策的依据

因此，Paxos、Raft还有另一个名字，即共识算法！

现在有一家企业叫熊猫集团

• 提案者相当于领导阶级(proposer)
• 接受者相当于董事会（acceptor）
• 学习者就是底层打工的小马仔(learner)。
• 提出的方案(proposal)

在年度总结大会上，领导可以在会议上提出各种新的方案，以此来促进集团发展，比如“小竹提出来年实行上四休三工作制”。

董事会的各位大领导，则可以针对“小竹”提出的方案进行批准，如果批准通过，集团所有打工人按方案落实即可。

3：Paxos推导过程

3.1：最初的P1

集团里可以提出方案的领导不止一人，而多位领导同时提出方案时，这时有可能会出现冲突，比如：

• 小竹：为了提升员工幸福感，明年实行“上四休三”工作制！
• 老王：为了提高工作的饱和度，明年将双休改为单休模式！

小竹和老王同时提出方案，如果一起批准落实，就会出现“一部分马仔一周干四天，另一部分马仔一周干六天”

这显然破坏了集团内部的“一致性”，此时该咋办？最简单的方案就是：

P1 -> 只让一位董事可以拥有批准权限，并且该董事必须接受提出的一个方案

因为董事只批准第一个方案，所以集团内部最终同时只能推行一种方案，避免多个方案冲突造成的不一致性！

3.2：P2的改进

上面这种模式可以嘛？不太行，毕竟现在只有一位领导，集团内大大小小方案都需要经他之手，万一某天他请假了呢？

这时方案就没人通过了（单点故障问题）

对于一个大型集团而言，这种现象必然是不可接受的，为此，具备“批准方案”权限的董事肯定不能只有一个，如下：

现在有多位董事都具备批准权限，那就出现了新的问题

如果不同的方案，同时提交给不同的董事，因为每位董事之前都没批准过其他方案，所以不同董事会一起批准通过，多种方案同时在集团内推行，又会因为方案冲突带来不一致！怎么办？完善一下通过批准的制度：

P2 -> 一个方案必须被大多数董事（至少半数以上）批准通过后，才允许在集团内推行！

为了满足这个规定，意味着某个领导提出的方案，不仅仅只是提交给一位董事，而需要提交给多位董事；

同时，一位董事不仅只接收一个方案，同时要接收、批准多个方案。

当然，为了帮助各位董事区分出“同时接收到的多个方案”，每个方案都必须有个唯一标识，即方案的编号。

就目前为止，一个完整的方案 = 方案编号 + 方案内容

通过这种“过半批准”机制，貌似解决了“不同方案被不同董事批准通过”的问题，但新问题又来了，看例子：

如上图所示

• 小竹将方案①“上四休三”提交给一号、二号董事，接着得到了两位董事批准；
• 同时，老王将方案②“双休改单休”提交给二号、三号董事，他的方案也得到了两位董事批准。

目前董事会一共三人，方案一、二都有两位董事支持，意味着这两个方案都得到了大多数董事的批准

根据前面的P2规定，集团内部又会同时推行两个方案，导致“一部分马仔一周干四天，另一部分马仔一周干六天”这种不一致场景复现。

OK，我们先来分析下产生不一致问题的原因，究其根本，就是因为在同一轮决策中，二号董事即批准了方案一、也批准了方案二

因此，在这轮决策里，最终有两个方案被批准通过。

3.3：P3的改进

怎么解决？很简单，既然同一轮决策批准多个方案会造成不一致性问题发生，那同一轮决策只允许批准通过一个方案即可。

P3 -> 同一轮决策中，所有董事都对同一个方案进行批准！

一轮决策中，所有董事同一个方案，代表最终只会有这一个方案通过，这样就解决了前面的问题。

当然，上面只是理想状态，现实情况并不可控，再看个例子：

在上午10:00时，只有一号董事在，小竹提交了“上四休三”方案，来看看是否满足前面的三个规定：

• ①小竹的方案，对一号董事来说，是收到的第一个方案，P1满足，一号批准通过；
• ②目前只有一位董事，1÷1=100%，通过此方案的董事在半数以上，P2满足；
• ③上午10:00只有一号董事在，因此P3也满足。

因为小竹提出的方案一，同时满足三个规定，因此准备开始在集团内推行。

可是到了10:30，堵车的二号董事、拉肚子的三号董事都来了，这时老王提交了“双休改单休”方案，再来看看前面的三个规定：

• ①老王的方案对二、三号董事来说，是收到的第一个方案，P1满足，二、三号批准通过；
• ②目前总共三位董事，2÷3≈66.67%，通过该方案的董事也在半数以上，P2满足；
• ③上午10:30，三位董事都在，并且同时对老王的方案进行批准，P3也满足。

此时来看，小竹的方案一还在准备推行，此时老王的方案二也通过了批准，方案二也要在集团内部推行实施

这时，由于不同方案、不同部门落实方案的快慢有所差异，两个方案“差不多一起推行”，又有可能造成不一致问题出现……

3.4：P4的改进

p4 -> 当董事批准过一个方案后，在同一轮决策又收到新的方案，就把前面通过的方案返回给新方案的提出人；提出人收到批准过的方案后，就撤销新方案的提交，等到下一轮决策时再提交

当老王提出“双休改单休”方案后，一号董事因为已经批准过小竹的方案一，因此会将方案一返回给老王

根据P4规定，老王在收到一号董事返回的方案一后，就会知道本轮决策中、在他之前已经有方案被批准通过

最后老王会撤销在本轮决策提交的方案二，留到下一轮决策时再提出，从而避免了集团内部由于方案冲突造成的不一致！

实际Paxos算法过程没有撤销，而是后来的提案者，将其Value值换成已确定的提案Value值

综上所述，经过多番推演后，通过不断完善制度，定义了P1~P4四个规定，从而保证了集团内决策的一致性

4：算法的实现过程

如上图所示，Paxos一轮决策分为Prepare、Accept、Learn三个大阶段

注意看图中的箭头走向，一轮决策开始时，会进入Prepare阶段，首先由提案者向接受者发出Prepare请求，接着对应的接受者给提案者返回响应。然后进入Accept阶段，提案者再向接受者发出Accept请求，对应的接受者再给提案者返回响应。

经过上述两轮后，一轮Paxos决策就结束了，接着会进入Learn阶段，由学习者学习确定的提案。

• Prepare预备阶段：集团领导向董事会提出方案的阶段；
• Accept接受阶段：集团董事会正式批准方案通过的阶段；
• Learn学习阶段：向集团内部打工马仔推行方案的阶段；

4.1：prepare准备阶段

Proposer提案者在提出提案之前，首先要生成一个提案编号

接着向至少大多数（半数以上）Acceptor接受者发出Prepare请求（通常是向所有Acceptor发出）

Prepare请求并不携带任何内容，只携带本次生成的提案编号（ID），对应的伪代码为：

// 接受者列表
Set<Acceptor> acceptors = ...;
// 自己的提案编号
Long proposalId = null;

/**
 * Proposer发送Prepare请求的方法
**/
public void sendPrepareReq(long currentProposalId) {
    // 1.获取一个全局递增的提案ID
    proposalId = generateId();
    // 2.循环向接受者发出Prepare请求
    for(Acceptor acceptor : acceptors) {
        // 3.给接受者发送Prepare请求，至少发给半数以上节点为止
        sendPrepareRequest(acceptor, proposalId);
    }
}

为啥Prepare请求要发给绝大多数接受者？

因为如果不将此请求发给绝大多数Acceptor，对应的提案就得不到大多数接受者的批准，无法满足之前提出的约定。

在Acceptor接收到Prepare请求后，会给提案者返回响应，那接受者内部会做什么处理呢？

有三个原则：

1. 如果Acceptor之前已确认过某个提案，则将之前接受过的提案（编号+Value）都返回给本次的Proposer提案者。
2. 如果之前已经收到过其他提案的Prepare请求，则判断两次请求的提案编号，如果本次请求的编号小于之前的提案编号，当前Acceptor就可以忽略当前Prepare请求，或者直接向对应的提案者返回错误提示。
3. 如果之前的编号，不大于本次请求的提案编号（即本次请求编号大于之前响应过的所有编号），就会响应本次Prepare请求（比如返回一个OK信号），同时承诺不再接受小于本次提案编号的提案。

// 已响应过的、编号最大Prepare请求对应的提案编号
Long maxRespondedProposalId = null;
// 已接受过（批准通过）的提案
Proposal acceptedProposal = null;

/**
 * Acceptor接收Prepare请求的方法
 *  currentProposalId参数：Prepare请求对应的提案编号
**/
public Object receivePrepareReq(long currentProposalId) {
    // 1.如果之前已经接受过提案（Proposal），则直接返回对应的提案
    if (acceptedProposal != null) {
        return acceptedProposal;
    }
    
    // 2.如果之前已经响应过别的Prepare请求，则判断提案编号大小
    if (maxRespondedProposalId != null) {
        // 3.如果本次Prepare请求的提案编号，小于响应过的最大编号，则直接返回错误
        if (currentProposalId < maxRespondedProposalId) {
            throw new Exception("你太小啦~");
        } 
        // 4. 如果本次Prepare请求的提案编号，不小于响应过的最大编号，记录编号并返回OK
        else {
            maxRespondedProposalId = currentProposalId;
            return "OK，你编号最大，我以后不会接受比你小的啦！";
        }
    }
}

4.2：accept批准阶段

提案者发出Prepare请求后，如何处理接受者返回的结果呢？如下：

// 接受者列表
Set<Acceptor> acceptors = ...;

// 计算出“大多数接受者”到底是几个
int moreThanHalf = acceptors.size() / 2 + 1;

// 正常响应Prepare请求的Acceptor数量
int prepareReqSuccess = 0;

// 本轮决策中已确认的提案（有可能存在多个，用集合保存）
List<Proposal> confirmedProposals = new ArrayList<>();

/**
 * Proposer提案者处理Prepare请求返回结果的方法
**/
public Object handlePrepareReqResult(Object result) {
    // 1.如果返回的是一个提案，说明之前已经有被确认的提案存在，记录一下
    if (result instanceof Proposal) {
        confirmedProposals.add((Proposal) result);
    } 
    // 2. 如果返回的是字符串，说明是正常响应OK的消息（自增响应成功的数量）
    else if (result instanceof String) {
        prepareReqSuccess++;
    }
    
    // 3.对于返回错误的Prepare请求不做处理
    
    // 4.判断正常响应Prepare请求的接受者数量是否已达半数以上
    if (prepareReqSuccess >= moreThanHalf) {
        // 5. 如果已经有半数以上，则发出Accept请求
        sendAcceptReq(...);
    }
}

仔细观察上述伪代码，首先计算出了“大多数接受者”的具体数量，接着用prepareReqSuccess记录了正常响应Prepare请求的接受者数量

同时，如果有返回已确认过的提案，也会记录下来。

根据之前的约束，一个提案如果要被接受，需要通过半数以上接受者的同意

因此，当一个Proposer提案者发出Prepare请求，并收到大多数Acceptor接受者的正常返回后，就可以认为自己的“提案申请”得到了大部分Acceptor的支持，所以在最后的if判断中，如果已正常响应的接受者数量，达到了半数以上，此时则会进入Accept阶段，就可以继续发出Accept请求。

Accept请求里包含提案编号和Value，Proposer提案者在发送该请求，会先进行判断，依据如下：

如果发出Prepare请求后，没有Acceptor返回已确认的提案，则说明自己是第一个提案，本次Accept请求会提交自己的编号+自己的Value值。

如果Acceptor返回了确认过的提案，发送请求时，就将自己的编号+已确认的、编号最大的、提案的Value值，发送给至少大多数Acceptor。

即前面伪代码中的最后一个判断，完整的逻辑如下：

// 4.判断正常响应Prepare请求的接受者数量是否已达半数以上
if (prepareReqSuccess >= moreThanHalf) {
    // 5.如果已经有半数以上，则准备发出Accept请求
    Proposal proposal = new Proposal();
    proposal.setProposalId(proposalId);

    // 6.判断Acceptor是否返回过提案
    if (confirmedProposals.size() > 0) {
        // 7.本轮决策有确认的提案，则找到编号最大提案发送
        Proposal maxProposal = getIdMaxProposal(confirmedProposals);
        proposal.setValue(maxProposal.getValue());
    } 
    // 8.如果本轮决策中不存在确认过的提案，则发送自己的Value
    else {
        proposal.setValue(this.value);
    }

    // 9.正式向Acceptor发出Accept请求（至少发满半数以上）
    for(Acceptor acceptor : acceptors) {
        sendAcceptReq(proposal);
    }
}

下面再来看看Acceptor接受者收到提案后的处理流程，共有两个原则：

1. 如果该Accept请求是Acceptor接收到的第一个提案，则必须接受该提案；
2. 如果不是第一个Accept请求，则对比当前Accept请求的编号，是否小于之前响应过的、最大的Prepare请求编号，如果小于则忽略本次Accept请求，反之则接受（确认提案）

// 已响应过的、编号最大Prepare请求对应的提案编号
Long maxRespondedProposalId = null;
// 已接受过（批准通过）的提案
Proposal acceptedProposal = null;

/**
 * Acceptor接收Accept请求的方法
 *  proposal：请求携带的的提案
**/
public String receivePrepareReq(Proposal proposal) {
    // 1.如果acceptedProposal为空，说明是接收到的第一个提案
    if (acceptedProposal == null) {
        // 如果是第一个提案则接受并返回对应标识
        acceptedProposal = proposal;
        return "accept";
    }

    // 2.如果不是第一个提案，则对比响应过的最大编号
    if (proposal.getProposalId() < maxRespondedProposalId) {
        // 3.如果本次提案小于响应过的最大Prepare请求，则拒绝/忽略该请求
        return "refuse";
    }

    // 4.如果不小于响应过的最大Prepare请求，则接受本次请求的提案
    acceptedProposal = proposal;
    return "accept";
}

如上图所示，目前是一个由A、B、C、D、E五个节点组成的分布式存储系统

此时A节点收到外部写入的“name=竹子”命令，B节点收到外部写入的“name=熊猫”的命令（A先于B写入）。

假设这里的C、D、E节点则是Acceptor接受者，于是A、B都准备向C、D、E节点发起Prepare请求，流程如下：

1. A接收到外部写入，生成提案编号（1），并向C、D、E发起Prepare请求；
2. C、D、E响应A的Prepare请求，并记录A的编号（1）；
3. A收到C、D、E的响应后，发现得到了大多数Acceptor响应，继续发起Accept请求；
   • 因为C、D、E没有返回已确认的提案，所以Value由A决定，则将“竹子”提交；
4. C、D、E之前都未接受过提案，因此都会接受并记录A的提案（ID=1，Value=竹子）； <- 注意这里
5. B接收到外部写入，生成提案编号（2），并向C、D、E发起Prepare请求；
6. 因为C、D、E已经接受过提案，所以会给B响应提案（ID=1，Value=竹子）；
7. B收到响应后，发现已存在确认的提案，得到大多数Acceptor返回后，发起Accept请求；
   • B从返回的提案中，找到编号最大的提案其Value值，生成提案（ID=2，Value=竹子）；
8. C、D、E收到B的提案后，发现其编号最大，则会将对应的提案记录下来并接受；

上面这个流程，就是图中画出的步骤，大家可以将本案例，把前面所有伪代码完整套一遍，此时就会更加清晰。

B节点Accept请求提交的Value为“竹子”，那它自己收到的“熊猫”难道丢了吗？

答案是No，“熊猫”这个值并未丢弃，而是留到下一轮继续提出

即：当B节点提交完“竹子”的Accept请求后，紧接着又会提出一个ID=3的Prepare请求，重复前面的流程，尝试将“熊猫”这个提案提交出去！

(id = 3, value = “熊猫”)

好了，关于两个阶段的流转就讲到这里，不过实际的Paxos算法里，并不会将某个节点的角色固化

即ABCDE五个节点，都可以在Proposer、Acceptor、Learner三者之间切换。

在Paxos算法被提出的时代背景里，并不存在中心化的主节点，所有节点都具备完整的读写能力，自身写入的数据，都会同步给系统内其余节点

4.3：learn学习阶段

这个阶段并不参与Paxos的决策，只负责学习已确认（已接受）的提案。

换到最开始的案例中，学习者就是打工仔，不参与集团方案的提出与决策，只能被动执行已批准通过的方案~

在Paxos算法里，Learner（学习者）学习已确认的提案，代表着它需要获取到已确认提案的Value，怎么做？一共有三种方案。

• Acceptor确认一个提案后，就将该提案发送给所有Learner（学习者）-> 董事们就去一个一个工位的跑。
• Acceptor确认一个提案后，将提案发给一个Learner，剩余Learner由它负责通知 -> 董事长秘书。
• Acceptor确认一个提案后，将提案发给部分Learner，剩余Learner由它们负责通知 -> 一个秘书有可能请假、生病，那就招一群秘书组成一个团

5：Paxos致命缺陷(中心化主从架构)

到这里，我们对Basic-Paxos算法的方方面面做了讲述，但Basic-Paxos有个致命的缺陷

有点类似于IOC的依赖循环问题，假设现有两个Propser同时发起Prepare请求，如下：

• A：获取全局递增编号1，发起Prepare请求，获得过半响应；
• B：获取全局递增编号2，发起Prepare请求，因为2>1，所以也获得过半响应；
• A：发起Accept请求，因为目前Acceptors响应过的最大编号为2，所以提案会被拒绝；
• A：发现Accept请求被拒绝，重新获取编号3，再发起Prepare请求，3>2，获得过半响应；
• B：发起Accept请求，可目前Acceptors响应过的最大编号为3，提案自然会被拒绝；
• B：Accept请求被拒，重新获取编号4，……

到这里，大家会发现，如果两个Propser同时发起Prepare请求，然后依次提出编号递增的提案，就会陷入相互循环的过程

两个Propser提案者都能完成Prepare阶段，可始终无法完成Accept阶段，造成没有Value被选定。

怎么解决这个问题？

答案是只允许一个节点发起提案，即：系统内只允许存在一个Propser角色的节点，其余节点只能选择是否接受提案，以及学习已确认的提案。

现在就明白为啥Paxos之后，分布式存储系统会发展成中心化的主从架构了吧？

因为去中心化的分布式存储，在当时来说，是一道无法攻克的难关，在做数据一致决策时，很容易陷入上面的死循环！

6：Multi-Paxos算法

最开始提到Basic-Paxos是一种单决策算法，一轮决策中只能确认一个Value，并且每确认一个Value都至少需要经过Prepare、Accept两个阶段

如果目前系统接收的写入并发较高，每一次值都需要单独进行一轮决策，这样的模式效率太低了。

回顾Basic-Paxos确认提案的两个阶段，大家会发现，其实Prepare阶段的作用，就是为了确认并发场景中，到底使用哪个Proposer的提案。

那假设一开始就能确认到底使用哪个Proposer的提案，是不是Prepare阶段阶段就可以去掉了？

答案是肯定的，这就是Basic-Paxos的变种：Multi-Paxos出现的原因，旨在提高共识收敛速度和减少通信延迟。

综上，如果在分布式系统运行的大部分时间内，都能确定一个Proposer（Leader/Master概念）

只允许它才能提出提案，这样就可以省略掉Prepare阶段，每次只需要发Accept请求即可。

道理很简单，因为同一时刻永远只会有一个提案出现，自然就不会出现争议，也不会因为多提案造成不一致现象发生

外部写请求只能交给Leader处理，代表着Leader发出的提案，自然都是确定的值。

当然，Multi-Paxos虽然引入了单Leader概念，不过却是一种弱Leader的思想

Multi-Paxos对脑裂问题也有容忍性，也就是“它允许多个节点自认为是Leader”的情况出现。

遇到这种脑裂场景时，就会退化成Basic-Paxos算法来保证一致性，经过一轮Basic-Paxos决策后，胜出的节点又会成为新Leader。

Raft共识算法就属于Multi-Paxos的变种~