对 Raft 算法的深入分析

分布式存储系统通常通过维护多个副本来进行容错,提高系统的可用性。要实现此目标,就必须要解决分布式存储系统的最核心问题:维护多个副本的一致性。

在一个具有一致性的性质的集群里面,同一时刻所有的结点对存储在其中的某个值都有相同的结果,即对其共享的存储保持一致。集群具有自动恢复的性质,当少数结点失效的时候不影响集群的正常工作,当大多数集群中的结点失效的时候,集群则会停止服务(不会返回一个错误的结果)。

本文用于记录对于 Raft 算法学习的一些总结。

Leader election

Raft协议的每个副本都会处于三种状态之一:Leader、Follower、Candidate。

  1. Leader:所有请求的处理者,Leader 副本接受 client 的更新请求,本地处理后再同步至多个其他副本。
  2. Follower:请求的被动更新者,从 Leader 接受更新请求,然后写入本地日志文件。
  3. Candidate:如果 Follower 副本在一段时间内没有收到 Leader 副本的心跳,则判断 Leader 可能已经故障,此时启动选主过程,此时副本会变成 Candidate 状态,直到选主结束。

Raft 算法将时间分为一个个的任期(term),每一个 term 的开始都是 Leader 选举。在成功选举 Leader 之后,Leader 会在整个 term 内管理整个集群。如果 Leader 选举失败,该 term 就会因为没有 Leader 而结束。

选举的过程会有三种结果:

  1. 自己被选成了主。当收到 2/N + 1 个投票后,该节点成为 leader,定期给其他所有节点发送心跳信息。term id 在每个 rpc 消息中都会带上用于检查过期消息,当一个节点收到的 rpc_term_id 比本地的 current_term_id 更大时,就更新 current_term_id 为 rpc_term_id,如果该节点当前的 state 为 leader 或者 candidate,则将 state 切换为 follower。如果 rpc_term_id 比自己本地的 current_term_id 还要小,则拒绝该 rpc 消息。
  2. 别人成了主。如上所述,如果一个 candidate 收到了大于本地 current_term_id 的 rpc 消息,将 state 切换成 follower。
  3. 没有选出主。如果没有任何一个节点收到 majority vote 时,每个 candidate 等待超时后,candidate 等待后都会将 current_term_id 加一(各个 candidate 等待时间不同)再次发起 RequestVoteRPC 进行新一轮 leader election。candidate 的 election timeout 从 150ms-300ms 之间随机取,第一个超时的 candidate 会最先发起新一轮的 leader election,带着 term_id 给其它节点送 RequestVoteRPC 消息,从而自己成为 leader,然后给其他节点发送心跳消息以告诉他们自己是主。

Log Replication

Leader 选取出来后,就可以接受 client 发送过来的请求了,每个请求包含一个需要被 replicated state machine 执行的操作,leader 会把它做为一个 log entry append 到日志中,然后给其他的节点发送 AppendEntriesRPC 请求。

当 Leader 确定一个 log entry 被 safely replicated了 也就是说呗大多数副本已经将该命令写入日志当中,就 apply 这条 log entry 到 state machine 中然后返回结果给客户端。如果某个 Follower 宕机了或者运行的很慢或者网络丢包了,就一直给这个 Follower 发 AppendEntriesRPC 直到日志一致。

当一条日志是 commited 时,Leader 才可以将它应用到状态机中。Raft 保证一条 commited 的 log entry 已经持久化了并且会被所有的节点执行。当一个新的 Leader 被选出来时,它的日志和其它的 Follower 的日志可能不一样,这个时候,就需要一个机制来保证日志的一致性。一个新 Leader 产生时,集群状态可能如下:

最上面这个是新 Leader,a~f 是Follower,每个格子代表一条 log entry,格子内的数字代表这个 log entry 是在哪个 term 上产生的。新 Leader 产生后,就以 Leader 上的 log 为准。其它的 follower 要么少了数据比如 b,要么多了数据,比如 d,要么既少了又多了数据,比如 f。

因此,需要有一种机制来让 Leader 和 Follower 对 log 达成一致,Leader 会为每个 Follower 维护一个 nextIndex,表示 Leader 给各个 Follower 发送的下一条 log entry 在 log 中的 index。初始化为 Leader 的最后一条 log entry 的下一个位置。Leader 给 Follower 发送 AppendEntriesRPC 消息,带着 (term_id, (nextIndex-1)), term_id 即 (nextIndex-1) 这个槽位的 log entry 的 term_id ,Follower 接收到 AppendEntriesRPC 后,会从自己的 log 中找是不是存在这样的 log entry,如果不存在,就给 Leader 回复拒绝消息,然后 Leader 将 nextIndex 减1,再重复,直到 AppendEntriesRPC 消息被接收。

以 Leader 和 Follower b 为例:

初始化,nextIndex 为11,Leader 给 b 发送 AppendEntriesRPC(6,10),b 在自己 log 的 10 号槽位中没有找到 term_id 为 6 的 log entry。则给 Leader 回应一个拒绝消息。接着,Leader 将 nextIndex 减一,变成 10,然后给 b 发送 AppendEntriesRPC(6, 9),b 在自己 log 的 9 号槽位中同样没有找到 term_id 为 6 的 log entry。循环下去,直到 leader 发送了 AppendEntriesRPC(4,4),b 在自己 log 的槽位 4 中找到了 term_id 为 4 的 log entry。接收了消息。随后,Leader 就可以从槽位 5 开始给 b 推送日志了。

Safety

Raft增加了如下两条限制以保证安全性(下面两点非常重要,之前看 Raft 很多一致性问题没法领会就是这两点没理解):

  1. 拥有最新的已提交的 log entry 的 Follower 才有资格成为 Leader。这个保证是在 RequestVote RPC 中做的,Candidate 在发送 RequestVote RPC 时,要带上自己的最后一条日志的 term 和 log index,其他节点收到消息时,如果发现自己的日志比请求中携带的更新,则拒绝投票。日志比较的原则是,如果本地的最后一条 log entry 的 term 更大,则 term 大的更新,如果 term 一样大,则 log index 更大的更新。
  2. Leader 只能推进 commit index 来提交当前 term 的已经复制到大多数服务器上的日志,旧 term 日志的提交要等到提交当前 term 的日志来间接提交(上面有提到)。之所以要这样,是因为可能会出现已提交的日志又被覆盖的情况:

img

  1. 在阶段 a,term 为 2,S1 是Leader,且 S1 写入日志(term, index) 为 (2, 2),并且日志被同步写入了 S2。
  2. 在阶段 b,S1 离线,触发一次新的选主,此时 S5 被选为新的 Leader,此时系统 term 为 3,且写入了日志 (term, index)(3, 2)
  3. S5 尚未将日志推送到 Followers 离线了,进而触发了一次新的选主,而之前离线的 S1 经过重新上线后被选中变成 Leader,此时系统 term 为 4,此时 S1 会将自己的日志同步到 Followers,按照上图就是将日志 (2, 2) 同步到了 S3,而此时由于该日志已经被同步到了多数节点 (S1, S2, S3),因此,此时日志 (2, 2) 可以被 commit 了即更新到状态机。
  4. 在阶段 d,S1 又很不幸地下线了,系统触发一次选主,而 S5 有可能被选为新的 Leader 这是因为 S5 可以满足作为主的一切条件(这个地方我第一次 Paper 的时候体会了很久,注意在阶段 d,S5 的 term 为 5):
    1. term = 3 > 2
    2. 最新的日志 index 为 2,比大多数节点如 S2/S3/S4 的日志都新,然后 S5 会将自己的日志更新到 Followers,于是 S2/S3 中已经被提交的日志 (2,2) 被截断了,这是致命性的错误,因为一致性协议中不允许出现已经应用到状态机中的日志被截断。

为了避免这种致命错误,需要做一个调整:只允许主节点提交包含当前 term 的日志

针对上述情况就是:即使日志 (2,2) 已经被大多数节点 S1/S2/S3 确认了,但是它不能被 commit,因为它是来自之前 term2 的日志,直到 S1 在当前 term4 产生的日志 (4, 3) 被大多数 Follower 确认,S1 方可 Commit (4, 3) 这条日志,当然,根据 Raft 定义,(4, 3) 之前的所有日志也会被 commit。此时即使 S1 再下线,重新选主时 S5 不可能成为 Leader,因为它没有包含大多数节点已经拥有的日志 (4, 3)。

日志压缩

在实际的系统中,不能让日志无限增长,否则系统重启时需要花很长的时间进行回放,从而影响可用性。Raft 采用对整个系统进行 snapshot 来解决,snapshot 之前的日志都可以丢弃。每个副本独立的对自己的系统状态进行 snapshot,并且只能对已经提交的日志记录进行 snapshot。

做 snapshot 既不要做的太频繁,否则消耗磁盘带宽, 也不要做的太不频繁,否则一旦节点重启需要回放大量日志,影响可用性。推荐当日志达到某个固定的大小做一次 snapshot。做一次 snapshot 可能耗时过长,会影响正常日志同步。可以通过使用 copy-on-write 技术避免 snapshot 过程影响正常日志同步。成员变更不能影响服务的可用性,但是成员变更过程的某一时刻,可能出现在 Cold 和 Cnew 中同时存在两个不相交的多数派,进而可能选出两个 Leader,形成不同的决议,破坏安全性。

成员变更

成员变更是在集群运行过程中副本发生变化,如增加/减少副本数、节点替换等。成员变更也是一个分布式一致性问题,既所有服务器对新成员达成一致。但是成员变更又有其特殊性,因为在成员变更的一致性达成的过程中,参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题,直接向 Leader 发送成员变更请求,Leader 复制成员变更日志,达成多数派之后提交,各服务器提交成员变更日志后从旧成员配置(Cold)切换到新成员配置(Cnew)。因为各个服务器提交成员变更日志的时刻可能不同,造成各个服务器从旧成员配置(Cold)切换到新成员配置(Cnew)的时刻不同。

为了解决这一问题,Raft 提出了两阶段的成员变更方法。集群先从旧成员配置 Cold 切换到一个过渡成员配置,称为共同一致(joint consensus),共同一致是旧成员配置 Cold 和新成员配置 Cnew 的组合Cold U Cnew,一旦共同一致 Cold U Cnew 被提交,系统再切换到新成员配置 Cnew。

Raft 两阶段成员变更过程如下:

  1. Leader 收到成员变更请求从 Cold 切成 Cnew。
  2. Leader 在本地生成一个新的 log entry,其内容是 Cold U Cnew,代表当前时刻新旧成员配置共存,写入本地日志,同时将该 log entry 复制至 Cold U Cnew 中的所有副本。在此之后新的日志同步需要保证得到 Cold 和 Cnew 两个多数派的确认。
  3. Follower 收到 Cold U Cnew的 log entry 后更新本地日志,并且此时就以该配置作为自己的成员配置。
  4. 如果 Cold 和 Cnew 中的两个多数派确认了 Cold U Cnew 这条日志,Leader 就提交这条 log entry。
  5. 接下来 Leader 生成一条新的 log entry,其内容是新成员配置 Cnew,同样将该 log entry 写入本地日志,同时复制到 Follower 上。
  6. Follower 收到新成员配置 Cnew 后,将其写入日志,并且从此刻起,就以该配置作为自己的成员配置,并且如果发现自己不在 Cnew 这个成员配置中会自动退出。
  7. Leader 收到 Cnew 的多数派确认后,表示成员变更成功,后续的日志只要得到 Cnew 多数派确认即可。Leader 给客户端回复成员变更执行成功。

异常分析:

  • 如果 Leader 的 Cold U Cnew 尚未推送到 Follower,Leader 就挂了,此后选出的新 Leader 并不包含这条日志,此时新 Leader 依然使用 Cold 作为自己的成员配置。
  • 如果 Leader 的 Cold U Cnew 推送到大部分的 Follower后 就挂了,此后选出的新 Leader 可能是 Cold也 可能是 Cnew 中的某个 Follower。
  • 如果 Leader 在推送 Cnew 配置的过程中挂了,那么同样,新选出来的 Leader 可能是 Cold 也可能是 Cnew 中的某一个,此后客户端继续执行一次改变配置的命令即可。
  • 如果大多数的 Follower 确认了 Cnew 这个消息后,那么接下来即使 Leader 挂了,新选出来的 Leader 肯定位于 Cnew 中。

两阶段成员变更,之所以分为两个阶段,是因为对 Cold 与 Cnew 的关系没有做任何假设,为了避免 Cold 和 Cnew 各自形成不相交的多数派选出两个 Leader,才引入了两阶段方案。

如果增强成员变更的限制,假设 Cold 与 Cnew 任意的多数派交集不为空,这两个成员配置就无法各自形成多数派,那么成员变更方案就可能简化为一阶段。

那么如何限制 Cold 与 Cnew,使之任意的多数派交集不为空呢?方法就是每次成员变更只允许增加或删除一个成员。