佳文分享: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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 配置猫抓,抓取网页视频
- 下一篇: 基础的数组/链表实现的队列