Paxos 协议简单介绍
一、简介
Paxos 协议是少数在工程实践中证实的强一致性、高可用的去中心化分布式协议。Google 的很多大型分布式系统都采用了 Paxos 算法来解决分布式一致性问题，如 Chubby、Megastore 以及 Spanner 等。开源的 ZooKeeper 以及 MySQL 5.7 推出的用来取代传统的主从复制的 MySQL Group Replication 等纷纷采用 Paxos 算法解决分布式一致性问题。
Paxos 协议的流程较为复杂，但其基本思想却不难理解，类似于人类社会的投票过程。Paxos 协议中，有一组完全对等的参与节点，这组节点各自就某一事件做出决议，如果某个决议获得了超过半数节点的同意则生效。Paxos 协议中只要有超过一半的节点正常，就可以工作，能很好对抗宕机、网络分化等异常情况。
二、协议角色
Proposer：提案者。Proposer 可以有多个，Proposer 提出议案（value）。所谓 value，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前 primary 为某个节点”等等。Paxos协议中统一将这些操作抽象为 value，同一轮 Paxos过程，最多只有一个 value 被批准。
Acceptor：批准者。Acceptor 有 N 个，Proposer 提出的 value 必须获得超过半数（N/2+1）的 Acceptor 批准后才能通过。Acceptor 之间完全对等独立。
Learner：学习者。不参与决策，学习被批准的 value（即获得 N/2 + 1 的 Acceptor 批准）。所谓学习就是通过读取各个 Proposer/Acceptor 对 value 的选择结果，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value。
上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。
三、协议流程
Paxos 算法解决的核心问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。
Paxos 协议一轮一轮的进行，每轮都有一个编号。每轮 Paxos 协议可能会批准一个 value，也可能无法批准一个 value。 如果某一轮 Paxos 协议批准了某个 value，则以后各轮 Paxos 只能批准这个 value （这是整个协议正确性的基础）。
上述各轮协议流程组成了一个 Paxos 协议实例，即一次 Paxos 协议实例只能批准一个 value，这也是 Paxos 协议强一致性的重要体现。
每轮 Paxos 协议分为准备阶段和批准阶段，在这两个阶段 Proposer 和 Acceptor 有各自的处理流程：
基本例子
基本例子里有 5 个 Acceptor， 1 个 Proposer，不存在任何网络、宕机异常。我们着重考察各个Accpetor 上变量 B 和变量 V 的变化，及 Proposer 上变量 b 的变化。
1、初始状态
| Acceptor 1 | Acceptor 2 | Acceptor 3 | Acceptor 4 | Acceptor 5 | |
|---|---|---|---|---|---|
| B | 0 | 0 | 0 | 0 | 0 |
| V | NULL | NULL | NULL | NULL | NULL |
| Proposer1 | |
|---|---|
| b | 1 |
2、Proposer 向所有 Accpetor 发送“Prepare(1)”，所有 Acceptor 正确处理，并回复 Promise(1, NULL)
| Acceptor 1 | Acceptor 2 | Acceptor 3 | Acceptor 4 | Acceptor 5 | |
|---|---|---|---|---|---|
| B | 1 | 1 | 1 | 1 | 1 |
| V | NULL | NULL | NULL | NULL | NULL |
| Proposer1 | |
|---|---|
| b | 1 |
3、Proposer 收到 5 个 Promise(1, NULL)，满足多余半数的 Promise 的 value 为空，此时发送Accept(1, v1)，其中 v1 是 Proposer 选择的 value。
| Acceptor 1 | Acceptor 2 | Acceptor 3 | Acceptor 4 | Acceptor 5 | |
|---|---|---|---|---|---|
| B | 1 | 1 | 1 | 1 | 1 |
| V | v1 | v1 | v1 | v1 | v1 |
4、此时，v1 被超过半数的 Acceptor 批准，v1 即是本次 Paxos 协议实例批准的 value。这里解释下为什么被批准的 value 无法改变，因为 v1 目前已经被超半数的 Acceptor 通过，即使再发起下一轮选举，也必须有三个 Promise（b，v1）才有可能通过，即被批准的 v1 无法改变。如果 Learner学习 value，学到的只能是 v1。
四、Multi-Paxos 算法
Paxos 协议引入了轮数的概念，高轮数的 Paxos 提案可以抢占低轮数的 Paxos 提案，从而避免了死锁的发生。然而这种设计却引入了“活锁”的可能，即 Proposer 相互不断以更高的轮数提出议案，使得每轮 Paxos过程都无法最终完成，从而无法批准任何一个value。Multi-Paxos 正是为解决此问题而提出，Multi-Paxos 基于Basic Paxos 做了两点改进：
针对每一个要确定的值，运行一次 Paxos 算法实例（Instance），形成决议。每一个 Paxos 实例使用唯一的 Instance ID 标识。
在所有 Proposers 中选举一个 Leader，由 Leader 唯一的提交 Proposal 给 Acceptors 进行表决。这样没有 Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。
Multi-Paxos 首先需要选举 Leader，Leader 的确定也是一次决议的形成，所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal，在 Leader 宕机之后服务临时不可用，需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下，Prepare 阶段可以跳过。
Multi-Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例，从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段，后续只需要执行 Accept 阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个 Instance ID 标识，Instance ID 由 Leader 本地递增生成即可。
Multi-Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性，这样的场景即退化为 Basic Paxos。
Chubby 和 Boxwood 均使用 Multi-Paxos。ZooKeeper 使用的 Zab 也是 Multi-Paxos 的变形。
参考资料：
《分布式系统原理介绍》
Paxos算法详解
分布式系列文章——Paxos算法原理与推导