MIT6.824 分布式系统实验 (3)

或者,候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号,且候选人的Log记录长度大于等于本地Log记录的长度

becomeCandidate时,立即开始选举,当然,这时候需要一些前序步骤:将term++标识进入了新的term,将votedfor置为me表示投票给自己了。

选举方:选举过程需要一个“得票数”的变量votesRcvd来记录已得票数(在分布式系统中,它的增加需要原子操作,因此用一个锁sync.cond锁来保护),此外,还要用一个finish变量来确定已经做出回答的server有多少。每当得到一枚票,就唤醒(broadcast)一次cond锁,堵塞疏通,做出“继续等待/处理最终票数/直接return”的选择。其中,继续等待是当票数不够一半,但还有server没有做出回复的时候。处理最终票数是剩余情况。直接return比较特殊,因为可能在等待得票的过程中,本candidate已经不是candidate了,可能降级为follower了。处理最终票数就很简单了,如果够一半就升级为leader(开始心跳goroutine),不够就变成follower(此时是因为所有server都已经做出了回复所以开始处理最终票数的),处理最终票数的过程中,要通过判断和加锁的方式,确保本candidate仍然是candidate,且当前任期和得票的任期一样。

接待员(中间函数):构造args和reply,调用投票方的投票函数。对返回结果,只在voteGranted为true的时候返回true,否则返回false,如果reply.term更大,就令candidate降级为follower。同时,在处理期间也要保证本candidate是candidate的时候才有必要继续进行,但继续进行的时候,非必要不得对candidate加锁,否则容易形成死锁。

投票方:先检查args.term,如果比自己大,那就先承认一下自己的follower地位, 如果args.term比自己小,那就voteGranted置为false,让选举方承认自己follower的地位,并且返回,没必要再理会这次选举。继续处理的是args.term>=自己的情况。如果还没投,或者已经投给了这个candidate,并且term相同的话选举方log更长,那就投给选举方,并且reset选举超时计时器。否则不投。简而言之,投票要检查term,term相等的话看log是不是新于自己,以及票是不是已经投出去了。

设计技巧:

将单个询问、处理回复和分发、回收分为两个过程。前者是接待员,为单个投票方提供单个接待服务,后者是总管,给各个投票方分配出各自的接待员。

尽量不加锁,或者锁粒度尽可能小,在处理的时候判断一下是不是状态还未过时。

【日志复制】

接待员(发送方/中间函数):取出目标server对应的nextIndex和matchIndex。如果nextIndex,即即将发送的entries的开始位置,<=snapshotLastIndex,就是已经被压缩了,那就将snapshot发送给目标server,返回。如果nextIndex在log里,就构造AppendEntriesArgs,把nextIndex后面所有的entries全发送过去,这时,要附带nextIndex-1这一条的index和term,用来给目标server做一致性检查。对于返回值,首先检查term判断是否本leader需要降级为follower,然后再判断是否成功。如果成功,就更新nextIndex和matchIndex,再看看需不需要commit。如果不成功,那就是一致性检查出问题了,找到冲突点,重新执行接待任务。

快速回退法: 发生冲突的时候,让follower返回足够的信息给leader,这样leader可以以term为单位来回退,而不用每次只回退一条log条目,因此当log不匹配的时候,leader只需要在每个不同的term发送一条appendEntries,这是一种加速策略。

冲突点回溯:找到args.PrevlogTerm的第一条log的index,就是目前看来的冲突index。不会往之前的term找,因为无法确定那里是不是冲突了。这个冲突index可能会有点悲观,这里会增加网络负载,可以优化。

MIT6.824 分布式系统实验

设计技巧:

matchIndex只在发送成功的时候更新,并且是为了commit设置的。follower的commitIndex始终是随着AppendEntriesArgs带来的leader的commitIndex更新的,自己不能主动判断更新。另,commit的时候会唤醒applyCond。

nextIndex总是很乐观的,靠一致性检查和冲突点回溯来防止错误。

一条log entry的index和它在log中的下标不是同一个东西。

对log的操作可能很多,设计一个log类来专门管理这些操作,像cmu数据库一样写一些基本的常用操作函数。

向管道中塞东西,可能会发生堵塞,因此要使用goroutine。例如 go rf.applyCh<-msg

appendNewentry时的index

关于日志复制时可能出现的异常情况讨论

如果leader正常工作,raft系统中不会出现什么问题,follower只需要接收leader发来的日志信息,将log的状态与leader的log状态靠齐即可。

一个旧leader故障之后,新的leader是否可以使系统达到一致?

假设现在系统中有三台机器,S1,S2和S3,其中S3是旧的leader,且系统此刻是一致的。S3可能引发不一致的故障时刻有三种:

将新条目添加到本地log之后立即故障:根据多数选举的规则,S1和S2中可以出现新的leader,系统继续服务。

将新条目添加到S1之后故障:S1可以成为leader,系统继续服务,S1会将这条条目传递给其他机器并且提交。

将新条目添加到S1并且提交之后故障:同上。

因此,旧leader S3故障之后,剩下的团体也可以正常服务。如果此时旧leader重新与集群建立了联系,系统将会如何?

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

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