Lab: Raft - Leader Election

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

说在前面

在实验的过程中,一定要反复阅读:

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)
}