深入理解Raft共识算法：核心机制与工程优化

Raft是分布式下的一种共识算法，因为算法清晰、简单而被众多分布式中间件所使用（例如Etcd、Kafka、RocketMQ）。

然而，当认真了解过Raft后，你会发现整个算法的机制相当复杂精妙，而且十分值得学习和记录。

数据结构与规则

Raft之所以简单、清晰，一大原因是Raft算法规定了一部分明确的数据结构与需要遵循的规则。

当然，这些数据结构与规则需要结合，甚至完全搞懂后续的机制后，才能被理解并发挥作用。

状态

持久化状态

以下是所有节点都将存储的持久化状态：

参数	解释
currentTerm	已知最新任期（首次启动为0，单调递增）
votedFor	当前任期投给的Candidate的id，没有为空
log[]	日志条目。每个日志保护索引、任期号和指令

易失性状态

以下是所有节点的易失性状态：

参数	解释
commitIndex	已知的已提交的最高日志索引（初始为0，单调递增）
lastApplied	已经被应用的最高的日志索引（初始为0，单调递增）

以下是Leader上的易失性状态：

参数	解释
nextIndex[]	每个节点一对一的下一个要发送日志索引
matchIndex[]	每个节点一对一的已知已复制的最高日志索引

RPC

请求投票RPC

以下是Candidate在发起请求投票RPC时，请求的数据结构：

参数	解释
term	候选人的任期号
candidateId	候选人id
lastLogIndex	候选人最新日志索引
lastLogTerm	候选人最新日志对应任期号

以下是对应接收到的响应的数据结构：

返回值	解释
term	当前任期号，候选人会根据term更新任期号
voteGranted	候选人是否赢得了此张选票

追加日志RPC

由Leader调用，用于日志复制或心跳，以下是请求的数据结构：

参数	解释
term	领导人的任期号
leaderId	领导者的id，便于将请求重定向到Leader（客户端请求可能不是直接发送到Leader而是发送给Follower）
prevLogIndex	最新日志的前一个的索引
prevLogTerm	最新日志的前一个的任期号
entries[]	需要追加的日志条目（作为心跳则为空，为了效率可以设为一次性发送多条）
leaderCommit	领导人的已知的已提交的最高的日志索引

以下是响应的数据结构：

返回值	解释
term	当前任期号，方便领导人更新任期号
success	prev相关参数匹配返回true，代表接收追加日志

规则

所有节点的规则

如果 commitIndex > lastApplied，那么lastApplied递增，并应用 log[lastApplied] 到状态机
如果接收的RPC请求或响应中，term > currentTerm，则令 currentTerm = term，并切换为Follower身份

Leader规则

一旦变为Leader，将定时发送心跳RPC（空的追加日志）给其他节点，防止Follower超时
如果接收到客户端请求，在本地追加日志，并等到日志应用后响应客户端（注意从追加到应用需要前置条件，详见后续机制）
如果Follower的最新日志索引大于等于nextIndex，则发送从nextIndex后的所有日志：
- 如果成功，则更新Follower的nextIndex和matchIndex
- 如果日志不匹配失败，则递减nextIndex并重试
如果存在N满足 N > commitIndex，使得大多数节点的 matchIndex[i] >= N 且 log[N].term == currentTerm 成立，则令 commitIndex = N

Follower规则

响应Candidate和Leader的请求
在选举超时后没有收到当前领导人的心跳或追加日志，或者给某个Candidate投了票，则自己变为候选人

Candidate规则

从变为Candidate开始，立刻开始选举：
- 自增任期号（currentTerm）
- 投票给自己
- 重置选举超时时间
- 发送请求投票的RPC给其他节点
如果接收到大多数节点的选票，则转变为Leader
如果收到Leader的追加日志RPC，则变为Follower
如果选举超时，则开始下一轮选举

请求投票规则

如果 term < currentTerm，那么响应voteGranted为false
如果voteFor为空或candidateId，且候选人的日志至少和自己一样新，那么响应voteGranted为true

追加日志规则

如果Leader的term比自己小，那么响应success为false
如果接收者发现prev相关参数无法在日志中完全匹配到，那么响应success为false
如果已存在的日志和新接收的日志存在冲突，那么删除从冲突发生的索引之后的所有日志
如果追加日志在接收者中不存在，那么就追加
如果leaderCommit大于commitIndex，那么设commitIndex为：leaderCommit或entries最新的索引，取最小值

节点身份

分布式是多节点的系统。在Raft中，每个节点都扮演三种身份之一：

Leader：领导节点，专门响应外部客户端请求
Follower：追随节点，只响应Leader和Candidate的内部请求
Candidate：候选节点，在选举新的Leader时产生的临时身份

绝大多数情况下，系统只有一个Leader而其他节点是Follower，Candidate只在选举新Leader时产生。

任期

在Raft中，时间被分为多个任期，每个节点都会存储一个任期号。

任期号是一个不断递增的整数，在Raft中充当了时钟信息。

每个任期都从选举开始，Raft保证一个任期内只有一个Leader节点。

领导选举

在Raft算法中，节点间通过RPC调用来发送内部请求。

正常情况下，Leader会周期性地发送心跳包给Follower来表明地位和状态。

如果一个Follower一段时间没有收到任何消息，那么就视为没有Leader并发起选举。

Follower会增加任期号并变为Candidate，向其他节点发送请求给自己投票。

Candidate身份会一直保持直到三种事件发生：

自己赢得选举
其他节点赢得选举
选举未产生Leader而超时

在选举期间，Candidate可能会收到其他节点的投票请求，然而Candidate只会听从任期号比自己大的投票请求。

当选举导致多个Candidate胜出时会导致超时，Raft的解决办法是给每个节点加一个随机的超时时间来减少这种可能。

日志复制

在Raft算法中，只有Leader才能负责处理客户端的请求。

当客户端发送一个影响状态机的请求时，Leader会将这个状态机指令添加到自己的日志中。

然后，Leader会并行发送追加日志的请求到所有Follower，要求Follower复制这个日志。

如果超过半数节点正常响应了Leader的请求，那么Leader会将这条日志的状态称为已提交。

接下来Leader会应用这个指令并向客户端返回响应。

Follower何时应用这些指令？答案是当Follower通过commitIndex知道之前的日志被提交时，才会应用这些指令。

Raft的每条日志包含了自增索引、任期号和指令。Raft的日志可以保证：

如果索引和任期号相同，那么指令也相同
如果索引和任期号相同，那么之前的日志也相同

第一条保证可以理解，因为任期内的指令压根不会更改。

第二条保证来自追加日志的请求：Leader发送的请求中，既包含了新的日志，还包含了前一个日志的索引和任期号。如果Follower找不到前一个日志，就会拒绝接收这个新的日志。

在Raft算法中，为了保证日志的一致性，Leader会强制覆盖Follower的日志。

Leader会针对每一个Follower维护一个nextIndex，代表需要发送的下一个日志记录。当Leader当选后，会将nextIndex设为自己最后一条日志的索引+1。当Leader被Follower拒绝后，会尝试减小nextIndex并继续，直到找到一致的地方。最后Follower会删掉不一致的日志，并加入Leader的日志。

安全性

选举限制

选举时，Raft规定只有存储了所有已提交日志的Candidate才能担任Leader，避免Leader的强制覆盖导致丢失已提交的日志。

Raft通过投票来阻止这种不安全的选举，具体来说，Raft在投票阶段会让节点进行判断：拒绝日志没有自己新的投票请求。

提交限制

当新Leader上台时，可能会遇到旧任期的可提交日志（超过半数节点存在这条日志，且小于当前任期）。

Raft规定，Leader不能直接提交旧任期的日志。Leader只能通过提交新日志的方式，来间接提交旧任期的可提交日志。

因为直接提交旧任期的日志并不能保证这些日志不被覆盖，提交这个日志导致的Follower状态机变化更可能导致系统共识出错。

通过新任期的日志提交来间接提交旧任期日志，相当于用新任期保护了旧任期的日志，保证了状态机指令应用的安全性。

领导人完整性

在Raft算法下，Leader一定不会丢失已提交日志，这一特性也称为领导人完整性特性。

我们来利用反证法推断一下：

如果一个Leader丢失了已提交日志，那么这个节点，一定不包含曾经的某条已提交日志，同时后续当选了Leader。

当选Leader要求收到半数以上节点的投票，同时提交日志也要求半数以上节点存储了这一条日志。

那么如果半数以上的节点已经存储了这条日志的情况下，不可能让这个日志没有自己新的节点担任Leader。

也就是说这个节点压根不可能拿到半数以上节点的投票，所以也不可能担任Leader，与假设不符。

节点崩溃

当Leader崩溃时，往往意味着选举和日志覆盖等策略。

而当Follower或Candidate节点崩溃后，Raft的策略是进行无限的RPC重试；同时Raft需要RPC保证幂等性，也就是说RPC生效但未响应的崩溃也不会产生问题。

配置更新

当集群的配置发生变化时，往往会出现问题，例如可能同时存在新集群的Leader和旧集群的Leader。

Raft规定，集群的配置变化需要使用两阶段方法，也叫做共同一致（Joint Consensus），使得集群在配置变化的过程中依然可以正常响应：

当新的配置（C-new）发送给Leader时，Leader将存储一个过渡配置（C-old,new）
未来，Leader将利用新旧两套配置做出所有决定（也就是说新配置和旧配置都必须通过）
当过渡配置提交后，两个集群都将需要根据新旧两套配置才能做出决定
Leader会创建一个新配置的日志（C-new）并复制给集群
当新配置提交后，旧的配置就会自动失效

当新的节点加入集群时，通常没有任何日志，那么这些节点需要一段时间来同步日志。Raft会让这些节点以无投票权的身份加入集群，等到日志追上了再参与配置更新。这种特殊节点的身份也被称为学习者（Learner），本质是一种被剥夺了部分权力的Follower。

既然存在新旧两套配置，那么旧配置的Leader可能并不是新配置的一个节点（这种情况比较抽象）。那么Leader会在提交新配置后退位变为Follower。

在集群配置更新后，不在新配置中的节点将不再收到心跳。这些节点会发起选举，并尝试担任新的Leader，两个集群如果不停争夺Leader会扰乱整个集群。

为了避免这种情况，服务器需要忽略Leader存在时的RPC投票请求。具体来说，节点在没有超时时将不会参与投票，而Leader发送的心跳包又能保证集群的正常运行。

日志压缩

Raft集群的正常运行离不开日志，但是不断增长的日志又成为了集群的负担之一。

Raft使用快照来进行日志压缩，每个节点都会独立地创建快照，快照包含以下内容：

最新的索引
最新的任期
状态机的最新值
最新的配置

一旦节点完成了一次快照，那么就可以删除掉最新索引前的所有日志和快照了。

虽然节点是独立地创建快照，但是Leader仍然需要偶尔将快照同步给部分Follower。因为某些Follower的同步速度过慢，或者刚加入集群，它想复制的日志可能已经因为创建快照被删除掉了。这时候Leader就会将最新的快照发给Follower，让Follower尽快同步。

而这个同步快照的RPC，是一个分块的RPC（分块是因为状态机的值可能有很多个），也被称为安装快照RPC：

请求：

参数	解释
term	领导人的任期号
leaderId	领导人的Id，便于重定向
lastIncludedIndex	快照最新日志的索引
lastIncludedTerm	快照最新日志的任期
offset	分块的字节偏移量
data[]	一段从偏移量开始的原始字节
done	标记是否为最后一个分块

响应：

结果	解释
term	当前任期号，便于Leader更新自己

接收这个快照的节点必须遵循如下的流程：

如果 term < currentTerm，那么立即响应
如果offset为0，那么创建一个新的快照
在指定的offset写入data的内容
如果done为false，那么等待更多数据
保存快照文件，丢弃索引小的任何快照
如果现有的日志里存在快照对应的日志，那么保留其后的日志并响应
丢弃整个日志
使用快照重置状态机和集群配置

对于Raft规定所有节点都可以独立产生快照这一点，可能会存在一些疑问：为什么不是只有Leader创建快照，然后发送给Follower呢？

性能考虑：发送快照需要网络带宽，而且Follower自己创建快照更方便
复杂性考虑：Leader需要发送快照，还要发送追加日志，这会让同步机制变得复杂且缓慢

Raft对于性能的考虑还给出了几点建议：

快照的创建不应该太经常，也不该太稀少，简单的策略是日志达到了阈值大小才触发快照
快照的写入需要一定时间，但对于新的指令我们也应该尽量减少阻塞。一个策略是可以利用写时复制技术进行加速

客户端交互

当客户端想要和Raft集群通信时，往往是随机选一个节点发送请求，然而这个节点不一定就是Leader节点。这个节点会拒绝这个请求，并返回Leader的正确信息，而Leader崩溃时，请求会超时，并触发客户端的重试。

Raft的一大目标是实现线性化语义，这需要保证状态机指令执行的幂等性。但是，当Raft的Leader提交日志后崩溃的情况下，客户端会因为响应超时进行重试。解决方案是给这些指令赋予一个唯一的序列号（例如哈希值），让状态机对比最新的已经执行指令，如果执行过则直接返回。

对于客户端的只读请求，直接返回数据可能会存在一个问题：Leader可能已经罢黜了，但是它还不知道。这时候可能会返回脏数据。

Raft通过两个措施来处理这个问题：

Leader在上台后会提交一条空的日志，这样可以确保旧任期的日志被正确提交了
Leader在响应只读请求前，需要和大多数节点通信一次，确保自己的Leader地位是稳固的

工程优化

预投票

如果部分节点因为网络原因，与Leader一直通信不畅，那么会不断发起选举并在一个少数派的分区里选出新的Leader。

当后续这些节点连接到Leader所在集群后，会导致集群发起一次”虚惊一场”的选举：虽然这些节点任期号可能更高，但是日志却不够新，也无法担任Leader。这些节点的加入只会让Leader集群的任期号提升，然后所有节点再发起一次选举。

但是这种抖动会影响集群的性能与可用性，所以引出了一个预投票机制（Pre-Vote）：

当节点要开始选举前，先发起一轮预投票
接收到预投票RPC的节点，如果任期内收到了Leader的心跳则直接拒绝
而只有预投票成功后，才能真正触发选举

也就是说，预投票机制通过一轮自检，避免了不必要的选举。

领导权转移

有时候Leader所在节点需要维护，或者需要一个更合适的节点担任Leader，就需要领导权转移。

整个过程是这样设计的：

当前Leader不再接收新的客户端请求
利用日志复制，使目标节点的日志与自己一致
当前Leader发送TimeoutNow请求到目标节点，直接触发超时选举

目标服务器在收到TimeoutNow请求后，很有可能优先选举并担任Leader。这时它会给前任Leader发送一条包含任期号的消息，使其下台。

单节点变更

共同一致（Joint Consensus）虽然有诸多好处，但是实现起来相对复杂。

单节点变更是一种更简单的配置变更方式，流程如下：

Leader将C-new作为一条日志发送给所有节点
节点收到配置后立即生效，无需等待提交
当日志同步到C-new的大多数节点时，Leader将日志标记为已提交
变更完成，可以继续进行下一轮新变更

单节点变更通过鸽巢原理，保证了新旧配置的交集必然存在，投票就不会产生多个Leader。

然而，为了正确性考虑，新当选的Leader需要发送一条空日志来确认提交，才能进行同步。在可用性问题上，Joint Consensus相比单节点变更往往也有更强大的表现。总的来说，单节点变更虽然简单，但还是更推荐用在偶尔添加或删除节点的场景。

算法缺陷

单点问题

在Raft算法下，Leader的职责相当大，系统的压力远大于Follower，容易成为系统的单点瓶颈。

拜占庭问题

Raft只能解决正常情况下的分布式，如果节点”撒谎”，集群中出现虚假信息，这时候Raft就束手无策了。

多Leader问题

Raft算法一直都是以单个Leader的情况来考虑，如果需要一个多Leader的集群，需要使用Multi-Raft或者其他办法。