概述

Raft 是一种分布式共识算法，相比于 Paxos，它最大的特性就是易于理解。为了达到这个目标，Raft 主要做了两方面的事情：

• 问题分解：把共识算法分为三个子问题，分别是领导者选举(leaderelection)、日志复制(log replication)和安全性(safety)。
• 状态简化：对算法做出一些限制，减少状态数量和可能产生的变动。
  

复制状态机

相同的初始状态 + 相同的输入 = 相同的结束状态，即在多个节点上，从相同的初始状态开始，执行相同的一串命令，会产生相同的最终状态。

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

可以说，我们使用共识算法，就是为了实现复制状态机。一个分布式场景下的各节点间，就是通过共识算法来保证命令序列的一致，从而始终保持它们的状态一致，从而实现高可用（投票选主是一种特殊的命令）。

其实复制状态机的功能可以更加强大，比如两个副本一个采用行存储的数据结构存储数据，另一个采用列存储，只要它们初始数据相同，并持续发给他们相同的命令，那么同一时刻从两个副本中读取到的结果也是一样的，这就是一种 HTAP 的实现方法（比如 TiDB）。

状态简化

在任何时刻，每一个服务器节点都处于 leader、follower 或 candidate 这三个状态之一。相比于 Paxos，这一点极大地简化了算法的实现。因为 Raft 只需考虑状态的切换，而不用像 Paxos 那样考虑状态之间的共存和互相影响。

Raft 把时间分割成任意长度的任期(term)，任期用连续的整数标记，每一段任期从一次选举开始。在某些情况下，一次选举无法选出 leader（比如两个节点收到了相同的票数），在这种情况下，这一任期会以没有 leader 结束，一个新的任期（包含一次新的选举）会很快重新开始。Raft 保证在任意一个任期内，最多只有一个 leader。

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

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

服务器之间通信的时候会交换当前任期号：

• 如果一个服务器上的当前任期号比其他的小，该服务器会将自己的任期号更新为较大的那个值。
• 如果一个 candidate 或者 leader 发现自己的任期号过期了，它会立即回到 follower 状态。
• 如果一个节点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求。

领导者选举

Raft 内部有一种心跳机制，如果存在 leader，那么它就会周期性地向所有 follower 发送心跳，来维持自己的地位。如果 follower 一段时间没有收到心跳，那么它就会认为系统中没有可用的 leader 了，然后开始进行选举。

开始一个选举过程后，follower 先增加自己的当前任期号，并转换到 candidate 状态。然后投票给自己，并且并行地向集群中的其他服务器节点发送投票请求(RequestVote RPC)。

最终会有三种结果：

• 它获得超过半数选票赢得了选举 -> 成为主并开始发送心跳。
• 其他节点赢得了选举 -> 收到新 leader 的心跳后，如果新 leader 的任期号不小于自己当前的任期号，那么就从 candidate 回到 follower 状态。
• 一段时间之后没有任何获胜者 -> 每个 candidate 都在一个自己的随机选举超时时间后增加任期号开始新一轮投票。

为什么会没有获胜者？比如有多个 folower 同时成为 candidate，得票太过分散，没有任何一个 candidate 得票超过半数。

对于没有成为 candidate 的 follower 节点，对于同一个任期，会按照先来先得的原则投出自己的选票。比如系统刚开始，所有节点都是 follower，第一个意识到没有 leader 的 follower 会增加自己的任期号并转换到 candidate 状态。然后投票给自己，并且并行地向集群中的其他节点发送投票请求。这个先来优势往往会让它成为 leader。

日志复制

leader 被选举出来后，开始为客户端请求提供服务。但客户端怎么知道新 leader 是哪个节点呢？

客户端随机向一个节点（或者老 leader）发送请求，这时会有三种情况：

• 这个节点正好是 leader，不用再找了，执行指令即可。
• 这个节点是 follower，那么它可以通过心跳得知 leader 的 ID，然后告知客户端该找谁。
• 这个节点宕机了，没有响应，那么客户端会再随机向另一个节点发送请求，重复几次，总会找到 leader。

leader 接收到客户端的指令后，会把指令作为一个新的条目追加到日志中去。一条日志需要具有三个信息：

• 状态机指令
• leader 的任期号
• 日志号（日志索引）

leader 并行发送 AppendEntries RPC 给 follower，让它们复制该条目。当该条目被超过半数的 follower 复制后，leader 就可以在本地执行该指令并把结果返回客户端。
我们把本地执行指令，也就是 leader 应用日志与状态机这一步，称作提交。

在此过程中，leader 或 follower 随时都有崩溃或缓慢的可能性，Raft 必须要在有宕机的情况下继续支持日志复制，并且保证每个副本日志顺序的一致（以保证复制状态机的实现）。这里分为三种情况进行探讨：

• follower 缓慢
• follower 宕机
• leader 宕机

①如果有 follower 因为某些原因没有给 leader 响应，那么 leader 会不断地重发追加条目请求（AppendEntries RPC），哪怕 leader 已经回复了客户端（即 leader 已经把日志复制给了超过半数的节点，已经提交了，但不能放弃落后的 follower，leader 会不断重发，直至该 follower 追上日志）。
②如果有 folower 崩溃后恢复，这时 Raft 追加条目的一致性检查生效，保证 follower 能按顺序恢复崩溃后的缺失的日志。

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

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

通过这种机制，leader 在当权之后就不需要任何特殊的操作来使日志恢复到一致状态。leader 只需要进行正常的操作，然后日志就能在回复 AppendEntries 一致性检查失败的时候自动趋于一致。leader 从来不会覆盖或者删除自己的日志条目（Append-Only）。

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

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

安全性

领导者选举和日志复制两个子问题实际上已经涵盖了共识算法的全程，但这两点还不能完全保证每一个状态机会按照相同的顺序执行相同的命令。因此 Raft 通过几个补充规则完善整个算法，使算法可以在各类宕机问题下都不出错。这些规则包括：

• leader 宕机处理：选举限制
• leader 宕机处理：新 leader 是否提交之前任期内的日志条目
• follower 和 candidate 宕机处理
• 时间与可用性限制

①leader 宕机处理：选举限制

如果一个 follower 落后了 leader 若干条日志（但没有漏一整个任期），那么下次选举中按照领导者选举里的规则，它依旧有可能当选 leader。它在当选新 leader 后就永远也无法补上之前缺失的那部分日志，从而造成状态机之间的不一致。所以需要对领导者选举增加一个限制，保证被选出来的 leader 一定包含了之前各任期的所有被提交的日志条目。

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

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

• 如果两份日志最后条目的任期号不同，那么任期号大的日志更“新”。
• 如果两份日志最后条目的任期号相同，那么日志较长的那个更“新”。

②leader 宕机处理：新 leader 是否提交之前任期内的日志条目
一旦当前任期内的某个日志条目已经存储到过半的服务器节点上，leader 就知道该日志条目可以被提交了。

follower 的提交触发：下一个 AppendEntries RPC：心跳 or 新日志（心跳可以看成是特殊的 AppendEntries RPC，只是没有日志体）

只有 leader 当前任期内的日志条目才通过计算副本数目的方式来提交。

一旦当前任期的某个日志条目以这种方式被提交，那么由于日志匹配特性，之前的所有日志条目也都会被间接地提交。

③follower 和 candidate 宕机处理

follower 和 candidate 崩溃后的处理方式比 leader 崩溃要简单得多，并且两者的处理方式是相同的。
如果 follower 或 candidate 崩溃了，那么后续发送给他们的 RequestVote 和 AppendEntriesRPCs 都会失败。
Raft 通过无限的重试来处理这种失败，如果崩溃的机器重启了，那么这些 RPC 就会成功完成。
如果一个服务器在完成了一个 RPC，但是还没有相应的时候崩溃了，那么它重启之后就会再次收到同样的请求（Raft 的 RPC 都是幂等的）。

④时间与可用性限制

Raft 算法整体不依赖客观时间，也就是说，哪怕因为网络或其他因素，造成后发的 RPC 先到，也不会影响Raft 的正确性。
只要整个系统满足下面的时间要求，Raft 就可以选举出并维持一个稳定的 leader：

广播时间(broadcastTime) << 选举超时时间(electionTimeout) << 平均故障时间(MTBF)

广播时间和平均故障时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPC 需要接受并将信息落盘，所以广播时间大约是 0.5ms 到 20ms，取决于存储的技术。因此，选举超时时间可能需要在 10ms 到 500ms 之间，大多数服务器的平均故障间隔时间都在几个月甚至更长。

集群成员变更

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

比如上图为三节点（S1~S3）集群扩容到五节点（S1~S5），S1 和 S2 为老配置集群，S3、S4 和 S5 为新配置集群。老配置为三节点，S1 和 S2 可以选出一个 leader（2/3），新配置为五节点，S3、S4 和 S5 可以选出一个 leader（3/5）。

这时就出现脑裂问题了，Raft 采用一种两阶段的方法实现自动化配置变更，避免这个问题。

集群先切换到一个过渡的配置，称之为联合一致（jointconsensus），配置信息作为一个日志体包装为一个普通的AppendEntries RPC，发送给所有 follower。

• 第一阶段，leader 发起新旧两个配置的并集，使整个集群进入联合一致状态。这时，所有 RPC 都要在新旧两个配置中都达到大多数才算成功。
• 第二阶段，leader 发起新配置，使整个集群进入新配置状态。这时，所有 RPC 只要在新配置下能达到大多数就算成功。
  

集群成员变更还有三个补充规则：

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