1. 首页
  2. 后端

(五)漫谈分布式之一致性算法篇：谁说Paxos晦涩难懂？你瞧这不一学就会！

良月柒 • 4天前 • 后端 • 阅读 23 
  (五)漫谈分布式之一致性算法篇：谁说Paxos晦涩难懂？你瞧这不一学就会！

=====================================

引言

—

本文为稀土掘金技术社区首发签约文章，30天内禁止转载，30天后未获授权禁止转载，侵权必究！

在前面《CAP与BASE理论》、《分布式一致性模型》两篇文章中，我们对“分布式思想、一致性模型”这两大分布式领域的基石侃侃而谈，可其中聊的内容都如同断梗浮萍一般的理论。

有句古话说得好：“纸上谈兵中觉浅，绝知此事要躬行”，在IT技术领域同样如此，一个再怎么高高在上的理论，再怎么被神化的技术方案，就算再好，如果无法落地，就意味着没有任何价值。价值和实用性成正比，实用性跟热度挂钩，回看前几篇聊的诸多理论，或许“年龄”比你都大，动辄便是一二十年前的思想，为何会沿用至今？

没在时代发展的洪流中泯然于众的道理很简单，是因为它们并不仅是空中楼阁般的高大上理论，而是有着完整落地的思想，它们已然成为构建分布式系统不可或缺的底层基石，而本文则来好好聊聊分布式与一致性思想的落地者：Paxos与Raft协议（算法）。

PS：个人编写的《技术人求职指南》小册已完结，其中从技术总结开始，到制定期望、技术突击、简历优化、面试准备、面试技巧、谈薪技巧、面试复盘、选Offer方法、新人入职、进阶提升、职业规划、技术管理、涨薪跳槽、仲裁赔偿、副业兼职……，为大家打造了一套“从求职到跳槽”的一条龙服务，同时也为诸位准备了七折优惠码：3DoleNaE，在为找工作而困扰的小伙伴可以点击：s.juejin.cn/ds/USoa2R3/了解详情！

一、一致性协议的由来

Paxos、Raft一致性协议，有些地方也称之为一致性算法，但不管称呼怎么变化，它们代表的意义是相同的，即作为CAP理论的落地者。不过在聊Paxos、Raft这些著名的一致性协议前，我们先来聊聊为何需要它们。

回到起初集中式的单机部署方案，因为现实中存在太多不可控因素，如硬件损坏、自然环境影响、网络故障、系统/进程崩溃……，这些因素都会导致部署在该机器上的程序无法正常运转，也无力处理到来的外部请求。这就是所谓的单点故障问题，如果一个系统未曾解决单点故障，意味着它还不够健壮、不够可靠、不够稳定！

如何保证高可用？最有效的手段就是选择集群模式部署，对业务系统这种无状态的服务来说，使用集群方案一本万利，可对于存储型的服务来说，虽然保证了可用性，但也带来了新的问题。

数据存储组件

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

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

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

面对上面的一系列问题，Paxos与Raft协议给出了答案，下面一起先来看看大名鼎鼎的Paxos。

二、Paxos协议

Paxos

Paxos算法由Lamport（莱斯利·兰伯特）提出，它是现有保证分布式一致性最有效的手段，也是诸多分布式一致性协议的“老祖宗”。Paxos是基于消息传递且具有高度容错性的一致性算法，它被广泛运用于各类分布式存储系统。

当然，Paxos算法最早出现在兰伯特《The Part-Time Parliament》这篇论文里，但由于其中使用“古希腊岛屿议会”的故事性手法来描述，用兰伯特的原话来说：

“为了进一步形象地展示，我以印第安纳·琼斯风格的考古学家的角色，戴着牛仔帽，拿着酒壶进行了几次演讲。我试图在这个主题中加入一些幽默，但以惨败告终。听过我演讲的人记得印第安纳·琼斯，但不记得算法。阅读这篇论文的人显然被希腊寓言分散了注意力，以至于他们不理解算法。”

因此，Paxos算法最开始鲜有人问津，直到后续谷歌真正运用到该思想后，Paxos才开始成为分布式一致性的代名词，为此，兰伯特本人也在多年后，又对最初的论文做了简化，新出了一篇名为《Paxos Made Simple论文》的论文。

OK，简单了解Paxos算法的产生背景后，为了下面更好的讲解，先声明一点，Paxos算法实际有两个大类，即：

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

现在看这两个分类或许有点迷糊，但没关系，大家心里有个概念即可，后续讲Paxos更多的是指Basic-Paxos，而关于Mulit-Paxos，Raft、ZAB协议就属于它优化版的变种，下面来一点点揭开Paxos的真面目。

2.1、拜占庭将军问题

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

拜占庭将军

然而，这些将军中可能存在叛徒，有可能发送虚假信息以干扰首都的决策。此外，信使也可能不可靠，导致信息丢失或被篡改。因此，拜占庭将军问题关注的是：如何在“有内奸、信使不可靠”的情况下，确保首都决策的正确性。

上述场景套到分布式系统里，身处四方的将军们，就是系统内一个个节点，而负责交换信息的信使，就是网络。各节点发出的数据可能不一致，网络传输数据时有可能中断丢失、重发乱序、被篡改等，而这就是分布式系统里的拜占庭将军问题。Paxos算法需要解决的就是拜占庭将军问题，即：如何在不可靠的分布式系统中，快速且正确地使各节点能够达成一致状态。

拜占庭将军问题，该如何保证决策的正确性？答案是根据大多数将军的共识进行决策！即使将军里有内奸、通信可能被篡改，但同一件事，如果大部分将军都秉持同一个说法，那就可以认为这个信息是可靠的，也可以用来作为下达决策的依据，因此，Paxos、Raft还有另一个名字，即共识算法！

2.2、Paxos中的三种角色

Paxos将任何操作都抽象成了“Value值”的概念，但Value并不仅仅是指一条数据，也可以是一个命令、一条日志……，根据不同的应用场景，Value所代表的含义并不同。目前假设Value代表的是一条数据，在分布式系统中，相同数据可能同时存在多个值，Paxos算法保证的就是根据大多数节点的共识，选定其中一个值，从而让系统内的数据快速达成一致状态。

为了实现一致性的目标，在Paxos的定义中，存在三种角色，它们各自在系统里发挥着不同的作用，如下：

Paxos角色

  • Proposer提案者：可以发起提案；
  • Acceptor接受者：可以选择是否批准提案；
  • Learner学习者：可以学习已经确定的提案。

PS：在分布式系统中，一个节点即可以是Paxos定义的提案者，也可以是接受者，又可以是学习者，即：并非一个节点只能担任一种角色，而是有可能会同时充当多种角色。

这里提到一个提案（Proposal）的概念，这啥意思？提案实际上就类似于一个“申请”，里面包含了两个核心值，一个是提案编号，另一个是本次要达成一致的Value，即：提案=编号+Value。好了，为了更充分的理解上述三种角色，这里套入到现实生活的例子中来理解：

现在有一家企业叫熊猫集团，提案者相当于领导阶级，接受者相当于董事会（决策层），学习者就是底层打工的小马仔。在年度总结大会上，领导可以在会议上提出各种新的方案，以此来促进集团发展，比如“小竹提出来年实行上四休三工作制”。董事会的各位大领导，则可以针对“小竹”提出的方案进行批准，如果批准通过，集团所有打工人按方案落实即可。

在上述案例中，小竹提出的“上四休三工作制”方案，就是一个提案，提案会给到接受者（董事会）进行批准，已经确定过的提案，打工人（学习者）就进行落实。Paxos算法的三种角色也是类似的作用，Proposer负责提出提案，Acceptor负责批准提案，Learner负责学习已确定的提案。

好了，大概理解Paxos的三种角色后，接着咱们一起来看看算法的具体的推导过程。

PS：为了便于诸位理解，推导过程会基于上面给出的生活案例来讲述，旨在降低大家的学习成本，即：

Proposer提案者 = 领导；

Acceptor接受者 = 董事；

Learner学习者 = 打工人（小马仔）；

Proposal提案 = 方案。

2.3、Paxos算法的推导过程

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

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

小竹和老王同时提出方案，如果一起批准落实，就会出现“一部分马仔一周干四天，另一部分马仔一周干六天”，这显然破坏了集团内部的“一致性”，此时该咋办？最简单的方案就是：

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

单Acceptor

这时不管多少��同时提出方案，也不管方案之间是否冲突，因为董事只批准第一个方案，所以集团内部最终同时只能推行一种方案，避免多个方案冲突造成的不一致性！

上面这种模式可以嘛？不太行，毕竟现在只有一位领导，集团内大大小小方案都需要经他之手，万一某天他请假了呢？这时方案就没人通过了（单点故障问题），对于一个大型集团而言，这种现象必然是不可接受的，为此，具备“批准方案”权限的董事肯定不能只有一个，如下：

多Acceptor

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

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

为了满足这个规定，意味着某个领导提出的方案，不仅仅只是提交给一位董事，而需要提交给多位董事；同时，一位董事不仅只接收一个方案，同时要接收、批准多个方案。当然，为了帮助各位董事区分出“同时接收到的多个方案”，每个方案都必须有个唯一标识，即方案的编号。就目前为止，一个完整的方案=方案编号+方案内容。

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

大多数Acceptor批准

如上图所示，小竹将方案①“上四休三”提交给一号、二号董事，接着得到了两位董事批准；同时，老王将方案②“双休改单休”提交给二号、三号董事，他的方案也得到了两位董事批准。目前董事会一共三人，方案一、二都有两位董事支持，意味着这两个方案都得到了大多数董事的批准，根据前面的P2规定，集团内部又会同时推行两个方案，导致“一部分马仔一周干四天，另一部分马仔一周干六天”这种不一致场景复现。

OK，我们先来分析下产生不一致问题的原因，究其根本，就是因为在同一轮决策中，二号董事即批准了方案一、也批准了方案二，因此，在这轮决策里，最终有两个方案被批准通过。怎么解决？很简单，既然同一轮决策批准多个方案会造成不一致性问题发生，那同一轮决策只允许批准通过一个方案即可。

套进上面的例子，小竹的方案在第一轮决策被通过，推行后全集团的打工人，都过上了上四休三的好日子；过了一段时间后，老王的方案在第二轮决策被通过，推行后全集团过上了单休的悲惨生活……。

来看这种情况，虽然两种方案最终都在集团内推行，但却没有同时推行，意味着不会出现“部分人三休、部分人单休”的不一致现象，最多出现“前段时间三休、这段时间单休”的情况，而后续这种情况明显可以容忍，毕竟在同一时刻里，集团内部所有人的“状态”保持着一致。

如何实现一轮决策只允许通过一个方案呢？很简单，再完善一下制度：

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

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

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

故障恢复场景

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

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

因为小竹提出的方案一，同时满足三个规定，因此准备开始在集团内推行。可是到了10:30，堵车的二号董事、拉肚子的三号董事都来了，这时老王提交了“双休改单休”方案，再来看看前面的三个规定：

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

此时来看，小竹的方案一还在准备推行，此时老王的方案二也通过了批准，方案二也要在集团内部推行实施，这时，由于不同方案、不同部门落实方案的快慢有所差异，两个方案“差不多一起推行”，又有可能造成不一致问题出现……

PS：案例中堵车、拉肚子又回来的董事，对应着发生网络故障、宕机又恢复的Acceptor；而方案推行的快慢有所差异，对应着Learner学习时的网络延迟。

OK，看完上面的特殊场景后，我们发现P3规定，也不能保证一轮决策中只通过一个方案，现在又该怎么办？答案是继续完善制度：

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

套入P4规定，再来看前面的例子：

Proposer放弃新提案

当老王提出“双休改单休”方案后，一号董事因为已经批准过小竹的方案一，因此会将方案一返回给老王，根据P4规定，老王在收到一号董事返回的方案一后，就会知道本轮决策中、在他之前已经有方案被批准通过，最后老王会撤销在本轮决策提交的方案二，留到下一轮决策时再提出，从而避免了集团内部由于方案冲突造成的不一致！

PS：实际Paxos算法过程没有撤销，而是后来的提案者，将其Value值换成已确定的提案Value值（后面算法过程细说）。

OK，综上所述，经过多番推演后，通过不断完善制度，定义了P1~P4四个规定，从而保证了熊猫集团内决策的一致性，而接着一起来看看Paxos具体的实现过程。

2.4、Paxos算法的实现过程

Paxos算法过程

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

经过上述两轮后，一轮Paxos决策就结束了，接着会进入Learn阶段，由学习者学习确定的提案。当然，大家看到这里有点迷糊，这三个阶段到底做了啥？套进前面的例子里理解一下：

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

当然，大家看完还是有点模糊没关系，目前大家只需明白整体流程走向即可，下面来对各阶段逐个展开。

2.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，对应的提案就得不到大多数接受者的批准，无法满足之前提出的约定。

PS：关于分布式系统中如何生成全局递增的唯一编号，后续会开专门的文章讲述，本文不做过多展开。

好了，回到之前画的时序图，在Acceptor接收到Prepare请求后，会给提案者返回响应，那接受者内部会做什么处理呢？有三个原则：

①如果Acceptor之前已确认过某个提案，则将之前接受过的提案（编号+Value）都返回给本次的Proposer提案者。

②如果之前已经收到过其他提案的Prepare请求，则判断两次请求的提案编号，如果本次请求的编号小于之前的提案编号，当前Acceptor就可以忽略当前Prepare请求，或者直接向对应的提案者返回错误提示。

③如果之前的编号，不大于本次请求的提案编号（即本次请求编号大于之前响应过的所有编号），就会响应本次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，你编号最大，我以后不会接受比你小的啦！";
        }
    }
}

伪代码的注释写的格外清晰，大家参照理解时最好带着“多线程”思维去看，如果有疑惑也没关系，等后面Accept阶段讲完后再来看一次，就会格外的清晰，最后再附上一张图帮助理解：

Prepare阶段

2.4.2、Accept批准阶段

上阶段说了Prepare阶段的逻辑，但提案者发出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接受者收到提案后的处理流程，共有两个原则：

①如果该Accept请求是Acceptor接收到的第一个提案，则必须接受该提案；

②如果不是第一个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";
}

大家简单过一遍上面的伪代码及注释，下面结合实际例子，来分析一遍完整的Prepare、Accept两个阶段的流转，先上张图：

Prepare与Accept流转

如上图所示，目前是一个由A、B、C、D、E五个节点组成的分布式存储系统，此时A节点收到外部写入的“name=竹子”命令，B节点收到外部写入的“name=熊猫”的命令（A先于B写入）。假设这里的C、D、E节点则是Acceptor接受者，于是A、B都准备向C、D、E节点发起Prepare请求，流程如下：

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

上面这个流程，就是图中画出的步骤，大家可以将本案例，把前面所有伪代码完整套一遍，此时就会更加清晰。当然，有人或许会好奇：B节点Accept请求提交的Value为“竹子”，那它自己收到的“熊猫”难道丢了吗？答案是No，“熊猫”这个值并未丢弃，而是留到下一轮继续提出，即：当B节点提交完“竹子”的Accept请求后，紧接着又会提出一个ID=3的Prepare请求，重复前面的流程，尝试将“熊猫”这个提案提交出去！

好了，关于两个阶段的流转就讲到这里，不过实际的Paxos算法里，并不会将某个节点的角色固化，即ABCDE五个节点，都可以在Proposer、Acceptor、Learner三者之间切换。同时，更值得注意的是：在Paxos算法被提出的时代背景里，并不存在中心化的主节点，即分布式存储系统，所有节点都具备完整的读写能力，自身写入的数据，都会同步给系统内其余节点。

PS：为啥最初的这种去中心化的、各节点都具备读写处理能力的分布式存储系统，在后续会逐步演变成中心化的、从节点被阉割写请求处理能力的主从架构？这点我们在后续分析，其实也跟Paxos算法有很大关系。

2.4.3、Learn学习阶段

上面聊完了Paxos一轮决策中最重要的Prepare、Accept阶段，现在来看看最后的Learn学习阶段，这个阶段并不参与Paxos的决策，只负责学习已确认（已接受）的提案。换到最开始的案例中，学习者就是打工仔，不参与集团方案的提出与决策，只能被动执行已批准通过的方案~

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

  • ①Acceptor确认一个提案后，就将该提案发送给所有Learner（学习者）。
  • ②Acceptor确认一个提案后，将提案发给一个Learner，剩余Learner由它负责通知。
  • ③Acceptor确认一个提案后，将提案发给部分Learner，剩余Learner由它们负责通知。

第一种方式，就相当于董事会通过一个方案后，董事们就去一个一个工位的跑，挨个告诉每个打工仔要推行新方案了。显然，这种方式虽然能让打工仔最快得知已经有新方案被确定了，可是缺点也很明显，有点“废董事”，如果集团有一万多名员工，董事们要跑一万多个工位~

第二种方式，等价于招了个“董事长秘书”，当董事会有新的方案确认后，由秘书去挨个工位通知打工人。这种方案对董事们来说很轻松，只要通知秘书即可，但缺点也很明显，如果这位秘书有一天生病了、请假了，就没人去负责通知了……

第三种方案，属于第二种方案的进阶版，既然一个秘书有可能请假、生病，那就招一群秘书组成一个团，当有新的方案被批准后，董事会只需要通知秘书团就好，由秘书团去挨个通知打工的小马仔。当然，这种方式也有缺点，毕竟秘书变多了，管理起来就更复杂……

好了，相信通过上面三段话，诸位就能很好理解提到的三种方案，而“学习”的动作究竟是干啥？很简单，比如上小节的例子，当name=竹子的提案被确认后，学习者就把这个确认的提案Value，同步写入到自身节点内即可。

2.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之后，分布式存储系统会发展成中心化的主从架构了吧？因为去中心化的分布式存储，在当时来说，是一道无法攻克的难关，在做数据一致决策时，很容易陷入上面的死循环！

2.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。

PS：到这里篇幅不算短了，为此本文不对Multi-Paxos进行展开，在下篇关于Raft的内容会详细说明，毕竟Raft就属于Multi-Paxos的变种~

三、Paxos一致性协议总结

因为Paxos的初衷是为了保证分布式系统，在遇到节点掉线又回归、网络消息乱序/重发、网络分区等不可控的场景下，系统仍能保证较强的一致性。算法本身的立意就很复杂，兰伯特又用“希腊小岛议会”的手法撰写论文，加上Paxos中并未划分出子问题，而是试图用一个抽象的Value，涵盖分布式系统的所有状况，种种因素相结合，就造就了Paxos难以理解的场面出现。

题外话：对国内来说，论文本身是英文版本，翻译成中文后本身就存在歧义，这无疑更增加了理解的复杂度。

当然，在本文中，你会发现Paxos不再那么难以理解，因为文中将“西方式的议会”案例，改为了我们更容易理解的“集团方案决策”，同时将算法过程，以我们更容易理解的伪代码方式描述，从而极大程度上降低了学习成本！

“小竹，更适合中国Java体质的技术写作者”，这是套用飞鹤奶粉广告梗说的一句玩笑话，要表达的意思并非我多么厉害，而是想表达一个思想：有些本来很绕的技术/事情，当拆解成贴近于对方生活场景的例子描述，就会变得简单起来，化繁为简，这是一个非常重要、有用的理念，希望诸位以后工作中能运用起来。

好了，本文就讲到这里，我们下篇再见！当然，我的所有文章都会陆续同步到微信公众号：竹子爱熊猫，想在微信上便捷阅读的小伙伴可搜索关注~

原文链接: https://juejin.cn/post/7356114363882061863

文章收集整理于网络，请勿商用，仅供个人学习使用，如有侵权，请联系作者删除，如若转载，请注明出处：http://www.cxyroad.com/16986.html

赞 (0)
良月柒 良月柒
0
Navicat Premium 破解教程,Navicat,激活码,注册码，亲测有效！
« 上一篇 6天前
(八)漫谈分布式之缓存篇：唠唠老生常谈的MySQL与Redis数据一致性问题！
下一篇 » 4天前

相关推荐

QR code