CAP Theorem


整理 CAP 理論的筆記。

CAP Theorem

由 加州柏克萊分校教授 Eric Brewer 在 1999 年的論文中發表:Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services。論文中第一次提到 CAP 三者的關係,描述如下:

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

論文的結論是:分散式系統裡,CAP 三者無法同時被滿足,只能擇其二。下圖則是 w3resource 在其文件中描述 NoSQL 時提到的 CAP 的關係,與其他實作的概念:


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

CAP 常見的排列組合:

  • CA (consistency + availability)
    • RDBMS
    • 2PC (2 Phase Commit, 二階段提交)
  • CP (consistency + partition tolerance)
    • Paxos 演算法
  • AP (availability + partition tolerance)
    • 關注的是 可用性分區容錯
    • [Dynamo][ct5]

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


延伸閱讀 (站內)

參考資料


Comments