分布式理论:深刻浅出Paxos算法

2021年09月15日 阅读数:2
这篇文章主要向大家介绍分布式理论:深刻浅出Paxos算法,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
前言

Paxos算法是用来解决分布式系统中,如何就某个值达成一致的算法。它晦涩难懂的程度彻底能够跟它的重要程度相匹敌。目前关于paxos算法的介绍已经很是多,但却不多有人能对P2c提出本身的看法,大多数是和稀泥式的人云亦云,但我觉着应该旗帜鲜明的亮出本身的观点,你们一块儿讨论,才能学到东西。但愿我能将本身的观点表述清楚。算法

我我的认为理解Paxos有两个关键:安全

  1. 为何要对提案进行顺序编号(或者说更大的编号意味着什么)。服务器

  2. 为何Promise能保证一致性(答案隐含在第1点中)网络

 

一致性问题

假设有一组服务器保存了用户的余额,初始是100块,如今用户提交了两个订单,一个订单是消费10元,一个订单是充值50元。因为网络错误和延迟等缘由,致使一部分服务器只收到了第一个订单(余额更新为90元),一部分服务器只收到了第二个订单(余额更新为150元),还有一部分服务器两个订单都接收到了(余额更新为140元),这三者没法就最终余额达成一致。这就是一致性问题。jvm

一致性算法并不保证全部提出的值都是正确的(这多是安全管理员的职责)。咱们假设全部提交的值都是正确的,算法须要负责的使对到底该选哪一个值作出决策,并使决策的结果被全部参与者获悉。分布式

在正式开始介绍Paxos所面临的难题前,为了表述方便,先提一下Paxos算法中的三个角色,后面会比较频繁的用到:ide

  1. Proposer:议案发起者。源码分析

  2. Acceptor:决策者,能够批准议案。学习

  3. Learner:最终决策的学习者。线程

咱们虚拟一个一致性问题的场景:有一个用户小绿,如今要对他的姓氏信息进行修改,此时有多个不一样的议案被提出,如何就最终的结果达成一致。

首先看一下下面这种最简单的状况:A1接受了Pa的议案“赵”,A2和A3接受了Pb的议案“钱”,那么最终小绿应该姓什么?

分布式理论:深刻浅出Paxos算法_分布式

答案很简单:超过半数的的议案就是最终的选定值。小绿应该姓“钱”!在议案提交后,Pa和Pb只要查询一下小绿姓氏,很容易就能查到 “钱”的数量超过半数,所以Pb的议案将会返回“成功”,Pa的议案将会返回“失败”。

P0. 当集群中,超过半数的Acceptor接受了一个议案,那咱们就能够说这个议案被选定了(Chosen)。

P0已是一个完备的一致性算法,保证了P0也就解决了一致性问题。可是P0的实用性不佳,一个议案想被半数以上的Acceptor接受是一件极其困难的事情!

看下面这种状况:A1,A2,A3分别接受了“赵”,“钱”,“孙”,结果没有任何一个议案造成多数派,全部的议案都将返回“失败”。议案的数量越多,那议案被选定的几率就越低,这显然是无法容忍的。

分布式理论:深刻浅出Paxos算法_分布式_02

要解决这个问题,必须容许一个Acceptor接受多个议案,后接受的议案能够覆盖掉以前接受的议案

以下图所示, A1已经接受了“赵”,A2已经接受了“钱”,此时Pc提出了“孙”,并被A1,A2,A3接受,这样就解决了没法造成多数派的问题。

分布式理论:深刻浅出Paxos算法_分布式_03

但如今又会面临下图中的新问题:A1,A2,A3已经接受了“赵”,此时咱们认为“赵”是被选定的,但此时恰恰Pb和Pc不识时务,Pb向A2提出了“钱”,Pc向A3提出了“孙”。这样就从一致性状态,又回到了不一致的状态…这显然破坏了一致性

分布式理论:深刻浅出Paxos算法_分布式_04

Paxos就是在上述背景下产生的,Paxos要实现的目标的是:

  1. 一次选举必需要选定一个议案(不能出现全部议案都被拒绝的状况)

  2. 一次选举必须只选定一个议案(不能出现两个议案有不一样的值,却都被选定的状况)

 

Paxos算法的推导

首先,Paxos算法的必需要能知足第一个条件:

P1:一个Acceptor必须接受它收到的第一个议案。

要知足这个条件实在太过简单了,方法略。。。

下面是我我的对这个条件的理解,为何必须知足这个条件:

假设只有一个Acceptor,只有一个Proposer。若是Acceptor出于某些缘由拒绝了Proposer的议案,那必然致使Paxos的目标T1没法达成。所以能够认为目标T1隐含了P1。

在开始P2的推导的前,为了区分不一样议案,须要先对每一个Proposer的议案进行编号,编号时必须保证每一个议案的编号具备惟一性(不讨论实现方法),并且编号是不断增大的。

Paxos的目标T2隐含了P2:

P2:若是一个值为v的议案被选定了,那么被选定的更大编号的议案,它的值必须也是v。

P2很容易理解,除了其中的一个形容词“更大编号的”,这个形容词很扎眼,为何只对更大编号的议案进行限制,更小的编号怎么办?

老头子给的解释很简单“By induction on proposal number”(若是不看论文后半部分,没人知道他在说什么…)我说一下我本身的理解:

首先把“更大编号的”几个字换成“其余的”,咱们称它为P2S。那么P2S可否知足Paxos的目标?答案是确定的。而后比较P2和P2S,谁的约束更强?这得看“更小的编号”是怎么处理的,从论文后面的推演来看更小编号的议案绝对不容许被选定!!!所以知足P2的议案是P2S的一个子集。

显而易见,P2S和P2都能知足Paxos目标。换句话说,能知足Paxos目标的办法不少,但咱们只选其中一个办法就OK了。不过,要选最简单的办法(看完后面就知道了)。

总之,如今咱们能够得出一个结论:

若是P1和P2都可以被知足,那么Paxos的两个目标就可以达成。

若是你对上面这个结论没有异议,那么就说明你已经充分理解了P1和P2。

接下来就须要想办法,如何才能知足P2:议案在选定前,都要先被Acceptor接受,所以要知足P2,咱们只要知足下面的条件:

P2a:若是一个值为v的议案被选定了,那么Acceptor接受的更大编号的议案,它的值必须也是v。

P2a是P2的充分条件,可是P2a存在一个大麻烦:当一个议案被选定后,一部分Acceptor没法马上得到通知。例以下图中A1和A2已经接受了“赵”,这时“赵”就被选定了,此时Pb向A3提出了一个议案“钱”,这是A3接受的第一个议案,为了知足P1,A3必须接受这个议案,此时就会致使P2a没法被知足了。

分布式理论:深刻浅出Paxos算法_分布式_05

为了解决上述的问题,咱们想一下:要是此时不让Pb提出“钱”这个议案,而是提出“赵”这议案就万事大吉了。顺着这个思路,咱们获得了P2b:

P2b:若是一个值为v的议案被选定了,那么Proposer提出的更大编号的议案,它的值必须也是v。

P2b是一个比P2a更强的约束,也就是说P2b是P2a的充分条件,只要能知足P2b,那P2a就自动知足。但P2b很难被知足,考虑下图这种状况,A1接受了议案“赵”,A2即将接受议案“赵”,此时Pb提出了一个议案“钱”,这种状况下咱们又会遇到跟P2a彻底相同的麻烦。

分布式理论:深刻浅出Paxos算法_分布式_06

很明显,要想知足P2b,咱们必需让Proposer拥有“预测将来”的能力,这听起来像在讲鬼故事,后面会想办法解决这一点。

在介绍如何“预测将来”以前,咱们必须先肯定Proposer在提出一个议案时,它的值该如何选取,由于取值的方法决定了“预测”的方法。

一个理所固然的取值方法:找到一个Acceptor的多数派集合,集合内被接受的议案的值都是v,此时Proposer提出一个新的议案,议案的值必须也是v;若是没有这样的多数派集合,那Proposer就职意提。

这个取值方法,彻底能符合P2b,这是一目了然的,但问题出在 “预测”上,咱们必须能预测到即将造成多数派的那个议案,若是有谁能作到那就真的是在讲鬼故事了。

Proposal提出议案的正确姿式:

P2c:在全部Acceptor中,任意选取半数以上的Acceptor集合,咱们称这个集合为S。Proposal新提出的议案(简称Pnew)必须符合下面两个条件之一:

  1. 若是S中全部Acceptor都没有接受过议案的话,那么Pnew的编号保证惟一性和递增便可,Pnew的值能够是任意值。

  2. 若是S中有一个或多个Acceptor曾经接受过议案的话,要先找出其中编号最大的那个议案,假设它的编号为N,值为V。那么Pnew的编号必须大于N,Pnew的值必须等于V。

P2c提出议案的规则有点复杂,它真的能知足P2b吗?至少看上去不是那么一目了然…..老头子用了概括法来证实P2c能知足P2b,但效果不佳,没什么人能看懂,因此下面的证实过程即便你看不懂也必要太沮丧(后面会给出图文解释)。

证实题(注意!前方高能)

已知议案分布式理论:深刻浅出Paxos算法_分布式_07是集合中第一个被选定的议案,接受这个议案的Acceptor集合为分布式理论:深刻浅出Paxos算法_分布式_08,在知足P2c的规则2的状况下,提出了一个新的议案分布式理论:深刻浅出Paxos算法_分布式_09,n>m,证实分布式理论:深刻浅出Paxos算法_分布式_10

第一步,证实初始成立:当议案的编号n = m+1时,证实分布式理论:深刻浅出Paxos算法_分布式_10

由于分布式理论:深刻浅出Paxos算法_分布式_12是第一个被选定的议案,所以在m+1提出以前,m必然是集群当中编号最大的议案

根据P2c的规则2,议案分布式理论:深刻浅出Paxos算法_分布式_13可以被提出,是由于存在一个多数派集合分布式理论:深刻浅出Paxos算法_分布式_14,这个集合中,编号最大的议案的值为分布式理论:深刻浅出Paxos算法_分布式_15。由于分布式理论:深刻浅出Paxos算法_分布式_16分布式理论:深刻浅出Paxos算法_分布式_17都是多数派集合,因此他们一定存在交集。交集中的Acceptor一定都接受了分布式理论:深刻浅出Paxos算法_分布式_18。m是整个集群最大的编号,固然也就是分布式理论:深刻浅出Paxos算法_分布式_19中最大的编号,根据P2c的规则2,分布式理论:深刻浅出Paxos算法_分布式_20一定等于分布式理论:深刻浅出Paxos算法_分布式_21

第二步,当n > m+1时,假设编号从m+1到n-1的议案的值都是分布式理论:深刻浅出Paxos算法_分布式_21,证实分布式理论:深刻浅出Paxos算法_分布式_10

编号为m+1到n-1的议案提出后,咱们没办法判断究竟那一个议案会被选定,但有一点是能够确定的:全部接受了分布式理论:深刻浅出Paxos算法_分布式_21的Acceptor构成了一个新的集合分布式理论:深刻浅出Paxos算法_分布式_25,这个集合包含了集合分布式理论:深刻浅出Paxos算法_分布式_16中的全部Acceptor,分布式理论:深刻浅出Paxos算法_分布式_27显然是一个多数派集合,这个集合接受的议案的编号在m到n-1之间,并且值为分布式理论:深刻浅出Paxos算法_分布式_21。没有包含在集合分布式理论:深刻浅出Paxos算法_分布式_27中的Acceptor所接受的议案必定小于m。

根据P2c的规则2,议案分布式理论:深刻浅出Paxos算法_分布式_09可以被提出,那么必定存在一个多数派集合分布式理论:深刻浅出Paxos算法_分布式_14,由于分布式理论:深刻浅出Paxos算法_分布式_16分布式理论:深刻浅出Paxos算法_分布式_33都是多数派集合,因此他们一定存在交集。交集中的议案的最大编号必定大于等于m,小于等于n-1。所以集合分布式理论:深刻浅出Paxos算法_分布式_14中编号最大的议案必定位于交集内。根据P2c的规则,分布式理论:深刻浅出Paxos算法_分布式_20一定等于分布式理论:深刻浅出Paxos算法_分布式_21

这个证实过程,若是你能看懂,请受我三跪。。。

接下来,上图,举例说明。

假设有一个议案(3,Va)提交后,这个议案成为了被Acceptor集群选定的第一个议案 ,那此时集群的状态可能会以下图所示:

分布式理论:深刻浅出Paxos算法_分布式_37

一共5个Acceptor,有3个Acceptor接受了议案(3,Va),刚刚过半。此时有一个编号为4的议案要提出,根据P2c的规则2,首先选一个过半的集合,就选上图中蓝色线圈出来的A3,A4,A5好了(任意选),这个集合中编号最大的议案是(3,Va),所以新提出的议案一定为(4,Va)。符合P2b。

议案(4,Va)提出后,集群的状态多是下面这样:

分布式理论:深刻浅出Paxos算法_分布式_38

此时再提出编号为5或6,7,8,9,10的议案,这个议案的值一定也是Va(不信的话请举出反例),符合P2b。依此类推。。。

由此可证,P2c是可以知足P2b的!!!

想一想看P2,P2a,P2b中为何必定要有“更大编号的”这几个扎眼的字眼,此时你应该能有一点感受了,可能你会把它理解成“后提出的”,若是你是这样理解的话,请往下看。

有些童鞋确定早就已经想到了:当议案(3,Va)提交后,这个议案成为了被Acceptor集群选定的第一个议案,此时集群的状态有没有多是下面这样?

分布式理论:深刻浅出Paxos算法_分布式_39

注意,这时议案(4,Vb)才是集群当中的编号最大的议案,要是这样就糟糕了!当咱们提出编号为5的议案时,它的取值就有多是Vb,致使没法知足P2b。

为了保证不出现这种状况,就要用到前面提到的“预测将来”的能力。跟P2c的议案规则相配套的,须要预测的将来是:

当一个议案在提出时(即便已经在发送的半路上了),它必须可以知道当前已经提出的议案的最大编号。

这样的话,议案(3,Va)提交时,就会知道有一个(4,Vb)的议案已经提交了,而后将本身的编号改为5或更大编号提交,一切就完美了。

可是你知道的,咱们并不可能真的预测将来,换个思路,议案确定是要提交给Acceptor的,只要由Acceptor来保证议案编号的顺序就OK了。因而有:

议案(n,v)在提出前,必须将本身的编号通知给半数以上的Acceptor,收到通知的Acceptor将n跟本身以前收到的通知进行比较,若是n更大,就将n确认为最大编号,当半数以上Acceptor确认n为最大编号时,议案(n,v)才能正式提交。

两个编号不一样的议案,不可能同时被确认为最大编号,证实略。

可是实际环境上,上面的条件还不足以保证议案被接受的顺序,好比议案(n,Va)被确认为最大编号后,开始向Acceptor发送,此时(n+1,Vb)提出,因为网络速度的缘由,(n+1,Vb)可能比(n,Va)更早被Acceptor接收到。

所以Acceptor收到一个新的编号n,在确认n比本身以前收到的编号大时,必须作出承诺(Promise):再也不接受比n小的议案

这个承诺会致使部分漏网之鱼(在发送途中被抢走最大编号的议案),没法造成多数派。

例以下图所示:有一个在途的议案(1,Va),当A2和A3对议案(2,Vb)作出承诺的同时,(1,Va)就失去了造成多数派的权利。

分布式理论:深刻浅出Paxos算法_分布式_40

至此,咱们就造成了一个完整的算法(具体实现请自行搜索PhxPaxos)。

 

后记

算法原文中,将Promise看作是P2c的具体实现,而咱们将Promise当作是弥补P2c的补充条件。这二者没有质的差异,只是角度不一样,我我的认为后一种更容易被理解,因此采用了后一种。不过采用后一种会遇到下面的麻烦:

按下面的顺序提交议案:

  • 议案(1,Va)向A1发送Prepare,得到A1的承诺。

  • 议案(2,Vb)向A1发送Prepare,得到A1的承诺。

  • 发送议案(1,Va)

此时A1会拒绝议案(1,Va)

分布式理论:深刻浅出Paxos算法_分布式_41

采用后一种解释的话,会发现A1拒绝议案(1,Va)是违反了P1的,而采用前一种解释则不违反P1。(这不过是个文字游戏,我已经懒的去思考了,就这样吧)

 

若是咱们将半数以上的Acceptor对同一个议案(n,v)作出承诺的状态称做是“锁定”状态。那么这个“锁定”状态具备如下性质:

排它性:全部比n小的议案都不容许提交,已经在途的议案,则不容许其造成多数派。

惟一性:任意时刻,全局只有一个议案能得到“锁定”状态。

原子性:议案n从锁定状态变为非锁定状态的过程是原子的,议案n+1从非锁定状态变动为锁定状态的过程也是原子的。

我相信(有点虚…),正是上面的这三条性质保证了一致性。

最后,感谢老头子给出的如此精彩的算法。

往期精彩回顾

一)线程的发展历史

(二)线程的应用及挑战

(三)从jvm层面了解线程的启动和中止

(四)Thread.join的做用和原理

(五)Synchronized原理分析

(六) synchronized的源码分析

(七)Volatile的做用及原理(八)ThreadLocal的使用及原理分析

 

分布式理论:深刻浅出Paxos算法_分布式_42