Paxos从理论走向实践的三剑客

行情分析

周日了,各位老铁有没有出去玩呀?小链还是要给大家准备精神食粮,哎......

比特币(1h线):实际昨天已经提醒了,超过250点回调就必须减仓。那么以目前的状况来说,9000基本已经确定成为了压力区间,那么之后的做单方式,就是等本轮调整结束。本轮调整不可以跌破8600,否则没有买点。只要在下午13:00前不跌破8600,就关注5分钟底背离做单,新低严格止损。

以太坊(1h线):昨天分析了接下来是震荡消化的调整行情,那么果然预测准确,这里必须注意以太坊走势较弱,买点构造和比特币类似,临界点560,但不建议操作。

EOS(4h线):实际昨天预言的临界点9.6没有跌破,那么这里震荡后还可以再新高,有能力的可以做低吸高抛的短线操作,不擅长超短的建议放弃,等待震荡调整结束后的机会。

每日充电

春眠不觉晓,春困真烦恼。周末是个小妖精,但愿长睡不用醒。

而——存稿已空,老板催工,这才是周末真正的模样。

回到昨天的话题(复习请看Paxos介绍)。Paxos虽然可以解决分布式系统一致性问题,但是理论价值高于实际用途

试想有100个皇帝的情况。在Paxos的框架下,总是可以通过不断的协(che)调(pi)达成最终的共识。但100个皇帝的不同意见会使得其中一个皇帝得到50%以上正面回复更加困难,从而降低算法达成一致的效率。

为了解决这个问题,兰波和后来者提出了三种非常精妙的简化算法,满足了现实工程对一致性的要求。下面我们就来看看这三剑客的风采。

1 Multi-Paxos

Multi-Paxos是兰波本人在Paxos基础上提出的实用算法,其思想非常简单,就是让皇帝数量变成1个,即可省略第一阶段的准备过程。

那怎样达成这一点呢?

▲运行完整的Paxos过程选举唯一的proposer

首先,所有proposer通过完整的Paxos算法选举出唯一的proposer。

▲唯一的proposer可以省略第一阶段提高效率

接下来唯一的proposer负责与acceptor进行沟通,问题简化到一个皇帝的过程。昨天描述的一个皇帝在两阶段如何与大臣沟通达成共识,从而乾纲独断希望老铁们还有印象。而实际上第一阶段是可以省略的,因为这里不存在直接回家的大臣。这就大大节省了算法耗费的时间。于是实际上,算法成为了一阶段的递交协议。

2 ZAB

ZAB被称为原子广播协议,雅虎的Zookeeper就采用了这种算法。Zookeeper使用单一主进程Leader用于处理客户端所有事务请求,采用Zab协议将服务器状态以事务形式广播到所有Follower上。由于事务间可能存在着依赖关系,ZAB协议保证Leader广播的变更序列按顺序处理,一个状态被处理那么它所依赖的状态也已经提前被处理。

实际上ZAB与Multi-Paxos非常相似,也需要简化出一个leader来发号施令。这两种算法的区别在于,Multi-Paxos每次选举出来的proposer可能没有存储最新的共识,所以刚当上leader的节点需要和其他节点进行同步。这就好比皇帝刚登基,需要召见大臣们了解国内各项政策的运行情况。

而ZAB则没有这种问题。ZAB在选举leader节点时会考虑不同节点更新共识的状态,选取更新最多共识的节点成为新leader。这样就可以省去新leader同步共识的环节。

3 RAFT

RAFT和前两种算法也很相似,同样先把很多leader简化成1个。其核心思想很容易理解:如果数个数据库初始状态一致,只要之后的进行的操作一致,就能保证之后的数据一致。由此RAFT使用的是Log进行同步,并且将服务器分为三种角色:Leader,Follower,Candidate,相互可以互相转换。

RAFT从大的角度看,分为两个过程:第一,选举Leader;第二,Leader生成Log,并与Follower进行Heartbeats同步。

第二步实际上就是维护与更新共识的过程,与前面两种算法没有太大差别。RAFT算法的亮点在于选举leader。在描述过程时我们引入了Heartbeats这个词,这就是选举leader的重要工具。

具体而言,每一个candidate与leader之间都有不断的信息交流,我们把这种信息称为Heartbeats(即心跳)。如果leader突然不给candidate传递心跳了,说明leader可能宕机,需要选出新leader。最先发现leader宕机的节点就会向全网广播自己成为新leader。

那如何甄选最先发现这一点的节点呢?

这就是RAFT设计精妙之处。每一个candidate与leader之间会有一个约定的心跳时间间隔阈值,比如取150ms到300ms之间的随机值。这个阈值对每个candidate而言是不同的。在leader宕机之后,存在一个candidate最先触发这一阈值。当他触发阈值之后,发现全网其他candidate并没有声明自己成为新leader,于是这一节点就会向全网宣示自己成为新leader并承担接下来的同步任务。

4 Paxos的意义

非拜占庭场景的共识算法可以看做区块链共识机制的前传。有些读者可能会认为,前传的重要性并不大,为什么我们要去关注呢?

小链非常喜欢托尔金的《魔戒》三部曲。托尔金在形成《魔戒》的宏伟世界观之前,其实首先完成了《霍比特人》的写作,揭开了中洲大陆的冰山一角。作为《魔戒》系列的前传,托尔金对霍比特人探险故事的介绍成为了魔戒争夺这场史诗级战争的基础和序幕。没有霍比特人的冒险,哪来之后的洪水滔天?

Paxos类算法在共识机制中的作用大抵如是。虽然正餐非常美味,营养丰富,但是前菜也同样重要。从现实出发,大家都互相认识的私链上Paxos三剑客还是很实用的算法,只是在公链上无用武之地。

所以,虽然各位老铁读我们的文章令小链十分感激,但在读之前先关注我们,也为我们继续陪伴大家奠定坚实的基础。话不多说,快长按下方二维码关注我们吧!

行情/道法自然 文/小众胡吹

老铁双击666↓↓↓

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

扫码关注云+社区

领取腾讯云代金券