Raft算法比Paxos更容易让人理解，也更简单。Paxos算法缺少标准的Multi-Paxos实践规范，不同团队直接实现差异大。 状态空间负责，容易引入bug。

而Raft算法，基于Paxos算法，在状态空间上进行了简化，只有一下三个状态，状态转移如图所示：

1. Follower
2. Candidate
3. Leader

同时也只有三种RPC:

1. RequestVote：由候选者在选举期间发起
2. AppendEntries： 由Leader发起，用于复制日志条目，并兼作心跳机制
3. InstallSnapshot：用于在服务器之间传输快照

如果服务器未在合理时间内收到 RPC 的响应，它会进行重试；为了获得最佳性能，服务器还会并行地发起多个 RPC。

时间片划分

在 Raft 算法中，时间被划分为一系列逻辑上的任期（term），每个任期以一次选举开始：若选举成功，则由唯一选出的Leader管理集群直至该任期结束；若选举失败，则该任期在没有Leader的情况下直接结束。

由于网络延迟或分区等原因，不同服务器可能在不同时间感知到任期的切换，甚至可能完全错过某次选举或整个任期。为此，Raft 引入任期作为逻辑时钟，帮助服务器识别和处理过时的信息（如陈旧的Leader）。

每台服务器本地维护一个单调递增的当前任期号。当服务器之间通信时，会交换彼此的任期号：若发现自己的任期号小于对方，就立即更新为更大的值。相应地：

• 如果候选者或Leader发现自己任期已过时，会立即转为Follower状态；
• 如果服务器收到任期号过期的请求，会直接拒绝该请求。

Leader选举

Raft 采用心跳机制来追踪Leader的选举过程，使用空的AppendEntries RPC 来实现。如果一个Follower在一个选举timeout之间没有收到联系，则会假设没有Leader，并开始新的选举。

开始选举，Follower会再加自己自己的任期号，并且将状态转换为Candidate。并且会投自己一票，然后会发送一个 RequestVote RPC 给其他服务器，要求对当前任期进行投票。 上面的状态会一直持续，直到三件事的发生：

1. 票数过半，赢得选举
2. 其他服务器赢得选举
3. 在选举期间没有任何服务器赢得选举

Candidate 获得大多数的投票会赢得选举。每台服务器在任期内最多为一个Candidate投票。确保了统一任期内最多只有一个节点赢得选举。

其他服务器赢得选举，会发送一个AppendEntries RPC。这时候需要比较任期号，如果RPC中任期号大于本节点的任期号，则会认为是合法的，否则是不合法的。

如果没有任何服务器赢得选举，则会在超时之后增加自己的任期号，重新进行选举。为了避免这个分裂的情况重复发生，每个节点中超时时间的数值会在一定范围内随机选取 这样只有一个服务器会率先超时，最后会赢得选举，因为先超时了，先投自己一票，随后会发送RPC进行拉票。

论文里另一个讨论的点是采用排名系统来进行选举，高排名的服务器会赢得选举。然而，发现这种方法会引发一些微妙的可用性问题：例如，当一个高排名的服务器发生故障时， 低排名的服务器可能需要等待超时后再次成为候选者；但如果它过早地这样做，就可能打断正在进行的Leader选举进程，从而阻碍系统选出Leader。 论文中对这一算法进行了多次调整，但每次调整之后，又会出现新的边界情况（corner cases）。 最终，得出结论：基于随机重试的方案更加直观、易于理解，也避免了上述复杂性。

关于投票规则的细节，在后文阐述。

日志复制

一旦选举成功，就会开始处理客户端的请求。Leader会将命令追加到日志条目中，发起RPC AppendEntries 给其他服务器，并等待响应。超过半数的服务器复制成功，则会确认成功，在状态机中执行日志命令，相应客户端。

如果某些Follower发生崩溃、运行缓慢，或者网络数据包丢失，Leader会无限重试 AppendEntries RPC（即使在已经向客户端返回响应之后），直到所有Follower最终都成功存储了该日志条目。

只有已经提交（commit）的日志，可以被安全应用到状态机,大多数的服务器如果复制了该日志，则会认为已经提交了。 这一提交操作同时也会提交该Leader日志中所有先前的条目，包括由之前Leader创建的条目。

raft 保证了下面两条性质：

• 如果两个不同日志中的条目具有相同的索引（index）和任期号（term），那么它们所存储的命令是相同的。
• 如果两个不同日志中的条目具有相同的索引和任期号，那么这两个日志在该索引之前的所有条目都完全一致。

第一条是因为Leader在给定任期内对某个日志索引最多只会创建一个条目，并且日志条目在其日志中的位置永远不会改变。

第二条AppendEntries RPC执行的一个简单一致性检查来保证。当Leader发送 AppendEntries RPC 时， 会在请求中包含紧邻新条目之前那个日志条目的索引和任期号。 如果Follower在其本地日志中找不到具有相同索引和任期号的条目，它就会拒绝接收这些新条目

上面两条性质起到了归纳的作用，让Leader确信：Follower的日志在新增条目之前的部分与其自身日志完全一致。

但是还是存在一些特殊情况，一个Follower可能缺少Leader日志中已有的条目，也可能包含Leader日志中没有的额外条目，或者同时存在这两种情况。日志中的缺失条目和多余条目可能跨越多个任期。可以参考下面的图片和说明。

在 Raft 中，Leader通过强制让Follower的日志与自己的日志保持一致来处理不一致性。这意味着Follower日志中存在冲突的条目将被Leader日志中的条目覆盖。

Leader必须找到两个日志中最后一个一致的日志条目，然后删除Follower日志中该位置之后的所有条目，并将自己日志中该位置之后的所有条目发送给该Follower。

这些操作在RPC一致性检查之后生效。

Leader为每个Follower维护一个 nextIndex 值，表示下一次将要发送给该Follower的日志条目索引。当一个Leader刚当选时，它会将所有Follower的 nextIndex 初始化为其自身日志中最后一个条目之后的索引（例如上图 中为 11）。

如果Follower的日志与Leader的日志不一致，那么在下一次 AppendEntries RPC 中，一致性检查就会失败。 在收到拒绝响应后，Leader会将该Follower的 nextIndex 值减一，并重试 AppendEntries RPC。 如此反复，直到 nextIndex 递减到某个位置，使得Leader和Follower的日志在该位置之前完全一致。

之后删除nextIndex之后的日志条目，Leader把nextIndex之后的日志条目发送给Follower。

可能的优化

当拒绝一个 AppendEntries 请求时，跟随者可以在响应中包含冲突条目的任期号，以及它在该任期内存储的第一个日志条目的索引。

领导者就可以直接将 nextIndex 递减到该任期的起始位置，从而一次性跳过该任期内所有冲突的条目； 这样，每个存在冲突的任期只需一次 AppendEntries RPC，而不是为每个冲突条目都发送一次 RPC。

不过作者认为这种优化可能并不必要，因为节点故障很少发生，而且不太可能出现大量不一致的日志条目。

安全性

在任意给定任期内当选的领导者，其日志中必定包含所有在之前任期中已提交的条目.

重要

日志条目仅沿一个方向流动——从领导者流向跟随者，而且领导者永远不会覆盖其日志中已有的条目。

选举限制

RequestVote RPC 实现了这一限制：该 RPC 包含了候选者日志的相关信息，如果投票方（即接收请求的服务器）发现自己的日志比候选者的日志更新，它就会拒绝向该候选者投票。

Raft 通过比较两个日志中最后一条条目的索引和任期号来判断哪个日志更新：

• 如果两个日志的最后条目具有不同的任期号，则任期号更大的日志更更新。
• 如果两个日志的最后条目具有相同的任期号，则日志更长（即索引更大）。

提交上一个任期的日志条目

下图的例子证明，某个旧的日志条目虽然已被大多数服务器存储，但仍可能被未来的领导者覆盖。

• 在 (a) 中，S1 是领导者，并将索引为 2 的日志条目部分地复制到其他服务器。
• 在 (b) 中，S1 崩溃；S5 在任期 3 中获得 S3、S4 和自身的选票，当选为新领导者，并在日志索引 2 处接受了一条不同的条目。
• 在 (c) 中，S5 崩溃；S1 重启并再次当选为领导者，继续进行日志复制。此时，来自任期 2 的索引 2 条目已被多数服务器存储，但它尚未被提交。
• 如果此时 S1 如 (d) 所示再次崩溃，S5 可能重新当选为领导者（获得 S2、S3 和 S4 的投票），并用自己的任期 3 的条目覆盖索引 2 处的旧条目。
• 然而，如果如 (e) 所示，S1 在崩溃前先将其当前任期（例如任期 4）的一条新日志条目成功复制到多数服务器，那么这条新条目即被视为已提交（此时 S5 无法赢得选举）。 一旦发生这种情况，该新条目之前的所有日志条目（包括之前任期的条目）也同时被提交。

关于提交上一个任期的日志条目的设计：旧任期的日志条目不能直接提交，但可以通过“当前任期的新条目被提交”而被间接提交。因为领导者会含有所有的日志条目。所以当新条目被提交时，领导者会立即将旧任期的日志条目提交。

安全性论证

这里一堆推理太多了，不细说了。

Follower和Candidate崩溃

如果一个跟随者或候选者崩溃了，那么后续发送给它的 RequestVote 和 AppendEntries RPC 请求都会失败。Raft 通过无限重试来应对这类失败：一旦崩溃的服务器重启，相应的 RPC 就能成功完成。

此外，如果某台服务器在完成 RPC 处理之后、发送响应之前发生崩溃，那么它在重启后会再次收到相同的 RPC 请求。由于 Raft 的 RPC 是幂等的（idempotent），重复处理不会造成任何问题。

例如，如果一个跟随者收到一个 AppendEntries 请求，其中包含的日志条目已经存在于它的日志中，它会直接忽略这些重复的条目。

时序和可用性

我们对 Raft 的一个基本要求是：安全性不能依赖于时序（timing）——系统不能仅仅因为某个事件发生得比预期更快或更慢，就产生错误的结果。

然而，可用性（即系统能否及时响应客户端请求）则不可避免地依赖于时序。

例如，如果消息交换所需的时间超过了服务器崩溃的典型间隔时间，那么候选者就无法持续运行足够长的时间来赢得选举；而没有稳定的领导者，Raft 就无法取得进展。

要满足下面的时序要求，可以让Raft成功选举并维持一个稳定的领导者

$$broadcastTime ≪ electionTimeout ≪ MTBF$$

在该不等式中：

• broadcastTime 是指一台服务器向集群中所有其他服务器并行发送 RPC 请求并收到响应所需的平均时间；
• electionTimeout 是上文中所述的选举超时时间；
• MTBF（Mean Time Between Failures）是指单台服务器平均无故障运行的时间。 广播时间应比选举超时时间小一个数量级，以确保领导者能够可靠地发送心跳消息，从而有效阻止跟随者发起新的选举。

同时，由于 Raft 采用随机化的选举超时机制，这一不等式也能显著降低选票分裂（split votes）的可能性。

选举超时时间又应比 MTBF 小几个数量级，以保证系统能够持续稳定地推进。

广播时间和平均故障间隔时间是底层系统固有的属性，而选举超时时间则是我们需要主动选择的参数。

Raft 的 RPC 通常要求接收方将信息持久化到稳定存储中，因此广播时间会根据所采用的存储技术不同，大致在 0.5 毫秒到 20 毫秒 之间。 因此，选举超时时间通常应设置在 10 毫秒到 500 毫秒 的范围内。

而典型服务器的 MTBF 通常为数月甚至更长，这很容易满足上述时序要求（即 $broadcastTime ≪ electionTimeout ≪ MTBF$）