分布式多副本一致性协议:paxos
黑客画家 发表于1个月前
分布式多副本一致性协议:paxos
  • 发表于 1个月前
  • 阅读 356
  • 收藏 24
  • 点赞 1
  • 评论 0

免费在线直播教学: java    web前端    c++   python   ios!>>>   

一、前言

     分布式多副本一致性在现实应用中是非常重要的,它既可以保证数据节点无单点(HA)时还能保证数据节点的一致性。此类协议比较著名的有paxos、raft和zab(zookeeper实现)等。其中,paxos允许多点写,而raft则是会先选举出一个leader,所有的写都会通过leader完成。

      本文会先介绍paxos思想,以后还会介绍raft。关于paxos的文章已经很多了,而且讲解的风格和方式不尽相同。我发现,如果单纯从纯理论角度来分析paxos,虽然在论证上会严谨一些,但是也导致即使你写了很大的篇幅,最终还是达不到想要的效果,最终还是:晦涩难懂。这其实也是paxos和raft的另一个区别,相对而言,raft从理论上就比paxos简单易懂的多。

      本文不准备从理论角度剖析paxos算法原理,我会尝试使用图形(伪代码)的方式给让大家对paxos有一个宏观的把握,同时,我在阅读了很多paxos文章之后,发现一篇以现实场景为角度讲解paxos的文章,我将其稍微修改了一下引用在这里。我相信,通过这两种角度,你的脑海中应该觉得paxos不再神秘。

二、paxos概念

      首先来必须看一下Lamport对paxos算法的文字版描述。

阶段一:

1、Proposer选择一个提案编号为Mn,然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求。

2、如果一个Acceptor收到一个编号为Mn的Prepare请求,且编号Mn大于该Acceptor已经响应的Prepare请求的编号,那么它就会将已经批准(accept)的最大编号的提案作为响应反馈给Proposer,同时该Acceptor会承诺不会再批准(accept)任何编号小于Mn的提案。

阶段二:

1、如果Proposer收到来自半数以上的Acceptor对其发出的编号为Mn的Prepare请求的响应,那么它就会发出一个针对[Mn,Vn]提案的Accept请求给Acceptor。注意:Vn的值就是收到的Prepare响应中编号最大的提案的值,如果响应中不包含任何提案,那么它就是任意值。

2、如果Acceptor收到这个针对[Mn,Vn]提案的Accept请求,只要改Acceptor尚未对编号大于Mn的Prepare请求作出响应,它就可以通过这个提案。

 注意:

Acceptor是一个集合(即不止一个Acceptor)。之所以要过半,是因为,任意的过半的集合都至少会有一个公共的交集,这适用于分区脑裂等场景。 

 

      是的,以上就是paxos算法的完整描述,是不是觉得非常“简单”,但是细细思考起来又会觉得比较抽象?下面我把上面的文字整理成图形伪代码的方式:  

                     

三、现实中的paxos

      下面的故事我是引自:http://www.cnblogs.com/esingchan/p/3917718.html,其中做了少许修改。

      假如有一群驴友(也就是前文提到的Proposer)要决定中秋节去旅游,这群驴友分布在全国各地,假定一共25个人,分别在不同的省,要决定到底去拉萨、昆明、三亚等等哪个地点(会合时间中秋节已经定了,此时需要决定旅游地)。最直接的方式当然就是建一个QQ群,大家都在里面投票,按照少数服从多数的原则。这种方式类似于“共享内存”实现的一致性,实现起来简单,但Paxos算法不是这种场景,因为Paxos算法认为这种方式有一个很大的问题,就是QQ服务器挂掉怎么办?Paxos的原则是容错性一定要很强。所以,Paxos的场景类似于这25个人相互之间只能发短信,需要解决的核心问题是,哪怕任意的一部分人(Paxos的目的其实是少于半数的人)“失联”了,其它人也能够在会合地点上达成一致。好了,怎么设计呢?

      这25个人找了另外的5个人(当然这5个人可以从25个人中选,这里为了描述方便,就单拿出另外5个人),比如北京、上海、广州、深圳、成都的5个人,25个人都给他们发短信(短信可以丢失,但一定不会被篡改),告诉自己倾向的旅游地。这5个人相互之间可以并不通信,只接受25个人发过来的短信。这25个人我们称为驴友,那5个人称为队长(也就是前文提到的Acceptor)。

      先来看驴友的逻辑。驴友可以给任意5个队长都发短信,发短信的过程分为两个步骤:

      第一步(申请阶段):询问5个队长,试图与队长沟通旅游地。因为每个队长一直会收到不同驴友的短信,不能跟多个驴友一起沟通,在任何时刻只能跟一个驴友沟通,按照什么原则才能做到公平公正公开呢?这些短信都带有发送时间(作为提案编号),队长采用的原则是同意与短信发送时间最新的驴友沟通,如果出现了更新的短信,则与短信更新的驴友沟通。总之,作为一个有话语权的人,只有时刻保持倾听最新的呼声,才能做出最明智的选择。在驴友发出短信后,等着队长回复。某些队长可能会回复说,你这条短信太老了,我不与你沟通(也可能直接不回复);有些队长则可能返回说,你的短信是我收到的最新的,我同意跟你沟通。对于后面这种情况,队长还得返回自己决定的旅游地(如果此时队长已经有决定的旅游地的话)。关于队长是怎么决定旅游地的,后面再说。

      对于驴友来说,第一步必须至少有半数以上队长都同意沟通了,才能进入下一步。否则,你连沟通的资格都没有,一直在那儿狂发吧。你发的短信更新,你获得沟通权的可能性才更大。

      因为至少有半数以上队长(也就是3个队长以上)同意,你才能与队长们进行实质性的沟通,也就是进入第二步;而队长在任何时候只能跟1个驴友沟通,所以,在任何时候,不可能出现两个驴友都达到了这个状态。当然,你可以通过狂发短信把沟通权抢了。

      对于获得沟通权的那个驴友(称为A),那些队长会给他发送他们自己决定的旅游地(也可能都还没有决定)。可以看出,各个队长是自己决定旅游地的,队长之间无需沟通。

      第二步(沟通阶段):这个幸运的驴友收到了队长们给他发的旅游地,可能有几种情况:

      第一种情况:跟A沟通的队长们(不一定是全部5个队长,但是半数以上)全部都还没有决定到底去哪儿旅游,此时驴友A心花怒放,给这些队长发第二条短信,告诉他们自己希望的旅游地(比如马尔代夫);

      可能会收到两种结果:一是半数以上队长都同意了,于是表明A建议的马尔代夫被半数以上队长都同意了,整个决定过程完毕了,其它驴友迟早会知道这个消息的,A先去收拾东西准备去马尔代夫;除此之外,表明失败。可能队长出故障了,比如某个队长在跟女朋友打电话等等,也可能被其它驴友抢占沟通权了(因为队长喜新厌旧嘛,只有要更新的驴友给自己发短信,自己就与新人沟通,A的建议队长不同意)等等。不管怎么说,苦逼的A还得重新从第一步开始,重新给队长们发短信申请。

      第二种情况:至少有一个队长已经决定旅游地了,A可能会收到来自不同队长决定的多个旅游地,这些旅游地是不同队长跟不同驴友在不同时间上做出的决定(比如1个同意去昆明,1个同意去三亚,2个同意去拉萨,1个没搭理我),A作为一个高素质驴友,也不按照自己的意愿乱来了(Paxos的关键所在,后者认同前者,否则整个决定过程永无止境),虽然自己原来可能想去马尔代夫等等。就给队长们发第二条短信的时候,告诉他们自己希望的旅游地(就是自己收到的那堆旅游地中时间最新决定的那个)。(比如,去昆明那个是北京那个队长前1分钟决定的,去三亚的决定是上海那个队长1个小时之前做出来的,于是顶昆明)。驴友A的想法是,既然有队长已经做决定了,那我就干脆顶最新那个决定。

      从上面的逻辑可以看出,一旦某个时刻有半数以上队长同意了某个地点比如昆明,紧跟着后面的驴友B继续发短信时,如果获得沟通权,因为半数以上队长都同意与B沟通了,说明B收到了来自半数以上队长发过来的消息,B必然会收到至少一个队长给他发的昆明这个结果(否则说明半数以上队长都没有同意昆明这个结果,这显然与前面的假设矛盾),B于是会顶这个最新地点,不会更改,因为后面的驴友都会顶昆明,因此同意昆明的队长越来越多,最终必然达成一致。(注意集合的概念,半数以上必定会有一个交集)

      看完了驴友的逻辑,那么队长的逻辑是什么呢?

      队长的逻辑比较简单。

      在申请阶段,队长只会选择与最新发申请短信的驴友沟通,队长知道自己接收到最新短信的时间,对于更老的短信,队长不会搭理;队长同意沟通了的话,会把自己决定的旅游地(或者还没决定这一信息)发给驴友。

      在沟通阶段,驴友C会把自己希望的旅游地发过来(同时会附加上自己申请短信的时间提案编号,比如3分钟前),所以队长要检查一下,如果这个时间(3分钟前)确实是当前自己最新接收到申请短信的时间(说明这段时间没有驴友要跟自己沟通),那么,队长就同意驴友C的这个旅游地了(比如昆明,哪怕自己1个小时前已经做过去三亚的决定,谁让C更新呢,于是更新为昆明);如果不是最新的,说明这3分钟内又有其它驴友D跟自己申请了,因为自己是个喜新厌旧的家伙,同意与D沟通了,所以驴友C的决定自己不会同意,等着D一会儿要发过来的决定吧。

      Paxos的基本思想大致就是上面的过程。可以看出,其实驴友的策略才是Paxos的关键。让我们来跟理论对应一下。

      Paxos主要用于保证分布式存储中副本(或者状态)的一致性。副本要保持一致,那么,所有副本的更新序列就要保持一致。因为数据的增删改查操作一般都存在多个客户端并发操作,到底哪个客户端先做,哪个客户端后做,这就是更新顺序。如果不是分布式,那么可以利用加锁的方法,谁先申请到锁,谁就先操作。但是在分布式条件下,存在多个副本,如果依赖申请锁+副本同步更新完毕再释放锁,那么需要有分配锁的这么一个节点(如果是多个锁分配节点,那么又出现分布式锁管理的需求,把锁给哪一个客户端又成为一个难点),这个节点又成为单点,岂不是可靠性不行了,失去了分布式多副本的意义,同时性能也很差,另外,还会出现死锁等情况。

      所以,说来说去,只有解决分布式条件下的一致性问题,似乎才能解决本质问题。

      如上面的例子,Paxos解决这一问题利用的是选举,少数服从多数的思想,只要2N+1个节点中,有N个以上同意了某个决定,则认为系统达到了一致,并且按照Paxos原则,最终理论上也达到了一致,不会再改变。这样的话,客户端不必与所有服务器通信,选择与大部分通信即可;也无需服务器都全部处于工作状态,有一些服务器挂掉,只有保证半数以上存活着,整个过程也能持续下去,容错性相当好。因此,以前看有的博客说在部署ZooKeeper这种服务的时候,需要奇数台机器,这种说法当然有一定来源背景,比如如果是5台,那么任意客户端与任意其中3台达成一致就相当于投票结束,不过6台有何不可?只是此时需要与4台以上达成一致。

四、工程中的paxos

      paxos的缺点之一就是理论简单、工程化难(这点和raft相比就很明显了),现实中大多数的paxos算法工程实现中都多多少少针对工程实现做了些许修改。国内号称没有对算法本身进行改动的paxos实现之一就是微信开源的phxpaxos( https://github.com/tencent-wechat/phxpaxos )。以后有机会专门写文章分析其源码。

 

 

 

共有 人打赏支持
粉丝 43
博文 44
码字总数 116360
×
黑客画家
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: