迹忆博客
当前位置: 主页 > 学无止境 > 算法 > 文章

我对Paxos算法的理解

发布时间: 2017-03-31 作者: 迹忆 浏览次数:

在分布式系统中,一个核心的问题就是数据的一致性。因此一致性算法是分布式中的重中之重。Paxos算法就是为了很好的解决一致性的问题,但是一直以来它都被认为是很难理解的,可能是因为它是用平常的语言来描述的,所以对于读者来说很难理解。想要了解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.

这里我翻译的应该没有错。

但是,我们看,对于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能够成立。说到这是不是刚才感觉要消失的那一丝光明又在眼前重现了。

那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从而我们最初的目的也能达到,至少目前是这样的。但是,我们再回过头来看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。最终满足我们最初的要求。

同样的,问题又来了。既然由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)中的每个成员发出请求,希望得到如下的响应:
    a. Acceptor承诺不再批准任何编号小于n的提案。
    b. 如果acceptor批准过小于编号n的提案,则将编号最大的提案响应给proposer。

我们称这个请求过程为提案n的prepare请求。

2. 如果proposer从某个组(包含半数以上的acceptor)中的acceptor方面得到响应,那么该proposer就可以提交值为v的提案n了。当然了,这里的v要视响应消息而定。如果得到的响应是acceptor已经批准的编号小于n的的那些提案中的编号最大的提案,那么提案n的值v就是响应的提案的值;如果得到的响应消息是acceptor没有批准过任何编号小于n的提案,那么值v就可以是任意的了。得到prepare请求的响应以后,proposer再次向同一

acceptor发出批准该提案的请求。我们称其为accept请求。

上面的算法是对proposer提出的。那对于acceptor方面有该如何处理呢?在上面的过程中,acceptor会收到两种类型的请求:prepare和accept。

acceptor是可以忽略任何请求的,并且不用考虑是否能满足什么条件。 所以说,这里我们说的是acceptor会对一个请求进行响应的情况。acceptor对于prepare 请求总是会积极响应。对于accept请求,如果他没有响应过不去批准该提案,那它会响应一个批准该提案的消息。也就是下面的条件

P1a:acceptor对于编号为n的提案的accept请求,如果之前没有对编号大于n的提案的prepare请求进行过响应,那么该acceptor会批准编号为n的提案。

原著中是这样描述的

P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

我们看,在P1a中是包含P1的。

到目前为止我们已经有了一个比较完整的算法。现在我们将proposer和acceptor综合起来,看一下整个算法的过程。

Phase1 (a)proposer选择一个编号为n的提案,并且发送一个带有编号n的prepare请求给一组包含半数以上的acceptor。
(b)一个acceptor接收到一个关于编号n的prepare请求,发现编号n比其先前接收到的所有的提案的编号都大,并且对于这些提案的prepare请求都已经进行了响应。那么acceptor会向n的prepare请求回应的消息包括两部分:一是,不会再批准任何小于n的提案;二是,将已经批准的编号小于n的的那些提案中的编号最大的提案的值,当然这个提案要存在。如果不存在则仅仅响应第一条。

Phase2 (a)当proposer从包含半数以上的一组acceptor那里收到关于编号n的提案的prepare请求的响应信息,那么它将会向这组acceptor发送一个编号为n值为v的提案的accept请求。这个v的值根据proposer得到的响应信息来定:如果在响应信息中包含有提案信息,那这个v就是该提案的值;如果没有提案信息,则v可以是任意值,只要proposer愿意。
(b)如果acceptor收到一个关于n的提案的accept请求,除非acceptor已经向大于n的提案的prepare请求进行了响应,否则该acceptor是会批准编号为n的提案的。

一个proposer只要遵循上面的步骤,他就可以生成多个提案。在上面的过程中,proposer可以在任意的时刻终止一个提案。对于acceptor来说,无论如何,如果acceptor由于之前已经向一个编号更大的提案的prepare请求进行了响应而要忽略当前提案的prepare或者accept请求的话,必须要能通知到proposer。由proposer来放弃这个提案的提交。

上面就是关于proposer和acceptor的算法。说到这里,对于proposer和acceptor要做的事情就已经清楚了。但是我们知道,在Paxos算法中是存在三种角色的。除了proposer和acceptor以外还有learner。既然我们的提案已经选出来了,那就需要learner来学习了。下面我们就来看一下learner是如何学习一个已经被选中的提案的。

最简单的方式就是,learner必须获取被半数以上acceptor批准的提案。所以,必须使每个acceptor,不论何时只要它批准一个提案就会通知到所有的learner,并将批准的proposal发送给learner。因此,learner可以及时的获取一个被选中的提案。但是,这种方式的代价就是会有大量的通信。因为这种方式要求每个acceptor向每个learner都要发送消息。[方式一]

还有一个方式就是,指定一个特定的learner负责和acceptor进行通信。acceptor只负责将其批准的提案发送给这个特定的learner,由这个learner再将其发送给其他的learner。[方式二]

方式二虽然有效的减少、了通信的次数,但是这种方式却是不可靠的。因为一旦那个特定的learner出现故障,所有的learner都将获取不到提案。所以在方式二的基础上演变出来了方式三。不再指定一个特定的learner,而是指定多个learner负责和acceptor通信,然后再将信息发送给其他的learner。很明显,这种方式较方式二来说通信次数又增加了,但是较方式一,通信次数依然是减少的。而且这种方式是比较可靠的。

考虑到,在实际场景中消息是会丢失的。一个被选中的提案可能不会被learner获取到。这时候它可以向acceptor询问一个其已经批准的提案,但是这个acceptor是没有办法知道这个提案是否被大多数的acceptor所批准。在这种情况下,learner可以求助于proposer。它可以让一个proposer按照之前描述的步骤来提交一个提案。如果该提案被提交成功了,根据之前的P2c、P2b等条件可以知道该提案的值已经被选中;否则该值没有被选中。

算法到这里就已经完整了。对于开始说到的三个角色——proposer、acceptor和learner,各自要进行的动作都已经明确了。下面来说一个比较特殊的情况。

我们来假设这样的一个情景:有两个proposer——p和q,每一个都会提出一系列编号递增的提案。这些提案都没有别选中过。现在p完成了阶段1的编号为n1的提案。然后p完成了阶段1的编号为n2(n2 > n1)的提案。所以对于n1的阶段2的accept请求会被忽略,因为所有的acceptor都已经向n2的prepare响应了不会再批准任何编号小于n2的提案。因此,p开始提出n3(n3 > n2),并且完成了prepare的请求。同样,这时n2的accept请求也会被忽略。以此进行下去岂不是就成了一个死循环了。

为了解决这个问题,参照learner学习提案的方式二,指定一个特定的proposer,使其作为唯一的可以提出提案的proposer。

所有上面的算法都有一个前提,就是任何两个proposer提出的提案的编号都不相同。

上面一堆堆的文字可能有些啰嗦,多数都是参照原文翻译过来的。有不确切的地方还希望多多指教!

参考文献:《Paxos Made Simple》

赞助
迹忆博客

上一篇:Memcached中的分布式思想

下一篇:没有了

除非注明转载,本站文章均为原创,欢迎转载,转载请以链接形式注明出处

本文地址: