Paxos Made Simple

介绍

Paxos作为一个实现容错的分布式系统的算法被认为是难以理解的，或许是因为之前主要是希腊的许多读者在介绍。事实上，它是最简单明了的分布式算法。它的核心是一个一致性算法—“议会”算法。下一张将说明着这种共识算法几乎不可避免的追随各种我们希望它满足的特性。最后一章完整的讲解了Paxos 算法

 

一致性算法

<!--[if !supportLists]-->•       <!--[endif]-->问题

假设某个过程集能够对一组值进行提议。一致性算法保证在这些被提议的值中只有一个值被选择。如果没有值被提议，也就不需要选择。如果某个值被选择，那么这些过程应该能学习到这个被选择的值。一致性满足一下要求：

<!--[if !supportLists]-->-          <!--[endif]-->只有被提议的值才可能被选择

<!--[if !supportLists]-->-          <!--[endif]-->只能有一个值被选择

<!--[if !supportLists]-->-          <!--[endif]-->过程只能学习到被选择的值

我们引入三种角色，通过三种类型的代理角色来执行一致性算法：提议发起者（proposers），提议批准者（acceptors）以及学习者（learners）。在实现中，每个过程可能扮演多个角色，但我们这里并不关心过程和代理角色之间是怎么映射的。

假设代理角色之间通过发消息进行通信。我们使用习惯的异步，非拜占庭式的模式：

<!--[if !supportLists]-->-          <!--[endif]-->代理角色工作在一个随心所欲且乱的极度紧张的状态下，可能因为出现故障而停止工作，也可能重启。因为可能在选择了一个值后，所有的代理角色都出现故障并重启，所以，在出现故障并重启时，除非某些信息能够被代理角色记住，否则这个方案是不可行的。

<!--[if !supportLists]-->-          <!--[endif]-->消息可以随意地传递，也可以被复制，并且可能被丢失，但不会被破坏。

 

一致性算法

 

<!--[if !supportLists]-->•       <!--[endif]-->选择一个值

最简单的方式，在只有一个提议批准者（ acceptor ）的情况下去选择一个值。某个提议发起者（ proposer ）向提议批准者（ acceptor）发起一个提议（ proposal ）,提议批准者（ acceptor）选择它接收到的第一个提议值。虽然简单，但这种方式并不符合要求，因为可能由于提议批准者（ acceptor）出现故障导致没有任何进展。

因此，我们尝试另外一种方式来选择一个值。我们转而使用多个提议批准者（ acceptors）而不再只是一个提议批准者（ acceptor ）。提议发起者发起一个提议的值给这些提议批准者（ acceptors ）。提议批准者可能接受这个提议的值。当有足够多的接受这个提议的值时，这个值就被选择。多少才是足够多呢？为了保证只有一个值被选择，我们把提议批准者（ acceptors）的多数认为足够多。

在保证没有故障或者消息丢失的情况下，即使只有一个提议发起者，只有一个值被提议，我们也希望能选择有一个值。这就要求：

P1. 提议批准者必须接受它接收到的第一个提议。

但这个要求会导致一个问题。多个值可以同时由不同的提议发起者提议，从而导致每个提议批准者都接受到一个值，但没有一个值被多数提议批准者（ acceptors）接受。甚至在只有两个提议的值时，每个值都被半数提议批准者（ acceptors）接受，某个提议批准者出现故障导致无法学习到哪个值被选择。

 

 

一致性算法

 

满足P1的同时，要求只有值被大多数批准者接受才被选择意味着批准者必须允许接受多个提议。我们通过给每个提议分配一个自然数来跟踪批准者接受到的不同提议，因此，一个提议由提议编号和提议值组成。为了防止混淆，我们要求不同的提议编号不同。具体如何完成取决于实现，我们现在只是假设。只有当一个提议被多数批准者接受，提议的值才被选择。这样，我们就说这个提议（也就是提议的值）被选择。

我们允许多个提议被选择，但是我们必须保证所有选择的提议的值是相同的。通过提议编号，它足以保证：

P2. 如果一个提议值v被选择，那么每个被选择的更高编号的提议拥有值v。

因为编号是完全有序的，条件P2完全保证只有一个值被选择。

为了能够被选择，一个提议必须至少被一个提议批准者接受。通过满足一下条件能够保证P2：

 

 

一致性算法

 

P2a .如果一个提议值v被选择，那么被任何批准者接受的每个更高编号的提议拥有值v。

我们仍然维护P1确保一些提议被选择。由于通信是异步的，一个提议能够被选择，同时某些批准者c从来没有接受到任何提议。假设一个新的提议发起者“被唤醒”，并且给一个不同值的提议分配一个更高编号。P1要求c接受这个提议，但违反了P2a。P1， P2a要求加强P2a：

P2b. 如果一个提议被选择，提议值为v，那么被任何提议发起者分配的每个更高编号的提议拥有值v。

由于一个提议在能被批准者接受之前，必须先被提议发起者申请发起提议，P2b包含P2a， P2a又包含了P2。

 

一致性算法

为了发现怎么去满足P2b，我们来考虑如何证明它是满足P2b 的。我们将假设一些提议，提议编号为m，提议值为v被选择，并说明任何分配编号为n>m的提议的值也是v。通过对n的推导归纳，我们将很容易的证明，在附加假设i..j表示i到j的编号集合，每个编号在m..(n-1)的提议拥有值v得条件下，我们能够证明编号为n的提议也拥有值v。对于编号为m的提议要被选择，就必须有集合C（大多数批准者）其中的每一个批准者都接受了它。将此与归纳假设相结合，编号m被选择的假设说明：

C中每个批准者接受了编号m..(n-1)的提议，并且被任何批准者接受的编号m..(n-1)中的每个提议拥有值v。

 

一致性算法

由于任何组成大多数的提议批准者集合S至少包含C中的一个成员，我们可以得出这样的结论：通过确保维持以下不变量，一个编号为n的提议拥有值v

P2c. 对于任意v和n，如果一个编号为n，值为v的提议被发起，那么就有组成大多数的提议批准者的集合S，如：

(a) S集合中的提议批准者都没有接受过提议编号小于n的提议

或

(b) 值v是S集合中提议批准者接受的所有编号小于n的提议中编号最大的提议的值。

通过维持P2c的不变性，我们同时能满足P2b

 

为了维持P2c的不变性，提议发起者想要发起编号为n的提议就必须学习到编号小于n的最大编号的提议，如果学习到了的话，就会被或将会被大多数提议批准者中的每一个接受。学习被接受了的提议是很容易的；预测未来的接受是很难的。与其尝试去预测未来，提议发起者可以通过提议批准者给它不再接受此类提议的承诺来控制。换句话说，提议批准者不接受任何提议编号小于n的提议请求。这将导出以下提议发起算法：

1. 提议发起者选择一个新的编号n，然后向提议批准者集合（所有提议批准者的一个子集）中每个成员发起提议请求，并请求回复：

<!--[if !supportLists]-->(a)     <!--[endif]-->回复一个承诺，承诺不再接受编号小于n的提议，并且

<!--[if !supportLists]-->(b)     <!--[endif]-->这个最大编号的提议（提议编号小于n）已经被接受，如果是这样的话

我将发起一个编号为n的提议的prepare请求。

2.

一致性算法

 

提议发起者通过给某些提议批准者集合发起请求(请求提议能够被接受)。(这并不要求和响应最初请求的提议批准者集合是相同的。)我们称之为accept请求。

这里描述提议算法。提议批准者是怎么回事？它能从提议发起者接收两种类型的请求： prepare请求和accept 请求。提议批准者能忽略任何请求而不放弃安全。因此，我们必须说只有当它被允许响应一个请求，它总能响应一个prepare请求。当且仅当它不承若不得情况下，它能响应一个accept请求以接受一个提议。换句话说：

P1a. 提议批准者能接受一个编号为n的提议，当且仅当它还没有响应一个编号大于n的提议的prepare请求。

观察发现P1a包含P1。

 

 

一致性算法

 

现在我们有一个完整的选择一个提议值得算法，满足所需的安全特征—假定一个唯一的提议编号。最终的算法经过一个很小的改动优化就可以得到。

假设提议批准者接收到一个编号为n的提议的prepare请求，但它已经回复过一个编号大于n的提议的prepare请求，从而承若不接受任何新的编号为n的提议，那么提议批准者就没有必要的理由回复这个prepare 请求，因为它不接受提议发起者发起的编号为n的提议。因此我们要求提议批准者忽略这种prepare请求，如果它已经接受了这个提议的prepare的请求，我们也要求他忽略它。

 

一致性算法

 

有了这个优化，提议批准者必须记住它接受过的最大编号的提议以及回复过的最大编号的prepare请求的编号。因为就算发生故障，都必须保证P2c的不变性，即使提议批准者发生故障后重启，它都必须记录这个信息。需要注意的是，提议发起者可以放弃一个提议并不关心有关该提议的一切—只要提议发起者不再尝试发起另一个相同编号的提议。

将提议发起者和提议批准者的行为动作放在一起，我们可以看到，该算法按照以下两阶段操作：

 

 

一致性算法

 

阶段1.(a) 提议发起者选择一个提议编号n，并发起一个编号为n的prepare请求给大多数提议批准者。

(b)如果一个提议批准者接受这个编号为n的prepare请求，并且这个编号n大于它之前已经响应的任何prepare请求，那么它以一个promise响应该请求，并不再接受任何编号小于n的提议以及如果可能的话，不再接受已经接受了的最高编号的提议。

阶段2.(a)如果提议发起者从大多数提议批准者接受到编号为n的prepare请求的响应，那么它为编号为n的提议，提议的值为v发送一个accept请求给所有的这些提议批准者（大多数），这里的v是这些响应中编号最大的提议的值，或者是任意值，如果这些响应反馈没有提议的值的话。

(b)如果提议批准者接受到编号为n的提议的accept请求，它就接受这个提议，除非它已经又响应了一个编号大于n的提议的prepare请求。

 

 

 

一致性算法

 

提议发起者可以发起多个提议，只要每一个发起的提议遵循这个算法。协议期间任何时候它都可以放弃提议。(即使提议的请求且/或响应经过很长的时间到达目的地，期间提议被放弃，也能够维护正确性。)如果有提议发起者开始尝试发起更高编号的提议时放弃一个提议可能是个好主意。因此，如果提议批准者忽略一个prepare或accept请求，因为它已经接受了一个更大编号提议的prepare请求，那么它应该尽可能的通知提议发起者放弃它的提议。这是个性能优化，并不影响正确性。

 

 

一致性算法

 

<!--[if !supportLists]-->•       <!--[endif]-->学习一个被选择的值

为了学到一个被选择的值，学习者必须发现一个提议被大多数批准者接受（批准）。很明显，算法必须知道，每个批准者，每当它接受批准了一个提议，必须发送给所有学习者，通知它们这个提议被批准接受。这需要学习者尽快的发现被选择的值，但要求每个批准者通知每个学习者--发起通知的数量等于批准者的数量乘以学习者的数量。

这里假定没有拜占庭问题，每个学习者很容易从另一个学习者发现被接受（批准）的值。我们可以让批准者把他们接受的值先通知给一个受人尊敬的学习者，再由这个学习者通知其他所有学习者。对于所有的学习者，为了发现被选择的值，这种方法需要额外的一轮。一旦这个受人尊敬的学习者发生故障，这种方式也是不可靠的。但是它只要求发起通知的数量等于批准者的数量加上学习者的数量。

更广泛的，批准者可以把他们接受的值先通知给一部分受人尊敬的学习者（所有学习者的一个子集），然后每个受人尊敬的学习者再把这个被选择的值通知给其他所有的学习者。这个所有学习者的子集可以选择大一点，以便得到更高的可靠性，即便这样需要更复杂的通信，更大的消耗。

由于可能出现消息丢失，一个值被选择了， 但学习者没有发现。学习者可以询问批准者接受了哪个提议，但是批准者出现故障的话使得不可能知道是否接受了某个提议。那样的话，只有当一个新的提议被选择出来后，学习者才能发现哪个值被选择。如果学习者想要知道是否有一个值被选择，它可以以提议发起者的角色身份发起一个提议，通过上述描述的算法。

 

 

一致性算法

 

<!--[if !supportLists]-->•       <!--[endif]-->进展

可以很容易的构造一个场景，两个提议发起者各自发起一系列编号递增，并且这些编号的提议之前没有被选择过的提议。提议发起者p完成了提议编号n1的第一阶段。其他的提议发起者q完成了提议编号n2（n2>n1）的第一阶段。提议发起者p的第二阶段接受了提议编号n1的请求，但被忽略，因为提议批准者承诺不接受任何新的提议编号小于n2。因此，提议发起者p开始完成新的提议编号n3（n3>n2）的第一阶段，导致第二个第二阶段接受了提议发起者q的请求被忽略。以此类推下去。。。

为了保证进度，一个比较特殊的，受人尊敬的、有威望的提议发起者（领导者）必须被选为唯一一个来尝试发起提议。如果这个领导者能够成功的和大多数提议批准者通信，并且如果使用的提议编号大于之前已经使用的编号，那么它将成功的发起提议并被接受。如果学习到发现更高编号的提议，领导者将放弃当前编号的提议并选择一个更高编号提议进行重试。

如果系统足够运行正常，可以依据活跃度来选举一个领导者。 Fischer, Lynch, and Patterson[1]的著名结论说明一个选举提议发起者的可靠算法必须具有随机性或实时的(例如，引入超时机制)。但是，无论选举是否成功，安全需要保证。

 

 

一致性实现

<!--[if !supportLists]-->•       <!--[endif]-->Paxos两阶段提交协议

Paxos两阶段提交分Phase1  Prepare阶段和Phase2 Accept阶段。

Phase1  Prepare阶段包括Prepare、 Promise（或者Reject ）两步骤。

Phase2 Accept阶段包括Accept、 Accepted（或者Nack ）两步骤