分布式一致性协议之Paxos协议详解-不念博客

像 2PC 和 3PC 都需要引入一个协调者的角色，当协调者 down 掉之后，整个事务都无法提交，参与者的资源都出于锁定的状态，对于系统的影响是灾难性的，而且出现网络分区的情况，很有可能会出现数据不一致的情况。有没有不需要协调者角色，每个参与者来协调事务呢，在网络分区的情况下，又能最大程度保证一致性的解决方案呢。此时 Paxos 出现了。

Paxos 算法是 Lamport 于 1990 年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，Lamport在八年后重新发表，即便如此Paxos算法还是没有得到重视。2006 年 Google 的三篇论文石破天惊，其中的 chubby 锁服务使用Paxos 作为 chubbycell 中的一致性，后来才得到关注。

Paxos 协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下，剩余的多数节点仍然能够达成一致。即每个节点，既是参与者，也是决策者

Paxos 协议的角色（可以是同一台机器）

由于 Paxos 和下文提到的 zookeeper 使用的 ZAB 协议过于相似，详细讲解参照下文， ZAB 协议部分

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。

基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改,即拜占庭错误的情况。(网络环境一般为自建内网，消息安全相对高)

Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

Paxos 协议的角色主要有三类节点：

提议者（Proposer）：提议一个值；
接受者（Acceptor）：对每个提议进行投票；
告知者（Learner）：被告知投票的结果，不参与投票过程。

过程：

规定一个提议包含两个字段：[n, v]，其中 n 为序号（具有唯一性），v 为提议值。

下图演示了两个 Proposer 和三个 Acceptor 的系统中运行该算法的初始过程，每个 Proposer 都会向所有 Acceptor 发送提议请求。

当 Acceptor 接收到一个提议请求，包含的提议为 [n1, v1]，并且之前还未接收过提议请求，那么发送一个提议响应，设置当前接收到的提议为 [n1, v1]，并且保证以后不会再接受序号小于 n1 的提议。

如下图，Acceptor X 在收到 [n=2, v=8] 的提议请求时，由于之前没有接收过提议，因此就发送一个 [no previous] 的提议响应，并且设置当前接收到的提议为 [n=2, v=8]，并且保证以后不会再接受序号小于 2 的提议。其它的 Acceptor 类似。

如果 Acceptor 接受到一个提议请求，包含的提议为 [n2, v2]，并且之前已经接收过提议 [n1, v1]。如果 n1 > n2，那么就丢弃该提议请求；否则，发送提议响应，该提议响应包含之前已经接收过的提议 [n1, v1]，设置当前接收到的提议为 [n2, v2]，并且保证以后不会再接受序号小于 n2 的提议。

如下图，Acceptor Z 收到 Proposer A 发来的 [n=2, v=8] 的提议请求，由于之前已经接收过 [n=4, v=5] 的提议，并且 n > 2，因此就抛弃该提议请求；Acceptor X 收到 Proposer B 发来的 [n=4, v=5] 的提议请求，因为之前接收到的提议为 [n=2, v=8]，并且 2 <= 4，因此就发送 [n=2, v=8] 的提议响应，设置当前接收到的提议为 [n=4, v=5]，并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。