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

#### ABSTRACT

CAP無法同時擁有三個特性
* Consistency\(C\)
* Availability(A)
* Partition Tolerance\(P\)

中的兩個，==但過去一直在辯論這是一個誤導，因為過於簡化實際設計的選擇==。現代應用要求在特地情景下最大化`C`以及`A`，通過==制定在partition期間的操作以及之後的recovery，可以跳出CAP的傳統認知與限制==

#### WHY “2 OF 3” IS MISLEADING
* 以兩個nodes來看CAP:
* 一個node更新導致另一個不一致 => `放棄C`
* 保持一致，則partition的另一側則會變不可用 => `放棄A`
* 只有在nodes通訊時才可能同時保有`C` & `A` => `放棄 P`
* ACID & BASE
* ACID四個特性：
* 原子性：不是“確保所有步驟都完全”就是“恢復到原本狀態”
* 一致性：可以確保預先制定的規則，即便有多人操作
* 隔離：transaction不互相干擾
* 耐久：系統故障也會維持已提交的transaction
* BASE三特性：
* 基本上可用：”隨時“可存取
* 軟性狀態：transaction中可能有過渡狀態，而非最終狀態
* 最終一致性：更新完後，紀錄一定一致
* ==ACID強調`C`，因為任一紀錄僅允許一筆交易，難水平擴展==
* ==BASE強調`A`，好擴展，可增加node來增加`A`==
* CAP定理最初以ACID與BASE的對比出現，CAP定理的出現是為了擴展設計空間，進行更廣泛的探索，因此提出了“2 of 3”的概念
* Partition很少發生，故CAP在大部分時間能完美實現`C`和`A`
* Partition發生時，要以三步驟方法來處理
:::success
* 檢測Partition
* 進入Partition Mode來限制一些操作
* Recovery
:::
#### CAP-LATENCY CONNECTION
* ==CAP忽略了延遲，但實際延遲和partition有密切關係==
* 在操作上，CAP timeout時必須選擇一個決策:
* 取消操作以降低`A`(無法響應請求而降低)
* 繼續操作並可能導致失去`C`(可能partition而無法一致)
* 嘗試通信達到`C`，如使用`Paxos`或`兩階段提交`
* 在partition過後透過node間通訊達到`C`
* 只是延遲了決策的時間點
* 無限重試通信即選擇`C`非`A`(因可能使系統長時不可用)
* ==Partition實際上為通信時限，系統如果無法在時限內達成`C`，就表示發生了Partition，必須就當前操作在`C`和`A`之間做出選擇==
* 從這角度出發可以有幾個重要的推論
* 不存在全局的partition，因為有些node可能檢測的到partition，有些不能則認爲系統處於正常狀態
* 可檢測到的node可以進入partition mode來優化，這是優化`C`和`A`的核心部分
* 根據響應時間來設定時限有助於進行優化
* 時限越短則進入partition mode越頻繁，越長優化
* 有時放棄`C`來避免保持`C`所帶來的高延遲是必要的
* Yahoo PNUTS將主副本放在本地，從而降低了延遲
* FB則採相反策略，延遲高但能同步
#### MANAGING PARTITIONS
* ==管理partition挑戰在於減輕對`C`和`A`的影響==
* steps:
:::success
* 檢測partition
* 進入明確的partition mode並限制一些操作
* 通信恢復時啟動partition recovery (為了恢復`C`以及彌補在partition期間的錯誤)
:::

* 進入partition mode後的兩種策略:
* ==限制操作==，如暫停寫的操作，保證`C`但降低`A`
* ==紀錄操作訊息==，幫助recovery，但會增加系統複雜性及延遲。

* **Which operations should proceed?**
* ==取決於系統必須維護的不變量==
* ==設計者必須在partition mode決定是否保持特定不變量，或者違反它，即要在`C`和`A`權衡==
* 更新的順序對`C`很重要，使用一個Version Vector來追蹤node上的歷史，用於確保partition過後的操作合併
* Version Vector可不可排序
* 可排序: 可確定更新順序，更好維護`C`
* 不可排序: 更新可能是同時，或不`C`，更難處理，要給系統判斷

* **Partition recovery**
* Partition延遲一些操作會違反一些不變量，可被系統用歷史來推斷這些
* ==設計者在recovery的過程會有兩個較困難的問題==:
* ==使兩方狀態`C`==
* ==Partition mode時對錯誤補償(兩邊結果不一樣，要如何對這錯誤補償來恢復`C`)==
* 通常在partition mode一開始時，會以某種方式向前滾動兩組的操作，途中保持`C`的狀態，比較容易修復當前狀態
* 大多系統無法始終解決衝突
* 有些系統要==手動解決衝突==
* 離線模式的wiki衝突，需要手動編輯
* 有些系統通過選擇某些操作來==合併衝突==，用限制操作會使更好合併
* Google Docs則是Partition期間限制某些操作，使recovery時更容易合併狀態
* 使用可交換操作是實現自動狀態收斂的最接近方法(操作可以任意交換順序而不影響結果)
* CRDTs在partition後自動收斂，並確保分割期間所有操作都是可交換的，或者將值表示為一個格點，確保所有操作都會對該格點進行單調增加。
* **Compensating for mistakes**
* 修復不變量方法包括
* ==最後寫入者獲勝==(忽略掉某些更新，只保留最後一個)
* ==合併操作==的智能方法or人類協助
* 補償操作目標是終止使用錯誤提交的數據，確保不影響系統
* 可能是撤銷
* 可能是採取一些措施來補償
* 正確性不取決串行化或隔離，更重要是取決於==確保整體系統狀態與輸出不受影響==

#### CONCLUSION
* ==設計者不該盲目的在partition期間犧牲`C`或`A`==。
* ==本文的方法透過partition期間管理不變量來優化`C`和`A`==
* 有Version Vector和CRDT等技術使優化更普遍
* ==最佳解大大依賴不變量以及操作細節==