[[441163]]

從本篇文章起，就要基于 raft 構(gòu)建分布式 kv 了。

raft 是一個(gè)分布式一致性算法，主要保證的是在分布式系統(tǒng)中，各個(gè)節(jié)點(diǎn)的數(shù)據(jù)一致性。raft 算法比較復(fù)雜，因?yàn)樗鉀Q的分布式一致性問題本來就是一個(gè)比較棘手的問題，raft 算法的實(shí)現(xiàn)主要可以拆解為三個(gè)部分：

• 領(lǐng)導(dǎo)選舉
• 日志復(fù)制
• 安全性

如果不太熟悉 raft 算法，可以看下這個(gè)網(wǎng)站的動(dòng)畫展示：

http://thesecretlivesofdata.com/raft

非常形象的展示了 raft 算法面臨的問題，以及 raft 算法解決問題的基本過程。

當(dāng)然，raft 算法的 paper 也值得參考：

https://github.com/maemual/raft-zh_cn

我在網(wǎng)上還找到了一個(gè)不錯(cuò)的 raft 算法的系列文章：

https://www.codedump.info/post/20180921-raft

https://blog.betacat.io/post/raft-implementation-in-etcd

看完了這些資料之后，應(yīng)該就對(duì) raft 算法有了一個(gè)大致的了解，然后就可以看看具體怎么實(shí)現(xiàn)。

這篇文章暫時(shí)只介紹第一個(gè) Leader 選舉問題，對(duì)應(yīng)的是 TinyKV 中的 Project 2aa 部分。

在 raft 集群中，節(jié)點(diǎn)分為了三種狀態(tài)：Follower(跟隨者)、Candidate(候選者)、Leader(領(lǐng)導(dǎo)者)，節(jié)點(diǎn)的初始狀態(tài)是 Follower。

Follower 節(jié)點(diǎn)需要定期獲取 Leader 的心跳信息來維持自己的狀態(tài)。Follower 節(jié)點(diǎn)有一個(gè)超時(shí)時(shí)間(ElectionTimeout)，在這段時(shí)間內(nèi)，如果它沒有收到來自 Leader 的心跳信息，那么它會(huì)認(rèn)為集群中沒有 Leader，然后便會(huì)發(fā)起選舉。

選舉的具體流程：

如上圖，節(jié)點(diǎn) A 的 Election Timeout 最先到達(dá)，因此它會(huì)將自己的狀態(tài)變更為 Candidate，并且將任期號(hào) Term 加 1(圖中最開始的任期號(hào)是 0，加一之后變?yōu)?1)，然后給自己投票，并且發(fā)送請求投票消息給 B 和 C 兩個(gè)節(jié)點(diǎn)。

B、C 節(jié)點(diǎn)發(fā)現(xiàn)自己的任期號(hào)比 A 小，所以就會(huì)給 A 投同意票，A 節(jié)點(diǎn)收到回復(fù)之后，計(jì)算投票是否超過了節(jié)點(diǎn)數(shù)的一半，如果滿足則成為 Leader。

以上闡述的是最理想的 Leader 選舉的情況，嚴(yán)格來說 Candidate 節(jié)點(diǎn)發(fā)起選舉后，需要一直保持狀態(tài)直到以下情況之一發(fā)生：

• 它自身贏得了選舉
• 其他的節(jié)點(diǎn)贏得了選舉
• 選舉超時(shí)到來，沒有節(jié)點(diǎn)成為 Leader

第一種情況，就是上面描述的選舉流程，它自身發(fā)起選舉，并且贏得了超過半數(shù)節(jié)點(diǎn)的投票，然后成為了 Leader。

第二種情況，如果選舉的過程當(dāng)中，有其他的節(jié)點(diǎn)成為 Candidate 并且贏得了選舉，那么它收到新的 Leader 發(fā)來的 AppendEntry RPC 消息，并且如果新的 Leader 任期號(hào)比自身的更大，那么它會(huì)認(rèn)為這個(gè) Leader 是有效的，自身變更為 Follower。

第三種情況，對(duì)應(yīng)的是節(jié)點(diǎn)在選舉中沒有輸也沒有贏，如果集群節(jié)點(diǎn)是偶數(shù)個(gè)，并且同時(shí)有兩個(gè)節(jié)點(diǎn)發(fā)起選舉，那么便可能會(huì)出現(xiàn)這種情況，這樣的話選舉便是無效的。當(dāng)選舉超時(shí)再次到來時(shí)，如果還是沒有新的 Leader，那么 Candidate 會(huì)發(fā)起新的一輪選舉。

具體到代碼實(shí)現(xiàn)，首先，最開始的邏輯在 tick 函數(shù)中，這里會(huì)由外層進(jìn)行調(diào)用，我們需要判斷節(jié)點(diǎn)的 Election Timeout 是否到了，如果是的話，則需要發(fā)起選舉。

// 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 { 
      // 發(fā)起新的選舉 
      r.startElection() 
    } 
  } 
} 

發(fā)起選舉，自身變更為 Candidate，任期號(hào) + 1，并且給自己投票。然后需要向其他節(jié)點(diǎn)發(fā)送 MsgRequestVote 類型的消息。

MsgRequestVote 消息需要包含當(dāng)前節(jié)點(diǎn)最后一條日志的 Index 和 Term，方便 Follower 判斷該節(jié)點(diǎn)的日志是不是最新的。

其他的 Follower 節(jié)點(diǎn)收到 MsgRequestVote 消息之后開始處理，處理時(shí)需要注意幾個(gè)點(diǎn)：

• 如果 msg 的任期號(hào) Term 比自己的 Term 小，直接拒絕這個(gè)消息
• 如果 msg 的 Term 比自己的大，則自己需要變更為 Follower(如果不是 Follower 的話)，并更新 Term
• 需要檢查 msg 的任期號(hào)和 index 號(hào)，如果 msg 的日志不是最新的，拒絕這個(gè)消息

校驗(yàn)全部通過之后，F(xiàn)ollower 節(jié)點(diǎn)就會(huì)投贊成票，然后發(fā)送 MsgRequestVoteResponse 消息給 Candidate 節(jié)點(diǎn)。

Candidate 節(jié)點(diǎn)收到 MsgRequestVoteResponse 消息之后，需要記下投票的結(jié)果，然后計(jì)算投票是否滿足：

• 如果拒絕票超過節(jié)點(diǎn)數(shù)的 1/2，那么競選失敗，Candidate 節(jié)點(diǎn)變?yōu)?Follower 狀態(tài)
• 如果贊成票超過節(jié)點(diǎn)數(shù)的 1/2，那么競選成功

如果競選成功，需要變更自己的狀態(tài)為 Leader，然后向其他節(jié)點(diǎn)發(fā)送一個(gè) MsgAppend 消息，附帶一個(gè)空的數(shù)據(jù) Entry，防止其他節(jié)點(diǎn)繼續(xù)發(fā)起選舉。

ps. 具體的代碼實(shí)現(xiàn)可參考 etcd 的 raft，然后再基于此來自己手動(dòng)實(shí)現(xiàn) TinyKV 中的代碼。