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

1. 一致性算法

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

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

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

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

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

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

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

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

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

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

（高编号指比被多数集选定的提议的编号高，下同）

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

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

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

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

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

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

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

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

首先将P2b转化为等价命题：若有提议Pm = v（编号为m，值为v）被多数集选定，则对任意的n，若n > m 则 Pn = v。

我们首先证明：对任意的n，若n >= m 则 Pn = v

下面用数学归纳法证明：

  1. 当n = m时，Pn = Pm = v命题成立。
  2. 假设当n <= k - 1 (k > m)时，命题成立，即编号在区间[m, k - 1]内的提议值均为v。由于Pm被选定，则说明存在多数集C，C中的所有接受者都接受了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的提议一定存在）。但此限定也就间接地导致所有的提议值都必须一样，显然是不可取的。

既然不能取指定值，那么我们不妨取最值。对于任意一个多数集S，S中接受者所接受的所有编号小于k的提议中，编号最大者（编号记为x）的值必定是v。因为两个多数集S与C必定会有交集，由结论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 >= m 则 Pn = v

  1. 当n = m时，Pn = Pm = v命题成立。
  2. 假设当n <= k - 1 (k > m)时，命题成立，即编号在区间[m, k - 1]内的提议值均为v。由于Pm被选定，则说明存在多数集C，C中的所有接受者都接受了Pm，结合归纳假设，可以得知结论D：(a) C中的所有接受者都接受了一个编号在[m, k - 1]内的提议，(b) 并且编号在[m, k - 1]内的提议值都为v。又因为提议k被提出，由P2c可知，存在一个多数集S，S满足P2c(a)或P2c(b)。因为两个多数集S与C必定会有交集，所以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 > m 则 Pn = v成立，也就是P2b成立。

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

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

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

若要提出编号为n的提议（记其值为V），首先得选则任意一个多数集S，若S中没有接受者接受过编号小于n的提议，则V可以为任意值。否则，V为S中接受者所接受的所有编号小于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: