分布式一致性协议 Raft 原理

Raft 是一种基于消息传递通信模型、用来管理日志复制的一致性协议，它允许一组机器像一个整体一样工作，即使其中的一些机器出现错误也能正常提供服务。在 Raft 被提出来之前，Paxos 协议是第一个被证明的一致性算法，但是 Paxos 的原理理解与工程实现都很困难。Raft 是 Paxos 的一种实现方式，目标是提供更好理解的算法，并被证明可以提供与 Paxos 相同的容错性以及性能。

概述

Raft 算法是可以用来替代 Paxos 算法的分布式共识算法，而且 Raft 算法比 Paxos 算法更易懂更易实现。为了达到易于理解的目标，Raft 利用问题分解方法，将『复制集群节点一致性』这一复杂问题划分为四个可以被独立解释并处理的子问题：领导选举（Leader Election）、日志复制（Log Replication）、安全性（Safety）、成员变更（Membership Changes）。文中会从这四方面介绍 Raft 算法的机制。

数据一致性

分布式系统中的节点通信存在两种模型：共享内存（Shared Memory）和消息传递（Messages Passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程运行缓慢慢、被杀死或者重启，消息可能会因此延迟、丢失、重复。Paxos 算法解决的是在不考虑 拜占庭将军问题 的条件下，在一个可能发生上述异常情况的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏共识，即确保数据的一致性。

分布式系统中常见的三种一致性模型：

• 强一致性：当更新操作在某个副本上执行成功后，之后所有的读操作都要能够获得最新的数据；
• 弱一致性：当更新某数据时，用户读到最新的数据需要一段时间的延迟；
• 最终一致性：它是一种特殊的弱一致性，当某个数据更新后，在经过一个时间片段，所有后续的操作能够获得新数据，在这个时间片段内，数据可能是不一致的。

Raft 是分布式领域中的强一致性算法，当其中某个节点收到客户端的一组指令时，它必须与其它节点沟通，以保证所有的节点以相同的顺序收到相同的指令，最终所有的节点会产生一致的结果，就像是一台机器一样。

状态机复制

在分布式环境中，如果我们要让一个服务具有容错能力，最常用的方法就是让一个服务的多个副本同时运行在不同的节点上。为了保证多个副本在运行时的状态都是同步的，即客户端无论将请求发送到哪一个节点中，最后都能得到相同的结果，因此采用状态机复制（State Machine Replication）方法。

状态机复制通常使用日志复制（Log Replication）实现，每个服务器节点存储一个包含一系列命令的日志，其状态机按顺序执行日志中的命令，每个日志中的命令都相同并且顺序也一致，因此每个状态机处理相同的命令序列，这样就能得到相同的状态和输出序列。

Raft 的工作就是保证复制日志的一致性，服务器上的Consensus模块接收来自客户端的命令，并将它们添加到日志中。随后该服务器与其他服务器上的Consensus模块通信，以确保每个服务器上具有相同的日志序列，即使有小部分的服务器通信失败。每个服务器上的状态机按顺序执行命令，并将输出返回给客户端，这样就形成了高可用的复制状态机。

Raft 算法和 Paxos 算法一样，也具有以下分布式共识算法的特性：

• 确保在所有非拜占庭条件下（包括网络延迟、分区和数据包丢失，重复、乱序）的安全性（不会返回不正确的结果）；
• 只要超过一半（n/2+1）服务器都可以运行，并且可以相互通信和与客户端通信，一致性算法就可用。 因此，五台服务器的典型集群可以容忍任何两台服务器的故障。如果服务器突然宕机，它们可以稍后恢复状态并重新加入群集；
• 它们不依赖于时序来确保日志的一致性，因为错误的时钟和极端消息延迟可能在最坏的情况下导致可用性问题；
• 在通常情况下，只要集群的大部分服务器已经响应了单轮远程过程调用，命令就可以完成，少数的慢服务器不会影响整个系统性能。

Leader Election

Raft 是一种用来管理上述日志复制过程的算法，Raft 通过『领导选举机制』选举出一个 Leader，由它全权管理日志复制来实现一致性。一个 Raft 集群包含若干个服务器节点，每一个节点都有一个唯一标识 ID，并且在任何时刻，每一个服务器节点都处于下面三个状态之一：

• Leader（领导人）：Leader 处理所有的客户端请求，在通常情况下，系统中只有一个 Leader 并且其他节点都是 Follower；
• Follower（跟随者）：Follower 不会发送任何请求，只是简单地响应来自 Leader 或 Candidate 的请求，如果一个客户端与 Follower 联系，那么 Follower 会把请求重定向至 Leader；
• Candidate（候选人）：如果 Follower 接收不到来自 Leader 的消息，那么它就会变成 Candidate 并发起一次选举，获得集群中大多数选票（超过 n/2+1）的候选人将成为新的 Leader。

Raft 把时间分割成任意长度的任期（Term），任期用连续的整数标记。每一段任期从一次选举开始，如果一个 Candidate 赢得选举，那么它在这个任期内充当领导人的职责。在某些情况下，一次选举可能会发生选票瓜分的情况，每个 Candidate 的选票数都不足n/2+1，这时这个任期会以没有 Leader 结束，一个新的任期和一次新的选举会重新开始。Raft 保证了在一个给定的任期内，最多只有一个 Leader。

节点通信

集群中的节点使用远程过程调用（RPC）进行通信，Raft 中一共有三种类型的 RPC：AppendEntries RPC 由 Leader 发起；RequestVote RPC 由 Candidate 在选举期间发起；InstallSnapshot RPC 由 Leader 发起，用于将快照分块发送给日志落后的 Follower。在本小节中会先介绍前两种 RPC。

AppendEntries（追加日志）RPC 用于日志复制和心跳消息，Leader 将客户端的命令通过 AppendEntries RPC 并行地发送给所有节点，主要包含的字段如下：

RequestVote RPC 用于 Candidate 向其它节点发起选举，主要内容有：

选举流程

当一个 Raft 集群启动时，所有节点都是 Follower 身份，一个节点从领导人或者候选者处接收到有效的 RPC 时会继续保持着 Follower 状态。Leader 会周期性的地向所有跟随者发送心跳消息（不包含日志内容的 AppendEntries RPC）来维持自己的权威。如果一个 Follower 在一段时间里没有接收到任何消息，那么他就会认为系统中没有可用的领导者，因此发起选举以选出新的领导者。

需要注意的是，一个节点只要收到来自其它节点的有效的 RPC，就会保持 Follower 状态。如果 RPC 发送方的任期较小，那么接受节点会忽略该消息。

要开始一次选举过程，Follower 先将自己当前的任期号加 1 并转换到 Candidate。然后他会并行的向集群中的其他节点发送 RequestVote RPC 来给自己投票。Candidate 会保持当前状态直到以下三件事情之一发生：

1. 第一种情况是它自己赢得了本次的选举：当一个 Candidate 从集群的多数服节点中获得了针对同一个任期号的选票，那么它就赢得了这次选举并成为领导人。每一个节点按照先到先得的原则，最多会对一个任期号投出一张选票，一旦 Candidate 赢得选举，它就立即成为 Leader，然后它会向其它的节点发送心跳消息来建立自己的权威并阻止新 Leader 的产生。
2. 第二种情况是其它节点成为 Leader：在等待投票期间，Candidate 可能会收到其它服务器节点声明它是领导人的 AppendEntries RPC。如果这个节点的term字段不小于 Candidate 当前的任期号，那么 Candidate 会承认 Leader 的合法性并回到 Follower 状态。 如果此次 RPC 中的任期号比自己小，那么 Candidate 会拒绝这次的 RPC 并且继续保持 Candidate 状态。
3. 第三种情况是如果有多个 Follower 同时成为 Candidate，那么选票可能会被瓜分以至于没有 Candidate 可以赢得大多数节点的支持。当这种情况发生时，Candidate 会发生选举时间超时，然后增加当前任期号来开始一轮新的选举。

前两种情况比较好理解，第三种情况中，如果没有额外的机制，每个 Candidate 都会进入选举超时状态并开启下一轮选举，选票可能会被无限的重复瓜分。为了避免集群陷入选举死循环状态，Raft 使用随机选举超时时间来解决这个问题。

随机选举超时时间

Raft 算法使用随机选举超时时间机制来确保很少会发生选票瓜分的情况，选举超时时间是从一个固定区间内（例如 150-300 ms）随机选择，这样可以把选举超时都分散开，在大多数情况下只有一个 Candidate 会选举超时。

同样的机制被用在选票瓜分的情况。每一个候选人在开始一次选举时会重置一个随机选举超时时间，在超时时间内等待投票的结果，这样减少了在新的选举中另外的选票瓜分的可能性。

领导人选举是 Raft 中对时间要求最为关键的方面。为了让 Raft 可以选举并维持一个稳定的领导人，系统需要满足下面的时间要求：

1

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

广播时间指的是从一个服务器节点并行发送 RPC 给集群中的其他节点并接收响应的平均时间，平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。Raft 要求广播时间要比选举超时时间小一个数量级，因此广播时间大约在 10ms 才能满足上述选举超时时间要求。而平均故障间隔时间要求则很容易达到，对于一台稳定的服务器，不会每隔几分钟就宕机一次。

Log Replication

当 Leader 被选举出来，它就开始为客户端提供服务。客户端的每一个请求都包含一条被状态机执行的指令，Leader 把这条指令作为一条新的日志条目附加到日志中，然后并行地向其它节点发起 AppendEntries RPC 。当这条日志条目被安全地复制，Leader 会应用这条日志条目到它的状态机中（状态机执行该指令），然后把执行的结果返回给客户端。如果 Follower 崩溃或者运行缓慢、网络丢包，领导人会不断地重试发送 AppendEntries RPC（即使 Leader 已经回复了客户端）直到所有的 Follower 最终都存储了所有的日志条目。

每个日志条目存储一条状态机指令和 Leader 收到该指令时的任期号。任期号用来检测多个日志副本之间的不一致情况，每个日志条目都有一个整数索引值来表明它在日志中的位置。

Leader 决定什么时候把日志条目应用到状态机中是安全的：这种日志条目被称为已提交的（Committed）。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。一旦创建该日志条目的 Leader 将它复制到过半的服务器上，该日志条目就会被提交。同时，Leader 日志中该日志条目之前的所有日志条目也都会被提交，包括由其他 Leader 创建的日志条目。

Log Matching

Raft 的日志机制来维持不同服务器之间日志高层次的一致性。这么做不仅简化了系统的行为也使得系统行为更加可预测，同时该机制也是保证安全性的重要组成部分。Raft 维护着以下日志匹配（Log Matching）特性：

• 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们存储着相同的命令；
• 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也都相同。

Leader 在特定的任期号内的一个日志索引处最多创建一个日志条目，同时日志条目在日志中的位置永远也不会改变，该点保证了第一条特性。第二个特性是由 AppendEntries RPC 执行一个简单的一致性检查所保证的：在发送 AppendEntries RPC 时，Leader 会将前一个日志条目的索引位置prevLogIndex和任期号prevLogTerm包含在里面。如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝该新的日志条目。

因此，每当 AppendEntries RPC 返回成功时，Leader 就知道该 Follower 的日志一定是和自己相同的。然而，Leader 崩溃时会使得日志处于不一致的状态。

日志一致性检查

在 Raft 算法中，Leader 通过强制 Follower 复制自己的日志处理不一致问题——这意味着在 Follower 中冲突的日志条目会被 Leader 的日志覆盖。

要使得 Follower 的日志和 Leader 保持一致的状态，Leader 必须找到两者最后达成一致的日志条目，然后删除 Follower 从该日志条目之后的所有日志，并发送自己的日志给 Follower。这些操作都在进行 AppendEntries RPC 的一致性检查时完成。

Leader 针对每一个 Follower 都维护了一个nextIndex字段，表示下一个需要发送给该 Follower 的日志条目的索引值。当一个领导人刚获得权力的时候，他初始化所有的nextIndex值为自己的最后一条日志的index加 1。如果一个 Follower 的日志和 Leader 不一致，那么在下一次的附加日志 RPC 时的一致性检查就会失败。在被 Follower 拒绝之后，Leader 就会减小nextIndex值并进行重试。最终nextIndex会在某个位置使得双方达成一致。然后执行日志覆盖操作，使得 Follower 的日志和 Leader 保持一致。

通过日志一致性检查机制，Leader 在获得权力时不需要任何特殊的操作来恢复一致性。Follower 日志在 AppendEntries RPC 的一致性检查失败时会自动趋于一致。

Safety

由于 Raft 算法通过强制覆盖 Follower 日志来保证数据一致性，并且 Leader 具有 Append-Only 特性，从来不会覆盖或者删除自己的日志。如果一个具有少数日志条目的节点当选为 Leader ，那么就会造成大量的数据丢失，为了避免发生这种情况，Raft 在领导选举时会增加一些限制条件，保证任何的 Leader 对于给定的任期号，都拥有之前任期所有被提交的日志条目。

选举限制

Raft 中日志条目的传送是单向的，只能由 Leader 传递给 Follower，并且 Leader 从不会覆盖自身本地日志中已经存在的条目。因此 Raft 使用投票的方式来阻止一个 Candidate 赢得选举，除非这个候选人包含了所有已经提交的日志条目。

Candidate 为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在集群中肯定存在于至少一个节点上。如果 Candidate 的日志和大多数的节点一样新，那么他一定持有了所有已经提交的日志条目。RequestVote RPC 实现了这样的限制：RPC 中包含了候选人的日志信息，Follower 会拒绝那些日志没有自己新的 Candidate 的投票请求。

Raft 通过比较两份日志中最后一条日志条目的lastLogIndex和term定义谁的日志比较新。如果两份日志最后的条目的term不同，那么term较大的日志更加新。如果两份日志最后条目term的相同，那么拥有较大lastLogIndex的日志就更加新。

Membership Changes

在项目运行中，我们可能会改变集群的配置，例如增加节点或机器的配置。尽管可以通过使整个集群下线，更新所有配置，然后重启整个集群的方式来实现，但是在更改期间集群会不可用。另外，如果存在手工操作步骤，那么就会有操作失误的风险。为了避免这些的问题，Raft 将配置变更自动化归并到算法中。

为了使配置变更机制能够安全，在转换的过程中不能够存在任何时间点使得在同一个任期里可能选出多个 Leader 。但是任何服务器直接从旧的配置转换到新的配置的方案都是不安全的，在成员变更时，因为无法做到在同一个时刻使所有的节点从旧配置转换到新配置，那么直接从旧配置向新配置切换就可能存在一个节点同时满足新旧配置的『超过半数』原则。

直接从一种配置转到另一种配置是不安全的，因为各个机器会在不同的时候进行转换。在上图中，集群从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，Server1 可以通过自身和 Server2 的选票成为Leader（满足旧配置下收到大多数选票的原则），Server3 可以通过自身和 Server4、Server5 的选票成为Leader（满足新配置，即集群有 5 个节点的情况下的大多数选票原则）。此时整个集群可能在同一任期中出现了两个 Leader，这和协议是违背的。

共同一致

为了保证安全性，Raft 配置更改采用两阶段方法。在配置变更过程中新老配置互相无法感知，而配置更替也无法一蹴而就。所以在配置更替前，将集群引导入一个过渡阶段，使得使用新配置和旧配置的机器都不会独立地处理日志。在 Raft 中，集群先切换到一个过渡的配置，称之为共同一致状态，一旦共同一致被提交，那么系统就切换到新的配置上。

第一阶段称为joint consensus，当joint consensus被提交后切换到新的配置下，在第一阶段中：

• 日志条目被复制给集群中新、老配置的所有服务器；
• 新、旧配置的服务器都可以成为 Leader；
• 达成一致（针对选举和提交）需要分别在两种配置上获得大多数的支持。

具体的切换过程如下：

1. Leader 收到配置变更请求时，创建包含包含新旧配置的日志C-old-new并复制给其他节点；
2. Follower 以日志中存在的最新的配置做决定，即使该配置未被提交，Leader 只有在C-old-new复制到大多数节点后才以这个配置做决定，这时处于共同决定的过程；
3. 之后提交新配置到所有节点，一旦新配置被提交，旧配置就会被抛弃。

一旦一个服务器将新的配置日志条目增加到它的日志中，他就会用这个配置来做出未来所有的决定（服务器总是使用最新的配置，无论它是否已经被提交）。共同一致允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换过程。此外，共同一致可以让集群在配置转换的过程中依然响应客户端的请求。

边界问题

在关于重新配置还有三个边界问题需要解决。第一个问题是，新的服务器在初始化时没有存储任何的日志条目。当这些服务器以这种状态加入到集群中，需要一段时间来更新追赶。为了避免这种可用性的间隔时间，Raft 在配置更新之前使用了一种额外的阶段，在这个阶段，新的服务器以没有投票权身份加入到集群中来（领导人复制日志给他们，但是不考虑他们是大多数）。一旦新的服务器追赶上了集群中的其他机器，重新配置可以像上面描述的一样处理。

第二个问题是，集群的 Leader 可能不是新配置的一员。在这种情况下，Leader 就会在提交了新配置日志之后退回到 Follower 状态。这意味着有这样的一段时间，Leader 管理着集群，但是不包括他自己；它复制日志但是不把自己算作是其中的一个节点。当新配置被提交时，会发生 Leader 过渡，因为这时是最早的新配置可以独立工作的时间点，在此之前，可能只能从旧配置中选出领导人。

第三个问题是，移除不在新配置中的服务器可能会扰乱集群。这些服务器将不会再接收到心跳，所以当选举超时，他们就会进行新的选举过程。他们会发送拥有新的任期号的 RequestVote RPC，这样会导致当前的 Leader 回退成 Follower 状态。新的 Leader 最终会被选出来，但是被移除的服务器将会再次超时，然后这个过程会再次重复，导致整体可用性大幅降低。

为了避免这个问题，当服务器确认当前 Leader 存在时，服务器会忽略 RequestVote RPC。当服务器在当前最小选举超时时间内收到一个 RequestVote RPC，他不会更新当前的任期号或者投出选票。每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。这有利于避免被移除的服务器扰乱：如果领导人能够及时发送心跳消息给集群，那么它就不会被更大的任期号废黜。

网络分区

在一个集群中，如果有部分节点的网络发生故障，与集群中另一部分节点的连接中断，形成相对独立的子网，就会出现网络分区现象。Raft 算法对不同情况下的网络分区具有不同的应对方案。

Leader 在少数节点分区中

在上图中，假设 Leader 节点 S1 被分割在了左侧的少数节点分区中。随着时间的流逝，集群中与 Leader 节点隔离的网络分区中，会率先有一个节点的选举计时器超时，这里假设该节点是 S5，此时 S5 就会切换成 Candidate 状态并发起下一轮选举。由于网络分区，当前集群中只有节点 S4、S5 能够收到节点 S5 的选举请求，假设节点 S5 最终赢得了选举，那么此时集群中会存在两个 Leader。

当出现这种情况时，Raft 算法需要保证客户端请求数据的一致性，为了解决这个问题，集群需要做到：

• 由 Leader 来处理读请求；
• 确保当前 Leader 仍然是有效的 Leader。

当客户端初次连接到集群时，会随机挑选一个服务器节点进行通信，如果客户端第一次挑选的节点是 Follower 节点，那么该节点会将请求重定向至 Leader 节点，由 Leader 来处理读写请求。Leader 会发起一次广播，以确保能联系到集群中的大多数节点，保证自身的权威性，然后才会对客户端请求进行处理。

在上图中，由于 S1 节点无法与集群中的大多数节点进行通信，因此不能正常处理客户端的请求，所有的请求都会被 S5 处理。最终 S1 分区的数据状态停留在分区发生时刻，而分区发生后的数据处理都在 S5 分区中保存。

当网络分区故障被修复时，此时节点 S1 发送的心跳消息会被节点 S3、S4、S5 接收到，但是这些心跳消息中携带的 Term 值小于当前 S3、S4、S5 节点的 Term 值，因此会被 S3、S4、S5 节点忽略；同时，节点 S5 发送的心跳消息会被节点 S1、S2 接收到，由于这些心跳消息携带的 Term 值大于当前 S1、S2 节点的 Term 值，所以节点 S1、S2 会切换成 Follower 状态，最终节点 S5 成为了整个集群中的 Leader 。

Leader 在多数节点分区中

如果网络分区时，Leader 节点被划分到节点较多的分区中，此时节点较少的分区中，会有节点的选举计时器超时，切换成 Candidate 并发起新一轮的选举。但是由于该分区中节点数不足半数，所以无法选举出新的 Leader，从而导致该分区内的节点不断发起选举，Term 号不断增长。

Raft 协议对这种情况进行了处理，当某个节点要发起选举之前，需要先进入 PreVote 的状态，节点会先尝试连接集群中的其他节点，如果能够成功连接到半数以上的节点，才能切换成 Candidate 身份真正发起新一轮的选举。

日志压缩

当系统中的日志越来越多后，会占用大量的空间。Raft 算法采用了快照机制来压缩庞大的日志，在某个时间点，将整个系统的所有状态稳定地写入到可持久化存储中，然后这个时间点后的所有日志全部清除。

通常服务器都是独立地创建快照，但是 Leader 也会偶尔发送快照给一些落后的节点，例如一个运行缓慢的 Follower 或者新加入集群的服务器，通过网络发送快照让该 Follower 更新到最新的状态。

Leader 使用 InstallSnapshot RPC 分块发送快照给太落后的 Follower，如果快照中包含重复的日志条目，那么 Follower 会删除日志中存在的条目，采用快照中的数据。

Follower 可以在 Leader 不知情的情况下创建快照，虽然快照的方式背离了 Raft 的强领导人原则，但是我们认为这种背离是值得的。领导人的存在，是为了解决在达成一致性时的冲突，但是在创建快照的时候，一致性已经达成，这时不存在冲突了，所以没有 Leader 也是可以的。数据依然是从 Leader 传给 Follower，只是 Follower 可以重新组织他们的数据。

总结

Raft 算法的实现原理清晰，在逻辑上比较遵循人的直觉，描述也很细致，考虑到了一些边界问题，这些不仅提升了 Raft 的可理解性，也令人相信其正确性。

Raft 算法将共识问题分解成数个相对独立的字问题，总体流程是节点选举出 Leader，由 Leader 负责日志的复制与提交。为了在任何异常情况下系统不出错，Raft 对领导选举与日志复制实施诸多约束：

• 利用随机选举超时时间避免选票瓜分；
• 使用一致性检查处理日志不一致问题；
• 通过选举限制策略保证新 Leader 数据的最新性；
• 利用最小选举超时时间保证 Leader 的权威性。

这种将复杂问题分解化的设计思想很好地描述了 Raft 是如何解决分布式系统中的一致性问题，并提出了一定的解决方案，帮助开发者更好地将其应用到工程中。

文中主要内容与部分图片来自论文 In Search of an Understandable Consensus Algorithm 与 寻找一种易于理解的一致性算法（扩展版），存在错误之处可以留言指正。

References

• CAP theorem
• Paxos
• Raft
• 拜占庭将军问题
• State machine replication
• In Search of an Understandable Consensus Algorithm
• 寻找一种易于理解的一致性算法（扩展版）
• The Raft Consensus Algorithm
• 分布式一致性算法：Raft 算法
• 解读Raft（四 成员变更）
• CAP 理论十二年回顾：“规则"变了

相关文章

• 漫谈分布式共识算法与数据一致性
• ZooKeeper 与 Zab 协议 · Analyze