搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发

晦涩的Paxos

磨链mochain社区 2018-06-28

什么是paxos?


Paxos是用于解决分布式系统中一致性问题的共识算法(Consensus Algorithm),其最基本的功能是为了在多个进程之间对某个值达成一致。通过这个最基本功能,就可以在多个进程之间进行数据库、状态机、账本(区块链)等对象的同步。

注意,Paxos不追求值的正确性、权威性、及时性,只追求一致性。

“共识”这个词不仅仅指结果,而且还代表不同进程对于各种处理达成的协议于限制。

Paxos的推导与理解过程比较晦涩难懂,每个人学习之后都会有自己的理解角度,下文是个人经过一个礼拜学习之后自己的一些简单理解,整理记录下来。


基本概念与角色


ID:相互不冲突的提案编号,用于区分不同轮次的提案。

Value:提案的值,即最后试图达成共识的候选结果。

Proposer:提案发起者,用于提出议案,提案的内容为:令 x=value,对同一轮提案,最多提议一个value 。Proposer角度看,提案分为两个阶段:Prepare阶段、Propose阶段。一轮提案的value不一定非要是Proposer自己提议的value。

Acceptor:提案投票者,有 N 个。Proposer 提出的 x=value 提案必须获得超过半数(N/2+1)的 Acceptor接受后才能被chosen。Acceptor 之间完全对等,在独立的时间轴执行提案投票。从Acceptor角度看,投票分两阶段进行:Promise阶段、Accept阶段。

Learner:提案学习者。一个提案超过半数accpetor通过即可被chosen,其他未确定的Acceptor可以通过learner来同步结果。



协议流程


以下流程针对每个进程(多个Proposer、多个Acceptor)都是独立执行的,进程之间的处理逻辑可能是顺序执行的,也可能是交错的,这就带来了整体的不确定性。Paxos就是通过增加各种约束处理条件,降低不确定性,使得多进程之间通过多轮投票,最终能够达成一致。


---


Prepare阶段


A:Proposer选择一个提案编号n,向所有的Acceptor广播Prepare(n)请求。

B:Acceptor收到Prepare(n)请求,若提案编号n比之前接收的Prepare请求都要大,则承诺(Promise,将n记录下来)将不会接收提案编号比n小的提议,并且带上之前Accept的提议中编号小于n的最大的提案value。如果n比之前接受的提案编号小,则不予理会。

Propose阶段


A:Proposer收到Acceptor的Promise

如果未超过半数的accpetor回复承诺(Promise),本次提案失败;

如果超过半数的Acceptor回复承诺,又分为不同情况:

如果(回复承诺的)所有Acceptor都未接收过value(都为null),那么向所有的Acceptor发起(Propose)自己的value和提案编号n。

如果有部分Acceptor接收过value,那么从接受过的value中选择提案编号最大的value作为本次提案的value,提议编号仍然为n(即:此时Proposer不能提议自己的value,只能信任Acceptor通过的value,以达成收敛的效果。)

B:Acceptor接收到提议后,如果该提案编号不等于自身当前承诺的编号(第一阶段记录的),不接受该请求,相等则将提案的value写入本地。


如何理解?


Leslie Lamport的论文《Paxos made simple》是通过一步步的问题推导,缩写约束范围来解释并数学证明Paxos的,虽然严格但还是比较抽象,理解起来还是比较吃力。




分布式抢占锁


个人更愿意把Paxos理解成一个分布式抢占锁机制。

传统上在非分布式环境中,我们往往用事务来维护系统的一致性。而Lock机制是最常用的一种控制数据有序修改的手段,因此,数据的修改可以分为两个阶段:加锁阶段(多个Proposer根据在单个Acceptor️收到加锁请求的时间先后顺序占用锁,此时系统有全局时钟)、修改阶段(并释放锁)。在Paxos中,Prepare阶段可以理解为Proposer向Acceptors集合请求加锁阶段,Propose阶段相当于修改阶段,以这样的角度看,就不会对为什么Paxos设计成两阶段协议有太多疑惑了。


但对于分布式系统而言,除了缺乏全局时钟外,还有容错问题:修改者与资源都会有多个副本,并且都有可能失效。对于Paxos而言,则表现为:


(1)Acceptor有多个,因此Paxos要求提案获得大多数Acceptor的Promise,才算加锁成功;这也比较好理解:如果小于半数,则可能存在两个提案同时加锁的情况。

(2)每个Proposer都有可能失效,不能影响其他Proposer工作。传统的独占锁在获得锁定权的Proposer失效时会导致系统死锁,因此不符合要求,因此Paxos选择将独占锁改成抢占锁机制,这意味着需要引入某种可以全局有效的抢占机制。


为了全局性的对提案进行排序,Paxos引入提案编号概念,编号由每个Proposer本地产生并且递增,具有全局唯一性并且可比较排序。Paxos规定高编号的提案可以抢占编号低的提案的锁(反过来也行,但总需要一个排序规则),使得低编号提案加锁失败(无法完成大多数Acceptor的提案确认),这样就不会出现某个Proposer的失效导致的死锁情况的发生(为什么要抢占?因为Proposer之间是孤立的,而且你永远不知道某个Proposer会在何时失效)。


如何理解提案编号的概念?相当于Paxos人为的为分布式系统设定了一个非集中式的全局时钟,所有的Acceptor进程均认可这种事先安排的顺序对提案的抢占锁进行处理。即然是时钟,前面发生的提案就不能跑到后面来处理。这个时钟在不同Acceptor之间并不精确同步,只能保证每个Acceptor节点以一种有序的方式处理Proposer对锁的抢占,保证每个Accepor上每个提案不受低编号的影响,而只受高编号的影响,以最快的在Acceptor集合内达成提案的收敛。


从Proposer角度看,所有编号的提案,都在快马加鞭的试图尽快的加锁(prepare)并获得大多数Acceptors的确认(accept),以免被更高ID的提案给抢占。Proposer之间没有任何协调机制,只能通过Acceptors完成有限交流(低编号提案value向高编号提案的传播)


由于每个Paxos过程会以各种组合交叉在一起,局面会比较复杂,我们抽丝剥茧后,可以确定的是,只会有一个提案的value会最终会被加锁并被大多数Acceptors确认。原因如下:

首先,从Acceptors集合角度来看,任何时候他们只能承诺最多一个提案:因为每个Acceptor同时只能承诺一个提案,任何时刻其承诺某一个提案的大多数的集合必然只有一个。


成功的加锁是成功的确认的基础,同时拒绝了更小编号的提案成功确认的可能性,降低了来自低编号提案的不确定性。

Proposer需要在成功的加锁之后,在更大编号的提案抢占锁之前,完成大多数Acceptor的确认。


一旦该编号n的提案加锁并经过大多数Acceptor确认成功后,更大编号的提案如果能抢占锁成功,则必然能够学习到编号n提案的value,因为大多数集合之间必然有交集。如果更大编号的提案没有抢占锁成功,则不会给Acceptors集合增加任何新的可供选择的value,编号n的提案的值,仍然是编号最大的值。

更大编号的提案学习到编号n的提案后,做为自己的提案内容。依次迭代,后续提案也是如此,必然达成一致。


因此,我们需要做的就是等待某个提案的value(可能是一次确认,也可能是逐渐收敛)成功获得大多数Acceptors确认而胜出。

那么,会不会有可能永远无法有提案胜出呢?有可能,比如提案轮流抢占锁,但都在Propose前被下一个提案抢占,就永远无法有提案胜出了(活锁),解决方法就是:随机等待,重新发起提案。

(类似的活锁情况还有很多种,例如:不同提案之间永远在相同的Acceptors之间争夺承诺但都无法及时写入value。或者每次一个Acceptor确认一个value后就被隔离分区,后续提案再也接触不到,到达一半后,系统再也无法达成大多数,但只要某个分区能够有大多数Acceptor存在,都可以达成一致。)


因此,只要有足够的时间让一个提案获得大多数Acceptors确认就不会有一致性问题。


(以上是自己分析协议流程后的理解,接触时间短,水平有限,不排除有根本性理解错误。Lamport的论文没有彻底研究透,待后续补充修改。)



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《晦涩的Paxos》的版权归原作者「磨链mochain社区」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注磨链mochain社区微信公众号

磨链mochain社区微信公众号:mochain-community

磨链mochain社区

手机扫描上方二维码即可关注磨链mochain社区微信公众号

磨链mochain社区最新文章

精品公众号随机推荐