狀態(tài)轉(zhuǎn)化

Raft協(xié)議已經(jīng)廣泛應(yīng)用于Etcd、Consul掷空、Tikv等各種主流產(chǎn)品吵血，今天開始我們就仔細(xì)了解下Raft協(xié)議煞赢。

重點

AppendEntry和RequestVote 兩個結(jié)構(gòu)體字段非常重要慎璧，對理解leader選舉床嫌、日志復(fù)制邏輯非常重要跨释。

隨機化：每個節(jié)點的election timeout會從一個固定的區(qū)間（如150-300ms間）隨機選擇，降低了競選活鎖的概率

• 每個Candidate在開始一次選舉的時候會重置一個隨機的選舉超時時間厌处，然后一直等待直到選舉超時鳖谈。

投票的3個檢查點

1. 日志索引(LastLogIndex)：RequestVote請求中的LastLogIndex 小于 自身LastLogIndex，則拒絕投票
2. 任期號(LastLogTerm)：RequestVote請求中LastLogTerm 小于 自身的Term阔涉，則拒絕投票
3. 投票狀態(tài)：自身未投票

兩個超時限制【etcd的默認(rèn)值缆娃，和raft無關(guān)】：

1. HeartBeat-interval : 100ms
2. Election Timeout : 1000ms， 每個節(jié)點等待發(fā)起選舉的時間點不一致洒敏，避免競選活鎖

這兩個超時配置影響什么龄恋？

1. HeartBeat-interval 影響心跳探測疙驾，最好根據(jù)節(jié)點間網(wǎng)絡(luò)質(zhì)量進行調(diào)整凶伙，如果是跨可用區(qū)，這個配置就需要特別注意它碎。etcd官方建議是節(jié)點往返時長的0.5-1.5倍左右函荣，

2. Election timeout 影響 Leader異常后等待多久重新發(fā)起選舉，也就是意味著 集群不可用時長扳肛。etcd官方建議是節(jié)點往返時長的10倍傻挂，上限是50s

動態(tài)圖：http://kailing.pub/raft/index.html

• 說明：關(guān)于網(wǎng)絡(luò)分區(qū)中的錯誤：5節(jié)點集群，2節(jié)點分區(qū)的集群因無法實現(xiàn)leader選取(永遠(yuǎn)不可能獲得半數(shù)以上票數(shù))挖息，故不會正常運行金拒，也就無法處理請求

如果幫到你，辛苦點贊鼓勵下吧套腹！

Raft兩個核心rpc結(jié)構(gòu)體

Raft算法中服務(wù)器節(jié)點間使用RPC通信绪抛，并且基本的一致性算法只需要兩種類型的RPC，請求投票(RequestVote电禀，由Candidate發(fā)起)和追加條目(AppendEntry, 由Leader發(fā)起)
AppendEntry：由leader節(jié)點發(fā)出幢码，攜帶收到的最新命令，同時還用作心跳消息尖飞。當(dāng)Follower收到此消息時症副，將重置選舉計時器。

type AppendEntryArgs struct {
  Term      int    // current term of the leader, very IMPORTANT
  LeaderId     int    // id of the leader, 0 to N-1 where N = total servers
  Entries      []Entry // new data to sync
  PrevLogIndex  int    // important metadata for log correctness
  PrevLogTerm    int    // important metadata for log correctness
  LeaderCommit  int   // what index have been received by the majority
}

type AppendEntryReply struct {
  Term       int   // current term of the receiving node
  Success      bool  // AppendEntry declined or accepted
  ConflictIndex  int    // if declined, specifying the conflicting index
  ConflictTerm  int    // if declined, specifying the conflicting term
}

RequestVote：當(dāng)Follower的選舉計時器超時(長時間沒有收到AppendEntry政基， 約300ms)贞铣，成為Candidate并調(diào)用所有其他節(jié)點為自己投票。

type RequestVoteArgs struct {
  Term       int      // current term of the candidate, very IMPORTANT
  CandidateId   int      // id of the candidate, 0 -  N-1 where N = total servers
  LastLogIndex   int      // important metadata for election correctness
  LastLogTerm   int      // important metadata for election correctness, explain later
}

type RequestVoteReply struct {
  Term       int      // current term of the receiving node
  VoteGranted   bool    // yes or no
}

leader選舉

節(jié)點狀態(tài)和選舉過程

狀態(tài)與選舉

節(jié)點共有3種狀態(tài)：Leader沮明、Candidate辕坝、Follower， 各角色的規(guī)則：
All Server ：

1. 如果commitIndex>lastApplied：增加lastApplied珊擂，應(yīng)用日志(lastApplied)到狀態(tài)機圣勒；
2. 如果rpc請求或響應(yīng)中的Term T > currentTerm; 則currentTerm = T费变，轉(zhuǎn)換為follower

Follower:

1. 響應(yīng)candidates 和 leaders的rpc請求；
2. 如果沒有接收到（或超時）leader 的AppendEntry或Candidate的requestVote請求圣贸，轉(zhuǎn)換為Candidate

Candidate:

1. 一旦轉(zhuǎn)換為Candidate挚歧，開啟選舉：
   • 增加currentTerm
   • 為自己投票
   • 重置選舉計時器
   • 發(fā)送RequestVote 給其他所有servers
2. 如果收到超半數(shù)投票：成為leader
3. 如果收到新leader的AppendEntry rpc消息：轉(zhuǎn)換為follower
4. 如果選舉超時：開啟新一輪選舉

Leader:

1. 定期向每個服務(wù)器發(fā)送初始的空 AppendEntries RPC（心跳）：在空閑期間重復(fù)以防止選舉超時
2. 接收客戶端請求：追加日志條目到本地日志，在條目應(yīng)用于狀態(tài)機后響應(yīng)
3. 如果最新日志索引 大于等于 follower的nextIndex：發(fā)送AppendEntry rpc吁峻，日志條目從nextIndex開始：
   • 如果成功：更新follower的nextIndex和matchIndex
   • 如果因為日志不一致而失敾骸：縮小nextIndex并且重試
4. 如果存在一個 N 使得 N > commitIndex，大多數(shù) matchIndex[i] ≥ N用含，并且 log[N].term == currentTerm：設(shè)置 commitIndex = N

在Raft節(jié)點剛啟動的時候矮慕，所有節(jié)點都是Follower狀態(tài)

1. 因為此時沒有Leader，所有的Follower都無法收到leader的心跳(AppendEntry)啄骇，所以每個Follower在每個隨機超時后(150-300ms)后痴鳄，進入Candidate狀態(tài)
2. 假設(shè)B進入Candidate會立即發(fā)起選舉，自增任期號(Term+1)缸夹，選票給自己痪寻，并向其他節(jié)點發(fā)起競選Leader投票消息
3. C收到B的競選Leader消息后，有2種處理情況：

• C也恰好發(fā)起Leader競選虽惭，并投票給自己橡类，此時不會投票給B。這時誰也無法獲取大多數(shù)支持芽唇，只能等待Election Timeout再發(fā)起選舉顾画。（Raft做引入隨機數(shù)，每個節(jié)點等待發(fā)起選舉時間點不一致匆笤，規(guī)避了潛在競選活鎖）研侣，返回：

RequestVoteReply { 
  Term: 當(dāng)前自身Term；如果該term大于candidate發(fā)起的term疚膊，則candidate轉(zhuǎn)化為follower
  VoteGranted: no
}

• C判斷B的數(shù)據(jù)至少和自己一樣新义辕、B-term大于C-term、且C未投票給其他候選者寓盗，則投票給B灌砖，B獲取大數(shù)據(jù)支持稱為Leader，返回：

RequestVoteReply {
    Term: Candidate發(fā)送的Term
    VoteGranted: yes
}

自測

https://segmentfault.com/a/1190000022398199
https://towardsdatascience.com/raft-algorithm-explained-a7c856529f40

以上兩篇文章對于Candidate傀蚌、Follower基显、Leader安全性、多Leader等問題在選舉中各種情況做了分析善炫，但是基本也是圍繞“投票的3個檢查點”展開撩幽，所以自己也可以根據(jù)檢查點做分析。

Raft Log復(fù)制 & 安全性

重點

關(guān)鍵特性：
Election Safety：最多一個leader
Leader Append-Only： leader不會覆蓋、刪除日志條目窜醉，只會追加新條目
Log Matching：如果兩個日志包含具有相同索引和任期的條目宪萄，則日志通過給定索引的所有條目都是相同的
Leader Completeness：如果在給定任期內(nèi)提交了日志條目，則該日志條目將出現(xiàn)在所有較高任期的Leader日志中
state Machine Safety：如果服務(wù)器已經(jīng)將給定索引出的日志條目應(yīng)用到其狀態(tài)機榨惰，則沒有其他服務(wù)器回味同一個索引引用不同的日志條目
通過以上5個特性拜英，推導(dǎo)出：

• 如果不同日志中的兩個條目擁有相同的索引和任期號，那么他們存儲了相同的指令
• 如果不同日志中的兩個條目擁有相同的索引和任期號琅催，那么他們之前的所有日志條目也都相同居凶。

Leader什么時候把日志條目應(yīng)用到狀態(tài)機？
這種條目被稱為 已提交 的藤抡；Raft算法保證所有已提交的日志條目都是持久化且最終會被所有可用的狀態(tài)機執(zhí)行侠碧。一旦創(chuàng)建該日志條目的 leader 將它復(fù)制到過半的服務(wù)器上，該日志條目就會被提交（例如在圖 6 中的條目 7）缠黍。Leader 將追蹤會被提交的日志條目的最大索引LeaderCommit弄兜，未來的所有 AppendEntries RPC 都會包含該索引，這樣其他的服務(wù)器才能最終知道哪些日志條目需要被提交嫁佳。Follower 一旦知道某個日志條目已經(jīng)被提交就會將該日志條目應(yīng)用到自己的本地狀態(tài)機中（按照日志的順序）挨队。

• 思考： leader和follower的日志保存階段：follower接受AppendEntry請求，如果接受日志條目蒿往，返回sussuce給leader。leader獲取半數(shù)以上接受狀態(tài)后湿弦，應(yīng)用該條目到本地狀態(tài)機瓤漏，并更新lastApplied條目，在下一條AE中LeaderCommit和LastApplied一致颊埃，follower在收到下一個AE蔬充，對比自身的LastApplied和LeaderCommit，決定將哪些條目應(yīng)用到本地狀態(tài)機 【自己猜測班利，還沒看源碼核對】

  
  
  圖6
  
  

  對圖6的格式說明：命令(x←3), Term(1),在logs中的序號饥漫，及l(fā)og index； 索引7因為半數(shù)以上提交罗标，所以7已經(jīng)被應(yīng)用到狀態(tài)機

復(fù)制邏輯

Raft中各server維護的狀態(tài)說明：

在節(jié)點成為leader后庸队，leader需要保證集群所有日志條目一致，在接受新日志服請求的同時闯割，需要將歷史日志同步給follower彻消，當(dāng)一個新leader出現(xiàn)時，該leader將所有nextIndex的值初始化為自己最后一個日志條目的index+1宙拉，在下一次AppendEntry rpc請求中宾尚，可能有2種場景：

第一： follower-1 的日志條目和leader持平；

leader 發(fā)出的新的AppendEntry rpc請求會攜帶Entries谢澈、PrevLogIndex煌贴、PrevLogTerm和leaderCommit御板， follower-1會對比rpc請求的PrevLogIndex和PrevLogTerm是否和自己日志索引一致，如果一直則接受本次Entries條目

第二： follower-2的日志條目相對leader落后較多牛郑；

follower-2 對比PrevLogTerm和prevlogIndex稳吮，此時判斷失敗，此時會將沖突的信息(ConflictIndex 和 ConflictTerm)返回給leader井濒，在被follower-2拒絕后灶似，leader就會減少nextIndex值，并重試AppendEntry RPC瑞你，最終nextIndex會在某個位置使得leader和follower-2日志達(dá)成一致酪惭。此時AppendEntry rpc就會成功，將follower-2中跟leader沖突的日志條目全部刪除者甲，然后追加leader的日志條目春感。