一文彻底搞懂 Raft 算法，看这篇就够了！！！

最近需要设计一个分布式系统，需要一个中间件来存储共享的信息，来保证多个系统之间的数据一致性，调研了两个主流框架 Zookeeper 和 ETCD，发现都能满足我们的系统需求。其中 ETCD 是 K8s 中采用的分布式存储，而其底层采用了 RAFT 算法来保证一致性，所以随便研究了下 RAFT 算法，这篇文章会从头到尾分析 Raft 算法的方方面面。

什么是分布式一致性 ？

分布式系统通常由异步网络连接的多个节点构成，每个节点有独立的计算和存储，节点之间通过网络通信进行协作。分布式一致性指多个节点对某一变量的取值达成一致，一旦达成一致，则变量的本次取值即被确定。

在大量客户端并发请求读/写的情况下，维护数据多副本的一致性无疑非常重要，且富有挑战。因此，分布式一致性在我们生产环境中显得尤为重要。

总结来讲，分布式一致性就是为了解决以下两个问题：

• 数据不能存在单个节点（主机）上，否则可能出现单点故障。

• 多个节点（主机）需要保证具有相同的数据。

常见分布式一致性算法

常见的一致性算法包括 Paxos 算法，Raft 算法，ZAB 算法等，

• Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，使其获得 2013 年图灵奖。自 Paxos 问世以来就持续垄断了分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性, 很多分布式一致性算法都由 Paxos 演变而来 #

• Paxos 是出了名的难懂，而 Raft 正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。

• ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）, 它应该是所有一致性协议中生产环境中应用最多的了。为什么呢？因为他是为 Zookeeper 设计的分布式一致性协议！

本文我们主要介绍 Raft 算法，后续会对其他算法进行详细介绍。

深入 Raft 算法

Raft 算法和其他分布式一致算法一样，内部采用如下图所示的复制状态机模型，在这个模型中，会利用多台服务器构成一个集群，工作流程如下图所示：

整个工作流程可以归纳为如下几步：

1. 用户输入设置指令，比如将设置 y 为 1，然后将 y 更改为 9.

2. 集群收到用户指令之后，会将该指令同步到集群中的多台服务器上，这里你可以认为所有的变更操作都会写入到每个服务器的 Log 文件中。

3. 根据 Log 中的指令序列，集群可以计算出每个变量对应的最新状态，比如 y 的值为 9.

4. 用户可以通过算法提供的 API 来获取到最新的变量状态。

算法会保证变量的状态在整个集群内部是统一的，并且当集群中的部分服务器宕机后，仍然能稳定的对外提供服务。

Raft 算法在具体实现中，将分布式一致性问题分解为了 Leader 选举、日志同步和安全性保证三大子问题，接下来我会对这三方面进行仔细讲解。

Raft 算法基础

Raft 正常工作时的流程如下图，也就是正常情况下日志复制的流程。Raft 中使用日志来记录所有操作，所有结点都有自己的日志列表来记录所有请求。算法将机器分成三种角色：Leader、Follower 和 Candidate。正常情况下只存在一个 Leader，其他均为 Follower，所有客户端都与 Leader 进行交互。

所有操作采用类似两阶段提交的方式，Leader 在收到来自客户端的请求后并不会执行，只是将其写入自己的日志列表中，然后将该操作发送给所有的 Follower。Follower 在收到请求后也只是写入自己的日志列表中然后回复 Leader，当有超过半数的结点写入后 Leader 才会提交该操作并返回给客户端，同时通知所有其他结点提交该操作。

通过这一流程保证了只要提交过后的操作一定在多数结点上留有记录（在日志列表中），从而保证了该数据不会丢失。

Raft 是一个非拜占庭的一致性算法，即所有通信是正确的而非伪造的。N 个结点的情况下（N 为奇数）可以最多容忍(N-1)/2 个结点故障。如果更多的节点故障，后续的 Leader 选举和日志同步将无法进行。

子问题 1：Leader 选举

在了解基本的工作流程之后，首先看下 Rsft 算法的第一个问题，如何选举 Leader。

1. 首次选举

如果定时器超时，说明一段时间内没有收到 Leader 的消息，那么就可以认为 Leader 已死或者不存在，那么该结点就会转变成 Candidate，意思为准备竞争成为 Leader。

成为 Candidate 后结点会向所有其他结点发送请求投票的请求（RequestVote），其他结点在收到请求后会判断是否可以投给他并返回结果。Candidate 如果收到了半数以上的投票就可以成为 Leader，成为之后会立即并在任期内定期发送一个心跳信息通知其他所有结点新的 Leader 信息，并用来重置定时器，避免其他结点再次成为 Candidate。

如果 Candidate 在一定时间内没有获得足够的投票，那么就会进行一轮新的选举，直到其成为 Leader,或者其他结点成为了新的 Leader，自己变成 Follower。

2. 再次选举

当 Leader 下线或者因为网络问题产生分区时，会导致再次选举。

• 情况 1：Leader 下线，此时所有其他节点的计时器不会被重置，直到一个节点成为了 Candidate，和上述一样开始一轮新的选举选出一个新的 Leader。

• 情况 2：某一 Follower 结点与 Leader 间通信发生问题，导致发生了分区，这时没有 Leader 的那个分区就会进行一次选举。这种情况下，因为要求获得多数的投票才可以成为 Leader，因此只有拥有多数结点的分区可以正常工作。而对于少数结点的分区，即使仍存在 Leader，但由于写入日志的结点数量不可能超过半数因此不可能提交操作。这也是为何一开始我提到 Raft 算法必须要半数以上节点正常才能工作。

下图总结了 Raft 算法中，每个节点的状态之间的变化：

• Leader：处理与客户端的交互和与 follower 的日志复制等，一般只有一个 Leader；

• Follower：被动学习 Leader 的日志同步，同时也会在 leader 超时后转变为 Candidate 参与竞选；

• Candidate：在竞选期间参与竞选；

3. 任期 Term

Raft 算法将时间分为一个个的任期（term），每一个 term 的开始都是 Leader 选举。

每一个任期以一次选举作为起点，所以当一个结点成为 Candidate 并向其他结点请求投票时，会将自己的 Term 加 1，表明新一轮的开始以及旧 Leader 的任期结束。所有结点在收到比自己更新的 Term 之后就会更新自己的 Term 并转成 Follower，而收到过时的消息则拒绝该请求。

在成功选举 Leader 之后，Leader 会在整个 term 内管理整个集群。如果 Leader 选举失败，该 term 就会因为没有 Leader 而结束。

4. 投票

在投票时候，所有服务器采用先来先得的原则，在一个任期内只可以投票给一个结点，得到超过半数的投票才可成为 Leader，从而保证了一个任期内只会有一个 Leader 产生（Election Safety）。

在 Raft 中日志只有从 Leader 到 Follower 这一流向，所以需要保证 Leader 的日志必须正确，即必须拥有所有已在多数节点上存在的日志，这一步骤由投票来限制。

在介绍投票规则之前，先简单介绍下日志的格式，方便理解：

如上图所示，日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

投票由一个称为 RequestVote 的 RPC 调用进行，请求中除了有 Candidate 自己的 term 和 id 之外，还要带有自己最后一个日志条目的 index 和 term。Candidate 首先会给自己投票，然后再向其他节点收集投票信息，收到投票信息的节点，会利用如下规则判断是否投票：

• 首先会判断请求的 term 是否更大，不是则说明是旧消息，拒绝该请求。

• 如果任期 Term 相同，则比较 index，index 较大则为更加新的日志；如果任期 Term 不同，term 更大的则为更新的消息。如果是更新的消息，则给 Candidate 投票。

由于只有日志在被多数结点复制之后才会被提交并返回，所以如果一个 Candidate 并不拥有最新的已被复制的日志，那么他不可能获得多数票，从而保证了 Leader 一定具有所有已被多数拥有的日志（Leader Completeness），在后续同步时会将其同步给所有结点。

子问题 2：日志同步

工作流程

Leader 选出后，就开始接收客户端的请求。Leader 把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader 将这条日志应用到它的状态机并向客户端返回执行结果。

某些 Followers 可能没有成功的复制日志，Leader 会无限的重试 AppendEntries RPC 直到所有的 Followers 最终存储了所有的日志条目。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

实际处理逻辑

Leader 会给每个 Follower 发送该 RPC 以追加日志，请求中除了当前任期 term、Leader 的 id 和已提交的日志 index，还有将要追加的日志列表（空则成为心跳包），前一个日志的 index 和 term。具体可以参考官方论文中的描述：

在接到该请求后，会进行如下判断：

1. 检查 term，如果请求的 term 比自己小，说明已经过期，直接拒绝请求。

2. 如果步骤 1 通过，则对比先前日志的 index 和 term，如果一致，则就可以从此处更新日志，把所有的日志写入自己的日志列表中，否则返回 false。

这里对步骤 2 进行展开说明，每个 Leader 在开始工作时，会维护 nextIndex[] 和 matchIndex[] 两个数组，分别记录了每个 Follower 下一个将要发送的日志 index 和已经匹配上的日志 index。每次成为 Leader 都会初始化这两个数组，前者初始化为 Leader 最后一条日志的 index 加 1，后者初始化为 0，每次发送 RPC 时会发送 nextIndex[i] 及之后的日志。

在步骤 2 中，当 Leader 收到返回成功时，则更新两个数组，否则说明 follower 上相同位置的数据和 Leader 不一致，这时候 Leader 会减小 nextIndex[i]的值重试，一直找到 follower 上两者一致的位置，然后从这个位置开始复制 Leader 的数据给 follower，同时 follower 后续已有的数据会被清空。

这里减少 nextIndex 的值有不同的策略，可以每次减一，也可以减一个较大的

值，或者是跨任期减少，用于快速找到和该结点相匹配的日志条目

在复制的过程中，Raft 会保证如下几点：

• Leader 绝不会覆盖或删除自己的日志，只会追加 （Leader Append-Only），成为 Leader 的结点里的日志一定拥有所有已被多数节点拥有的日志条目，所以先前的日志条目很可能已经被提交，因此不可以删除之前的日志。

• 如果两个日志的 index 和 term 相同，那么这两个日志相同 （Log Matching），第二点主要是因为一个任期内只可能出现一个 Leader，而 Leader 只会为一个 index 创建一个日志条目，而且一旦写入就不会修改，因此保证了日志的唯一性。

• 如果两个日志相同，那么他们之前的日志均相同，因为在写入日志时会检查前一个日志是否一致，从而递归的保证了前面的所有日志都一致。从而也保证了当一个日志被提交之后，所有结点在该 index 上提交的内容是一样的（State Machine Safety）。

子问题 3：安全性保障（核心）

Raft 算法中引入了如下两条规则，来确保了

• 已经 commit 的消息，一定会存在于后续的 Leader 节点上，并且绝对不会在后续操作中被删除。

• 对于并未 commit 的消息，可能会丢失。

多数投票规则

在上面投票环节也有介绍过，一个 candidate 必须获得集群中的多数投票，才能被选为 Leader；而对于每条 commit 过的消息，它必须是被复制到了集群中的多数节点，也就是说成为 Leader 的节点，至少有 1 个包含了 commit 消息的节点给它投了票。

而在投票的过程中每个节点都会与 candidate 比较日志的最后 index 以及相应的 term，如果要成为 Leader，必须有更大的 index 或者更新的 term，所以 Leader 上肯定有 commit 过的消息。

提交规则

上面说到，只要日志在多数结点上存在，那么 Leader 就可以提交该操作。但是 Raft 额外限制了 Leader 只对自己任期内的日志条目适用该规则，先前任期的条目只能由当前任期的提交而间接被提交。 也就是说，当前任期的 Leader，不会去负责之前 term 的日志提交，之前 term 的日志提交，只会随着当前 term 的日志提交而间接提交。

这样理解起来还是比较抽象，下面举一个例子，该集群中有 S1 到 S5 共 5 个节点，

• 初始状态如 (a) 所示，之后 S1 下线；

• (b) 中 S5 从 S3 和 S4 处获得了投票成为了 Leader 并收到了一条来自客户端的消息，之后 S5 下线。

• (c) 中 S1 恢复并成为了 Leader，并且将日志复制给了多数结点，之后进行了一个致命操作，将 index 为 2 的日志提交了，然后 S1 下线。

• (d) 中 S5 恢复，并从 S2、S3、S4 处获得了足够投票，然后将已提交的 index 为 2 的日志覆盖了。

这个例子中，在 c 状态，由于 Leader 直接根据日志在多数节点存在的这个规则，将之前 term 的日志提交了，当该 Term 下线后，后续的 Leader S5 上线，就将之前已经 commit 的日志清空了，导致 commit 过的日志丢失了。

为了避免这种已提交的日志丢失，Raft 只允许提交自己任期内的日志，也就是不会允许 c 中这种操作。（c）中可能出现的情况有如下两类：

• （c）中 S1 有新的客户端消息 4，然后 S1 作为 Leader 将 4 同步到 S1、S2、S3 节点，并成功提交后下线。此时在新一轮的 Leader 选举中，S5 不可能成为新的 Leader，保证了 commit 的消息 2 和 4 不会被覆盖。

• （c）中 S1 有新的消息，但是在 S1 将数据同步到其他节点并且 commit 之前下线，也就是说 2 和 4 都没 commit 成功，这种情况下如果 S5 成为了新 Leader，则会出现（d）中的这种情况，2 和 4 会被覆盖，这也是符合 Raft 规则的，因为 2 和 4 并未提交。

Raft 相关扩展

1. 日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft 采用对整个系统进行 snapshot 来解决，snapshot 之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行 snapshot，并且只能对已经提交的日志记录进行 snapshot。

Snapshot 中包含以下内容：

• 日志元数据。最后一条已提交的 log entry 的 log index 和 term。这两个值在 snapshot 之后的第一条 log entry 的 AppendEntries RPC 的完整性检查的时候会被用上。

• 系统当前状态。上面的例子中，x 为 0，y 为 9。

当 Leader 要发给某个日志落后太多的 Follower 的 log entry 被丢弃，Leader 会将 snapshot 发给 Follower。或者当新加进一台机器时，也会发送 snapshot 给它。

做 snapshot 既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次 snapshot。

2. 集群成员变更

很多时候，集群需要对节点进行维护，这样就会涉及到节点的添加和删除。为了在不停机的情况下， 动态更改集群成员，Raft 提供了下面两种动态更改集群成员的方式：

• 单节点成员变更：One Server ConfChange

• 多节点联合共识：Joint Consensus

动态成员变更存在的问题

在 Raft 中有一个很重要的安全性保证就是只有一个 Leader，如果我们在不加任何限制的情况下，动态的向集群中添加成员，那么就可能导致同一个任期下存在多个 Leader 的情况，这是非常危险的。

如下图所示，从 Cold 迁移到 Cnew 的过程中，因为各个节点收到最新配置的实际不一样，那么肯能导致在同一任期下多个 Leader 同时存在。

比如图中此时 Server3 宕机了，然后 Server1 和 Server5 同时超时发起选举：

• Server1：此时 Server1 中的配置还是 Cold，只需要 Server1 和 Server2 就能够组成集群的 Majority，因此可以被选举为 Leader

• Server5：已经收到 Cnew 的配置，使用 Cnew 的配置，此时只需要 Server3，Server4，Server5 就可以组成集群的 Majority，因为可以被选举为 Leader

也就是说，以 Cold 和 Cnew 作为配置的节点在同一任期下可以分别选出 Leader。

基于此，Raft 提供了两种集群变更的方式来解决上面可能出现的问题。

单节点成员变更

单节点成员变更，就是保证每次只往集群中添加或者移除一个节点，这种方式可以很好的避免在变更过程中多个 Leader 的问题。

下面我们可以枚举一下所有情况，原有集群奇偶数节点情况下，分别添加和删除一个节点。在下图中可以看出，如果每次只增加和删除一个节点，那么 Cold 的 Majority 和 Cnew 的 Majority 之间一定存在交集，也就说是在同一个 Term 中，Cold 和 Cnew 中交集的那一个节点只会进行一次投票，要么投票给 Cold，要么投票给 Cnew，这样就避免了同一 Term 下出现两个 Leader。

变更的流程如下：

1. 向 Leader 提交一个成员变更请求，请求的内容为服务节点的是添加还是移除，以及服务节点的地址信息

2. Leader 在收到请求以后，回向日志中追加一条 ConfChange 的日志，其中包含了 Cnew，后续这些日志会随着 AppendEntries 的 RPC 同步所有的 Follower 节点中

3. 当 ConfChange 的日志被添加到日志中是立即生效（注意：不是等到提交以后才生效）

4. 当 ConfChange 的日志被复制到 Cnew 的 Majority 服务器上时，那么就可以对日志进行提交了

以上就是整个单节点的变更流程，在日志被提交以后，那么就可以：

1. 马上响应客户端，变更已经完成

2. 如果变更过程中移除了服务器，那么服务器可以关机了

3. 可以开始下一轮的成员变更了，注意在上一次变更没有结束之前，是不允许开始下一次变更的。

多节点联合共识

对于同时变更多个节点的情况， Raft 提供了多节点的联合共识算法，这里采用了两阶段提交的思想。

主要步骤分为下面三步：

1. Leader 收到 Cnew 的成员变更请求，然后生成一个 Cold,new 的 ConfChang 日志，马上应用该日志，然后将日志通过 AppendEntries 请求复制到 Follower 中，收到该 ConfChange 的节点马上应用该配置作为当前节点的配置。

2. 在将 Cold,new 日志复制到大多数节点上时，那么 Cold,new 的日志就可以提交了，在 Cold,new 的 ConfChange 日志被提交以后，马上创建一个 Cnew 的 ConfChange 的日志，并将该日志通过 AppendEntries 请求复制到 Follower 中，收到该 ConfChange 的节点马上应用该配置作为当前节点的配置。

3. 一旦 Cnew 的日志复制到大多数节点上时，那么 Cnew 的日志就可以提交了，在 Cnew 日志提交以后，就可以开始下一轮的成员变更了。

这里有几个概念比较拗口，这里解释一下：

• Cold,new：这个配置是指 Cold，和 Cnew 的联合配置，其值为 Cold 和 Cnew 的配置的交集，比如 Cold 为[A, B, C]， Cnew 为[B, C, D]，那么 Cold,new 就为[A, B, C, D]

• Cold,new 的大多数：是指 Cold 中的大多数和 Cnew 中的大多数。

结合下面的图，我们可以走一遍整个集群的变更过程，在多点联合共识的规则之下，每一个任期之中不会出现两个 Leader。

1. Cold,new 日志在提交之前，在这个阶段，Cold,new 中的所有节点有可能处于 Cold 的配置下，也有可能处于 Cold,new 的配置下，如果这个时候原 Leader 宕机了，无论是发起新一轮投票的节点当前的配置是 Cold 还是 Cold,new，都需要 Cold 的节点同意投票，所以不会出现两个 Leader。也就是 old 节点不可能同时 follow 两个 leader。

2. Cold,new 提交之后，Cnew 下发之前，此时所有 Cold,new 的配置已经在 Cold 和 Cnew 的大多数节点上，如果集群中的节点超时，那么肯定只有有 Cold,new 配置的节点才能成为 Leader，所以不会出现两个 Leader

3. Cnew 下发以后，Cnew 提交之前，此时集群中的节点可能有三种，Cold 的节点（可能一直没有收到请求）， Cold,new 的节点，Cnew 的节点，其中 Cold 的节点因为没有最新的日志的，集群中的大多数节点是不会给他投票的，剩下的持有 Cnew 和 Cold,new 的节点，无论是谁发起选举，都需要 Cnew 同意，那么也是不会出现两个 Leader

4. Cnew 提交之后，这个时候集群处于 Cnew 配置下运行，只有 Cnew 的节点才可以成为 Leader，这个时候就可以开始下一轮的成员变更了。

作者：码老思

链接：https://juejin.cn/post/7218915344130359351

来源：稀土掘金