前言
在生活充滿互聯網應用的今天，我們每一次點擊的背後可能都是個龐大且復雜的系統，像是搶票系統如何確保大傢可以有快速地搶到票，而且不會重復出售同一張票，或是銀行系統如何確保你的餘額，不會因為連到不同的機房就顯示不同的數字等等，這些系統為了同時服務大量的客戶，都需要依靠分佈式系統以突破單機的瓶頸。
CAP 定理決定了分佈式系統天生上的限制，通過 CAP 定理我們可以理解為什麼共識機制如此復雜，以及系統如何在強一致性與最終一致性間做取舍。本篇會從分佈式系統的挑戰開始，介紹 CAP 定理，以及 CAP 中的三元取舍，希望讀者閱讀後可以對分佈式系統有個思考框架。
分佈式有多難？
不管設計什麼架構，我們都希望滿足 高性能 且 高可用 的系統，為了突破性能的瓶頸，我們從單核走向了多核，從單機走向了多機；為了防止意外造成系統無法運作，我們通過「備份」來對抗各種天災人禍。分佈式的目的就在於 突破單機的性能瓶頸 並 建立不間斷的服務 ，而分佈式設計帶來的好處，恰恰也是分佈式設計的困難點。
試想一個情境，我們使用了某銀行的網絡支付轉帳給朋友，恰巧就在此時，因為某個路段在修路把銀行北京機房對上海機房的光纖網絡挖斷了，造成北京機房已經有這筆轉帳記錄，但上海沒有（如圖一），雪上加霜的是，此時北京機房對外的網絡也意外被切斷了，所以使用者查看轉帳結果時，被導向了上海機房，造成使用者以為轉帳沒有成功再轉了一筆（如圖二），最後光纖網絡修復後，使用者才發現原來有兩筆轉帳的紀錄（如圖三）。
上述情況隻是分佈式可能面臨的其中一種情況，就算網線沒有被挖斷，系統還是會因為網絡延遲造成數據短暫的不一致，現實中有各種不同的意外情況要應對，此時如果我們有一個可以幫助我們思考分佈式系統的思想框架，將會有助於我們設計分佈式系統。
圖一：A 通過北京機房匯錢給 B
圖二：A 通過上海機房匯錢給 B
圖三：節點之間連接修復
分佈式的思考框架 — CAP 定理介紹
Eric Brewer 最早於 1998 年有 CAP 理論的構想，在 2000 年的 PODC[1] 會議上發表這個猜想，2002 年時由 Seth Gilbert 及 Nancy Lynch 證實[2] 了這個猜想，因此 CAP 定理（CAP theorem）又被稱作 Brewer’s theorem。
CAP 定理由一致性（Consistency）、可用性（Availability）及分區容錯性（Partition tolerance）組成，不過由於作者當初提出時，並沒有給這三者明確的定義，因此不同的人對於 CAP 的定義有些分歧，像是 IBM Cloud[3] 上的定義跟 Wiki[4] 的就有些出入。這裡我們使用 Robert Greiner[5] 給的定義，不過光是 Robert Greiner 就定義過兩次 CAP，這裡我們選擇 新的定義[6] 解釋，因為作者已經把 舊的定義[7] 標上 Outdated 了，讀者可以自行比較兩次定義的差異。
CAP 定理
In a distributed system (a collection of interconnected nodes that share data. ), you can only have two out of the following three guarantees across a write/read pair: Consistency, Availability, and Partition Tolerance — one of them must be sacrificed.
首先 Robert 定義適用於 CAP 定理的系統，這個系統必須是一個分佈式系統，不過分佈式系統有很多種，像是有些系統隻涉及邏輯運算，但不涉及數據保存，而有些系統則是兩者都有，因此作者特別表明是要有「共享數據」的分佈式系統。在這個系統內依據 CAP 定理，我們的每一次讀寫頂多 隻能滿足 Consistency、Availability 或是 Partition Tolerance 三者中的兩個 。後面我們會在說明為什麼隻能滿足其中的兩項，這裡我們先看定義。
Consistency
A read is guaranteed to return the most recent write for a given client.
對於一致性，Robert 的定義是：系統必須保證客戶端的讀操作會取得最近更新的數據。作者選擇從用戶的角度而不是從系統的角度描述，原因是每一次事務（Transaction）發生的過程，系統都處於不一致的狀態，所以從系統的角度看，系統是不可能隨時保持一致性的。從用戶的角度，我們可以通過一些設計，像是 Quorum NWR，每一次用戶讀取都至少從 R 個節點讀取，並從中選出最新的數據返回，以此來達成對用戶的一致性。
Availability
A non-failing node will return a reasonable response within a reasonable amount of time (no error or timeout) .
對於可用性，Robert 的定義是：一個健康的節點必須在合理的時間內返回合理的回應。作者使用「合理的」而不是「正確的」來描述回應，原因是系統會面臨各種不能控制的風險，但隻要系統設計合適，在意外發生的情況下還是可以給出合理的回應，那這個系統就具有可用性。
Partition tolerance
The system will continue to function when network partitions occur.
對於分區容錯性，Robert 的定義是 — 在網絡分區的情況下，系統依然能夠繼續運作。在網絡發達的今天，我們的手機幾乎隨時都處於連接的狀態，所以網絡分區對一般用戶比較難想像。
對機房來說，不同機房之間的連接通常是用專門的網線，為了確保機房的網絡穩定及安全性，這些網線是不對外公開的，如果這些網線如果被挖斷，對於機房來說，等於機房跟機房之間的網絡就斷了，所以機房與機房就會產生分區，而在分區的情況下，不同的機房還是可以對外繼續運作的能力，就叫分區容錯性。
在實際設計上，分區容錯代表的不僅是分區的情況下還要繼續運作，還包括連接恢復後，如何同步及修正兩個分區的數據差異，才算完整的達到分區容錯性。
分佈式的不可能三角 — CAP 三元取舍
CAP 定理乍看之下，三個任取兩個都可以，但在現實世界中，網絡是最無法被保證的，所以分區容錯性（P）是一定要被保障的，所以實際設計系統時，我們要在一致性（C）跟可用性（A）之間做取舍。
強一致性 — CP 與 ACID
ACID 是關系型數據庫的基石，代表每次事務（Transaction）需要滿足原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）及持久性（Durability）。CAP 定理是對於系統的描述，而 ACID 是對於事務（Transaction）的描述，雖然兩種對於不同層面描述的理論不應該被放在一起討論，但這裡想強調的是 ACID 是強一致性的描述，如果在分佈式情況下滿足了，也等於滿足了 CP 模型。
分佈式要在系統層面滿足強一致性，通常會使用兩階段提交（Two-Phase Commit, 2PC），通常步驟如下：
- 使用者向協調者（Coordinator）發起一個寫操作
- 準備階段（Prepare Phase）: 協調者向其他所有節點詢問是否可以進行此操作
- 執行階段（Commit Phase）: 若所有節點都回復可以執行操作，則協調者向所有節點發送執行此操作
設計兩階段提交時要註意，在準備階段（Prepare Phase），節點如果回復「允許」進行操作，那麼不管發生什麼意外，節點都要能保證在執行階段（Commit Phase）進行此操作，即使準備階段後，節點因意外關機，節點也要在意外恢復後，也需要依據協調者的指令完成準備階段答應的操作。另外因為是強一致性的關系，所以協調者會在執行階段（Commit Phase）結束才回復使用者，因為如果協調者在準備階段（Prepare Phase）結束就回復給使用者，那可能因為協調者還沒發送執行信息給其他節點前，就意外關機，造成使用者接收到的信息與整個集群不一致。
Prepare Phase
Commit Phase
兩階段操作被應用在許多分佈式算法及系統中，比較出名的像是 MySQL XA[8] 、 Raft[9] 等。在更復雜的情況，使用三階段提交（Three-Phase Commit, 3PC）來解決。
高可用性 — AP 與 BASE
BASE 代表的是基礎可用（Basically Available）、最終一致性（Eventually Consistent）及軟狀態（Soft State），從字面意義就能發現，BASE 以可用性為主，對一致性的要求則比較低，隻要最終狀態是一致性即可，所以滿足了 BASE，基本上就符合 AP 模型。
對於互聯網的用戶來說，如果一個系統不可用，那即使應用內部的狀態有多麼的一致，對用戶來說都是壞掉的，所以我們很常在互聯網應用中看到基礎可用（Basically Available）的手法，以 微博點贊數為例，熱門的貼文剛發表時，就會湧入一堆人按贊，每一次按贊對系統來說都是一次寫入，如果系統為了強一致性讓一部份人暫時無法寫入的話，那大傢一定會覺得是不是系統壞掉了，所以微博並不需要急著統計出一個精確的數字，因為對大多數人來說 8 個贊跟 10 個贊沒什麼區別，隻要系統可以在最後保持最終一致性即可。
不過隻滿足了基礎可用，系統還是要有方法可以恢復最終一致性（Eventually Consistent），常見的做法有讀時修復（Read Repair）、寫時修復（Write Repair）以及反熵（Anti-Entropy）。讀時修復在讀取時同時到多個節點讀取，並以最新的節點為主；寫時修復，同時寫入多個節點，若發現有寫入失敗則記錄下來，定時重傳，直到寫入成功，或是有新的寫入為止；最後反熵則是定期檢查狀態是否一致，如果不一致則通過特定的修復順序，修正每個節點的數據，詳細步驟會在之後講 Gossip 協議時提到。
總結
這次我們介紹了 CAP 定理，以及 CAP 定理應用的模型，如果想對 CAP 定理有進一步的認識，可以看 Eric Brewer 在 2012 年寫的文章 — CAP 定理 12 年來的回顧[10] 。使用 CAP 定理有兩個要註意的地方：
- 首先雖然系統分區（P）的情況並不常發生，但我們一定要為了分區容錯性做準備；反之在沒有分區的情況下，我們要盡力同時達成一致性跟可用性。
- 第二是雖然我們以 CAP 來描述整個系統，但其實系統內可以設計成敏感的數據滿足 CP 模型，不重要的數據則滿足 AP 模型，所以 CAP 定理是可以拉到數據層面來思維的。
最後，理解 CAP 定理是理解分佈式的重要入門，更是了解區塊鏈共識機制的基本觀念，少了 CAP 的概念，可能隻能在方法與步驟上層面上理解共識機制，但有了 CAP 的概念，則可以進一步的探討，算法如何在一致性與可用性之間做取舍。
以上是我對於 CAP 定理的分享，也歡迎大傢分享你們如何理解及應用 CAP 定理！下一篇我們會從近代的共識機制 Raft 算法說起。
參考資料
[1]
PODC: https://en.wikipedia.org/wiki/Symposium_on_Principles_of_Distributed_Computing
[2]
證實: https://dl.acm.org/doi/10.1145/564585.564601
[3]
IBM Cloud: https://cloud.ibm.com/docs/Cloudant/guides?topic=Cloudant-cap-theorem#cap-
[4]
Wiki: https://en.wikipedia.org/wiki/CAP_theorem#cite_note-Brewer2012-6
[5]
Robert Greiner: https://robertgreiner.com/
[6]
新的定義: https://robertgreiner.com/cap-theorem-revisited/
[7]
舊的定義: https://robertgreiner.com/cap-theorem-explained/
[8]
MySQL XA: https://dev.mysql.com/doc/refman/8.0/en/xa.html
[9]
Raft: https://zh.wikipedia.org/zh-hans/Raft
[10]
CAP 定理 12 年來的回顧: https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/