CAP理論斷言任何基于網(wǎng)絡(luò)的數(shù)據(jù)共享系統(tǒng)虫埂，最多只能滿足數(shù)據(jù)一致性、可用性圃验、分區(qū)容忍性三要素中的兩個要素掉伏。但是通過顯式處理分區(qū)情形，系統(tǒng)設(shè)計師可以做到優(yōu)化數(shù)據(jù)一致性和可用性，進(jìn)而取得三者之間的平衡斧散。

自打引入CAP理論的十幾年里供常，設(shè)計師和研究者已經(jīng)以它為理論基礎(chǔ)探索了各式各樣新穎的分布式系統(tǒng)，甚至到了濫用的程度鸡捐。NoSQL運(yùn)動也將CAP理論當(dāng)作對抗傳統(tǒng)關(guān)系型數(shù)據(jù)庫的依據(jù)栈暇。

CAP理論主張任何基于網(wǎng)絡(luò)的數(shù)據(jù)共享系統(tǒng)，都最多只能擁有以下三條中的兩條：

• 數(shù)據(jù)一致性（C）箍镜，等同于所有節(jié)點(diǎn)訪問同一份最新的數(shù)據(jù)副本源祈；
• 對數(shù)據(jù)更新具備高可用性（A）；
• 能容忍網(wǎng)絡(luò)分區(qū)（P）色迂。

CAP理論的表述很好地服務(wù)了它的目的香缺，即開闊設(shè)計師的思路，在多樣化的取舍方案下設(shè)計出多樣化的系統(tǒng)歇僧。在過去的十幾年里確實(shí)涌現(xiàn)了不計其數(shù)的新系統(tǒng)赫悄，也隨之在數(shù)據(jù)一致性和可用性的相對關(guān)系上產(chǎn)生了相當(dāng)多的爭論×罂“三選二”的公式一直存在著誤導(dǎo)性，它會過分簡單化各性質(zhì)之間的相互關(guān)系」糜纾現(xiàn)在我們有必要辨析其中的細(xì)節(jié)写隶。實(shí)際上只有“在分區(qū)存在的前提下呈現(xiàn)完美的數(shù)據(jù)一致性和可用性”這種很少見的情況是CAP理論不允許出現(xiàn)的。

雖然設(shè)計師仍然需要在分區(qū)的前提下對數(shù)據(jù)一致性和可用性做取舍讲仰，但具體如何處理分區(qū)和恢復(fù)一致性慕趴，這里面有不計其數(shù)的變通方案和靈活度。當(dāng)代CAP實(shí)踐應(yīng)將目標(biāo)定為針對具體的應(yīng)用鄙陡，在合理范圍內(nèi)最大化數(shù)據(jù)一致性和可用性的“合力”冕房。這樣的思路延伸為如何規(guī)劃分區(qū)期間的操作和分區(qū)之后的恢復(fù)，從而啟發(fā)設(shè)計師加深對CAP的認(rèn)識趁矾，突破過去由于CAP理論的表述而產(chǎn)生的思維局限耙册。

為什么“三選二”公式有誤導(dǎo)性

理解CAP理論的最簡單方式是想象兩個節(jié)點(diǎn)分處分區(qū)兩側(cè)。允許至少一個節(jié)點(diǎn)更新狀態(tài)會導(dǎo)致數(shù)據(jù)不一致毫捣，即喪失了C性質(zhì)详拙。如果為了保證數(shù)據(jù)一致性，將分區(qū)一側(cè)的節(jié)點(diǎn)設(shè)置為不可用蔓同，那么又喪失了A性質(zhì)饶辙。除非兩個節(jié)點(diǎn)可以互相通信，才能既保證C又保證A斑粱，這又會導(dǎo)致喪失P性質(zhì)弃揽。一般來說跨區(qū)域的系統(tǒng)，設(shè)計師無法舍棄P性質(zhì)，那么就只能在數(shù)據(jù)一致性和可用性上做一個艱難選擇矿微。不確切地說痕慢，NoSQL運(yùn)動的主題其實(shí)是創(chuàng)造各種可用性優(yōu)先、數(shù)據(jù)一致性其次的方案冷冗；而傳統(tǒng)數(shù)據(jù)庫堅守ACID特性（原子性守屉、一致性、隔離性蒿辙、持久性）拇泛，做的是相反的事情。下文“ACID思灌、BASE俺叭、CAP”小節(jié)詳細(xì)說明了它們的差異。

事實(shí)上泰偿，CAP理論本身就是在類似的討論中誕生的熄守。早在1990年代中期，我和同事構(gòu)建了一系列的基于集群的跨區(qū)域系統(tǒng)（實(shí)質(zhì)上是早期的云計算）耗跛，包括搜索引擎裕照、緩存代理以及內(nèi)容分發(fā)系統(tǒng)¹。從收入目標(biāo)以及合約規(guī)定來講调塌，系統(tǒng)可用性是首要目標(biāo)晋南，因而我們常規(guī)會使用緩存或者事后校核更新日志來優(yōu)化系統(tǒng)的可用性。盡管這些策略提升了系統(tǒng)的可用性羔砾，但這是以犧牲系統(tǒng)數(shù)據(jù)一致性為代價的负间。

關(guān)于“數(shù)據(jù)一致性 VS 可用性”的第一回合爭論，表現(xiàn)為ACID與BASE之爭²姜凄。當(dāng)時BASE還不怎么被人們接受政溃，主要是大家看重ACID的優(yōu)點(diǎn)而不愿意放棄。提出CAP理論态秧，目的是證明有必要開拓更廣闊的設(shè)計空間董虱，因此才有了“三選二”公式。CAP理論最早在1998年秋季提出申鱼，1999年正式發(fā)表³空扎，并在2000年登上Symposium on Principles of Distributed Computing大會的主題演講⁴，最終確立了該理論的正確性。

“三選二”的觀點(diǎn)在幾個方面起了誤導(dǎo)作用，詳見下文“CAP之惑”小節(jié)的解釋骂维。首先，由于分區(qū)很少發(fā)生撮慨，那么在系統(tǒng)不存在分區(qū)的情況下沒什么理由犧牲C或A竿痰。其次，C與A之間的取舍可以在同一系統(tǒng)內(nèi)以非常細(xì)小的粒度反復(fù)發(fā)生砌溺，而每一次的決策可能因?yàn)榫唧w的操作影涉，乃至因?yàn)闋可娴教囟ǖ臄?shù)據(jù)或用戶而有所不同。最后规伐，這三種性質(zhì)都可以在程度上衡量蟹倾，并不是非黑即白的有或無〔粒可用性顯然是在0%到100%之間連續(xù)變化的鲜棠，一致性分很多級別，連分區(qū)也可以細(xì)分為不同含義培慌，如系統(tǒng)內(nèi)的不同部分對于是否存在分區(qū)可以有不一樣的認(rèn)知豁陆。

要探索這些細(xì)微的差別，就要突破傳統(tǒng)的分區(qū)處理方式吵护，而這是一項(xiàng)根本性的挑戰(zhàn)盒音。因?yàn)榉謪^(qū)很少出現(xiàn)，CAP在大多數(shù)時候允許完美的C和A馅而。但當(dāng)分區(qū)存在或可感知其影響的情況下祥诽，就要預(yù)備一種策略去探知分區(qū)并顯式處理其影響。這樣的策略應(yīng)分為三個步驟：探知分區(qū)發(fā)生瓮恭，進(jìn)入顯式的分區(qū)模式以限制某些操作雄坪，啟動恢復(fù)過程以恢復(fù)數(shù)據(jù)一致性并補(bǔ)償分區(qū)期間發(fā)生的錯誤。

ACID偎血、BASE、CAP

ACID和BASE代表了兩種截然相反的設(shè)計哲學(xué)盯漂，分處一致性-可用性分布圖譜的兩極颇玷。ACID注重一致性，是數(shù)據(jù)庫的傳統(tǒng)設(shè)計思路就缆。我和同事在1990年代晚期提出BASE帖渠，目的是抓住當(dāng)時正逐漸成型的一些針對高可用性的設(shè)計思路，并且把不同性質(zhì)之間的取舍和消長關(guān)系擺上臺面〗咴祝現(xiàn)代大規(guī)目战迹跨區(qū)域分布的系統(tǒng)，包括云在內(nèi)切揭，同時運(yùn)用了這兩種思路狞甚。

這兩個術(shù)語都好記有余而精確不足，出現(xiàn)較晚的BASE硬湊的感覺更明顯廓旬，它是“Basically Available, Soft state, Eventually consistent（基本可用哼审、軟狀態(tài)、最終一致性）”的首字母縮寫。其中的軟狀態(tài)和最終一致性這兩種技巧擅于對付存在分區(qū)的場合涩盾，并因此提高了可用性十气。

CAP與ACID的關(guān)系更復(fù)雜一些，也因此引起更多誤解春霍。其中一個原因是ACID的C和A字母所代表的概念不同于CAP的C和A砸西。還有一個原因是選擇可用性只部分地影響ACID約束。ACID四項(xiàng)特性分別為：

原子性（A）址儒。所有的系統(tǒng)都受惠于原子性操作芹枷。當(dāng)我們考慮可用性的時候，沒有理由去改變分區(qū)兩側(cè)操作的原子性离福。而且滿足ACID定義的杖狼、高抽象層次的原子操作，實(shí)際上會簡化分區(qū)恢復(fù)妖爷。

一致性（C）蝶涩。ACID的C指的是事務(wù)不能破壞任何數(shù)據(jù)庫規(guī)則，如鍵的唯一性絮识。與之相比绿聘，CAP的C僅指單一副本這個意義上的一致性，因此只是ACID一致性約束的一個嚴(yán)格的子集次舌。ACID一致性不可能在分區(qū)過程中保持熄攘，因此分區(qū)恢復(fù)時需要重建ACID一致性。推而廣之彼念，分區(qū)期間也許不可能維持某些不變性約束挪圾，所以有必要仔細(xì)考慮哪些操作應(yīng)該禁止，分區(qū)后又如何恢復(fù)這些不變性約束逐沙。

隔離性（I）哲思。隔離是CAP理論的核心：如果系統(tǒng)要求ACID隔離性，那么它在分區(qū)期間最多可以在分區(qū)一側(cè)維持操作吩案。事務(wù)的可串行性（serializability）要求全局的通信棚赔，因此在分區(qū)的情況下不能成立。只要在分區(qū)恢復(fù)時進(jìn)行補(bǔ)償徘郭，在分區(qū)前后保持一個較弱的正確性定義是可行的靠益。

持久性（D）。犧牲持久性沒有意義残揉，理由和原子性一樣胧后，雖然開發(fā)者有理由（持久性成本太高）選擇BASE風(fēng)格的軟狀態(tài)來避免實(shí)現(xiàn)持久性。這里有一個細(xì)節(jié)抱环，分區(qū)恢復(fù)可能因?yàn)榛赝顺志眯圆僮骷保鵁o意中破壞某項(xiàng)不變性約束途样。但只要恢復(fù)時給定分區(qū)兩側(cè)的持久性操作歷史記錄，破壞不變性約束的操作還是可以被檢測出來并修正的濒憋。通常來講何暇，讓分區(qū)兩側(cè)的事務(wù)都滿足ACID特性會使得后續(xù)的分區(qū)恢復(fù)變得更容易，并且為分區(qū)恢復(fù)時事務(wù)的補(bǔ)償工作奠定了基本的條件凛驮。

CAP和延遲的聯(lián)系

CAP理論的經(jīng)典解釋裆站，是忽略網(wǎng)絡(luò)延遲的，但在實(shí)際中延遲和分區(qū)緊密相關(guān)黔夭。CAP從理論變?yōu)楝F(xiàn)實(shí)的場景發(fā)生在操作的間歇宏胯，系統(tǒng)需要在這段時間內(nèi)做出關(guān)于分區(qū)的一個重要決定：

• 取消操作因而降低系統(tǒng)的可用性，還是
• 繼續(xù)操作本姥，以冒險損失系統(tǒng)一致性為代價

依靠多次嘗試通信的方法來達(dá)到一致性肩袍，比如Paxos算法或者兩階段事務(wù)提交，僅僅是推遲了決策的時間婚惫。系統(tǒng)終究要做一個決定氛赐；無限期地嘗試下去，本身就是選擇一致性犧牲可用性的表現(xiàn)先舷。

因此以實(shí)際效果而言艰管，分區(qū)相當(dāng)于對通信的時限要求。系統(tǒng)如果不能在時限內(nèi)達(dá)成數(shù)據(jù)一致性蒋川，就意味著發(fā)生了分區(qū)的情況牲芋，必須就當(dāng)前操作在C和A之間做出選擇。這就從延遲的角度抓住了設(shè)計的核心問題：分區(qū)兩側(cè)是否在無通信的情況下繼續(xù)其操作捺球？

從這個實(shí)用的觀察角度出發(fā)可以導(dǎo)出若干重要的推論缸浦。第一，分區(qū)并不是全體節(jié)點(diǎn)的一致見解氮兵，因?yàn)橛行┕?jié)點(diǎn)檢測到了分區(qū)裂逐，有些可能沒有。第二胆剧，檢測到分區(qū)的節(jié)點(diǎn)即進(jìn)入分區(qū)模式——這是優(yōu)化C和A的核心環(huán)節(jié)絮姆。

最后醉冤，這個觀察角度還意味著設(shè)計師可以根據(jù)期望中的響應(yīng)時間秩霍，有意識地設(shè)置時限；時限設(shè)得越短蚁阳，系統(tǒng)進(jìn)入分區(qū)模式越頻繁铃绒，其中有些時候并不一定真的發(fā)生了分區(qū)的情況，可能只是網(wǎng)絡(luò)變慢而已螺捐。

有時候在跨區(qū)域的系統(tǒng)颠悬，放棄強(qiáng)一致性來避免保持?jǐn)?shù)據(jù)一致所帶來的高延遲是非常有意義的矮燎。Yahoo的PNUTS系統(tǒng)因?yàn)橐援惒降姆绞骄S護(hù)遠(yuǎn)程副本而帶來數(shù)據(jù)一致性的問題⁵。但好處是主副本就放在本地赔癌，減小操作的等待時間诞外。這個策略在實(shí)際中很實(shí)用，因?yàn)橐话銇碇v灾票，用戶數(shù)據(jù)大都會根據(jù)用戶的（日常）地理位置做分區(qū)峡谊。最理想的狀況是每一位用戶都在他的數(shù)據(jù)主副本附近。

Facebook使用了相反的策略⁶：主副本被固定在一個地方刊苍，因此遠(yuǎn)程用戶一般訪問到的是離他較近既们，但可能已經(jīng)過時的數(shù)據(jù)副本。不過當(dāng)用戶更新其頁面的時候是直接對主副本進(jìn)行更新正什，而且該用戶的所有讀操作也被短暫轉(zhuǎn)向從主副本讀取啥纸，盡管這樣延遲會比較高。20秒后婴氮，該用戶的流量被重新切換回離他較近的副本斯棒，此時副本應(yīng)該已經(jīng)同步好了剛才的更新。

CAP之惑

CAP理論經(jīng)常在不同方面被人誤解莹妒，對于可用性和一致性的作用范圍的誤解尤為嚴(yán)重名船，可能造成不希望看到的結(jié)果。如果用戶根本獲取不到服務(wù)旨怠，那么其實(shí)談不上C和A之間做取舍渠驼，除非把一部分服務(wù)放在客戶端上運(yùn)行，即所謂的無連接操作或稱離線模式⁷鉴腻。離線模式正變得越來越重要迷扇。HTML5的一些特性，特別是客戶端持久化存儲特性爽哎，將會促進(jìn)離線操作的發(fā)展蜓席。支持離線模式的系統(tǒng)通常會在C和A中選擇A，那么就不得不在長時間處于分區(qū)狀態(tài)后進(jìn)行恢復(fù)课锌。

“一致性的作用范圍”其實(shí)反映了這樣一種觀念厨内，即在一定的邊界內(nèi)狀態(tài)是一致的，但超出了邊界就無從談起渺贤。比如在一個主分區(qū)內(nèi)可以保證完備的一致性和可用性雏胃，而在分區(qū)外服務(wù)是不可用的。Paxos算法和原子性多播（atomic multicast）系統(tǒng)一般符合這樣的場景⁸志鞍。像Google的一般做法是將主分區(qū)歸屬在單一個數(shù)據(jù)中心里面瞭亮，然后交給Paxos算法去解決跨區(qū)域的問題，一方面保證全局協(xié)商一致（global consensus）如Chubby⁹固棚，一方面實(shí)現(xiàn)高可用的持久性存儲如Megastore¹⁰统翩。

分區(qū)期間仙蚜，獨(dú)立且能自我保證一致性的節(jié)點(diǎn)子集合可以繼續(xù)執(zhí)行操作，只是無法保證全局范圍的不變性約束不受破壞厂汗。數(shù)據(jù)分片（sharding）就是這樣的例子委粉，設(shè)計師預(yù)先將數(shù)據(jù)劃分到不同的分區(qū)節(jié)點(diǎn)，分區(qū)期間單個數(shù)據(jù)分片多半可以繼續(xù)操作娶桦。相反艳丛，如果被分區(qū)的是內(nèi)在關(guān)系密切的狀態(tài)，或者有某些全局性的不變性約束非保持不可趟紊，那么最好的情況是只有分區(qū)一側(cè)可以進(jìn)行操作氮双，最壞情況是操作完全不能進(jìn)行。

“三選二”的時候取CA而舍P是否合理霎匈？已經(jīng)有研究者指出了其中的要害——怎樣才算“舍P”含義并不明確^11,12戴差。設(shè)計師可以選擇不要分區(qū)嗎？哪怕原來選了CA铛嘱，當(dāng)分區(qū)出現(xiàn)的時候暖释，你也只能回頭重新在C和A之間再選一次。我們最好從概率的角度去理解：選擇CA意味著我們假定墨吓，分區(qū)出現(xiàn)的可能性要比其他的系統(tǒng)性錯誤（如自然災(zāi)難球匕、并發(fā)故障）低很多。

這種觀點(diǎn)在實(shí)際中很有意義帖烘，因?yàn)槟承┕收辖M合可能導(dǎo)致同時丟掉C和A亮曹，所以說CAP三個性質(zhì)都是一個度的問題。實(shí)踐中秘症，大部分團(tuán)體認(rèn)為（位于單一地點(diǎn)的）數(shù)據(jù)中心內(nèi)部是沒有分區(qū)的照卦，因此在單一數(shù)據(jù)中心之內(nèi)可以選擇CA；CAP理論出現(xiàn)之前乡摹，系統(tǒng)都默認(rèn)這樣的設(shè)計思路役耕，包括傳統(tǒng)數(shù)據(jù)庫在內(nèi)。然而就算可能性不高瞬痘，單一數(shù)據(jù)中心完全有可能出現(xiàn)分區(qū)的情況板熊，一旦出現(xiàn)就會動搖以CA為取向的設(shè)計基礎(chǔ)。最后邻邮，考慮到跨區(qū)域時出現(xiàn)的高延遲竣况，在數(shù)據(jù)一致性上讓步來換取更好性能的做法相對比較常見筒严。

CAP還有一個方面很多人認(rèn)識不清，那就是放棄一致性其實(shí)有隱藏負(fù)擔(dān)鸭蛙，即需要明確了解系統(tǒng)中存在的不變性約束摹恨。滿足一致性的系統(tǒng)有一種保持其不變性約束的自然傾向，即便設(shè)計師不清楚系統(tǒng)中所有的不變性約束晒哄，相當(dāng)一部分合理的不變性約束會自動地維持下去肪获。相反，當(dāng)設(shè)計師選擇可用性的時候较木，因?yàn)樾枰诜謪^(qū)結(jié)束后恢復(fù)被破壞的不變性約束青柄，顯然必須將各種不變性約束一一列舉出來，可想而知這件工作很有挑戰(zhàn)又很容易犯錯峰锁。放棄一致性為什么難双戳，其核心還是“并發(fā)更新問題”，跟多線程編程比順序編程難的原因是一樣的千诬。

管理分區(qū)

怎樣緩和分區(qū)對一致性和可用性的影響是對設(shè)計師的挑戰(zhàn)膏斤。其關(guān)鍵是以非常明確莫辨、公開的方式去管理分區(qū)，不僅需要主動察覺分區(qū)的發(fā)生沮榜，還需要為分區(qū)期間所有可能受侵害的不變性約束預(yù)備專門的恢復(fù)過程和計劃蟆融。管理分區(qū)有三個步驟：

• 檢測到分區(qū)開始
• 明確進(jìn)入分區(qū)模式，限制某些操作山憨，并且
• 當(dāng)通信恢復(fù)后啟動分區(qū)恢復(fù)過程

最后一步的目的是恢復(fù)一致性，以及補(bǔ)償在系統(tǒng)分區(qū)期間程序產(chǎn)生的錯誤玛迄。

圖1可見分區(qū)的演變過程。普通的操作都是順序的原子操作蓖议，因此分區(qū)總是在兩筆操作之間開始讥蟆。一旦系統(tǒng)在操作間歇檢測到分區(qū)發(fā)生，檢測方一側(cè)即進(jìn)入分區(qū)模式从撼。如果確實(shí)發(fā)生了分區(qū)的情況钧栖，那么一般分區(qū)兩側(cè)都會進(jìn)入到分區(qū)模式低零，不過單方面完成分區(qū)也是可能的。單方面分區(qū)要求在對方按需要通信的時候掏婶，本方要么能正確響應(yīng)雄妥，要么不需要通信依溯；總之操作不得破壞一致性。但不管怎么樣枝秤，由于檢測方可能有不一致的操作慷嗜，它必須進(jìn)入分區(qū)模式庆械。采取了quorum決定機(jī)制的系統(tǒng)即為單方面分區(qū)的例子。其中一方擁有“法定通過節(jié)點(diǎn)數(shù)”沐序，因此可以執(zhí)行操作，而另一方不可以執(zhí)行操作邑时。支持離線操作的系統(tǒng)明顯地含有“分區(qū)模式”的概念，一些支持原子多播（atomic multicast）的系統(tǒng)也含有這個概念绰寞，如Java平臺的JGroups滤钱。

當(dāng)系統(tǒng)進(jìn)入到分區(qū)模式，它有兩種可行的策略铜靶。其一是限制部分操作争剿，因此會削弱可用性痊末。其二是額外記錄一些有利于后面分區(qū)恢復(fù)的操作信息。系統(tǒng)可通過持續(xù)嘗試恢復(fù)通信來察覺分區(qū)何時結(jié)束涩笤。

哪些操作可以執(zhí)行蹬碧？

決定限制哪些操作炒刁，主要取決于系統(tǒng)需要維持哪幾項(xiàng)不變性約束。在給定了不變性約束條件之后飒筑，設(shè)計師需要決定在分區(qū)模式下协屡，是否堅持不觸動某項(xiàng)不變性約束全谤，抑或以事后恢復(fù)為前提去冒險觸犯它。例如补憾，對于“表中鍵的惟一性”這項(xiàng)不變性約束盈匾，設(shè)計師一般都選擇在分區(qū)期間放寬要求，容許重復(fù)的鍵岩瘦。重復(fù)的鍵很容易在恢復(fù)階段檢查出來窿撬，假如重復(fù)鍵可以合并劈伴，那么設(shè)計師不難恢復(fù)這項(xiàng)不變性約束。

對于分區(qū)期間必須維持的不變性約束严里，設(shè)計師應(yīng)當(dāng)禁止或改動可能觸犯該不變性約束的操作田炭。（一般而言漓柑，我們沒辦法知道操作是否真的會破壞不變性約束辆布，因?yàn)闊o法知道分區(qū)另一側(cè)的狀態(tài)。）信用卡扣費(fèi)等具有外部化特征的事件常以這種方式工作景用。適合這種情況的策略惭蹂，是記錄下操作意圖盾碗，然后在分區(qū)恢復(fù)后再執(zhí)行操作。這類事務(wù)往往從屬于一些更大的工作流耗美，在工作流明確含有類似“訂單處理中”狀態(tài)的情況下商架，將操作推遲到分區(qū)結(jié)束并無明顯的壞處。設(shè)計師以用戶不易察覺的方式犧牲了可用性备图。用戶只知道自己下了指令赶袄，系統(tǒng)稍后會執(zhí)行弃鸦。

說得更概括一點(diǎn)幢痘，分區(qū)模式給用戶界面提出了一種根本性的挑戰(zhàn)颜说，即如何傳達(dá)“任務(wù)正在進(jìn)行尚未完成”的信息门粪。研究者已經(jīng)從離線操作的角度對此問題進(jìn)行了一些深入的探索玄妈，離線操作可以看成時間很長的一次分區(qū)。例如Bayou的日歷程序用顏色來區(qū)分顯示可能（暫時）不一致的條目¹³绎签。工作流應(yīng)用和帶離線模式的云服務(wù)中也常見類似的提醒诡必，前者的例子如交易中的電子郵件通知搔扁，后者的例子如Google Docs稿蹲。

在分區(qū)模式的討論中，我們將關(guān)注點(diǎn)放在有明確意義的原子操作而非單純的讀寫剖效，其中一個原因是操作的抽象級別越高璧尸，對不變性約束的影響通常就越容易分析清楚。大體來說垫竞，設(shè)計師要建立一張所有操作與所有不變性約束的叉乘表格（cross product）欢瞪，觀察并確定其中每一處操作可能與不變性約束相沖突的地方徐裸。對于這些沖突情況重贺，設(shè)計師必須決定是否禁止、推遲或修改相應(yīng)的操作次企。在實(shí)踐中缸棵，這類決定還受到分區(qū)前狀態(tài)和/或環(huán)境參數(shù)的影響谭期。例如有的系統(tǒng)為特定的數(shù)據(jù)設(shè)立了主節(jié)點(diǎn)隧出，那么一般允許主節(jié)點(diǎn)執(zhí)行操作鸳劳，不允許其他節(jié)點(diǎn)操作。

對分區(qū)兩側(cè)跟蹤操作歷史的最佳方式是使用版本向量涵紊，版本向量可以反映操作間的因果依賴關(guān)系幔摸。向量的元素是（節(jié)點(diǎn), 邏輯時間）數(shù)值對既忆，分別對應(yīng)一個更新了對象的節(jié)點(diǎn)和它最后更新的時間。對于同一對象的兩個給定的版本A和B跃脊，當(dāng)所有結(jié)點(diǎn)的版本向量一致有A的時間大于或等于B的時間酪术，且至少有一個節(jié)點(diǎn)的版本向量有A的時間較大，則A新于B橡疼。

如果不可能對版本向量排序欣除，那么更新操作是并發(fā)的挪略，而且有可能出現(xiàn)不一致的情況瘟檩。只要知道分區(qū)兩側(cè)版本向量的沿革墨辛。系統(tǒng)不難判斷哪些操作的執(zhí)行順序是確定的趴俘，哪些操作是并發(fā)的寥闪。最近的研究成果證明¹⁴，當(dāng)設(shè)計師選擇可用性優(yōu)先凿渊，一般最多只能將一致性收緊到這樣的程度埃脏。

分區(qū)恢復(fù)

到了某個時刻秋忙，通信恢復(fù)灰追，分區(qū)結(jié)束狗超。由于每一側(cè)在分區(qū)期間都是可用的努咐，其狀態(tài)仍繼續(xù)向前進(jìn)展麦撵，但是分區(qū)會推遲某些操作并侵犯一些不變性約束溃肪。分區(qū)結(jié)束的時刻惫撰，系統(tǒng)知道分區(qū)兩側(cè)的當(dāng)前狀態(tài)和歷史記錄，因?yàn)樗诜謪^(qū)模式下記錄了詳盡的日志扼雏。當(dāng)前狀態(tài)不如歷史記錄有價值诗充，因?yàn)橥ㄟ^歷史記錄诱建，系統(tǒng)可以判斷哪些操作違反了不變性約束俺猿，產(chǎn)生了何種外在的后果（如發(fā)送了響應(yīng)給用戶）押袍。在分區(qū)恢復(fù)過程中，設(shè)計師必須解決兩個問題：

• 分區(qū)兩側(cè)的狀態(tài)最終必須保持一致汽馋，
• 并且必須補(bǔ)償分區(qū)期間產(chǎn)生的錯誤豹芯。

通常情況告组，矯正當(dāng)前狀態(tài)最簡單的解決方法是回退到分區(qū)開始時的狀態(tài)癌佩，以特定方式推進(jìn)分區(qū)兩側(cè)的一系列操作，并在過程中一直保持一致的狀態(tài)放案。Bayou就是這個實(shí)現(xiàn)機(jī)制矫俺，它會回滾數(shù)據(jù)庫到正確的時刻并按無歧義的厘托、確定性的順序重新執(zhí)行所有的操作铅匹，最終使所有的節(jié)點(diǎn)達(dá)到相同的狀態(tài)¹⁵。同樣地流礁，并發(fā)版本控制系統(tǒng)CVS在合并分支的時候神帅，也是從從一個共享的狀態(tài)一致點(diǎn)開始萌抵，逐步將更新合并上去谜嫉。凹联。

大部分系統(tǒng)都存在不能自動合并的沖突蔽挠。比如澳淑，CVS時不時有些沖突需要手動介入杠巡，帶離線模式的wiki系統(tǒng)總是把沖突留在產(chǎn)生的文檔里給用戶處理¹⁶。

相反蚌铜，有些系統(tǒng)用了限制操作的辦法來保證沖突總能合并冬殃。一個例子就是Google Docs將其文本編輯操作¹⁷精簡為應(yīng)用樣式、添加文本和刪除文本深滚。因此痴荐，雖然總的來說沖突問題不可解蹬昌，但現(xiàn)實(shí)中設(shè)計師可以選擇在分區(qū)期間限制使用部分操作攀隔，以便系統(tǒng)在恢復(fù)的時候能夠自動合并狀態(tài)昆汹。如果要實(shí)施這種策略满粗，推遲有風(fēng)險的操作是相對簡單的實(shí)現(xiàn)方式。

還有一種辦法是讓操作可以交換順序挤聘，這種辦法最接近于形成一種解決自動狀態(tài)合并問題的通用框架组去。此類系統(tǒng)將線性合并各日志并重排操作的順序从隆，然后執(zhí)行缭裆。操作滿足交換率澈驼，意味著操作有可能重新排列成一種全局一致的最佳順序。不幸的是畅铭，只允許滿足交換率的操作這個想法實(shí)現(xiàn)起來沒那么容易勃蜘。比如加法操作可以交換順序缭贡，但是加入了越界檢查的加法就不行了阳惹。

Marc Shapiro及其INRIA同事最近的工作^18,19對于可交換順序的操作在狀態(tài)合并方面的應(yīng)用起了很大的促進(jìn)作用莹汤。該團(tuán)隊提出一種從理論上證明可以保證分區(qū)后合并的數(shù)據(jù)類型，稱為可交換多副本數(shù)據(jù)類型（commutative replicated data types抹竹，CRDTs）窃判。他們介紹了如何使用此類數(shù)據(jù)結(jié)構(gòu)來

• 保證分區(qū)期間進(jìn)行的所有操作都是可交換順序的袄琳，或者
• 用“格（lattice）”的數(shù)學(xué)概念來表示數(shù)據(jù)唆樊，并保證相對于“格”來說刻蟹，分區(qū)期間的所有操作都是單調(diào)遞增的座咆。

用后一種方法合并狀態(tài)會匯總分區(qū)兩邊的最大集合介陶。這種方法是對亞馬遜購物車合并算法²⁰的形式化總結(jié)和改良哺呜，合并后的數(shù)據(jù)是兩邊購物車的并集箕戳，而并運(yùn)算是一種單調(diào)的集合運(yùn)算。這種策略的壞處是刪掉的購物車商品有可能再次出現(xiàn)介牙。

其實(shí)CRDTs完全可以實(shí)現(xiàn)同時支持增澳厢、刪操作的分區(qū)耐受集合环础。此方法的本質(zhì)是維護(hù)兩個集合：一個放增加的項(xiàng)目，一個放刪除的項(xiàng)目剩拢，兩集合之差即為真正的集合成員线得。增集合、刪集合分別合并起來都不困難徐伐，因而增刪集合之差合并起來也不困難贯钩。在某個時間點(diǎn)上办素，系統(tǒng)可以從兩個集合中清理掉刪除的數(shù)據(jù)項(xiàng)角雷。假如按照一般的設(shè)計，像這種清理操作僅在系統(tǒng)沒分區(qū)的時候才可行性穿，屬于設(shè)計師必須在分區(qū)期間禁止或推遲的特定操作谓罗，但是CRDTs的清理操作并不會對可用性產(chǎn)生外在的影響。因此通過CRDTs來實(shí)現(xiàn)狀態(tài)季二，設(shè)計師既保證了可用性檩咱，又保證了分區(qū)后系統(tǒng)自動合并狀態(tài)。

補(bǔ)償錯誤

比計算分區(qū)后狀態(tài)更難解決的問題是如何彌補(bǔ)分區(qū)期間造成的錯誤胯舷。跟蹤和限制分區(qū)模式下的操作刻蚯，這兩種措施足以使設(shè)計師確知哪些不變性約束可能被違反，然后分別為它們制定恢復(fù)策略桑嘶。一般系統(tǒng)在分區(qū)恢復(fù)期間檢查違反情況炊汹，修復(fù)工作也必須在這段時間內(nèi)完成。

恢復(fù)不變性約束的方法有很多逃顶，粗陋一點(diǎn)的辦法如“最后寫入者勝”（因此會忽略部分更新）讨便，聰明一點(diǎn)的辦法如合并操作和人為跟進(jìn)事態(tài)（human escalation）。人為跟進(jìn)事態(tài)的例子如飛機(jī)航班“超售”的情形：可以把乘客登機(jī)看作是對之前售票情況的分區(qū)恢復(fù)以政，必須恢復(fù)“座位數(shù)不少于乘客數(shù)”這項(xiàng)不變性約束霸褒。那么當(dāng)乘客太多的時候，有些乘客將失去座位盈蛮，客服最好能設(shè)法補(bǔ)償他們废菱。

航班的例子揭示了一個外在錯誤（externalized mistake）：假如航空公司沒說過乘客一定有座位，這個問題會好解決得多。因此我們看到推遲有風(fēng)險的操作的又一個理由——到了分區(qū)恢復(fù)的時候殊轴，我們才知道真實(shí)的情況衰倦。矯正此類錯誤的核心概念是“補(bǔ)償（compensation）”；設(shè)計師必須設(shè)立補(bǔ)償操作旁理，除了恢復(fù)不變性約束樊零，還要糾正外在錯誤。

技術(shù)上CRDTs只允許局部可驗(yàn)證的不變性約束孽文，所以沒有補(bǔ)償?shù)谋匾そ螅m然這種限制降低了CRDTs方法本身的能力。用了CRDTs來處理狀態(tài)合并的設(shè)計方案可以允許暫時違反全局性的不變量約束叛溢，分區(qū)結(jié)束后才合并狀態(tài)塑悼，以及履行必要的補(bǔ)償。

恢復(fù)外在錯誤通常要求知道一些有關(guān)外在輸出的歷史信息楷掉。以“喝醉酒打電話”為例厢蒜，一位老兄不記得自己昨晚喝高了的時候打過幾個電話，雖然他第二天白天恢復(fù)了正常狀態(tài)烹植，但通話日志上的記錄都還在斑鸦，其中有些通話很可能是錯誤的。撥出的電話就是這位老兄的狀態(tài)（喝高了）的外在影響草雕。而由于這位老兄不記得打過什么電話巷屿，也就很難補(bǔ)償其中可能造成的麻煩。

又以機(jī)器為例墩虹，電腦可能在分區(qū)期間把一份訂單執(zhí)行了兩次嘱巾。如果系統(tǒng)能區(qū)分兩份一樣的訂單是有意的還是重復(fù)了，它就能取消掉一份重復(fù)的訂單诫钓。如果這次錯誤產(chǎn)生了外在影響旬昭，補(bǔ)償策略可以是自動生成一封電子郵件，向顧客解釋系統(tǒng)意外將訂單執(zhí)行了兩次菌湃，現(xiàn)在錯誤已經(jīng)被糾正问拘，附上一張優(yōu)惠券下次可以用。假如沒有完善的歷史記錄惧所，就只好靠顧客親自去發(fā)現(xiàn)錯誤了骤坐。

曾經(jīng)有人正式研究過將補(bǔ)償性事務(wù)作為處理長壽命事務(wù)（long-lived transactions）的一種手段^21,22。長時間運(yùn)行的事務(wù)會面臨另一種形態(tài)的分區(qū)決策：是長時間持有鎖來保證一致性比較好呢下愈？還是及早釋放鎖向其他事務(wù)暴露未提交的數(shù)據(jù)纽绍，提高并發(fā)能力比較好呢？比如在單筆事務(wù)中更新所有的員工記錄就是一個典型例子驰唬。按照一般的方式串行化這筆事務(wù)顶岸，將導(dǎo)致所有的記錄都被鎖定腔彰，阻止并發(fā)叫编。而補(bǔ)償性事務(wù)采取另一種方式辖佣，它將大事務(wù)拆成多個分別提交的子事務(wù)。如果要中止大事務(wù)搓逾，系統(tǒng)必須發(fā)起一筆新的卷谈、起糾正作用的事務(wù)，逐一撤銷所有已經(jīng)提交的子事務(wù)霞篡，這筆新事務(wù)就是所謂的補(bǔ)償性事務(wù)世蔗。

總的來說，補(bǔ)償性事務(wù)的目的是避免中止其他用了未正確提交數(shù)據(jù)的事務(wù)（即不允許級聯(lián)取消）朗兵。這種方案不依賴串行化或隔離的手段來保障正確性污淋，其正確性取決于事務(wù)序列對狀態(tài)和輸出所產(chǎn)生的凈影響。那么余掖，經(jīng)過補(bǔ)償寸爆，數(shù)據(jù)庫的狀態(tài)究竟是不是相當(dāng)于那些子事務(wù)根本沒執(zhí)行過一樣呢？考慮等價必須連外在行為也包括在內(nèi)盐欺；舉個例子赁豆，把重復(fù)扣取的交易款退還給顧客，很難說成等于一開始就沒多收顧客的錢冗美，但從結(jié)果上看勉強(qiáng)算扯平了魔种。分區(qū)恢復(fù)也延續(xù)同樣的思路。雖然服務(wù)不一定總能直接撤銷其錯誤粉洼，但起碼承認(rèn)錯誤并做出新的補(bǔ)償行為节预。怎樣在分區(qū)恢復(fù)中運(yùn)用這種思路效果最好，這個問題沒有固定的答案属韧“材猓“自動柜員機(jī)上的補(bǔ)償問題”小節(jié)以一個很小的應(yīng)用領(lǐng)域?yàn)槔c(diǎn)出了一些思考方向。

當(dāng)系統(tǒng)中存在分區(qū)挫剑，系統(tǒng)設(shè)計師不應(yīng)該盲目地犧牲一致性或可用性去扣。運(yùn)用以上討論的方法，設(shè)計師通過細(xì)致地管理分區(qū)期間的不變性約束樊破，兩方面的性質(zhì)都可以取得最佳的表現(xiàn)愉棱。隨著版本向量和CRDTs等比較新的技術(shù)逐漸被納入一些簡化其用法的框架，這方面的優(yōu)化手段會得到比較普遍的應(yīng)用。但引入CAP實(shí)踐畢竟不像引入ACID事務(wù)那么簡單森逮，實(shí)施的時候需要對過去的策略進(jìn)行全面的考慮耘斩，最佳的實(shí)施方案極大地依賴于具體服務(wù)的不變性約束和操作細(xì)節(jié)。

自動柜員機(jī)上的補(bǔ)償問題

以自動柜員機(jī)（ATM）的設(shè)計來說朋其，強(qiáng)一致性看似符合邏輯的選擇王浴，但現(xiàn)實(shí)情況是可用性遠(yuǎn)比一致性重要。理由很簡單：高可用性意味著高收入梅猿。不管怎么樣氓辣，討論如何補(bǔ)償分區(qū)期間被破壞的不變性約束，ATM的設(shè)計很適合作為例子袱蚓。

ATM的基本操作是存款钞啸、取款、查看余額喇潘。關(guān)鍵的不變性約束是余額應(yīng)大于或等于零体斩。因?yàn)橹挥腥】畈僮鲿|犯這項(xiàng)不變性約束，也就只有取款操作將受到特別對待颖低，其他兩種操作隨時都可以執(zhí)行絮吵。

ATM系統(tǒng)設(shè)計師可以選擇在分區(qū)期間禁止取款操作，因?yàn)樵谀嵌螘r間里沒辦法知道真實(shí)的余額忱屑，當(dāng)然這樣會損害可用性〉徘茫現(xiàn)代ATM的做法正相反，在stand-in模式下（即分區(qū)模式）想幻，ATM限制凈取款額不得高于k粱栖，比如k為$200。低于限額的時候脏毯，取款完全正常闹究；當(dāng)超過限額的時候，系統(tǒng)拒絕取款操作食店。這樣渣淤，ATM成功將可用性限制在一個合理的水平上，既允許取款操作吉嫩，又限制了風(fēng)險价认。

分區(qū)結(jié)束的時候，必須有一些措施來恢復(fù)一致性和補(bǔ)償分區(qū)期間系統(tǒng)所造成的錯誤自娩。狀態(tài)的恢復(fù)比較簡單用踩，因?yàn)椴僮鞫际欠辖粨Q率的，補(bǔ)償就要分幾種情況去考慮忙迁。最后的余額低于零違反了不變性約束脐彩。由于ATM已經(jīng)把錢吐出去了，錯誤成了外部實(shí)在姊扔。銀行的補(bǔ)償辦法是收取透支費(fèi)并指望顧客償還惠奸。因?yàn)轱L(fēng)險已經(jīng)受到限制，問題并不嚴(yán)重恰梢。還有一種情況是分區(qū)期間的某一刻余額已經(jīng)小于零（但ATM不知道）佛南，此時一筆存款重新將余額變?yōu)檎墓ｊｃy行可以追溯產(chǎn)生透支費(fèi)，也可以因?yàn)轭櫩鸵呀?jīng)繳付而忽略該違反情況嗅回。

總而言之及穗，因?yàn)橥ㄐ叛舆t的存在，銀行系統(tǒng)不依靠一致性來保證正確性妈拌，而更多地依靠審計和補(bǔ)償拥坛∨畹“空頭支票詐騙”也是類似的例子尘分，顧客趕在多家分行對賬之前分別取出錢來然后逃跑。透支的錯誤過后才會被發(fā)現(xiàn)丸氛，對錯誤的補(bǔ)償也許體現(xiàn)為法律行動的形式培愁。

致謝

感謝Mike Dahlin、Hank Korth缓窜、Marc Shapiro定续、Justin Sheehy、Amin Vahdat禾锤、Ben Zhao以及IEEE Computer Society的志愿者們私股，感謝他們對本文的有益反饋。

作者簡介

Eric Brewer是University of California, Berkeley的計算機(jī)科學(xué)教授恩掷，在Google擔(dān)任基礎(chǔ)設(shè)施方面的VP倡鲸。他的研究興趣包括云計算、可伸縮的服務(wù)器黄娘、傳感器網(wǎng)絡(luò)峭状，還有適合發(fā)展中地區(qū)應(yīng)用的技術(shù)。他還幫助建立了美國聯(lián)邦政府的門戶網(wǎng)站USA.gov逼争。Brewer從MIT獲得電子工程和計算機(jī)科學(xué)的博士學(xué)位优床。他是National Academy of Engineering的院士。聯(lián)系方式：brewer@cs.berkeley.edu

參考文獻(xiàn)

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

原文鏈接

CAP Twelve Years Later: How the "Rules" Have Changed
CAP理論十二年回顧："規(guī)則"變了