分布式系统之CAP理论
一.CAP起源
CAP原本是一個猜想，2000年PODC大會的時候大牛Brewer提出的，他認為在設計一個大規(guī)模可擴放的網(wǎng)絡服務時候會遇到三個特性：一致性（consistency）、可用性（Availability）、分區(qū)容錯（partition-tolerance）都需要的情景，然而這是不可能都實現(xiàn)的。之后在2003年的時候，Mit的Gilbert和Lynch就正式的證明了這三個特征確實是不可以兼得的。該理論是NoSQL數(shù)據(jù)庫管理系統(tǒng)構(gòu)建的基礎。。
Consistency、Availability、Partition-tolerance的提法是由Brewer提出的，而Gilbert和Lynch在證明的過程中改變了Consistency的概念，將其轉(zhuǎn)化為Atomic。Gilbert認為這里所說的Consistency其實就是數(shù)據(jù)庫系統(tǒng)中提到的ACID的另一種表述：
一個用戶請求要么成功、要么失敗，不能處于中間狀態(tài)（Atomic）；
一旦一個事務完成，將來的所有事務都必須基于這個完成后的狀態(tài)（Consistent）；
未完成的事務不會互相影響（Isolated）；
一旦一個事務完成，就是持久的（Durable）。
對于Availability，其概念沒有變化，指的是對于一個系統(tǒng)而言，所有的請求都應該‘成功’并且收到‘返回’。
對于Partition-tolerance，所指就是分布式系統(tǒng)的容錯性。節(jié)點crash或者網(wǎng)絡分片都不應該導致一個分布式系統(tǒng)停止服務。
二.CAP簡介
CAP定律說的是在一個分布式計算機系統(tǒng)中，一致性，可用性和分區(qū)容錯性這三種保證無法同時得到滿足，最多滿足兩個。
?
2.1?強一致性
強一致性：系統(tǒng)在執(zhí)行過某項操作后仍然處于一致的狀態(tài)。在分布式系統(tǒng)中，更新操作執(zhí)行成功后所有的用戶都應該讀到最新的值，這樣的系統(tǒng)被認為是具有強一致性的。 等同于所有節(jié)點訪問同一份最新的數(shù)據(jù)副本；
All clients always have the same view of the data。
2.2?可用性
可用性：每一個操作總是能夠在一定的時間內(nèi)返回結(jié)果，這里需要注意的是"一定時間內(nèi)"和"返回結(jié)果"。一定時間指的是，在可以容忍的范圍內(nèi)返回結(jié)果，結(jié)果可以是成功或者失敗。 對數(shù)據(jù)更新具備高可用性（A）；
Each client can alwa read and write。
2.3?分區(qū)容錯性
分區(qū)容錯性：理解為在存在網(wǎng)絡分區(qū)的情況下，仍然可以接受請求（滿足一致性和可用性)。這里的網(wǎng)絡分區(qū)是指由于某種原因，網(wǎng)絡被分成若干個孤立的區(qū)域，而區(qū)域之間互不相通。還有一些人將分區(qū)容錯性理解為系統(tǒng)對節(jié)點動態(tài)加入和離開的能力，因為節(jié)點的加入和離開可以認為是集群內(nèi)部的網(wǎng)絡分區(qū)。
Partition Tolerance的意思是，在網(wǎng)絡中斷，消息丟失的情況下，系統(tǒng)照樣能夠工作。 以實際效果而言，分區(qū)相當于對通信的時限要求。系統(tǒng)如果不能在時限內(nèi)達成數(shù)據(jù)一致性，就意味著發(fā)生了分區(qū)的情況，必須就當前操作在C和A之間做出選擇
2.4?放棄C.A.P
放棄P：如果想避免分區(qū)容錯性問題的發(fā)生，一種做法是將所有的數(shù)據(jù)（與事務相關的）都放在一臺機器上。雖然無法100%保證系統(tǒng)不會出錯，但不會碰到由分區(qū)帶來的負面效果。當然這個選擇會嚴重的影響系統(tǒng)的擴展性。
放棄A:相對于放棄“分區(qū)容錯性“來說，其反面就是放棄可用性。一旦遇到分區(qū)容錯故障，那么受到影響的服務需要等待一定的時間，因此在等待期間系統(tǒng)無法對外提供服務。
放棄C：這里所說的放棄一致性，并不是完全放棄數(shù)據(jù)一致性，而是放棄數(shù)據(jù)的強一致性，而保留數(shù)據(jù)的最終一致性。以網(wǎng)絡購物為例，對只剩下一件庫存的商品，如果同時接受到了兩份訂單，那么較晚的訂單將被告知商品告罄。
一致性與可用性的決擇： 而CAP理論就是說在分布式存儲系統(tǒng)中，最多只能實現(xiàn)上面的兩點。而由于當前的網(wǎng)絡硬件肯定 會出現(xiàn)延遲丟包等問題，所以分區(qū)容忍性是我們必須需要實現(xiàn)的。所以我們只能在一致性和可用 性之間進行權衡。
三.基本CAP的證明思路
CAP的證明基于異步網(wǎng)絡，異步網(wǎng)絡也是反映了真實網(wǎng)絡中情況的模型。真實的網(wǎng)絡系統(tǒng)中，節(jié)點之間不可能保持同步，即便是時鐘也不可能保持同步，所有的節(jié)點依靠獲得的消息來進行本地計算和通訊。這個概念其實是相當強的，意味著任何超時判斷也是不可能的，因為沒有共同的時間標準。之后我們會擴展CAP的證明到弱一點的異步網(wǎng)絡中，這個網(wǎng)絡中時鐘不完全一致，但是時鐘運行的步調(diào)是一致的，這種系統(tǒng)是允許節(jié)點做超時判斷的。
CAP的證明很簡單，假設兩個節(jié)點集{G1, G2}，由于網(wǎng)絡分片導致G1和G2之間所有的通訊都斷開了，如果在G1中寫，在G2中讀剛寫的數(shù)據(jù)， G2中返回的值不可能G1中的寫值。由于A的要求，G2一定要返回這次讀請求，由于P的存在，導致C一定是不可滿足的。
四.CAP的理解
4.1?流行解釋
目前流行的、對CAP理論解釋的情形是從同一數(shù)據(jù)在網(wǎng)絡環(huán)境中存在多個副本出發(fā)為前提的。為了保證數(shù)據(jù)不會丟失，同時也是為了增加并發(fā)訪問量（讀寫分離），在企業(yè)級的數(shù)據(jù)管理方案中，一般必須考慮數(shù)據(jù)的冗余存儲問題，而這應該是通過在網(wǎng)絡上的其他獨立物理存儲節(jié)點上保留另一份、或多份數(shù)據(jù)副本來實現(xiàn)的（如附圖所示）。因為在同一個存儲節(jié)點上的數(shù)據(jù)冗余明顯不能解決單點故障問題，這與通過多節(jié)點集群來提供更好的計算可用性的道理是相同的。
如上圖的情況，數(shù)據(jù)在節(jié)點A、B、C上保留了三份，如果對節(jié)點A上的數(shù)據(jù)進行了修改，然后再讓客戶端通過網(wǎng)絡對該數(shù)據(jù)進行讀取。那么，客戶端的讀取操作什么時候返回呢？
一種情況是要求節(jié)點A、B、C的三份數(shù)據(jù)完全一致后返回。也就是說，這時從任何一個網(wǎng)絡節(jié)點讀取的數(shù)據(jù)都是一樣的，這就是所謂的強一致性讀。很明顯，這時數(shù)據(jù)讀取的Latency要高一些（因為要等數(shù)據(jù)在網(wǎng)絡中的復制），同時A、B、C三個節(jié)點中任何一個宕機，都會導致數(shù)據(jù)不可用。也就是說，要保證強一致性，網(wǎng)絡中的副本越多，數(shù)據(jù)的可用性就越差。
另一種情況是，允許讀操作立即返回，容忍B節(jié)點的讀取與A節(jié)點的讀取不一致的情況發(fā)生。這樣一來，可用性顯然得到了提高，網(wǎng)絡中的副本也可以多一些，唯一得不到保證的是數(shù)據(jù)一致性。當然，對寫操作同樣也有多個節(jié)點一致性的情況，在此不再贅述。
可以看出，上述對CAP理論的解釋主要是從網(wǎng)絡上多個節(jié)點之間的讀寫一致性出發(fā)考慮問題的。而這一點，對于關系型數(shù)據(jù)庫意味著什么呢？當然主要是指通常所說的Standby（關于分布式事務，涉及到更多考慮，隨后討論）情況。對此，在實踐中我們大多已經(jīng)采取了弱一致性的異步延時同步方案，以提高可用性。這種情況并不存在關系型數(shù)據(jù)庫為保證C、A而放棄P的情況；而對海量數(shù)據(jù)管理的需求，關系型數(shù)據(jù)庫擴展過程中所遇到的性能瓶頸，似乎也并不是CAP理論中所描述的那種原因造成的。那么，上述流行的說法中所描述的關系型數(shù)據(jù)庫為保證C、A而犧牲P到底是在指什么呢？ 如果只將CAP當作分布式系統(tǒng)中多個數(shù)據(jù)副本之間的讀寫一致性問題的通用理論對待，那么就可以得出結(jié)論：CAP既適用于NoSQL數(shù)據(jù)庫，也適用于關系型數(shù)據(jù)庫。它是NoSQL數(shù)據(jù)庫、關系型數(shù)據(jù)庫，乃至一切分布式系統(tǒng)在設計數(shù)據(jù)多個副本之間讀寫一致性問題時需要遵循的共同原則。
4.2?形式化描述
要真正理解 CAP 理論必須要讀懂它的形式化描述。 形式化描述中最重要的莫過于對 Consistency, Availability, Partition-tolerance 的準確定義。
Consistency (一致性) 實際上等同于系統(tǒng)領域的 before-or-after atomicity 這個術語，或者等同于 linearizable (可串行化) 這個術語。具體來說，系統(tǒng)中對一個數(shù)據(jù)的讀和寫雖然包含多個子步驟并且會持續(xù)一段時間才能執(zhí)行完，但是在調(diào)用者看來，讀操作和寫操作都必須是單個的即時完成的操作，不存在重疊。對一個寫操作，如果系統(tǒng)返回了成功，那么之后到達的讀請求都必須讀到這個新的數(shù)據(jù)；如果系統(tǒng)返回失敗，那么所有的讀，無論是之后發(fā)起的，還是和寫同時發(fā)起的，都不能讀到這個數(shù)據(jù)。
要說清楚 Availability 和 Partition-tolerance 必須要定義好系統(tǒng)的故障模型。在形式化證明中，系統(tǒng)包含多個節(jié)點，每個節(jié)點可以接收讀和寫的請求，返回成功或失敗，對讀還要返回一個數(shù)據(jù)。和調(diào)用者之間的連接是不會中斷的，系統(tǒng)的節(jié)點也不會失效，唯一的故障就是報文的丟失。 Partition-tolerance 指系統(tǒng)中會任意的丟失報文(這和“最終會有一個報文會到達”是相對的)。 Availability 是指所有的讀和寫都必須要能終止。
注： “Availability 是指所有的讀和寫都必須要能終止” 這句話聽上去很奇怪，為什么不是“Availability 是指所有的寫和讀都必須成功”？ 要回答這個問題，我們可以仔細思考下“什么是成功”。“成功”必須要相對于某個參照而言，這里的參照就是 Consistency。
4.3?兩種重要的分布式場景
關于對CAP理論中一致性C的理解，除了上述數(shù)據(jù)副本之間的讀寫一致性以外，分布式環(huán)境中還有兩種非常重要的場景，如果不對它們進行認識與討論，就永遠無法全面地理解CAP，當然也就無法根據(jù)CAP做出正確的解釋。
1.分布式環(huán)境中的事務場景?
我們知道，在關系型數(shù)據(jù)庫的事務操作遵循ACID原則，其中的一致性C，主要是指一個事務中相關聯(lián)的數(shù)據(jù)在事務操作結(jié)束后是一致的。所謂ACID原則，是指在寫入/異動資料的過程中，為保證交易正確可靠所必須具備的四個特性：即原子性（Atomicity，或稱不可分割性）、一致性（Consistency）、隔離性（Isolation，又稱獨立性）和持久性（Durability）。
例如銀行的一個存款交易事務，將導致交易流水表增加一條記錄。同時，必須導致賬戶表余額發(fā)生變化，這兩個操作必須是一個事務中全部完成，保證相關數(shù)據(jù)的一致性。而前文解釋的CAP理論中的C是指對一個數(shù)據(jù)多個備份的讀寫一致性。表面上看，這兩者不是一回事，但實際上，卻是本質(zhì)基本相同的事物：數(shù)據(jù)請求會等待多個相關數(shù)據(jù)操作全部完成才返回。對分布式系統(tǒng)來講，這就是我們通常所說的分布式事務問題。
眾所周知，分布式事務一般采用兩階段提交策略來實現(xiàn)，這是一個非常耗時的復雜過程，會嚴重影響系統(tǒng)效率，在實踐中我們盡量避免使用它。在實踐過程中，如果我們?yōu)榱藬U展數(shù)據(jù)容量將數(shù)據(jù)分布式存儲，而事務的要求又完全不能降低。那么，系統(tǒng)的可用性一定會大大降低，在現(xiàn)實中我們一般都采用對這些數(shù)據(jù)不分散存儲的策略。
當然，我們也可以說，最常使用的關系型數(shù)據(jù)庫，因為這個原因，擴展性（分區(qū)可容忍性P）受到了限制，這是完全符合CAP理論的。但同時我們應該意識到，這對NoSQL數(shù)據(jù)庫也是一樣的。如果NoSQL數(shù)據(jù)庫也要求嚴格的分布式事務功能，情況并不會比關系型數(shù)據(jù)庫好多少。只是在NoSQL的設計中，我們往往會弱化甚至去除事務的功能，該問題才表現(xiàn)得不那么明顯而已。
因此，在擴展性問題上，如果要說關系型數(shù)據(jù)庫是為了保證C、A而犧牲P，在盡量避免分布式事務這一點上來看，應該是正確的。也就是說：關系型數(shù)據(jù)庫應該具有強大的事務功能，如果分區(qū)擴展，可用性就會降低；而NoSQL數(shù)據(jù)庫干脆弱化甚至去除了事務功能，因此，分區(qū)的可擴展性就大大增加了。
2.分布式環(huán)境中的關聯(lián)場景
初看起來，關系型數(shù)據(jù)庫中常用的多表關聯(lián)操作與CAP理論就更加不沾邊了。但仔細考慮，也可以用它來解釋數(shù)據(jù)庫分區(qū)擴展對關聯(lián)所帶來的影響。對一個數(shù)據(jù)庫來講，采用了分區(qū)擴展策略來擴充容量，數(shù)據(jù)分散存儲了，很顯然多表關聯(lián)的性能就會下降，因為我們必須在網(wǎng)絡上進行大量的數(shù)據(jù)遷移操作，這與CAP理論中數(shù)據(jù)副本之間的同步操作本質(zhì)上也是相同的。
因此，如果要保證系統(tǒng)的高可用性，需要同時實現(xiàn)強大的多表關系操作的關系型數(shù)據(jù)庫在分區(qū)可擴展性上就遇到了極大的限制（即使是那些采用了各種優(yōu)秀解決方案的MPP架構(gòu)的關系型數(shù)據(jù)庫，如TeraData，Netezza等，其水平可擴展性也是遠遠不如NoSQL數(shù)據(jù)庫的），而NoSQL數(shù)據(jù)庫則干脆在設計上弱化甚至去除了多表關聯(lián)操作。那么，從這一點上來理解"NoSQL數(shù)據(jù)庫是為了保證A與P，而犧牲C"的說法，也是可以講得通的。當然，我們應該理解，關聯(lián)問題在很多情況下不是并行處理的優(yōu)點所在，這在很大程度上與Amdahl定律相符合。
所以，從事務與關聯(lián)的角度來看關系型數(shù)據(jù)庫的分區(qū)可擴展性為什么受限的原因是最為清楚的。而NoSQL數(shù)據(jù)庫也正是因為弱化，甚至去除了像事務與關聯(lián)（全面地講，其實還有索引等特性）等在分布式環(huán)境中會嚴重影響系統(tǒng)可用性的功能，才獲得了更好的水平可擴展性。
那么，如果將事務與關聯(lián)也納入CAP理論中一致性C的范疇的話，問題就很清楚了：關于“關系型數(shù)據(jù)庫為了保證一致性C與可用性A，而不得不犧牲分區(qū)可容忍性P”的說法便是正確的了。但關于"NoSQL選擇了C與P，或者A與P"的說法則是錯誤的，所有的NoSQL數(shù)據(jù)庫在設計策略的大方向上都是選擇了A與P（雖然對同一數(shù)據(jù)多個副本的讀寫一致性問題的設計各有不同），從來沒有完全選擇C與P的情況存在。
現(xiàn)在看來，如果理解CAP理論只是指多個數(shù)據(jù)副本之間讀寫一致性的問題，那么它對關系型數(shù)據(jù)庫與NoSQL數(shù)據(jù)庫來講是完全一樣的，它只是運行在分布式環(huán)境中的數(shù)據(jù)管理設施在設計讀寫一致性問題時需要遵循的一個原則而已，卻并不是NoSQL數(shù)據(jù)庫具有優(yōu)秀的水平可擴展性的真正原因。而如果將CAP理論中的一致性C理解為讀寫一致性、事務與關聯(lián)操作的綜合，則可以認為關系型數(shù)據(jù)庫選擇了C與A，而NoSQL數(shù)據(jù)庫則全都是選擇了A與P，但并沒有選擇C與P的情況存在。????????????????????????
五.一致性分類?
對于分布式數(shù)據(jù)系統(tǒng)，分區(qū)容忍性是基本要求，否則就失去了價值。因此設計分布式數(shù)據(jù)系統(tǒng)，就是在一致性和可用性之間取一個平衡。對于大多數(shù)WEB應用，其實并不需要強一致性，因此犧牲一致性而換取高可用性，是多數(shù)分布式數(shù)據(jù)庫產(chǎn)品的方向。 ?????? ??????
當然，犧牲一致性，并不是完全不管數(shù)據(jù)的一致性，否則數(shù)據(jù)是混亂的，那么系統(tǒng)可用性再高分布式再好也沒有了價值。犧牲一致性，只是不再要求關系型數(shù)據(jù)庫中的強一致性，而是只要系統(tǒng)能達到最終一致性即可，考慮到客戶體驗，這個最終一致的時間窗口，要盡可能的對用戶透明，也就是需要保障“用戶感知到的一致性”。通常是通過數(shù)據(jù)的多份異步復制來實現(xiàn)系統(tǒng)的高可用和數(shù)據(jù)的最終一致性的，“用戶感知到的一致性”的時間窗口則取決于數(shù)據(jù)復制到一致狀態(tài)的時間。 ?????? ???????
對于一致性，可以分為從客戶端和服務端兩個不同的視角。從客戶端來看，一致性主要指的是多并發(fā)訪問時更新過的數(shù)據(jù)如何獲取的問題。從服務端來看，則是更新如何復制分布到整個系統(tǒng)，以保證數(shù)據(jù)最終一致。一致性是因為有并發(fā)讀寫才有的問題，因此在理解一致性的問題時，一定要注意結(jié)合考慮并發(fā)讀寫的場景。
5.1?客戶端角度
從客戶端角度，多進程并發(fā)訪問時，更新過的數(shù)據(jù)在不同進程如何獲取的不同策略，決定了不同的一致性。對于關系型數(shù)據(jù)庫， 要求更新過的數(shù)據(jù)能被后續(xù)的訪問都能看到，這是強一致性。如果能容忍后續(xù)的部分或者全部訪問不到，則是弱一致性。如果經(jīng)過一段時間后要求能訪問到更新后的數(shù)據(jù)，則是最終一致性。 ????? ?????
在MongoDB中可以通過配置讓復制集成員內(nèi)部支持強一致性，這時可以設置一個寫成功數(shù)，只有寫操作成功樹滿足設定的值時才會向客戶端返回結(jié)果。
最終一致性根據(jù)更新數(shù)據(jù)后各進程訪問到數(shù)據(jù)的時間和方式的不同，又可以區(qū)分為：因果一致性(CAUSAL CONSISTENCY)，如果進程A通知進程B它已更新了一個數(shù)據(jù)項，那么進程B的后續(xù)訪問將返回更新后的值，且一次寫入將保證取代前一次寫入。與進程A無因果關系的進程C的訪問遵守一般的最終一致性規(guī)則。讀己之所寫（READ-YOUR-WRITES）一致性，當進程A自己更新一個數(shù)據(jù)項之后，它總是訪問到更新過的值，絕不會看到舊值。這是因果一致性模型的一個特例。會話（SESSION）一致性，這是上一個模型的實用版本，它把訪問存儲系統(tǒng)的進程放到會話的上下文中。只要會話還存在，系統(tǒng)就保證“讀己之所寫”一致性。如果由于某些失敗情形令會話終止，就要建立新的會話，而且系統(tǒng)的保證不會延續(xù)到新的會話。單調(diào)（MONOTONIC）讀一致性，如果進程已經(jīng)看到過數(shù)據(jù)對象的某個值，那么任何后續(xù)訪問都不會返回在那個值之前的值。單調(diào)寫一致性，系統(tǒng)保證來自同一個進程的寫操作順序執(zhí)行。要是系統(tǒng)不能保證這種程度的一致性，就非常難以編程了。
上述最終一致性的不同方式可以進行組合，例如單調(diào)讀一致性和讀己之所寫一致性就可以組合實現(xiàn)。并且從實踐的角度來看，這兩者的組合，讀取自己更新的數(shù)據(jù)，和一旦讀取到最新的版本不會再讀取舊版本，對于此架構(gòu)上的程序開發(fā)來說，會少很多額外的煩惱。
5.2?服務端角度
從服務端角度，如何盡快將更新后的數(shù)據(jù)分布到整個系統(tǒng)，降低達到最終一致性的時間窗口，是提高系統(tǒng)的可用度和用戶體驗非常重要的方面。對于分布式數(shù)據(jù)系統(tǒng)：N — 數(shù)據(jù)復制的份數(shù),W — 更新數(shù)據(jù)是需要保證寫完成的節(jié)點數(shù),R — 讀取數(shù)據(jù)的時候需要讀取的節(jié)點數(shù)，如果W+R>N，寫的節(jié)點和讀的節(jié)點重疊，則是強一致性。例如對于典型的一主一備同步復制的關系型數(shù)據(jù)庫，N=2,W=2,R=1，則不管讀的是主庫還是備庫的數(shù)據(jù)，都是一致的。如果W+R<=N，則是弱一致性。例如對于一主一備異步復制的關系型數(shù)據(jù)庫，N=2,W=1,R=1，則如果讀的是備庫，就可能無法讀取主庫已經(jīng)更新過的數(shù)據(jù)，所以是弱一致性。
對于分布式系統(tǒng)，為了保證高可用性，一般設置N>=3。不同的N,W,R組合，是在可用性和一致性之間取一個平衡，以適應不同的應用場景。如果N=W,R=1，任何一個寫節(jié)點失效，都會導致寫失敗，因此可用性會降低，但是由于數(shù)據(jù)分布的N個節(jié)點是同步寫入的，因此可以保證強一致性。如果N=R,W=1，只需要一個節(jié)點寫入成功即可，寫性能和可用性都比較高。但是讀取其他節(jié)點的進程可能不能獲取更新后的數(shù)據(jù)，因此是弱一致性。這種情況下，如果W<(N+1)/2，并且寫入的節(jié)點不重疊的話，則會存在寫沖突。
六.傳統(tǒng)數(shù)據(jù)庫與NoSQL數(shù)據(jù)庫
傳統(tǒng)的關系型數(shù)據(jù)庫在功能支持上通常很寬泛，從簡單的鍵值查詢，到復雜的多表聯(lián)合查詢再到事務機制的支持。而與之不同的是，NoSQL系統(tǒng)通常注重性能和擴展性，而非事務機制（事務就是強一致性的體現(xiàn)）。 ?????
傳統(tǒng)的SQL數(shù)據(jù)庫的事務通常都是支持ACID的強事務機制。A代表原子性，即在事務中執(zhí)行多個操作是原子性的，要么事務中的操作全部執(zhí)行，要么一個都不執(zhí)行;C代表一致性，即保證進行事務的過程中整個數(shù)據(jù)加的狀態(tài)是一致的，不會出現(xiàn)數(shù)據(jù)花掉的情況;I代表隔離性，即兩個事務不會相互影響，覆蓋彼此數(shù)據(jù)等;D表示持久化，即事務一量完成，那么數(shù)據(jù)應該是被寫到安全的，持久化存儲的設備上（比如磁盤）。 ????????
NoSQL系統(tǒng)僅提供對行級別的原子性保證，也就是說同時對同一個Key下的數(shù)據(jù)進行的兩個操作，在實際執(zhí)行的時候是會串行的執(zhí)行，保證了每一個Key-Value對不會被破壞。例如MongoDB數(shù)據(jù)庫，它是不支持事務機制的，同時也不提倡多表關聯(lián)的復雜模式設計，它只保證對單個文檔(相當于關系數(shù)據(jù)庫中的記錄)讀寫的原子性。
補充: ?MPP架構(gòu)介紹 MPP (Massively Parallel Processing)，大規(guī)模并行處理系統(tǒng)，這樣的系統(tǒng)是由許多松耦合的處理單元組成的，要注意的是這里指的是處理單元而不是處理器。每個單元內(nèi)的CPU都有自己私有的資源，如總線，內(nèi)存，硬盤等。在每個單元內(nèi)都有操作系統(tǒng)和管理數(shù)據(jù)庫的實例復本。這種結(jié)構(gòu)最大的特點在于不共享資源。
七.戰(zhàn)勝CAP
核心內(nèi)容就是放松Gilbert和Lynch證明中的限制：“系統(tǒng)必須同時達到CAP三個屬性”，放松到“系統(tǒng)可以不同時達到CAP，而是分時達到”。??
CAP理論被很多人拿來作為分布式系統(tǒng)設計的金律，然而感覺大家對CAP這三個屬性的認識卻存在不少誤區(qū)。從CAP的證明中可以看出來，這個理論的成立是需要很明確的對C、A、P三個概念進行界定的前提下的。在本文中筆者希望可以對論文和一些參考資料進行總結(jié)并附帶一些思考
CAP理論的表述很好地服務了它的目的，即開闊設計師的思路，在多樣化的取舍方案下設計出多樣化的系統(tǒng)。在過去的十幾年里確實涌現(xiàn)了不計其數(shù)的新系統(tǒng)，也隨之在數(shù)據(jù)一致性和可用性的相對關系上產(chǎn)生了相當多的爭論。“三選二”的公式一直存在著誤導性，它會過分簡單化各性質(zhì)之間的相互關系。現(xiàn)在我們有必要辨析其中的細節(jié)。實際上只有“在分區(qū)存在的前提下呈現(xiàn)完美的數(shù)據(jù)一致性和可用性”這種很少見的情況是CAP理論不允許出現(xiàn)的。
雖然設計師仍然需要在分區(qū)的前提下對數(shù)據(jù)一致性和可用性做取舍，但具體如何處理分區(qū)和恢復一致性，這里面有不計其數(shù)的變通方案和靈活度。當代CAP實踐應將目標定為針對具體的應用，在合理范圍內(nèi)最大化數(shù)據(jù)一致性和可用性的“合力”。這樣的思路延伸為如何規(guī)劃分區(qū)期間的操作和分區(qū)之后的恢復，從而啟發(fā)設計師加深對CAP的認識，突破過去由于CAP理論的表述而產(chǎn)生的思維局限。
7.1 為什么“三選二”公式有誤導性
理解CAP理論的最簡單方式是想象兩個節(jié)點分處分區(qū)兩側(cè)。允許至少一個節(jié)點更新狀態(tài)會導致數(shù)據(jù)不一致，即喪失了C性質(zhì)。如果為了保證數(shù)據(jù)一致性，將分區(qū)一側(cè)的節(jié)點設置為不可用，那么又喪失了A性質(zhì)。除非兩個節(jié)點可以互相通信，才能既保證C又保證A，這又會導致喪失P性質(zhì)。一般來說跨區(qū)域的系統(tǒng)，設計師無法舍棄P性質(zhì)，那么就只能在數(shù)據(jù)一致性和可用性上做一個艱難選擇。不確切地說，NoSQL運動的主題其實是創(chuàng)造各種可用性優(yōu)先、數(shù)據(jù)一致性其次的方案；而傳統(tǒng)數(shù)據(jù)庫堅守ACID特性（原子性、一致性、隔離性、持久性），做的是相反的事情。下文“ACID、BASE、CAP”小節(jié)詳細說明了它們的差異。
“三選二”的觀點在幾個方面起了誤導作用，詳見下文“CAP之惑”小節(jié)的解釋。首先，由于分區(qū)很少發(fā)生，那么在系統(tǒng)不存在分區(qū)的情況下沒什么理由犧牲C或A。其次，C與A之間的取舍可以在同一系統(tǒng)內(nèi)以非常細小的粒度反復發(fā)生，而每一次的決策可能因為具體的操作，乃至因為牽涉到特定的數(shù)據(jù)或用戶而有所不同。最后，這三種性質(zhì)都可以在程度上衡量，并不是非黑即白的有或無。可用性顯然是在0%到100%之間連續(xù)變化的，一致性分很多級別，連分區(qū)也可以細分為不同含義，如系統(tǒng)內(nèi)的不同部分對于是否存在分區(qū)可以有不一樣的認知。
要探索這些細微的差別，就要突破傳統(tǒng)的分區(qū)處理方式，而這是一項根本性的挑戰(zhàn)。因為分區(qū)很少出現(xiàn)，CAP在大多數(shù)時候允許完美的C和A。但當分區(qū)存在或可感知其影響的情況下，就要預備一種策略去探知分區(qū)并顯式處理其影響。這樣的策略應分為三個步驟：探知分區(qū)發(fā)生，進入顯式的分區(qū)模式以限制某些操作，啟動恢復過程以恢復數(shù)據(jù)一致性并補償分區(qū)期間發(fā)生的錯誤。
7.2?解決CAP
根據(jù)一些專家的分析，CAP并不是一個嚴謹?shù)亩?#xff0c;并不是犧牲了Consistency，就一定能同時獲得Availability和Partition Tolerance。還有一個很重要的因素是Latency，在CAP中并沒有體現(xiàn)。在現(xiàn)在NoSQL以及其他一些大規(guī)模設計時，A和P并不是犧牲C或部分犧牲C的借口，因為即使犧牲了C，也不一定A和P，并且C不一定必須要犧牲。
淘寶一天就處理了1億零580萬，而12306一天處理的交易僅僅166萬條 ，如果從并發(fā)性上來說，淘寶的并發(fā)量遠比12306大，但天貓的商品信息，促銷數(shù)據(jù)都可以做緩存，做CDN，而12306的“商品”是一個個座位，這些座位必須通過后端數(shù)據(jù)庫即時查詢出來，狀態(tài)的一致性要求很高。
從這點上看，12306的商品信息很難利用到緩存，因此12306查看“商品”的代價是比較大的，涉及到一系列的后端數(shù)據(jù)庫操作，從這個角度講，12306的復雜度是高于天貓的。 淘寶的商品相對獨立，而12306商品之間的關聯(lián)性很大，由于CAP定律限制，如果其商品的一致性要求過高，必然對可用性和分區(qū)容錯性造成影響。
因此，業(yè)務設計上，如果找到一條降低一致性要求時，還能保證業(yè)務的正確性的業(yè)務分拆之路。舉個例子，火車票查詢時，不要顯示多少張，而是顯示“有”或“無”，或者顯示>100張，50~100,小于50等，這樣就可以減小狀態(tài)的更新頻率，充分使用緩存數(shù)據(jù)。
CAP 理論說在一個系統(tǒng)中對某個數(shù)據(jù)不存在一個算法同時滿足 Consistency, Availability, Partition-tolerance。注意，這里邊最重要和最容易被人忽視的是限定詞“對某個數(shù)據(jù)不存在一個算法”。這就是說在一個系統(tǒng)中，可以對某些數(shù)據(jù)做到 CP, 對另一些數(shù)據(jù)做到 AP，就算是對同一個數(shù)據(jù)，調(diào)用者可以指定不同的算法，某些算法可以做到 CP，某些算法可以做到 AP。
7.3?做到兩項
要做到 CP， 系統(tǒng)可以把這個數(shù)據(jù)只放在一個節(jié)點上，其他節(jié)點收到請求后向這個節(jié)點讀或?qū)憯?shù)據(jù)，并返回結(jié)果。很顯然，串行化是保證的。但是如果報文可以任意丟失的話，接受請求的節(jié)點就可能永遠不返回結(jié)果。
要做到 CA， 一個現(xiàn)實的例子就是單點的數(shù)據(jù)庫。你可能會疑惑“數(shù)據(jù)庫也不是 100% 可用的呀？” 要回答這個疑惑，注意上面說的故障模型和 availability 的定義就可以了。
要做到 AP， 系統(tǒng)只要每次對寫都返回成功，對讀都返回固定的某個值就可以了。
如果我們到這里就覺得已近掌握好 CAP 理論了，那么就相當于剛把橘子剝開，就把它扔了。
CAP 理論更重要的一個結(jié)果是， 在 Partial Synchronous System (半同步系統(tǒng)) 中，一個弱化的 CAP 是能達到的:對所有的數(shù)據(jù)訪問，總返回一個結(jié)果 * 如果期間沒有報文丟失，那么返回一個滿足 consistency 要求的結(jié)果。
這里的半同步系統(tǒng)指每個節(jié)點存在一個時鐘，這些時鐘不需要同步，但是按照相同的速率流逝。更通俗的來說，就是一個能夠?qū)崿F(xiàn)超時機制的系統(tǒng)。
舉個例子，系統(tǒng)可以把這個數(shù)據(jù)只放在一個節(jié)點上，其他節(jié)點收到請求后向這個節(jié)點讀或?qū)憯?shù)據(jù)，并設置一個定時器，如果超時前得到結(jié)果，那么返回這個結(jié)果，否則返回失敗。更進一步的，也是最重要的，實現(xiàn)一個滿足最終一致性 (Eventually Consistency) 和 AP 的系統(tǒng)是可行的。 現(xiàn)實中的一個例子是 Cassandra 系統(tǒng)。
而對于分布式數(shù)據(jù)系統(tǒng)，分區(qū)容忍性是基本要求，否則就失去了價值。因此設計分布式數(shù)據(jù)系統(tǒng)，就是在一致性和可用性之間取一個平衡。對于大多數(shù)WEB應用，其實并不需要強一致性，因此犧牲一致性而換取高可用性，是多數(shù)分布式數(shù)據(jù)庫產(chǎn)品的方向。 當然，犧牲一致性，并不是完全不管數(shù)據(jù)的一致性，否則數(shù)據(jù)是混亂的，那么系統(tǒng)可用性再高分布式再好也沒有了價值。犧牲一致性，只是不再要求關系型數(shù)據(jù)庫中的強一致性，而是只要系統(tǒng)能達到最終一致性即可，考慮到客戶體驗，這個最終一致的時間窗口，要盡可能的對用戶透明，也就是需要保障“用戶感知到的一致性”。通常是通過數(shù)據(jù)的多份異步復制來實現(xiàn)系統(tǒng)的高可用和數(shù)據(jù)的最終一致性的，“用戶感知到的一致性”的時間窗口則取決于數(shù)據(jù)復制到一致狀態(tài)的時間。
最終一致性(EVENTUALLY CONSISTENT) 對于一致性，可以分為從客戶端和服務端兩個不同的視角。從客戶端來看，一致性主要指的是多并發(fā)訪問時更新過的數(shù)據(jù)如何獲取的問題。從服務端來看，則是更新如何復制分布到整個系統(tǒng)，以保證數(shù)據(jù)最終一致。一致性是因為有并發(fā)讀寫才有的問題，因此在理解一致性的問題時，一定要注意結(jié)合考慮并發(fā)讀寫的場景。 從客戶端角度，多進程并發(fā)訪問時，更新過的數(shù)據(jù)在不同進程如何獲取的不同策略，決定了不同的一致性。對于關系型數(shù)據(jù)庫，要求更新過的數(shù)據(jù)能被后續(xù)的訪問都能看到，這是強一致性。如果能容忍后續(xù)的部分或者全部訪問不到，則是弱一致性。如果經(jīng)過一段時間后要求能訪問到更新后的數(shù)據(jù)，則是最終一致性。 最終一致性根據(jù)更新數(shù)據(jù)后各進程訪問到數(shù)據(jù)的時間和方式的不同，又可以區(qū)分為： 因果一致性(CAUSAL CONSISTENCY)
如果進程A通知進程B它已更新了一個數(shù)據(jù)項，那么進程B的后續(xù)訪問將返回更新后的值，且一次寫入將保證取代前一次寫入。與進程A無因果關系的進程C的訪問遵守一般的最終一致性規(guī)則。“讀己之所寫（READ-YOUR-WRITES）”一致性。當進程A自己更新一個數(shù)據(jù)項之后，它總是訪問到更新過的值，絕不會看到舊值。這是因果一致性模型的一個特例。會話（SESSION）一致性。這是上一個模型的實用版本，它把訪問存儲系統(tǒng)的進程放到會話的上下文中。只要會話還存在，系統(tǒng)就保證“讀己之所寫”一致性。如果由于某些失敗情形令會話終止，就要建立新的會話，而且系統(tǒng)的保證不會延續(xù)到新的會話。單調(diào)（MONOTONIC）讀一致性。如果進程已經(jīng)看到過數(shù)據(jù)對象的某個值，那么任何后續(xù)訪問都不會返回在那個值之前的值。單調(diào)寫一致性。系統(tǒng)保證來自同一個進程的寫操作順序執(zhí)行。要是系統(tǒng)不能保證這種程度的一致性，就非常難以編程了。上述最終一致性的不同方式可以進行組合，例如單調(diào)讀一致性和讀己之所寫一致性就可以組合實現(xiàn)。并且從實踐的角度來看，這兩者的組合，讀取自己更新的數(shù)據(jù)，和一旦讀取到最新的版本不會再讀取舊版本，對于此架構(gòu)上的程序開發(fā)來說，會少很多額外的煩惱。 從服務端角度，如何盡快將更新后的數(shù)據(jù)分布到整個系統(tǒng)，降低達到最終一致性的時間窗口，是提高系統(tǒng)的可用度和用戶體驗非常重要的方面。
對于分布式數(shù)據(jù)系統(tǒng)： N — 數(shù)據(jù)復制的份數(shù),W — 更新數(shù)據(jù)是需要保證寫完成的節(jié)點數(shù),R — 讀取數(shù)據(jù)的時候需要讀取的節(jié)點數(shù)如果W+R>N，寫的節(jié)點和讀的節(jié)點重疊，則是強一致性。例如對于典型的一主一備同步復制的關系型數(shù)據(jù)庫，N=2,W=2,R=1，則不管讀的是主庫還是備庫的數(shù)據(jù)，都是一致的。 如果W+R<=N，則是弱一致性。例如對于一主一備異步復制的關系型數(shù)據(jù)庫，N=2,W=1,R=1，則如果讀的是備庫，就可能無法讀取主庫已經(jīng)更新過的數(shù)據(jù)，所以是弱一致性。 對于分布式系統(tǒng)，為了保證高可用性，一般設置N>=3。不同的N,W,R組合，是在可用性和一致性之間取一個平衡，以適應不同的應用場景。 如果N=W,R=1，任何一個寫節(jié)點失效，都會導致寫失敗，因此可用性會降低，但是由于數(shù)據(jù)分布的N個節(jié)點是同步寫入的，因此可以保證強一致性。如果N=R,W=1，只需要一個節(jié)點寫入成功即可，寫性能和可用性都比較高。但是讀取其他節(jié)點的進程可能不能獲取更新后的數(shù)據(jù)，因此是弱一致性。這種情況下，如果W<(N+1)/2，并且寫入的節(jié)點不重疊的話，則會存在寫沖突。
參考文獻
- http://www.infoq.com/cn/articles/cap-twelve-years-later-how-the-rules-have-changed/
- http://blog.csdn.net/it_man/article/details/8574201
- http://www.cnblogs.com/mmjx/archive/2011/12/19/2290540.html
- http://blog.csdn.net/zhangzhebjut/article/details/22977977
轉(zhuǎn)載于:https://www.cnblogs.com/WeiGe/p/5632847.html
總結(jié)
以上是生活随笔為你收集整理的分布式系统之CAP理论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [HIHO1323]回文字符串（区间dp
- 下一篇： 算法系列：杂项