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
一致性指的是每次客戶端的讀取操作，不管是讀取哪一個節點，結果有兩個：
- 都讀到最新的寫入資料
- 都是讀取失敗
這兩個是二擇一的結果，沒有模糊地帶。以一個三節點的架構來講：
- NodeA, NodeB, NodeC 裡的
X = 1 - Client
SET X = 9to NodeA
- NodeA 同步 X 到 NodeB, NodeC
- Client
GET Xfrom 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 Protocol、Quorum 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 理論的證明侷限在 原子性讀寫場景中，並聲明不支援資料庫交易的場景。
- 分區容錯歸納為既定的網路環境條件，並非獨立的選擇條件
延伸閱讀
分散式系統系列文章
- 聊聊分散式系統
- 分散式一致性問題與共識演算法
- CAP Theorem
- Distributed Message Systems
- Eventually Consistent 與 Dynamo NWR 模型
- 淺談分散式交易
- Design Patterns for Distributed Systems
- 分散式系統設計 - 正體中文版翻譯記事
Dapr 系列文章
- 摘要 Dapr 的設計與概念
- Experience Dapr - Hello World
- Experience Dapr - Run on K8s
- Experience Dapr - Secret Store
參考資料
- 左耳朵耗子：分散式系統架構經典資料
- Fallacies of distributed computing
- Google I/O 2009 - Transactions Across Datacenters
Comments
About
著作
演講
AWS Certifications
