[[282654]]

數(shù)據(jù)服務(wù)的高可用是所有企業(yè)都想擁有的，但是要想讓數(shù)據(jù)有高可用性，就需要冗余數(shù)據(jù)寫(xiě)多份。寫(xiě)多份的問(wèn)題會(huì)帶來(lái)一致性的問(wèn)題，而一致性的問(wèn)題又會(huì)帶來(lái)性能問(wèn)題，這就會(huì)陷入一個(gè)無(wú)解的死循環(huán)!這里所謂數(shù)據(jù)一致性，就是當(dāng)多個(gè)用戶試圖同時(shí)訪問(wèn)一個(gè)數(shù)據(jù)庫(kù)時(shí)，如果它們的事務(wù)同時(shí)使用相同的數(shù)據(jù)，可能會(huì)發(fā)生以下四種情況：丟失更新、未確定的相關(guān)性、不一致的分析和幻像讀。本篇文章將會(huì)給大家系統(tǒng)的介紹多種處理分布式數(shù)據(jù)一致性的技術(shù)模型。

以下是作者原文：

在生產(chǎn)線上用一臺(tái)服務(wù)器來(lái)提供數(shù)據(jù)服務(wù)的時(shí)候，經(jīng)常會(huì)遇到如下的兩個(gè)問(wèn)題：

• 一臺(tái)服務(wù)器的性能不足以提供足夠的能力服務(wù)于所有網(wǎng)絡(luò)請(qǐng)求。
• 擔(dān)心服務(wù)器宕機(jī)，造成服務(wù)不可用或是數(shù)據(jù)丟失。

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

• 數(shù)據(jù)分區(qū)：就是把數(shù)據(jù)分塊放在不同的服務(wù)器上(如：uid % 16，一致性哈希等)。
• 數(shù)據(jù)鏡像：讓所有的服務(wù)器數(shù)據(jù)同步，提供無(wú)差別的數(shù)據(jù)服務(wù)。

使用第一種方案，無(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ī)器越多數(shù)據(jù)就會(huì)變得越復(fù)雜，尤其是跨服務(wù)器的事務(wù)處理，也就是跨服務(wù)器的數(shù)據(jù)一致性。這個(gè)是一個(gè)很難的問(wèn)題!讓我們用最經(jīng)典的Use Case：“A帳號(hào)向B帳號(hào)匯錢(qián)”來(lái)說(shuō)明一下，熟悉RDBMS事務(wù)的都知道從帳號(hào)A到帳號(hào)B需要6個(gè)操作：

• 從A帳號(hào)中把余額讀出來(lái);
• 對(duì)A帳號(hào)做減法操作;
• 把結(jié)果寫(xiě)回A帳號(hào)中;
• 從B帳號(hào)中把余額讀出來(lái);
• 對(duì)B帳號(hào)做加法操作;
• 把結(jié)果寫(xiě)回B帳號(hào)中。

為了數(shù)據(jù)的一致性，這6件事，要么都成功做完，要么都不成功，而且這個(gè)操作的過(guò)程中，對(duì)A、B帳號(hào)的其它訪問(wèn)必需鎖死，所謂鎖死就是要排除其它的讀寫(xiě)操作，不然會(huì)有臟數(shù)據(jù)問(wèn)題，這就是事務(wù)。但是，在加入了多個(gè)機(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的扣錢(qián)成功了，但B的加錢(qián)不成功，我們還要把A的操作給回滾回去。在不同的機(jī)器上實(shí)現(xiàn)，就會(huì)比較復(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)的匯錢(qián)有兩個(gè)并發(fā)操作(要匯給B和C)，這兩個(gè)操作發(fā)生在不同的兩臺(tái)服務(wù)器上怎么辦?也就是說(shuō)，在數(shù)據(jù)鏡像中，在不同的服務(wù)器上對(duì)同一個(gè)數(shù)據(jù)的寫(xiě)操作怎么保證其一致性，保證數(shù)據(jù)不沖突?

同時(shí)，我們還要考慮性能因素，如果不考慮性能的話，事務(wù)完成并不困難，系統(tǒng)慢一點(diǎn)就行了。除了考慮性能外，我們還要考慮可用性，也就是說(shuō)，一臺(tái)機(jī)器沒(méi)了，數(shù)據(jù)不丟失，服務(wù)可由別的機(jī)器繼續(xù)提供。 于是，我們需要重點(diǎn)考慮下面的這么幾個(gè)情況：

• 容災(zāi)：數(shù)據(jù)不丟、結(jié)點(diǎn)的Failover
• 數(shù)據(jù)的一致性：事務(wù)處理
• 性能：吞吐量 、 響應(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ù)丟失異常的唯一手段。所以，在這篇文章中，我們只討論在數(shù)據(jù)冗余情況下考慮數(shù)據(jù)的一致性和性能的問(wèn)題。簡(jiǎn)單說(shuō)來(lái)：

• 要想讓數(shù)據(jù)有高可用性，就得寫(xiě)多份數(shù)據(jù)。
• 寫(xiě)多份的問(wèn)題會(huì)導(dǎo)致數(shù)據(jù)一致性的問(wèn)題。
• 數(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ì)話一致性，單讀一致性，單寫(xiě)一致性，但為了本文的簡(jiǎn)單易讀，我只說(shuō)下面三種)：

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

3，Strong 強(qiáng)一致性：新的數(shù)據(jù)一旦寫(xiě)入，在任意副本任意時(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ù)：

Master-Slave

首先是Master-Slave結(jié)構(gòu)，對(duì)于這種加構(gòu)，Slave一般是Master的備份。在這樣的系統(tǒng)中，一般是如下設(shè)計(jì)的：

• 讀寫(xiě)請(qǐng)求都由Master負(fù)責(zé)。
• 寫(xiě)請(qǐng)求寫(xiě)到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)寫(xiě)Master的時(shí)候，Master負(fù)責(zé)先備份，等成功后，再寫(xiě)Slave，兩者都成功后返回成功，整個(gè)過(guò)程是同步的，如果寫(xiě)Slave失敗了，那么兩種方法，一種是標(biāo)記Slave不可用報(bào)錯(cuò)并繼續(xù)服務(wù)(等Slave恢復(fù)后同步Master的數(shù)據(jù)，可以有多個(gè)Slave，這樣少一個(gè)，還有備份，就像前面說(shuō)的寫(xiě)三份那樣)，另一種是回滾自己并返回寫(xiě)失敗。(注：一般不先寫(xiě)Slave，因?yàn)槿绻麑?xiě)Master自己失敗后，還要回滾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可以正常做讀寫(xiě)服務(wù)，這個(gè)和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ù)間的沖突進(jìn)行合并，這非常困難?？纯碊ynamo的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é)議的縮寫(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ù)寫(xiě)入磁盤(pán)等等)。 兩階段提交的算法如下：

第一階段：

• 協(xié)調(diào)者會(huì)問(wèn)所有的參與者結(jié)點(diǎn)，是否可以執(zhí)行提交操作。
• 各個(gè)參與者開(kāi)始事務(wù)執(zhí)行的準(zhǔn)備工作：如：為資源上鎖，預(yù)留資源，寫(xiě)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說(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ì)分配一些資源或改寫(xiě)一些數(shù)據(jù)。比如B2C網(wǎng)上購(gòu)物的下單操作在后臺(tái)會(huì)有一系列的流程需要做。如果一步一步地做，就會(huì)出現(xiàn)這樣的問(wèn)題，如果某一步做不下去了，那么前面每一次所分配的資源需要做反向操作把他們都回收掉，所以，操作起來(lái)比較復(fù)雜?，F(xiàn)在很多處理流程(Workflow)都會(huì)借鑒2PC這個(gè)算法，使用 try -> confirm的流程來(lái)確保整個(gè)流程的能夠成功完成。 舉個(gè)通俗的例子，西方教堂結(jié)婚的時(shí)候，都有這樣的橋段：

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

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

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

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)

其實(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)門(mé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)就包括考慮將軍如何去做這件事情。下面是對(duì)于這件事情的思考：

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á)。

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)》一書(shū)中(從第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é)更好。然而從證明中來(lái)看，他們倆都不能肯定這個(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上。即便如此paxos算法還是沒(méi)有得到重視，2001年Lamport 覺(jué)得同行無(wú)法接受他的幽默感，于是用容易接受的方法重新表述了一遍。可見(jiàn)Lamport對(duì)Paxos算法情有獨(dú)鐘。近幾年P(guān)axos算法的普遍使用也證明它在分布式一致性算法中的重要地位。2006年Google的三篇論文初現(xiàn)“云”的端倪，其中的Chubby Lock服務(wù)使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。(Lamport 本人在他的blog 中描寫(xiě)了他用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ì)拒絕其實(shí)小于當(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))，并保證不接收其它的提案做承諾。<>

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

第二階段：Accept階段

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

當(dāng)結(jié)點(diǎn)們收到了Accept Request后，如果對(duì)于接收的結(jié)果來(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é)

下圖來(lái)自：Google App Engine的co-founder Ryan Barrett在2009年的google i/o上的演講:

前面，我們說(shuō)過(guò)，要想讓數(shù)據(jù)有高可用性，就需要冗余數(shù)據(jù)寫(xiě)多份。寫(xiě)多份的問(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代表要寫(xiě)入至少W份才認(rèn)為成功，R表示至少讀取R個(gè)備份。配置的時(shí)候要求W+R > N。 因?yàn)閃+R > N， 所以 R > N-W 這個(gè)是什么意思呢?就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫(xiě)成功的倍數(shù)的差值要大。

也就是說(shuō)，每次讀取，都至少讀取到一個(gè)最新的版本。從而不會(huì)讀到一份舊數(shù)據(jù)。當(dāng)我們需要高可寫(xiě)的環(huán)境的時(shí)候，我們可以配置W = 1 如果N=3 那么R = 3。 這個(gè)時(shí)候只要寫(xiě)任何節(jié)點(diǎn)成功就認(rèn)為成功，但是讀的時(shí)候必須從所有的節(jié)點(diǎn)都讀出數(shù)據(jù)。如果我們要求讀的高效率，我們可以配置 W=N R=1。這個(gè)時(shí)候任何一個(gè)節(jié)點(diǎn)讀成功就認(rèn)為成功，但是寫(xiě)的時(shí)候必須寫(xiě)所有三個(gè)節(jié)點(diǎn)成功才認(rèn)為成功。

NWR模型的一些設(shè)置會(huì)造成臟數(shù)據(jù)的問(wèn)題，因?yàn)檫@很明顯不是像Paxos一樣是一個(gè)強(qiáng)一致的東西，所以，可能每次的讀寫(xiě)操作都不在同一個(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，寫(xiě)一份就算成功)，B結(jié)點(diǎn)上還是v1版本，此時(shí)，B結(jié)點(diǎn)接到寫(xiě)請(qǐng)求，按道理來(lái)說(shuō)，他需要拒絕掉，但是他一方面并不知道別的結(jié)點(diǎn)已經(jīng)被更新到v2，另一方面他也無(wú)法拒絕，因?yàn)閃=1，所以寫(xiě)一分就成功了。于是，出現(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è)操作序列：

一個(gè)寫(xiě)請(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)生。

現(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)都是一樣的。

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

如果D3沒(méi)有傳播到C的時(shí)候又一個(gè)請(qǐng)求被C處理了，于是，以C結(jié)點(diǎn)上的數(shù)據(jù)是D4(A,2; C,1)。

好，最精彩的事情來(lái)了：如果這個(gè)時(shí)候來(lái)了一個(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)

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。