参考：

In Search of an Understandable Consensus Algorithm(Extended Version)
ongardie/dissertation/stanford.pdf
raft.github.io

Raft 的 Figure 8 讲了什么问题？为什么需要 no-op 日志？
为什么Raft协议不能提交之前任期的日志？
Raft博士论文总结

1 介绍

Raft 是一种为了管理日志复制的一致性算法，旨在实现多节点状态机的高可靠一致性。
相比 Paxos，Raft 将算法分解为领导者选举、日志复制、安全性三大模块，使用随机超时避免选票分裂，并引入共同一致机制实现集群成员动态变更。

Raft 通过选举一个杰出的领导者（也叫 Leader 节点），然后给予他全部的管理日志复制的责任来实现一致性。Leader 节点接收来自客户端的请求日志数据，然后同步到集群中其它节点进行复制，当日志已经同步到超过半数以上节点的时候，Leader 节点再通知集群中其它节点哪些日志已经被复制成功，可以提交到 Raft 状态机中执行。

通过以上方式，Raft 算法将一致性问题分为了几个子问题：

Leader 选举：集群中必须存在一个 Leader 节点。当现存的 Leader 节点发生故障的时候, 一个新的领导者需要被选举出来。
日志复制：Leader 节点接收来自客户端的请求然后将这些请求序列化成日志数据再同步到集群中其它节点，强制要求其他节点的日志和自己保持一致。
安全性：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。这个解决方案涉及到选举机制上的一个额外限制。

2 Raft 基础

一个 Raft 集群包含若干个服务器节点。5 个服务器节点是一个典型的例子，这允许整个系统容忍 2 个节点失效。

角色：
在任何时刻，每一个服务器节点都处于这三个状态之一：领导者（Leader）、跟随者（Follower）和候选人（Candidate）。

跟随者：是被动的，他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。
领导者：处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给领导者）。
候选人：是用来在选举新领导者时使用。

在通常情况下，系统中只有一个领导者并且其他的节点全部都是跟随者。

任期：
Raft 把时间分割成任意长度的任期。任期用连续的整数标记。每一段任期从一次选举开始，每个领导者的领导周期称为一个任期（Term），任期号是单调递增的。
在某些情况下，一次选举过程会造成选票的瓜分。在这种情况下，这一任期会以没有领导者结束；一个新的任期（和一次新的选举）会很快重新开始。Raft 保证了在一个给定的任期内，最多只有一个领导者。

不同的服务器节点可能多次观察到任期之间的转换，但在某些情况下，一个节点也可能观察不到任何一次选举或者整个任期全程。任期在 Raft 算法中充当逻辑时钟的作用，任期使得服务器可以检测一些过期的信息。
比如过期的领导者。每个节点存储一个当前领导者的任期号，这一编号在整个时期内单调递增。每当服务器之间通信的时候都会交换当前任期号；如果一个服务器的当前任期号比其他人小，那么他会更新自己的任期号到较大的任期号值。如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的 RPCs。

请求投票（RequestVote） RPCs 由候选人在选举期间发起；
附加条目（AppendEntries）RPCs 由领导者发起，用来复制日志和提供一种心跳机制。
后面为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时，会进行重试，并且他们能够并行的发起 RPCs 来获得最佳的性能。

一个关于 Raft 一致性算法的浓缩总结（不包括成员变换和日志压缩）
原文：
Election Safety: at most one leader can be elected in a given term. §5.2
Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries. §5.3
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
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
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

总结：

特性	解释
选举安全特性	对于一个给定的任期号，最多只会有一个领导者被选举出来
领导者只附加原则	领导者绝对不会删除或者覆盖自己的日志，只会追加新条目
日志匹配原则	如果两个日志在相同索引位置包含一个具有相同任期号的条目，那么这两个日志在该索引位置之前的所有条目都完全相同
领导者完全特性	如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导者中
状态机安全特性	如果某一服务器已将给定索引位置的日志条目应用至其状态机中，则其他任何服务器在该索引位置不会应用不同的日志条目

2.2 复制状态机

一致性算法是从复制状态机的背景下提出的（参考英文原文引用 37）。在这种方法中，一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如，大规模的系统中通常都有一个集群领导人，像 GFS、HDFS 和 RAMCloud，典型应用就是一个独立的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

图 1

图 1 ：复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的。

复制状态机通常都是基于复制日志实现的，如图 1。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。

一致性算法的任务是保证复制日志的一致性。服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，即使有些服务器发生故障。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成了一个高可靠的状态机。

实际系统中使用的一致性算法通常含有以下特性：

安全性保证（绝对不会返回一个错误的结果）：在非拜占庭错误情况下，包括网络延迟、分区、丢包、重复和乱序等错误都可以保证正确。
可用性：集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用。因此，一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。它们稍后可能会从可靠存储的状态中恢复并重新加入集群。
不依赖时序来保证一致性：物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。
通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

3 Raft 算法核心

3.1 领导者选举

拥有一个领导者大大简化了对复制日志的管理。例如，领导者可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从领导者流向其他服务器。一个领导者可能会发生故障，或者和其他服务器失去连接，在这种情况下一个新的领导者会被选举出来。

系统启动时，所有节点都是跟随者。领导者周期性的向所有跟随者发送心跳包（即不包含日志项内容的附加条目 AppendEntries RPCs）以维持自己的领导地位。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么它就会认为系统中没有可用的领导者，它会转变为候选人，发起新一轮的选举。

要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后他会并行地向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。候选人会继续保持着当前状态直到以下三件事情之一发生：

他自己赢得了这次的选举：
当一个候选人从整个集群获得了超过半数（多数派）节点的针对同一个任期号的选票，那么他就赢得了这次选举并成为领导者。每一个服务器最多会对一个任期号投出一张选票，按照先来先服务的原则（注意：后面 3.3.1 选举限制章节在投票上增加了一点额外的限制）。要求大多数选票的规则确保了最多只会有一个候选人赢得此次选举。一旦候选人赢得选举，他就立即成为领导者。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止发起新的选举。
其他的服务器成为领导者
在等待投票的时候，候选人可能会从其他的服务器接收到声明它是领导者的附加条目 AppendEntries RPC。如果这个领导者的任期号（包含在此次的 RPC 中）不小于候选人当前的任期号，那么候选人会承认领导者合法并回到跟随者状态。如果此次 RPC 中的任期号比自己小，那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态。
一段时间之后没有任何一个获胜的人。
第三种可能的结果是候选人既没有赢得选举也没有输：如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。当这种情况发生的时候，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举。然而，没有其他机制的话，选票可能会被无限的重复瓜分。

利用随机选举超时机制避免重复选票瓜分：
Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。为了阻止选票起初就被瓜分，选举超时时间是从一个固定的区间（例如 150-300 毫秒）随机选择。
在大多数情况下，只有一个服务器会首先触发选举超时，然后他赢得选举并在其他服务器超时之前发送心跳包。
同样的机制被用在选票瓜分的情况下。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。这种方案能够快速的选出一个领导者。

3.2 日志复制

一旦一个领导者被选举出来，他就开始为客户端提供服务。客户端的每一个请求都包含一条被复制状态机执行的指令。领导者把这条指令作为一条新的日志条目附加到日志中去，然后并行地发起附加条目 RPCs 给其他的服务器，让他们复制这条日志条目。当领导者得知某个日志条目已经被大多数节点复制时，领导者会应用这条日志条目到它的状态机中然后把执行的结果返回给客户端。如果跟随者崩溃或者运行缓慢，再或者网络丢包，领导者会不断的重复尝试附加日志条目 RPCs （尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目。

图 6

图 6：日志由有序序号标记的条目组成。每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令。一个条目当可以安全地被应用到状态机中去的时候，就认为是可以提交了。

日志以上图展示的方式组织。每一个日志条目存储一条状态机指令和从领导者收到这条指令时的任期号。日志中的任期号用来检查是否出现不一致的情况，同时也用来保证 2 Raft 基础章节中的某些性质。每一条日志条目同时也都有一个整数索引值来表明它在日志中的位置。

领导者来决定什么时候把日志条目应用到状态机中是安全的，这种日志条目被称为已提交。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行：

在领导者将创建的日志条目复制到超过半数节点上的时候，日志条目就会被提交（例如在上图中共 5 个节点，3 个节点已经拥有日志条目 7）。
同时，领导者的日志中之前的所有日志条目也都会被提交，包括由其他领导者创建的条目。3.3 安全性章节会讨论某些当在领导者改变之后应用这条规则的隐晦内容，同时他也展示了这种提交的定义是安全的。

领导者跟踪了最大的将会被提交的日志项的索引，并且索引值会被包含在未来的所有附加日志 RPCs （包括心跳包），这样其他的服务器才能最终知道领导者的提交位置。一旦跟随者知道一条日志条目已经被提交，那么他也会将这个日志条目应用到本地的状态机中（按照日志的顺序）。

我们设计了 Raft 的日志机制来维护不同服务器日志之间的高层次的一致性。这么做不仅简化了系统的行为也使其更具有可预测性，同时它也是安全性保证的一个重要组件。Raft 维护着以下的特性，这些特性共同组成了 2 Raft 基础中说的日志匹配特性（Log Matching Property）：

如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

第一个特性来自这样的一个事实，领导者最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。
第二个特性由附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候，领导者会把新的日志条目前紧挨着的条目的索引位置和任期号包含在日志内。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。
一致性检查就像一个归纳步骤：一开始空的日志状态肯定是满足日志匹配特性的，然后一致性检查在日志扩展的时候保护了日志匹配特性。因此，每当附加日志 RPC 返回成功时，领导者就知道跟随者的日志一定是和自己相同的了。

在正常的操作中，领导者和跟随者的日志保持一致性，所以附加日志 RPC 的一致性检查从来不会失败。然而，领导者崩溃的情况会使得日志处于不一致的状态（老的领导者可能还没有完全复制所有的日志条目）。这种不一致问题会在领导者和跟随者的一系列崩溃下加剧。图 7 展示了跟随者的日志可能和新的领导者不同。跟随者可能会丢失一些在新的领导者中存在的日志条目，他也可能拥有一些领导者没有的日志条目，或者两者都发生。丢失或者多出日志条目可能会持续多个任期。

图 7

图 7：当一个领导者成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。
例如，场景 f 可能会这样发生，该服务器在任期 2 的时候是领导者，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导者，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

在 Raft 算法中，领导者是通过强制跟随者直接复制自己的日志来处理不一致问题的。这意味着在跟随者中的冲突的日志条目会被领导者的日志覆盖。3.3 安全性章节会阐述如何通过增加一些限制来使得这样的操作是安全的。

要使得跟随者的日志进入和自己一致的状态，领导者必须找到最后两者达成一致的地方，然后删除跟随者从那个点之后的所有日志条目，并发送自己在那个点之后的日志给跟随者。所有的这些操作都在进行附加日志 RPCs 的一致性检查时完成。领导者针对每一个跟随者维护了一个 nextIndex，这表示下一个需要发送给跟随者的日志条目的索引地址。当一个领导者刚获得权力的时候，他初始化所有的 nextIndex 值为自己的最后一条日志的 index 加 1（图 7 中的第 11 索引）。如果一个跟随者的日志和领导者不一致，那么在下一次的附加日志 RPC 时的一致性检查就会失败。在被跟随者拒绝之后，领导者就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得领导者和跟随者的日志达成一致。当这种情况发生，附加日志 RPC 就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上领导者的日志。一旦附加日志 RPC 成功，那么跟随者的日志就会和领导者保持一致，并且在接下来的任期里一直继续保持。

如果需要的话，算法可以通过减少被拒绝的附加日志 RPCs 的次数来优化。例如，当附加日志 RPC 的请求被拒绝的时候，跟随者可以 (返回) 冲突条目的任期号和该任期号对应的最小索引地址。借助这些信息，领导者可以减小 nextIndex 一次性越过该冲突任期的所有日志条目；这样就变成每个任期需要一次附加条目 RPC 而不是每个条目一次。在实践中，我们十分怀疑这种优化是否是必要的，因为失败是很少发生的并且也不大可能会有这么多不一致的日志。

通过这种机制，领导者在获得权力的时候就不需要任何特殊的操作来恢复一致性。他只需要进行正常的操作，然后日志就能在回复附加日志 RPC 的一致性检查失败的时候自动趋于一致。领导者从来不会覆盖或者删除自己的日志 (2 Raft 基础中说过的领导者只附加特性）。

日志复制机制展示一致性特性：Raft 能够接受，复制并应用新的日志条目只要大部分的机器是工作的；在通常的情况下，新的日志条目可以在一次 RPC 中被复制给集群中的大多数机器；并且单个的缓慢的跟随者不会影响整体的性能。

3.3 安全性

前面的章节里描述了 Raft 算法是如何选举和复制日志的。然而，到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。例如，一个跟随者可能会进入不可用状态同时领导者已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导者并且覆盖这些日志条目（坏的节点好了，但此时如果他成为了领导者，那些理应被安全提交到状态机的日志条目，这个节点是没有的，然后会试图找到他们最后一个相同提交条目的索引，删除跟随者后面的提交条目，这违反了前面说的状态机日志索引一致性特性）；因此，这种设计会导致不同的状态机可能会执行不同的指令序列。

这一节通过在领导选举的时候增加一些限制来完善 Raft 算法。这一限制保证了任何的领导者对于给定的任期号，都拥有了之前任期的所有被提交的日志条目（ 2 Raft 基础中的领导者完整特性）。增加这一选举时的限制，我们对于提交时的规则也更加清晰。最终，我们将展示对于领导者完整特性（Leader Completeness Property） 的简要证明，并且说明该特性是如何引导复制状态机做出正确行为的。

3.3.1 选举限制

在任何基于领导者的一致性算法中，领导者都必须存储所有已经提交的日志条目。在某些一致性算法中，例如 Viewstamped Replication，某个节点即使是一开始并没有包含所有已经提交的日志条目，它也能被选为领导者。这些算法都包含一些额外的机制来识别丢失的日志条目并把他们传送给新的领导者，要么是在选举阶段要么在之后很快进行。不幸的是，这种方法会导致相当大的额外的机制和复杂性。Raft 使用了一种更加简单的方法，它可以保证在选举的时候新的领导者拥有所有之前任期中已经提交的日志条目，而不需要传送这些日志条目给领导者。这意味着日志条目的传送是单向的，只从领导者传给跟随者，并且领导者从不会覆盖自身本地日志中已经存在的条目。

Raft 使用投票的方式来阻止一个候选人赢得选举，除非这个候选人包含了所有已经提交的日志条目。候选人为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果候选人的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么他一定持有了所有已经提交的日志条目。请求投票（RequestVote） RPC 实现了这样的限制：RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新，且按优先级执行，先比 lastLogTerm，再比 lastLogIndex（任期相同情况下）：

如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。（优先级最高）
如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

注：日志新鲜度判定依据的是“节点本地日志中最后一条日志条目（无论是否已提交）的索引 + 任期”

3.3.2 提交之前任期内的日志条目

如同 3.2 日志复制章节介绍的那样，领导者知道一条当前任期内的日志记录是可以被提交的，只要它被存储到了大多数的服务器上。如果一个领导者在提交日志条目之前崩溃了，未来后续的领导者会继续尝试复制这条日志记录。然而，一个领导者不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交了。所以提交老任期日志存在一个致命漏洞 —— 一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的领导者覆盖掉，图 3.7 就是这个漏洞的典型场景：

图 3.7

图 3.7：如图的时间序列展示了领导者无法决定对老任期号的日志条目进行提交的原因，否则存在安全问题。

在 (a) 中，S1 是领导人，只有少部分的 (跟随者) 复制了索引位置 2 的日志条目。

在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。

然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。此时会产生两个分支：

在允许提交之前任期的日志规则下，如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。

在不允许提交之前任期的日志规则下，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为 S5 就不可能选举成功）。这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。

再次强调，这里图示想演示的是 “如果允许提交之前任期的日志，将导致什么问题”。

为了消除图 3.7 里描述的情况，Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有领导人当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，领导人可以安全的知道一个老的日志条目是否已经被提交（例如，该条目是否存储到所有服务器上），但是 Raft 为了简化问题使用一种更加保守的方法。

当领导人复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号, 这在提交规则上产生了额外的复杂性。在其他的一致性算法中，如果一个新的领导人要重新复制之前的任期里的日志时，它必须使用当前新的任期号。Raft 使用的方法更加容易辨别出日志，因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外，和其他的算法相比，Raft 中的新领导人只需要发送更少日志条目（其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号）。但是，这在实践中可能并不十分重要，因为领导者更换很少发生。

举例：
如一个节点有之前任期的条目 2 和当前自己任期创建的条目 4 均未提交，那么他会向其他节点复制条目 2 和 4，但是条目 2 永远不能通过被超过半数节点复制来提交，只有当前任期的条目 4 才使用被超过半数节点复制则提交的方案。条目 2 的提交时机在于条目 4 的提交时机，一旦条目 4 被提交，条目 2 也会被间接提交。若条目 4 没被提交，就算所有节点都存在条目 2 ，条目 2 也不会提交。

3.3.3 安全性论证

在给定了完整的 Raft 算法之后，我们现在可以更加精确的讨论领导者完整性特性（这一讨论基于 9.2 节的安全性证明）。我们假设领导者完全性特性是不存在的，然后我们推出矛盾来。假设任期 T 的领导者（领导者 T）在任期内提交了一条日志条目，但是这条日志条目没有被存储到未来某个任期的领导者的日志中。设大于 T 的最小任期 U 的领导者 U 没有这条日志条目。

图 9

图 9：如果 S1 （任期 T 的领导者）在它的任期里提交了一条新的日志，然后 S5 在之后的任期 U 里被选举为领导者，那么至少会有一个机器，如 S3，既拥有来自 S1 的日志，也给 S5 投票了。

在领导者 U 选举的时候一定没有那条被提交的日志条目（领导者从不会删除或者覆盖任何条目）。
领导者 T 复制这条日志条目给集群中的大多数节点，同时，领导者 U 从集群中的大多数节点赢得了选票。因此，至少有一个节点（投票者、选民）同时接受了来自领导者 T 的日志条目，并且给领导者 U 投票了，如图 9。这个投票者是产生这个矛盾的关键。
这个投票者必须在给领导者 U 投票之前先接受了从领导者 T 发来的已经被提交的日志条目；否则他就会拒绝来自领导者 T 的附加日志请求（因为此时他的任期号会比 T 大）。
投票者在给领导者 U 投票时依然保存有这条日志条目，因为任何中间的领导者都包含该日志条目（根据上述的假设），领导者从不会删除条目，并且跟随者只有在和领导者冲突的时候才会删除条目。
投票者把自己选票投给领导者 U 时，领导者 U 的日志必须和投票者自己一样新。这就导致了两者矛盾之一。
首先，如果投票者和领导者 U 的最后一条日志的任期号相同，那么领导者 U 的日志至少和投票者一样长，所以领导者 U 的日志一定包含所有投票者的日志。这是另一处矛盾，因为投票者包含了那条已经被提交的日志条目，但是在上述的假设里，领导者 U 是不包含的。
除此之外，领导者 U 的最后一条日志的任期号就必须比投票人大了。此外，他也比 T 大，因为投票人的最后一条日志的任期号至少和 T 一样大（他包含了来自任期 T 的已提交的日志）。创建了领导者 U 最后一条日志的之前领导者一定已经包含了那条被提交的日志（根据上述假设，领导者 U 是第一个不包含该日志条目的领导者）。所以，根据日志匹配特性，领导者 U 一定也包含那条被提交的日志，这里产生矛盾。
这里完成了矛盾。因此，所有比 T 大的领导者一定包含了所有来自 T 的已经被提交的日志。
日志匹配原则保证了未来的领导者也同时会包含被间接提交的条目，例如图 8 (e) 中的索引 2。

通过领导者完全特性，我们就能证明图 3 中的状态机安全特性，即如果服务器已经在某个给定的索引值应用了日志条目到自己的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上。在一个服务器应用一条日志条目到他自己的状态机中时，他的日志必须和领导者的日志，在该条目和之前的条目上相同，并且已经被提交。现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期；日志完全特性保证拥有更高任期号的领导者会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此，状态机安全特性是成立的。

最后，Raft 要求服务器按照日志中索引位置顺序应用日志条目。和状态机安全特性结合起来看，这就意味着所有的服务器会应用相同的日志序列集到自己的状态机中，并且是按照相同的顺序。

3.4 跟随者和候选人崩溃

到目前为止，我们都只关注了领导人崩溃的情况。跟随者和候选人崩溃后的处理方式比领导人要简单的多，并且他们的处理方式是相同的。如果跟随者或者候选人崩溃了，那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单地通过无限的重试；如果崩溃的机器重启了，那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC，但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的，所以这样重试不会造成任何问题。例如一个跟随者如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求。

3.5 持久化状态与节点重启

Raft 节点必须将足够的信息持久化至稳定存储，以实现节点重启后的安全恢复。其中，每个节点都需持久化自身的当前任期与投票记录；这一步是必要的，可防止节点在同一任期内重复投票，或用已被废黜领导者的日志条目覆盖新任领导者的日志条目。每个节点还需在日志条目被纳入提交统计前，完成新日志条目的持久化；这能避免节点重启时，已提交的日志条目丢失或被撤销提交。

其他状态变量在节点重启时丢失并无安全风险，因为这类变量均可重新生成。最具代表性的例子是 commitIndex —— 节点重启时，可将其安全地重新初始化为 0。即便集群中所有节点同时重启，commitIndex 也只会暂时滞后于其实际值。一旦领导者选举产生并能提交新的日志条目，其 commitIndex 便会向前推进，并迅速将该 commitIndex 同步至所有跟随者节点。

状态机可分为易失性和持久化两种类型。易失性状态机在节点重启后，必须通过重新应用日志条目完成恢复（需先应用最新的快照，详见第 5 章）。而持久化状态机在重启后，多数日志条目其实已完成应用；为避免重复应用这些条目，节点必须同时持久化自身的最后应用索引。

若节点丢失任意持久化状态，便无法以原有身份安全重新加入集群。此类节点通常可通过发起集群成员变更操作，以新身份重新加入集群（详见 4 集群成员变化）。但如果集群中多数派节点均丢失了持久化状态，日志条目可能发生丢失，且集群成员变更操作也将无法推进；若要继续运行集群，系统管理员需接受数据丢失的可能性。

3.6 时间和可用性

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。例如，如果消息交换比服务器故障间隔时间长，候选人将没有足够长的时间来赢得选举；没有一个稳定的领导人，Raft 将无法工作。

领导人选举是 Raft 中对时间要求最为关键的方面。Raft 可以选举并维持一个稳定的领导人,只要系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

在这个不等式中，广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间；选举超时时间就是在 3.1 领导者选举中介绍的选举的超时时间限制；然后平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能。选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现。

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

3.7 领导者移交扩展

本节介绍 Raft 的一项可选扩展机制，支持将集群中某一节点的领导权移交至另一节点。该领导者移交机制主要适用于两类场景：

领导者需主动退位的情况。例如，节点可能因维护需要重启，或即将被移出集群（详见 4 集群成员变化）。若领导者直接退位，集群会在一个选举超时时间内处于空闲状态，直至其他节点因选举超时发起选举并胜出。而如果领导者在退位前将领导权主动移交至其他节点，便可避免这一短暂的不可用状态。
部分节点比其他节点更适合担任领导者的情况。例如，高负载的节点并非领导者的合适人选；在广域网部署架构中，为最小化客户端与领导者之间的网络延迟，通常更倾向于由主数据中心内的节点担任领导者。其他共识算法或许能在领导者选举阶段直接适配这类偏好，但 Raft 要求领导者必须是日志足够新的节点，而这类节点未必是最优选择。对此，Raft 中的现任领导者可定期检查可用的跟随者节点，判断是否存在更适合担任领导者的节点；若存在，则将领导权移交至该节点。（倘若人类中的领导者也能如此从容让位就好了。）

在 Raft 中执行领导者移交时，前任领导者会先将自身的日志条目同步至目标节点，随后让目标节点无需等待选举超时时间结束，直接发起选举。通过这一方式，前任领导者能确保目标节点在其任期开始时，已拥有集群中所有的已提交日志条目；同时，与正常选举流程一致，多数派投票机制会保障 Raft 各项安全属性（如领导者完备性原则）始终得以维持。以下是该移交过程的详细执行步骤：

前任领导者停止接收新的客户端请求；
当前领导者完整更新目标服务器的日志以使其与自己的日志匹配，使用前文描述的 3.2 日志复制。
前任领导者向目标节点发送 TimeoutNow 请求，该请求的效果等同于目标节点的选举计时器触发：目标节点立即启动一次新的选举（增加自身任期号并成为候选节点）。

目标节点接收到 TimeoutNow 请求后，大概率会先于集群中其他节点发起选举，并在新一任期内当选领导者。其向现任领导者发送的第一条消息会包含新的任期号，这一信息会触发前任领导者正式退位，至此领导者移交操作完成。

该机制也需考虑异常场景：若目标节点发生故障，集群必须恢复正常的客户端业务处理。如果在约一个选举超时时间后，领导者移交仍未完成，前任领导者会终止此次移交操作，并恢复接收客户端请求。即便前任领导者判断失误、目标节点实际处于可用状态，该失误造成的最坏结果也只是触发一次额外的选举，选举结束后集群的客户端业务处理便会恢复正常。

这一移交方案完全遵循 Raft 集群的正常状态转换规则，因此能保障共识安全性。例如，Raft 本身已保证，即便节点时钟以任意速度运行，集群的安全性也不会受影响；而目标节点接收 TimeoutNow 请求，其效果等同于该节点的时钟快速向前跳变，这一情况在 Raft 的安全设计范围内。不过，目前我们尚未对该领导者移交方案开展工程实现与效果评估。

4 集群成员变化

到目前为止，我们始终假设集群配置（即参与共识算法的服务器节点集合）是固定不变的。但在实际应用中，我们偶尔需要对配置进行变更 —— 例如替换故障节点，或是调整副本的复制规模。这项操作可通过手动方式完成，具体有两种实现思路：

先将整个集群下线，完成配置文件的更新后再重启集群，以此实现配置变更。但这种方式会导致集群在配置变更过程中完全不可用。
让新节点接管某一集群成员的网络地址，以此完成节点替换。但这种方式要求管理员必须确保被替换的节点永不重新上线，否则系统的安全性属性将遭到破坏（例如，集群中会出现额外的投票权，引发投票异常）。

上述两种集群成员变更的方式均存在明显弊端，且只要涉及手动操作步骤，就必然存在人为操作失误的风险。

为规避这些问题，我们决定将配置变更流程自动化，并将其整合至 Raft 共识算法中。基于 Raft 的集群成员变更机制，集群在配置变更期间仍能保持正常运行，且该机制仅需对基础共识算法做少量扩展即可实现。图 4.1 总结了用于执行集群成员变更的远程过程调用（RPC）相关接口，其具体设计细节将在本章后续内容中展开说明。

图 4.1 用于执行集群成员变更的远程过程调用（RPC）
添加节点远程过程调用（AddServer RPC）用于将新节点添加至当前集群配置，移除节点远程过程调用（RemoveServer RPC）用于将某一节点从当前集群配置中移除。§4.1 这类章节编号，标识了各特性的具体论述位置；4.4 节则阐述了在完整的系统中，如何使用这些远程过程调用的具体方法。

4.1 安全性

保障安全性是集群配置变更面临的首要挑战。要让该配置变更机制具备安全性，就必须保证在配置变更的过渡阶段，绝对不会出现同一任期内选举出两位领导者的情况。若一次配置变更操作添加或移除多个节点，直接将集群从旧配置切换至新配置的方式存在安全风险：我们无法让所有节点同时完成原子性的配置切换，因此集群在过渡阶段有可能分裂为两个相互独立的多数派（见图 4.2）。

图 10

图 10：直接从一种配置转到新的配置是十分不安全的，因为各个机器可能在任何的时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。

大多数成员更改算法都引入了其他机制来处理这种问题。这是我们最初为 Raft 所做的，但后来我们发现了一个更简单的方法，即禁止会导致多数成员不相交的成员更改。因此，Raft 限制了允许的更改类型：一次只能从集群中添加或删除一个服务器。成员更改中更复杂的更改是通过一系列单服务器更改实现的。本章的大部分内容描述了单服务器方法，它比我们原来的方法更容易理解。为了完整起见，第 4.3 节描述了原始的方法，它增加了处理任意配置更改的复杂性。在发现更简单的单服务器更改方法之前，我们在 LogCabin 中实现了更复杂的方法；在撰写本文时，它仍然使用更复杂的方法。

当仅向集群添加/移除一个节点时，旧集群的任意多数派与新集群的任意多数派之间必然存在重叠（见图 4.3）。这种重叠特性可防止集群分裂为两个相互独立的多数派；在 3.3.3 安全性论证中，这一特性保证了「投票者（the voter）」的存在。因此，仅增删单个节点时，直接切换至新配置的操作具备安全性。Raft 正是利用这一特性，仅通过少量额外机制就实现了集群成员的安全变更。

图 4.3：从偶数和奇数大小的集群中添加和删除单个服务器。
在每个图中，蓝色矩形显示旧集群的大部分，红色矩形显示新集群的大部分。在每个单服务器成员更改中，旧集群的任意多数派与新集群的任意多数派之间的重叠性均能得到保持，这用来保证安全性。例如在子图 (b) 中，旧集群的多数派需包含左侧 3 个节点中的至少 2 个；新集群的多数派需包含新集群全部节点中的至少 3 个，且这 3 个节点里至少有 2 个必须来自旧集群。

集群配置信息通过复制日志中的专用日志条目进行存储和传播。这一设计借助 Raft 已有的机制来实现配置信息的复制与持久化；同时，通过为配置变更和客户端请求设定执行顺序（允许两者在管道或批处理被并发复制），集群在配置变更过程中仍可持续响应客户端请求。

当领导者收到从当前配置（C_old）中增删节点的请求时，它将新配置（C_new）作为一条日志条目追加到自身日志中，并通过 Raft 的常规机制复制该条目。
每个节点一旦将新配置条目添加到自身的日志中，新配置便立即在该节点生效：C_new 条目会被复制到新配置包含的所有节点，且系统会以新配置下的多数派节点为依据，判定该 C_new 条目是否提交。这意味着节点无需等待配置条目完成提交，而是始终使用自身日志中最新的配置。

当 C_new 条目完成提交时，本次配置变更即宣告完成。此时领导者能够确认：新配置 C_new 已被多数派的新配置节点采纳；同时也能确定，所有未切换至 C_new 的节点已无法构成集群的多数派，且未采纳 C_new 的节点也无法被选举为领导者。C_new 的提交使得以下三类操作可以正常执行：

领导者可向请求方确认配置变更已成功完成；
若本次配置变更涉及节点移除，则被移除的节点可被下线；
可启动后续的配置变更操作。在此之前，若叠加执行配置变更，可能会导致集群陷入图 4.2 所示的不安全状态。

如前文所述，无论配置条目是否已提交，节点始终使用自身日志中最新的配置。这一设计让领导者可轻松避免配置变更的叠加执行（即上述第三点）—— 只需在前置变更的日志条目提交前，不启动新的变更操作即可。只有当旧配置下的多数派节点均已按 C_new 的规则运行时，启动新的成员变更操作才是安全的。若节点仅在确认 C_new 已提交后才采纳该配置，Raft 领导者将难以判断旧配置下的多数派节点是否已完成配置切换：领导者需要追踪哪些节点知晓该条目已提交，且节点需将自身的提交索引持久化至磁盘 —— 而这两种机制均非 Raft 的必需设计。相反，每个节点在 C_new 条目写入自身日志后立即采纳该配置，且领导者只需确认 C_new 条目已提交，即可判定启动后续配置变更操作是安全的。但需注意，这一设计也意味着：配置变更的日志条目可能被移除（例如领导者发生变更时）；在此情况下，节点必须能够回退到自身日志中前一版的配置。

在 Raft 中，达成共识的过程（包括投票和日志复制）均遵循请求发起方的配置规则，具体规则如下：

节点会接受来自「非自身最新配置成员」的领导者的 AppendEntries 请求。否则，新节点将永远无法被加入集群（因为它不会接受任何「添加该节点的配置条目」之前的日志条目）；
节点也会将选票投给「非自身最新配置成员」的候选人（前提是该候选人的日志足够新，且任期号为当前有效任期）。这类投票有时是保障集群可用性的必要操作。例如：向一个 3 节点集群中添加第 4 个节点后，若其中一个原有节点故障，就需要新节点的投票才能形成多数派、选举出领导者。

因此，节点处理入站 RPC 请求时，无需查阅自身当前的配置。

4.2 可用性

集群成员变更会引发多项影响集群可用性保障的问题。4.2.1 节阐述了新节点加入集群前的日志追平机制，避免其阻塞新日志条目的提交流程；4.2.2 节说明若现任领导者被移出集群，应如何对其完成逐步下线操作；4.2.3 节则介绍了如何防止已被移除的节点干扰新集群的领导者。最后，4.2.4 节阐明了为何这一设计成型的成员变更算法，足以在任意集群成员变更过程中保障集群的可用性。

4.2.1 新节点的日志追平

当新节点被加入集群时，其通常未存储任何日志条目。若节点以该状态加入集群，其日志可能需要较长时间才能追平领导者的日志，而在此期间，集群会更容易陷入不可用状态。例如，一个三节点集群在正常情况下可容忍单节点故障且不损失可用性；但如果为该集群新增一个空日志的第四节点，且原有三个节点中有一个发生故障，集群将暂时无法提交新的日志条目（见图 4.4（a））。若短时间内向集群批量新增多个节点，且这些新节点需参与集群多数派共识，也会引发可用性问题（见图 4.4（b））。上述两种情况中，除非新节点的日志追平领导者的日志，否则集群将一直处于不可用状态。

图 4.4 新增空日志节点危及集群可用性的示例
本图展示了两个不同集群中的节点日志状态。每个集群初始均包含 3 个节点，即 S1 至 S3。
场景（a）中，新增节点 S4 后，节点 S3 发生故障。集群本应在单节点故障后保持正常运行，却因此丧失了可用性：此时提交新日志条目需要 4 个节点中的 3 个参与共识，但 S3 已发生故障，且 S4 的日志落后过多，无法追加新日志条目。
场景（b）中，节点 S4、S5、S6 被接连新增至集群。提交新增 S6（第三个新节点）的配置日志条目时，需要 4 个节点的日志均完成该条目的存储，而 S4 至 S6 的日志均大幅落后于集群最新状态。
除非新节点完成日志追平，否则上述两个集群均无法恢复可用状态。

为避免出现可用性空档，Raft 在配置变更前新增了一个阶段：新节点以非投票节点的身份加入集群。领导者会向其复制日志条目，但在投票和日志提交的多数派计算中，该节点暂不被纳入统计。待新节点的日志追平集群其他节点后，配置变更即可按前述流程执行。（这套支持非投票节点的机制在其他场景中同样适用，例如可通过该机制将集群状态复制至大量节点，由这些节点处理一致性要求较低的只读请求。）

领导者需要判断新节点的日志何时达到足够同步的状态，才能继续执行配置变更。这一判断过程需谨慎处理以保障可用性：若过早将新节点纳入投票节点，集群的可用性仍会面临前述的风险。我们的设计目标是，让任何临时性的不可用时长都不超过选举超时时间 —— 因为客户端本就需要能够容忍这种时长的偶发不可用（如领导者故障时的情况）。此外，在条件允许的情况下，我们会尽可能让新节点的日志更贴近领导者的日志，进一步缩短不可用的时间。

若新节点处于不可用状态，或同步速度过慢、始终无法完成日志追平，领导者应终止此次配置变更。这一检查步骤至关重要：Lamport 所设想的早期 Paxon（早期 Paxos）共识机制之所以会失效，正是因为缺少了该步骤 —— 其集群成员被意外修改为全部是已遇难的船员，导致集群彻底无法推进任何操作。尝试加入不可用或同步缓慢的节点，往往是操作失误所致。事实上，我们在首次测试配置变更请求时，曾因网络端口号的拼写错误导致新节点无法连接，而系统也正确终止了此次变更并返回了错误信息。

我们提出以下算法，用于判断新节点的日志是否达到足够同步的状态、可被正式加入集群：领导者向新节点的日志条目复制过程分轮次进行（见图 4.5）。每一轮的操作，是将领导者在本轮开始时日志中存在的所有条目，全部复制至新节点的日志。在复制当前轮次条目期间，领导者可能会接收到新的日志条目，这些条目将在后续轮次中完成复制。随着同步的推进，每一轮次的耗时会逐步缩短。该算法会等待固定的轮次数（如 10 轮），若最后一轮的耗时小于一个选举超时时间，则领导者可将新节点正式加入集群 —— 此时可认为未完成复制的日志条目数量极少，不会造成显著的可用性空档。反之，领导者则终止此次配置变更并返回错误，调用方可重新发起请求（由于新节点的日志已完成部分同步，后续请求的成功率会更高）。

图 4.5 新节点日志追平的轮次复制机制
为实现新节点的日志追平，领导者向新节点的日志条目复制过程采用分轮次执行的方式。当新节点同步完领导者在本轮开始时日志中的所有条目后，本轮复制即完成；但在此期间，领导者可能已接收到新的日志条目，这类条目将在下一轮次中完成复制。

新节点日志追平的第一步，是领导者发现新节点的日志为空。对于全新节点，AppendEntries（追加日志）RPC 的一致性检查会反复失败，直到领导者为该节点维护的 nextIndex（下一个日志索引）最终降至 1。这一反复交互的过程，可能成为新节点加入集群时的主要性能瓶颈（完成该阶段后，可通过批量传输的方式，以更少的 RPC 请求向跟随者同步日志条目）。可通过多种方式让 nextIndex 更快收敛至正确值，包括第 3 章中提及的方法。而针对新节点加入这一特定场景，最简单的解决方案是：让跟随者在 AppendEntries 的响应中返回自身的日志长度，领导者即可据此为跟随者的 nextIndex 设置上限。

4.2.2 移除现任领导者

若要求现任领导者将自身从集群中移除，其必须在某个时间点退位。一种直接的解决方案是使用 3.7 领导者移交扩展扩展机制：接收到自移除指令的领导者，会将领导权移交至其他节点，再由新的领导者正常执行集群成员变更操作。

我们最初为 Raft 设计了另一种方案：由现任领导者自行执行移除自身的成员变更操作，完成后再退位。该方案会让 Raft 进入一种稍显特殊的运行模式 —— 领导者会临时管理一个自身并非成员的集群配置。我们最初在设计任意配置变更（见 4.4 基于联合共识的任意配置变更）时必须采用该方案，因为旧配置和新配置可能不存在任何公共节点，导致领导权无法完成移交。对于未实现领导者移交机制的系统，该方案同样适用。

在该方案中，被移出配置的领导者会在新配置条目（Cnew） 提交后正式退位。若领导者在 Cnew 提交前退位，其仍可能因选举超时重新当选领导者，进而导致集群进度停滞。在双节点集群中移除领导者的极端场景下，该节点甚至可能需要重新当选领导者，集群才能继续推进操作（见图 4.6）。因此，领导者会等待 Cnew 提交后再退位 —— 这是新配置无需被移除领导者参与、即可独立正常运行的首个时间节点：此时新配置（Cnew）的成员必然能在内部选举出一位新的领导者。被移除的领导者退位后，Cnew 中的某个节点会因选举超时发起选举并胜出。这一短暂的可用性空档是可容忍的，因为领导者故障时也会出现类似的情况。

图 4.6 新配置条目提交前，被移除的节点仍需担任领导者以推进集群操作
本图展示了双节点集群中移除节点 S1 的场景。S1 为集群当前的领导者，此时暂不应退位 —— 集群仍需要由其担任领导者。S2 在从 S1 处接收新配置条目（Cnew）前，无法当选为新领导者（原因在于：S2 仍需获得 S1 的选票，才能构成旧配置（Cold）的多数派；而 S1 会因 S2 的日志未同步至最新状态，拒绝为其投出选票）。

该方案会带来两个关于集群决策的推论，这些推论并无明显弊端，但可能与直觉不符：第一，在 Cnew 的提交阶段，领导者会在一段时间内管理一个自身并非成员的集群 —— 其仍会向集群复制日志条目，但在多数派计算中不再将自身纳入统计；第二，若某个节点并非自身最新配置的成员，其仍应发起新的选举，因为在 Cnew 提交前，集群可能仍需要该节点发挥作用（见图 4.6）。除非该节点属于自身的最新配置，否则其在选举中不会将自身的选票纳入统计。

4.2.3 干扰性节点

若缺少额外的机制，未被纳入新配置（Cnew）的节点会干扰集群的正常运行。一旦集群领导者生成 Cnew 条目，未被纳入 Cnew 的节点将不再收到心跳包，进而因选举超时发起新的选举。此外，这些节点无法接收 Cnew 条目，也无法感知该条目的提交，因此始终不会知晓自身已被移出集群。它们会携带更大的任期号发送 RequestVote（请求投票）RPC，这会导致当前的领导者退化为跟随者状态。尽管 Cnew 中的节点最终会选举出新的领导者，但这些干扰性节点会再次因选举超时发起选举，上述过程将不断重复，最终导致集群可用性大幅下降。若多个节点被移出集群，该情况会进一步恶化。

我们最初为解决该干扰问题提出的方案是：节点在发起选举前，应先检查自身是否有机会赢得选举，避免浪费其他节点的资源。这一设计为选举流程新增了一个阶段，即预投票（Pre-Vote）阶段：候选节点会先向其他节点询问，自身的日志是否足够新、能否获得它们的选票；只有当候选节点确认自身能获得集群多数派的选票时，才会增加自身的任期号并发起正式的选举。

遗憾的是，预投票阶段无法解决干扰性节点的问题：在某些场景下，干扰性节点的日志足够新，但其发起的选举仍会对集群造成干扰。令人意外的是，这类情况甚至会在配置变更完成前发生。例如，图 4.7 展示了一个节点被移出四节点集群的场景：一旦领导者生成 Cnew 日志条目，待移除的节点就会成为干扰性节点。此时预投票检查无法发挥作用，因为该待移除节点的日志，比旧配置和新配置中多数派节点的日志都更新。（尽管预投票阶段无法解决干扰性节点的问题，但该设计能有效提升领导者选举的整体鲁棒性，具体见第 9 章。）

图 4.7 新配置条目提交前节点即可产生干扰且预投票阶段无法发挥作用的示例
本图展示了四节点集群中移除节点 S1 的场景。S4 为新配置的领导者，已在自身日志中生成新配置条目（Cnew），但尚未将该条目复制至集群其他节点；旧配置中的节点也不再收到 S4 发送的心跳包。即便在 Cnew 完成提交前，S1 就会因选举超时递增自身任期号，并将该更大的任期号发送至新配置中的节点，最终迫使 S4 退位。预投票算法在此场景下无法发挥作用，原因是 S1 的日志新鲜度，与新旧任一配置中多数派节点的日志持平。

基于这一场景我们得出结论：仅通过日志对比的方案（如预投票检查），无法判断一次选举是否会对集群造成干扰。我们无法要求节点在发起选举前，检查 Cnew 中所有节点的日志 —— 因为 Raft 必须始终能容忍节点故障。同时，我们也不愿假设领导者能以足够快的速度复制日志条目，快速脱离图 4.7 所示的场景：这一假设在实际中可能成立，但它依赖于更强的性能前提（日志分歧的检测性能、日志条目的复制性能），而我们更倾向于避免这类假设。

Raft 最终采用的解决方案是：通过心跳包判断集群是否存在有效的领导者。在 Raft 中，若领导者能持续向跟随者发送心跳包，则认为该领导者处于活跃状态（否则其他节点会发起选举）。因此，对于能正常接收领导者心跳包的集群，其他节点不应能对其造成干扰。我们通过修改 RequestVote RPC 实现这一逻辑：若节点在最小选举超时时间内收到过现任领导者的心跳包，当它再接收到 RequestVote 请求时，不会更新自身的任期号，也不会投出选票。该节点可直接丢弃请求、回复拒绝投票，或延迟处理请求，三种方式的实际效果基本一致。这一修改不会影响正常的选举流程 —— 因为正常情况下，每个节点都会等待至少一个最小选举超时时间后，才会发起选举。但它能有效避免未被纳入 Cnew 的节点造成的干扰：只要领导者能持续向其配置内的节点发送心跳包，就不会因其他节点的更大任期号而被废黜。

该修改会与前文描述的领导者移交机制产生冲突 —— 在领导者移交过程中，节点可无需等待选举超时，合法发起选举。针对该场景，其他节点即使感知到集群存在现任领导者，也仍需处理该 RequestVote 请求。解决方案是：在这类 RequestVote 请求中添加一个特殊标记，用于标识该选举的合法性（即 “我获得了干扰领导者的许可 —— 是它让我发起的选举！”）。

4.2.3 可用性论证

本节将论证，上述解决方案足以在集群成员变更的全过程中维持集群的可用性。由于 Raft 的成员变更操作由领导者主导，我们将从以下方面展开论证：该算法能在成员变更过程中持续维护领导者的存在、并在需要时完成领导者替换；且变更过程中的领导者能够正常处理客户端请求，并完成配置变更操作。本论证的前提包括：旧配置（Cold）的多数派节点保持可用（至少直至 Cnew 提交），且新配置（Cnew）的多数派节点同样保持可用。

配置变更的所有阶段，集群均能选举出领导者
- 若新配置中日志最新的可用节点已包含 Cnew 条目，则该节点可收集 Cnew 多数派的选票，成为新的领导者。
- 若上述节点未包含 Cnew 条目，则说明 Cnew 尚未提交。此时，在旧配置和新配置的所有节点中，日志最新的可用节点能同时收集到 Cold 多数派和 Cnew 多数派的选票，因此无论基于哪种配置，该节点都能当选领导者。
领导者当选后将持续维持领导权（假设其能向自身所属配置的节点正常发送心跳包），仅当一种情况会主动退位：自身并非 Cnew 的成员，且已完成 Cnew 的提交。
- 若领导者能稳定地向自身所属配置的节点发送心跳包，则其自身及所有跟随者都不会接受更大的任期号：这些节点不会因选举超时发起新的选举，且会忽略其他节点携带更大任期号的 RequestVote 请求，因此领导者不会被强制退位。
- 若未被纳入 Cnew 的节点完成 Cnew 的提交并退位，Raft 会随即选举出新的领导者，该领导者大概率属于 Cnew，进而推动配置变更完成。当然，该退位节点仍有极小概率重新当选领导者；若其再次当选，会先确认 Cnew 的提交状态，随后迅速退位，而下一次选举的胜出者大概率会是 Cnew 中的节点。
配置变更的全过程中，领导者始终能处理客户端请求
- 变更过程中，领导者可持续将客户端请求追加至自身的日志。
- 由于新节点在被正式加入集群前已完成日志追平，领导者能及时推进自身的提交索引（commit index），并向客户端返回响应。
领导者会持续推进直至完成配置变更：通过提交 Cnew 条目完成配置变更，必要时会主动退位，让 Cnew 中的节点当选新领导者。

4.3 基于联合共识的任意配置变更

本节提出一种更复杂的集群成员变更方案，可一次性处理集群配置的任意变更。例如，可向集群一次性新增两个节点，也可一次性替换五节点集群中的所有节点。这是我们最早提出的成员变更方案，在此仅作完整说明。如今我们已掌握更简洁的单节点变更方案，因此更推荐采用该方案 —— 因为处理任意配置变更需要引入额外的实现复杂度。文献中探讨成员变更时，通常默认其为一次性的任意变更，但我们认为，实际系统中无需这种灵活性：通过一系列单节点变更操作，即可将集群成员调整为任意期望的配置。

为确保任意配置变更全过程的安全性，集群会先切换至一种名为联合共识的过渡配置；待联合共识配置提交完成后，系统再正式切换至新配置。联合共识配置融合了旧配置与新配置的所有规则，具体如下：

日志条目会同步复制至新旧两种配置包含的所有节点；
新旧配置中的任意节点均有资格担任集群领导者；
共识达成（包括领导者选举和日志条目提交），需同时获得旧配置和新配置各自的多数派认可。例如，将 3 节点集群变更为另一组 9 节点集群时，共识达成需同时满足：旧配置 3 节点中的 2 个节点认可，且新配置 9 节点中的 5 个节点认可。

联合共识机制允许集群中的各个节点在不同时间点完成配置切换，且不会损害共识安全性。此外，该机制能让集群在配置变更的全过程中，持续处理客户端的请求。

该方案在单节点成员变更算法的基础上做了扩展，新增了一条用于存储联合共识配置的中间日志条目，图 4.8 展示了这一完整过程。当领导者接收到将配置从旧配置（Cold）变更为新配置（Cnew）的请求时，会将联合共识配置（图中记为 Cold,new）作为一条日志条目存入自身日志，并通过 Raft 的常规机制将该条目复制至集群其他节点。与单节点配置变更算法的规则一致，各节点在将配置条目存入自身日志后，会立即启用该配置。这意味着，领导者会依据 Cold,new的规则，判断该联合共识配置的日志条目是否完成提交。若此时领导者发生故障，新的领导者可能基于 Cold或 Cold,new选举产生，具体取决于胜出的候选节点是否已接收并存储 Cold,new配置条目。无论何种情况，此阶段的 Cnew都无法单独作出任何共识决策。

待 Cold,new配置条目提交完成后，Cold和 Cnew均无法脱离对方的认可单独作出共识决策；同时，领导者完备性原则会保证，只有存储了 Cold,new日志条目的节点，才有资格被选举为领导者。此时，领导者即可安全地创建一条描述 Cnew的配置日志条目，并将其复制至整个集群。同样，各节点在接收到该 Cnew配置条目后，会立即启用新配置。当 Cnew的配置条目依据其自身的规则完成提交后，旧配置便不再具备任何效力，未被纳入新配置的节点即可下线。如图 11 所示，整个配置变更过程中，不存在 Cold和 Cnew能同时单独作出共识决策的时间点，这一设计从根本上保障了配置变更的安全性。

图 11

图 11：一个配置切换的时间线。虚线表示已经被创建但是还没有被提交的配置日志条目，实线表示最后被提交的配置日志条目。领导人首先创建了 Cold,new 的配置条目在自己的日志中，并提交到 Cold,new 中（Cold 的大多数和 Cnew 的大多数）。然后他创建 Cnew 条目并提交到 Cnew 中的大多数。这样就不存在 Cnew 和 Cold 可以同时做出决定的时间点。

联合共识方案可进一步泛化，支持在前一次配置变更尚未完成时发起新的配置变更，但这一泛化设计并无实际应用价值。因此我们采用了更简洁的设计：当集群正在执行配置变更时（即领导者的最新配置尚未提交，或当前生效的是联合共识这类非简单多数派配置），领导者会直接拒绝新的配置变更请求。被拒绝的变更请求只需稍作等待，后续重新发起即可。

联合共识方案之所以比单节点变更方案更复杂，核心原因在于其需要完成向过渡配置的切换，以及从过渡配置向新配置的回切。同时，联合共识配置还需要修改所有与投票、日志提交相关的共识决策逻辑：领导者不再是简单统计参与共识的节点数量，而是需要分别检查这些节点是否构成旧配置的多数派，且同时构成新配置的多数派。在我们的 Raft 工程实现中，仅需找到并修改约六处相关的数量对比逻辑，即可完成该机制的落地。

4.4 系统集成

Raft 的各实现可通过不同方式，对外提供本章所述的集群成员变更机制。例如，图 4.1 中的 AddServer 和 RemoveServer 远程过程调用（RPC），可由管理员直接发起，也可由脚本调用 —— 该脚本通过一系列单节点变更步骤，实现任意形式的集群配置调整。

实践中，或许可以根据节点故障这类事件自动触发集群成员变更操作，但这一操作必须遵循合理的策略执行。例如，集群若自动移除故障节点会存在风险，这可能导致集群副本数量过少，无法满足预设的持久性和容错性要求。一种合理的方案是，由系统管理员配置集群的目标规模，在该规模限制下，让可用节点自动替换故障节点。

在执行需要多步单节点变更的集群成员变更操作时，建议遵循先增后删的原则。例如，在三节点集群中替换某一节点时，先新增一个节点再移除目标节点，能让系统在变更的全过程中，始终保持单节点故障的容忍能力；但如果先移除节点再新增，系统会暂时丧失故障屏蔽能力 —— 因为双节点集群要求两个节点均处于可用状态，才能完成共识决策。

集群成员变更机制，促使我们采用一种全新的集群引导方式。无动态成员管理能力时，各节点仅需通过静态配置文件记录集群配置；而支持动态成员变更后，便不再需要该静态配置文件 —— 因为系统会将集群配置纳入 Raft 日志进行统一管理，同时静态配置文件也存在潜在的配置错误风险（例如，新节点应使用哪一版集群配置完成初始化？）。因此，我们建议集群首次创建时按如下方式操作：先对单个节点完成初始化，将一条集群配置条目作为其日志的第一条条目，该配置条目仅包含该节点自身；由于该节点可单独构成其所属配置的多数派，因此能直接认定该配置已完成提交。此后，其他节点均以空日志状态完成初始化，通过集群成员变更机制被加入集群，并同步获取当前的集群配置。

集群成员变更还要求为客户端设计动态的集群发现机制，相关实现细节将在第 6 章展开论述。

4.5 结论

本章阐述了 Raft 的一项扩展机制，用于实现集群成员变更的自动化处理。这是完整共识类系统的重要组成部分 —— 因为系统的容错性需求会随时间发生变化，且故障节点最终也需完成替换。

共识算法从根本上必须参与到配置变更全过程的安全性保障中，原因在于新的集群配置会改变 “多数派” 的判定内涵。本章提出了一种简洁的实现方案，支持单次新增或移除单个节点。这类操作以简洁的方式保障了共识安全性，核心原因是变更过程中，任意两个不同的多数派集合间至少存在一个公共节点。通过组合多次单节点变更操作，可实现更复杂的集群配置调整。同时，Raft 机制能让集群在成员变更的全过程中保持正常运行。

保障配置变更过程中的集群可用性，需要解决若干非基础性问题。其中，尤为值得注意的是，未被纳入新配置的节点干扰集群合法领导者这一问题，具有出乎意料的隐蔽性；我们曾尝试过多种基于日志对比的解决方案，但均存在缺陷，最终才确定了基于心跳包的可行解决方案。

5 日志压缩

Raft 日志在正常运行过程中，会随客户端请求的持续写入不断增长。日志体积越大，占用的存储空间就越多，日志重放的耗时也越长。若未采取任何日志压缩手段，最终将引发可用性问题：节点要么因存储空间耗尽无法运行，要么启动耗时过长。因此，任何实际的分布式系统都需实现某种形式的日志压缩。

日志压缩的核心思路是，日志中的大量信息会随时间推移失效，可直接舍弃。例如，若某条操作将变量 x 赋值为 2，后续另有操作将 x 赋值为 3，那么前者便失去效用。当日志条目完成提交并应用至状态机后，用于达成当前状态的各类中间状态和操作便无保留必要，可通过压缩对其进行清理。

与 Raft 核心算法、集群成员变更不同，不同系统对日志压缩的需求各有差异，目前尚无适用于所有场景的日志压缩解决方案，原因有二。其一，不同系统会在实现简洁性与运行性能之间，做出不同程度的取舍。其二，日志压缩的实现需要状态机深度参与，而各类状态机在规模上差异显著，且底层存储介质也分为磁盘型和易失性内存型两类。

本章旨在探讨多种日志压缩的实现方案。在各类方案中，日志压缩的主要工作均由状态机承担 —— 状态机负责将自身状态写入磁盘并完成状态压缩。状态机可通过多种方式实现这一需求，相关细节将在本章逐一阐述，并在图 5.1 中进行汇总说明：

图 5.1 展示了各类日志压缩方案在 Raft 中的具体应用方式。图中日志结构合并树的相关细节以 LevelDB 为参考，日志清理的细节以 RAMCloud 为参考，其中删去了删除操作的管理规则。

从概念上讲，为基于内存的状态机创建快照最为简单。执行快照时，将当前完整的系统状态写入稳定存储的快照文件，随后舍弃截至该时间点的全部日志。Chubby 和 ZooKeeper 均采用了该机制，我们也在 LogCabin 中实现了快照机制。本章 5.1 节将对这一方案展开最深入的阐述。
对于基于磁盘的状态机，系统会在常规运行过程中，将最新的系统状态副本持久化至磁盘。因此，一旦状态机将写入操作落地磁盘，即可舍弃对应的 Raft 日志；仅在向其他节点发送一致性磁盘镜像时，才会启用快照机制（详见 5.2 节）。
日志压缩的增量式实现方案（如日志清理、日志结构合并树）将在 5.3 节介绍。这类方案能高效完成磁盘写入，且可在系统运行期间均衡利用各类资源。
最后，5.4 节将探讨一种日志压缩方案：通过将快照直接存储在日志中，最大限度简化其实现所需的机制。该方案虽更易落地，但仅适用于规模极小的状态机。

LogCabin 目前仅实现了基于内存的快照方案（其内置了一个基于内存的状态机）。

各类日志压缩方案存在若干核心共性。其一，日志压缩的决策并非由领导者集中执行，而是由各节点独立对自身日志的已提交前缀完成压缩。这一设计避免了领导者向本地日志已存有相关数据的跟随者重复传输数据，同时也提升了系统的模块化程度：日志压缩的大部分复杂逻辑均封装在状态机内部，与 Raft 核心逻辑的交互极少。这有助于将系统整体复杂度控制在最低水平——Raft 的复杂度与日志压缩的复杂度为叠加关系，而非乘积关系。将压缩职责集中于领导者的替代方案将在 5.4 节进一步探讨（对于规模极小的状态机，基于领导者的方案或许更优）。

其二，状态机与 Raft 的基础交互，核心是将日志前缀的管理职责从 Raft 移交至状态机。状态机在应用日志条目后，终将通过特定方式将这些条目对应的状态落地磁盘，以支持当前系统状态的恢复。一旦完成落地，状态机会通知 Raft 舍弃对应的日志前缀。Raft 在移交该日志前缀的管理职责前，必须留存用于描述该前缀的部分自身状态。具体而言，Raft 会记录最后一条舍弃日志条目的索引与任期；该信息能在状态机完成状态落地后，为日志的后续部分提供锚定基准，确保追加日志的一致性检查可正常执行（该检查需要日志首条条目前一记录的索引与任期）。Raft 还会从已舍弃的日志前缀中留存最新的集群配置，以支持集群成员变更操作。

其三，当 Raft 舍弃某一日志前缀后，状态机将承担两项新的职责。若节点发生重启，状态机需先从磁盘加载与已舍弃日志条目对应的状态，之后才能应用 Raft 日志中的后续条目。此外，状态机还需生成一致性的状态镜像，用以发送至日志大幅落后于领导者的慢跟随者节点。无法将日志压缩推迟至日志条目“全量复制”到集群所有节点后再执行，因为少数慢跟随者不能影响集群的整体可用性，且集群可随时新增节点。因此，慢跟随者或新节点有时需要通过网络获取其初始状态。当领导者发现，追加日志操作所需的下一条目已从自身日志中舍弃时，便会触发该流程。此时，状态机需生成一致性的状态镜像，由领导者发送至该跟随者节点。

5.1 基于内存状态机的快照实现

快照机制的首个实现方案，适用于状态机数据结构全程驻留内存的场景。对于数据集规模达千兆或数十千兆字节的状态机而言，这一选择十分合理：该方案能让操作快速完成，因全程无需从磁盘读取数据；同时实现难度更低，可灵活使用复杂的富数据结构，且每个操作均可完整执行（无需为 I/O 操作阻塞）。

图 12 展示了状态机驻留内存时，Raft 中快照机制的核心实现思路。集群中各节点独立执行快照操作，仅对自身日志内的已提交条目进行快照处理。快照的核心工作是序列化状态机的当前状态，这一过程与状态机的具体实现强相关。例如，LogCabin 的状态机以树结构作为核心数据结构，其通过前序深度优先遍历完成树的序列化（确保应用快照时，父节点先于子节点创建）。此外，状态机还需序列化其为向客户端提供线性一致性所维护的相关信息（详见第 6 章）。

图 12

图 12：节点将其日志中已提交的条目（索引 1 至 5）替换为一份新快照，该快照仅存储当前系统状态（本示例中为变量 x 和 y）。在舍弃索引 1 至 5 的条目前，Raft 会保存该快照的最后包含索引（5）与最后包含任期（3），为快照在日志中完成定位，使其处于条目 6 之前的位置。

状态机完成快照写入后，即可对日志执行截断操作。Raft 首先持久化节点重启所需的状态信息：快照中包含的最后一条日志条目的索引与任期、以及该索引对应的最新集群配置。随后，Raft 舍弃截至该索引的全部日志前缀，所有旧快照也可一并删除，因其已无使用价值。

如前文所述，领导者有时需要向日志大幅落后的慢跟随者、以及新加入集群的节点同步自身状态。在快照机制中，该同步状态即为集群最新快照，领导者通过一种全新的 RPC——安装快照完成快照传输，具体见图 5.3。
当跟随者通过该 RPC 接收快照后，需决定如何处理本地已有的日志条目：通常情况下，快照会包含跟随者本地日志中未有的新信息，此时跟随者需舍弃全部本地日志 —— 这些日志已被快照完全取代，且其中可能存在与快照冲突的未提交条目；若跟随者接收的快照仅对应其本地日志的某一前缀（因重传或操作失误导致），则仅删除快照所覆盖的日志条目，快照之后的条目仍有效，需予以保留。

图 5.3：领导者调用安装快照远程过程调用，向日志落后的跟随者发送快照。
仅当领导者已舍弃通过追加日志操作向该跟随者复制条目所需的下一条日志条目时，才会选择发送快照。
领导者将快照切分为数据块进行传输。此举除带来其他益处外，还能通过每个数据块向跟随者发送存活信号，使其得以重置选举计时器。所有数据块均按序发送，这一设计简化了快照文件的磁盘写入流程。
该远程过程调用携带有 Raft 节点重启时加载快照所需的状态信息：快照覆盖的最后一条日志条目对应的索引与任期，以及该时间点的最新集群配置。

本节后续内容将探讨基于内存状态机实现快照的若干次要问题：

5.1.1 节阐述如何让快照操作与系统正常业务操作并行执行，最大限度降低其对客户端的影响；
5.1.2 节探讨快照的执行时机选择，平衡存储空间占用与快照操作的性能开销；
5.1.3 节探讨快照实际实现过程中遇到的各类问题。

5.1.1 并发快照

创建快照的过程耗时较长，核心耗时点集中在状态序列化与磁盘写入两个环节。
例如，当前服务器中复制 10GB 内存约需 1 秒，而对该数据进行序列化的耗时通常会远长于此；即便是固态硬盘，每秒的写入量也仅约 500MB。因此，快照的序列化与写入操作必须与节点的常规业务操作并发执行，避免系统出现可用性中断。

所幸写时复制技术可在不影响快照写入的前提下，处理新的状态更新请求。实现这一目标主要有两种方式：

状态机可基于不可变（函数式）数据结构构建，以此支持并发快照。
由于状态机的指令不会就地修改状态，快照任务可保留对某一历史状态的引用，并将该状态一致性地写入快照文件。
亦可借助操作系统提供的写时复制支持（前提是编程环境支持该特性）。
以 Linux 系统为例，驻留内存的状态机可通过 fork 系统调用复制服务器的整个地址空间。子进程负责将状态机数据写入磁盘并退出，而父进程可继续处理业务请求。LogCabin 的现有实现采用的正是这种方式。

节点执行并发快照时需要额外的内存资源，这一点需提前规划并做好管理。状态机必须为快照文件提供流式接口，避免快照数据在生成过程中全量驻留于内存。但即便如此，写时复制仍会产生额外的内存开销，且开销规模与快照过程中状态机被修改的数据占比成正比。此外，依赖操作系统实现写时复制通常会消耗更多内存，这一问题由伪共享导致——例如，若两个不相关的数据项恰好位于同一内存页，即便仅修改其中一项，另一项也会被连带复制。

若快照过程中出现内存耗尽的极端情况，节点应停止接收新的日志条目，直至快照生成完成；这一操作会暂时降低节点的可用性（但集群整体仍可能保持可用），但至少能让节点完成恢复。此时不应中断快照并延后重试，因为后续的快照尝试大概率仍会遭遇相同的内存问题。（LogCabin 虽为磁盘写入实现了流式接口，但目前尚未能优雅处理内存耗尽的场景。）

5.1.2 快照触发时机

节点需合理决策快照的触发时机。若快照触发过于频繁，会造成磁盘带宽及其他资源的浪费；若触发过于稀疏，则可能导致节点存储资源耗尽，同时也会增加节点重启时的日志重放耗时。

一种简单的策略是：当日志文件的字节大小达到固定阈值时触发快照。若将该阈值设置为显著大于快照的预期大小，快照操作带来的磁盘带宽开销会相对较小。但这种方式对于小型状态机而言，可能会产生不必要的大体积日志文件。

更优的方式是对比快照文件与日志文件的大小：若快照文件的体积远小于日志文件，此时触发快照通常是值得的。但快照生成前，其文件大小难以精准计算，且计算过程本身开销较高——要么会给状态机带来繁重的元数据管理负担，要么动态计算的耗时几乎与实际生成快照相当。对快照文件进行压缩虽能节省存储空间与传输带宽，但压缩后的文件大小同样难以预测。

所幸的是，以上一次快照的大小而非下一次快照的预估大小为参考，能让快照触发的决策效果趋于合理。具体策略为：当日志文件大小超过上一次快照大小与可配置扩展系数的乘积时，触发新的快照。该扩展系数的取值本质是在磁盘带宽开销与存储利用率之间做权衡。例如，将扩展系数设为 4 时，节点约 20% 的磁盘带宽会用于快照操作（每生成 1 字节的快照数据，对应会写入 4 字节的日志条目），且此时节点所需的磁盘容量约为存储单份状态数据的 6 倍（包含旧快照、4 倍于旧快照的日志文件，以及正在写入的新快照）。

快照操作仍会造成 CPU 与磁盘带宽的突发占用，可能影响客户端的请求处理性能。这一问题可通过硬件扩容缓解，例如新增一块磁盘以提供额外的磁盘带宽。

此外，也可通过合理的调度策略，让客户端请求无需等待正执行快照的节点。具体而言，集群内的节点可相互协调，确保任意时刻仅有少数节点执行快照（在条件允许的情况下）。由于 Raft 协议仅要求集群中多数节点完成日志条目提交即可，因此少数节点执行快照通常不会对客户端的业务请求造成负面影响。若领导者需要执行快照，可先主动退位，让其他节点临时接管集群的管理工作。若该调度策略的可靠性足够高，甚至可无需实现并发快照——节点执行快照期间可暂时下线（但该节点仍会被计入集群的故障屏蔽能力评估）。

这一策略是未来的重要优化方向，因其有望在提升系统整体性能的同时，简化快照的实现机制。

5.1.3 实现注意事项

本节梳理快照功能实现所需的核心组件，并探讨各组件的落地难点：

快照的保存与加载：保存快照即把状态机的状态序列化后写入文件，加载则是其逆过程。我们发现这一过程实现起来相对简单，仅需将各类数据对象从其原生表示形式序列化为指定格式，只是该序列化操作略显繁琐。为避免状态机的全量数据在内存中缓冲，为状态机设计面向磁盘文件的流式接口十分必要；同时，对序列化的数据流进行压缩并添加校验和，也能带来实际收益。LogCabin 会先将每个快照写入临时文件，待写入完成并刷盘后，再对文件进行重命名；这一机制能确保服务器启动时，不会加载未写入完成的快照。
快照的传输：实现快照传输，需要完成 InstallSnapshot 远程过程调用（RPC）中领导者与跟随者两端的逻辑开发。这部分实现同样相对简单，且可复用一部分快照本地保存与加载的代码。快照传输的性能通常无需重点优化——需要接收快照的跟随者，本就未参与日志条目的提交流程，因此其同步进度的紧迫性较低；当然，若集群发生更多节点故障，快速完成该跟随者的快照同步，对恢复集群可用性会有重要意义。
消除不安全的日志访问与日志条目丢弃：LogCabin 的初始设计未考虑日志压缩场景，因此代码中存在一个默认假设：若日志中存在条目 i，那么条目 1 至 i-1 也必然存在。但开启日志压缩后，该假设不再成立；例如，在 AppendEntries RPC 中查询前一条日志条目的任期时，该条目可能已被丢弃。要在代码中彻底移除这一假设，需要严谨的逻辑梳理与充分的测试验证。若能借助功能更强大的类型系统，让编译器强制约束所有日志访问操作都处理索引越界的情况，这一工作的难度会大幅降低。当所有日志访问操作都被改造为安全实现后，丢弃日志的前缀部分就变得十分简单。在此之前，我们只能对快照的保存、加载和传输功能做独立测试；而实现安全的日志丢弃后，这些功能便能在全系统测试中得到完整的场景验证。
基于写时复制的并发快照：实现并发快照，要么需要重构状态机的设计，要么需要借助操作系统的 fork 操作。LogCabin 目前采用 fork 实现该特性，而 fork 与线程、C++ 析构函数的兼容性较差，要实现该逻辑的正确运行曾面临不少难点。但该方案的代码量极少，且完全无需修改状态机的数据结构，因此我们认为这是最优实现方案。
快照触发时机的决策：我们建议在开发阶段，设置为每应用一条日志条目后即触发一次快照，这一方式能帮助开发人员快速发现程序漏洞。待快照功能完整实现后，再接入更贴合实际业务的触发策略即可（例如，基于 Raft 日志的大小、上一次快照的大小等统计信息动态决策）。

我们发现，快照功能的分步开发与测试具有一定挑战性。上述大部分组件必须全部实现后，才能落地日志条目的丢弃逻辑；而唯有完成日志丢弃的开发，这些新编写的代码路径，才能在全系统测试中得到充分的场景覆盖。因此，开发人员需要谨慎规划各组件的实现与测试顺序。

5.2 磁盘型状态机的快照处理

本节探讨面向大型磁盘型状态机（数据量达数十乃至数百吉字节）的快照处理方案，这类状态机以磁盘作为主要的持久化存储介质。其工作特性存在特殊性：为应对故障恢复，磁盘中始终留存有一份可用的状态副本。每执行一条 Raft 日志条目，都会修改磁盘上的状态，最终实际生成一个新的快照。因此，日志条目一经执行，即可从 Raft 日志中删除。（状态机也可将写操作缓存在内存中，以提升磁盘写入效率；待这些写操作落盘后，对应的日志条目即可从 Raft 日志中删除。）

磁盘型状态机的核心问题，在于直接修改磁盘状态会造成性能损耗。若未启用写缓冲，每执行一条命令都需要进行一次或多次磁盘随机写操作，这会限制系统的整体写入吞吐量（而写缓冲对此的优化效果可能十分有限）。5.3 节将探讨日志压缩的增量处理方案，该方案通过大粒度的顺序写操作实现更高效的磁盘写入。

为向同步速度较慢的从节点传输快照，磁盘型状态机必须能够生成一份一致性的磁盘快照。尽管其磁盘中始终存在快照，但该快照会被持续修改。因此，这类状态机仍需借助写时复制技术，将一份一致性快照保留足够长的时间，以完成传输过程。所幸的是，磁盘格式几乎均按逻辑块划分，因此在状态机中实现写时复制的逻辑会较为简便。

磁盘型状态机也可依托操作系统的原生支持实现快照功能。例如，Linux 系统中的逻辑卷管理（LVM）可用于创建整个磁盘分区的快照，而部分新一代文件系统也支持对单个目录创建快照。

复制磁盘镜像快照的过程可能耗时良久，且随着磁盘修改操作的不断累积，保留该快照所需的额外磁盘空间也会随之增加。尽管我们尚未实现磁盘型快照的相关功能，但推测磁盘型状态机可通过下述算法传输磁盘内容，从而规避上述大部分开销：

为每个磁盘逻辑块记录其最后一次的修改时间。
主节点在维持正常业务运行的同时，将全部磁盘内容按逻辑块逐一传输至目标从节点；此过程中，主节点不会占用额外的磁盘空间。由于传输过程中磁盘块会被并发修改，从节点接收到的磁盘镜像大概率是不一致的。主节点在传输每个磁盘块时，需记录其当前的最后修改时间。
对磁盘内容创建写时复制快照。快照创建完成后，主节点将持有一份一致性的磁盘内容副本；但后续客户端的持续操作会引发磁盘修改，这将导致主节点产生额外的磁盘空间占用。
仅重传那些在步骤 2 首次传输后、步骤 3 快照创建前发生修改的磁盘逻辑块。

理想情况下，在步骤 3 完成一致性快照创建时，该快照的大部分磁盘块已完成传输。若能达成此状态，步骤 4 的传输过程将高效完成：主节点在步骤 4 中为保留快照所占用的额外磁盘空间会极少，而步骤 4 中为重传修改块所消耗的额外网络带宽也会极低。

5.3 增量清理方案

日志压缩的增量实现方案（如日志清理与日志结构合并树，即 LSM 树）同样具备可行性。这类方案虽比快照机制更为复杂，但拥有多项优势特性：

每次仅对部分数据执行操作，可将日志压缩的负载均匀分摊至系统全运行周期。
无论常规运行还是日志压缩阶段，均能实现高效磁盘写入，且两种场景下均采用大粒度顺序写方式。增量方案还会针对性地对磁盘中可回收空间最大的区域执行压缩，因此相较于基于内存的状态机所采用的快照机制（每次创建快照都会重写全部磁盘数据），增量方案向磁盘写入的数据量更少。
因不会对磁盘区域执行原地修改，故而能较为便捷地传输一致性的状态快照。

5.3.1 节与 5.3.2 节将首先阐述日志清理与 LSM 树的通用基础原理，5.3.3 节则进一步探讨其在 Raft 算法中的具体应用方式。

5.3.1 日志清理的基础

日志清理最初应用于日志结构文件系统领域，近期也被提出用于 RAMCloud 这类内存存储系统。从理论上讲，日志清理可适配任意类型的数据结构，只是部分结构的高效实现难度更高。

日志清理将日志作为系统状态的持久化存储载体，其存储布局针对顺序写做了优化，但这也导致读操作实际为随机访问，因此需要通过索引结构定位待读取的数据项。

在日志清理机制中，日志会被划分为若干连续的区域，称为段。日志清理器的每次清理过程，均通过三步算法完成日志压缩：

首先筛选出累计失效条目占比高的段，作为本次清理的对象；
随后将这些段中的有效条目（即对当前系统状态有实际贡献的条目）复制至日志头部；
最后释放这些被清理段的存储空间，将其预留为新段的可用空间。

为最大限度降低对系统常规运行的影响，该清理过程可与业务操作并行执行。

由于有效条目被向前复制至日志头部，日志重放时的条目顺序会被打乱。因此可在日志条目中嵌入额外信息（如版本号），确保日志执行时能恢复正确的条目顺序。

清理段的选择策略对系统性能影响显著，已有研究提出了一种成本收益策略，该策略不仅会考量有效条目占用的存储空间，还会评估这些条目预计的有效存续时长。

判定日志条目是否为有效条目是状态机的核心职责。例如在键值存储系统中，若某个键存在且当前值与日志条目中的设定值一致，那么将该键设为指定值的日志条目即为有效条目。而判定删除某个键的日志条目是否有效则更为复杂：只要日志中仍保留该键此前的赋值条目，该删除条目就始终为有效条目。RAMCloud 会根据实际需要保留删除指令（这类指令被称为墓碑记录），另一种实现方案则是定期导出当前系统状态中所有存在的键的汇总信息，此后所有与未列入该汇总的键相关的日志条目，均判定为失效条目。键值存储是一类相对简单的应用场景，日志清理也可适用于其他类型的状态机，但遗憾的是，不同状态机的条目有效性判定逻辑均存在差异。

5.3.2 日志结构合并树的基础

日志结构合并树（LSM 树）由奥尼尔首次提出，后经 BigTable 系统的应用，在分布式领域得到广泛普及。目前该结构已被 Apache Cassandra、HyperDex 等系统采用，也有 LevelDB 及其衍生版本（如 RocksDB、HyperLevelDB）这类开源库实现了该机制。

LSM 树是一种存储有序键值对的类树型数据结构。从整体设计来看，其磁盘使用方式与日志清理方案相近：均采用大粒度顺序写，且不会对磁盘上的数据执行原地修改。二者的核心区别在于，LSM 树不会将所有系统状态都保存在日志中，而是会对状态进行重新组织，以优化随机访问的性能。

典型的 LSM 树会将近期写入的键值对暂存于磁盘上的小型日志中。当该日志达到固定容量阈值时，系统会将其中的内容按键排序，并以有序形式写入一个名为 有序段（run） 的文件。有序段一旦生成便不会被原地修改，而系统会通过定期的压缩过程，将多个有序段合并为新的有序段，并丢弃原有的旧段。该合并过程与归并排序的原理相似：若同一键出现在多个待合并的有序段中，仅保留其最新版本，因此合并后生成的有序段数据会更紧凑。LevelDB 采用的压缩策略如图 5.1 所示，该策略按生成时间对有序段进行分层管理以提升处理效率，这一点与日志清理机制的设计思路相近。

在系统常规运行过程中，状态机可直接对 LSM 树中的数据进行操作。读取某个键时，会先检查小型日志中是否有该键的近期修改记录，再依次检索各个有序段。为避免每次键查找都遍历所有有序段，部分系统会为每个有序段创建布隆过滤器—— 这是一种紧凑的数据结构，可在部分场景下精准判定某个键不存在于某一有序段中；当然该结构也存在局限性，有时即便键实际不存在，仍需对有序段进行一次检索验证。

5.3.3 Raft 中的日志清理与日志结构合并树

我们尚未尝试在 Raft 中实现日志清理或日志结构合并树机制，但推测二者均可在此场景下良好运行。将日志结构合并树应用于 Raft 的实现方式相对直观：由于 Raft 日志已将近期条目持久化存储在磁盘中，日志结构合并树可在内存中以更易操作的树型结构存储近期数据，这能提升查询请求的处理效率；当 Raft 日志达到固定容量阈值时，该树型结构已完成排序，可直接作为新的有序段写入磁盘。

将主节点的状态传输至同步速度较慢的从节点时，只需将所有有序段发送至从节点（而非内存中的树型结构）；所幸有序段具备不可变性，无需担心其在传输过程中被修改。

而将日志清理应用于 Raft 则并非如此直观。我们最初考虑的方案是将 Raft 日志直接划分为若干段并执行清理操作（见图 5.4 (a)）。但该方案存在明显弊端：清理操作会在日志中被释放段的位置形成大量空闲空洞，这就需要对日志复制机制做相应改造。我们认为该方案可通过改造实现运行，但会为 Raft 本身及其与状态机的交互过程带来极大的复杂度。此外，由于仅有主节点可向 Raft 日志追加条目，日志清理需基于主节点执行，这会造成主节点网络带宽的浪费（相关内容将在 5.4 节进一步探讨）。

一种更优的方案是采用与日志结构合并树相近的方式处理日志清理：Raft 为近期的状态变更维护一份连续的日志，状态机则将自身状态以日志形式独立存储，二者的日志在逻辑上相互独立（见图 5.4 (b)）。当 Raft 日志达到固定容量阈值时，其新条目会作为新的段写入状态机的日志，而 Raft 日志中对应的前缀部分则会被删除。状态机中的段由集群各节点独立执行清理操作，Raft 日志则完全不受此过程的影响。

相较于直接清理 Raft 日志，我们更倾向于该方案，原因有二：一是日志清理的复杂度被完全封装在状态机内部，状态机与 Raft 之间的接口仍保持简洁；二是集群各节点可独立执行清理操作，无需依赖主节点。

如前所述，该方案要求状态机将 Raft 的所有日志条目写入自身日志（不过可通过大批次的方式执行该操作）。这一额外的复制操作可通过优化省去：直接迁移 Raft 日志中由日志条目组成的文件，并将该文件整合至状态机的数据结构中。该优化手段对性能要求严苛的系统而言十分实用，但遗憾的是，这会使状态机与 Raft 模块的耦合程度大幅提高 —— 因为状态机需要理解 Raft 日志的磁盘存储格式。

5.4 替代方案：基于主节点的实现方式

本章提出的日志压缩方案偏离了 Raft 的强主节点原则，原因是集群各节点可在主节点不知情的情况下自行执行日志压缩操作。但我们认为这一设计偏差具备合理性：主节点的核心作用是避免共识达成过程中出现决策冲突，而快照处理与日志压缩均发生在共识达成之后，因此不会产生任何决策冲突。数据的流转方向仍保持为主节点至从节点，唯一的变化是从节点如今可独立对自身数据进行重组。

我们也曾探讨过基于主节点的日志压缩方案，但这类方案的些许优势，通常会被性能层面的问题完全抵消。若让主节点先完成自身日志的压缩，再将压缩结果传输至各从节点，而非让从节点独立执行压缩操作，这一做法本身就存在资源浪费。向每个从节点传输冗余的状态数据，不仅会耗费大量网络带宽，还会拖慢整体的日志压缩进程。各从节点本身已具备执行本地状态压缩所需的全部信息，而主节点的下行网络带宽向来是 Raft 集群中最稀缺的资源，也是核心的性能瓶颈。

对于基于内存的快照机制而言，节点从本地状态生成快照的开销，通常远低于通过网络发送和接收快照的开销。而对于增量压缩方案，其开销对比结果会稍受硬件配置的影响，但我们依然认为，让各节点独立执行压缩的方式综合成本更低。

5.4.1 将快照存储于日志中

基于主节点的实现方案存在一项潜在优势：若能将所有系统状态均存储于日志中，就无需为状态的复制与持久化设计新机制。为此，我们设计了一种基于主节点的快照实现方案，具体逻辑如图 5.5 所示 —— 由主节点创建快照，并将快照封装为日志条目存储至 Raft 日志中，再通过 AppendEntries 远程过程调用（RPC）将该快照发送至所有从节点。为尽可能降低对系统常规运行的干扰，可将单个快照拆分为多个日志条目，在日志中与常规客户端命令交错写入。

图 5.5 基于主节点的快照存储方案：将快照分块存入日志并与客户端请求交错排布
该方案将快照分块存储于 Raft 日志中，且快照分块条目与客户端请求条目交错写入。快照创建过程从开始条目启动，至结束条目完成，快照数据则存储在开始条目与结束条目之间的若干日志条目中。为使客户端请求能与快照创建过程并行执行，方案会对单个快照分块条目的大小做限制，同时限制日志的条目追加速率：主节点仅在确认前一个快照分块条目已提交后，才会将下一个快照分块条目追加至日志。
当集群各节点确认结束条目已提交后，即可删除自身日志中截至对应开始条目前的所有日志条目。该方案下的日志重放需采用双遍执行算法：先执行日志中最新的完整快照，再执行该快照开始条目之后的所有客户端请求条目。

相较于将快照存储在日志外部的方案，该方式能实现更优的机制简洁性：节点无需为快照的传输和持久化设计独立机制，快照的复制与持久化流程可与普通日志条目完全一致。但除了会向原本可独立生成快照的从节点传输数据、造成网络带宽浪费外，该方案还存在一个严重缺陷：若主节点在创建快照的过程中发生故障，会在各节点的日志中遗留部分快照数据。理论上，这种故障情况可能反复发生，由多次快照尝试失败产生的垃圾数据会持续累积，最终耗尽节点的存储容量。因此，我们认为该机制不具备实际落地的可行性。

5.4.2 面向超小型状态机的基于主节点方案

对于超小型状态机而言，将快照存储于日志中不仅具备实际可行性，还能大幅简化实现流程。若快照体积足够小（约 1 兆字节以内），便可完整存入单个日志条目，且不会对系统常规运行造成过长时间的中断。主节点若采用该方式完成集群节点的日志压缩，需执行以下步骤：

停止接收新的客户端请求；
等待自身日志中的所有条目完成提交，且自身状态机执行完所有日志条目；
同步创建快照；
将该快照作为单个日志条目追加至自身日志末尾；
恢复接收新的客户端请求。

当各节点确认该快照条目已完成提交后，即可删除自身日志中该快照条目之前的所有条目。在停止接收客户端请求并传输该快照条目的过程中，该方案会造成短暂的服务可用性中断，但对于超小型状态机而言，其影响程度有限。

这一简化方案省去了多项实现工作：无需将快照持久化至日志外部，无需通过新的远程过程调用（RPC）传输快照，也无需实现快照的并发创建机制。但实际场景中，成功的系统其使用规模往往会超出设计者最初的预期，因此该方案无法适配规模更大的状态机。

5.5 结论

本章探讨了 Raft 算法中多种日志压缩方案，相关方案汇总如图 5.1 所示。
不同方案适用于不同的系统，具体选型取决于状态机的规模、系统对性能的要求以及可投入的实现复杂度。Raft 支持各类日志压缩方案的实现，且这些方案均遵循一套统一的概念框架，核心共性如下：

集群各节点独立对自身日志的已提交前缀部分执行压缩操作；
状态机与 Raft 的基础交互，核心是将日志前缀的管理职责从 Raft 移交至状态机。当状态机将日志中的命令落地至磁盘后，会通知 Raft 删除对应的日志前缀；Raft 则会留存最后一条被删除日志条目的索引与任期，以及该索引对应的最新集群配置；
当 Raft 完成日志前缀的删除后，状态机将承担两项新职责：一是在节点重启时加载系统状态，二是生成一致性的状态镜像并传输至同步速度较慢的从节点。

面向基于内存的状态机的快照机制，已在 Chubby、ZooKeeper 等多款生产级系统中得到成功落地，我们也在 LogCabin 系统中实现了该方案。

尽管对内存数据结构执行各类操作的速度均较为可观，但快照创建过程中，系统性能可能受到显著影响。并发创建快照有助于掩盖资源占用带来的性能损耗；未来若对集群内所有节点做快照时间调度，让各节点错峰执行快照操作，或可实现快照处理完全不影响客户端业务。

采用原地修改状态的磁盘型状态机，在设计理念上更为简洁。为向其他节点传输一致性的磁盘镜像，这类状态机仍需借助写时复制技术，但磁盘本身天然按块划分，因此该技术的实现开销相对较低。但常规运行过程中的磁盘随机写操作速度通常较慢，因此该方案会限制系统的写入吞吐量。

从整体来看，增量方案是效率最优的日志压缩方式。这类方案每次仅对少量状态数据执行操作，可有效抑制资源占用的突发波动（且同样支持并发压缩）；同时还能避免同一数据被反复写入磁盘，稳定的数据最终会被存储至磁盘中极少被压缩的区域。尽管增量压缩的实现存在一定复杂度，但可将该部分复杂度剥离至 LevelDB 这类第三方库中实现。此外，通过将数据结构驻留内存，并将更多磁盘数据缓存至内存中，采用增量压缩方案的系统，其客户端操作性能可接近基于内存的状态机的水平。

6 客户端交互

本章阐述客户端与基于 Raft 的复制状态机交互过程中的若干关键问题：

6.1 节说明客户端如何发现集群（即便集群的节点组成会随时间动态变化）；
6.2 节说明客户端的请求如何路由至集群主节点进行处理；
6.3 节说明 Raft 如何实现线性一致性；
6.4 节说明 Raft 如何更高效地处理只读查询。

图 6.1 展示了客户端与复制状态机交互所使用的远程过程调用（RPC），本章将对这些 RPC 的核心要素展开逐一探讨。上述问题适用于所有基于共识的分布式系统，Raft 所采用的解决方案与其他同类系统相近。

本章默认基于 Raft 的复制状态机以网络服务的形式直接向客户端提供访问。当然，Raft 也可直接集成至客户端应用程序中。在此种部署方式下，部分客户端交互相关问题会向上转移至该嵌入式应用的网络客户端层。例如，该嵌入式应用的网络客户端在发现应用集群时，会遇到与 Raft 网络服务的客户端发现 Raft 集群完全相同的问题。

6.1 集群发现

当 Raft 以网络服务形式对外提供能力时，客户端必须先定位到集群，才能与复制状态机进行交互。对于节点组成固定的集群，这一操作十分简便，比如可将集群节点的网络地址静态配置在配置文件中。但当集群的节点组成会随时间动态变化时（如第 4 章所述），集群发现就成为了更大的挑战。现有两种通用实现方案：

客户端通过网络广播或组播机制发现集群内所有节点，该方案仅适用于支持这两种网络特性的特定部署环境。
客户端通过部署在公知访问地址的外部目录服务（如域名系统 DNS）发现集群节点。该外部系统中的节点列表无需保证强一致性，但需满足完备性要求：客户端必须能通过该列表找到集群的所有节点，即便列表中包含少量当前非集群成员的节点，也不会产生任何影响。因此在执行集群节点变更操作时，需先更新该外部节点目录，将待加入集群的节点纳入其中；待节点变更操作完成后，再对该目录进行二次更新，移除已退出集群的节点。

LogCabin 的客户端目前采用 DNS 实现集群发现，该系统暂未实现节点成员变更前后 DNS 记录的自动更新功能（此操作现阶段由管理脚本完成）。

6.2 将请求路由至主节点

Raft 中的客户端请求是通过领导者处理的，因此客户端需要一种主节点发现机制。客户端首次启动时，会随机连接集群中的一个节点；若所选节点并非主节点，该节点会直接拒绝此次请求。此时最直接的处理方式，是让客户端继续随机选择其他节点重试，直至找到主节点。若客户端采用无放回随机选择的策略，在包含 n 个节点的集群中，这种简单方案平均需要 $\frac{n+1}{2}$ 次尝试即可定位到主节点，该效率对小型集群而言已能满足需求。

通过简单的优化手段，可进一步提升请求路由至主节点的效率。集群节点通常能获取当前主节点的网络地址 —— 因 AppendEntries 请求的报文会携带主节点的身份信息。当非主节点接收到客户端请求时，可选择以下两种处理方式之一：

我们推荐的方案（LogCabin 亦采用此方案）：该节点拒绝请求，若已获知主节点地址，则将其返回给客户端。客户端可基于该地址直接重新连接主节点，后续请求便能以最优效率执行。该方案的实现仅需编写少量额外代码，因为客户端原本就需在主节点故障时，重新连接集群中的其他节点。
备选方案：该节点将客户端的请求代理至主节点。该方案在部分场景下实现更简便，例如，若客户端可连接任意节点执行读请求（见 6.4 节），那么由节点代理客户端的写请求，可避免客户端为仅有的写操作，单独维护一条至主节点的专属连接。

Raft 还必须防止过期的主节点信息造成客户端请求的无限期阻塞。系统中的主节点信息可能在主节点、从节点及客户端侧全部失效，具体情况如下：

主节点侧：某一节点可能仍处于主节点状态，但若其并非集群当前的有效主节点，就可能无意义地阻塞客户端请求。例如，某主节点与集群其他节点发生网络分区，但仍能与特定客户端保持通信；若无额外机制，该节点因无法将日志条目复制至其他任何节点，会永久阻塞该客户端的请求。而此时集群中，可能已存在一个更高任期的新主节点，该节点能与集群多数节点通信，且可完成客户端请求的提交。因此 Raft 规定：若主节点在选举超时时间内，未能向集群多数节点完成一轮成功的心跳交互，便会主动退位；此举可让客户端重新选择其他节点进行请求重试。
从节点侧：从节点会记录主节点的身份信息，以便为客户端执行请求重定向或代理操作。当从节点发起新的选举，或集群的任期发生变更时，必须立即丢弃该过期的主节点信息；否则可能造成客户端请求的无意义阻塞（例如，两个节点可能互相向对方重定向客户端请求，导致客户端陷入无限循环）。
客户端侧：若客户端与主节点（或任意特定节点）的连接中断，只需随机选择集群中的其他节点重试即可。若执意尝试连接最后一次记录的主节点，一旦该节点发生故障，会造成不必要的请求延迟。

6.3 实现线性化语义

截至目前的实现中，Raft 为客户端提供至少一次语义：复制状态机可能会多次执行同一命令。例如，客户端向主节点提交某条命令，主节点将该命令追加至自身日志并完成条目提交，却在向客户端返回响应前发生故障。由于客户端未收到任何确认信息，会将该命令重新提交给新的主节点；而新主节点又会将此命令作为新条目追加至日志并完成提交。如此一来，即便客户端仅希望命令执行一次，实际却会被执行两次。即便无客户端主动重提交，若网络层出现客户端请求的重复转发，命令同样可能被多次执行。

该问题并非 Raft 所独有，绝大多数有状态分布式系统都会遇到。但至少一次语义对共识类系统而言尤为不适，因为这类系统的客户端通常需要更强的一致性保证。命令重复执行引发的问题往往表现得较为隐蔽，客户端难以自行恢复，最终会导致计算结果错误、系统状态异常，或二者同时发生。图 6.2 展示了结果错误的典型场景：某状态机提供分布式锁服务，客户端发起加锁请求后未收到确认，再次请求时却无法获取锁，原因是其第一次的加锁请求实际已执行成功。状态异常的典型场景则是自增操作：客户端期望某值自增 1，实际却自增了 2 次及以上。而网络层面的请求重排与客户端并发操作，还可能引发更为意外的结果。

图 6.2 命令重复执行引发错误结果的示例
客户端向复制状态机提交一条获取锁的命令，其首次发起的命令已成功获取锁，但客户端始终未收到确认响应。当客户端重试该请求时，会发现锁已被占用。

Raft 的设计目标之一，便是实现线性化语义，从根源上规避此类问题。在线性化语义下，每个操作都会在调用发起与响应返回之间的某个时间点瞬时执行且仅执行一次。这是一种强一致性模型，客户端极易理解，且该模型明确禁止命令被多次处理。

要在 Raft 中实现线性化语义，服务器需对重复请求做过滤处理。核心思路是：服务器持久化保存客户端操作的执行结果，利用该结果跳过同一请求的多次执行。具体实现方式为：为每个客户端分配一个唯一标识，客户端为自身发起的每一条命令分配唯一序列号；服务器的状态机为每个客户端维护一个会话，该会话会跟踪针对该客户端已处理的最新序列号，以及对应的执行结果。当服务器收到某条命令时，若检测到其序列号已被处理过，会直接向客户端返回结果，而不会重新执行该命令。

基于上述重复请求过滤机制，Raft 即可实现线性化语义：Raft 日志为所有服务器定义了命令的串行执行顺序，每条命令会在其首次出现在 Raft 日志中的时刻，瞬时且仅执行一次；而该命令后续在日志中出现的所有重复条目，都会被状态机按上述规则过滤掉。

该方案还可自然扩展，以支持单客户端的并发请求处理：只需对客户端会话的存储结构做调整，不再仅跟踪最新的序列号与对应结果，而是维护一个序列号 - 执行结果的键值对集合。客户端每次发起请求时，需在请求中携带自身尚未收到执行结果的最小序列号；服务器状态机收到该请求后，会丢弃所有比该序列号更小的执行结果记录。

但受限于存储资源，会话无法被永久保存，服务器最终必须对长期无活动的客户端会话执行过期清理。这一操作会带来两个新问题：服务器如何就客户端会话的过期时间达成共识？以及如何处理会话被过早过期、但实际仍在活跃的客户端？

首先，服务器必须就会话的过期时间达成共识，否则各节点的状态机会出现数据不一致。例如，某一服务器对某客户端的会话执行了过期清理，后续便会重新执行该客户端的重复命令；而集群中其他服务器仍保留该会话，会过滤掉这些重复命令 —— 最终导致复制状态机的全局不一致。因此，会话的过期清理逻辑必须是确定性的，这一点与状态机的常规操作要求完全一致。目前有两种可行的实现方案：一是为服务器维护的会话数量设置上限，采用最近最少使用（LRU）策略淘汰过期会话；二是基于集群协商一致的时间源，触发会话的过期清理。LogCabin 采用的是第二种方案：主节点为每一条追加至 Raft 日志的命令附加自身的当前时间戳，服务器在提交该日志条目时，会就该时间戳达成共识；随后状态机便基于该确定性的时间戳，对非活跃的客户端会话执行过期清理。而活跃的客户端会在空闲期主动发送保活请求。

6.4 更高效地处理只读查询

客户端的只读命令仅对复制状态机进行查询，不会对其做出修改。因此自然会产生一个问题：这类查询是否可以绕开 Raft 日志？毕竟 Raft 日志的设计初衷，是按统一顺序将状态变更复制到集群各节点的状态机中。绕开日志能带来可观的性能收益 —— 只读查询在诸多应用中均为高频操作，而向日志追加条目所需的同步磁盘写入，本身是耗时操作。

但若无额外的防护措施，绕开日志会导致只读查询返回过期结果。例如，某任领导者若与集群其他节点发生网络分区，集群剩余节点可能会选举出新的领导者，并向 Raft 日志提交新的条目。如果这个被分区的领导者在未与其他节点交互的情况下响应只读查询，返回的结果就是过期的，且不满足线性一致性。线性一致性要求，读操作的结果必须反映出该读操作发起后某个时刻的系统状态；每一次读操作，至少要返回最新已提交写操作的执行结果。（允许返回过期读结果的系统，仅能保证串行化特性，这是一种更弱的一致性级别。）已有第三方 Raft 实现因过期读问题出现故障，因此该问题需要重点关注。

所幸，我们可以在绕开 Raft 日志处理只读查询的同时，依然保证线性一致性。要实现这一目标，领导者需执行以下步骤：

若领导者尚未将其当前任期内的任一条目标记为已提交，则等待该操作完成。领导者完备性原则保证了领导者拥有所有已提交条目，但是在任期开始之初，可能无法确定具体是哪些条目。为明确这一点，领导者需要提交一个自身任期内的条目。Raft 的处理方式是，让每位领导者在任期开始时，向日志中提交一条空操作（no-op）条目。该空操作条目一经提交，领导者的 commitIndex 在其任期内，就将始终不低于集群中其他所有节点的 commitIndex。
领导者将当前的 commitIndex 保存至本地变量 readIndex（读取索引），该值将作为查询操作所基于的状态版本的下界。
领导者需要确保自身未被未知的新任领导者取代。其会发起一轮新的心跳，并等待集群多数节点的确认响应。一旦收到这些响应，领导者即可确定：在发送心跳的时刻，集群中不存在任期更大的领导者。因此，彼时的 readIndex，是集群中所有节点曾记录过的最大提交索引。
领导者等待自身的状态机推进至至少与 readIndex 对应的位置，此时的状态足以满足线性一致性的要求。
最后，领导者针对自身的状态机执行该查询，并将结果回复给客户端。

关于第 2、4 点可能有个疑问：领导者将当前的 commitIndex 保存至本地变量 readIndex 有啥用？提交 no-op 空条目后 commitIndex 不是等于 readIndex？都提交到状态机了吧，为啥有 “待自身的状态机推进至至少与 readIndex 对应的位置” 这种说法？

原因：
关于提交日志条目到状态机，就像交给一个消息队列一样，队列里面的日志条目最终会应用到状态机，但不是立即应用，状态机的实际运行进度，只由另一个独立指标决定 —— 最后应用索引（Last Applied Index）。
所以一个只读查询到达时，状态机里面会存在这样一段时间窗口：日志条目已经复制到多数派集群并且完成提交（commitIndex 更新），但是这个提交的日志条目可能还没有在状态机应用（Last Applied Index < commitIndex），如果直接返回结果的话会导致客户端接收到 Raft 集群已提交的消息却查不到对应数据；但如果无限制延迟查询的话，若此时集群又接收到新的写操作日志条目并提交，会导致 commitIndex 不断增大，若以动态的 commitIndex 为基准等待，执行查询时获取到的并不是查询发起时的状态结果，而可能是被新的日志条目覆盖后的结果。

因此不能立即执行查询返回结果，也不能没有限制地延后执行查询。

解决方案：
Raft 的方案是处理客户端只读查询请求时，Leader 接收请求后，不会立即执行查询，而是先暂存该请求（新 Leader 则需要先完成本任期 no-op 空条目提交，以确保 commitIndex 为集群全局可靠值）；
在处理该请求的这一刻，给每个只读查询分配一个局部变量 readIndex，记录当前的 readIndex = commitIndex（冻结固定的状态基准，让等待有明确终止条件），随后先通过心跳包确认 Leader 仍为合法主节点，保证 readIndex 对应的日志已在集群共识提交；返回状态允许包含后续已应用日志。
再等待 Last Applied Index 达到 readIndex；当 Last Applied Index 达到 readIndex 后，通过读写锁互斥让应用日志的线程短暂阻塞，原子性执行查询并拿到结果（可同步 / 异步返回给客户端），锁释放后应用线程立刻继续异步应用后续的日志条目。
期间集群运行不受任何影响，系统依旧可以接受新的日志条目并完成提交，让 commitIndex 持续增大。

这种方式比将只读查询作为新条目提交至日志的方式更高效，因为它避免了同步磁盘写入。为进一步提升效率，领导者可平摊确认自身领导权的开销：对于已累积的任意数量的只读查询，仅需发起一轮心跳即可完成领导权确认。

跟随者也可协助分担只读查询的处理工作。这不仅能提升系统的读吞吐量，还能将负载从领导者转移，让领导者可以处理更多的读写请求。但若无额外防护措施，这些由跟随者处理的读操作，同样存在返回过期数据的风险。例如，与集群发生分区的跟随者，可能长时间无法从领导者处接收新的日志条目；即便跟随者收到了领导者的心跳，该领导者也可能已被取代，只是自身尚未知晓。要安全处理读请求，跟随者可向领导者发起请求，仅获取当前的 readIndex（领导者会执行上述 1-3 步）；随后，跟随者可针对自身的状态机执行上述 4-5 步，处理所有已累积的只读查询。

LogCabin 在领导者节点上实现了上述算法，且在高负载场景下，会将心跳的开销平摊至多个只读查询。目前，LogCabin 的跟随者节点暂不处理只读请求。

6.4.1 利用时钟减少只读查询的消息交互

前文提出的只读查询处理方案，可在异步模型中实现线性一致性（该模型中时钟、处理器及消息的运行速率均无约束）。该安全等级的实现依赖通信交互：每批只读查询均需向集群半数以上节点发送一轮心跳包，这会增加查询的延迟。本节后续将介绍一种替代方案，该方案通过时钟机制使只读查询彻底避免消息发送。目前 LogCabin 尚未实现此方案，除非为满足性能需求确有必要，否则不建议采用。

若要以时钟替代消息实现只读查询，可通过常规的心跳机制实现一种租约机制^[33]。当领导者的心跳包得到集群多数节点的确认后，即可认定在约一个选举超时时间内，不会有其他节点成为新的领导者，并据此续期自身租约（见图 6.3）。在租约有效期内，领导者可直接响应只读查询，无需进行任何额外的通信交互。（第 3 章介绍的领导权转移机制支持领导者提前交接，交接前领导者需先让自身租约失效。）

图 6.3：
利用时钟替代消息实现只读查询时，领导者将通过常规的心跳机制维护租约。当领导者的心跳得到集群多数节点的确认后，会将自身租约有效期延长至「起始时间 + 选举超时时间 + 时钟漂移上限」，因为从节点在此之前不会触发选举超时。领导者在租约有效期内，可无需进行任何通信，直接处理只读查询请求。

该租约方案要求集群中所有服务器的时钟漂移存在上限约束（即在指定时间段内，任意服务器的时钟走时速率，均不超过其他服务器的该上限倍）。确定并维持该上限值在实际运维中存在诸多挑战 —— 例如进程调度、垃圾回收暂停、虚拟机迁移，或为实现时间同步进行的时钟速率调整，均会对其造成影响。若该前提假设无法满足，系统可能会返回任意过期的数椐。

所幸可通过一项简单的扩展方案，提升对客户端的一致性保障：即便在异步模型假设下（即时钟出现异常时），每个客户端仍能看到复制状态机的状态呈单调递增演进，即实现顺序一致性。例如，客户端不会先看到日志索引 n 对应的状态，在切换至其他服务器后，却只能看到日志索引 n-1 对应的状态。该保障的实现方式为：服务器在向客户端返回的每一个响应中，均附带当前状态机状态对应的日志索引；客户端需跟踪自身已获取结果对应的最新日志索引，并在每次发起请求时将该信息传递给服务器。若服务器接收到某客户端的请求时，发现该客户端已见过的日志索引高于自身的最后应用日志索引，则暂不处理该请求。

6.5 结论

本章探讨了客户端与 Raft 集群交互过程中的若干问题。其中，线性一致性的实现与只读查询的优化这两个问题，在正确性层面的处理尤为微妙。遗憾的是，现有共识算法相关研究文献仅关注集群节点间的通信机制，却将这些重要问题排除在外。我们认为这一做法存在疏漏：一个完整的分布式系统必须实现与客户端的正确交互，否则核心共识算法所保障的一致性等级便无从体现。正如我们在实际的 Raft 落地系统中所见，客户端交互逻辑已成为系统故障的主要诱因，而我们也希望，对这些问题的深入理解能够助力规避此类问题的后续发生。