分布式一致性协议-Paxos

什么是Paxos

Paxos协议主要说的是Paxos算法。该算法致力于解决分布式一致性问题，基于消息传递且具有高度容错性。

Tips：

“Paxos由 莱斯利·兰伯特(Leslie Lamport)于1998年在《The Part-Time Parliament》论文中首次公
开，最初的描述使用希腊的一个小岛Paxos，描述了Paxos小岛中通过决议的流程，并以此命名这个算
法，但是这个描述理解起来比较有挑战性。后来在2001年，莱斯利·兰伯特重新发表了朴实的算法描述版
本《Paxos Made Simple》
自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。
Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore
以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group
Replication等纷纷采用Paxos算法解决分布式一致性问题。然而，Paxos的最大特点就是难，不仅难以
理解，更难以实现。
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它
的算法都是残次品。”

Paxos到底解决了什么问题

注：这里某个数据的值并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令
（command）…根据应用场景不同，某个数据的值有不同的含义。

我们都知道2PC和3PC都能在一定程度上解决分布式环境下的一致性问题。但也都没能解决协调者宕机的情况。

那么如何解决协调者宕机的情况呢？

一个最基本的想法就是引入多个协调者，并且声明其中一个为主协调者。

而这也是Paxos算法的基本思想。

Paxos的版本有: Basic Paxos , Multi Paxos, Fast-Paxos, 具体落地有Raft 和Zookeeper的ZAB协议。

主要的Paxos算法介绍

Basic Paxos

角色介绍

• Client（客户端）：客户端向分布式系统发出请求，并等待响应。例如，对分布式文件服务器中文件的写请求。
• Proposer（提案发起者）：提案者提倡客户端请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议向前发展。
• Acceptor（决策者）：Acceptor可以接受（accept）提案；并进行投票, 投票结果是否通过以多数派为准, 以如果某个提案被选定，那么该提案里的value就被选定了。
• Learner（学习者）：学习者充当该协议的复制因素(不参与投票)。

决策模型

• Prepare
  Proposer提出一个提案,编号为N, 此N大于这个Proposer之前提出所有提出的编号, 请求
  Accpetor的多数人接受这个提案
• Promise
  如果编号N大于此Accpetor之前接收的任提案编号则接收, 否则拒绝
• Accept
  如果达到多数派, Proposer会发出accept请求, 此请求包含提案编号和对应的内容
• Accepted
  如果此Accpetor在此期间没有接受到任何大于N的提案,则接收此提案内容, 否则忽略

流程图

1.无故障的情况

2.Acceptor失败的情况

在下图中，多数派中的一个Acceptor发生故障，因此多数派大小变为2。在这种情况下，Basic
Paxos协议仍然成功。

3.Proposer失败的情况

Proposer在提出提案之后但在达成协议之前失败。具体来说，传递到Acceptor的时候失败了,这个
时候需要选出新的Proposer（提案人）,那么 Basic Paxos协议仍然成功。

4.当多个提议者发生冲突的情况

最复杂的情况是多个Proposer都进行提案,导致Paxos的活锁问题。

针对活锁问题解决起来非常简单:因为上述情况出现的前提是多个提议者之间立马发起提议，所以只需要在每个Proposer再去提案的时候随机加上一个等待时间即可。

Multi-Paxos

流程图

针对basic Paxos是存在一定得问题,首先就是流程复杂,实现及其困难，其次效率低(达成一致性需要2轮
RPC调用)，针对basic Paxos流程进行拆分为选举和复制的过程。

1.第一次发起投票流程-在所有的Acceptor中确定一个Leader

2.第二次发起投票流程-直接由Leader确认