1.CAP的歷史
1985年Lynch證明了異步通信中不存在任何一致性的分布式算法（FLP Impossibility）的同時(shí)，人們就開(kāi)始尋找分布式系統(tǒng)設(shè)計(jì)的各種因素。一致性算法既然不存在，但若能找到一些設(shè)計(jì)因素，并進(jìn)行適當(dāng)?shù)娜∩嵋宰畲笙薅葷M足實(shí)現(xiàn)系統(tǒng)需求成為當(dāng)時(shí)的重要議題。比如，在CAP之前研究者就已經(jīng)發(fā)現(xiàn)低延遲和順序一致性不可能同時(shí)被滿足。
2000年，Eric Brewer教授在PODC的研討會(huì)上提出了一個(gè)猜想：一致性、可用性和分區(qū)容錯(cuò)性三者無(wú)法在分布式系統(tǒng)中被同時(shí)滿足，并且最多只能滿足其中兩個(gè)！
這個(gè)猜想首次把一致性、可用性和分區(qū)容錯(cuò)三個(gè)因素提煉出來(lái)作為系統(tǒng)設(shè)計(jì)的重要特征，斷言用此三者可以劃分所有的分布式系統(tǒng)，并指明這三個(gè)特征之間的不可能性關(guān)系。Brewer猜想比單純的“低延遲和順序一致性不能被同時(shí)滿足”的結(jié)論更具體，對(duì)實(shí)際系統(tǒng)的構(gòu)建也更具有可操作性！
Brewer教授當(dāng)時(shí)想象的分布式場(chǎng)景是webservice，一組websevrice后臺(tái)運(yùn)行著眾多的server，對(duì)service的讀寫(xiě)會(huì)反應(yīng)到后臺(tái)的server集群，并對(duì)CAP進(jìn)行了定義：
C（一致性）：所有的節(jié)點(diǎn)上的數(shù)據(jù)時(shí)刻保持同步
A（可用性）：每個(gè)請(qǐng)求都能接受到一個(gè)響應(yīng)，無(wú)論響應(yīng)成功或失敗
P（分區(qū)容錯(cuò)）：系統(tǒng)應(yīng)該能持續(xù)提供服務(wù)，即使系統(tǒng)內(nèi)部有消息丟失（分區(qū)）
高可用、數(shù)據(jù)一致是很多系統(tǒng)設(shè)計(jì)的目標(biāo)，但是分區(qū)又是不可避免的事情：
CA without P：如果不要求P（不允許分區(qū)），則C（強(qiáng)一致性）和A（可用性）是可以保證的。 但其實(shí)分區(qū)不是你想不想的問(wèn)題，而是始終會(huì)存在，因此CA的系統(tǒng)更多的是允許分區(qū)后各子系統(tǒng)依然保持CA。
CP without A：如果不要求A（可用），相當(dāng)于每個(gè)請(qǐng)求都需要在Server之間強(qiáng)一致，而P（分區(qū)）會(huì)導(dǎo)致同步時(shí)間無(wú)限延長(zhǎng)，如此CP也是可以保證的。很多傳統(tǒng)的數(shù)據(jù)庫(kù)分布式事務(wù)都屬于這種模式。
AP wihtout C：要高可用并允許分區(qū)，則需放棄一致性。一旦分區(qū)發(fā)生，節(jié)點(diǎn)之間可能會(huì)失去聯(lián)系，為了高可用，每個(gè)節(jié)點(diǎn)只能用本地?cái)?shù)據(jù)提供服務(wù)，而這樣會(huì)導(dǎo)致全局?jǐn)?shù)據(jù)的不一致性。現(xiàn)在眾多的NoSQL都屬于此類。
CAP的出現(xiàn)仿佛是一盞明燈，它揭露了分布式系統(tǒng)的本質(zhì)，并給出了設(shè)計(jì)的準(zhǔn)則，而這正是1985年以來(lái)人們正在尋找的東西！所以CAP在當(dāng)時(shí)的影響力是非常大的！
- CAP被上升為定理
2002年，Lynch與其他人證明了Brewer猜想，從而把CAP上升為一個(gè)定理。但是，她只是證明了CAP三者不可能同時(shí)滿足，并沒(méi)有證明任意二者都可滿足的問(wèn)題，所以，該證明被認(rèn)為是一個(gè)收窄的結(jié)果。
Lynch的證明相對(duì)比較簡(jiǎn)單：采用反正法，如果三者可同時(shí)滿足，則因?yàn)樵试SP的存在，一定存在Server之間的丟包，如此則不能保證C，證明簡(jiǎn)潔而嚴(yán)謹(jǐn)。
在該證明中，對(duì)CAP的定義進(jìn)行了更明確的聲明：
C：一致性被稱為原子對(duì)象，任何的讀寫(xiě)都應(yīng)該看起來(lái)是“原子“的，或串行的。寫(xiě)后面的讀一定能讀到前面寫(xiě)的內(nèi)容。所有的讀寫(xiě)請(qǐng)求都好像被全局排序。
A：對(duì)任何非失敗節(jié)點(diǎn)都應(yīng)該在有限時(shí)間內(nèi)給出請(qǐng)求的回應(yīng)。（請(qǐng)求的可終止性）
P：允許節(jié)點(diǎn)之間丟失任意多的消息，當(dāng)網(wǎng)絡(luò)分區(qū)發(fā)生時(shí)，節(jié)點(diǎn)之間的消息可能會(huì)完全丟失
該定義比Brewer提出的概念清晰了很多，也顯得更加正式化！
