分布式系統(tǒng)的事務(wù)處理
當(dāng)我們在生產(chǎn)線上用一臺服務(wù)器來提供數(shù)據(jù)服務(wù)的時候，我會遇到如下的兩個問題：
1）一臺服務(wù)器的性能不足以提供足夠的能力服務(wù)于所有的網(wǎng)絡(luò)請求。
2）我們總是害怕我們的這臺服務(wù)器停機(jī)，造成服務(wù)不可用或是數(shù)據(jù)丟失。
于是我們不得不對我們的服務(wù)器進(jìn)行擴(kuò)展，加入更多的機(jī)器來分擔(dān)性能上的問題，以及來解決單點(diǎn)故障問題。 通常，我們會通過兩種手段來擴(kuò)展我們的數(shù)據(jù)服務(wù)：
1）數(shù)據(jù)分區(qū)：就是把數(shù)據(jù)分塊放在不同的服務(wù)器上（如：uid % 16，一致性哈希等）。
2）數(shù)據(jù)鏡像：讓所有的服務(wù)器都有相同的數(shù)據(jù)，提供相當(dāng)?shù)姆?wù)。
對于第一種情況，我們無法解決數(shù)據(jù)丟失的問題，單臺服務(wù)器出問題時，會有部分?jǐn)?shù)據(jù)丟失。所以，數(shù)據(jù)服務(wù)的高可用性只能通過第二種方法來完成——數(shù)據(jù)的冗余存儲（一般工業(yè)界認(rèn)為比較安全的備份數(shù)應(yīng)該是3份，如：Hadoop和Dynamo）。 但是，加入更多的機(jī)器，會讓我們的數(shù)據(jù)服務(wù)變得很復(fù)雜，尤其是跨服務(wù)器的事務(wù)處理，也就是跨服務(wù)器的數(shù)據(jù)一致性。這個是一個很難的問題。 讓我們用最經(jīng)典的Use Case：“A帳號向B帳號匯錢”來說明一下，熟悉RDBMS事務(wù)的都知道從帳號A到帳號B需要6個操作：
- 從A帳號中把余額讀出來。
- 對A帳號做減法操作。
- 把結(jié)果寫回A帳號中。
- 從B帳號中把余額讀出來。
- 對B帳號做加法操作。
- 把結(jié)果寫回B帳號中。
為了數(shù)據(jù)的一致性，這6件事，要么都成功做完，要么都不成功，而且這個操作的過程中，對A、B帳號的其它訪問必需鎖死，所謂鎖死就是要排除其它的讀寫操作，不然會有臟數(shù)據(jù)的問題，這就是事務(wù)。那么，我們在加入了更多的機(jī)器后，這個事情會變得復(fù)雜起來：
1）在數(shù)據(jù)分區(qū)的方案中：如果A帳號和B帳號的數(shù)據(jù)不在同一臺服務(wù)器上怎么辦？我們需要一個跨機(jī)器的事務(wù)處理。也就是說，如果A的扣錢成功了，但B的加錢不成功，我們還要把A的操作給回滾回去。這在跨機(jī)器的情況下，就變得比較復(fù)雜了。
2）在數(shù)據(jù)鏡像的方案中：A帳號和B帳號間的匯款是可以在一臺機(jī)器上完成的，但是別忘了我們有多臺機(jī)器存在A帳號和B帳號的副本。如果對A帳號的匯錢有兩個并發(fā)操作（要匯給B和C），這兩個操作發(fā)生在不同的兩臺服務(wù)器上怎么辦？也就是說，在數(shù)據(jù)鏡像中，在不同的服務(wù)器上對同一個數(shù)據(jù)的寫操作怎么保證其一致性，保證數(shù)據(jù)不沖突？
同時，我們還要考慮性能的因素，如果不考慮性能的話，事務(wù)得到保證并不困難，系統(tǒng)慢一點(diǎn)就行了。除了考慮性能外，我們還要考慮可用性，也就是說，一臺機(jī)器沒了，數(shù)據(jù)不丟失，服務(wù)可由別的機(jī)器繼續(xù)提供。 于是，我們需要重點(diǎn)考慮下面的這么幾個情況：
- 容災(zāi)：數(shù)據(jù)不丟、結(jié)點(diǎn)的Failover
- 數(shù)據(jù)的一致性：事務(wù)處理
- 性能：吞吐量 、 響應(yīng)時間
前面說過，要解決數(shù)據(jù)不丟，只能通過數(shù)據(jù)冗余的方法，就算是數(shù)據(jù)分區(qū)，每個區(qū)也需要進(jìn)行數(shù)據(jù)冗余處理。這就是數(shù)據(jù)副本：當(dāng)出現(xiàn)某個節(jié)點(diǎn)的數(shù)據(jù)丟失時可以從副本讀到，數(shù)據(jù)副本是分布式系統(tǒng)解決數(shù)據(jù)丟失異常的唯一手段。所以，在這篇文章中，簡單起見，我們只討論在數(shù)據(jù)冗余情況下考慮數(shù)據(jù)的一致性和性能的問題。簡單說來：
1）要想讓數(shù)據(jù)有高可用性，就得寫多份數(shù)據(jù)。
2）寫多份的問題會導(dǎo)致數(shù)據(jù)一致性的問題。
3）數(shù)據(jù)一致性的問題又會引發(fā)性能問題
這就是軟件開發(fā)，按下了葫蘆起了瓢。#p#
一致性模型
說起數(shù)據(jù)一致性來說，簡單說有三種類型（當(dāng)然，如果細(xì)分的話，還有很多一致性模型，如：順序一致性，F(xiàn)IFO一致性，會話一致性，單讀一致性，單寫一致性，但為了本文的簡單易讀，我只說下面三種）：
1）Weak 弱一致性：當(dāng)你寫入一個新值后，讀操作在數(shù)據(jù)副本上可能讀出來，也可能讀不出來。比如：某些cache系統(tǒng)，網(wǎng)絡(luò)游戲其它玩家的數(shù)據(jù)和你沒什么關(guān)系，VOIP這樣的系統(tǒng)，或是百度搜索引擎（呵呵）。
2）Eventually 最終一致性：當(dāng)你寫入一個新值后，有可能讀不出來，但在某個時間窗口之后保證最終能讀出來。比如：DNS，電子郵件、Amazon S3，Google搜索引擎這樣的系統(tǒng)。
3）Strong 強(qiáng)一致性：新的數(shù)據(jù)一旦寫入，在任意副本任意時刻都能讀到新值。比如：文件系統(tǒng)，RDBMS，Azure Table都是強(qiáng)一致性的。
從這三種一致型的模型上來說，我們可以看到，Weak和Eventually一般來說是異步冗余的，而Strong一般來說是同步冗余的，異步的通常意味著更好的性能，但也意味著更復(fù)雜的狀態(tài)控制。同步意味著簡單，但也意味著性能下降。 好，讓我們由淺入深，一步一步地來看有哪些技術(shù)：
Master-Slave
首先是Master-Slave結(jié)構(gòu)，對于這種加構(gòu)，Slave一般是Master的備份。在這樣的系統(tǒng)中，一般是如下設(shè)計(jì)的：
1）讀寫請求都由Master負(fù)責(zé)。
2）寫請求寫到Master上后，由Master同步到Slave上。
從Master同步到Slave上，你可以使用異步，也可以使用同步，可以使用Master來push，也可以使用Slave來pull。 通常來說是Slave來周期性的pull，所以，是最終一致性。這個設(shè)計(jì)的問題是，如果Master在pull周期內(nèi)垮掉了，那么會導(dǎo)致這個時間片內(nèi)的數(shù)據(jù)丟失。如果你不想讓數(shù)據(jù)丟掉，Slave只能成為Read-Only的方式等Master恢復(fù)。
當(dāng)然，如果你可以容忍數(shù)據(jù)丟掉的話，你可以馬上讓Slave代替Master工作（對于只負(fù)責(zé)計(jì)算的結(jié)點(diǎn)來說，沒有數(shù)據(jù)一致性和數(shù)據(jù)丟失的問題，Master-Slave的方式就可以解決單點(diǎn)問題了） 當(dāng)然，Master Slave也可以是強(qiáng)一致性的， 比如：當(dāng)我們寫Master的時候，Master負(fù)責(zé)先寫自己，等成功后，再寫Slave，兩者都成功后返回成功，整個過程是同步的，如果寫Slave失敗了，那么兩種方法，一種是標(biāo)記Slave不可用報(bào)錯并繼續(xù)服務(wù)（等Slave恢復(fù)后同步Master的數(shù)據(jù)，可以有多個Slave，這樣少一個，還有備份，就像前面說的寫三份那樣），另一種是回滾自己并返回寫失敗。（注：一般不先寫Slave，因?yàn)槿绻麑慚aster自己失敗后，還要回滾Slave，此時如果回滾Slave失敗，就得手工訂正數(shù)據(jù)了）你可以看到，如果Master-Slave需要做成強(qiáng)一致性有多復(fù)雜。
Master-Master
Master-Master，又叫Multi-master，是指一個系統(tǒng)存在兩個或多個Master，每個Master都提供read-write服務(wù)。這個模型是Master-Slave的加強(qiáng)版，數(shù)據(jù)間同步一般是通過Master間的異步完成，所以是最終一致性。 Master-Master的好處是，一臺Master掛了，別的Master可以正常做讀寫服務(wù)，他和Master-Slave一樣，當(dāng)數(shù)據(jù)沒有被復(fù)制到別的Master上時，數(shù)據(jù)會丟失。很多數(shù)據(jù)庫都支持Master-Master的Replication的機(jī)制。
另外，如果多個Master對同一個數(shù)據(jù)進(jìn)行修改的時候，這個模型的惡夢就出現(xiàn)了——對數(shù)據(jù)間的沖突合并，這并不是一件容易的事情?？纯碊ynamo的Vector Clock的設(shè)計(jì)（記錄數(shù)據(jù)的版本號和修改者）就知道這個事并不那么簡單，而且Dynamo對數(shù)據(jù)沖突這個事是交給用戶自己搞的。就像我們的SVN源碼沖突一樣，對于同一行代碼的沖突，只能交給開發(fā)者自己來處理。（在本文后后面會討論一下Dynamo的Vector Clock）
Two/Three Phase Commit
這個協(xié)議的縮寫又叫2PC，中文叫兩階段提交。在分布式系統(tǒng)中，每個節(jié)點(diǎn)雖然可以知曉自己的操作時成功或者失敗，卻無法知道其他節(jié)點(diǎn)的操作的成功或失敗。當(dāng)一個事務(wù)跨越多個節(jié)點(diǎn)時，為了保持事務(wù)的ACID特性，需要引入一個作為協(xié)調(diào)者的組件來統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫入磁盤等等)。 兩階段提交的算法如下：
第一階段：
- 協(xié)調(diào)者會問所有的參與者結(jié)點(diǎn)，是否可以執(zhí)行提交操作。
- 各個參與者開始事務(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é)束這個Global Transaction。
- 如果有一個參與者回應(yīng)“拒絕提交”，那么，協(xié)調(diào)者向所有的參與者發(fā)送“回滾操作”，并釋放所有資源，然后回應(yīng)“回滾完成”，協(xié)調(diào)者收集各結(jié)點(diǎn)的“回滾”回應(yīng)后，取消這個Global Transaction。
我們可以看到，2PC說白了就是第一階段做Vote，第二階段做決定的一個算法，也可以看到2PC這個事是強(qiáng)一致性的算法。在前面我們討論過Master-Slave的強(qiáng)一致性策略，和2PC有點(diǎn)相似，只不過2PC更為保守一些——先嘗試再提交。 2PC用的是比較多的，在一些系統(tǒng)設(shè)計(jì)中，會串聯(lián)一系列的調(diào)用，比如：A -> B -> C -> D，每一步都會分配一些資源或改寫一些數(shù)據(jù)。比如我們B2C網(wǎng)上購物的下單操作在后臺會有一系列的流程需要做。如果我們一步一步地做，就會出現(xiàn)這樣的問題，如果某一步做不下去了，那么前面每一次所分配的資源需要做反向操作把他們都回收掉，所以，操作起來比較復(fù)雜?，F(xiàn)在很多處理流程（Workflow）都會借鑒2PC這個算法，使用 try -> confirm的流程來確保整個流程的能夠成功完成。 舉個通俗的例子，西方教堂結(jié)婚的時候，都有這樣的橋段：
1）牧師分別問新郎和新娘：你是否愿意……不管生老病死……（）
2）當(dāng)新郎和新娘都回答愿意后（鎖定一生的資源），牧師就會說：我宣布你們……（事務(wù)提交）
這是多么經(jīng)典的一個兩階段提交的事務(wù)處理。 另外，我們也可以看到其中的一些問題， A）其中一個是同步阻塞操作，這個事情必然會非常大地影響性能。 B）另一個主要的問題是在TimeOut上，比如，
1）如果第一階段中，參與者沒有收到詢問請求，或是參與者的回應(yīng)沒有到達(dá)協(xié)調(diào)者。那么，需要協(xié)調(diào)者做超時處理，一旦超時，可以當(dāng)作失敗，也可以重試。
2）如果第二階段中，正式提交發(fā)出后，如果有的參與者沒有收到，或是參與者提交/回滾后的確認(rèn)信息沒有返回，一旦參與者的回應(yīng)超時，要么重試，要么把那個參與者標(biāo)記為問題結(jié)點(diǎn)剔除整個集群，這樣可以保證服務(wù)結(jié)點(diǎn)都是數(shù)據(jù)一致性的。
3）糟糕的情況是，第二階段中，如果參與者收不到協(xié)調(diào)者的commit/fallback指令，參與者將處于“狀態(tài)未知”階段，參與者完全不知道要怎么辦，比如：如果所有的參與者完成第一階段的回復(fù)后（可能全部yes，可能全部no，可能部分yes部分no），如果協(xié)調(diào)者在這個時候掛掉了。那么所有的結(jié)點(diǎn)完全不知道怎么辦（問另的參與者都不行）。為了一致性，要么死等協(xié)調(diào)者，要么重發(fā)第一階段的yes/no命令。
兩段提交最大的問題就是第3）項(xiàng)，如果第一階段完成后，參與者在第二階沒有收到?jīng)Q策，那么數(shù)據(jù)結(jié)點(diǎn)會進(jìn)入“不知所措”的狀態(tài)，這個狀態(tài)會block住整個事務(wù)。也就是說，協(xié)調(diào)者Coordinator對于事務(wù)的完成非常重要，Coordinator的可用性是個關(guān)鍵。 因些，我們引入三段提交，三段提交在Wikipedia上的描述如下，他把二段提交的第一個段break成了兩段：詢問，然后再鎖資源。最后真正提交。三段提交的示意圖如下：
三段提交的核心理念是：在詢問的時候并不鎖定資源，除非所有人都同意了，才開始鎖資源。
理論上來說，如果第一階段所有的結(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）
其實(shí)，三段提交是一個很復(fù)雜的事情，實(shí)現(xiàn)起來相當(dāng)難，而且也有一些問題。
看到這里，我相信你有很多很多的問題，你一定在思考2PC/3PC中各種各樣的失敗場景，你會發(fā)現(xiàn)Timeout是個非常難處理的事情，因?yàn)榫W(wǎng)絡(luò)上的Timeout在很多時候讓你無所事從，你也不知道對方是做了還是沒有做。于是你好好的一個狀態(tài)機(jī)就因?yàn)門imeout成了個擺設(shè)。
一個網(wǎng)絡(luò)服務(wù)會有三種狀態(tài)：1）Success，2）Failure，3）Timeout，第三個絕對是惡夢，尤其在你需要維護(hù)狀態(tài)的時候。
Two Generals Problem（兩將軍問題）
Two Generals Problem 兩將軍問題是這么一個思維性實(shí)驗(yàn)問題： 有兩支軍隊(duì)，它們分別有一位將軍領(lǐng)導(dǎo)，現(xiàn)在準(zhǔn)備攻擊一座修筑了防御工事的城市。這兩支軍隊(duì)都駐扎在那座城市的附近，分占一座山頭。一道山谷把兩座山分隔開來，并且兩位將軍唯一的通信方式就是派各自的信使來往于山谷兩邊。不幸的是，這個山谷已經(jīng)被那座城市的保衛(wèi)者占領(lǐng)，并且存在一種可能，那就是任何被派出的信使通過山谷是會被捕。 請注意，雖然兩位將軍已經(jīng)就攻擊那座城市達(dá)成共識，但在他們各自占領(lǐng)山頭陣地之前，并沒有就進(jìn)攻時間達(dá)成共識。兩位將軍必須讓自己的軍隊(duì)同時進(jìn)攻城市才能取得成功。因此，他們必須互相溝通，以確定一個時間來攻擊，并同意就在那時攻擊。如果只有一個將軍進(jìn)行攻擊，那么這將是一個災(zāi)難性的失敗。 這個思維實(shí)驗(yàn)就包括考慮他們?nèi)绾稳プ鲞@件事情。下面是我們的思考：
1）第一位將軍先發(fā)送一段消息“讓我們在上午9點(diǎn)開始進(jìn)攻”。然而，一旦信使被派遣，他是否通過了山谷，第一位將軍就不得而知了。任何一點(diǎn)的不確定性都會使得第一位將軍攻擊猶豫，因?yàn)槿绻诙粚④姴荒茉谕粫r刻發(fā)動攻擊，那座城市的駐軍就會擊退他的軍隊(duì)的進(jìn)攻，導(dǎo)致他的軍對被摧毀。
2）知道了這一點(diǎn)，第二位將軍就需要發(fā)送一個確認(rèn)回條：“我收到您的郵件，并會在9點(diǎn)的攻擊。”但是，如果帶著確認(rèn)消息的信使被抓怎么辦？所以第二位將軍會猶豫自己的確認(rèn)消息是否能到達(dá)。
3）于是，似乎我們還要讓第一位將軍再發(fā)送一條確認(rèn)消息——“我收到了你的確認(rèn)”。然而，如果這位信使被抓怎么辦呢？
4）這樣一來，是不是我們還要第二位將軍發(fā)送一個“確認(rèn)收到你的確認(rèn)”的信息。
靠，于是你會發(fā)現(xiàn)，這事情很快就發(fā)展成為不管發(fā)送多少個確認(rèn)消息，都沒有辦法來保證兩位將軍有足夠的自信自己的信使沒有被敵軍捕獲。
這個問題是無解的。兩個將軍問題和它的無解證明首先由E.A.Akkoyunlu,K.Ekanadham和R.V.Huber于1975年在《一些限制與折衷的網(wǎng)絡(luò)通信設(shè)計(jì)》一文中發(fā)表，就在這篇文章的第73頁中一段描述兩個黑幫之間的通信中被闡明。 1978年，在Jim Gray的《數(shù)據(jù)庫操作系統(tǒng)注意事項(xiàng)》一書中（從第465頁開始）被命名為兩個將軍悖論。作為兩個將軍問題的定義和無解性的證明的來源，這一參考被廣泛提及。
這個實(shí)驗(yàn)意在闡明：試圖通過建立在一個不可靠的連接上的交流來協(xié)調(diào)一項(xiàng)行動的隱患和設(shè)計(jì)上的巨大挑戰(zhàn)。
從工程上來說，一個解決兩個將軍問題的實(shí)際方法是使用一個能夠承受通信信道不可靠性的方案，并不試圖去消除這個不可靠性，但要將不可靠性削減到一個可以接受的程度。比如，第一位將軍排出了100位信使并預(yù)計(jì)他們都被捕的可能性很小。在這種情況下，不管第二位將軍是否會攻擊或者受到任何消息，第一位將軍都會進(jìn)行攻擊。另外，第一位將軍可以發(fā)送一個消息流，而第二位將軍可以對其中的每一條消息發(fā)送一個確認(rèn)消息，這樣如果每條消息都被接收到，兩位將軍會感覺更好。然而我們可以從證明中看出，他們倆都不能肯定這個攻擊是可以協(xié)調(diào)的。他們沒有算法可用（比如，收到4條以上的消息就攻擊）能夠確保防止僅有一方攻擊。再者，第一位將軍還可以為每條消息編號，說這是1號，2號……直到n號。這種方法能讓第二位將軍知道通信信道到底有多可靠，并且返回合適的數(shù)量的消息來確保最后一條消息被接收到。如果信道是可靠的話，只要一條消息就行了，其余的就幫不上什么忙了。最后一條和第一條消息丟失的概率是相等的。
兩將軍問題可以擴(kuò)展成更變態(tài)的拜占庭將軍問題 (Byzantine Generals Problem)，其故事背景是這樣的：拜占庭位于現(xiàn)在土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當(dāng)時拜占庭羅馬帝國國土遼闊，為了防御目的，因此每個軍隊(duì)都分隔很遠(yuǎn)，將軍與將軍之間只能靠信差傳消息。 在戰(zhàn)爭的時候，拜占庭軍隊(duì)內(nèi)所有將軍必需達(dá)成一致的共識，決定是否有贏的機(jī)會才去攻打敵人的陣營。但是，軍隊(duì)可能有叛徒和敵軍間諜，這些叛徒將軍們會擾亂或左右決策的過程。這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達(dá)成一致的協(xié)議，這就是拜占庭將軍問題。#p#
Paxos算法
Wikipedia上的各種Paxos算法的描述非常詳細(xì)，大家可以去圍觀一下。
Paxos 算法解決的問題是在一個可能發(fā)生上述異常的分布式系統(tǒng)中如何就某個值達(dá)成一致，保證不論發(fā)生以上任何異常，都不會破壞決議的一致性。一個典型的場景是，在一個分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個「一致性算法」以保證每個節(jié)點(diǎn)看到的指令一致。一個通用的一致性算法可以應(yīng)用在許多場景中，是分布式計(jì)算中的重要問題。從20世紀(jì)80年代起對于一致性算法的研究就沒有停止過。
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）?？梢奓amport對Paxos算法情有獨(dú)鐘。近幾年P(guān)axos算法的普遍使用也證明它在分布式一致性算法中的重要地位。2006年Google的三篇論文初現(xiàn)“云”的端倪，其中的Chubby Lock服務(wù)使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。（Lamport 本人在 他的blog 中描寫了他用9年時間發(fā)表這個算法的前前后后）
注：Amazon的AWS中，所有的云服務(wù)都基于一個ALF（Async Lock Framework）的框架實(shí)現(xiàn)的，這個ALF用的就是Paxos算法。我在Amazon的時候，看內(nèi)部的分享視頻時，設(shè)計(jì)者在內(nèi)部的Principle Talk里說他參考了ZooKeeper的方法，但他用了另一種比ZooKeeper更易讀的方式實(shí)現(xiàn)了這個算法。
簡單說來，Paxos的目的是讓整個集群的結(jié)點(diǎn)對某個值的變更達(dá)成一致。Paxos算法基本上來說是個民主選舉的算法——大多數(shù)的決定會成個整個集群的統(tǒng)一決定。任何一個點(diǎn)都可以提出要修改某個數(shù)據(jù)的提案，是否通過這個提案取決于這個集群中是否有超過半數(shù)的結(jié)點(diǎn)同意（所以Paxos算法需要集群中的結(jié)點(diǎn)是單數(shù)）。
這個算法有兩個階段（假設(shè)這個有三個結(jié)點(diǎn)：A，B，C）：
第一階段：Prepare階段
A把申請修改的請求Prepare Request發(fā)給所有的結(jié)點(diǎn)A，B，C。注意，Paxos算法會有一個Sequence Number（你可以認(rèn)為是一個提案號，這個數(shù)不斷遞增，而且是唯一的，也就是說A和B不可能有相同的提案號），這個提案號會和修改請求一同發(fā)出，任何結(jié)點(diǎn)在“Prepare階段”時都會拒絕其值小于當(dāng)前提案號的請求。所以，結(jié)點(diǎn)A在向所有結(jié)點(diǎn)申請修改請求的時候，需要帶一個提案號，越新的提案，這個提案號就越是是最大的。
如果接收結(jié)點(diǎn)收到的提案號n大于其它結(jié)點(diǎn)發(fā)過來的提案號，這個結(jié)點(diǎn)會回應(yīng)Yes（本結(jié)點(diǎn)上最新的被批準(zhǔn)提案號），并保證不接收其它<n的提案。這樣一來，結(jié)點(diǎn)上在Prepare階段里總是會對最新的提案做承諾。
優(yōu)化：在上述 prepare 過程中，如果任何一個結(jié)點(diǎn)發(fā)現(xiàn)存在一個更高編號的提案，則需要通知 提案人，提醒其中斷這次提案。
第二階段：Accept階段
如果提案者A收到了超過半數(shù)的結(jié)點(diǎn)返回的Yes，然后他就會向所有的結(jié)點(diǎn)發(fā)布Accept Request（同樣，需要帶上提案號n），如果沒有超過半數(shù)的話，那就返回失敗。
當(dāng)結(jié)點(diǎn)們收到了Accept Request后，如果對于接收的結(jié)點(diǎn)來說，n是最大的了，那么，它就會修改這個值，如果發(fā)現(xiàn)自己有一個更大的提案號，那么，結(jié)點(diǎn)就會拒絕修改。
我們可以看以，這似乎就是一個“兩段提交”的優(yōu)化。其實(shí)，2PC/3PC都是分布式一致性算法的殘次版本，Google Chubby的作者M(jìn)ike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。
我們還可以看到：對于同一個值的在不同結(jié)點(diǎn)的修改提案就算是在接收方被亂序收到也是沒有問題的。
關(guān)于一些實(shí)例，你可以看一下Wikipedia中文中的“Paxos樣例”一節(jié)，我在這里就不再多說了。對于Paxos算法中的一些異常示例，大家可以自己推導(dǎo)一下。你會發(fā)現(xiàn)基本上來說只要保證有半數(shù)以上的結(jié)點(diǎn)存活，就沒有什么問題。
多說一下，自從Lamport在1998年發(fā)表Paxos算法后，對Paxos的各種改進(jìn)工作就從未停止，其中動作最大的莫過于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ù)寫多份。寫多份的問題會帶來一致性的問題，而一致性的問題又會帶來性能問題。從上圖我們可以看到，我們基本上來說不可以讓所有的項(xiàng)都綠起來，這就是著名的CAP理論：一致性，可用性，分區(qū)容忍性，你只可能要其中的兩個。
NWR模型
最后我還想提一下Amazon Dynamo的NWR模型。這個NWR模型把CAP的選擇權(quán)交給了用戶，讓用戶自己的選擇你的CAP中的哪兩個。
所謂NWR模型。N代表N個備份，W代表要寫入至少W份才認(rèn)為成功，R表示至少讀取R個備份。配置的時候要求W+R > N。 因?yàn)閃+R > N， 所以 R > N-W 這個是什么意思呢？就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫成功的倍數(shù)的差值要大。
也就是說，每次讀取，都至少讀取到一個最新的版本。從而不會讀到一份舊數(shù)據(jù)。當(dāng)我們需要高可寫的環(huán)境的時候，我們可以配置W = 1 如果N=3 那么R = 3。 這個時候只要寫任何節(jié)點(diǎn)成功就認(rèn)為成功，但是讀的時候必須從所有的節(jié)點(diǎn)都讀出數(shù)據(jù)。如果我們要求讀的高效率，我們可以配置 W=N R=1。這個時候任何一個節(jié)點(diǎn)讀成功就認(rèn)為成功，但是寫的時候必須寫所有三個節(jié)點(diǎn)成功才認(rèn)為成功。
NWR模型的一些設(shè)置會造成臟數(shù)據(jù)的問題，因?yàn)檫@很明顯不是像Paxos一樣是一個強(qiáng)一致的東西，所以，可能每次的讀寫操作都不在同一個結(jié)點(diǎn)上，于是會出現(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ù)的版本號已經(jīng)被人更新成了v2，那么服務(wù)器就會拒絕你。版本這個事就像“樂觀鎖”一樣。
但是，對于分布式和NWR模型來說，版本也會有惡夢的時候——就是版本沖的問題，比如：我們設(shè)置了N=3 W=1，如果A結(jié)點(diǎn)上接受了一個值，版本由v1 -> v2，但還沒有來得及同步到結(jié)點(diǎn)B上（異步的，應(yīng)該W=1，寫一份就算成功），B結(jié)點(diǎn)上還是v1版本，此時，B結(jié)點(diǎn)接到寫請求，按道理來說，他需要拒絕掉，但是他一方面并不知道別的結(jié)點(diǎn)已經(jīng)被更新到v2，另一方面他也無法拒絕，因?yàn)閃=1，所以寫一分就成功了。于是，出現(xiàn)了嚴(yán)重的版本沖突。
Amazon的Dynamo把版本沖突這個問題巧妙地回避掉了——版本沖這個事交給用戶自己來處理。
于是，Dynamo引入了Vector Clock（矢量鐘？!）這個設(shè)計(jì)。這個設(shè)計(jì)讓每個結(jié)點(diǎn)各自記錄自己的版本信息，也就是說，對于同一個數(shù)據(jù)，需要記錄兩個事：1）誰更新的我，2）我的版本號是什么。
下面，我們來看一個操作序列：
1）一個寫請求，第一次被節(jié)點(diǎn)A處理了。節(jié)點(diǎn)A會增加一個版本信息(A，1)。我們把這個時候的數(shù)據(jù)記做D1(A，1)。 然后另外一個對同樣key的請求還是被A處理了于是有D2(A，2)。這個時候，D2是可以覆蓋D1的，不會有沖突產(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ù)及其版本號都是一樣的。
3）如果我們有一個新的寫請求到了B結(jié)點(diǎn)上，于是B結(jié)點(diǎn)生成數(shù)據(jù)D3(A,2; B,1)，意思是：數(shù)據(jù)D全局版本號為3，A升了兩新，B升了一次。這不就是所謂的代碼版本的log么？
4）如果D3沒有傳播到C的時候又一個請求被C處理了，于是，以C結(jié)點(diǎn)上的數(shù)據(jù)是D4(A,2; C,1)。
5）好，最精彩的事情來了：如果這個時候來了一個讀請求，我們要記得，我們的W=1 那么R=N=3，所以R會從所有三個節(jié)點(diǎn)上讀，此時，他會讀到三個版本：
- 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）這個時候可以判斷出，D2已經(jīng)是舊版本（已經(jīng)包含在D3/D4中），可以舍棄。
7）但是D3和D4是明顯的版本沖突。于是，交給調(diào)用方自己去做版本沖突處理。就像源代碼版本管理一樣。
很明顯，上述的Dynamo的配置用的是CAP里的A和P。
我非常推大家都去看看這篇論文：《Dynamo：Amazon’s Highly Available Key-Value Store》，如果英文痛苦，你可以看看譯文（譯者不詳）。
