當討論分布式系統時，我們都會討論些什么？
我一直在學習有關分布式系統的知識，學習時間不算短了。老實說，只要你開始鉆研分布式系統，知識點好像學不完似的，一個接一個。分布式系統領域的文獻太多了，包括許多大學發表的論文，還有很多書籍可選。像我這樣的絕對新手，很難決定應該閱讀哪些論文或者購買哪些書籍。
同時，我還發現了幾個博客作者，他們在博客中推薦這篇或者那篇論文，聲稱這是分布式系統工程師（先別糾結這個詞的含義）應該必知必會的。于是，我的閱讀列表越來越長： FLP, Zab, 時間, 分布式系統中的時鐘和事件順序， Viewstamped Replication, Paxos, Chubby ，等等。問題是，很多時候他們沒有說明為什么要閱讀這篇或者那篇論文。為了滿足好奇心，不分主次地學習所有知識，這種想法我挺喜歡。不過，我們還是應該確定不同內容的閱讀優先級，畢竟，每天只有 24 小時呀。
除了有大量的論文和研究資料，分布式系統領域的書也很多。我買了挺多本。我翻看其中的章節，發現有些書的書名起得很有吸引力，貌似是我感興趣的內容，實則不然，或者說，這些書的內容并沒有涉及我想解決的問題。
在寫這篇博客的同時，我仍然在持續學習分布式系統知識，所以請讀者有點耐心，明白本文難免會存在錯誤。已經寫好的內容，以后我會盡力做相應的擴充。
在這里，我想告訴大家，我已經在好幾個會議上講過這篇博客的內容，演講稿： What We Talk About When We Talk About Distributed Systems
我在斯德哥爾摩 Erlang 用戶大會上的演講視頻： What We Talk About When We Talk About Distributed Systems
主要概念
確定分布式系統算法的分類，主要依據是搞清楚算法的各種屬性。例如，定時模型、進程間通信類型和失效模型等等。本文涉及的主要概念包括：
- 定時模型（Timing Model）
- 進程間通信（Interprocess Communication）
- 失效模式（Failure Modes）
- 失效檢測器（Failure Detectors）
- 領導人選舉（Leader Election）
- 共識（Consensus）
- 法定人數（Quorums）
- 分布式系統中的時間
- 快速瀏覽 FLP
- 結束語
- 參考文獻 </ul>
- 消息傳遞模型：進程間相互發送消息；
- 共享內存模型：不同的進程讀寫共享的變量，實現數據的共享。 </ul>
- 強完備性：到最后，每一個崩潰的進程都會被每一個正常運行的進程永久地懷疑；
- 最終強精準性：最終，沒有任何正常運行的進程會被其他正常的進程所懷疑。 </ul>
- 終止：每一個正確的進程最終都會決定一個值；
- 合法性：如果某個進程最終決定取值是 _v_ ，那么這個 _v_ 必然是由某個進程提議的；
- 誠實：沒有進程會決定兩次；
- 一致性：兩個正確的進程，它們的決定不會不同。 </ul>
- 《可靠且安全的分布式程序設計導論》第 5 章
- 《同步消息傳遞系統中的容錯一致》
- 《容錯、異步分布式系統中的通信與一致抽象》 </ul>
- Marcos K. Aguilera. 2010. Stumbling over consensus research: misunderstandings and issues. In Replication, Bernadette Charron-Bost, Fernando Pedone, and André Schiper (Eds.). Springer-Verlag, Berlin, Heidelberg 59-72.
- Paulo Sérgio Almeida, Carlos Baquero, and Victor Fonte. 2008. Interval Tree Clocks. In Proceedings of the 12th International Conference on Principles of Distributed Systems (OPODIS ‘08), Theodore P. Baker, Alain Bui, and Sébastien Tixeuil (Eds.). Springer-Verlag, Berlin, Heidelberg, 259-274.
- Kenneth P. Birman. 2012. Guide to Reliable Distributed Systems: Building High-Assurance Applications and Cloud-Hosted Services. Springer Publishing Company, Incorporated.
- Mike Burrows. 2006. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th symposium on Operating systems design and implementation (OSDI ‘06). USENIX Association, Berkeley, CA, USA, 335-350.
- Christian Cachin, Rachid Guerraoui, and Luis Rodrigues. 2014. Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer Publishing Company, Incorporated.
- Tushar Deepak Chandra and Sam Toueg. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (March 1996), 225-267.
- Umberto Eco. 2013. Inventing the Enemy: Essays. Mariner Books.
- Colin J. Fidge. 1988. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference 10 (1) , 56–66.
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1983. Impossibility of distributed consensus with one faulty process. In Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS ‘83). ACM, New York, NY, USA, 1-7.
- Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463-492.
- Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.
- Leslie Lamport. 1998. The part-time parliament. ACM Trans. Comput. Syst. 16, 2 (May 1998), 133-169.
- Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
- Moni Naor and Avishai Wool. 1998. The Load, Capacity, and Availability of Quorum Systems. SIAM J. Comput. 27, 2 (April 1998), 423-447.
- Brian M. Oki and Barbara H. Liskov. 1988. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In Proceedings of the seventh annual ACM Symposium on Principles of distributed computing (PODC ‘88). ACM, New York, NY, USA, 8-17.
- Diego Ongaro and John Ousterhout. 2014. In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX conference on USENIX Annual Technical Conference (USENIX ATC’14), Garth Gibson and Nickolai Zeldovich (Eds.). USENIX Association, Berkeley, CA, USA, 305-320.
- M. Pease, R. Shostak, and L. Lamport. 1980. Reaching Agreement in the Presence of Faults. J. ACM 27, 2 (April 1980), 228-234.
- Stefan Poledna. 1996. Fault-Tolerant Real-Time Systems: The Problem of Replica Determinism. Kluwer Academic Publishers, Norwell, MA, USA.
- Michel Raynal. 2010. Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems (1st ed.). Morgan and Claypool Publishers.
- Michel Raynal. 2010. Fault-tolerant Agreement in Synchronous Message-passing Systems (1st ed.). Morgan and Claypool Publishers.
- Benjamin Reed and Flavio P. Junqueira. 2008. A simple totally ordered broadcast protocol. In Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware (LADIS ‘08). ACM, New York, NY, USA, , Article 2 , 6 pages.
- Justin Sheehy. 2015. There Is No Now. ACM Queue
- Marko Vukolic. 2012. Quorum Systems: With Applications to Storage and Consensus. Morgan and Claypool Publishers. </ul>
定時模型
定時模型有三種：同步模型，異步模型和部分同步模型。同步模型的使用最簡單。所有組件在所謂的同步輪次（synchronous
round）中同時執行算法步驟。在同步模型中，消息送達的耗時是已知的，每個進程的速度也是確定的，即每個進程執行一個算法步驟的耗時是確定的。同步模 型的主要問題是它不能很好地反映真實世界，與分布式系統的差別就更大了。在分布式系統中，我們向另外一個進程發送消息，肯定希望自己行大運，因為只有這 樣，才能保證消息一定發送到目標進程。好在我們可以利用同步模型獲得理論結果，再把結果轉換到其他模型。例如，在同步模型中時間是有保證的，如果一個問題 在同步模型中都解決不了，那么在其他模型中，沒有了時間的保證（例如，完美失效檢測器就是這樣一個模型），就更不可能解決這個問題了。
異步模型的使用相對復雜。在異步模型中，每個組件自行決定算法步驟的執行順序，每一步的耗時也沒有保證。雖然 異步模型的描述很簡單，也更接近真實世界，但是它仍然算不上正確地反映了真實世界。例如，在異步模型中，一個進程響應請求的時間有可能是無限長，但是在真 實的項目中，一般會為請求設置一個超時限制，如果在此期間沒有收到響應，將會中止請求并且報告異常。異步模型帶來的一個難點是如何確認一個進程的活躍度條 件（liveness condition）。在最著名的不可能性結果當中，其中一個就是有關異步模型的： “只要有一個進程可能會失效就不可能達成共識”（Impossibility of Consensus with one Faulty Process），也就是說，不可能區分下列兩種情況：（1）進程失效了；（2）進程沒有失效，但是它需要耗費無限長的時間去響應一條消息。
在 部分同步模型中，每個組件都了解一些關于定時的信息，它們要么使用近似同步的時鐘，要么大致了解消息送達的耗時或者每個進程執行一個算法步驟的耗時。
Nancy Lynch 寫的書 《分布式算法》，就是按照上述三種定時模型組織內容的。
進程間通信
這部分討論分布式系統的不同進程之間如何交換信息，包括兩類：記住一點，我們可以做到：使用一種消息傳遞算法，構建一個分布式共享的內存對象。可讀可寫的寄存器就是這樣一種實現，在很多分布式系統書籍中都可以見到這個例子。有些作者還使用隊列和堆棧來描述一致性屬性，例如， 線性化（linearizabilty）。大家不要弄混“共享內存”的兩種含義：第一種是指不同的進程讀寫同一個共享的變量，這是實現數據共享的一種方法；第二種是指在消息傳遞之上構建的共享內存抽象，剛剛已經講過。
在理解基于消息傳遞模型的算法時，還必須弄清楚進程之間是哪一種鏈接（可以理解為進程之間的信道）。不同種類的鏈接抽象為算法提供的保證也不相 同。例如，完美鏈接能夠保證消息的可靠送達，不會重復發送消息；它保證消息會且只會一次送達。顯然，現實世界并非如此。當算法設計者在設計盡量接近真實的 模型時，他們會使用其他類型的鏈接抽象。請牢記，即使完美鏈接并非那么真實，它仍然有用。例如，如果我們能證明，即使鏈接是完美的我們也無法解決某個問 題，那么所有的相關問題也將是不可解的。在討論鏈接時，研究者通常會假定消息順序是“先入先出”的， Zab 就是一個例子。
失效模式
我以前寫過一篇文章 “分布式系統中的失效模式”， 不過仍然值得在這里說道說道。進程的失效模式是分布式系統模型的一個屬性，它是對進程失效種類的假設。崩潰-結束（crash-stop）失效模式的假設 是：進程一直是正確的，直到它發生崩潰；崩潰之后，這個進程不會被恢復。還有崩潰-恢復（crash-recovery）失效模式，進程崩潰后會被恢復。 有些算法還會把進程恢復到崩潰之前的狀態。要做到這一點，恢復后的進程要么從持久存儲中讀取以前的數據，要么與同一群組的其他進程通信，獲取所需的數據。 需要指出的是，在有些群組成員算法中，一個崩潰之后再恢復的進程并不等同于沒崩潰之前的原始進程。二者是否等同，取決于這是一個動態群組還是一個固定群 組。還有一種失效模式叫做忽略失效模式（omission failure mode），它的假設是進程不能接收或者發送消息。忽略有兩種：進程接收不到消息，或者進程發送不了消息。為什么要了解這個呢？想想這種情景，實現分布式 緩存的一組進程，如果其中一個進程無法應答其他進程的請求，只要它能收到其他進程的請求，那么這個進程的狀態就是最新的，它仍然可以響應來自客戶的讀請 求。
一種更復雜的失效模式叫做拜占庭失效模式或者任意失效模式（Byzantine or arbitrary failures mode）：進程有可能向同伴發送錯誤的信息；進程可能是冒充的；應答給其他進程的數據是正確的，但是篡改了本地數據庫的內容，等等。
在設計一個分布式系統時，必須考慮清楚要應對的進程失效類別。Birman （參見 《可靠的分布式系統指南》）認為，一般來說我們不需要應對拜占庭失效。他引用了在 Yahoo! 完成的工作，得出一個結論：崩潰失效比拜占庭失效更為常見。
失效檢測器
有了定時模型和進程失效模式的假設，我們就可以構建報告系統狀態的抽象——失效檢測器，即檢測某個進程是否已經崩 潰，或者懷疑這個進程已經崩潰。完美失效檢測器從不虛報進程失效。假定系統是崩潰-結束失效模式加上同步定時模型，我們只需使用超時就能實現一個完美失效 檢測器：要求進程定期向檢測器報到，報到消息肯定能送達給失效檢測器（同步模型能夠保證這一點）；如果報到消息沒有如期送達，我們可以斷定該進程已經崩 潰。在實際的系統中，不能假定消息送達的耗時，也不能保證進程執行每個步驟的耗時。這時候，我們可以構建一個失效檢測器 p ，如果進程 q 在超時限制 N 毫秒內沒有回答，那么檢測器會報告進程 q 可能已經崩潰。如果后來 q 又開始應答了，那么 p 將把 q 從懷疑已經崩潰的名單中剔除。因為檢測器不知道它與 q 之間的實際網絡延遲，又不想再把 q 添加到懷疑名單中（事實已經證明 q 沒有崩潰），所以它會增大 N 的取值，保證 q
有足夠的報到時間。如果在某個時間點 q 真的崩潰了，檢測器首先把它列入懷疑名單，并將一直保留在那里（因為 q 永遠不會再報到了）。要了解這個算法，請閱讀 《可靠且安全的分布式程序設計指南》一書的“最終完美失效檢測器”部分，講得更好。
失效檢測器通常有兩個屬性：完備性和精準性。最終完美失效檢測器具有：
失效檢測器是異步模型中解決共識問題的關鍵。在 FLP 論文中，提出了很多著名的不可能性結果。這篇論文指出，在異步的分布式系統中，如果進程有可能失效，那么就不可能達成共識。要達成共識，就必須為系統引入一個 能夠規避上述問題的失效檢測器。
領導人選舉
與失效檢測相反的一個問題是，如何判定一個進程沒有崩潰，它因此能夠正確地工作。網絡中其他進程會信賴這個進程，把它當作能夠協調分布式行動的領導人。像 Raft 或者 Zab 這樣的協議就依賴領導人進程來協調行動。協議中有一個領導人，意味著不同節點的地位變得不對稱，非領導人節點將成為跟隨者。領導人節點因此成為很多操作的瓶頸。選擇什么協議，取決于我們 要解決什么樣的問題。有時，我們并不想使用需要領導人選舉的協議。記住，大部分通過某種共識獲得一致性的協議，都包含一個領導人進程和一組跟隨者進程。這 樣的例子包括 Paxos 、 Zab 或者 Raft 。
共識
共識（consensus 或 agreement）問題是由 Pease ， Shostak 和 Lamport 在論文 “在存在失效的情況下達成一致”首先提出來的。他們是這么描述的：容錯系統通常要求提供一種手段，使得獨立的處理器或者進程能夠達成某種精確的相互一致。例如，一個冗余系統的多個處理器可能需要定期同步它們的內部時鐘。或者每個處理從某個時變的輸入傳感器讀取的數值都有稍微不同，它們需要確定一個統一的值。所 以，共識是指獨立的進程之間達成一致。針對某一個問題，這些進程提議了一些值，像它們的傳感器的當前取值，然后根據這些值就共同的行動達成一致。例如，一 輛轎車包含多個提供剎車溫度水平信息的傳感器。這些傳感器的讀數可能不同，因為它們的精度等不一樣。但是汽車的防抱死制動系統需要它們達成一致，這樣才能 確定需要施加多少壓力給剎車。這就是一個在我們日常生活中解決的共識問題。 《容錯的實時系統》這本書解釋了在汽車行業的分布式系統中遇到的共識及其他問題。
實現某種形式共識的進程，它的作用是對外顯露一個API ，包括提議和決定功能。在共識的開始階段，進程提議一個值，然后根據系統中提議的所有值，決定一個最終的值。共識算法必須滿足下列屬性：終止 （Termination）、合法性（Validity）、誠實（Integrity）和一致性（Agreement）。例如，對于常規共識，
更多細節，請參考上面提到的原始論文。還有一些很棒的參考書：
法定人數
法定人數（Quorum）是設計容錯分布式系統的工具，它是能表征系統特征的進程的交集，其中某些進程有可能失效。舉個例子，假設某個算法遵循崩潰失效模式，由 N 個進程組成。只要大多數進程成功地應用了某個操作（例如，寫入數據庫），就可以說已經有了進程的法定人數。只要只有少數進程崩潰，即不超過 N/2-1 個進程崩潰，那么大多數進程仍然知曉應用到系統的最后操作。例如， Raft
在提交日志到系統時就用到了由大多數進程構成的法定人數。領導人向跟隨者發出日志復制請求，只要有一半的服務器有應答，領導人立即把這一日志項應用到它的 狀態機。領導人加上一半服務器，已經構成了大多數。這樣做的好處是， Raft 不必等待所有的服務器都應答日志復制的 RPC 請求之后才開始復制操作。
再舉一個例子，限定每次只能有一個進程可以訪問共享的資源。保衛資源的進程組成了集合 S 。當進程 p 要訪問資源時，它首先要向 S 中的大多數進程征求許可，大多數進程授權它可以訪問資源。現在，系統中另外一個進程 q 也要訪問這個資源，但是它永遠獲得不了大多數保衛進程的許可和授權。只有當進程 p 釋放資源后，進程 q 才有可能訪問這個資源。更多細節，見論文
“法定人數系統的負載、容量和可用性”。
法定人數并不總是指進程的大多數。有時，為了保證操作的成功，需要更多的進程形成法定人數，例如，由 N 個可能出現拜占庭失效的進程構成的進程組。此時，如果 f 表示可容忍的最多失效進程數，那么法定人數將是大于 (N + f) / 2 。參見 《可靠且安全的分布式程序設計導論》。
如果你對這個話題感興趣，有一本專門講分布式系統法定人數的書：
《法定人數系統及其在存儲和共識中的應用》
分布式系統中的時間
理解時間及其后果，是分布式系統最大的問題之一。在日常生活中，我們都習慣了事件一個接一個發生，按照完美定義的 “在……之前發生”（happend before）的順序。如果是一系列分布式進程，它們交換消息和訪問資源都是并發的。我們該如何判斷事件的先后發生順序？要回答此類問題，不同的進程必須共享一個同步時鐘，還要準確地知道通過網絡交換信息的耗時、 CPU 調度任務的耗時等等。顯然，在現實系統中不可能做到這一點。有一篇討論上述問題的影響深遠的論文，標題是 “時間，時鐘和分布式系統中的事件順序”。這篇論文引入了邏輯時鐘的概念。邏輯時鐘是為系統中每個事件分配一個數字的方法。這些數字與實際的時間無關，而是與分布式系統節點對事件的處理有關。
邏輯時鐘算法有很多種，像 向量時鐘和 區間樹時鐘。
我推薦一篇討論分布式系統時間的文章， Justin Sheehy 寫的 “沒有現在”，很有意思的討論。
我認為，時間及其在分布式系統中引起的問題，是需要理解的關鍵概念。 我們必須摒棄同時性（simultaneity）的想法。同時性的想法源自“絕對知識”的老觀念，我們以前認為絕對知識是可以獲得的。物理定律告訴我們，即使是光也需要時間才能從一個地方達到另外一個地方，這樣，當光到達我們的眼睛時，我們的大腦會處理光傳遞的信息。這是一種舊的世界觀。Umberto Eco
在 《發明敵人》這本書的“絕對和相對”一章中討論了上述想法。
快速瀏覽 FLP
最后，我們快速瀏覽 只要有一個進程有可能失效，就無法達成分布式共識這篇論文，把剛才學到的有關分布式系統的各種概念關聯起來。在摘要的開頭，作者寫道：
共識問題涉及的是由一組進程組成的異步系統，其中一些進程是不可靠的。在異步系統中，對處理速度或者消息送達時間不做任何假設，其中有些進程可能會崩潰。
這種說法有一個問題。在通常的技術術語中， 異步可 能是指處理請求的方式。以 RPC 為例，進程 p 向進程 q 發送一個異步請求；在進程 q 處理請求的同時， p 會繼續做別的事情——也就是說， p 不會為了等待應答而阻塞自己的運行。你看，同樣是叫異步，在這里的含義與在分布式系統文獻中的含義完全不同。不了解這一點，你很難完全理解 FLP 論文的第一句話。
接下來，作者寫道：
本文提出一個令人驚奇的結果：系統中哪怕是只有一個進程可能會失效，就完全不可能存在異步共識協議。我們假設系統中不存在拜占庭失效，消息系統也是可靠的——所有消息都會被正確地一次送達。由此可見，這篇論文討論的系統只存在崩潰-停止（或者說失效-停止）的失效模式，（除了不存在拜占庭模式），也不存在忽略失效模式，因為消息系統是可靠的。
最后，作者還添加下面一條約束：
不假定進程能夠檢測出另外一個進程是否死亡。也就是說，一個進程無法區分另外一個進程的兩種狀態：死亡（完全停止運行）或者運行得很慢。這就是說，本文討論的系統中不存在失效檢測器。
總結一下， FLP 不可能性結果適用于具有下列特征的異步系統：崩潰-停止失效模式；可靠的消息系統；不存在失效檢測器。不了解各種分布式系統模型的理論，我們就可能漏掉很多細節，我們的理解甚至與作者的原意相去甚遠。
想要更詳細地了解 FLP 不可能性，請看博客文章： FLP 簡要梳理。
Marcos Aguilera 寫了一篇有意思的論文 “共識研究中的那些坑：誤解與問題”，文中討論了 FLP 作為分布式系統的一個不可能性結果，它的含義究竟是什么（劇透警告：這里說的不可能性與 停機問題中的不可能性不是一回事兒）。
結束語
如你所知，分布式系統的學習需要時間投入。分布式系統是一個非常龐大的議題，每個子領域都已經有非常多的研究。與此同時，分布式系統的實現和驗證又是非常復雜的，有很多容易犯錯的細微之處，處理不好的話，我們實現的分布式系統就會在意想不到的情況下無法正常地工作。如果不能正確地理解分布式系統的底層理論，下列問題甚至更多問題就會發生：選擇錯誤的法定人數，結果導致新的復制算法丟失關鍵數據；選擇非常保守 的法定人數，導致應用程序運行變慢，從而滿足不了向用戶承諾的服務約定；我們要解決的問題本來根本沒必要使用共識，用最終一致性就行，（但是我們卻選擇使 用共識）；錯誤地假設系統的定時模型；使用了不符合底層系統屬性的失效檢測器；我們想優化像 Raft
這樣的算法，于是去掉了貌似不相關的一個小步驟，結果卻破壞了算法的安全性保證。
好，我明白了，我不想重新發明分布式系統輪子，但是面對如此眾多的問題和文獻，我該從哪里著手呢？在本文開頭，我指出隨機地閱讀論文沒有什么用處。就像上面提到的 FLP 論文，不了解各種定時模型，你就沒辦法理解論文的第一句話。因此，我推薦下列入門書籍：
《分布式算法》，Nancy Lynch 著。這本書就好像是分布式系統的圣經，內容涵蓋上面提及的各種模型，包括每種模型涉及的算法。
《可靠且安全的分布式程序設計指南》，Christian Cachin 等人著。這本書不光導論寫得非常棒，還涵蓋了很多種共識算法。這本書還有個優點，到處可見解釋算法的偽代碼。
還有很多書。我覺得這兩本非常適合入門使用。
參考文獻
如果你還想深入研究，請看本文的參考文獻列表：原文鏈接：What We Talk About When We Talk About Distributed Systems（翻譯：柳泉波）
來自：http://dockone.io/article/898
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！