谷歌的粗粒度锁服务Chubby的设计者和开发者Burrows曾说过：所有的共识协议本质上要么是Paxos，要么是它的变种。网上有很多讲解Paxos算法的文章，但是质量参差不齐。今天，笔者就带大家深入聊一聊Paxos。什么是Paxos？Paxos算法是一种基于消息传递的共识算法，具有很高的容错性。它是目前公认的解决分布式一致性问题最有效的算法之一。Paxos算法是2013年获得图灵奖的Lamport大师提出的一种基于消息传递的分布式共识算法，自Paxos问世以来，持续垄断分布式共识算法。Paxos这个词几乎等同于分布式共识。Google的很多大型分布式系统都使用Paxos算法来解决分布式一致性问题，比如Chubby、Megastore、Spanner。MySQL5.7引入的开源ZooKeeper和MySQLGroupReplication来替代传统的主从复制，采用了Paxos算法来解决分布式一致性问题。但它也有两个明显的缺点：难以理解，工程和实现上比较复杂。问题背景在常见的分布式系统中，总会出现机器宕机或网络异常（包括消息延迟、丢失、重复、乱序、网络分区）等情况。Paxos算法需要解决的问题是在可能出现上述异常的分布式系统中，如何快速、正确地对集群内某个数据的取值达成共识，并保证整个系统不会出现异常。无论上述任何异常情况如何，均已损坏。一致性。这里的某个数据的值不仅仅是狭义上的某个数字，它可以是一条日志，也可以是一条命令。根据不同的应用场景，某个数据的值有不同的含义。相关概念在Paxos算法中，存在三种角色：Proposer（提议者）Acceptor（人大代表）Learner（普通大众）需要注意的是，在具体的算法实现过程中，并不是一个过程只能扮演其中一个角色，它可以同时充当多个。例如，一个进程既是Proposer、Acceptor又是Learner。还有一个很重要的概念叫Proposal。要商定的最终价值在提案中。这个提案包括什么？它只包含信息价值吗？下面我们继续往下看是怎么回事。目前，我们认为它只是一个普通的值。第一次了解Paxos算法的过程和我国的立法过程非常相似（法案提案、法案审查、法案表决、法律公布四个阶段）。所谓提案，就是新颁布的法律。提议者（proposer）可以提出（propose）提案；Acceptor可以接受（accept）提议；如果一个提案被选中（chosen），那么提案中的值就被选中。回到刚才说的“对某个数据的值的约定”，就是说Proposer、Acceptor、Learner都认为选择（选择）了同一个值。那么，什么情况下Proposer、Acceptor、Learner可以考虑选择某个值呢？Proposer：只要Proposer发出的提案被Acceptor接受（一开始只需要一个Acceptor接受，在推导过程中会发现需要超过半数的Acceptor同意),Proposer认为提案中的值被选中。Acceptor：只要Acceptor接受了一个提案，Acceptor就认为提案中的值被选中。Learner：作为学习者，Acceptor告诉Learner选择了哪个值，Learner认为选择了那个值。问题描述假设有一组进程（proposerteam）可以提议（propose）值，一个共识算法需要保证在这么多提议值中只选择（chosen）一个相同的值。也就是说，要么不提出价值，只要提出价值和选择价值，最后大家学习到的价值一定是一致的。对于共识算法，安全要求是：只能选择提议的值。仅选择一个值。如果进程认为选择了一个值，那么这个值必须是实际选择的值。Paxos的目标：保证一个值最终会被选中，当这个值被选中时，进程最终能够获取到选中的值。俗话说，有需求的地方，就会有不好的问题。如果假设不同的角色可以通过发送消息进行通信，那么：每个角色都以自己任意的速度进行通信和执行，而在这个过程中，错误可能会因为各种原因导致执行停止或重启。选择一个值后，由于故障恢复正常的角色会丢失一些重要信息，导致他们无法确定选择的值。消息在传递过程中可能会延迟任何时间长度，可能会重复或丢失。但是消息不会被破坏，即消息的内容不会被篡改（拜占庭将军问题）。以上是可能遇到的问题，如何解决？？？推导过程中最简单的方案——只有一个Acceptor假设只有一个Acceptor（可以有多个Proposer），只要Acceptor接受它收到的第一个proposal，这个proposal就被选中，并且value中的建议选择设定值。这确保只会选择一个值。但是，如果唯一的Acceptor宕机，整个系统就无法工作了！所以，一个Acceptor是不可行的，必须有多个Acceptor！MultipleAcceptor当有多个Acceptor时，如何保证在多个Proposer和多个Acceptor的情况下选择一个值？大家可以先自己想想。首先，我们的最终目标是无论有多少Proposer提出提案，都只有一个值被选中。那么，我们可以先定义一个约束：P1：一个Acceptor必须接受它收到的第一个提议。但是这种方式还会有其他的问题：如果每个Proposer提出的proposalvalue都不一样，而这个proposal发送给了不同的Acceptor。根据P1约束，每个Acceptor都接受自己收到的第一个proposal，选择不同的值，导致不一致。就是因为“一个提案被一个Acceptor接受了，这个提案的值被选中”导致了上面的不一致。因此，我们需要添加一条规则：规则：一个提案需要被半数以上的Acceptor接受才能被选中。如果一个提案被超过半数接受，则意味着“一个Acceptor必须能够接受多个提案！”’，否则可能导致最后没有选到值。比如上图中的情况。v1、v2、v3没有被选中，因为它们只被一个Acceptor接受，没有被超过半数的Acceptor接受。一开始，[proposal=value]已经不能满足现在的需求了，因为当一个Proposer向一个Acceptor发送多个proposal时，需要用一个数字来区分它们被提议的先后顺序。现在[提案=提案编号+价值]。虽然允许选择多个提案，但必须确保所有选择的提案具有相同的值。否则又会出现不一致。P2：如果选择了一个值为v的提案，那么每个被选中的编号更高的提案也必须具有值v。一个提案只有在被Acceptor接受时才能被选中，因此我们可以将P2约束重写为约束P2aonAcceptor接受的提案。P2a：如果一个值为v的提案被选中，那么Acceptor接受的每个编号更高的提案也必须有一个值为v。只要满足P2a，就可以满足P2。但是，考虑以下情况：以立法过程为背景，假设人大代表（接受人）共有5人。人民法院（Proposer2）提出[M1,V1]议案，第2-5号人大代表（过半数）接受了该议案，因此对于第2-5号人大代表和人民法院，他们都认为选择了V1提案。此时全国人大代表1在完成其他事务后也参与其中（全国人大代表1此前未收到任何提案），此时最高人民检察院（另一提案人Proposer1）送来【M2，提案V2]（V2≠V1且M2>M1），对于NPC代表1，这是它收到的第一个提案。根据P1（一个Acceptor必须接受它收到的第一个提案。），NPC代表1必须接受这个提案！同时，NPC代表1认为V2被选中。出现两个问题：人大代表1认为选V2，人大代表2-5和人民法院认为选V1。有一个不一致。选择了V1，但人大1采纳的议案[M2,V2]中数值较大的为V2，且V2≠V1。这与P2a矛盾（如果选择了一个值为v的提案，那么Acceptor接受的每个编号更高的提案的值也必须为v）。因此，我们需要加强P2a约束！P2a是Acceptor接受的提案约束，但实际上提案是由Proposer提出的，所以我们可以对Proposer提出的提案进行约束。得到P2b：P2b：如果一个值为v的proposal被选中，那么Proposer提出的任何一个编号较大的proposal的value也一定是v。那么，如何保证在一个值为v的proposal被选中后，Proposer提出的编号较大的proposal的value都是v呢？只要满足P2c：P2c：对于任意N和V，如果提议[N,V]被提议，则存在一个由半数以上Acceptor组成的集合S，满足以下两个条件中的任意一个：没有一个Acceptor接受过数量小于N的提案。S中Acceptor接受的数量最多的提案的值为V。Proposer生成提案以满足P2b，这里有一个重要的想法：Proposer在生成提案之前，它应该首先“学习”已经被选中或者可能被选中的值，然后将这个值作为它提出的proposal的值。如果没有选择任何值，Proposer可以自行决定该值的取值。只有这样才能达成共识。这个阶段的学习是通过“准备请求”来实现的。于是我们得到如下提案生成算法：(1)Proposer选择一个新的提案编号N，然后向一组Acceptor（一半以上）发送请求，要求该集合中的每个Acceptor做出如下响应（response):向Proposer承诺，不接受编号小于N的提案。如果Acceptor接受了提案，它将接受的最大编号小于N的提案响应给Proposer。我们称此请求为编号为N的Prepare请求。(2)如果Proposer收到超过半数的响应Acceptors，它可以生成一个编号为N，Value为V的提议[N,V]。这里的V是所有响应中编号最大的提议的Value。如果所有响应中都没有提案，那么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只需要记住：它接受过的编号最高的提案和它响应过的编号最高的请求。Paxos算法描述经过上面的推导，我们总结一下Paxos算法的流程。Paxos算法分为两个阶段。具体如下：第一阶段：Proposer选择一个编号为N的提案，然后向半数以上的Acceptor发送一个编号为N的Prepare请求。如果一个Acceptor收到一个编号为N的Prepare请求，并且N大于该Acceptor已经响应的所有Prepare请求的数量，那么它会把它已经接受的编号最高的提案（如果有的话）反馈给该AcceptorProposer，Acceptor承诺不接受任何编号小于N的提案。Phase2：如果Proposer收到超过半数的Acceptor对编号为N的Prepare请求的响应，它将发送一个Accept请求[N,V]向超过半数的Acceptor提出建议（不同于以往的Acceptor）。必须相同）。注：V是接收到的响应中编号最大的提案的值。如果响应不包含任何提案，则V由Proposer自己确定。如果Acceptor收到一个编号为N的提案的Accept请求，只要Acceptor没有响应编号大于N的Prepare请求，它就会接受该提案。Learner学习选定的值。Learner可以通过三种方式学习（获取）所选值：Option1：Acceptor收到提案并将提案发送给所有Learner。优点：Learner可以快速获取选择的值value缺点：通信次数为M*N（M为proposal数量，N为Learner数量）。方案2Acceptor接受一个提案，并将提案发送给主Learner，主Learner通知其他Learner。优点：减少了通信次数（M+N-1）（M是proposals的数量，N是learner的数量，M个proposal发送给mainlearner，然后mainlearner通知N-1个learner）缺点：单点故障问题（主learner可能会失败）Option3Acceptor接受一个proposal，将proposal发送给Learner组，Learner组再通知其他Learner。优点：解决2单点故障问题，可靠性好缺点：实现复杂，网络通信复杂度高如何通过选择主Proposer来保证Paxos算法的活跃性，才能保证Paxos算法的活跃性。通过选择主要提议者并指定只有主要提议者可以提议提案。这样，只要主Proposer和半数以上的Acceptor能够在网络中正常通信，如果主Proposer提出一个编号更高的提案，则该提案最终会被通过，从而通过选出一个主Proposer，整个Paxos算法可以保持活跃。至此，我们得到了一个能够同时保证安全性和活性的分布式共识算法——Paxos算法。综上所述，我们已经详细阐述了Paxos算法是什么，它的特点，以及算法的具体推导过程。Paxos算法是很多共识算法的变种，值得学习。
