一致性模型
說起數(shù)據(jù)一致性來說，簡單說有三種類型（當然，如果細分的話，還有很多一致性模型，如：順序一致性，F(xiàn)IFO一致性，會話一致性，單讀一致性，單寫一致性，但為了本文的簡單易讀，我只說下面三種）：
1）Weak 弱一致性：當你寫入一個新值后，讀操作在數(shù)據(jù)副本上可能讀出來，也可能讀不出來。比如：某些cache系統(tǒng)，網(wǎng)絡(luò)游戲其它玩家的數(shù)據(jù)和你沒什么關(guān)系，VOIP這樣的系統(tǒng)，或是百度搜索引擎（呵呵）。
2）Eventually 最終一致性：當你寫入一個新值后，有可能讀不出來，但在某個時間窗口之后保證最終能讀出來。比如：DNS，電子郵件、Amazon S3，Google搜索引擎這樣的系統(tǒng)。
3）Strong 強一致性：新的數(shù)據(jù)一旦寫入，在任意副本任意時刻都能讀到新值。比如：文件系統(tǒng)，RDBMS，Azure Table都是強一致性的。
從這三種一致型的模型上來說，我們可以看到，Weak和Eventually一般來說是異步冗余的，而Strong一般來說是同步冗余的，異步的通常意味著更好的性能，但也意味著更復雜的狀態(tài)控制。同步意味著簡單，但也意味著性能下降。 好，讓我們由淺入深，一步一步地來看有哪些技術(shù)：
Master-Slave
首先是Master-Slave結(jié)構(gòu)，對于這種加構(gòu)，Slave一般是Master的備份。在這樣的系統(tǒng)中，一般是如下設(shè)計的：
1）讀寫請求都由Master負責。
2）寫請求寫到Master上后，由Master同步到Slave上。
從Master同步到Slave上，你可以使用異步，也可以使用同步，可以使用Master來push，也可以使用Slave來pull。 通常來說是Slave來周期性的pull，所以，是最終一致性。這個設(shè)計的問題是，如果Master在pull周期內(nèi)垮掉了，那么會導致這個時間片內(nèi)的數(shù)據(jù)丟失。如果你不想讓數(shù)據(jù)丟掉，Slave只能成為Read-Only的方式等Master恢復。
當然，如果你可以容忍數(shù)據(jù)丟掉的話，你可以馬上讓Slave代替Master工作（對于只負責計算的結(jié)點來說，沒有數(shù)據(jù)一致性和數(shù)據(jù)丟失的問題，Master-Slave的方式就可以解決單點問題了） 當然，Master Slave也可以是強一致性的， 比如：當我們寫Master的時候，Master負責先寫自己，等成功后，再寫Slave，兩者都成功后返回成功，整個過程是同步的，如果寫Slave失敗了，那么兩種方法，一種是標記Slave不可用報錯并繼續(xù)服務(wù)（等Slave恢復后同步Master的數(shù)據(jù)，可以有多個Slave，這樣少一個，還有備份，就像前面說的寫三份那樣），另一種是回滾自己并返回寫失敗。（注：一般不先寫Slave，因為如果寫Master自己失敗后，還要回滾Slave，此時如果回滾Slave失敗，就得手工訂正數(shù)據(jù)了）你可以看到，如果Master-Slave需要做成強一致性有多復雜。
Master-Master
Master-Master，又叫Multi-master，是指一個系統(tǒng)存在兩個或多個Master，每個Master都提供read-write服務(wù)。這個模型是Master-Slave的加強版，數(shù)據(jù)間同步一般是通過Master間的異步完成，所以是最終一致性。 Master-Master的好處是，一臺Master掛了，別的Master可以正常做讀寫服務(wù)，他和Master-Slave一樣，當數(shù)據(jù)沒有被復制到別的Master上時，數(shù)據(jù)會丟失。很多數(shù)據(jù)庫都支持Master-Master的Replication的機制。
另外，如果多個Master對同一個數(shù)據(jù)進行修改的時候，這個模型的惡夢就出現(xiàn)了——對數(shù)據(jù)間的沖突合并，這并不是一件容易的事情?？纯碊ynamo的Vector Clock的設(shè)計（記錄數(shù)據(jù)的版本號和修改者）就知道這個事并不那么簡單，而且Dynamo對數(shù)據(jù)沖突這個事是交給用戶自己搞的。就像我們的SVN源碼沖突一樣，對于同一行代碼的沖突，只能交給開發(fā)者自己來處理。（在本文后后面會討論一下Dynamo的Vector Clock）
Two/Three Phase Commit
這個協(xié)議的縮寫又叫2PC，中文叫兩階段提交。在分布式系統(tǒng)中，每個節(jié)點雖然可以知曉自己的操作時成功或者失敗，卻無法知道其他節(jié)點的操作的成功或失敗。當一個事務(wù)跨越多個節(jié)點時，為了保持事務(wù)的ACID特性，需要引入一個作為協(xié)調(diào)者的組件來統(tǒng)一掌控所有節(jié)點(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點是否要把操作結(jié)果進行真正的提交(比如將更新后的數(shù)據(jù)寫入磁盤等等)。 兩階段提交的算法如下：
第一階段：
第二階段：
我們可以看到，2PC說白了就是第一階段做Vote，第二階段做決定的一個算法，也可以看到2PC這個事是強一致性的算法。在前面我們討論過Master-Slave的強一致性策略，和2PC有點相似，只不過2PC更為保守一些——先嘗試再提交。 2PC用的是比較多的，在一些系統(tǒng)設(shè)計中，會串聯(lián)一系列的調(diào)用，比如：A -> B -> C -> D，每一步都會分配一些資源或改寫一些數(shù)據(jù)。比如我們B2C網(wǎng)上購物的下單操作在后臺會有一系列的流程需要做。如果我們一步一步地做，就會出現(xiàn)這樣的問題，如果某一步做不下去了，那么前面每一次所分配的資源需要做反向操作把他們都回收掉，所以，操作起來比較復雜?，F(xiàn)在很多處理流程（Workflow）都會借鑒2PC這個算法，使用 try -> confirm的流程來確保整個流程的能夠成功完成。 舉個通俗的例子，西方教堂結(jié)婚的時候，都有這樣的橋段：
1）牧師分別問新郎和新娘：你是否愿意……不管生老病死……（）
2）當新郎和新娘都回答愿意后（鎖定一生的資源），牧師就會說：我宣布你們……（事務(wù)提交）
這是多么經(jīng)典的一個兩階段提交的事務(wù)處理。 另外，我們也可以看到其中的一些問題， A）其中一個是同步阻塞操作，這個事情必然會非常大地影響性能。 B）另一個主要的問題是在TimeOut上，比如，
1）如果第一階段中，參與者沒有收到詢問請求，或是參與者的回應(yīng)沒有到達協(xié)調(diào)者。那么，需要協(xié)調(diào)者做超時處理，一旦超時，可以當作失敗，也可以重試。
2）如果第二階段中，正式提交發(fā)出后，如果有的參與者沒有收到，或是參與者提交/回滾后的確認信息沒有返回，一旦參與者的回應(yīng)超時，要么重試，要么把那個參與者標記為問題結(jié)點剔除整個集群，這樣可以保證服務(wù)結(jié)點都是數(shù)據(jù)一致性的。
3）糟糕的情況是，第二階段中，如果參與者收不到協(xié)調(diào)者的commit/fallback指令，參與者將處于“狀態(tài)未知”階段，參與者完全不知道要怎么辦，比如：如果所有的參與者完成第一階段的回復后（可能全部yes，可能全部no，可能部分yes部分no），如果協(xié)調(diào)者在這個時候掛掉了。那么所有的結(jié)點完全不知道怎么辦（問另的參與者都不行）。為了一致性，要么死等協(xié)調(diào)者，要么重發(fā)第一階段的yes/no命令。
兩段提交最大的問題就是第3）項，如果第一階段完成后，參與者在第二階沒有收到?jīng)Q策，那么數(shù)據(jù)結(jié)點會進入“不知所措”的狀態(tài)，這個狀態(tài)會block住整個事務(wù)。也就是說，協(xié)調(diào)者Coordinator對于事務(wù)的完成非常重要，Coordinator的可用性是個關(guān)鍵。 因些，我們引入三段提交，三段提交在Wikipedia上的描述如下，他把二段提交的第一個段break成了兩段：詢問，然后再鎖資源。最后真正提交。三段提交的示意圖如下：
三段提交的核心理念是：在詢問的時候并不鎖定資源，除非所有人都同意了，才開始鎖資源。
理論上來說，如果第一階段所有的結(jié)點返回成功，那么有理由相信成功提交的概率很大。這樣一來，可以降低參與者Cohorts的狀態(tài)未知的概率。也就是說，一旦參與者收到了PreCommit，意味他知道大家其實都同意修改了。這一點很重要。下面我們來看一下3PC的狀態(tài)遷移圖：（注間圖中的虛線，那些F,T是Failuer或Timeout，其中的：狀態(tài)含義是 q – Query，a – Abort，w – Wait，p – PreCommit，c – Commit）
其實，三段提交是一個很復雜的事情，實現(xiàn)起來相當難，而且也有一些問題。
看到這里，我相信你有很多很多的問題，你一定在思考2PC/3PC中各種各樣的失敗場景，你會發(fā)現(xiàn)Timeout是個非常難處理的事情，因為網(wǎng)絡(luò)上的Timeout在很多時候讓你無所事從，你也不知道對方是做了還是沒有做。于是你好好的一個狀態(tài)機就因為Timeout成了個擺設(shè)。
一個網(wǎng)絡(luò)服務(wù)會有三種狀態(tài)：1）Success，2）Failure，3）Timeout，第三個絕對是惡夢，尤其在你需要維護狀態(tài)的時候。
Two Generals Problem（兩將軍問題）
Two Generals Problem 兩將軍問題是這么一個思維性實驗問題： 有兩支軍隊，它們分別有一位將軍領(lǐng)導，現(xiàn)在準備攻擊一座修筑了防御工事的城市。這兩支軍隊都駐扎在那座城市的附近，分占一座山頭。一道山谷把兩座山分隔開來，并且兩位將軍唯一的通信方式就是派各自的信使來往于山谷兩邊。不幸的是，這個山谷已經(jīng)被那座城市的保衛(wèi)者占領(lǐng)，并且存在一種可能，那就是任何被派出的信使通過山谷是會被捕。 請注意，雖然兩位將軍已經(jīng)就攻擊那座城市達成共識，但在他們各自占領(lǐng)山頭陣地之前，并沒有就進攻時間達成共識。兩位將軍必須讓自己的軍隊同時進攻城市才能取得成功。因此，他們必須互相溝通，以確定一個時間來攻擊，并同意就在那時攻擊。如果只有一個將軍進行攻擊，那么這將是一個災(zāi)難性的失敗。 這個思維實驗就包括考慮他們?nèi)绾稳プ鲞@件事情。下面是我們的思考：
1）第一位將軍先發(fā)送一段消息“讓我們在上午9點開始進攻”。然而，一旦信使被派遣，他是否通過了山谷，第一位將軍就不得而知了。任何一點的不確定性都會使得第一位將軍攻擊猶豫，因為如果第二位將軍不能在同一時刻發(fā)動攻擊，那座城市的駐軍就會擊退他的軍隊的進攻，導致他的軍對被摧毀。
2）知道了這一點，第二位將軍就需要發(fā)送一個確認回條：“我收到您的郵件，并會在9點的攻擊?！钡牵绻麕е_認消息的信使被抓怎么辦？所以第二位將軍會猶豫自己的確認消息是否能到達。
3）于是，似乎我們還要讓第一位將軍再發(fā)送一條確認消息——“我收到了你的確認”。然而，如果這位信使被抓怎么辦呢？
4）這樣一來，是不是我們還要第二位將軍發(fā)送一個“確認收到你的確認”的信息。
靠，于是你會發(fā)現(xiàn)，這事情很快就發(fā)展成為不管發(fā)送多少個確認消息，都沒有辦法來保證兩位將軍有足夠的自信自己的信使沒有被敵軍捕獲。
這個問題是無解的。兩個將軍問題和它的無解證明首先由E.A.Akkoyunlu,K.Ekanadham和R.V.Huber于1975年在《一些限制與折衷的網(wǎng)絡(luò)通信設(shè)計》一文中發(fā)表，就在這篇文章的第73頁中一段描述兩個黑幫之間的通信中被闡明。 1978年，在Jim Gray的《數(shù)據(jù)庫操作系統(tǒng)注意事項》一書中（從第465頁開始）被命名為兩個將軍悖論。作為兩個將軍問題的定義和無解性的證明的來源，這一參考被廣泛提及。
這個實驗意在闡明：試圖通過建立在一個不可靠的連接上的交流來協(xié)調(diào)一項行動的隱患和設(shè)計上的巨大挑戰(zhàn)。
從工程上來說，一個解決兩個將軍問題的實際方法是使用一個能夠承受通信信道不可靠性的方案，并不試圖去消除這個不可靠性，但要將不可靠性削減到一個可以接受的程度。比如，第一位將軍排出了100位信使并預(yù)計他們都被捕的可能性很小。在這種情況下，不管第二位將軍是否會攻擊或者受到任何消息，第一位將軍都會進行攻擊。另外，第一位將軍可以發(fā)送一個消息流，而第二位將軍可以對其中的每一條消息發(fā)送一個確認消息，這樣如果每條消息都被接收到，兩位將軍會感覺更好。然而我們可以從證明中看出，他們倆都不能肯定這個攻擊是可以協(xié)調(diào)的。他們沒有算法可用（比如，收到4條以上的消息就攻擊）能夠確保防止僅有一方攻擊。再者，第一位將軍還可以為每條消息編號，說這是1號，2號……直到n號。這種方法能讓第二位將軍知道通信信道到底有多可靠，并且返回合適的數(shù)量的消息來確保最后一條消息被接收到。如果信道是可靠的話，只要一條消息就行了，其余的就幫不上什么忙了。最后一條和第一條消息丟失的概率是相等的。
兩將軍問題可以擴展成更變態(tài)的拜占庭將軍問題 (Byzantine Generals Problem)，其故事背景是這樣的：拜占庭位于現(xiàn)在土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當時拜占庭羅馬帝國國土遼闊，為了防御目的，因此每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。 在戰(zhàn)爭的時候，拜占庭軍隊內(nèi)所有將軍必需達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，軍隊可能有叛徒和敵軍間諜，這些叛徒將軍們會擾亂或左右決策的過程。這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達成一致的協(xié)議，這就是拜占庭將軍問題。
