The Paxos Paper

原论文：Paxos Made Live - An Engineering Perspective

领域内描述 Paxos 算法的资料其实有不少，这里选择的论文是从工程角度阐述依靠 Paxos 搭建 Chubby 的经验，而不是像 Raft 论文那样的理论文章。这篇文章讨论的内容包括 Paxos 原理、对 Paxos 做的改进以及工程方面对可测试性、可维护性等做出的额外付出，这篇 blog 聚焦在 Paxos 的部分。

我们首先回顾一下一致性共识算法要解决的问题：

硬件设备，尤其是廉价硬件设备的可靠性难以保证。一个构建在这些设备上的分布式系统希望具备容忍各类故障的能力，如网络波动、硬盘故障、系统崩溃等。要实现这一点，思路之一是将分布式系统的状态复制到各个节点中，这样就算出现了部分成员异常，整个系统也能维持正常运转，发生异常的成员后续也能重新接入。

一致性共识算法处理的就是状态复制问题。简单来说，它们将一系列的操作指令分配到每台主机上形成日志，如果出现主机崩溃，其他主机也保留了集群状态。崩溃的主机重新加入集群时，也可以通过接收日志，并重放操作的方式来保持自身状态和集群状态一致。

这里不再介绍 Chubby（详见之前的 blog），简言之，它是一个分布式锁服务。每个 Chubby cell 包含 5 个副本，而 Chubby 存储的对象（锁、小文件等）都存在底层的数据库里，这个数据库由 Paxos 复制。

如图，Chubby 的底层数据库包含快照和日志两部分。当有数据库操作被提交到该数据库时，该操作会作用于数据库，并记录到日志。而 Paxos 算法保证所有副本的日志相同。Chubby 客户端会同某个单独的 Chubby 结点通信，并在数据库中更新 Chubby 集群状态。

论文将 Paxos、数据库和 Chubby 做了分层处理，这是一种工程设计方面的考量，毕竟这种可复制的日志功能完全可以复用到别的系统中。

上图描述了日志层的 API，其操作包括 submit 和 callback。前者向日志提交一条操作记录，提交成功后，通过 Paxos 传播该日志，并触发 callback。

Paxos 基础 ​

一轮 Paxos 的过程可以分为如下三个阶段：

1. 一个成员被选举为 coordinator （注意，Paxos 的 coordinator 和 master 是两个概念）；
2. coordinator 选择一个值（或者说，操作记录），通过 accept 消息广播到集群，其他成员可以接受或者拒绝该消息；
3. 一旦大多数成员接受该消息，集群就达成了一致， coordinator 再广播一条 commit 消息告知其他成员这一点。（原理上就像是两阶段提交）

在现实场景中 Paxos 可以被并发执行，这也就是说，集群中同时可能有多个成员变成 coordinator ，这些 coordinator 可能选择不同的值进行广播。

为了确保集群能对一个值达成一致，Paxos 引入了如下限制机制：

1. 给后继 coordinator 分配顺序；
2. 限制每个 coordinator 对广播值的选择范围。

给 coordinator 标定顺序，意味着集群成员能够分辨 coordinator 的 “新旧”，于是便可以拒绝旧的 coordinator 的 accept 消息。为了实现这一点，每个 coordinator 会被分配一个递增的序列号，而每个集群成员都会记录它所见过的最大的序列号。当它想变成 coordinator ，它就将序列号加一，向集群发送 propose 消息。集群成员会从 propose 消息中拿出序列号，并和自己本地记录的序列号做对比。如果大多数成员都认可（ propose 消息中的序列号更大，此时它回复 promise 消息，表明它将拒绝更小序列号 coordinator 的 accept 消息），则消息的发送者成为 coordinator 。

一旦集群就某个值达成了一致，后续的 coordinator 就必须选择同样的值广播，以免破坏一致。为此， promise 消息中带有集群成员最近接受的值以及广播这个值的 coordinator 序列号。新的 coordinator 必须选择最新的值进行广播，当然，如果所有的 promise 消息中都没有这类内容，它就可以自由的选择一个前面 submit 给日志的值。 综合来看，新的 coordinator 必然会拿到已经达成一致的值的信息（因为该信息被集群大多数认可，它一定存在于至少一个回复 promise 消息的成员中）。

为就一系列值达成一致，最简单的做法是重复地执行 Paxos 算法。在论文中，每一次单独执行被视为 Paxos 的一个实例（ instance ）。每当给日志 submit 一个值，就是启动了一个 Paxos 实例。

在这种 Multi-Paxos 的场景下，一些成员可能因为各种原因运行缓慢，没有参与到最近的 Paxos 实例中，状态落后其他成员太多。此时，这些成员可以利用日志来快速跟进状态（ catch-up ）。每当一个成员要发送消息时，它必须先将自身状态记入日志持久化，意味着一次 Paxos 实例中必然包含多次磁盘写操作。显然，这里有值得优化的地方：如果消息发送越少，那么磁盘写的次数就越少，算法运行也就越快。如果多个 Paxos 实例中没有发生 coordinator 变化（多次 Paxos 执行都由同一个 coordinator 发起），我们就可以省略前述 Paxos 过程第一步的选举过程，即省略一次 propose 消息的发送和响应。论文把这种优化后的 coordinator 称为 master 。更进一步，在一次 Paxos 实例中， master 可以打包广播多个值。

算法优化 ​

磁盘崩溃 ​

当一个成员的磁盘崩溃后，它就失去了它的持久化状态，进而破坏 Paxos 通信。从表现上看，磁盘崩溃分两种：1）文件内容发生变化；2）文件不再可用。对于前者，论文在每个文件中保存了校验和，方便识别。对于后者，有必要区分磁盘本身为空和磁盘崩溃后信息丢失两种场景。论文依靠第三方 GFS 进行鉴别：每个成员启动后都会在 GFS 中做标记。一旦成员重启后磁盘为空，但在 GFS 中发现标记，那就说明这块磁盘之前崩溃过。

一个磁盘发生崩溃的成员将不会进行投票，其首要任务是恢复自身状态。它将利用 catch-up 机制快速跟进，但不会发送任何 promise 或 ack 消息，直至它观察到了自它重启后执行的一次完整的 Paxos 实例。

master 心跳 ​

论文令 master 周期性向集群提交心跳值，以通知其他成员自己正常运行，这样它们就不会试图变成 coordinator 提交值。反之，一旦 master 失联，集群就会选出带有更大序列号的新 master 。之前的 master 仍然会提交值，如果它仍然能和某些成员发生联系，就会得到当前更大的序列号。当它和全部集群成员恢复联系，它就可能用更大的序列号来发起 propose ，导致整个集群的序列号暴涨。

论文设置 master 心跳机制的原因是为了确保 master 正常运行时，其他成员不能向集群提交值，如此一来， master 存储的集群状态必然是最新的。对于这类一致性算法，读操作同样也要被记入日志，这样做能够确保读到的就是最近的状态，否则 client 可能会同落后的 master （这里说 coordinator 更稳妥）进行交互，拿到不那么新的状态。

epoch 变量 ​

master 在接收到请求到集群达成一致的过程中，有可能失去其 master 地位，此时，这条请求就应该被丢弃。为了检查这种情况，论文引入 epoch 概念进行优化。 epoch 是集群的一个全局状态变量，被存放在底层数据库中。如果 master 在前述时间段内不发生变化， epoch 就不会改变，由此可以判断是否需要丢弃某条请求。

快照机制 ​

同 Raft 一样，快照是为了控制空间占用和成员恢复时的日志重放时间。本论文中的 Paxos 框架允许上层应用在任意时间点进行快照操作，此时 Paxos 会截断当前时间点前的日志，将集群状态保存为快照。一旦有成员崩溃，它在恢复过程中会安装最近的快照，并重放在那之后的日志。快照并不会被同步，每个成员自己决定快照时机。

对 Paxos 来说，快照机制的引入带来了显而易见的复杂性：

• 快照必须和日志保持逻辑上的相互一致性。每个快照都需要记录它相对于日志的内容信息，论文使用快照句柄（ snapshot handle ）实现。句柄里包括与 Paxos 相关的数据，在创建快照时，句柄会被交给上层应用保存，应用需要将其提交给 Paxos，以协调快照和日志。
• 取快照是耗时操作。论文中将取快照分为三个阶段：1）应用请求一个快照句柄；2）取快照；3）操作完成后，应用将快照句柄提交给 Paxos，后者据此裁剪日志。
• 取快照操作可能失败。论文的框架里，只有在获取快照句柄后，Paxos 才会裁剪日志。在合理的逻辑里，应用会识别第二步中快照的完整性，如果失败，就不会提交句柄。
• catch-up 时，Paxos 成员可能需要重放已经被裁剪的日志，此时它将从其他成员获取快照安装，并根据句柄信息获取还需要的日志。注意，在这个过程中，领先的成员可能还在创建更新的快照，此时 catch-up 阶段的成员就只能再重复这一过程，请求更新的快照。又及，领先成员在发送完快照后可能会崩溃，此时本成员就得向另一个领先成员建立通信。
• 快照的查询机制。快照既可以被设计成通过领先成员传递，也可以设计成通过第三方服务，比如 GFS，来传递。论文对这里的设计持开放态度，允许应用程序告知 Paxos 框架快照的位置信息。