我对Paxos算法的理解

电脑杂谈  发布时间:2019-08-13 13:01:49  来源:网络整理

paxos算法为代码_paxos算法实现_paxos算法思想

在分布式功能中,一个核心的难题就是数据的一致性。因此一致性算法是分布式中的重中之重。Paxos算法就是为了很好的极速11选5一致性的难题,反而依然以来它都被可能是很难理解的,认为是因为它是用日常的修辞来描述的,不过对于读者来说很难理解。想要了解Paxos算法,建议还是先好好的拜读一下“原著”——《Paxos Made Simple》。

好了,屁话不多说,上面开始走入Paxos的全球。

问题的提出

假定有一组程序要出具一些值,那怎么确保其他值的唯一性呢?一致性算法就是来确保其他值中只有一个值被确定。当然了,或者一个值被确定了,假如它们流程也是能获得这个被确定的值。

如果,我们见到,在这一个过程中也是涵盖三种角色——proposers(提议者)、acceptors和learners。在这个实现这个硬件的过程中一个成员认为要出演多个反派。

选择一个值得最简单的手段就是使各组成员中只有一个acceptor,一个proposer向这个acceptor提交议案,该acceptor选择它接收到的第一个提案。这种手段并且简单,反而并不能满足我们的要求。因为,一旦这个acceptor出现难题,则该流程将是没有办法继续走下去的。

如果,这儿需要我们使用这些的原理来选择这个值了。我们不使用单个的acceptor,取而代之的是我们使用多个acceptor来完成这个过程。也就是说proposer从之前的向一个acceptor提交议案改成向一组acceptor提交议案。一个acceptor会报批一个提案。一个提案的值被一个足够大的组中的一切acceptor所获批,就说该草案被选中了。那难题来了,很大的组才算是足够大呢[Q1]?

对于Q1,我们可以如此来认知:对于所有的acceptor有集合{acceptor1 , acceptor2 , acceptor3 , .. , acceptor(n)} A。假设有一个集合T,T中的每位元素都是一组acceptor。T中的它们组都是由A中的acceptor所组成的。

T:{{acceptor(k),acceptor(k+1), ...,acceptor(j)}, {acceptor1,acceptor2,...,acceptor(m)}, ..., {acceptor(l),acceptor(l+1),...,acceptor(n)}}

对于T中的任意两组acceptor至少有一个公共acceptor。这样的集合T就可以被可能是足够大的,也就是在Q1中提出的足够大的组。

好,清楚了这个足够大的组之后我们继续向下走。因为任意两个组至少有一个公共acceptor,不过说只有在一个acceptor最多只获准一个提案的现象下才能够选定一个提案。这里需要证明一下,一个acceptor最多只获准一个提案是在一次竞选的过程中。当进行下一次选举的时候是被禁止随后获批提案的。说到这里各位对这个难题应该有些模糊。没关系,请继续往下看,认知了中间的难题在返回这儿看就豁然开朗了。

在没有信息丢失的现象下,而且只有一个proposer提交了一个提案,我们应该能够该草案被选中的。这样就造成了Paxos算法中的第一个条件:

P1. 一个acceptor必须批准它接收到的第一个提案。

在原著中是如此说的:

P1. An acceptor must accept the first proposal that it recevies.

这里我翻译的也是没有错。

paxos算法为代码_paxos算法思想_paxos算法实现

只是,我们看paxos算法为代码,对于P1的要求也是会造成如此的一个问题。当多个proposer在同一时间内出具了多个不同的草案,这是有可能会出现没有一个提案会被多数以上的acceptor所获批[Q2]。关于这个难题该这么来认知呢?在P1的要求下——每位acceptor必须批准它接收到的第一个提案。所以会出现下面的景象:

多个acceptor接收到的草案都不相近

也就是说acceptor1第一个接收到value1,acceptor2第一个接收到value2,... 以此类推。他们都获准接收到的第一个提案,不过就加剧了Q2中造成的难题。即使说只有两个提案被提出,如果每位议案都被差不多一半的acceptor所获批,而且只有一个acceptor出错,也没有办法确保在P1的要求下有一个提案被确定。

我们明白,一个提案被选中的前提是该草案被一半以下的acceptor所获批。而在P1中又违反,一个acceptor必须批准它接收到的第一个提案,不过从P1条件又造成了我们下面所解释的难题Q2。所以综合上面的现象,我们可以推导出一个acceptor必须被禁止接收多个草案。acceptor会为每位议案分配一个序号。那么到这个地方我们的草案就已然更换了,不再是只有value构成,现在的草案是由编号和value两部份构成。同时要求任何两个提案之间的编号都不相近。到当前为止,我们又有了两个武器:

1. 一个acceptor可以接收多个提案。

2. 每个议案由编号和value两部份共同组成。任意的两个提案的编号都不相近。

拿起我们的手继续前行。接下来有两个结论需要证明一下。

一个提案要想被选中,必须被一半以下的acceptor所获批;我们禁止再一次选举过程中有多个草案被选中,反而它们被选中的草案的value值必须相同。到这儿好像能见过一丝光明了。提案有了编号,这就给我们后续的论述有了多大的帮助。在硬件中只要希望确保上面的条件成立,我们只要确保选中的草案的唯一性:

P2:或者一个带有v的草案被选中了,假设该草案的编号为m。那么任何大于m的被选中的草案的值都为v。

同样P2在原著中是如此说的

P2:If a proposal wiht value v is chosen, then every higher-numbered proposal that is chosen has value v.

因为编号是有序的。所以说能确保P2成立的话,只要满足我们最初的要求。

不过看了P2就好像先前见到的那一丝光明又消失了。且看P1是要每位acceptor批准其接收到的第一个提案。而到了P2则讨论的就直接是对于选中的草案的要求。从P1到P2这期间究竟发生了多少,我们不得而知。不过没关系,就算我们从P2中可以明白,只要满足了P2就能满足只有一个值被选中的这一关键点——这应该我们所能够达到的动机。

上面我们来做的就是反推应该怎么来确保P2能够设立。说到这是不是刚才好像要消逝的那一丝光明又在眼前重现了。

paxos算法思想_paxos算法为代码_paxos算法实现

那P2又该怎么来满足呢?首先,一个提案要想被选中,那该草案必须被至少一个acceptor所获批。这一点是毋庸置疑的。因此,新的条件又造成了。

P2a:或者一个值为v的草案被选中了,假设编号为m。那么对于每位编号大于m的草案来说,或者被acceptor批准,该草案的值也必须为v。

该条件在原著中是如此说的

P2a: If a proposal whth value v is chosen, then every heigher-numbered proposal accepted by any acceptor has value v.

经过P2a,话说P2可以得到满足了。因为提案的编号是全序的,也就是说后出具的草案的编号肯定是多于先填写的草案的编号了。而对于P2a条件中的要求,后出具的虽然被报批的草案其值必须为v。这样P2肯定会被满足了。

所以说只要满足P2a就能满足P2从而我们最初的动机也能接近,起码当前是如此的。但是paxos算法为代码,我们再回过头来看P1,就能发现,本来还有一些地方是我们遗漏的。我们明白,团体之间的通信是异步的。假如有一个acceptor,暂称其为C,还未收到任何提案的时候有一个编号为m的草案就已然被选中了。假设这时一个新的proposer被唤醒,然后填写了一个编号大于m的草案,如果该草案的值和m也不相近。当C收到这个草案以后,按照P1,C是必须要报批这个草案的。这时就相悖了P2a了。对于P2a,我们能看出,是站在acceptor角度提出的。因此就造成了下面的难题。所以需要重新站在proposer的视角来提出一些限制。

P2b: 一个值为v的草案被确定了,该草案编号为m。那么对于任何编号大于m的由proposer提交的草案的值必须为v。

当然我们引用原文

P2b: If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

由于一个提案在被acceptor批准之前必须由提议者提交,即使P2b可以满足P2a从而满足了P2。在这里,站在proposer的视角提出了P2b。那又该怎么来确保P2b呢?我们假设某个编号为m,值为v的草案被选中了,对于任何被提出的编号为 n(n > m)的草案,其值都为v。现在我们使用归纳法来表明该说法是设立的。

提案[ m , v ]被选中,我们的计算条件如下

对于编号在 m...(n-1) 中的任何一个被提出的草案的值都为v。

同样由于提案m被选中,即使肯定有一个集合C,涵盖半数以上的acceptor,C中的每一个acceptor都获准了草案m。因此我们可以推断出,在C中的每一个acceptor都获准了编号在m...(n-1)范围内的一个提案,如果m...(n-1)中的被任意一个acceptor批准的草案的值都为v(这儿需要注意的是,任意一个acceptor并不都是值得C中的acceptor)。

由于任意一个集合S,涵盖了半数以上的acceptor,肯定会至少涵盖一个C中的acceptor,不过我们可以通过上面的条件来满足P2b。也就是任意一个被提出的编号为n (n > m)的草案的值都为v。

P2c:对于任意的v和n,或者一个编号为n,值为v的草案被提出的话,肯定存在一个包含半数以上的acceptor的集合S满足:要么集合S中没有一个acceptor批准过任意的编号小于n的草案;要么对于集合S中批准的编号小于n的某些提案中,编号最大的草案的值为v。

通过维持P2c的不变性,只要确保P2b。从而满足P2a,因而满足P2。最终满足我们最初的要求。

paxos算法为代码_paxos算法实现_paxos算法思想

同样的,难题又来了。既然由P2c => P2b => P2a => P2。那我们又由多少来表明P2c的完整性呢[Q3]?

对于Q3,我们可以使用反证法来表明。

假设提案[m,v]早已被确定,有草案n ① n=m+1 假设n的值不为v,而为w。则按照P2c要么有一组S从来没有批准过小于n的草案;要么在报批的所有编号小于n的草案中,编号最大的草案的值为w。因为S和C至少有一个公共acceptor,所以说两个条件都不满足。所以假设不设立。因此n的值为v。② 编号m属于m...(n-1),假设n的值不为v,设为w’ 。则存在一个集合S’,要么在S’中没有一个acceptor批准过编号小于n的草案;要么在S’中批准过的一切的编号小于n的草案中,编号最大的草案的值为w’,设该草案的编号为p(p∈m...(n-1))。根据我们在归纳法中的计算条件编号属于m...(n-1)的草案的值都为v,如果S’和C至少有一个公共acceptor,不过由S’中的acceptor批准的高于n的草案中编号最大的那种提案也属于m...(n-1)。从而可以推导出w’=v。即可证明提案n的值为v。

到这儿我们就表明了P2C的完整性。

由此可见,一个proposer要想提交一个编号为n的草案,其次获取到编号小于n的某些提案中编号最大的那种提案,假设该草案编号为p,或者有这个草案的话,草案p已经或者将会被某一个包含半数以上的acceptor的集合中的一切的acceptor所获批。获取如此的一个已经被报批的草案是相当简单的,反倒预测一个批准的草案是相当困难的。所以,一个proposer可以请求acceptor不要批准任何高于编号n的草案。这时,体系的硬件就要造成了:

1. 一个proposer准备填写一个编号为n的草案之前,首先会向某组(含半数以上的acceptor)中的每位团体发出请求,能够得到如下的号召:


本文来自电脑杂谈,转载请注明本文网址:
http://xinshanjie.com/a/jisuanjixue/article-119092-1.html

相关阅读
发表评论  请自觉遵守互联网相关的政策法规,严禁发布、暴力、反动的言论

热点图片
拼命载入中...