360SDN.COM

【Zookeeper灵魂】一个关于Paxos算法的故事

来源:高效运维  2017-09-19 11:25:44    评论:0点击:

本文转载自公众号:大数据研习社

前言

Zookeeper 默认采用 FastLeaderElection 算法,然而 FastLeaderElection 对于 Zookeeper 来讲只是相当于 paxos 中的 leader 选举。

下面我们用最简单的方式加以描述并建立起 Paxos 和 ZKServer 的对应关系。

Paxos描述了这样一个场景:

  1. 有一个叫做 Paxos 的小岛(Island)上面住了一批居民,岛上面所有的事情由一些特殊的人决定,他们叫做议员(Senator)。

  2. 议员的总数(SenatorCount)是确定的,不能更改。

  3. 岛上每次环境事务的变更都需要通过一个提议(Proposal),每个提议都有一个编号(PID),这个编号是一直增长的,不能倒退。

  4. 每个提议都需要超过半数 ((SenatorCount) / 2+1) 的议员同意才能生效。

  5. 每个议员只会同意大于当前编号的提议,包括已生效的和未生效的。

  6. 如果议员收到小于等于当前编号的提议,他会拒绝,并告知对方:你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号,他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。

现在议会有一个目标:保证所有的议员对于提议都能达成一致的看法。

好,现在议会开始运作,所有议员一开始记事本上面记录的编号都是0。

  1. 有一个议员发了一个提议:
    将电费设定为1元/度。

  2. 他首先看了一下记事本,嗯,当前提议编号是0。

  3. 那么我的这个提议的编号就是1,于是他给所有议员发消息:1号提议,设定电费1元/度。

  4. 其他议员收到消息以后查了一下记事本,哦,当前提议编号是0,这个提议可接受,于是他记录下这个提议并回复:我接受你的1号提议,同时他在记事本上记录:当前提议编号为1。

  5. 发起提议的议员收到了超过半数的回复,立即给所有人发通知:1号提议生效!

  6. 收到的议员会修改他的记事本,将1好提议由记录改成正式的法令,当有人问他电费为多少时,他会查看法令并告诉对方:1元/度。

现在看冲突的解决:

假设总共有三个议员 S1-S3,S1和S2同时发起了一个提议:

  1. 1号提议,设定电费。

  2. S1想设为1元/度,S2想设为2元/度。

  3. 结果S3先收到了S1的提议,于是他做了和前面同样的操作。

  4. 紧接着他又收到了S2的提议,结果他一查记事本,咦,这个提议的编号小于等于我的当前编号1,于是他拒绝了这个提议:对不起,这个提议先前提过了。

  5. 于是S2的提议被拒绝,S1正式发布了提议:1号提议生效。

  6. S2向S1或者S3打听并更新了1号法令的内容,然后他可以选择继续发起2号提议。

好,我觉得 Paxos 的精华就这么多内容。现在让我们来对号入座,看看在 ZKServer 里面 Paxos 是如何得以贯彻实施的。

??小岛(Island)—— ZKServerCluster
??议员(Senator)—— ZKServer
??提议(Proposal)—— ZNodeChange(Create/Delete/SetData…)
??提议编号(PID)—— Zxid(ZooKeeperTransactionId)

正式法令——所有ZNode及其数据:

貌似关键的概念都能一一对应上,但是等一下,Paxos 岛上的议员应该是人人平等的吧,而 ZKServer 好像有一个 Leader 的概念。

没错,其实 Leader 的概念也应该属于 Paxos 范畴的。

如果议员人人平等,在某种情况下会由于提议的冲突而产生一个“活锁”(所谓活锁我的理解是大家都没有死,都在动,但是一直解决不了冲突问题)

Paxos 的作者 Lamport 在他的文章 “ThePart-TimeParliament”中阐述了这个问题并给出了解决方案——在所有议员中设立一个总统,只有总统有权发出提议,如果议员有自己的提议,必须发给总统并由总统来提出。

好,我们又多了一个角色:总统

?总统——ZKServerLeader

现在我们假设总统已经选好了,下面看看 ZKServer 是怎么实施的。

情况一:

屁民甲(Client)到某个议员(ZKServer)那里询问Get某条法令的情况ZNode的数据,议员毫不犹豫的拿出他的记事本localstorage,查阅法令并告诉他结果,同时声明:我的数据不一定是最新的。你想要最新的数据?没问题,等着,等我找总统 Sync 一下再告诉你。

情况二:

屁民乙Client到某个议员ZKServer那里要求政府归还欠他的一万元钱,议员让他在办公室等着,自己将问题反映给了总统,总统询问所有议员的意见,多数议员表示欠屁民的钱一定要还,于是总统发表声明,从国库中拿出一万元还债,国库总资产由100万变成99万。屁民乙拿到钱回去了Client函数返回

情况三:

总统突然挂了,议员接二连三的发现联系不上总统,于是各自发表声明,推选新的总统,总统大选期间政府停业,拒绝屁民的请求。

呵呵,到此为止吧,当然还有很多其他的情况,但这些情况总是能在 Paxos 的算法中找到原型并加以解决。

这也正是我们认为 Paxos 是 Zookeeper 的灵魂的原因。当然 ZKServer 还有很多属于自己特性的东西:Session,Watcher,Version 等等,需要我们花更多的时间去研究和学习。

 

 

 

 

阅读原文

为您推荐

友情链接 |九搜汽车网 |手机ok生活信息网|ok生活信息网|ok微生活
 Powered by www.360SDN.COM   京ICP备11022651号-4 © 2012-2016 版权