美文网首页zookeeper
分布式系统理论:一致性协议Paxos

分布式系统理论:一致性协议Paxos

作者: 95a6af369245 | 来源:发表于2019-01-10 17:27 被阅读122次

      Paxos算法是莱斯利·兰伯特(Leslie Lamport)于1990年提出的一种基于消息传递的一致性算法。 Paxos 算法是一个解决分布式系统中,多个节点之间就某个值(注意是某一个值,不是一系列值)达成一致的通信协议。能够处理在少数派离线的情况下,剩余的多数派节点仍然能够达成一致。 Lamport是通过故事的方式提出Paxos 问题:

      希腊岛屿Paxon 上的执法者在议会大厅中表决通过法律(一次paxos过程),并通过服务员(proposer)传递纸条的方式交流信息,每个执法者会将通过的法律记录在自己的账目上。问题在于执法者和服务员都不可靠,他们随时会因为各种事情离开议会大厅(服务器拓机或网络断开),并随时可能有新的执法者进入议会大厅进行法律表决(新加入机器),使用何种方式能够使得这个表决过程正常进行,且通过的法律不发生矛盾(对一个值达成一致)。 注意:paxos过程中不存在拜占庭将军问题(消息不会被篡改)和两将军问题(信道可靠)。 paxos 协议中有四种角色:

      client 议题产生者,产生一个待分布式系统达成一致的值v

      proposer 提议者,用client产生的值v,向acceptor发出提议

      acceptor 决策者,决定是否接受proposer的提议,大多数接受了提议,结果达成一致,达成一致的结果不可更改

      learner 决策学习者,学习最终达成一致的结果。一旦学习成功,关闭对应的paxos过程(paxos instance),并通知acceptor(或acceptor主动向learner获取)。

      这四种角色中,proposer和acceptor比较重要,协议主要的交互逻辑都在这两种角色中。

      paxos 是一个两阶段的通信协议:

      第一阶段 Prepare

      client产生一个值v,并告知proposer,我这里产生了一个待accept的值。

      proposer收到通知后,生成一个全局唯一并且递增的提案ID,带着这个ID(不需要携带v)向集群中的所有acceptor发送PrepareRequest请求。 acceptor收到PrepareRequest请求后,检查一下之前接收到的提案ID(包括第一阶段和第二阶段),新接收的提案ID用n表示,之前接收到的提案ID用N表示。如果n = N,返回拒绝,并携带N的值。如果n N,把n记录下来,以后不再接收提案ID比n小的提议,这时分两种情况:

      之前没有accept任何值v,返回可以接收提议

      之前已经accept过值,返回可以接收提议,并携带已经accept的,并且提案ID最大的值

      第二阶段 Accept

      如果proposer收到大多数acceptor的拒绝应答,回到第一阶段,根据接收到的最大的N,把提案ID增大,继续发送PrepareRequest。

      如果proposer收到大多数acceptor可以接收提议的应答,从多个应答中选出提案ID最大的值(第一阶段如果acceptor已经accept过值,会返回提案ID最大的值),作为提案值。如果应答中没有值,选择client产生的值v作为提案值。然后携带当前的提案ID,一起向集群中所有acceptor发送AccpetRequest请求。 对这段话进行解释:第一阶段client产生的值v,不一定作为Accept阶段的提案值。为了更快的达成一致,如果之前已经accept了值,那么proposer会倾向于把提案值修改为之前接受的值。各个proposer不是针锋相对,而是合作共赢。 acceptor收到AccpetRequest后,检查请求中携带的提案ID,如果此提案ID大于或等于acceptor记录的提案ID(在第一阶段和第二阶段,acceptor记录最大的提案ID),接受提议并记录提案ID和提案值。否则拒绝,并返回记录的提案ID。 proposer收到大多数acceptor接受提案的应答,形成决议,达成一致。

      如果proposer收到大多数acceptor拒绝的应答,回到第一阶段,把提案增大(增加幅度依据acceptor返回的提案ID),发送PrepareRequest。

      举个例子帮助理解paxos协议,把整个paxos协议的流程想象成一次竞标。有两个老板(client),每个老板都有一个属于自己的秘书(proposer),还有3个政府官员(acceptor)。

      第一阶段

      两个老板(client)分别提出议题:“XXX项目我要中标”,各自的秘书(proposer)带着现金(提案ID),去找政府官员(acceptor)。

      作为政府官员(acceptor),谁给的钱多答应给谁中标(只是口头答应,并没有签约)。钱少的直接拒绝。

      场景1:秘书p1带着10000美金去找3个官员a1、a2、a3,这时候还没有人来找过a1、a2、a3,所以这3个官员直接就答应了p1,并告诉p1他们之前没有接受过任何提议。这样p1在一阶段获得了全票支持。过一会,秘书p2带着8000美金去找3个官员,3个官员一看只有8000美金,直接拒绝p2,告诉p2别人已经出价10000。

      场景2:p1的行为和第一个场景相同。p2带着12000美金去找3个官员,3个官员一看p2给的钱比p1多,把p2的钱记下来,很高兴的告诉p2,可以接收p2的提议。这样在第一阶段p1和p2都获得了全票支持。

      场景3:p1和p2同时带着10000美金去找3个官员,p1先找到了a1、a2,此时没有人找过a1和a2,a1和a2答应p1,告诉p1他们之前没有接受过任何提议。p2在p1之前找到了a3,之前没有人找过a3,a3答应p2,告诉p2他之前没有接受过任何提议。这时候p1也找到了a3,a3一看和之前收到的钱一样多,拒绝了p1。同样,在p2找到a1和a2时,应为钱数一样,也被拒绝。最终,在第一阶段,p1获得2票(a1和a2),超过半数,p1可以进入第二阶段。p2获得1票,少于半数,p2被打回第一阶段。

      第二阶段

      场景1:在第一阶段p1获得了全票支持,p1带着老板的议题去找官员签合同,并告诉官员之前已经给了10000美金。官员看了一下收款记录,没错是10000美金,3个官员和p1成功签约,达成一致。在第一阶段p2被拒绝,这时p2回到第一阶段,带了12000美金去找官员。官员一看12000比刚才接受的10000多,告诉p2,你的钱多,可以接受你的议题,但是之前已经接受了p1的议题,p1的议题内容为“XXXXXX”。p2看了下p1的议题,觉得自己的老板没前途,干脆跟着p1的老板干算了,于是把自己的议题修改为p1的议题(为了更快达成一致)。p2带着修改之后的议题去找官员,告诉官员之前给了12000。官员看了一下记录,没错是12000,接受了p2的议题(这时p2的议题和p1一样,虽然官员同时接受了p1和p2,但是系统仍然是一致的)。

      场景2:在第一阶段p1获得了全票支持,p1带着老板的议题去找官员签合同,并告诉官员之前已经给了10000美金。官员看了一下收款记录,记录上写的是12000,于是告诉p1,已经有人出了12000,我们不能accept你的提议。在第一阶段p2也获得了全票支持,这时候p2来找官员,告诉官员之前给了12000,官员核实了一下记录,发现没错,接受了p2的议题。p1被拒绝后,回到第一阶段,带了14000美金去找官员。官员一看14000比刚才接受的12000多,告诉p1,你的钱多,可以接受你的议题,但是之前已经接受了p2的议题,p2的议题内容为“XXXXXX”。p1看了下p2的议题,觉得自己的老板没前途,干脆跟着p2的老板干算了,于是把自己的议题修改为p2的议题(为了更快达成一致)。p1带着修改之后的议题去找官员,告诉官员之前给了14000。官员看了一下记录,没错是14000,接受了p1的议题(这时p1的议题和p2一样,虽然官员同时接受了p1和p2,但是系统仍然是一致的)。

      场景3-1:在第一阶段p1获得a1、a2的应答,p1带着老板的议题去找a1、a2签合同,并告诉a1、a2之前已经给了10000美金。核实之后,a1和a2接受了p1的议题。由于大多数官员接受了p1的议题,所以p1的议题被确定接受。

      场景3-2:在第一阶段p1获得a1、a2的应答,p1带着老板的议题去找a1、a2签合同。但是p2在被打回第一阶段后,以很快的速度带着12000美金,赶在p1之前再次找到a1和a2以及a3。a1、a2、a3答应p2,并把记录金额修改为12000,并告诉p2,我们没有接受任何议题(p1还在签约途中)。这时p1终于找到了a1和a2,准备签约,但是a1和a2告诉p1,我们刚才收了12000,比你给的10000要多,拒绝接受你的议题,p1被打回第一阶段。在第一阶段p2获得全票,于是带着议题去找a1、a2、a3签约,a1、a2、a3核实金额之后,成功签约,达成一致。

      paxos协议中的活锁问题

      在上边描述的场景中,如果在官员签约之前,p1和p2一直不停的往上加金额,就算进入第二阶段,也会因为有更高的报价,导致签约失败被打回第一阶段。就像拍卖会中,多个买家一直往上飙价格,最后一件东西都没有卖出去。这种情况称为活锁,没有产生阻塞,但是一直无法达成一致。

      有三种解决方案:

      在被打回第一阶段再次发起PrepareRequest请求前加入随机等待时间。

      设置一个超时时间,到达超时时间后,不再接收PrepareRequest请求。

      在proposer中选举出一个leader,通过leader统一发出PrepareRequest和AcceptRequest。

      multi paxos

      一次paxos过程(paxos instance)只能对一个值达成一致。multi paxos是运行多个paxos instance来对多个值达成一致。

      下边以MySQL组复制为例,说明multi paxos。

      MySQL组复制中存在多个master,可以同时接受client写入和读取数据,并且可以保证多个master中数据一致,每一次写入数据都会生成一条log日志,通过paxos协议进行一致性处理,达成一致之后完成log复制。针对一系列操作,需要运行多次paxos过程(paxos instance),需要引入一个ID来标识相应的paxos instance,这里用logID表示。每一次写入操作,都生成一个logID与log日志对应,也同时与paxos instance对应,logID全局唯一且自增。

      有了logID之后,每个paxos instance独立运行,可以对每条log日志达成一致。这样问题貌似已经解决了,但是还有优化的空间。

      每一次paxos instance都是一个两阶段过程(prepare和accept),所有proposer地位平等,都可以提出议题。在有多个proposer同时提出议题时,有很大概率冲突,每次冲突都会重新执行prepare阶段,网络和性能开销较大。同时paxos协议本身存在活锁问题,有可能导致一个议题始终无法达成一致。为了解决这两个问题,multi paxos中引入了leader的概念,从多个proposer中选举出一个leader作为提议代表,每个提议都通过leader发出。这样的话,解决了活锁问题(活锁问题的第三个解决方案)。因为提议都是通过leader发出,只要leader保证提案ID自增,就可以跳过prepare阶段,直接进行accept阶段(两阶段变为一阶段)。

      那么问题来了,如何选举leader?运行一次paxos instance,提议的v就是“选举自己为leader”。但是还有问题,一次paxos instance只能对一个值达成一致。举个例子:A、B、C三台机器,运行paxos选举leader。第一次选举产生结果,A是leader。之后A拓机,再次运行paxos,选举的结果还是A是leader。运行多个paxos instance(multi paxos)可以选举出不同的leader,但是multi paxos需要选举出一个leader来优化网络损耗和活锁的问题,这里产生一个问题递归依赖。

      换个思路,给每一个达成一致的值v一个过期时间,达到过期时间清空v,这样用一个paxos instance就可以选出不同的leader。每台机器上都启动一个倒计时T,leader在存活状态下,不断重置T,T在倒计时为零时清空上次选举的结果,并发起选举。

      上边简单说明了一种选举leader的算法,通过选举leader,可以提高paxos的性能(两阶段变为一阶段),并解决活锁问题。paxos的正确性不依赖于选举结果,在选举失败或者同时选出多个leader的情况下,退化为普通paxos。

      总结

      paxos协议可以归纳为几个原则:

      不接受旧值(通过递增ID确定新旧)

      为了更快达成一致,proposer会把值修改为最有可能达成一致的值

      只有多数派接受了值,值才达成一致

      一旦一个值达成一致,不可更改

      paxos是一致性协议的基础,其他的协议(raft、zab等)都是paxos的改进版本。paxos侧重理论,实现paxos非常困难。谷歌chubby论文中提到,从paxos出发,在实现过程中处理了很多实际中的细节之后,已经变成另外一个算法了,这时候正确性无法得到理论的保证。所以才出现了许多基于paxos的改进算法。

    相关文章

      网友评论

        本文标题:分布式系统理论:一致性协议Paxos

        本文链接:https://www.haomeiwen.com/subject/upnarqtx.html