CAP Theorem


整理 CAP 理論的筆記。


CAP Theorem

CAP 理論Eric Brewer 在 1999 年的論文中發表的一個猜想:Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Eric Brewer 是加州柏克萊分校的教授,也是 Google VP Infrastructure

論文中第一次提到 CAP 三者的關係,描述如下:

  • 一致性 (Consistency):每次讀取有兩個結果,一種是取得最近寫入的資料,另一種則是得到錯誤
  • 可用性 (Availability):每次請求都能獲得一個 (非錯誤)回應,但不保證返回的是最新寫入的資料
  • 分區容錯 (Partition tolerance):任意數量的訊息被節點間的網路丟失 (或延遲),系統仍繼續運行。

論文的結論是:

分散式系統裡,CAP 三者無法同時被滿足,只能擇其二。

2003 年由 Seth Gilbert 和 Nancy A. Lynch 共同發表的論文 Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services 正式證明 CAP 三個關係,確實無法同時兼得。

Consistency

一致性指的是每次客戶端的讀取操作,不管是讀取哪一個節點,結果有兩個:

  1. 都讀到最新的寫入資料
  2. 都是讀取失敗

這兩個是二擇一的結果,沒有模糊地帶。以一個三節點的架構來講:

  1. NodeA, NodeB, NodeC 裡的 X = 1
  2. Client SET X = 9 to NodeA
    • NodeA 同步 X 到 NodeB, NodeC
  3. Client GET X from NodeB
    • Return X = 9

所以一致性這個結果,是對於 客戶端 (Client) 來講。

一致性在單機的狀況,不會有通訊問題;相反的,在叢集架構 (Cluster) 必然就有節點之間的通訊,然後衍伸的問題。

注意:CAP 理論中的 Consistency,不等同於 ACID 中的 Consistency,

  • CAP’s C = sequential consistency, 大概類似於 ACID 的 Atomicity
  • ACID’s C = does the data satisfy schema constraints

資料庫談的 一致性 實際上與交易相關,也就是 ACID 談的概念。

Availability

延續一致性的描述,可用性 是以單位時間之內,系統可以提供給客戶端的服務,也就是承諾客戶在可用的時間範圍之內,會盡力提供服務。

例如最常聽到的就是 SLA 強調可用性是 99.95%,代表的是一年之內系統可以正常服務的承諾時間比例。換言之,系統有 0.05% 的時間之內的不可用,是可以接受的。

可用性通常透過 冗余 (Redundant) 的方式,像是提供至少兩個以上的節點。

透過冗余達到的可用性,但因為等於是多節點,所以就會回到資料一致性的問題,這是個剛柔並濟的問題。

Partition tolerance

Partition tolerance 中文稱為 分區容錯,分區可以有以下意思:

  • 節點在不同地理位置,以資料中心做分區的單位:例如台北與高雄兩地資料中心的分區。
    • Node A 在 192.168.10.0/24 網段裡,Node B 在 192.168.20.0/24 網段裡。
    • Node A 在台北機房,Node B 則在高雄機房。
    • 兩端機器透過 Public IP 直接資料交換
  • 運算節點在同一個地理位置的區域網路
    • Node A 和 Node B 都在 192.168.10.0/24 網段裡。
    • Node A 和 Node B 都在台北機房
    • 兩個區域網路透過內部高速網路骨幹與 Switch 串接起來。
  • 運算節點在不同的地理位置,但是屬於內網架構
    • Node A 在 192.168.10.0/24 網段裡,Node B 在 192.168.20.0/24 網段裡。
    • Node A 在台北機房,Node B 則在高雄機房
    • 兩個區域網路透過內部網路骨幹 (Backbone) 串接起來,例如走 MPLS、或者 AWS Direct Connect.

Partition 中文為分區的意思,通常指的是 資料 分散在不同的運算節點。Partition 在不同的架構裡,會有其他類似的用詞,例如 Sharding (分片),通常指的是資料的分片,同一份資料,被切成幾塊,散落在不同的區域 (Partition)。這時候的 Partition 的意思指的是運算單元的區塊。

除了資料在不同的區域,也可以說是 運算節點 在不同的區域。在 AWS 的架構實踐原則,MultiAZ 就是種分區容錯的概念,也就是每個運算單元,至少同時有兩個以上的 Instance 跑在兩個 Available Zone (可用區域)。AZ 是在十公里範圍的資料中心而言,更大範圍就是跨地區 (Regional) 的 Partition,例如東京到奧勒剛兩的地區的資料同步。

分散式系統的本質是利用多台電腦,透過網路串聯的方式,達到 n 倍的線性效能、容量。很多人會說 CAP 理論中的 CA 不存在,因為沒有了 Partition 的概念,就等於單機,就不是分散式系統了。所以在一個分散式系統中,Partition tolerance 是必要的,那麼剩下的就是 CP、AP 的選擇了,他們個別考慮的是一致性與可用性。

二擇一

下圖則是 w3resource 在其文件中描述 NoSQL 時提到的 CAP 的關係,與其他實作的概念:


Source: https://www.w3resource.com/mongodb/nosql.php

CAP 的排列組合:

  • CA (consistency + availability)
    • 不考慮分區容錯問題,也就是單機模式,等於不考慮分散式架構
      * 通常單機是的 RDBMS 就是 CA 的概念。
  • CP (consistency + partition tolerance)
    • 優先考慮資料的 強一致性,也就是 ACID
    • 透過 Paxos 演算法、Raft … 達到強一致性共識演算法。
    • 屬於 分散式交易,通常透過 剛性事務 機制。
    • 著名的實作:etcd、Consul、CockroachDB
  • AP (availability + partition tolerance)
    • 關注可用性,也就是水平擴展的能力,這概念是巨型分散式系統架構的理論基礎。
    • 用柔性事務達到 最終一致性,背後依循的是 BASE 理論,TCC、Message Queue 都是實踐方式。
    • 透過 Gossip ProtocolQuorum NWR、TCC、ZAB 等協議,達到最終一致性。
    • 最著名的實作:DynamoDB、Cassandra

Transactions Across Datacenters

Google I/O 2009 Transactions Across Datacenters 整理一了張很有意思的結論,如下圖:

CAP 十二年後:CA 理論

CAP 理論出現後,在網路上分成兩派,很多人覺得不應該 分區容錯 當作變因,因為在區域網路 (LAN) 裡面,很少會發生這樣的問題,在廣域網路 (WAN) 才會有這樣的現象。12 年後 (2012),Eric Brewer 修訂 CAP 的定義,發表論文: CAP Twelve Years Later: How the “Rules” Have Changed,其中 Why "2 of 3" is missleading 段落中說明了某些分區在極少發故障的狀況下,CAP 三者是可以順暢的配合。

同年,證明 CAP 猜想的 Seth Gilbert 和 Nancy A. Lynch,也發表論文修正: Perspectives on the CAP Theorem, 重點如下:

  • CAP 理論的證明侷限在 原子性讀寫場景中,並聲明不支援資料庫交易的場景。
  • 分區容錯歸納為既定的網路環境條件,並非獨立的選擇條件

延伸閱讀

參考資料




Comments