学习Raft算法的笔记 (3)

要使得跟随着的日志进入和自己一致的状态,领导人必须找到最后两者达成一致的地方,然后删除那个点之后的所有日志条目,发送自己的日志给跟随者。所有的这些日志操作都在进行附加日志RPCs的一致性检查时完成。领导人针对没一个维护者维护了一个nextIndex,这表示下一个发送给追随者的日志条目的索引地址。当一个领导人刚获得领导者的权利的时候,他初始化所有的nextIndex值作为自己的最后一条日志的index加1。如果一个跟随者的日志和领导人不一致,那么下一次日志附RPC时的一致性检查就会失败。在被跟随者拒绝之后,领导人就会减少nextIndex值并进行重试。最终nextIndex会在某个位置使得领导人和跟随者的日志达成一致。当这种情况发生,附加日志RPC就会成功,这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志RPC成功,那么跟随者的日志就会和领导人保持一直,并且在接下来的任期里一直继续保持。

安全性

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的日志来间接提交(log Index 小于commit Index的日志被间接提交)
之所以要这样,是因为可能会出现已提交的日志被覆盖的情况:

已提交的日志被覆盖

如图的时间序列展示了领导人无法决定对老任期号的日志条目进行提交。在(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的要求之一就是安全性不能依赖时间:整个系统不能因为某些事件运行的比预期快一点或者慢一点产生了错误的结果。但是,可用性(系统可以及时的响应客户端)不可避免的要依赖时间。例如,如果消息交换比服务器故障间隔时间长,候选人没有足够长的时间来赢得选举,没有一个稳定的领导人,Raft将无法工作。
领导人选举时Raft中对时间要求最为关键的方面。Raft可以选举并维持一个稳定的领导人,只需要满足下面的时间要求:

广播时间(broadcastTime) << 选举时间(election Timeout) << 平均故障时间(MTBF)

在这个不等式中,广播时间指的时从一个服务器并行的发送RPCs给集群中的其他服务器并接收平均时间,选举超时时间(150ms-300ms)选举超时时间限制,然后平均故障时间就是对于一台服务器而言,两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级,这样领导人才能发送稳定的心跳消息来阻止跟随者开始进入选举状态,通过随机化选举超时时间的方法,整个不等式也使得选票瓜分的情况变成不肯能。选举选举超时时间要比平局故障时间间隔小上几个数量级,这样系统才能稳定的运行。当领导人崩溃后,整个系统会大约相当于超时时的时间里不可用。我们希望这种情况在系统中国运行很少出现。

广播时间和平均故障间隔时间是由系统决定的,但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去,所以广播时间大约是 0.5 毫秒到 20 毫秒,取决于存储的技术。因此,选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长,很容易满足时间的需求。

成员变更

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjsxz.html