前言

今天要來說一個覺得人家論文太難，所以就寫一個博士論文重新發明共識演算法的故事。

其實，Paxos太難這件事不只一個人說過，也許前面幾篇講解Paxos流程不是特別的難，那是因為他論文並不是長那樣(笑。Paxos的論文涵蓋了很嚴謹且繁雜的證明過程來說明整個流程，不斷一步步用反證法或是歸納法不斷推導最後證明共識演算法的正確性。

而據說論文一開始發表時連很多研討會的委員都看不懂Lamport在說什麼，而導致該篇論文並沒有受到重視。而是之後Lamport又寫了好幾篇解釋的論文，並且隨著分散式系統的發展，Paxos論文才又被撿回來。

而Raft的出生也是因為Paxos論文太過理論，放到工程實作的角度實在難以實作，因此Diego Ongaro在Stanford和他的指導老師John Ousterhout便發明了Raft這一個共識演算法。

以下內容為參考John Ousterhout親自講解Raft的上課影片，所做之筆記。非常推薦直接觀看影片!

https://www.youtube.com/watch?v=vYp4LYbnnW8

Raft

簡介

Raft的目的就是要 replicate 一組 log 至集群中的每個server，確保每個server執行了相同且順序一致的指令，得到相同的結果或是進入相同的狀態。

• Replicate log => Replicate State Machine
• State Machine => 泛指所有的application或是program，接受一個input產出一個output
• Log => 用來幫助所有的server執行相同且順序一致的指令

簡易的步驟

1. Client先對集群中的某一個Server C，發送一個指令，該指令先存在Log中。
2. Server C 透過 Consensus協議 將該指令複製到每一個server上。
3. 當每一個server都保存了該指令後，所有server就可以執行該指令
4. Server C回傳結果給Client

只要保證每一個server的log儲存相同的指令且順序一致，並且state machine是相同的，我們可以確保每一個server會產生相同結果或是進入相同的狀態。

Raft Consensus

1. 只要超過半數的server活著且可以互相溝通，我們可以保證活著的server達成一致結果，跟Paxos一樣。
2. 能夠處理的Failure Model => 能夠處理少於半數的server lost，或是message delay/lost。

Consensus 種類

一般的 Consensus 方法分成兩種

1. Symmetric, no leader
   • 所有server角色相同
   • client可以向每一個server發送指令或是請求
2. Asymmetric, leader based
   • 在任一時刻，只會有一個server作為leader，處理client的請求，其餘server直接接受leader的決策
   • client只可以向server發送請求

Raft 這邊使用 Asymmetric, leader based

• 我們可以將問題分成兩個情況

  1. normal operation
  2. leader change

• 因為client只跟leader溝通，其餘server只需負責接收leader的決策 =>

  • normal operation 更為簡單不容易發生conflict
  • 比 Symmetric, no leader 更有效率

Raft Overview

0. 術語
1. Leader election
2. Normal operation (basic log replication)
3. Safety and consistency after leader changes
4. Neutralizing old leader

我們今天先介紹Leader election與Normal operation

術語

Server State

在任一時刻，server只會有以下三種角色

1. Leader:
   • 負責與client互動
   • log replication
   • 任一時刻，集群只會有一個leader
2. Follower
   • 相較於leader完全被動
   • 不會主動發送任何RPC，只會回應傳入的RPC
3. Candidate
   • 暫時的角色，可以被選為新leader

Terms (任期)

時間被分為一個個terms，term是一個嚴格遞增的數字
每一次經歷新的election，term都會增加
選出來的leader存活運作期間就是維持在該term

1. Raft保證任一時刻只會有一個leader
2. 選舉過程可能出現選不出leader的情況，
   • 系統會進入下一個term，並再次嘗試選出新的leader
3. 每一個server皆會記錄current term在永久儲存中，因為是分散式，所以每一個server紀錄的term會不一樣，因為可能自己曾經failed過被重啟，因此沒有跟到真實的term。總之，這個current term就是該server自身認為系統目前的term (不一定是正確)。

Term的重點在於

Raft 可以透過term來判斷哪些資訊是 過期的資訊

舉例:
一個current_term=2的serverA，
向current_term=3的serverB傳送資料，
Raft可以發現A的資料一定是過時的，他中間可能失效重啟過，Raft只採用較新的資料。

RPC Call

1. RequestVote RPC: 在選出新的leader時使用
2. AppendEntries RPC: 在normal operation時，leader發送此RPC來replcate log至其他server

Leader election

兩個重點

1. 如何選出 leader，並且保證任一時刻只有一個leader
2. 當leader失效如何偵測，並且選出新leader

Heartbeats and Timeouts

每一個server初始為 Follower ，相信著這個cluster有一個leader的存在，被動的接受Leader或是Candidate的RPC並回應。

因此Leader要讓大家認知自己是leader的方法，就是週期性傳送Heartbeats (empty AppendEntries RPC) 給所有的 followers

若是Followers超過了 election Timeout 仍然沒有收到任何RPC，則

1. 認定系統目前沒有leader
2. follower轉成candidate發起選舉

Election Basics

對每一個 Follower 超過 election Timeout 發起選舉

1. 自己紀錄的 current_term + 1
2. 轉成 Candidate state
3. 投給自己
4. 發送 RequestVote RPCs 給其餘的servers，不斷嘗試直到

   1. 收到過半數的server的選票

      • 變成 Leader
      • 開始發送 AppendEntries heartbeats 給其他servers

   2. 收到合法Leader的RPC

      • 退回 Follower

   3. 這一輪沒有人拿到過半數的票 (election Timeout超時)

      • current_term 再遞增一次
      • 發起下一輪選舉，回到 步驟1

Safety

性質: 保證每一個term只會有一個winner成為leader

作法:

• 每一個server只能投一張票 (這個重要資訊必須存在disk，否則投完票，失敗重啟可能會重複投票)
• 不可能有兩個candidates同時拿到過半數的選票

Liveness

性質: 選舉不會無限持續下去讓系統一直沒有leader，一定有一個candidate最終一定會贏

作法:

• 每一個candidate的election timeout，是[T,2T]的隨機數字
• 因此一定有一個candidate有機會比別人先timeout進入下一輪選舉，讓大家投給他

Normal operation (basic log replication)

Log Structure

每一個 log entry 皆保存: index, term, command
可以注意到每一個server中log的term一定是遞增的
log也必須存在disk中，以便在失敗重啟後可以取回

如果一個log entry已經在過半數的server上皆被保存，我們稱該log entry被commit，該log已經可以被每一個server中的state machine執行。

如上圖，index7 會被 commited，且可以知道 index7 以前的entries都被commited。

Normal Operation

1. client 發送請求或是指令給 leader
2. leader 將該指令存到log中
3. leader 發送 AppendEntries RPCs 給 followers，follower儲存並回復收到。
4. 當一個 log entry 被 commited (過半數servers回覆收到，並儲存該log entry):
   1. Leader可以將該command送去state machine執行，並返回結果給client
   2. Leader在下一次的AppendEntries RPCs通知followerd該log entry被commited
   3. followers也可以把該command送去執行。

若是 followers 失敗或是丟失訊息，Leader會不斷嘗試同一個RPCs直到成功
因為只需要過半數的servers回覆收到，則log就會被commited並執行，效能並不會太差，集群中一個server 失效，並不會拖垮效能。

Log Consistency

性質: 若是兩個servers的log，某一個log entry擁有同樣的(index, term) 則

1. 該 log entry 一定儲存同樣的command
2. 該 log entry 前面的所有 entries 一定也都是一樣的

引伸:
若一個log entry被commited，則該log entry 前面的所有 entries一定也被commited

作法:

AppendEntries Consistency Check

1. 每一個 AppendEntries RPCs 除了包含最新的entry外，還包含 前一個entry的(index, term)
2. Followers 一定要 擁有同樣的前一個entry的(index, term) 才會儲存最新的log entry，否則就不接受該RPC
3. 可以想像成歸納法證明的步驟 (假設n-1成立，推出n成立，保證n之前都會符合該性質)

小結

到這邊我們已經瞭解了Raft大致的運作，可以發現相較於Paxos，Raft提供了更多實作的細節，這使得人們可以輕易地依照論文上面的指導直接利用各種語言實作最原汁原味的Raft。

如果想看實際執行結果，可以到下面連結，你可以透過互動模擬來暸解Raft的運作！
https://raft.github.io/

但是，其實按照上面的做法會有一點小問題，仍然必須做出更動，這部分就留待明天再說啦。