分布式一致性算法-Raft算法

Raft

Raft 算法是另一种复制状态机共识算法。并且 Raft 是由于 Paxos 算法的晦涩难懂而被设计出来。Raft 通过首先选举一个 distinguished leader,然后让它全权负责管理复制日志来实现一致性。Leader 从客户端接收日志条目,把日志条目复制到其他服务器上,并且在保证安全性的时候通知其他服务器将日志条目应用到他们的状态机中。拥有一个 leader 大大简化了对复制日志的管理。

Raft 算法主要包括三个问题,即:领导者选举、日志复制以及安全性。

  1. Leader 选举:当前的 leader 宕机时,一个新的 leader 必须被选举出来。
  2. 日志复制:Leader 必须从客户端接收日志条目然后复制到集群中的其他节点,并且强制要求其他节点的日志和自己的保持一致。
  3. 安全性:如果有任何的服务器节点已经应用了一个特定的日志条目到它的状态机中,那么其他服务器节点不能在同一个日志索引位置应用一条不同的指令。

下面我们针对这三个问题依次进行总结,主要依据是论文的翻译,并且我会在论文的基础上把一些值得注意的点以及不那么清楚的地方展开来。

Raft 基础

一个 Raft 集群有若干个服务器结点,一般为 5 个或以上奇数个,至于为什么是奇数个,主要是奇数比偶数在容灾方面跟节省资源并且在出现网络分区的时候保证可用,具体可以参考(Zookeeper集群节点为什么推荐为奇数)。回归正题,在 Raft 协议中,结点通常有:Leader、Follower 和 Candidate 三个状态

  • Leader:Leader 作为集群的领导者,在集群中是唯一的,并且起到接收客户端请求的作用。
  • Follower:Follower 不会发送任何请求,只是负责响应 Candidate 和 Leader。
  • Candidate:顾名思义,是指选举阶段的候选人,

在论文中用下图来表示三者的关系:

在 Raft 中,算法将时间分割成一段段任期(term),如果 Follower 在一定时间内没有接收到 Leader 的心跳,则会进入一个新的任期,此时会有多个 Candidate,它们都会尝试成为 Leader,如果一个 candidate 赢得选举,然后他就在该任期剩下的时间里充当 leader 。在某些情况下,一次选举无法选出 leader 。在这种情况下,这一任期会以没有 leader 结束;一个新的任期(包含一次新的选举)会很快重新开始。Raft 保证了在任意一个任期内,最多只有一个 leader 。

在 Raft 中,服务器之间通过 RPC 进行通信,而 RPC 又分为 RequestVote RPC 和 AppendEntries RPC 。RequestVote RPC 主要是 Candidate 请求投票时发出的;而 AppendEntries RPC 指的是追加日志条目的 RPC,主要是由 Leader 发起,对 Follower 的一种心跳机制。在上图中,S2 向其他结点发送第一次 RPC 为 RequestVote RPC 意思是请求其他结点投票,第二次则为 AppendEntries RPC。

Leader 选举

当算法开始时,所有的结点都是 Follower,如果 Follower 在一定时间内没有收到来自 Leader 的心跳,它会认为当前没有 Leader,进入一个新的任期,并且成为一个 Candidate,向其他的 Follower 发送 RequestVote RPC,其他的 Follower 收到了 RPC,则会继续维持自己的 Follower 的状态并且向发来 RPC 的 Candidate 进行回复表示同意(该结点成为 Leader)注意:并不是一定会回复同意,后面会讨论特殊情况。另外值得注意的是,当一个任期内,一个 Follower 会按照先来先服务的原则只投给一个 Candidate,

图中 S1 和 S4 都是 Candidate,S2 S3 S5 在收到 RequestVote RPC 后继续维持 Follower 的状态,最后 S4 在收到过半投票后成为了 Leader

在选举过程中,Candidate 会一直保持当前状态直到以下三件事情之一发生:1、它自己赢得了这次的选举(收到过半的投票),2、其他的服务器节点成为 leader ,3、一段时间之后没有任何获胜者。

当 Candidate 收到了过半的服务器的回复,它便赢得了选举,状态由 Candidate 变成 Leader。当 Candidate 成为 Leader 时,会发送心跳消息给其他服务器,当 Candidate 收到了新 Leader 的心跳,状态会变回 Follower 表示集群中已经有新 Leader 了。如上图中的 S1.

在等待投票期间,candidate 可能会收到另一个声称自己是 Leader 的服务器节点发来的 AppendEntries RPC 。如果这个 Leader 的任期号(包含在RPC中)不小于 candidate 当前的任期号,那么 candidate 会承认该 leader 的合法地位并回到 follower 状态。 如果 RPC 中的任期号比自己的小,那么 candidate 就会拒绝这次的 RPC 并且继续保持 candidate 状态。如下图所示,S1是任期3的 Leader,而S3是任期3的 Candidate,当 S1 向 S3 发送 AppendEntries RPC(橙色),但是S3的任期大于S1,此时 S3 依然保持 Candidate 状态。

当选举过程中出现了选票瓜分而导致没有一个 Candidate 获得半数以上的选票,当 Candidate 超时后,会进入一个新的任期重新发送 RequestVote RPC。 Raft 为了避免上述一直重复的情况,选举时间会从一个固定区间进行随机选择,能够保证超时时间是分散开来。这样减小了在新的选举中再次发生选票瓜分情况的可能性。如图所示:

在上图中,S2 S3 S4 都是 Candidate 并且都在任期6,并且 S3 和 S4 均为2票,S2 为1票,此时无法决定新 Leader,当它们在一个随机时间内超时时(S3 最先超时),会进入新的任期7,并且发送新的 RequestVote RPC,第二次的选举没有出现瓜分的情况,最后 S3 选举成功成为了 Leader。

日志复制

当 Raft 选举出 Leader 后,Leader 开始接收客户端的指令,而当客户端发送一个请求给服务器时,Leader 将请求作为一个日志条目添加到日志中,并且发送 AppendEntries RPC 给其他的 Follower,当 Follower 收到 RPC,会复制该日志条目并且给 Leader 回复。当 Leader 收到过半的 Follower 的回复,Leader 会应用该条目到它的状态机中(状态机执行该指令)然后把执行的结果返回给客户端。如果出现 Follower 由于某种原因没有回复,即时已经过半并且回复客户端了,Leader 会一直重复发送 AppendEntries RPC 直到所有的 Follower 存储了该日志条目。

在 Raft 中,日志主要由状态机指令以及当时 Leader 收到指令时的任期号组成。其中状态机指令是客户端发送的指令,而任期号是为了防止副本之间不一致。Raft 的日志如下图所示

Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。一旦创建该日志条目的 leader 将它复制到过半的服务器上,该日志条目就会被提交(例如在图 6 中的条目 7)。同时,leader 日志中该日志条目之前的所有日志条目也都会被提交,包括由其他 leader 创建的条目。Leader 追踪将会被提交的日志条目的最大索引,未来的所有 AppendEntries RPC 都会包含该索引,这样其他的服务器才能最终知道哪些日志条目需要被提交。Follower 一旦知道某个日志条目已经被提交就会将该日志条目应用到自己的本地状态机中(按照日志的顺序)。

Raft 在日志复制的时候会有一个简单的一致性检查:在发送 AppendEntries RPC 的时候,leader 会将前一个日志条目的索引位置和任期号包含在里面。如果 follower 在它的日志中找不到包含相同索引位置和任期号的条目,那么他就会拒绝该新的日志条目。相反的,如果 Follower 返回成功了,则可以保证 Follower 和 Leader 相同,如下图所示

当然,如果只是一致性检查是无法满足需求的,比如如果 Leader 在还没有完全复制就崩溃了,会导致集群中出现数据不一致的情况,比如:缺少日志条目、出现未提交的日志等。

Raft 一般采用 Leader 强制 Follower 复制日志来实现不一致问题。通过找到一个与 Leader 相同的最大的条目索引,再将后面的日志覆盖的方法实现。主要实现是在回复一致性检查的时候,Leader 会针对每个 Follower 维护一个索引(nextIndex),表示 Leader 要发送给 Follower 的下一个日志条目的索引。当选出一个新 Leader 时,该 Leader 将所有 nextIndex 的值都初始化为自己最后一个日志条目的 index 加1,如果出现了一致性检查失败,Leader 会在下一次将 nextIndex 减小后重试,直到最终在某个位置达成一致,一致性检查成功。将 follower 中跟 leader 冲突的日志条目全部删除然后追加 leader 中的日志条目(如果有需要追加的日志条目的话)。一旦 AppendEntries RPC 成功,follower 的日志就和 leader 一致,并且在该任期接下来的时间里保持一致。

如果想要的话,该协议可以被优化来减少被拒绝的 AppendEntries RPC 的个数。例如,当拒绝一个 AppendEntries RPC 的请求的时候,follower 可以包含冲突条目的任期号和自己存储的那个任期的第一个 index 。借助这些信息,leader 可以跳过那个任期内所有冲突的日志条目来减小 nextIndex;这样就变成每个有冲突日志条目的任期需要一个 AppendEntries RPC 而不是每个条目一次。在实践中,我们认为这种优化是没有必要的,因为失败不经常发生并且也不可能有很多不一致的日志条目。

安全性

选举限制

在上述对 Raft 的描述中,可能有疑问,如果选举出来的 Leader 对于整个集群来说,日志条目不是最新的,这时候新 Leader 可能需要将数据同步成最新的后,再对其他没有完全复制的 Follower 发送 AppendEntries RPC,实现起来会很麻烦。在 Raft 中,是通过保证新 Leader 在当选时就包含了之前所有任期号中已经提交的日志条目,不需要再传送这些日志条目给新 Leader 。这意味着日志条目的传送是单向的,只从 Leader 到 Follower,并且 Leader 从不会覆盖本地日志中已经存在的条目。

Raft 规定:RequestVote RPC 中包含了 candidate 的日志信息,如果投票者自己的日志比 candidate 的还新,它会拒绝掉该投票请求。

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

在 Raft 中,如果在 Leader 发送给 Follower AppendEntries RPC 后,提交之前崩溃了,后面选举出的新 Leader 是不会主动去提交这个条目的,甚至新的 Leader 有可能会覆盖这个日志条目,下面分几种情况讨论:

旧 Leader 发送的 AppendEntries RPC 已经到过半结点

当 Leader 将日志复制给过半的 Follower,如下图所示,黑色的结点为已经复制的结点

此时 Leader 还没有提交日志就崩溃了,但是已经复制的结点仍然有2个,没复制的结点也有2个,而在选举限制中有:如果投票者自己的日志比 candidate 的还新,它会拒绝掉该投票请求。所以未复制的结点最终只有2票,是不可能成为新 Leader 的,最终 已经复制日志的结点会成为 Leader。

新 Leader 选举后,它并不会直接提交这个复制过半的日志条目,它会在下一个日志条目提交的时候,和旧的日志条目一起提交,论文中称为:间接地提交前任的日志条目。

raft10.gif

如上图所示,S1 为一开始的 Leader,在 S1 发送任期为2的日志给S2、S3后崩溃了,此时已经复制过半,S5 虽然率先超时成为了 Candidate,但是S2、S3由于选举限制拒绝投票导致S5只有2票无法成为 Leader,S3超时后成为了 Candidate 并且成功成为第4任 Leader,成为 Leader 后,S3 不会直接提交任期2的日志,而是在提交任期4的日志的时候把前任的日志一起提交。

注意:网上有部分博客说新 Leader 会发送空日志让 Follower 提交前任的日志,但是在动画中并没有体现出来,这种说法有待商榷

旧 Leader 发送的 AppendEntries RPC 未过半

当 Leader 将日志复制给 Follower 但未过半,如下图所示,黑色的结点为已经复制的结点

此时还没有提交就崩溃了,此时集群中已经复制的 Follower 有1个,未复制的有3个,此时就不能保证新 Leader 一定是已经复制日志的结点。所以此时又有两种情况

如果新 Leader 包含了前任日志条目,和上一种情况一样,会间接地提交。

如果新 Leader 不包含前任的日志条目,此时新 Leader 有新日志要复制,发送 AppendEntries RPC 给其他 Follower,其他含有前任未提交日志的 Follower 会覆盖前任的日志

如上图所示,S1 发送了2个任期2的日志,但是只有S2复制了(未过半),S1就崩溃了,此时 S5 成功成为新的 Leader,它在发送任期3的新日志给 Follower 时,Follower 会讲前任日志进行覆盖。

参考资料