从零到壹学习共识算法第十四讲:通过 PhxPaxos 了解 Paxos 原理

作者:黎跃春

孔壹学院创始人兼CEO

黎跃春:孔壹学院创始人兼CEO,国内区块链布道先行者,通信和信息技术培养工程区块链高级授课专家。如果您有任何关于区块链的问题,可以加入区块链技术交流QQ群729666975(进群无需添加验证信息,直接点击下一步,等待管理员通过即可),我们会为您一一解答。

从零到壹学习共识算法为一个系列,一共18讲,包括通过一个App的演示深入理解区块链运行原理、go 实现简单的区块链、拜占庭、PoW、PoS、DPoS、Paxos、Raft等,为大家详尽的介绍共识算法的学习过程。今天我们将为大家介绍从零到壹学习共识算法第十四讲:通过 PhxPaxos 了解 Paxos 原理 。话不多说,马上开启我们的共识算法学习之旅。

课程学习,添加莉莉微信(kongyixueyuan)。

孔壹学院

下载

Prepare阶段

Prepare

Proposer在Prepare阶段主要做了这么几件事:

重置各个状态位,表明当前正处于Prepare阶段。

获取提案编号ProposalID。当bNeedNewBallot为true时需要将ProposalID+1。否则沿用之前的ProposalID。bNeedNewBallot是在NewValue中调用Prepare方法时传入的m_bWasRejectBySomeone参数。也就是如果之前没有被任何Acceptor拒绝(说明还没有明确出现更大的ProposalID),则不需要获取新的ProposalID。对应的场景是Prepare阶段超时了,在超时时间内没有收到过半Acceptor同意的消息,因此需要重新执行Prepare阶段,此时只需要沿用原来的ProposalID即可。

发送Prepare请求。该请求PaxosMsg是Protocol Buffer定义的一个message,包含MsgType、InstanceID、NodeID、ProposalID等字段。在BroadcastMessage(oPaxosMsg)中还会将oPaxosMsg序列化后才发送出去。

PaxosMsg的定义如下,Prepare和Accept阶段Proposer和Acceptor的所有消息都用PaxosMsg来表示:

OnPrepareReply

Proposer发出Prepare请求后就开始等待Acceptor的回复。当Proposer所在节点收到PaxosPrepareReply消息后,就会调用Proposer的OnPrepareReply(oPaxosMsg),其中oPaxosMsg是Acceptor回复的消息。

该阶段Proposer主要做了以下事情:

判断消息是否有效。包括ProposalID是否相同,自身是否处于Prepare阶段等。因为网络是不可靠的,有些消息可能延迟很久,等收到的时候已经不需要了,所以需要做这些判断。

将收到的消息加入MsgCounter用于统计。

根据收到的消息更新自身状态。包括Acceptor承诺过的ProposalID,以及Acceptor接受过的编号最大的提案等。

根据MsgCounter统计的Acceptor投票结果决定是进入Acceptor阶段还是重新发起Prepare请求。这里如果判断需要重新发起Prepare请求的话,也不是立即进行,而是等待一段随机的时间,这样做的好处是减少不同Proposer之间的冲突,采取的策略跟raft中leader选举冲突时在一段随机的选举超时时间后重新发起选举的做法类似。

注:这里跟Paxos算法中提案编号对应的并不是ProposalID,而是BallotNumber。BallotNumber由ProposalID和NodeID组成。还实现了运算符重载。如果ProposalID大,则BallotNumber(即提案编号)大。在ProposalID相同的情况下,NodeID大的BallotNumber大。

Accept 阶段

接下来Proposer就进入Accept阶段:

Accept

Accept请求中 里的Value是这样确定的:如果Prepare阶段有Acceptor的回复中带有提案值,则该Value为所有的Acceptor的回复中,编号最大的提案的值。否则就是Proposer在最初调用NewValue时传入的值。

OnAcceptReply

这里跟OnPrepareReply的过程基本一致。比较大的区别在于最后如果过半的Acceptor接受了该Accept请求,则说明该Value被选定(Chosen)了,就发送消息,让每个节点上的Learner学习该Value。

Acceptor

OnPrepare

OnPrepare用于处理收到的Prepare请求,逻辑如下:

OnAccept

再来看看OnAccept:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180713G1XTAI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券