Raft共识算法 (3)

如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中,S1 是领导者,部分的复制了索引位置 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中几种情况的思考 follower节点与leader日志内容不一致时怎么处理?

Raft共识算法


我们先举例说明:正常情况下,follower节点应该向B节点一样与leader节点日志内容一致,但也会出现A、C等情况,出现了不一致,以A、B节点为例,当leader节点向follower节点发送AppendEntries<prevLogIndex=7,prevLogTerm=3,entries=[x<-4]>,leaderCommit=7时,我们分析一下发生了什么,B节点日志与prevLogIndex=7,prevLogTerm=3相匹配,将index=7(x<-5)这条entry提交committed,并在日志中新加入entryx<-4,处于uncommitted状态;A节点接收到时,当前日志index<prevLogIndex与prevLogIndex=7,prevLogTerm=3不相匹配,拒接该请求,不会将x<-4添加到日志中,当leader知道A节点因日志不一致拒接了该请求后,不断递减preLogIndex重新发送请求,直到A节点index,term与prevLogIndex,prevLogTerm相匹配,将leader的entries复制到A节点中,达成日志状态一致。

我们看一下附加日志 RPC(由领导人负责调用复制日志指令;也会用作heartbeat)的定义:
| 参数 | 解释 |
|----|----|
|term| 领导人的任期号|
|leaderId| 领导人的 Id,以便于跟随者重定向请求|
|prevLogIndex|新的日志条目紧随之前的索引值|
|prevLogTerm|prevLogIndex 条目的任期号|
|entries[]|准备存储的日志条目(表示心跳时为空;一次性发送多个是为了提高效率)|
|leaderCommit|领导人已经提交的日志的索引值|

返回值 解释
term   当前的任期号,用于领导人去更新自己  
success   跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真  

接收者实现:

如果 term < currentTerm 就返回 false;

如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配,则返回 false;

如果已经存在的日志条目和新的产生冲突(索引值相同但是任期号不同),删除这一条和之后所有的;

附加日志中尚未存在的任何新条目;

如果 leaderCommit > commitIndex,令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个;

简单总结一下,出现不一致时核心的处理原则是一切遵从leader。当leader向follower发送AppendEntry请求,follower对AppendEntry进行一致性检查,如果通过,则更新状态信息,如果发现不一致,则拒绝请求,leader发现follower拒绝请求,出现了不一致,此时将递减nextIndex,并重新给该follower节点发送日志复制请求,直到找到日志一致的地方为止。然后把follower节点的日志覆盖为leader节点的日志内容。

leader挂掉了,怎么处理

前面可能断断续续的提到这种情况的处理方法,首要的就是选出新leader,选出新leader后,可能上一任期还有一些entries并没有提交,处于uncommitted状态,该怎么办呢?处理方法是新leader只处理提交新任期的entries,上一任期未提交的entries,如果在新leader选举前已经被大多数节点记录在日志中,则新leader在提交最新entry时,之前处于未提交状态的entries也被committed了,因为如果两个日志包含了一条具有相同index和term的entry,那么这两个日志在这个index之前的所有entry都相同;如果在新leader选举前没有被大多数节点记录在日志中,则原有未提交的entries有可能被新leader的entries覆盖掉。

出现网络分区时怎么处理?

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

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