實現分佈式 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。

第二種情況，如果選舉的過程當中，有其他的節點成爲 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 消息之後開始處理，處理時需要注意幾個點：

校驗全部通過之後，Follower 節點就會投贊成票，然後發送 MsgRequestVoteResponse 消息給 Candidate 節點。

Candidate 節點收到 MsgRequestVoteResponse 消息之後，需要記下投票的結果，然後計算投票是否滿足：

如果競選成功，需要變更自己的狀態爲 Leader，然後向其他節點發送一個 MsgAppend 消息，附帶一個空的數據 Entry，防止其他節點繼續發起選舉。

ps. 具體的代碼實現可參考 etcd 的 raft，然後再基於此來自己手動實現 TinyKV 中的代碼。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/N9Ws-8GYJeGDYQj1EodjlQ

猜你喜歡