paxos算法在分布式领域有着非常重要的地位。但是，Paxos算法有两个明显的缺点：1.难以理解；2.工程实现比较困难。网上有很多讲解Paxos算法的文章，但是质量参差不齐。看了很多关于Paxos的资料，发现学习Paxos最好的资料就是论文《Paxos Made Simple》，其次是维基百科中英文版对Paxos的介绍。本文试图带你一步步揭开Paxos的神秘面纱。什么是Paxos？Paxos算法是一种基于消息传递的共识算法，具有很高的容错性。它是目前公认的解决分布式一致性问题最有效的算法之一。GoogleChubby的作者MikeBurrows表示，世界上只有一种共识算法，那就是Paxos，其他算法都有缺陷。虽然MikeBurrows说的有点夸张，但至少说明了Paxos算法的现状。然而，Paxos算法也因晦涩难懂而臭名昭著。这篇文章的目的是带领大家深入浅出地了解Paxos算法，不仅要了解它的执行过程，还要了解算法的推导过程，以及作者是如何一步步得出最终的解决方案的步。只有了解了推导过程，才能深刻把握算法的本质。而理解推导过程对我们的思考也很有帮助。可能会给我们带来一些解决问题的思路，启发我们。问题背景在常见的分布式系统中，总会出现机器宕机或网络异常（包括消息延迟、丢失、重复、乱序、网络分区）等情况。Paxos算法需要解决的问题是在可能出现上述异常的分布式系统中，如何快速、正确地对集群内某个数据的取值达成共识，并保证整个系统不会出现异常。无论上述任何异常情况如何，均已损坏。一致性。注意：这里的某个数据的值并不是狭义上的某个数字，它可以是一条日志，也可以是一条命令。..根据不同的应用场景，某个数据的值有不同的含义。相关概念在Paxos算法中，存在三个角色：ProposerAcceptorLearners在具体实现中，一个进程可能同时服务于多个角色。例如，一个进程可能同时是提议者、接受者和学习者。还有一个很重要的概念叫做提案（Proposal）。要商定的最终价值在提案中。注意：暂时考虑“proposal=value”，即proposal只包含value。在我们接下来的推导过程中，我们会发现如果proposal只包含value，就会出现问题，所以我们会重新设计proposal。暂时我认为“Proposer可以直接提出建议”。在我们接下来的推导过程中，我们会发现Proposer直接提出proposal会出现问题，需要增加一个学习proposals的过程。Proposer可以提出（propose）提案；Acceptor可以接受（accept）提案；如果一个提案被选中（chosen），那么提案中的值就被选中。回到刚才说的“对某个数据的值的约定”，就是说Proposer、Acceptor、Learner都认为选择（选择）了同一个值。那么，在什么情况下Proposer、Acceptor、Learner可以考虑选择一个值呢？Proposer：只要Proposer发出的提案被Acceptor接受（一开始只需要一个Acceptor接受，在推导过程中就会被接受）发现超过半数的Acceptoragree)，Proposer认为提案中的值已经被选中。Acceptor：只要Acceptor接受了一个proposal，Acceptor就任务要选择proposal中的值。Learner：Acceptor告诉Learner选择了哪个值，Learner认为选择了那个值。问题描述假设有一组流程可以提出（propose）价值（价值在proposalProposal中）。一个共识算法需要保证在提出的那么多值中，只有一个值被选中（选择）。如果没有提出任何值，则不应选择任何值。如果选择了一个值，那么所有进程都应该能够学习（learn）到所选值。对于共识算法，安全要求是：只能选择提议的值。只有一个值被选中，如果一个进程认为一个值被选中，那么这个值必须是实际被选中的那个。我们没有准确定义其活性要求。我们的目标是确保最终选择建议值。Whenavalueisselected,theprocesscaneventuallylearnthisvalue.Paxos的目标：保证一个值最终会被选中，当这个值被选中时，进程最终能够获取到选中的值。假设不同的角色可以通过发送消息进行通信，那么：每个角色都以任意的速度执行，可能会因为错误而停止，也可能会重新启动。选择一个值后，所有actor都可能会失败并重启，除非那些失败并重启的actor可以记录一些信息，否则重启后无法确定所选的值。消息在传递过程中可能会延迟任何时间长度，可能会重复或丢失。但是消息不会被破坏，即消息的内容不会被篡改（拜占庭将军问题）。推导过程中最简单的方案——只有一个Acceptor假设只有一个Acceptor（可以有多个Proposer），只要Acceptor接受它收到的第一个proposal，这个proposal就被选中，并且value中的建议选择设定值。这确保只会选择一个值。但是，如果唯一的Acceptor宕机，整个系统就无法运行了！因此，必须有多个Acceptor！多个Acceptor和多个Acceptor的情况如下图所示。那么，在多个Proposer和多个Acceptor的情况下如何保证一个值被选中呢？让我们开始寻找解决方案。如果我们希望即使只有一个Proposer提出一个值，最终也会选择该值。然后，获得以下约束：P1：Acceptor必须接受它收到的第一个提议。然而，这会导致另一个问题：如果每个Proposer提出不同的值并发送给不同的Acceptor。根据P1，Acceptor接受自己收到的值，导致选择不同的值。有一个不一致。如下图所示：就是因为“一个提案被一个Acceptor接受了，这个提案的值被选中了”导致了上面的不一致。因此，我们需要添加一个规则：规则：一个提案必须被半数以上的Acceptor接受才能被选中。该规则还暗示：“一个Acceptor必须能够接受多个提案！”否则，最后可能没有选择值。比如上图中的情况。v1、v2、v3没有被选中，因为它们只被一个Acceptor接受。开头提到的“proposal=value”已经不能满足需求了，所以重新设计了proposals，在每个proposal中增加了一个proposalnumber来表示proposals被提出的先后顺序。使“提案=提案编号+价值”。虽然允许选择多个提案，但必须确保所有选择的提案具有相同的值。否则又会出现不一致。所以有如下约束：P2：如果一个值为v的proposal被选中，那么每个被选中的编号较大的proposal的值也一定是v。一个proposal只有被Acceptor接受才能被选中，因此我们可以将P2约束重写为对Acceptor接受的提案的约束P2a。P2a：如果一个值为v的提案被选中，那么Acceptor接受的每个编号更高的提案也必须有一个值为v。只要满足P2a，就可以满足P2。但是，请考虑以下情况：假设总共有5个Acceptor。Proposer2提出了[M1,V1]提案，Acceptor2~5（过半）接受了提案，所以对于Acceptor2~5和Proposer2来说，都认为V1被选中了。Acceptor1刚刚从宕机状态恢复过来（Acceptor1之前没有收到任何提案），此时Proposer1向Acceptor1发送了一个[M2,V2]的提案（V2≠V1且M2>M1），对于Acceptor1来说，这是第一个它收到的建议。根据P1（一个Acceptor必须接受它收到的第一个提议。），Acceptor1必须接受这个提议！同时，Acceptor1认为V2被选中。有两个问题：Acceptor1认为V2被选中，Acceptor2~5和Proposer2认为V1被选中。有一个不一致。V1被选中，但是编号较大的Acceptor1接受的提议[M2,V2]的值为V2，且V2≠V1。这与P2a矛盾（如果选择了一个值为v的提案，那么Acceptor接受的每个编号更高的提案的值也必须为v）。所以我们需要加强P2a约束！P2a是Acceptor接受的提案约束，但实际上提案是由Proposer提出的，所以我们可以对Proposer提出的提案进行约束。得到P2b：P2b：如果选择了一个值为v的proposal，那么Proposer提出的任何一个编号较大的proposal的value也一定是v。P2a可以从P2b推导出来，进而可以推导出P2。那么，如何保证在一个值为v的proposal被选中后，Proposer提出的编号较大的proposal的值为v呢？只要满足P2c：P2c：对于任意N和V，如果提议[N,V]被提议，则存在一个由半数以上Acceptor组成的集合S，满足以下两个条件中的任意一个：S中的每个Acceptor都没有接受过编号小于N的提案。S中Acceptor接受的编号最大的提案的值为V。Proposer生成提案以满足P2b，这里有一个重要的思路：在Proposer生成之前提案，它应该首先“学习”已经选择或可能选择的值，然后使用这个值作为它提出的提案的值。如果没有选择任何值，Proposer可以自行决定该值的取值。只有这样才能达成共识。这个阶段的学习是通过“准备请求”来实现的。于是我们得到了如下的提案生成算法：Proposer选择一个新的提案编号N，然后向一组Acceptor（一半以上）发送请求，要求该集合中的每个Acceptor做出如下响应（response）。(a)向Proposer承诺，任何数量小于N的提案都不会被接受。(b)如果Acceptor已经接受了该提议，则以小于N的最大数量的已被接受的提议回应Proposer。我们称这个请求为编号为N的Prepare请求。如果Proposer收到超过半数的Acceptor的响应，它可以生成一个编号为N，ValueV的提案[N,V]。这里的V是提案的Value在所有回答中数量最多。如果所有的响应中都没有proposal，那么此时V可以被Proposer选中。提案生成后，Proposer将提案发送给半数以上的Acceptor，并期望这些Acceptor接受该提案。我们称此请求为接受请求。（注：此时接受Accept请求的Acceptor集不一定是之前响应Prepare请求的Acceptor集）Acceptor接受提议。Acceptor可以忽略任何请求（包括Prepare请求和Accept请求）而不用担心破坏算法的安全性。因此，我们这里要讨论的是Acceptor什么时候可以响应一个请求。我们对Acceptor接受提案给出如下约束：P1a：只要Acceptor没有响应任何编号大于N的Prepare请求，那么他就可以接受编号为N的提案。如果Acceptor收到编号为N的Prepare请求，之前响应过编号大于N的Prepare请求。根据P1a，Acceptor不能接受编号为N的提案。因此，Acceptor可以忽略编号为N的Prepare请求。当然你也可以回复一个error，让Proposer知道他的提案最早不会被接受可能的。因此，一个Acceptor只需要记住：1.被接受的编号最高的提案和2.已被响应的编号最高的请求。Paxos算法描述经过上面的推导，我们总结一下Paxos算法的流程。Paxos算法分为两个阶段。具体如下：Phase1：(a)Proposer选择一个编号为N的提案，然后向超过半数的Acceptor发送一个编号为N的Prepare请求。(b)如果一个Acceptor收到编号为N的Prepare请求，并且N大于该Acceptor已响应的所有Prepare请求的数量，则它会接受它已接受的编号最大的提案（如果有的话）。)作为对Proposer的回应，Acceptor承诺不接受任何编号小于N的提案。Phase2：(a)如果Proposer收到超过半数Acceptor对编号为N的Prepare请求的回应，则它将向超过半数的Acceptor发送对[N,V]提案的Accept请求。注：V是接收到的响应中编号最大的提案的值。如果响应不包含任何提案，则V由Proposer自己确定。(b)如果Acceptor收到一个编号为N的提案的Accept请求，只要Acceptor没有响应编号大于N的Prepare请求，它就会接受该提案。Learner学习选择值Learner学习（获取）选择值有三种选择：如何保证Paxos算法的活性通过选择主提议者，可以保证Paxos算法的活性。至此，我们得到了一个能够同时保证安全性和活性的分布式共识算法——Paxos算法。
