適合 分布式系統(tǒng)工程師 的 分布式系統(tǒng)理論
Gwen Shapira曾在Cloudera做工程師，現(xiàn)在宣傳Kafka知给，他在Twitter問了以下問題渺杉，使我有所思考臭猜。
我想在分布式理論上有所提升琴儿。應該從哪開始夹界？有推薦的書？
— Gwen (Chen) Shapira (@gwenshap) August 7, 2014
我第一反應是“可以看：FLP論文羹应、paxos論文掀鹅、Byzantine將軍論文”云头。我推薦的主要閱讀材料，如果你貿(mào)然去讀淫半，你至少要閱讀6個月才會有感覺溃槐。由此可知，推薦一噸的理論論文讓你閱讀科吭，這是了解分布式系統(tǒng)的錯誤的方式（除非你在讀博士）昏滴。 論文一般是深奧、復雜的对人，而且需要一系列學習和豐富的經(jīng)驗才能感覺到其貢獻谣殊、才能把其放到對應的場景(以理解和應用)。
工程師了解分布式理論有什么好處牺弄？
很不幸姻几，幾乎沒有好的引導文章，來總結势告、提煉蛇捌、場景化 分布式系統(tǒng)理論中的重要結論和想法; 特別是 通俗易懂的引導文章 更沒有。
考慮這樣的空白區(qū)域咱台，讓我想問另一個問題：
一個分布式系統(tǒng)工程師應該了解什么樣的分布式系統(tǒng)理論络拌？
這種情況下，了解一點點理論并不是壞事回溺。我日常工作是一個分布式系統(tǒng)工程師春贸，下面會給出 我認為適合我的基本概念 們混萝。
你認為我缺失的請告知我!
準備
下面四個讀物解釋了構建分布式系統(tǒng)會遇到的困難。這些讀物都勾勒了一些列 抽象而非技術 的困難萍恕，分布式系統(tǒng)工程師必須要克服這些困難逸嘀。這些讀物的后面章節(jié)有更詳細的研究。
Distributed Systems for Fun and Profit 是一本小書允粤，它想覆蓋分布式系統(tǒng)中的一些基本問題厘熟，包括 時鐘所起的作用、不同策略的復制维哈。
Notes on distributed systems for young bloods - 非理論绳姨，而是一個很好的實踐，以讓你落到實處阔挠。
A Note on Distributed Systems - 一個經(jīng)典論文飘庄，關于 為什么你不能假裝所有遠程交互像本地對象一樣。
The fallacies of distributed computing 分布式計算的8個錯誤的推論购撼，以提醒系統(tǒng)設計者跪削。
你應該知道 安全 和 活力:
- 安全 說的是 永遠不會發(fā)生壞事。比如迂求，不返回不一致的值 是 一種 安全碾盐， 同一時刻不會選出兩個 主節(jié)點 也是 一種 安全。
- 活力 說的是 好事情終究會發(fā)生揩局。比如毫玖，對于每個api調(diào)用，一個系統(tǒng)終究會返回一個結果凌盯，這是一種 活力付枫；保證一次寫磁盤最終總能結束，這是一種 活力驰怎。
失敗和時鐘
分布式系統(tǒng)工程師面對的許多困難可以歸結為以下兩個原因:
進程可能失敗
There is no good way to tell that they have done so
進程間怎么共用時鐘阐滩、什么樣的失敗可以檢測、什么樣的算法和原語可以被正確實現(xiàn)县忌，這三者之間有很深的聯(lián)系掂榔。一般情況下，我們假設不同節(jié)點絕對無法共用時鐘(時刻值或流過了多少時間).
你應該知道:
- 失敗模型的層次：節(jié)點崩潰后關機 -> 節(jié)點崩潰后死機(經(jīng)過無限長時間后才響應) -> 惡意節(jié)點 (不遵守約定的規(guī)則) 症杏。 各個層次間逐漸將限制放松装获，你應該知道這些限制.
- 兩個節(jié)點之間，沒有任何共用時鐘鸳慈，你怎么確定一個節(jié)點上的一個事件和另一個節(jié)點上的另一個事件之間的先后順序. 這就要閱讀Lamport時鐘和更一般化的Vector時鐘, 也可以閱讀Dynamo論文.
- 允許單節(jié)點失敗對實現(xiàn)正確的分布式系統(tǒng)有多大的沖擊饱溢？(見下面FLP結論處)
- 時鐘的不同模型：同步喧伞、部分同部 走芋、 異步
- 失敗檢測是一個基本問題绩郎，失敗檢測可以平衡準確度和完成度(如果能檢測到失敗了，則可以容許不那么準確翁逞、沒完全做完)肋杖，失敗檢測也可以解決安全和活力間的沖突。把失敗檢測作為理論來研究的論文是 Chandra and Toueg’s ‘Unreliable Failure Detectors for Reliable Distributed Systems’. 不過也有一些簡短的總結-我特別喜歡this random one from Stanford.
容錯導致的基本矛盾
一個系統(tǒng)容忍一些錯誤而沒有降級 必須能當成 就像這些錯誤沒有發(fā)生過一樣挖函。這意味著系統(tǒng)的一部分要冗余地工作(同樣的功能部署多個節(jié)點)状植，冗余是絕對必要的，冗余一般會帶來性能和資源的消耗怨喘。這就是給一個系統(tǒng)添加冗余的基本矛盾津畸。
你應該知道：
- 確保串行單復制的多數(shù)派技術. 見 Skeen’s original paper, 不過或許更好的是 Wikipedia條目.
(多數(shù)派中有一個是主節(jié)點,其余為從節(jié)點，以主節(jié)點接收到的寫請求序列為準[即串行]必怜，主節(jié)點單方面的要求從節(jié)點們接受主節(jié)點的寫請求序列[從節(jié)點不得反抗肉拓、不得有異議：從節(jié)點是誠實的非惡意的、遵守全局規(guī)則的梳庆、非拜占庭的])
最終一致性膏执、其他技術 以 對系統(tǒng)行為做更弱的保證 為代價 來 設法避開 此矛盾 . 可以看 Dynamo 論文 , 不過 必須要讀 Pat Helland的論文 經(jīng)典 Life Beyond Transactions .
基本原語
在分布式系統(tǒng)中驻售，很少有約定的基本構建塊，更多的是處于形成中的基本構建塊更米。你應該知道下面的問題是什么欺栗，并且從哪能找到他們的解決方案：
- 主節(jié)點選舉 (例如 Bully 算法)
一致快照 (比如 這個來自 Chandy and Lamport的經(jīng)典論文 )
一致性 (見上面 2PC 、 Paxos 處)
- 分布式狀態(tài)機復制 (看Wikipedia 就行, Lampson的 論文 是權威但是太枯燥了).
- 廣播 - 同時發(fā)送消息給集群
* [原子廣播](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.4709&rep=rep1&type=pdf) - 你能發(fā)送消息給一集群征峦，使得要么集群中的所有節(jié)點都收到了這條信息纸巷、要么集群中全部節(jié)點都沒收到此消息?(這就是原子廣播)
* Gossip ([經(jīng)典論文](http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/CSL-89-1_Epidemic_Algorithms_for_Replicated_Database_Maintenance.pdf))
* [因果廣播](https://www.cs.cornell.edu/courses/cs614/2003sp/papers/BSS91.pdf) (也可以看看 [Birman](https://www.cs.rice.edu/~alc/comp520/papers/Cheriton_Skeen.pdf)和[forth](https://www.cs.princeton.edu/courses/archive/fall07/cos518/papers/catocs-limits-response.pdf) ).
-
鏈式復制 (將節(jié)點們放進一個虛擬鏈表中，從而可以干凈的確保寫請求的一致性和順序 ).
對負載中讀請求占絕大多數(shù)的一系列改良
基礎結論
有些事實只需要主觀理解(不需要關注證明).
如果節(jié)點間可能丟失消息[:P]眶痰，那么你不可能 既 實現(xiàn)一致性存儲[:C] 又 響應所有時刻的請求[:A]. 這就是 CAP理論.
在一個異步系統(tǒng)中瘤旨，一致性不可能以這樣一個途徑實現(xiàn)：既a) 總是正確的 ； 又b) 總是能結束 即使只有一個節(jié)點可能以 崩潰-*停止 失敗 (FLP結論). 在看證明之前竖伯，看下我以簡明的方式解釋FLP結論的論文 Papers We Love SF talk . 建議: 沒有理解證明的需要.
(一個異步系統(tǒng)中存哲，假設節(jié)點崩潰后停止而不是奔潰后又恢復；1七婴、要確保結果總是正確的祟偷，2、每次寫請求能夠在有限時間內(nèi)返回結果打厘。這兩點沒法同時滿足：這就是FLP結論)
一般地修肠，只進行少于2輪的消息傳遞，不可能達成一致性 .
原子廣播和一致性户盯，二者的難度精確的相等嵌施。更直白的說饲化，如果你能解原子廣播，那么你也能解一致性吗伤，反之亦然吃靠。 Chandra 和 Toueg 證明了這一點, 但是你只需要知道這個論斷是成立的。
真實系統(tǒng)
最重要的足淆、應該不斷重復的實踐是：讀新的巢块、真實的系統(tǒng)的描述，并評價他們設計的決定巧号。 下面是建議的系統(tǒng)：
Google:
Not Google:
Postscript 結尾
如果你馴服了這個列表中的所有概念和技術族奢，我很樂意和你聊聊Cloudera的分布式系統(tǒng)工程師職位。
