# 3-3. In Search of an Understandable Consensus Algorithm
:::info
過去十年大家討論到共識演算法就會想到Paxos，大多數共識的實現也是以它為起點，但Paxos很難理解也很難實作，因此作者嘗試設計一種以可理解性為主要設計目標的演算法Raft來取代Paxos。
:::
## 1. Introduction
>**共識演算法:** 允許多台機器像一個整體一樣工作，即使其中幾台機器故障時仍然能正常工作。

>**什麼是*Raft*?**
>用來管理複製日誌（replicated log）的一致性協定，目的是要 replicate 一組 log 至集群中的每個server，確保每個server執行了相同且順序一致的指令，得到相同的結果或是進入相同的狀態。

>**已經有*Paxos*了，為什麼還要有*Raft*?**
>過去大家談論到共識演算法(一致性演算法)都是想到*Paxos*，但*Paxos*非常難理解，而且架構十分複雜在實務上來說也很難實現，因此作者認為需要一個更好理解且容易實作的共識演算法。

為了讓演算法更容易被理解，Raft **減少狀態空間（相較於*Paxos*，*Raft* 降低了不確定性的程度和伺服器之間的不一致)**，並將共識問題分成幾個子問題**leader election**、**log replication**、**safety**。
*Raft*幾個獨特的特性：
1. **Strong leader**: 例如log entries只從leader發送給其他的伺服器，簡化了對replicate log的管理而且好理解。
2. **Leader election**: 使用隨機計時器來選出Leader，這樣做只需對算法必需的心跳機制(heartbeat)增加少量機制，就能簡單且快速地解決領導選舉過程中可能發生的衝突
>*heartbeat*機制 : 分布式系統中用來維持節點間狀態同步和檢測節點是否在線的方法。
3. **Membership changes**: 在改變cluster中伺服器組成的時候，使用了一種稱為「聯合共識」(joint consensus)的新方法，在cluster配置的轉換過程中，新舊兩種配置大多數是重疊的，可以確保即使在進行配置變更的時候，cluster也能夠繼續正常運行。

## 2. Replicated state machines
replicated state machines是為了應對在分散式系統中fault tolerance problem而產生的機制，在這種機制下，多台機器(state machines)擁有相同的log(replicated)，他們讀取同樣順序的operation，進行一樣的command，因此可以確保所有機器都是在一樣的狀態。即使有些機器壞了，其他機器都可以取代它繼續正常工作

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

>repliacate state machine通常使用log replication來實現，每個伺服器都包含一系列command的log，伺服器上的狀態機會依序執行log中的指令，只要保證每一個server的log儲存相同的指令且順序一致，並且state machine是相同的，我們可以確保每一個server會產生相同結果或是進入相同的狀態。

**共識演算法最主要的目的就是保證複製日誌（replicated log）的一致性**，用於實際系統的共識演算法包含以下特徵：
1. 確保在所有非拜占庭錯誤下的***safety***，即使是網路延遲、分區、資料包遺失、資料包重複和資料包亂序，也永遠不會傳一個錯誤的結果。
2. (**可用性**)只要超過一半的伺服器是可運行的，可以互相通訊和與客戶端通訊，那麼共識演算法就可用，失敗的伺服器可以從穩定儲存的狀態恢復並重新加入cluster。
3. **不依賴時序來保證log一致性**，因為錯誤的時脈和極端訊息的延遲在最壞的情況下會產生影響可用性的一系列問題。
4. 在通常情況下，只要cluster中超過一半的伺服器已經回應了單輪遠端過程呼叫（RPC），命令就可以被視為完成。**少數慢伺服器不會影響整個系統的效能**。
## 3. What’s wrong with Paxos?
:::success
Paxos的貢獻:
1. 定義了能在單一決策問題（例如single replicated log entry）上達成共識的協議(稱為single-decree Paxos)
2. 支持改變cluster中的成員
3. 提供safety和liveness
4. 在大多數情況下效率高的
:::
:::danger
Paxos的兩個致命缺點 :
1. **很難理解**
推測主要原因是Paxos用single-decree Paxos為基礎，這個協議分為兩個階段，但是Paxos的作者並沒有對這兩個階段進行簡單直觀的說明，而且這兩個階段也不能分開了單獨理解，所以使用者很難理解為什麼該演算法能起作用，而Multi-Paxos的合成規則又增加了更多複雜性。
2. **沒有為實際的實作提供一個良好的基礎**
其中一個原因是針對Multi-Paxos演算法沒有統一的理解，因為Lamport 的描述主要是針對signle-decree Paxos的，對於multi-Paxos的可能方法也有描述，但缺少了很多細節，雖然目前已經有人在嘗試具體化和優化Paxos，但是這些嘗試都互不相同並且它們跟Lamport描述的也不完全一樣。而像Chubby這樣的系統已經實作了類似Paxos演算法，但是也同樣沒有透露出很多的實作細節。

除此之外，Paxos的架構對於建立實際系統來說其實是一個糟糕的設計，因為Paxos演算法描述和現實的實做系統之間有著巨大的鴻溝，幾乎所有的實作都是從Paxos開始，然後在實現的過程中發現了一系列的難題，在解決難題的過程中，發展出了跟Paxos 完全不一樣的架構，最終的系統往往會建立在一個還未被證明的協定之上。
:::
綜合上述，作者認為Paxos不管在教學端和系統建構端都沒有提供一個好的基礎，所以決定嘗試設計一個替代Paxos，並且具有更好特性的共識演算法，也就是Raft。

## 4. Designing for understandability
設計Raft的目標:
* 提供⼀個完整且實際的系統實現基礎，希望能大幅減少開發者的工作。
* 必須在任何情況下都是安全的，
* 必須在大多數的應用條件下是可用的
* 必須在正常情況下是高效的。
* 可理解性高(最難達成的)，保證普通人都能理解

因為根據可理解性的分析具有高度主觀性，使用兩種方法讓Raft更容易被理解:
1. **problem decomposition(問題分解)** : 盡可能將問題分解成相對獨⽴、可被解決、解釋、理解的⼦問題，Raft演算法將共識問題分離成leader election、log replication、safety三個子問題。
2. **減少狀態數量** : 簡化需要考慮的狀態空間，盡可能使系統變得更連貫且盡可能消除不確定性。
>但某些情況下不確定性提高了可用性，例如隨機化方法增加了不確定性，但是這能夠透過以類似的方式處理所有可能的選擇來減少狀態空間，所以作者用隨機化方法來簡化Raft中的leader election演算法

## 5. The Raft consensus algorithm
Raft是用來**管理replicate log一致性**的演算法，會選出一個*Leader*擁有管理所有replicate log的權限，進而達到一致性，這簡化了管理replicate log的難度，*Leader*可以自行決定新log的寫入位置，資料都從*Leader*流向其他server。

Raft將共識問題分解為三個相對獨立的子問題 :
1. ***Leader* election** : 舊*Leader* fail時選出新的leader。
2. **Log replication** : *Leader*必須接收來自客戶端的log entries然後複製到cluster中的其他節點，並且強制其他節點的log和自己的保持一致。
3. **Safety** : 關鍵在於State Machine Safety ，只要有任何伺服器節點將特定的log entries套用到它的狀態機中，其他伺服器節點就不能在同一個log索引位置上儲存另外一條不同的指令。

:::warning
Raft在任何時候都會保證下列特性:
1. **Election Safety** : 對於一個給定的任期號，最多只會有一個leader被選出來。
2. ***Leader* Append-Only** : *Leader*絕對不會刪除或覆蓋自己的log，只會增加。
3. **Log Matching** : 如果兩個log在相同的索引位置且log entries的 *任期號碼(term)* 相同，就認為這個log從頭到這個索引位置之間的所有log entry和command都完全相同。
4. **Leader Completeness** : 如果某個log entry在某個*term*中已經被commit，那麼這個entry一定出現在更大任期號的所有leader中。
5. **State Machine Safety** : 如果一個*leader*已經將給定索引值位置的log entry應用到狀態機中，那麼其他任何的伺服器在這個索引位置不會提交一個不同的log。
:::

### 5.1 Raft basics
Raft cluster的伺服器都處於三個狀態之一：
1. *Leader* : 同個時間只有一個，回應所有客戶端請求。
2. *Follower* : 除了*Leader*外的server，只回應*Leader*或*Candidate*的請求
3. *Candidate* : 選舉新的*Leader*時使用。

Raft把時間分割成任意長度的*任期（term）*，用連續遞增整數編號，任期開始即選舉，Raft 保證一個任期只有一個*Leader*，*term*被視為是Raft的logical clock，讓伺服器可以發現一些過期的訊息。

每個節點都儲存當前任期號(不一定正確，就是server自己認為現在系統最新的term），節點之間通訊會交換任期號，當一個節點：
* 當前任期號比其他節點小，更新自己的任期號
* *Leader*或*Candidate*發現自己任期號過期，立即轉為*Follower*
* 收到過期的任期號請求，拒絕請求。

>**節點之間通訊使用遠端過程呼叫（RPCs）**:
>1. *RequestVote RPC* : *Candidate*在選舉期間發起。
>2. *AppendEntries RPC* : *Leader*發起，用於複製log和*heartbeat*。

### 5.2 Leader election
1. 剛開始所有節點都是Follower。
* *Follwer* 一段時間沒接收到訊息即*election timeout*，會發起新選舉。
* *Leader* 週期性發送 **heartbeat（不含log的 *AppendEntries RPC*)** 給所有Follower來讓大家認知到自己是leader。
* *Follwer*只要能收到*Leader*或*Candidate*的RPC就保持目前狀態。

2. 開始選舉 : *Follower*增加自己*term*（任期號）並轉為*Candidate*，並行向其他節點發送*RequestVote RPC*，並給自己投票，直到發生下列其中一項:
* 自己贏得選舉。
* 收到*Leader*的*heartbeat*，且*heartbeat*中的任期不小於自己的當前任期，則自己變為Follower。(若小於自己的任期，則拒絕並保持Candidate)。
* 如果同時出現多個*Candidate*，選票可能被瓜分，沒有人得到多數選票，則等待超時後重新選舉。
>選舉超時時間是從一個固定的區間（例如，150-300ms）中隨機選擇，來防止多次無人上任，每個節點開始選舉時重製逾時時間，可以讓多數情況只有一個節點超時，進入下一輪贏得選舉。

3. 獲得多數票的*Candidate*變成*Leader*。
* 每個節點在一個任期內，按照**first-come-first-served**（5.4還有額外限制）的原則，最多為一個*Candidate*投票。
* 成為*Leader*後向其他節點發送*heartbeat*建立權威。

### 5.3 Log replication
* Leader複製log流程:
1. 把client請求的command加到log，然後parallel發*AppendEntries RPC*給其他節點讓其追加log。
2. 在log被其他節點安全複製後（多數節點已複製），Leader執行該command到狀態機並傳回結果給client。
3. 如果中途出現問題，Leader 會不斷重發AppendEntries RPC，直到所有Follower 都追加了該日誌。
* commit log
* 一個log entry包含**目前的*term***和一條**command**，也都有一個index來表示在log中的位置
* **一旦建立該log entry的leader將它複製到過半的節點上時，該log entry就會被commit**，且leader log中該log entry**之前的所有log entry也會被commit**，包括先前的其他leader建立的log entry。
* Leader記錄最大已提交索引leaderCommit，並放進所有AppendEntries RPC，其他節點由此得知Leader已提交位置，並按log順序應用到自己的狀態機。
>**已經提交的log特性 :**
>1. 該entry及其之前的所有entry都將永久保存在系統中，不會被覆蓋或刪除，並且最終會被所有的節點接受。
>2. 一旦一個日誌條目被提交，它就可以被安全地應用到系統的狀態機上，
* log 一致性
* **Log Matching**。(上面5.提到的)
* 在不同的log中的兩個entry擁有相同的索引和任期號，那麼他們儲存了相同的指令。
* 在不同的log中的兩個entry擁有相同的索引和任期號，那麼他們之前的所有日誌條目也全部相同
* 其中第二項是**AppendEntries consistency check**所保證的，因為每次發*AppendEntries RPC*給Follower時，除了包含最新的entry外，還包含前一個entry的(index, term)，Followers 一定要 擁有同樣的前一個entry的(index, term) 才會儲存最新的log entry，否則就不接受該RPC。所以一旦*AppendEntries RPC*回傳成功，說明Follower 所有log和Leader相同
>可以想像成歸納法證明的步驟 (假設n-1成立，推出n成立，保證n之前都會符合該性質)
>**什麼時候會發生log不一致的狀況?**
正常情況下一致性檢查不會失敗，但是**Leader在未完全複製log時宕機會使log不一致**，如*Figure 7*。

* log 不一致時的恢復
**Leader 不需要特殊操作就能恢復一致性，會強制Follower複製自己的log，覆蓋Follower中所有衝突日誌**，(也就是上面5.提到的Leader Append-Only特性)。
在AppendEntries consistency check時Leader找到最後和Follower 一致的地方，刪除Follower之後的衝突日誌，並傳送自己的日誌給Follower。
* 當選出一個新的leader時，該Leader將所有的nextIndex 的值都初始化為自己最後一個log entry的index加1。
* **Follower日誌不一致則拒絕AppendEntries consistency**，Leader減少nextIndex重試直到成功，成功後Follower刪除衝突日誌並追加Leader日誌，log就會保持一致。

### 5.4 Safety
上面的討論不能保證每個狀態機以相同順序執行相同指令，例如因故障而缺少已經被提交的日誌的Follower可能被選為Leader並覆蓋日誌，就會造成不同的狀態機執行不同的指令的情況。
所以需要**增加選舉的限制，保證Leader Completeness Property**(上面5.提到的特性)，**確保Leader一定包含所有已經提交的log entry**。
1. Election restriction
某些一致性演算法中需要額外複雜機制把缺少的日誌傳給Leader，但Raft 保證Leader本來就有所有的log，而且**log entry的傳送只有一個方向**，那就是**從leader到follower**，leader從來不會覆蓋本地日誌中已有的日誌。
因此Raft採用投票的方式來保證一個candidate只有擁有先前所有任期中已經提交的log entry之後，才有可能贏得選舉，也就是說在等待投票時，*RequestVote RPC*會包含Candidate的日誌訊息，**投票人會拒絕日誌沒有比自己新的投票請求。**
:::success
投票者**比較最後一筆日誌的索引值和任期編號(*term*)**：
* 任期號不同，則任期號大的比較新
* 任期編號相同，索引值大的（日誌較長的）較新
:::
2. Committing entries from previous terms
5.3中提到只要日誌條目被存在多數節點，Leader就知道此日誌在自己任期已提交，但Leader可能在提交之前崩潰，新Leader不知道保存在多數節點的entry是否提交，如Figure 8，說明即使某日誌被複製到多數節點也不代表它被提交，仍可能被覆蓋。

所以Raft 對日誌提交條件增加一個額外限制：**Leader 在目前任期至少有一則日誌被提交（即超過半數節點複製）**，如圖8 中的（e）所示，那麼由於日誌匹配特性（Log Matching），先前的所有日誌條目也會被間接地提交。

3. Safety argument
使用**反證法**，透過假設Leader Completeness Property 是不滿足的，再推出矛盾，來**論證leader的Leader Completeness Property**。
>假設任期T的Leader T在任期內提交了一個log entry，但是該log entry沒有存在未來某些任期的Leader中，假設U是大於T的沒有存該log entry的最小term，處在任期U的leader稱為leader U。
**矛盾1.**
如果voter和leader U最後一個log entry的term相同的話，那麼leader U的日誌至少和voter的一樣長，所以leader U的log一定包含voter log中的所有log entry。但因為voter包含了已提交的log entry，所以leader U必定也包含該log entry，而前面我們假設了leader U是不包含的。
**矛盾2.**
如果不是上面描述的情況的話，那麼leader U最後一個log entry的任期號碼必然需要比voter的更大。也還比T還大，因為voter擁有在任期號碼為T提交的log entry，所以voter最後一個log entry的term至少為T。創建了leader U的最後一個log entry的之前的leader一定已經包含了已被提交的log entry（因為我們上面假設了leader U是第一個沒有該log entry的leader），所以，根據Log Matching特性，leader U一定也包含了該已被提交的日誌條目。
### 5.5 Follower and candidate crashes
Follower和Candidate 崩潰後的處理方式相較於Leader崩潰簡單很多，Raft只需要不斷重試發送RPCs即可，崩潰重啟後再執行RPC。
>**一直重複發送相同的RPCs 不會對系統造成傷害嗎?**
>不會，因為Raft 的RPCs 都是**冪等**的，也就是說**任意多次執行所產生的影響均與一次執行的影響相同**，一個follower 如果接收了一個AppendEntries 請求，但是這個請求裡面的這些log entry在它log中已經有了，它就會直接忽略這個新的請求中的這些log entry。

### 5.6 Timing and availability
Raft 的要求之一就是**安全性不能依賴時間**，整個系統不能因為某些事件運作的比預期快一點或慢一點就產生了錯誤的結果，但可用性不可避免要依賴時間，最關鍵在於Leader election，需要滿足以下時間要求：
>**廣播時間（broadcastTime） << 選舉逾時時間（electionTimeout） << 平均故障間隔時間（MTBF）**
* 廣播時間（broadcastTime）
* 一個節點並行發送RPC 給其他節點並接收回應的平均時間。
* 應比選舉超時時間小一個數量級才能保證穩定的heartbeat。
* 廣播時間大約是0.5ms到20ms，取決於儲存的技術。

* 選舉超時時間（electionTimeout）(只有這個是我們自己選擇的)
* 即5.2 中選舉超時時間限制，隨機化使得難以瓜分選票。
* 需要比平均故障間隔時間小上幾個數量級
* Leader 崩潰後系統將在一個選舉超時時間中不可用，此情況應很少出現。
* 平均故障間隔時間（MTBF）
* 對一台伺服器而言，兩次故障間隔時間的平均值。
* 大多數伺服器平均故障時間在幾個月甚至更長，很容易滿足時間的需求。

## 6. Cluster membership changes
前面都是假設cluster的配置（參與共識演算法的server節點集合）固定不變，但是在實際情況中有時候需要去改變cluster配置，例如在server崩潰的時候去更換server或是更改副本的數量，而手動暫停重啟易出錯且會有段時間不可用，所以需要**自動化改變配置**。

為了讓配置修改的機制是安全的，在轉換的過程中同一個任期不能夠存在兩個Leader同時當選，但一次性自動的轉換所有伺服器是不可能的，任何切換方法都不安全，所以在轉換期間整個cluster可能會分裂成兩個獨立的多數，為了確保安全性，配置變更必須使用**兩階段方法**。cluster會先切換到一個過渡性配置，稱為**Joint Consensus（聯合共識）**，一旦聯合共識被提交，那麼系統就切換到新的配置上。
>Joint Consensus是舊配置和新配置的結合:
>* log entry被複製給cluster中新、舊配置的所有伺服器。
>* 新、舊配置的server都可以成為領導人。
>* **達成一致（選舉和提交）需要分別在兩種配置上獲得大多數的支持**。
>
>允許獨立的伺服器在不影響安全性的前提下，在不同的時間進行設定轉換，還可以讓cluster在設定轉換的過程中回應客戶端的請求。

* **配置轉換過程(*Figure 11*)** :
1. 當一個Leader 接收到一個改變配置從$C_{old}$ 到$C_{new}$ 的請求，會建立聯合共識的配置（圖中的$C_{old, new}$ ），並儲存為一個新log entry。
2. Leader 將$C_{old, new}$ 發給所有Follower進行複製。
* 如果$C_{old, new}$ 被半數以上節點同步，則此配置已提交，之後遵循Raft 安全性機制，**只有擁有$C_{old, new}$ 日誌條目的伺服器才有可能被選為新Leader**。
* 如果半數同步前Leader崩潰，如果新Leader沒有$C_{old, new}$ ，就退回舊配置重試更新。
* 在這段時期，$C_{new}$ 不會有任何影響。
3. $C_{old, new}$ 已提交後，$C_{old}$ 已不會產生影響，Leader 再建立和提交$C_{new}$ 就是安全的了。


**整個過程中沒有哪個時候讓$C_{old}$ 和$C_{new}$ 同時產生影響**，保證了安全性。

* 配置變更三個需要解決的問題：
1. 新的節點可能在一開始並沒有儲存任何的日誌條目，他們需要一段時間來更新自己的日誌，此時無法作為提交和選舉的節點。
>**為了避免因此造成的系統短時間的不可用**，會**在配置變更之前引入了一個額外的階段** : 此期間以沒有投票權身分加入cluster中來，不參加選舉投票和日誌提交決策，直到日誌同步完成。
2. leader 有可能不是新配置中的一員
>Leader 在提交了$C_{new}$ 日誌之後主動回到Follower狀態，代表有一段時間Leader管理一個不包括自己的集群，它會複製日誌給其他節點，但是算副本數量的時候不會算上自己。
3. 被移除的伺服器(（不處於$C_{new}$ 狀態的節點)未關閉，可能會擾亂叢集。(因為它們不再收到heartbeat，就會一直超時發起帶有新任期號的選舉。)
>集群中節點在未達到選舉超時時間前，不響應*RequestVote RPC*。因為如果當前Leader能夠在超時時間內發送心跳，Follwer 就能確認當前Leader存在而不回應新的投票請求。
## 7. Clients and log compaction
## 8. Implementation and evaluation

* 可理解性：比Paxos好很多
* 正確性：前面證明
* 性能：和Paxos差不多
* **選舉超時時間隨機化**能大大加快領導人選舉過程收斂。
* 透過**減少選舉超時時間**可以減少系統的宕機時間，但繼續減少會違反Raft的時間不等式需求，建議使用150-300 毫秒。

## 9. Related work

介紹其他一致性演算法的特性。
Raft的強Leader模型簡化了整個演算法，但同時也排斥了一些效能最佳化的方法，例如，平等主義Paxos（EPaxos）在某些沒有領導人的情況下可以達到很高的表現，而Raft和Paxos最大的差異就在於Raft的強Leader特性。
## 10. Conclusion
演算法的設計通常以正確性、效率和簡潔性為主要目標，但可理解性也很重要，所以本篇作者開發了一種新的算法Raft，相比於其他的共識演算法，Raft以可理解性為主要設計目標，隨著設計的進展，發現重複使用了一些技術，例如問題分解和狀態空間簡化，除了提高可理解性，也更容易證實其正確性。

## Reference
[筆記] https://zhuanlan.zhihu.com/p/514512060
[翻譯] https://zhuanlan.zhihu.com/p/524885008