實現分布式 Kv—2 Raft Leader 選舉
從本篇文章起，就要基于 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 中的代碼。
