Lab: Raft - Leader Election

以下为本人在完成 Lab 2 过程中的总结，不涉及代码细节

说在前面

在实验的过程中，一定要反复阅读：

• Raft Paper Figure 2

• 6.824 Course Notes

• Students' Guide to Raft

• Raft Q&A

Leader Election 主要由以下几个部分组成：

• Election Timeout Daemon

• Send RequestVote RPC

• Receive RequestVote RPC

• Marjority Votes Checking Daemon

Election Timeout Daemon

每个 raft server 都需要一个 daemon 来检查选举超时的情况，当没有收到任何有效消息时，则应该发起一次新的选举；当收到有效消息时，则重置选举超时的计算。这里，有效的消息包括：

• Candidate 发来有效的 RequestVote RPC

• Leader 发来有效的 AppendEntries RPC

• Candidate 收到有效的 RequestVote RPC Reply

• Leader 收到有效的 AppendEntries RPC Reply

因此我们可以在 Make 中创建这样一个 daemon:

go func() {
    for {
        et := generateET()
        select {
        case <-rf.rCh:
        case <-time.After(et): {
            go rf.startsNewElection()
        }
    }
}

通过 rCh channel 来接受有效信息的信号。rf.startsNewElection 严格按照 Figure 2 描述的实现即可：

• Increment currentTerm：每个 term 只能有一次选举

• Vote for self：每个 server 在单次选举中只能投一票，参选者默认投给自己

• Reset election timer

• Send RequestVote RPCs to all other servers

Send RequestVote RPCs

RequestVoteArgs

RequestVoteArgs 需包含以下字段：

type RequestVoteArgs struct {
    Term         int
    CandidateID  int
    LastLogIndex int
    LastLogTerm  int
}

注意这里的 LastLog 指的是 raft server 的 log entries 的最后一个，目的在于让 Follower 判断 Candidate 是否至少和它一样与时俱进。注意不要和 AppendEntriesArgs 中的 PrevLog 混淆，后者指的是 Leader 上次发给 Follower 的最后一个 logEntry，因此 Leader 发给每个 Follower 的 AppendEntriesArgs 都可能不同。

Retry

由于可能出现网络分区，RequestVote 请求需要超时重发。

Receive RequestVote RPCs

严格按照 Figure2 描述的步骤实现即可

1. 检查过时请求：term < currentTerm

2. 当 server 还未投出自己宝贵一票，或者已经投了 Candidate 一票时，检查 Candidate 的 log entries 是否与自己与时俱进，如果是，则投它一票。当 server 已经投给 Candidate 一票时，server 的请求响应可能在网络中丢失，因此当再次收到相同请求时，有必要再次同意投票。

Majority Votes Checking Daemon

这里把检查是否得到多数票的逻辑放到一个 Daemon 里，主要目的在于方便组织代码，将其放在 Send RequestVote RPCs 之后也没有问题：

go func() {
    rf.mu.Lock()
    if rf.isCandidate() && rf.hasMajorityVotes() {
        rf.becomesLeader()
    }
    rf.mu.Unlock()
    time.Sleep(CheckMajorityVoteTimeout)
}