分布式系統(tǒng)原理

CAP 理論

CAP 理論是由 Eric Brewer 提出的分布式系統(tǒng)中最為重要的理論之一[8]。本文將 CAP 理論安排在原理部分的最后介紹是為了利用前面已經(jīng)介紹過的幾種分布式協(xié)議來幫助理解 CAP 理論。

1. 定義

CAP 理論的定義很簡(jiǎn)單，CAP三個(gè)字母分別代表了分布式系統(tǒng)中三個(gè)相互矛盾的屬性：

Consistency (一致性)：CAP 理論中的副本一致性特指強(qiáng)一致性（1.3.4 ）；

Availiablity(可用性)：指系統(tǒng)在出現(xiàn)異常時(shí)已經(jīng)可以提供服務(wù)；

Tolerance to the partition of network (分區(qū)容忍)：指系統(tǒng)可以對(duì)網(wǎng)絡(luò)分區(qū)（1.1.4.2 ）這種異常情況進(jìn)行容錯(cuò)處理；

CAP 理論指出：無法設(shè)計(jì)一種分布式協(xié)議，使得同時(shí)完全具備 CAP 三個(gè)屬性，即 1)該種協(xié)議下的副本始終是強(qiáng)一致性，2)服務(wù)始終是可用的，3)協(xié)議可以容忍任何網(wǎng)絡(luò)分區(qū)異常；分布式系統(tǒng)協(xié)議只能在 CAP 這三者間所有折中。

CAP 理論的詳細(xì)證明可以參考相關(guān)論文。這里可以簡(jiǎn)單用一個(gè)反例證明不存在 CAP 兼具的系統(tǒng)。假設(shè)系統(tǒng)只有兩個(gè)副本 A 和 B，Client 更新這兩個(gè)副本，假設(shè)在網(wǎng)絡(luò)分化時(shí)，Client 與副本 A 可以正常通信，但副本 B 與 Client、副本 B 與副本 A 無法通信，此時(shí)，Client 對(duì)副本 A 更新的信息永遠(yuǎn)無法同步到副本 B 上。如果希望系統(tǒng)依舊具有強(qiáng)一致的屬性，則此時(shí)需要停止更新服務(wù)，即不 再修改數(shù)據(jù)，從而讓副本 A 與副本 B 保持一致；如果希望系統(tǒng)依舊可以提供更新服務(wù)，則只能更新副本 A 而無法更新副本 B，此時(shí)無法保證副本 A 與副本 B 一致。

2. CAP 理論的意義

熱力學(xué)第二定律說明了永動(dòng)機(jī)是不可能存在的，不要去妄圖設(shè)計(jì)永動(dòng)機(jī)。與之類似，CAP 理論的意義就在于明確提出了++不要去妄圖設(shè)計(jì)一種對(duì) CAP 三大屬性都完全擁有的完美系統(tǒng)++，因?yàn)檫@種系統(tǒng)在理論上就已經(jīng)被證明不存在。

3. 協(xié)議分析

本節(jié)分析在第二章中介紹的幾種分布式協(xié)議是如何在 CAP 三大屬性中做折中與取舍的。在三章介紹典型分布式系統(tǒng)時(shí)，也會(huì)用 CAP 理論對(duì)這些系統(tǒng)的分布式協(xié)議進(jìn)行分析。

3.1 Lease 機(jī)制

Lease 機(jī)制犧牲了部分異常情況下的 A，從而獲得了完全的 C 與很好的 P。

上面這句話有點(diǎn)抽象，下面一一解釋。首先，Lease 機(jī)制不是在任何情況下都具有可用性的，使用 Lease 機(jī)制的協(xié)議，在發(fā)生異常時(shí)，需要等待 Lease 超時(shí)才能收回 Lease 權(quán)限。然而，Lease 的持有者可能在 Lease 超時(shí)前就已經(jīng)出現(xiàn)異常而不能提供服務(wù)了，直到 Lease 超時(shí)這段時(shí)間內(nèi)，系統(tǒng)服務(wù)的可用性都有問題。例如，如果用 lease 決定 Primary 副本的，Primary 副本節(jié)點(diǎn)宕機(jī)后，只有待 Lease 超時(shí)才能選出新的 primary 副本，這段時(shí)間由于缺乏 primary 副本是沒有更新服務(wù)的。再者，Lease協(xié)議本身保證了對(duì)于Lease約定的承諾在Lease頒發(fā)者和持有者之間是始終一致的。即使Lease持有者由于網(wǎng)絡(luò)分化沒有真正收到 Lease，Lease 頒發(fā)者也會(huì)在 Lease 時(shí)間內(nèi)執(zhí)行自己的承諾；而一旦 Lease 持有者收到 Lease，則即使再出現(xiàn)網(wǎng)絡(luò)分化，也無法影響雙方對(duì) Lease 承諾理解的一致性。最后，Lease 協(xié)議引入了“時(shí)間”這一概念，使得在對(duì)抗網(wǎng)絡(luò)分化上有其特別的優(yōu)勢(shì)，另外，Lease只需由頒發(fā)者向持有者通信，即使網(wǎng)絡(luò)是單向的也不影響 Lease 協(xié)議的正常工作。

3.2 Quorum 機(jī)制

這里僅討論一般的 Quorum 機(jī)制，即總共有 N 個(gè)副本，成功更新 W 個(gè)副本則算成功提交，讀取時(shí)讀 R 個(gè)副本。這種一般的 Quorum 機(jī)制，在 CAP 三大因素中都各做了折中，有一定的 C，有較好的 A，也有較好的 P，是一種較為平衡的分布式協(xié)議。

首先，讀取 R 個(gè)副本時(shí)，可以保證讀取到成功提交的版本，但無法保證讀取到最新的成功提交 的版本（2.4.4 ）。也就是說，系統(tǒng)具有一定的一致性，卻無法真正做到強(qiáng)一致性。再者，無論是更 新 W 個(gè)副本，還是讀取 R 個(gè)副本，協(xié)議可以允許部分副本異常而不影響更新或者讀取服務(wù)。最后， 只要能與 W 個(gè)副本通信就可以提供更新服務(wù)，能與 R 個(gè)副本通信就可以提供讀服務(wù)，協(xié)議具有一 定的容忍網(wǎng)絡(luò)分化的能力。工程中，當(dāng)使用 3 個(gè)副本時(shí)，可以講三個(gè)副本部署在三個(gè)不同的機(jī)房， 只有同時(shí)出現(xiàn)兩個(gè)機(jī)房的網(wǎng)絡(luò)都異常時(shí)才會(huì)影響服務(wù)，這種情況的概率本身已經(jīng)非常低了。

3.3 兩階段提交協(xié)議

兩階段提交系統(tǒng)具有完全的 C，很糟糕的 A，很糟糕的 P。

首先，兩階段提交協(xié)議保證了副本間是完全一致的，這也是協(xié)議的設(shè)計(jì)目的。再者，協(xié)議在一個(gè)節(jié)點(diǎn)出現(xiàn)異常時(shí)，就無法更新數(shù)據(jù)，其服務(wù)可用性較低。最后，一旦協(xié)調(diào)者與參與者之間網(wǎng)絡(luò)分化，無法提供服務(wù)。

3.4 Paxos 協(xié)議

同樣是強(qiáng)一致性協(xié)議，Paxos 在 CAP 三方面較之兩階段提交協(xié)議要優(yōu)秀得多。Paxos 協(xié)議具有完全的 C，較好的 A，較好的 P。Paxos 的 A 與 P 的屬性與 Quorum 機(jī)制類似，因?yàn)?Paxos 的協(xié)議本身就具有 Quorum 機(jī)制的因素。

首先，無需贅述，Paxos 協(xié)議是一種強(qiáng)一致性協(xié)議。再者，Paxos 協(xié)議只有兩種情況下服務(wù)不可用：一是超過半數(shù)的 Proposer 異常，二是出現(xiàn)活鎖（2.8.4 ）。前者可以通過增加 Proposer 的個(gè)數(shù)來降低由于 Proposer 異常影響服務(wù)的概率，后者本身發(fā)生的概率就極低。最后，只要能與超過半數(shù)的Proposer 通信就可以完成協(xié)議流程，協(xié)議本身具有較好的容忍網(wǎng)絡(luò)分區(qū)的能力。

參考：《分布式系統(tǒng)原理介紹》 - 劉杰

總結(jié)

以上是生活随笔為你收集整理的分布式系统原理 之9 CAP 理论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。