Paxos在分布式系统中的重要性无需多言。我们能在网络上找到非常多解析Paxos原理的文章，这些文章大部分只讲协议的过程，有些深入的文章还会讲协议的证明，我总感觉缺少对Paxos协议“生动直观”的理解。最终我认为最直观解释Paxos的文章是作者Lamport在2001年发表的《Paxos Made Simple》。作者写这篇文档的目的是因为1998年发表的paxos原文《The part-time parliament》被很多人吐槽晦涩难懂。在《Paxos Made Simple》文中作者对Paxos协议做了一次从简单场景到完整协议的推演。我写这篇文章没有什么新奇的地方，仅仅写我对《Paxos Made Simple》的推演过程的消化理解。

Paxos协议要解决的问题：

在一个不可靠的分布式环境中，各个实体达成一个一致的状态。

如果系统中只有一个proposal，那么这个proposal的提议在大多数acceptor存活时，必须要被接受。因此

P1.  An acceptor must accept the first proposal that it receives.

如果有多个proposal，每个acceptor只接受第一个proposal而拒绝后续所有的proposal的话。那么就可能会导致每个proposal都不能被大多数acceptor接受，导致协议无法收敛。因此：

每个acceptor接受的proposal不止一个，当然，只有被大多数acceptor接收的proposal才会被chosen

因此，我们允许多个proposal被选中，但是必须保证：这些被选中的proposal都有同样的value。也就是说：

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

如何来保证只要一个value为v的proposal被chosen，后续的proposal的值都为v呢？

P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

简单啊，只要保证后面的被acceptor的proposal的值都为v就好了。那么如何保证后面的被accept的prososal都是v呢？

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

简单啊，只要后面proposer发出的proposal都为v就好了。（这不废话吗）

那么，如何保证一旦一个proposal被chosen，后续的proposal都跟之前的proposal有相同的value呢？

P2c. For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

意思是我们要把好proposal的出口这一关，就是说proposal不能瞎jb提，这样才能保证“达成一致”的这个过程最快速的收敛。P2c翻译一下的意思就是：对于任何一个proposal(n,v)（n是提案编号，v是提案值），如果要提出这个proposal，必须要满足一下的两个条件之一：

1. 大多数的acceptor都没有accept小于n的proposal； 或者

2. 大多数的acceptor accept的提案都小于n，这其中序号最大的一个提案的值就是v

怎么理解这两个条件呢？直观一点讲就是，如果你想提案，要么1）大多数acceptor没有接受过任何提案；要么2)你的提案跟之前最大编号的提案一样。

好，其实paxos本质上就是通过约束每个proposer要提出的proposal来达到快速达成一致的目的（收敛）。

那么如何来约束proposor提出的proposal呢？根据之前提出了两个条件，因此proposer在提出proposal之前，必须先“学习”，学习当前（大多数acceptor）最大提案的值。这个学习的过程叫做"Prepare":

Prepare阶段

一个Proposer要想提案，它首先得知道当前要么大部分acceptor没有接受过任何提案，要么找到一个在大部分acceptor组成的集合中最大的提案值。因此Proposer首先获取一个新的提案编号，然后使用这个编号N向大部分acceptor发送prepare请求。这些acceptor给proposer响应

1）要么大多数acceptor从来没有接受过任何提案

2）要么有部分acceptor告诉proposer当前最大的提案编号和提案值

    2.1 有部分Acceptor的接受的最新的提案大于等于N，不可能。因为Acceptor只返回小于N的最大编号和提案值。一个acceptor不会响应一个小于它当前提案编号的proposal。

    2.2 所有的提案编号都小于N。

3）有返回的acceptor没有达到大多数（proposal无法继续）

我们再看Acceptor在Prepare阶段的逻辑：

1）如果Acceptor没有承诺/接受过任何提案，那么向Proposal直接返回承诺，也就是后续不会接收小于N的proposal

2）如果Acceptor 承诺过一个小于N的提案，那么Aceeptor可以直接向Proposal再次承诺N，也就是之前的小于N的Proposal将永远不会被自己Accept

3）如果Acceptor接受过一个小于N的提案，那么返回这个提案编号和提案值

4）如果Acceptor承诺过一个大于N的提案，那么忽略当前为N的提案（承诺也没用，因为就算承诺了N，也不可能接受N）

5）如果Acceptor接受过一个大于N的提案，那么忽略当前为N的提案

一旦Acceptor给出了Prepare阶段的响应，意味着这个Acceptor将不会接受小于N的提案。什么意思呢？只要一个Proposal通过了Prepare阶段，也就意味着任何一个小于N的Proposal如果还没有Prepare，他将不能通过Prepare阶段，如果通过了Prepare，它也不会被大多数acceptor接受。相当于对整个acceptor集群做了一个锁定操作，即锁定不会有一个小于N的proposal被chosen。

但是也会出现这个问题，当为N的proposal在通过prepare阶段之后但是还没有还没有发送acceptor请求之前，另一个proposer发起了一个编号为N+1的proposal，这个时候N+1也可以通过Prepare阶段，接着另一个Proposor可能再发起一个N+2的proposal，这样整个协议过程将无法收敛。

Accept阶段

Proposer在Acceptor阶段的逻辑：当第一阶段学习(Prepare)完成后，Proposal收到了大部分Acceptor的响应。

1. 如果有一个最大的Proposal被接受，也就以为着当前没有任何一个大于N的proposal被chosen。那么Proposer将会用自己选用的Proposal编号和学习到的当前最大Proposal的值作为新提案发起Accept请求。 （是否意味着有可能已经有小于N的proposal被chosen？有可能。是否意味着有可能有多个小于N的proposal被chosen？有可能。但是没关系，因为这些已经被chosen的提案值和当前将要发出的提案值都一样）。

2. 如果大部分的Acceptor没有接受过任何Proposal，那么Proposer可以自己指定任何提案值发起Accept请求。

Acceptor在Accept阶段的逻辑：

P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

也就是，如果Acceptor没有承诺过大于N的proposal，那它就可以accept N。（如果他Accept过小于N的proposal呢？）。一个Acceptor需要记住两样东西：

1. 已经承诺过的最大提案编号，用来忽略大于此编号的prepare和accept请求

2. 已经接受过的最大提案编号和提案值，用来约束后续的提案值（通过后续提案的prepare请求）

到此为止，这个协议的逻辑算讲完了。