快速理解一致性協議 raft

02-10

為了更好地拉人入坑，我決定寫篇關於 raft 的教程出來，儘可能深入淺出一些，讓甚至是沒接觸分散式系統的同學也能理解。paper 還是要看的，只不過這篇文章希望做一個概覽。

繼續廣告，我的項目在：

neverchanje/yaraft

neverchanje/consensus-yaraft

==============

Raft 解決的問題很簡單，就是讓多個副本的日誌數據達成一致。舉個例子，就是地球上發生了幾個事件，稱作 {1,2,3}。A 是某國家元首（稱為 leader），它得知事件是 {1,2,3}；B, C 是某記者（稱為 follower），它們只知道事件 {1,2}。如何讓 A, B, C 對事件集合達成一致，就是 Raft 所需要解決的問題。

很簡單的，leader 需要告知其他 followers，發生了事件 3，並且它發生在事件 1,2 之後。

接下來正經點說。

分散式系統里，機器時不時就會崩，網路時不時就會抖。當然如果你把 timeout 設置到 10s，出錯的概率其實不會很高，但這就意味著你的系統有最高 10s 的不可用時間。

所以我們引出了幾個需求：

數據不能丟，需要多節點備份
有一定的容錯能力（fault tolerance），少數節點的網路抖動不會對多數節點造成影響。

這個問題發展出了一套理論，我只簡單地講講：

考慮 2N+1 個節點。一份數據，至少需要複製到 N+1 個節點上才算是提交（commit），否則可能出現衝突。比方說事件 x=1 發到 N 個節點，同時事件 x=2 發到另外 N 個節點。如果 x=1 和 x=2 同時提交了，最終 x 的值是多少很難說清。這和多線程鎖是一樣的。2N 個節點的情況也同理。
一份數據複製到 N 個節點上，如果要容忍 K 個錯誤，需要 K < N，這樣才能保證複製到 N 個節點滿足數據提交的要求。也就是說，N 個節點，最多容忍 N-1 個錯誤。

我也時常在想一個問題，為什麼多數一致性協議都要求過半節點複製成功才算提交？3 個節點，複製到 2 個才算提交（2/3）；5 個節點，複製到 3 個才算提交（3/5）。為什麼沒有一個專門優化 4/6 或者 4/5 的協議？

我覺得可能是「過半」這個 constraint 足夠松，它能夠最大程度容忍錯誤，能夠最小程度上保證提交。

思考日誌分發（log replication），可以圍繞這個簡單點考慮：

leader 將日誌發給 follower，過半就算提交。

假設 5 個節點，假設 leader 永遠在任，那麼除非有 3 個 followers 全部失效，否則系統沒有問題。follower 一切堅持以 leader 為主導，深入貫徹其基本思想，只要 leader 是對的，即便有 follower 趕不上，leader 也能把它往前拉。

然而 leader 也是會意外下馬的，一旦 leader 出事，問題就來了。上一任 leader 說過的話，算不算數呢？應該聽當前這一任 leader 的，還是聽上一任的？

我們為每一屆選舉，標記一個任期 term。

A (Leader): <index: 1, term: 2> <index: 2, term: 2> <index: 3, term: 3>B (Follower): <index: 1, term: 2> <index: 2, term: 2> <index: 3, term: 2>C (Follower): <index: 1, term: 2> <index: 2, term: 2>

A 當選了新的 leader，他是在第三屆選舉當選的，所以當前 term 為 3。B，C 為 follower。A 和 B 存在衝突。A 認為地球上發生了三件事，第三件事是在 term=3 的時候發生的，而 B 認為第三件事是在上一任 leader 在的時候（term=2）發生的。

因為 A 有最大話語權，所以 B 只能乖乖聽話，修改記錄：

B (Follower): <index: 1, term: 2> <index: 2, term: 2> <index: 3, term: 3>

Raft 的選舉也是如日誌分發類似，過半節點認同候選人（candidate），它才能當選 leader。

過程大概是 candidate 發起投票，follower 可以投同意票，也可以投反對票。過半的 follower 同意，則 candidate 當選為 leader。

顯然，這樣每一屆選舉，只能選出一個 leader。

群眾要為選舉出來的 leader 負責。

假設 A, B, C 把 C 選舉出來作為 leader，那麼慘劇就目不忍視了：

A (Follower): <index: 1, term: 2> <index: 2, term: 2> <index: 3, term: 3>B (Follower): <index: 1, term: 2> <index: 2, term: 2> <index: 3, term: 3>C (Leader): <index: 1, term: 2> <index: 2, term: 2>

雖然 <index: 3, term: 3> 這條日誌已經提交（複製過半），C 依然會無情地將它們抹去。

這是不合理的。好比如 A 和 B 在 <index: 3, term: 3> 確立了社會主義，結果 C 一上來就要改革為農奴制，而沒有取得 A, B 的共識。

所以在 Raft 中，C 是永遠不能當選為 leader 的。A, B 會認為 C 不夠新。過半的節點認為它不夠新，C 就不可能當選。

考慮網路的非同步化，真實網路很難讓我們再用現實世界舉例。現實中上一任元首通常不會對當下的國家再下命令（垂簾聽政的意思），而網路中卻時有發生。

比如第三屆選舉當選的元首，卻收到第二屆選舉發起的投票，這是不合常理的。這時候它不會去投票，而是會直接無視。

所以，term 就成了是否忽略消息的重要依據。每個節點都具有一個屬性，稱為 currentTerm，每條消息都會攜帶發送者的 term。收到任何消息時，節點都會判斷消息是否來自於以前的 term（term < currentTerm），如果是的話，直接無視。

term = 3 的節點收到消息 term=5，這意味著什麼？意味著：

節點長期與其他節點隔離，以至於第四屆，第五屆選舉時，投票沒有通知他。
即便它貴為 term=3 的 leader，如今它也應該下台做 term=5 的 follower。

考慮網路非同步化，我們重新整理 leader 選舉的過程。

candidate 發起投票，消息中會攜帶它的 currentTerm。它可能出現 term 過低，被人無視的處境。此時 candidate 的本屆選舉相當於失敗，它應當進行下一屆選舉（curentTerm++）。因為他堅信，leader 已經下台了。

follower 收到 candidate 的投票，如果投票的 term 足夠大（比如 currentTerm=2，消息 term=3），follower 就會同意，並將自己的 currentTerm 設為 3。

（term = 3 的 candidate 發起投票，S2，S3，S5 同意）

candidate 收到過半的 follower 同意，則它當選 leader。

好了，我們再整理一個問題：candidate 發起投票，原因是 leader 下台，需要換屆。而它又是如何得知 leader 是否下台的？

在平時，leader 會發送心跳（heartbeat）給所有 followers，告訴它們自己還活著。一旦 leader 失效，followers 沒有收到心跳，那麼它們自然會選舉出新的 leader。

所以可能某個 candidate 發起投票，卻被所有人無視，但只要他堅信 leader 已經下台（沒收到任何來自 leader 的消息），那麼他依然會發起新的選舉。

到此這篇教程就結束了，Raft 論文中還有一些需要體會的內容，但對初識一致性協議的同學來說不那麼重要。文章中有錯誤的地方歡迎指正，有不理解或者批評的地方也歡迎提出。