Paxos算法是Leslie Lamport于1990年在文献[1]中提出的一种基于消息传递且具有高度容错特性的共识算法（分布式系统间达成共识的算法，可以是信息达成共识、数据达成共识、意见达成共识等等，非事务的ACID中的C特性）。

Paxos字面含义，是Leslie Lamport在文献[1]中用模拟的希腊Paxos岛的岛屿名称。Paxos算法名称的由来，即源自Leslie Lamport在文献[1]提出的算法。

掌握Paxos，建议从wiki上的Paxos文章[1]开始。然后可以读《Paxos Made Simple》、《Paxos Made Live》等文章，通过了解算法背后的面对的问题、问题产生的背景，有助于深入理解Paxos协议。

Paxos所解决问题的背景

Paxos用于分布式系统中（包括多CPU、多核的单机环境），每个实体（单机、处理器）之间需要保持一致的场景。因此影响因素有两个，一是实体，二是消息传输渠道，对应到分布式系统中，常用Processors描述实体即物理节点，Network描述消息传输渠道即网络。

1. 实体：考虑实体在分布式系统中可能出现的错误情况如下：
1.1 实体的执行速度不可控，可快可慢。多个实体间在运行速度上不可期待。所以一致性协议需要考虑实体差异，屏蔽实体执行速度的差异。
1.2 实体有发生失败的情况。
1.3 实体失败后，恢复到失败前的状态，然后重新加入分布式系统。
1.4 新实体加入。
1.5 实体不会发生拜占庭将军问题（不会串通、撒谎或以其他方式破坏协议，简化了拜占庭将军问题）。
1.6 容忍N个实体发生失败，且至少有2N+1个个体存在于分布式系统中。

2. 消息传输渠道：考虑实体间在分布式系统中传递消息时可能出现的错误情况如下：

2.1 实体之间，通过消息传输渠道发送消息。

2.2 消息不可控。

1）消息是异步发送的，到达时间不确定，或早或晚。

2）消息可能丢失、多个消息间可能无序、消息复制。

2.3

消息传输过程不会发生拜占庭将军问题（消息不会被任意/恶意地篡改）。

Paxos中的角色

Paxos是一个协议，在这个协议中，首先把分布式系统中参与者“多个实体”划分为几种角色，然后赋予不同角色不同的作用，以方便表述协议内容。但是需要注意的是，不同角色之间可以集中于一个实体，也可以角色之间互相转换。所以从实体的角度看，角色其实是实体不同的操作。实体发起提议，则为Proposer；实体接收提议这个消息，则为Acceptor；发出提议被大多数实体接受后的实体就是Leader，此时，分布式系统中多个副本达成一致，满足了一致性，但这是局部一致性；在一个提议被接收、接受的过程中，作为少数派没有接收到或接受提议的实体，当有Leader出现后，则需要获得即学习“多数派认可了的值”，这样的实体就是learner。当leaner非实时地学习到了“多数派认可了的值”，则分布式系统中所有的实体达到了最终一致。具体角色的功能如下：

1. Client：向分布式系统发起任务请求，等待分布式系统回应。

2. Proposer，提议者：要区分场景，场景为选主或执行Client的任务。

2.1 但是一旦要执行Client的任务，则通常意味着已经成为了Leader，因为不可能让分布式系统中的每个实体都去执行Client的任务（无主架构例外，如AWS的Dynamo系统。无主，Leaderless），然后就各自执行结果的值再去征询其他实体的意见以达成一致。所以要区分场景，先选主，就哪个实体作为Leader达成一致，此时选主的过程就是各个实体作为Proposer发挥此角色作用的过程。而主一旦选定，在一个租期内一直作为Leader的角色存在，则Client发来新请求则省略选主的过程。

2.2 当选主完成，Leader负责执行Client的任务，执行结果发给其他实体（此时其他实体就是Acceptor角色），请Acceptor确认执行结果是否能够被大家认可，如果被大多数认可，就达成了一致，Acceptor执行Leader发送来的结果（如在数据库中执行REDO日志恢复数据）。

2.3 如果不选主，则一群Proposer发出提议，参与一致性达成的竞争，会有多轮“提议-接受”的过程，这样的过程轮数不可控且耗时，所以无主（不选主）意味着低效。这也是很多分布式系统中先选主的原因。

3. Acceptor (Voters)，接受者/提议回复者/选民：Proposer发出消息被认可，认可Proposer发出消息者就是一个Acceptor，认可消息需要特定的规则来保证认可的过程。

3.1 Quorum（法定人数，即多数派）：是K个Acceptor接受了同一个提议然后K这个值达到了所有带有角色的实体个数N的一半以上，则称K个Acceptor达到Quorum，即有多数派批准了提议。

3.2 反之，不接受消息即不认可消息（也许如因宕机而没有机会认可消息）而又处于正常状态（可收可发消息）的实体，被称为“learner”。在learner上没有与Leader一致的数据，因此，learner需要向Leader要数据，要数据的过程就是一个“学习”的过程，要数据的目的就是learner要与Leader和Acceptor保持数据的一致，当所有的节点数据达到一致则相关的节点（主副本、从副本）之间就处于一个一致的状态。

4. Learners：多数派之外的少数派。

5. Leader，领导者：在一个Paxos组中，通过上述的选主从多个Proposer中找出一个作为Leader，Paxos协议保证只能有一个Leader。

Basic Paxos协议

Paxos协议定义了一些规则，以约束各种角色之间的行为：

规则P2c：如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v。

角色之间传递的消息，有两种：

1. 一种是Proposer发出的消息，每一位Proposer的消息称为提案，提案带有一个唯一的“提案编号（Proposal Number）”（在一个Paxos实例中，不同提案编号间要存在全序关系）。

2. 一种是Acceptor发出的消息。消息中，包括“Agreed Value”。

Basic Paxos协议形成决议的过程分为两个阶段（即Paxos完成一次写操作需要两次来回），第一个阶段是提出决议（prepare/promise），第二个阶段是批准决议（propose/accept）。

1.Prepare阶段：

a) proposer选择一个提案编号n，并将prepare请求发送给所有acceptors（只要获得多数派的回应即可进入Accept批准阶段）。

i. 提案编号是单调递增的（提案编号使得提案之间呈全序关系，全序参见1.3.1节），proposer选择自己已知的最大提案编号然后加1后发出新提案。

ii. 多数派是通过数量确定的，不是固定的角色，只要proposer收到半数以上的回复，即确认已经把prepare请求发给了“多数派”。

b) acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息（回复消息表示接受提案），则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案。

i. 没有构成第一个“多数派的少数派”的acceptor，也可能因自己发出回应而成为“多数派”的新一员；也可能在本次提议下，成为永久的“少数派”。

ii. 少数派成员，未来需要通过Learners身份学习proposer提案中的values内容。

iii. 如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案。

2.Accept批准阶段：

a) 当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。proposer向回复prepare请求的acceptors发送accept请求：包括编号n和根据前述规则P2c决定的value；如果根据规则P2c没有已经接受的value，则proposer可以自行决定value。

b) 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求。

需要注意的是：在如上过程中，任何时候发生中断（网络分区、延时等发生）都应该保证正确性。例如：如果一个proposer发现已经有其他proposers提出了编号更高的提案，则需要中断这个过程；如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案。

终止一个提案，可能由编号更大的提案拥有者proposer提出终止之前的某个提案。之后，如果两个proposer都转而提出一个编号更大的提案，就可能陷入活锁状态，为了解决此问题，可引入随机睡眠-重试的方法加以解决。

决议形成后，需要发布给learners（acceptor已经接受过了决议）。因为前提假设了没有消息篡改，所以acceptors只需将批准的消息发送给某一个learner或learners的一个子集，然后learners间再获取已经通过的决议。但是，由于消息传递的不确定性，可能会没有任何learner获得了决议批准的消息，文献[1]给出了解决方式。

如下是Paxos协议的示意过程[2]。此过程中，四种角色，Aceptor包括3条竖线含义为多数派，Learner包括2条竖线含义为少数派。只有Learnder学习获得了新值之后，才返回到客户端。一个过程化的流程，可参考图1。