Paxos-Made-Simple
1. 简介用于实现高容错性分布式系统的Paxos算法，一直以来总是被认为是难以理解的，或许是因为对很多人来说，初始版本就像是”希腊语"一样（最初的论文是以希腊故事展开的形式）[5]。实际上，它也算是最浅显易见的分布式算法之一了。它的核心就是一个一致性算法——论文[5]中的“synod”算法。在下一个章节可以看到，它基本上是根据一个一致性算法所必需满足的条件自然而然地推断出来的。最后一个章节，我们通过将Paxos算法作为构建一个实现了状态机的分布式系统的一致性实现，来完整地描述它。这种使用状态机方法的论文[4]应该早已广为人知，因为它可能已经是分布式系统理论研究领域被引用最广泛的了。 2. 一致性算法2.1 问题描述假设有一组可以提出提案的进程集合。一个一致性算法需要保证：在这些被提出的提案中，只有一个会被选定。如果没有提案被提出，则不会有被选定的提案。当一个提案被选定后，进程应该能获取被选定提案的信息。 对于一致来说，安全性（Safety）需求是这样的：只有被提出的提案才能被选定。只能有一个值被选中（chosen），同时进程不能认为某个提案被选定，除非它真的是被选定的那个。 我们不会尝试去精确地描述活性（Liveness）需求。但是从总体上看，最终的目标是保证有一个提案被选定，并且当提案被选定后，进程最终也能获取到被选定提案的信息。一个分布式算法，有两个重要的属性：Safety和Liveness，简单来说：Safety是指那些需要保证永远都不会发生的事情Liveness是指那些最终一定会发生的事情 在这个一致性算法中，有三个参与角色，我们分别用Proposer，Acceptor和Learner来表示。在具体实现中，一个进程可能充当不止一种角色，但是在这里我们并不关心它们之间的映射关系。 假设不同的参与者之间可以通过发消息来进行通信，我们使用普通的非拜占庭模式的异步模型：每个参与者以任意的速度运行，可能会因停止而执行失败，也可能会重启。当一个提案被选定后，所有的参与者都有可能失败然后重启，除非这些参与者可以记录某些信息，否则是不可能存在一个解法的。消息在传输中可能花费任意时间，可能会重复，也可能丢失，但不会被损坏（不会被篡改，即不会发生拜占庭问题）。 2.2 提案的选定选定提案最简单的方式就是只有一个Acceptor存在。Proposer发送提案给Acceptor，Acceptor会选择它接收到的第一个提案作为被选提案。虽然简单，这个解决方案却很难让人满意，因为当Acceptor出错时，整个系统就无法工作了。 因此，我们应该选择其他方式来选定提案，比如可以用多个Acceptor来避免一个Acceptor的单点问题。这样的话，Proposer向一个Acceptor集合发送提案，某个Acceptor可能会通过（accept）这个提案。当有足够多的Acceptor通过它时，我们就认为这个提案被选定了。那么怎样才算是足够多呢？为了确保只一个提案被选定，我们可以让这个集合大到包含了Acceptor集合中的多数成员。因为任意两个多数集（majority）至少包含一个公共成员，如果我们再规定一个Acceptor只能通过一个提案，那么就能保证只有一个提案被选定（这是很多论文都研究过的多数集的一个普通应用[3]）。 假设没有失败和消息丢失的情况，如果我们希望在每个Proposer只能提出一个提案的前提下仍然可以选出一个提案来，这就意味着如下需求： P1. 一个Acceptor必须通过它收到的第一个提案。但是这个需求会引发另外的问题。如果有多个提案被不同的Proposer同时提出，这会导致虽然每个Acceptor都通过了一个提案，但是没有一个提案是由多数人通过的。甚至即使只有两个提案被提出，如果每个都被差不多一半的Acceptor通过了，哪怕只有一个Acceptor出错都可能导致无法确定该选定哪个提案。比如有5个Acceptor，其中2个通过了提案a，另外3个通过了提案b，此时如果通过提案b的3个当中有一个出错了，那么a和b的通过数都为2, 这样就无法确定了。 P1再加一个提案被选定需要由半数以上Acceptor通过的这个需求，暗示着一个Acceptor必须要能通过不止一个提案。我们为每个提案分配一个编号来记录一个Acceptor通过的那些提案，于是一个提案就包含一个提案编号以及它的value值。为了避免造成混淆，需要保证不同的提案具有不同编号。如何实现这个功能依赖于具体的实现细节，在这里我们假设已经实现了这种保证。当一个具有value值的提案被多数Acceptor通过后，我们就认为该value被选定了。同时我们也认为该提案被选定了。 我们允许多个提案被选定，但是我们必须保证所有被选定的提案具有相同的值value。通过对提案编号的约定，它需要满足以下保证： P2. 如果具有value值v的提案被选定了，那么所有比它编号高的提案的value值也必须是v。 因为编号是完全有序的，所以条件P2就保证了只有一个value值被选定这一关键安全性属性。 一个提案能被选定，必须要被至少一个Acceptor通过，所以我们可以通过满足如下条件来满足P2: P2a. 如果一个具有value值v的提案被选定了，那么被Acceptor通过的所有编号比它高的提案的value值也必须是v。我们仍然需要P1来保证有提案会被选定。因为通信是异步的，一个提案可能会在某个Acceptor c还没收到任何提案时就被选定了。假设有个新的Proposer苏醒了，然后提出了一个具有不同value值的更高编号的提案，根据P1, 需要c通过这个提案，但这是与P2a相矛盾的。因此为了同时满足P1和P2a，需要对P2a进行强化： P2b. 如果具有value值v的提案被选定了，那么所有比它编号更高的被Proposer提出的提案的value值也必须是v。一个提案被Acceptor通过之前肯定是由某个Proposer提出，因此P2b就隐含P2a，进而隐含了P2. 为了发现如何保证P2b，我们来看看如何证明它成立。我们假设某个具有编号m和value值v的提案被选定了，需要证明任意具有编号n（n > m）的提案都具有value值v。我们可以通过对n使用数学归纳法来简化证明，这样我们可以在额外的假设下——即编号在m..(n-1)之间的提案具有value值v，来证明编号为n的提案具有value值v，其中i..j表示从i到j的集合。因为编号为m的提案已经被选定了，这就意味着存在一个多数Acceptor组成的集合C，C中的每个成员都通过了这个提案。结合归纳的假设，m被选定意味着： C中的每一个Acceptor都通过了一个编号在m..(n-1)之间的提案，并且每个编号在m..(n-1)之间的被Acceptor通过的提案都具有value值v。由于任何包含多数Acceptor的集合S都至少包含一个C中的成员，我们可以通过保持如下不变性来确保编号为n的提案具有value值v： P2c. 对于任意v和n，如果一个编号为n，value值为v的提案被提出，那么肯定存在一个由多数Acceptor组成的集合S满足以下条件中的一个： a. S中不存在任何Acceptor通过了编号小于n的提案 b. v是S中所有Acceptor已经通过的编号小于n的具有最大编号的提案的value值。通过维护P2c的不变性我们就可以满足P2b的条件了。 为了维护P2c的不变性，一个Proposer在提出编号为n的提案时，如果存在一个将要或者已经被多数Acceptor通过的编号小于n的最大编号提案，Proposer需要知道它的信息。获取那些已经被通过的提案很简单，但是预测未来会被通过的却很困难。为了避免去预测未来，Proposer通过提出承诺不会有那样的通过情况来控制它。换句话说，Proposer会请求那些Acceptor不要再通过任何编号小于n的提案了。这就导致了如下的提案生成算法：Proposer选择一个新的提案编号n，然后向某个Acceptor集合中的成员发送请示，要求它作出如下回应： （a）保证不再通过任何编号小于n的提案。 （b）当前它已经通过的编号小于n的最大编号提案，如何存在的话。 我们把这样的请求称为编号为n的prepare请求。如果Proposer收到来自集合中多数成员的响应结果，那么它可以提出编号为n，value值为v的提案，这里v是所有响应中最大编号提案的value值，如果响应中不包含任何提案，那么这个值就由Proposer自由决定。 Proposer通过向某个Acceptor集合发送需要被通过的提案请求来产生一个提案（这里的Acceptor集合不一定是响应前一个请求的集合）。这们把这个叫做accept请求。 目前我们描述了Proposer端的算法。那么Acceptor端是怎样的呢？它可能会收到来自Proposer端的两种请求：prepare请求和accept请求。Acceptor可以忽略任意请求而不用担心破坏算法的安全性。因此我们只需要说明它在什么情况下可以对一个请求作出响应。它可以在任何时候响应prepare请求也可以在不违反现有承诺的情况下响应accept请求。换句话说： P1a. 一个Acceptor可以通过一个编号为n的提案，只要它还未响应任何编号大于n的prepare请求。可以看出P1a包含了P1。 现在我们就获得了一个满足安全性需求的提案选定算法——假设在提案编号唯一的前提下。只要再做点小优化，就能得到最终的算法了。假设一个Acceptor收到了一个编号为n的prepare请求，但是它已经对编号大于n的prepare请求作出了响应，因此它肯定不会再通过任何新的编号为n的提案。那么它就没有必要对这个请求作出响应，因为它肯定不会通过编号为n的提案，于是我们会让Acceptor忽略这样的prepare请求，我们也会让它忽略那些它已经通过的提案的prepare请求。通过这个优化，Acceptor只需要记住它已经通过的提案的最大编号以及它已经响应过prepare请求的提案的最大编号。因为必须要在出错的情况下也保证P2c的不变性，所以Acceptor要在故障和重启的情况下也能记住这些信息。Proposer可以随时丢弃提案以及它的所有信息——只要它可以保证不会提出具有相同编号的提案即可。 把Proposer和Acceptor的行为结合起来，我们就能得到算法的如下两阶段执行过程：Phase 1:Proposer选择一个提案编号n，然后向Acceptor的多数集发送编号为n的prepare请求。如果一个Acceptor收到一个编号为n的prepare请示，且n大于它所有已响应请求的编号，那么它就会保证不会再通过任意编号小于n的提案，同时将它已经通过的最大编号提案（如果存在的话）一并作为响应。Phase 2:如果Proposer收到多数Acceptor对它prepare请求（编号为n）的响应，那么它就会发送一个编号为n，value值为v的提案的accept请求给每个Acceptor，这里v是收到的响应中最大编号提案的值，如果响应中不包含任何提案，那么它就可以是任意值。如果Acceptor收到一个编号为n的提案的accept请求，只要它还未对编号大于n的prepare作出响应，它就可以通过这个提案。 一个Proposer可以提出多个提案，只要它能遵循以上算法约定。它可以在任意时刻丢弃某个提案（即使针对该提案的请求或响应在提案丢弃后很久才到达，正确性依然可以保证）。如果Proposer已经在尝试提交更大编号的提案，那么丢弃也未尝不是一件好事。因此，如果一个Acceptor因为已经收到更高编号的prepare请求而忽略某个prepare或者accept请求，它应该通知对应的Proposer，然后该Proposer可以丢弃这个提案。这是一个不影响正确性的性能优化。 2.3 获取被选定的提案值为了获取被选定的值，一个Learner必须要能知道一个提案已经被多数Acceptor通过了。最直观的算法是，让每个Acceptor在通过一个提案时就通知所有Learner，把通过的提案告知它们。这可以让Learner尽快找到被选定的值，但这需要每个Acceptor和Learner之间互相通信——通信次数等于二者数量的乘积。 在假设非拜占庭错误的前提下，一个Learner可以很容易地通过另一个Learner了解一个值已经被选定了。我们可以让所有Acceptor将它们的通过信息发送给一个特定的Learner，当一个value被选定时，由它来通知其他Learner。这种方法需要额外一个步骤才能通知到所有Learner，而且它也不是可靠的，因为那个特定的Learner可能会发生一些故障。但是这种情况下的通信次数，只需要二者数量之和。 更一般地，Acceptor可以将它们的通过信息发送给一个特写的Learner集合，它们中的任何一个都可以在某个value被选定后通知所有Learner。这个集合中的Learner越多，可靠性就越好，通信复杂度也相应更高。 因为消息可能会丢失，一个value被选定后，可能没有Learner会发现。Learner可以向Acceptor询问它们通过了哪些提案，但是任一Acceptor出错，都有可能导致无法分辨是否有多数Acceptor通过了某个提案。在这种情况下，只有当一个新的提案被选定时，Learner才能发现被选定的value。如果一个Learner想知道是否已经选定一个value，它可以让Proposer利用上面的算法提出一个提案。 2.4 进展性很容易可以构造出这样一种情况，两个Proposer持续地提出序号递增的提案，但是没有提案会被选定。Proposer p为编号为n1的提案完成Phase 1, 然后另一个Proposer q为编号为n2(n2>n1)的提案完成Phase 1。Proposer p对于编号n1的Phase 2的accept请求会被忽略，因为Acceptor承诺不再通过任何编号小于n2的提案。这样Proposer p就会用一个新的编号n3(n3>n2)重新开始并完成Phase 1，这又导致了Proposer q对于Phase 2的accept请求被忽略，如此往复。 ...