paxos made simple
介绍
paxos算法实现了带容错性的分布式系统一直被认为是难以理解的，可能是因为原来的表示对于读者来说是希腊语的。事实上他是最简单最显著的算法。他的核心是共识算法synod算法。下个章节会展示这种算法几乎不可避免的遵循我们想满足的性质，在最后一个章节我们将会解释完整的paxos算法。他通过直接将共识应用雨构建分布式系统状态机来获得的--一种应该是众所周知的方法，因为他可能是分布式系统理论种最常见的文章。
2共识算法
2.1问题
假设有一组可以产出值的进程。共识算法在提出的值中选出一个。如果没有值被产出，那么没有值会被选中。如果值被选中，这个进程将会学习选中的值。关于共识的安全需求是。
- 可以选择的值必须是已经被提出的
- 只有一个值被选中
- 一个过程永远不会知道一个值已经被选择，除非它实际上已经被选择了
我们不会试图的确定准确的存活需求。目标是确保提出的值最终选中，如果值已经被选中，那么进程可以最终学习到这个值。
我们通过三个代理人类别来实现共识算法中的三个规则：提出者，接受者，学习者。在实现中，单个进程可以充当多个的代理，但是从参数到流程的映射与我们无关。
假设代理可以与另一个代理发送信息进行交流。我们使用习惯的异步方法，非拜占庭模型，其中
- 代理以任意速度运行，可能由于停止而失败，可能重启。因为所有的代理可能在选择值和重新启动后都有可能失败，除非一些信息可以通过重新启动恢复，所以不可能有解决方案。
- 信息交付可能需要任意长的时间，可以被复制，可以丢失但是不会损坏
2.2选择值
最简单的选择值的方式是只有一个接收者。一个proposer发送提案给接受者，接收者选择第一个提出的值进行接受。算法简单，这个方案不能被接受因为接收者的失败会让之后的进展无法进行。
所以让我们尝试另一个方法选择值。让我们使用多个接受者，而不是单个接收者。proposer发送提案值到一组接收者。接收者可能接收提案值。当足够多的接收者接收到了值，这个值就被选中了。多少接收者收到才够呢？为了确保只有一个值被选中，我们可以让足够大的任何绝大多数代理。因为任何俩个多数只少有一个共同的接受者，所以一个接受者只能接受一个值，这种方法就有效。这是一个很明显的多数概论，这已经在很多论文中被观察到。
在没有故障或者信息丢失的情况下，我们想要选择一个值，即便只有一个值被一个proposer提出。它提出了以下要求。
- P1：接受者必须接受它收到的第一个提议。
但是这引发了一个问题。几个值可能被在不同的proposer在同一时间提出，导致了每个接受者都接受了一个值，但是没有一个值是被大多数人接受的。即便只有俩个被提出的值，如果每个值都被一半的接受者接受了，单一接受者的失败可能导致那个被选择的值不能被学习到。
P1和那个值只有当，这暗示着，接受者必须允许接受一个以上的proposal（提案）。我们通过为每个提案分配一个（自然）号码来跟踪接受者可能接受的不同提案，所以提案包含了提案好和值。为了防止混乱，我们需要不同的提案号。它如何达到目的取决于实现，所以现在我们只是做假设。当一个提案和它的值被大多数接受者接受，这个值被选中。在这种情况下，我们说提案(以及它的值)已经被选择。
我们可以允许多个提案被选中，但是我们必须确保所有被选中的提案有相同的值。通过归纳提案号就足以保证。
- P2：如果提案和值V被选中，那么被选中的编号值更大的提案也具有v。
因为值是完全有序的，条件P2保证了关键的安全问题：只有一个值被选中了。
要被选中，提案必须被只少一个接受者接受。因此我们可以通过以下来满足P2：
- P2a：如果提案和它的值v被选中，那么任何接受者所接受的编号更大的提案都具有值 v
我们仍然保持P1以确保一些提案是被选中的。因为交流是异步的，提案可能被一些没有收到任何提案的特殊的接受者C选择。假设新的提案“唤醒”和问题并发送具有不同值的更高编号的提案。P1需要c来接受这个提案违反P2a。为了同时维护P1和P2a需要加固P2a变为
- P2b：如果提案和它的值v被选中，则任何提案这发布的每个更高编号的提案都具有值v
因为提案必须由提议者发出，才能被接受人接受，P2b隐含着P2b，反过来也蕴含着P2。
为了发现如何满足提案P2b，让我们考虑我们如何证明它成立。我们假设一些提案，编号为m值为v。并证明任何编号为n>m的提案也具有值v。我们可以使用n的归纳法来使证明更简单，因此我们可以在附加的假设下证明提案号n具有值v，集中i...j百世从i...j的数字集合。为了提案号m被选中，一定存在集合C，它由大多数的接受者组成，使得C中的每个接受者都接受它。把这个和归纳假设结合起来，假设m被选中意味着：
- 每个C中的接受者都接受了在m...(n-1)中一个提案和它的值，并且被任何接受者所接受的编号在m到n-1之间的所有提案都具有值v。
由于大多数接受组合组成的集合S至少包含一个C中的元素，我们可以通过确保以下不变形得到维持，从而得出编号为n的提案具有值v的结论
- P2c：对于任何v和n，如果提案值v和编号n已被发布，那么就有一个集合S由大多数的接受者构成，满足一下俩个条件之一：(a)没有接受者接受过编号小于n的提案，或者（b）v是S中小于n的天被接受的提案中编号最高的提案值。
因此我们可以通过维持P2c的不变性来满足P2b
为了维持P2c的不变形，那些想要发布编号为n提案的proposer，必须学习编号小于n的最大提案，如果有的话，她已经或将要被大多数的接受者所接受。了解已经被接受的提案是很容易的，预测未来是非常困难的。提议者不是试图预测未来，而是通过提取不会有任何此类接受的承诺来控制未来。换句话说，proposer需要接受者不接受任何其他的小于n的提案号，这导致了以下用于发布提案的算法。
proposer选择新的提案号n和发送请求到每个接受者集合，要求他们回应：
- （a）承诺不再接受小于n的数字
- （b）小于n的最大编号提案（如果有的话）
我们将这样的请求称为编号为n的准备请求。
- 如果proposer从大多数接受者哪里收到了请求响应，那么它可以发出一个编号为n值为v的提案。其中v是响应中最大编号值的提案，或者如果响应者没有报告任何建议提案，则是提议者选择的任何职。
proposer通过向一组接受者发送提议的请求来发布提案。（这不需要是响应初始请求的同一组接受者）我们称之为接受请求。
这描述了proposer的算法。那么接受者如何呢？它可以接受俩种类型的来自proposer的请求：准备请求和接受请求（prepare requests and accept requests.）。接受者可以忽略任何请求而不影响安全性。我们只需要说明何时允许对请求做出响应。它可以响应请求，接受提议，当且仅当它没有承诺不接受该提案。换句话说：
- P1a：一个接受者可以接受被编号n的提案，当且仅当没有响应过准备请求有比n大的数字
观察P1a包含了P1
现在我们有了完整的选择值的算法它满足需要的安全特性--假设唯一的提案编号。最终后的算法是通过一个小的优化得到的。
假设接受者接受了一个编号为n的准备请求，但是它已经回复了一个编号比n大的准备请求，因此将会承诺不接受新的请求n。接受者就没有理由去响应新的准备请求，因此它将不会接受proposer想要发出的编号为n的提案。所以我们让接受者忽略这样的准备请求。我们还让接受者忽略它已经提议出的准备请求。
通过这个优化，接受者需要只记住它接收过的最高的编号的提案，并只响应最高编号的提案。因为P2c必须保持不变，即使会失败，接受者必须忘记这个信息即便它失败或重启。记住这个proposer可以放弃一个提议，并忘记整个提议--只要它不再试图发送相同编号的提案。
将proposer和接受者的行为放在一起，我们看到这个算法操作遵循以下阶段
阶段1
(a)proposer选择一个提案号n并且发送编号为n准备请求到大多数接受者。
(b)如果接受者收到一个请求编号n，大于任何它已经响应过的准备请求，那么它响应请求并承诺不在接受任何编号小于n的提案，并接受编号最高的提案（如果有的话）。
阶段2
(a) 如果proposer接受到来自大多数接受者它准备请求的响应（编号为n），那么它发送编号为n值为v的接收请求（accpet request）到每个接受者，其中v是响应中最大编号的提案值，如果响应没有报告提案，则为任何值。
(b)如果接受者收到了提案编号为n接受请求，它接收提议，除非它已经响应了一个数字大于n的准备请求。
proposer可以制造多个提案，只要每一个都遵循这个算法。它可以在协议中的任何时间放弃提案。（正确性被保证了，即便请求和响应可能在放弃提议后很久才能到达目的地，但仍然保持了准确性。）如果一些提议者已经开始尝试提出更高数字，那么放弃提案可能是个好主意。因此，如果接受者因为接收到了一个数字忽略了准备和接受请求，那么它应该通知申请人，谁应该放弃他的提案。这是一种不影响正确性的性能优化
2.3学习一个选定的值
为了学习到已经被选中的值，学习者必须找到那个被大多数接受者接受的提案。最明显的算法是让每个接受者，每当接它接收提案时，响应给所有的学习者，发送它们的提案。这使得学习者可以尽快的找到被选择的值，但是需要每个接受者响应每个学习者--响应的数量等于接受者数量和学习者数量的乘积。
非拜占庭故障的假设，使得一个学习者可以从另一个学习者那里发现一个已经被接受的值。我们可以让接受者用他们的接收来响应一个指定的学习者，当值被选中时，这反过来通知其他学习者。这个方法需要额外的一轮来让所有的学习者发现所选的值。它也不太可靠，因为学习者可能会失败。但是需要响应的数量只等于接受者数量和学习者数量的总和。
更广泛的，接受者可以使用它们的接收来进行响应一些指定的学习者组，它值被选中时，它们中的每一个都可以通知所有的学习者。使用大的指定学习者集合在复杂的沟通下提供了好的稳定性。
因为信息丢失，可以选择一个值，而不被学习者发现，学习者可以问接受者他们接受了什么提案，但是失败提案可能导致不知道大多数接受者是否接受了某一提议。在这个例子中，只有在新的提案被选择时，学习者才会发现选择了什么值。如果学习者需要知道一个值是否已经被选中了，它可以让proposer使用上面描述的算法发出提案。
2.4 进展
很容易构建一个设想，俩个proposal每个保持发出编号递增的提案序列，没有一个是被选中的。proposer p完成了一阶段提案号为n1。另一个proposal q完成了一阶段提案号位n2>n1。proposal阶段2的对于提案号n1的接收请求将会被忽视，因为接受者已经承诺了不在接受任何小于n2的提案号。所以proposer p之后开始完成1阶段一获得一个新的填好n3>n2，这导致了proposer q的2阶段接受请求将被忽视，以此类推。
为了确保进展，必须选择一个指定的提议者作为唯一尝试提出提案的人。如果指定的proposer可以成功的和大多数接受者交流，并且如果使用的提案号大于任何已经用过的，那么它将被成功的发表一个被接受的提案。通过放弃一个提案，如果它了解到某个提案的更高的请求，再试一次，指定的proposer将最终成为足够高的提案号。
如果足够的系统（proposer，接受者，通信网络）正常工作。因此，可以通过通过选择一指定的proposer来实现活性。Ficher，Lynch和Patterson的著名结果表明，一个可靠的选举proposer的算法必须使用随机型或者实时性--例如，通过使用超时。然而无论选举是否成功，安全性都得到了保证。
2.5 实现方案
paxos边摸与专门的leader选举机制。任何节点都可以成为一个提议者（Proposer），但为了简化决策过程和避免多个提议者之间的冲突，通常会选出一个节点作为Leader。Leader负责提议值并协调整个共识流程。如果系统中没有Leader或有多个Leader同时提议值，可能会导致冲突或效率降低。
basic-paxos中没有leader的概念，只有multi-paxos中有leader的概念。
其中instance（实例）是无限长的列表，每达成一个提案我们就把这个达成共识的天放在instance中，有了leader之后承诺编号就可以保持不变，解决了活锁问题。
- leader先进行prepare请求，递增提案编号，然后广播给所有的accepter。然后如果提案编号最大接受提案，并且承诺不接受更小的提案号（和basic-paxos一样）。
- 如果leader拿到了多数的承诺，发起accept阶段，指定提案值，保持之前的提案编号。把消息广播给所有的accepter并得到了多数的响应。然后以此类推。（只使用一个提案号）
paxos算法假设一个进程网络。在它的一致性算法中，每个进程扮演者proposer，接受者，和学习者的角色。算法选择leader， 它扮演者指定的proposer的和指定的学习者角色。paxos一致性算法是准确的正式上面描述的，其中请求和响应作为普通消息发送。（相应信息是被对应的提案号标记的以避免混淆。）稳定的存储在故障期间保存，他被用来维护那些接受者忘记的信息。在实际发送响应之前，接受者将其预期的响应记录在稳定的存储中。
剩下的就是对于保证机制的描述，没有俩份提案的编号是相同的。不同的proposer从不相交的数据集中选择它的编号，所以俩个不同的proposer不会发出相同的编号，每个proposer都记得它试图发表的（在存储中）最高编号提案，并且使用一个比他用过的更高的提案编号来开始第一阶段。
实现状态机
一个简单的实现分布式系统就像一个向中央服务器发出命令的客户端集合。服务可以被描述为确定的状态机，它按某种顺序执行客户端命令。状态机有当前状态，它通过名令行作为输入并产生输出一个新的状态来执行一个步骤。例如，分布式的银行系统客户可能是柜员，状态机的状态可能是所有用户账户的余额组成的。取款将通过执行状态机命令来执行，当且仅当账户余额大于提款金额的时候，账户余额才会减少，产生新的和旧的余额作为输出。
使用单一中央服务器实现方式会在该服务发生故障时失效。因此我们使用服务集合作为替代，每一个都独立的实现状态机。因为状态机是确定的，如果他们使用相同的命令序列，所有的服务都会产生相同的状态序列和输出。发出命令的客户端可以使用任何服务生成的输出。
保证所有服务的执行相同的状态机序列命令，我们实现了paxos共识算法的一系列独立实现，第i个实例所选中的值就是第i个状态机的命令。每个服务扮演了所有的角色（proposer，接受者和学习者）在算法的每个实例中。现在，我们假设一组服务是固定的，所有的共识算法的实力都使用一组相同的代理。
在常规的操作中，单个服务被选举成为leader，在共识算法的所有实体中，它作为一个被选中的proposer(唯一一个试图提出提案的人)。客户端发送命令道leader，leader确定每个命令应该出现在序列中的哪个位置。如果leader决定某个客户端的命令应该是第135条命令，它试图将该命令宣威共识算法的第135个实例的值。它通常都会成功。它可能会因为故障而失败，或者因为另一个服务也认为突然自己是leader并且对于它在第135的位置有着不同的意见。但是共识算法确保了最多只能一个命令作为第135条命令。
这种方法的效率关键在于，在paxos共识算法中，知道阶段2才选择要建议的值。回顾一下，在proposer算法的第一阶段后，提议者的值是确定的，否则提议者可以自由提出任价值。
我们现在将描述paxos的状态太极实现在通常操作下的工作。之后我们将讨论可能出现的问题。我们考虑前任leader失败新leader被选中时将会发生什么（系统启动是特殊的例子，这种情况下没有命令被提出）。
新的leader，在共识算法中作为一个学习者，需要知道大部分已经被选中的命令。假设它知道命令1-134,138,和139也就是说在共识算法实例1–134、138 和 139 中选择的值。（我们之后会讲看到命令序列中的这种间隙是如何产生的）它之后执行实例135-137和所有大于139的实力的阶段1（我们在下面描述如何做到这一点）。假设执行执行的结果决定了实例135-140中提议的值。但是其他实例中提议的值没有限制。然后leader对实例135和140执行阶段2，从而选择命令135和140。
leader和任何学习到所有leader已知的命令的其他的服务，可以执行命令1-135。然而他们不能执行命令138-140，尽管他们也知道这些命令，因为命令136-137还没有被选择。leader可以将客户端请求的下俩个命令作为136和137。相反，我们通过提议命令136和137设为特殊的no-op命令来填补这个空缺，该命令不会改变状态。（它通过执行一致性算法的事例136和137来实现这一点。）一个这样的no-op命令被选中了，138-140命令可以被执行。
这里的np-op就是空占位符，可以保持日志一致性，简化恢复机制
Leader会为每个客户端请求分配一个递增的命令编号，以确保在日志中顺序一致性。
命令1-140现在已经被选中了。leader也完成了共识算法中所有大于140实例的第一阶段，在实例的第二阶段，它可以自由地提出任何值。它指派命令编号141到客户端请求的下一个命令，并将它作为共识算法的第141个实例的第二阶段中将其作为提议的值。他将受到下一个客户端的命令提议为命令142，以此类推。
在它了解到命令141已经被选择之前，leader可以提议命令142。它在提议141中发送的所有信息都有可能丢失，并且在让任何服务器了解到leader提议的命令141之前，命令142可以被选择。当leader在实例中没有收到对阶段2消息的预期响应时，它将重新传输这些信息。如果一切顺利提案的命令将会被选中，然而，它可能首先失败，在被选中的命令序列中留下一个空缺。一般来说，假设一个leader可以提前得到$\alpha$个命令--即，在命令1到i被选中后，它可以提议命令i+1到i+$\alpha$。这样将会出现$\alpha$-1个命令的缺口。
新选择的领导者执行共识算法的无限多个实例阶段1--在上面的场景中，对于实例135-137和所有比139大的实例。对所有的实例使用了相同的提案号，它可以通过发送一个合理的短消息到其他服务来做到。在阶段1，只有当接受者已经从某个提议者那里收到了阶段2的消息时，它才会响应不止一个简单的OK。（在场景中，这只适用于135和140。）因此，服务（作为接受者）可以用一条合理的短消息响应所有实例。执行阶段1的无限多个实例不会造成任何问题。
因此leader的失败和新的选举应该是罕见的事件，执行状态机命令的有效成本--即，在命令和状态上达成一致--只是执行共识算法的第二阶段的成本。paxos共识算法有着任何算法最小可能的代价，以在存在错误的情况下达成一致。因此，paxos算法本质上是最佳的。
这个对于系统假定的常规操作的讨论，总是有一个唯一的leader，除了现任leader和当选的心leader之间的短暂周期。在异常的情况下，leader的选举会发生异常。如果没有服务作为leader，那么没有心的命令会被提出。如果多个服务他们是leader，那么他们可以在共识算法的相同实例中提出值，这可能会组织任何值被选择。然而，安全性被保证了--俩个不同的服务将永远不会在对第i个状态机命令的选择上有分歧。进需要选举一个leader来确保进展。
如果服务集合可以改变，那么必须有某种方法确定那些服务器实现了共识算法的哪些实例。最简单的方法是通过状态机本身。当前的服务集可以成为状态的一部分，可以通过普通的状态机命令改变。我们可以让执行共识算法的实例i+$\alpha$的服务器集合由第i个状态机执行后的状态的来指定，从而允许领导者提前获得$\alpha$个命令。这允许一个任意复杂的重新配置算法的简单实现。