In Search of an Understandable Consensus Algorithm (Extended Version)

阅读论文 Raft，参考 FAQ1，note1，FAQ2，note2。

概述

MapReduce 的 master、GFS 的 master 和 VM FT 的共享磁盘都存在单点故障（即使 GFS 的 master 存在副本，其依然是单点故障，因为故障时系统会停止），从而可以很简单的避免脑裂。脑裂会发生的根本原因在于，无法区分机器故障和网络分区故障。共识算法使用多数原则（仲裁协议，quorum），可以在复制的同时避免脑裂。如果集群中有 \(2f+1\) 个服务器，则共识算法可以容忍 \(f\) 个服务器故障。共识算法通常使用状态机复制，以复制日志的方式实现。客户端、服务器以及共识算法和状态机的关系见下图。

Raft 的主要设计目标是可理解性，通过分解问题和减少状态来实现。问题被分解为多个子集，例如：领导者选举、日志复制、安全性和成员变更。使用随机化超时时间、限制选举保证日志单向流动等方式，来减少状态。

实现

基础知识

服务器有三种状态：leader、follower、candidate，服务器初始时都是 follower。正常情况下，只有一个 leader 和多个 follower。只有 leader 会处理客户端的请求，如果客户端将请求发送给 follower，该 follower 会将其重定向到 leader。服务器之间使用远程过程调用（RPC）进行通信，基本的 Raft 算法使用两种 RPC，candidate 在选举时会发起 RequestVote RPC，leader 在复制日志和发送心跳时会发起 AppendEntries RPC（心跳消息是没有日志条目的 AppendEntries RPC）。Raft 保证 RPC 是幂等的。

时间被划分为任期（term），使用单调递增的连续整数表示。每个服务器都会持久存储当前任期，不同服务器的任期可能不同（由于故障）。服务器之间进行通信时会交换任期，处于旧任期的服务器会更新其任期。如果 leader 或 candidate 发现自己包含旧任期，它会成为 follower。如果服务器收到具有旧任期的请求，它会拒绝该请求。

领导者选举

如果一个 follower 在超时时间（该时间被称为选举超时，election timeout）内没有收到来自 leader 或 candidate 的有效 RPC（何为有效，参考图 2），它将递增其任期成为 candidate，开始选举新的 leader。它为自己投票，然后向集群中的其它服务器发送 RequestVote RPC。

• 如果 candidate 收到大多数服务器的投票，它会成为新的 leader，同时向其他服务器发送心跳消息，以建立其权威防止新的选举。每个服务器在给定的任期内，只能投票给一个 candidate。服务器是否投票给某个 candidate 存在限制，将在安全性中讨论。
• 如果在等待投票时，candidate 收到 leader 的 AppendEntries RPC，且 leader 的任期大于等于 candidate 的任期，那么 candidate 会成为 follower。如果 leader 的任期更小，则 candidate 会拒绝该 RPC。或者收到其他 candidate 的 RequestVote RPC，且其任期大于当前 candidate 的任期，当前 candidate 同样会成为 follower。
• 如果存在多个 candidate 使选票分裂，使得没有 candidate 可以得到大多数服务器的投票，则每个 candidate 都会超时，继续递增任期，重新开始选举。Raft 使用随机 election timeout 来确保选票分裂很少发生（避免同时超时），election timeout 是从一个固定间隔中随机选择的（例如 [150, 300] 毫秒），每个候选人在开始选举时会重新随机化 election timeout。

如果 follower 在执行完成 AppendEntries RPC 之后，回复之前发生崩溃，则 leader 会重试 RPC。如果 follower 重新上线，它会忽略重复请求中的日志条目。如果 candidate 在发送 RequestVote RPC 之后崩溃，重启之后它会重新发送 RPC，follower 会持久存储其投票的 candidate，避免在同一任期内多次投票。

为了保证系统的可用性，election timeout 存在如下要求：

$$ broadcastTime\ll electionTimeout\ll MTBF $$

其中 \(broadcastTime\) 是发送 RPC 的平均往返时间，\(electionTimeout\) 是 follower 的超时时间，\(MTBF\) 是单个服务器的平均故障间隔时间。broadcast time 应该比 election timeout 小一个数量级，防止 follower 开始不必要的选举。election timeout 应该比 MTBF 小几个数量级，这样在 leader 真正发生故障时客户端不会等待太久。

日志复制

客户端会向 leader 发送请求，请求包含由复制状态机执行的命令，leader 会将当前任期和命令作为一个条目（entry）追加到日志中（只读命令可以不记录日志，但有额外的限制，在可线性化中描述），由日志索引标识其位置。然后 leader 向其他服务器并行发送 AppendEntries RPC 以复制该条目，当大多数服务器确认复制该条目时，leader 将条目应用到其状态机（即状态机执行条目中的命令），并将执行结果返回给客户端，之后 leader 通过不断地失败重试保证剩余服务器会复制该条目。

只要创建日志条目的 leader 将其复制到大多数服务器上，该日志条目就是已提交的（committed）。注意，是创建日志条目的 leader，而不是之后的 leader，这将在安全性中讨论。Raft 保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。leader 提交其创建的日志条目时，也会提交 leader 日志中在该日志条目之前的所有日志条目，包含由之前 leader 创建的条目（会在安全性中解释原因）。leader 会跟踪其已提交日志条目的最高索引，并且在之后的 AppendEntries RPC 中包含该索引，以通知 follower 哪些日志条目已提交，之后 follower 会应用已提交的日志条目到本地状态机（按照日志顺序）。

Raft 的日志匹配（Log Matching）属性保证不同服务器之间日志的一致性：如果两个日志在同一索引位置的条目具有相同任期，则两个日志中所有小于等于该索引位置的条目都相同。如何实现该属性？leader 在给定任期只会对自己的日志进行追加，而不会覆盖。当 leader 向 follower 发送 AppendEntries RPC 时，会进行一致性检查。请求中会包含上一个条目的索引和任期，如果 follower 中对应索引的任期不同，则 follower 会拒绝该请求，回复 leader 匹配失败。如果系统正常运行，那么所有服务器上的日志都会相同。

但是当发生故障时，服务器之间的日志会产生不一致。如何处理不一致？leader 会为每个 follower 维护一个 nextIndex，表示 leader 下次向 follower 发送该索引位置的日志条目，如果 follower 拒绝 leader 的 AppendEntries RPC，则 leader 会将该 follower 对应的 nextIndex 递减，然后重试 RPC 直到 follower 和 leader 的日志完全相同（冲突条目将被删除）。整个过程表现为，递减 follower 的 nextIndex 到和 leader 日志最长相等前缀之后的一个位置，然后追加条目到 follower 直到其 nextIndex 和 leader 日志的尾后索引相等。

可以对上述算法进行优化，不是将 nextIndex 每次递减 1，而是递减整个任期，这通过在 follower 回复的信息中包含冲突条目的任期以及该任期在其日志中的第一个索引位置来实现。从而，每个冲突的任期都需要一个 AppendEntries RPC，而不是每个冲突的条目一个 RPC。为什么直接返回第一个索引位置，论文并没有描述之后该如何处理。我的理解是，其实并不是从该索引位置开始重传日志条目，因为这样可能会导致不必要的重传已提交的日志条目。在 leader 接收到冲突的任期和第一个索引之后，应该会递增该索引直到任期不同为止（之所以可以这样，是因为日志匹配属性），然后再传递该位置的日志条目。这样关于课程中提出的问题，为什么需要返回任期，而不是只返回第一个索引，也可以得到解答。

安全性

选举限制

即使日志一致，两个状态机也可能执行不同的命令序列。例如，leader 提交日志时，某个 follower 可能发生故障，如果它成为 leader，它将覆盖旧 leader 中的条目，而这些条目可能已经应用于旧 leader 的状态机上。为此 Raft 的领导者完整性（Leader Completeness）属性保证在某个任期被提交的日志条目必定会出现在更高任期的 leader 日志中，从而可以保证所有状态机执行相同的命令序列。

如何实现该属性？candidate 在发送 RequestVote RPC 时，会包含其日志信息，如果投票者的日志比 candidate 的日志更（读第四声）新，则投票者会拒绝投票。更新的定义如下：如果两个日志的最后一个条目具有不同任期，则更大任期的日志更新；否则，更长的日志更新。上述限制使得，只有包含所有已提交日志条目的 candidate 才有可能当选 leader，日志只会从 leader 流向 follower。

提交之前任期的条目

在日志复制中提到，创建日志条目的 leader 将其复制到大多数服务器上，则该日志条目就是已提交的。之所这样定义，是因为即使 leader 将之前任期的条目（不是由当前 leader 创建）复制到大多数服务器上，依然可能会被之后的 leader 覆盖（根据之前描述的日志匹配属性）。如果将其视为已提交，则会违反领导者完整性属性，导致状态机不一致。那么之前任期的条目何时视为已提交？当前任期的一个日志条目被提交时，由于日志匹配属性，之前任期的条目将会间接提交。

日志压缩

日志可能会变得很大，导致崩溃恢复需要花费很多时间重放所有日志，以及日志占用大量空间，Raft 通过使用快照来压缩日志。每个服务器会定期创建快照（通常是当日志达到固定大小时），快照中包含状态机的状态、状态对应的最后一个日志条目的索引和任期（以支持 AppendEntries PRC 的一致性检查）、当时的配置信息（用于集群成员变更）。当服务器将快照持久化之后，可以删除该快照之前的日志和之前的快照（剩余日志的索引并不会重置为从 1 开始，或许会新开一个数组从 1 开始存储，但是对外来说索引总是会加上某个偏移量）。

如果有一个严重滞后或新加入集群的 follower，它需要的日志可能已经被 leader 删除，此时 leader 需要使用 InstallSnapshot RPC 向滞后的 follower 发送快照。通常快照会比 follower 的日志更新，follower 会丢弃整个日志，使用快照替代。但是，由于重传或错误，follower 可能会收到描述其日志前缀的快照，此时仅会删除快照覆盖的日志，快照之后的日志将被保留。

为了避免在创建快照时停止操作，可以使用写时复制技术。状态机可以通过实现某种数据结构支持写时复制，或者使用操作系统的写时复制支持（例如，Linux 的 fork）来创建状态机的内存快照（作者使用该实现方式）。具体来说，Linux 的 fork 创建的子进程会共享和父进程相同的内存页面，如果父进程更新页面，则操作系统会对该页面执行写时复制。

可线性化

什么是可线性化？每个操作似乎在其调用和响应之间的某个时刻以原子的方式执行。Raft 如何实现可线性化语义？如果 leader 在执行命令之后回复客户端之前崩溃，然后客户端在新的 leader 重试请求，将会多次执行同一个命令。如果客户端向新 leader 发送读请求，由于旧 leader 在回复客户端之后发送下一个 AppendEntries RPC 之前崩溃，新 leader 可能并没有将某些已提交的命令应用到状态机，此时客户端可能会从新 leader 读取到旧数据。如果出现网络分区故障，旧 leader 可能不知道它已经被新 leader 取代，此时客户端可能从旧 leader 读取到旧数据。

首先，客户端需要为每个命令分配唯一的序列号，状态机会跟踪为每个客户端处理的最后的序列号以及相关响应。如果状态机收到已被执行的命令，它不会执行该命令而是直接返回响应。注意，日志中依然包含重复命令的日志条目。其次，每个 leader 在任期开始时会提交一个无操作日志条目，从而确定哪些日志条目已被提交并将其应用到状态机。能否通过心跳消息确定哪些日志条目已提交，个人认为不能，就是之前提到的旧任期日志条目不能通过计数判断是否已提交。最后，leader 在回复读请求之前，需要和集群中的大多数交换心跳消息，以确保它仍然是 leader（或者可以使用租约，论文中没有详细介绍，不过课程笔记中有提到具体方式）。

问题

Q：Raft 集群是部署在一个数据中心，还是多个数据中心？

A：通常是一个数据中心，这样可以避免 leader 跨数据中心向多个 follower 发送 RPC（网络延迟）。

Q：客户端如何知道谁是新的 leader？

A：客户端包含所有 server 的地址，它可以随机发送请求，follower 会将请求重定向到它认为的 leader。

Q：为什么日志的索引从 1 开始？

A：可以将其视为从 0 开始，索引 0 包含任期为 0 的空日志条目，以方便 AppendEntries RPC 在初始时的一致性检查。个人认为，类似于求数组的前缀和时从索引 1 开始。

Q：Raft 何时将其状态（currentTerm、votedFor、log）持久化到磁盘？

A：在内存中修改状态的同时刷盘，只有持久化之后 leader 才能向 follower 发送 RPC，follower 才能回复 leader，leader 才能将命令应用到状态机。否则，如果服务器发生崩溃，Raft 的各种属性将无法得到保证。

Q：图 2 中的 lastApplied 为何不需要持久化？如果发生崩溃，服务器如何知道日志条目是否应用于状态机？

A：论文作者在会话中对该问题以及下一个问题进行了解释（推荐阅读）。实际上 lastApplied 是否被持久化取决于状态机是否被持久化。如果状态机不被持久化，那么崩溃恢复之后需要重放所有日志，所以 lastApplied 会被初始化为 0。否则，只需重放 lastApplied 之后的日志。按我的理解，由于快照的存在，以及更新状态机的同时持久化产生的随机 I/O 开销较大，所以状态机一般不会实时持久化。如果存在快照，lastApplied 会被赋值为快照中包含的索引。

Q：图 2 中的 matchIndex 有什么作用？

A：matchIndex 表示 follower 和 leader 匹配的最高日志条目的索引（可能会小于实际值），只要大多数 follower 的 matchIndex 超过 leader 的 commitIndex，并且 log[matchIndex] 条目的任期是当前 leader 的任期（参见提交的定义），则 leader 可以增加 commitIndex。

Q：图 7 的 leader 崩溃之后，谁有可能成为新的 leader？

A：服务器 acd 都有可能成为新的 leader。首先日志 9 是最后一个提交的日志条目，根据领导者完整性属性，只能从 acd 中选择 leader。同时，acd 都有可能得到大多数服务器的投票，对于 a 来说是 abef，对于 c 来说是 abcef，对于 d 来说是 abcdef。有一点需要注意，服务器最后一个日志条目的任期可能并不是其当前任期。

总结

Raft 共识算法实现可线性化一致性模型，核心内容包括领导者选举、日志复制和安全性。论文中还提到 Raft 的集群成员变更机制，我并没有做介绍。然后日志压缩可以看作是 Raft 的额外补充。如课程中所述，论文中也有很多细节没有介绍，单个机制可以有多种不同的实现方式。课程视频、问答和笔记是对论文很好的补充，其中还提到一篇文章 Raft does not Guarantee Liveness in the face of Network Faults，讲述 Raft 在特定情况下无法建立稳定的领导者，除非使用 PreVote 和 CheckQuorum 技术。可见这篇论文介绍的仅仅是 Raft 的基本实现，现实中面临各种复杂场景，或许需要添加很多额外的机制。

附录