Raft 算法

In Search of an Understandable Consensus Algorithm (Extended Version) 论文：

拜占庭将军问题

假设多位拜占庭将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成是否要进攻的一致性决定？

解决方案大致可以理解成：先在所有的将军中选出一个大将军，用来做出所有的决定。

举例如下：假如现在一共有 3 个将军 A，B 和 C，每个将军都有一个随机时间的倒计时器，倒计时一结束，这个将军就把自己当成大将军候选人，然后派信使传递选举投票的信息给将军 B 和 C，如果将军 B 和 C 还没有把自己当作候选人（自己的倒计时还没有结束），并且没有把选举票投给其他人，它们就会把票投给将军 A，信使回到将军 A 时，将军 A 知道自己收到了足够的票数，成为大将军。在有了大将军之后，是否需要进攻就由大将军 A 决定，然后再去派信使通知另外两个将军，自己已经成为了大将军。如果一段时间还没收到将军 B 和 C 的回复（信使可能会被暗杀），那就再重派一个信使，直到收到回复。

复制状态机

复制状态机的核心思想：相同的初始状态 + 相同的输入 = 相同的结束状态

多个节点上，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态。

TIP

在 Raft 中，Leader 将客户端请求（Command）封装到一个个 log entry 中，将这些 log entries 复制到所有 follower 节点，然后大家按相同顺序应用 log entries 中的 command，根据复制状态机的理论，大家的结束状态肯定是一致的。

把复制状态机需要同步的数据量按大小进行分类，它们分别适合不同类型的共识算法：

数据量非常小，如集群成员信息、配置文件、分布式锁、小容量分布式任务队列。可以采用无 Leader 的共识算法（如 Basic Paxos），实现有 Chubby、ZooKeeper 等。

数据量比较大但可以拆分为不相干的各部分，如大规模存储系统。可以采用有 Leader 的共识算法（如 Multi Paxos、Raft），实现有 GFS、HDFS 等。

不仅数据量大，数据之间还存在关联，这时一个共识算法集群容纳不了所有的数据。这种情况下，就要把数据分片到多个状态机中，状态机之间通过 两阶段提交 来保证一致性。这类场景主要是一些如 Spanner、OceanBase、TiDB 等支持分布式事务的分布式数据库。它们通常会对 Paxos 或 Raft 等共识算法进行一定的改造，来满足事务级的要求。

共识算法

共识是可容错系统中的一个基本问题：即使面对故障，服务器也可以在共享状态上达成一致。

共识算法允许一组节点像一个整体一样一起工作，即使其中的一些节点出现故障也能够继续工作下去，其正确性主要是源于复制状态机的性质：一组 Server 的状态机计算相同状态的副本，即使有一部分的 Server 宕机了它们仍然能够继续运行。

我们使用共识算法，就是为了实现复制状态机。

一般通过使用复制日志来实现复制状态机。

每个 Server 存储着一份包括命令序列的日志文件，状态机会按顺序执行这些命令。因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。由于状态机是确定性的，所以处理相同的状态，得到相同的输出。因此共识算法的工作就是 保持复制日志的一致性。

服务器上的共识模块从客户端接收命令并将它们添加到日志中。它与其他服务器上的共识模块通信，以确保即使某些服务器发生故障，每个日志最终包含相同顺序的请求。一旦命令被正确地复制，它们就被称为已提交。每个服务器的状态机按照日志顺序处理已提交的命令，并将输出返回给客户端，因此，这些服务器形成了一个单一的、高度可靠的状态机。

适用于实际系统的共识算法通常具有以下特性：

安全：确保在非拜占庭条件（也就是上文中提到的简易版拜占庭）下的安全性，包括网络延迟、网络分区、丢包、重复发送、乱序问题，无法解决拜占庭问题（如存储不可靠、消息错误）。
高可用：只要大多数服务器都是可操作的，并且可以相互通信，也可以与客户端进行通信，那么这些服务器就可以看作完全功能可用的。在集群中大多数服务器响应，命令就可以完成，不会被少数运行缓慢的服务器来影响整体系统性能。因此，一个典型的由五台服务器组成的集群可以容忍任何两台服务器端故障。假设服务器因停止而发生故障；它们稍后可能会从稳定存储上的状态中恢复并重新加入集群。
一致性不依赖时序：错误的时钟和极端的消息延迟，在最坏的情况下也只会造成可用性问题，而不会产生一致性问题。这一点是共识算法的优势，因为共识算法不受硬件影响，不会因外部因素造成错误。但也造成了一些限制，让共识算法受网络影响很大，在异地容灾场景下，共识算法的支持性比较差。

Raft 区分于其他共识算法的三个特征：

Strong Leader：在 Raft 中，日志只能从 Leader 流向其他服务器。这简化了复制日志的管理，使得 Raft 更容易理解。
Leader Election：Raft 使用随机计时器进行 Leader 选举。这只需在任何共识算法都需要的心跳（heartbeats）上增加少量机制，同时能够简单快速地解决冲突。
Membership Changes：Raft 使用一种 联合一致（Joint Consensus）的方法 来处理集群成员变更的问题，变更时，两种不同配置的大多数机器会重叠。这允许整个集群在配置变更期间可以持续正常运行。

长生命周期的强 Leader，是 Raft 实现起来简单，并区别于其他共识算法最重要的特点。但不可忽视的是，这一点也使得 Raft 在性能上存在很大的隐患。因为 Raft 日志流的单向性，Raft 选举出的 Leader 必须具有完整的日志。为了保证时时刻刻都能有具备完整日志的节点可以成为 Leader，Raft 又必须使用 顺序日志复制 的方法来避免日志空洞。这就是 Raft 的三个子问题 领导人选举、日志复制、安全性 的闭环逻辑。

no-op（no-operation）补丁

一个节点当选 Leader 后，立刻发送一个自己当前任期的空日志体的 AppendEntries RPC。这样就可以把之前任期内满足提交条件的日志都提交了。

一旦 no-op 完成复制，就可以把之前任期内符合提交条件的日志保护起来了，从而就可以使它们安全提交。因为没有日志体，这个过程应该是很快的。

目前大部分应用于生产系统的 Raft 算法，都是启用 no-op 的。

状态简化

节点类型

一个 Raft 集群包括若干服务器，以典型的 5 服务器集群举例。在任意的时间，每个服务器一定会处于以下三个状态中的一个：

Leader：负责发起心跳，响应客户端，创建日志，同步日志。
Candidate：Leader 选举过程中的临时角色，由 Follower 转化而来，发起投票参与竞选。
Follower：接收 Leader 的心跳和日志同步数据，投票给 Candidate。

在正常的情况下，只有一个服务器是 Leader，剩下的服务器是 Follower。Follower 是被动的，它们不会发送任何请求，只是响应来自 Leader 和 Candidate 的请求。

任期

Raft 算法将时间划分为任意长度的任期（term），任期用连续的数字表示，看作当前 term 号。每一个任期的开始都是一次选举，在选举开始时，一个或多个 Candidate 会尝试成为 Leader。如果一个 Candidate 赢得了选举，它就会在该任期内担任 Leader。如果没有选出 Leader，将会开启另一个任期，并立刻开始下一次选举。Raft 算法保证在任意一个任期内，最多只有一个 Leader。

RPC 通信

Raft 算法中服务器节点之间使用 RPC 进行通信，并且 Raft 中只有两种主要的 RPC：

RequestVote RPC（请求投票）：由 Candidate 在选举期间发起。
AppendEntries RPC（追加条目）：由 Leader 发起，用来复制日志和提供一种心跳机制。

每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号：

如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值。
如果一个 Candidate 或者 Leader 发现自己的 term 过期了，他会立即退回成 Follower。
如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求。

日志

entry：每一个事件成为 entry，只有 Leader 可以创建 entry。entry 的内容为 <term, index, cmd>，其中 cmd 是可以应用到状态机的操作。
log：由 entry 构成的数组，每一个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机中。

领导人选举

Raft 使用 心跳机制 来触发 Leader 的选举。如果一台服务器能够收到来自 Leader 或者 Candidate 的有效信息，那么它会一直保持为 Follower 状态，并且刷新自己的 electionElapsed，重新计时。

Leader 会向所有的 Follower 周期性发送心跳来保证自己的 Leader 地位。如果一个 Follower 在一个周期内没有收到心跳信息，就叫做选举超时，然后它就会认为此时没有可用的 Leader，并且开始进行一次选举以选出一个新的 Leader。

为了开始新的选举，Follower 会 自增自己的 term 号 并且 转换状态为 Candidate。然后他会 投票给自己，并且并行地向所有节点发起 RequestVote RPC 请求，Candidate 的状态会持续到以下情况发生：

获得超过半数选票赢得选举：成为 Leader 并开始发送心跳。
其他节点赢得选举：收到新 Leader 的心跳后，如果新 Leader 的任期号不小于自己当前的任期号，那么就从 Candidate 回到 Follower 状态。
一轮选举结束无人胜出：每个 Candidate 都在一个自己的随机选举超时时间后增加任期号开始新一轮投票。

赢得选举的条件是：一个 Candidate 在一个任期内收到了来自集群内的多数选票（ $\frac{N}{2} + 1$ ），就可以成为 Leader。

在 Candidate 等待选票的时候，它可能收到其他节点声明自己是 Leader 的心跳，此时有两种情况：

该 Leader 的 term 号大于等于自己的 term 号，说明对方已经成为 Leader，则自己回退为 Follower。
该 Leader 的 term 号小于自己的 term 号，那么会拒绝该请求并让该节点更新 term。

由于可能同一时刻出现多个 Candidate，导致没有 Candidate 获得大多数选票，如果没有其他手段来重新分配选票的话，那么可能会无限重复下去。Raft 使用了 随机的选举超时时间 来避免上述情况。每一个 Candidate 在发起选举后，都会随机化一个新的选举超时时间，这种机制使得各个服务器能够分散开来，在大多数情况下只有一个服务器会率先超时；它会在其他服务器超时之前赢得选举。

// 请求投票 RPC Request
struct RequestVoteRequest {
    int term;         // 自己当前的任期号
    int candidateId;  // 自己的 ID
    int lastLogIndex; // 自己最后一个日志号
    int lastLogTerm;  // 自己最后一个日志的任期
}

// 请求投票 RPC Response
struct RequestVoteResponse {
    int  term;        // 自己当前的任期号
    bool voteGranted; // 自己是否投票给这个 Candidate
}

对于没有成为 Candidate 的 Follower 节点，对于同一个任期，会按照 先来先得 的原则投出自己的选票。

日志复制

一条日志（<index, term, cmd>）中需要具有三个信息：

日志号（index）
Leader 的任期号（term）
状态机指令（cmd）

一旦选出了 Leader，它就开始接收客户端的请求。每一个客户端的请求都包含一条需要被复制状态机（Replicated State Machine）执行的命令。Leader 收到客户端请求后，会生成一个 entry，包含 <index, term, cmd>，再将这个 entry 添加到自己的日志末尾后，向所有的节点广播该 entry（Leader 并行发送 AppendEntries RPC 给 Follower），要求其他服务器复制这条 entry。如果 Follower 接收该 entry，则会将 entry 添加到自己的日志后面，同时返回给 Leader 同意。如果 Leader 收到了超过半数的成功响应，Leader 会将这个 entry 应用到自己的状态机中，之后可以称这个 entry 是提交的，并且向客户端返回执行结果。

日志复制超过了半数的节点后，是否就会百分百会提交呢？

不是。因为从 Follower 复制完成，到 Follower 通知 Leader，再到 Leader 完成提交，是需要时间的。在这个时间内如果 Leader 宕机了，日志复制虽然超过了半数的节点，但是未能完成提交。

Raft 保证以下两个性质：

在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们一定有相同的 cmd。（通过“仅有 Leader 可以生成 entry”来保证第一个性质）
在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们前面的 entry 也一定相同。（通过“一致性检查”来保证第二个性质）

在此过程中，Leader 或 Follower 随时都有崩溃或缓慢的可能性，Raft 必须要在有宕机的情况下继续支持日志复制，并且保证每个副本日志顺序的一致，以保证复制状态机的实现。具体有三种可能：

如果有 Follower 因为某些原因没有给 Leader 响应，那么 Leader 会不断地重发追加条目请求（AppendEntries RPC），哪怕 Leader 已经回复了客户端。
如果有 Follower 崩溃后恢复，这时 Raft 追加条目的一致性检查生效，保证 Follower 能按顺序恢复崩溃后缺失的日志。

Raft 的一致性检查

Leader 在每一个发往 Follower 的追加条目 RPC 中，会放入前一个日志条目的索引位置和任期号，如果 Follower 在它的日志中找不到前一个日志，那么它就会拒绝此日志，Leader 收到 Follower 的拒绝后，会发送前一个日志条目，从而逐渐向前定位到 Follower 第一个缺失的日志。

如果 Leader 崩溃，那么崩溃的 Leader 可能已经复制了日志到部分 Follower 但还没有提交，而被选出的新 Leader 又可能不具备这些日志，这样就有部分 Follower 中的日志和新 Leader 的日志不相同。Raft 在这种情况下，Leader 通过 强制 Follower 复制它的日志 来解决不一致的问题，这意味着 Follower 中跟 Leader 冲突的日志条目会被新 Leader 的日志条目覆盖（因为没有提交，所以不违反外部一致性）。

总结

通过这种机制，Leader 在当权之后就不需要任何特殊的操作来使日志恢复到一致状态。

Leader 只需要进行正常的操作，然后日志就能在回复 AppendEntries 一致性检查失败的时候自动趋于一致。

Leader 从来不会覆盖或者删除自己的日志条目（Append-Only）。

这样的日志复制机制，就可以保证一致性特性：

只要过半的服务器能正常运行，Raft 就能够接收、复制并应用新的日志条目；
在正常情况下，新的日志条目可以在一个 RPC 来回中被复制给集群中的过半机器；
单个运行慢的 Follower 不会影响整体的性能。

// 追加日志 RPC Request
struct AppendEntriesRequest {
    int term;         // 自己当前的任期号
    int leaderId;     // Leader (自己) 的 ID
    int prevLogIndex; // 前一个日志的日志号
    int prevLogTerm;  // 前一个日志的任期号
    byte[] entries;   // 当前日志体
    int leaderCommit; // Leader 的已提交日志号
}

// 追加日志 RPC Response
struct AppendEntriesResponse {
    int  term;    // 自己当前的任期号
    bool success; // Follower 是否包括前一个日志
}

如果 leaderCommit > commitIndex，那么把 commitIndex 设为 MIN(leaderCommit, index of last new entry)。

为了使得 Follower 的日志和自己的日志一致，Leader 需要找到 Follower 与它日志一致的地方，然后删除 Follower 在该位置之后的日志，接着把这之后的日志发送给 Follower。Leader 给每一个 Follower 维护了一个 nextIndex，它表示 Leader 将要发送给该追随者的下一条日志条目的索引。当一个 Leader 开始掌权时，它会将 nextIndex 初始化为它的最新的日志条目索引数 +1。如果一个 Follower 的日志和 Leader 的不一致，AppendEntries 一致性检查会在下一次 AppendEntries RPC 时返回失败。在失败之后，Leader 会将 nextIndex 递减然后重试 AppendEntries RPC。最终 nextIndex 会达到一个 Leader 和 Follower 日志一致的地方。这时，AppendEntries 会返回成功，Follower 中冲突的日志条目都被移除了，并且添加所缺少的上了 Leader 的日志条目。一旦 AppendEntries 返回成功，Follower 和 Leader 的日志就一致了，这样的状态会保持到该任期结束。

安全性

Leader 宕机处理：选举限制

如果一个 Follower 落后了 Leader 若干条日志（但没有漏一整个任期），那么在下次选举中，按照领导者选举里的规则，它依旧有可能当选 Leader。它在当选新 Leader 后就永远也无法补上之前缺失的那部分日志，从而造成状态机之间的不一致。

所以 Leader 需要保证自己存储全部已经提交的日志条目。这样才可以使日志条目只有一个流向：从 Leader 流向 Follower，Leader 永远不会覆盖已经存在的日志条目。

RequestVote RPC 执行了这样的限制：RPC 中包含了 Candidate 的日志信息，如果投票者自己的日志比 Candidate 的还新，它会拒绝掉该投票请求。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁的日志比较新：

如果两个日志的 term 不同，term 大的更新；
如果 term 相同，更长的 index 更新。

Leader 宕机处理：新 Leader 是否提交之前任期内的日志条目

一旦当前任期内的某个日志条目已经存储到过半的服务器节点上，Leader 就知道该日志条目可以被提交了。

如果某个 Leader 在提交某个日志条目之前崩溃了，以后的 Leader 会试图完成该日志条目的复制。复制，而非提交，不能通过心跳提交老日志。

Raft 永远不会通过计算副本数目的方式来提交之前任期内的日志条目。

只有 Leader 当前任期内的日志条目才通过计算副本数目的方式来提交。一旦当前任期的某个日志条目以这种方式提交，那么由于日志匹配特性，之前的所有日志条目也都会被间接地提交。

Follower 和 Candidate 宕机处理

如果 Leader 崩溃，集群中的节点在 electionTimeout 时间内没有收到 Leader 的心跳信息就会触发新一轮的选举，在选举期间整个集群对外是不可用的。

如果 Follower 和 Candidate 崩溃，处理方式会简单很多。之后发送给它的 RequestVote RPC 和 AppendEntries RPC 会失败。由于 Raft 的所有请求都是幂等的，所以失败的话会无限的重试。如果崩溃恢复后，就可以收到新的请求，然后选择追加或者拒绝 entry。

时间与可用性

Raft 的要求之一就是安全性不依赖于时间：系统不能仅仅因为一些事件发生的比预想的快一些或者慢一些就产生错误。

只要整个系统满足下面的时间要求，Raft 就可以选举出并维持一个稳定的 Leader：

broadcastTime << electionTimeout << MTBF

broadcastTime（广播时间）：向其他节点并发发送消息的平均响应时间。
electionTimeout（选举超时时间）：选举超时时间。
MTBF（平均故障时间）：单台机器的平均健康时间。

broadcastTime 应该比 electionTimeout 小一个数量级，为的是使 Leader 能够持续发送心跳信息（heartbeat）来阻止 Follower 开始选举。

electionTimeout 也要比 MTBF 小几个数量级，为的是使得系统稳定运行。当 Leader 崩溃时，大约会在整个 electionTimeout 的时间内不可用；我们希望这种情况仅占全部时间的很小一部分。

由于 broadcastTime 和 MTBF 是由系统决定的属性，因此需要决定 electionTimeout 的时间。一般来说，broadcastTime 一般为 0.5～20ms，electionTimeout 可以设置为 10～500ms，MTBF 一般为几个月甚至更长。

集群成员变更

两阶段方法

在需要改变集群配置的时候（如增删节点、替换宕机的机器或者改变复制的程度），Raft 可以进行配置变更自动化。自动化配置变更机制最大的难点是 保证转换过程中不会出现同一任期的两个 Leader，因为转换期间整个集群可能划分为 两个独立的大多数。（脑裂问题）

图片所示为 3 节点集群（S1、S2、S3）扩容到 5 节点集群（S1、S2、S3、S4、S5）。S1、S2 为老配置集群，S3、S4、S5 为新配置集群。老配置为 3 节点，S1、S2 可以选出一个 Leader，新配置为 5 节点，S3、S4、S5 可以选出一个 Leader。

为了解决这个问题，配置采用了一种 两阶段 的方法。

集群先切换到一个过渡的配置，称为 联合一致。

第一阶段，Leader 发起 $C_{o l d, n e w}$ ，使整个集群进入 联合一致状态。这时，所有 RPC 都要在新旧两个配置中都达到大多数才算成功。
第二阶段，Leader 发起 $C_{n e w}$ ，使整个集群进入 新配置状态。这时，所有 RPC 只要在新配置下能达到大多数就算成功。

和普通日志不同，对于集群成员变更的日志，只要服务器将该配置日志条目增加到自己的日志中，他就会用该配置做出未来所有的决策。这就意味着无论新配置日志条目是否提交，服务器总是会使用它日志中最新的配置。

而 Leader 只要发起了 $C_{o l d, n e w}$ 或 $C_{n e w}$ ，就会直接按照联合一致或者新配置来执行。

宕机处理

我们假设 Leader 可以在集群成员变更的任何时候宕机，大概有以下几种可能：

Leader 在 $C_{o l d, n e w}$ 未提交时宕机
Leader 在 $C_{o l d, n e w}$ 已提交但 $C_{n e w}$ 未发起时宕机
Leader 在 $C_{n e w}$ 已发起时宕机

图片所示为 3 节点集群（S1、S2、S3）扩容到 5 节点集群（S1、S2、S3、S4、S5）。其中 S3 是当前任期的 Leader，这时我们增加 S4、S5 两个节点，Raft 会先将它们设置为只读，等到它们追上日志进度后，才会开始集群成员变成。然后现任 Leader S3 发起 $C_{o l d, n e w}$ 并复制给了 S4、S5，这时的 S3、S4、S5 已经进入了联合一致状态，他们的决策要在新旧两个配置中都达到大多数才算成功。

1. Leader 在 $C_{o l d, n e w}$ 未提交时宕机

S1、S2 超时，开始进行选举，并且可以产生一个老配置的 Leader。但是，在联合一致状态下，S3 必须要在老配置（S1、S2、S3）和新配置（S1、S2、S3、S4、S5）下都拿到超过半数选票才能当选。

所以 S3 无法当选 Leader，集群中只能选出 S1、S2 中的一个 Leader。这样集群成员变更就失败了，但不会出现两个 Leader。

这里还有一种可能，选出的新 Leader 具有 $C_{o l d, n e w}$ ，但按照安全性限制，这个新 Leader 无法提交 $C_{o l d, n e w}$ 。可以让他继续发送 $C_{n e w}$ ，继续进行集群成员变更。

如图，Leader 复制 $C_{o l d, n e w}$ 到新老配置的大多数节点，满足联合一致，但 Leader 在 $C_{o l d, n e w}$ 未提交时宕机，这时 S1 当选 Leader，根据安全性规则，S1 不可以直接提交 $C_{o l d, n e w}$ ，所以 S1 只能继续复制 $C_{n e w}$ ，这时它把 $C_{n e w}$ 复制到了 S1、S4、S5 节点，构成了新配置集群的大多数，但这时能提交 $C_{n e w}$ 吗？

不可以。因为没有 S3 的反馈， $C_{o l d, n e w}$ 的提交规则并没有被满足。这时提交的 $C_{n e w}$ 会把 $C_{o l d, n e w}$ 一并提交，这是不安全的。

在某些设计中，可以强制让 $C_{n e w}$ 按照联合一致规则提交，如果 Leader 满足不了条件会自动退位。

2. Leader 在 $C_{o l d, n e w}$ 已提交但 $C_{n e w}$ 未发起时宕机

在这种情况下，Leader 的 $C_{o l d, n e w}$ 日志在新旧两种配置的集群中超过半数了， $C_{o l d, n e w}$ 就可以被提交了。

如果 Leader 在 $C_{o l d, n e w}$ 已提交但 $C_{n e w}$ 未发起时宕机，选举限制安全性规则决定了选出的新 Leader 一定具有 $C_{o l d, n e w}$ ，也就是符合在两种配置集群中都超过半数，已经不存在出现脑裂问题的可能了。

联合一致状态下，也是可以正常执行命令的，但也需要在两个配置集群中都达到大多数才能提交。

3. Leader 在 $C_{n e w}$ 已发起时宕机

$C_{o l d, n e w}$ 提交后，Leader 就会发起 $C_{n e w}$ ，这时 Leader 只要满足新配置中的条件，就可以提交日志。要 $C_{n e w}$ 发起，意味着 $C_{o l d, n e w}$ 已经被复制到了大多数节点，就不需要再去管老配置。

如果 Leader 在 $C_{n e w}$ 已发起时宕机，已经复制了 $C_{n e w}$ 的节点会 只按新配置选举，没有复制 $C_{n e w}$ 的节点会 按新老配置选举。有没有复制 $C_{n e w}$ 的节点都有可能当上 Leader。没有复制 $C_{n e w}$ 的节点选举成功也会发 $C_{n e w}$ 。

图片所示为 5 节点集群（S1、S2、S3、S4、S5）缩容到 3 节点集群（S1、S2、S3）。这时如果 Leader 宕机了， $C_{n e w}$ 会不会被覆盖？

不会。因为处于联合一致状态的节点，也就是只复制了 $C_{o l d, n e w}$ 没有复制 $C_{n e w}$ 的节点，必须要在两个集群中都得到大多数选票才能选举成功。而 S2、S3 不会投票给 S1、S4、S5 中的一个，所以 S3 宕机只有 S2 才能当选，已提交的 $C_{n e w}$ 不会被覆盖。

总结

在 $C_{o l d, n e w}$ 发起但未提交时，Raft 集群还未进入联合一致状态。这时 Leader 宕机，可以仅靠老配置选出来的新 Leader。

一旦 $C_{o l d, n e w}$ 提交，Raft 集群就进入了联合一致状态，这时 Leader 宕机，选出的新 Leader 也要符合联合一致的选票规则了。

$C_{o l d, n e w}$ 提交后，Leader 就可以发起 $C_{n e w}$ ，从 $C_{n e w}$ 开始，集群就可以仅靠新配置进行选举和日志复制了。

如果是缩减集群的情况下，Leader 可能自身就是缩减的对象，那么它会在 $C_{n e w}$ 复制完成后自动退位。

集群成员变更的三个补充规则

新增节点时，需要等新增的节点完成日志同步再开始集群成员变更。这是为了防止集群在新增节点还未同步日志时就进入联合一致状态或新配置状态，影响正常命令日志提交。
缩减节点时，Leader 本身可能就是要缩减的节点，这时它会在完成 $C_{n e w}$ 的提交后自动退位。在发起 $C_{n e w}$ 后，要退出集群的 Leader 就会处在操纵一个不包含它本身的 Raft 集群的状态下。这时它可以发送 $C_{n e w}$ 日志，但是日志计数时不计自身。
为了避免下线的节点超时选举而影响集群运行，服务器会在它确信集群中有 Leader 存在时拒绝 RequestVote RPC。因为 $C_{n e w}$ 的新 Leader 不会再发送心跳给要退出的节点，如果这些节点没有及时下线，它们会超时增加任期号后发送 RequestVote RPC。虽然它们不可能当选 Leader，但会导致 Raft 集群进入投票选举阶段，影响集群的正常运行。为了解决这个问题，Raft 在 RequestVote RPC 上补充了一个原则：一个节点如果在最小超时时间之内收到了 RequestVote RPC，那么它会拒绝此 RPC。这样，只要 Follower 连续收到 Leader 的心跳，那么退出集群节点的 RequestVote RPC 就不会影响到 Raft 集群的正常运行了。

WARNING

这种集群成员变更的方法一般称为 Joint Consensus 方法或多节点变更方法。这种方法边界情况很多，实现复杂，实际上有点违背 Raft 的设计初衷。所以现在大多数对 Raft 算法的实现都是基于 单节点变更 的方法。单节点变更可以极大简化实现难度。

单节点变更

联合一致（Joint Consensus）集群成员变更方法比较复杂，不太契合 Raft 的易理解性。在 Diego Ongaro 的博士论文和后续的大部分对 Raft 实现中，都使用的是另一种更简单的单节点变更方法，即一次只增减一个节点，称为 单节点集群成员变更方法。

特性

在 Raft 的单节点变更方法中，只增减一个节点时无法选出两个 Leader。

其原因在于新旧配置的“大多数”（majority）必然存在重叠节点，这些重叠节点的投票只能投给一个配置（要么旧配置，要么新配置），从而避免了脑裂（split brain）问题。这样增减一个节点的情况下，就可以不经过联合一致，直接从老配置切换到新配置。

1. 新旧配置的“大多数”必然重叠

假设集群当前有 $N$ 个节点（旧配置），变更为 $N \pm 1$ 个节点（新配置）。无论增减哪一个节点，新旧配置的“大多数”分别为：

旧配置的大多数： $⌈ N / 2 ⌉ + 1$
新配置的大多数： $⌈ (N \pm 1) / 2 ⌉ + 1$

旧配置的大多数和新配置的大多数必须包含至少一个重叠节点（即两者交集非空）。

2. 重叠节点的投票是互斥的

Raft 要求每个节点在同一任期内只能投一次票。因此重叠节点无法同时为旧配置和新配置的候选人投票。如果它投给旧配置的 Leader，则新配置无法获得足够票数；反之亦然。

3. 无法同时满足两个“大多数”

要选出两个 Leader（旧配置和新配置各一个），需要：

旧配置的 Leader 获得旧配置的大多数投票。
新配置的 Leader 获得新配置的大多数投票。

但由于重叠节点的投票互斥，两个“大多数”无法同时满足：

如果重叠节点投给旧配置，新配置无法凑够大多数。
如果重叠节点投给新配置，旧配置无法凑够大多数。

4. 对比：多节点变更的脑裂风险

在联合一致（Joint Consensus）中，若同时增减多个节点，新旧配置的“大多数”可能无重叠，此时可能同时选出两个 Leader（脑裂）。而单节点变更通过强制“大多数”重叠，天然避免了这一问题。

如果需要一次增减多个节点，只需要多次执行单节点变更即可。

步骤

集群要从 3 节点切换到 4 节点：

完成增加节点的日志同步

如何判断增加节点完成了日志同步？

增加节点在追赶日志的同时，Leader 也在不断接收新的日志，所以看起来新增的节点和其他 Follower 一样，永远会落后 Leader 当前的若干日志。可以通过分多轮同步的方法来完成同步。每一轮开始，Leader 记录下当前日志号，然后同步新增节点的日志至此位置。如此重复，在一定的轮数（如 10 轮）后，就可以认为新增节点的日志已经足够新，可以开始集群成员变更了。

当前的 Leader S3 开始产生并发送 $C_{n e w}$ 。和联合一致方法一样，当前的 Leader S3 有 $C_{n e w}$ 的日志后，它就按照新配置来执行了。也就是说 $C_{n e w}$ 只有复制到了三个节点以上才能完成提交。
$C_{n e w}$ 复制到了 S1 和 S4 中，S3 完成了 $C_{n e w}$ 的提交，单节点成员集群变更完成。

在 $C_{n e w}$ 没有复制到大多数节点时 Leader 宕机：

选出的新 Leader 可能是 S4，具有 $C_{n e w}$ ，那么它会继续进行集群成员变更。
选出的新 Leader 也可能是 S1 或 S2，没有 $C_{n e w}$ ，这时集群成员变更失败。

因为 S4 复制了 $C_{n e w}$ ，所以它需要三个节点的选票才能当选，也就是 S1、S2、S3 至少有两者给它投票了。这也是老配置的大多数，所以这里不会产生脑裂现象。

缺陷

联合一致支持一步完成机器的替换，比如我们可以通过联合一致的方法把原来集群的 (a,b,c) 三台机器替换为 (d,b,c) 三台机器。但使用单节点变更就只能由 (a,b,c) 三台机器替换为 (a,b,c,d) 四台机器再替换为 (d,b,c) 三台机器，需要两步。
单节点变更过程必然经历偶数节点的状态，这会降低集群的高可用性。当机器两两分布时，如果发生网络分区，则无法选出 Leader。
- 解决办法：优化单节点变更的过程中偶数节点集群的大多数概念。
- 对于 4 机器集群，老配置中的任意两个节点 (a,b)、(a,c)、(b,c) 也可以算作变更过程中四节点的大多数，可以让 $C_{n e w}$ 提交。
- 因为 (a,b)、(a,c)、(b,c) 是新老配置的最小交集，只要它们都复制了 $C_{n e w}$ ，就可以保证选出的新 Leader 一定是新配置的，所以不会发生脑裂问题。
连续的两次变更，如果第一步变更的过程中如果出现了切主，那么紧跟着的下一次变更可能出现错误。

可能出现的错误

集群准备从 4 节点增加两个节点到 6 节点，分为两次单节点成员变更进行。Leader S3 把 $C_{n e w 1}$ 复制到了 S5（要增加的节点），之后 S3 宕机，重新选举，S1 依靠 S2、S4 的两票当选 Leader，这时认为 $C_{n e w 1}$ 变更失败，新 Leader S1 开始 $C_{n e w 2}$ 的复制， $C_{n e w 2}$ 向集群中增加节点 S6，这时的新 Leader S1 不认为集群中存在 S5，所以 $C_{n e w 2}$ 还是把集群从 4 节点变成 5 节点。所以 S1 把 $C_{n e w 2}$ 复制到了 S1、S2、S6 后，就达到了 5 节点的大多数，可以提交 $C_{n e w 2}$ 了，认为单节点集群成员变更完成。之后 S1 宕机，S3 依靠 S3、S4、S5 的选票重新当选 Leader，这时对于 S3 而言还是 $C_{n e w 1}$ 的配置，认为集群是 S1 到 S5 五个节点，所以只需要三票就可以当选。S3 当选 Leader 后，就会把 $C_{n e w 1}$ 复制到所有的节点，造成已提交的 $C_{n e w 2}$ 被覆盖，S3 根本不知道 S6 的存在，所以 S6 上的 $C_{n e w 2}$ 不会被覆盖。这里已提交的 $C_{n e w 2}$ 被覆盖了。

解决方法

新 Leader 必须提交一条自己任期内的 no-op 日志，才能开始单节点集群成员变更。这样，S1 在当选新 Leader 后，就可以通过 no-op 把未提交的 $C_{n e w 1}$ 覆盖掉，再开始 $C_{n e w 2}$ 的复制，就不会出现上述问题。

日志压缩机制

为什么要进行日志压缩？因为随着 Raft 集群的不断运行，各状态机上的 log 也在不断地积累，总会有一个时间把状态机的内存打爆，所以我们需要一个机制来安全地清理状态机上的 log。

Raft 采用的是一种快照技术，每个节点在达到一定条件之后，可以把当前日志中的命令都写入自己的快照，然后就可以把已经并入快照的日志都删除了。

快照中一个 key 只会留有最新的一份 value，占用空间比日志小很多。

一个 Follower 落后 Leader 很多，如果老的日志被清理了，Leader 怎么同步给 Follower 呢？

Raft 的策略是直接向 Follower 发送自己的快照。

只读操作处理

直观上讲 Raft 的读只要直接读取 Leader 上的结果就行了。但直接从 Leader 的状态机取值实际上并不是线性一致性读（强一致性读）。

线性一致性读（强一致性读）的定义：读到的结果要是读请求发起时已经完成提交的结果（快照）。

在 Leader 和其他节点发生了网络分区的情况下，其他节点可能已经重新选出了一个 Leader，而如果老 Leader 在没有访问其他节点的情况下直接拿自身的值返回客户端，这个读取的结果就有可能不是最新的。

要追求线性一致性读（强一致性读），需要让 这个读的过程或结果，也在大多数节点上达到共识。

稳妥的方法是把读也当作一个 log，由 Leader 发到所有的节点上寻求共识，这个读的 log 提交后，得到的结果一定是符合线性一致性的。可以对这个方法进行优化，并符合以下规则：

线性一致性读一定要发往 Leader。
如果一个 Leader 在它的任期内还没有提交一个日志，那么它要在提交了一个日志后才能反馈 Client 读请求（可以通过 no-op 补丁来优化这一点）。因为只有在自己任期内提交了一个日志，Leader 才能确认之前任期的哪些日志已被提交，才不会出现已提交的数据读取不到的情况。

TIP

安全性规则能保证被选出的 Leader 一定具有所有已被提交的日志，但它有可能有的日志还没有提交，它并不能确定哪些日志是已提交的，哪些日志没提交，而在它任期内提交一个日志，就能确定这一点。

在进行读操作前，Leader 要向所有节点发送心跳，并得到大多数节点的反馈，以确认自己仍是 Leader。
Leader 把自己已提交的日志号设为 readIndex，只要 Leader 应用到了 readIndex 的日志，就可以查询状态机结果并返回 Client 了。

优化过后的线性一致性读，也至少需要一轮 RPC（Leader 确认的心跳），并不比写操作快多少（写操作最少一轮 AppendEntries RPC）。

所以还可以继续优化，因为读的这轮 RPC 仅仅是为了确认集群中没有新 Leader 产生。那么如果 Leader 上一次心跳发送的时间还不到选举超时时间的下界，集群就不能选出一个新 Leader，那么这段时间就可以不经过这轮心跳确认，直接返回读的结果。

如果不要求强一致性读，怎样利用 Follower 承载更大的读压力？（弱一致性读）

Follower 接收到读请求后，向 Leader 请求 readIndex。
Follower 等待自身状态机应用日志到 readIndex。
Follower 查询状态机结果，并返回客户端。

性能

分析 Raft 的性能：最根本的，每完成一个日志（命令）的复制与提交，需要的网络（RPC）来回次数。Raft 在理想情况下，只需要一次 AppendEntries RPC 来回即可提交日志（理论上的极限）。

影响 Raft 性能的因素以及优化方法：

选举及维持 Leader 所需的代价：合理设置选举超时时间。
Batch：一个日志可以包含多个命令，然后批量进行复制，来节省网络。
Pipeline：Leader 不用等待 Follower 的回复，就继续给 Follower 发送下一个日志。
Multi-Raft：将数据分组，每组数据是独立的，用自己的 Raft 来同步。

Raft 与 Paxos 比较

Raft 不允许日志空洞，所以性能没 Paxos 好。

长生命周期的强 Leader，是 Raft 实现起来简单，并区别于其他共识算法最重要的特点。要保证日志只能从 Leader 流向 Follower，Raft 选举出的 Leader 必须具有完整的日志。为了保证时时刻刻都能有具备完整日志的节点可以成为 Leader，Raft 又必须使用 顺序日志复制 的方法来避免日志空洞。

这里的 Paxos 实际上指的是一个 能完美处理所有日志空洞带来的边界情况，并能保证处理这些边界情况的代价要小于允许日志空洞带来的收益的共识算法。

Raft 确实不允许日志空洞这个性能上限，但大部分系统实现连 Raft 的上限都是远远没有达到的，所以无需考虑 Raft 本身的瓶颈。Raft 也有允许日志空洞的实现，比如 ParallelRaft 就是 Raft 允许日志空洞的改造。

Raft 算法 ​

拜占庭将军问题 ​

复制状态机 ​

共识算法 ​

状态简化 ​

节点类型 ​

任期 ​

RPC 通信 ​

日志 ​

领导人选举 ​

日志复制 ​

安全性 ​

Leader 宕机处理：选举限制 ​

Leader 宕机处理：新 Leader 是否提交之前任期内的日志条目 ​

Follower 和 Candidate 宕机处理 ​

时间与可用性 ​

集群成员变更 ​

两阶段方法 ​

宕机处理 ​

总结 ​

单节点变更 ​

特性 ​

步骤 ​

缺陷 ​

日志压缩机制 ​

只读操作处理 ​

性能 ​

Raft 与 Paxos 比较 ​