佳文分享：CAP定理
1976年6月4號，周5，在遠(yuǎn)離音樂會(huì)大廳的一個(gè)樓上的房間內(nèi)，在位于Manchester的Lesser Free Trade Hall ，Sex Pistols 樂隊(duì)（注：Sex Pistols的經(jīng)理人Malcolm McLaren 2010.4.8去世）開始了他們的第一次演出（gig， 注：規(guī)模太小稱不上演唱會(huì) ）。關(guān)于當(dāng)晚誰出席了那場演出有些混亂，部分是由于6周后的還有一場音樂會(huì)，但最基本的還是由于，這場演出被覺得是永久改變西方音樂文化 的一場演出。這場演出是如此的重要且富有象征意義，以至于David Nolan寫了一本書：《我發(fā)誓我在那里：那場改變了世界的演出 》，對那些聲稱自己看過那場演出的人做出推斷。由于6月4號被覺得是punk搖滾的開始。
在這之前（大約是在1971年左右）曾有一些protopunk 樂隊(duì)，比如New York Dolls 和Velet Underground ，但從音樂民俗學(xué)來說，是Sex Pistals開啟了這場革命，在這場運(yùn)動(dòng)中驅(qū)動(dòng)了Buzzcocks 樂隊(duì)的吉他，The Smiths 樂隊(duì)哀怨的哭訴，The Fall 樂隊(duì)的電子切音，Joy Division 和Simply Red 樂隊(duì)華麗的升調(diào)（我猜你不了解全部的含義）（注：我缺乏搖滾方面的知識(shí)，這部分翻的不是非常愜意，好在不影響大局，有punk搖滾知識(shí)的同學(xué)能夠提供幫助 ）
2000年7月19號，周三，對主流文化來說并不（象前者一樣）具有相同的重要性，但這個(gè)日子對互聯(lián)網(wǎng)公司來說，和25年Sex Pistols對音樂所做的一樣，具有相同的影響。這就是Eric Brewer 在ACM研討會(huì)上關(guān)于分布式計(jì)算的原則 （Principles of Distributed Computing）所做的開題演講 （keynote speech）。
Sex Pistols向同一時(shí)候代的人展示了差點(diǎn)兒無限制的狂躁遠(yuǎn)比學(xué)院派的結(jié)構(gòu)主義重要的多，給不論什么人3根弦以及一些許可就能夠組建一支樂隊(duì)。Eric Brewer，在那時(shí)被稱為Brewer猜想，覺得當(dāng)應(yīng)用系統(tǒng)變得越來越web化，應(yīng)當(dāng)放棄對數(shù)據(jù)一致性（data consistency）的擔(dān)憂，由于要想獲得這樣的新的分布式系統(tǒng)的高可用性（high availability），確保數(shù)據(jù)一致性是我們無法做到的，這樣給予不論什么人3臺(tái)server和一雙關(guān)注客戶體驗(yàn)的眼睛就能夠建立一家互聯(lián)網(wǎng)公司。Brewer的信徒（當(dāng)天就有的和后來皈依的）包含像Amazon , EBay 和Twitter 這類公司
2年后，2002年，麻省理工（MIT）的Seth Gilbert 和Nancy Lynch ，理論上證明 了Brewer猜想是正確的，就此Brewer定理（Theorem）誕生了。
Brewer（CAP）定理
那么究竟Brewer的定理是什么，為何它足以和1976年Manchester的punk演出媲美？
Brewer 在2000年的演講是基于他在UC Berkley的理論工作以及主持Inktomi （期間）的觀察，是通過數(shù)年前Brewer和其它人，在怎樣構(gòu)建高伸縮性系統(tǒng)（highly scalable system）時(shí)所做出的各種折衷方案的討論（比如：SOSP（Symposium on Operating System Principles）的1997年的Cluster-Based Scalable Network Service 和1999年的Harvest, yield, and scalable tolerant system ）就像其它的很多思想，因此這個(gè)演講的內(nèi)容并非全新的，它是很多聰明人的共同成果（我確信Brewer會(huì)非常快說明這一點(diǎn)）。
Brewer覺得在分布式的環(huán)境下設(shè)計(jì)和部署系統(tǒng)時(shí)，有3個(gè)核心的系統(tǒng)需求 （systemic requirements），以一種特殊的關(guān)系存在。（他主要是談?wù)揥eb類的應(yīng)用，但現(xiàn)在許多的公司業(yè)務(wù)是多網(wǎng)站／多國家的，因此該理論相同適用于你的數(shù)據(jù)中心/LAN/WAN的設(shè)計(jì)）
這3個(gè)核心的需求是：Consistency ，Availability 和Partition Tolerance ，賦予了該理論另外一個(gè)名字 － CAP 。
要想將該理論和現(xiàn)實(shí)的聯(lián)系起來，讓我們舉一個(gè)簡單的樣例：你想購買一套托爾斯泰 的《戰(zhàn)爭與和平 》，以便在明天開始的長假中有可讀的東西。然而你最喜歡的網(wǎng)上書店僅僅有一本庫存了。你進(jìn)行搜索，確認(rèn)書能夠在你出發(fā)前送到，然后將書增加你的購物車。接著你想起來另一些其它的東西要買，所以繼續(xù)瀏覽站點(diǎn)（你是否在站點(diǎn)僅僅買一件東西？當(dāng)然要充分利用包裹的費(fèi)用了）。但當(dāng)你查看某個(gè)防曬霜的客戶反饋時(shí)，國內(nèi)某個(gè)地方的某個(gè)人，進(jìn)入站點(diǎn)，將那本書增加到自己的購物車，然后直接付款（他們急需解決桌子搖晃的問題，當(dāng)中一條桌腳比其它的短的多）。
- Consistency
一個(gè)服務(wù)是一致的完整操作或全然不操作（A service that is consistent operates fully or not at all，精確起見列出原文，也有人將其簡稱為數(shù)據(jù)一致性）。Gilbert 和Lynch在他們的證明中使用“atomic”而不是consistent，技術(shù)上來講更準(zhǔn)確，由于嚴(yán)格來說，當(dāng)用在數(shù)據(jù)庫事務(wù)的屬性中時(shí)，consistent是指ACID 中的C，其含義是假設(shè)數(shù)據(jù)違反了某些預(yù)設(shè)的約束（preset constraints）就不能被持久化（persisted）。但假設(shè)你將其覺得是分布式系統(tǒng)中的一個(gè)預(yù)設(shè)約束：不同意同一數(shù)據(jù)有不同的值，那么我覺得這個(gè)抽象概念的漏洞就被堵住了（而且，假設(shè)Brewer使用atomic這個(gè)詞，就會(huì)被稱為AAP定理，那每次我們讀它的時(shí)候都會(huì)被送進(jìn)醫(yī)院）（注：我預(yù)計(jì)是有口吃加白癡的嫌疑）。在前面購書的樣例中，你將書增加購物車或無法增加。支付成功或不成功。你無法部分增加或部分支付一本書。庫存中僅僅有一本書，當(dāng)天僅僅有一個(gè)人能得到它。假設(shè)2個(gè)客戶都能夠完畢訂單流程（如完畢支付），那么倉庫中的和系統(tǒng)中的不一致性就會(huì)導(dǎo)致問題。在這個(gè)樣例中或許并非個(gè)大問題：某個(gè)人在假期中會(huì)非常無聊或擺弄防曬霜，但假設(shè)將其擴(kuò)大到數(shù)千個(gè)不一致性，而且涉及到金錢（比如：金融交易中關(guān)于買賣的東西和交易記錄的內(nèi)容不一致）就會(huì)是個(gè)大問題。或許我們能夠利用數(shù)據(jù)庫來解決一致性問題。在（購書的）訂單流程中的某個(gè)點(diǎn)降低《戰(zhàn)爭與和平》的庫存記錄。當(dāng)其它的客戶到達(dá)這個(gè)點(diǎn)的時(shí)候，書架空了，訂單流程將會(huì)通知客戶，而不會(huì)進(jìn)行到支付環(huán)節(jié)。這樣第一個(gè)操作順利完畢，第二個(gè)操作則不會(huì)完畢。數(shù)據(jù)庫非常適合這樣的情況，由于數(shù)據(jù)庫關(guān)注ACID屬性，而且通過隔離性（Isolation）來保證一致性，這樣當(dāng)?shù)谝粋€(gè)客戶會(huì)使得庫存記錄減1，同一時(shí)候購物車的記錄加1，不論什么中間狀態(tài)同第二個(gè)客戶都是隔離的，當(dāng)然第二個(gè)客戶必須等待幾百毫秒以便數(shù)據(jù)存儲(chǔ)達(dá)到一致狀態(tài)。
- Availability
可用性僅僅是意味著服務(wù)是可用的（能夠完畢如上的操作或不完畢）。當(dāng)你購書時(shí)期望得到反饋，而不是瀏覽器報(bào)告站點(diǎn)無法連接的信息。Gilbert 和Lynch在其CAP定理的證明中非常好地指出了，可用性通常在你最須要的時(shí)刻背棄你。站點(diǎn)通常在業(yè)務(wù)最繁忙的時(shí)刻掛掉，由于站點(diǎn)壓力最大。一個(gè)他人無法訪問的服務(wù)對不論什么人都沒有價(jià)值。??
- Partition Tolerance
假設(shè)你的應(yīng)用和數(shù)據(jù)庫執(zhí)行在一個(gè)機(jī)器上（忽略規(guī)模的問題并假定你的代碼都沒問題），你的server是作為一種原子處理單元（atomic processor）：要么工作要么不工作（比如：假設(shè)down機(jī)就不可用，但也不會(huì)造成數(shù)據(jù)不一致問題）
一旦開始將數(shù)據(jù)和邏輯分布在不同的節(jié)點(diǎn)上，就有形成partition的風(fēng)險(xiǎn)。假定網(wǎng)線被切斷，partition就形成了，節(jié)點(diǎn)A無法和節(jié)點(diǎn)B通訊。因?yàn)閃eb提供的這樣的分布式能力，暫時(shí)的partition是一個(gè)常見的情況，如之前說所的，在全球化的有多個(gè)數(shù)據(jù)中心的公司中這并不罕見。
Gilbert 和Lynch是這樣定義partition tolerance的
除了整個(gè)網(wǎng)絡(luò)的故障外，其它的故障（集）都不能導(dǎo)致整個(gè)系統(tǒng)無法正確響應(yīng)。(No set of failures less than total network failure is allowed to cause the system to respond incorrectly)
請注意Brewer的凝視，單節(jié)點(diǎn)partition就等同于servercrash，由于假設(shè)無法連接它，那它就和不存在一樣。
定理的重要性
CAP定理在應(yīng)用系統(tǒng)規(guī)模化時(shí)最有效。在低壓力的情況下，小的延遲（以便數(shù)據(jù)庫達(dá)到一致的狀態(tài)）還不足以對整體的性能或用戶體驗(yàn)造成影響。你所承擔(dān)的負(fù)載分布，可能都是出于系統(tǒng)管理的原因。？
但隨著活動(dòng)的添加，吞吐量的上限（pinch-points）將會(huì)限制增長并產(chǎn)生錯(cuò)誤。必須等待網(wǎng)頁的返回是一種情況，還有一種情況則是在你輸入信用卡信息后遇到 “HTTP 500 java.lang.schrodinger.purchasingerror”，你就想知道你是否付了錢但無法得到東西，還是沒付錢，或者這僅僅是交易中一個(gè)不重要的錯(cuò)誤。誰知道呢？你不太可能繼續(xù)下去，非常有可能到別的地方購物，或更有可能給銀行打電話。
無論是那種情況對業(yè)務(wù)都沒有優(yōu)點(diǎn)。Amazon聲稱 每0.1秒的響應(yīng)延遲都會(huì)導(dǎo)致1％的銷售減少。Google說 他們注意到0.5秒的延遲會(huì)使流量降低15%。
我之前 曾就scalability寫過一些東西，不想在這里反復(fù)，僅僅想指出2點(diǎn)：第一點(diǎn)是，解決scale問題看起來是一個(gè)架構(gòu)方面的問題，但最初的討論卻不是，而是業(yè)務(wù)決策。我已經(jīng)非常厭倦聽到技術(shù)人員說，由于當(dāng)前的流量，這樣或那樣的方案不能用。并非說技術(shù)人員錯(cuò)了，通常他們講的非常正確，是由于從一開始所限定的scale 隱含地做了revenue決策－這一問題應(yīng)該在業(yè)務(wù)分析時(shí)明白地決定下來。
第二點(diǎn)是，一旦你開始討論怎樣scale業(yè)務(wù)系統(tǒng)，大致會(huì)落到2種意識(shí)形態(tài)陣營中：數(shù)據(jù)庫派和非數(shù)據(jù)庫派。
對于數(shù)據(jù)庫派來說，毫無疑問，鐘愛數(shù)據(jù)庫技術(shù)，并傾向于談?wù)搊ptimistic locking 和sharding 這類的東西來解決scale問題，并將數(shù)據(jù)庫作為系統(tǒng)的核心。
非數(shù)據(jù)庫派會(huì)傾向于盡可能多的在數(shù)據(jù)庫環(huán)境（避免關(guān)系世界）之外管理數(shù)據(jù)以解決scale問題。
我覺得，能夠公平地說，前一派人對CAP定理的熱情肯定不如后一派（雖然他們在討論定理 ）。這是由于，假設(shè)你必須在consistency，availability，partition tolerance三者中放棄一個(gè)，大多數(shù)會(huì)選擇放棄consistency，而consistency是數(shù)據(jù)庫存在的理由。（選擇的）邏輯，無疑，是availability和partition tolerance可以使你賴以賺錢的系統(tǒng)生存下去，而不一致性感覺好像是你可以用好的設(shè)計(jì)來解決的問題。
和IT中的其它事情一樣，這不是非黑即白的問題。Eric Brewer在其PODC演講的第13頁slide中，當(dāng)比較ACID和其非正式的相應(yīng)物的BASE 時(shí)，甚至說“我覺得這是一個(gè)系列（spectrum）”（注：這里光譜有一個(gè)系列的含義，是指ACID和BASE是不正確立的）。假設(shè)你對這個(gè)主題感興趣（有些超出我在這里討論的范圍了），你能夠從一篇叫做，“Design and Evaluation of a Continuous Consistency Model for Replicated Service ”的論文開始，該文由Haifeng Yu和Amin Vahdat 編寫。大家不能夠?qū)AP解讀為暗示數(shù)據(jù)庫的消亡。
雖然這樣，兩方都認(rèn)同scale的解決之道是分布式的并行計(jì)算，而不是以前覺得的超級計(jì)算機(jī)。90年代中期進(jìn)行的Network of Workstations 項(xiàng)目受到了Eric Brewer的影響，并終于導(dǎo)致了CAP定理的誕生，由于他在一個(gè)關(guān)于Inktomi and the Internet Bubble 的介紹中說到，答案總是并行處理：
?
假設(shè)不通過并行的方式，你就沒有機(jī)會(huì)，在合適的時(shí)間內(nèi)解決這個(gè)問題。和其它很多事情一樣。假設(shè)是個(gè)非常大的項(xiàng)目，會(huì)須要非常多人來完畢它。因此，假設(shè)想建造一個(gè)橋梁，就須要非常多建筑工人。這就是并行處理。因此問題會(huì)演變?yōu)椤霸鯓訉⒉⑿刑幚砗蚷nternet結(jié)合在一起”
圖片證明
這里有一個(gè)簡單的圖片證明，由于我發(fā)現(xiàn)用圖片會(huì)比較好理解。多數(shù)情況下我使用和Gilber 和Lynch同樣的術(shù)語，以便和他們的論文聯(lián)系起來。
?
上圖顯示了網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)N1，N2。他們共享同一數(shù)據(jù)V（庫存中《戰(zhàn)爭與和平》的數(shù)量），其值為V0。N1上有一個(gè)算法A，我們能夠覺得A是安全，無bug，可預(yù)測和可靠的。N2上有一個(gè)相似的算法B。在這個(gè)樣例中，A寫入V的新值而B讀取V的值。
?
正常情況下（sunny-day scenario），步驟例如以下：(1)A寫入新的V值，我們稱作v1。(2)N1發(fā)送信息給N2，更新V的值。(3)如今B讀取的V值將會(huì)是V1。
假設(shè)網(wǎng)絡(luò)斷開（partions）（意味著從N1無法發(fā)送信息到N2）那么在第3步的時(shí)候，N2就會(huì)包括一個(gè)步一致的V值。
希望看上去非常明確。即使將其scale到幾百個(gè)事務(wù)（transaction）中，這也會(huì)成為一個(gè)大問題。假設(shè)M是一個(gè)異步消息，那么N1無法知道N2是否收到了消息。即使M是保證能發(fā)送的（guaranteed delivery），N1也無法知道是否消息由于partition事件的發(fā)生而延遲，或N2上的其它故障而延遲。即使將M作為同步（synchronous）信息也不能解決這個(gè)問題，由于那將會(huì)使得N1上A的寫操作和N1到N2的更新事件成為一個(gè)原子操作（atomic operation），而這將導(dǎo)致相同的等待問題，該問題我們已經(jīng)討論過（或更糟）。Gilbert 和Lynch已經(jīng)證明，使用其它的變種方式，即使是部分同步模型（每一個(gè)節(jié)點(diǎn)上使用安排好的時(shí)鐘）也無法保證原子性（atomicity）。
因此，CAP告訴我們，假設(shè)想讓A和B是高可用（highly available）的（比如，以最小的延遲（latency）提供服務(wù)）而且想讓全部的N1到Nn（n的值可以是數(shù)百甚至是上千）的節(jié)點(diǎn)可以冗余網(wǎng)絡(luò)的partitions（丟失信息，無法傳遞信息，硬件無法提供服務(wù)，處理失敗），那么有時(shí)我們就得面臨這種情況：某些節(jié)點(diǎn)覺得V的值是V0（一本《戰(zhàn)爭與和平》的庫存）而其它節(jié)點(diǎn)會(huì)覺得V的值是V1（《戰(zhàn)爭與和平》的庫存為0）
我們都希望全部的事情是結(jié)構(gòu)化的，一致的且和諧的，就像70年代早期的prog rock 樂隊(duì)，但我們面臨的是一些punk風(fēng)格的混亂。其實(shí)，雖然有可能會(huì)嚇到我們的祖母，但一旦你了解了它就還OK，由于2者能夠很愉快地在一起工作。
讓我們從事務(wù)（transactional）的角度高速分析一下。
?
假設(shè)我們有個(gè)事務(wù)（比如：一組環(huán)繞著persistent數(shù)據(jù)項(xiàng)V的工作單元）a，a1是寫操作，a2是讀操作。在一個(gè)local的系統(tǒng)中，能夠利用數(shù)據(jù)庫中的簡單鎖（simple locking）的機(jī)制方便地處理，隔離（isolating）a2中的讀操作，直到a1的寫成功完畢。然而，在分布式的模型中，須要考慮到N1和N2節(jié)點(diǎn)，中間的消息同步也要完畢才行。除非我們能夠控制a2何時(shí)發(fā)生，我們永遠(yuǎn)無法保證a2能夠讀到a1寫入的數(shù)據(jù)。全部增加控制的方法（堵塞，隔離，中央化的管理，等等）會(huì)要么影響partition tolerance，要么影響a1(A)和a2(B)的可用性。
CAP選擇
當(dāng)處理CAP的問題時(shí)，你會(huì)有幾個(gè)選擇。最明顯的是：
有一種架構(gòu)的方法（approach）稱作BASE（B asically A vailable, S oft-state, E ventually consistent）支持終于一致概念的接受。BASE（注：化學(xué)中的含義是堿），如其名字所看到的，是ACID（注：化學(xué)中的含義是酸）的反面，但假設(shè)覺得不論什么架構(gòu)應(yīng)該全然基于一種（BASE）或全然基于還有一種（ACID），就大錯(cuò)特錯(cuò)了。這一點(diǎn)是須要謹(jǐn)記重點(diǎn)，尤其是這個(gè)行業(yè)的“一邊倒（oooh shiny，注：這個(gè)全然意譯了）”的習(xí)慣性的採用策略。這里，我要遵從Brewer教授自己的觀點(diǎn)，他就本文通過email表達(dá)了自己的觀點(diǎn)（comment）：
如您所指出的，術(shù)語BASE第一次出現(xiàn)是在1997年的SOSP文章中。那一年，我和我的學(xué)生在他們的辦公室中，一起造了這個(gè)詞。我承認(rèn)這有些人為的因素，但ACID也是一樣的－－遠(yuǎn)超人們所能意識(shí)到的，所以我們?nèi)藶檫€行。Jim Gray和我討論了這些縮寫，他欣然認(rèn)可ACID也有些扭曲（stretch）– A和D（的概念）有相當(dāng)多的反復(fù)部分，C至多也是含糊不清的。但這對術(shù)語暗示了一系列的理念（idea of spectrum），這是PODC演講中的一個(gè)重要觀點(diǎn)，你正確地指出了這一點(diǎn)。
EBay的Dan Pritchett有一篇關(guān)于BASE的非常棒的介紹 （presentation）。
Guy Pardon， atomikos 的CTO寫了一篇他稱作“CAP解決之道（證實(shí)Brewer的錯(cuò)誤） ”的文章，提出了一種架構(gòu)方法，能夠達(dá)到Consistency, Availability和Partition-tolerance，當(dāng)然附帶了一些說明（顯然你不可能在同一時(shí)刻滿足所有的3個(gè)要求）。值得一讀，Guy雄辯地表達(dá)了（在該領(lǐng)域）相反的觀點(diǎn)。
總結(jié)
在Consistency, Availability和Partition-tolerance中，你僅僅能保證2點(diǎn)，這是確實(shí)的，而且已經(jīng)被這個(gè)星球上最成功的站點(diǎn)證實(shí)了。假設(shè)對站點(diǎn)是有效的，我看不出在企業(yè)環(huán)境中，在日常的工作中，不考慮相同的折衷設(shè)計(jì)的理由。假設(shè)業(yè)務(wù)方面明白表明不須要上規(guī)模（scale）那好，有簡單的解決方式，但這是值得討論的。在不論什么情況下，這些討論都是針對特定操作的適合的設(shè)計(jì)，而不是廬山（注：shebang取意譯）全貌。正如Brewer在其郵件中所說的：“唯一的我能夠增加的是同一服務(wù)的不同部分能夠選擇這一系列（spectrum）中的不同的點(diǎn)”有時(shí)，不管scale的代價(jià)怎樣，你絕對須要一致性 ，由于缺少它的風(fēng)險(xiǎn)太大了。
這些天，我說得有些過，說Amazon和EBay沒有scalability問題，我覺得他們的確有這類問題，但他們?nèi)缃裼修k法解決該問題。這也是為何他們能夠自由討論這些問題的解決辦法。不論他們?nèi)缃袷呛我?guī)模（結(jié)合他們早就發(fā)布的數(shù)字）僅僅會(huì)越來越大。一旦規(guī)模上來，你的問題就會(huì)轉(zhuǎn)到（shift）諸如操作維護(hù)，監(jiān)控，發(fā)布軟件的更新等等 － 當(dāng)然（這些問題）都非常難解決，但值得，尤其當(dāng)你因此獲得現(xiàn)金流（revenue stream）。
參考
轉(zhuǎn)載于:https://www.cnblogs.com/gcczhongduan/p/4085309.html
總結(jié)
以上是生活随笔為你收集整理的佳文分享：CAP定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 配置猫抓，抓取网页视频
- 下一篇： 基础的数组/链表实现的队列