本文共 9936 字，大约阅读时间需要 33 分钟。
前言
本文的写作目的在于与大家分享笔者学习Paxos时的思路，希望对大家Paxos的理解有所裨益。
Paxos算法可以说是现代分布式系统建设中最基础的一致性算法，也是笔者见到最精妙的算法。但是Paoxs证明过程总让人感觉到晦涩难懂。笔者刚开始接触该算法时，也百思不解其中奥妙，也花了不少心思去设想一个又一个场景，直到算法可以解释地通为止。事实上，一旦理解，就如同算法作者Lamport所述，Paxos确实并不是很复杂的算法。
笔者认为，在分布式系统中，由于消息传递的时延，所有的进程收到的消息都只代表**“曾经”**的系统状态，进程必须仅凭这些"曾经"可信的消息(无拜占庭将军问题)，独立地去思考，并做出正确的决策。因此
我们着眼于某个进程，并假定系统中其他的进程都"足够聪明"，如果我们观察的进程也可以制定出"足够聪明"的决策，那么整个分布式系统也将"聪明"地达到一致。
笔者受到了知乎"拒绝策略"回答问题的提示，有想了解的朋友可戳
在古希腊的有一个叫做Paxos的小岛，岛上采用会议的形式来通过法令，议会中的议员通过信使进行消息的传递。值得注意的是，议员和信使都是兼职的，他们随时有可能会离开议会厅，并且信使可能会重复的传递信息，也可能一去不复返。因此，议会协议要保证在这个情况下法令仍然能够正确的产生，并且不会出现冲突。
在分布式系统中，存在若干个进程，假设有一组进程集合，既可以提出提案，也可以接受提案，提案包含了需要批准的决议，进程和进程之间仅通过网络传递消息，进程的处理速度有快有慢，并且随时可以退出或加入系统。那么Paxos算法为了达到一致性，在所有的提案中，最终只能有一个决议被批准。
在进行论述之前，先回顾一下Paxos算法中的词汇约定：
在分布式系统中，进程的处理有快有慢，消息的传递也存在时差，因此系统中的进程没有办法根据消息的到达的顺序去确定当前的提案进展。
事实上，满足一致性的分布式系统，每一个Acceptor或者Proposer都会有一个确定的决策依据；同时，由于消息顺序在分布式系统下不可信赖，每个Acceptor和Proposer必须在不清楚当前提案进展的前提下，做出正确的决策。
我们可以局部地去观察某个Acceptor或者Proposer，先假定系统中其他的Proposer和Acceptor都在某个时刻做出了正确的决策。
我们从最简单的场景出发，通过丰富场景，讨论可能遇到的问题，借此来不断完善提案协议以及Acceptor和Proposer的决策方案。在这一设定下，我们来讨论Acceptor和Proposer如何决策才能够一定选到一致的提案。
一致性目标：某个决议Value被批准(choose)后，该决议Value不可修改
显然我们会做出上述要求。同时，被批准(chosen)的决议一定先被Acceptor所接受(accept)，也一定会从Proposer的提案Proposal发出。
最简单的提案协议莫过于，提案中包含了需要让Acceptor接受的Value
协议方案一：每个提案的仅包含我们要批准的决议，即Proposal(Value)
首先观察Acceptor应有的决策方案。
[场景A-1] Acceptor没有收到任何提案的场景下，Acceptor收到了一个Proposer的提案
此时，Acceptor当前的决议Value为空，在此情况下，Acceptor没有理由拒绝任何一个先到来的提案。
Acceptor决策一：一个Acceptor必须接受(accept)第一次收到的提案Proposal(Value)
但是，如果这时Acceptor同时又收到另一个Proposer的提案呢?
[场景A-2] 在该Acceptor收到了一个Proposer提出提案的场景下，Acceptor同时收到另一个Proposer的提案
根据Acceptor决策一，Acceptor一定会接受(accept)先到的提案，那么Acceptor是否应该接受(accept)后到的提案呢？
不妨扩充提案协议：
协议方案二：一个提案Proposal具有ID和Value两个属性，即Proposal(ID, Value)，具有相同ID的Proposal一定是同一个Proposal，并且假定ID越小说明消息越陈旧
同时，我们可以为Acceptor制定下一条决策方案：
Acceptor决策二：一个Acceptor在已经接受提案的场景下，当有新的提案到达时，可以拒绝ID更小的提案
由于扩充了Proposal的数据结构，当Acceptor有可能在收到某一提案Proposal(ID, Value)的前后，都有可能收到另一次提案，且提案的ID有可能大也有可能小。因此场景A-2被分成了2种场景。
[场景A-2-1] Acceptor在收到Proposal_m(ID_m, Value_m)之前，收到Proposal_n(ID_n, Value_n)
[场景A-2-2] Acceptor在收到Proposal_m(ID_m, Value_m)之后，收到Proposal_n(ID_n, Value_n) (其中 ID_n > ID_m)
无论如何“在接受更小ID的Proposalm“的状态下，要想剔除矛盾，Acceptor必须要能够提前将更小ID的Proposal_m拒绝掉。也就是说，Acceptor在收到Proposal_m的时候，已经知道了自己即将收到Proposal_n。
为了达到这一目的，我们需要再次扩充提案协议：
协议方案三：引入只包含ID的预提案，即PreProposal(ID)，在Proposer发送提案之前，首先向Acceptor发送一个预提案，告知Acceptor自己即将发送的提案的ID。
同时，既然知道将会有更大ID的提案到达，Acceptor将不会接受任何更小ID的提案。
Acceptor决策三：Acceptor收到某个Proposer的PreProposal(ID)时，向这个Proposer承诺(promise)正式提案Proposal(ID, Value)，不会接受更小ID的提案。
下面我们需要分析，当引入预提案后，能否真的解决场景A-2-2的问题。事实上，我们的情况更加复杂了：由于引入了预提案-提案两阶段，在Acceptor收到Proposer一次提案流程中，会产生了前后三个空隙，，同时Acceptor收到的另一次提案的ID也可大可小，因此，我们的场景A-2，被分成了6种情况。
[场景A-2’-1] Acceptor接收到消息的顺序(速记：小小大大)：PreProposal_m(ID_m) -> Proposal_m(ID_m, Value_m) -> PreProposal_n(ID_n) -> Proposal_n(ID_n, Value_n)
[场景A-2’-2] Acceptor接收到消息的顺序(速记：小大小大)：PreProposal_m(ID_m) -> PreProposal_n(ID_n) -> Proposal_m(ID_m, Value_m) -> Proposal_n(ID_n, Value_n) [场景A-2’-3] Acceptor接收到消息的顺序(速记：小大大小)：PreProposal_m(ID_m) -> PreProposal_n(ID_n) -> Proposal_n(ID_n, Value_n) -> Proposal_m(ID_m, Value_m) [场景A-2’-4] Acceptor接收到消息的顺序(速记：大小小大)：PreProposal_n(ID_n) -> PreProposal_m(ID_m) -> Proposal_m(ID_m, Value_m) -> Proposal_n(ID_n, Value_n) [场景A-2’-5] Acceptor接收到消息的顺序(速记：大小大小)：PreProposal_n(ID_n) -> PreProposal_m(ID_m) -> Proposal_n(ID_n, Value_n) -> Proposal_m(ID_m, Value_m) [场景A-2’-6] Acceptor接收到消息的顺序(速记：大大小小)：PreProposal_n(ID_n) -> Proposal_n(ID_n, Value_n) -> PreProposal_m(ID_m) -> Proposal_m(ID_m, Value_m) (其中 ID_n > ID_m)
我们可以化简场景：我们希望在当前的决策方案下，Acceptor能接受accept具有更大ID的Proposal_n。
我们同时也注意到再次丰富场景是无用的，因为我们总会遇到先经历更小ID提案流程、再经历更大ID提案流程的场景。为了解决这个问题，我们只能要求两次提案Proposal_m(ID_m, Value_m)和Proposal_n(ID_n, Value_n)中，Value_n := Value_m。此时，即使遇到更大ID提案，Acceptor也可以接受并且不产生矛盾。
好在我们还有一次预提案PreProposal。当发生预提案发生的时候说明真正的提案还没有下达，Acceptor在收到预提案PreProposal_n时，向该预提案的提议者Proposer_n反馈自己已经接受的Proposal_m(ID_m, Value_m)，要求Proposer_n在下次发生Proposal_n时修正提案的Value，也就是发送Proposal_n(ID_n, Value_m)，如果可以达成这一条，那么Acceptor遇到所有场景的问题，都可以顺利解决。
Acceptor决策四：一个Acceptor在收到某个Proposer的预提案PreProposal时，如果自己曾经接受了某提案Proposal(ID, Value)，就将上次接受的提案反馈给这个预提案的Proposer，并期望Proposer修正Value为当前的值
理想情况下，所有问题肯定可以顺利解决，但是显然Acceptor没有权力修改Proposer的内存，它对Proposer的期望也正是假定了Proposer会执行正确的决策。那么Proposer下次一定会按照Acceptor所期望的那样，发送修正后的Value吗？
下面我们观察Proposer应有的决策方案。
一个Proposer不会凭空产生某个提案，产生提案前Proposer必然收到了Client的请求。此时Proposer内存已经生成了提案的Value，但是该提案并未被批准(chosen)。为了可以批准该提案，Proposer应首先生成一个ID，并广播预提案PreProposal(ID)，然后等待Acceptors的回复。Acceptors既有可能回复自己的承诺(promise)，也有可能回复自己已接受的提案，也有可能忽略Proposer的预提案。
这里我们先引入**“过半机制”(Quorum)**，然后在分析在"过半"的下，提案是否会达成一致。
此时，Proposer在发送预提案PreProposal(ID)后，Proposer收到Acceptors的承诺既有可能超过一半也有可能未过半。这里我们引入第一个决策方案：
Proposer决策一：在PreProposal发送后，当Proposer收到网络中过半Acceptors的承诺(promise)，那么Proposer发送自己的提案Proposal(ID, Value)，并期望得到过半Acceptors的接受
此时Proposer会先遇到两个场景：
[场景P-1] Proposer收到Acceptors的承诺未过半
[场景P-2] Proposer收到了过半Acceptors的承诺
首先考虑场景P-1：网络中有多于一半的Acceptors不接受Proposer的预提案PreProposal(ID)，说明当前网络中还存在其他的提案，且必定会有一个提案Proposal_j(ID_j, Value_j)，它的ID’是所有提案中最大的，也必定会赢得过半的Acceptors的承诺，而最终也必然有过半的Acceptors接受该提案Proposal_j。此时网络中的Acceptors可能会有三种状态：
考虑场景P-2：Proposer收到了过半Acceptors的承诺，承诺中可能包含了Acceptor曾经接受的提案，因此我们分成两个场景考虑
[场景P-2-1] 这过半的Acceptors中没有回复任何接受过的提案
[场景P-2-2] 这过半的Acceptors中有Acceptor回复了接受过的某个提案，组成了一个提案集合Proposals
考虑场景P-2-1：由于没有其他可参考的提案，那么此时理所应当将自己的值Value_i，以及预提案携带的ID_i，生成提案Proposal_i(ID_i, Value_i)发送出去
考虑场景P-2-2，Proposer收到了一个提案集合Proposals[Proposal_x0, Proposal_x1, …, Proposal_xn]，显然每个提案都得到了过半Acceptors的接受，那么Proposer意识到自己的原来的Value值肯定会落选，那么就必须从集合Proposals中选取某个Value值；同时在集合Proposals中，对于任意两个提案Proposal_xi和Proposal_xj，也必然存在交集的Acceptor同时接受两个提案，可以得到集合Value_xi == Value_xj；Proposer只需要选取集合Proposals中，ID最大的提案Proposal_xn的值Value_xn即可
Proposer决策二：如果预提案之后，Acceptors反馈了一批接受过的提案，那么Proposer选取ID最大的提案中的Value值，做为自己的Value值，并发起正式提案
虽然我们在假设所有的Acceptor和Proposer都能做出相同且正确的决策下，最终可以得到一致的Value，但毕竟不是严密的证明过程。下面，我们遵从《Paxos Made Simple》的描述，尝试去理解数学证明。
P1. Acceptor必须批准它收到的第一个决议。
我们必须保证只有一个提案被提出的情况下，仍然可以批准这项决议。这与之前讨论的Acceptor决策一相同。
P2. 如果一个提案Proposal(ID, Value)被批准，那么所有被批准的提案（编号更高）包含的决议都是Value。
如果存在多个提案被批准，为了保证一致性，随后提出的提案必须与之前的提案有相同的决议。这与之前分析的Acceptor决策三和决策四相当。
P2A. 如果一个提案Proposal(ID, Value)被批准，那么任何Acceptor批准的提案（编号更高）包含的决议都是Value。
这里对P2进行了变换，将决议的一致性转移到Acceptor上。根据Acceptor决策四，显然Acceptor在接受某项提案后，再次收到的提案中的决议Value保持不变。
P2B. 如果一个提案Proposal(ID, Value)被批准，那么此后，任何Proposer提出的提案（编号更高）包含的决议都是Value。
这里对P2A进行了变换，将决议的一致性再次转移到Proposer上。显然Acceptor后来收到的提案必定是从Proposer发出，当然我们对Proposer的要求，希望提出的提案中的决议Value与Acceptor期望相同。
以上只是我们期望的约束条件，我们需要证明，在我们引入的策略下，决议Value会一直保持一致。也就是：
Question. 如果在提案Proposal_0(ID_0, Value_0)与Proposal_n-1(ID_n-1, Value_n-1)之间的提案，其决议Value = Value_0，下一个提出的提案Proposal_n(ID_n, Value_n)中，Value_n == Value_0
接着，我们引入我们的"过半机制"(Quorum)
Quorum. 当一个具有Value的决议被过半的Acceptors接受后，该决议被批准
由此可以得到，每一个被批准的决议，一定存在过半的Acceptors，其中存在没有批准过其他提案的Acceptor，也存在批准过其他提案的Acceptor，这些曾经被批准的提案编号最大的决议必须要与当前被批准的决议相同。于是我们得到另一个约束条件。
P2C. 对于任意的ID和Value，如果提案Proposal_n(ID_n, Value_n)被提出，那么存在一个由Acceptor的多数派组成的集合S，这个S满足以下两个条件之一
- S中没有Acceptor批准过编号小于ID_n的提案
- 在S的任何Acceptor批准的所有提案中，编号最大提案的决议与当前提案决议一致，即 ID_n-1 < ID_n 时，Value_n-1 == Value_n
并且我们知道，满足 P2C，就满足了 P2B、P2A、P2，即 P2C => P2B => P2A => P2，最终通过 P1 和 P2 来满足一致性。
也就是说：
Question’. 在提案Proposal_0(ID_0, Value_0)已经被批准的情况下，之后被批准的提案Proposal_n(ID_n, Value_n)，我们要证明：在P2C的约束下，对于任意 ID_n > ID_0，存在 Value_n == Value_0
假设Proposal_0(ID_0, Value_0)已经被批准，首先需要证明下一个被批准的提案Proposal_1(ID_1, Value_1)中，Value_1 == Value_0。
根据 P2C，过半接受提案Proposal_1(ID_1, Value_1)的集合S，一定存在一个子集S’，S’内的Acceptor曾经批准过ID小于ID_1的提案，该提案只可能是Proposal_0，由于批准Proposal_1和批准Proposal_0的都是过半集合，必然存在交集，因此Proposer在确定Proposal_1取值的时候会选择Value_0，于是我们得到 Value_1 == Value_0。
假设曾经批准过的提案Proposal_1(ID_1, Value_1)到Proposal_n-1(ID_n-1, Value_n-1)中，所有的Value值都为Value_0，需要证明，当前批准的提案Proposal_n(ID_n, Value_n)中，Value_n == Value_0
根据 P2C，过半接受提案Proposal_1(ID_1, Value_1)的集合S，同样存在一个子集S’，S’内的Acceptor曾经批准过ID小于ID_n但是编号最大的提案，提案有可能在Proposal_1到Proposal_n-1之间，亦有可能只有Proposal_0。如果在在Proposal_1到Proposal_n-1之间，那么Value_n == Value_0；如果只有Proposal_0，那么同样 Value_n == Value_0。
由此根据归纳基础和归纳过程，我们证明了，在"过半机制"(Quorum)下，如果有提案提出，之后批准的提案一定一致。
参考资料
[1] Leslie Lamport. Paxos Made Simple
[2] 倪超. 从Paxos到Zookeeper: 分布式一致性原理与实践 [3] .转载地址：http://tzdqb.baihongyu.com/