论文笔记：[USENIX ATC'14] In Search of an Understandable Consensus Algorithm (Raft)

发表于 更新于 分类于

Raft 是一种分布式共识算法，用于解决在异步通信网络中存在节点失效且本地存储可靠的情况下多个分布式节点达成一致的问题。在已经提出 Paxos 算法用于解决这一问题的情况下继续提出 Raft 算法，主要是为了解决 Paxos 理解困难的问题。Paxos 算法更偏向于理论研究，对于实现的很多细节虽然略有提及，但是并没有进行深入的讲解和讨论，因此对于算法的实现和优化而言还有很多困难。

个人认为，Raft 算法本身，在理解上并不比 Paxos 具有更多优势。就好像数学中的非标准分析之于\(\epsilon-\delta\)极限表示法下的标准实分析。虽然使用非标准分析表述微积分内部的概念比较易于理解，但是其保证其正确的基础证明非常难以理解，而标准实分析中表述微积分内部的概念虽然有点绕，但是其基础证明的难度却没有那么高。对比而言，Paxos 的 safety 和 liveness 性质就很好理解，而 Raft 协议虽然给出了一些性质约束，但是由此能够得出 linearizability consistency 的证明却要难以理解的多 [3]。此外，这篇论文中还给出了在 Paxos Made Simple [2] 中没有讨论清楚的一些实现细节，因此对算法的实现人员比较友好，但是相对而言，对其进行进一步优化的难度也要大得多。

基本思路

Single-decree Paxos 协议中，如果想要高效的推进算法进度，也是需要选主的。但是 Paxos 论文中引入选主这一问题相当晚，直到最后一步没有 lead 时候有可能不能推进算法进行的时候，才提出可以引入主节点，通过总是让主节点获胜的方法来使得算法进行下去。而在 Multi-decrees Paxos 的场景中，如果已经有了（唯一的）主节点，又可以对算法进行相当程度的优化。Raft 协议就是针对这一点进行展开的，即先选出唯一的主节点，再由该主节点主导 log replication 过程。在此，Raft 协议还做了一个假设，即 client 的请求只由主节点进行处理。考虑到上述要求，Raft 协议的第一部分要求就是选主，对此有如下限制：

  1. 任意时刻最多只能有 1 个主节点

  2. client 的请求只由主节点进行处理

  3. 主节点从不修改自己的（状态机指令）日志，至对其进行 append 操作

  4. 主节点已经提交过的日志，在换主后，必将出现在新主节点的日志中

用论文中的说法就是这样的：

Election Safety

at most one leader can be elected in a given term. §5.2
Client interaction

Clients of Raft send all of their requests to the leader. §8
Leader Append-Only

a leader never overwrites or deletes entries in its log; it only appends new entries. §5.3
Leader Completeness

if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms. §5.4 （此处 term 表示 leader 的任期）

其中 Leader Append-Only 和 Leader Completeness 这两个性质约束了选主的时候，新的主节点必须拥有最新的 committed 的日志。

在有了主节点之后，问题就简单了。主节点只需将 client 的请求定序，并复制给其他节点即可。由此引申出如下性质：

Log Matching

if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index. §5.3
State Machine Safety

if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index. §5.4.3

直觉上应该没什么问题，主节点永远拥有最新的状态，所有的请求都发给主节点，主节点在 replica 到多数后回应请求结果。liveness 主要集中在选主上面，即是否能在这样的约束条件下保证能够选出主节点，本论文没有证明这一结论。

实现细节

Raft 协议的核心在于选主。Raft 使用心跳机制用于检测主节点的存活，从而触发选主流程。每个节点有三种状态：跟随者（Follower），候选者（Candidate），领导者（Leader）。每个节点初始处于跟随者的状态。如果它认为领导者节点已经失效，则进行选主流程：

  1. 首先增加 term 顺序号，然后将自己的状态转为一个候选者。

  2. 然后提议选举自己成为领导者，并将这一请求广播给其他节点

  3. 重复上述步骤，直到以下几种情况发生：

    1. 赢得选举

    2. 其他节点已经成为了领导者

当一个节点得到多数节点的认可时，可认为其赢得选举。每个节点按照先到先得的原则同意其他节点的选举请求（此处原因可参考 Paxos，即只有一个节点选举时也会赢得选举）。考虑到 Leader Append-Only 和 Leader Completeness 这两个性质，在此过程中应该对选主过程做出合理限制，以免新任领导者节点没有最新的 committed 的状态，从而违背 State Machine Safety 性质。这一限制即，在选主请求中，携带当前自己已知的最新的 committed index。每个节点在应答其他节点的选主请求时，如果对方具有比自己当前最新 committed index 更低的值，就拒绝其选主请求。

Raft 选择随机等待重试的方法来尽量避免选举平局的出现。根据 [4] 中的结论，在不依赖于真实物理时间的情况下（包括随机量），只需有 1 个节点失效即有可能导致选主失败，因此我们只能尽量避免这一情况，而不存在确定性的策略，没有 corner case 的解决这一问题。尽管还有其他可能的策略来尽量避免这一局面的出现，但是 Raft 论文的作者认为随机 back-off 的策略比较简单而且不容易出现 corner case，个人认同这一观点。

有了主节点（领导者）后，其他问题就好办了。所有的客户端请求都统一发给主节点，这些请求在主节点上被定序，然后顺序的进行处理。主节点将接到的请求广播给所有其他节点，一旦多数节点确认接收到这一请求，即可认为该请求已经 committed，至此主节点将这一操作应用到自身的状态机上，并将结果返回给客户端。

尽管主节点可能在没有来得及将一个请求发送给多数节点时就挂掉了，此时会有两种可能性

  1. 这一请求被下一任领导者继续完成

  2. 这一请求被下一任领导者放弃，并使用其他内容覆盖

尽管这两种情况可能以任意顺序交替发生，但是仍然可以保证当且仅当一个请求被扩散到多数节点后才被 committed，一旦 committed 就不会被重写覆盖。原论文 [1] 中没有进行形式化证明，但是直觉上感觉是正确的，因为在选主的时候做出了合理的限制。论文 [3] 中含有正确性证明（不确定，没看完）。

一般来说，一个状态机系统的操作日志不会是无限长的。因此在必要的时候，我们要对状态机操作日志进行压缩（compact）。Raft 论文中使用状态机快照（snapshot）来进行日志压缩，但是其他多种方案也可以达到这一目的，例如 LSM（Log-Structured Merge tree）。一个快照可以被看作是在此时之前的所有操作日志顺序执行的结果。在保留了一定数目的操作日志后，更老的日志子集就被状态机快照所取代。快照的一个问题是，有可能某个节点落后主节点太多，以至于所需的操作日志已经变成了快照而不可获取单独的操作日志项。这既有可能是因为慢节点，也有可能是因为网络分区，还有可能是新添加的节点。对于此种情况，该节点只能获取最新的快照，进行状态机恢复，然后继续获取并应用在此之后的操作日志。

成员变换

成员变换之所以成为一个问题，是因为由于成员组成不同，在切换的时刻，可能由这两组不同的成员分别各自选出主节点，从而出现两个主节点，违背了 Election Safety 性质。

Paxos 由于不要求一定有主节点，也不要求只有一个主节点，因此可以不用进行特殊处理，只是将成员列表作为状态机的一个状态即可。Paxos 论文 [2] 中设计每个提议者（proposer）最多只能缓冲 \(\alpha\) 条来自客户端的指令，因此只需将成员变更的命令放在将要提交的第 \(\alpha + 1\) 条指令处即可。在此成员变更指令生效前，新加入的节点只作为学习者（learner）的角色即可。此外也可以参考论文 [5] 中的方法。

Raft 处理这一问题采用重叠（overlapped）集群的方式，在成员变更的过程中，要求两个重叠集群一致认可同一个主节点。需要注意的是，被移出集群的节点可能形成一个小的封闭系统自发选主，从而干扰正常集群。在此需要进行特殊处理，即当一个跟随者（Follower）认为领导者存活时（通过心跳包），不再接受其他节点的选主请求。

与 Paxos 的简单对比

Raft 应该算是 Paxos 的一个简化特例版本，由于提供了更多的工程细节，省略了一些证明的过程，所以变得更容易理解和实现。但是如果需要进一步优化，则 Paxos 应该是一个更好的选择。目前已知的两个优化的点是：

  1. 无主节点的并行提交（Raft 的前提就是有且只有一个主节点，这上面完全优化不了）

  2. 状态机指令的可交换性（例如 key-value store 场景下对两个不同 key 的操作是可交换的，Raft 不存在并行提交，所以对此也无从优化）

References

  • [1] Diego Ongaro, and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. Atc ’14 22, 2 (2014), 305–320. DOI:https://doi.org/10.1145/1529974.1529978

  • [2] Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News 32, 4 (2001), 51–58. DOI:https://doi.org/10.1145/568425.568433

  • [3] Doug Woos, James R Wilcox, and Steve Anton, et al. 2016. Planning for change in a formal verification of the raft consensus protocol. In Proceedings of the 5th ACM SIGPLAN Conference on Certified Programs and Proofs - CPP 2016, 154–165. DOI:https://doi.org/10.1145/2854065.2854081

  • [4] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382. DOI:https://doi.org/10.1145/3149.214121

  • [5] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. 2009. Vertical paxos and primary-backup replication. Proc. 28th ACM Symp. Princ. Distrib. Comput. - Pod. ’09 February (2009), 312. DOI:https://doi.org/10.1145/1582716.1582783