Raft 算法

简介

Raft 算法实际上是 Multi-Paxos 的一个变种，通过新增两个约束：

1. 追加日志约束 ：Raft 中追加节点的日志必须是串行连续的，而 Multi-Paxos 中则可以并发追加日志（实际上 Multi-Paxos 的并发也只是针对日志追加，最后应用到内部 State Machine 的时候还是必须保证顺序）。
2. 选主的限制：Raft 中只有那些拥有最新、最全日志的节点才能当选 Leader 节点，而 Multi-Paxos 由于允许并发写日志，因此无法确定一个拥有最新、最全日志的节点，因此可以选择任意一个节点作为 Leader，但是选主之后必须要把 Leader 节点的日志补全。

基于这两个限制，Raft 算法的实现比 Multi-Paxos 更加简单易懂，不过由于 Multi-Paxos 的并发度更高，因此从理论上来说 Multi-Paxos 的性能会更好一些，但是到现在为止业界也没有一份权威的测试报告来支撑这一观点。

对比一下 Multi-Paxos 和 Raft 下集群中可能存在的日志顺序：

可以看出，Raft 中永远满足这样一个约束：follower log 一定会是 leader log 的子集并且顺序一定是连续的，而 Multi-Paxos 则不一定满足这个约束，日志记录通常是乱序的。

raft 算法主要通过两种方法来提高可理解性

1. 问题分解 raft 算法把问题分解成了选主/Leader Election[^12]，日志复制[^13]，安全性[^14]和成员关系变化这几个子问题。

   • 选主/Leader Election[^12]在一个领袖节点发生故障之后必须重新给出一个新的领袖节点

   • 日志复制[^13]领袖节点从客户端接受操作请求，然后讲操作日志复制到集群中的其他服务器上，并且强制要求其他服务器的日志必须和自己的保持一致

   • 安全性[^14]

     安全性 raft 的安全特性是下文提到的状态机安全原则，如果一个服务器已经将给定索引位置的日志条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目

   • 成员关系变化配置发生变化的时候，集群能够继续工作

2. 减少状态空间 raft 算法通过减少需要考虑的状态数量来简化状态空间。这将是的整个系统更加一致并且尽可能的消除不确定性。

‍

基本概念

一个 raft 协议组织的集群中，一共包含如下 3 类角色

• Leader 领袖
• Candidate 候选人
• Follower 群众

Term 任期

raft 算法将事件划分为任意个不同长度的任期

在 raft 的世界里，每个任期的开始都是一次领导人的选举，如果一个候选人赢得了选举，那么它就会在该任期内的剩余时间内担当领导人，如果选票被瓜分，在次任期内没有选出领导人就结束了，则系统自动进入下一任期，重新开始选举，raft 算法保证在给定的一个任期内最多只有一个领导人，某些任期会在选举失败的情况下，存在没有领导人的状态。

每个 raft 节点各自都在本地维护了一个当前任期值，触发这个数字变化主要由两个场景：开始选举和与其他节点交换信息，当节点之间进行通信时，会相互交换当前的任期号。如果一个节点（包括领导人）的当前任期号比其他节点的任期号小，则将本地的任期号自觉的更新为较大的任期号，如果一个候选人或者领导人意识到它的任期号过期了（比别人小），那么它还会立刻切换成群众状态, 如果一个节点收到的请求所携带的任期号时过期的，那么该节点就会拒绝响应本次请求。

‍

选主/Leader Election

节点启动时，默认处于 Follower 的状态，所以开始时所有节点均是 Follower，那么什么时候触发选主呢？Raft 用“心跳”的方式来保持主从节点的联系，如果长时间没有收到主节点的心跳，则开始选主。这里会涉及到两个时间：

• 心跳间隔，主节点隔多长时间发送心跳信息
• 等待时间(election timeout)，如果超过这个时间仍然没有收到心跳，则认为主节点宕机。一般每个节点各自在 150～300ms 间随机取值。

当一个节点在等待时间内没有收到主节点的心跳信息，它首先将自己保存的 term 增加 1 并进入 Candidate 状态。此时它会先投票给自己，然后并行发送 RequestVote 消息给其它所有节点，请求这些节点投票给自己。然后等待直到以下 3 种情形之一发生：

1. 收到大于一半的票，当选为主节点
2. 有其它节点当选了主节点，此时会收到新的主节点的心跳
3. 过了一段时间后依旧没有当选，此时该节点会尝试开始新一轮选举

对于第一种情形，Candidate 节点需要收到集群中与自己 term 相同的所有节点中大于一半的票数（当然如果节点 term 比自己大，是不会理睬自己的选举消息的）。节点投票时会采取先到先得的原则，对于某个 term，最多投出一票（后面还会再对投票加一些限制）。这样能保证某个 term 中，最多只会产生一个 leader。当一个 Candidate 变成主节点后，它会向其它所有节点发送心跳信息，这样其它的 Candidate 也会变成 Follower。

第二种情形是在等待投票的过程中，Candidate 收到其它主节点的心跳信息（只有主节点才会向其它节点发心跳），且信息中包含的 term 大于等于自己的 term，则当前节点放弃竞选，进入 Follower 状态。当然，如前所说，如果心跳中的 term 小于自己，则不予理会。

第三种情形一般发生在多个 Follower 同时触发选举，而各节点的投票被分散了，导致没有 Candidate 能得到多数票。超过投票的等待时间后，节点触发新一轮选举。理论上，选举有可能永远平票，Raft 中由于各个节点的超时时间是随机的，实际上平票不太会永远持续下去。

怎样才能具有成为领导人的资格？

• 没有包含所有已提交日志条目的节点成为不了领导人
• 日志条目只有一个流向：从 leader 流向 follower。领导人永远不会覆盖已经存在的日志条目

‍

日志复制

Log Replication 分为两个主要步骤：复制/Replication 和 提交/Commit。当一个节点被选为主节点后，它开始对外提供服务，收到客户端的 command 后，主节点会首先将 command 添加到自己的日志队列中，然后并行地将消息发送给其它所有的节点，在确保消息被安全地复制（下文解释）后，主节点会将该消息提交到状态机中，并返回状态机执行的结果。如果 follower 挂了或因为网络原因消息丢失了，主节点会不断重试直到所有从节点最终成功复制该消息。

日志结构示例如下：

日志由许多条目（log entry）组成，条目顺序编号。条目包含它生成时节点所在的 term （小方格中上方的数字），以及日志的内容。当一个条目被认为安全地被复制，且提交到状态机时，我们认为它处于“已提交（committed）”状态。

是否将一个条目提交到状态机是由主节点决定的。Raft 要保证提交的条目会最终被所有的节点执行。当主节点判断一个条目已经被复制到大多数节点时，就会提交 /Commit 该条目，提交一个条目的同时会提交该条目之前的所有条目，包括那些之前由其它主节点创建的条目（还有些特殊情况下面会提）。主节点会记录当前提交的日志编号 (log index)，并在发送心跳时带上该信息，这样其它节点最终会同步提交日志。

上面说的是“提交”，那么“复制”是如何进行的？在现实情况下，主从节点的日志可能不一致（例如在消息到达从节点前主节点挂了，而从节点被选为了新的主节点，此时主从节点的日志不一致）。Raft 算法中，主节点需要处理不一致的情况，它要求所有的从节点复制自己的所有日志（当然下一小节会介绍额外的限制，保证复制是安全的）。

要复制所有日志，就要先找到日志开始不一致的位置，如何做到呢？Raft 当主节点接收到新的 command 时，会发送 AppendEntries 让从节点复制日志，不一致的情况也会在这时被处理（AppendEntries 消息同时还兼职作为心跳信息）。

‍

下面是日志不一致的示例：

‍

主节点需要为每个从节点记录一个 nextIndex，作为该从节点下一条要发送的日志的编号。当一个节点刚被选为主节点时，为所有从节点的 nextIndex 初始化自己最大日志编号加 1（如上图示例则为 11）。接着主节点发送 AppendEntries 给从节点，此时从节点会进行一致性检查（Consistency Check）。

所谓一致性检查，指的是当主节点发送 AppendEntries 消息通知从节点添加条目时，需要将新条目 A 之前的那个条目 B 的 log index 和 term，这样，当从节点收到消息时，就可以判断自己第 log index 条日志的 term 是否与 B 的 term 相同，如果不相同则拒绝该消息，如果相同则添加条目 A。

主节点的消息被某个从节点拒绝后，主节点会将该从节点的 nextIndex 减一再重新发送 AppendEntries 消息。不断重试，最终就能找主从节点日志一致的 log index，并用主节点的新日志覆盖从节点的旧日志。当然，如果从节点接收 AppendEntries 消息后，主节点会将 nextIndex 增加一，且如果当前的最新 log index 大于 nextIndex 则会继续发送消息。

通过以上的机制，Raft 就能保证：

• 如果两个日志条目有相同的 log index 和 term，则它们的内容一定相同。
• 如果两个节点中的两个条目有相同的 log index 和 term，则它们之前的所有日志一定相同

日志复制的流程总结

1. 客户端向 Leader 发送写请求
2. Leader 将写请求解析成操作指令追加到本地日志文件中
3. Leader 为每个 Follower 广播 AppendEntries RPC
4. Follower 通过一致性检查，选择从哪个位置开始追加 Leader 的日志条目
5. 一旦日志项提交成功，Leader 就将该日志条目对应的指令应用(apply)到本地状态机，并向客户端返回操作结果
6. Leader 后续通过 AppendEntries RPC 将已经成功（在大多数节点上）提交的日志项告知 Follower
7. Follower 收到提交的日志项后，将其应用到本地状态机

‍

安全性

要保证所有的状态机有一样的状态，单凭前几节的算法还不够。例如有 3 个节点 A、B、 C，如果 A 为主节点期间 C 挂了，此时消息被多数节点（A，B）接收，所以 A 会提交这些日志。此时若 A 挂了，而 C 恢复且被选为主节点，则 A 已经提交的日志会被 C 的日志覆盖，从而导致状态机的状态不一致。所以 raft 会对选主进行限制。

选主的限制

在所有的主从结构的一致性算法中，主节点最终都必须包含所有提交的日志。有些算法在从节点不包含所有已提交日志的情况下，依旧允许它当选为主节点，之后从节点会将这些日志同步到主节点上。但是 Raft 采用了简单的方式，只允许那些包含所有已提交日志的节点当选为主节点。

注意到节点当选主节点要求得到多数票，同时一个日志被提交的前提条件是它被多数节点接收，综合这两点，说明选举要产生结果，则至少有一个节点在场，它是包含了当前已经提交的所有日志的。

因此，Raft 算法在处理要求选举的 RequestVote 消息时做了限制：消息中会携带 Candidate 的 log 消息，而在投票时，Follower 会判断 Candidate 的消息是不是比自己“更新”（下文定义），如果不如自己“新”，则拒绝为该 Candidate 投票。

Raft 会首先判断两个节点最后一个 log entry 的 term，哪个节点的对应的 term 更大则代表该节点的日志“更新”；如果 term 的大小一致，则谁的 log entry 更多谁就“更新”。

注意，加了这个限制后，选出的节点不会是“最新的”，即包含所有日志；但会是足够新的，至少比半数节点更新，而这也意味着它所包含的日志都是可以被提交的（但不一定已经提交）。

Follower 与 Candidate 宕机

这部分 Raft 的处理非常简单，如果 Follower 或 Candidate 宕机，主节点会不断进行重试，即不管挂不挂都照常发送 AppendEntries 消息。这样当 Follower 或 Candidate 恢复之后，日志仍能被正确复制。有时 Follower 会处理消息却在响应前宕机，此时由于 Raft 算法是幂等的，因此重复发送也没有关系。