MIT 6.824 2015 Paxos Lab 实现笔记

Question

在 2015 年及以前，MIT 6.824 课程的一致性算法实验都是用的 Paxos 算法。实现了 Raft 之后觉得也有必要实现一下 Paxos 这个经典的算法。

首先 Paxos 算法最原始的论文有 Leslie Lamport 写的 The Part-time Parliment 和 Paxos Made Simple。前面一篇是 1990 年写的，而且不同于其他学术论文，这篇论文用讲故事的方法来描述 Paxos 算法，我其实很喜欢这篇论文。不过，因为里面出现了太多的希腊字母和单词，而且行文实在是太过独特，许多人纷纷表示看不懂。于是，Lamport 在 2001 年的一场学术会议上向其他学者口头讲了一遍 Paxos 算法，并在事后根据回忆用正常一点的英语写了第二篇更容易懂的论文。

其实 Paxos 的核心算法个人觉得比 Raft 简单，因为它只做了一件事：如何让多个参与者对一个值的取值达成一致。但是为什么大家觉得 Raft 更好懂而且更好实现呢？因为 Paxos 只用数学语言和定理描述了算法，并没有说明一些工程实现上的细节，而且也没有随论文发表源代码和测试，就算实现了也难以确保自己的实现是正确的。而 Raft 则在论文里详细地描述了每个参与者的数据结构，RPC 的定义以及详细流程，同时还给出了作者本人的参考实现，所以哪怕论文读不太懂，对着代码看也能帮助理解算法。

Paxos 算法分为 Propose、Accept、Learn 三个阶段，不区分 Leader、Follower 等，任何参与者都可以提出一个值（这会导致活锁 Live-Lock 的问题，优化实现通常还是会先选举出 Leader）。Paxos 的核心思想是，预测未来是很难的一件事，所以我们干脆限制未来的可能性就好。

Paxos 里提到了三个角色 Proposer、Acceptor、Learner，其实我们并不需要开很多个进程，这些角色实际上对应的是 RPC 过程。Proposer 是驱动 Paxos 算法的一个线程，会发送消息给 Acceptor 和 Learner。模仿 Raft 的风格，其实 Paxos 算法包含以下几个 RPC：Propose RPC、Accept RPC、Decided RPC。Acceptor 负责处理 Propose 消息和 Accept 消息，Learner 则处理 Decided 消息。

因为 Paxos 算法仅仅是确定一个值的算法，而实际应用场景中，我们需要确定一系列值，例如状态机的 Log。那么对于每一个 Log，我们都要运行一次 Paxos 算法（称为一个 Instance），所以我们还需要分配序列号用来标识我们确定的是哪个值，可以理解为是 Raft 里的 Log Index。Lab 里叫 Seq。每个进程都需要记录关于每个 Seq 的状态信息，包括见过最大的 Propose N，已经 Accept 的最大的 N 及其对应的值 V。对于提交多个日志的 Paxos 算法一般就叫做 Multi-Paxos 了。

1. 当上层应用需要提交一个 Log 的时候，需要提供给 Paxos 算法一个 Seq 和需要提交的值。然后，每个参与者（Proposer）需要雀帝那个一个比自己见过的当前 Seq 对应的最大的数字 N_max 更大的数 N，而且需要这个 N 不会被别人提出。实现上，我们可以根据参与者 ID 来分配号码，例如有 3 个参与者，0,3,6… 给 0 号进程使用，1,4,7… 给 1 号进程使用。确定数字 N 后，向所有进程（包括自己）发送 Propose(Seq, N) 消息。这个阶段用来确定谁可以在之后提交值。
2. 其他进程收到 Propose(Seq, N) 消息后，查询对应的 Acceptor 状态，如果最大的 Propose N 不如收到的大，那就更新 Acceptor 状态，记录这个 N，并且将已经 Accept 的最大的 N 以及其对应的值 V 返回给对方。也就是回复 Promise(true, AcceptN, AcceptV)。这意味着 Acceptor 做出了承诺：未来不会接受任何比 N 更小的请求。如果收到的 N 小于承诺过的 N，那么将拒绝这次 Propose 请求，回复 Promise(false)。
3. 等收到集群中超过半数的成功回复后，就可以进入 Accept 阶段，这个阶段用来确定最终提交的值。但是，Proposer 不一定可以提交上层应用提交的值，而是要先检查 Promise 回复中，最大的 AcceptN 是多少，如果所有的回复都表示没有 Accept 过值，那么 Proposer 才可以申请 Accept 自己的值；否则，Proposer 只能申请 Accept 最大的 AcceptN 对应的 AcceptV。
4. 确定好提交的值后，向所有 Acceptor 发送 Accept(Seq, N, V) 请求。Acceptor 收到 Accept 请求后，检查 N 是否大于等于自己收到过的最大的 Propose N。如果是，那么值就被确定了，Acceptor 将这次的 N 记录到自己最大的 AcceptN 中，并将值保存到 AcceptV 里，返回 Accept(true)；否则拒绝这次 Accept 请求，返回 Accept(false)。
5. Proposer 收到超过半数的 Accept 成功回复后，就可以认为这个值已经成功提交了。这时候就可以给客户端返回成功的消息，并向集群广播 Decided(Seq, N) 信息。Learner 收到 Decided 信息后，直接将 Seq 对应的值保存在自己的日志里，并且将 Seq 的状态修改为 Decided。

总结一下，Paxos 决定值的关键阶段是 Propose 和 Accept，Propose 是主动发起的请求，其他都是被动处理的：

1. Propose 阶段用来寻找已经被确定的值，防止更旧的值被提交。
2. Accept 阶段确定值，一旦大多数都接受了某个值，那么未来所有的提交都将会是这个值。

实现了基础的 Paxos 算法之后，就可以在这个基础上实现 KV 服务了，也就是 Lab 3 的下半部分。

实现 Paxos KV 的思路和 Raft KV 其实大同小异，只是 Log 的 Index 需要由 KV 服务器自己提供，个人实现的时候是取第一个日志空洞的位置。同时，何时将日志应用到状态机也需要应用自己处理。尽管日志可以乱序确定具体值，但是提交还是要按顺序。只要模仿 Raft 维护一个 apply 的 Index，然后按顺序查询 Paxos 日志，将确定的值应用到状态机即可。去重原理也是利用 Reqeust ID 进行去重即可。

至于确定日志状态，粗暴点的办法就是定时轮询，实验对性能没有要求，就选择这个简单的办法。

Paxos 和 Raft

可以看出，Paxos 并不像 Raft 那样提交某个日志的时候将前面连续的所有日志也一起提交，而是允许“空洞”的存在。但这也会带来一些麻烦，进程需要逐条查询缺失的日志，论文里提到的就是重新发起一次 Paxos 过程即可。

之前提到活锁的问题，Paxos 有可能发生以下的情况：

1. A Propose 1 并且得到了大多数回复，准备 Accept。
2. B 这时 Propose 2，因为数字更大，Acceptor 更新自己的状态，得到大多数回复。
3. A 发送 Accept 1 请求，因为 1 < 2，所以这次 Accept 被拒绝，重新发起 Propose 3，得到大多数回复。
4. B 发送 Accept 2 请求，同样 2 < 3，Accept 被拒绝，B 重新发起 Propose 4，得到大多数回复。

以此类推，虽然整个系统里没有人宕机，消息也正常收发，但是系统的整体状态却没能推进。针对这种情况的解决办法也很简单，确保只有一个 Proposer 能够提出 Propose 请求即可。至于怎么选举 Leader，Lamport 提出了一种简单的办法，那就是谁的 ID 大谁就当 Leader，并定期向其他进程发送心跳消息维持 Leader 身份。

其他进程如果超过一定时间间隔都没有收到 Leader 心跳，那么就尝试将自己选举成 Leader。收到客户端请求之后，如果发现自己不是 Leader，就拒绝这次请求，并通知客户端 Leader 的地址。非 Leader 不可以发起 Propose 请求，也就不会向其他服务器发送信息。即使是同时出现两个 Leader 也不要紧，因为 Paxos 本来就允许多个进程同时发起 Propose 请求，只是效率更低。

另外，对于每一个日志项都需要发送两轮 RPC，一次 Propose 一次 Accept 才可以确定值，显得有些低效。能不能在满足某些条件的时候只通过 Accept 来确定值呢？例如，如果我们能猜到 Prepare 的结果是可以自由提出任何值，不就可以省略 Prepare，直接 Accept 我们需要的值吗？如果我们能确保 Leader 只能有唯一一个，那就不会有其他人主动发起 Propose 请求了。我们可以将 Leader 选举过程也当成一条特殊的日志写入状态机就好了，Paxos 会保证这条日志只会有唯一确定的取值。

当一个 Proposer 在 Leader Elect 过程中收到大多数 Accept 回复后，就可以确定自己是 Leader 了，之后都可以用自己的 Propose N 来提交日志了。Leader 当选之后需要补齐自己的日志空洞，对于未提交的日志，需要用自己的 Propose N 来重新提交一次。

所以其实 Multi-Paxos 和 Raft 很像，选主的时候都是谁数字大谁当选（Raft 是 Term，Paxos 是 Propose N）。而且，一旦一个日志项（Raft 叫 Log Entry，Paxos 叫 Proposal）被多数派接收，那么它就是可以提交（Committ）的，而且这个值将永远不会被修改。等日志被提交（Committed）之后，上层应用才能应用（Apply）。Raft 强制日志要按顺序 Commit 以及 Apply，但 Paxos 允许乱序 Commit 的特性，给了上层应用更大的灵活性可以乱序 Apply。所以理论上，Paxos 性能上限比 Raft 更高。

Raft 相对于 Paxos 而言做出了更多的限制：

1. 同步日志上，Raft 不允许日志出现空洞，也就是如果想同步一条日志，需要将这条日志之前的所有日志也一并同步，Paxos 则认为日志之间是独立的，可以单独地同步任何一条日志。
2. Leader Election 上，只有日志和半数以上的成员至少一样新，才可以当选 Leader，而 Paxos 则是任何一个成员都可以当选。
3. 前面两个限制简化了 Leader Election 和日志提交的过程，只要 Leader 有最新的已被提交的日志，那么之前的日志都是已经提交的。至少有一个多数派有已经提交的日志。

而 Raft 和 Paxos 保证一个值被多数派确定确定后不会被修改都是利用了同一个原理：任何多数派之间肯定有交集。这个交集就确保了这个值不会被修改。

所以，其实 Raft 反而比 Paxos 多了更多限制，更复杂，更不好懂。据说 MIT 6.824 第一年换用 Raft 作为 Programming Lab 的时候，TA 和学生都饱受折磨，错误地以为 Raft 至少和 Paxos 一样好写，但胜在 Paper 详细，Diego Ongaro 的博士论文基本就等于手把手教你实现 Raft 了，他本人也给出了 LogCabin 这个参考实现。

Paxos 其实更简洁，限制更少，但可惜一开始的 Paper 写得过于文学性，后面的 Paper 也没有给伪代码或者代码参考等，让人难以将算法翻译成代码。看来酒香也怕巷子深，好的东西还是要用大众更容易接受的办法展示出来才能收获更多关注。

也难怪 Google Chubby 作者 Mike Burrows 说：世界上只有一种共识算法，那就是 Paxos。