徹底厘清真實世界中的分布式系統

編者的話：本文從一個實踐者的角度，首先介紹了分布式系統的一些理論結果，例如 FLP 不可能性和 CAP 定理等；然后介紹了構建實際分布式系統最重要的一個原則：端到端；最后討論了實際系統經常用到的協調服務。

求知之路漫長喲，不知何處是盡頭。我們一路求索，終于有跡可循。這為我們帶來了希望，驅散了恐懼。

譯者注：「Down the Rabbit Hole」是一句俗語，源自小說《愛麗絲漫游仙境》（Alice's Adventures in Wonderland），比喻對未知的探索。

分布式系統領域的文獻雖然多，我作為一名實踐者，卻發現如果你不是科班出身，就不知道怎樣入門或者如何綜合這么多的知識。這篇文章提供了一個不是那么學術的思路，幫助你理解分布式系統的各種設計思想。也就是說，本文沒提出什么新的設計思想，而是構建了一個框架，人們可以按照這個框架去研究一些有影響的設計思想。文中列出的參考文獻，是研究分布式系統的絕佳起點。特別是，我們將審視幾個形式化結果，以及不那么形式化的一些設計原則，這是我們討論分布式系統設計的基礎。

這是你最后的機會，一旦選定就沒得回頭了。要是分布式系統領域也有紅藥丸/藍藥丸就好了。分布式系統是如此復雜，我們徹底搞清楚它吧。

譯者注：這一段的開頭引用《黑客帝國》（The Matrix）中 Neo 的話。選擇紅藥丸，回到現實世界，有可能是痛苦的；選擇藍藥丸，繼續生活在幻想的幸福當中。這里的含義似乎是你是選擇理解真實的分布式系統（過程可能很痛苦），還是繼續保持無知的幸福呢？

指導原則

為了厘清分布式系統的設計，很重要的一點是明確立論的指導原則或者說是定理，其中最基礎的一個可能是「兩將軍問題」，首先由 Akkoyunlu 等人在論文 「網絡通信設計中的一些約束和權衡」 中提出，而在 1975 年版和 1978 年版的 《數據庫操作系統注記》 中， Jim Gray 對兩將軍問題的討論，使得這個問題開始被人們所熟知。兩將軍問題表明：通過不可靠網絡通信的兩個進程不可能達成一致的決定。兩將軍問題非常接近于必須保證下列條件成立的二元共識問題（“攻擊”或者“不攻擊”）：

• 終止（Termination）: 所有正確的進程都會決定某個取值（活性/liveness）；
• 合法性（Validity）： 所有正確的進程，如果它決定的取值是 v ，那么這個 v 必然是由某個正確的進程提議的(非平凡/non-triviality)；
• 誠實性（Integrity）： 所有正確的進程，最多只決定一個取值 v ，并且這個 v 是正確的取值（安全性/safety）；
• 一致性（Agreement）： 所有正確的進程決定的取值是相同的（安全性/safety）。

很顯然，任何有用的分布式算法都涉及活性和安全性屬性。如果再考慮到網絡是異步的、存在崩潰失效，問題就更復雜了：

• 異步：消息有可能被無限延遲，但是最終會被投遞；
• 崩潰失效：進程有可能無限停機。

對上述情境的思考，引導我們去了解據稱是最重要的分布式系統理論結果之一： FLP 不可能性，由 Fischer, Lynch 和 Patterson 在 1985 年論文 「只要存在一個可能失效的進程就不可能達成共識」 中首次提出。這個結果表明兩將軍問題是不可能解決的。在崩潰-失效模型中，如果進程完成工作且給出響應的耗時沒有上限，我們就不可能區分下面兩種情況：進程已經崩潰或者只是響應的耗時比較長。 FLP 結果還表明，在異步環境中，只要至少有一個進程有可能失效，就不存在能夠確定解決共識問題的算法。也就是說，存在崩潰-失效的異步環境中，不可能存在完美的失效檢測器。

譯者注：把 failure 翻譯為「失效」，意味著系統已經完全不能工作；把 fault 翻譯為「故障」，意思是系統組件有問題，不能按照原先設計目的正常地工作。

討論故障容忍（fault-tolerant）系統時，很重要的一點是把拜占庭故障（實質上就是任意的故障）考慮在內。此類故障包括但不限于：試圖破壞系統的攻擊。例如，一次安全攻擊可能會生成或者偽造消息。 拜占庭將軍問題 是兩將軍問題的泛化版，它描述的就是拜占庭故障。拜占庭故障容忍是指檢測出或者屏蔽掉大量的拜占庭故障，保護系統免受威脅。

我們為什么如此重視共識？因為它是解決分布式系統設計中很多重要問題的關鍵。領導人選舉（leader election）要實現共識，這樣才能動態選出一個協調者，避免單點失效。分布式數據庫要實現共識，這樣才能保證不同節點的數據是一致的。消息隊列要實現共識，這樣才能支持消息投遞事務或保證消息投遞的順序。分布式初始化（init）系統要實現共識，這樣才能協調不同的進程。共識根本就是分布式程序設計的一個重要問題。

人們 一次又一次的證明 ，無論是局域網還是廣域網，它們經常是不可靠的，總體上也是異步的。這給分布式系統的設計帶來真切而巨大的挑戰。

這些不可能性結果不單單有學術意義，受此啟發，大量分布式系統及設計開始涌現，這些系統在網絡失效時提供了不同的保證。

L. Peter Deutsch 寫的 「有關分布式計算的幾個謬論」 是研究分布式系統理論的絕佳起點。文中列舉了很多新手會誤以為真的假設，其中第一條就是“網絡是可靠的”。這些實際上不成立的假設包括：

1. 網絡是可靠的。
2. 延遲為零。
3. 帶寬是無限的。
4. 網絡是安全的。
5. 拓撲不會改變。
6. 肯定有一個管理員。
7. 傳輸的代價為零。
8. 網絡是同質的。

最近， CAP 定理被 認真審視 ，人們 爭論 這個定理的作用是否被夸大了。盡管如此， CAP 定理仍然是一個有用的工具，它能幫助我們建立分布式系統的基本權衡因素，認清廠商玩的花招。 Gilbert 和 Lynch 合寫的 「對 CAP 定理的看法」 明確了易出故障（fault-prone）系統固有的安全性（safety）與活性（liveness）之間的權衡，而 Fox 和 Brewer 合寫的 「完備度、完成概率和可擴展的容忍系統」 從更實用角度描述了 CAP 定理的特征。我將一直毫不含糊地說， CAP 定理在分布式系統領域的地位非常重要，對分布式系統設計者和實踐者來說，它具有重大的意義。

重燃希望

根據前面這些理論結果，很多分布式算法，包括實現線性化操作、序列化事務和領導人選舉的算法，都沒什么用。果真如此嗎？當然不是。只要精心設計，分布式系統不用靠撞大運就能保持正確性。

首先需要指出， FLP 定理并沒有說共識是無法達成的，而是說在有限時間內不一定能達成。其次， FLP 定理討論的是不受控制的系統。在同步系統中，進程間消息投遞的耗時有一個上限；在異步系統中則沒有固定的限制。實際的系統一般表現為部分同步（partial synchrony）， Dwork 和 Lynch 在 「部分同步系統的共識」 一文中描述了部分同步的兩個模型。在第一個模型中，上限是固定的但是預先不知道；在第二個模型中，上限是已知的，但只是從某個未知的時間點 T 開始才保證這個上限成立。Dwork 和 Lynch 針對這兩種模型（搭配不同的故障模型），分別給出相應的能夠容忍故障的共識協議。

Chandra 和 Toueg 在 「可靠分布式系統中的不可靠失效檢測器」 介紹了不可靠失效檢測器的概念。每一個進程都有一個本地、外部的失效檢測器，這個檢測器有可能出錯。失效檢測器監控系統中的部分進程，維護一個它懷疑已經崩潰進程的列表。檢測失效的方法很簡單：檢測器定期向某個進程發送打招呼消息，如果超過某個耗時上限（2×消息來回的最大可能耗時），仍然沒有收到該進程的響應，就把它列入懷疑名單。檢測器有可能犯錯，把正確的進程列入懷疑名單中。不過，如果檢測器在后續時段又收到進程的響應，會自動糾錯，把這個進程從懷疑名單去掉。在一個條件稍微放松的系統模型中，只要有失效檢測器，即使它是不可靠的，也能解決共識問題。

共識保證了不同的進程就某個取值達成一致，而原子化廣播（atomic broadcast）保證了每一個進程按照相同的順序投遞同一個消息。在上面那篇論文中，作者證明了共識和原子化廣播彼此是等價的。因此， FLP 等不可能性結果同樣適用于原子化廣播。有些協調服務，如 Apache ZooKeeper ，就用到原子化廣播。

在《可靠且安全的分布式程序設計導論》一書中，Cachin, Guerraoui 和 Rodrigues 指出很多實踐系統可以被認為是部分同步的：

分布式系統通常表現為一個同步系統。更準確地說，我們所知的大部分系統，在大部分時間內，投遞消息的耗時有一個上限。當然，在有的時段，系統又是異步的。例如，網絡過載，或者某個進程因為內存不夠而運行得緩慢。更典型的例子，進程收發消息的緩沖區有可能發生溢出，導致消息丟失，此時投遞消息的耗時肯定超過通常的上限。消息重傳有助于保證通信鏈接的可靠性，同時又引入不可預測的延遲。從這個意義上，實際的系統是部分同步的。

我們注意到，部分同步只是說最終保證消息投遞的耗時有一個固定的限制，但最終是指什么時候，沒有明確指出。類似地，我們稱這樣的系統是最終同步的。這里的最終同步，并不是說過了一段時間后系統就永遠是同步的，也不是說系統開始是異步的，一段時間之后變成同步的。相反，最終同步是指系統有時是異步的，此時消息投遞的耗時有可能是無限長，但是也存在系統同步的時段，足夠一個算法做有用的工作或者運行完。關鍵是要記住，異步系統不提供任何定時保證。

最后，在 「分布式共識所需的最少同步」 一文中， Dolev, Dwork 和 Stockmeyer 描述了一種分布式共識協議叫做 t-復原（t-resilient），它能在最多 t 個進程失效時保證系統仍然正常地工作。本文給出幾個關鍵的系統參數和同步條件，描述不同的參數和條件對算法的影響。可以證明，在某些模型中共識是可達的，在另外一些模型中則不行。

依靠法定多數（quorum），能夠實現容忍故障的共識。直覺上，如果大多數進程能就每一個決定達成一致，即使出現故障，也至少有一個進程了解完整的歷史。

在某些系統模型中，不可能達成確定性共識，許多有用的算法也因此無法實現。但是，大部分實際系統對應的模型能夠規避這一點。不管怎樣，這都顯示出分布式系統固有的復雜性，以及解決特定問題所需的嚴格性。

從理論轉向實踐

上述理論有什么實踐意義呢？對于初學者而言，這意味著分布式系統沒有表面看起來那么簡單。不認識到這一點，人們就會 在文檔中不確切地描述權衡因素 ，還有很多因為認識不足而導致 數據丟失和違反安全性 的例子。我們需要重新考慮分布式系統的設計方式，把焦點從系統屬性及保證轉向行業規則和應用的不變量。

我最鐘意的一篇論文是 Saltzer, Reed 和 Clark 寫的 「系統設計中的端到端原則」 。這篇論文很好讀，它提出了一個非常有說服力的設計原則，幫助人們搞清楚究竟應該在分布式系統的哪一層實現所需的功能。端到端原則是說在系統的底層實現功能有可能是多余的，或者與付出的代價相比，這樣做的用處不大。很多時候，外部保證比內部保證更有意義，也就是說應該在應用層提供保證，而不是依靠子系統、中間件或者系統的底層提供保證。

我們以“設計周全的文件傳輸”為例說明端到端原則。某個文件保存在計算機 A 的硬盤的文件系統中， A 通過通信網絡與計算機 B 相連。現在要求把這個文件從計算機 A 無損地傳輸到計算機 B ，在此過程中有可能出現各種失效。換言之，這是一個文件傳輸應用程序，依賴底層存儲和網絡的抽象。開發者考慮到下列問題有可能發生：

1. 文件剛寫到計算機 A 的磁盤時，數據是正確的。如果現在讀這個文件，有可能因為磁盤存儲系統的硬件故障而讀到錯誤的數據。
2. 無論是在計算機 A 還是 B 上，文件系統、文件傳輸程序或者數據通信系統在緩沖和復制文件數據時都可能出錯。
3. 計算機 A 或 B 的處理器或者內存在緩沖和復制時有可能暫時出錯。
4. 通信系統有可能丟掉或者改變網絡包數據、丟包或者多次投遞同一個網絡包。
5. 任何一個主機都有可能在文件傳輸過程中（已經完成了未知比例的數據傳輸）崩潰。

這些本質上都屬于拜占庭問題。如果我們逐個考慮這些威脅，很顯然，即使我們在底層實現了問題處理程序，高層的應用仍然必須檢查問題是否存在。例如，通信系統依靠校驗和、重試和網絡包排序提供可靠的數據傳輸。這只是消除了上述第 4 個威脅。為了克服其余的威脅，文件傳輸應用程序仍然需要端到端校驗和重試機制。

在底層構建可靠性，代價太大。不光需要不少的投入，這么做也純屬多余。實際上，這雖然減少應用層重試的頻率，卻在底層了增加不必要的負擔，最終降低系統的性能。應該只靠端到端校驗和重試保證正確性，底層的實現對此沒什么幫助。通信系統的可靠性和正確性并非那么很重要，在通信層保證復原性并不能減少應用層的負擔。實際上，僅僅依靠底層不可能保證正確性，因為消除第 2 個威脅要求編寫正確的程序，但是并非所有的程序都是由文件傳輸應用開發者自己編寫的。

根本上，在底層實現功能會引發兩個問題。首先，底層不清楚應用的需求和語義，這就意味著在底層實現的功能往往是不充分的，在應用層仍然需要實現類似的功能，這就造成邏輯的重復，如前面例子所示。其次，其他依賴底層的應用，即使不需要這些功能，也得承擔相應的代價。

Saltzer, Reed 和 Clark 把端到端原則視為系統設計的“奧坎姆剃刀”原則，他們認為，端到端原則有助于指導設計系統的層次組織和確定功能在哪一層實現。

因為經常是先確定通信子系統之后，才知道要運行的上層應用，所以設計者必須頂住誘惑，不要試圖為用戶提供超出需要的功能。了解端到端原則，有助于增強抵抗力。

需要特別指出的是，端到端原則不是萬能藥。它是一個指導原則，幫助設計者從端到端角度思考解決方案，確認應用的需求，考慮失效的模式。最后，它提供了一種理念：把功能往系統上層移，靠近用到這項功能的應用程序。當然，凡事都有例外。有時為了性能優化，選擇在底層實現功能。總之，端到端原則主張底層應當避免承擔任何超出需要的責任。在 Google Bigtable 論文 的“教訓”部分有類似的論述：

我們學習到的另外一個教訓是，在搞清楚新特性將被如何使用之前，不要添加這個新特性。例如，剛開始時，我們計劃提供支持通用事務的 API 。由于我們沒有馬上使用這些 API ，就沒有實現它們。現在，我們有很多運行在 Bigtable 上的實際應用，我們能夠檢驗這些應用的真實需求，結果發現大部分應用只需要單行事務。其他需要分布式事務的使用情景，最重要的一個是用分布式事務維護二級索引，我們計劃添加特別的機制滿足這一需求。這種新機制的通用性比不上分布式事務，但是更有效率（尤其是執行橫跨幾百行的更新操作時），也更適合我們采用的跨數據中心樂觀復制的模式。

接下來的討論中，我們把端到端原則視為一個常識。

到底由誰來保證

一般來說，我們要靠健壯的算法、事務管理器和協調服務來維護一致性和應用的正確性。這會引發兩個問題：這些服務經常是不可靠的；還經常成為嚴重的系統性能瓶頸。

分布式協調算法很難做到萬無一失。即使是像兩階段提交這樣有效的協議，也容易受崩潰和網絡分區的影響而無法正常工作。更能容忍故障的協議，像 Paxos 和 Raft ，它們的擴展性不佳，只能運行在比較小的集群內，也不能跨越廣域網。像 ZooKeeper 這樣的共識系統 決定了整個系統的可用性 ，一旦它宕機了，你的麻煩就大了。出于性能的考慮，法定多數通常設得較小，這種情況并不少見。

于是乎，協調系統作為一種基礎設施，變得既復雜又脆弱。這太諷刺了，因為本來是想利用協調系統降低整個系統的脆弱性。另外一方面，消息中間件很大程度上是依靠協調為開發者提供下列有關消息投遞的保證：有且只有一次、順序、事務等等。

從傳輸協議到企業消息代理，對投遞保證的依賴都屬于分布式系統設計中的反模式。很難正確地處理投遞的語義。尤其是對分布式消息投遞而言， 你想要的往往不是你需要的 。重要的是審視其中涉及的權衡因素，了解這些因素如何影響系統的設計（ 和用戶體驗！ ），權衡這些因素以便做出更好的設計決定。

由于各種失效模式的存在，提供強保證變得很難。實際上，根據前面我們討論的兩將軍問題和 FLP 不可能性結果，有些保證， 像有且只有一次的投遞，甚至是不可能提供的 。如果你想提供有且只有一次投遞、有序投遞的保證，往往屬于超出需要的過度設計和實現。系統變得難以部署和維護、脆弱和運行慢。提供保證的服務，如果能完美地運行，開發者的開發工作肯定變得更輕松。現實情況是這些服務很多時候不能完美地運行。你會在凌晨一點收到警報，不得不查找問題的源頭： 從監控服務看，RabbitMQ 明明一切正常，為什么整個系統卻接連出現問題？

如果部署在生產環境的系統依賴此類保證，那你遲早會遇到一次（往往不止一次）上述的麻煩。最終，所謂的保證就不存在了，因此導致的后果可大可小。這種設計系統的方式不光危險，也不可取，尤其是當你運維一個大規模系統，特別看重系統的吞吐或者需要提供關鍵的服務等級約定時。

分布式事務顯然會影響性能。協調的代價是昂貴的，因為進程不能單獨繼續運行，這會限制系統的吞吐、可用性和擴展性。 Peter Bailis 有一個非常棒的演講 「沉默是金：避免協調的系統設計」 ，他詳細討論了協調的代價以及如何避免協調。他提到一個特別的例子，其中分布式事務會導致系統的吞吐下降 400 倍。

如果不需要協調，系統可以無限橫向擴展，從而極大提高系統的吞吐和可用性。但是有時協調是不可避免的。在 《數據庫系統中的協調避免》 一書中， Bailis 等人回答了一個關鍵問題：為了保證正確性，在哪種情況下協調是不可避免的？他們提出一個屬性叫不變量交匯點（invariant confluence, I-confluence），它是安全、無協調、可用及收斂的執行的充分必要條件。 I-confluence 的本質是在應用層定義和保持不變性，因為我們在這里可以用應用的語義而不是底層數據庫操作來定義正確性。

不知道應用程序的正確性定義（例如， I-confluence 用到的那些不變性），在讀寫模型中，能夠保證的最佳正確性是序列化。

給定事務集，以及統一分散狀態的合并函數，就可以判定 I-confluence 是否成立。如果成立，就意味著存在一種保證不變性的無協調執行策略。如果不成立，意味著這樣的策略不存在，協調就是必需的。由此可見， I-confluence 能夠幫我們識別出何時需要協調，何時不需要。由于是在應用層定義和保持不變性，就不會存在超出需要的設計。

回想一下，分布式計算的同步性（synchrony）只是對時間做的假設，所以同步（synchronization）從根本上是兩個或兩個以上進程隨著時間推移進行的協調。我們知道，無需協調的系統能提供最優的性能和可用性，因為每個進程完全獨立運行。然而，根據 I-confluence 理論，這樣的分布式系統沒什么用或者說是不可能的。 Christopher Meiklejohn 在 Strange Loop 大會做的演講 「分布式、最終一致的計算」 中，用汽車打比方來解釋協調。駕駛汽車需要摩擦力，但是只能有非常少量的摩擦點。太多的摩擦點會出問題或者降低效率。如果把物理時間看做摩擦力，完全消除它是不可能的，因為這是問題的本質屬性。但是我們可以盡量減少它在系統中的使用。通常，可以選用邏輯時間取代物理時間，例如，使用 Lamport 時鐘或者其他沖突消除技術。有關這一思路的經典介紹，是 Lamport 寫的書 《分布式系統的時間、時鐘和事件順序》 。

系統在執行延遲敏感操作時通常會完全放棄協調。這是非常自然的權衡選擇，只不過要在文檔中清楚地指出這一點。不幸的是， 現實往往并非如此 ，這很不應該。 I-confluence 提供了一個有用的協調避免框架，我們還能從中學到更多：重新審視我們現在設計分布式系統的方式，看起來這些方式與端到端原則有些背道而馳。

在底層實現功能，意味著一開始我們就要付出代價——序列化事務、線性化讀寫和協調。這好像違反了端到端原則。應用程序并不關心原子性、隔離級別或者線性化，它關心的是兩個用戶共享同一個 ID 或者兩個訂單預定了同一個房間或者銀行賬戶有負結余，數據庫是不知道這些的。有時，諸如此類的規則甚至不需要任何代價昂貴的協調。

如果把應用規則和約束編碼成基礎設施層理解的語言，這會引發幾個問題。首先，必須把應用語義無縫地轉換成底層操作。以消息傳送為例，應用程序并不關心投遞送達的保證，它關心的是這個消息要干什么。其次，我們不能使用很多通用的解決方案，有時甚至要專門處理特別的情況。這種處理的實際擴展性如何是未知的。第三，降低了性能，這本來是可以避免的（I-confluence 已經揭示了這一點）。最后，一切都依賴基礎設施，希望它能按照設計運行—— 往往并非如此 。

身為消息平臺團隊的一員，我經歷過無數次像下面這樣的對話：

相反，如果重新評估系統間交互和系統 API 及語義，把其中一些特性從基礎設施移到應用層，我們就能構建更健壯、更容錯和更高性能的系統。就消息傳遞而言，真的需要基礎設施層保證先入先出順序嗎？系統存在失效情況下要保證分布式消息的順序，同時還要提供高可用性，這太難了，代價高。如果消息是可交換的，就沒必要保證消息的順序。同樣，投遞事務需要又慢又脆弱的協調，還無法提供應用層的保證。如果消息是冪等的，就不需要事務，重試就行了。如果需要應用層的保證，那就在應用層構建，基礎設施可保證不了。

我特別喜歡 Gregor Hohpe 寫的 「咖啡店不用兩階段提交」 。這篇文章揭示了，如果我們仿效真實世界解決分布式系統問題，解決方案會非常簡單。我有信心設計更好的系統，有時我們只需換個角度思考問題。事物的運作方式蘊含著一定的道理，這可沒用到計算機或者復雜的算法。

不要試圖用脆弱、笨重的抽象來掩蓋復雜性，相反，在設計決策時識別問題，端到端思考，直面問題。追尋分布式系統之道的道路漫長而艱難，現在就開始吧。

感謝 Tom Santero 幫忙審閱本文的前期草稿。文中有不準確的地方，表達的各種意見，都由我自己負責。

原文鏈接： From the Ground Up: Reasoning About Distributed Systems in the Real World （翻譯：柳泉波）