我相信有很多小伙伴是第1次听到Paxos这个名词,这个Paxos算法到底是个什么东西呢?
它就是一个基于消息传递的一致性算法,由Leslie Lamport在1990年提出(是的,你没有看错,这个Paxos的算法已经是30多年前的算法了),但是直到近几年才被广泛应用于分布式计算中。 Zookeeper本身是Apache开源的一个项目(受到Google Chubby项目的影响),它的和核心算法就是采用Paxos算法。虽然这个算法已经诞生了30多年,但是Paxos算法依然被认为是到目前为止唯一的分布式一致性算法,其它的相关算法都是Paxos的改进或简化。
那么如此优秀的一个算法,为什么沉寂了几十年以后才火起来?因为写这个算法的哥们是以讲故事的形式来陈述这个算法的核心思想,但是传统意义上的论文应该是有非常严谨的引用数据,以及各种复杂的公式来证明推导论文核心观点的正确性。但是这个哥们他就写的很随意,就是讲故事而已,他认为并不是每个人都受过非常高等的教育,也不是每一个人都在数学公式方面有着过人的天赋,所以他采用的最通俗易懂的说故事的方式。但是一个故事作为论文来说,在学术界肯定是不被接受,所以他的这篇论文一直没有被提名过。但是企业级在选型的时候肯定能选择最实际的,所以他的这个算法还是被逐渐的广泛应用起来。我记得好像是在2000年左右这个算法第1次被人使用,然后在随后的十几二十年里面才慢慢慢慢逐渐的推广起来,再加上后来这个算法作者的一个好朋友,帮他把这个论文稍微修饰了一下,补充了一些学术界可以接受的公式推导在里面,所以逐渐的这个算法渐渐的就越来越多的人去使用。
好了,扯完了历史,我们来开始正式的说一下,Paxos这个算法。不过在说这个算法之前,我们必须要先达成一个共识:就是没有拜占庭将军的问题,这个问题是由莱斯利·兰伯特提出的点对点通信中的基本问题,含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的——就是说Paxos只有在一个可信的计算环境中才能成立,这个环境是不会被入侵所破坏的,没有黑客,没有病毒,所有的计算结果和网络通信都是健康的,可信的。
Paxos描述了这样一个场景:有一个叫做Paxos的小岛上面住了一批居民,岛上面所有的事情由一些特殊的人决定,他们叫做议员。议员的总数是确定的,不能更改。岛上每次环境事务的变更都需要通过一个提议,每个提议都有一个编号,这个编号是一直增长的,不能倒退。每个提议都需要超过半数的议员同意才能生效。每个议员只会同意大于当前编号的提议,包括已生效的和未生效的。如果议员收到小于等于当前编号的提议,他会拒绝,并告知对方你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号,他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标:保证所有的议员对于提议都能达成一致的看法。
小岛 –> ZK Server Cluster
议员 –> ZK Server
提议 –> ZNode Change(Create/Delete/SetData…)
提议编号 –> Zxid(ZooKeeper Transaction Id)
正式法令 –> 所有节点及其数据
接下来我会把Paxos算法拆成两个小段来讲解,会比较清楚一点:
① 当议会开始运作,所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议:将电费设定为1元/度。他首先看了一下记事本:当前提议编号是0,那么我的这个提议的编号就是1,于是他给所有议员发消息:1号提议,设定电费1元/度。其他议员收到消息以后查了一下记事本,哦,当前提议编号是0,这个提议可接受,于是他记录下这个提议并回复:我接受你的1号提议,同时他在记事本上记录:当前提议编号为1。
② 发起提议的议员收到了超过半数的回复,立即给所有人发通知:1号提议生效!收到的议员会修改他的记事本,将1号提议由记录改成正式的法令,当有人问他电费为多少时,他会查看法令并告诉对方:1元/度。
为什么我拆成两个小段,就因为在上述的俩小段中隐藏了一个两阶段提交的概念:第①阶段是让大家都写日志并且给我一个回复,但是根源上这件事情还没有定下来。只有当我在第②阶段收到过半回复确认的时候,我才有信心确定下来。
举一个比较好理解一点的例子:假设你在家里面宣布一件事情,然后喊了一嗓子,有的人在客厅,他听到了他知道了,但是有的人在厨房,有的人在厕所他不知道。然后这个时候你在等待过半通过的事情那永远等待不到,因为在厕所跟厨房的那个人听不到,他永远不会给你确认的回复。没有过半那这件事就不成立,不成立的话就得回滚,但是偏偏在回滚的时候,在客厅的那几个人又出去了……
所以必须采用两阶段提交+过半通过的方式来确保每一个提案的准确性,只有这样才能相对舒服一些在分布式情况下解决数据传递的问题:假设总共有三个议员S1-S3,S1和S2同时发起了一个提议:1号提议,设定电费。S1想设为1元/度, S2想设为2元/度。结果S3先收到了S1的提议,于是他做了和前面同样的操作。紧接着他又收到了S2的提议,结果他一查记事本,咦,这个提议的编号小于等于我的当前编号1,于是他拒绝了这个提议:对不起,这个提议先前提过了。于是S2的提议被拒绝,S1正式发布了提议:1号提议生效。S2向S1或者S3打听并更新了1号法令的内容,然后他可以选择继续发起2号提议。
貌似关键的概念都能一一对应上,但是等一下,Paxos岛上的议员应该是人人平等的吧,而ZK Server好像有一个Leader的概念。没错,其实Leader的概念也应该属于Paxos范畴的。如果议员人人平等,在某种情况下会由于提议的冲突而产生一个活锁(可以这么理解: S1,S2,S3都发起了一个提议,然后人人都为自己的提议投了一票,这三个提议都是一票,所以没有谁大于谁的概念,所以这三个提议失败了,那都失败了以后这三个人又重复的又继续提议,从而产生恶性循环永远过不了半),Paxos的作者在文章《The Part-Time Parliament》中阐述了这个问题并给出了解决方案——在所有议员中设立一个总统,只有总统有权发出提议,如果议员有自己的提议,必须发给总统并由总统来提出。如此以来:我们又多了一个角色:总统,也就是ZK Server Leader。那么整个Paxos算法里面最核心的问题就来了,这个总统是怎么选出来的?这玩意儿一两句话讲不清楚,下一篇我再详细讲解。
那么通过上面的一些举例说明,我们大致了解了Paxos算法,那么基于这个算法整个Zookeeper集群的具体实施如下:
① 客户端连接到某一个follower服务get某个节点的数据,Zookeeper服务会从本地的数据中将数据查询出来返回给客户端,并且告诉客户端,说我这儿的数据并不是最新的,如果你想要更新的数据,我去跟leader同步一下,然后再告诉你。
② 客户端连接到某一个follower服务请求写入操作,follower查询是没问题,但是写入的话他没这个权利。follower就会将这个请求转给leader, leader就会将这个请求通过两阶段提交和过半通过的方式征求大家的意见,只要有半数以上的follow同意这个写入操作, leader就会再次发出声明进行这个写入操作。当所有的步骤都在集群内部消化完以后,最终才给客户端返回OK。
③ 当leader宕机以后,所有的follower就会选举出新的leader来代替原来的leader,而在选举新的leader的这个过程当中不对外进行业务上的服务提供。
这里顺便多说一句,在整个Zookeeper的集群当中,除了leader跟follower以外,还有第3种叫observer,可以理解成没有投票权利的follower。设立observer的目的就是为了严格控制follower的数量:因为follower会参与投票,理论上投票的机器越多,那么投票的速度就越慢。为了保证能够在极短的时间内选出新的leader,一般follower的台数控制在个位数左右,我不管你整个集群中有多少台机器,有100台也好,1000台也好,只有一个leader和个位数的follower,其余的全是observer。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/111941.html