问题描述
Paxos算法的目的是解决分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成最终一致。当多个进程提出（Propose）不同的值，算法保证最终只有其中一个值被选定，即需要满足：
- 只有被提出（Propose）的值才可能被最终选定（Chosen）。
- 有且只有一个值会被最终选定（Chosen）。
- 进程只会获知到已经确认被选定（Chosen）的值。
三种角色
Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner)。每个进程可能充当不止一种角色。
Paxos允许这三种角色在相互的通信中存在消息丢失、延迟、乱序以及重复的故障，但假设消息不会被篡改。它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。
- Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
- Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
- Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。
两个阶段
Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：
- 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors对收到的Prepare请求进行Promise承诺。
- 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
- 第三阶段：Learn阶段。Proposer在多数的Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。
算法的推导
为了保证必须有值被接受，所以Paxos算法中：
P1：Acceptor必须接受（Accept）它所收到的第一个Proposal。
因为我们需要只有一个提案被提出的情况下，仍然能选出一个决议。但这样产生一个问题，如果多个Proposers同时提出Proposal，可能会导致没有任何一个提案被多数Acceptor批准。在P1的基础上，加上一个提案需要半数以上的Acceptor批准才能选定，因此需要Acceptor能够批准多个提案。
这里我们使用一个全局的编号来唯一标识每一个被Acceptor批准的提案（假设当前已经具备这样的外部组件能够生成全局唯一的，编号本文不详细讨论）。此时，提案变成了一个由编号和值组成的组合体。为了保证只有一个值会被最终选定，Paxos进一步提出：
P2：如果值为v的Proposal被选定（Chosen），则任何被选定（Chosen）的具有更高编号的Proposal值也一定为v。
P1和P2，就保证了有且只有一个值会被最终选定。但P2难以实现为具体的算法。我们提出p2的充分条件P2a：
P2a：如果值为v的Proposal被选定（Chosen），则任何被Acceptor批准的的具有更高编号的Proposal值也一定为v。
因为只有首先被批准才有可能被最终选定。但是P2a依然难以实现，因为acceptor很有可能并不知道之前已经被选定的提案的信息（该acceptor恰好不在接受它的多数派中），因此进一步提出P2a的充分条件P2b：
P2b：如果值为v的Proposal被选定（Chosen），则对所有的Proposer，它们提出的的任何具有更高编号的Proposal值也一定为v。
因为只有提案被提出才可能被批准。更进一步，提出充分条件P2c：
P2c：如果编号为n，值为v的提案被提出，必须存在一个由半数以上的Acceptor组成的集合S，满足以下条件中的任意一个：
- S中没有任何Acceptor曾经批准过编号比n小的提案
- S中的Acceptors所接受过的编号最大且小于n的提案的值也是v
我们再对P1进行延伸，提出p1的充分条件P1a：
P1a：一个Acceptor只要尚未响应过任何编号大于n的请求，它就可以接受这个编号为n的提案
自此可以引出如下的提案生成算法：
Proposer生成提案
1. Proposer选择一个新的编号n，向超过一半的Acceptors发送请求消息。Acceptor回复信息:
- 承诺不会批准编号比n小的proposal
- 如果它已经批准过编号比n小的提案，它会返回已经批准的编号最大且小于n的提案的值。
该请求称为Prepare请求。
2. 如果Proposer收到超过一半Acceptors的回复，它就可以提出编号n，值为v的提案。其中v是收到的回复中编号最大的提案的值，如果没有这样的值 (半数以上的Acceptor都没有批准过任何提案)，则可以自由提出任何值。然后，向超过一半的Acceptors发出请求（和前一阶段的Acceptors集合不要求相同，两个集合因为都超过一半，必定存在至少一个公共的Acceptor），请求对方接受提出的提案
该请求称为Accept请求。
Acceptor批准提案
1. 当收到Prepare请求时，如果其编号n大于之前所收到的Prepare消息，则回复。
因为，若一个Acceptor收到一个编号为n的请求，但该Acceptor已经对编号大于n的Prepare请求做出了响应，它肯定不会批准编号为n的提案，因此Acceptor没有必要对这个Prepare请求做出响应
2. 当收到Accept请求时，仅当它没有回复过一个具有更大编号的提案，批准该提案并回复。
算法陈述
阶段一：
- Proposer选择一个提案编号n，向Acceptor的某个超过半数的子集成员发送编号为n的Prepare请求
- 如果一个Acceptor收到一个编号为n的Prepare请求，且编号n大于该Acceptor已经响应的所有Prepare请求的编号，那么它会将它已经批准过的最大编号的提案（如果有）的值作为响应反馈给Proposer，同时Acceptor会承诺不会再批准任何编号小于n的提案
阶段二：
- 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为n的Prepare请求的响应，那么它就会发送一个针对提案（编号n，值v）的Accept请求给Acceptor。注：其中v是收到的回复中编号最大的提案的值，如果没有这样的值 (半数以上的Acceptor都没有批准过任何提案)，则可以自由提出任何值。
- 如果Acceptor收到这个编号n，值v的Accept请求，只要该Acceptor尚未对编号大于n的Prepare请求做出响应，它就会通过这个提案。
提案的获取
如果一个提案已经被半数以上的Acceptor批准，代表这个提案已经被选定。Leaner获取提案获取这个被选定的提案有如下几种方式：
- 一旦Acceptor批准了一个提案，就将提案发送过所有的Learner。缺点是每个Acceptor需要与所有的Leaner进行通信，通信次数为二者的乘积。
- 所有Acceptor将它们对提案的批准情况发送给一个主Learner。当主Learner被通知一个提案已经被选定时，它会负责通知其他的Learner。缺点是主Learner带来单点故障问题。
- 将方法2的主Learner扩大为一个特定的Learner集合。
一些例子
paxos1.jpg
- 图中P代表Prepare阶段，A代表Accept阶段。3.1代表从server s1发出的编号为3的proposal。X和Y代表proposal值。
- 例1中P 4.5的Prepare阶段前，P 3.1已达成多数派，其值X被Accept，然后P 4.5学习到值X。X被最终选定
paxos2.jpg
- 例2中在P 4.5的Prepare阶段前，P 3.1与s3的accept阶段率先完成，与s1和s2 accept阶段有一定延迟。但P 4.5将学习到X，并将自己的值由Y替换为X。X被最终选定。
paxos3.jpg
- 例3中在P 4.5的Prepare阶段前，P 3.1与s2和s3的accept阶段尚未完成。当P 4.5提出Prepare请求，s3由于未批准任何提案，将不会返回任何提案值，并承诺不会再批准任何编号小于4的提案。接着，s3收到P 3.1 Accept请求，这个提案不会得到批准。P 4.5的提案在得到s3, s4和s5批准后，Y被最终选定。
paxos4.jpg
- 例4中两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。
- 一个解决活锁的方法是Multi-Paxos算法。
网友评论