Task

完成各种情况的领导人选举。

我们首先需要熟悉一下 Raft 的工作原理，建议先过一遍前置芝士。

Step

先完善 Raft 结构和 Make 函数，再结合 Gif 思考单个节点的状态。
节点开始时的状态是 Follower，election timeout 后，状态会改为 Candidate。我们应该如何设计选举超时，当然是开一个 go routinerf.ticker() 对超时进行检测。那么是用time.Sleep还是time.Timer实现呢？官方的建议是用 sleep，但我用的是 timer，也能够正常实现，并且我还实现了 sleep 的版本，感觉速度上相差无几。

ticker

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func (rf *Raft) ticker() {
	for !rf.killed() {
		select {
		case <-rf.heartbeatTimer.C:
			rf.mu.Lock()
			if rf.state == Leader {
				rf.startHeartbeatL(true)
				rf.heartbeatTimer.Reset(getHeartbeatDuration())
				rf.electionTimer.Reset(getElectionDuration())
			}
			rf.mu.Unlock()
		case <-rf.electionTimer.C:
			rf.mu.Lock()
			rf.startElectionL()
			rf.electionTimer.Reset(getElectionDuration())
			rf.mu.Unlock()
		}
	}
}

节点成为 Candidate 后并发发送 RequestVote RPC，自己如何处理 RPC 返回的结果，如何判断投给自己的节点数量是否超过半数？

Leader election

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27



func (rf *Raft) foraVote(peer int, args *RequestVoteArgs, cnt *int) {
	reply := RequestVoteReply{}
	DPrintf(dVote, "S%v -> S%v send vote", rf.me, peer)
	if rf.sendRequestVote(peer, args, &reply) {
		rf.mu.Lock()
		defer rf.mu.Unlock()
		if args.Term == rf.currentTerm && rf.state == Candidate {
			if reply.VoteGranted {
				DPrintf(dVote, "S%v <- S%v voted", rf.me, peer)
				*cnt++
				if *cnt > len(rf.peers)/2 {
					for i := range rf.peers {
						rf.nextIndex[i] = rf.getLastLogL().Index + 1
						rf.matchIndex[i] = 0
						DPrintf(dHeart, "S%v <- S%v nextIndex:%v", rf.me, i, rf.nextIndex[i])
					}
					rf.changeStateL(Leader)
				}
			} else if reply.Term > rf.currentTerm {
				DPrintf(dVote, "S%v <- S%v ~voted", rf.me, peer)
				rf.changeStateL(Follower, reply.Term, NULL)
				rf.persist()
			}
		}
	}
}

peer 节点从哪些方面处理投票逻辑，任期？日志情况（2B）？

Follower RequestVote RPC handler

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
	rf.mu.Lock()
	defer rf.mu.Unlock()
	defer rf.persist()
	// currTerm higher || voted
	if rf.currentTerm > args.Term || (rf.votedFor != NULL && rf.currentTerm == args.Term) {
		reply.Term, reply.VoteGranted = rf.currentTerm, false
		return
	}
	if rf.currentTerm < args.Term {
		rf.changeStateL(Follower, args.Term, NULL)
	}
	//  check log leader
	//  candidate lastLogTerm to short || (lastLogTerm=rf.lastLogTerm && candidate lastLogIndex to short)
	if rf.getLastLogL().Term > args.LastLogTerm || (rf.getLastLogL().Term == args.LastLogTerm && rf.getLastLogL().Index > args.LastLogIndex) {
		reply.Term, reply.VoteGranted = rf.currentTerm, false
		return
	}
	rf.changeStateL(Follower, args.Term, args.CandidateId)
	rf.electionTimer.Reset(getElectionDuration())
	reply.Term, reply.VoteGranted = rf.currentTerm, true
}

Tips

Candidate 选举前要先自增 currentTerm。
在 2A 中，我们处理 RequestVote Handler 的时候还不需要关注日志的新旧（2B），rf.persist() 也还不需要关注（2C），仅需要思考任期应该如何处理。
因为处理投票 RPC 的返回时需要加锁保证 rf 结构的原子读取和写入，顺便就可以进行投票数量的计数。
Candidate 成为 Leader 时，需要及时发送 heartbeat，告诉别人自己是老大，阻止他们的选举。
heartbeat 频率不能太高，控制在每秒 10 次以内，否则会突然宕机（但其实我亲测 heartbeatTimeout 设为 60ms，election 设为 rand(180)+180，test 了 1k 次没一次是 fail 的）。

The paper’s Section 5.2 mentions election timeouts in the range of 150 to 300 milliseconds. Such a range only makes sense if the Leader sends heartbeats considerably more often than once per 150 milliseconds (e.g., once per 10 milliseconds). Because the tester limits you tens of heartbeats per second, you will have to use an election timeout larger than the paper’s 150 to 300 milliseconds, but not too large, because then you may fail to elect a Leader within five seconds.

6.824 Lab2A

Task

Step

Tips