在有了日志之后，在进行投票时，就需要进行日志比较了。

因为 Raft 算法是强 Leader 算法，因此会要求 Leader 一定要包含所有已经提交日志。因此，在进行选举时，我们确保只有具有比大多数 Peer 更新日志的候选人才能当选 Leader。

日志新旧比较

关于两个 Peer 所存日志谁更 up-to-date 的问题，论文中是这样描述的：

Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs.

  1. If the logs have last entries with different terms, then the log with the later term is more up-to-date.
  2. If the logs end with the same term, then whichever log is longer is more up-to-date

总结下，比较对象是最后一个 LogEntry，比较规则是：

  1. Term 高者更新
  2. Term 同，Index 大者更新
1
2
3
4
5
6
7
8
9
10
func (rf *Raft) isMoreUpToDateLocked(candidateIndex, candidateTerm int) bool {
        l := len(rf.log)
        lastTerm, lastIndex := rf.log[l-1].Term, l-1
        LOG(rf.me, rf.currentTerm, DVote, "Compare last log, Me: [%d]T%d, Candidate: [%d]T%d", lastIndex, lastTerm, candidateIndex, candidateTerm)

        if lastTerm != candidateTerm {
                return lastTerm > candidateTerm
        }
        return lastIndex > candidateIndex
}

增加日志比较

选举这一块需要增加的逻辑比较简单，只需要：

  1. 在发送 RPC 构造参数时增加上最后一条日志信息
  2. 在接收 RPC 投票前比较日志新旧

根据论文图 2 补全 RPC 相关结构体字段：

1
2
3
4
5
6
7
type RequestVoteArgs struct {
        // Your data here (PartA, PartB).
        Term         int
        CandidateId  int
        LastLogIndex int
        LastLogTerm  int
}

发送方（Candidate），在发送 RPC 增加构造参数，带上 Candidate 最后一条日志的信息（index 和 term）。

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
28
func (rf *Raft) startElection(term int) {
        votes := 0
        askVoteFromPeer := func(peer int, args *RequestVoteArgs) {}

        rf.mu.Lock()
        defer rf.mu.Unlock()
        if rf.contextLostLocked(Candidate, term) {
                LOG(rf.me, rf.currentTerm, DVote, "Lost Candidate[T%d] to %s[T%d], abort RequestVote", rf.role, term, rf.currentTerm)
                return
        }

        l := len(rf.log)
        for peer := 0; peer < len(rf.peers); peer++ {
                if peer == rf.me {
                        votes++
                        continue
                }

                args := &RequestVoteArgs{
                        Term:         rf.currentTerm,
                        CandidateId:  rf.me,
                        LastLogIndex: l-1,
                        LastLogTerm:  rf.log[l-1].Term,
                }

                go askVoteFromPeer(peer, args)
        }
}

接收方（各个 Peer 的回调函数），在对齐 Term，检查完没有投过票之后，进一步比较最后一条日志，看谁的更新。如果本 Peer 比 Candidate 更新，则拒绝投票给 Candidate。

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
28
29
30
31
32
33
34
35
// example RequestVote RPC handler.
func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
        // Your code here (PartA, PartB).

        rf.mu.Lock()
        defer rf.mu.Unlock()

        reply.Term = rf.currentTerm
        reply.VoteGranted = false
        // align the term
        if args.Term < rf.currentTerm {
                LOG(rf.me, rf.currentTerm, DVote, "-> S%d, Reject Vote, Higher term, T%d>T%d", args.CandidateId, rf.currentTerm, args.Term)
                return
        }
        if args.Term > rf.currentTerm {
                rf.becomeFollowerLocked(args.Term)
        }

        // check for votedFor
        if rf.votedFor != -1 {
                LOG(rf.me, rf.currentTerm, DVote, "-> S%d, Reject Voted, Already voted to S%d", args.CandidateId, rf.votedFor)
                return
        }

        // check log, only grante vote when the candidates have more up-to-date log
        if rf.isMoreUpToDateLocked(args.LastLogIndex，args.LastLogTerm) {
                LOG(rf.me, rf.currentTerm, DVote, "-> S%d, Reject Vote, S%d's log less up-to-date", args.CandidateId)
                return
        }

        reply.VoteGranted = true
        rf.votedFor = args.CandidateId
        rf.resetElectionTimerLocked()
        LOG(rf.me, rf.currentTerm, DVote, "-> S%d, Vote granted", args.CandidateId)
}