上一篇文章講到了實作一個簡單的單機版 kv，如果不熟悉的話可以先回顧一下：
實作分布式 kv—1 Standalone KV
從本篇文章起，就要基于 raft 建構分布式 kv 了。
raft 是一個分布式一緻性算法，主要保證的是在分布式系統中，各個節點的資料一緻性。raft 算法比較複雜，因為它所解決的分布式一緻性問題本來就是一個比較棘手的問題，raft 算法的實作主要可以拆解為三個部分：
- 上司選舉
- 日志複制
- 安全性
如果不太熟悉 raft 算法，可以看下這個網站的動畫展示：
http://thesecretlivesofdata.com/raft
非常形象的展示了 raft 算法面臨的問題，以及 raft 算法解決問題的基本過程。
當然，raft 算法的 paper 也值得參考：
https://github.com/maemual/raft-zh_cn
我在網上還找到了一個不錯的 raft 算法的系列文章：
https://www.codedump.info/post/20180921-raft
https://blog.betacat.io/post/raft-implementation-in-etcd
看完了這些資料之後，應該就對 raft 算法有了一個大緻的了解，然後就可以看看具體怎麼實作。
這篇文章暫時隻介紹第一個 Leader 選舉問題，對應的是 TinyKV 中的 Project 2aa 部分。
在 raft 叢集中，節點分為了三種狀态：Follower（跟随者）、Candidate（候選者）、Leader（上司者），節點的初始狀态是 Follower。
Follower 節點需要定期擷取 Leader 的心跳資訊來維持自己的狀态。Follower 節點有一個逾時時間（ElectionTimeout），在這段時間内，如果它沒有收到來自 Leader 的心跳資訊，那麼它會認為叢集中沒有 Leader，然後便會發起選舉。
選舉的具體流程：
如上圖，節點 A 的 Election Timeout 最先到達，是以它會将自己的狀态變更為 Candidate，并且将任期号 Term 加 1（圖中最開始的任期号是 0，加一之後變為 1），然後給自己投票，并且發送請求投票消息給 B 和 C 兩個節點。
B、C 節點發現自己的任期号比 A 小，是以就會給 A 投同意票，A 節點收到回複之後，計算投票是否超過了節點數的一半，如果滿足則成為 Leader。
以上闡述的是最理想的 Leader 選舉的情況，嚴格來說 Candidate 節點發起選舉後，需要一直保持狀态直到以下情況之一發生：
- 它自身赢得了選舉
- 其他的節點赢得了選舉
- 選舉逾時到來，沒有節點成為 Leader
第一種情況，就是上面描述的選舉流程，它自身發起選舉，并且赢得了超過半數節點的投票，然後成為了 Leader。
第二種情況，如果選舉的過程當中，有其他的節點成為 Candidate 并且赢得了選舉，那麼它收到新的 Leader 發來的 AppendEntry RPC 消息，并且如果新的 Leader 任期号比自身的更大，那麼它會認為這個 Leader 是有效的，自身變更為 Follower。
第三種情況，對應的是節點在選舉中沒有輸也沒有赢，如果叢集節點是偶數個，并且同時有兩個節點發起選舉，那麼便可能會出現這種情況，這樣的話選舉便是無效的。當選舉逾時再次到來時，如果還是沒有新的 Leader，那麼 Candidate 會發起新的一輪選舉。
具體到代碼實作，首先，最開始的邏輯在 tick 函數中，這裡會由外層進行調用，我們需要判斷節點的 Election Timeout 是否到了，如果是的話，則需要發起選舉。
// tick advances the internal logical clock by a single tick.
func (r *Raft) tick() {
// Your Code Here (2A).
switch r.State {
case StateLeader:
// ...
case StateFollower, StateCandidate:
r.electionElapsed++
if r.electionElapsed >= r.electionTimeout {
// 發起新的選舉
r.startElection()
}
}
} 複制
發起選舉，自身變更為 Candidate，任期号 + 1，并且給自己投票。然後需要向其他節點發送 MsgRequestVote 類型的消息。
MsgRequestVote 消息需要包含目前節點最後一條日志的 Index 和 Term，友善 Follower 判斷該節點的日志是不是最新的。
其他的 Follower 節點收到 MsgRequestVote 消息之後開始處理，處理時需要注意幾個點：
- 如果 msg 的任期号 Term 比自己的 Term 小，直接拒絕這個消息
- 如果 msg 的 Term 比自己的大，則自己需要變更為 Follower（如果不是 Follower 的話），并更新 Term
- 需要檢查 msg 的任期号和 index 号，如果 msg 的日志不是最新的，拒絕這個消息
校驗全部通過之後，Follower 節點就會投贊成票，然後發送 MsgRequestVoteResponse 消息給 Candidate 節點。
Candidate 節點收到 MsgRequestVoteResponse 消息之後，需要記下投票的結果，然後計算投票是否滿足：
- 如果拒絕票超過節點數的 1/2，那麼競選失敗，Candidate 節點變為 Follower 狀态
- 如果贊成票超過節點數的 1/2，那麼競選成功
如果競選成功，需要變更自己的狀态為 Leader，然後向其他節點發送一個 MsgAppend 消息，附帶一個空的資料 Entry，防止其他節點繼續發起選舉。
ps. 具體的代碼實作可參考 etcd 的 raft，然後再基于此來自己手動實作 TinyKV 中的代碼。