解读Raft(一 算法基础) (2)

用于Leader节点复制日志给其他节点,也作为心跳。

参数 解释
term   Leader节点的任期  
leaderId   Leader节点的ID  
prevLogIndex   此次追加请求的上一个日志的索引  
prevLogTerm   此次追加请求的上一个日志的任期  
entries[]   追加的日志(空则为心跳请求)  
leaderCommit   Leader上已经Commit的Index  

prevLogIndex和prevLogTerm表示上一次发送的日志的索引和任期,用于保证收到的日志是连续的。

返回值 解释
term   当前任期号,用于Leader节点更新自己的任期(应该说是如果这个返回值比Leader自身的任期大,那么Leader需要更新自己的任期)  
success   如何Follower节点匹配prevLogIndex和prevLogTerm,返回true  

接收者实现逻辑

返回false,如果收到的任期比当前任期小

返回false,如果不包含之前的日志条目(没有匹配prevLogIndex和prevLogTerm)

如果存在index相同但是term不相同的日志,删除从该位置开始所有的日志

追加所有不存在的日志

如果leaderCommit>commitIndex,将commitIndex设置为commitIndex = min(leaderCommit, index of last new entry)

RequestVote RPC

用于Candidate获取选票。

参数 解释
term   Candidate的任期  
candidateId   Candidate的ID  
lastLogIndex   Candidate最后一条日志的索引  
lastLogTerm   Candidate最后一条日志的任期  
参数 解释
term   当前任期,用于Candidate更新自己的任期  
voteGranted   true表示给Candidate投票  

接收者的实现逻辑

返回false,如果收到的任期比当前任期小

如果本地状态中votedFor为null或者candidateId,且candidate的日志等于或多余(按照index判断)接收者的日志,则接收者投票给candidate,即返回true

节点的执行规则

所有节点

如果commitIndex > lastApplied,应用log[lastApplied]到状态机,增加lastApplied

如果RPC请求或者响应包含的任期T > currentTerm,将currentTerm设置为T并转换为Follower

Followers

响应来自Leader和Candidate的RPC请求

如果在选举超时周期内没有收到AppendEntries的请求或者给Candidate投票,转换为Candidate角色

Candidates

转换为candidate角色,开始选举:

递增currentTerm

给自己投票

重置选举时间

发送RequestVote给其他所有节点

如果收到了大多数节点的选票,转换为Leader节点

如果收到Leader节点的AppendEntries请求,转换为Follower节点

如果选举超时,重新开始新一轮的选举

Leaders

一旦选举完成:发送心跳给所有节点;在空闲的周期内不断发送心跳保持Leader身份

如果收到客户端的请求,将日志追加到本地log,在日志被应用到状态机后响应给客户端

如果对于一个跟随者,最后日志条目的索引值大于等于 nextIndex,那么:发送从 nextIndex 开始的所有日志条目:

如果成功:更新相应跟随者的 nextIndex 和 matchIndex

如果因为日志不一致而失败,减少 nextIndex 重试

如果存在一个满足N > commitIndex的 N,并且大多数的matchIndex[i] ≥ N成立,并且log[N].term == currentTerm成立,那么令commitIndex等于这个N

解读Raft(一 算法基础)

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

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