本章摘要： 全面檢視分散式環境中的三大不確定性來源——網路的無界延遲、時鐘的漂移與同步限制、程序的任意暫停。說明部分失敗是分散式系統的本質特徵，並介紹 fencing tokens 與系統模型等容錯工具。

本章將悲觀主義推到極致，全面檢視分散式系統中可能出錯的一切。在單機環境中，程式要麼正常運作，要麼完全崩潰；但在分散式系統中，部分失敗（partial failure）才是常態。理解這些問題是設計可靠分散式系統的第一步。

故障與部分失敗#

在單機上撰寫程式時，行為通常是確定性的（deterministic）：相同的操作總是產生相同的結果。若硬體出問題，後果通常是整台機器完全失效（kernel panic、藍白當機畫面），而非產出錯誤的結果。這是刻意的設計選擇——電腦隱藏了底層物理世界的模糊性，呈現出數學般精確的理想化模型。

然而，當軟體運行在多台機器上、透過網路連接時，情況徹底改變。系統的某些部分可能以不可預測的方式故障，而其他部分仍正常運作——這就是部分失敗。部分失敗的難點在於它是非確定性的（nondeterministic）：同樣的操作有時成功、有時失敗，你甚至無法確定某個操作是否成功，因為訊息在網路上的傳輸時間也是不確定的。

雲端運算 vs 超級電腦#

大規模計算系統的建構哲學存在一個光譜：

  • 高效能運算（HPC）：超級電腦使用數千個 CPU 進行科學計算。故障處理策略是定期將狀態 checkpoint 到持久儲存；若任何節點失敗，就停止整個叢集、修復後從 checkpoint 重啟。本質上是將部分失敗升級為全面失敗，更接近單機的運作模式。
  • 雲端運算：多租戶資料中心、commodity 硬體、IP 網路、彈性資源分配。必須隨時服務使用者，不能因為某個節點故障就停機維修。
  • 傳統企業資料中心：介於兩者之間。

本書聚焦的網路服務與超級電腦有幾個關鍵差異：

  • 網路服務必須隨時在線，無法像批次任務那樣暫停重啟
  • 雲端使用 commodity 硬體，故障率較高但成本低廉
  • 資料中心網路基於 IP/Ethernet，延遲不可預測
  • 系統規模越大，某個元件故障的機率越高——在數千節點中，總有什麼東西是壞的
  • 容錯能力允許滾動升級，逐一重啟節點而不中斷服務
  • 跨地理分佈的部署必須透過不可靠的公共網際網路通訊

如果我們想讓分散式系統正常運作，就必須接受部分失敗的可能性，並在軟體中建構容錯機制。即使是小型系統，也應該認真考慮部分失敗的處理方式——懷疑、悲觀與偏執在分散式系統中是值得的。

從不可靠的元件建構可靠的系統是計算領域的老概念：錯誤校正碼可以在有雜訊的通道上正確傳輸資料，TCP 在不可靠的 IP 之上提供可靠的傳輸層。系統可以比其組成元件更可靠，但這是有極限的。

不可靠的網路#

本書關注的是 shared-nothing 架構：機器之間唯一的通訊方式就是網路。網際網路和資料中心內部網路幾乎都是非同步封包網路（asynchronous packet networks）——傳送一個封包時，網路不保證它何時到達、甚至是否到達。

當你發送請求並期待回應時，可能出錯的地方包括：

  • 請求在網路上遺失（例如網路線被拔掉）
  • 請求排隊等待，稍後才送達（網路或接收方過載）
  • 遠端節點已故障（當機或斷電）
  • 遠端節點暫時停止回應（例如長時間 GC 暫停），稍後恢復
  • 遠端已處理請求，但回應在網路上遺失
  • 遠端已處理請求，但回應被延遲

Figure 8-1: 無法分辨請求遺失、遠端節點故障或回應遺失

發送方甚至無法確認封包是否送達——唯一的確認方式是收到回應，而回應本身也可能遺失或延遲。在非同步網路中，這些情況無法區分：你唯一知道的是還沒收到回應。通常的處理方式是設定超時（timeout）：等待一段時間後，假設回應不會來了。

網路故障的實務情況#

網路問題出乎意料地常見，即使在精心管理的資料中心內也是如此。研究顯示，一個中型資料中心每月約發生 12 次網路故障，其中一半斷開單台機器，另一半斷開整個機架。增加冗餘網路設備的效果不如預期，因為它無法防範人為錯誤（如錯誤設定的交換器）。

網路分區（network partition，又稱 netsplit）是指網路的一部分與其餘部分被切斷。即使網路故障在你的環境中很罕見，軟體仍必須能夠處理它們。若錯誤處理未被定義和測試，可能發生任意的壞事：叢集可能永久死鎖，甚至刪除所有資料。

偵測故障#

許多系統需要自動偵測故障節點（例如負載平衡器需要移除死掉的節點，單主複製需要提升 follower）。但網路的不確定性使這件事很困難。某些情況下可以獲得明確的回饋：

  • 節點程式崩潰但 OS 仍在運行：OS 會傳送 RST 或 FIN 封包拒絕 TCP 連線
  • 節點程式崩潰：可透過腳本通知其他節點
  • 路由器確定 IP 不可達：回覆 ICMP Destination Unreachable

但你不能依賴這些回饋。即使 TCP 確認封包已送達，應用程式可能在處理前就崩潰了。最終，你通常只能等待超時，然後宣告節點死亡。

超時與無界延遲#

超時該設多長？沒有簡單的答案。

  • 長超時：等待時間長，故障偵測慢
  • 短超時：偵測快，但更容易誤判——將暫時變慢的節點宣告為死亡

過早宣告節點死亡會造成問題：該節點的工作必須移轉到其他節點，增加其負載。若系統本已過載，這可能觸發級聯失敗（cascading failure）——極端情況下，所有節點互相宣告對方死亡。

在理想狀況下，若網路保證最大延遲 d，節點保證在時間 r 內處理請求，那麼 2d + r 就是合理的超時。但現實中的非同步網路具有無界延遲（unbounded delays），多數伺服器也無法保證最大處理時間。

網路壅塞與排隊#

封包延遲的變異性主要來自排隊（queueing）：

  • 多個節點同時傳送封包到同一目標，交換器必須排隊，隊列滿時封包被丟棄
  • 目標機器的 CPU 忙碌時，OS 將請求排隊等待應用程式處理
  • 虛擬化環境中，VM 被暫停數十毫秒讓其他 VM 使用 CPU，期間無法消費網路資料
  • TCP 流量控制（flow control / backpressure）在傳送端增加額外的排隊

Figure 8-2: 多機器同時傳送流量導致交換器佇列過載

在公有雲和多租戶資料中心，資源由眾多客戶共享。吵雜的鄰居（noisy neighbor）大量使用資源時，網路延遲可能劇烈波動。

與其使用固定的超時值，更好的做法是讓系統持續量測回應時間及其變異性（jitter），並自動調整超時。Phi Accrual failure detector 就是這種方法，被 Akka 和 Cassandra 採用。TCP 的重傳超時也以類似方式運作。

同步 vs 非同步網路#

為什麼不能在硬體層級解決網路可靠性問題？比較一下傳統電話網路：它建立電路（circuit），為通話預留固定頻寬，通話期間保證恆定的低延遲。這是同步網路——延遲有上界（bounded delay）。

資料中心和網際網路使用的是封包交換（packet switching）而非電路交換，因為它最適合突發性流量（bursty traffic）。網頁請求、email、檔案傳輸不需要固定頻寬，只需要盡快完成。封包交換透過動態共享頻寬，最大化線路利用率——代價就是排隊和無界延遲。

延遲的不可預測性不是自然定律，而是成本與效益的取捨。靜態資源分配（如電路交換）可以提供延遲保證，但利用率低、成本高。動態資源分配（如封包交換）利用率高、成本低，但延遲不可預測。目前的多租戶資料中心和公有雲並未啟用 QoS，因此我們必須假設壅塞、排隊和無界延遲會發生。

不可靠的時鐘#

時鐘在分散式系統中用途廣泛：判斷超時、量測回應時間、記錄事件時間戳等。但在分散式環境中，時間是棘手的問題。通訊不是瞬時的，且每台機器都有自己的硬體時鐘（石英晶體振盪器），精確度各不相同。雖然可以透過 NTP（Network Time Protocol）同步時鐘，但同步本身也有其限制。

日曆時鐘 vs 單調時鐘#

現代電腦至少有兩種時鐘，用途不同：

日曆時鐘（Time-of-day clock）：

  • 回傳日期和時間（wall-clock time），例如 Linux 的 clock_gettime(CLOCK_REALTIME) 或 Java 的 System.currentTimeMillis()
  • 通常與 NTP 同步，理論上不同機器的時間戳意義相同
  • 但可能被 NTP 強制重設而向後跳躍，且常忽略閏秒
  • 不適合量測經過的時間

單調時鐘（Monotonic clock）：

  • 適合量測時間間隔，例如 Linux 的 clock_gettime(CLOCK_MONOTONIC) 或 Java 的 System.nanoTime()
  • 保證只會向前移動，絕不會向後跳
  • 絕對值無意義（可能是開機後的奈秒數），不同機器之間的值無法比較
  • NTP 可以調整單調時鐘前進的速率（slewing），但不會讓它跳躍
  • 精確度通常很好，可量測微秒甚至更短的間隔

時鐘同步與準確度#

日曆時鐘需要與 NTP 同步才有用，但同步的準確度受到許多因素影響：

  • 石英漂移（quartz drift）：Google 假設其伺服器的漂移率為 200 ppm，每 30 秒同步一次可能累積 6 ms 誤差，一天不同步則漂移 17 秒
  • NTP 強制重設：若本地時鐘偏差過大，可能被強制重設，導致時間跳躍
  • 防火牆阻擋：節點可能意外被防火牆隔離 NTP 流量而不自知
  • 網路延遲限制：NTP 精確度受限於網路延遲，網際網路上最低誤差約 35 ms
  • NTP 伺服器錯誤：有些 NTP 伺服器本身就報告錯誤的時間
  • 閏秒問題：導致一分鐘有 59 或 61 秒，已造成許多大型系統崩潰
  • VM 時鐘虛擬化：CPU 共享時 VM 被暫停，時鐘看似跳躍前進
  • 不受控的設備：使用者可能故意設定錯誤的時間

不正確的時鐘很容易被忽略。CPU 故障或網路異常會導致明顯的問題，但石英時鐘有缺陷或 NTP 設定錯誤時，大部分功能看似正常，時鐘卻悄悄偏離現實。如果軟體依賴精確同步的時鐘，結果往往是靜默的資料遺失而非明顯的崩潰。因此，必須仔細監控所有機器之間的時鐘偏移。

用時間戳排序事件的陷阱#

在多主複製的資料庫中，使用日曆時鐘的時間戳來排序事件是很誘人但危險的做法。

Figure 8-3: Client B 的寫入因果上晚於 Client A，但時間戳較早

圖中 Client A 在 node 1 寫入 x = 1（時間戳 42.004），Client B 隨後在 node 3 將 x 遞增為 2（時間戳 42.003）。當兩個寫入都複製到 node 2 時，node 2 會錯誤地認為 x = 1 較新（時間戳較大），丟棄 x = 2。Client B 的操作就這樣靜默消失了。

這就是 Last Write Wins（LWW） 策略的問題，被 Cassandra 和 Riak 等廣泛採用。其根本缺陷在於：

  • 時鐘落後的節點無法覆寫時鐘超前的節點所寫入的值
  • 無法區分真正的並行寫入和因果序列寫入
  • 兩個節點可能產生相同的時間戳

邏輯時鐘（logical clocks）——基於遞增計數器而非物理振盪器——是更安全的事件排序替代方案。它們不量測實際時間，只追蹤事件的相對順序。

時鐘讀數的信賴區間#

時鐘的讀數不應被視為一個精確的時間點，而是一個時間範圍（confidence interval）。例如，系統可能有 95% 的信心認為現在時間在 10.3 到 10.5 秒之間，但無法更精確。如果不確定度是 +/- 100 ms，時間戳中的微秒位數就毫無意義。

Google 的 TrueTime API（用於 Spanner）是個有趣的例外：它明確回報時鐘的信賴區間 [earliest, latest]，讓應用程式知道實際時間落在這個範圍內。Spanner 利用這個信賴區間實現跨資料中心的 snapshot isolation：若兩個交易的信賴區間不重疊，就能確定它們的先後順序；若重疊，則透過刻意等待信賴區間長度後再提交，確保因果順序。為了縮短等待時間，Google 在每個資料中心部署 GPS 接收器或原子鐘，將時鐘不確定度控制在約 7 ms。

Process Pauses#

考慮一個單主資料庫的場景：leader 透過租約（lease）——一種帶超時的鎖——來證明自己仍是 leader。以下程式碼看似合理但實際上有兩個問題：

while (true) {
    request = getIncomingRequest();
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }
    if (lease.isValid()) {
        process(request);
    }
}

問題一：租約到期時間由其他機器設定，與本地時鐘比較可能因時鐘偏移出錯。問題二：即使改用單調時鐘，程式在檢查時間和實際處理請求之間可能發生意外的長時間暫停。若執行緒在 lease.isValid() 附近暫停了 15 秒，租約可能已過期、另一個節點已接管，但此執行緒完全不知情，繼續處理請求。

造成長時間暫停的原因包括：

  • GC 暫停（stop-the-world）：Java 的 GC 有時持續數分鐘
  • VM 暫停：虛擬機可能被暫停以進行即時遷移（live migration）
  • 裝置休眠：筆電合蓋
  • OS 上下文切換：執行緒在任意程式碼位置被暫停
  • 同步磁碟 I/O：等待慢速磁碟操作，尤其是網路檔案系統
  • 記憶體分頁（swapping/paging）：存取被換出的記憶體頁觸發磁碟 I/O
  • Unix 信號：SIGSTOP 信號直接暫停程式

分散式系統中的節點必須假設其執行可能在任意時刻被暫停很長時間。暫停期間，其他節點繼續運行、甚至可能宣告暫停的節點死亡。

即時系統（real-time systems）可以透過 RTOS、限制動態記憶體配置等方式提供回應時間保證，但成本極高、吞吐量較低，不適用於一般的伺服器端資料處理系統。實務上可以緩解 GC 暫停的影響：例如將 GC 暫停視為節點的計劃性短暫停機，讓其他節點在此期間接手請求。

知識、真相與謊言#

分散式系統中的節點無法確知任何事——它只能根據透過不可靠網路收到（或沒收到）的訊息來猜測。它無法可靠地區分網路問題和節點問題。

真相由多數決定#

考慮三個場景：

  • 節點可以接收所有訊息，但傳出的訊息全部遺失或延遲。即使它運作正常，其他節點也會宣告它死亡。
  • 半斷線的節點即使發現訊息未被確認，也無法改變其他節點的判決。
  • 經歷長時間 GC 暫停的節點被宣告死亡。GC 結束後它甚至不知道一分鐘已經過去，從它的角度看幾乎沒有時間流逝。

這些故事的寓意是：節點不能信任自己對局勢的判斷。分散式系統不能完全依賴單一節點，因為它隨時可能故障。許多分散式演算法依賴法定人數（quorum）——節點間的投票：決策需要最低數量的節點同意。若法定人數宣告某節點死亡，即使該節點自認為活著，它也必須遵從。最常見的法定人數是絕對多數（超過半數節點），因為系統中只能有一個多數，不會出現兩個多數做出矛盾決策。

Leader 與鎖#

系統經常需要某些東西「只有一個」：一個分區的 leader、一個資源的鎖持有者、一個使用者名稱的擁有者。但即使一個節點相信自己是「被選中的」，也不代表法定人數同意。若它在被宣告死亡後仍繼續以 leader 身份行事，可能導致嚴重問題。

Figure 8-4: 分散式鎖的錯誤實作：Client 1 誤以為仍持有鎖

圖中展示了一個實際的資料損壞 bug（HBase 曾有此問題）：Client 1 取得租約後發生長時間 GC 暫停，租約過期；Client 2 取得相同檔案的租約並開始寫入；Client 1 從暫停中恢復，仍以為租約有效，也對同一檔案寫入，造成資料損壞。

Fencing Tokens#

解決上述問題的簡單技術叫做 fencing。每次鎖服務授予鎖或租約時，同時回傳一個遞增的 fencing token。每個對儲存服務的寫入請求都必須攜帶當前的 fencing token。

Figure 8-5: 使用遞增的 fencing token 確保儲存存取安全

運作方式：Client 1 以 token 33 取得租約後暫停，租約過期。Client 2 以 token 34 取得租約並寫入。Client 1 恢復後以 token 33 嘗試寫入，但儲存服務發現已處理過更高的 token（34），因此拒絕 token 33 的請求。若使用 ZooKeeper，其 transaction ID（zxid）或 node version（cversion）就可以作為 fencing token。

Fencing 機制要求資源端主動檢查 token，拒絕過時的寫入請求。不能只依賴客戶端自行檢查鎖的狀態。這也是一種良好的防禦性設計：服務不應假設其客戶端總是行為良好。

拜占庭故障#

Fencing tokens 能偵測無意中出錯的節點（如不知道租約已過期）。但若節點刻意想破壞系統，它可以傳送偽造的 fencing token。

本書假設節點是不可靠但誠實的（unreliable but honest）：它們可能緩慢或無回應，狀態可能過時，但如果回應了，就是據其所知在遵守協議。若節點可能「說謊」（傳送任意錯誤或偽造的回應），這就是拜占庭故障（Byzantine fault），在這種環境中達成共識的問題稱為拜占庭將軍問題。

拜占庭容錯（Byzantine fault-tolerant）在以下場景中有意義：

  • 航太環境：輻射可能損壞記憶體或 CPU 暫存器，導致任意不可預測的回應
  • 多方參與的系統：部分參與者可能試圖欺詐（如 Bitcoin 等區塊鏈）

但在一般的資料中心系統中，所有節點由同一組織控制，可以合理信任，拜占庭容錯的成本過高。Web 應用需要防範惡意客戶端，但通常透過輸入驗證和授權而非拜占庭協議來處理。

弱形式的「說謊」 仍值得防範：網路封包可能因硬體問題損壞（TCP/UDP 的 checksum 通常能捕捉但偶有遺漏）、應用程式輸入需要驗證、NTP 客戶端查詢多個伺服器並排除離群值。

系統模型與現實#

為了設計正確的分散式演算法，我們需要將預期的故障形式化為系統模型（system model）。

時序模型：

模型假設
同步模型（Synchronous）假設網路延遲、程式暫停、時鐘誤差都有上界。不現實但便於推理
部分同步模型（Partially synchronous）大部分時間表現如同步系統，但偶爾會超出上界。這是最實際的模型
非同步模型（Asynchronous）不做任何時序假設，甚至沒有時鐘。非常受限

節點故障模型：

模型說明
崩潰-停止（Crash-stop）節點崩潰後永不恢復
崩潰-恢復（Crash-recovery）節點可能崩潰後恢復，持久儲存在崩潰間保留，記憶體狀態遺失
拜占庭故障（Byzantine）節點可能做出任意行為

對真實系統建模，部分同步 + 崩潰-恢復通常是最有用的組合。

Safety 與 Liveness#

演算法的正確性屬性可分為兩類：

  • Safety（安全性）：「不好的事永遠不會發生」。若被違反，可以指出違反的具體時刻，且無法撤銷。例如：fencing token 的唯一性和單調遞增。
  • Liveness（活性）：「好的事最終會發生」。在某個時間點可能尚未滿足，但仍有希望未來被滿足。例如：請求最終會收到回應。

分散式演算法通常要求 safety 在所有情況下都成立（即使所有節點崩潰或整個網路失敗），而 liveness 則允許附加條件（例如只在多數節點存活且網路最終恢復的情況下保證）。

理論上的系統模型是簡化的抽象，與混亂的現實之間總有差距。例如崩潰-恢復模型假設持久儲存在崩潰間存活，但硬碟也可能損壞。證明演算法正確不代表其實作永遠正確——但理論分析能揭露可能隱藏很久的問題，與實證測試同樣重要。

本章小結#

本章全面檢視了分散式系統中的各種問題：

  • 網路：封包可能遺失或任意延遲，回應也可能遺失或延遲。沒收到回應時，無法判斷訊息是否送達。
  • 時鐘：節點的時鐘可能與其他節點嚴重不同步，可能突然向前或向後跳躍。依賴時鐘是危險的，因為你很可能不知道時鐘的誤差範圍。
  • 程式暫停：程式可能在任意時刻暫停很長時間（GC、VM 暫停、上下文切換等），被其他節點宣告死亡，然後恢復卻不知道自己曾被暫停。

部分失敗的可能性是分散式系統的定義性特徵。容錯的第一步是偵測故障，但偵測本身就很困難。大多數系統依賴超時來判斷節點是否存活，但超時無法區分網路故障和節點故障。一旦偵測到故障，讓系統容忍它也不容易——沒有共享記憶體、沒有全域變數、沒有共享狀態，節點甚至無法就「現在幾點」達成一致。

儘管如此，這並非毫無希望。下一章將探討在這些限制下，仍能提供特定保證的分散式演算法。

Backward 事務 一致性與共識 Forward