左耳朵耗子：分散式系統架構經典資料
作者｜陳皓、楊爽
前段時間，我寫了一系列分散式系統架構方面的文章（拉到文末看目錄），有很多讀者紛紛留言討論相關的話題，還有讀者留言表示對分散式系統架構這個主題感興趣，希望我能推薦一些學習資料。
就像我在前面的文章中多次提到的，分散式系統的技術棧巨大無比，所以我要推薦的學習資料也比較多，會在後面的文章中陸續發出。在今天這篇文章中，我將推薦一些分散式系統的基礎理論和一些不錯的圖書和資料。
這篇文章比較長，所以我特意整理了目錄，幫你快速找到自己感興趣的內容。
基礎理論
CAP 定理
Fallacies of Distributed Computing
經典資料
Distributed systems theory for the distributed systems engineer
FLP Impossibility Result
An introduction to distributed systems
Distributed Systems for fun and profit
Distributed Systems: Principles and Paradigms
Scalable Web Architecture and Distributed Systems
Principles of Distributed Systems
Making reliable distributed systems in the presence of software errors
Designing Data Intensive Applications
基礎理論
下面這些基礎知識有可能你已經知道了，不過還是容我把其分享在這裡。我希望用比較通俗易懂的文字將這些枯燥的理論知識講請楚。
CAP 定理
CAP 定理是分散式系統設計中最基礎，也是最為關鍵的理論。它指出，分散式數據存儲不可能同時滿足以下三個條件。
一致性（Consistency）：每次讀取要麼獲得最近寫入的數據，要麼獲得一個錯誤。
可用性（Availability）：每次請求都能獲得一個（非錯誤）響應，但不保證返回的是最新寫入的數據。
分區容忍（Partition tolerance）：儘管任意數量的消息被節點間的網路丟失（或延遲），系統仍繼續運行。
也就是說，CAP 定理表明，在存在網路分區的情況下，一致性和可用性必須二選一。而在沒有發生網路故障時，即分散式系統正常運行時，一致性和可用性是可以同時被滿足的。這裡需要注意的是，CAP 定理中的一致性與 ACID 資料庫事務中的一致性截然不同。
掌握 CAP 定理，尤其是能夠正確理解 C、A、P 的含義，對於系統架構來說非常重要。因為對於分散式系統來說，網路故障在所難免，如何在出現網路故障的時候，維持系統按照正常的行為邏輯運行就顯得尤為重要。你可以結合實際的業務場景和具體需求，來進行權衡。
例如，對於大多數互聯網應用來說（如門戶網站），因為機器數量龐大，部署節點分散，網路故障是常態，可用性是必須要保證的，所以只有捨棄一致性來保證服務的 AP。而對於銀行等，需要確保一致性的場景，通常會權衡 CA 和 CP 模型，CA 模型網路故障時完全不可用，CP 模型具備部分可用性。
CA (consistency + availability)，這樣的系統關注一致性和可用性，它需要非常嚴格的全體一致的協議，比如「兩階段提交」（2PC）。CA 系統不能容忍網路錯誤或節點錯誤，一旦出現這樣的問題，整個系統就會拒絕寫請求，因為它並不知道對面的那個結點是否掛掉了，還是只是網路問題。唯一安全的做法就是把自己變成只讀的。
CP (consistency + partition tolerance)，這樣的系統關注一致性和分區容忍性。它關注的是系統里大多數人的一致性協議，比如：Paxos 演算法 (Quorum 類的演算法)。這樣的系統只需要保證大多數結點數據一致，而少數的結點會在沒有同步到最新版本的數據時變成不可用的狀態。這樣能夠提供一部分的可用性。
AP (availability + partition tolerance)，這樣的系統關心可用性和分區容忍性。因此，這樣的系統不能達成一致性，需要給出數據衝突，給出數據衝突就需要維護數據版本。Dynamo 就是這樣的系統。
然而，還是有一些人會錯誤地理解 CAP 定理，甚至誤用。Cloudera 工程博客中，CAP Confusion: Problems with 『partition tolerance』一文中對此有詳細的闡述。
在谷歌的 Transaction Across DataCenter 視頻中，我們可以看到下面這樣的圖。這個是 CAP 理論在具體工程中的體現。
Fallacies of Distributed Computing
本文是英文維基百科上的一篇文章。它是 Sun 公司的勞倫斯·彼得·多伊奇（Laurence Peter Deutsch）等人於 1994~1997 年提出的，講的是剛剛進入分散式計算領域的程序員常會有的一系列錯誤假設。
多伊奇於 1946 年出生在美國波士頓。他創辦了阿拉丁企業（Aladdin Enterprises），並在該公司編寫出了著名的 Ghostscript 開源軟體，於 1988 年首次發布。
他在學生時代就和艾倫·凱（Alan Kay）等比他年長的人一起開發了 Smalltalk，並且他的開發成果激發了後來 Java 語言 JIT 編譯技術的創造靈感。他後來在 Sun 公司工作並成為 Sun 的公司院士。在 1994 年，他成為了 ACM 院士。
基本上，每個人剛開始建立一個分散式系統時，都做了以下 8 條假定。隨著時間的推移，每一條都會被證明是錯誤的，也都會導致嚴重的問題，以及痛苦的學習體驗。
網路是穩定的。
網路傳輸的延遲是零。
網路的帶寬是無窮大。
網路是安全的。
網路的拓撲不會改變。
只有一個系統管理員。
傳輸數據的成本為零。
整個網路是同構的。
阿爾農·羅特姆 - 蓋爾 - 奧茲（Arnon Rotem-Gal-Oz）寫了一篇長文 Fallacies of Distributed Computing Explained 來解釋這些點。
由於他寫這篇文章的時候已經是 2006 年了，所以從中能看到這 8 條常見錯誤被提出十多年後還有什麼樣的影響：一是，為什麼當今的分散式軟體系統也需要避免這些設計錯誤；二是，在當今的軟硬體環境里，這些錯誤意味著什麼。比如，文中在談「延遲為零」假設時，還談到了 AJAX，而這是 2005 年開始流行的技術。
而加勒思·威爾遜（Gareth Wilson）的文章則用日常生活中的例子，對這些點做了更為通俗的解釋。
這 8 個需要避免的錯誤不僅對於中間件和底層系統開發者及架構師是重要的知識，而且對於網路應用程序開發者也同樣重要。分散式系統的其他部分，如容錯、備份、分片、微服務等也許可以對應用程序開發者部分透明，但這 8 點則是應用程序開發者也必須知道的。
為什麼我們要深刻地認識這 8 個錯誤？是因為，這要我們清楚地認識到——在分散式系統中錯誤是不可能避免的，我們能做的不是避免錯誤，而是要把錯誤的處理當成功能寫在代碼中。
後面，我會寫一個系列的文章來談一談，分散式系統容錯設計中的一些常見設計模式。敬請關注！
經典資料
Distributed systems theory for the distributed systems engineer
本文作者認為，推薦大量的理論論文是學習分散式系統理論的錯誤方法，除非這是你的博士課程。因為論文通常難度大又很複雜，需要認真學習，而且需要理解這些研究成果產生的時代背景，才能真正的領悟到其中的精妙之處。
在本文中，作者給出了他整理的分散式工程師必須要掌握的知識列表，並直言掌握這些足夠設計出新的分散式系統。首先，作者推薦了 4 份閱讀材料，它們共同概括了構建分散式系統的難點，以及所有工程師必須克服的技術難題。
Distributed Systems for Fun and Profit，這是一本小書，涵蓋了分散式系統中的關鍵問題，包括時間的作用和不同的複製策略。後文中對這本書有較詳細的介紹。
Notes on distributed systems for young bloods，這篇文章中沒有理論，是一份適合新手閱讀的分散式系統實踐筆記。
A Note on Distributed Systems，這是一篇經典的論文，講述了為什麼在分散式系統中，遠程交互不能像本地對象那樣進行。
The fallacies of distributed computing，每個分散式系統新手都會做的 8 個錯誤假設，並探討了其會帶來的影響。上文中專門對這篇文章做了介紹。
隨後，分享了幾個關鍵點。
失敗和時間（Failure and Time）。分散式系統工程師面臨的很多困難都可以歸咎於兩個根本原因：1. 進程可能會失敗；2. 沒有好方法表明進程失敗。這就涉及到如何設置系統時鐘，以及進程間的通訊機制，在沒有任何共享時鐘的情況下，如何確定一個事件發生在另一個事件之前。
可以參考 Lamport 時鐘和 Vector 時鐘，還可以看看 Dynamo 論文。
容錯的壓力（The basic tension of fault tolerance）。能在不降級的情況下容錯的系統一定要像沒有錯誤發生的那樣運行。這就意味著，系統的某些部分必須冗餘地工作，從而在性能和資源消耗兩方面帶來成本。
最終一致性以及其他技術方案在以系統行為弱保證為代價，來試圖避免這種系統壓力。閱讀 Dynamo 論文和帕特·赫爾蘭（Pat Helland）的經典論文 Life Beyond Transactions 能獲很得大啟發。
基本原語（Basic primitives）。在分散式系統中幾乎沒有一致認同的基本構建模塊，但目前在越來越多地在出現。比如 Leader 選舉，可以參考 Bully 演算法；分散式狀態機複製，可以參考維基百科和 Lampson 的論文，後者更權威，只是有些枯燥。
基本結論（Fundamental Results）。某些事實是需要吸收理解的，有幾點：如果進程之間可能丟失某些消息，那麼不可能在實現一致性存儲的同時響應所有的請求，這就是 CAP 定理；一致性不可能同時滿足以下條件：a. 總是正確，b. 在非同步系統中只要有一台機器發生故障，系統總是能終止運行——停止失敗（FLP 不可能性）；一般而言，消息交互少於兩輪都不可能達成共識（Consensus）。
真實系統（Real systems）。學習分散式系統架構最重要的是，結合一些真實系統的描述，反覆思考和點評其背後的設計決策。如谷歌的 GFS、Spanner、Chubby、BigTable、Dapper 等，以及 Dryad、Cassandra 和 Ceph 等非谷歌系統。
FLP Impossibility Result
FLP 不可能性的名稱起源於它的三位作者，Fischer、Lynch 和 Paterson。它是關於理論上能做出的功能最強的共識演算法會受到怎樣的限制的討論。
所謂共識問題，就是讓網路上的分散式處理者最後都對同一個結果值達成共識。該解決方案對錯誤有恢復能力，處理者一旦崩潰以後，就不再參與計算。在同步環境下，每個操作步驟的時間和網路通信的延遲都是有限的，要解決共識問題是可能的，方式是：等待一個完整的步長來檢測某個處理者是否已失敗。如果沒有收到回復，那就假定它已經崩潰。
共識問題有幾個變種，它們在「強度」方面有所不同——通常，一個更「強」問題的解決方案同時也能解決比該問題更「弱」的問題。共識問題的一個較強的形式如下。
給出一個處理者的集合，其中每一個處理者都有一個初始值：
所有無錯誤的進程（處理過程）最終都將決定一個值；
所有會做決定的無錯誤進程決定的都將是同一個值；
最終被決定的值必須被至少一個進程提出過。
這三個特性分別被稱為「終止」、「一致同意」和「有效性」。任何一個具備這三點特性的演算法都被認為是解決了共識問題。
FLP 不可能性則討論了非同步模型下的情況，主要結論有兩條。
在非同步模型下不存在一個完全正確的共識演算法。不僅上述較「強」形式的共識演算法不可能實現，FLP 還證明了比它弱一些的、只需要有一些無錯誤的進程做決定就足夠的共識演算法也是不可能實現的。
在非同步模型下存在一個部分正確的共識演算法，前提是所有無錯誤的進程都總能做出一個決定，此外沒有進程會在它的執行過程中死亡，並且初始情況下超過半數進程都是存活狀態。
FLP 的結論是，在非同步模型中，僅一個處理者可能崩潰的情況下，就已經沒有分散式演算法能解決共識問題。這是該問題的理論上界。其背後的原因在於，非同步模型下對於一個處理者完成工作然後再回復消息所需的時間並沒有上界。因此，無法判斷出一個處理者到底是崩潰了，還是在用較長的時間來回復，或者是網路有很大的延遲。
FLP 不可能性對我們還有別的啟發。一是網路延遲很重要，網路不能長時間處於擁塞狀態，否則共識演算法將可能因為網路延遲過長而導致超時失敗。二是計算時間也很重要。對於需要計算共識的處理過程（進程），如分散式資料庫提交，需要在短時間裡就計算出能否提交的結果，那就要保證計算結點資源充分，特別是內存容量、磁碟空閑時間和 CPU 時間方面要足夠，並在軟體層面確保計算不超時。
另一個問題是，像 Paxos 這樣的共識演算法為什麼可行？實際上它並不屬於 FLP 不可能性證明中所說的「完全正確」的演算法。它的正確性會受超時值的影響。但這並不妨礙它在實踐中有效，因為我們可以通過避免網路擁塞等手段來保證超時值是合適的。
An introduction to distributed systems
它是分散式系統基礎課的課程提綱，也是一份很棒的分散式系統介紹，幾乎涵蓋了所有知識點，並輔以簡潔並切中要害的說明文字，非常適合初學者提綱挈領地了解知識全貌，快速與現有知識結合，形成知識體系。此外，還可以把它作為分散式系統的知識圖譜，根據其中列出的知識點一一搜索，你能學會所有的東西。
Distributed Systems for fun and profit
這是一本免費的電子書。作者撰寫此書的目的是希望以一種更易於理解的方式，講述以亞馬遜的 Dynamo、谷歌的 BigTable 和 MapReduce 等為代表的分散式系統背後的核心思想。
因而，書中著力撰寫分散式系統中的關鍵概念，以便讓讀者能夠快速了解最為核心的知識，並且進行了足夠詳實的講述，方便讀者體會和理解，又不至於陷入細節。
全書分為五章，講述了擴展性、可用性、性能和容錯等基礎知識，FLP 不可能性和 CAP 定理，探討了大量的一致性模型；討論了時間和順序，及時鐘的各種用法。隨後，探討了複製問題，如何防止差異，以及如何接受差異。此外，每章末尾都給出了針對本章內容的擴展閱讀資源列表，這些資料是對本書內容的很好補充。
Distributed Systems: Principles and Paradigms
本書是由計算機科學家安德魯·斯圖爾特·塔能鮑姆（Andrew S. Tanenbaum）和其同事馬丁·范·斯蒂恩（Martin van Steen）合力撰寫的，是分散式系統方面的經典教材。
語言簡潔，內容通俗易懂，介紹了分散式系統的七大核心原理，並給出了大量的例子；系統講述了分散式系統的概念和技術，包括通信、進程、命名、同步化、一致性和複製、容錯以及安全等；討論了分散式應用的開發方法（即范型）。
但本書不是一本指導「如何做」的手冊，僅適合系統性地學習基礎知識，了解編寫分散式系統的基本原則和邏輯。中文翻譯版為《分散式系統原理與范型》（第二版）。
Scalable Web Architecture and Distributed Systems
這是一本免費的在線小冊子，其中文翻譯版為可擴展的 Web 架構和分散式系統。本書主要針對面向的互聯網（公網）的分散式系統，但其中的原理或許也可以應用於其他分散式系統的設計中。作者的觀點是，通過了解大型網站的分散式架構原理，小型網站的構建也能從中受益。本書從大型互聯網系統的常見特性，如高可用、高性能、高可靠、易管理等出發，引出了一個類似於 Flickr 的典型的大型圖片網站的例子。
首先，從程序模塊化易組合的角度出發，引出了面向服務架構（SOA）的概念。同時，引申出寫入和讀取兩者的性能問題，及對此二者如何調度的考量——在當今的軟硬體架構上，寫入幾乎總是比讀取更慢，包括軟體層面引起的寫入慢（如資料庫的一致性要求和 B 樹的修改）和硬體層面引起的寫入慢（如 SSD）。
網路提供商提供的下載帶寬也通常比上傳帶寬更大。讀取往往可以非同步操作，還可以做 gzip 壓縮。寫入則往往需要保持連接直到數據上傳完成。因此，往往我們會想把服務做成讀寫分離的形式。然後通過一個 Flickr 的例子，介紹了他們的伺服器分片式集群做法。
接下來講了冗餘。數據的冗餘異地備份（如 master-slave）、服務的多版本冗餘、避免單點故障等。
隨後，在冗餘的基礎上，講了多分區擴容，亦即橫向擴容。橫向擴容是在單機容量無法滿足需求的情況下不得不做的設計。但橫向擴容會帶來一個問題，即數據的局域性會變差。本來數據可以存在於同一台伺服器上，但現在數據不得不存在於不同伺服器上，潛在地降低了系統的性能（主要是可能延長響應時間）。另一個問題是多份數據的不一致性。
之後，本書開始深入講解數據訪問層面的設計。首先拋出一個大型數據（TB 級以上）的存儲問題。如果內存都無法緩存該數據量，性能將大幅下降，那麼就需要緩存數據。數據可以緩存在每個節點上。
但如果為所有節點使用負載均衡，那麼分配到每個節點的請求將十分隨機，大大降低緩存命中率，從而導致低效的緩存。接下來考慮全局緩存的設計。再接下來考慮分散式緩存的設計。進一步，介紹了 Memcached，以及 Facebook 的緩存設計方案。
代理伺服器則可以用於把多個重複請求合併成一個，對於公網上的公共服務來說，這樣做可以大大減少對數據層訪問的次數。Squid 和 Varnish 是兩個可用於生產的代理服務軟體。
當知道所需要讀取的數據的元信息時，比如知道一張圖片的 URL，或者知道一個要全文搜索的單詞時，索引就可以幫助找到那幾台存有該信息的伺服器，並從它們那裡獲取數據。文中擴展性地討論了本話題。
接下來談負載均衡器，以及一些典型的負載均衡拓撲。然後討論了對於用戶會話數據如何處理。比如，對於電子商務網站，用戶的購物車在沒有下單之前都必須保持有效。
一種辦法是讓用戶會話與伺服器產生關聯，但這樣做會較難實現自動故障轉移，如何做好是個問題。另外，何時該使用負載均衡是個問題。有時節點數量少的情況下，只要使用輪換式 DNS 即可。負載均衡也會讓在線性能問題的檢測變得更麻煩。
對於寫入的負載，可以用隊列的方式來減少對伺服器的壓力，保證伺服器的效率。消息隊列的開源實現有很多，如 RabbitMQ、ActiveMQ、BeanstalkD，但有些隊列方案也使用了如 Zookeeper，甚至是像 Redis 這樣的存儲服務。
本書主要講述了高性能互聯網分散式服務的架構方案，並介紹了許多實用的工具。作者指出這是一個令人興奮的設計領域，雖然只講了一些皮毛，但這一領域不僅現在有很多創新，將來也會越來越多。
Principles of Distributed Systems
本書是蘇黎世聯邦理工學院的教材。它講述了多種分散式系統中會用到的演算法。雖然分散式系統的不同場景會用到不同演算法，但並不表示這些演算法都會被用到。不過，對於學生來說，掌握了演算法設計的精髓也就能舉一反三地設計出解決其他問題的演算法，從而得到分散式系統架構設計中所需的演算法。
本書覆蓋的演算法有：
頂點塗色演算法（可用於解決互相衝突的任務分配問題）
分散式的樹演算法（廣播演算法、會聚演算法、廣度優先搜索樹演算法、最小生成樹演算法）
容錯以及 Paxos（Paxos 是最經典的共識演算法之一）
拜占庭協議（節點可能沒有完全宕機，而是輸出錯誤的信息）
全互聯網路（伺服器兩兩互聯的情況下演算法的複雜度）
多核計算的工程實踐（事務性存儲、資源爭用管理）
主導集（又一個用隨機化演算法打破對稱性的例子；這些演算法可以用於路由器建立路由）
……
這些演算法對你邁向更高級更廣闊的技術領域真的相當有幫助的。
Making reliable distributed systems in the presence of software errors
這本書的書名直譯過來是在有軟體錯誤的情況下，構建可靠的分散式系統，Erlang 之父喬·阿姆斯特朗（Joe Armstrong）的力作。書中撰寫的內容是從 1981 年開始的一個研究項目的成果，這個項目是尋找更好的電信應用編程方式。
當時的電信應用都是大型程序，雖然經過了仔細的測試，但投入使用時程序中仍會存在大量的錯誤。作者及其同事假設這些程序中確實有錯誤，然後想法設法在這些錯誤存在的情況下構建可靠的系統。他們測試了所有的編程語言，沒有一門語言擁有電信行業所需要的所有特性，所以促使一門全新的編程語言 Erlang 的開發，以及隨之出現的構建健壯系統（OTP）的設計方法論和庫集。
書中抽象了電信應用的所有需求，定義了問題域，講述了系統構建思路——模擬現實，簡單通用，並給出了指導規範。阿姆斯特朗認為，在存在軟體錯誤的情況下，構建可靠系統的核心問題可以通過編程語言或者編程語言的標準庫來解決。所以本書有很大的篇幅來介紹 Erlang，以及如何運用其構建具有容錯能力的電信應用。
雖然書中的內容是以構建 20 世紀 80 年代的電信系統為背景，但是這種大規模分散式的系統開發思路，以及對系統容錯能力的核心需求，與互聯網時代的分散式系統架構思路出奇一致。書中對問題的抽象、總結，以及解決問題的思路和方案，有深刻的洞察和清晰的闡釋，所以此書對現在的項目開發和架構有極強的指導和借鑒意義。
Designing Data Intensive Applications
這是一本非常好的書。我們知道，在分散式的世界裡，數據結點的擴展是一件非常麻煩的事。而這本書則深入淺出地用很多工程案例講解了如何讓數據結點做擴展。作者馬丁·科勒普曼（Martin Kleppmann）在分散式數據系統領域有著很深的功底，並在這本書中完整地梳理各類紛繁複雜設計背後的技術邏輯，不同架構之間的妥協與超越，很值得開發人員與架構設計者閱讀。
這本書深入到 B-Tree、SSTables、LSM 這類數據存儲結構中，並且從外部的視角來審視這些數據結構對 NoSQL 和關係型資料庫所產生的影響。它可以讓你很清楚地了解到真正世界的大數據架構中的數據分區、數據複製的一些坑，並提供了很好的解決方案。
最贊的是，作者將各種各樣的技術的本質非常好地關聯在一起，幫你觸類旁通。而且抽絲剝繭，循循善誘，從「提出問題」，到「解決問題」，到「解決方案」，再到「優化方案」和「對比不同的方案」，一點一點地把非常晦澀的技術和知識展開。
本書的引用相當多，每章後面都有幾百個 Reference。通過這些 Reference，你可以看到更為廣闊更為精彩的世界。
這本書是 2017 年 3 月份出版的，目前還沒有中譯版，不過英文也不難讀。非常推薦。這裡有這本書的 PPT，你可從這個 PPT 中管中窺豹一下。
小 結
在今天的文章中，我給出了一些分散式系統的基礎理論知識和幾本很不錯的圖書和資料，需要慢慢消化吸收。也許你看到這麼龐大的書單和資料列表有點望而卻步，但是我真的希望你能夠花點時間來看看這些資料。相信你看完這些資料後，一定能上一個新的台階。再加上一些在工程項目中的實踐，我保證你，一定能達到大多數人難以企及的技術境界。
自從 2002 年開始接觸分散式計算系統至今，我學習分散式系統已經有 15 年了，發現還有很多東西還要繼續學習。是的，學無止境啊。如果你想成為一名很不錯的架構師，你一定要好好學習這些知識。
左耳朵耗子的《分散式系統架構的本質》系列文章一共有九篇，目錄如下，繼續閱讀請掃碼訂閱專欄（支持微信支付）。一次訂閱，永久閱讀，還可以隨時在評論區與左耳朵耗子、資深編輯和同學們交流！
左耳朵耗子的《分散式系統架構的本質》系列文章一共有九篇，目錄如下，繼續閱讀請掃碼訂閱專欄（支持微信支付）。一次訂閱，永久閱讀，還可以隨時在評論區與左耳朵耗子、資深編輯和同學們交流！
TAG:InfoQ |