# 3-3. Raft - In Search of an Understandable Consensus Algorithm
## Introduction
Consensus algorithms: 通常出現在 replicated state machines 的背景下，允許 machines 成為一致的群體，且當單一個體不可用時全體還是可以存活

* Paxos
* 在 Consensus algorithms 的討論中占主導地位
* 缺點: 非常困難理解、在實際運用時需要做複雜的更動
* Raft
* 目標為 understandability
* decomposition (leader election、log replication、safety)
* state space reduction(減少 nondeterminism、inconsistent between servers，randomized timer 來選舉 leader)
* 擁有舊機制: Viewstamped Replication
* 新機制:
* Strong leader: log entries 僅從 leader 流向其他 servers，簡化了複製日誌的管理
* Leader election: randomized timer 來選舉 leader，只對 Consensus algorithms 中 heatbeat 機制增加了一小部分，迅速地解決衝突。
* Membership changes： 對於改變 cluster 中 set of server 的機制採用了一種新的 joint consensus 方法，在轉換期間的兩種不同配置的大多數重疊，允許 cluster 在配置變更期間繼續正常運作

* Raft 好處
* simpler and more understandable
* 對於實際的系統應用 completely enough
* several open-source or companies implementations
* safety properties
* 和其他系統一樣的 efficiency
## Replicated state machines
* replicated state machines
* 概念: 一組 server 上的 state machines 執行++相同狀態的完全相同++副本，即使某些伺服器宕機也能繼續運作
* 常用於解決分散式系統中的各種容錯問題
* 組成: replicated log、consensus algorithms、state machine
* replicated log
* 包含一系列命令
* 不同 server 的 log 包含相同的命令且順序相同
* state machines
* state machine 按順序執行 log 中的命令
* 不同 server 都計算出相同的狀態和相同的輸出序列
* Consensus algorithms
* 通常出現在 replicated state machines 的背景下
* 管理replicated log
* consensus module 接收來自 client 的 state machine 命令並將它們加入到其日誌中
* communicates with 其他伺服器上的 the consensus modules(即使某些伺服器失敗)
::: info
servers 形成了一個單一的、高度可靠的 state machines
:::

Consensus algorithms' properties for practical system :
* safety: 在所有 non-Byzantine 條件下確保永不返回錯誤結果，包括網絡延遲、分區以及數據包的丟失、重複和重新排序
* available: 只要大多數(大於一半) servers 可運行、能夠相互通信、可與客戶端通信，它們就是可用的
* server 假定是以 stop 來失效的，它們可能稍後從 stable storage 的狀態中恢復並重新加入 cluster
* 不依賴於時間來確保 log 的 consistency： 錯誤的 clock 和極端的消息延遲最多可以導致 availability 問題
* slower server 的少數不會影響整個系統的性能: 一旦 cluster 的大多數回應了一輪 remote procedure calls，命令就可以完成

## What’s wrong with Paxos?
* Paxos
1. 定義單一決策如何達成一致的 protocal(例如 a replicated log entry)，single-decree Paxos
2. 結合 single-decree Paxos 的多個實作，達到一系列的決策(例如 a replicated log)，multi-Paxos
* safety、liveness、efficient、supporting changes in cluster membership
* 缺點:
* Paxos異常難以理解
* single-decree Paxos：被分成兩個階段，這兩個階段沒有簡單直觀的解釋，且不能獨立理解
* multi-Paxos: 組成規則增加了顯著的額外複雜性和微妙性
* 沒有提供一個良好的基礎來建立實際的實作
* Lamport的描述主要關於單一法令Paxos，其他系統與Lamport的草圖有所不同、類Paxos算法細節沒有被公開
* Paxos架構對於建立實際系統來說是不佳的選擇
* 單一法令分解
* 缺點: 獨立選擇一系列 log entry 然後將它們合併成一個 order log 的好處很少，增加了複雜性
* 改善: 設計一個圍繞 log 的系統，其中 new entry 以限定的順序添加，會更簡單且更有效率
* 核心使用了對等的點對點方法
* 缺點: 在只做出單一決策的簡化世界中，這種方法是有意義的，但很少有實際系統使用這種方法
* 改善: 做出一系列決策時，首先選舉出一位 leader，然後讓 leader 協調決策會更簡單且更快
:::info
Paxos 的公式對於證明其正確性的定理很有用，但真實的實作與Paxos算法的描述間存在顯著差距，每個實作都是從Paxos開始，發現實作它的困難，然後發展出一個基於一個未經證明的協議的不同架構
:::

## Designing for understandability
設計Raft目標
* complete and practical foundation: 減少開發者系統建造所需的工作量
* safe: 必須在所有條件下都是安全的，並且在一般運作的條件下可用
* efficient: 對於常見操作
* understandability: 必須讓廣大受眾能夠舒適地理解算法

在不同的設計方案之間進行選擇: 根據 understandability 來評估各種選擇
* 存在很高程度的主觀性
* 使用了兩種普遍適用的技術
* problem decomposition: 將問題分解成可以獨立解決、解釋和理解的單獨部分
* simplify the state space: 通過減少需要考慮的 state 數量，使系統更加連貫並在可能的情況下消除 nondeterminism

## The Raft consensus algorithm
1. elect a leader，然後賦予 leader 完全負責管理 replicated log 的責任(實現 consensus)
2. leader 接受來自 client 的 log entry，在其他 server 上複製這些 entry，並告訴 server 何時可以將 log entry 安全地應用到它們的 state machine 上。
3. leader 可能會失敗或與其他伺服器斷開連接，在這種情況下會選舉新的 leader

++擁有一位 leader 簡化了 replicated log 的管++理
* leader 決定在 log 事項時無需諮詢其他 server
* data 以一種簡單的方式從 leader 流向其他伺服器

:::warning
Raft guarantees that each of these properties is true at all time
* Election Safety: at most one leader can be elected in a given term
* Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries
* Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index
* Leader Completeness: if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms
* State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index
:::

### Raft basics
Raft cluster 包含數個 server
* three state of server
* leader
* 處理所有 client request
* follower
* 被動的：他們不會自行發起請求，只是對來自 leader 和 candidate 的 request 作出 response
* 如果 client 聯繫 follower，會將其重定向到 leader
* candidate
* 用於 elect 新的 leader
* system part
* in start of term
* one or more candidate
* in middle of term
* only one leader in a term
* others are follower
* term
* time 被分為任意長度的 term
* term 以連續整數編號
* elect
* start of term 進行一次選舉
* 一個或多個 candidate 嘗試成為 leader


++不同的 server 可能會在不同的時間觀察到 term 之間的轉換，一台 server 可能會沒有觀察到選舉或甚至整個任期++
* server

* currentTerm
* 每當 server 之間通訊時就會交換currentTerm，如果一台 server 的 currentTerm 小於另一台的，那麼它將其currentTerm 更新為較大的值
* 允許 server 檢測過時的資訊，如 older leader
* communication
* 使用 RPCs 進行通信
* 僅需要兩種類型的RPCs
* RequestVote RPCs 由 candidate 在選舉期間發起
* AppendEntries RPCs 由 leader 發起，用於複製 log entry 或提供heatbeat
* 如果一台 server receive request with older termNumber，server 將拒絕該 request
* 如果 server 沒有及時收到 response，它們會重試RPCs
* 為了最佳性能並行發出RPCs


* rule

### Leader election
Raft 使用 heatbeat 機制來選擇什麼時候要觸發 leader 選舉

1. when server start -> follower
* 只要 server 從 leader 或 candidate 那裡收到有效的 RPCs，就會保持在 follwer
* leader 發送定期的 heatbeat（不攜帶 log entry 的 AppendEntries RPCs）給所有 follower
2. follower doesn't receive any RPCs in election time period(election timeout) -> candidate
* 會假定沒有可行的 leader，並開始一場選舉來選擇新的 leader
* follower 會增加其 **currentTerm** 並轉變為 candidate
* 為自己投票且並行地向 cluster 中的其他 server 發出 RequestVote RPCs

elect result
* win elect
* 候選人在同一 term 獲得了超越半數選票，那麼它就贏得了選舉
* 一旦 candidate 贏得選舉，它就成為 leader，它向所有其他伺服器發送 heatbeat 消息，以防止新的選舉
:::info
Election Safety
每個 server 在單一 term 內最多只會為一個 candidate 投票(**voteFor**)，基於 first-come-first-served 的原則，多數規則確保了最多只有一個 candidate 能夠在特定 term 贏得選舉
:::
* another server(candidate) become leader
* a candicate 可能會收到來自另一個聲稱是 leader 的 server 發來的 AppendEntries RPC
* 如果該 leader 的 term（包含在其RPC中） >= candidate 的 **currentTerm**，那麼候選人將承認該領導者的合法性並返回到 follower
* 如果 RPC 中的 term < candicate 的 **currentTerm**，那麼 candicate 將拒絕該 RPC 並繼續保持 candidate
* no winner after election timeout
* 如果許多 follower 同時成為 candidate，選票可能會被分割，以至於沒有候選人獲得多數票
* 每個 candiadate 都會 timeout 並通過增加其 **currentTerm** 並發起另一輪RequestVote RPCs來開始新的選舉
* 防止分割的選票可能會無限重複
* randomized election timeout: 從固定區間中隨機選擇的
* 在大多數情況下只有單一伺服器會超時
* 每個 candidate 在選舉開始時重啟其 randomized election timeout，減少了新選舉中另一次分裂投票的可能性

### Log replication
forcing the other logs to agree with its own
#### client request
一旦選出了 leader 就開始處理 client request
* client request 包含一條要由 replicated state machines 執行的命令
1. leader 將該命令作為 new entry 追加到自己的 log
2. leader 並行向其他 server 發出 AppendEntries RPCs 複製 entry
* 如果 follower unavailble，leader 會無限重試 AppendEntries RPCs（即使在它已經回應給 client 之後）直到所有 follower 最終儲存 log entry
2. 當 entry 已被安全複製時，leader 將該 entry 在自己的 state machine 執行
3. 將結果返回給 client

#### log機制

log entry = 一條 state machine 命令 + leader 接收該 entry 時的 term number + log index
* term number 用於檢測 log 之間的不一致性
* log index 標識 entry 在 log 中的位置

##### commit entry
* ==一旦創建 entry 的 leader 在大多數 server 上複製了該 entry，該 entry 就被視為 commit==
* 允許 log entry executed by state machine of leader
* Raft 保證已提交的 entry 是永久的，並且最終會被所有可用的 state machine 執行
* 等同於 commit leader log 中的++所有先前條目++，包括由前任 leader 創建的 entry(之後會提到)
* leader 跟踪其知道的最高 commit index(**leaderCommit**)，並在未來的AppendEntries RPCs（包括 heatbeat）中包含該 index，以便其他 server 最終知道
* 一旦 follower 了解到一個日誌條目已被 commit，它就將該條目應用於其本地 state machine
##### Log Matching
不一致原因
* 在正常運作期間，leader 和 follower 的 log 保持一致
* ==leader 崩潰==可能會讓日誌保持不一致（leader 可能沒有複製在崩潰後 log 中的 entry），不一致可能在一系列 leader 和 follower 崩潰中累積
* 一個 follower 可能缺少 leader 存在的entry 或者可能有額外的entry，這些 entry 在 leader 上不存在，或者兩者都有

:::info
Log Matching
如果兩個 log 中的兩個 entry 具有相同的 index 和 term => two entry 儲存相同的命令、two log 在此 entry 先前的所有都是相同的
:::
確保 Log Matching 的原因
* 原因一： 一個 leader 在 term 內最多只創建一個對應 log index 的 entry，且 log entry 永遠不會改變在 log 中的位置
* 原因二： AppendEntries RPC 會執行的一個的一致性檢查
* 當發送一個AppendEntries RPC時，包括了 leader log 中緊接在 new entry 之前的 entry 的 index(**prevLogIndex**) 和 term(**prevLogTerm**)
* 如果 follower 在其 log 中沒有找到有相同 index、 term 的 entry，那麼它就會拒絕新條目
* 檢查步驟
1. log 的初始空狀態滿足 log 匹配屬性
2. 每當 log 被擴展時，啟動一致性檢查
3. follower log 中的衝突 entry 將被leader log 中的 entry 覆蓋
3.1. leader 找到兩個 log 最後一致的 entry(**nextIndex[]**)
3.2. 刪除 follower log 中該點之後的任何 entry
3.3. 將該點之後 leader 的所有 entry 發給 follower
4. 每當AppendEntries成功返回時，領導者就知道追隨者的日誌通過新條目與自己的日誌相同

==leader 初始化==(達成一致)
1. 當 leader 首次上台時，它將所有 **nextIndex** 初始化為其 log 中最後一個 entry 之後的 index
2. 如果 follower 的 所有 log entry 與 leader 的不一致，則在下一個 AppendEntries RPC 被拒絕
3. 在被拒絕後，leader 減少 **nextIndex** 並重試AppendEntries RPC
4. 最終，**nextIndex** 將達到 leader 和 follower 匹配的點
5. AppendEntries成功，刪除 follower log 衝突 entry 並追加 leader entry（如果有的話）
:::info
Leader Append-Only
憑藉這種機制，當 leader 上任時，它不需要採取任何特別行動來恢復日誌的一致性。它只是開始正常運作，而 log 會自動在 AppendEntries 一致性檢查失敗的 response 中逐漸趨同，一個 leader 永遠不會覆寫或刪除其自己 log 中的 entry
:::
log 機制達成 Consensus 屬性
* safety 基礎
* consistency
* available
* 單個slower follower 不會影響性能

:::info
Raft 在不同 server 上的 log 之間保持高度的一致性，簡化了系統的行為並使其更可預測，且為確保安全的一部分
:::

### Safety
如果任何 server 已將特定 log entry 執行於其 state machine，那麼其他 server 則不得為相同的 log index(位置) 執行不同的命令
* 到目前為止描述的機制還不足以保證每個 state machine 以相同的順序執行完全相同的命令
* ex: 一個 follower 可能在 leader 提交commit log entries 前成為不可用的情況下被選為 leader 並用新的 entry 覆蓋這些 entry -> new leader 和其他 server 有不同的 state machine 執行命令序列
* 通過增加一項限制來完成，限制規定了哪些 server 可以被選為 leader
* 確保任何給定 term 的 leader 包含了前幾 term 中所有已提交的 entries
* 鑑於選舉限制，接著使 commit 規則更加精確

#### Election restriction
:::info
Leader Completeness
leader 最終必須儲存所有已 commit 的 log entry
:::

Raft 保證所有前 term 中已提交的 entry 在新 leader 當選的那一刻起就存在於其身上
:::info
Leader Append-Only
這意味著 log entry 只在一個方向上流動，從 leader 到 follower，leader 永遠不會覆寫其 log 中現有的 entry
:::
作法: 透過投票程序來防止一個違法的(log 不包含所有已 commit 的 log) candidate 贏得選舉
>up-to-date
比較 log 中最後一個 entry 的 index 和 term
如果 log 的最後 entry 位於不同的 term，則 term 較晚的 log 會更加 up-to-date
如果 log 以相同的 term 結束，那麼較長的 log 就會更加 up-to-date
* candidate 必須聯繫到大多數 server 才能獲勝，所以不管怎麼選出大多數，在這個集合中都會包含所有已 commit 的 entry
* 因為要能夠 commit 代表必須存在在大多數的 server 上
* 根據鴿籠原理，每個已 commit 的 entry 必須至少出現在那些 server 中其中一個上
* 如果 candidate 的 log 至少與該多數集中任何其他 log 一樣 up-to-date，那麼它將包含所有已 commit 的 entry
* 利用 RequestVote RPC: RPC包含了關於 candidate log 的信息(**lastLogIndex**、**lastLogTerm**)，如果投票者自己的 log 比 candidate 的更 up-to-date，就會拒絕投票給 candidate

:::success
在任何基於領導者的共識算法中，領導者最終必須儲存所有已提交的日誌條目。在一些共識算法中，即使領導者最初不包含所有已提交的條目，也可以被選舉為領導者。這些算法包含額外的機制來識別缺失的條目並在選舉過程中或之後不久將它們傳輸給新領導者。不幸的是，這導致了相當大的額外機制和複雜性。Raft使用了一種更簡單的方法，它保證所有前任期中已提交的條目在新領導者當選的那一刻起就存在於每位新領導者身上，無需將這些條目轉移給領導者。這意味著日誌條目只在一個方向上流動，從領導者到追隨者，領導者永遠不會覆寫其日誌中現有的條目。

Raft通过投票过程来防止一个候选人赢得选举，除非其日志包含所有已提交的条目。候选人必须联系到大多数集群才能被选举，这意味着每个已提交的条目必须至少出现在那些服务器中的一个上。如果候选人的日志至少与该多数派中任何其他日志一样更新（其中“更新”将在下面明确定义），那么它将包含所有已提交的条目。RequestVote RPC实现了这个限制：RPC包含了关于候选人日志的信息，如果投票者自己的日志比候选人的更更新，它就会拒绝投票给候选人。

Raft通过比较日志中最后条目的索引和任期来确定哪个日志更加更新。如果日志的最后条目位于不同的任期，那么任期较晚的日志更加更新。如果日志以相同的任期结束，那么较长的日志更加更新。
:::

#### Committing entries from previous terms
:::info
State Machine Safety
已被執行的 entry 的 index 就再也不能被覆蓋了
:::
問題: ==有機會覆蓋(移除)重複但未 commit 的 log，導致 log 和 執行順序不一致==
(其中一個舊的 entry 被儲存在大多數server，但仍然可以被未來的 leader 覆蓋)

* 一個 entry 若是複製到其他 server 但卻未達到可以 commit 的情況(leader 在複製的過程中死了)，下一個會 leader 並不會對其進行任何恢復的行為
* 根據 AppendEntries RPC
* 若是此 entry 存在在新的 leader，entry 會被複製到其他 server 上
* 若是此 entry 不存在在新的 leader，最後會被其他已 commit 的 entry 被覆蓋過去

>a leader 知道，一旦其++目前++ term 的 entry 被儲存在大多數 server 上，那麼該 entry 就被認為是已 commit 的
But，a leader 不能立即得出結論認為，一旦一個來自++先前++ term 的 entry 被儲存在大多數 server 上，就認為該 entry 已經 commit

因為 Election restriction
所以 判斷 commit(安全性)
* 計算副本來 commit -> 來自 leader 目前 term 的 entry
* 先前 term 的 entry 則是通過 Leader Completeness
* 一旦 commit 了當前 term 的 entry，那麼所有在 leader log 上先前的 entry 由於 Log Matching 而間接地被 commit
:::danger
若是存在一個未被 commit 的 entry，代表這個 entry 並不能被視為一致性內的一部份，可能就會被覆蓋還是之後 client 會重新要求，但它目前對系統還是屬於無效的，因為尚未被執行
:::

#### Safety argument
使用反證法，證明 Leader Completeness 是成立的

反例假設:
* term T 的 leader（leaderT）commit 了一個來自其 term 的 entry，但該 entry 未被某個未來 term 的 leader 儲存(最小的 term U > T，其 leader（leaderU）沒有儲存該 entry)

矛盾:
commit 的 entry 在 leaderU 當選時必定不在其 log 中（leader 從不刪除或覆蓋條目）
1. leaderT 在 cluster 的大多數上複製了該 entry
2. leaderU從 cluster 的大多數獲得了投票
* 因此，至少有一個 server（“投票者”）既接受了來自 leaderT 的 entry 又投票給了 leaderU
1. 此投票者，先從 leaderT 那裡接受了commit entry，後投票給 leaderU；否則拒絕來自 leaderT 的 AppendEntries RPC request(commit entry 複製)（此投票者其當前 term > T 的 term）
2. 投票者在投票給 leaderU 時仍然存儲了該 entry
* 投票者投票給 leaderU，所以 leaderU 的 log 必須與投票者的一樣 up-to-date，導致2個矛盾
* leaderU 的 **lastLogTerm** == 投票者的 **lastLogTerm** -> leaderU 的 log 必須至少與投票者的一樣長，因此 leaderU log 包含了投票者 log 中的每一個entry
=> 矛盾，因為投票者包含了 commit 的 entry 而假設 leaderU 不包含
* leaderU 的 **lastLogTerm** > 投票者的 **lastLogTerm** >= leaderT 的 **lastLogTerm** -> 創建 leaderU 的 **lastLogTerm** entry 的早期 leader，必須在其 log 中包含了 leaderT commit 的 entry（根據假設）
=> 矛盾，根據 Log Matching，leaderU 的 log 也必須包含 leaderT commit 的 entry

Log Matching 保證未來的 leader 也將包含間接 commit 的 entry

## Follower and candidate crashes
* follower崩潰
* 未來發送給它的 RequestVote 和 AppendEntries RPCs將會失敗
* Raft 透過無限重試來處理這些失敗情況
* 如果崩潰的 server 重新啟動了，那麼RPC將成功完成
* 如果 server 在完成 RPC (複製)之後但在 送出 response 之前崩潰，那麼它在重新啟動後將再次收到相同的 RPC
* candidate 崩潰
* 只會超時，然後其他人發起新的選舉

#### Timing and availability
Raft 安全性不依賴時間
* 系統不能因為某件事發生的比較快而影響結果

*BUT!* 可用性與時間相關
* 例如，訊息交換時間比 server crash 還要久，會導致選不出 leader

在整個系統中與時間最相關的為選舉，need:
:::info
broadcastTime ≪ electionTimeout ≪ MTBF
:::
* broadcastTime: server 並行向其他 server 發送 RPC 並接收 response 的平均時間
* electionTimeout: 選舉超時區間
* MTBF: 單個 server crash 的平均時間
* broadcastTime ≪ electionTimeout: 以便能持續發送heatbeat
* electionTimeout ≪ MTBF: 系統只會在選舉期間不可用，佔總體時間不多

## Cluster membership changes
到目前為止，cluster 中的 server 都是固定的，但實際上 set 的配置還是有機會改變(server change)

Raft 自動化解決
安全
* 在配置變更期間，不能同時存在2個 leader
* two-phase approach
* 過渡配置: joint consensus
* old + new
* 允許集群在配置更改期間繼續服務 client 請求
* entry 會被複製到 old、new 配置中的所有 server 上
* 來自任何一種配置的 server 都可以作為 leader
* 達成共識（對於選舉和 entry commit）需要來自 old 配置和 new 配置的各自多數的同意

過程
先切換到 joint consensus，joint consensus commit 後，系統就會成為新的
1. 當 leader 收到從 Cold 變更到Cnew 的配置 request，將 Cold,new 作為 entry 並進行複製擴散
2. 一旦某個 server 將新配置 entry 添加到 log 中，它就會使用該配置進行所有未來的決策
* leader 使用 Cold,new 的規則來確定 Cold,new entry 何時 commit(新的 leader 可能在 Cold 或 Cold,new 下被選出，這取決於獲勝的 candidate 是否收到了 Cold,new，Cnew在此期間都不能單方面做出決策)
3. 一旦Cold,new 被 commit，Cold 和 Cnew都不能在沒有對方批准的情況下做出決策
4. Leader Completeness 確保只有擁有 Cold,new entry 的 server 可以被選為leader
5. leader 創建 Cnew 的 entry 並將其複製到 cluster
6. new 配置在每個 server 看到它時就會生效
7. 當新配置( Cnew )被 commit 後，舊配置就變得無關緊要了，不在新配置中的伺服器可以被關閉
:::info
Cold 和 Cnew 都無法在任何時候單方面做出決策，這保證了安全性
:::
三個問題
* new server 最初可能不存儲任何 log entery，如果在這種狀態下被添加到 cluster 中，可能需要相當長的時間來趕上，在此期間可能無法 commit new entry
* 引入了一個額外階段，在這個階段中new server 作為非投票成員加入 cluster （leader 將 entry 複製給它們，但它們不被考慮為多數，參與選舉）
* leader 可能不會是新配置的一部分
* 一旦leader commit 了 Cnew的entry，它就會退回到 follower
* new leader 選舉：只有包含最新 commit entry candidate 才能被投票，所以最後的 leader 一定是新的
* 新的 cluster 中只有 新的 server可以被發送訊息，一些尚未被關閉可能會干擾選舉，因為收不到 heatbeat 而開始發起新的選舉，導致可用性差
* 當 server 認為目前仍有 leader 則忽略 RequestVote RPCs -> 忽略在一個 electionTimeout 內收到 的 RequestVote RPCs
* 不會影響正常的選舉，每個 server 在開始選舉前至少等待一個electionTimeout

## Clients and log compaction
* clent 如何與Raft互動
* clirnt 如何找到 leader 以及Raft 如何支持 linearizable semantics
* 如何使用 snapshotting 方法回收 log 中的空間
## Implementation and evaluation
使用三個標準來評估Raft：可理解性、正確性、性能
* 可理解性
* 利用2所大學中學生的學時候測驗結果來得知，Raft 比 Paxos 更易懂，不論是在實際測驗或者是訪談中
* 正確性
* 對安全性制定正式的規範及證明
* 性能
* 2個問題
* 選舉過程的收斂是否足夠快?
* 在 leader crash 之後，最小的系统崩潰時間是多久？
* 反覆使五個服務器組成的集群的領導者崩潰，並計時檢測崩潰並選舉新領導者所需的時間
* server 擁有不同的 log 長度
* 鼓勵分裂投票，模擬了 leader 在 crash 前複製 new entry 的行為
* 頂部圖表顯示，在選舉超時中加入少量的隨機化足以避免選舉中的分裂投票
* 底部圖表顯示，通過減少選舉超時可以減少整體停機時間