分布式共识：Paxos 算法 | 小谷的编程随笔空间

世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本。—— Mike Burrows，Google Chubby 作者

Paxos 是由 Leslie Lamport（就是大名鼎鼎的 LaTeX 中的「La」）提出的一种基于消息传递的协商共识算法，是当今分布式系统最重要的理论基础，几乎就是「共识」二字的代名词。这个极高的评价出自于提出 Raft 算法的论文（《一种可以让人理解的共识算法（In Search of an Understandable Consensus Algorithm）》）。

「一致性」和「共识」

一致性：指数据不同副本之间的差异
共识：达成一致性的方法与过程

由于翻译的关系，很多中文资料把 Consensus 同样翻译为一致性，导致网络上大量的「二手中文资料」将这两个概念混淆起来，如果你在网上看到「分布式一致性算法」，应明白其指的其实是「Distributed Consensus Algorithm」。

Paxos 的诞生

Paxos 算法的目标就是让城邦能够在每一位居民都 不承诺 一定会及时参与的情况下，依然可以按 少数服从多数 的原则，最终达成一致意见。

Lamport 在 1990 年首次发表了 Paxos 算法，选的论文题目就是「The Part-Time Parliament」。由于算法本身极为复杂，用希腊城邦作为比喻反而使得描述更晦涩，论文的三个审稿人一致要求他把希腊城邦的故事删掉。这令 Lamport 感觉颇为不爽，干脆就撤稿不发了，所以 Paxos 刚刚被提出的时候并没有引起什么反响。

1998 年，Lamport 将文章重新整理后投到 ACM Transactions on Computer Systems。这次论文成功发表，Lamport 的名气也确实吸引了一些人去研究，但并没有多少人能弄懂他在说什么。

2001 年，Lamport 认为前两次的论文没有引起反响，是因为同行们无法理解他以「希腊城邦」来讲故事的幽默感，所以这一次他以「Paxos Made Simple」为题，在 SIGACT News 杂志上发表文章，放弃了「希腊城邦」的比喻，尽可能用（他认为）简单直接、（他认为）可读性较强的方式去介绍 Paxos 算法。

The Paxos algorithm, when presented in plain English, is very simple. —— Paxos Made Simple

Lamport 连发三篇文章都没能让大多数同行理解 Paxos，直到 2006 年，在 Google 的 Chubby、Megastore 以及 Spanner 等分布式系统都使用 Paxos 解决了分布式共识的问题。 加上 Mike Burrows 那稍带夸张的评论，Paxos 算法一夜间成为计算机科学分布式这条分支中最炙手可热的概念，开始被学术界众人争相研究。Lamport 本人因其对分布式系统的杰出理论贡献获得了 2013 年的图灵奖，随后才有了 Paxos 在区块链、分布式系统、云计算等多个领域大放异彩的故事。

算法流程

三类节点

Paxos 算法将分布式系统中的节点分为三类：

提案节点（Proposer）：提出对某个值进行设置操作的节点，设置值这个行为就被称为提案（Proposal），值一旦设置成功，就是不会丢失也不可变的。
- 不要把「设置值」类比成程序中变量赋值操作，而 应该类比成日志记录操作
- Raft 算法中就直接把「提案」叫作「日志」
决策节点（Acceptor）：应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，即称该提案 被批准 （Accept）。
- 提案被批准即意味着该值不能被更改，也不会丢失，且最终所有节点都会接受它
记录节点（Learner）：不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。
- 譬如少数派节点从网络分区中恢复时，将会进入这种状态

在使用 Paxos 算法的分布式系统里， 所有的节点都是平等的 ，它们都可以承担以上某一种或者多种的角色。不过为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个。

Paxos 算法本身并 不考虑拜占庭将军问题，即发出、收到的信息可能延迟送达、可能丢失，但不去考虑消息有传递错误的情况。

分布式并发

分布式的环境下，由于要同时考虑到分布式系统内可能在任何时刻出现的通信故障，如果一个节点在取得锁之后、在释放锁之前发生崩溃失联，这将导致整个操作被无限期的等待所阻塞。

因此算法中的加锁就不完全等同于并发控制中以互斥量来实现的加锁，还必须提供一个其他节点能抢占锁的机制 ，以避免因通信问题而出现死锁。

分布式环境中的锁必须是可抢占的

第一个阶段：准备阶段

「准备」（Prepare）就相当于抢占锁的过程。如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为 Prepare 请求）。

提案节点的 Prepare 请求中会附带一个 全局唯一且单调递增 的数字 n 作为提案 ID。
决策节点收到后，会给予提案节点两个承诺与一个应答
- [承诺] 不会再接受提案 ID <= n 的 Prepare 请求
- [承诺] 不会再接受提案 ID < n 的 Accept 请求
- [应答] 不违背历史承诺的前提下，回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID。
  - 如果这个值没有被任何提案设定过，则返回空值
  - 如果违反历史承诺，即收到的提案 ID 并不是决策节点收到的最大的 ID，允许直接对 Prepare 请求不予理会。

Paxos 算法整体的时序图

第二个阶段：批准过程

提案节点收到多数决策节点的应答（称为 Promise 应答）后，就可以开始第二阶段的「批准」（Accept）过程，由两种可能的结果：

提案节点发现所有响应的决策节点之前都没有设定过该值（即为空）
- 可以随意设置要设定的值（说明是第一个设置值的节点）
- 提案节点将设定的值和提案 ID 组成二元组 (id, value)，再次广播给所有决策节点（Accept 请求）
如果提案节点发现响应中的节点存在值，那就必须无条件地从应答中找出提案最大 ID 最大的那个值并接收，组成一个二元组（id, maxAcceptValue)，再次广播给全部决策节点。（Accept 请求）

当每一个决策节点收到 Accept 请求的时候，都会在不违背以前的承诺的前提下，接收并持久化当前提案 ID 和提案附带的值。如果违反此前做出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的 ID，则允许对此 Accept 请求不予理会。

提案节点收到了大多数决策节点的应答（Accepted 应答）后，协商结束，共识协议形成，然后将形成的决议发送给所有记录节点进行学习。

Paxos 实例

(TODO)

Multi Paxos

分布式共识 的复杂性主要来源网络的不可靠与请求的可并发两大因素。

活锁问题与许多 Basic Paxos 异常场景中所遭遇的麻烦，都可以看作源于任何一个提案节点都能够完全平等地、与其他节点并发地提出提案而带来的复杂问题。为此，Lamport 提出了一种 Paxos 的改进版本—— Multi Paxos 算法，希望能够找到一种两全其美的办法，既不破坏 Paxos 中「众节点平等」的原则，又能在提案节点中实现主次之分，限制每个节点都有不受控的提案权利。

Multi Paxos 对 Basic Paxos 的核心改进是增加了「选主」的过程，提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里 是否存在一个主提案节点。

如果没有主提案节点，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对「由我作为主节点」这件事情协商达成一致共识，如果得到了决策节点中多数派的批准，便宣告竞选成功。

选主完成之后，除非主节点失联之后发起重新竞选，否则从此往后，就 只有主节点本身才能够提出提案。

主节点提案时，就无须再次经过准备过程。

(TODO)

Gossip 协议

Gossip 最早由施乐公司 Palo Alto 研究中心在论文「Epidemic Algorithms for ReplicatedDatabase Maintenance」中提出的一种用于分布式数据库在多节点间复制同步数据的算法。

最初它是被称作「流行病算法」（Epidemic Algorithm）的，只是不太雅观，今天 Gossip 这个名字用得更为普遍，除此以外，它还有「流言算法」、「八卦算法」、「瘟疫算法」等别名，这些名字都很形象地反映了 Gossip 的特点：

要同步的信息如同流言一般传播，病毒一般扩散。

比特币网络中使用了 Gossip 协议，用于在各个分布式节点中互相同步区块头和区块体的信息。

相比 Paxos、Raf t等算法，Gossip 的过程十分简单，它可以看作以下两个步骤的简单循环：

如果有某一项信息需要在整个网络的所有节点中传播，那从信息源开始，选择一个固定的传播周期（譬如 1 秒），随机选择它相连接的 k 个节点（称为 Fan-Out）来传播消息。
每一个节点收到消息后，如果这个消息是它之前没有收到过的，则在下一个周期内，该节点将向除了发送消息给它的那个节点外的其他相邻的 k 个节点发送相同的消息，直到最终网络中所有节点都收到了消息。

尽管这个过程需要一定时间，但是理论上最终网络的所有节点都会拥有相同的消息。（广度优先搜索的变种）

Gossip 对网络节点的连通性和稳定性几乎 没有任何要求 ，它一开始就将网络某些节点只能与一部分节点部分连通（Partially Connected Network）而不是以全连通网络（Fully Connected Network）作为前提。

Gossip 具有极强的鲁棒性，而且非常适合在公众互联网中应用。

Gossip 的缺点: