分布式架构学习(四)-一致性算法Paxos

Paxos算法

Paxos算法是Lamport提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。

Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛
Paxos作为比喻，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战
性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made
Simple》

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型
分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的
ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法
解决分布式一致性问题。

Paxos算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。

Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

Paxos相关概念

首先一个很重要的概念叫提案（Proposal）。最终要达成一致的value就在提案里。

提案 (Proposal)：Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)

在Paxos算法中，有如下角色：

Proposer : Proposer 可以 提出提案 (Proposal)。
Accecptor : Acceptor 可以 接受提案。一旦接受提案，提案里面的 value 值就被选定了。
Learner : Acceptor 告诉 Learner 哪个提案被选定了，那么 Learner 就学习这个被选择的 value。

Paxos算法

Paxos算法通过一个决议需要经过两个阶段：

阶段一：

(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。

Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。

(b) 如果一个Acceptor收到一个编号为N的Prepare请求，会返回一个Promise请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。
- 两个承诺：
  - 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。
  - 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。
- 一个应答：
  - 不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

阶段二：

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

Learnner学习被选取后的提案

通过决议后，需要将被选取后的提案广播给所有的learn节点

方案一：快速的将被选取的提案传播给其他Learnner，但是需要通信的次数最多

方案二：创建一个主Learnner，减少通信次数，但是需要考虑单点故障问题

方案三：将一个主Learnner变成一个集合，这个集合接收到了之后再转发给其他不在这个集合当中的Learnner节点

Paxos算法伪代码

v2-8d4eaf5fdeb145e8bdf5e3bb1af408c9_720w

获取一个Proposal ID n，为了保证Proposal ID唯一，可采用时间戳+Server ID生成；
Proposer向所有Acceptors广播Prepare(n)请求；
Acceptor比较n和minProposal，如果n>minProposal 令Acceptor中的minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，如果Acceptor之前没有接到任何Prepare请求，就可以任意决定本次提案的value；
到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；
Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal。
提议者接收到过半数请求后，如果发现有返回值minProposal >n，表示有更新的提议，跳转到1；否则value达成一致。

Multi-Paxos算法

上面描述的Paxos算法在极端的环境下，可能无法保证算法的**“活性”**

活性：最终一定会发生的事情，这里代表最终一定要选定value

有两个Proposer依次提出了一系列编号递增的提案，导致最终陷入死循环，一直没有value被选定,具体流程如下:

为了保证 Paxos 算法流程的可持续性，以避免陷入上述提到的“死循环”，就必须选择一个主Proposer，并规定有主Proposer才能提出议案。这样一来，只要主Proposer和过半的Acceptor能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准。当然，如果Proposer发现当前算法流程中已经有一个编号更大的提案被提出或正在接受批准，那么它会丢弃当前这个编号较小的提案，并最终能够选出一个编号足够大的提案。因此，如果系统中有足够多的组件（包括 Proposer、Acceptor和其他网络通信组件）能够正常工作，那么通过选择一个主Proposer，整套Paxos算法流程就能够保持活性。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。