Raft协议(三)

68人浏览 / 0人评论 / 添加收藏

前面的部分主要描述了Raft的核心流程,也提及了个别机制比如说在给定任期内最多只能选举一名领导人。但是在分布式系统中有很多种情况可能发生,还需要更为详细的安全机制来确保每个状态机都可以以相同的顺序执行完全相同的命令。因此,我们需要针对“领导者选举”以及“日志复制”额外加上一些安全属性,来完善整个Raft算法。除此之外,Raft也提供了一种快照机制来清楚日志中长期积累的陈旧信息。

本篇内容讲详细介绍这两个模块的内容,感兴趣的小伙伴多多点赞支持吧~

安全属性(Safety)
1)选举限制
综上所述,Leader在整个Raft机制中真的充当着非常重要必不可少的角色,因此Leader的选举重中之重。
我们来试想一个场景:当leader提交了多个日志条目时,follower如果此时不可用,还没来得及复制这些日志,就被选举为新任leader了,然后这个新任leader呢,又用新的日志条目覆盖了其他节点上面上任leader committed的日志条目。那么就会导致多个不同的状态机可能执行不同的命令序列。
因此,核心问题还是在于leader选举出现了问题,对于哪些服务器有资格当选leader的限制对于Raft算法的完善十分重要,前面我们已经提过了个别的限制,下面我们再明确细化一下:
 

  • 日志条目仅朝一个方向流动,leader永远不会覆盖其日志中的现有条目,也不会删除其日志中的条目,只能将新条目追加到其日志中(Leader Append-Only);
  • 在选举过程中,Candidate为了赢得选举,其日志中必须包含所有已提交的条目。为了当选,Candidate必须获得大多数服务器的投票才能当选新任leader,RequestVote RPC中包含有关Candidate日志的信息(term, index),如果其他服务器发现自己的日志比Candidate的日志新,那么将拒绝投票;

如何判定日志新旧?Raft通过比较日志中最后一个条目的index以及term来确定两个日志中哪一个更新。如果日志的最后一个条目有不同的term,那么更大的term对应的日志比较新。如果日志的term都相同,那么index大的日志更新。

2)Commit限制
Commit限制:通过计算副本数,仅提交leader当前term的日志条目。

为什么要增加这个限制?我们同样基于这个图进行场景模拟就知道了。
 

  • 阶段(a):S1是leader,收到请求后仅复制index2的日志给了S2,尚未复制给S3 ~ S5;
  • 阶段(b):S1崩溃,S5凭借 S3、S4 和自身的投票当选为term3的leader,收到请求后保存了与index2不同的条目(term3),此时尚未复制给其他节点;
  • 阶段(c):S5崩溃,S1重新启动,当选为新任leader(term4),并继续复制,将term2, index2复制给了 S3。这个时候term2,index2已经的日志条目已复制到大多数的服务器上,但是还没提交。
  • 阶段(d):如果S1如d阶段所示,又崩溃了,S5重新当选了leader(获得S2、S3、S4的选票)然后将 term3, index2的条目赋值给了所有的节点并commit。那这个时候,已经 committed 的 term2, index2被 term3, index2覆盖了。

因此,为了避免上述情况,commit需要增加一个额外的限制:仅commit leader当前term的日志条目。
举个例子,比如在c阶段,即使term4的时候S1已经把term2, index2复制给了大多数节点,但是它也不能直接将其commit,必须等待term4的日志并成功复制后一起commit。
所以除非说阶段c中term2, index2始终没有被 commit,这样S5在阶段d将其覆盖就是安全的,在要么就是像阶段e一样,term2, index2跟term4, index3一起被 commit,这样S5根本就无法当选leader,因为大多数节点的日志都比它新,也就不存在前边的问题了。

3)Follower 和 Candidate 崩溃
Follower和Candidate崩溃相对来说比Leader节点崩溃更好处理,如果Follower和Candidate出现了问题,那么也就意味着RequestVote和AppendEntries RPC将失败。Raft会无限期的重试,直到服务器重新启动,RPC将成功完成。如果很不凑巧,Follower和Candidate节点是在完成RPC之后但在响应之前崩溃,那么它将在重新启动后再次收到相同的 RPC。

4)时间安排和可用性
Raft的安全机制不能依赖于时间(如果与预期时间不符,可能会导致一系列问题),但是可用性(系统及时响应客户端的能力)必然取决于时间,比如领导者选举必须有时间限制,否则系统无法运行下去。
领导者选举是Raft机制中最关键的一个模块。只要系统满足以下时间安排,Raft就能够顺利选举初一个稳定的Leader:
broadcastTime ≪ electionTimeout ≪ MTBF
 

  • BroadcastTime:是服务器向集群中的每个服务器并行发送 RPC 并接收其响应所需的平均时间; 
  • ElectionTimeout:是前面所描述的选举超时时间;
  • MTBF:是单个服务器的平均故障间隔时间;

在时间长短来看,广播时间是最短的,以便leader在当选后能够更可靠快速地发送心跳消息,以便阻止follower选举冲突;由于选举超时采用的是随即方法,这种方法可以降低分散选票的几率,选举超时时间比MTBF会小几个数量级。当leader节点崩溃时,系统在选举超时时间内不可用。因此,为了维持整个系统的完美可用性,选举超时时间仅占总时间的一小部分,防止影响系统运行。
BroadcastTime以及MTBF的时间具体由底层系统决定,但是ElectionTimeout时间是我们需要自行设定的。

快照机制
正如前面所介绍的内容,Raft核心算法维护了日志的一致性,通过apply日志我们就可以得到一致的状态机,客户端的操作命令会被包装成日志交给 Raft 处理。但是大家有没有想过一个问题,随着客户端请求的增多,这些日志是不是会越来越长,占用越来越高的存储空间?而且,每次系统重启时都需要完整回放一遍所有日志才能得到最新的状态机。如果没有某种机制来清除日志中积累的陈旧信息,最终就会导致可用性问题影响整个系统的运行。

所以,为了避免这一情况的发生,Raft采用了最简单的日志压缩方法--快照(Snapshot)。简单来说,就是将某一时刻系统的状态 dump 下来并落地存储,这样该时刻之前的所有日志条目就都可以丢弃了(也包括先前的快照)。每个服务器独立拍摄快照,仅覆盖committed完成的日志,因为只有committed日志才是确保最终会应用到状态机的。
 

上图展示了服务器用新快照替换了其日志中已提交的条目(index1-index5),新快照仅存储当前状态(变量x、y)。快照中显示的last included index以及的last included term用于定位日志位置以及支持AppendEntries一致性检查。

Follower可以保持最新状态的方法就是leader通过网络向其发送最新快照。比如,当follower落后的时候,leader需要向其同步日志,但是这个时候假设leader已经做了快照,旧的日志已经被删除,leader就可以使用InstallSnapshot RPC向落后的follower发送快照,其中将包含该follower未包含的新信息。同样,当集群中有新节点加入,或者某个节点宕机太久落后了太多日志时,leader也可以直接发送快照,节约了大量日志传输和回放时间。

全部评论