分布式-Multi Paxos

简介

由于任何一个节点都具有提案的权利，导致活锁的出现。需要寻找一种两全其美的方法：既不破坏 Paxos 中“众节点平等”的原则，又能在提案节点中实现主次之分，限制每个节点都有不受控的提案权利。

Multi Paxos

Multi Paxos 对 Basic Paxos 的核心改进是，增加了“选主”的过程：

• 提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里是否存在一个主提案节点；

• 一旦没有发现主节点存在，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对“由我作为主节点”这件事情协商达成一致共识；

• 如果得到了决策节点中多数派的批准，便宣告竞选成功。

当选主完成之后，除非主节点失联会发起重新竞选，否则就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。

Raft 算法

针对“分布式系统中如何对某个值达成一致”这个问题，分为三个子问题来考虑：

• 如何选主（Leader Election）

• 如何把数据复制到各个节点上（Entity Replication）

• 如何保证过程是安全的（Safety）

如何选主

使用paxos算法选主。

数据复制过程

在正常情况下，当客户端向主节点发起一个操作请求后，比如提出“将某个值设置为 X”，数据复制的过程为：

1. 主节点将 X 写入自己的变更日志，但先不提交，接着把变更 X 的信息在下一次心跳包中广播给所有的从节点，并要求从节点回复“确认收到”的消息；

2. 从节点收到信息后，将操作写入自己的变更日志，然后给主节点发送“确认签收”的消息；

3. 主节点收到过半数的签收消息后，提交自己的变更、应答客户端并且给从节点广播“可以提交”的消息；

4. 从节点收到提交消息后提交自己的变更，数据在节点间的复制宣告完成。

异常情况下，网络出现了分区，部分节点失联，但只要仍能正常工作的节点数量能够满足多数派（过半数）的要求，分布式系统就仍然可以正常工作。

假设有 S1、S2、S3、S4 和 S5 共 5 个节点，我们来看下数据复制过程：

• 假设由于网络故障，形成了 S1、S2 和 S3、S4、S5 两个分区。

• 一段时间后，S3、S4、S5 三个节点中的某一个节点比如 S3，最先达到心跳超时的阈值，获知当前分区中已经不存在主节点了；

• 于是，S3 向所有节点发出自己要竞选的广播，并收到了 S4、S5 节点的批准响应，加上自己一共三票，竞选成功。

• 此时，系统中同时存在 S1 和 S3 两个主节点，但由于网络分区，它们都不知道对方的存在。

假设现在故障恢复，分区解除，五个节点可以重新通讯了：

1. S1 和 S3 都向所有节点发送心跳包，从它们的心跳中可以得知 S3 的任期编号更大、是最新的，所以五个节点均只承认 S3 是唯一的主节点。

2. S1、S2 回滚它们所有未被提交的变更。

3. S1、S2 从主节点发送的心跳包中获得它们失联期间发生的所有变更，将变更提交写入本地磁盘。

4. 此时分布式系统各节点的状态达成最终一致。

Raft 算法是etcd、LogCabin、Consul 等重要分布式程序的实现基础。ZooKeeper 的 ZAB 算法和 Raft 的思路也非常类似，这些算法都被认为是与 Multi Paxos 的等价派生实现。