在搭建Hadoop集群的时候,想必大家都遇到过在更改配置文件后,需要将修改应用到整个集群的问题。当集群中的机器数量很少时,可以依次手动修改,但是当集群足够大时,手动同步配置几乎是不可能的。有没有一种算法,能让在集群中任意一台机器上修改的配置同步到整个集群?

1. 一致性算法

Paxos就是一种解决此类一致性问题的算法。假设有一个变量Var,以及一些能对Var的值提出修改意见的程序。一致性算法保证在这些程序提出的修改值中,只有一个能够被选中并应用到Var上;此外,其它未被选中的程序必须能够知晓这个被选定的值。因此,一致性算法的目的就是:确保某个被提议的值最终会被选定,且一旦被选定,则任意一个程序最终都会知晓这个被选定的值。

在Paxos中,有三个角色:提议者、接受者、学习者。提议者提出建议值给接受者,接受者选定好一个被提议的值后,学习者能知晓那个被选定的值。

2. 选定一个值-协议推导

如何能确保有且只有一个值被选定呢?最简单的方法是只存在一个接受者,他只需要选定第一个收到的提议值即可。但此方法是不可行的,接收者的宕机会导致整个算法无法进行下去。

所以,我们需要使用多个接受者。一个提议者将提议发送给多个接受者,只要大多数接受者同意他的提议,这个提议值才能被选定。大多数接受者指的是超过接受者总数的一半,记任意一个大多数接受者组成的集合为多数集。为什么需要多数集同意,才能确保提议值被选定呢?假设有两个不同的提议值V1V2被选定,提议值V1被多数集S1选定,提议值V2被多数集S2选定,因为任意两个多数集必定会有一个共同的接受者,记S1S2的一个公共接受者为A,那么A同意的提议值V' = V1 = V2,这与假设不符。因此不存在两个不同的提议值被选定,也就是说只需要多数集同意,整个接受者集合就只能选定唯一一个提议值。

现在,我们有一个或多个提议者,以及多个接受者。考虑到消息的丢失以及机器宕机,即使当有且只有一个提议者提出有且只有一个值时,这个值也必须被选定。因此,P1被提出:

P1. 接受者必须接受第一个到达的提议

但是P1会带来一个问题:假若有不同的提议者同时提议不同的值,而没有任何一个值被大多数接受者接受,这就导致算法无法选定一个唯一的提议值。如果接受者能且只能接受一个提议,那么算法就进行不下去了。因此我们可以放宽一下限制,允许接受者接受多个提议,即在提议值被确定之前,接受者可以更改其接受的值。这样一来,算法就可以继续进行下去了。

为了区分不同的提议,我们可以给每个提议附加一个唯一的编号。尽管接受者可以接受不同的提议,但是必须保证有且只有一个值被选定。故引出P2:

P2. 如果值为v的提议被多数集选定,则任意一个被选定的高编号提议的值必须为v

(高编号指比被多数集选定的提议的编号高,下同)

P2的定义还是有一些抽象,为了使算法的实现更加具体,我们可以对接受者的行为进行进一步的限制,从而引出P2a

P2a. 如果值为v的提议被多数集选定,则任意一个被接受的高编号提议的值必须为v

P2aP2的要求更多,因为P2只是限制了被选定的提议值,而P2a限定了所有被接受者接受的提议值,不论该提议最终是否会被选定。当然,在被选定之前,提议必须先被接受,故满足P2a即可满足P2

在满足P2a的同时,我们仍需要满足P1(不然P2的提出就没有意义了),此时又会带来一个新的问题。考虑下面的场景:已经有一个提议被多数集选定,但是由于消息传递的失败,现在存在一个接受者c没有收到任何提议;此时,某个提议者提出了一个高编号且值不同的提议,依照P1c必须接受该提议,但这违背了P2a

为了解决这个问题,我们可以对提议者进行限制,加强一下我们要求。引出P2b:

P2b. 如果值为v的提议被多数集选定,则任意一个被提出的高编号提议的值必须为v

当然,在被接受之前,提议必须先被提出,故满足P2b即可满足P2a。故有:P2b => P2a => P2

P2b的定义还是太抽象,需要找一个能使P2b成立,且容易实现的条件。那么,怎样才能满足P2b呢?为了找出使P2b成立的条件,我们先尝试使用数学归纳法来证明P2b,当证明过程缺少条件时,该条件即为我们所寻找的用来满足P2b的条件。

首先将P2b转化为等价命题:若有提议Pm = v(编号为m,值为v)被多数集选定,则对任意的n,若n > mPn = v

我们首先证明:对任意的n,若n >= mPn = v

下面用数学归纳法证明:

  1. n = m时,Pn = Pm = v命题成立。
  2. 假设当n <= k - 1 (k > m)时,命题成立,即编号在区间[m, k - 1]内的提议值均为v。由于Pm被选定,则说明存在多数集CC中的所有接受者都接受了Pm,结合归纳假设,可以得知结论D(a) C中的所有接受者都接受了一个编号在[m, k - 1]内的提议,(b) 并且编号在[m, k - 1]内的提议值都为v

我们需要利用结论D推导出当n = k时,命题也同样成立,这样才能完成归纳法的证明过程,进而推导出P2b。故此时我们需要附加一个条件,用它结合结论D来证明Pk = v

提议Pk是任意提出的提议,怎么通过结论D使Pk = v呢?结论D(b)明确地告诉我们,编号在[m, k - 1]内提议的值必定是v,那我们可以通过限定某些条件,使编号在[m, k - 1]内的某个提议的值为Pk,那么就可以证明Pk = v了。

我们可以尝试指定[m, k - 1]内的某个提议的值为Pk,那么问题就解决了。但是由于m的一般性,区间[m, k - 1] (k > m)是不确定的,也就是只能指定Pk-1 = Pk(编号为k - 1的提议一定存在)。但此限定也就间接地导致所有的提议值都必须一样,显然是不可取的。

既然不能取指定值,那么我们不妨取最值。对于任意一个多数集SS中接受者所接受的所有编号小于k的提议中,编号最大者(编号记为x)的值必定是v。因为两个多数集SC必定会有交集,由结论D(a)可知,x >= m(这是最大者的意义所在),又由结论D(b)以及x < k可知,Px = v必定成立。我们只需要限定Pk = Px,把它作为已知条件,这样就能成功地推导出Pk = v,进而完成上述数学归纳法的论证。

故而Pre-P2c被引出:

Pre-P2c. 对任意的v、n,若编号为n,值为v的提议被提出,那么必定会存在一个多数集S满足:S中接受者所接受的所有编号小于n的提议中,编号最大者的值是v

当然,归纳法的步骤2中已经暗含了S中必定会存在有接受者接受编号小于n的提议,为了避免最大号提议不存在的情况,对Pre-P2c进行修改,得到P2c

P2c. 对任意的v、n,若编号为n,值为v的提议被提出,那么必定会存在一个多数集S满足以下条件中的任意一个:(a):S中没有接受者接受过编号小于n的提议,或者(b):S中接受者所接受的所有编号小于n的提议中,编号最大者的值是v。

有了P2c就能证明P2b,进而有P2c => P2b => P2a => P2。下面在P2c成立的情况下,完成上述归纳法的证明过程:

证明命题Q若有提议Pm = v(编号为m,值为v)被多数集选定,则对任意的n,若n >= mPn = v

  1. n = m时,Pn = Pm = v命题成立。
  2. 假设当n <= k - 1 (k > m)时,命题成立,即编号在区间[m, k - 1]内的提议值均为v。由于Pm被选定,则说明存在多数集CC中的所有接受者都接受了Pm,结合归纳假设,可以得知结论D(a) C中的所有接受者都接受了一个编号在[m, k - 1]内的提议,(b) 并且编号在[m, k - 1]内的提议值都为v又因为提议k被提出,由P2c可知,存在一个多数集SS满足P2c(a)P2c(b)。因为两个多数集SC必定会有交集,所以S中必定有接受者接受了编号小于k的提议,故P2c(b)成立。即在S中接受者所接受的所有编号小于k的提议中,编号最大者(编号记为x)的值是Pk。由结论D(a)可知,x >= m,又由结论D(b)以及x < k可知,Px = v必定成立。故Pk = Px = v,即当n = k时命题也成立。

1、2归纳可知,命题Q成立,所以命题:若有提议Pm = v(编号为m,值为v)被多数集选定,则对任意的n,若n > mPn = v成立,也就是P2b成立。

那怎么保证P2c成立呢?是继续找一个更具体、更容易实现的条件,还是就此打住,寻求一个能保证P2c成立的算法?

3. 选定一个值-协议实现

引出P2c后,我们无需再进行具体化了。现在,我们着手于P2c的实现。先将P2c转化为等价命题:

若要提出编号为n的提议(记其值为V),首先得选则任意一个多数集S,若S中没有接受者接受过编号小于n的提议,则V可以为任意值。否则,VS中接受者所接受的所有编号小于n的提议中最大者的值。

为了满足P2c,提议者在提议编号为n的提议时,需要知道已经或将要被多数集接受的编号小于n的提议中编号最大者的值v(如果存在)。为什么会提到将要呢?因为提议者与接受者间的消息传递是异步、有时延、不可靠的,可能提出提议n后,接受者还会收到编号小于n的提议。

未来往往不可预测,与其耗费大量精力去预测未来,不如对接受者的行为进行约束。提议者会请求接受者不再接受编号小于n的提议。具体的提议算法如下:

  1. 提议者选择编号为n的提议,提议值为Vo。然后发送一个预提议给接受者,要求他们回复以下消息:

    • 承诺不再接受编号小于n的提议
    • 他所接受的编号小于n的提议中(如果存在的话)编号最大者的编号及其提议值
  2. 记提议者最终提议的值为V。如果提议者收到了多数集的回复,则从这些回复中选出一个编号最高的提议,其值为Vm。若Vm存在,则V = Vm,反之,V = Vo。之后提议者发出正式提议给之前预提议的接受者,Pn = V

在接受者端的算法又是怎样的呢?接受者可能会收到两种请求:预提议以及正式提议。接受者可以忽略所有请求,协议只是对接受者回复的请求有所约束:(a).接受者可以回复任何预提议(b).只有当他被允许时才能回复正式提议(因为他在回复预提议时许下了承诺)。因此,P1a被引出,很显然,P1a是遵循P1的:

P1a. 当且仅当接受者没有回复编号大于n的预提议时,他才能接受编号为n的正式提议。

由于(b)的限制,我们引出了P1a。但是对于(a),并没有一个执行标准,因此我们可以对其作出限制,来减少回复预提议的次数,进而降低系统的负荷。假设有这样一个接受者,他收到了一个编号为n的预提议,但是他已经回复了编号为n的预提议,也就是说他已经许下承诺,不会接受编号为n的提议,所以他此时再回复这个编号为n的预提议就没有意义了。另外,对于已经接受的提议,也没有回复其预提议的必要了。所以,接受者需要记录他已经回复的预提议中最大的编号,以及他已经接受的正式提议中的编号最大的提议。

将提议者以及接受者的算法合并到一起,我们可以将整个算法流程分为两个部分:

  1. 阶段1

    • (a) 提议者选择一个提议号n,然后发送编号为n的预提议到多数集。
    • (b) 如果接受者收到一个编号为n的预提议,若他之前已经回复的预提议的编号都小于n,则回复他已经接受的编号最大的提议(如果有的话)以及许下承诺,不再回复编号小于n的预提议。
  2. 阶段2

    • (a) 如果提议者从多数集收到编号为n的预提议的回复,那么他向同一个多数集发送一个编号为n的正式提议,其值为预提议的回复中附带的提议中的编号最大者对应的值,若这个最大编号者不存在,则正式提议的值可以为任意值。
    • (b) 如果接受者收到一个编号为n的正式提议,当且仅当他已经回复了编号大于n的预提议时,他才能拒绝这个提议。

4. 学习被选定的值

目前我们已经可以在众多提议中选定一个值,对于学习者而言,要想知道某个值已经被选定,那么他必须知道这个值已经被多数集接受。怎么让学习者知道呢?最简单的方法就是当接受一个提议时,每个接受者都把这个提议发送给学习者,当接受到大多数接受者发来的同一个提议时,学习者就可以明确地知道这个提议已经被选定。但是这个方法的复杂度比较高,要发送的消息数为学习者的总数量乘上接受者的总数量。

为了降低复杂度,我们可以选择出一个学习者作为领导者,这个领导者先从接受者那里学习到被选定的提议,然后将这个提议发送给其它学习者。这样一来,要发送的消息数量就降低为学习者总数加上接受者总数了。但是这个方法的可靠性无法保证,因为学习者中的领导者是可能宕机的。

为了提高可靠性,我们可以在学习者中选出一组领导者。这组领导者分别从接受者那里知晓被选定的提议,然后分别把选定的提议发送给其它学习者。这样就能降低领导者宕机带来的风险,代价就是提高了复杂度。

但是由于消息会丢失,可能没有任何一个学习者能知晓被选定的值。学习者可以问接受者,你们选定的提议是什么?但是由于消息会丢失或者接受者宕机,学习者可能收不到多数集的反馈信息。在这种情况下,必须有一个新的提议被接受,学习者才能再次有机会知道被选定的值。如果学习者想知道某个值是不是被选定,则可以用该值作为新提议的值,提出这个提议,要是提议被接受,则表示该值之前已经被选定。

5. 总结

正如Lamport在论文《Paxos made simple》摘要中所说的那样,Paxos算法的确很简单。算法只需要保证有且只有一个提议值被选定,且这个值最终会被所有学习者知道。在选定提议阶段,首先依据算法的目的提出了P1以及P2。为了方便实现P2,将要求加强到限制接受者接受的所有提议,得到P2a,之后又进一步加强到限制提议者提出的提议,得到P2b。为了将P2b进一步具体化,我们推理得出了P2c,满足P2c即可满足P2b进而满足P2。最后我们找到了满足P2c的算法,这便是Paxos的选值算法。选定提议值后,还需要将选定的值告知所有学习者,此过程有多种实现的方式,每种方式在复杂度以及可靠性方面都有所偏重,需要我们在二者之间做出权衡。总结而言,Paxos是一个简单、有趣的一致性算法。

(完)


References: