9. 分散式系統的麻煩

意外這東西挺有意思：你沒碰上之前，它就從來不會發生。

A.A. 米爾恩，《小熊維尼和老灰驢的家》（1928）

正如 “可靠性與容錯” 中所討論的，要使一個系統可靠，就要確保即使出了問題（即發生故障），整個系統仍能繼續工作。然而，要預見並處理所有可能的故障並非易事。開發者很容易把注意力主要放在正常路徑上（畢竟大多數時候一切都執行良好！），而忽略會帶來大量邊界情況的故障。

如果希望系統在發生故障時依然可靠，就必須從根本上轉變思維方式，把注意力放在各種可能出錯的地方，即使出錯的機率很低。某件事只有百萬分之一的機率出錯並不意味著可以不管：系統足夠大時，百萬分之一的事件每天都會發生。經驗豐富的系統運維人員會告訴你，任何 可能 出錯的事情，終究都會 出錯。

而且，使用分散式系統與在單臺計算機上編寫軟體有著根本區別——最主要的區別，就是事情有了許多新奇而刺激的出錯方式 ^{1 2}。本章將帶你領略實踐中會遇到的問題，並幫助你理解哪些東西可以依賴，哪些不可以。

為了理解我們面對的挑戰，接下來讓我們把悲觀主義發揮到極致，考察分散式系統裡可能出錯的種種事情。我們將討論網路問題（“不可靠的網路”），以及時鐘和時序問題（“不可靠的時鐘”）。這些問題造成的後果往往令人迷失方向，因此我們還要探討如何認識分散式系統的狀態，以及如何推斷已經發生過的事情（“知識、真相和謊言”）。隨後在 第 10 章 中，我們將透過一些例子看看，面對這些故障時如何實現容錯。

故障與部分失效

當你在一臺計算機上編寫程式時，它通常會以相當可預測的方式執行：要麼正常工作，要麼徹底罷工。有缺陷的軟體可能會讓人覺得計算機偶爾也會“狀態不好”（而重啟往往能解決問題），但這通常只是軟體寫得糟糕所造成的表象。

從根本上說，單臺計算機上的軟體不應該時靈時不靈：只要硬體正常，同樣的操作總會產生同樣的結果（也就是 確定性的）。如果硬體出了問題（例如記憶體損壞或聯結器鬆動），後果通常是整個系統失效（例如核心恐慌、“藍色畫面宕機”或無法啟動）。一臺執行著良好軟體的計算機，通常要麼功能完好，要麼完全失效，而不會停留在兩者之間。

這是計算機設計中的有意選擇：發生內部故障時，我們寧願讓計算機徹底崩潰，也不願讓它返回錯誤結果，因為後者既難處理又容易造成混亂。於是，計算機把其底層模糊而混亂的物理現實隱藏起來，呈現出一個以數學般的完美方式執行的理想化系統模型。CPU 指令每次都會做同樣的事情；寫入記憶體或磁碟的資料會原樣保留，不會隨機損壞。正如 “硬體與軟體故障” 中所討論的，事實並非真的如此——現實中，資料的確可能在沒有任何警告的情況下損壞，CPU 偶爾也會悄無聲息地給出錯誤結果——只不過這些情況足夠罕見，通常可以忽略。

當軟體執行在透過網路連線的多臺計算機上時，情況就截然不同了。分散式系統中的故障要頻繁得多，我們再也無法視而不見，只能直面物理世界混亂的現實。而在物理世界中，可能出錯的事情多得驚人，下面這段軼事便是一個寫照 ³：

在我有限的從業經歷中，我處理過單個數據中心（DC）內長期存在的網路分割槽、PDU（配電單元）故障、交換機故障、整個機架意外斷電重啟、整個資料中心骨幹網故障、整個資料中心停電，以及一名低血糖司機開著福特皮卡撞進資料中心的 HVAC（供暖、通風與空調）系統。而我甚至還不是運維人員。

—— 柯達黑爾

在分散式系統中，即使其他部分工作正常，系統的某些部分也很可能以不可預知的方式發生故障。這叫作 部分失效。棘手之處在於，部分失效是 非確定性的：任何涉及多個節點及其網路的操作，有時能夠成功，有時卻會莫名其妙地失敗。正如我們稍後會看到的，你甚至可能根本 不知道 某件事究竟成功了沒有！

正是這種非確定性和部分失效的可能性，讓分散式系統如此難以駕馭 ⁴。不過，如果分散式系統能夠容忍部分失效，也會由此獲得強大的能力。例如，你可以執行滾動升級：每次重啟一個節點來安裝軟體更新，同時讓整個系統始終不間斷地工作。因此，藉助容錯，我們可以用不可靠的元件構建出比單節點系統更可靠的分散式系統。

不過，在實現容錯之前，我們需要進一步瞭解究竟要容忍哪些故障。應當考慮儘可能廣泛的故障——包括那些看來不太可能發生的故障——並在測試環境中人為製造這些情形，觀察系統會怎樣反應。在分散式系統中，多一些懷疑、悲觀和偏執總會有所回報。

不可靠的網路

正如 “共享記憶體、共享磁碟與無共享架構” 中所討論的，本書關注的分散式系統大多是 無共享系統，也就是一組透過網路連線的機器。網路是這些機器彼此通訊的唯一途徑——我們假定每臺機器都有自己的記憶體和磁碟，一臺機器無法直接訪問另一臺機器的記憶體或磁碟，只能透過網路向服務傳送請求。即使儲存本身是共享的（例如 Amazon S3），機器也仍然要透過網路與共享儲存服務通訊。

網際網路和資料中心裡的大多數內部網路（通常是乙太網）都是 非同步分組網路。在這種網路中，一個節點可以向另一個節點發送訊息（即資料包），但網路既不保證訊息何時到達，也不保證它一定能夠到達。如果你發出請求並等待響應，可能會發生許多問題（其中一些如 圖 9-1 所示）：

1. 請求可能已經丟失（或許有人拔掉了網線）。
2. 請求可能還在佇列中等待，稍後才會送達（或許網路或接收方過載了）。
3. 遠端節點可能已經失效（或許它崩潰了，或是被關閉了）。
4. 遠端節點可能只是暫時停止響應（或許它正經歷一次漫長的垃圾回收暫停；參見 “程序暫停”），稍後又會恢復響應。
5. 遠端節點可能已經處理了請求，但響應在網路中丟失了（或許某臺網絡交換機配置有誤）。
6. 遠端節點可能已經處理了請求，但響應被延遲，稍後才會送達（或許網路或你自己的機器過載了）。

傳送方甚至無法判斷資料包是否送達：唯一的辦法是由接收方發回響應訊息，而這個響應同樣可能丟失或延遲。在非同步網路中，這些情形無法區分：你掌握的唯一資訊只是“尚未收到響應”。向另一個節點發送請求卻沒有收到響應時，不可能 判斷原因究竟是什麼。

處理這個問題的慣常辦法是設定 超時：等待一段時間後便放棄，並假定響應不會再來。然而，即使發生超時，你仍然不知道遠端節點是否收到了請求（如果請求仍在某處排隊，那麼即便傳送方已經放棄，它仍可能在稍後送達接收方）。

TCP 的侷限性

網路資料包有大小上限（通常只有幾千位元組），但許多應用程式需要傳送無法裝進單個數據包的訊息，例如請求和響應。這類應用程式通常使用 TCP（傳輸控制協議）建立一條 連線，把較大的資料流拆成一個個資料包，再在接收端重新組裝起來。

TCP 常被說成能提供“可靠”的傳輸，這裡的“可靠”是指：它能檢測並重傳丟失的資料包，發現順序錯亂的資料包並將其恢復為正確順序，還能用簡單的校驗和檢測資料包損壞。TCP 也會判斷應當以多快的速度傳送資料，既儘可能快速傳輸，又不至於壓垮網路或接收節點；這叫作 擁塞控制、流量控制 或 背壓 ⁵。

當你把資料寫入套接字來“傳送”時，資料其實不會立即發出，只會先進入作業系統管理的緩衝區。擁塞控制演算法判斷目前有能力傳送資料包後，才會從緩衝區取出一個數據包大小的資料，交給網路介面。資料包會經過若干交換機和路由器，最終由接收節點的作業系統把資料放進接收緩衝區，並向傳送方發回確認包。直到這時，接收端作業系統才會通知應用程式又有資料到達 ⁶。

既然 TCP 提供了“可靠性”，是不是就不必再操心網路不可靠了？遺憾的是，並非如此。如果在一定的超時時間內沒有收到確認，TCP 會認定資料包必定已經丟失，但它同樣無法判斷丟掉的究竟是發出的資料包，還是返回的確認包。TCP 雖然可以重發，卻不能保證重發的資料包一定能夠到達。如果網線被拔了，TCP 可沒法替你把它插回去。最終，經過可配置的超時時間後，TCP 會放棄重試，並嚮應用程式報告錯誤。

如果 TCP 連線因錯誤而關閉——或許是遠端節點崩潰了，也可能是網路中斷了——你無法知道遠端節點究竟處理了多少資料 ⁶。即使 TCP 已經確認某個資料包送達，也只說明遠端節點的作業系統核心收到了它；應用程式仍可能在處理這份資料之前就崩潰。如果要確認請求成功，必須由應用程式本身明確返回成功響應 ⁷。

儘管如此，TCP 依然非常有用，因為它讓我們能夠方便地收發無法裝進單個數據包的訊息。建立 TCP 連線後，還可以透過同一條連線傳送多個請求和響應。通常的做法是先發送一個頭部，註明緊隨其後的訊息有多少位元組，再發送訊息本身。HTTP 和許多 RPC 協議（參見 “流經服務的資料流：REST 與 RPC”）都是這樣工作的。

實踐中的網路故障

我們建設計算機網路已有幾十年，按說早該找到讓網路可靠的辦法了。遺憾的是，我們至今仍未成功。系統性研究與大量軼事證據都表明，即使在由一家公司運營的資料中心這類受控環境中，網路問題也可能頻繁得出人意料 ⁸：

• 一項針對中型資料中心的研究發現，每月大約會發生 12 次網路故障，其中一半會斷開一臺機器，另一半則會斷開整個機架 ⁹。
• 另一項研究測量了架頂交換機、匯聚交換機和負載均衡器等元件的失效率 ¹⁰。研究發現，增加冗餘網路裝置並不能像預想的那樣大幅減少故障，因為它防不住人為錯誤（例如交換機配置錯誤），而人為錯誤正是停機的一大主因。
• 廣域光纖鏈路的中斷曾被歸咎於奶牛 ¹¹、海狸 ¹² 和鯊魚 ¹³（不過隨著海底電纜的防護改善，鯊魚咬壞電纜的事件已經越來越少 ¹⁴）。當然，人類也難辭其咎：誤配置 ¹⁵、盜割電纜 ¹⁶ 和蓄意破壞 ¹⁷ 都曾造成事故。
• 在不同雲區域之間的通訊中，高百分位數的往返時間最長可達數 分鐘 ¹⁸。即使在同一個資料中心內，交換機軟體升級出現問題並觸發網路拓撲重配置時，資料包也可能延遲一分鐘以上 ¹⁹。因此，我們必須假定訊息可能遭到任意長時間的延遲。
• 有時通訊只會部分中斷，能否連通取決於通訊雙方是誰。例如，A 與 B 可以通訊，B 與 C 也可以通訊，但 A 與 C 卻無法通訊 ^{20 21}。還有些故障更出人意料，比如某個網路介面有時會丟棄所有入站資料包，卻仍能正常發出資料包 ²²：網路鏈路在一個方向上可用，並不保證反方向也可用。
• 即使網路中斷只持續了很短時間，其後續影響也可能遠遠長於最初的問題 ^{8 20 23}。

即使你的環境很少遇到網路故障，故障 有可能 發生這一事實也意味著軟體必須能夠處理它。只要透過網路通訊，就有可能失敗——這一點無可迴避。

如果沒有明確定義並測試網路故障的處理方式，後果可能糟到沒有下限。例如，即使網路已經恢復，叢集仍可能陷入死鎖，從此無法再處理請求 ²⁴；甚至還可能刪掉你的全部資料 ²⁵。一旦軟體落入設計者未曾預料的情形，它就可能做出任何出人意料的事情。

處理網路故障不一定意味著要 容忍 它。如果網路通常相當可靠，那麼在發生網路問題時直接向用戶顯示錯誤訊息，也可以是一種合理策略。不過，你必須知道軟體會如何應對網路問題，並確保系統能夠從中恢復。可以考慮有意觸發網路問題，測試系統會如何反應（這叫作 故障注入；參見 “故障注入”）。

故障檢測

許多系統需要自動檢測發生故障的節點。例如：

• 負載均衡器需要停止向已經宕機的節點發送請求（也就是把它 移出輪詢池）。
• 在採用單主複製的分散式資料庫中，如果領導者失效，就需要把某個追隨者提升為新的領導者（參見 “處理節點故障”）。

遺憾的是，網路的不確定性讓人很難判斷節點是否仍在工作。在某些特定情況下，你也許能收到明確表明某處出了問題的反饋：

• 如果執行節點的機器可以訪問，但目標埠沒有程序監聽（例如程序已經崩潰），作業系統會返回 RST 或 FIN 資料包，從而關閉或拒絕 TCP 連線。
• 如果節點程序崩潰（或被管理員終止），但節點的作業系統仍在執行，可以由指令碼把崩潰訊息通知其他節點，讓另一個節點不必等待超時便能迅速接管。例如，HBase 就採用這種方式 ²⁶。
• 如果你能訪問資料中心裡網路交換機的管理介面，就可以查詢交換機，在硬體層面檢測鏈路故障（例如遠端機器是否已經斷電）。但如果你透過網際網路連線、身處無法訪問交換機本身的共享資料中心，或是網路問題使管理介面也無法訪問，這種辦法就行不通了。
• 如果路由器確信你要連線的 IP 地址不可達，它可能會返回一個 ICMP“目標不可達”資料包。不過，路由器也沒有什麼神奇的故障檢測能力——它同樣受到網路中其他參與者所面對的那些限制。

能夠迅速得知遠端節點宕機固然有用，但不能指望總有這樣的反饋。發生問題時，你或許會從協議棧的某一層收到錯誤響應，但通常必須假定自己什麼響應也收不到。你可以重試幾次，等待超時；如果超時時間內一直沒有回覆，最終便宣告該節點已經死亡。

超時和無界延遲

如果超時是檢測故障的唯一可靠方法，那麼超時時間應該設為多長？遺憾的是，這個問題沒有簡單答案。

較長的超時意味著要等很久才能宣告節點死亡（在此期間，使用者可能只能等待，或不斷看到錯誤訊息）。較短的超時可以更快發現故障，卻更容易把只是暫時變慢的節點（例如節點或網路出現負載峰值）誤判為死亡。

過早宣告節點死亡會帶來麻煩：如果節點其實仍然活著，並且正在執行某個操作（例如傳送電子郵件），此時另一個節點又接管了它的工作，同一個操作最終可能執行兩次。我們將在 “知識、真相和謊言”、第 10 章 以及 “資料庫的端到端原則” 中更詳細地討論這個問題。

宣告節點死亡後，它承擔的職責就要轉移給其他節點，這會額外增加其他節點和網路的負擔。如果系統本來就在高負載下勉力支撐，過早宣告節點死亡可能讓局面進一步惡化。尤其可能出現這樣的情況：節點其實沒有死，只是過載導致響應緩慢；把它的負載轉移給其他節點，又可能引發級聯失效（極端情況下，所有節點互相宣告對方死亡，整個系統徹底停止工作——參見 “當過載系統無法恢復時”）。

設想一個虛構的系統，其網路保證資料包的最大延遲：每個資料包要麼在時間 d 以內送達，要麼丟失，絕不會在超過 d 之後才送達。再假定我們能夠保證，任何尚未失效的節點總會在時間 r 以內處理完請求。在這種情況下，每個成功的請求都能保證在 2d + r 以內收到響應；如果過了這麼久仍未收到響應，就可以斷定網路或遠端節點沒有正常工作。假如這些保證真的成立，那麼 2d + r 就是合理的超時時間。

遺憾的是，我們使用的大多數系統都不具備上述任何一項保證：非同步網路具有 無界延遲（也就是說，它會盡快嘗試送達資料包，但資料包所需的傳輸時間沒有上限），大多數伺服器實現也不能保證一定在某個最長時間內處理完請求（參見 “響應時間保證”）。對故障檢測而言，系統僅僅在大多數時候執行得很快還不夠：如果超時時間設得很短，一次短暫的往返時間尖峰就足以打亂整個系統。

網路擁塞與排隊

開車出行時，交通擁堵往往是造成行程時間波動的最大因素。同樣，在計算機網路上，資料包延遲的變化通常也是排隊造成的 ²⁷：

• 如果多個節點同時向同一個目的地傳送資料包，網路交換機就必須讓這些資料包排隊，再逐一送入通往目的地的網路鏈路（如 圖 9-2 所示）。網路鏈路繁忙時，資料包可能需要等待一段時間才能獲得傳送機會，這叫作 網路擁塞。如果流入的資料太多，交換機佇列被塞滿，資料包就會被丟棄，因而必須重發——即使網路本身仍在正常工作。
• 資料包抵達目標機器時，如果所有 CPU 核心都在忙，作業系統會把來自網路的請求放進佇列，直到應用程式有能力處理為止。等待時間取決於機器的負載，可能任意之長 ²⁸。
• 在虛擬化環境中，當另一臺虛擬機器佔用某個 CPU 核心時，正在執行的作業系統常常會暫停數十毫秒。在此期間，虛擬機器無法消費任何網路資料，因此虛擬機器監控器會將流入的資料排隊（緩衝）²⁹，進一步增大網路延遲的波動。
• 如前所述，為避免網路過載，TCP 會限制資料的傳送速率。這意味著資料甚至還沒進入網路，就已經在傳送方額外排了一次隊。

此外，當 TCP 檢測到資料包丟失並自動重傳時，應用程式雖然不會直接看到丟包，卻會感受到由此造成的延遲：先等待超時，再等待重傳的資料包得到確認。

上述因素都會造成網路延遲的波動。當系統接近最大容量時，排隊延遲的變化範圍尤其大：擁有充足餘量的系統可以輕鬆排空佇列，而利用率很高的系統則可能迅速積起長隊。

在公共雲和多租戶資料中心中，許多客戶共享同一批資源：網路鏈路和交換機是共享的，甚至每臺機器的網路介面和 CPU（使用虛擬機器時）也是共享的。處理大量資料時，可能耗盡網路鏈路的全部容量，使其達到 飽和。你既無法控制，也無法瞭解其他客戶如何使用共享資源；如果附近某個 吵鬧的鄰居 正在大量消耗資源，網路延遲就可能劇烈波動 ^{30 31}。

在這樣的環境中，只能透過實驗來選擇超時時間：長期測量大量機器之間網路往返時間的分佈，確定延遲通常會有多大波動。然後結合應用程式自身的特點，在故障檢測的延遲與過早超時的風險之間做出適當權衡。

更好的辦法是不用固定配置的超時時間，而讓系統持續測量響應時間及其波動（抖動），再根據觀測到的響應時間分佈自動調整超時。Phi 累積故障檢測器 ³² 就採用了這種方法，Akka 和 Cassandra 等系統都在使用它 ³³。TCP 的重傳超時也以類似方式工作 ⁵。

同步網路與非同步網路

如果可以指望網路在某個固定的最長延遲內送達資料包，而且絕不丟包，分散式系統就會簡單得多。為什麼不能在硬體層面解決這個問題，讓網路變得可靠，從而使軟體不必再操心呢？

要回答這個問題，不妨把資料中心網路與傳統的固定電話網路（非蜂窩網路，也非 VoIP）比較一下。傳統電話網路極其可靠：音訊幀延遲和通話中斷都很罕見。電話通話需要持續保持較低的端到端延遲，並提供足夠頻寬來傳輸語音取樣。如果計算機網路也能具備類似的可靠性與可預測性，豈不是很好？

透過電話網路撥號時，網路會建立一條 電路：從一名通話者到另一名通話者的整條路徑上，都會為這次通話分配固定且有保證的頻寬。這條電路會一直保留到通話結束 ³⁴。例如，ISDN 網路以每秒 4,000 幀的固定速率執行。建立通話時，每一幀都會在兩個方向上各分配 16 位空間。因此在整個通話期間，雙方都能保證每 250 微秒恰好傳送 16 位音訊資料 ³⁵。

這類網路是 同步的：即使資料要經過多臺路由器，也不會排隊，因為每一跳都已經為這次通話預留了 16 位的空間。由於無需排隊，網路的最大端到端延遲是固定的。我們稱之為 有界延遲。

我們不能簡單地讓網路延遲可預測嗎？

注意，電話網路中的電路與 TCP 連線截然不同：電路會預留固定數量的頻寬，只要電路存在，其他人就無法使用這部分頻寬；TCP 連線的資料包則會伺機利用當時可用的任意網路頻寬。你可以交給 TCP 一塊大小不定的資料（例如電子郵件或網頁），它會盡力在最短時間內傳輸完畢。TCP 連線空閒時不會佔用頻寬，偶爾傳送的保活包除外。

如果資料中心網路和網際網路採用電路交換，那麼建立電路時就可以同時確定有保證的最大往返時間。但它們並非如此：乙太網和 IP 都是分組交換協議，資料包會排隊，因而網路延遲沒有上界。這些協議中根本沒有“電路”的概念。

為什麼資料中心網路和網際網路要使用分組交換？因為它們針對 突發流量 做了最佳化。音訊或影片通話在整個通話期間每秒傳輸的位數相當穩定，很適合使用電路。相比之下，請求網頁、傳送電子郵件或傳輸檔案並沒有特定的頻寬要求——我們只希望它們儘快完成。

如果要透過電路傳輸檔案，就必須先猜測應當分配多少頻寬。猜得太低，傳輸速度會慢得毫無必要，同時還有網路容量閒置；猜得太高，電路又無法建立，因為網路不能為無法保證頻寬分配的電路放行。因此，用電路傳輸突發資料既浪費網路容量，又使傳輸無謂地變慢。TCP 則不同，它會根據可用的網路容量動態調整資料傳輸速率。

人們也曾嘗試構建兼具電路交換與分組交換的混合網路。非同步傳輸模式（ATM）在 20 世紀 80 年代曾與乙太網競爭，但除了電話網路的核心交換機外，並未得到廣泛採用。InfiniBand 與之有些相似 ³⁶：它在鏈路層實現端到端流量控制，減少了網路排隊的必要，不過鏈路擁塞仍可能帶來延遲 ³⁷。如果謹慎運用 服務質量（QoS，即資料包的優先順序與排程）和 准入控制（對傳送方限速），就可以在分組網路上類比電路交換，或提供統計意義上的有界延遲 ^{27 34}。低延遲、低損耗和可伸縮吞吐量（L4S）等新型網路演算法，試圖從客戶端和路由器兩端緩解部分排隊與擁塞控制問題。Linux 的流量控制器（TC）也允許應用程式為實現 QoS 而重新安排資料包的優先順序。

不過，多租戶資料中心、公共雲以及經由網際網路的通訊，目前都沒有啟用這樣的服務質量機制。現有部署技術無法讓我們對網路的延遲或可靠性作出任何保證：必須假定網路擁塞、排隊和無界延遲都會發生。因此，超時時間沒有所謂“正確”的取值，只能透過實驗來確定。

網際網路服務提供商之間的對等互聯協議，以及透過邊界閘道器協議（BGP）建立路由的方式，比 IP 本身更像電路交換。在這個層面上，確實可以買到專用頻寬。不過，網際網路路由工作在網路層面，而不是主機之間的單條連線層面，其時間尺度也長得多。

不可靠的時鐘

時鐘和時間都很重要。應用程式會以各種方式依賴時鐘，回答下面這些問題：

1. 這個請求已經超時了嗎？
2. 這項服務響應時間的第 99 百分位數是多少？
3. 過去五分鐘裡，這項服務平均每秒處理多少次查詢？
4. 使用者在我們的網站上停留了多長時間？
5. 這篇文章是什麼時候釋出的？
6. 提醒郵件應該在哪一天、什麼時間發出？
7. 這個快取條目什麼時候過期？
8. 日誌檔案裡這條錯誤訊息的時間戳是什麼？

問題 1～4 測量的是 持續時間（例如從傳送請求到收到響應之間的時間間隔），問題 5～8 描述的則是 時間點（在某個具體日期和時刻發生的事件）。

在分散式系統中，時間是個棘手的問題，因為通訊並非瞬間完成：訊息從一臺機器經網路傳到另一臺機器需要時間。收到訊息的時刻必然晚於發出訊息的時刻，但由於網路延遲會發生變化，我們不知道究竟晚了多少。涉及多臺機器時，這一事實有時會讓事件的先後順序難以確定。

此外，網路中的每臺機器都有自己的時鐘，而且它是實實在在的硬體裝置，通常是石英晶體振盪器。這些裝置並不十分精確，因此每臺機器都各有一套時間觀念，可能比其他機器走得稍快或稍慢。時鐘可以在一定程度上同步：最常用的機制是網路時間協議（NTP），它根據一組伺服器報告的時間來校準計算機時鐘 ³⁹；這些伺服器又從 GPS 接收器等更精確的時間源取得時間。

單調時鐘與日曆時鐘

現代計算機至少配有兩種不同的時鐘：日曆時鐘 和 單調時鐘。它們雖然都用來度量時間，卻服務於不同目的，因此必須加以區分。

日曆時鐘

日曆時鐘所做的，正是人們直覺上認為時鐘應該做的事：按照某種曆法返回當前日期和時間（也稱為 牆上時鐘時間）。例如，Linux 的 clock_gettime(CLOCK_REALTIME) 和 Java 的 System.currentTimeMillis() 返回從 紀元 至今經過的秒數（或毫秒數）：這裡的紀元是格里高利曆中的 1970 年 1 月 1 日 UTC 零時，且不計閏秒。有些系統使用其他日期作為參考點。（Linux 雖然把這個時鐘稱為 實時 時鐘，但它與實時作業系統毫無關係，參見 “響應時間保證”。）

日曆時鐘通常會與 NTP 同步，因此理想情況下，一臺機器上的某個時間戳與另一臺機器上的同一時間戳表示同一時刻。不過，日曆時鐘也有各種怪異之處，下一節將進一步說明。尤其是當本地時鐘比 NTP 伺服器快得太多時，它可能會被強制重置，看起來就像突然跳回了過去。這樣的跳變，以及閏秒造成的類似跳變，使日曆時鐘不適合測量已經過去了多長時間 ⁴⁰。

夏令時（DST）開始或結束時，日曆時鐘也可能跳變；只要始終採用沒有夏令時的 UTC 時區，就能避開這類跳變。歷史上，日曆時鐘的解析度也相當粗糙，例如舊版 Windows 系統的時鐘每次會向前跳 10 毫秒 ⁴¹。在較新的系統上，這已經不是什麼大問題。

單調時鐘

單調時鐘適合測量持續時間（時間間隔），例如超時時間或服務響應時間。Linux 的 clock_gettime(CLOCK_MONOTONIC)、clock_gettime(CLOCK_BOOTTIME) ⁴² 和 Java 的 System.nanoTime() 都屬於單調時鐘。之所以叫“單調”，是因為它保證只會向前走（日曆時鐘卻可能突然跳回過去）。

你可以先讀取一次單調時鐘，做些事情，稍後再讀一次。兩次讀數之 差 就是其間經過的時間——它更像秒錶，而不是掛鐘。不過，單調時鐘的 絕對 讀數沒有任何意義：它可能表示計算機啟動至今的納秒數，也可能採用其他任意起點。尤其不能比較兩臺不同計算機的單調時鐘讀數，因為它們表示的並不是同一回事。

在有多個 CPU 插槽的伺服器上，每顆 CPU 都可能有自己的計時器，而且未必與其他 CPU 同步 ⁴³。作業系統會補償其中的差異，盡力讓應用程式執行緒看到單調遞增的時鐘，即使執行緒在不同 CPU 之間排程也是如此。不過，對這樣的單調性保證最好還是有所保留 ⁴⁴。

如果 NTP 發現計算機的本地石英鐘比 NTP 伺服器走得更快或更慢，可以調節單調時鐘向前推進的速率，這叫作對時鐘進行 漸進校準。預設情況下，NTP 最多可以把時鐘速率加快或減慢 0.05%，但不能讓單調時鐘突然向前或向後跳變。單調時鐘通常有很好的解析度：在大多數系統上，它能測量微秒級甚至更短的時間間隔。

在分散式系統中，用單調時鐘測量經過的時間（例如超時）通常沒有問題，因為這不要求不同節點的時鐘彼此同步，而且測量中的輕微誤差也不會造成太大影響。

時鐘同步和準確性

單調時鐘不需要同步，但日曆時鐘只有根據 NTP 伺服器或其他外部時間源進行校準才有用。遺憾的是，讓時鐘顯示正確時間的手段遠沒有想象中那麼可靠和準確——硬體時鐘與 NTP 都可能反覆無常。下面只是其中幾個例子：

• 計算機裡的石英鐘並不十分精確，它會發生 漂移（走得比應有速度更快或更慢），而漂移程度又會隨機器溫度變化。Google 假定其伺服器的時鐘漂移最高可達 200 ppm（百萬分之二百）⁴⁵。這相當於每隔 30 秒與伺服器重新同步一次的時鐘會漂移 6 毫秒，而每天才同步一次的時鐘會漂移 17 秒。即使其他一切都正常，時鐘漂移也會限制所能達到的最佳精度。
• 如果計算機時鐘與 NTP 伺服器相差太大，它可能拒絕同步，也可能強制重置本地時鐘 ³⁹。在重置前後觀察時間的應用程式，可能會看到時間向後倒退，或突然向前跳躍。
• 如果防火牆意外阻斷了節點與 NTP 伺服器的通訊，這項錯誤配置可能很長時間都無人察覺；在此期間，漂移不斷累積，不同節點的時鐘最終可能相差甚遠。軼事證據表明，實踐中確實發生過這種情況。
• NTP 同步的準確性不可能優於網路延遲。因此，在資料包延遲波動不定的擁塞網路上，它的準確性必然有限。一項實驗表明，經由網際網路同步所能達到的最小誤差為 35 毫秒 ⁴⁶，而網路延遲偶爾出現尖峰時，誤差會達到一秒左右。具體取決於配置，過大的網路延遲甚至可能讓 NTP 客戶端徹底放棄同步。
• 有些 NTP 伺服器本身不正確或配置有誤，報告的時間能相差數小時 ^{47 48}。NTP 客戶端會查詢多臺伺服器並忽略離群值，以減輕這類錯誤的影響。即便如此，把系統的正確性押在某個網際網路陌生人報給你的時間上，多少還是令人不安。
• 閏秒會讓一分鐘變成 59 秒或 61 秒，從而打亂那些設計時未考慮閏秒的系統對時序所作的假設 ⁴⁹。閏秒已經導致許多大型系統崩潰 ^{40 50}，足見關於時鐘的錯誤假設有多麼容易悄然混入系統。處理閏秒的最佳辦法，或許是讓 NTP 伺服器“撒謊”：把閏秒調整分攤到一整天內逐漸完成，這稱為 平滑處理 ^{51 52}；不過實踐中各 NTP 伺服器的實際行為並不一致 ⁵³。好在從 2035 年起將不再使用閏秒，這個問題也會隨之消失。
• 在虛擬機器中，硬體時鐘也是虛擬化的，這給需要精確計時的應用程式帶來了額外挑戰 ⁵⁴。多個虛擬機器共享 CPU 核心時，一臺虛擬機器執行，其他虛擬機器就可能暫停數十毫秒。從應用程式的視角看，這種暫停表現為時鐘突然向前跳躍 ²⁹。如果虛擬機器暫停了幾秒，其時鐘隨後可能比實際時間慢幾秒，但 NTP 仍可能報告時鐘幾乎完全同步 ⁵⁵。
• 如果軟體執行在你無法完全控制的裝置上（例如移動裝置或嵌入式裝置），那麼裝置的硬體時鐘可能根本不值得信任。有些使用者會故意把硬體時鐘設定成錯誤的日期和時間，例如藉此在遊戲中作弊 ⁵⁶。因此，時鐘可能被設到離譜的過去或未來。

只要足夠重視時鐘精度，並願意投入大量資源，的確可以做到非常精確。例如，歐洲針對金融機構的 MiFID II 法規要求所有高頻交易基金把時鐘與 UTC 的誤差控制在 100 微秒以內，以便排查“閃崩”等市場異常，並幫助發現市場操縱 ⁵⁷。

藉助專用硬體（GPS 接收器和/或原子鐘）、精確時間協議（PTP），再輔以審慎的部署與監控，就能達到這樣的精度 ^{58 59}。不過，只依賴 GPS 也有風險，因為 GPS 訊號很容易受到干擾；某些地方（例如軍事設施附近）甚至經常發生這種情況 ⁶⁰。一些雲服務商已經開始為虛擬機器提供高精度時鐘同步 ⁶¹。即便如此，時鐘同步仍需格外小心。如果 NTP 守護程序配置有誤，或防火牆阻斷了 NTP 流量，漂移造成的時鐘誤差很快就會變得很大。

對同步時鐘的依賴

時鐘的問題在於，它看似簡單易用，陷阱卻多得驚人：一天未必恰好有 86,400 秒，日曆時鐘可能倒著走，一個節點所認為的時間也可能與另一個節點相差很大。

本章前面討論過網路丟包和任意延遲資料包的問題。儘管網路在絕大多數時候表現良好，設計軟體時仍必須假定網路偶爾會發生故障，並妥善處理這些故障。時鐘也是如此：它們大多數時候都走得好好的，但健壯的軟體必須做好應對錯誤時鐘的準備。

部分問題在於，錯誤的時鐘很容易無人察覺。如果機器的 CPU 有缺陷，或網路配置有誤，它多半會徹底無法工作，因此問題很快就會暴露並得到修復。反之，如果石英鐘有缺陷，或 NTP 客戶端配置有誤，那麼即使時鐘逐漸偏離現實越來越遠，大多數事情看上去仍然執行正常。如果某段軟體依賴精確同步的時鐘，最終結果更可能是隱蔽而細微的資料丟失，而不是一場驚天動地的崩潰 ^{62 63}。

因此，如果使用的軟體要求時鐘同步，就必須仔細監控所有機器之間的時鐘偏差。凡是時鐘與其他節點偏離太遠的節點，都應當被宣告死亡並移出叢集。這樣的監控可以確保在故障時鐘造成太大破壞以前及時發現它。

用於事件排序的時間戳

下面來看一種很容易讓人想依賴時鐘、卻十分危險的情形：為多個節點上的事件排序 ⁶⁴。例如，兩個客戶端都向分散式資料庫寫入時，誰先到達？哪次寫入更新？

圖 9-3 展示了在採用多主複製的資料庫中，日曆時鐘的一種危險用法（這個例子與 圖 6-8 類似）。客戶端 A 在節點 1 上寫入 x = 1；這次寫入複製到節點 3；客戶端 B 在節點 3 上將 x 遞增（此時 x = 2）；最後，兩次寫入都複製到節點 2。

在 圖 9-3 中，寫入複製到其他節點時，會按照寫入起源節點的日曆時鐘附上時間戳。這個例子中的時鐘同步已經非常好：節點 1 與節點 3 的偏差不到 3 毫秒，實踐中恐怕很難達到這麼好的水平。

遞增操作建立在先前寫入的 x = 1 之上，因此我們自然會認為 x = 2 這次寫入應該具有更大的時間戳。遺憾的是，圖 9-3 中並非如此：寫入 x = 1 的時間戳是 42.004 秒，寫入 x = 2 的時間戳卻是 42.003 秒。

正如 “最後寫入者勝（丟棄併發寫入）” 所討論的，解決不同節點併發寫入值之間衝突的一種辦法是 最後寫入者勝（LWW）：對於同一個鍵，只保留時間戳最大的寫入，丟棄所有時間戳更早的寫入。在 圖 9-3 的例子中，節點 2 收到這兩個事件後，會錯誤地斷定 x = 1 才是更新的值，並丟棄對 x = 2 的寫入，於是遞增操作便丟失了。

要避免這個問題，可以確保每當覆蓋一個值時，新值的時間戳一定高於被覆蓋值，即使這個時間戳已經超前於寫入者的本地時鐘。不過，這樣就要付出額外讀取的代價，先找出當前最大的時間戳。Cassandra 和 ScyllaDB 等系統希望在一次往返中寫入所有副本，因此它們直接使用客戶端時鐘生成的時間戳，並採用最後寫入者勝策略 ⁶²。這種做法存在一些嚴重問題：

• 資料庫寫入可能莫名其妙地消失：在走得較慢的節點追上走得較快的節點之前，它無法覆蓋後者先前寫入的值 ^{63 65}。這樣可能在不向應用程式報告任何錯誤的情況下，悄無聲息地丟棄任意數量的資料。
• LWW 無法區分短時間內接連發生的順序寫入（在 圖 9-3 中，客戶端 B 的遞增操作顯然發生在客戶端 A 的寫入 之後）與真正的併發寫入（兩個寫入者都不知道對方的寫入）。為了避免違反因果關係，還需要版本向量等額外的因果關係追蹤機制（參見 “檢測併發寫入”）。
• 兩個節點可能各自獨立生成具有相同時間戳的寫入，特別是時鐘解析度只有毫秒時。解決這類衝突還需要一個額外的決勝值（簡單地取一個很大的隨機數即可），但這種做法同樣可能違反因果關係 ⁶²。

因此，儘管保留最“新”的值並丟棄其他值，看上去是很誘人的衝突解決辦法，但必須意識到，“新”的定義取決於本地日曆時鐘，而它很可能並不準確。即使時鐘經過嚴密的 NTP 同步，也可能出現這樣的情況：資料包在時間戳 100 毫秒時發出（按傳送方的時鐘），卻在時間戳 99 毫秒時到達（按接收方的時鐘）——看起來彷彿資料包還沒發出就已經到達，這當然不可能。

能否把 NTP 同步做得足夠精確，從而徹底避免這類錯誤排序？恐怕不能。除了石英鐘漂移等其他誤差源以外，NTP 的同步精度本身就受網路往返時間限制。若要保證順序正確，時鐘誤差必須顯著小於網路延遲，而這是不可能做到的。

所謂的 邏輯時鐘 ⁶⁶ 以遞增計數器為基礎，而不是以振盪的石英晶體為基礎，因此是為事件排序時更安全的選擇（參見 “檢測併發寫入”）。邏輯時鐘既不度量一天中的時刻，也不度量經過了多少秒，只記錄事件之間的相對順序（一個事件發生在另一個事件之前還是之後）。與之相對，日曆時鐘和單調時鐘度量真實流逝的時間，因此也稱為 物理時鐘。我們將在 “ID 生成器和邏輯時鐘” 中更詳細地討論邏輯時鐘。

帶置信區間的時鐘讀數

機器的日曆時鐘也許能以微秒甚至納秒為解析度提供讀數，但測量得如此精細，並不表示讀數真的精確到了這個程度。事實上，它大機率沒有這麼準。前面說過，即使每分鐘都與區域網中的 NTP 伺服器同步一次，不精確的石英鐘也很容易漂移數毫秒。若使用公共網際網路上的 NTP 伺服器，最理想的精度大概也只有數十毫秒；遇到網路擁塞時，誤差很容易飆升到 100 毫秒以上。

因此，不應把一次時鐘讀數理解為一個精確的時間點，它更像是落在某個置信區間內的一段時間範圍。例如，系統也許有 95% 的把握認為當前時刻位於這一分鐘的第 10.3 秒至第 10.5 秒之間，但無法知道得更精確 ⁶⁷。如果時間只能確定到 ±100 毫秒，那麼時間戳中精確到微秒的那些數字基本毫無意義。

不確定性的邊界可以根據時間源來計算。如果計算機直接連線著 GPS 接收器或原子鐘，預期誤差範圍取決於裝置本身；對 GPS 而言，還取決於衛星訊號的質量。如果從伺服器獲取時間，不確定性大致等於：自上次與伺服器同步以來石英鐘的預期漂移，加上 NTP 伺服器自身的不確定性，再加上與伺服器之間的網路往返時間——這是第一步近似，並且假定伺服器值得信任。

遺憾的是，大多數系統都不會暴露這種不確定性。例如，呼叫 clock_gettime() 時，返回值並不會告訴你時間戳的預期誤差，因此你無從得知它的置信區間究竟是五毫秒，還是五年。

不過也有例外：Google Spanner 的 TrueTime API ⁴⁵ 和 Amazon 的 ClockBound 都會明確報告本地時鐘的置信區間。查詢當前時間時，得到的是兩個值：[earliest, latest]，分別表示 最早可能 與 最晚可能 的時間戳。根據對不確定性的計算，時鐘能夠斷定真實的當前時間位於這個區間內。區間的寬度取決於多種因素，其中包括本地石英鐘距離上次與更精確的時間源同步已經過去多久。

用於全域性快照的同步時鐘

在 “快照隔離與可重複讀” 中，我們討論了 多版本併發控制（MVCC）。對於既要支援短小快速的讀寫事務，又要支援大型、長時間執行的只讀事務（例如備份或分析）的資料庫來說，MVCC 是一項非常有用的功能。它讓只讀事務能夠看到資料庫在某個特定時間點的一致狀態，也就是一個 快照，同時又不必鎖住或干擾讀寫事務。

一般來說，MVCC 需要單調遞增的事務 ID。如果某次寫入發生在快照之後（也就是說，寫入的事務 ID 大於快照的事務 ID），那麼快照事務就看不到這次寫入。在單節點資料庫上，用一個簡單的計數器就足以生成事務 ID。

可是，當資料庫分佈在許多機器上，甚至橫跨多個數據中心時，生成全域性單調遞增的事務 ID（覆蓋所有分片）就很困難，因為這需要協調。事務 ID 還必須反映因果關係：如果事務 B 讀取或覆蓋了事務 A 先前寫入的值，B 的事務 ID 就必須大於 A，否則快照將不一致。面對大量短小快速的事務，在分散式系統中生成事務 ID 會成為難以承受的瓶頸。（我們將在 “ID 生成器和邏輯時鐘” 中討論這類 ID 生成器。）

能不能直接把同步日曆時鐘產生的時間戳當作事務 ID？如果時鐘同步能做得足夠好，時間戳的確具備所需屬性：越晚的事務，時間戳越大。當然，問題依舊在於時鐘精度的不確定性。

Spanner 正是以這種方式實現跨資料中心的快照隔離 ^{68 69}。它利用 TrueTime API 報告的時鐘置信區間，依據的是下面這個觀察：假設有兩個置信區間，每個區間都由最早和最晚的可能時間戳組成（A = [A最早, A最晚]，B = [B最早, B最晚]），如果兩個區間不重疊（即 A最早 < A最晚 < B最早 < B最晚），那麼 B 必定發生在 A 之後，不存在任何疑問。只有當兩個區間發生重疊時，我們才無法確定 A 與 B 的先後順序。

為了確保事務時間戳能夠反映因果關係，Spanner 會在提交讀寫事務之前，刻意等待相當於置信區間長度的一段時間。這樣一來，任何可能讀到該資料的事務都會發生在足夠晚的時刻，使它們的置信區間不再重疊。為了儘量縮短等待，Spanner 需要把時鐘不確定性控制得儘可能小；為此，Google 在每個資料中心都部署了 GPS 接收器或原子鐘，從而把時鐘同步誤差控制在大約 7 毫秒以內 ⁴⁵。

嚴格來說，Spanner 並非一定要使用原子鐘和 GPS 接收器：真正重要的是獲得置信區間，精確的時間源只是幫助縮小這個區間。其他系統也開始採用類似方法。例如，YugabyteDB 在 AWS 上執行時可以利用 ClockBound ⁷⁰，還有若干系統也開始在不同程度上依賴時鐘同步 ^{71 72}。

程序暫停

再來看一個在分散式系統中危險使用時鐘的例子。假設某個資料庫的每個分片都只有一個領導者，而且只有領導者可以接受寫入。一個節點怎麼知道自己仍是領導者（沒有被其他節點宣告死亡），因而可以安全地接受寫入呢？

一種辦法是由領導者向其他節點取得一份 租約，它類似於帶有超時的鎖 ⁷³。任何時刻只能有一個節點持有租約。因此，節點拿到租約後，就知道自己在租約到期以前的一段時間內仍是領導者。為保持領導者身份，節點必須在租約到期前定期續租。如果節點失效，就會停止續租；租約到期後，另一個節點便可接管。

可以想象，請求處理迴圈大致如下：

while (true) {
    request = getIncomingRequest();

    // 確保租約至少還剩 10 秒
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

這段程式碼有什麼問題？首先，它依賴同步時鐘：租約到期時間由另一臺機器設定（例如以當前時間加 30 秒來計算），卻要與本地系統時鐘比較。如果兩臺時鐘的偏差超過幾秒，這段程式碼的行為就會變得古怪。

其次，即使把協議改成只使用本地單調時鐘，仍然存在另一個問題：程式碼假定讀取時間（System.currentTimeMillis()）與處理請求（process(request)）之間只會經過極短時間。通常這段程式碼確實執行得很快，預留 10 秒足以確保租約不會在請求處理到一半時過期。

可是，如果程式執行時意外暫停了呢？例如，假設執行緒執行到 lease.isValid() 附近時停了 15 秒，隨後才恢復。在處理請求時，租約很可能早已過期，另一個節點也已接任領導者。然而，沒有任何東西會告訴這個執行緒它剛才停了那麼久；直到迴圈進入下一輪，它才會發現租約已經過期——而在此之前，它可能已經處理了請求，做出了不安全的操作。

認為執行緒可能暫停這麼久，是否合理？很遺憾，完全合理。造成長時間暫停的原因多種多樣：

• 多個執行緒爭用鎖、佇列等共享資源時，執行緒可能把大量時間花在等待上。換用 CPU 核心更多的機器甚至可能讓這類問題進一步惡化，而且爭用問題往往很難診斷 ⁷⁴。
• 許多程式語言執行時（例如 Java 虛擬機器）都帶有 垃圾回收器（GC），偶爾需要停止所有正在執行的執行緒。過去，這類 STW GC 暫停 有時會讓程式停上幾分鐘 ⁷⁵！現代 GC 演算法已經大大緩解了這個問題，但 GC 暫停仍可能相當明顯（參見 “限制垃圾回收的影響”）。
• 在虛擬化環境中，虛擬機器可以被 掛起（暫停所有程序並把記憶體內容儲存到磁碟），隨後再 恢復（還原記憶體內容並從原處繼續執行）。這種暫停可能發生在程序執行的任何時刻，持續時間也沒有上限。這個功能有時用於把虛擬機器從一臺宿主機 實時遷移 到另一臺宿主機而無需重啟；在這種情況下，暫停多久取決於程序寫入記憶體的速率 ⁷⁶。
• 在膝上型電腦和手機等終端使用者裝置上，執行也可能隨時掛起並恢復，例如使用者合上膝上型電腦螢幕時。
• 當作業系統切換到另一個執行緒，或者虛擬機器監控器切換到另一臺虛擬機器時，當前執行緒可能停在程式碼中的任意位置。對虛擬機器而言，被其他虛擬機器佔用的 CPU 時間稱為 竊取時間。如果機器負載很高——也就是有很長的執行緒佇列在等待執行——暫停的執行緒可能要過一陣子才能再次獲得執行機會。
• 如果應用程式執行同步磁碟訪問，執行緒可能暫停下來，等待緩慢的磁碟 I/O 操作完成 ⁷⁷。在許多語言中，即使程式碼沒有明確讀寫檔案，磁碟訪問也可能出人意料地發生。例如，Java 類載入器會在類第一次使用時才載入類檔案，而這可能出現在程式執行的任何時刻。I/O 暫停與 GC 暫停甚至可能相互疊加 ⁷⁸。如果所謂的磁碟其實是網路檔案系統或網路塊裝置（例如 Amazon EBS），I/O 延遲還會受到網路延遲波動的影響 ³¹。
• 如果作業系統允許 換頁到磁碟（分頁），一次簡單的記憶體訪問也可能觸發缺頁錯誤，必須從磁碟把某個頁面載入記憶體。在這項緩慢的 I/O 操作完成以前，執行緒會一直暫停。如果記憶體壓力很大，還可能需要先把另一個頁面換出到磁碟。極端情況下，作業系統會把大部分時間耗在記憶體頁面的換入換出上，幾乎不做實際工作，這叫作 抖動。為了避免這種情況，伺服器通常會禁用分頁——與其冒著發生抖動的風險，不如終止一個程序來釋放記憶體。
• 向 Unix 程序傳送 SIGSTOP 訊號也會令其暫停，例如在 shell 中按 Ctrl-Z。這個訊號會立即停止給程序分配 CPU 週期，直到 SIGCONT 令它恢復；隨後，它會從先前停下的位置繼續執行。即使你的環境通常不用 SIGSTOP，運維人員也可能不小心發出這個訊號。

上述任何事件都可能在任意位置 搶佔 正在執行的執行緒，過一段時間再讓它恢復，而執行緒對此毫無察覺。這個問題類似於保證單機多執行緒程式碼的執行緒安全：不能對時序作任何假定，因為上下文切換與並行執行隨時都可能發生。

在單臺機器上編寫多執行緒程式碼時，我們有不少成熟工具來保證執行緒安全：互斥鎖、訊號量、原子計數器、無鎖資料結構、阻塞佇列等等。遺憾的是，這些工具不能直接套用到分散式系統，因為分散式系統沒有共享記憶體，只有經由不可靠網路傳遞的訊息。

分散式系統中的節點必須假定：自己的執行可能在任意時刻暫停很長時間，哪怕正處於函式執行途中。暫停期間，外部世界仍在繼續運轉，甚至可能因為這個節點遲遲沒有響應而宣告它死亡。最終節點恢復執行時，甚至意識不到自己曾經“睡著”，直到稍後再次讀取時鐘。

響應時間保證

如上所述，在許多程式語言與作業系統中，執行緒和程序都可能暫停任意長的時間。不過，只要投入足夠努力，這些暫停的原因 確實可以 消除。

有些軟體執行在這樣的環境中：如果不能在規定時間內響應，就可能造成嚴重損害。控制飛機、火箭、機器人、汽車及其他實體裝置的計算機，必須快速而且可預測地響應感測器輸入。在這些系統中，軟體必須趕在明確規定的 截止時間 之前響應；錯過截止時間，就可能導致整個系統失效。這樣的系統稱為 硬實時 系統。

例如，汽車的車載感測器檢測到碰撞正在發生時，你絕不會希望安全氣囊因為控制系統恰好遭遇 GC 暫停而延遲彈出。

要在系統中提供實時保證，需要軟體棧的每一層共同支援：需要 實時作業系統（RTOS），保證在規定的時間間隔內為程序分配 CPU 時間；庫函式必須說明最壞情況下的執行時間；動態記憶體分配可能要受到限制，甚至完全禁止（雖然存在實時垃圾回收器，應用程式仍必須確保不會給 GC 安排太多工作）；此外還要進行海量測試與測量，驗證系統確實滿足保證。

這些要求不僅帶來大量額外工作，也嚴重限制了可用的程式語言、庫和工具，因為大多數語言和工具都不提供實時保證。正因如此，實時系統開發極其昂貴，最常用於安全攸關的嵌入式裝置。而且，“實時”並不等於“高效能”——事實上，實時系統的吞吐量可能更低，因為及時響應必須優先於一切（另見 “延遲與資源利用率”）。

對於大多數伺服器端資料處理系統，實時保證既不經濟，也不合適。因此，這些系統只能承受非實時環境帶來的程序暫停與時鐘不穩定。

限制垃圾回收的影響

垃圾回收曾是造成程序暫停的最大原因之一 ⁷⁹。好在 GC 演算法已經有了長足進步：如今，經過適當調優的回收器通常只會暫停幾毫秒。Java 執行時提供併發標記清除（CMS）、垃圾優先（G1）、Z 垃圾回收器（ZGC）、Epsilon 和 Shenandoah 等回收器，分別針對高頻建立物件、大型堆等不同記憶體使用特徵進行最佳化。相比之下，Go 提供的是一種更簡單、嘗試自我最佳化的併發標記清除垃圾回收器。

如果必須徹底避免 GC 暫停，可以選擇完全沒有垃圾回收器的語言。例如，Swift 使用自動引用計數來判斷何時能夠釋放記憶體；Rust 和 Mojo 則透過型別系統追蹤物件的生命週期，讓編譯器判斷記憶體需要保留多久。

也可以繼續使用帶垃圾回收的語言，同時減輕暫停造成的影響。一種做法是把 GC 暫停看作節點短暫的計劃內停機：某個節點進行垃圾回收時，由其他節點處理客戶端請求。如果執行時能夠提前告知應用程式節點即將進行 GC 暫停，應用程式就可以停止向該節點發送新請求，等待它處理完尚未完成的請求，然後趁沒有請求進行時執行 GC。這種技巧能向客戶端隱藏 GC 暫停，並降低響應時間的高百分位數 ^{80 81}。

這種思路還有一個變體：只讓垃圾回收器處理容易快速回收的短命物件，並定期重啟程序，趕在長期存活物件積累到需要執行一次完整 GC 之前 ^{79 82}。每次可以只重啟一個節點，並在計劃重啟前先把流量從該節點遷走，就像滾動升級一樣（參見 第 5 章）。

這些措施無法徹底杜絕垃圾回收暫停，卻能切實減輕其對應用程式的影響。

知識、真相和謊言

到目前為止，本章已經考察了分散式系統與單機程式的不同之處：系統沒有共享記憶體，只能透過延遲不定的不可靠網路來傳遞訊息，還可能遭遇部分失效、不可靠的時鐘和程序暫停。

如果還不熟悉分散式系統，這些問題帶來的後果會讓人極度迷失方向。網路中的一個節點不可能 確切知道 其他節點的任何事情，只能根據收到（或沒有收到）的訊息作出猜測。一個節點只有與另一個節點交換訊息，才能得知對方處於什麼狀態，例如儲存了哪些資料、是否正常執行等等。如果遠端節點沒有響應，就無從得知它的狀態，因為網路問題與節點自身的問題無法可靠地區分。

關於這類系統的討論已經近乎哲學：在系統中，我們究竟知道什麼為真、什麼為假？如果感知和測量的機制都不可靠，我們又能在多大程度上確信自己的認知 ⁸³？軟體系統是否應當服從我們認為物理世界必然遵循的法則，例如因果律？

好在我們不必一路追問到生命的意義。在分散式系統中，可以明確寫出對系統行為所作的假設（即 系統模型），再把實際系統設計成符合這些假設。我們還可以證明某個演算法在特定系統模型中能夠正確執行。這意味著，即使底層系統模型只提供極少保證，也仍然可以實現可靠的行為。

不過，要讓軟體在不可靠的系統模型中表現良好，絕非輕而易舉。本章餘下部分將進一步探討分散式系統中的知識與真相，幫助我們思考可以作出哪些假設，以及希望提供哪些保證。在 第 10 章 中，我們將繼續考察一些分散式演算法：它們在特定假設下提供特定保證。

多數派原則

設想一個存在非對稱故障的網路：某個節點可以收到發給它的所有訊息，但它發出的訊息都會丟失或延遲 ²²。這個節點明明工作得完全正常，也在接收其他節點的請求，可其他節點就是聽不見它的迴應。等到超時後，其他節點由於一直收不到回覆，便宣告它已經死亡。接下來的場面如同噩夢：這個半失聯的節點被拖向墓地，一路掙扎高喊“我還沒死！”——可惜誰也聽不見它的呼喊，送葬隊伍仍以堅忍不拔的決心繼續前進。

在一個沒那麼噩夢般的場景中，半失聯的節點也許會發現自己發出的訊息得不到其他節點的確認，於是意識到網路必定出了故障。然而，其他節點仍會錯誤地宣告它死亡，而它對此無能為力。

第三種場景是，假設某個節點暫停執行一分鐘。在此期間，它既不處理請求，也不傳送響應。其他節點一邊等待、一邊重試，終於失去耐心，宣告它死亡並把它抬上靈車。最終暫停結束，節點的執行緒若無其事地繼續執行。其他節點驚訝地看到，那個本應死去的節點突然精神抖擻地從棺材裡探出頭來，興高采烈地與旁人聊天。剛恢復時，這個節點甚至不知道整整一分鐘已經過去，也不知道自己已經被宣告死亡——在它看來，距離上次和其他節點交談彷彿只過了一瞬間。

這些故事告訴我們，節點未必能相信自己對處境的判斷。分散式系統不能只依賴某一個節點，因為節點隨時可能失效，使系統陷入僵局而無法恢復。因此，許多分散式演算法依賴 法定人數，也就是讓多個節點投票（參見 “讀寫仲裁”）：一項決策必須獲得若干節點的最低票數，藉此減少對任何單個節點的依賴。

宣告節點死亡的決定也是如此。如果達到法定人數的節點宣告另一個節點已經死亡，那麼即使它覺得自己還活得好好的，也必須被視為死亡。單個節點必須服從法定人數作出的決定並下臺。

最常見的法定人數，是超過節點總數一半的絕對多數，當然也可以採用其他形式。多數法定人數讓系統能在少數節點發生故障時繼續工作：三個節點可以容忍一個故障節點，五個節點則可以容忍兩個。與此同時，它仍然是安全的，因為系統中只能形成一個多數派，不可能同時出現兩個作出衝突決定的多數派。我們將在 第 10 章 討論 共識演算法 時，更詳細地介紹法定人數的用法。

分散式鎖和租約

分散式應用程式中的鎖與租約很容易被誤用，也是程式缺陷的常見來源 ⁸⁴。下面來看一種具體的出錯方式。

在 “程序暫停” 中，我們看到租約是一種會超時的鎖：如果原持有者停止響應（可能是因為它崩潰了、暫停太久，或與網路斷開），租約就可以交給新的持有者。當系統要求某種東西只能有一個時，就可以使用租約。例如：

• 只允許一個節點擔任資料庫分片的領導者，以避免腦裂（參見 “處理節點故障”）。
• 只允許一個事務或客戶端更新特定資源或物件，以免併發寫入將其損壞。
• 一項大型處理作業中的每個輸入檔案只應由一個節點處理，避免多個節點重複執行同一份工作而白白浪費計算資源。

值得仔細想一想：如果多個節點同時相信自己持有租約——也許是程序暫停造成的——會發生什麼？對第三個例子而言，後果不過是浪費一些計算資源，並不嚴重；但在前兩個例子中，資料可能丟失或損壞，嚴重得多。

例如，圖 9-4 展示了鎖實現錯誤導致的資料損壞。（這並非純粹的理論問題：HBase 曾經就有這個缺陷 ^{85 86}。）假設你想確保某個儲存服務裡的檔案一次只能由一個客戶端訪問，因為多個客戶端同時寫入會損壞檔案。於是，你要求客戶端在訪問檔案之前，先向鎖服務取得租約。這類鎖服務通常用共識演算法來實現，我們將在 第 10 章 中進一步討論。

問題正是 “程序暫停” 所討論的情形：持有租約的客戶端如果暫停太久，租約就會過期。另一個客戶端此時可以取得同一檔案的租約，並開始寫入。等暫停的客戶端恢復後，它誤以為自己的租約依然有效，也繼續寫入檔案。於是便出現了腦裂：兩個客戶端的寫入彼此衝突，最終損壞檔案。

圖 9-5 展示了另一個後果類似的問題。這個例子裡沒有程序暫停，只有客戶端 1 崩潰。就在崩潰前，客戶端 1 向儲存服務發出了一項寫請求，但請求在網路中延遲了很久。（回想 “實踐中的網路故障”，資料包有時會延遲一分鐘以上。）等寫請求抵達儲存服務時，租約早已超時，客戶端 2 已經取得租約併發出了自己的寫入。結果便是類似 圖 9-4 的資料損壞。

用柵欄機制隔離殭屍與延遲請求

殭屍 一詞有時用來形容這樣的原租約持有者：它還不知道自己已經失去租約，仍把自己當作當前持有者行事。既然無法徹底杜絕殭屍，就必須確保它們不能以腦裂的形式造成任何破壞。這稱為用 柵欄機制 隔離殭屍。

有些系統試圖透過關停殭屍來隔離它，例如斷開它的網路連線 ⁹、透過雲服務商的管理介面關閉虛擬機器，甚至直接切斷機器電源 ⁸⁷。這種做法稱為 STONITH，即“擊斃另一個節點”。遺憾的是，它有幾個問題：無法防範 圖 9-5 所示的超長網路延遲；所有節點可能彼此關停 ¹⁹；而等到殭屍被發現並關閉時，也許早已為時過晚，資料已經損壞。

圖 9-6 展示了一種更健壯的柵欄機制，既能防範殭屍，也能防範延遲請求。

假設鎖服務每次授予鎖或租約時，還會返回一個 柵欄令牌。這是一個每次授予鎖都會增大的數字，例如由鎖服務負責遞增。隨後可以要求客戶端每次向儲存服務傳送寫請求時，都必須帶上自己當前的柵欄令牌。

在 圖 9-6 中，客戶端 1 取得租約及令牌 33，隨後卻長時間暫停，導致租約過期。客戶端 2 接著取得租約及令牌 34（令牌值始終遞增），並向儲存服務傳送帶令牌 34 的寫請求。稍後，客戶端 1 恢復執行，也向儲存服務傳送寫請求，其中帶著自己的令牌 33。然而，儲存服務記得自己已經處理過令牌值更高（34）的寫入，因此會拒絕令牌 33 的請求。剛取得租約的客戶端必須立刻向儲存服務執行一次寫入；一旦這次寫入完成，所有殭屍都會被隔離在外。

如果使用 ZooKeeper 作為鎖服務，可以把事務 ID zxid 或節點版本 cversion 用作柵欄令牌 ⁸⁵。在 etcd 中，修訂號與租約 ID 共同發揮類似作用 ⁸⁹。Hazelcast 的 FencedLock API 則會顯式生成柵欄令牌 ⁹⁰。

這種機制要求儲存服務能夠檢查寫入所攜帶的令牌是否已經過時。另一種辦法是讓服務支援類似原子比較並設定（CAS）的寫入：只有從當前客戶端上次讀取物件以後，沒有其他客戶端寫過該物件，寫入才會成功。物件儲存服務就支援這類檢查：Amazon S3 稱之為 條件寫入，Azure Blob Storage 稱之為 條件標頭，Google Cloud Storage 則稱之為 請求前置條件。

多副本隔離

如果客戶端只需寫入一個支援這類條件寫入的儲存服務，那麼鎖服務多少有些多餘 ^{91 92}，因為完全可以直接依託該儲存服務來分配租約 ⁹³。不過，有了柵欄令牌以後，也可以把它用於多個服務或副本，確保原租約持有者在所有這些服務上都被隔離。

例如，假設儲存服務是一個採用最後寫入者勝來解決衝突的無主複製鍵值儲存（參見 “無主複製”）。在這樣的系統中，客戶端直接向每個副本傳送寫入，各副本根據客戶端分配的時間戳，自行決定是否接受寫入。

如 圖 9-7 所示，可以把寫入者的柵欄令牌放在時間戳最高有效的若干位或數字中。這樣就能確保，新租約持有者生成的任何時間戳，都大於原租約持有者生成的所有時間戳，即使原持有者的寫入實際發生得更晚。

在 圖 9-7 中，客戶端 2 的柵欄令牌為 34，因此它生成的所有以 34… 開頭的時間戳，都大於客戶端 1 生成的任何以 33… 開頭的時間戳。客戶端 2 成功寫入達到法定人數的一組副本，但無法連線副本 3。因此，殭屍客戶端 1 稍後嘗試寫入時，這次寫入雖然會被副本 1 和 2 忽略，卻可能在副本 3 上成功。這不成問題，因為後續的仲裁讀會優先選擇客戶端 2 那個時間戳更大的寫入，而讀修復或反熵過程最終會覆蓋客戶端 1 寫入的值。

從這些例子可以看出，假定任何時刻只有一個節點持有租約並不安全。所幸，只要稍加留意，就可以藉助柵欄令牌防止殭屍與延遲請求造成任何破壞。

拜占庭故障

柵欄令牌能夠發現並阻止 無意間 出錯的節點，例如尚未發現租約已經過期的節點。但如果節點蓄意破壞系統保證，只需傳送帶有偽造柵欄令牌的訊息，就能輕易繞過這種防護。

本書假定節點雖然不可靠，卻是誠實的：它們可能因為故障而響應緩慢或永不響應，也可能因為 GC 暫停或網路延遲而持有過時狀態；但我們假定，只要節點 確實 作出響應，它說的就是“真話”——至少據它自己所知，它是在遵守協議規則。

如果節點有可能“撒謊”，也就是發出任意錯誤或損壞的響應，分散式系統問題就會困難得多。例如，一個節點可能在同一輪選舉中投出多張互相矛盾的票。這種行為叫作 拜占庭故障，而在這種互不信任的環境中達成共識的問題，則稱為 拜占庭將軍問題 ⁹⁴。

如果某些節點發生故障、不遵守協議，或有惡意攻擊者干擾網路時，系統仍能繼續正確執行，就稱這個系統具有 拜占庭容錯 能力。這類問題在某些特定情形下確實很重要。例如：

• 在航空航天環境中，輻射可能破壞計算機記憶體或 CPU 暫存器裡的資料，使節點以任意且不可預測的方式迴應其他節點。系統失效的代價極其高昂——例如飛機墜毀導致機上人員全部遇難，或火箭撞上國際空間站——因此飛行控制系統必須能夠容忍拜占庭故障 ^{98 99}。
• 在有多方參與的系統中，部分參與者可能企圖欺騙或詐騙其他人。此時，節點不能輕信另一個節點發來的訊息，因為訊息可能帶有惡意。比特幣等加密貨幣及其他區塊鏈，就可以看作一種無需依賴中央權威，讓彼此不信任的各方就某筆交易是否發生達成一致的方式 ¹⁰⁰。

不過，對本書討論的系統而言，通常可以放心假定不存在拜占庭故障。資料中心裡的所有節點都受你的組織控制，因而有望值得信任；輻射水平也足夠低，記憶體損壞並非主要問題——儘管人們已經在考慮把資料中心送入軌道 ¹⁰¹。多租戶系統中的租戶彼此並不信任，但系統依靠防火牆、虛擬化和訪問控制策略把租戶相互隔離，而不是使用拜占庭容錯。讓系統實現拜占庭容錯的協議代價很高 ¹⁰²，而具有容錯能力的嵌入式系統又依賴硬體層面的支援 ⁹⁸。對大多數伺服器端資料系統來說，部署拜占庭容錯方案的成本高得並不現實。

Web 應用程式的確必須預料到，Web 瀏覽器等由終端使用者控制的客戶端可能作出任意乃至惡意的行為。這也正是輸入驗證、資料清理和輸出轉義如此重要的原因，例如它們可以防止 SQL 注入與跨站指令碼攻擊。不過，我們通常不會為此使用拜占庭容錯協議，只需讓伺服器充當權威，決定哪些客戶端行為可以接受、哪些不可以。在沒有這種中央權威的點對點網路中，拜占庭容錯才更為重要 ^{103 104}。

軟體缺陷也可以看作拜占庭故障，但如果所有節點部署的都是同一套軟體，拜占庭容錯演算法也救不了你。大多數拜占庭容錯演算法要求超過三分之二的節點正常執行（例如四個節點中最多隻能有一個發生故障）。若想用這種辦法防範軟體缺陷，就得準備同一軟體的四種獨立實現，並寄希望於缺陷只出現在其中一種實現裡。

同理，如果某種協議能保護我們免受漏洞、安全失陷和惡意攻擊，當然很有吸引力。遺憾的是，這同樣不現實：在大多數系統中，攻擊者既然能夠攻陷一個節點，多半也能攻陷所有節點，因為它們很可能執行相同的軟體。因此，身份認證、訪問控制、加密和防火牆等傳統機制，仍然是抵禦攻擊者的主要手段。

弱形式的謊言

雖然我們通常假定節點是誠實的，但仍值得在軟體中加入一些機制，防範較弱形式的“撒謊”，例如硬體問題、軟體缺陷或配置錯誤產生的無效訊息。這些機制算不上完整的拜占庭容錯，因為它們擋不住意志堅定的攻擊者；但作為提高可靠性的手段，它們既簡單又務實。例如：

• 硬體問題，或作業系統、驅動程式、路由器等元件中的缺陷，確實可能損壞網路資料包。TCP 與 UDP 內建的校驗和通常能夠發現損壞的資料包，但偶爾也會漏檢 ^{105 106 107}。一般只需一些簡單措施就足以防範這類損壞，例如在應用層協議中加入校驗和。TLS 加密連線也能抵禦資料損壞。
• 可公開訪問的應用程式必須仔細清理所有使用者輸入，例如檢查數值是否落在合理範圍內，並限制字串長度，防止攻擊者透過分配巨量記憶體來造成拒絕服務。防火牆後的內部服務也許可以放寬輸入檢查，但協議解析器仍然最好保留基本校驗 ¹⁰⁵。
• NTP 客戶端可以配置多個伺服器地址。同步時，客戶端會聯絡所有伺服器，估算各自的誤差，並檢查大多數伺服器是否就某個時間範圍達成一致。只要大部分伺服器正常，配置有誤、報告錯誤時間的 NTP 伺服器就會被識別為離群值，並排除在同步過程之外 ³⁹。與只依賴一臺伺服器相比，使用多臺伺服器能讓 NTP 更加健壯。

系統模型與現實

人們已經設計了許多演算法來解決分散式系統問題。例如，我們將在 第 10 章 中考察共識問題的解決方案。要真正有用，這些演算法必須能夠容忍本章討論的分散式系統中的各種故障。

演算法的編寫方式不應過度依賴其執行環境中具體的硬體與軟體配置。這又要求我們以某種方式，把系統中預期會發生的故障型別形式化。為此，我們定義 系統模型：它是一種抽象，用來說明演算法可以作出哪些假設。

關於時序假設，通常使用以下三種系統模型：

同步模型

同步模型假定網路延遲、程序暫停和時鐘誤差都有上界。這並不表示時鐘完全同步，也不表示網路延遲為零；它只是意味著，我們知道網路延遲、暫停和時鐘漂移永遠不會超過某個固定上限 ¹⁰⁸。對大多數實際系統而言，同步模型並不現實，因為正如本章所討論的，無界延遲和暫停確實可能發生。

部分同步模型

部分同步是指系統在 大多數時候 都像同步系統一樣執行，但偶爾會突破網路延遲、程序暫停和時鐘漂移的界限 ¹⁰⁸。對許多系統來說，這是一個現實的模型：絕大多數時候，網路與程序表現得相當規矩，否則我們什麼事情也做不成；但我們也必須正視這樣一個事實——任何時序假設都有可能偶爾失效。發生這種情況時，網路延遲、程序暫停和時鐘誤差都可能變得任意之大。

非同步模型

在這種模型中，演算法不能作出任何時序假設——事實上，它甚至沒有時鐘可用（因而也不能使用超時）。有些演算法可以針對非同步模型來設計，但這種模型限制極大。

除了時序問題，還必須考慮節點失效。常見的節點系統模型包括：

崩潰停止故障

在 崩潰停止（或 故障停止）模型中，演算法可以假定節點只有一種失效方式：崩潰 ¹⁰⁹。節點可能在任意時刻突然停止響應，此後便永遠消失，再也不會回來。

崩潰恢復故障

我們假定節點可能在任意時刻崩潰，也可能在一段未知時間後重新開始響應。在崩潰恢復模型中，節點擁有能在崩潰後保留資料的穩定儲存（即非易失性磁碟儲存），但記憶體中的狀態會丟失。

效能下降和功能不全

除了崩潰與重啟，節點還可能變慢：它們也許仍能響應健康檢查，卻慢得無法完成任何實際工作。例如，千兆網路介面可能因為驅動程式缺陷，吞吐量突然跌到 1 Kb/s ¹¹⁰；面臨記憶體壓力的程序可能把大部分時間花在垃圾回收上 ¹¹¹；磨損的 SSD 可能表現得極不穩定；高溫、聯結器鬆動、機械振動、電源問題、韌體缺陷等也會影響硬體 ¹¹²。這類情形稱為 跛行節點、灰色失效 或 慢失效 ¹¹³，甚至可能比徹底失效的節點更難處理。還有一種相關問題：程序不再執行原本應做的某些工作，其他功能卻仍在繼續，例如後臺執行緒崩潰或死鎖時 ¹¹⁴。

拜占庭（任意）故障

節點可能做出任何行為，包括像上一節所述那樣欺騙其他節點。

對現實系統建模時，帶崩潰恢復故障的部分同步模型通常最有用。它允許出現無界網路延遲、程序暫停和慢節點。那麼，分散式演算法該如何應對這種模型呢？

定義演算法的正確性

要定義一個演算法怎樣才算 正確，可以描述它必須具備哪些 屬性。例如，排序演算法的輸出具有這樣一項屬性：對輸出列表中的任意兩個不同元素，位於左側的元素都小於位於右側的元素。這不過是用形式化語言定義一份列表何謂“有序”。

同理，我們也可以列出分散式演算法應具備的屬性，以此定義它怎樣才算正確。例如，如果演算法要為鎖生成柵欄令牌（參見 “用柵欄機制隔離殭屍與延遲請求”），我們可能要求它滿足以下屬性：

唯一性

任意兩個柵欄令牌請求都不能返回相同的值。

單調序列

如果請求 x 返回令牌 t**x，請求 y 返回令牌 t**y，而且 x 在 y 開始以前已經完成，那麼 t**x < t**y。

可用性

請求柵欄令牌且沒有崩潰的節點，最終會收到響應。

如果演算法在某個系統模型允許發生的所有情形下，始終滿足這些屬性，就可以說它在該系統模型中是正確的。然而，如果所有節點都崩潰，或所有網路延遲都突然變成無限長，那麼任何演算法都不可能完成工作。面對一個允許系統徹底失效的模型，我們怎樣才能仍然給出有用的保證呢？

安全性與活性

為了說清這個問題，有必要區分兩類不同的屬性：安全性 與 活性。在剛才的例子中，唯一性 和 單調序列 屬於安全屬性，可用性 則屬於活性屬性。

兩者究竟有何區別？一個明顯線索是，活性屬性的定義中往往含有“最終”二字。（沒錯，你已經猜到了：最終一致性 就是一項活性屬性 ¹¹⁵。）

安全性常被非正式地定義為 壞事不會發生，活性則是 好事最終會發生。不過，最好不要過度解讀這種通俗說法，因為“好”與“壞”屬於價值判斷，並不太適合用來描述演算法。安全性與活性的嚴格定義要精確得多 ¹¹⁶：

• 如果安全屬性遭到違反，我們可以指出它在哪一個具體時刻被破壞。例如，唯一性遭到破壞時，可以找到返回重複柵欄令牌的那次具體操作。安全屬性一旦被違反，就無法撤銷——損害已經造成。
• 活性屬性正好相反：它在某個時刻可能尚未成立（例如節點已經發出請求，卻還沒收到響應），但未來始終還有滿足它的希望（也就是最終收到響應）。

區分安全屬性與活性屬性的一個好處，是能幫助我們應對棘手的系統模型。對分散式演算法，通常要求安全屬性在系統模型允許的所有情形下都 始終 成立 ¹⁰⁸。也就是說，即使所有節點崩潰，或整個網路失效，演算法仍必須保證絕不返回錯誤結果，因而安全屬性依舊得到滿足。

而對活性屬性，我們可以附加條件。例如，可以規定只有在多數節點尚未崩潰、且網路最終能從中斷中恢復時，請求才必須得到響應。部分同步模型的定義要求系統最終回到同步狀態——也就是說，任何一次網路中斷都只能持續有限時間，隨後會得到修復。

將系統模型對映到現實世界

安全屬性、活性屬性和系統模型，對推理分散式演算法的正確性非常有用。但當演算法真正落地實現時，現實世界混亂的一面又會回來找麻煩；這時便清楚地看到，系統模型只是對現實的簡化抽象。

例如，崩潰恢復模型中的演算法通常假定穩定儲存裡的資料能挺過崩潰。但如果磁碟資料損壞了，或因硬體錯誤、配置錯誤而被清空，會發生什麼 ¹¹⁷？如果伺服器存在韌體缺陷，重啟時明明硬碟連線無誤，卻無法識別它們，又會怎樣 ¹¹⁸？

法定人數演算法（參見 “讀寫仲裁”）依賴節點記住自己聲稱已經儲存的資料。如果節點會患上“失憶症”，忘掉先前儲存的資料，就會破壞法定人數條件，進而破壞演算法的正確性。或許還需要定義一種新系統模型：假定穩定儲存在崩潰後通常得以保留，但偶爾也會丟失。可這樣的模型又會變得更加難以推理。

演算法的理論描述可以直接宣告，假定某些事情絕不會發生——在非拜占庭系統中，我們確實必須對哪些故障可能發生、哪些不可能發生作出假設。然而，真實實現也許仍要包含程式碼，處理那些理論上“不可能”發生的事情；哪怕處理方式歸結為 printf("Sucks to be you") 和 exit(666)，也就是把殘局留給人類運維人員收拾 ¹¹⁹。（這正是計算機科學與軟體工程之間的一項區別。）

這並不是說理論化、抽象化的系統模型毫無價值——恰恰相反。它們極其有助於把真實系統的複雜性提煉成一組可管理、可推理的故障，使我們能夠理解問題，並嘗試用系統化的方法加以解決。

形式化方法和隨機測試

怎樣知道一個演算法確實滿足所需屬性？併發、部分失效與網路延遲會產生海量潛在狀態。我們需要保證這些屬性在每一種可能狀態下都成立，還要確保沒有遺漏任何邊界情況。

一種辦法是對演算法進行形式化驗證：用數學語言描述演算法，再運用證明技術，證明它在系統模型允許的所有情形下都滿足所需屬性。證明演算法正確，並不表示它在真實系統中的 實現 必然始終行為正確。不過，這是非常好的一步，因為理論分析能夠發現演算法中的隱患；這些問題在真實系統中可能潛伏很久，直到某些異常情況打破了你的假設（例如時序假設）才突然發作。

把理論分析與經驗性測試結合起來，驗證實現的行為是否符合預期，是一種穩妥做法。基於屬性的測試、模糊測試和確定性模擬測試（DST）等技術都利用隨機化，在各種不同情形下測試系統。Amazon Web Services 等公司已經成功地把這些技術組合運用於許多產品 ^{120 121}。

模型檢查與規範語言

模型檢查器 是幫助驗證演算法或系統行為是否符合預期的工具。演算法規範要用 TLA+、Gallina 或 FizzBee 等專門設計的語言來編寫。藉助這類語言，我們可以專注於演算法行為，不必糾纏於程式碼實現細節。模型檢查器隨後會系統地嘗試各種可能發生的情況，利用模型來驗證不變數是否在演算法的所有狀態中都成立。

嚴格來說，模型檢查無法證明演算法的不變數在每一種可能狀態下都成立，因為大多數現實演算法的狀態空間是無限的。要真正驗證所有狀態，需要給出形式化證明；這雖然可行，但通常比執行模型檢查器困難得多。因此，使用模型檢查器時，通常要把演算法模型縮減成一個可以完全驗證的近似版本，或是給執行設定某種上限（例如限制最多可以傳送多少條訊息）。這樣一來，只會在更長執行過程中出現的缺陷就無法被發現。

即便如此，模型檢查器仍然在易用性與發現隱蔽缺陷的能力之間取得了很好的平衡。CockroachDB、TiDB、Kafka 和許多其他分散式系統，都使用模型規範來發現並修復缺陷 ^{122 123 124}。例如，研究人員藉助 TLA+ 證明，檢視戳複製（VR）的文字描述存在歧義，可能導致資料丟失 ¹²⁵。

按照設計，模型檢查器執行的並非實際程式碼，而是一個只描述協議核心思想的簡化模型。這樣更容易系統地探索狀態空間，但也帶來規範與實現逐漸偏離的風險 ¹²⁶。可以檢查模型與真實實現的行為是否等價，不過這需要在真實實現中插樁 ¹²⁷。

故障注入

許多缺陷只有在機器或網路發生失效時才會觸發。故障注入是一種有效（有時也相當嚇人）的技術，用來驗證系統實現遇到問題時是否仍會按預期工作。思路很簡單：向正在執行的系統環境注入故障，再觀察系統如何反應。注入的故障可以是網路失效、機器崩潰、磁碟損壞、程序暫停——凡是你能想到的計算機出錯方式都可以嘗試。

故障注入測試通常在與系統實際生產環境十分相似的環境中執行；有些團隊甚至直接在生產環境中注入故障。Netflix 透過 Chaos Monkey 工具推廣了這種做法 ¹²⁸。在生產環境中注入故障通常稱為 混沌工程，我們在 “可靠性與容錯” 中已經討論過。

執行故障注入測試時，首先要部署被測系統，以及故障注入協調者和指令碼。協調者負責決定注入哪些故障、何時注入；本地或遠端指令碼則負責讓單個節點或程序發生失效。注入指令碼會利用許多不同工具來觸發故障：Linux 程序可以用 kill 命令暫停或終止，磁碟可以用 umount 解除安裝，網路連線可以透過防火牆規則中斷。檢查故障注入期間以及之後的系統行為，就能確認系統是否一如預期。

觸發不同失效所需的工具五花八門，因此故障注入測試寫起來頗為繁瑣。常見做法是採用 Jepsen 之類的故障注入框架來簡化流程。這類框架集成了多種作業系統，並預置了大量故障注入器 ¹²⁹。Jepsen 在許多廣泛使用的系統中都成功發現過關鍵缺陷，成效極為顯著 ^{130 131}。

確定性模擬測試

確定性模擬測試（DST）也已成為模型檢查與故障注入的一種流行補充。它探索狀態空間的方式與模型檢查器相似，但測試的是真實程式碼，而不是模型。

在 DST 中，模擬器會自動執行大量隨機化的系統執行。模擬期間的網路通訊、I/O 和時鐘計時都由模擬元件取代，讓模擬器能夠精確控制各種時序與失效場景下，所有事情發生的先後順序。這樣一來，模擬器所能探索的情形遠多於手寫測試或故障注入。如果測試失敗，還可以重新執行，因為模擬器知道觸發失敗的準確操作序列；故障注入則無法對系統實施如此細粒度的控制。

DST 要求模擬器能夠控制網路延遲等一切非確定性來源。要讓程式碼變得確定，通常採用以下三種策略之一：

應用程式層

有些系統從一開始就以便於確定性執行程式碼為目標進行構建。例如，FoundationDB 是 DST 領域的先驅之一，它基於名為 Flow 的非同步通訊庫構建。Flow 為開發者提供了一個接入點，可以把確定性網路模擬注入系統 ¹³²。類似地，TigerBeetle 是一款原生支援 DST 的線上事務處理（OLTP）資料庫。它把系統狀態建模為狀態機，所有狀態變更都在單一事件迴圈內發生。再配合時鐘等確定性模擬原語，這種架構便能以確定性方式執行 ¹³³。

執行時層

帶非同步執行時與常用庫的程式語言，為引入確定性提供了接入點。可以用單執行緒執行時，強制所有非同步程式碼順序執行。例如，FrostDB 修改 Go 執行時，讓 goroutine 依次執行 ¹³⁴。Rust 的 madsim 庫也採用類似方式。Madsim 為 Tokio 非同步執行時 API、AWS S3 庫、Kafka 的 Rust 庫以及許多其他元件提供確定性實現。應用程式只需換用確定性的庫與執行時，無需修改自身程式碼，就能獲得確定性的測試執行。

機器層

除了在執行時修改程式碼，也可以讓整臺機器變得確定。這個過程十分精細：機器必須對所有通常帶有非確定性的呼叫給出確定性響應。Antithesis 等工具透過構建定製的虛擬機器監控器來實現這一點，由它把通常非確定性的操作替換成確定性操作。從時鐘到網路再到儲存，一切都必須納入考慮。完成後，開發者就能在虛擬機器監控器內的一組容器中執行整個分散式系統，得到一個完全確定的分散式系統。

DST 的優勢不止是能夠重放。Antithesis 等工具發現較為罕見的行為時，會把一次測試執行分叉成多個子執行，藉此嘗試探索應用程式中的更多程式碼路徑。確定性測試通常使用模擬時鐘與網路呼叫，因此執行速度可以快於現實中的時間流逝。例如，TigerBeetle 的時間抽象可以模擬網路延遲和超時，而無需真的等待足夠長時間讓超時觸發。這類技術讓模擬器能夠以更快速度探索更多程式碼路徑。

確定性的力量

非確定性正是本章所討論的所有分散式系統難題的核心：併發、網路延遲、程序暫停、時鐘跳變和崩潰都會以不可預測的方式發生，而且系統每次執行時都可能不同。反過來說，如果能讓系統變得確定，許多事情都會大為簡化。

事實上，讓事物具有確定性是個簡單而強大的思想，在分散式系統設計中反覆出現。除了確定性模擬測試，前面幾章還介紹過多種利用確定性的方式：

• 事件溯源的一項關鍵優勢（參見 “事件溯源與 CQRS”），是可以確定性地重放事件日誌，重新構建派生的物化檢視。
• 工作流引擎（參見 “持久化執行與工作流”）依賴確定性的工作流定義，藉此提供持久化執行語義。
• 我們將在 “使用共享日誌” 中討論的 狀態機複製，會在每個副本上獨立執行相同的確定性事務序列，從而複製資料。我們已經見過這種思想的兩個變體：基於語句的複製（參見 “複製日誌的實現”），以及透過儲存過程序列執行事務（參見 “儲存過程的利弊”）。

不過，要讓程式碼具有徹底的確定性，仍須十分小心。即使已經消除了所有併發，並用確定性模擬替換 I/O、網路通訊、時鐘和隨機數生成器，系統裡仍可能殘留非確定性。例如，在某些程式語言中，遍歷雜湊表元素的順序可能不確定；是否會觸及資源上限（記憶體分配失敗、棧溢位）同樣具有非確定性。

總結

本章討論了分散式系統中可能發生的各種問題，其中包括：

• 每當試圖透過網路傳送資料包時，它都可能丟失或遭到任意延遲。響應同樣可能丟失或延遲，因此只要沒有收到響應，你就無從知道訊息是否送達。
• 即使已經盡力配置 NTP，一個節點的時鐘仍可能與其他節點嚴重不同步，也可能突然向前或向後跳變。依賴這樣的時鐘非常危險，因為你多半無法可靠估計其置信區間。
• 程序可能在執行到任意位置時暫停很長時間，被其他節點宣告死亡；隨後它又恢復執行，卻完全沒有意識到自己曾經暫停。

可能出現這類 部分失效，正是分散式系統的決定性特徵。只要軟體試圖完成任何涉及其他節點的事情，就可能偶爾失敗、莫名其妙地變慢，或徹底不作響應（最終超時）。在分散式系統中，我們會把容忍部分失效的能力構建到軟體裡，使整個系統即使有部分元件損壞，也能繼續工作。

要容忍故障，第一步是 檢測 故障，可就連這一步也很困難。大多數系統都沒有準確判斷節點是否已經失效的機制，因此多數分散式演算法只能依靠超時來判斷遠端節點是否仍然可用。然而，超時無法區分網路失效與節點失效，而網路延遲的波動有時又會讓系統錯誤地懷疑某個節點已經崩潰。跛行節點更加難以處理：它們仍在響應，卻慢得根本做不了任何有用的工作。

即便檢測出了故障，要讓系統容忍它也並不容易：機器之間既沒有全域性變數，沒有共享記憶體，沒有公共知識，也沒有其他形式的共享狀態 ⁸³。節點甚至無法就“現在幾點”達成一致，更不用說更深刻的問題了。資訊從一個節點流向另一個節點的唯一途徑，就是經由不可靠網路傳送。重大決策不能安全地交給單個節點，因此我們需要協議來召集其他節點參與，並爭取讓達到法定人數的節點達成一致。

如果你習慣於在單臺計算機那種數學般完美的理想環境中編寫軟體——同一個操作總會確定性地返回相同結果——那麼轉向分散式系統混亂的物理現實，難免會感到震驚。反過來，分散式系統工程師常常認為，只要能在單臺計算機上解決，問題就微不足道 ⁴。事實上，如今單臺計算機確實能做很多事情。如果能夠避免開啟潘多拉魔盒，把工作簡單地留在一臺機器上，例如使用嵌入式儲存引擎（參見 “嵌入式儲存引擎”），通常就值得這樣做。

不過，正如 “分散式與單節點系統” 所討論的，可伸縮性並不是採用分散式系統的唯一理由。容錯與低延遲（把資料放在地理位置更靠近使用者的地方）同樣重要，而這些目標無法靠單個節點實現。分散式系統的力量在於，原則上它可以在服務層面永不停機，因為所有故障和維護都能在節點層面處理。（當然在實踐中，如果把一項錯誤配置釋出到所有節點，分散式系統照樣會被徹底擊垮。）

本章還稍稍岔開話題，探討網路、時鐘和程序的不可靠性是否屬於無可避免的自然法則。答案是否定的：網路可以提供硬實時響應保證與有界延遲，只不過代價極其高昂，硬體資源的利用率也會隨之降低。大多數非安全攸關係統都會在便宜而不可靠與昂貴而可靠之間選擇前者。

本章始終在討論問題，呈現出一幅頗為黯淡的圖景。下一章將轉向解決方案，討論一些專為應對分散式系統問題而設計的演算法。

參考文獻