Published on

[系統設計筆記] CAP 定理

Authors
  • avatar
    Name
    Vic Chen
    Twitter

前言

在系統設計面試中，很常會需要先跟面試官討論一個基礎問題：「這個系統在 Consistency、Availability、Partition Tolerance 之間要怎麼取捨？」
這就是著名的 CAP 理論。如果對這個理論沒有清楚的理解，會很難解釋為什麼要選某種資料庫或某種系統架構。

什麼是 CAP 定理？

在一個分散式系統中，不可能同時完全滿足以下三個特性：

  1. Consistency（一致性）
  • 所有的節點在同一時間看到的資料都相同。
  • 當某個節點寫入新資料後，所有節點的讀取都會返回更新後的值
  1. Availability（可用性）
  • 每個非故障節點的請求都能收到回應**（但不保證回應是最新的資料）**。
  • 即使部分節點失效，系統仍能對外提供服務。
  1. Partition Tolerance（分區容錯性）
  • 當網路分區（Partition）發生時，系統仍能繼續運作。

IMPORTANT

分散式系統一定要面對網路不可靠，因此 P 幾乎是必須的。

為什麼不能三者兼得？

分散式系統無法同時達到 C + A + P，只能在 網路分區發生時 在 C 與 A 之間做取捨。

  • 如果要 Consistency + Partition Tolerance (CP)

    • 系統會犧牲可用性，在網路分區時，寧願拒絕請求也要保持一致性。
    • 例子：Zookeeper、HBase。

  • 如果要 Availability + Partition Tolerance (AP)

    • 系統會犧牲一致性，在網路分區時，允許不同節點回傳不同的結果，之後再達成最終一致性。
    • 例子：Cassandra、DynamoDB。

  • 如果要 Consistency + Availability (CA)

    • 理論上只能在單機或沒有分區的情況下成立。
    • 例子：傳統的單體資料庫（MySQL 單節點）。

何時選擇一致性 (Consistency)？

某些系統必須優先一致性，即使犧牲可用性：

  1. 訂票系統：避免同一座位被重複預訂
  2. 電商庫存：避免庫存被超賣
  3. 金融系統：確保交易和價格資訊即時且正確

何時選擇可用性？

大多數系統可以容忍短暫不一致時，應優先可用性，並採用最終一致性（Eventual Consistency）

  1. 社群媒體：個人資料更新後，其他人暫時看到舊資料沒關係
  2. 內容平台（如 Netflix）：電影描述暫時沒更新，不影響使用
  3. 評論網站（如 Yelp）：餐廳營業時間短暫過時比無資料好

NOTE

判斷標準是：「用戶短暫看到不一致資料會造成災難嗎？」 Yes -> 選一致性 No -> 選可用性

CAP 定理在系統設計面試上的應用

在系統設計面試中，CAP 定理是討論 Non-functional requirements 的起點。你需要問：「這個系統要優先一致性還是可用性？」

如果優先「一致性」

  • 分散式交易（Distributed Transactions）：透過 2PC（二階段提交）等協議，確保多個資料庫儲存同步一致，但會增加複雜度和延遲。
  • 單一節點方案（Single-Node Solutions）：採用單一資料庫，完全避免資料傳播問題，雖然犧牲了擴展性，但有單一真值來源（Single source of truth）。

技術選擇：

  • 傳統關聯式資料庫（PosgtreSQL, MySQL）
  • DynamoDB（強一致性模式）

如果優先「可用性」

  • 多副本架構（Multiple Replicas）：透過非同步複製擴產讀取副本，即是資料稍有延遲，也能從任一副本讀取，提升讀取效率與可用性，但可能出現過時資料。
  • 變更資料截取（Change Data Capture, CDC）：利用 CDC 追蹤主資料變更，非同步地將更新傳播到副本、快取等其他系統。這讓主系統保持高可用性，資料最終會同步（Eventual Consistency）

技術選擇：

  • Cassandra
  • DynamoDB（可多用區配置）
  • Redis clusters

NOTE

大多數現在分散式資料庫都能配置一致性或者可用性，關鍵是根據需求選擇

進階 CAP 定理考量

隨著系統複雜度的增長，一致性和可用性之間的選擇並非總是二選一。現代分散式系統通常需要根據功能和 use case 採取不同的方法。

1. Ticketmaster

  • 訂座位：強一致性，避免重複預訂
  • 瀏覽活動資訊：可優先可用性，資料過時沒關係

在面試時，可以說對於票卷系統，會優先考慮預定交易的一致性，但會優化用戶瀏覽和查看活動時的可用性。

2. Tinder

  • 配對功能：需一致性，雙方同時滑右要立即看到配對
  • 瀏覽個人資料：可優先可用性，暫時看到舊的照片和資訊沒關係

在面試時，可以說對於約會應用系統，會優先考慮匹配時的一致性，但會優化在查看個人資料時的可用性。

一致性模型的不同層級

在討論 CAP 定理的一致性時，通常指的是強一致性（所有讀取都反應最新的寫入），然而去了解一致性模型的不同層級，可以幫助做出更細緻的設計決策

  • 強一致性（Strong Consistency） 每次讀取都獲得最新的寫入，這是效能成本最高，但對於如銀行帳戶餘額等，需要絕對正確性的系統是必要的。

  • 因果一致性（Causal Consistency） 相關事件會以相同的順序顯示給所有使用者，確保對用戶的順序一致，例如：留言必須出現在貼文之後，確保依賴關係的邏輯順序

  • 讀自己寫一致性（Read-your-own-writes Consistency） 用戶自己能立即看到剛剛的更新，但其他用戶可能還會看到舊資料。常見於社群平台，讓用戶及時看到自己的個人資料變更

  • 最終一致性（Eventual Consistency） 系統最終會達到一致，但短時間內可能會出現不一致，這是最寬鬆的模式。適用於如 DNS 等暫時不一致可接受的系統，也是大部分分散式資料庫預設的行為，通常在優先可用性時採用

小結

  • CAP 定理很重要，他決定你系統設計的方向，只要問自己：「每次讀取都需要最新資料嗎？」如果需要，優先考量一致性；否則優先考量可用性。