raft-paper-note

Raft 论文笔记

Posted by Mickey on June 15, 2019

简介

一致性算法允许一组机器像一个整体一样工作,即使其中一些机器出现故障也能够继续工作下去,因此一致性算法在构建可信赖的大规模软件系统中扮演着重要的角色

过去 10 年里 Paxos 算法统治着一致性算法这一领域,但 Paxos 算法十分难以理解,且 Paxos 自身的算法结构需要进行大幅的修改才能够应用到实际的系统中

在设计 Raft 算法的时候, 我们使用了一些技巧来提高它的可理解性,包括算法分解(Raft 主要被分成 Leader 选举,日志复制和安全性保证三个模块)和减少状态机的状态(相比于 Paxos,Raft 减少了非确定性和服务器互相处于非一致性的方式)

Raft 和许多现有的一致性算法都很相似(主要是 Vierstamped Replication),但也有一些独特的特性:

  1. 强 Leader: 和其他的一致性算法相比,Raft 使用一种更强的领导能力形式。比如日志条目只从 Leader 发送给其他服务器。这种方式简化了对复制日志的管理,并且使得 Raft 算法更加易于理解
  2. Leader 选举: Raft 算法使用一个随机的计时器来选举 Leader。这种方式只是在任何一致性算法都必须实现的心跳机制上增加了一点机制。在解决冲突的时候会更加简单快捷
  3. 成员关系调整: Raft 使用一种共同一致的方法来处理集群成员变换的问题,在这种方法下,处于调整过程中的两种不同的配置集群中大多数机器会有重叠,这就使得集群在成员变换的时候依然可以继续工作

复制状态机

复制状态机

复制状态机的结构。一致性算法管理着来自客户端指令的复制日志,状态机从日志中以相同顺序处理相同指令,所以产生的结果也是相同的

一致性算法是从复制状态机的背景下提出的。在这种方法中,一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错问题。例如,大规模系统中通常都有一个 Leader,像 GFS, HDFS 和 RAMCloud。典型应用就是一个独立的复制状态机去管理 Leader 选举和存储配置信息,并在 Leader 宕机的情况下也要存活下来, 如 Chubby 和 ZooKeeper

复制状态机通常都是基于复制日志实现的。如图1,每个服务器存储一个包含着一系列指令的日志,并按照日志的顺序执行这些指令。因为每个状态机都是确定的,因此每一次执行操作都产生相同的状态和同样的序列

一致性算法的工作就是用来保证复制日志相同。在每台服务器上运行的一致性模块接收客户端发来的指令,然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信,以保证每个服务器上的日志最终都以相同的顺序包含相同的指令,尽管有些服务器会宕机

一旦指令被正确地复制,每一个服务器上的状态机就能按照日志的顺序处理,并输出结果返回给客户端。因此,服务器集群就形成了一个高可靠的状态机

Paxos 的问题

难以理解和不好实现

Raft 一致性算法

Raft 是一种用来管理复制日志的一致性算法:通过选举一个 Leader,然后给予它管理复制日志的全部责任来实现一致性

Leader 从客户端接收日志条目,把日志条目复制到其他服务器上,并且当保证安全性的时候告诉其他的服务器把日志条目应用到它们的状态机中。Leader 的设置简化了对复制日志的管理,例如 Leader 可以决定新的日志条目放在日志中的位置(索引值)而不需要与其他服务器商议, 并且数据都从 Leader 流向其他服务器

通过 Leader,Raft 将一致性问题分解成了三个相对独立的子问题, 这些问题会在接下来的子章节中进行讨论:

  1. Leader 选举:当前的 Leader 宕机时, 一个新的 Leader 需要被选举出来
  2. 日志复制:Leader 必须从客户端接收日志然后复制到集群中的其他节点,并强制要求其他节点的日志保持和自己相同
  3. 安全性:在 Raft 中安全性的关键是状态机安全:如果有任何的服务器节点已经把一个确定的日志条目应用到它的状态机中,那么其他服务器节点不能再同一个日志索引位置应用一个不同的指令。下文会阐述 Raft 算法如何保证这个特性,这个解决方案涉及到一个额外的选举机制上的限制

Raft 基础

一个 Raft 集群包含若干个服务器节点。任何时刻,每个服务器节点都处于这三个状态之一:Leader,Follower 或者 Candidate

  1. Follower:通常情况下系统中只有一个 Leader,并且其他的节点全都是 Follower。Follower 是被动的,它们不会发送任何请求,只是简单地响应来自 Leader 或 Candidate 的请求
  2. Leader:Leader 处理所有的客户端请求。如果一个客户端将请求发送给了 Follower,那么 Follower 会把请求重定向到 Leader
  3. Candidate:Candidate 是在 Leader 选举时使用的

下图展示了这些状态和它们之间的转换:

2

服务器状态。Follower 只响应来自其他服务器的请求。如果 Follower 接收不到消息,那么它就会变成 Candidate 并发起一次选举(election)。获得集群中大多数选票的 Candidate 成为 Leader。在一个任期内,Leader 一直保持 Leader的角色(直到宕机)

Raft 把时间分割成任意长度的任期(term), 如下图所示:

3

时间被划分成一个个的任期,每个任期开始都是一次选举。在选举成功后,Leader 会管理整个集群直到任期结束。有时候选举会失败,那么这个任期就会没有 Leader 而结束。任期之间的切换可以在不同的时间不同的服务器上观察到。 每一段任期从一次选举开始, 一个或多个 Candidate 尝试成为 Leader。如果一个 Candidate 赢得选举,它就在这个任期中充当 Leader 的职责。在某些情况下,一次选举过程会出现选票被平分,那么这一任期会以没有 Leader 结束,一个新的任期(新的选举)会很快重新开始。Raft 保证一个任期内最多只有一个 Leader

任期在 Raft 中充当逻辑时钟的作用,允许服务器查明一些过期信息(比如旧的 Leader)

每个节点存储一个当前任期号,这一编号总是单调增长

当服务器之间通信的时候会交换当前的任期号信息:

  1. 如果一个服务器当前任期号比别人小(即任期号过期了),就会更新自己的编号到较大的值
  2. 如果一个 Candidate 或 Leader 发现自己的任期号过期了, 那么他会立即恢复成 Follower
  3. 如果一个节点收到一个包含过期的任期号的请求, 会直接拒绝这个请求

Raft 中服务器通信使用 RPC 来完成, 并且基本的一致性算法只需要两种类型的 RPC:

  1. 请求投票(RequestVote)RPC 由 Candidate 在选举期间发起
  2. 附加条目(AppendEntries)RPC 由 Leader 发起, 用于复制日志和提供心跳机制

服务器会并行发起 RPC 来获得最佳的性能。当服务器没有及时收到 RPC 的响应回复,会进行重试

Leader 选举

Raft 使用心跳机制来触发 Leader 选举

服务器启动时都是 Follower 的身份,直到它从 Leader 或者 Candidate 接收到有效的 RPC

Leader 周期性地向所有 Follower 发送心跳包(即不包含日志项内容的附加日志项 RPC)来维持自己的身份

如果一个 Follower 在一段时间内没有接收到任何消息,也就是选举超时,那么它就会认为系统中没有可用 Leader,并发起新一轮选举以选出新的 Leader

要开始一次选举,Follower 首先要增加自己当前任期号,并转为 Candidate 角色。然后它并行地向集群中的其他所有节点发送请求投票的 RPC 来给自己投票

Candidate 会保持当前角色,直到发生下列三种情况之一:

  1. 他自己赢得了这次选举
  2. 其他的节点成为 Leader
  3. 一段时间后没有任何一个获胜的节点

当 Candidate 从整个集群的大多数节点(保证了选举安全性)获得了针对同一个任期的投票, 那么它就赢得了这次选举并成为 Leader。每个服务器对一个任期号最多只投出一张选票,按照先来先服务的原则。一旦 Candidate 赢得选举,就立即成为 Leader,并向其他服务器发送心跳消息来建立自己的权威, 并防止有节点重新开始选举

在等待投票时,Candidate 可能会从其他服务器接收到声明 Leader 的心跳消息。如果这个 Leader 的任期号(包含在 RPC 参数中)不小于 Candidate 当前的任期号,那么 Candidate 就会承认该 Leader 合法并回到 Follower 状态,否则 Candidate 就会拒绝这次 RPC 并继续保持 Candidate 状态

第三种结果是 Candidate 既没有赢得选举也没有输,即选票被各个 Candidate 平分。这时候每一个 Candidate 都会超时,然后通过增加当前任期号来开始新一轮选举。但没有其他机制的话,选票可能会被无限地重复平分

Raft 算法使用随机选举超时时间(超时时间就是前文说的 Follower 在一段时间内没有接收到任何消息)来确保很少发生选票平分的情况:为了阻止选票最初就被平分,选举超时时间是从一个固定的区间(如150 - 300 ms)随机选择。这样可以把服务器都分散开来,以至于大多数情况下只有一个服务器会选举超时(即选择的超时时间最短的), 然后它赢得选举并在并在其他服务器超时之前发送心跳包。在选票平分的情况下也使用同样的机制:每个 Candidate 在开始第一次选举的时候会重置一个随机的选举超时时间,然后在超时时间内等待投票结果,这样就减少了在新的选举中另外的选票平分的可能性

日志复制

一旦一个 Leader 被选举出来,它就开始为客户端提供服务。客户端每个请求都包含一条能被复制状态机执行的指令。Leader 把这条指令作为一条新的日志条目附加到日志中去,然后并行地发起附加条目 RPC 到其他服务器,让他们复制这条日志

当这条日志被安全地复制,Leader 会把这条日志应用到它的状态集中,然后把执行结果返回给客户端。如果某些 Follower 宕机或运行缓慢,或网络丢包,Leader会不断地重复 RPC(尽管已经回复了客户端)直到所有 Follower 都最终存储了所有的日志条目

4

日志由有序序号标记的条目组成。每个条目都包含创建时的任期号(图中框中的数字),和一个状态机需要执行的指令。当一个条目可以安全地被应用到状态机中去的时候,就认为是可以提交了。日志中的任期号用来检查是否出现不一致,每一条日志条目同时也有一个整数索引值来表明它在日志中的位置

Leader 来决定什么时候把日志条目应用到状态机中是安全的,这种已被应用的日志条目被称为已提交。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。在 Leader 将创建的日志条目复制到大多数的服务器上的时候,日志条目就会被提交(例如上图中的条目7),同时,Leader 的日志中之前的所有日志条目也都会被提交,包括由其他 Leader 创建的条目

Leader 跟踪了最大的将会被提交的日志项索引,并且索引值会包含在未来所有的附加日志 RPC(包括心跳包),这样其他服务器才能知道 Leader 的提交位置

一旦 Follower 知道一条日志条目已提交, 那么他也会将这个日志条目应用到本地状态机(按照日志的顺序)

Raft 的日志机制来维护一个不同服务器的日志之间的高层次的一致性, 不仅简化了系统的行为也使得更加可预计,同时也是安全性保证的一个重要组件

Raft 维护着以下特性:

  1. 如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们存储了相同的指令,因为在一个任期里,Leader 最多在指定的一个日志索引位置创建一条日志条目,同时日志条目在日志中的位置也从来不会改变
  2. 如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们之前的所有日志条目也全部相同。附加日志 RPC 的一个简单的一致性检查保证了这个特性,在发送附加日志 RPC 时,Leader 会把新的日志条目紧接着前一个条目的索引位置和任期号包含在里面,如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目,它就会拒绝接受新的日志条目。一致性检查就像一个归纳步骤,一开始日志为空时状态肯定是满足日志匹配特性的,当日志扩展的时候, 一致性检查保护了日志匹配特性。因此每当附加日志 RPC 返回成功时,Leader 就能确定 Follower 的日志一定是和自己相同的了

Leader 宕机的情况可能会使得 Leader 和 Follower 的日志处于不一致的状态(旧的 Leader 可能还没有完全复制所有的日志条目),下图展示了 Follower 的日志可能和新的 Leader 不同的方式。Follower 可能会比新的 Leader 多出或缺少一些日志,或者两者都有,多出或缺少的日志可能会持续多个任期

5

当一个 Leader 成功当选时,Follower 可能是任何情况(a-f)。每一个盒子表示是一个日志条目,里面的数字表示任期号。Follower 可能会缺少一些日志条目(a-b),可能会有一些未被提交的日志条目(c-d),或者两种情况都存在(e-f)。例如,场景 f 可能会这样发生,某服务器在任期 2 的时候是 Leader,已附加了一些日志条目到自己的日志中,但在提交之前就崩溃了,很快这个机器就被重启了,在任期 3 重新被选为Leader,并且又增加了一些日志条目到自己的日志中,在任期 2 和任期 3 的日志被提交之前,这个服务器又宕机了,并且在接下来的几个任期里一直处于宕机状态

在 Raft 中, Leader 处理不一致是通过强制 Follower 复制自己的日志来解决, 因此 Follower 中冲突的日志条目会被 Leader 的日志覆盖,Raft 通过增加一些限制来使得这样的操作安全

要使得某个 Follower 的日志和自己一致,Leader 必须找到最后两者达成一致的地方,然后删除 Follower 上的从那个点之后的所有日志条目,最后Leader再发送自己在那个点之后的所有日志给 Follower

Leader 针对每个 Follower 维护了一个 nextIndex,表示下一个需要发送给该 Follower 的日志索引。Leader 刚被选举出来时会初始化所有的 nextIndex 值为自己最后一条日志的 index + 1 (上图中的11)

如果一个 Follower 的日志和 Leader 不一致, 那么下一次附加日志 RPC 的一致性检查就会失败。在被 Follower 拒绝后,Leader 就会减小 nextIndex 值并进行重试,最终 nextIndex 会在某个位置与 Follower 达成一致。一旦达成一致,附加日志 RPC 就会返回成功,这时候就会把 Follower 冲突的日志条目全部删除并加上 Leader 的日志,因此 Follower 的日志就会和 Leader 保持一致,并且在接下来的任期内一直继续保持

算法可以通过减少被拒绝的附加日志 RPC 的次数来优化。例如当附加日志 RPC 被拒绝的时候,Follower 可以返回冲突条目的任期号和自己存储的那个任期的最早的索引地址。借助这些信息,Leader 可以直接让 nextIndex 越过那个任期冲突的所有日志条目,这样就变成每个任期需要一次附加条目 RPC(而不是每个条目一次)

这种机制使得 Leader 在选举成功后不需要任何特殊的操作来恢复一致性,只需要进行正常的操作,日志就能自动地在回复附加日志 RPC 的一致性检查失败的时候自动趋于一致。Leader 绝不会覆盖或删除自己的日志

安全性

到目前为止描述的机制还不能充分保证每个状态机会执行相同的指令序列,例如一个 Follower 可能会进入不可用状态,同时 Leader 已经提交了若干日志条目,然后这个 Follower 可能会被选举为 Leader 并且覆盖这些(之前已被提交的)日志条目 — 因此不同的状态机仍可能执行不同的指令序列

选举限制

现在我们需要在 Leader 选举的时候增加一些限制来完善 Raft 算法。这一限制保证了任何 Leader 对于给定的任期号,都拥有之前任期的所有被提交的日志条目

在任何基于 Leader 的一致性算法中,Leader 都必须存储所有已经提交的日志条目。当一个 Candidate 没有完全包含所有已提交的日志条目时,Raft 使用投票的方式来阻止这个 Candidate 赢得选举。Candidate 为了赢得选举必须联系集群中的大部分节点,意味着每个已提交的日志条目在这些节点中肯定存在于至少一个节点上,也就是说, 如果 Candidate 的日志至少和大多数服务器的节点一样新,那么它一定持有所有已提交的日志

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号确定较新的日志:任期号越大的日志越新,任期号一样, 日志较长的那个较新。

综上, 请求投票 RPC 实现了这样的限制:RPC中包含了 Candidate 的日志信息,然后投票者会拒绝掉所有日志没有自己新的投票请求

提交之前任期内的日志条目

如上所述,只要一条日志被存储到大多数服务器上,Leader 就能确定这条当前任期内的日志是可提交的,如果 Leader 在提交日志之前崩溃了,后续的 Leader 会继续尝试复制这条记录。然而,一个 Leader 不能断定一条之前任期的日志被保存到大多数服务器上时一定是已提交的,下图展示了一种情况:一条已被存储到大多数节点上的旧日志条目,依然可能被后续的 Leader 覆盖掉

6

该图展示了为什么 Leader 无法通过老的日志的任期号来判断其提交状态。在(a)中,S1 是 Leader,部分的复制了索引位置 2 的日志条目。在(b)中,S1 崩溃了,然后 S5 在任期3里通过 S3、S4 和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到(c),S5 又崩溃了,S1 重新启动,选举成功,开始复制日志。在这时,来自任期 2 的那条日志已经被复制到了集群中的大多数机器上,但是还没有被提交。如果 S1 在(d)中又崩溃了,S5 可以重新被选举成功(通过来自 S2,S3 和 S4 的选票),然后覆盖了他们在索引 2 处的日志。但是,在崩溃之前,如果 S1 在自己的任期里复制了日志条目到大多数机器上,如(e)中,然后这个条目就会被提交(S5 就不可能选举成功)。在这个时候,之前的所有日志就会被正常提交处理

为了消除上图的情况,Raft 永远不会通过计算副本数目的方式来确定一个之前任期内的日志条目是否已提交,只有当前任期内的日志可以通过计算副本数目判断是否能提交日志,由于日志匹配的特性,之前的日志条目也会间接地被提交

当 Leader 给 Follower 复制之前任期里的日志时,Raft 会为所有日志保留原始的任期号,这在提交规则上产生了额外的复杂性(因为其他一致性算法在新的 Leader 重新复制之前任期日志时,必须使用新任期号),但更容易辨别出日志,也使得新的 Leader 只需要发送更少的日志条目

安全性论证

在给出完整的 Raft 算法后,现在可以更精确地讨论 Leader 完整性特性:利用反证法,先假设 Leader 完整性不存在,然后推出矛盾来

假设任期 T 的 Leader(Leader T)在任期内提交了一条日志条目,但这条日志没有被存储到未来某个任期的 Leader 中。设大于 T 的最小任期 U 的 Leader U 没有这条日志条目:

7

如果 S1(任期 T 的 Leader)提交了一条新的日志在它的任期里,然后 S5 在之后的任期 U 里被选举为 Leader,然后至少会有一个机器,如 S3,既拥有来自 S1 的日志,也给 S5 投票了

Leader 完整性的证明过程:

  1. 在 Leader U 选举的时候一定没有那条被提交的日志条目(Leader 从不会删除或者覆盖任何条目)
  2. Leader T 复制这条日志条目给集群中的大多数节点,同时,Leader U 从集群中的大多数节点赢得了选票。因此,至少有一个节点同时接受了来自 Leader T 的日志条目,并且给 Leader U 投票了(鸽巢定理),如上图的 S3。这个投票者是产生这个矛盾的关键
  3. 这个投票者必须在给 Leader U 投票之前先接受了从 Leader T 发来的已经被提交的日志条目,否则他就会拒绝来自 Leader T 的附加日志请求(因为此时他的任期号会比T大)
  4. 投票者在给 Leader U 投票时依然保有这条日志条目,因为任何中间的 Leader 都包含该日志条目(根据上述的假设),Leader 从不会删除条目,并且 Follower 只有和 Leader 冲突的时候才会删除条目
  5. 投票者把自己选票投给 Leader U 时,Leader U 的日志必须和投票者自己一样新,这就导致了两者矛盾之一
  6. 首先,如果投票者和 Leader U 的最后一条日志的任期号相同,那么 Leader U 的日志至少和投票者一样长,所以 Leader U 的日志一定包含所有投票者的日志,这是另一处矛盾,因为投票者包含了那条已经被提交的日志条目,但是在上述的假设里,Leader U是不包含的
  7. 除此之外,Leader U 的最后一条日志的任期号就必须比投票人大了。此外,他也比 T 大,因为投票人的最后一条日志的任期号至少和 T 一样大(他包含了来自任期T的已提交的日志)。创建了 Leader U 最后一条日志的之前 Leader 一定已经包含了那条被提交的日志(根据上述假设,Leader U 是第一个不包含该日志条目的Leader)。所以,根据日志匹配特性,Leader U 一定也包含那条被提交当然日志,这里产生矛盾
  8. 这里完成了矛盾。因此,所有比 T 大的 Leader 一定包含了所有来自 T 的已经被提交的日志

日志匹配原则保证了未来的 Leader 也同时会包含被间接提交的条目

通过Leader完整性, 我们就能证明图3中的状态机安全特性:

  1. 如果服务器已经应用了某个给定的索引值的日志条目到自己的状态机里,那么其他的服务器不会在这个索引值上应用一个不同的日志到它的状态机中
  2. 现在来考虑任意服务器应用一个指定索引位置的日志的最小任期:日志完全特性保证拥有更高任期号的 Leader 会存储相同的日志条目,所以之后的任期中,服务器应用的这个索引值上的日志指令一定也是与 Leader 相同的

因此,状态机安全特性是成立的

Follower 和 Candidate 崩溃

Follower 和 Candidate 崩溃后的处理方式比 Leader 要简单得多。如果 Follower 或 Candidate 崩溃了,那么后续发送给它们的 RPC 都会失败。Raft 处理这种失败的方式就是无限重试:

  1. 如果崩溃的机器重启了,那么这些 RPC 就会成功
  2. 如果服务器在完成了一个 RPC 但还没有回复响应时崩溃了,那么它重新启动后会再次受到同样的请求。Raft 的 RPC 都是幂等的(如果 Follower 受到一个重复的附加日志 RPC,会直接忽略),因此重试不会造成任何问题

图表总结

状态整理

所有服务器上持久存在的:

状态 解释
currentTerm 服务器最后一次知道的任期号(初始化为 0,持续递增)
votedFor 在当前获得选票的 Candidate 的 Id
log[] 日志条目集,每一个条目包含一个用户状态机执行的指令,和收到时的任期号

所有服务器上经常变的:

状态 解释  
commitIndex 已知的最大的已经被提交的日志条目的索引值
lastApplied 最后被应用到状态机的日志条目索引值(初始化为 0,持续递增)  

在Leader里经常改变的(选举后重新初始化):

状态 解释
nextIndex[] 对于每一个服务器,需要发送给他的下一个日志条目的索引值(初始化为 Leader 最后索引值加一)
matchIndex[] 对于每一个服务器,已经复制给他的日志的最高索引值

RPC 整理

附加日志 RPC(AppendEntries):

由 Leader 负责调用来复制日志指令,也会用作 heartbeat

参数 解释
term Leader的任期号
leaderId Leader的 Id,以便于Follower重定向请求
prevLogIndex 新的日志条目紧随之前的索引值
prevLogTerm prevLogIndex 条目的任期号
entries[] 准备存储的日志条目(表示心跳时为空;一次性发送多个是为了提高效率
leaderCommit Leader已经提交的日志的索引值
返回值 解释
term 当前的任期号,用于Leader去更新自己
success Follower 包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

接收者实现:

  1. 如果 term < currentTerm 就返回 false
  2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配,则返回 false
  3. 如果已经存在的日志条目和新的产生冲突(索引值相同但是任期号不同),删除这一条和之后所有的
  4. 附加任何在已有的日志中不存在的条目
  5. 如果 leaderCommit > commitIndex,令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个

请求投票 RPC(RequestVote):

由 Candidate 负责调用用来征集选票

参数 解释
term Candidate 的任期号
candidateId 请求选票的 Candidate 的 Id
lastLogIndex Candidate 的最后日志条目的索引值
lastLogTerm Candidate 最后日志条目的任期号
返回值 解释
term 当前任期号,以便于 Candidate 去更新自己的任期号
voteGranted Candidate 赢得了此张选票时为真

接收者实现:

  1. 如果 term < currentTerm 返回 false
  2. 如果 votedFor 为空或者就是 candidateId,并且 Candidate 的日志至少和自己一样新,那么就投票给他

各类角色服务器需遵守的规则

所有服务器:

  1. 如果 commitIndex > lastApplied,那么就 lastApplied 加一,并把log[lastApplied] 应用到状态机中
  2. 如果接收到的 RPC 请求或响应中,任期号 T > currentTerm,那么就令 currentTerm 等于 T,并切换状态为 Follower

Follower:

  1. 响应来自 Candidate 和 Leader 的请求
  2. 如果在超过选举超时时间的情况之前都没有收到 Leader 的心跳,或者是 Candidate 请求投票的,就自己变成 Candidate

Candidate:

  1. 在转变成Candidate后就立即开始选举过程
    1. 自增当前的任期号(currentTerm)
    2. 给自己投票
    3. 重置选举超时计时器
    4. 发送请求投票的 RPC 给其他所有服务器
  2. 如果接收到大多数服务器的选票,那么就变成 Leader
  3. 如果接收到来自新的 Leader 的附加日志 RPC,转变成 Follower
  4. 如果选举过程超时,再次发起一轮选举

Leader:

  1. 一旦成为 Leader:发送空的附加日志 RPC(心跳)给其他所有的服务器;在一定的空余时间之后不停的重复发送,以阻止 Follower 超时
  2. 如果接收到来自客户端的请求:附加条目到本地日志中,在条目被应用到状态机后响应客户端
  3. 如果对于一个 Follower,最后日志条目的索引值大于等于 nextIndex,那么:发送从 nextIndex 开始的所有日志条目:
    1. 如果成功:更新相应 Follower 的 nextIndex 和 matchIndex
    2. 如果因为日志不一致而失败,减少 nextIndex 重试
  4. 如果存在一个满足 N > commitIndex 的 N,并且大多数的 matchIndex[i] ≥ N 成立,并且 log[N].term == currentTerm 成立,那么令 commitIndex 等于这个 N

集群成员变化

到目前为止,我们都假设集群的成员信息配置(即加入到一致性算法的服务器集合,下文简称配置)是固定不变的

为了保证自动化的配置修改机制的安全性,转换过程中的任意时间点都不能存在两个 Leader。然而,任何直接从旧的配置转换成新配置的方案都是不安全的,在转换期间可能会发生整个集群划分成两个独立的大多数群体,见下图

8

直接从一种配置转到新的配置是十分不安全的,因为各个机器可能在任何的时候进行转换。在这个例子中,集群配额从 3 台机器变成了 5 台。不幸的是,存在这样的一个时间点,两个不同的 Leader在同一个任期里都可以被选举成功(一个是通过旧的配置,一个通过新的配置)

因此为保证安全性,配置更改必须使用两阶段提交的方法。在 Raft 中,集群先切换到一个过渡的配置(此时状态称为 Joint Consensus, 共同一致),一旦共同一致被提交之后,那么系统就再切换到新的配置上,共同一致状态是旧配置和新配置的并集,在此状态下:

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

9

一个配置切换的时间线,虚线表示已经被创建但是还没有被提交的条目,实线表示最后被提交的日志条目。Leader 先在自己的日志中创建一条 C-old,new 的配置条目,并提交到 C-old,new(C-old 的大多数和 C-new 的大多数)中。然后同样地再创建 C-new 条目,并提交到 C-new 中的大多数。这样过程中就不存在 C-new 和 C-old 可以同时做出决定的时间点

当一个 Leader 接收到一个改变集群配置的请求,他会以创建日志条目的形式将当前使用的配置更新为共同一致的配置(即图中的 C-old,new)。所有的服务器只使用其日志中最新的配置条目(无论是否已被提交),因此 Leader 会使用 C-old,new 的规则来决定日志条目 C-old,new 什么时候需要被提交。如果此过程中 Leader 崩溃了,被选出来的新任 Leader 可能使用 C-old 配置,也可能是 C-old,new 配置。但在任何情况下,C-new 配置在这一时期都不会单方面地做出决定

一旦 C-old,new 被提交,那么 C-old 和 C-new 的成员都不能单独做出决定,并且 Leader 完整性保证了只有配置为 C-old,new 的服务器才可能被选举为 Leader。这时,Leader 再创建一条 C-new 配置的日志条目并复制给集群就是安全的操作了

关于集群成员变化还有三个问题值得讨论:

  1. 新的服务器可能没有存储任何日志条目,需要一段时间来更新。为了避免这种可用性的间隔时间,Raft 在配置更新的时候使用了一种额外的阶段,在这个阶段新的服务器以没有投票权的身份加入到集群中(Leader会把日志复制给他们,但不把他们当做是大多数)
  2. 集群的 Leader 可能不是新配置的成员。这种情况下,Leader 就会在提交了 C-new 日志后退位(回到 Follower 状态)。也就是说存在这样一段时间,Leader 管理着集群,但不包括它自己;Leader 复制日志但是不会把自己算作大多数之一。当 C-new 被提交时,会发生 Leader 过渡,因为这时是新配置可以独立工作的最早时间点。在此之前,可能只能从 C-old 中选出 Leader
  3. 移除不在 C-new 中的服务器可能会扰乱集群。这些服务器将不会再接收到心跳,所以当选举超时,他们就进行新一轮选举,发送新一轮的请求投票 RPC,这样会导致当前 Leader 回退到 Follower 状态。新的 Leader 最终会被选出来,但是被移除的服务器将会再次超时,然后重复这个过程,导致整体可用性大幅降低。为避免这个问题,当服务器确认当前 Leader 存在后,会忽略请求投票 RPC。特别的,当服务器在当前最小选举超时时间内收到一个请求投票 RPC,他不会更新当前的任期号或者投出选票。这不会影响正常选举,因为每个服务器在开始一次选举前会等待一个最小选举超时时间,而且这有利于避免被移除的服务器扰乱:如果Leader能向集群发送心跳,那么他就不会被更大的任期号废除