#103 分散式系統的「開會」藝術 - 淺談共識演算法

 上一篇文章聊到了在沒有統一時鐘的分散式世界裡，如何利用 Lamport Timestamp 這樣的邏輯時鐘來替事件排出先後順序。知道了「順序」固然重要，但這只是第一步。在現實的分散式系統中，往往有一群機器需要協同工作，它們不僅要知道誰先誰後，更需要對「某件事」達成一致的看法。

想像一下，一個由五台伺服器組成的資料庫叢集。當一個使用者送出請求：「把我的帳戶餘額扣除 100 元，轉給小明」。這五台機器必須對這個操作達成共識：

• 這筆交易發生了嗎？
• 這筆交易發生在另一筆交易之前還是之後？
• 現在大家的餘額資料庫裡，最新的狀態是什麼？

如果其中一台機器認為轉帳成功了，而另一台認為失敗了，那整個系統就會陷入精神分裂般的混亂。

讓一群不可靠的機器（可能會當機、網路會延遲或斷線）對某個值達成一致的過程，就是著名的「共識問題」(Consensus Problem)。而解決這個問題的方法，就稱為「共識演算法」。共識演算法是分散式系統中最困難、也最迷人的主題之一。這篇文章就用最淺顯的方式來揭開它的內容。

理論上的絕望：「兩將軍問題」

在介紹電腦之間怎麼達成共識之前，我們得先了解為什麼這件事這麼難。電腦科學家喜歡用一個經典的思想實驗來說明這個困境，稱為「兩將軍問題」(Two Generals' Problem)。

想像這樣一個場景： 有兩支友軍部隊（將軍 A 和將軍 B）分別駐紮在兩座山頭上。山谷中間有一支強大的敵軍。兩位將軍都知道，如果單獨進攻，絕對會被打敗；只有兩支軍隊在「同時」發起進攻，才能勝利。現在問題來了，他們唯一的溝通方式是派遣傳令兵穿越被敵軍佔領的山谷。傳令兵在途中很可能被敵軍截獲而犧牲。

• 場景一：將軍 A 決定明天早上 8 點進攻。他派出傳令兵告訴將軍 B：「明天 8 點進攻，收到請回覆。」
• 困難點：如果傳令兵半路被抓了，將軍 B 沒收到訊息，那麼將軍 A 明天進攻就會變成自殺任務。所以將軍 A 必須等待將軍 B 的確認回覆。
• 場景二：傳令兵成功到達。將軍 B 同意了，並派出傳令兵回覆：「我同意明天 8 點進攻，收到請回覆確認你知道我同意了。」
• 困難點：現在輪到將軍 B 擔心了。如果他的回信傳令兵被抓了怎麼辦？將軍 A 沒收到確認，可能就不敢進攻。所以將軍 B 不敢貿然行動，除非他確定將軍 A 收到了他的確認。

你發現問題了嗎？這將導致無窮無盡的「確認的確認」。A 需要確認 B 收到了，B 需要確認 A 收到了 B 的確認，A 又要確認 B 收到了 A 的確認的確認等等等。只要最後一條訊息有丟失的風險，雙方就永遠無法達成「百分之百確定」的共識。這就是分散式系統面臨的根本困境：在一個不可靠的通訊網路上，要達成完美的共識在理論上是不可能的。這聽起來很令人失望，對吧？但工程師的工作就是在不完美的世界裡尋找可行的方案。我們不需要「完美的」共識，我們只需要「足夠好、能容忍一定程度故障」的共識。你可能還聽過所謂的「拜占庭將軍問題」，這是兩將軍問題的延伸，會在未來的文章裡討論。

複製狀態機 (Replicated State Machine)

上面的內容說明了在不可靠網路下無法達成完美共識，那現實中的 Google、Facebook 是怎麼運作的？它們的資料庫為什麼不會亂掉？因為我們把問題轉換了一下。我們不追求讓所有機器在同一瞬間達成共識，我們追求的是讓所有機器「按照相同的順序，執行相同的指令」。這就是「複製狀態機」(Replicated State Machine) 的概念。

如果多台機器從相同的初始狀態開始，並且嚴格按照相同的順序接收並執行了一系列指令，那麼它們最終一定會停留在相同的狀態。

這聽起來是不是很耳熟？沒錯，這又回到了我們上一篇談的「順序」問題。在實務上，共識演算法通常不是用來決定一個簡單的值（例如 "X=5"），而是用來決定「操作日誌 (Log) 的順序」。

想像一個資料庫叢集，它們的共識過程是這樣的：

• 所有機器都同意：日誌的第 1 條指令是「將 A 帳戶設為 100 元」。
• 所有機器都同意：日誌的第 2 條指令是「將 B 帳戶設為 50 元」。
• 所有機器都同意：日誌的第 3 條指令是「A 轉帳 10 元給 B」。

只要每台機器對這個「日誌的順序」達成共識，那麼每台機器各自去執行這些指令後，大家的資料庫狀態就會是一模一樣的（A 剩下 90 元，B 變成 60 元）。所以，現代分散式系統中的共識演算法，其核心任務就是：如何在一個可能有人出錯的情況下，讓大家對這份「操作日誌」的內容和順序達成一致。

實用的解決方案：Raft 演算法

在很長一段時間裡，共識演算法的代名詞是 Paxos。Paxos 功能強大，被認為是唯一經過數學嚴格證明的演算法。但它有一個巨大的缺點：太難懂了。難懂到連許多頂尖的教授和工程師都要花很多時間才能參透，更別提正確實作了，當然也包括當年的我，看了一次就不想再看。

為了拯救被 Paxos 折磨的眾生，史丹佛大學的研究人員在 2014 年提出了 Raft 演算法．可參考 https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14。Raft 的設計目標非常明確：要讓人容易理解 (Understandability)，同時在功能和效能上不輸給 Paxos。現在許多主流的開源軟體（如 Kubernetes 使用的 etcd）都採用了 Raft。

Raft 如何運作？選個班長來主導。

Raft 為了簡化問題，採取了一種強勢的領導風格。你可以把它想像成一個班級在決定班會記錄：

• 選班長 (Leader Election)： 在任何時刻，整個叢集（班級）裡只能有一個「領導者」(Leader)。其他的機器都是「跟隨者」(Follower)。 如果領導者當機了（班長轉學了），剩下的跟隨者會發起投票，選出一個新的領導者。Raft 透過巧妙的隨機逾時機制 (Randomized Timeout)，確保大家能快速、平穩地選出新領導者，避免大家同時搶著當班長的僵局。
• 班長說了算 (Log Replication)： 一旦選出領導者，所有的決策都由它負責。 當外界（客戶端）發來一個請求（例如「存入 100 元」），這個請求會直接交給領導者。 領導者會先把這個請求寫入自己的「日誌草稿」中，然後像發考卷一樣，把這條日誌複製並發送給所有的跟隨者，並說：「嘿，把這條加到你們的日誌裡！」
• 達成多數共識 (Quorum)： 跟隨者收到日誌後，會存下來並回覆領導者：「報告班長，我收到了！」 關鍵來了：領導者不需要等待所有人都回覆。只要收到超過半數 (Majority / Quorum) 的節點回覆說「收到了」，領導者就會認為這條日誌已經安全了，可以正式執行（Commit），並回覆客戶端「操作成功」。

選班長的過程也是很精彩，也有相對應的數個演算法，未來文章可以再討論。最簡單的應用實例就是 Windows 作業系統裡的 "網路芳鄰" （這是很久以前的名字了）。

這種「少數服從多數」的機制是分散式系統容錯的關鍵。假設你有 5 台機器，你只需要 3 台機器正常運作，整個系統就能達成共識並繼續對外服務。這允許你有 2 台機器同時壞掉。這種類似於 "中央集權式" 的運作方式確實省了許多麻煩，並且也清楚好懂好實作。