# 1-2 CAP Twelve Years Later How the “Rules” Have Changed

==CAP 定理斷言任何網路共享資料系統只能具備三個理想特性的其二。然而，透過明確處理分區，能夠最佳化一致性和可用性，從而達成三者的某種權衡。==

CAP 讓設計者敞開心胸接受更廣泛的系統和權衡 (trade-offs)，但「三者之二」的簡單陳述容易令人過度簡化特性間錯綜複雜的衝突。實際上 CAP 只明確說明了**在存在分區的情況下實現完美的可用性和一致性是不可能的**。

儘管當存在分區時，設計者仍需在一致性和可用性之間做選擇，但在處理分區和從中恢復的操作中是有彈性的。現代 CAP 的目標應是**最大限度地結合對特定應用有意義的一致性和可用性**。這種方法**結合了分區期間的操作和分區後的恢復計劃**，從而幫助設計者重新思考 CAP 與其所延伸的意義。

## Why “2 of 3” Is Misleading

- 最簡單理解 CAP 的方法就是想像兩個節點在不同的分區：
- 允許至少一個節點能夠更新狀態，導致不一致 -> 放棄 C
- 選擇保有一致性，有一邊的分區需要表現得像是 unavailable -> 放棄 A
- 只有在節點之間可以溝通時才能保有一致性和可用性 -> 放棄 P

:::info
### BASE and ACID
- BASE: Basically Available, Soft state, Eventually consistent
- ACID: Atomicity, Consistency, Isolation, Durability
:::

**「三者之二」的觀點在幾個方面都有誤導性：**
- 當系統未分區時，沒有理由放棄 C 或 A
- 如果使用者因為 P 無法存取服務，則不需要 C 或 A 的選擇
- 設計者可能無法選擇沒有 P
- 在同一系統中可以多次精細的選擇 C 或 A
- 子系統可以做出不同的選擇
- 還可以根據操作甚至涉及的特定資料或使用者而改變
- 三個特性都不是非有即無的
- Availability: 0~100%
- Consistency 有好幾個 level，一致性範圍的概念反應了在某個邊界之內一致性有保障，但之外是不可預測的。
- Partition 也有細微差別

## CAP-Latency Connection

CAP定理的經典詮釋中忽略延遲，但實務上延遲和分區是高度相關的。在超時的時候，程式需要做出分區決策 (partition decision)：

:::warning
- 取消操作，從而降低可用性
- 處理操作，冒著不一致性的風險
:::

嘗試重新通訊？（透過 Paxos 或 two-phase commit）
- 延遲做出決策的時間
- 無限次重試通訊本質上是犧牲可用性選擇一致性

實際上，分區是通訊的時間限制。所以應對延遲的設計問題在於：是否讓兩方在無法通訊的情況下前進。

節點對於是否發生分區沒有全域的認知。有些偵測到分區，有些沒有，偵測到的進入分區模式 (one-sided partition)，限制操作並確保某種程度的 CA，設計者可以根據目標的回應時間設定時間限制，限制嚴格的系統很可能因網路壅塞頻繁而進入分區模式。

## Managing Partitions

挑戰：減輕分區對一致性和可用性的影響。

關鍵是非常明確地管理分區，這種管理方法分為三個步驟：
- 檢測到分區的開始
- 進入分區模式（可能限制某些操作）
- 在通訊恢復時啟動分區恢復

**Partition’s evolution**

進入分區模式的兩種策略：
1. 限制某些操作，降低可用性
2. 記錄有關操作的額外資訊，幫助之後的分區恢復

### Which operations should proceed?

取決於系統必須維護的 invariant。最好的方法是用 **version vector** 記錄兩邊的歷史，向量的元素是一對 (node, logical time) 記錄更新和更新時間，讓系統判斷哪些操作是已經按已知順序、哪些操作是同時執行的。這種因果一致性 (causal consistency) 在設計者選擇專注於可用性的情況下，已被證明為通常是最好的結果。

### Partition recovery

兩個問題需要處理：
- 兩邊的狀態要變成一致的
- 必須對分區模式期間所犯的錯誤進行補償

通常來說，從分區開始時的狀態開始 rolling forward 是比較簡單的。Merge conflicts 可以用人工編輯解決，或是**限制分區模式時的操作以利恢復時能自動 merge state**。延遲有風險的操作是實施此策略的一種相對容易的方法。

**Commutative replicated data types (CRDTs)** 是可在分區後收斂的資料結構，可以用來確保分區期間的所有操作都是可交換的，或是表示 lattice 的值並確保分區時的所有操作都單調遞增到那個 lattice，後者透過移動到每一側值的最大值來收斂狀態，但可能出現刪除的項目再次出現的情況。如果維護兩種集合 (added 和 deleted) 就能避免，兩種集合的合併清理需在沒有分區時操作，但背景的清理不影響可用性的感知。

### Compensating for mistakes

Invariants 可以透過「最後寫入為準」或合併操作、人工升級等方法來修復。目標是避免 abort 使用錯誤資料的 transaction，從而防止 cascading aborts。Compensating transactions 透過將 transaction 分解為 subtransaction (saga) 來平衡一致性和並行性，若要中止較大的 transaction，compensating transaction 會撤銷已提交的 subtransaction 的影響。服務提供者可能不會直接糾正錯誤，而是承認錯誤並採取補償措施。

## Conclusions

系統設計者在**面對分區時不應盲目犧牲一致性或可用性，可以透過謹慎管理 invariant 來最佳化這兩個特性**。隨著 **version vector** 和 **CRDT** 等新技術的引入，這種最佳化應該會變得更普遍。然而，與 ACID transactions 不同，這種方法需要更周到的部署，最佳解方主要取決於服務的 invariant 和操作的細節。