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