前言

继续上一次的Lab2,这次我们对PartB部分进行分析,这一部分我们需要完成日志的部分。

正文

准备工作

具体的论文的内容(5.3和5.4.1)不再赘述,这里我们来重点看下几个重要的参数,论文中讲述的不是特别明确或者说是比较难理解。

日志同步

raft认为当一个entry已经复制到大部分的节点后,这个entry就是已经是committed了,并且也通过选主的机制确保了这一特性,然后为了让Follower的状态能够和Leader的状态保持一致,那么就需要寻找到最后一个相同的entry(根据不同日志中拥有相同的term和index那么之前的日志都是相同的),那么Follower就会复制这之后的Leader的日志。Leader通过维护一个nextIndex[]数组,意思是对于每一个节点,下一个将要发给它的日志的索引值,当某个节点成为Leader后,初始化nextIndex为自己的下一个log entry,当AppendEntries发送匹配失败后,Leader尝试减小nextIndex对应的值重新发送rpc请求直到一致为止。

如何确保Leader拥有所有committed的日志

那么Leader如何确保包含所有的已经commited的日志呢,这里就是通过在选举的时候确保candidate必须比大部分节点的log要新才能够获得选举的胜利,通过比较term和index。

machIndex是什么

此外Leader还会维护一个matchIndex[]数组用来记录Leader认为已经匹配的最大的索引值,matchIndex[]并不是一定直接说等于nextIndex-1,因为nextIndex是先初始化为Leader的log entry+1,所以按照逻辑来看nextIndex是一个乐观估计,认为Follower能够直接和Leader的记录匹配,而matchIndex是一个保守估计,是成功更新日志后再更新matchIndex。

PreLogIndex是什么

然后还有一个难点是PreLogIndex是什么,该怎么选取。论文中是这样子表述的index of log entry immediately preceding new ones意思是紧跟new ones的那个日志的索引,这里我们要弄清楚new ones到底是什么:new ones指的是Leader认为应该即将发送给Follower的日志,所以PreLogIndex应该是指Leader认为Follower已经同步的最高的日志,那么他就应该是nextIndex[Follower]-1,注意它不应该是的matchIndex[Follower],因为我们要用更加积极的估计,如果匹配失败我们还可以调整PreLogIndex的值。

applyCh是干什么的

我们通过applyCh将ApplyMsg这个消息发送出去,(这里需要commitIndex<lastApplied),来让entry应用到节点上。

何时加锁

当要改变结构体中的相关参数时,当要读取结构体中的可变参数时都需要加锁

结构剖析

好终于进入正题,同样前面准备一些简单格式化输出函数,随机函数就不再赘述了,直接看raft的节点结构体

然后在前面还要声明下日志的结构体,具体介绍在注释里面了

之后是RequestVote rpc需要的结构体参数

这里只需要添加一个LastLogIndex和LastLogTerm来记录candidate的最后的日志的情况。

重点来看RequestVote()这里的逻辑,这里有一个坑点。

这里首先判断请求的term是否大于rf的term,如果是小于,或者是两者的term相等,但是rf已经投票给了其他人,那么就返回false。然后如果请求的term大于rf的term,那么更新rf的term,然后rf要转变为Follower一下。然后根据前面的选举限制,需要比较哪个日志比较新来判断是否接受更新,最后无论是否投票成功都需要更新server的term

错误的写法:

看到不同点在哪里了么?所以我们需要严格按照论文的要求进行完成

再继续看AppendEntries

看AppendEntries()函数

首先是寻找相同的日志,通过判断相同索引的term是否相同判断是否是同一entry,注意还要判断是否数组越界。

然后寻找第一个不匹配的日志,通过这个索引来更新节点的日志,注意每次更新完节点都需要判断一下是否需要更新commitIndex,然后调用sendApplyMsg()判断是否需要发送ApplyMsg来进行应用。

再看Start()函数

当客户要求添加日志时,首先判断是否是Leader,如果是Leader那么添加日志,更新nextInex,matchIndex。

看Make()函数

添加几个rf参数的初始化

然后convertTo()函数需要修改一些东西,当转变为Leader时需要初始化一下nextIndex和matchIndex。

然后是sendApplyMsg()是怎么发送ApplyMsg

注意判断是否需要Apply,然后应该用goroutine以防止阻塞,但是channel那里不需要加锁。

最后我们关注两个最重要的动作函数,startElection()和broadcastHeartbeat()函数

调整的不多就是添加了几个参数

broadcastHeartbeat():

这里不仅需要添加几个参数,还要判断是否Leader已经将日志添加到大部分的Follower中,才能更新commitIndex,然后还有一个nextIndex的修正。

结果

这里写了脚本进行测试,因为有可能一次测试不出来是否没有错误,需要跑循环

总结

时间效率待优化,跑的有点太慢了差一点就超时了,回头继续想想。