MIT 6.5840 Raft Implementation(2A, Leader Election)

Raft实现思路+细节

2A

任务分解

总体来说，2A中主要的任务就是选出领导人，在选出领导人的时候，我们要遵循下图。

在2A中，由于并没有出现日志复制，所以我们只需要考察两者的任期是否相等，以及接收者在本轮任期中有没有投票即可。

因而我们可以这样地给出2A中的实现内容：

• 完善GetState()函数，这样才能让评测机知道我们选出了Leader

• 完善Raft结构体（见论文上的State）

• 完善RequestVote()函数，按照上图中的逻辑

• 完善Make()函数，对成员进行初始化

• 完善ticker()和MakeElection()函数，在没有收到领导人信息的时候开始选举

• 初步写出heartbeat相关功能（只需要在接收时变成跟随者即可）

实现细节

1. 关于Raft结构体，基本上需要参考论文上的State即可。

   我在这里多加了一个safe状态（表示作为跟随者在这个周期内有没有收到领导人的信息，在收到RPC时置为true，在ticker()初始化和变成跟随者时变成false，若ticker()检查时为false，则直接开始选举），这样就模拟了发动选举的过程。(credit to @Vargvain )

2. 关于RequestVote()函数，在2A阶段我们先判断任期的大小关系，如果候选人更大，那就让接收者先同步任期，并变成追随者；如果接收者更大，就直接返回false。如果相等，那么就看是否已经投过票，如果投过，返回false，反之返回true。

   在这里，我建议封装好toCandidate(), toFollower(), toLeader()这几个函数，这样可以减少代码复用，而且用到的也确实挺多的。

3. 关于Make()函数，我们暂时只要给不同变量赋上初始值。

4. 关于ticker()函数。首先要做的是调整ElectionTimeout，论文中有提到heartbeatInterval << ElectionTimeout，并且通过分析可以发现ElectionTimeout中随机值上界不超过下界的两倍，我选择ElectionTimeout = 400 + (rand.Int63() % 400)。接下来就是看是否是一个not safe的跟随者，如果是这样，那就开始选举（一个Go程）。

   选举函数基本是2A中最大的难点。首先，我们需要给RequestVoteArgs赋好初始值，然后就对于每一个peer（当然，peerId != rf.me），处理RequestVoteReply，如果回复的任期更高，那就变成Follower，反之，统计票数，如果超过半数，就变成领导人。

5. 关于heartbeat，只需要依照RequestVoteRPC的格式完成基本的AppendEntriesRPC，并在变成领导人时给每个人发就行。

注意事项

关于锁的一些小建议（credit to @lauyeeyu）

• 尽量缩短 Lock() 和 Unlock() 之间的长度（更细的控制）
• 在Sleep或者耗时间的操作中不要持有锁，会占用进程，或导致死锁
• 小心控制流语句 (continue, break, return) 可能会跳过你写的 Unlock()
• 读写变量前别忘了上锁
• 必要时（为了缩短上锁区域的长度）可以变量先读到临时变量，然后就可以解锁了，之后读取可以使用临时变量（但是要小心数据修改可能的隐患）

关于并发

• 有必要再去了解一下并发进行的形式和原理
• 对于这种情况，如果里面不用_peerId会出问题，因为在新开的Go程进行到某一阶段时可能peerId已经发生了变化。
  

关于测试

总时长情况大概如下图：

关于每一个测试后面的四个数字意义，见MIT课程页面