# Lab: Raft - Leader Election

## 说在前面

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

* Raft Paper Figure 2
* 6.824 Course Notes
* [Students' Guide to Raft](https://thesquareplanet.com/blog/students-guide-to-raft/)
* [Raft Q\&A](https://thesquareplanet.com/blog/raft-qa/)

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
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 需包含以下字段：

```go
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
go func() {
    rf.mu.Lock()
    if rf.isCandidate() && rf.hasMajorityVotes() {
        rf.becomesLeader()
    }
    rf.mu.Unlock()
    time.Sleep(CheckMajorityVoteTimeout)
}
```