# 1-1. Perspectives on the CAP Theorem
:::warning
**目的：** 回顧CAP定理的基本概念與背景，分析CAP定理對於分散式系統設計與實現的具體影響，並介紹實際案例來討論關於CAP定理取捨的實際影響。
:::
## 1. Introduction
CAP定理揭露了一個在分散式計算中通常會遇到的難題：在一個不可靠的分散式系統中，無法同時保證 Safety 和 Liveness。
* **Safety ：** 所有回應對客戶端而言都是正確的(可以想成是 Consistency)
* **Liveness ：** 系統最終都會對請求給予回應，即使系統中可能發生一些錯誤事件 ( 可以想成是 Availability)

因此，分散式系統的設計者需要在一致性與可用性間做出取捨，針對需應用的場景決定要強調一致性還是可用性，或是兩者各半，嘗試找到最佳平衡點。

本篇論文會先討論CAP定理的正式定義，接著探討CAP定理如何適用於 Safety 和 Liveness 之間的取捨框架，再討論這些取捨的實際影響和對應策略，最後總結並討論在CAP定理下的新方向。

## 2. The Cap Theorem
* **consistency:** 每個server根據服務規範對每個請求返回正確的回應，不同的服務可能有多個正確的回應。
* Trivial services：無需服務器間協調，不適用CAP定理。
* Weakly consistent services：為了不犧牲可用性而開發，如分散式的web cache。
* Simple services：具有直接正確性的要求，線性操作，服務在單一中心化的server上照順序執行，例如集中式server維護某種狀態，每個請求按順序處理，更新狀態並回應。
* Complicated services：需要更複雜的協調和交易語義。
* **Availability:** 系統保證對每個請求最後都有回應。
* **Partition Tolerance:** 系統應該能在出現網路分區時繼續運行。

CAP定理指出，在面對網路分區和通訊失敗時，無法創建一個能夠同時實現線性讀/寫共享記憶體，並保證對每個請求都有回應的分散式系統。因為在分區情況下，server分為好幾組無法通信的集合，導致無法判斷應返回哪個值，而無法保證一致性。但即使在無分區的情況下，由於消息可能延遲或丟失，也可能返回不正確的響應，所以即使沒有分區，也無法保證一致性。因此，在分散式系統中，開發者必須在一致性、可用性和分區容忍之間做出選擇，通常無法全部滿足。

## 3. Theoretical Context
在一個分區系統中權衡consistency和availability是在一個不可靠系統中權衡safety和liveness的特例。
* **Safety:** 聲明**從頭到尾都不會發生任何不好的結果**，也就是說，在每次執行中，每個回應都是正確的。
* **Liveness:** 聲明**最終都會有好的結果**，只要執行時間夠長，最終結果都會是正確的。

我們從上面對safety和liveness的定義中可以明顯看出在一個分區系統中，任何實現atomic讀寫regeister的協議都無法同時保證safety和liveness。

### 3.2 Agreement is Impossibe
consensus：每個process $p_{i}$，以一個初始值$v_{i}$開始，所有process必須就其中一個達成共識。共識演算法是達成Strong Consistency的一種做法，要滿足共識演算法有以下三個條件：
* **agreement(一致性):** 當演算法完成時，每個process(節點)需要輸出相同的值，也就是需要做出相同的決定，不再變動，也稱為safety。
* **validity(有效性):** 每個輸出的值必須是某個process的輸入值，也就是說最終結果一定是來自某一個節點的值，也稱為safety。
* **termination(終止性):** 最後每個process必須輸出一個值，也就是保證所有參與決策且無故障的節點最終會做一個決定，執行的演算法不會無法終止，也稱為liveness。

共識的不可能性是安全性和活性之間必須折衷的一個重要例子。

consensus 之所以重要，是因為它是建立可靠分散式系統的replicated state machine方法的核心，為了提高可用性，server可能在一組server上進行複製，為了保持一致性，server需要就每次的服務的更新達成一致，特別是針對更新的順序。
由於共識的安全性要求比CAP定理討論的還要嚴格，代表在一個容易發生分割的系統中無法達成共識。也有人證明一個沒有分割的系統也無法達成共識，即使是在沒有任何失敗的情況下，也有可能每一個聲稱的共識協議都無法終止，這表示在共識問題中，即使系統只有一點輕微故障的可能性，安全性和活性也是不可能同時實現的。

### 3.3 Coping with the Safety/Liveness Trade-off for Consensus
在不夠可靠的系統中safety和liveness是不可能的，這邊提出兩個問題做討論。
:::warning
1. **網路同步問題:** 在什麼條件下可以同時實現兩者?需要多少同步程度才能避免固有的折衷?也就是說需要多大的可靠性才能同時實現一致性和可用性?
2. 網路是不可靠的，**能達到的最高一致性水平是什麼**?
:::
#### 3.3.1 Synchrony
如果網路滿足下列條件，即可稱作同步
1. 每個process都有clock，所有clock都是同步的，沒有任一個節點時間偏差是無上限的。
2. 每個訊息都在規定的時間內被傳送。
3. 每個process計算速率都一樣。

可以將完全同步系統想成按輪進行，每一round中每個process都會發送一些訊息，也會接收其他process發送的訊息，並執行一些本地運，在這種情況下，如果最多只有n個server會crash，那只需要執行n+1 round就可以解決共識問題，也就是根本不需要在safety和liveness做折衷。
:::warning
但實際上系統不可能完全同步，因此需要思考在實際運作時，解決共識需要多少同步?
:::
1. Dwork等人提出了**最終同步**的概念，一個系統可能經歷一些同步和非同步的時期，我們稱為**部分同步系統**，但只要它最終穩定並保持足夠長的同步時期，我們就能解決共識。
2. 之後又有人證明至少需要f+2輪同步來解決共識，在同步系統中，不管多少失敗我們都可以解決共識，但在異步系統中，即使只有一個節點失敗，也無法保證能正確結束，因為該節點的失敗是其他節點無法探測且不知的，也就是說從其他節點來看，該故障節點可能只是網路延遲或是該節點運算較慢。然而**在最終同步系統中只要< n/2個失敗都可以解決共識**(n是server數量)，所以現在大多共識的實作都是做給最終會同步的系統。
#### 3.3.2 Consistency
:::warning
在一個有f個失敗的系統中，我們能保證的最大一致性是甚麼?
:::
Chaudhuri提出集合協議，和共識問題相似，每個進程開始時都有一個值，最終選擇一個輸出，但這邊的輸出允許不同，也就是說在k集合協議中，代表可能有k個不同的輸出，得到一個較弱的一致性保證，在另一片論文中證明了如果最多有k-1個失敗，k-set的共識是可以被解決的，換句話說，**如果你想確保可用性，k集合協議就是你在有k−1個失敗的系統中能得到的“最多”的協議。**

## 4. Practical Implications
為了能成功構建和部署分散式系統，在處理不可靠的網路時，除了選擇犧牲可用性或犧牲一致性(因為CAP定理告訴我們，我們幾乎不可能在易分區的網路中同時實現一致性和可用性)，在實踐中經常出現另一種方法是：將一個較大的系統分割成不同的子系統，每個子系統可能選擇不同的折衷方案。
### 4.1 Best Effort Availability
在面對不可靠網路時，最常見的做法是設計一種無論如何都能保證一致性的服務，確保操作的正確性，該服務優化為提供最佳努力可用性，當所有運行服務的服務器位於同一數據中心時，這個方法是很常見的，其中一個常見的例子就是google開發的Chubby
* **Chubby Lock Service：** 支持Google文件系統、BigTable等，提供**強一致性**，其核心是一個基於主從設計的分散式資料庫，通過使用 replicated state machine協定（特別是Paxos）來維持同步logs，確保server間的一致性，只要不超過一半的server失敗，Chubby就能夠繼續運作。每個Chubby單元都被部署在單一資料庫中心，Chubby單元內的溝通通常是快速且可靠的，而且主服務器的失敗不太頻繁，所以這種設計對於Chubby來說是很好的。
### 4.2 Best Effort Consistency
當應用被部屬在廣域的網路上而不是數據中心內時，強一致性服務所能達到的可用性水平可能會迅速下降。這種情況下會選擇犧牲一致性，來保證任何時候都有回應，即使結果不一定正確。
* **Web Cache：** 網頁內容（例如圖片和影片）被緩存在全球數據中心的server上，每當用戶請求特定網頁時，內容可以從附近的網頁緩存中提取，緩存服務器與終端用戶的接近性確保了響應的迅速，也很少會因為網路連接問題而影響回應。不過就無法保證所有使用者在任何給定時間訪問網頁時都接收到完全相同的內容，緩存服務只能盡力提供最新的內容。會做這樣的折衷是因為瀏覽網頁的使用者不一定需要強一致性，在網頁中如果服務中斷可能帶來更大的不便。
### 4.3 Trading Consistency for Availability
這邊嘗試更精確地調整一致性和可用性之間的取捨。例如，對於某些內容來說，慢一小時才同步資訊可能是可以接受的，但慢一天則不行。只要最近的網路連接良好（例如在過去的一小時內），我們應該能夠在保持良好可用性的同時，提供這種程度的一致性，如果存在長時間的分割（例如超過一天），那麼保持可用性將是不可能的。這樣的系統既不提供強一致性，也不保證可用性，但如果存在重大網路分割，服務可能仍然無法使用。
* **航空預訂系統：** TACT工具包的一個應用，當飛機上的大多數座位都可用時，預訂系統通常可以依賴於之前的數據來回應，因為還有很多座位，當有新的預訂時也很容易被接納。但隨著飛機座位的填滿，預訂系統需要越來越準確的數據，以確保飛機不會超額預訂，使用TACT，預訂系統可以隨著可用座位數量的減少而要求越來越高的一致性水平。
### 4.4 Segmenting Consistency and Availability
許多系統並非僅有單一統一的要求，可能系統的某些部分需要強一致性，其他部分則需要高可用性，下面舉出系統可能被分割的一些維度。
* **資料分割：** 不同類型的資料需要不同程度的一致性，例如一個購物平台可能需要一個很強的可用性，能夠快速給使用者回饋，但是在結帳、帳單、運輸的部分則必須是強一致的，因為若最後的收到的物品和她原本下訂的不同，會讓使用者體驗感覺很差。
* **操作分割：** 不同類型的操作模式需要不同程度的一致性，在一個系統中，對於只需讀而不會更改任何資料的操作會保證高可用性，但在網路分割的時候，修改資料庫的操作就不會被回應，也就是沒有那麼高的可用性。像是在一個「查詢」的操作中，保證高可用性，但在一個「購買」操作中則需要保證高一致性。
* **功能性分割：** 將服務劃分成不同的子服務，每個子服務可能有不同的需求，像是4.1提到的服務Chubby中，其中一個子服務用來處理coarse-grained locks和分散式協調，在這個子服務中，有高一致性，除此之外，也提供像是DNS的服務來處理命名，在這個子服務中，這邊就提供較弱的一致性但有高可用性。
* **使用者分割：** 在面對網路性能挑戰時，一些服務將他們的基礎設施分散在各地，從而保證不同地理位置的使用者都能有好的服務體驗。例如Craigslist將server設置於美國的東岸和西岸，讓加州的用戶連接到西岸數據中心，這樣不僅提升了服務的可用性，還能確保數據的一致性，東岸的請求也是如此。除此之外，社交網路也會考慮地理因素，確保朋友圈的高可用性。
* **階層式分割：** 一些app是按階層組織的，在最上層可能包括全世界的資料庫，而越往下層會將世界分成地理位置上的小片段或資料庫的小部分，在不同階層須提供不同程度的可用性及一致性，看是讓子節點有較高的可用性還是讓根節點有較低的一致性。

## 5. The CAP Theorem in Future Systems
CAP定理展示了一個在容錯系統中safety與liveness的取捨，雖然目前已經探索了各種解決方案，但隨著網路技術的快速演進，對於CAP定理的理解和應用也需要隨之進化。
* **可擴展性：** 因網路技術變化快速，系統設計需要考慮到未來的成長，但強一致性協議可能難以有效擴展。
* **抵禦攻擊：** CAP定理主要針對網路分區問題，但現在網路面臨更嚴重的攻擊，如DDoS，這些攻擊並非單純的網路分區，而需要不同的理解方式來處理一致性與可用性的取捨。
* **移動無線網路：** CAP定理原先是針對廣域網路服務，但現在越來越多的物聯網流量來自移動裝置，而移動網路中的取捨問題可能更難解決，因為無線通訊非常不可靠。