Raft分布式共识算法是什么

这篇文章主要讲解了“Raft分布式共识算法是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Raft分布式共识算法是什么”吧！

Raft 算法是一类基于日志复制的分布式共识算法，旨在提供与 Multi-Paxos 共识算法相同的容错性和性能的前提下，追求更好的可理解性和工程可实现性。Paxos 算法为分布式系统面临的共识问题提供了解决思路，但其难以理解的特性一直被大家所诟病，更不用说工程实现，这也是 Raft 算法诞生的主要动因。

Raft 算法的作者认为可理解性和工程可实现性也是一个优秀分布式共识算法所应该具备的特性，并通过以下两点保证算法的可理解性：

• 问题分解 ：将分布式共识问题拆分成主节点选举、日志复制、安全点，以及成员变更 4 个独立子问题逐一进行解决。

• 简化状态 ：通过增强某些阶段的一致性程度（例如约束能够成为下一任 Leader 的参选节点条件），以减少算法需要考虑的系统状态数量。

要理解 Raft 算法的运行机制，我们应该先对其应用场景有一个感知。以一个简单的分布式 KV 系统为例，在这个系统中会有多个参与节点，其中各个节点都持有数据的完整副本。系统可以响应用户的读写请求，并且能够保证读写操作的线性一致性语义，即当用户成功写入某个 <key, value> 键值对之后，后续不论从哪个节点发起读请求，都能够读取到写入时间点之后的数据。一个典型的分布式 KV 系统往往限制只有 Leader 节点能够响应数据更新请求，但是所有的节点都能够响应读请求，因为大多数的应用场景都具备读多写少的特性。

如何保证各个节点都持有数据的完整副本是该 KV 系统所面临的问题，这也是分布式系统所面临的典型问题。惯用的解决思路是引入日志文件，每条日志对应用户的一次更新操作（也叫指令）。日志在 Leader 节点生成，并复制给集群中所有的参与节点。如果能够保证每个节点复制的日志都是完整且与 Leader 节点日志具备相同的写入顺序，那么只要在各个节点本地按序重放这些日志所承载的指令，就能够实现让各个节点的数据副本状态在未来的某个时间点达成最终一致。这也是可复制状态机（Replicated State Machines）的基本思想，如下图：

从目前来看，在这个分布式 KV 系统中我们主要面临两个问题：

1. 如何正确选举出一个 Leader 节点？

2. 如何实现日志数据从 Leader 向其它节点有序且一致的复制？

这也是 Raft 算法要解决的两个基本问题。当然，在解决这两个问题的过程中会面临许多安全问题，我们会专门用一小节去讨论这些问题。

在正式介绍 Raft 算法的运行机制之前，我们先对 Raft 算法的一些基本属性和关键特性做一个简单的介绍。

首先来看基本属性，主要包含 term 和 logIndex 这两个概念，说明如下：

• term ：中文译为“任期”，更加形象一点可以将其理解为“朝代”，而 Leader 节点就是具体某个朝代的君王（不同于实际中一个朝代可能有多任君王，这里限制一个朝代只能有一位君王），当改朝换代时对应的 term 值也会递增（初始为 0，单调递增）。

• logIndex ：Raft 算法采用日志记录用户的操作指令，并通过为每条日志分配一个 index 以维护日志的顺序性。Raft 算法要求在同一任期内 logIndex 是单调递增且不重复的，一些实现则更进一步要求在整个算法运行期间 logIndex 始终是单调递增且不重复的。

在一个分布式系统中往往需要引入时钟的概念，并且为了避免物理时钟偏差对于系统正确性的影响，分布式系统往往选用逻辑时钟。属性 term 和 logIndex 结合在一起可以充当 Raft 算法的逻辑时钟，用于衡量一条日志的时间顺序，具体会在下文进一步说明。类比时钟的概念，我们自然也就能够理解 Raft 算法为什么要限制 term 和 logIndex 必须是单调递增的，且不允许重复和被更改。

关于 logIndex 属性，还有两个特殊的位置值需要说明：

• committedLogIndex ：一条日志被标记为 committed 的条件是这条日志成功被复制到集群中过半数的节点上，lastCommittedLogIndex 小于等于 lastLogIndex。

• appliedLogIndex ：一条日志被标记为 applied 的条件是这条日志所承载的指令被成功应用到业务状态机中，lastAppliedLogIndex 小于等于 lastCommittedLogIndex，即一条能够被 applied 的日志前提一定是被 committed 的。

再来了解一下 Raft 算法的关键特性：

• Strong Leader ：一个集群在同一任期内只能包含一个 Leader 节点，日志数据仅从 Leader 节点单向流向其它 Follower 节点，这样的设计简化了对日志副本的管理，同时让算法更加易于理解。

• Leader Election ：基于随机计时器触发 Leader 选举进程，相对于固定周期的超时策略，随机化超时周期这么一个小小的改动却能更加简单和高效的解决选举分裂问题。

• Membership Changes ：基于联合共识机制处理集群节点的变更事件，在过渡期间允许两种不同的节点配置方案共存，以保证集群在节点变更期间仍然能够正常运行。

本文我们重点介绍主节点选举、日志复制，以及过程中需要考虑的一些安全点。在介绍主节点选举和日志复制机制时我们重点关注算法的运行流程，一些需要考虑的安全问题将留到安全点小节进行统一探讨。

主节点选举

Raft 算法中的节点分为三类角色：Leader、Candidate 和 Follower。一个任期内集群中的所有节点只能包含一个 Leader 节点，剩余的节点均为 Follower 节点，而 Candidate 节点是 Follower 尝试竞选成为下一任 Leader 节点的中间状态。下图演示了一个节点角色演变的过程：

Raft 算法基于心跳机制触发主节点选举进程。一个 Leader 节点在位期间会始终向所有的 Follower 节点发送心跳请求以宣示自己的权威，如果一个 Follower 节点在一段时间内没有收到来自 Leader 节点的心跳，则会认为“皇帝已经驾崩了”，于是切换状态为 Candidate 尝试谋权篡位，竞选成为下一任 Leader。

Raft 算法基于投票机制实现主节点选举，所以一个节点竞选的过程本质上就是向集群中其它节点征集选票的过程。Raft 集群中的节点一般采用 RPC 的方式进行通信，所以参选节点会向集群中的所有节点发送 RequestVote RPC 请求以征集选票（同时会为自己投上一票），请求内容如下：

• term ：参选节点的任期值（当前任期值加 1），即如果该节点成功当选 Leader 的任期值。

• candidateId ：参选节点的节点 ID。

• lastLogIndex ：参选节点本地最后一条日志对应的 logIndex 值。

• lastLogTerm ：参选节点本地最后一条日志对应的 term 值。

为保证一个任期内只有一个 Leader 节点被选出，Raft 算法要求节点在一个任期内只能投票给一个参选节点，按照先来先服务的原则。如果接收到请求的节点当前未投票给任何参选节点，则会判断请求是否满足：

1. 参选节点的 term 值大于等于当前节点的 term 值。

2. 如果 term 值相等，则参选节点的 lastLogIndex 大于等于当前节点的 lastLogIndex 值。

只有在同时满足上述两个条件时，当前节点才会为参选节点投上自己宝贵的一票，并承诺在当前任期内不会再投票给任何其它参选节点。

节点针对参选节点的 RequestVote 响应中会携带以下信息：

• term ：当前投票节点的任期值。

• voteGranted ：是否同意投票。

参选节点在一轮征集选票的过程中可能会遇到以下三种情况：

1. 参选节点赢得集群中过半数的选票。

2. 接收到的 RequestVote 响应中包含比自己任期更大的 term 值，说明已有其它节点竞选 Leader 成功。

3. 没有任何一个节点赢得选票，即本轮竞选没有任何一个节点胜出。

针对 情况一 ，说明该参选节点竞选 Leader 成功。为了防止某些节点谋权篡位，该节点需要立即向集群中的所有节点发送心跳请求以宣示自己的权威。

针对 情况二 ，如果该 Leader 节点的任期较当前节点更大，则当前节点需要转变为 Follower 节点以服从新 Leader 节点的统治，否则可以无视该“Leader”节点，继续发动革命以推翻其政权。

针对 情况三 ，说明有至少两个以上的参选节点同时发起了选举进程，并瓜分了选票，导致没有一个节点赢得过半数的选票。此时，这些节点只能在等待一段时间后继续发起一轮新的选举进程以打破这种僵持的状态。

为了尽量避免出现第三种情况，一个简单且有效的解决方案就是随机化每个节点发起选举进程的超时时间。只要这些节点不是同一时刻发动革命，那么打成平手的概率将大大降低。

关于主节点选举还有另外一个需要考虑的问题，即某些节点因为一些原因（比如网络延迟、节点负载较高等）未能正常接收到来自 Leader 节点的权威宣示通知，导致这些节点经常误认为“皇帝驾崩了”，尝试谋权篡位。按照 Raft 算法的主节点选举设计，这些“捣乱”的节点会提升 term 值以发起选举进程，但是因为大多数节点与 Leader 节点的租约是有效的，所以很多时候这些“捣乱”节点的谋权篡位计划只能以失败告终。然而，这类无谓的举动会导致对 term 值的浪费，对集群运行的稳定性构成威胁。

为了解决此类问题，我们可以将选举进程拆分为预选举和正式选举两个阶段。一个节点在发起正式选举之前必须先经过一轮预选举，预选举区别于正式选举的地方在于参选节点并不会真正递增 term 值，而是尝试以 term + 1 的任期值去试探性的征集选票。如果预选举能够成功才会真正递增 term 值，并进入正式选举环节开始征集选票，否则对集群的运行状态不会构成影响。

日志复制

在正确选举出 Leader 节点之后，接下来 Raft 算法需要解决的核心问题就剩下如何将日志数据有序的从 Leader 节点复制给集群所有的 Follower 节点，并保证各个节点上日志数据的一致性了。

Raft 算法中的日志分为两类：一类是系统运行期间内部产生的日志，比如集群节点配置变更信息；另外一类就是用户向 Raft 集群提交请求所生成的日志，这类日志会承载用户的操作指令，也是 Raft 日志的主要形式。不过 Raft 算法在执行日志复制时并不区分日志的类型，而是统一处理。

Leader 节点会以并发的形式向各个 Follower 节点复制日志数据，如果一条日志被集群中过半数的节点成功复制，则视该日志为 committed，即已提交。对于 committed 的日志，节点本地的可复制状态机会解析并应用其中所承载的指令，然后将其标记为 applied。

Raft 算法中的日志除了承载操作指令外，至少还包含 term 和 logIndex 两个基本属性（如上图），并且承诺：

1. 如果两条日志具备相同的 term 和 logIndex，则这两条日志所承载的指令必然是相同的。

2. 如果两条日志具备相同的 term 和 logIndex，则这两条日志的前置日志也是相同的，即具备相同的 term、logIndex 和指令。

关于 承诺一 ，Raft 算法要求在同一个 term 内 logIndex 必须是单调递增且不允许重复和被更改的，所以能够保证。

关于 承诺二 ，Raft 算法在发送日志复制请求时会携带前置日志的 term 和 logIndex 值（即 prevLogTerm 和 prevLogIndex），只有在 prevLogTerm 和 prevLogIndex 匹配的情况下才能成功响应请求。如果 prevLogTerm 和 prevLogIndex 不匹配，则说明当前节点可能是新加入的、或者之前服从于其它 Leader，亦或当前节点之前是 Leader 节点。为了兑现承诺二，Leader 节点需要与该 Follower 节点向前追溯找到 term 和 logIndex 匹配的那条日志，并使用 Leader 节点的日志强行覆盖该 Follower 此后的日志数据。

Leader 节点一般基于 RPC 请求的方式向目标 Follower 节点复制日志数据，对应的复制日志 AppendEntries RPC 请求内容如下：

• term ：Leader 节点的任期值。

• leaderId ：Leader 节点 ID，Follower 节点可以据此将请求重定向给 Leader 节点。

• prevLogIndex ：前置日志的 logIndex 值。

• prevLogTerm ：前置日志的 term 值。

• entries ：本次请求复制的日志数据集合，如果为空的话可以充当心跳请求。

• leaderCommit ：Leader 节点的 lastCommittedLogIndex 值。

Follower 节点关于 AppendEntries 响应的内容如下：

• term ：Follower 节点的 term 值，如果相较于 Leader 节点更大，则 Leader 节点会更新自己的 term 值并退位。

• success ：标识 Follower 节点是否成功复制请求中的日志数据。

Follower 节点在接收到 AppendEntries 请求之后会按照以下流程进行处理：

1. 如果请求中的 term 值小于自己的 term 值，说明请求来源 Leader 节点已经失效，则拒绝请求，并返回自己的 term 值；

2. 如果对应 prevLogTerm 和 prevLogIndex 的日志与本地不匹配，则拒绝请求，以兑现承诺二；

3. 如果本地存在一条日志的 logIndex 和 prevLogIndex 相等，但是对应的 term 值和 prevLogTerm 不相同，则需要删除包含这条日志的所有后继日志，以兑现承诺二。如果采用全局递增的 logIndex 设计，则不会出现此类情况；

4. 在保证 prevLogTerm 和 prevLogIndex 匹配的情况下，如果本地不包含请求中的日志数据，则往本地追加日志数据；

5. 如果请求中的 leaderCommit 相较于本地记录的 committedLogIndex 更大，则更新本地 committedLogIndex 值为 min(leaderCommit, lastLogIndex)。

在实现层面，作为 Leader 节点可以为每个 Follower 节点启动一个线程专门负责往该 Follower 节点复制日志数据并维护心跳。考虑各个 Follower 节点的负载和网络连通性，这样的设计能够保证往各个 Follower 节点复制日志数据进程是相互独立的。如果某个 Follower 节点所属的宿主机或网络出现问题，则对应的线程需要重试 AppendEntries 请求直到成功为止，但这并不会影响往其它 Follower 节点复制日志数据的进程。

安全点

上面我们介绍了 Raft 算法关于主节点选举和日志数据复制机制的设计，总的来说还是比较容易理解的。然而，到目前为止我们都是建立在一个理想运行环境下，实际运行中我们面临的情况要复杂很多，作为一个分布式共识算法，应该提供在面对复杂环境下的各种容错机制。本小节我们就一起来探讨实际运行过程中可能存在的安全问题，以及 Raft 算法是如何解决的。

Leader 节点宕机

通过前面对于主节点选举机制的介绍可知，Raft 算法会在 Leader 节点宕机时基于超时机制从集群节点中选举出一个新的 Leader 节点。设想如果新选出的 Leader 节点并未完全同步前任 Leader 节点已经 committed 的日志数据，那么按照 Raft 算法日志复制的规则，新 Leader 节点会强行覆盖集群中其它节点与自己冲突的日志数据。如果某些节点已经将这些被覆盖的日志所承载的指令应用到了自己的状态机中，那么就会导致节点之间数据的不一致，所以在执行主节点选举时不应该赋予所有的节点都有竞选成功的机会。

Raft 算法解决上述问题的思路是限制只有包含所有已经 committed 日志的节点才有机会竞选成功。这也是为什么参选节点在征集选票时，Raft 算法对于投票节点是否同意投票需要添加如下两条限制：

1. 参选节点的 term 值大于等于投票节点的 term 值。

2. 如果 term 值相等，则参选节点的 lastLogIndex 大于等于投票节点的 lastLogIndex 值。

那么这两个条件就一定能够保证新选出的 Leader 节点一定包含所有已经 committed 的日志吗？我们需要先明确以下两点：

1. 一条日志被 committed 的条件是这条日志被集群中 过半数 以上的节点成功复制。

2. 一个节点能够竞选 Leader 成功的条件是该节点赢得集群中 过半数 以上节点的选票。

所以上面这两个“过半数”能够保证至少有一个节点既包含最新的一条被 committed 的日志，同时又给参选节点投上了自己的一票。然后附加上主节点选举的约束条件，可以得出新选举出的 Leader 节点的日志一定比该节点更新，所以新选举出的 Leader 节点一定包含最新一条被 committed 的日志。

上述分析说明在 Leader 切换的过程中，新任 Leader 不会覆盖前任 Leader 已经 committed 的日志，也就不会导致数据不一致。

Leader 节点宕机除了影响主节点选举，还会影响日志复制。上面这幅时序图描述了 Raft 集群处理客户端提交指令请求并复制日志的过程，Leader 节点可能在任何阶段发生宕机，下面来探讨一下在 Leader 节点发生宕机时，Raft 算法如何保证数据的一致性。

• Leader 在将日志复制给 Follower 节点之前宕机

Leader 节点在为指令生成完日志之后会将对应的日志写入本地存储系统，然后开始并发将该日志复制给集群中所有的 Follower 节点。如果 Leader 节点在开始复制之前发生宕机，则对应的日志目前处于 uncommitted 状态。新选举出来的 Leader 节点一定不包含该日志，所以当上一任 Leader 节点从宕机中恢复并以 Follower 角色启动后，新任 Leader 会以本地的日志强行覆盖与其冲突的日志。因为该条日志对应的指令并未被应用到状态机，所以也就不会导致数据不一致。

• Leader 在将日志复制给 Follower 节点之间宕机

Leader 节点在将日志复制给 Follower 节点之间发生宕机，此时该日志处于 uncommitted 状态。这一阶段分为两种情况：

1. 复制给了集群中小部分的 Follower 节点。

2. 复制给了集群中大部分的 Follower 节点。

对于 情况一 ，新任 Leader 节点不一定包含该日志，如果包含则按照第二种情况予以处理，如果不包含则新任 Leader 会以本地的日志强行覆盖与其冲突的日志。因为该条日志对应的指令并未被应用到状态机，所以也就不会导致数据不一致。

对于 情况二 ，则新任 Leader 节点一定包含该日志，但并不知道前任 Leader 是否已经提交了该日志，所以不能依据前任 Leader 节点的状态做决策，需要继续完成对于该日志的复制。我们可以认为对于已经 committed 的日志，新任 Leader 能够确定这些日志已经或未来一定能够被集群中所有的节点成功复制，但是对于那些 uncommitted 的日志，新任 Leader 节点需要再次尝试将其复制给各个 Follower 节点，并依据自己的复制状态决定是否提交这些日志。

针对第二情况一种极端的情形就是 Leader 节点在准备提交该日志之前发生宕机。

• Leader 在响应客户端之前宕机

Leader 节点在响应客户端之前发生宕机，此时该日志在 Leader 本地已经处于 committed 状态，所以新任 Leader 本地一定包含该日志。然而，新任 Leader 可能还未被通知该日志已经被提交，但是按照 Raft 算法的日志复制机制，该日志未来一定会被新任 Leader 标记为 committed。

此种情形下，客户端会因为等待超时而误认为本次指令提交失败，所以会尝试重新提交指令，客户端需要考虑指令的幂等性问题。

Follower 或 Candidate 节点宕机

相对于 Leader 节点宕机而言，Follower 或 Candidate 节点发生宕机的处理过程要简单许多。Candidate 是节点参与竞选的中间状态，如果出现宕机只会导致该节点竞选失败，不会对集群的运行状态构成影响。Follower 节点在整个算法运行期间始终被动的接收请求，并且 Raft 算法要求当向一个 Follower 节点复制日志失败时，Leader 节点应该循环重试直到复制成功。所以，当一个 Follower 节点从宕机中恢复运行，则会从宕机的位置继续开始复制日志，而不会丢失日志。

时间层面考量

在设计一个分布式系统时我们往往需要基于时间去判断事件的先后顺序，这里的时间应该依赖于逻辑时钟而非物理时钟。前面曾提及过在整个 Raft 算法的设计中，结合 term 和 logIndex 这两个维度可以充当逻辑时钟的概念。此外，因为 Raft 算法的正常运行依赖于超时策略，所以还需要考虑以下几个层面的时间问题：

• broadcastTime ：集群机器之间的平均网络延迟。

• electionTimeout ：Raft 节点的选举超时时间。

• MTBF ：机器宕机的平均时间间隔。

如果要保证 Raft 算法的正常运行，则需要满足 broadcastTime << electionTimeout << MTBF。

前面我们介绍了 Leader 节点会周期性的向所有 Follower 节点发送心跳以宣示自己的权威，每轮心跳都是一次 RPC 请求，这中间涉及到网络的延迟开销 broadcastTime。Follower 节点如果在等待 electionTimeout 之后还未收到来自 Leader 的心跳请求则会认为“皇帝驾崩了”，于是尝试执行谋权篡位计划。所以需要保证 broadcastTime 远小于 electionTimeout，以避免网络平均延迟对于集群正常运行的影响。

此外，在 Leader 宕机与选举出新任 Leader 之间，整个集群处于无主的状态，我们应该尽可能缩短此类状态的持续时间，而控制的参数就是 electionTimeout 的最小值，所以 electionTimeout 需要在保证大于 broadcastTime 的前提下远小于一个集群中机器的平均故障间隔时间 MTBF。

网络分区问题

在一个分布式系统中，网络分区是我们无法回避的问题。对于 Raft 算法而言，当出现网络分区时会让一个 Raft 集群分裂成两个甚至多个较小的 Raft 集群，好在 Raft 仍然能够保证在网络出现分区时的数据一致性。

如上图，假设我们现在有一个包含 5 个节点的 Raft 集群，网络分区导致该集群分裂成了两个小集群 A 和 B，其中 A 包含 3 个节点（L1 是 Leader），B 包含 2 个节点（L2 是 Leader）。当我们向该集群提交指令时，因为存在两个 Leader 节点，所以节点 L1 或 L2 都有可能会响应我们的请求（节点总数为 5）：

• 如果请求发送给了 L1 节点，因为节点 L1 所属集群包含 3 个节点，所以提交给该分区的指令对应的日志存在被 committed 的可能性，此时 3 个节点均成功复制了日志。

• 如果请求发送给了 L2 节点，因为节点 L2 所属集群包含 2 个节点，所以提交给该集群的指令对应的日志因不满足过半数的条件而无法被提交。

当网络分区恢复时，因为 L1 节点的日志相对于 L2 节点更新，所以节点 L2 会主动从 Leader 角色切换为 Follower 角色，对应的未提交日志会被 L1 节点强行覆盖掉，集群数据重新恢复一致。因为整个过程中节点 L2 不会提交任何日志，所以也就不会应用任何指令到状态机，但是网络分区期间，L2 所属集群的数据状态滞后于整个集群，路由到该集群的请求读取不到最新的数据状态。

此外，还有一种导致网络分区的场景并不是因为网络本身出现问题，而是因为集群节点变更所导致。因为 Raft 的主节点选举基于多数投票机制，如果因为新节点的加入导致集群出现两个“大多数”的情况就可能会导致选举出两个 Leader 节点。为了避免此类问题，Raft 算法中提出了一种联合共识（Joint Consensus）的解决思路，允许在集群节点变更期间新旧节点配置共存。然而，事实表明联合共识机制对于工程实现并不友好，所以作者在其博士毕业 论文 中又对该机制进行了改进，通过限制一次仅允许增加或移除单个节点来简化工程实现。改进后的策略能够保证在集群节点变更期间，新旧配置中的大多数始终包含一个共同的节点，因为该共同节点只会认可一个 Leader，从而保证在集群配置变更期间不会选举出两个不同的 Leader 节点。关于 Raft 算法集群节点配置变更策略的具体流程，建议读者阅读 Raft 算法作者的博士毕业论文，因这一部分对于整体理解 Raft 算法的影响不大，本文不打算展开说明。

感谢各位的阅读，以上就是“Raft分布式共识算法是什么”的内容了，经过本文的学习后，相信大家对Raft分布式共识算法是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！