作者 Eric Brewer 譯者 郭曉剛 李湃 發(fā)布于 2012年6月11日
編者按：由InfoQ主辦的全球架構(gòu)師峰會(huì)將于2012年8月10日-12日在深圳舉行，為了更好地詮釋架構(gòu)的意義、方法和實(shí)踐，InfoQ中文站近期會(huì)集中發(fā)布一批與架構(gòu)相關(guān)的文章，本篇即為其中之一。InfoQ也歡迎讀者親身參與到本次全球架構(gòu)師峰會(huì)中，與來(lái)自國(guó)內(nèi)外的頂尖架構(gòu)師進(jìn)行面對(duì)面的交流。報(bào)名參會(huì)請(qǐng)點(diǎn)擊這里。
支付寶與烏云分享架構(gòu)安全設(shè)計(jì)指南
西門(mén)子如何系統(tǒng)培養(yǎng)架構(gòu)師以及內(nèi)部系統(tǒng)架構(gòu)解密
ArchSummit全球架構(gòu)師峰會(huì)報(bào)名啟動(dòng)！8折優(yōu)惠，6月30日截止！
本文首發(fā)于 Computer 雜志，由InfoQ和IEEE呈現(xiàn)給您。
CAP理論斷言任何基于網(wǎng)絡(luò)的數(shù)據(jù)共享系統(tǒng)，最多只能滿足數(shù)據(jù)一致性、可用性、分區(qū)容忍性三要素中的兩個(gè)要素。但是通過(guò)顯式處理分區(qū)情形，系統(tǒng)設(shè)計(jì)師可以做到優(yōu)化數(shù)據(jù)一致性和可用性，進(jìn)而取得三者之間的平衡。
自打引入CAP理論的十幾年里，設(shè)計(jì)師和研究者已經(jīng)以它為理論基礎(chǔ)探索了各式各樣新穎的分布式系統(tǒng)，甚至到了濫用的程度。NoSQL運(yùn)動(dòng)也將CAP理論當(dāng)作對(duì)抗傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的依據(jù)。
CAP理論主張任何基于網(wǎng)絡(luò)的數(shù)據(jù)共享系統(tǒng)，都最多只能擁有以下三條中的兩條：
CAP理論的表述很好地服務(wù)了它的目的，即開(kāi)闊設(shè)計(jì)師的思路，在多樣化的取舍方案下設(shè)計(jì)出多樣化的系統(tǒng)。在過(guò)去的十幾年里確實(shí)涌現(xiàn)了不計(jì)其數(shù)的新系統(tǒng)，也隨之在數(shù)據(jù)一致性和可用性的相對(duì)關(guān)系上產(chǎn)生了相當(dāng)多的爭(zhēng)論?！叭x二”的公式一直存在著誤導(dǎo)性，它會(huì)過(guò)分簡(jiǎn)單化各性質(zhì)之間的相互關(guān)系?，F(xiàn)在我們有必要辨析其中的細(xì)節(jié)。實(shí)際上只有“在分區(qū)存在的前提下呈現(xiàn)完美的數(shù)據(jù)一致性和可用性”這種很少見(jiàn)的情況是CAP理論不允許出現(xiàn)的。
雖然設(shè)計(jì)師仍然需要在分區(qū)的前提下對(duì)數(shù)據(jù)一致性和可用性做取舍，但具體如何處理分區(qū)和恢復(fù)一致性，這里面有不計(jì)其數(shù)的變通方案和靈活度。當(dāng)代CAP實(shí)踐應(yīng)將目標(biāo)定為針對(duì)具體的應(yīng)用，在合理范圍內(nèi)最大化數(shù)據(jù)一致性和可用性的“合力”。這樣的思路延伸為如何規(guī)劃分區(qū)期間的操作和分區(qū)之后的恢復(fù)，從而啟發(fā)設(shè)計(jì)師加深對(duì)CAP的認(rèn)識(shí)，突破過(guò)去由于CAP理論的表述而產(chǎn)生的思維局限。
理解CAP理論的最簡(jiǎn)單方式是想象兩個(gè)節(jié)點(diǎn)分處分區(qū)兩側(cè)。允許至少一個(gè)節(jié)點(diǎn)更新?tīng)顟B(tài)會(huì)導(dǎo)致數(shù)據(jù)不一致，即喪失了C性質(zhì)。如果為了保證數(shù)據(jù)一致性，將分區(qū)一側(cè)的節(jié)點(diǎn)設(shè)置為不可用，那么又喪失了A性質(zhì)。除非兩個(gè)節(jié)點(diǎn)可以互相通信，才能既保證C又保證A，這又會(huì)導(dǎo)致喪失P性質(zhì)。一般來(lái)說(shuō)跨區(qū)域的系統(tǒng)，設(shè)計(jì)師無(wú)法舍棄P性質(zhì)，那么就只能在數(shù)據(jù)一致性和可用性上做一個(gè)艱難選擇。不確切地說(shuō)，NoSQL運(yùn)動(dòng)的主題其實(shí)是創(chuàng)造各種可用性優(yōu)先、數(shù)據(jù)一致性其次的方案；而傳統(tǒng)數(shù)據(jù)庫(kù)堅(jiān)守ACID特性（原子性、一致性、隔離性、持久性），做的是相反的事情。下文“ACID、BASE、CAP”小節(jié)詳細(xì)說(shuō)明了它們的差異。
事實(shí)上，CAP理論本身就是在類似的討論中誕生的。早在1990年代中期，我和同事構(gòu)建了一系列的基于集群的跨區(qū)域系統(tǒng)（實(shí)質(zhì)上是早期的云計(jì)算），包括搜索引擎、緩存代理以及內(nèi)容分發(fā)系統(tǒng)1。從收入目標(biāo)以及合約規(guī)定來(lái)講，系統(tǒng)可用性是首要目標(biāo)，因而我們常規(guī)會(huì)使用緩存或者事后校核更新日志來(lái)優(yōu)化系統(tǒng)的可用性。盡管這些策略提升了系統(tǒng)的可用性，但這是以犧牲系統(tǒng)數(shù)據(jù)一致性為代價(jià)的。
關(guān)于“數(shù)據(jù)一致性 VS 可用性”的第一回合爭(zhēng)論，表現(xiàn)為ACID與BASE之爭(zhēng)2。當(dāng)時(shí)BASE還不怎么被人們接受，主要是大家看重ACID的優(yōu)點(diǎn)而不愿意放棄。提出CAP理論，目的是證明有必要開(kāi)拓更廣闊的設(shè)計(jì)空間，因此才有了“三選二”公式。CAP理論最早在1998年秋季提出，1999年正式發(fā)表3，并在2000年登上Symposium on Principles of Distributed Computing大會(huì)的主題演講4，最終確立了該理論的正確性。
“三選二”的觀點(diǎn)在幾個(gè)方面起了誤導(dǎo)作用，詳見(jiàn)下文“CAP之惑”小節(jié)的解釋。首先，由于分區(qū)很少發(fā)生，那么在系統(tǒng)不存在分區(qū)的情況下沒(méi)什么理由犧牲C或A。其次，C與A之間的取舍可以在同一系統(tǒng)內(nèi)以非常細(xì)小的粒度反復(fù)發(fā)生，而每一次的決策可能因?yàn)榫唧w的操作，乃至因?yàn)闋可娴教囟ǖ臄?shù)據(jù)或用戶而有所不同。最后，這三種性質(zhì)都可以在程度上衡量，并不是非黑即白的有或無(wú)?？捎眯燥@然是在0%到100%之間連續(xù)變化的，一致性分很多級(jí)別，連分區(qū)也可以細(xì)分為不同含義，如系統(tǒng)內(nèi)的不同部分對(duì)于是否存在分區(qū)可以有不一樣的認(rèn)知。
要探索這些細(xì)微的差別，就要突破傳統(tǒng)的分區(qū)處理方式，而這是一項(xiàng)根本性的挑戰(zhàn)。因?yàn)榉謪^(qū)很少出現(xiàn)，CAP在大多數(shù)時(shí)候允許完美的C和A。但當(dāng)分區(qū)存在或可感知其影響的情況下，就要預(yù)備一種策略去探知分區(qū)并顯式處理其影響。這樣的策略應(yīng)分為三個(gè)步驟：探知分區(qū)發(fā)生，進(jìn)入顯式的分區(qū)模式以限制某些操作，啟動(dòng)恢復(fù)過(guò)程以恢復(fù)數(shù)據(jù)一致性并補(bǔ)償分區(qū)期間發(fā)生的錯(cuò)誤。
ACID和BASE代表了兩種截然相反的設(shè)計(jì)哲學(xué)，分處一致性-可用性分布圖譜的兩極。ACID注重一致性，是數(shù)據(jù)庫(kù)的傳統(tǒng)設(shè)計(jì)思路。我和同事在1990年代晚期提出BASE，目的是抓住當(dāng)時(shí)正逐漸成型的一些針對(duì)高可用性的設(shè)計(jì)思路，并且把不同性質(zhì)之間的取舍和消長(zhǎng)關(guān)系擺上臺(tái)面?，F(xiàn)代大規(guī)?？鐓^(qū)域分布的系統(tǒng)，包括云在內(nèi)，同時(shí)運(yùn)用了這兩種思路。
這兩個(gè)術(shù)語(yǔ)都好記有余而精確不足，出現(xiàn)較晚的BASE硬湊的感覺(jué)更明顯，它是“Basically Available, Soft state, Eventually consistent（基本可用、軟狀態(tài)、最終一致性）”的首字母縮寫(xiě)。其中的軟狀態(tài)和最終一致性這兩種技巧擅于對(duì)付存在分區(qū)的場(chǎng)合，并因此提高了可用性。
CAP與ACID的關(guān)系更復(fù)雜一些，也因此引起更多誤解。其中一個(gè)原因是ACID的C和A字母所代表的概念不同于CAP的C和A。還有一個(gè)原因是選擇可用性只部分地影響ACID約束。ACID四項(xiàng)特性分別為：
原子性（A）。所有的系統(tǒng)都受惠于原子性操作。當(dāng)我們考慮可用性的時(shí)候，沒(méi)有理由去改變分區(qū)兩側(cè)操作的原子性。而且滿足ACID定義的、高抽象層次的原子操作，實(shí)際上會(huì)簡(jiǎn)化分區(qū)恢復(fù)。
一致性（C）。ACID的C指的是事務(wù)不能破壞任何數(shù)據(jù)庫(kù)規(guī)則，如鍵的唯一性。與之相比，CAP的C僅指單一副本這個(gè)意義上的一致性，因此只是ACID一致性約束的一個(gè)嚴(yán)格的子集。ACID一致性不可能在分區(qū)過(guò)程中保持，因此分區(qū)恢復(fù)時(shí)需要重建ACID一致性。推而廣之，分區(qū)期間也許不可能維持某些不變性約束，所以有必要仔細(xì)考慮哪些操作應(yīng)該禁止，分區(qū)后又如何恢復(fù)這些不變性約束。
隔離性（I）。隔離是CAP理論的核心：如果系統(tǒng)要求ACID隔離性，那么它在分區(qū)期間最多可以在分區(qū)一側(cè)維持操作。事務(wù)的可串行性（serializability）要求全局的通信，因此在分區(qū)的情況下不能成立。只要在分區(qū)恢復(fù)時(shí)進(jìn)行補(bǔ)償，在分區(qū)前后保持一個(gè)較弱的正確性定義是可行的。
持久性（D）。犧牲持久性沒(méi)有意義，理由和原子性一樣，雖然開(kāi)發(fā)者有理由（持久性成本太高）選擇BASE風(fēng)格的軟狀態(tài)來(lái)避免實(shí)現(xiàn)持久性。這里有一個(gè)細(xì)節(jié)，分區(qū)恢復(fù)可能因?yàn)榛赝顺志眯圆僮?，而無(wú)意中破壞某項(xiàng)不變性約束。但只要恢復(fù)時(shí)給定分區(qū)兩側(cè)的持久性操作歷史記錄，破壞不變性約束的操作還是可以被檢測(cè)出來(lái)并修正的。通常來(lái)講，讓分區(qū)兩側(cè)的事務(wù)都滿足ACID特性會(huì)使得后續(xù)的分區(qū)恢復(fù)變得更容易，并且為分區(qū)恢復(fù)時(shí)事務(wù)的補(bǔ)償工作奠定了基本的條件。
CAP理論的經(jīng)典解釋，是忽略網(wǎng)絡(luò)延遲的，但在實(shí)際中延遲和分區(qū)緊密相關(guān)。CAP從理論變?yōu)楝F(xiàn)實(shí)的場(chǎng)景發(fā)生在操作的間歇，系統(tǒng)需要在這段時(shí)間內(nèi)做出關(guān)于分區(qū)的一個(gè)重要決定：
依靠多次嘗試通信的方法來(lái)達(dá)到一致性，比如Paxos算法或者兩階段事務(wù)提交，僅僅是推遲了決策的時(shí)間。系統(tǒng)終究要做一個(gè)決定；無(wú)限期地嘗試下去，本身就是選擇一致性犧牲可用性的表現(xiàn)。
因此以實(shí)際效果而言，分區(qū)相當(dāng)于對(duì)通信的時(shí)限要求。系統(tǒng)如果不能在時(shí)限內(nèi)達(dá)成數(shù)據(jù)一致性，就意味著發(fā)生了分區(qū)的情況，必須就當(dāng)前操作在C和A之間做出選擇。這就從延遲的角度抓住了設(shè)計(jì)的核心問(wèn)題：分區(qū)兩側(cè)是否在無(wú)通信的情況下繼續(xù)其操作？
從這個(gè)實(shí)用的觀察角度出發(fā)可以導(dǎo)出若干重要的推論。第一，分區(qū)并不是全體節(jié)點(diǎn)的一致見(jiàn)解，因?yàn)橛行┕?jié)點(diǎn)檢測(cè)到了分區(qū)，有些可能沒(méi)有。第二，檢測(cè)到分區(qū)的節(jié)點(diǎn)即進(jìn)入分區(qū)模式——這是優(yōu)化C和A的核心環(huán)節(jié)。
最后，這個(gè)觀察角度還意味著設(shè)計(jì)師可以根據(jù)期望中的響應(yīng)時(shí)間，有意識(shí)地設(shè)置時(shí)限；時(shí)限設(shè)得越短，系統(tǒng)進(jìn)入分區(qū)模式越頻繁，其中有些時(shí)候并不一定真的發(fā)生了分區(qū)的情況，可能只是網(wǎng)絡(luò)變慢而已。
有時(shí)候在跨區(qū)域的系統(tǒng)，放棄強(qiáng)一致性來(lái)避免保持?jǐn)?shù)據(jù)一致所帶來(lái)的高延遲是非常有意義的。Yahoo的PNUTS系統(tǒng)因?yàn)橐援惒降姆绞骄S護(hù)遠(yuǎn)程副本而帶來(lái)數(shù)據(jù)一致性的問(wèn)題5。但好處是主副本就放在本地，減小操作的等待時(shí)間。這個(gè)策略在實(shí)際中很實(shí)用，因?yàn)橐话銇?lái)講，用戶數(shù)據(jù)大都會(huì)根據(jù)用戶的（日常）地理位置做分區(qū)。最理想的狀況是每一位用戶都在他的數(shù)據(jù)主副本附近。
Facebook使用了相反的策略6：主副本被固定在一個(gè)地方，因此遠(yuǎn)程用戶一般訪問(wèn)到的是離他較近，但可能已經(jīng)過(guò)時(shí)的數(shù)據(jù)副本。不過(guò)當(dāng)用戶更新其頁(yè)面的時(shí)候是直接對(duì)主副本進(jìn)行更新，而且該用戶的所有讀操作也被短暫轉(zhuǎn)向從主副本讀取，盡管這樣延遲會(huì)比較高。20秒后，該用戶的流量被重新切換回離他較近的副本，此時(shí)副本應(yīng)該已經(jīng)同步好了剛才的更新。
CAP理論經(jīng)常在不同方面被人誤解，對(duì)于可用性和一致性的作用范圍的誤解尤為嚴(yán)重，可能造成不希望看到的結(jié)果。如果用戶根本獲取不到服務(wù)，那么其實(shí)談不上C和A之間做取舍，除非把一部分服務(wù)放在客戶端上運(yùn)行，即所謂的無(wú)連接操作或稱離線模式7。離線模式正變得越來(lái)越重要。HTML5的一些特性，特別是客戶端持久化存儲(chǔ)特性，將會(huì)促進(jìn)離線操作的發(fā)展。支持離線模式的系統(tǒng)通常會(huì)在C和A中選擇A，那么就不得不在長(zhǎng)時(shí)間處于分區(qū)狀態(tài)后進(jìn)行恢復(fù)。
“一致性的作用范圍”其實(shí)反映了這樣一種觀念，即在一定的邊界內(nèi)狀態(tài)是一致的，但超出了邊界就無(wú)從談起。比如在一個(gè)主分區(qū)內(nèi)可以保證完備的一致性和可用性，而在分區(qū)外服務(wù)是不可用的。Paxos算法和原子性多播（atomic multicast）系統(tǒng)一般符合這樣的場(chǎng)景8。像Google的一半做法是將主分區(qū)歸屬在單一個(gè)數(shù)據(jù)中心里面，然后交給Paxos算法去解決跨區(qū)域的問(wèn)題，一方面保證全局協(xié)商一致（global consensus）如Chubby9，一方面實(shí)現(xiàn)高可用的持久性存儲(chǔ)如Megastore10。
分區(qū)期間，獨(dú)立且能自我保證一致性的節(jié)點(diǎn)子集合可以繼續(xù)執(zhí)行操作，只是無(wú)法保證全局范圍的不變性約束不受破壞。數(shù)據(jù)分片（sharding）就是這樣的例子，設(shè)計(jì)師預(yù)先將數(shù)據(jù)劃分到不同的分區(qū)節(jié)點(diǎn)，分區(qū)期間單個(gè)數(shù)據(jù)分片多半可以繼續(xù)操作。相反，如果被分區(qū)的是內(nèi)在關(guān)系密切的狀態(tài)，或者有某些全局性的不變性約束非保持不可，那么最好的情況是只有分區(qū)一側(cè)可以進(jìn)行操作，最壞情況是操作完全不能進(jìn)行。
“三選二”的時(shí)候取CA而舍P是否合理？已經(jīng)有研究者指出了其中的要害——怎樣才算“舍P”含義并不明確11,12。設(shè)計(jì)師可以選擇不要分區(qū)嗎？哪怕原來(lái)選了CA，當(dāng)分區(qū)出現(xiàn)的時(shí)候，你也只能回頭重新在C和A之間再選一次。我們最好從概率的角度去理解：選擇CA意味著我們假定，分區(qū)出現(xiàn)的可能性要比其他的系統(tǒng)性錯(cuò)誤（如自然災(zāi)難、并發(fā)故障）低很多。
這種觀點(diǎn)在實(shí)際中很有意義，因?yàn)槟承┕收辖M合可能導(dǎo)致同時(shí)丟掉C和A，所以說(shuō)CAP三個(gè)性質(zhì)都是一個(gè)度的問(wèn)題。實(shí)踐中，大部分團(tuán)體認(rèn)為（位于單一地點(diǎn)的）數(shù)據(jù)中心內(nèi)部是沒(méi)有分區(qū)的，因此在單一數(shù)據(jù)中心之內(nèi)可以選擇CA；CAP理論出現(xiàn)之前，系統(tǒng)都默認(rèn)這樣的設(shè)計(jì)思路，包括傳統(tǒng)數(shù)據(jù)庫(kù)在內(nèi)。然而就算可能性不高，單一數(shù)據(jù)中心完全有可能出現(xiàn)分區(qū)的情況，一旦出現(xiàn)就會(huì)動(dòng)搖以CA為取向的設(shè)計(jì)基礎(chǔ)。最后，考慮到跨區(qū)域時(shí)出現(xiàn)的高延遲，在數(shù)據(jù)一致性上讓步來(lái)?yè)Q取更好性能的做法相對(duì)比較常見(jiàn)。
CAP還有一個(gè)方面很多人認(rèn)識(shí)不清，那就是放棄一致性其實(shí)有隱藏負(fù)擔(dān)，即需要明確了解系統(tǒng)中存在的不變性約束。滿足一致性的系統(tǒng)有一種保持其不變性約束的自然傾向，即便設(shè)計(jì)師不清楚系統(tǒng)中所有的不變性約束，相當(dāng)一部分合理的不變性約束會(huì)自動(dòng)地維持下去。相反，當(dāng)設(shè)計(jì)師選擇可用性的時(shí)候，因?yàn)樾枰诜謪^(qū)結(jié)束后恢復(fù)被破壞的不變性約束，顯然必須將各種不變性約束一一列舉出來(lái)，可想而知這件工作很有挑戰(zhàn)又很容易犯錯(cuò)。放棄一致性為什么難，其核心還是“并發(fā)更新問(wèn)題”，跟多線程編程比順序編程難的原因是一樣的。
怎樣緩和分區(qū)對(duì)一致性和可用性的影響是對(duì)設(shè)計(jì)師的挑戰(zhàn)。其關(guān)鍵是以非常明確、公開(kāi)的方式去管理分區(qū)，不僅需要主動(dòng)察覺(jué)分區(qū)的發(fā)生，還需要為分區(qū)期間所有可能受侵害的不變性約束預(yù)備專門(mén)的恢復(fù)過(guò)程和計(jì)劃。管理分區(qū)有三個(gè)步驟：
（點(diǎn)擊看大圖）
最后一步的目的是恢復(fù)一致性，以及補(bǔ)償在系統(tǒng)分區(qū)期間程序產(chǎn)生的錯(cuò)誤。
圖1可見(jiàn)分區(qū)的演變過(guò)程。普通的操作都是順序的原子操作，因此分區(qū)總是在兩筆操作之間開(kāi)始。一旦系統(tǒng)在操作間歇檢測(cè)到分區(qū)發(fā)生，檢測(cè)方一側(cè)即進(jìn)入分區(qū)模式。如果確實(shí)發(fā)生了分區(qū)的情況，那么一般分區(qū)兩側(cè)都會(huì)進(jìn)入到分區(qū)模式，不過(guò)單方面完成分區(qū)也是可能的。單方面分區(qū)要求在對(duì)方按需要通信的時(shí)候，本方要么能正確響應(yīng)，要么不需要通信；總之操作不得破壞一致性。但不管怎么樣，由于檢測(cè)方可能有不一致的操作，它必須進(jìn)入分區(qū)模式。采取了quorum決定機(jī)制的系統(tǒng)即為單方面分區(qū)的例子。其中一方擁有“法定通過(guò)節(jié)點(diǎn)數(shù)”，因此可以執(zhí)行操作，而另一方不可以執(zhí)行操作。支持離線操作的系統(tǒng)明顯地含有“分區(qū)模式”的概念，一些支持原子多播（atomic multicast）的系統(tǒng)也含有這個(gè)概念，如Java平臺(tái)的JGroups。
當(dāng)系統(tǒng)進(jìn)入到分區(qū)模式，它有兩種可行的策略。其一是限制部分操作，因此會(huì)削弱可用性。其二是額外記錄一些有利于后面分區(qū)恢復(fù)的操作信息。系統(tǒng)可通過(guò)持續(xù)嘗試恢復(fù)通信來(lái)察覺(jué)分區(qū)何時(shí)結(jié)束。
決定限制哪些操作，主要取決于系統(tǒng)需要維持哪幾項(xiàng)不變性約束。在給定了不變性約束條件之后，設(shè)計(jì)師需要決定在分區(qū)模式下，是否堅(jiān)持不觸動(dòng)某項(xiàng)不變性約束，抑或以事后恢復(fù)為前提去冒險(xiǎn)觸犯它。例如，對(duì)于“表中鍵的惟一性”這項(xiàng)不變性約束，設(shè)計(jì)師一般都選擇在分區(qū)期間放寬要求，容許重復(fù)的鍵。重復(fù)的鍵很容易在恢復(fù)階段檢查出來(lái)，假如重復(fù)鍵可以合并，那么設(shè)計(jì)師不難恢復(fù)這項(xiàng)不變性約束。
對(duì)于分區(qū)期間必須維持的不變性約束，設(shè)計(jì)師應(yīng)當(dāng)禁止或改動(dòng)可能觸犯該不變性約束的操作。（一般而言，我們沒(méi)辦法知道操作是否真的會(huì)破壞不變性約束，因?yàn)闊o(wú)法知道分區(qū)另一側(cè)的狀態(tài)。）信用卡扣費(fèi)等具有外部化特征的事件常以這種方式工作。適合這種情況的策略，是記錄下操作意圖，然后在分區(qū)恢復(fù)后再執(zhí)行操作。這類事務(wù)往往從屬于一些更大的工作流，在工作流明確含有類似“訂單處理中”狀態(tài)的情況下，將操作推遲到分區(qū)結(jié)束并無(wú)明顯的壞處。設(shè)計(jì)師以用戶不易察覺(jué)的方式犧牲了可用性。用戶只知道自己下了指令，系統(tǒng)稍后會(huì)執(zhí)行。
說(shuō)得更概括一點(diǎn)，分區(qū)模式給用戶界面提出了一種根本性的挑戰(zhàn)，即如何傳達(dá)“任務(wù)正在進(jìn)行尚未完成”的信息。研究者已經(jīng)從離線操作的角度對(duì)此問(wèn)題進(jìn)行了一些深入的探索，離線操作可以看成時(shí)間很長(zhǎng)的一次分區(qū)。例如Bayou的日歷程序用顏色來(lái)區(qū)分顯示可能（暫時(shí)）不一致的條目13。工作流應(yīng)用和帶離線模式的云服務(wù)中也常見(jiàn)類似的提醒，前者的例子如交易中的電子郵件通知，后者的例子如Google Docs。
在分區(qū)模式的討論中，我們將關(guān)注點(diǎn)放在有明確意義的原子操作而非單純的讀寫(xiě)，其中一個(gè)原因是操作的抽象級(jí)別越高，對(duì)不變性約束的影響通常就越容易分析清楚。大體來(lái)說(shuō)，設(shè)計(jì)師要建立一張所有操作與所有不變性約束的叉乘表格，觀察并確定其中每一處操作可能與不變性約束相沖突的地方。對(duì)于這些沖突情況，設(shè)計(jì)師必須決定是否禁止、推遲或修改相應(yīng)的操作。在實(shí)踐中，這類決定還受到分區(qū)前狀態(tài)和/或環(huán)境參數(shù)的影響。例如有的系統(tǒng)為特定的數(shù)據(jù)設(shè)立了主節(jié)點(diǎn)，那么一般允許主節(jié)點(diǎn)執(zhí)行操作，不允許其他節(jié)點(diǎn)操作。
對(duì)分區(qū)兩側(cè)跟蹤操作歷史的最佳方式是使用版本向量，版本向量可以反映操作間的因果依賴關(guān)系。向量的元素是（節(jié)點(diǎn), 邏輯時(shí)間）數(shù)值對(duì)，分別對(duì)應(yīng)一個(gè)更新了對(duì)象的節(jié)點(diǎn)和它最后更新的時(shí)間。對(duì)于同一對(duì)象的兩個(gè)給定的版本A和B，當(dāng)所有結(jié)點(diǎn)的版本向量一致有A的時(shí)間大于或等于B的時(shí)間，且至少有一個(gè)節(jié)點(diǎn)的版本向量有A的時(shí)間較大，則A新于B。
如果不可能對(duì)版本向量排序，那么更新操作是并發(fā)的，而且有可能出現(xiàn)不一致的情況。只要知道分區(qū)兩側(cè)版本向量的沿革。系統(tǒng)不難判斷哪些操作的執(zhí)行順序是確定的，哪些操作是并發(fā)的。最近的研究成果證明14，當(dāng)設(shè)計(jì)師選擇可用性優(yōu)先，一般最多只能將一致性收緊到這樣的程度。
到了某個(gè)時(shí)刻，通信恢復(fù)，分區(qū)結(jié)束。由于每一側(cè)在分區(qū)期間都是可用的，其狀態(tài)仍繼續(xù)向前進(jìn)展，但是分區(qū)會(huì)推遲某些操作并侵犯一些不變性約束。分區(qū)結(jié)束的時(shí)刻，系統(tǒng)知道分區(qū)兩側(cè)的當(dāng)前狀態(tài)和歷史記錄，因?yàn)樗诜謪^(qū)模式下記錄了詳盡的日志。當(dāng)前狀態(tài)不如歷史記錄有價(jià)值，因?yàn)橥ㄟ^(guò)歷史記錄，系統(tǒng)可以判斷哪些操作違反了不變性約束，產(chǎn)生了何種外在的后果（如發(fā)送了響應(yīng)給用戶）。在分區(qū)恢復(fù)過(guò)程中，設(shè)計(jì)師必須解決兩個(gè)問(wèn)題：
通常情況，矯正當(dāng)前狀態(tài)最簡(jiǎn)單的解決方法是回退到分區(qū)開(kāi)始時(shí)的狀態(tài)，以特定方式推進(jìn)分區(qū)兩側(cè)的一系列操作，并在過(guò)程中一直保持一致的狀態(tài)。Bayou就是這個(gè)實(shí)現(xiàn)機(jī)制，它會(huì)回滾數(shù)據(jù)庫(kù)到正確的時(shí)刻并按無(wú)歧義的、確定性的順序重新執(zhí)行所有的操作，最終使所有的節(jié)點(diǎn)達(dá)到相同的狀態(tài)15。同樣地，并發(fā)版本控制系統(tǒng)CVS在合并分支的時(shí)候，也是從從一個(gè)共享的狀態(tài)一致點(diǎn)開(kāi)始，逐步將更新合并上去。。
大部分系統(tǒng)都存在不能自動(dòng)合并的沖突。比如，CVS時(shí)不時(shí)有些沖突需要手動(dòng)介入，帶離線模式的wiki系統(tǒng)總是把沖突留在產(chǎn)生的文檔里給用戶處理16。
相反，有些系統(tǒng)用了限制操作的辦法來(lái)保證沖突總能合并。一個(gè)例子就是Google Docs將其文本編輯操作17精簡(jiǎn)為應(yīng)用樣式、添加文本和刪除文本。因此，雖然總的來(lái)說(shuō)沖突問(wèn)題不可解，但現(xiàn)實(shí)中設(shè)計(jì)師可以選擇在分區(qū)期間限制使用部分操作，以便系統(tǒng)在恢復(fù)的時(shí)候能夠自動(dòng)合并狀態(tài)。如果要實(shí)施這種策略，推遲有風(fēng)險(xiǎn)的操作是相對(duì)簡(jiǎn)單的實(shí)現(xiàn)方式。
還有一種辦法是讓操作可以交換順序，這種辦法最接近于形成一種解決自動(dòng)狀態(tài)合并問(wèn)題的通用框架。此類系統(tǒng)將線性合并各日志并重排操作的順序，然后執(zhí)行。操作滿足交換率，意味著操作有可能重新排列成一種全局一致的最佳順序。不幸的是，只允許滿足交換率的操作這個(gè)想法實(shí)現(xiàn)起來(lái)沒(méi)那么容易。比如加法操作可以交換順序，但是加入了越界檢查的加法就不行了。
Marc Shapiro及其INRIA同事最近的工作18,19對(duì)于可交換順序的操作在狀態(tài)合并方面的應(yīng)用起了很大的促進(jìn)作用。該團(tuán)隊(duì)提出一種從理論上證明可以保證分區(qū)后合并的數(shù)據(jù)類型，稱為可交換多副本數(shù)據(jù)類型（commutative replicated data types，CRDTs）。他們介紹了如何使用此類數(shù)據(jù)結(jié)構(gòu)來(lái)
用后一種方法合并狀態(tài)會(huì)匯總分區(qū)兩邊的最大集合。這種方法是對(duì)亞馬遜購(gòu)物車(chē)合并算法20的形式化總結(jié)和改良，合并后的數(shù)據(jù)是兩邊購(gòu)物車(chē)的并集，而并運(yùn)算是一種單調(diào)的集合運(yùn)算。這種策略的壞處是刪掉的購(gòu)物車(chē)商品有可能再次出現(xiàn)。
其實(shí)CRDTs完全可以實(shí)現(xiàn)同時(shí)支持增、刪操作的分區(qū)耐受集合。此方法的本質(zhì)是維護(hù)兩個(gè)集合：一個(gè)放增加的項(xiàng)目，一個(gè)放刪除的項(xiàng)目，兩集合之差即為真正的集合成員。增集合、刪集合分別合并起來(lái)都不困難，因而增刪集合之差合并起來(lái)也不困難。在某個(gè)時(shí)間點(diǎn)上，系統(tǒng)可以從兩個(gè)集合中清理掉刪除的數(shù)據(jù)項(xiàng)。假如按照一般的設(shè)計(jì)，像這種清理操作僅在系統(tǒng)沒(méi)分區(qū)的時(shí)候才可行，屬于設(shè)計(jì)師必須在分區(qū)期間禁止或推遲的特定操作，但是CRDTs的清理操作并不會(huì)對(duì)可用性產(chǎn)生外在的影響。因此通過(guò)CRDTs來(lái)實(shí)現(xiàn)狀態(tài)，設(shè)計(jì)師既保證了可用性，又保證了分區(qū)后系統(tǒng)自動(dòng)合并狀態(tài)。
比計(jì)算分區(qū)后狀態(tài)更難解決的問(wèn)題是如何彌補(bǔ)分區(qū)期間造成的錯(cuò)誤。跟蹤和限制分區(qū)模式下的操作，這兩種措施足以使設(shè)計(jì)師確知哪些不變性約束可能被違反，然后分別為它們制定恢復(fù)策略。一般系統(tǒng)在分區(qū)恢復(fù)期間檢查違反情況，修復(fù)工作也必須在這段時(shí)間內(nèi)完成。
恢復(fù)不變性約束的方法有很多，粗陋一點(diǎn)的辦法如“最后寫(xiě)入者勝”（因此會(huì)忽略部分更新），聰明一點(diǎn)的辦法如合并操作和人為跟進(jìn)事態(tài)（human escalation）。人為跟進(jìn)事態(tài)的例子如飛機(jī)航班“超售”的情形：可以把乘客登機(jī)看作是對(duì)之前售票情況的分區(qū)恢復(fù)，必須恢復(fù)“座位數(shù)不少于乘客數(shù)”這項(xiàng)不變性約束。那么當(dāng)乘客太多的時(shí)候，有些乘客將失去座位，客服最好能設(shè)法補(bǔ)償他們。
航班的例子揭示了一個(gè)外在錯(cuò)誤（externalized mistake）：假如航空公司沒(méi)說(shuō)過(guò)乘客一定有座位，這個(gè)問(wèn)題會(huì)好解決得多。因此我們看到推遲有風(fēng)險(xiǎn)的操作的又一個(gè)理由——到了分區(qū)恢復(fù)的時(shí)候，我們才知道真實(shí)的情況。矯正此類錯(cuò)誤的核心概念是“補(bǔ)償（compensation）”；設(shè)計(jì)師必須設(shè)立補(bǔ)償操作，除了恢復(fù)不變性約束，還要糾正外在錯(cuò)誤。
技術(shù)上CRDTs只允許局部可驗(yàn)證的不變性約束，所以沒(méi)有補(bǔ)償?shù)谋匾?，雖然這種限制降低了CRDTs方法本身的能力。用了CRDTs來(lái)處理狀態(tài)合并的設(shè)計(jì)方案可以允許暫時(shí)違反全局性的不變量約束，分區(qū)結(jié)束后才合并狀態(tài)，以及履行必要的補(bǔ)償。
恢復(fù)外在錯(cuò)誤通常要求知道一些有關(guān)外在輸出的歷史信息。以“喝醉酒打電話”為例，一位老兄不記得自己昨晚喝高了的時(shí)候打過(guò)幾個(gè)電話，雖然他第二天白天恢復(fù)了正常狀態(tài)，但通話日志上的記錄都還在，其中有些通話很可能是錯(cuò)誤的。撥出的電話就是這位老兄的狀態(tài)（喝高了）的外在影響。而由于這位老兄不記得打過(guò)什么電話，也就很難補(bǔ)償其中可能造成的麻煩。
又以機(jī)器為例，電腦可能在分區(qū)期間把一份訂單執(zhí)行了兩次。如果系統(tǒng)能區(qū)分兩份一樣的訂單是有意的還是重復(fù)了，它就能取消掉一份重復(fù)的訂單。如果這次錯(cuò)誤產(chǎn)生了外在影響，補(bǔ)償策略可以是自動(dòng)生成一封電子郵件，向顧客解釋系統(tǒng)意外將訂單執(zhí)行了兩次，現(xiàn)在錯(cuò)誤已經(jīng)被糾正，附上一張優(yōu)惠券下次可以用。假如沒(méi)有完善的歷史記錄，就只好靠顧客親自去發(fā)現(xiàn)錯(cuò)誤了。
曾經(jīng)有人正式研究過(guò)將補(bǔ)償性事務(wù)作為處理長(zhǎng)壽命事務(wù)（long-lived transactions）的一種手段21,22。長(zhǎng)時(shí)間運(yùn)行的事務(wù)會(huì)面臨另一種形態(tài)的分區(qū)決策：是長(zhǎng)時(shí)間持有鎖來(lái)保證一致性比較好呢？還是及早釋放鎖向其他事務(wù)暴露未提交的數(shù)據(jù)，提高并發(fā)能力比較好呢？比如在單筆事務(wù)中更新所有的員工記錄就是一個(gè)典型例子。按照一般的方式串行化這筆事務(wù)，將導(dǎo)致所有的記錄都被鎖定，阻止并發(fā)。而補(bǔ)償性事務(wù)采取另一種方式，它將大事務(wù)拆成多個(gè)分別提交的子事務(wù)。如果要中止大事務(wù)，系統(tǒng)必須發(fā)起一筆新的、起糾正作用的事務(wù)，逐一撤銷所有已經(jīng)提交的子事務(wù)，這筆新事務(wù)就是所謂的補(bǔ)償性事務(wù)。
總的來(lái)說(shuō)，補(bǔ)償性事務(wù)的目的是避免中止其他用了未正確提交數(shù)據(jù)的事務(wù)（即不允許級(jí)聯(lián)取消）。這種方案不依賴串行化或隔離的手段來(lái)保障正確性，其正確性取決于事務(wù)序列對(duì)狀態(tài)和輸出所產(chǎn)生的凈影響。那么，經(jīng)過(guò)補(bǔ)償，數(shù)據(jù)庫(kù)的狀態(tài)究竟是不是相當(dāng)于那些子事務(wù)根本沒(méi)執(zhí)行過(guò)一樣呢？考慮等價(jià)必須連外在行為也包括在內(nèi)；舉個(gè)例子，把重復(fù)扣取的交易款退還給顧客，很難說(shuō)成等于一開(kāi)始就沒(méi)多收顧客的錢(qián)，但從結(jié)果上看勉強(qiáng)算扯平了。分區(qū)恢復(fù)也延續(xù)同樣的思路。雖然服務(wù)不一定總能直接撤銷其錯(cuò)誤，但起碼承認(rèn)錯(cuò)誤并做出新的補(bǔ)償行為。怎樣在分區(qū)恢復(fù)中運(yùn)用這種思路效果最好，這個(gè)問(wèn)題沒(méi)有固定的答案。“自動(dòng)柜員機(jī)上的補(bǔ)償問(wèn)題”小節(jié)以一個(gè)很小的應(yīng)用領(lǐng)域?yàn)槔c(diǎn)出了一些思考方向。
當(dāng)系統(tǒng)中存在分區(qū)，系統(tǒng)設(shè)計(jì)師不應(yīng)該盲目地犧牲一致性或可用性。運(yùn)用以上討論的方法，設(shè)計(jì)師通過(guò)細(xì)致地管理分區(qū)期間的不變性約束，兩方面的性質(zhì)都可以取得最佳的表現(xiàn)。隨著版本向量和CRDTs等比較新的技術(shù)逐漸被納入一些簡(jiǎn)化其用法的框架，這方面的優(yōu)化手段會(huì)得到比較普遍的應(yīng)用。但引入CAP實(shí)踐畢竟不像引入ACID事務(wù)那么簡(jiǎn)單，實(shí)施的時(shí)候需要對(duì)過(guò)去的策略進(jìn)行全面的考慮，最佳的實(shí)施方案極大地依賴于具體服務(wù)的不變性約束和操作細(xì)節(jié)。
以自動(dòng)柜員機(jī)（ATM）的設(shè)計(jì)來(lái)說(shuō)，強(qiáng)一致性看似符合邏輯的選擇，但現(xiàn)實(shí)情況是可用性遠(yuǎn)比一致性重要。理由很簡(jiǎn)單：高可用性意味著高收入。不管怎么樣，討論如何補(bǔ)償分區(qū)期間被破壞的不變性約束，ATM的設(shè)計(jì)很適合作為例子。
ATM的基本操作是存款、取款、查看余額。關(guān)鍵的不變性約束是余額應(yīng)大于或等于零。因?yàn)橹挥腥】畈僮鲿?huì)觸犯這項(xiàng)不變性約束，也就只有取款操作將受到特別對(duì)待，其他兩種操作隨時(shí)都可以執(zhí)行。
ATM系統(tǒng)設(shè)計(jì)師可以選擇在分區(qū)期間禁止取款操作，因?yàn)樵谀嵌螘r(shí)間里沒(méi)辦法知道真實(shí)的余額，當(dāng)然這樣會(huì)損害可用性?，F(xiàn)代ATM的做法正相反，在stand-in模式下（即分區(qū)模式），ATM限制凈取款額不得高于k，比如k為$200。低于限額的時(shí)候，取款完全正常；當(dāng)超過(guò)限額的時(shí)候，系統(tǒng)拒絕取款操作。這樣，ATM成功將可用性限制在一個(gè)合理的水平上，既允許取款操作，又限制了風(fēng)險(xiǎn)。
分區(qū)結(jié)束的時(shí)候，必須有一些措施來(lái)恢復(fù)一致性和補(bǔ)償分區(qū)期間系統(tǒng)所造成的錯(cuò)誤。狀態(tài)的恢復(fù)比較簡(jiǎn)單，因?yàn)椴僮鞫际欠辖粨Q率的，補(bǔ)償就要分幾種情況去考慮。最后的余額低于零違反了不變性約束。由于ATM已經(jīng)把錢(qián)吐出去了，錯(cuò)誤成了外部實(shí)在。銀行的補(bǔ)償辦法是收取透支費(fèi)并指望顧客償還。因?yàn)轱L(fēng)險(xiǎn)已經(jīng)受到限制，問(wèn)題并不嚴(yán)重。還有一種情況是分區(qū)期間的某一刻余額已經(jīng)小于零（但ATM不知道），此時(shí)一筆存款重新將余額變?yōu)檎?。銀行可以追溯產(chǎn)生透支費(fèi)，也可以因?yàn)轭櫩鸵呀?jīng)繳付而忽略該違反情況。
總而言之，因?yàn)橥ㄐ叛舆t的存在，銀行系統(tǒng)不依靠一致性來(lái)保證正確性，而更多地依靠審計(jì)和補(bǔ)償。“空頭支票詐騙”也是類似的例子，顧客趕在多家分行對(duì)賬之前分別取出錢(qián)來(lái)然后逃跑。透支的錯(cuò)誤過(guò)后才會(huì)被發(fā)現(xiàn)，對(duì)錯(cuò)誤的補(bǔ)償也許體現(xiàn)為法律行動(dòng)的形式。
感謝Mike Dahlin、Hank Korth、Marc Shapiro、Justin Sheehy、Amin Vahdat、Ben Zhao以及IEEE Computer Society的志愿者們，感謝他們對(duì)本文的有益反饋。
Eric Brewer是University of California, Berkeley的計(jì)算機(jī)科學(xué)教授，在Google擔(dān)任基礎(chǔ)設(shè)施方面的VP。他的研究興趣包括云計(jì)算、可伸縮的服務(wù)器、傳感器網(wǎng)絡(luò)，還有適合發(fā)展中地區(qū)應(yīng)用的技術(shù)。他還幫助建立了美國(guó)聯(lián)邦政府的門(mén)戶網(wǎng)站USA.gov。Brewer從MIT獲得電子工程和計(jì)算機(jī)科學(xué)的博士學(xué)位。他是National Academy of Engineering的院士。聯(lián)系方式：http://www.360doc.com/mailto:brewer@cs.berkeley.edu
Computer雜志是IEEE Computer Society的旗艦刊物，發(fā)表經(jīng)過(guò)同行評(píng)議的高水平文章，讀者和作者都是從事各類計(jì)算科技相關(guān)領(lǐng)域的專業(yè)人士，文章涵蓋的范圍囊括軟硬件的新研究和新應(yīng)用。這本雜志比商業(yè)雜志更注重技術(shù)內(nèi)涵，比研究期刊更注重實(shí)用思維。Computer為您傳遞工作中用得上的信息。
1. E. Brewer, "Lessons from Giant-Scale Services," IEEE Internet Computing, July/Aug. 2001, pp. 46-55.
2. A. Fox et al., "Cluster-Based Scalable Network Services," Proc. 16th ACM Symp. Operating Systems Principles (SOSP 97), ACM, 1997, pp. 78-91.
3. A. Fox and E.A. Brewer, "Harvest, Yield and Scalable Tolerant Systems," Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pp. 174-178.
4. E. Brewer, "Towards Robust Distributed Systems," Proc. 19th Ann. ACM Symp.Principles of Distributed Computing (PODC 00), ACM, 2000, pp. 7-10; on-line resource.
5. B. Cooper et al., "PNUTS: Yahoo!’s Hosted Data Serving Platform," Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288.
6. J. Sobel, "Scaling Out," Facebook Engineering Notes, 20 Aug. 2008; on-line resource.
7. J. Kistler and M. Satyanarayanan, "Disconnected Operation in the Coda File System" ACM Trans. Computer Systems, Feb. 1992, pp. 3-25.
8. K. Birman, Q. Huang, and D. Freedman, "Overcoming the ‘D’ in CAP: Using Isis2 to Build Locally Responsive Cloud Services," Computer, Feb. 2011, pp. 50-58.
9. M. Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems," Proc. Symp. Operating Systems Design and Implementation (OSDI 06), Usenix, 2006, pp. 335-350.
10. J. Baker et al., "Megastore: Providing Scalable, Highly Available Storage for Interactive Services," Proc. 5th Biennial Conf. Innovative Data Systems Research (CIDR 11), ACM, 2011, pp. 223-234.
11. D. Abadi, "Problems with CAP, and Yahoo’s Little Known NoSQL System," DBMS Musings, blog, 23 Apr. 2010; on-line resource.
12. C. Hale, "You Can’t Sacrifice Partition Tolerance," 7 Oct. 2010; on-line resource.
13. W. K. Edwards et al., "Designing and Implementing Asynchronous Collaborative Applications with Bayou," Proc. 10th Ann. ACM Symp. User Interface Software and Technology (UIST 97), ACM, 1999, pp. 119-128.
14. P. Mahajan, L. Alvisi, and M. Dahlin, Consistency, Availability, and Convergence, tech. report UTCS TR-11-22, Univ. of Texas at Austin, 2011.
15. D.B. Terry et al., "Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System," Proc. 15th ACM Symp. Operating Systems Principles (SOSP 95), ACM, 1995, pp. 172-182.
16. B. Du and E.A. Brewer, "DTWiki: A Disconnection and Intermittency Tolerant Wiki," Proc. 17th Int’l Conf. World Wide Web (WWW 08), ACM, 2008, pp. 945-952.
17. "What’s Different about the New Google Docs: Conflict Resolution" blog.
18. M. Shapiro et al., "Conflict-Free Replicated Data Types," Proc. 13th Int’l Conf. Stabilization, Safety, and Security of Distributed Systems (SSS 11), ACM, 2011, pp. 386-400.
19. M. Shapiro et al., "Convergent and Commutative Replicated Data Types," Bulletin of the EATCS, no. 104, June 2011, pp. 67-88.
20. G. DeCandia et al., "Dynamo: Amazon’s Highly Available Key-Value Store," Proc. 21st ACM SIGOPS Symp. Operating Systems Principles (SOSP 07), ACM, 2007, pp. 205-220.
21. H. Garcia-Molina and K. Salem, "SAGAS," Proc. ACM SIGMOD Int’l Conf. Management of Data (SIGMOD 87), ACM, 1987, pp. 249-259.
22. H. Korth, E. Levy, and A. Silberschatz, "A Formal Approach to Recovery by Compensating Transactions," Proc. VLDB Endowment (VLDB 90), ACM, 1990, pp. 95-106
聯(lián)系客服
