實戰從零開始實現 Raft

一 前言

Raft 算法是一種分佈式一致性算法，由 Diego Ongaro 和 John Ousterhout 在 2013 年提出。它主要用於分佈式系統中，保證系統中的數據在多個節點間保持一致性。

Raft 算法被廣泛應用於衆多分佈式系統中，尤其是在需要強一致性保證的場景中，例如：

• 分佈式存儲系統：如 ETCD、Consul 等鍵值存儲系統，它們利用 Raft 算法來保證數據的強一致性和高可用性。

• 分佈式數據庫：一些分佈式數據庫管理系統（DBMS），如 CockroachDB 等。

• 分佈式鎖服務：例如 Google 的 Chubby 以及微軟的 Azure Service Bus 等。

得物的多個內部中間件也是使用 Raft 算法作爲多分片一致性的保證。

長期以來，大部分開發者都是將 Raft 作爲一個黑盒使用，只知道它能保證多分片的一致性，對其運行原理也停留在紙面。當面臨 Raft 性能調優或者奇怪的 Raft 問題排障的時候則束手無策。

費曼說過：“What I cannot create, I do not understand。” 我們中國先賢也強調 “知行合一，以致良知”。如果我們不能親手編寫一次 Raft 算法，對這個東西就不能算作理解。

二 核心概念

在着手開始寫之前，我們先介紹幾個 Raft 算法中的核心概念。

日誌複製狀態機

如果說什麼是分佈式系統理論的基石，那一定 “日誌”。此處的日誌與我們平時在應用中打印的給人閱讀的信息不同，它是最簡單的存儲抽象，是按時間排序的 append-only 的、有序的記錄序列。

“日誌” 揭示了系統當下正在發生的事實。

關於日誌的更深入理解，可以參考博客 The Log: What every software engineer should know about real-time data's unifying abstraction，非常全面深刻。

當進入分佈式的領域，日誌就需要 “狀態機” 的輔助：

• 如果兩個相同的確定性過程以相同的狀態開始並以相同的順序獲得相同的輸入，它們將產生相同的輸出並以相同的狀態結束。

• 確定性意味着處理不依賴於時間，並且不會讓任何其他輸入影響其結果。例如，一個程序的輸出受到線程特定執行順序或調用 gettimeofday 或其他一些不可重複的東西的影響，通常最好被認爲是非確定性的。

• 進程的狀態是在處理結束時保留在機器上的任何數據，無論是在內存中還是在磁盤上。

關於以相同的順序獲得相同的輸入的一點應該會引起人們的注意——這就是日誌的用武之地。這是一個非常直觀的概念：如果你將兩段確定性代碼提供給相同的輸入日誌，它們將產生相同的輸出。

所以 Raft 最重要的任務就是解決如何在分佈式系統中使多個副本的日誌數據達成一致的問題。

Leader、Follower、Candidate

爲了實現上述目標，Raft 使用強領導模型，即要求集羣中的一個副本充當 Leader，其他副本充當 Follower。

Leader 負責根據客戶端請求採取行動生成命令，將命令複製給 Follower，並將響應返回給客戶端。

多個副本根據選舉算法推選合法的 Leader。

這個方案解決了分佈式系統中的以下問題：

• 容錯性（Fault Tolerance）：分佈式系統中可能會出現節點故障，包括宕機、網絡分區等問題。通過這些角色的分工和協作，系統可以在一定數量的節點出現故障時仍然正常運行。

• 領導者選舉（Leader Election）：在分佈式系統中，通常需要一個節點（Leader）來協調其他節點（Followers）的工作，以確保一致性和效率。Leader 負責管理日誌複製、決策提議等任務。當 Leader 失效時，系統需要能夠選舉出新的 Leader。

• 一致性（Consensus）：爲了保證系統狀態的一致性，需要所有節點就某個值或狀態達成共識。這通常通過一系列的投票和通信過程來實現，其中 Candidate 角色在選舉過程中起到關鍵作用。

• 去中心化（Decentralization）：在去中心化的系統中，沒有中央權威來決定系統狀態。這些角色的引入有助於在沒有中心節點的情況下實現一致性和決策。

這種模型有其優點和缺點：

• 顯著的優點是簡單。數據總是從領導者流向 Leader，只有 Leader 響應客戶端請求 (工程實踐中有例外)。這使得 Raft 集羣更容易分析、測試和調試。

• 缺點是性能——因爲集羣中只有一臺服務器與客戶端通信，這在客戶端活動激增的情況下可能成爲瓶頸。當然這個可以通過一些工程手段在一致性和吞吐性能中做出平衡，例如我們可以放棄強一致的要求，從 Follower 中讀取數據，減輕 Leader 的負擔，關於一致性的部分，可以參考文章《共識、線性一致性、順序一致性、最終一致性、強一致性概念區分》。

三 Why Elixir

本系列中介紹的 Raft 實現是用 Elixir 編寫的。在筆者看來，Elixir 具有三個優勢，使其成爲本系列和網絡服務的有前途的實現語言：

• Raft 框架需要大量的網絡編程，而 Elixir 基於 Erlang 在網絡編程方面體驗一騎絕塵，甚至自帶 RPC 實現；

• Elixir 自帶一個功能強大的 Shell，開發調試的難度大大降低；

• Raft 這類算法需要大量的併發編程，而併發編程在 Elixir 中就像呼吸一樣簡單；

• Erlang 語言的 OTP 框架大大降低的服務器編程的心智負擔，常見的服務端編程場景都有合適的解決方案。

這個項目的開發中，筆者借鑑了這個生產級別的開源 Raft 庫——龍舟的實現細節，如果對生產級的 Raft 實現感興趣，可以閱讀龍舟的代碼。

我們的實現大致代碼結構如下：

.                                                                                                                                                                                                                                                    
├── README.md                                                                                                                                                                                                                                        
├── Taskfile.yaml                                                                                                                                                                                                                                    
├── lib                                                                                                                                                                                                                                              
│   └── ex_raft                                                                                                                                                                                                                                      
│       ├── config.ex                                                                                                                                                                                                                                
│       ├── core               # 各個狀態下的處理邏輯                                                                                                                                                                                                                      
│       │   ├── candidate.ex                                                                                                                                                                                                                         
│       │   ├── common.ex                                                                                                                                                                                                                            
│       │   ├── follower.ex                                                                                                                                                                                                                          
│       │   ├── free.ex                                                                                                                                                                                                                              
│       │   ├── leader.ex                                                                                                                                                                                                                            
│       │   └── prevote.ex                                                                                                                                                                                                                           
│       ├── debug.ex                                                                                                                                                                                                                                 
│       ├── exception.ex                                                                                                                                                                                                                             
│       ├── guards.ex                                                                                                                                                                                                                                
│       ├── log_store        # 日誌存儲，本節暫時不用                                                                                                                                                                                                                 
│       │   ├── cub.ex                                                                                                                                                                                                                               
│       │   └── inmem.ex                                                                                                                                                                                                                             
│       ├── log_store.ex                                                                                                                                                                                                                             
│       ├── message_handlers      # 各個狀態下的消息處理                                                                                                                                                                                                                 
│       │   ├── candidate.ex                                                                                                                                                                                                                         
│       │   ├── follower.ex                                                                                                                                                                                                                          
│       │   ├── leader.ex                                                                                                                                                                                                                            
│       │   └── prevote.ex                                                                                                                                                                                                                           
│       ├── mock              # 日誌複製狀態機，本節暫時不用                                                                                                                                                                                                                       
│       │   └── statemachine.ex                                                                                                                                                                                                                      
│       ├── models              # 幾個分片常用的數據結構                                                                                                                                                                                                                     
│       │   ├── replica.ex                                                                                                                                                                                                                           
│       │   └── replica_state.ex                                                                                                                                                                                                                     
│       ├── pb                      # 消息的數據結構                                                                                                                                                                                                                 
│       │   ├── ex_raft.pb.ex                                                                                                                                                                                                                        
│       │   ├── ex_raft.proto                                                                                                                                                                                                                        
│       │   └── gen.sh                                                                                                                                                                                                                               
│       ├── remote                 # 節點間通信客戶端                                                                                                                                                                                                                  
│       │   ├── client.ex                                                                                                                                                                                                                            
│       │   └── erlang.ex                                                                                                                                                                                                                            
│       ├── remote.ex                                                                                                                                                                                                                                
│       ├── replica.ex            # 分片進程                                                                                                                                                                                                                    
│       ├── serialize.ex                                                                                                                                                                                                                             
│       ├── server.ex             # 節點間以及和客戶端通信的服務端                                                                                                                                                                                                                   
│       ├── statemachine.ex                                                                                                                                                                                                                          
│       ├── typespecs.ex                                                                                                                                                                                                                             
│       └── utils                     # 工具集                                                                                                                                                                                                               
│           ├── buffer.ex                                                                                                                                                                                                                            
│           └── uvaint.ex                                                                                                                                                                                                                            
├── mix.exs                                                                                                                                                                                                                                          
├── mix.lock                                                                                                                                                                                                                                         
├── test                                                                                                                                                                                                                                             
│   ├── ex_raft_test.exs                                                                                                                                                                                                                             
│   ├── log_store.exs                                                                                                                                                                                                                                
│   └── test_helper.exs                                                                                                                                                                                                                              
└── tmp

四 選主實現

這一節中，我們暫時不考慮日誌複製的細節，專注實現選主邏輯。

從論文 In Search of an Understandable Consensus Algorithm（《尋找一種易於理解的一致性算法（擴展版）》，以下稱爲 “論文”）中，可以得知：“選主” 這個過程本身也是個狀態機（注意區分此處的狀態機和日誌複製狀態機不是一回事）：

在典型的穩態場景中，集羣中的一臺服務器是 Leader，而所有其他服務器都是 Follower。

雖然我們希望事情永遠這樣保持下去，但 Raft 的目標是容錯，所以我們會討論一些故障場景：例如其中一些服務器 crash、網絡分區等。

爲了實現選主的邏輯，我們要引入一些概念：

任期（Term）

論文中的解釋：任期（Term）是分佈式系統中共識算法中的一個關鍵概念，尤其是在領導者選舉（Leader Election）和共識達成過程中。任期是時間上的一個劃分，用於組織和同步分佈式系統中的事件，確保系統中的所有節點能夠在一個明確的時間段內就某個領導者或一系列決策達成一致。

簡單來說，任期標明瞭 Leader 的服役階段。

任期這個概念有以下特性：

• 任期越大，話語權越大：本地任期較小的總是服從任期更高的消息來源。

• 每次選舉，任期都會 + 1：確保不會多個選舉過程計票混亂。

• 一山不容二虎：同個任期內最多隻有一個 Leader 被選出。

選舉計時（Election Timer）

每個 Follower 都會在本地維持一個選舉計時器，在選舉計時器到期前，如果沒有收到 Leader 的日誌或者心跳，Follower 就會認爲 Leader 出了意外，那麼就會開始發起選舉。這裏有幾個常見問題：

Q：會不會有多個 Follower 同時成爲候選人？

A：會的，爲了避免這種情況出現，我們給選舉計時器添加一些隨機區間，這是 Raft 簡單的原因之一。Raft 使用這種隨機化來降低多個 Follower 同時進行選舉的機會。但是即使他們同時成爲候選人，任何給定任期內也只有一個人會被選爲領導人。在極少數情況下，如果選票分裂，沒有候選人能獲勝，將進行新的選舉。

Q：如果 Follower 與集羣斷開連接（分區）怎麼辦？

A：這就是網絡分區的隱蔽性，因爲 Follower 無法區分誰被分區了。這種情況 Follower 會開始選舉。但這種情況下 Follower 不會得到任何選票。這個節點可能會在候選狀態中持續自旋（每隔一段時間重新啓動一個新的選舉），直到重新連接到集羣。

消息類型

Raft 中兩個節點的通信類型多種多樣，不過涉及到選主的部分較爲簡單，只有下圖添加註釋這 4 種消息類型：

狀態機框架

從上述介紹中可以看出，選主這個過程涉及多個狀態的輪轉，每個狀態下對不同消息做不同的反應，所以非常自然我們選擇狀態機的方式實現。

而 Erlang OTP 有個自帶的狀態機實現框架：gen_statem，有了這個利器，可以寫出很清晰的狀態機邏輯：

選舉計時

我們這裏的計時方式也是借鑑了 “龍舟” 的風格，即維護一個單位時間很小（1s）的本地時鐘，其他超時事件全部用該時鐘的整數倍來計算，這種方式配置和編碼起來較爲簡單。

我們在代碼中需要判斷 localTick 的次數超出了 electionTimeout，即可將自身狀態轉變爲 Candidate 開啓選主。

拉票

開啓投票前 Candidate 需要做這幾件事：

• 將自身的 Term+1；

• 投自己一票。

完成這些後，就將攜帶新 Term 的消息發給所有其他的節點。

需要注意的是在這個 Raft 實現中，消息發送全部採用單向流，消息的發送和處理是隔離開的。

具體實現中則是使用了 Erlang 自帶的 RPC，簡化了自己開發通信協議的成本。

處理拉票消息

由於 Raft 中任期概念的設計，其他角色在接收到拉票消息時需要考慮以下幾種情況：

• request_vote 消息攜帶的 Term 大於本地 Term

這種情況較爲簡單，做 Follower 即可。

需要注意的是，在遇到較大 Term 而轉換自身狀態的情況下，不用重置選舉計時器，原因在註釋中寫明瞭：

Not to reset the electionTick value to avoid the risk of having the local node not being to campaign at all. if the local node generates the tick much slower than other nodes (e.g. bad config, hardware clock issue, bad scheduling, overloaded etc), it may lose the chance to ever start a campaign unless we keep its electionTick value here.

簡而言之就是防止某個節點一直處於 Follower 角色，失去選舉的機會。

代碼中 cast_pipein 這個函數是指在變更狀態爲 Follower 後，繼續處理這個 request_vote 消息。

• request_vote 消息攜帶的 Term 小於本地 Term

這種情況，直接丟掉消息就行，任期小的消息在 Raft 算法中是不用處理掉的。

• request_vote 消息攜帶的 Term 等於本地 Term

這種情況就是在情況 1 轉變本地 Term 的後續，當任期一致時，投不投票也有講究。

Raft 算法中規定，如下情況可以投贊成票：

• 這個任期中當前節點誰都沒投過，這個消息來源第一個來拉票的，那就投給消息來源節點；

• 這個任期中當前節點投過了，而且我投的就是同個節點，那就不介意再投一次。

計票

Candidate 在散出 request_vote 的消息後，會開始等待其他節點的回執，這時候有 3 種情況：

• 收到了更高 Term 的心跳或者其他消息

這種情況說明集羣中已經存在一個更高任期的節點，那也不需要繼續選舉了，直接默認該消息來源節點爲 Leader。這裏和上文中處理更高 Term 的 request_vote 消息類似。

• 收到了半數以上的同意選票

大部分節點同意了當前的選舉要求，那該節點就成爲這個任期的合法 Leader：

• 在下個選舉週期到來前還沒收到半數選票

Raft 算法不會給 Candidate 無限的計票窗口，如果一直沒有收到足夠的選票，就清零計票，重置 Term+1，再次發起選舉，重複上述的過程，直到有個合法的 Leader 誕生。

接着上面網絡分區的場景討論，相信許多 Raft 系統的維護人員會發現，如果某個離羣的節點在重新迴歸後會立即成爲 Leader，就是這個原因，離羣的節點在不停的自旋選舉過程中將自己的 Term 抬高了很多，一但回到集羣就會因爲 Term 優勢成爲 Leader。爲了解決這個問題，Raft 有個 prevote 的補丁，這裏暫不展開討論。

五 Leader 的工作

當 Candidate 成功成爲 Leader 後，就需要承擔 Leader 的責任。在 Raft 算法中，Leader 需要持續的向 Follower 發送心跳消息表明自己的存在。

Follower 收到心跳後，就可以重置自己的選舉計時，起碼在這個選舉週期內，集羣中有個 Leader 了，不用開啓選舉。

Leader 收到心跳回執後，需要標記下 Follower 的狀態，這個狀態在集羣可用性處理和後續的日誌複製中有大用。

六 日誌複製

上面的概念介紹中我們已經闡述過，Raft 本質就是多個副本的日誌數據達成一致的解決方案。 我們已經實現了選主能力，但是尚未涉及到日誌的部分。

接下來，我們將爲選主集羣添加日誌複製能力。爲了實現這個目標，我們需要一些新的數據結構和接口協議，同時也會對選主部分邏輯做增強的安全檢查處理。

從客戶端行爲開始

Raft 集羣的客戶端會和集羣產生交互，而交互的具體內容則是一個個具體的指令（Command）。例如一個 Raft 架構的 KVDB，客戶端會向集羣發送類似 PUT foo bar 的寫請求或者是 GET foo 的讀請求，這裏的請求都可以算作指令的範疇。

Raft 集羣在接收到客戶端的指令後，根據論文第 5.3 節，會做如下的動作：

• 如果當前節點不是 Leader，則會把 Command 轉發至 Leader；

• Leader 接收到指令後會先寫入本地的日誌倉庫，然後向所有 Follower 發送日誌複製 (AppendEntries， 本實現中叫 Replicate) 請求；

• 一旦 Leader 確認該 Command 已充分複製（即集羣半數以上節點承認它們的日誌倉庫中成功複製了該 Command ），該 Command 就會被 commit；

• Leader 會更新它的 commit 水位，在 Raft 中 commit 的日誌即被認爲是安全的日誌，Leader 會在隨後的心跳或者日誌複製請求中攜帶 commit 水位，Follower 在收到心跳後更新本地 commit 水位；

• 各個節點會選擇自己覺得合適的時機將已經 commit 的日誌 apply 至狀態機，這裏時機的選擇會很大影響 Raft 實現的吞吐和 RT。

這裏是論文中提供的日誌複製的簡單例子：

按照論文的論述，這種日誌複製的機制有 2 個特點：

1. 如果在不同的日誌中的兩個條目擁有相同的索引和任期號，那麼他們存儲了相同的指令。

2. 如果在不同的日誌中的兩個條目擁有相同的索引和任期號，那麼他們之前的所有日誌塊也全部相同。

簡單來說，如果 2 個節點中某個日誌 Entry 的 index 和 Term 一樣，那麼從集羣啓動到日誌記錄的當下，集羣中所有節點的狀態是完全一致的。

這 2 個特點在論文中被定義爲 “日誌匹配特性”，由這個特性保證了 “集羣狀態可預測性”。

數據結構

爲了實現日誌複製功能，我們需要擴展一下數據結構。

Entry

Entry 即一個個日誌塊，每個 Entry 會攜帶一個 Command，爲了讓 Command 可以在集羣中傳播，Command 會序列化爲一個 binary。

這裏的日誌類型中本篇會新增用到以下兩個，其餘的暫時用不上：

• append_entries/append_entries_resp: 日誌複製 / 日誌複製回執

• propose：提案

Message

Message 結構中，我們擴展瞭如下字段：

• log_term/log_index：當前節點日誌複製的最新進度；

• commit: 已提交的日誌水位；

• hint：日誌複製異常時攜帶的水位信息（這種情況一般會觸發日誌的覆蓋）。

其他字段暫時用不到。

日誌倉庫

爲了實現日誌複製，每個節點都需要維護一個自己的日誌倉庫用於存儲 Raft 的 Entry，我們爲日誌倉庫抽象瞭如下的 API：

這裏同樣採取 API 和實現分離的設計方式，具體的實現是可拔插的。（按照 Elixir 的編程習慣，這裏用 Protocol 的方式來定義更優雅）

在我們這個版本的實現中，我們採用了 Cubdb 作爲日誌倉庫的實現基礎。(Cubdb 是一個以 B + 樹文件存儲爲基礎的嵌入式 KVDB)。具體的實現方式可以參考代碼。使用這個存儲主要是爲了簡單考慮，如果考慮性能的話可以模仿龍舟的方式使用 wal 和 memcache 結合的方式，大大提升日誌存儲的吞吐性能。

日誌複製分步實現

發起提案

這裏提案（Propose）即客戶端對 Raft 集羣發起的指令（Raft 中讀指令要比寫指令複雜的多，讀指令涉及到一致性相關討論，感興趣的可以搜索 Raft 中 read_index 的內容）。

接下來就是根據當前節點的不同角色來判斷：

• 如果當前節點是 Candidate: 可以直接拒絕這個提案，畢竟集羣都沒 Ready。

• 如果節點爲 Follower: 就把提案轉發到 Leader。

• 如果節點爲 Leader：進入提案處理流程，本實現中就是向本地節點發一條 propose 處理消息，這麼做是爲了複用 Term 異常處理等邏輯。

leader 複製提案

Leader 在接收到 propose 後做如下動作：

• 從 propose 中提取需要複製的 Entries；

• 將 Entries 添加至本地日誌倉庫；

• 維護本地的日誌水位；

• 如果日誌複製前後日誌水位發生變化，說明有新日誌，就會開啓日誌複製廣播。

Leader 廣播日誌複製消息

這一過程比較簡單，不過需要注意的是 Leader 會維護每個 Follower 的複製水位，這個水位是通過日誌複製和心跳共同維護的。

日誌複製會從每個 Follower 的複製水位開始，直到 Leader 的最新日誌或者最大複製體積。

發送的日誌複製請求會攜帶 Leader 記錄的複製水位 index 和水位對應的 Term，這倆數據是非常重要的，Follower 會根據這兩個標定來檢查日誌是否安全。

Follower 處理日誌複製請求

Follower 在接到日誌複製消息後有如下情形：

• 消息中日誌複製起點 log_index 小於 Follower 本地已提交水位 (commit index)

這種情形說明 Leader 的複製水位已經落後太多，沒必要做更多的動作，只需要回覆 Leader 最新的 commit 水位即可。

• 消息中日誌複製起點 log_index 小於等於 Follower 的最新日誌進度

這種情況說明 Leader 發來的日誌可能與 Follower 的日誌有部分重疊，這個時候要非常謹慎，需要仔細對比 Leader 的日誌和本地日誌是否匹配。

這裏的日誌匹配的過程分爲這麼幾步：

• 判斷日誌複製起點的任期和本地是否一致，如果不一致立即拒絕複製；

• 如果任期一致，從消息中找到第一個與本地日誌塊不一致的日誌 Entry 即爲匹配起點，不一致指的是任期和 index 任意一個不一致；

• 當找到匹配起點後，後續所有日誌都是用 Leader 的日誌覆蓋本地。

爲何需要在日誌複製時做這麼嚴格的任期檢查呢？這個問題先保留，後面再細緻討論。

• 日誌複製起點大於 Follower 的最新日誌進度

這種情況就比較簡單了，日誌都跳號了，肯定不能接受，直接回絕即可。

Leader 處理複製回執

Leader 在接收了 Follower 的日誌複製回執後會有如下情形：

• 複製成功

這種爲正常情況，Leader 會更新 Follower 的水位，並且發起一次 commit 的嘗試。

commit 的請求按照論文，必須選擇至少半數複製成功的安全水位。

這裏取安全水位的做法參考了龍舟的技巧，每次收到回執後將所有節點的 match 水位排序後取中位數即爲半數同意的安全水位，非常巧妙。

值得注意的是，在 commit 之前我們還特地做了一次 Term 的檢查工作，這裏是 Raft 的安全性檢查，後文中會詳細討論。

• 複製失敗

異常情況下，按照論文的描述，Leader 不用做日誌回滾，只需要調整複製的起點水位即可。複製的起點水位取本地記錄的 match 水位和 Follower 返回的合理水位中的較小值（重複了沒有問題，不連續纔是大問題）。

如果這個過程中 Follower 的日誌已經髒了，這個安全水位開始的日誌可以覆蓋糾正 Follower 的日誌。

日誌複製安全性討論

在上節的分步實現中，我們多次做了日誌的任期檢查：

• Follower 在接收到日誌複製消息後，會對比複製消息的 Term 和本地日誌 Term 是否一致；

• Leader 在收到日誌複製成功回執後 commit 之前，會校驗 commit 水位的 Term 和當前 Term 是否一致（即不允許跨任期提交）；

爲什麼 Raft 需要不厭其煩地做 Term 和 index 的檢查呢？

在 Raft 論文中有如下論述：

在正常的操作中，Leader 和 Follower 的日誌保持一致性，所以日誌複製 RPC 的一致性檢查從來不會失敗。

然而，Leader 意外崩潰的情況會使得日誌處於不一致的狀態（老的 Leader 可能還沒有完全複製所有的日誌塊）。這種不一致問題會在 Leader 和 Follower 的一系列崩潰下加劇。

下圖展示了 Follower 的日誌可能和新 Leader 不同。Follower 可能會丟失一些在新的 Leader 中存在的日誌塊，也可能擁有一些新 Leader 沒有的日誌塊，或者兩者都發生。丟失或者多出日誌塊可能會持續多個任期。

當一個 Leader 成功當選時，Follower 可能是任何情況（a-f）。每一個 Box 表示是一個 Entry；裏面的數字表示任期號。Follower 可能會缺少一些 Entries（a-b），可能會有一些未被提交的 Entries（c-d），或者兩種情況都存在（e-f）。

例如，場景 f 可能會這樣發生，某節點在任期 2 的時候是 Leader，已附加了一些 Entries 到自己的日誌倉庫中，但在提交之前就崩潰了；很快這個機器就被重啓了，在任期 3 重新被選爲 Leader，並且又增加了一些 Entries 到自己的日誌倉庫中；在任期 2 和任期 3 的日誌被提交之前，這個節點又宕機了，並且在接下來的幾個任期裏一直處於宕機狀態。

在 Raft 算法中，Leader 是通過強制 Follower 直接複製自己的日誌來處理不一致問題的。這意味着在 Follower 中的衝突的日誌塊會被 Leader 的日誌覆蓋。

要使得 Follower 的日誌進入和自身一致的狀態，Leader 必須找到最後兩者達成一致的地方，然後刪除 Follower 從那個點之後的所有日誌塊（水位重置），併發送自己在水位之後的日誌給 Follower。

所有的這些操作都在進行日誌複製 RPC 的一致性檢查時完成。Leader 針對每一個 Follower 維護了一個 nextIndex，這表示下一個需要發送給 Follower 的日誌塊的索引。當一個 Leader 剛剛被選出的時候，它初始化所有的 nextIndex 值爲自己的最後一條日誌的 index 加 1（圖中的 11）。

如果一個 Follower 的日誌和 Leader 不一致，那麼在下一次的日誌複製 RPC 時的一致性檢查就會失敗。在被 Follower 拒絕之後，Leader 就會減小 nextIndex 值並進行重試。最終 nextIndex 會在某個位置使得 Leader 和 Follower 的日誌達成一致。當這種情況發生，日誌複製 RPC 就會成功，這時就會把 Follower 衝突的日誌塊全部刪除並且加上 Leader 的日誌。一旦附加日誌 RPC 成功，那麼 Follower 的日誌就會和 Leader 保持一致，並且在接下來的任期裏一直繼續保持。

通過這種機制，Leader 在獲得權力的時候就不需要任何特殊的操作來恢復一致性。他只需要進行正常的操作，然後日誌就能在日誌複製 RPC——日誌複製回覆處理這一過程中自動趨於一致。Leader 從來不會覆蓋或者刪除自己的日誌。

Rethink 集羣選主

在上面的篇幅中，我們討論過集羣選主的過程，一個節點只要拿到集羣半數以上的 request_vote 的成功回執即可成爲 Leader，而且投票的原則非常簡單，只要這個任期我沒投過票或者我投過相同的節點即可贊成投票。

不過在添加日誌複製後這裏會出現一個小問題，例如在下圖中：

如果 f 節點發起選舉並得到了大多數成員認可，那麼集羣大部分節點就會面臨日誌回退，已經 “安全” 的日誌都變得不再安全，這不符合 Raft 的設計初衷，所以我們需要在投票時添加一個機制防止類似 f 節點這類比較 “舊” 的節點當選爲 Leader。

論文中有如下論述：

Raft 使用投票的方式來阻止一個 Candidate 贏得選舉，除非這個 Candidate 包含了所有已經提交的日誌塊。Candidate 爲了贏得選舉必須聯繫集羣中的大部分節點，這意味着每一個已經提交的日誌塊在這些服務器節點中肯定存在於至少一個節點上。如果 Candidate 的日誌至少和大多數的服務器節點一樣新（這個新的定義會在下面討論），那麼他一定持有了所有已經提交的日誌塊。請求投票（RequestVote）RPC 實現了這樣的限制：

RPC 中包含了 Candidate 的日誌信息，然後投票人會拒絕掉那些日誌沒有自己新的投票請求。

簡單來說就是：投票的時候如果拉票人的日誌沒我本地的新，那我就不能投票給你。

代碼實現：

• 發起投票：發起投票時 Candidate 需要在 request_vote 消息中攜帶本地的日誌任期和最新的日誌 index；

• 處理投票：其他節點處理 request_vote 消息時，需要檢查拉票消息的日誌是不是要比本地更新（日誌的 Term 大於本地或者同個 Term 下的日誌 index 大於本地）。

Leader 提交過往任期的日誌討論

在日誌複製的第 5 步中，Leader 獲取了半數以上的安全水位執行提交，不過提交前判斷了是否與當前任期一致，如果出現跨任期的情況，就會暫緩這次提交，爲什麼需要這一步呢？

論文有如下論述：

對 Leader 來說，只要當前任期的日誌被存儲到了大多數的服務器上，那麼這個日誌是可以被提交的。

如果 Leader 在提交日誌塊之前崩潰了，未來後續的 Leader 會繼續嘗試複製這條日誌塊。然而，一個 Leader 不能斷定一個之前任期裏的日誌塊被保存到大多數服務器上的時候就一定已經提交了。

下圖 8 展示了一種情況，一條已經被存儲到大多數節點上的老日誌塊，也依然有可能會被未來的 Leader 覆蓋掉。

如圖的時間序列展示了爲什麼 Leader 無法決定對老任期號的日誌塊進行提交。

(a) S1 是 Leader，部分 (Follower) 複製了 index=2 的日誌塊。

(b) S1 崩潰了，然後 S5 在任期 3 裏通過 S3、S4 和自己的選票贏得選舉，然後從客戶端接收了一條不一樣的日誌塊放在了索引 2 處。

(c) S5 又崩潰了；S1 重新啓動，選舉成功，開始複製日誌。這時來自任期 2 的那條日誌已經被複制到了集羣中的大多數機器上，但是還沒有被提交。

(d) 如果 S1 又崩潰了，S5 可以重新被選舉成功（通過來自 S2、S3 和 S4 的選票），然後覆蓋了他們在 index=2 處的日誌。

(e) 如果在崩潰之前，S1 把自己主導的新任期裏產生的日誌塊複製到了大多數機器上，那麼在後面任期裏面這些新的日誌塊就會被提交（因爲 S5 就不可能選舉成功）。這樣在同一時刻就同時保證了，前的所有老的日誌塊就會被提交。

簡單來說就是：過往任期的 “安全” 水位不一定是安全的，完全可能在 Leader 切換後被覆蓋，只有當前任期的 “安全” 水位是安全的，因爲其他日誌不一致的節點沒法在該任期內當選 Leader 只能被覆蓋。

七 用戶狀態機

前面的篇幅中我們已經介紹了 Raft 的 2 個核心部分：

• 集羣選主

• 日誌複製

但是現在的 Raft 集羣還沒法集成任何業務，因爲缺了和業務息息相關的一環——用戶狀態機。

接下來，我們將完成 Raft 拼圖的最後一塊，將業務能力集成，並嘗試用這個完全體的 Raft 製作一個分佈式的 KVDB。

什麼是用戶狀態機？

在 Raft 一致性算法中，業務狀態機（也稱爲應用狀態機或用戶狀態機）指的是實際執行業務邏輯的組件。當 Raft 處理完日誌條目（通常是客戶端發送的命令或操作請求）並通過選舉和日誌複製機制達成一致後，這些日誌條目會被提交給狀態機進行處理。

業務狀態機是確定性的，這意味着對於任何給定的輸入，它總是產生相同的結果，無論在哪個節點上運行。這個特性保證了，只要日誌條目的順序相同，所有節點上的狀態機經過相同的序列化輸入後會達到相同的狀態。因此，即使集羣中發生故障，只要有一個存活的節點，就可以通過複製其狀態來恢復其他節點，從而保持整個系統的狀態一致。

在 Raft 中，業務狀態機的職責包括：

• 執行命令：解析並執行由 Raft 提交的日誌條目中的命令或操作。

• 更新狀態：根據命令的結果更新內部狀態。

• 返回結果：將操作結果返回給客戶端或其他組件。

• 持久化狀態（optional）：將關鍵狀態寫入磁盤，防止數據丟失。

• 快照：定期創建狀態機的快照，減少日誌的大小，提高性能。

需要注意的是，Raft 算法本身不關心業務狀態機的具體實現細節，它只負責保證日誌條目的順序一致性和可用性。這使得 Raft 能夠適用於各種不同的分佈式系統和應用場景，例如數據庫、緩存、配置管理系統等。

定義狀態機行爲

參照上面的概念定義，我們可以定義用戶狀態機的行爲：

我們的狀態機約定有如下 API：

• 開啓、關閉狀態機；

• 執行 Raft 日誌中的業務命令；

• 對應用狀態機執行當前狀態的讀命令；

• 準備快照的檢查點，用於快照保存；

• 保存快照；

• 加載快照。

Raft 中是這麼定義 “快照” 的，後文有更加詳細的解釋：

快照（Snapshot）是一種重要的機制，用於減少系統的狀態大小並提高性能。在 Raft 中，快照的主要目的是記錄系統的一個完整狀態點，這樣就不需要從大量的日誌條目中重新計算整個狀態。

應用狀態機與 Raft 日誌的交互

應用狀態機提供的各個 API 是和 Raft 的日誌複製緊密相關的，我們分開討論每個 API 的使用時機。

執行 Raft 日誌中的業務命令

Raft 的狀態中保存了 2 個水位：

• commit_index: 一個上上篇文章中討論的複製的安全進度（集羣半數以上的複製水位）；

• last_applied: 已經複製到應用狀態機的水位。

當 commit_index>last_applied 且 commit_index 任期與當前任期一致（原因見上篇文章 Leader 提交過往任期的日誌討論）時，即可將（last_applied, commit_index] 這個範圍的日誌應用到應用狀態（即調用 update 方法）。

而執行 apply 的時機就很有講究了，各個 Raft 框架的實現各不相同，合理的 apply 時機和整個 Raft 框架的性能息息相關，開發者需要自己在框架的吞吐、提案的延遲中取一個合理的折中。我們這裏的實現較爲簡單，定時 apply 到 statemachine 即可。

保存快照

快照（Snapshot）是一個重要的優化機制，用於處理日誌文件不斷增長所帶來的存儲和性能問題。隨着系統的運行，Raft 需要記錄越來越多的狀態轉換指令，這些指令以日誌條目的形式存儲，以便在需要時能夠重放這些指令來重建系統狀態。

然而，隨着日誌的增長，以下問題逐漸顯現：

• 存儲成本上升：因爲需要保存更多的日誌條目。

• 性能下降：特別是在服務器重啓或新成員加入集羣時，需要重放大量的日誌條目來恢復狀態，這可能導致長時間的延遲。

爲了解決這些問題，Raft 引入了快照機制。快照是對系統當前狀態的一個完整拷貝，它包含了從系統啓動到快照生成時刻的所有狀態信息。一旦快照創建完成，它所代表的那一刻之前的所有日誌條目就可以被安全地刪除，因爲快照包含了那些日誌條目所能提供的所有信息。

以下是快照在 Raft 中的一些關鍵作用：

• 狀態壓縮：快照可以顯著減少存儲需求，因爲它取代了之前所有的日誌條目。

• 狀態恢復：當服務器重啓或者新節點加入集羣時，可以從最新的快照恢復狀態，而無需重放所有日誌條目。

• 日誌同步：如果某個節點的日誌與領導者不同步，領導者可以向該節點發送快照，幫助其快速更新至最新狀態。

快照的生成時機通常是根據預設的策略，比如日誌條目達到一定數量或存儲使用量超過閾值。

在 Raft 中，快照的生成和傳輸過程需要謹慎設計，以確保數據一致性和系統的穩定性。

在我們這個玩具實現中，就不實現複雜的自動快照了，實現一個手動快照入口即可。

快照的構成包括 2 個部分：

• Raft 集羣當前狀態：包括各個節點的 id、任期、保持快照時的最新 index 和集羣節點構成等，這部分我們稱之爲 snapshot_metadata。

• 用戶狀態機想要持久化的數據：這部分數據由業務自己實現管理。

Raft 無法知道用戶狀態機想要持久化的數據，所以在保存快照時，攜帶 snapshot_metadata 調用用戶狀態機的快照 API。這裏我們設計了很簡單的快照格式，用一個 4 字節的 header 保存 snapshot_meta 的長度，方便恢復的時候做長度切割。

我們的玩具實現中只是單純的存在當前節點磁盤，生產中可以根據實際的業務需要將快照存儲在三方存儲（例如 s3）中方便管理。

快照恢復

既然有快照保存，那就一定有快照恢復，快照恢復有以下幾種情形：

• 集羣節點重啓：需要加載本地快照恢復到最近的持久化進度，後續再從進度處重複日誌達到一致性；

• 新節點加入集羣：由於新節點沒有本地快照，需要從遠端拉取快照，可以從 Leader 處獲取也可以從單獨的快照服務中獲取。

第二種情形較爲複雜，我們就先不討論了，這裏只實現第一種情況：

快照恢復的過程就是快照製作的反過程，我們從存儲（磁盤）上讀出快照數據，parse 爲業務快照和 metadata，其中:

• metadata 可以用於恢復集羣成員、任期、最新 index 等數據；

• 業務快照則可以調用 statemachine 的 load_snapshot api 恢復業務數據。

八 編寫一個分佈式 KVDB

至此，我們已經介紹完了 Raft 中核心的概念，爲了更直觀的感受用 Raft 的功能，我們選擇一個很簡單的業務場景來驗證——KVDB。

我們的玩具 KVDB 將支持以下能力：

• 添加 kv 對，如果相同 key 就覆蓋；

• 刪除 kv 對；

• 讀某個 key 對應的 val。

狀態機實現

爲了實現這個 KVDB，我們首先按照業務狀態機的業務約定實現狀態機接口。

這裏的 kv 數據全部存儲在內存 map 中，update 和 read 方法即對該 map 的讀寫。

快照實現也非常簡單，將所有的 kv 對 dump 爲一個 json，快照加載的時候讀取這個 json 恢復所有 kv 即可。

完整的 Raft-base KVDB

有了這個狀態機，我們就可以將我們編寫的 Raft 框架和這個狀態機聯合起來，組成一個 Raft-kv。

我們簡單組織一下上層的 API：

• show：展示當前集羣結構；

• put：寫入一個 kv；

• delete：刪除一個 key；

• read：讀取一個 key；

• save_snapshot：快照落盤。

從代碼可知，這裏的寫入和刪除都是對 Raft 集羣發起一個提案，而讀則是採用的較爲簡單的 “髒讀” 策略，直接讀的本地內存（如果想要更爲嚴格的一致性，需要實現 Raft 提供的一致性讀 API）。

接下來就是激動人心的時刻，我們將把從選主到狀態機所有的代碼串聯起來，檢驗 Raft 是否能正常工作。

驗證

Raft 集羣組建

這裏我們在本地啓動 3 個 Erlang 進程，每個進程有個獨立的 node id 和 port，各個 node 通過 Erlang 虛擬機相互發現通信。

配置文件中，我們將這 3 個 node 組成一個 Raft 集羣。

從圖中的 show 命令執行結果可知，3 個節點成功組成了穩態的 Raft 集羣，節點 1 爲 Leader，2 和 3 爲 Follower。

讀寫作業

• 在 1 節點寫入 foo1:bar1；

• 在 2 和 3 節點讀取 foo1，均可以讀出結果 bar1；

• 在 2 節點刪除 foo1，在 1 節點和 3 節點均無法繼續讀出 foo1。

由結果可知，我們的寫入和刪除提案都被 3 個節點複製執行成功。

快照落盤與恢復

• 在 1 節點寫入 foo1:bar1 和 foo2:bar2 兩個 kv；

• 執行快照落盤操作，將一個 json 存入本地磁盤；

• 重啓該 node，該節點從 Leader 轉換爲 Follower；

• 讀取 foo1，得到結果 bar1；

• 讀取 foo2，得到結果 bar2；

由實驗結果可知，我們的快照製作和快照恢復功能生效了，節點可以從磁盤中恢復狀態和集羣達到一致性。

九 總結

本文深入探討了 Raft 日誌複製算法的核心概念和實現細節。從日誌複製狀態機的基礎，到 Leader、Follower、Candidate 的角色定義，我們逐步揭開了 Raft 算法的神祕面紗。我們選擇了 Elixir 作爲實現語言，展示了其在構建高效、可擴展的分佈式系統中的潛力。

通過分步實現日誌複製，我們瞭解瞭如何發起提案、Leader 如何複製提案以及 Follower 如何處理日誌複製請求。安全性討論讓我們認識到了在分佈式系統中保證數據一致性的重要性。此外，我們還探討了 Raft 算法在集羣選主和用戶狀態機中的常見問題和陷阱，以及如何通過定義狀態機行爲來執行業務命令。

在實踐層面，我們學習瞭如何編寫一個分佈式 KVDB，並驗證了其正確性。這包括了 Raft 集羣的組建、讀寫操作的執行、以及快照的落盤與恢復。這些實際操作不僅加深了我們對 Raft 算法的理解，也爲我們提供了寶貴的實踐經驗。

本文僅淺嘗輒止地瞭解了一下 Raft 的核心知識，製作了一個玩具的 Raft 實現，而生產級別的 Raft 框架需要考慮的問題更多了。感興趣的開發者可以在本文的基礎上進階思考一下這些問題：

• 如何實現一致性讀？

• 如何避免網絡分區的節點重新回到集羣立即成爲 Leader？

• 如何選擇日誌 commit 和 apply 的時機可以讓 Raft 框架獲得最理想的吞吐？

• 如何實現動態的節點增刪？

隨着分佈式理論的發展，業界也對 Raft 做了很多的擴展和升級，例如：

• 通過 Raft 集羣的分級並聯獲取更高的硬件資源利用率；

• 分拆日誌匹配的 job 爲一個無狀態的服務，增加 Leader 的水平日誌處理能力；

• 增加 Observer 角色（只複製不參與選主）橫向擴展集羣的讀能力。

更多奇思妙想可以參考 ACM 上的論文。

隨着技術的不斷進步，我們有理由相信 Raft 算法及其在分佈式系統中的應用將會更加廣泛。在未來，我們期待看到更多創新的實現和應用場景，以解決日益複雜的分佈式計算問題。讓我們拭目以待，共同見證分佈式技術的未來發展。

引用：

• https://engineering.linkedin.com/distributed-systems/log-what-every-software-engineer-should-know-about-real-time-datas-unifying

• https://zhuanlan.zhihu.com/p/618127949

• https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#%E5%AF%BB%E6%89%BE%E4%B8%80%E7%A7%8D%E6%98%93%E4%BA%8E%E7%90%86%E8%A7%A3%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7%E7%AE%97%E6%B3%95%E6%89%A9%E5%B1%95%E7%89%88

• https://github.com/lucaong/cubdb

• https://dl.acm.org/action/doSearch?AllField=raft

文 / 古月方塊

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/R2XXYFoR67VsiGwT6XM96A