Raft共识算法 (2)

对所有的请求(RequestVote、AppendEntry等请求),如果发现其Term小于当前节点,则拒绝请求,如果是candidate选举期间,收到不小于当前节点任期的leader节点发来的AppendEntry请求,则认可该leader,candidate转换为follower。

日志复制(Log replication)

leader选举成功后,将进入有效工作阶段,即日志复制阶段,其中日志复制过程会分记录日志和提交数据两个阶段。

整个过程如下:

首先client向leader发出command指令;(每一次command指令都可以认为是一个entry)

leader收到client的command指令后,将这个command entry追加到本地日志中,此时这个command是uncommitted状态,因此并没有更新节点的当前状态;

之后,leader向所有follower发送这条entry,follower接收到后追加到日志中,并回应leader;

leader收到大多数follower的确认回应后,此entry在leader节点由uncommitted变为committed状态,此时按这条command更新leader状态;

在下一心跳中,leader会通知所有follower更新确认的entry,follower收到后,更新状态,这样,所有节点都完成client指定command的状态更新。

可以看到client每次提交command指令,服务节点都先将该指令entry追加记录到日志中,等leader确认大多数节点已追加记录此条日志后,在进行提交确认,更新节点状态。如果还对这个过程有些模糊的话,可以参考Raft动画演示,较为直观的演示了领导人选举及日志复制的过程。

安全(Safety)

前面描述了Raft算法是如何选举和复制日志的。然而,到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。我们需要再继续深入思考以下几个问题:

第一个问题,leader选举时follower收到candidate发起的投票请求,如果同意就进行回应,但具体的规则是什么呢?是所有的follower都有可能被选举为领导人吗?

第二个问题,leader可能在任何时刻挂掉,新任期的leader怎么提交之前任期的日志条目呢?

选举限制

针对第一个问题,之前并没有细讲,如果当前leader节点挂了,需要重新选举一个新leader,此时follower节点的状态可能是不同的,有的follower可能状态与刚刚挂掉的leader相同,状态较新,有的follower可能记录的当前index比原leader节点的少很多,状态更新相对滞后,此时,从系统最优的角度看,选状态最新的candidate为佳,从正确性的角度看,要确保Leader Completeness,即如果在某一任期一条entry被提交成功了,那么在更高任期的leader中这条entry一定存在,反过来讲就是如果一个candidate的状态旧于目前被committed的状态,它一定不能被选为leader。具体到投票规则:
1) 节点只投给拥有不比自己日志状态旧的节点;
2)每个节点在一个term内只能投一次,在满足1的条件下,先到先得;

我们看一下请求投票 RPC(由候选人负责调用用来征集选票)的定义:
| 参数 | 解释|
|---|---|
|term| 候选人的任期号|
|candidateId| 请求选票的候选人的 Id |
|lastLogIndex| 候选人的最后日志条目的索引值|
|lastLogTerm| 候选人最后日志条目的任期号|

返回值 解释
term   当前任期号,以便于候选人去更新自己的任期号  
voteGranted   候选人赢得了此张选票时为真  

接收者实现:

如果term < currentTerm返回 false

如果 votedFor 为空或者为 candidateId,并且候选人的日志至少和自己一样新,那么就投票给他

可以看到RequestVote投票请求中包含了lastLogIndex和lastLogTerm用于比较日志状态。这样,虽然不能保证最新状态的candidate成为leader,但能够保证被选为leader的节点一定拥有最新被committed的状态,但不能保证拥有最新uncommitted状态entries。

提交之前任期的日志条目

领导人知道一条当前任期内的日志记录是可以被提交的,只要它被存储到了大多数的服务器上。但是之前任期的未提交的日志条目,即使已经被存储到大多数节点上,也依然有可能会被后续任期的领导人覆盖掉。下图说明了这种情况:

Raft共识算法

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

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