搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 分布式一致性算法-paxos

分布式一致性算法-paxos

2017-10-12
举报

在分布式环境中,每个节点都有可能假死、被杀死或者重启,并且各个节点之间的网络通讯也是不可靠的,可能出现消息丢失和传输不通等问题。在这种不可靠的环境中,如何就某个决议达成一致,并且不论发生什么错误,都能保持最终一致性,是很难的。大师Leslie Lamport发明了paxos算法,它能够保证不论多少节点出问题,都能保持一致性。并且在一半以上节点正常的情况下,系统能正常提供服务。

下面是paxos算法的介绍,我在学习过程中有很多疑问,都使用了加粗的匪夷所思做标注。建议先读一下大师的论文《Paxos Made Simple》和wike百科,建立对paxos的大概了解,以免被我不严谨的描述误导了。

角色

算法定义了client,proposer,acceptor,learner,leader角色。每个节点可以同时担任多个角色。

client:向分布式系统提出请求,并等待回复。举个例子,在分布式系统中一个写文件操作。 proposer:接收client的请求,封装成议案,然后试图说服acceptors通过议案。 acceptor:决定是否接受决议,如果过半数以上的acceptors通过议案,那么该议案被确定; learner:负责学习已经确定的议案; leader:paxos需要一个主proposer推进算法的进程。如果没有主proposer,paxos算法可能发生活锁问题。

算法的提出

划分角色后,保障一致性的算法可以描述成:

  1. 议案只有在被proposers提出后才能被批准

  2. 在一次Paxos算法的执行实例中,只确定一个议案

  3. learners只能学习被批准的议案

直观上,条件1和3实现容易;条件2该怎么实现呢?大师Leslie Lamport试图给出条件2的增强条件,并使条件在工程上实现起来更容易。大师的基本思路是:

P0:如果多数acceptors同意一个议案,那么议案被通过。因为两个多数派必然包含一个共同的acceptor,如果一个accetpor保证只接受一个议案,那么就可以保证只有一个议案被确定。

接下来,大师论文中用了一个显而易见,得到下面这个增强条件:

P1:一个acceptor必须接受(accept)第一次收到的议案。

这个条件是正确的,因为如果acceptor对于接收到的第一个议案都不接受,那么没法往下进行了。可是一个显而易见,将大师的思维历程都隐藏了,增强条件p1就这么匪夷所思的出来了。

然而条件p1是不完备的。假设有偶数个acceptor和2个议案,那么可能每个议案都获得一半acceptor的同意,都没能赢得多数派同意,也就不能最终确定哪个议案。该怎么对p1条件做约束,使得一定会有一个多数派同意一个议案呢?

匪夷所思的,作者没有对这个问题作出解答。而是直接给出来一个多数派同意一个决议后,怎么保证只确定一个决议,而不会是两个或者多个的增强条件。

P2:一旦一个议案被确定,那么之后批准的议案必须和它相同。

如果P1和P2都能够保证,那么条件2就能够保证。但是p2的描述还是不足以指导实践,继续增强条件。

P2a:一旦一个议案被确定,那么之后任何acceptor接受的议案必须和它相同。

如果一个议案被确定后。一个proposer和一个acceptor从休眠中苏醒,proposer提出一个新的议案,而acceptor还没有接受任何议案。根据P1,accetpor应当接受,根据P2a,则不应当接受,这种场景下P2a和P1有矛盾。于是需要换个思路,转而对proposer的行为进行约束:

P2b:一旦一个议案被确定,那么以后任何proposer提出的提案必须和它相同。

由于acceptor能接受的提案都必须由proposer提出,所以P2b蕴涵了P2a,是一个更强的约束。但是p2b的描述还是不足以指导实践,继续增强条件。

P2c:如果一个编号为n的议案被提出,那么存在一个多数派,要么他们中所有人都没有接受编号小于n 的任何议案,要么他们已经接受的所有编号小于n的议案中编号最大的那个议案和编号为n的议案相同。

大师用数据归纳法证明了P2c是P2b的充分条件(过程具体参考论文或者wiki)。P2c是一个可以指导工程实现的操作性更强的条件,它指明了proposer该怎么提出议案。根据P2c,proposer需要先和acceptors中的多数派通讯,获取acceptor最近一次接受的议案,然后再根据P2c的约定提出议案。

很明显,P2c的实现可以通过2阶段提交来完成。这时有一个问题。比如一个acceptor没有接受过任何议案,第一阶段proposer发送一个编号为n的议案的prepare给acceptor,acceptor同意了。但是在proposer进入第二阶段之前,acceptor接受了一个标号为n-1的议案。这种情况就违背了P2c约束条件,所以还需要对P1条件条件做更强的约束。

P1a:当且仅当acceptor没有回应过编号大于n的prepare请求时,acceptor接受编号为n的议案。

确定议案

算法分两阶段。

  1. prepare阶段:
    1.1 proposer选择一个议案编号n并将prepare请求发送给acceptors中的一个多数派
    1.2 acceptor收到prepare消息后,如果议案的编号大于它已经回复的所有prepare消息,则acceptor将自己上次接受的提案回复给proposer,并承诺不再回复小于n的提案;否则,回复拒绝消息。

  2. 批准阶段
    2.1 当一个proposer收到了多数acceptors对prepare的回复后,就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求,包括编号n和根据P2c条件生成的议案。如果根据P2c没有已经接受的议案,那么它可以自由决定议案。
    2.2 在不违背自己向其他proposer的承诺的前提下,acceptor收到accept请求后即接受这个请求

上面算法是大师论文中的,但是最后确定议案的过程没有写。我诚惶诚恐的加上一条:

2.3 如果proposer收到多数accetpor接受议案的回复,那么确定选出该议案,并将该议案内容发送给回复的acceptors。否则,重新进入prepare阶段。

学习议案

确定议案后,需要让所有的learner都知道。方法有很多:(1)最简单的方法是,acceptors接收到确定议案的消息,就发送给每个learners。缺点是这会产生大量的通知消息。(2)选择一个主learner,acceptors只需要通知主learner,然后由主learner通知其他的learners。这样可以减少通知消息,但是主learner会导致单点问题。如果主learner挂掉以后,acceptors需要等待选出一个新的主learner后,才能继续通知主learner,比较耗时(3)可以选取多个主learners,acceptors和多个主learners通讯。

活锁问题

有一种场景。两个proposers同时连续发送编号递增的议案,结果都没有被选中。proposer1使用标号n1完成第一个阶段,紧接着proposer2使用标号n2完成第一个阶段(其中n2>n1)。然后proposer1进入第二阶段,但是标号为n1的接受请求会被拒绝。proposer1被拒绝后,申请更高的标号n3(其中n3>n2),从完成第一阶段。这时proposer2进入第二阶段,但是标号为n2的接受请求也会被决绝。如果循环往复,造成活锁问题。

大师提出选取主proposer,让其来提交议案方法解决活锁问题。具体怎么选取主节点,大师认为太简单的,不屑于讨论。

算法学习总结

学习paxos算法花了很长时间,过了很多遍大师的论文《Paxos Made Simple》才明白了大致流程。感觉paxos主要难在两点上:

  1. lamport大师的论文只体现了思考的结果,每一步条件的强化都像神来之笔。刚开始想着根据大师的思路,加上自己的思考,能够跟上一两个步骤,但是后来发现自己想太多了。如果大师能够出一本书,将paxos算法思路的由来,一步步推理的过程和思考的时候遇到的坑,都一一道来,估计会更容易让别人理解。

  2. lamport大师的论文论述不够严谨。由于P1条件不完备,在某些情境下无法形不成多数派接受一个议案,导致没有议案被最终确定,这时候,应该继续探讨如何对P1条件做约束,保证一定会有一个议案被最终确定。可是大师却选择讨论议案被最终确定后,怎么保证之后不会有其他议案被确定。这是逻辑上的证明有问题。这个问题是一个大坑,一直到最后都没有明白其中的奥秘。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《分布式一致性算法-paxos》的版权归原作者「小勃子技术路」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注小勃子技术路微信公众号

小勃子技术路微信公众号:gh_507a968765be

小勃子技术路

手机扫描上方二维码即可关注小勃子技术路微信公众号

小勃子技术路最新文章

精品公众号随机推荐

举报