來源：COOLSHELL https://coolshell.cn/articles/10910.html
當(dāng)我們?cè)谏a(chǎn)線上用一臺(tái)服務(wù)器來提供數(shù)據(jù)服務(wù)的時(shí)候萨驶，我會(huì)遇到如下的兩個(gè)問題：
1）一臺(tái)服務(wù)器的性能不足以提供足夠的能力服務(wù)于所有的網(wǎng)絡(luò)請(qǐng)求。
2）我們總是害怕我們的這臺(tái)服務(wù)器停機(jī)顷编，造成服務(wù)不可用或是數(shù)據(jù)丟失绳矩。
于是我們不得不對(duì)我們的服務(wù)器進(jìn)行擴(kuò)展锦针，加入更多的機(jī)器來分擔(dān)性能上的問題弟蚀，以及來解決單點(diǎn)故障問題拌消。 通常挑豌，我們會(huì)通過兩種手段來擴(kuò)展我們的數(shù)據(jù)服務(wù)：
1）數(shù)據(jù)分區(qū)：就是把數(shù)據(jù)分塊放在不同的服務(wù)器上（如：uid % 16，一致性哈希等）墩崩。
2）數(shù)據(jù)鏡像：讓所有的服務(wù)器都有相同的數(shù)據(jù)氓英，提供相當(dāng)?shù)姆?wù)。
對(duì)于第一種情況鹦筹，我們無法解決數(shù)據(jù)丟失的問題铝阐，單臺(tái)服務(wù)器出問題時(shí)，會(huì)有部分?jǐn)?shù)據(jù)丟失铐拐。所以徘键，數(shù)據(jù)服務(wù)的高可用性只能通過第二種方法來完成——數(shù)據(jù)的冗余存儲(chǔ)（一般工業(yè)界認(rèn)為比較安全的備份數(shù)應(yīng)該是3份练对，如：Hadoop和Dynamo）。 但是吹害，加入更多的機(jī)器螟凭，會(huì)讓我們的數(shù)據(jù)服務(wù)變得很復(fù)雜，尤其是跨服務(wù)器的事務(wù)處理它呀，也就是跨服務(wù)器的數(shù)據(jù)一致性螺男。這個(gè)是一個(gè)很難的問題。 讓我們用最經(jīng)典的Use Case：“A帳號(hào)向B帳號(hào)匯錢”來說明一下纵穿，熟悉RDBMS事務(wù)的都知道從帳號(hào)A到帳號(hào)B需要6個(gè)操作：
從A帳號(hào)中把余額讀出來下隧。
對(duì)A帳號(hào)做減法操作。
把結(jié)果寫回A帳號(hào)中谓媒。
從B帳號(hào)中把余額讀出來淆院。
對(duì)B帳號(hào)做加法操作。
把結(jié)果寫回B帳號(hào)中句惯。
為了數(shù)據(jù)的一致性迫筑，這6件事，要么都成功做完宗弯，要么都不成功脯燃，而且這個(gè)操作的過程中，對(duì)A蒙保、B帳號(hào)的其它訪問必需鎖死辕棚，所謂鎖死就是要排除其它的讀寫操作，不然會(huì)有臟數(shù)據(jù)的問題邓厕，這就是事務(wù)逝嚎。那么，我們?cè)诩尤肓烁嗟臋C(jī)器后详恼，這個(gè)事情會(huì)變得復(fù)雜起來：
1）在數(shù)據(jù)分區(qū)的方案中：如果A帳號(hào)和B帳號(hào)的數(shù)據(jù)不在同一臺(tái)服務(wù)器上怎么辦补君？我們需要一個(gè)跨機(jī)器的事務(wù)處理。也就是說昧互，如果A的扣錢成功了挽铁，但B的加錢不成功，我們還要把A的操作給回滾回去敞掘。這在跨機(jī)器的情況下叽掘，就變得比較復(fù)雜了。
2）在數(shù)據(jù)鏡像的方案中：A帳號(hào)和B帳號(hào)間的匯款是可以在一臺(tái)機(jī)器上完成的玖雁，但是別忘了我們有多臺(tái)機(jī)器存在A帳號(hào)和B帳號(hào)的副本更扁。如果對(duì)A帳號(hào)的匯錢有兩個(gè)并發(fā)操作（要匯給B和C），這兩個(gè)操作發(fā)生在不同的兩臺(tái)服務(wù)器上怎么辦？也就是說浓镜，在數(shù)據(jù)鏡像中溃列，在不同的服務(wù)器上對(duì)同一個(gè)數(shù)據(jù)的寫操作怎么保證其一致性，保證數(shù)據(jù)不沖突膛薛？
同時(shí)听隐，我們還要考慮性能的因素，如果不考慮性能的話相叁，事務(wù)得到保證并不困難，系統(tǒng)慢一點(diǎn)就行了辽幌。除了考慮性能外增淹，我們還要考慮可用性，也就是說乌企，一臺(tái)機(jī)器沒了虑润，數(shù)據(jù)不丟失，服務(wù)可由別的機(jī)器繼續(xù)提供加酵。 于是拳喻，我們需要重點(diǎn)考慮下面的這么幾個(gè)情況：
1）容災(zāi)：數(shù)據(jù)不丟、結(jié)點(diǎn)的Failover
2）數(shù)據(jù)的一致性：事務(wù)處理
3）性能：吞吐量 猪腕、 響應(yīng)時(shí)間
前面說過冗澈，要解決數(shù)據(jù)不丟，只能通過數(shù)據(jù)冗余的方法陋葡，就算是數(shù)據(jù)分區(qū)亚亲，每個(gè)區(qū)也需要進(jìn)行數(shù)據(jù)冗余處理。這就是數(shù)據(jù)副本：當(dāng)出現(xiàn)某個(gè)節(jié)點(diǎn)的數(shù)據(jù)丟失時(shí)可以從副本讀到腐缤，數(shù)據(jù)副本是分布式系統(tǒng)解決數(shù)據(jù)丟失異常的唯一手段捌归。所以，在這篇文章中岭粤，簡單起見惜索，我們只討論在數(shù)據(jù)冗余情況下考慮數(shù)據(jù)的一致性和性能的問題。簡單說來：
1）要想讓數(shù)據(jù)有高可用性剃浇，就得寫多份數(shù)據(jù)巾兆。
2）寫多份的問題會(huì)導(dǎo)致數(shù)據(jù)一致性的問題。
3）數(shù)據(jù)一致性的問題又會(huì)引發(fā)性能問題
這就是軟件開發(fā)虎囚，按下了葫蘆起了瓢臼寄。
一致性模型
說起數(shù)據(jù)一致性來說，簡單說有三種類型（當(dāng)然溜宽，如果細(xì)分的話吉拳，還有很多一致性模型，如：順序一致性适揉，F(xiàn)IFO一致性留攒，會(huì)話一致性煤惩，單讀一致性，單寫一致性炼邀，但為了本文的簡單易讀魄揉，我只說下面三種）：
1）Weak 弱一致性：當(dāng)你寫入一個(gè)新值后，讀操作在數(shù)據(jù)副本上可能讀出來拭宁，也可能讀不出來洛退。比如：某些cache系統(tǒng)，網(wǎng)絡(luò)游戲其它玩家的數(shù)據(jù)和你沒什么關(guān)系杰标，VOIP這樣的系統(tǒng)兵怯，或是百度搜索引擎（呵呵）。
2）Eventually 最終一致性：當(dāng)你寫入一個(gè)新值后腔剂，有可能讀不出來媒区，但在某個(gè)時(shí)間窗口之后保證最終能讀出來。比如：DNS掸犬，電子郵件袜漩、Amazon S3，Google搜索引擎這樣的系統(tǒng)湾碎。
3）Strong 強(qiáng)一致性：新的數(shù)據(jù)一旦寫入宙攻，在任意副本任意時(shí)刻都能讀到新值。比如：文件系統(tǒng)介褥，RDBMS粘优，Azure Table都是強(qiáng)一致性的。
從這三種一致型的模型上來說呻顽，我們可以看到雹顺，Weak和Eventually一般來說是異步冗余的，而Strong一般來說是同步冗余的廊遍，異步的通常意味著更好的性能嬉愧，但也意味著更復(fù)雜的狀態(tài)控制。同步意味著簡單喉前，但也意味著性能下降没酣。 好，讓我們由淺入深卵迂，一步一步地來看有哪些技術(shù)：
Master-Slave
首先是Master-Slave結(jié)構(gòu)裕便，對(duì)于這種加構(gòu)，Slave一般是Master的備份见咒。在這樣的系統(tǒng)中偿衰，一般是如下設(shè)計(jì)的：
1）讀寫請(qǐng)求都由Master負(fù)責(zé)。
2）寫請(qǐng)求寫到Master上后，由Master同步到Slave上下翎。
從Master同步到Slave上缤言，你可以使用異步，也可以使用同步视事，可以使用Master來push胆萧，也可以使用Slave來pull。 通常來說是Slave來周期性的pull俐东，所以跌穗，是最終一致性。這個(gè)設(shè)計(jì)的問題是虏辫，如果Master在pull周期內(nèi)垮掉了蚌吸，那么會(huì)導(dǎo)致這個(gè)時(shí)間片內(nèi)的數(shù)據(jù)丟失。如果你不想讓數(shù)據(jù)丟掉乒裆，Slave只能成為Read-Only的方式等Master恢復(fù)套利。
當(dāng)然推励，如果你可以容忍數(shù)據(jù)丟掉的話鹤耍，你可以馬上讓Slave代替Master工作（對(duì)于只負(fù)責(zé)計(jì)算的結(jié)點(diǎn)來說，沒有數(shù)據(jù)一致性和數(shù)據(jù)丟失的問題验辞，Master-Slave的方式就可以解決單點(diǎn)問題了） 當(dāng)然稿黄，Master Slave也可以是強(qiáng)一致性的， 比如：當(dāng)我們寫Master的時(shí)候跌造，Master負(fù)責(zé)先寫自己杆怕，等成功后，再寫Slave壳贪，兩者都成功后返回成功陵珍，整個(gè)過程是同步的，如果寫Slave失敗了违施，那么兩種方法互纯，一種是標(biāo)記Slave不可用報(bào)錯(cuò)并繼續(xù)服務(wù)（等Slave恢復(fù)后同步Master的數(shù)據(jù)，可以有多個(gè)Slave磕蒲，這樣少一個(gè)留潦，還有備份，就像前面說的寫三份那樣）辣往，另一種是回滾自己并返回寫失敗兔院。（注：一般不先寫Slave，因?yàn)槿绻麑慚aster自己失敗后站削，還要回滾Slave坊萝，此時(shí)如果回滾Slave失敗，就得手工訂正數(shù)據(jù)了）你可以看到，如果Master-Slave需要做成強(qiáng)一致性有多復(fù)雜屹堰。
Master-Master
Master-Master肛冶，又叫Multi-master，是指一個(gè)系統(tǒng)存在兩個(gè)或多個(gè)Master扯键，每個(gè)Master都提供read-write服務(wù)睦袖。這個(gè)模型是Master-Slave的加強(qiáng)版，數(shù)據(jù)間同步一般是通過Master間的異步完成荣刑，所以是最終一致性馅笙。 Master-Master的好處是，一臺(tái)Master掛了厉亏，別的Master可以正常做讀寫服務(wù)董习，他和Master-Slave一樣，當(dāng)數(shù)據(jù)沒有被復(fù)制到別的Master上時(shí)爱只，數(shù)據(jù)會(huì)丟失皿淋。很多數(shù)據(jù)庫都支持Master-Master的Replication的機(jī)制。
另外恬试，如果多個(gè)Master對(duì)同一個(gè)數(shù)據(jù)進(jìn)行修改的時(shí)候窝趣，這個(gè)模型的惡夢(mèng)就出現(xiàn)了——對(duì)數(shù)據(jù)間的沖突合并，這并不是一件容易的事情训柴⊙剖妫看看Dynamo的Vector Clock的設(shè)計(jì)（記錄數(shù)據(jù)的版本號(hào)和修改者）就知道這個(gè)事并不那么簡單，而且Dynamo對(duì)數(shù)據(jù)沖突這個(gè)事是交給用戶自己搞的幻馁。就像我們的SVN源碼沖突一樣洗鸵，對(duì)于同一行代碼的沖突，只能交給開發(fā)者自己來處理仗嗦。（在本文后后面會(huì)討論一下Dynamo的Vector Clock）
Two/Three Phase Commit
這個(gè)協(xié)議的縮寫又叫2PC膘滨，中文叫兩階段提交。在分布式系統(tǒng)中稀拐，每個(gè)節(jié)點(diǎn)雖然可以知曉自己的操作時(shí)成功或者失敗火邓，卻無法知道其他節(jié)點(diǎn)的操作的成功或失敗。當(dāng)一個(gè)事務(wù)跨越多個(gè)節(jié)點(diǎn)時(shí)钩蚊，為了保持事務(wù)的ACID特性贡翘，需要引入一個(gè)作為協(xié)調(diào)者的組件來統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫入磁盤等等)。 兩階段提交的算法如下：
第一階段：
協(xié)調(diào)者會(huì)問所有的參與者結(jié)點(diǎn)砰逻，是否可以執(zhí)行提交操作鸣驱。
各個(gè)參與者開始事務(wù)執(zhí)行的準(zhǔn)備工作：如：為資源上鎖，預(yù)留資源蝠咆，寫undo/redo log……
參與者響應(yīng)協(xié)調(diào)者踊东，如果事務(wù)的準(zhǔn)備工作成功北滥，則回應(yīng)“可以提交”，否則回應(yīng)“拒絕提交”闸翅。
第二階段：
如果所有的參與者都回應(yīng)“可以提交”再芋，那么，協(xié)調(diào)者向所有的參與者發(fā)送“正式提交”的命令坚冀。參與者完成正式提交济赎，并釋放所有資源，然后回應(yīng)“完成”记某，協(xié)調(diào)者收集各結(jié)點(diǎn)的“完成”回應(yīng)后結(jié)束這個(gè)Global Transaction司训。
如果有一個(gè)參與者回應(yīng)“拒絕提交”，那么液南，協(xié)調(diào)者向所有的參與者發(fā)送“回滾操作”壳猜，并釋放所有資源，然后回應(yīng)“回滾完成”滑凉，協(xié)調(diào)者收集各結(jié)點(diǎn)的“回滾”回應(yīng)后统扳，取消這個(gè)Global Transaction。
我們可以看到畅姊，2PC說白了就是第一階段做Vote咒钟，第二階段做決定的一個(gè)算法，也可以看到2PC這個(gè)事是強(qiáng)一致性的算法涡匀。在前面我們討論過Master-Slave的強(qiáng)一致性策略盯腌，和2PC有點(diǎn)相似溉知，只不過2PC更為保守一些——先嘗試再提交陨瘩。 2PC用的是比較多的，在一些系統(tǒng)設(shè)計(jì)中级乍，會(huì)串聯(lián)一系列的調(diào)用舌劳，比如：A -> B -> C -> D，每一步都會(huì)分配一些資源或改寫一些數(shù)據(jù)玫荣。比如我們B2C網(wǎng)上購物的下單操作在后臺(tái)會(huì)有一系列的流程需要做甚淡。如果我們一步一步地做，就會(huì)出現(xiàn)這樣的問題捅厂，如果某一步做不下去了贯卦，那么前面每一次所分配的資源需要做反向操作把他們都回收掉，所以焙贷，操作起來比較復(fù)雜∧旄睿現(xiàn)在很多處理流程（Workflow）都會(huì)借鑒2PC這個(gè)算法，使用 try -> confirm的流程來確保整個(gè)流程的能夠成功完成辙芍。 舉個(gè)通俗的例子啡彬，西方教堂結(jié)婚的時(shí)候羹与，都有這樣的橋段：
1）牧師分別問新郎和新娘：你是否愿意……不管生老病死……（詢問階段）
2）當(dāng)新郎和新娘都回答愿意后（鎖定一生的資源），牧師就會(huì)說：我宣布你們……（事務(wù)提交）
這是多么經(jīng)典的一個(gè)兩階段提交的事務(wù)處理庶灿。 另外纵搁，我們也可以看到其中的一些問題， A）其中一個(gè)是同步阻塞操作往踢，這個(gè)事情必然會(huì)非常大地影響性能腾誉。 B）另一個(gè)主要的問題是在TimeOut上，比如峻呕，
1）如果第一階段中妄辩，參與者沒有收到詢問請(qǐng)求，或是參與者的回應(yīng)沒有到達(dá)協(xié)調(diào)者山上。那么眼耀，需要協(xié)調(diào)者做超時(shí)處理，一旦超時(shí)佩憾，可以當(dāng)作失敗哮伟，也可以重試。
2）如果第二階段中妄帘，正式提交發(fā)出后楞黄，如果有的參與者沒有收到，或是參與者提交/回滾后的確認(rèn)信息沒有返回抡驼，一旦參與者的回應(yīng)超時(shí)鬼廓，要么重試，要么把那個(gè)參與者標(biāo)記為問題結(jié)點(diǎn)剔除整個(gè)集群致盟，這樣可以保證服務(wù)結(jié)點(diǎn)都是數(shù)據(jù)一致性的碎税。
3）糟糕的情況是，第二階段中馏锡，如果參與者收不到協(xié)調(diào)者的commit/fallback指令雷蹂，參與者將處于“狀態(tài)未知”階段，參與者完全不知道要怎么辦杯道，比如：如果所有的參與者完成第一階段的回復(fù)后（可能全部yes匪煌，可能全部no，可能部分yes部分no）党巾，如果協(xié)調(diào)者在這個(gè)時(shí)候掛掉了萎庭。那么所有的結(jié)點(diǎn)完全不知道怎么辦（問別的參與者都不行）。為了一致性齿拂，要么死等協(xié)調(diào)者驳规，要么重發(fā)第一階段的yes/no命令。
兩段提交最大的問題就是第3）項(xiàng)创肥，如果第一階段完成后达舒，參與者在第二階沒有收到?jīng)Q策值朋，那么數(shù)據(jù)結(jié)點(diǎn)會(huì)進(jìn)入“不知所措”的狀態(tài)，這個(gè)狀態(tài)會(huì)block住整個(gè)事務(wù)巩搏。也就是說昨登，協(xié)調(diào)者Coordinator對(duì)于事務(wù)的完成非常重要，Coordinator的可用性是個(gè)關(guān)鍵贯底。 因些丰辣，我們引入三段提交，三段提交在Wikipedia上的描述如下禽捆，他把二段提交的第一個(gè)段break成了兩段：詢問笙什，然后再鎖資源。最后真正提交胚想。三段提交的示意圖如下：
三段提交的核心理念是：在詢問的時(shí)候并不鎖定資源琐凭，除非所有人都同意了，才開始鎖資源浊服。
理論上來說统屈，如果第一階段所有的結(jié)點(diǎn)返回成功，那么有理由相信成功提交的概率很大牙躺。這樣一來愁憔，可以降低參與者Cohorts的狀態(tài)未知的概率。也就是說孽拷，一旦參與者收到了PreCommit吨掌，意味他知道大家其實(shí)都同意修改了。這一點(diǎn)很重要脓恕。下面我們來看一下3PC的狀態(tài)遷移圖：（注意圖中的虛線膜宋，那些F,T是Failuer或Timeout，其中的：狀態(tài)含義是 q – Query进肯，a – Abort激蹲，w – Wait棉磨，p – PreCommit江掩，c – Commit）
從上圖的狀態(tài)變化圖我們可以從虛線（那些F,T是Failuer或Timeout）看到——如果結(jié)點(diǎn)處在P狀態(tài)（PreCommit）的時(shí)候發(fā)生了F/T的問題，三段提交比兩段提交的好處是乘瓤，三段提交可以繼續(xù)直接把狀態(tài)變成C狀態(tài)（Commit）环形，而兩段提交則不知所措。
其實(shí)衙傀，三段提交是一個(gè)很復(fù)雜的事情抬吟，實(shí)現(xiàn)起來相當(dāng)難，而且也有一些問題统抬。
看到這里火本，我相信你有很多很多的問題，你一定在思考2PC/3PC中各種各樣的失敗場景，你會(huì)發(fā)現(xiàn)Timeout是個(gè)非常難處理的事情掉房，因?yàn)榫W(wǎng)絡(luò)上的Timeout在很多時(shí)候讓你無所事從仗岖，你也不知道對(duì)方是做了還是沒有做。于是你好好的一個(gè)狀態(tài)機(jī)就因?yàn)門imeout成了個(gè)擺設(shè)擎析。
一個(gè)網(wǎng)絡(luò)服務(wù)會(huì)有三種狀態(tài)：1）Success簿盅，2）Failure，3）Timeout揍魂，第三個(gè)絕對(duì)是惡夢(mèng)桨醋，尤其在你需要維護(hù)狀態(tài)的時(shí)候。
Two Generals Problem（兩將軍問題）
Two Generals Problem 兩將軍問題是這么一個(gè)思維性實(shí)驗(yàn)問題： 有兩支軍隊(duì)现斋，它們分別有一位將軍領(lǐng)導(dǎo)喜最，現(xiàn)在準(zhǔn)備攻擊一座修筑了防御工事的城市。這兩支軍隊(duì)都駐扎在那座城市的附近庄蹋，分占一座山頭返顺。一道山谷把兩座山分隔開來，并且兩位將軍唯一的通信方式就是派各自的信使來往于山谷兩邊蔓肯。不幸的是遂鹊，這個(gè)山谷已經(jīng)被那座城市的保衛(wèi)者占領(lǐng)，并且存在一種可能蔗包，那就是任何被派出的信使通過山谷是會(huì)被捕秉扑。 請(qǐng)注意，雖然兩位將軍已經(jīng)就攻擊那座城市達(dá)成共識(shí)调限，但在他們各自占領(lǐng)山頭陣地之前舟陆，并沒有就進(jìn)攻時(shí)間達(dá)成共識(shí)。兩位將軍必須讓自己的軍隊(duì)同時(shí)進(jìn)攻城市才能取得成功耻矮。因此秦躯，他們必須互相溝通，以確定一個(gè)時(shí)間來攻擊裆装，并同意就在那時(shí)攻擊踱承。如果只有一個(gè)將軍進(jìn)行攻擊，那么這將是一個(gè)災(zāi)難性的失敗哨免。 這個(gè)思維實(shí)驗(yàn)就包括考慮他們?nèi)绾稳プ鲞@件事情茎活。下面是我們的思考：
1）第一位將軍先發(fā)送一段消息“讓我們?cè)谏衔?點(diǎn)開始進(jìn)攻”。然而琢唾，一旦信使被派遣载荔，他是否通過了山谷，第一位將軍就不得而知了采桃。任何一點(diǎn)的不確定性都會(huì)使得第一位將軍攻擊猶豫懒熙，因?yàn)槿绻诙粚④姴荒茉谕粫r(shí)刻發(fā)動(dòng)攻擊丘损，那座城市的駐軍就會(huì)擊退他的軍隊(duì)的進(jìn)攻，導(dǎo)致他的軍對(duì)被摧毀工扎。
2）知道了這一點(diǎn)号俐，第二位將軍就需要發(fā)送一個(gè)確認(rèn)回條：“我收到您的郵件，并會(huì)在9點(diǎn)的攻擊定庵±舳觯”但是，如果帶著確認(rèn)消息的信使被抓怎么辦蔬浙？所以第二位將軍會(huì)猶豫自己的確認(rèn)消息是否能到達(dá)猪落。
3）于是，似乎我們還要讓第一位將軍再發(fā)送一條確認(rèn)消息——“我收到了你的確認(rèn)”畴博。然而笨忌，如果這位信使被抓怎么辦呢？
4）這樣一來俱病，是不是我們還要第二位將軍發(fā)送一個(gè)“確認(rèn)收到你的確認(rèn)”的信息官疲。
靠，于是你會(huì)發(fā)現(xiàn)亮隙，這事情很快就發(fā)展成為不管發(fā)送多少個(gè)確認(rèn)消息途凫，都沒有辦法來保證兩位將軍有足夠的自信自己的信使沒有被敵軍捕獲。
這個(gè)問題是無解的溢吻。兩個(gè)將軍問題和它的無解證明首先由E.A.Akkoyunlu,K.Ekanadham和R.V.Huber于1975年在《一些限制與折衷的網(wǎng)絡(luò)通信設(shè)計(jì)》一文中發(fā)表维费，就在這篇文章的第73頁中一段描述兩個(gè)黑幫之間的通信中被闡明。 1978年促王，在Jim Gray的《數(shù)據(jù)庫操作系統(tǒng)注意事項(xiàng)》一書中（從第465頁開始）被命名為兩個(gè)將軍悖論犀盟。作為兩個(gè)將軍問題的定義和無解性的證明的來源，這一參考被廣泛提及蝇狼。
這個(gè)實(shí)驗(yàn)意在闡明：試圖通過建立在一個(gè)不可靠的連接上的交流來協(xié)調(diào)一項(xiàng)行動(dòng)的隱患和設(shè)計(jì)上的巨大挑戰(zhàn)阅畴。
從工程上來說，一個(gè)解決兩個(gè)將軍問題的實(shí)際方法是使用一個(gè)能夠承受通信信道不可靠性的方案迅耘，并不試圖去消除這個(gè)不可靠性贱枣，但要將不可靠性削減到一個(gè)可以接受的程度。比如豹障，第一位將軍排出了100位信使并預(yù)計(jì)他們都被捕的可能性很小冯事。在這種情況下，不管第二位將軍是否會(huì)攻擊或者受到任何消息血公，第一位將軍都會(huì)進(jìn)行攻擊。另外缓熟，第一位將軍可以發(fā)送一個(gè)消息流累魔，而第二位將軍可以對(duì)其中的每一條消息發(fā)送一個(gè)確認(rèn)消息摔笤，這樣如果每條消息都被接收到，兩位將軍會(huì)感覺更好垦写。然而我們可以從證明中看出吕世，他們倆都不能肯定這個(gè)攻擊是可以協(xié)調(diào)的。他們沒有算法可用（比如梯投，收到4條以上的消息就攻擊）能夠確保防止僅有一方攻擊命辖。再者，第一位將軍還可以為每條消息編號(hào)分蓖，說這是1號(hào)尔艇，2號(hào)……直到n號(hào)。這種方法能讓第二位將軍知道通信信道到底有多可靠么鹤，并且返回合適的數(shù)量的消息來確保最后一條消息被接收到终娃。如果信道是可靠的話，只要一條消息就行了蒸甜，其余的就幫不上什么忙了棠耕。最后一條和第一條消息丟失的概率是相等的。
兩將軍問題可以擴(kuò)展成更變態(tài)的拜占庭將軍問題 (Byzantine Generals Problem)柠新，其故事背景是這樣的：拜占庭位于現(xiàn)在土耳其的伊斯坦布爾窍荧，是東羅馬帝國的首都。由于當(dāng)時(shí)拜占庭羅馬帝國國土遼闊恨憎，為了防御目的搅荞，因此每個(gè)軍隊(duì)都分隔很遠(yuǎn)，將軍與將軍之間只能靠信差傳消息框咙。 在戰(zhàn)爭的時(shí)候咕痛，拜占庭軍隊(duì)內(nèi)所有將軍必需達(dá)成一致的共識(shí)，決定是否有贏的機(jī)會(huì)才去攻打敵人的陣營喇嘱。但是茉贡，軍隊(duì)可能有叛徒和敵軍間諜，這些叛徒將軍們會(huì)擾亂或左右決策的過程者铜。這時(shí)候腔丧，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達(dá)成一致的協(xié)議作烟，這就是拜占庭將軍問題愉粤。
Paxos算法
Wikipedia上的各種Paxos算法的描述非常詳細(xì)，大家可以去圍觀一下拿撩。
Paxos 算法解決的問題是在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致衣厘，保證不論發(fā)生以上任何異常，都不會(huì)破壞決議的一致性。一個(gè)典型的場景是影暴，在一個(gè)分布式數(shù)據(jù)庫系統(tǒng)中错邦，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列型宙，那么他們最后能得到一個(gè)一致的狀態(tài)撬呢。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)「一致性算法」以保證每個(gè)節(jié)點(diǎn)看到的指令一致妆兑。一個(gè)通用的一致性算法可以應(yīng)用在許多場景中魂拦，是分布式計(jì)算中的重要問題。從20世紀(jì)80年代起對(duì)于一致性算法的研究就沒有停止過搁嗓。
Notes：Paxos算法是萊斯利·蘭伯特（Leslie Lamport芯勘，就是 LaTeX 中的”La”，此人現(xiàn)在在微軟研究院）于1990年提出的一種基于消息傳遞的一致性算法谱姓。由于算法難以理解起初并沒有引起人們的重視借尿，使Lamport在八年后1998年重新發(fā)表到ACM Transactions on Computer Systems上（The Part-Time Parliament）。即便如此paxos算法還是沒有得到重視屉来，2001年Lamport 覺得同行無法接受他的幽默感路翻，于是用容易接受的方法重新表述了一遍（Paxos Made Simple）∏芽浚可見Lamport對(duì)Paxos算法情有獨(dú)鐘茂契。近幾年P(guān)axos算法的普遍使用也證明它在分布式一致性算法中的重要地位。2006年Google的三篇論文初現(xiàn)“云”的端倪慨绳，其中的Chubby Lock服務(wù)使用Paxos作為Chubby Cell中的一致性算法掉冶，Paxos的人氣從此一路狂飆。（Lamport 本人在 他的blog 中描寫了他用9年時(shí)間發(fā)表這個(gè)算法的前前后后）
注：Amazon的AWS中脐雪，所有的云服務(wù)都基于一個(gè)ALF（Async Lock Framework）的框架實(shí)現(xiàn)的厌小，這個(gè)ALF用的就是Paxos算法。我在Amazon的時(shí)候战秋，看內(nèi)部的分享視頻時(shí)璧亚，設(shè)計(jì)者在內(nèi)部的Principle Talk里說他參考了ZooKeeper的方法，但他用了另一種比ZooKeeper更易讀的方式實(shí)現(xiàn)了這個(gè)算法脂信。
簡單說來癣蟋，Paxos的目的是讓整個(gè)集群的結(jié)點(diǎn)對(duì)某個(gè)值的變更達(dá)成一致。Paxos算法基本上來說是個(gè)民主選舉的算法——大多數(shù)的決定會(huì)成個(gè)整個(gè)集群的統(tǒng)一決定狰闪。任何一個(gè)點(diǎn)都可以提出要修改某個(gè)數(shù)據(jù)的提案疯搅，是否通過這個(gè)提案取決于這個(gè)集群中是否有超過半數(shù)的結(jié)點(diǎn)同意（所以Paxos算法需要集群中的結(jié)點(diǎn)是單數(shù)）。
這個(gè)算法有兩個(gè)階段（假設(shè)這個(gè)有三個(gè)結(jié)點(diǎn)：A埋泵，B幔欧，C）：
第一階段：Prepare階段
A把申請(qǐng)修改的請(qǐng)求Prepare Request發(fā)給所有的結(jié)點(diǎn)A，B，C琐馆。注意规阀，Paxos算法會(huì)有一個(gè)Sequence Number（你可以認(rèn)為是一個(gè)提案號(hào)恒序，這個(gè)數(shù)不斷遞增瘦麸，而且是唯一的，也就是說A和B不可能有相同的提案號(hào)）歧胁，這個(gè)提案號(hào)會(huì)和修改請(qǐng)求一同發(fā)出滋饲，任何結(jié)點(diǎn)在“Prepare階段”時(shí)都會(huì)拒絕其值小于當(dāng)前提案號(hào)的請(qǐng)求。所以喊巍，結(jié)點(diǎn)A在向所有結(jié)點(diǎn)申請(qǐng)修改請(qǐng)求的時(shí)候屠缭，需要帶一個(gè)提案號(hào)，越新的提案崭参，這個(gè)提案號(hào)就越是是最大的呵曹。
如果接收結(jié)點(diǎn)收到的提案號(hào)n大于其它結(jié)點(diǎn)發(fā)過來的提案號(hào)，這個(gè)結(jié)點(diǎn)會(huì)回應(yīng)Yes（本結(jié)點(diǎn)上最新的被批準(zhǔn)提案號(hào)）何暮，并保證不接收其它<n的提案奄喂。這樣一來，結(jié)點(diǎn)上在Prepare階段里總是會(huì)對(duì)最新的提案做承諾海洼。
優(yōu)化：在上述 prepare 過程中跨新，如果任何一個(gè)結(jié)點(diǎn)發(fā)現(xiàn)存在一個(gè)更高編號(hào)的提案，則需要通知 提案人坏逢，提醒其中斷這次提案域帐。
第二階段：Accept階段
如果提案者A收到了超過半數(shù)的結(jié)點(diǎn)返回的Yes，然后他就會(huì)向所有的結(jié)點(diǎn)發(fā)布Accept Request（同樣是整，需要帶上提案號(hào)n）肖揣，如果沒有超過半數(shù)的話，那就返回失敗浮入。
當(dāng)結(jié)點(diǎn)們收到了Accept Request后龙优，如果對(duì)于接收的結(jié)點(diǎn)來說，n是最大的了舵盈，那么陋率，它就會(huì)修改這個(gè)值，如果發(fā)現(xiàn)自己有一個(gè)更大的提案號(hào)秽晚，那么瓦糟，結(jié)點(diǎn)就會(huì)拒絕修改。
我們可以看以赴蝇，這似乎就是一個(gè)“兩段提交”的優(yōu)化菩浙。其實(shí)，2PC/3PC都是分布式一致性算法的殘次版本，Google Chubby的作者M(jìn)ike Burrows說過這個(gè)世界上只有一種一致性算法劲蜻，那就是Paxos陆淀，其它的算法都是殘次品。
****我們還可以看到：對(duì)于同一個(gè)值的在不同結(jié)點(diǎn)的修改提案就算是在接收方被亂序收到也是沒有問題的先嬉。
關(guān)于一些實(shí)例轧苫，你可以看一下Wikipedia中文中的“Paxos樣例”一節(jié)，我在這里就不再多說了疫蔓。對(duì)于Paxos算法中的一些異常示例含懊，大家可以自己推導(dǎo)一下。你會(huì)發(fā)現(xiàn)基本上來說只要保證有半數(shù)以上的結(jié)點(diǎn)存活衅胀，就沒有什么問題岔乔。
多說一下，自從Lamport在1998年發(fā)表Paxos算法后滚躯，對(duì)Paxos的各種改進(jìn)工作就從未停止雏门，其中動(dòng)作最大的莫過于2005年發(fā)表的Fast Paxos。無論何種改進(jìn)掸掏，其重點(diǎn)依然是在消息延遲與性能茁影、吞吐量之間作出各種權(quán)衡。為了容易地從概念上區(qū)分二者阅束，稱前者Classic Paxos呼胚，改進(jìn)后的后者為Fast Paxos。
總結(jié)
下圖來自：Google App Engine的co-founder Ryan Barrett在2009年的google i/o上的演講《Transaction Across DataCenter》（視頻： http://www.youtube.com/watch?v=srOgpXECblk）
前面息裸，我們說過蝇更，要想讓數(shù)據(jù)有高可用性，就需要冗余數(shù)據(jù)寫多份呼盆。寫多份的問題會(huì)帶來一致性的問題年扩，而一致性的問題又會(huì)帶來性能問題。從上圖我們可以看到访圃，我們基本上來說不可以讓所有的項(xiàng)都綠起來厨幻，這就是著名的CAP理論：一致性，可用性腿时，分區(qū)容忍性况脆，你只可能要其中的兩個(gè)。
NWR模型
最后我還想提一下Amazon Dynamo的NWR模型批糟。這個(gè)NWR模型把CAP的選擇權(quán)交給了用戶格了，讓用戶自己的選擇你的CAP中的哪兩個(gè)。
所謂NWR模型徽鼎。N代表N個(gè)備份盛末，W代表要寫入至少W份才認(rèn)為成功弹惦，R表示至少讀取R個(gè)備份。配置的時(shí)候要求W+R > N悄但。 因?yàn)閃+R > N棠隐， 所以 R > N-W 這個(gè)是什么意思呢？就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫成功的倍數(shù)的差值要大檐嚣。
也就是說助泽，每次讀取，都至少讀取到一個(gè)最新的版本净嘀。從而不會(huì)讀到一份舊數(shù)據(jù)报咳。當(dāng)我們需要高可寫的環(huán)境的時(shí)候侠讯，我們可以配置W = 1 如果N=3 那么R = 3挖藏。 這個(gè)時(shí)候只要寫任何節(jié)點(diǎn)成功就認(rèn)為成功，但是讀的時(shí)候必須從所有的節(jié)點(diǎn)都讀出數(shù)據(jù)厢漩。如果我們要求讀的高效率膜眠，我們可以配置 W=N R=1。這個(gè)時(shí)候任何一個(gè)節(jié)點(diǎn)讀成功就認(rèn)為成功溜嗜，但是寫的時(shí)候必須寫所有三個(gè)節(jié)點(diǎn)成功才認(rèn)為成功宵膨。
NWR模型的一些設(shè)置會(huì)造成臟數(shù)據(jù)的問題，因?yàn)檫@很明顯不是像Paxos一樣是一個(gè)強(qiáng)一致的東西炸宵，所以辟躏，可能每次的讀寫操作都不在同一個(gè)結(jié)點(diǎn)上，于是會(huì)出現(xiàn)一些結(jié)點(diǎn)上的數(shù)據(jù)并不是最新版本土全，但卻進(jìn)行了最新的操作捎琐。
所以，Amazon Dynamo引了數(shù)據(jù)版本的設(shè)計(jì)裹匙。也就是說瑞凑，如果你讀出來數(shù)據(jù)的版本是v1，當(dāng)你計(jì)算完成后要回填數(shù)據(jù)后概页，卻發(fā)現(xiàn)數(shù)據(jù)的版本號(hào)已經(jīng)被人更新成了v2籽御，那么服務(wù)器就會(huì)拒絕你。版本這個(gè)事就像“樂觀鎖”一樣惰匙。
但是技掏，對(duì)于分布式和NWR模型來說，版本也會(huì)有惡夢(mèng)的時(shí)候——就是版本沖的問題项鬼，比如：我們?cè)O(shè)置了N=3 W=1哑梳，如果A結(jié)點(diǎn)上接受了一個(gè)值，版本由v1 -> v2秃臣，但還沒有來得及同步到結(jié)點(diǎn)B上（異步的涧衙，應(yīng)該W=1哪工，寫一份就算成功），B結(jié)點(diǎn)上還是v1版本弧哎，此時(shí)雁比，B結(jié)點(diǎn)接到寫請(qǐng)求，按道理來說撤嫩，他需要拒絕掉偎捎，但是他一方面并不知道別的結(jié)點(diǎn)已經(jīng)被更新到v2，另一方面他也無法拒絕序攘，因?yàn)閃=1茴她，所以寫一分就成功了。于是程奠，出現(xiàn)了嚴(yán)重的版本沖突丈牢。
Amazon的Dynamo把版本沖突這個(gè)問題巧妙地回避掉了——版本沖這個(gè)事交給用戶自己來處理。
于是瞄沙，Dynamo引入了Vector Clock（矢量鐘己沛？!）這個(gè)設(shè)計(jì)。這個(gè)設(shè)計(jì)讓每個(gè)結(jié)點(diǎn)各自記錄自己的版本信息距境，也就是說申尼，對(duì)于同一個(gè)數(shù)據(jù)，需要記錄兩個(gè)事：1）誰更新的我垫桂，2）我的版本號(hào)是什么师幕。
下面，我們來看一個(gè)操作序列：
1）一個(gè)寫請(qǐng)求诬滩，第一次被節(jié)點(diǎn)A處理了霹粥。節(jié)點(diǎn)A會(huì)增加一個(gè)版本信息(A，1)碱呼。我們把這個(gè)時(shí)候的數(shù)據(jù)記做D1(A蒙挑，1)。 然后另外一個(gè)對(duì)同樣key的請(qǐng)求還是被A處理了于是有D2(A愚臀，2)忆蚀。這個(gè)時(shí)候，D2是可以覆蓋D1的姑裂，不會(huì)有沖突產(chǎn)生馋袜。
2）現(xiàn)在我們假設(shè)D2傳播到了所有節(jié)點(diǎn)(B和C)，B和C收到的數(shù)據(jù)不是從客戶產(chǎn)生的舶斧，而是別人復(fù)制給他們的欣鳖，所以他們不產(chǎn)生新的版本信息，所以現(xiàn)在B和C所持有的數(shù)據(jù)還是D2(A茴厉，2)泽台。于是A什荣，B，C上的數(shù)據(jù)及其版本號(hào)都是一樣的怀酷。
3）如果我們有一個(gè)新的寫請(qǐng)求到了B結(jié)點(diǎn)上稻爬，于是B結(jié)點(diǎn)生成數(shù)據(jù)D3(A,2; B,1)，意思是：數(shù)據(jù)D全局版本號(hào)為3蜕依，A升了兩新桅锄，B升了一次。這不就是所謂的代碼版本的log么样眠？
4）如果D3沒有傳播到C的時(shí)候又一個(gè)請(qǐng)求被C處理了友瘤，于是，以C結(jié)點(diǎn)上的數(shù)據(jù)是D4(A,2; C,1)檐束。
5）好辫秧，最精彩的事情來了：如果這個(gè)時(shí)候來了一個(gè)讀請(qǐng)求，我們要記得厢塘，我們的W=1 那么R=N=3茶没，所以R會(huì)從所有三個(gè)節(jié)點(diǎn)上讀，此時(shí)晚碾，他會(huì)讀到三個(gè)版本：
A結(jié)點(diǎn)：D2(A,2)
B結(jié)點(diǎn)：D3(A,2; B,1);
C結(jié)點(diǎn)：D4(A,2; C,1)
6）這個(gè)時(shí)候可以判斷出，D2已經(jīng)是舊版本（已經(jīng)包含在D3/D4中）喂急，可以舍棄格嘁。
7）但是D3和D4是明顯的版本沖突。于是廊移，交給調(diào)用方自己去做版本沖突處理糕簿。就像源代碼版本管理一樣。
很明顯狡孔，上述的Dynamo的配置用的是CAP里的A和P懂诗。
我非常推大家都去看看這篇論文：《Dynamo：Amazon’s Highly Available Key-Value Store》，如果英文痛苦苗膝，你可以看看譯文（譯者不詳）殃恒。
（全文完）
