當(dāng)我們在談?wù)摲植际较到y(tǒng)的時候我們在談?wù)撌裁碵譯]本文是我在閱讀了Alvaro Videla先生的博客之后，受益良多，決定翻譯下來。也征得了Videla先生本人的同意，原文鏈接在此 http://videlalvaro./2015/12/learning-about-distributed-systems.html 在過去的相當(dāng)長一段時間內(nèi)，我嘗試著學(xué)習(xí)分布式系統(tǒng)，并且可以說，一旦你開始挖掘這方面，你會發(fā)現(xiàn)這一方向看起來是沒有止境的，深坑一個接著一個。分布式系統(tǒng)中的話題是相當(dāng)廣泛的，伴隨著一篇又一篇各個大學(xué)發(fā)出的論文，和一些書籍。事實證明，對于一個像我這樣的萌新，一開始是很難抉擇到底要讀哪些論文，看哪些書的。 同時，我也發(fā)現(xiàn)有很多博客推薦了這樣或者那樣的對那些想要成為分布式系統(tǒng)工程師（不管這個詞的含義是什么）的人們必讀的論文。下面是列舉的論文： FLP, Zab, Time, Clocks and the Ordering of Events in a Distributed Systems, Viewstamped Replication, Paxos, Chubby 我的問題在于很多時候我沒有看到有一個理由來告訴我 為什么 我應(yīng)該讀這篇或者那篇論文。我熱愛為了滿足好奇心僅僅是為了知識而學(xué)習(xí)的想法，但是同時應(yīng)該考慮到閱讀的先后順序，畢竟一天只有24小時。 除了大量的論文和研究資料，就像上面所提到的，還有很多書籍。在借閱了相當(dāng)多的書籍之后，我開始發(fā)現(xiàn)一本書的標(biāo)題并不能夠滿足我在尋找的問題或者說它的內(nèi)容并不能解決我想要解決的問題。因此，我想我想仔細討論一下我所認為的分布式系統(tǒng)的最主要的概念，并且給出引用告訴你應(yīng)該去哪里學(xué)習(xí)他們。 由于我是一邊學(xué)習(xí)一邊寫下這些文字的，所以請有點耐心，我也可能會犯下一些錯誤，并且我會嘗試解釋一切我所寫下的內(nèi)容。 在我們開始前，我必須得告訴你我寫這篇文章時參考了大量引用，所以這兒有些slides如果你感興趣的話。
并且這兒有段我在Erlang User Conference in Stockholm 的演講視頻。
讓我們開始吧。 分布式系統(tǒng)算法可以根據(jù)不同的性質(zhì)進行分類。比如說根據(jù)時序模型，根據(jù)進程間的通信方式，根據(jù)這個算法所使用的故障模式，還有很多很多，我們接下來也會看到。 接下來我們將看到的主要概念有：
時序模型 (Timing model)接下來我們要討論 同步模型(synchronous model), 異步模型(asynchronous model) 和 部分同步模型(partially synchronous model) 。 同步模型是最簡單的一種。每個部分通過所謂 同步輪次(synchronous rounds) 進行同步的工作。 消息傳遞所需要的時間通常是已知的，并且我們?nèi)藶榧俣ㄒ粋€進程的速度，比如一個進程要花多久才能進行算法的一步。這個模型的問題在于它并沒有真實的反映現(xiàn)實情況，甚至說在一個分布式系統(tǒng)中，一個進程可以給另一個進程發(fā)送消息，并且祈禱星星是對齊的（大概意思是運轉(zhuǎn)良好），所以消息可以抵達上述進程，在這樣的分布式系統(tǒng)中描述的也不是很好。這個模型的好處在于使用這個模型可以得到理論解然后轉(zhuǎn)換到其他模型中。例如說，因此模型對于時間的保證，我們可以發(fā)現(xiàn)有個問題在時序保證的情況下也無法解決，那么很可能在我們放松了條件的情況下也無法解決。 異步模型 相比而言復(fù)雜一些。 每個部分可能執(zhí)行算法的每個步驟的順序無法保證，并且他們無法確定他們執(zhí)行算法每一步的速度。這個模型的問題在于雖然它的描述很簡單并且相當(dāng)接近現(xiàn)實，但是它始終是無法準(zhǔn)確反映現(xiàn)實世界的。例如，一個進程可能要花無限長的時間來響應(yīng)一個請求，但是在現(xiàn)實的項目中，我們很可能會在上述請求中強加一個時限，一旦到了時間就會停止那個請求。這個模型的一個難點就在于，我們?nèi)绾文軌虼_保一個行程的存活情況。最出名的 不可能情況 可以參見這里，“Impossibility of Consensus with one Faulty Process” 在部分同步模型中，每個部分有一些關(guān)于時序的信息，可以保證近似的同步時鐘，或者他們可能知道消息傳遞的近似時間，或者一個進程執(zhí)行算法每一步所需的近似時間。 Distributed Algorithms Nancy Lynch的這本書有關(guān)于時許模型的部分。 進程間通信(Interprocess communication)接下來我們考慮進程是 如何 在系統(tǒng)中交換信息的。在消息傳遞(message passing)模型中，它們可以通過傳遞消息來完成。在內(nèi)存共享(shared memory)模型中，它們可以通過共享變量來完成。 需要在心里牢記一件事——我們可以通過消息傳遞算法來建立一個共享內(nèi)存對象。一個在很多書中都有的堿性粒子就是讀/寫寄存器的實現(xiàn)。我們也可以用隊列或者棧來保證連續(xù)性的性質(zhì)，linearizabilty。我們不應(yīng)該混淆通過一個共享變量來在進程之間 共享內(nèi)存 和建立在消息傳遞基礎(chǔ)上的 共享內(nèi)存抽象 。 回到消息傳遞模型，我們可以通過另一種抽象來嘗試?yán)斫馑惴ǎ哼M程之間建立聯(lián)系的方法（想想進程間傳遞消息的管道）。這些鏈接保證了算法使用它們時的穩(wěn)定。例如，有種抽象叫 完美鏈接(Perfect Links) 可以有可靠的傳遞并且不會重復(fù)。這種抽象也保證了一次傳遞。這種抽象很顯然沒反映真實世界的情況，因此算法設(shè)計者們設(shè)計了許多其他模型，更加貼近真實的系統(tǒng)。雖然 完美鏈接(Perfect Links) 并不是如此現(xiàn)實，但是它依舊十分有用。例如如果我們可以證明一個問題即使在完美鏈接的情況下也無法解決，那么我們可以知道許多相關(guān)問題也可能無法解決。關(guān)于鏈接的問題許多作者通常認為或者假定了FIFO消息模型，Zab 故障模式(Failure Modes)我曾經(jīng)寫過一邊關(guān)于故障模式的文章failure modes in distributed systems它依舊值得重新多讀幾遍。一個分布式系統(tǒng)的重要特征就是它嘉定了何種故障模式。在 故障-停止(crash-stop) 模型中，一個進程總是被認為是正確的，直到它發(fā)生了故障。一旦它掛了，它就真掛了，不重啟了。也有一種模型叫做_故障-重啟(crash-recovery)_模型，發(fā)生錯誤后進程將會沖洗。在這種情況下，算法包括了一種能夠讓進程恢復(fù)到它掛之前的狀態(tài)的途徑。有多種方法，比如說從一個持續(xù)的儲存中讀取，或者與在一個組中的其他進程進行交流。如果對某些算法來說，一個進程掛了再恢復(fù)就不算做之前的同一個進程了的話，這個算法就是沒用的。這通常取決于我們是用動態(tài)分組還是靜態(tài)分組。 也有些故障模式中，進程是無法接受或者傳遞消息的，這種被稱為 疏漏故障模式(omission failure modes) 當(dāng)然，除了這種，還有很多其他類型的疏漏。為什么這很重要？想象這樣的場景，一組進程組成了一個分布式的緩存，如果一個進程沒能夠回復(fù)其他進程的請求，即使它能夠接收到請求并且保證了它的狀態(tài)是最新的，所以它依舊可以聽取客戶端的讀取請求。 Byzantine，一個更復(fù)雜的故障模式，或者說叫_arbitrary failures mode_。在這種模式中進程可能給它的同伴發(fā)出錯誤的信息。他們可能模仿或者冒充其他進程，或者說給其他進程傳遞了正確的數(shù)據(jù)，但是弄亂了它自己本地的數(shù)據(jù)內(nèi)容。 當(dāng)考慮一個系統(tǒng)的設(shè)計時，我們應(yīng)該考慮我們想要解決怎樣的進程故障。Birman(Guide to Reliable Distributed Systems) 提出了我們通常不需要結(jié)局Byzantine 故障的觀點。他根據(jù)在Yahoo的工作他們總結(jié)出Crash failure 總是比Byzantine failures更常見。（譯者注：意思就是，進程本身掛掉遠比進程間出現(xiàn)欺騙頻繁的多） 故障檢測(Failure Detector)根據(jù)進程的故障模式和時限假定，我們可以構(gòu)建出一個能夠向系統(tǒng)報告是否有一個進程掛掉或者它可能掛掉的抽象。完美檢測器(Perfer Failure detector) 能夠永遠不給出誤報。對Crash-stop模式和同步模型，我們可以僅僅通過添加時限來完成這樣的算法。如果我們讓進程周期性的去ping故障檢測進程，我們就可以知道何時一個ping到達故障檢測其（同步模型保證了這一點）。如果ping沒能在實現(xiàn)設(shè)定的時限中到達，那么我們就可以認為其他節(jié)點掛了。 在一個更加實際的系統(tǒng)中，也許你不可能總是假設(shè)一個消息到達目標(biāo)的時間，或者一個進程執(zhí)行算法每一步所需的時間。在這個例子中我們有個進程檢測 故障檢測器通常提供了兩種興趣：完備性和準(zhǔn)確性。對于總是完美的故障檢測來說，我們有如下性質(zhì)：
故障檢測對于解決在異步模型中的一致性是非常重要的。非常重要的的不可能性結(jié)果可以在這篇論文中看到FLP。這篇論文討論了在進程可能出故障的分布式異步模型中的一致性的不可達性。可以通過這篇論文來了解。circumvent the problem. 領(lǐng)袖選擇(Leader Election)與故障檢測的問題相反，為了確定哪個進程沒有掛并且工作良好。這種進程將被網(wǎng)絡(luò)中的其他伙伴新人并且被認為是可以協(xié)調(diào)分布式的行動的領(lǐng)導(dǎo)者。這種就是類似于Raft or Zab提出里的基礎(chǔ)領(lǐng)導(dǎo)者的分布式算法。 在協(xié)議中有一個領(lǐng)導(dǎo)者可以在節(jié)點中產(chǎn)生不對稱性，因為那些不是領(lǐng)導(dǎo)者的節(jié)點將會成為追隨者。這將會導(dǎo)致領(lǐng)導(dǎo)者節(jié)點最終成為許多操作的節(jié)點，因此基于我們試圖解決的問題，使用一個需要領(lǐng)導(dǎo)者選舉的算法也許不是我們想要的。需要注意的是大部分協(xié)議都是通過一致推出一個領(lǐng)導(dǎo)者來達到一致性。 Paxos, Zab or Raft for some examples. 一致性(Consensus)一致性問題最先是在這篇文章中Reaching Agreement in the Presence of Faults由Pease, Shostak 和Lamport 提出的，他們是這樣介紹這個問題的：
所以一致性是在各個獨立部分之間保持統(tǒng)一的問題。這些進程對于某個問題會有不同的數(shù)值，例如像他們傳感器的當(dāng)前度數(shù)，然后得基于他們提出的數(shù)值達到一個統(tǒng)一的行為。例如，一輛車也許會就提供突破溫度等級信息有許多傳感器。這些傳感器讀數(shù)因為精度會有所不同，但是ABS電腦需要知道到底多大的壓力來完成突破。這就是一個我們每天都得面對的一致性問題。Fault-Tolerant Real-Time Systems這本書中解釋了自動化工業(yè)中的一致性還有其他問題。 一個實現(xiàn)了某種一致性形式的進程通過 提出(propose) 和 決定(decide) 的api來工作。當(dāng)一致決定開始時，一個進程將提出一個值并且在整個系統(tǒng)中所有值的基礎(chǔ)上，決定最后的值。這種算法將滿足如下性質(zhì)：
更多細節(jié)可以參照下面的論文：
法定人數(shù)(Quorums 他媽的我實在不知道這個怎么翻譯）Quorums 是一種用來設(shè)計容錯分布式系統(tǒng)的工具。 Quorum是指一系列用來理解系統(tǒng)的行為的想交的進程，因為有些進程可能會失效。 例如說，如果我們有一個使用N個使用Crash-failure模式的進程的算法，我們有一組法定的進程不管何時只有大部分的進程才能對系統(tǒng)進行特定操作，比如說寫數(shù)據(jù)庫。如果小部分的進程掛了，例如 另一個例子就是，假設(shè)我們想要限制一個進程訪問共享資源。這個資源是被 Quorums 并不是總是指一組進程的多數(shù)。有時候他們甚至需要更多的進程來組成一個合法的數(shù)量來完成某個操作，就像一組可能出現(xiàn)Byzantine錯誤的N個進程。如果 如果你對這個話題感興趣，有一整本講這個話題的書: Quorum Systems: With Applications to Storage and Consensus 分布式系統(tǒng)中的時序問題理解時序與其后果是分布式系統(tǒng)中的最大問題之一。我們習(xí)慣了生活中的一件事挨著一件事的概念,在其中有個概念非常容易定義，happened before。但是當(dāng)我們有一系列分布式的進程，它們在交換消息，同步得獲取資源，等等活動的時候，我們?nèi)绾文艽_定哪個活動先發(fā)生呢？為了能夠回答這樣的問題，進程需要共享一個同步鎖，并且準(zhǔn)確知道電子在網(wǎng)絡(luò)中移動需要多久，CPU調(diào)度需要多久，等等等等。很明顯這不是一個現(xiàn)實中可能存在的系統(tǒng)。 在這方面開創(chuàng)性的論文是Time, Clocks, and the Ordering of Events in a Distributed System 介紹了邏輯時鐘的概念。邏輯時鐘(Logical Clocks) 是一種給系統(tǒng)中每個活動都附加一個值的方法，這個值與真正的時間沒有關(guān)系，而是與在系統(tǒng)中的活動的過程有關(guān)。 有許多這方面的算法,Vector Clocks or Interval Tree Clocks. Justin Sheehy有個關(guān)于分布式系統(tǒng)中的時序非常有趣的討論There Is No Now 我想聲明的是，時序問題在分布式系統(tǒng)中是最重要的問題。我們必須忘掉同步的概念。這關(guān)系到關(guān)于絕對主義的舊的信念，我們之前總是認為一件事是可實現(xiàn)的。物理學(xué)告訴我們即使是光也需要時間從一個地方到另一個地方，所以不管何時它到達我們的眼睛，被我們的大腦所處理，不管這個光有什么含義，它都是這個世界的舊的影像。這個概念在Umberto Eco 的書Inventing the Enemy,中有”Absolute and Relative”這章專門討論。 FLP 瀏覽讓我們來瀏覽下Impossibility of Distributed Consensus with One Faulty Process這篇論文并且試著將它與我們之前討論的概念結(jié)合起來來結(jié)束這篇文章。
所以我們有一個 異步系統(tǒng) ，在這個系統(tǒng)中既沒有時序的假定，也沒有進程的速度啊或者傳遞消息所需的時間啊之類的嘉定。我們只知道有些進程可能會掛掉。 在通常的技術(shù)討論中，asynchronous 也許會指的是一種進程請求的方式，例如RPC那樣，當(dāng)一個進程 p 向進程 q 發(fā)出一個異步請求后，當(dāng) q 在處理這個請求時，p 將繼續(xù)做其他事情，也就是說 p 不會阻塞來等待一個答復(fù)。我們可以看到這個定義是與分布式系統(tǒng)中的定義完全不同的，所以沒有這樣的只是，很難完全理解在FLP中的第一句話。 這篇論文接下來說到：
所以這篇論文僅僅考慮 Crash-stop 的故障模式（就像上文所說 Fail-stop ）。我們可以知道沒有遺漏的錯誤，因為消息系統(tǒng)是可靠的。 最后他們還加上了這樣的限制：
所以我們也無法使用故障檢測器。 概括一下， 這意味著FLP不可能將異步系統(tǒng)用到Fail-stop的進程上，通過可靠的消息系統(tǒng)，并且不知道進程的死亡。不知道不同的分布式模型的相關(guān)理論，可能會忽略不少細節(jié)，或者以與作者所想表達的意思不同的方式來解釋。 更加詳細的FLP相關(guān)可以從這里看到。 A Brief Tour of FLP Impossibility Stumbling over Consensus Research: Misunderstandings and Issues 總覺正如你所看到的，學(xué)習(xí)分布式系統(tǒng)是很花時間的。這是一個非常大的主題，并且有無數(shù)的子領(lǐng)域的研究。同時，實現(xiàn)和驗證分布式系統(tǒng)也是非常復(fù)雜的。有很多不可預(yù)知的情況會將我們的系統(tǒng)打破。 假如我們選擇了錯誤的Quorum那么我們的新的副本算法就會失去重要的數(shù)據(jù)？或者說我們選擇了一個非常保守的Quorum就會給我們的系統(tǒng)帶來不必要的速度下降？假如我們嘗試解決的問題根本不需要一致性那么我們是否可以活的好好的？也許我們的系統(tǒng)有著錯誤的時序嘉定？或者它使用了不好的錯誤檢測器？如果我們想要優(yōu)化像Raft這樣的算法，是否會使得這兒或者那兒情況下系統(tǒng)失效？這些在我們嘗試?yán)斫夥植际较到y(tǒng)理論時都會發(fā)生。 好了，我明白了，我不會重復(fù)造輪子的，但是在如此多的知識和問題需要學(xué)習(xí)的情況下，如何開始呢，接下來怎么辦呢？就像剛開始說的那樣，我覺得隨便讀論文會讓你迷失，就像在FLP論文里那樣，理解第一句話就需要你知道很多時序模型。因此我推薦你下面這些論文按序讀。 Introduction to Reliable and Secure Distributed Programming References
|
|
|
