[[108342]]

我們?cè)谏a(chǎn)線上用一臺(tái)服務(wù)器來(lái)提供數(shù)據(jù)服務(wù)的時(shí)候，我會(huì)遇到如下的兩個(gè)問(wèn)題：

1）一臺(tái)服務(wù)器的性能不足以提供足夠的能力服務(wù)于所有的網(wǎng)絡(luò)請(qǐng)求。

2）我們總是害怕我們的這臺(tái)服務(wù)器停機(jī)，造成服務(wù)不可用或是數(shù)據(jù)丟失。

于是我們不得不對(duì)我們的服務(wù)器進(jìn)行擴(kuò)展，加入更多的機(jī)器來(lái)分擔(dān)性能上的問(wèn)題，以及來(lái)解決單點(diǎn)故障問(wèn)題。 通常，我們會(huì)通過(guò)兩種手段來(lái)擴(kuò)展我們的數(shù)據(jù)服務(wù)：

1）數(shù)據(jù)分區(qū)：就是把數(shù)據(jù)分塊放在不同的服務(wù)器上（如：uid % 16，一致性哈希等）。

2）數(shù)據(jù)鏡像：讓所有的服務(wù)器都有相同的數(shù)據(jù)，提供相當(dāng)?shù)姆?wù)。

對(duì)于第一種情況，我們無(wú)法解決數(shù)據(jù)丟失的問(wèn)題，單臺(tái)服務(wù)器出問(wèn)題時(shí)，會(huì)有部分?jǐn)?shù)據(jù)丟失。所以，數(shù)據(jù)服務(wù)的高可用性只能通過(guò)第二種方法來(lái)完成——數(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è)很難的問(wèn)題。 讓我們用最經(jīng)典的Use Case：“A帳號(hào)向B帳號(hào)匯錢”來(lái)說(shuō)明一下，熟悉RDBMS事務(wù)的都知道從帳號(hào)A到帳號(hào)B需要6個(gè)操作：

1. 從A帳號(hào)中把余額讀出來(lái)。
2. 對(duì)A帳號(hào)做減法操作。
3. 把結(jié)果寫回A帳號(hào)中。
4. 從B帳號(hào)中把余額讀出來(lái)。
5. 對(duì)B帳號(hào)做加法操作。
6. 把結(jié)果寫回B帳號(hào)中。

為了數(shù)據(jù)的一致性，這6件事，要么都成功做完，要么都不成功，而且這個(gè)操作的過(guò)程中，對(duì)A、B帳號(hào)的其它訪問(wèn)必需鎖死，所謂鎖死就是要排除其它的讀寫操作，不然會(huì)有臟數(shù)據(jù)的問(wèn)題，這就是事務(wù)。那么，我們?cè)诩尤肓烁嗟臋C(jī)器后，這個(gè)事情會(huì)變得復(fù)雜起來(lái)：

 1）在數(shù)據(jù)分區(qū)的方案中：如果A帳號(hào)和B帳號(hào)的數(shù)據(jù)不在同一臺(tái)服務(wù)器上怎么辦？我們需要一個(gè)跨機(jī)器的事務(wù)處理。也就是說(shuō)，如果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ù)器上怎么辦？也就是說(shuō)，在數(shù)據(jù)鏡像中，在不同的服務(wù)器上對(duì)同一個(gè)數(shù)據(jù)的寫操作怎么保證其一致性，保證數(shù)據(jù)不沖突？

同時(shí)，我們還要考慮性能的因素，如果不考慮性能的話，事務(wù)得到保證并不困難，系統(tǒng)慢一點(diǎn)就行了。除了考慮性能外，我們還要考慮可用性，也就是說(shuō)，一臺(tái)機(jī)器沒(méi)了，數(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í)間

前面說(shuō)過(guò)，要解決數(shù)據(jù)不丟，只能通過(guò)數(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ù)丟失異常的唯一手段。所以，在這篇文章中，簡(jiǎn)單起見(jiàn)，我們只討論在數(shù)據(jù)冗余情況下考慮數(shù)據(jù)的一致性和性能的 問(wèn)題。簡(jiǎn)單說(shuō)來(lái)：

1）要想讓數(shù)據(jù)有高可用性，就得寫多份數(shù)據(jù)。

2）寫多份的問(wèn)題會(huì)導(dǎo)致數(shù)據(jù)一致性的問(wèn)題。

3）數(shù)據(jù)一致性的問(wèn)題又會(huì)引發(fā)性能問(wèn)題

這就是軟件開(kāi)發(fā)，按下了葫蘆起了瓢。

一致性模型

說(shuō)起數(shù)據(jù)一致性來(lái)說(shuō)，簡(jiǎn)單說(shuō)有三種類型（當(dāng)然，如果細(xì)分的話，還有很多一致性模型，如：順序一致性，F(xiàn)IFO一致性，會(huì)話一致性，單讀一致性，單寫一致性，但為了本文的簡(jiǎn)單易讀，我只說(shuō)下面三種）：

1）Weak 弱一致性：當(dāng)你寫入一個(gè)新值后，讀操作在數(shù)據(jù)副本上可能讀出來(lái)，也可能讀不出來(lái)。比如：某些cache系統(tǒng)，網(wǎng)絡(luò)游戲其它玩家的數(shù)據(jù)和你沒(méi)什么關(guān)系，VOIP這樣的系統(tǒng)，或是百度搜索引擎（呵呵）。

2）Eventually 最終一致性：當(dāng)你寫入一個(gè)新值后，有可能讀不出來(lái)，但在某個(gè)時(shí)間窗口之后保證最終能讀出來(lái)。比如：DNS，電子郵件、Amazon S3，Google搜索引擎這樣的系統(tǒng)。

3）Strong 強(qiáng)一致性：新的數(shù)據(jù)一旦寫入，在任意副本任意時(shí)刻都能讀到新值。比如：文件系統(tǒng)，RDBMS，Azure Table都是強(qiáng)一致性的。

從這三種一致型的模型上來(lái)說(shuō)，我們可以看到，Weak和Eventually一般來(lái)說(shuō)是異步冗余的，而Strong一般來(lái)說(shuō)是同步冗余的，異步的通 常意味著更好的性能，但也意味著更復(fù)雜的狀態(tài)控制。同步意味著簡(jiǎn)單，但也意味著性能下降。 好，讓我們由淺入深，一步一步地來(lái)看有哪些技術(shù)：

#p#

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來(lái)push，也可以使用Slave來(lái)pull。 通常來(lái)說(shuō)是Slave來(lái)周期性的pull，所以，是最終一致性。這個(gè)設(shè)計(jì)的問(wèn)題是，如果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)來(lái)說(shuō)，沒(méi)有數(shù)據(jù)一致性和數(shù)據(jù)丟失的問(wèn) 題，Master-Slave的方式就可以解決單點(diǎn)問(wèn)題了） 當(dāng)然，Master Slave也可以是強(qiáng)一致性的， 比如：當(dāng)我們寫Master的時(shí)候，Master負(fù)責(zé)先寫自己，等成功后，再寫Slave，兩者都成功后返回成功，整個(gè)過(guò)程是同步的，如果寫Slave失 敗了，那么兩種方法，一種是標(biāo)記Slave不可用報(bào)錯(cuò)并繼續(xù)服務(wù)（等Slave恢復(fù)后同步Master的數(shù)據(jù)，可以有多個(gè)Slave，這樣少一個(gè)，還有備 份，就像前面說(shuō)的寫三份那樣），另一種是回滾自己并返回寫失敗。（注：一般不先寫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ù)間同步一 般是通過(guò)Master間的異步完成，所以是最終一致性。 Master-Master的好處是，一臺(tái)Master掛了，別的Master可以正常做讀寫服務(wù)，他和Master-Slave一樣，當(dāng)數(shù)據(jù)沒(méi)有被復(fù)制 到別的Master上時(shí)，數(shù)據(jù)會(huì)丟失。很多數(shù)據(jù)庫(kù)都支持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è)事并不那么簡(jiǎn)單，而且Dynamo對(duì)數(shù)據(jù)沖突這個(gè)事是交給用戶自己搞的。就像我們的SVN源碼沖 突一樣，對(duì)于同一行代碼的沖突，只能交給開(kāi)發(fā)者自己來(lái)處理。（在本文后后面會(huì)討論一下Dynamo的Vector Clock）

Two/Three Phase Commit

這個(gè)協(xié)議的縮寫又叫2PC，中文叫兩階段提交。在分布式系統(tǒng)中，每個(gè)節(jié)點(diǎn)雖然可以知曉自己的操作時(shí)成功或者失敗，卻無(wú)法知道其他節(jié)點(diǎn)的操作的成功或失敗。當(dāng)一個(gè)事務(wù)跨越多個(gè)節(jié)點(diǎn)時(shí)，為了保持事務(wù)的ACID特性，需要引入一個(gè)作為協(xié)調(diào)者的組件來(lái)統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫入磁盤等等)。 兩階段提交的算法如下：

第一階段：

1. 協(xié)調(diào)者會(huì)問(wèn)所有的參與者結(jié)點(diǎn)，是否可以執(zhí)行提交操作。
2. 各個(gè)參與者開(kāi)始事務(wù)執(zhí)行的準(zhǔn)備工作：如：為資源上鎖，預(yù)留資源，寫undo/redo log……
3. 參與者響應(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說(shuō)白了就是第一階段做Vote，第二階段做決定的一個(gè)算法，也可以看到2PC這個(gè)事是強(qiáng)一致性的算法。在前面我們討論過(guò) Master-Slave的強(qiáng)一致性策略，和2PC有點(diǎn)相似，只不過(guò)2PC更為保守一些——先嘗試再提交。 2PC用的是比較多的，在一些系統(tǒng)設(shè)計(jì)中，會(huì)串聯(lián)一系列的調(diào)用，比如：A -> B -> C -> D，每一步都會(huì)分配一些資源或改寫一些數(shù)據(jù)。比如我們B2C網(wǎng)上購(gòu)物的下單操作在后臺(tái)會(huì)有一系列的流程需要做。如果我們一步一步地做，就會(huì)出現(xiàn)這樣的問(wèn) 題，如果某一步做不下去了，那么前面每一次所分配的資源需要做反向操作把他們都回收掉，所以，操作起來(lái)比較復(fù)雜。現(xiàn)在很多處理流程（Workflow）都 會(huì)借鑒2PC這個(gè)算法，使用 try -> confirm的流程來(lái)確保整個(gè)流程的能夠成功完成。 舉個(gè)通俗的例子，西方教堂結(jié)婚的時(shí)候，都有這樣的橋段：

1）牧師分別問(wèn)新郎和新娘：你是否愿意……不管生老病死……（詢問(wèn)階段）

2）當(dāng)新郎和新娘都回答愿意后（鎖定一生的資源），牧師就會(huì)說(shuō)：我宣布你們……（事務(wù)提交）

這是多么經(jīng)典的一個(gè)兩階段提交的事務(wù)處理。 另外，我們也可以看到其中的一些問(wèn)題， A）其中一個(gè)是同步阻塞操作，這個(gè)事情必然會(huì)非常大地影響性能。 B）另一個(gè)主要的問(wèn)題是在TimeOut上，比如，

#p#

1）如果第一階段中，參與者沒(méi)有收到詢問(wèn)請(qǐng)求，或是參與者的回應(yīng)沒(méi)有到達(dá)協(xié)調(diào)者。那么，需要協(xié)調(diào)者做超時(shí)處理，一旦超時(shí)，可以當(dāng)作失敗，也可以重試。

2）如果第二階段中，正式提交發(fā)出后，如果有的參與者沒(méi)有收到，或是參與者提交/回滾后的確認(rèn)信息沒(méi)有返回，一旦參與者的回應(yīng)超時(shí)，要么重試，要么把那個(gè)參與者標(biāo)記為問(wèn)題結(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)完全不知道怎么辦（問(wèn)別的參與者都不行）。為了一致性，要 么死等協(xié)調(diào)者，要么重發(fā)第一階段的yes/no命令。

兩段提交最大的問(wèn)題就是第3）項(xiàng)，如果第一階段完成后，參與者在第二階沒(méi)有收到?jīng)Q策，那么數(shù)據(jù)結(jié)點(diǎn)會(huì)進(jìn)入“不知所措”的狀態(tài)，這個(gè)狀態(tài)會(huì)block住整個(gè)事務(wù)。也就是說(shuō)，協(xié)調(diào)者Coordinator對(duì)于事務(wù)的完成非常重要，Coordinator的可用性是個(gè)關(guān)鍵。 因些，我們引入三段提交，三段提交在Wikipedia上的描述如下，他把二段提交的第一個(gè)段break成了兩段：詢問(wèn)，然后再鎖資源。最后真正提交。三段提交的示意圖如下：

三段提交的核心理念是：在詢問(wèn)的時(shí)候并不鎖定資源，除非所有人都同意了，才開(kāi)始鎖資源。

理論上來(lái)說(shuō)，如果第一階段所有的結(jié)點(diǎn)返回成功，那么有理由相信成功提交的概率很大。這樣一 來(lái)，可以降低參與者Cohorts的狀態(tài)未知的概率。也就是說(shuō)，一旦參與者收到了PreCommit，意味他知道大家其實(shí)都同意修改了。這一點(diǎn)很重要。下 面我們來(lái)看一下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的問(wèn)題，三段提交比兩段提交的好處是，三段提交可以繼續(xù)直接把狀態(tài)變成C狀態(tài)（Commit），而兩段提交則不知所措。

其實(shí)，三段提交是一個(gè)很復(fù)雜的事情，實(shí)現(xiàn)起來(lái)相當(dāng)難，而且也有一些問(wèn)題。

看到這里，我相信你有很多很多的問(wèn)題，你一定在思考2PC/3PC中各種各樣的失敗場(chǎng)景，你會(huì)發(fā)現(xiàn)Timeout是個(gè)非常難處理的事情，因?yàn)榫W(wǎng)絡(luò)上的Timeout在很多時(shí)候讓你無(wú)所事從，你也不知道對(duì)方是做了還是沒(méi)有做。于是你好好的一個(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（兩將軍問(wèn)題）

Two Generals Problem 兩將軍問(wèn)題是這么一個(gè)思維性實(shí)驗(yàn)問(wèn)題： 有兩支軍隊(duì)，它們分別有一位將軍領(lǐng)導(dǎo)，現(xiàn)在準(zhǔn)備攻擊一座修筑了防御工事的城市。這兩支軍隊(duì)都駐扎在那座城市的附近，分占一座山頭。一道山谷把兩座山分隔開(kāi) 來(lái)，并且兩位將軍唯一的通信方式就是派各自的信使來(lái)往于山谷兩邊。不幸的是，這個(gè)山谷已經(jīng)被那座城市的保衛(wèi)者占領(lǐng)，并且存在一種可能，那就是任何被派出的 信使通過(guò)山谷是會(huì)被捕。 請(qǐng)注意，雖然兩位將軍已經(jīng)就攻擊那座城市達(dá)成共識(shí)，但在他們各自占領(lǐng)山頭陣地之前，并沒(méi)有就進(jìn)攻時(shí)間達(dá)成共識(shí)。兩位將軍必須讓自己的軍隊(duì)同時(shí)進(jìn)攻城市才能 取得成功。因此，他們必須互相溝通，以確定一個(gè)時(shí)間來(lái)攻擊，并同意就在那時(shí)攻擊。如果只有一個(gè)將軍進(jìn)行攻擊，那么這將是一個(gè)災(zāi)難性的失敗。 這個(gè)思維實(shí)驗(yàn)就包括考慮他們?nèi)绾稳プ鲞@件事情。下面是我們的思考：

1）第一位將軍先發(fā)送一段消息“讓我們?cè)谏衔?點(diǎn)開(kāi)始進(jìn)攻”。然而，一旦信使被派遣，他 是否通過(guò)了山谷，第一位將軍就不得而知了。任何一點(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á)。

#p#

3）于是，似乎我們還要讓第一位將軍再發(fā)送一條確認(rèn)消息——“我收到了你的確認(rèn)”。然而，如果這位信使被抓怎么辦呢？

4）這樣一來(lái)，是不是我們還要第二位將軍發(fā)送一個(gè)“確認(rèn)收到你的確認(rèn)”的信息。

靠，于是你會(huì)發(fā)現(xiàn)，這事情很快就發(fā)展成為不管發(fā)送多少個(gè)確認(rèn)消息，都沒(méi)有辦法來(lái)保證兩位將軍有足夠的自信自己的信使沒(méi)有被敵軍捕獲。

這個(gè)問(wèn)題是無(wú)解的。兩 個(gè)將軍問(wèn)題和它的無(wú)解證明首先由E.A.Akkoyunlu,K.Ekanadham和R.V.Huber于1975年在《一些限制與折衷的網(wǎng)絡(luò)通信設(shè) 計(jì)》一文中發(fā)表，就在這篇文章的第73頁(yè)中一段描述兩個(gè)黑幫之間的通信中被闡明。 1978年，在Jim Gray的《數(shù)據(jù)庫(kù)操作系統(tǒng)注意事項(xiàng)》一書中（從第465頁(yè)開(kāi)始）被命名為兩個(gè)將軍悖論。作為兩個(gè)將軍問(wèn)題的定義和無(wú)解性的證明的來(lái)源，這一參考被廣泛提 及。

這個(gè)實(shí)驗(yàn)意在闡明：試圖通過(guò)建立在一個(gè)不可靠的連接上的交流來(lái)協(xié)調(diào)一項(xiàng)行動(dòng)的隱患和設(shè)計(jì)上的巨大挑戰(zhàn)。

從工程上來(lái)說(shuō)，一個(gè)解決兩個(gè)將軍問(wèn)題的實(shí)際方法是使用一個(gè)能夠承受通信信道不可靠性的方案， 并不試圖去消除這個(gè)不可靠性，但要將不可靠性削減到一個(gè)可以接受的程度。比如，第一位將軍排出了100位信使并預(yù)計(jì)他們都被捕的可能性很小。在這種情況 下，不管第二位將軍是否會(huì)攻擊或者受到任何消息，第一位將軍都會(huì)進(jìn)行攻擊。另外，第一位將軍可以發(fā)送一個(gè)消息流，而第二位將軍可以對(duì)其中的每一條消息發(fā)送 一個(gè)確認(rèn)消息，這樣如果每條消息都被接收到，兩位將軍會(huì)感覺(jué)更好。然而我們可以從證明中看出，他們倆都不能肯定這個(gè)攻擊是可以協(xié)調(diào)的。他們沒(méi)有算法可用 （比如，收到4條以上的消息就攻擊）能夠確保防止僅有一方攻擊。再者，第一位將軍還可以為每條消息編號(hào)，說(shuō)這是1號(hào)，2號(hào)……直到n號(hào)。這種方法能讓第二 位將軍知道通信信道到底有多可靠，并且返回合適的數(shù)量的消息來(lái)確保最后一條消息被接收到。如果信道是可靠的話，只要一條消息就行了，其余的就幫不上什么忙 了。最后一條和第一條消息丟失的概率是相等的。

 兩將軍問(wèn)題可以擴(kuò)展成更變態(tài)的拜占庭將軍問(wèn)題 (Byzantine Generals Problem)， 其故事背景是這樣的：拜占庭位于現(xiàn)在土耳其的伊斯坦布爾，是東羅馬帝國(guó)的首都。由于當(dāng)時(shí)拜占庭羅馬帝國(guó)國(guó)土遼闊，為了防御目的，因此每個(gè)軍隊(duì)都分隔很遠(yuǎn)， 將軍與將軍之間只能靠信差傳消息。 在戰(zhàn)爭(zhēng)的時(shí)候，拜占庭軍隊(duì)內(nèi)所有將軍必需達(dá)成一致的共識(shí)，決定是否有贏的機(jī)會(huì)才去攻打敵人的陣營(yíng)。但是，軍隊(duì)可能有叛徒和敵軍間諜，這些叛徒將軍們會(huì)擾亂 或左右決策的過(guò)程。這時(shí)候，在已知有成員謀反的情況下，其余忠誠(chéng)的將軍在不受叛徒的影響下如何達(dá)成一致的協(xié)議，這就是拜占庭將軍問(wèn)題。

Paxos算法

Wikipedia上的各種Paxos算法的描述非常詳細(xì)，大家可以去圍觀一下。

Paxos 算法解決的問(wèn)題是在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致，保證不論發(fā)生以上任何異常，都不會(huì)破壞決議的一致性。一個(gè)典型的場(chǎng)景是，在 一個(gè)分布式數(shù)據(jù)庫(kù)系統(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)用在許多場(chǎng)景中，是分布式計(jì)算中的重要問(wèn)題。從 20世紀(jì)80年代起對(duì)于一致性算法的研究就沒(méi)有停止過(guò)。

Notes：Paxos算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的”La”，此人現(xiàn)在在微軟研究院）于1990年提出的一種基于消息傳遞的一致性算法。由于算法難以理解起初并沒(méi)有 引起人們的重視，使Lamport在八年后1998年重新發(fā)表到ACM Transactions on Computer Systems上（The Part-Time Parliament）。即便如此paxos算法還是沒(méi)有得到重視，2001年Lamport 覺(jué)得同行無(wú)法接受他的幽默感，于是用容易接受的方法重新表述了一遍（Paxos Made Simple）。 可見(jiàn)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里說(shuō)他參考了ZooKeeper的方法，但他用了另一種比ZooKeeper更易讀的方式實(shí)現(xiàn)了這個(gè)算法。

簡(jiǎn)單說(shuō)來(lái)，Paxos的目的是讓整個(gè)集群的結(jié)點(diǎn)對(duì)某個(gè)值的變更達(dá)成一致。Paxos算法基本上來(lái)說(shuō)是個(gè)民主選舉的算法——大多數(shù)的決定會(huì)成個(gè)整個(gè)集 群的統(tǒng)一決定。任何一個(gè)點(diǎn)都可以提出要修改某個(gè)數(shù)據(jù)的提案，是否通過(guò)這個(gè)提案取決于這個(gè)集群中是否有超過(guò)半數(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ù)不斷遞增，而且是唯一的，也就是說(shuō)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ā)過(guò)來(lái)的提案號(hào)，這個(gè)結(jié)點(diǎn)會(huì)回應(yīng)Yes（本結(jié)點(diǎn)上最新的被批準(zhǔn)提案號(hào)），并保證不接收其它<n的提案。這樣一來(lái)，結(jié)點(diǎn)上在Prepare階段里總是會(huì)對(duì)最新的提案做承諾。

優(yōu)化：在上述 prepare 過(guò)程中，如果任何一個(gè)結(jié)點(diǎn)發(fā)現(xiàn)存在一個(gè)更高編號(hào)的提案，則需要通知 提案人，提醒其中斷這次提案。

#p#

第二階段：Accept階段

如果提案者A收到了超過(guò)半數(shù)的結(jié)點(diǎn)返回的Yes，然后他就會(huì)向所有的結(jié)點(diǎn)發(fā)布Accept Request（同樣，需要帶上提案號(hào)n），如果沒(méi)有超過(guò)半數(shù)的話，那就返回失敗。

當(dāng)結(jié)點(diǎn)們收到了Accept Request后，如果對(duì)于接收的結(jié)點(diǎn)來(lái)說(shuō)，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說(shuō)過(guò)這個(gè)世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

我們還可以看到：對(duì)于同一個(gè)值的在不同結(jié)點(diǎn)的修改提案就算是在接收方被亂序收到也是沒(méi)有問(wèn)題的。

關(guān)于一些實(shí)例，你可以看一下Wikipedia中文中的“Paxos樣例”一節(jié)，我在這里就不再多說(shuō)了。對(duì)于Paxos算法中的一些異常示例，大家可以自己推導(dǎo)一下。你會(huì)發(fā)現(xiàn)基本上來(lái)說(shuō)只要保證有半數(shù)以上的結(jié)點(diǎn)存活，就沒(méi)有什么問(wèn)題。

多說(shuō)一下，自從Lamport在1998年發(fā)表Paxos算法后，對(duì)Paxos的各種改進(jìn)工作就從未停止，其中動(dòng)作最大的莫過(guò)于2005年發(fā)表的Fast Paxos。無(wú)論何種改進(jìn)，其重點(diǎn)依然是在消息延遲與性能、吞吐量之間作出各種權(quán)衡。為了容易地從概念上區(qū)分二者，稱前者Classic Paxos，改進(jìn)后的后者為Fast Paxos。

總結(jié)

前面，我們說(shuō)過(guò)，要想讓數(shù)據(jù)有高可用性，就需要冗余數(shù)據(jù)寫多份。寫多份的問(wèn)題會(huì)帶來(lái)一致性的 問(wèn)題，而一致性的問(wèn)題又會(huì)帶來(lái)性能問(wèn)題。從上圖我們可以看到，我們基本上來(lái)說(shuō)不可以讓所有的項(xiàng)都綠起來(lái)，這就是著名的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ù)的差值要大。

也就是說(shuō)，每次讀取，都至少讀取到一個(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ù)的問(wèn)題，因?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ì)。也就是說(shuō)，如果你讀出來(lái)數(shù)據(jù)的版本是v1，當(dāng)你計(jì)算完成后要回填數(shù)據(jù)后，卻發(fā)現(xiàn)數(shù)據(jù)的版本號(hào)已經(jīng)被人更新成了v2，那么服務(wù)器就會(huì)拒絕你。版本這個(gè)事就像“樂(lè)觀鎖”一樣。

但是，對(duì)于分布式和NWR模型來(lái)說(shuō)，版本也會(huì)有惡夢(mèng)的時(shí)候——就是版本沖的問(wèn)題，比如：我們?cè)O(shè)置了N=3 W=1，如果A結(jié)點(diǎn)上接受了一個(gè)值，版本由v1 -> v2，但還沒(méi)有來(lái)得及同步到結(jié)點(diǎn)B上（異步的，應(yīng)該W=1，寫一份就算成功），B結(jié)點(diǎn)上還是v1版本，此時(shí)，B結(jié)點(diǎn)接到寫請(qǐng)求，按道理來(lái)說(shuō)，他需要拒絕 掉，但是他一方面并不知道別的結(jié)點(diǎn)已經(jīng)被更新到v2，另一方面他也無(wú)法拒絕，因?yàn)閃=1，所以寫一分就成功了。于是，出現(xiàn)了嚴(yán)重的版本沖突。

Amazon的Dynamo把版本沖突這個(gè)問(wèn)題巧妙地回避掉了——版本沖這個(gè)事交給用戶自己來(lái)處理。

于是，Dynamo引入了Vector Clock（矢量鐘？!）這個(gè)設(shè)計(jì)。這個(gè)設(shè)計(jì)讓每個(gè)結(jié)點(diǎn)各自記錄自己的版本信息，也就是說(shuō)，對(duì)于同一個(gè)數(shù)據(jù)，需要記錄兩個(gè)事：1）誰(shuí)更新的我，2）我的版本號(hào)是什么。

下面，我們來(lái)看一個(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沒(méi)有傳播到C的時(shí)候又一個(gè)請(qǐng)求被C處理了，于是，以C結(jié)點(diǎn)上的數(shù)據(jù)是D4(A,2; C,1)。

5）好，最精彩的事情來(lái)了：如果這個(gè)時(shí)候來(lái)了一個(gè)讀請(qǐng)求，我們要記得，我們的W=1 那么R=N=3，所以R會(huì)從所有三個(gè)節(jié)點(diǎn)上讀，此時(shí)，他會(huì)讀到三個(gè)版本：

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》，如果英文痛苦，你可以看看譯文（譯者不詳）。

原文鏈接：http://coolshell.cn/