# 1-1 Perspectives on the CAP Theorem: :::info **最重要的結論** **consistency 資料一致性 availability 可用性 partition tolerate 分割容錯性** ==三者只能取其二，無法同時滿足== ::: ### The CAP Theorem - CAP的定義: - ==**consistency**==: 每個server保證能夠回傳最新的==正確結果== - ==**availability**==: 每個request在任何情況下都能最終得到response（但在現實的系統中就算最終能得到結果，但太久才得到response視為不具availability) - ==**partition tolerate**==: 當出現分區時（封包延遲或遺失、連接中斷、塞車等），系統能夠繼續執行 CAP therorem可以用一句話來概括: In a network subject to communication failures, it is impossible for any web service to implement an atomic read/write shared memory that guarantees a response to every request. ### Theoretical Context - #### Consistent, Availability, and Partition-Tolerance - ==***safety property***==: nothing bad ever happens，也就是說，任何節點在每個execution後結果都是正確的，==consistency屬於safety== - ==***liveness property***==:eventually something good happens，也就是說，只要時間夠長，最終一定會有結果，==availability屬於liveness== 從此觀點來看，容易產生分區的系統是不可能在保證safety & liveness的情況下做到atomic地讀/寫暫存器 - #### Agreement is Impossible :::info Consensus（共識） : 系統中每個process $p_{i}$ 有初始值 $v_{i}$，若要有共識有三個必要條件。 ::: * ==**agreement**==:最終每個process須輸出相同值，也就是每個節點必須有相同的決定 * ==**validity**==:每個process輸出值必定為某個process的輸入值，換句話說，最終的共識來自某一節點 * ==**termination**==:最終一定會有個輸出結果，演算法不會無限的執行下去，能做出最終決定 很明顯，agreement和validity具safety property，而termination具liveness property，也==因此safety property 和 liveness property必須做出取捨。== consensus是建立replicated state machine的關鍵，為了提高availability可能多準備幾個複製節點來備份;為了提高consistency，在每次執行時都會進行更新，必須在每次更新達成一致，尤其是更新的順序。 consensus的safety條件比CAP theroem中更加嚴格;在分散的節點atomic的讀/寫記憶體更加難以實現，引用的論文的結論為即使在沒有分區的系統中，consensus仍舊無法達成，部份protocol 聲稱能達成agreement & validity，但是演算法卻無法停止，無法做出最終決定。 - #### Coping with the Safety/Liveness Trade-off for Consensus 接下來這段主要在探討兩個問題 :::warning 1. 若在***足夠不可靠***的分散式系統中無法同時達成safety & liveness，那能達到上述兩個條件的系統可靠程度要多高？大部分人著手於網路的同步性上，i.e.,網路要多可靠才能同時滿足consistency & availability? 2. 既然網路是不可靠的，那consistency的上限在哪裡？ ::: :::info **Synchrony:** 若網路滿足三個條件即視為同步 1. 每個process都有個自己的clock, 且每個clock是同步的 2. 每段訊息在已知且固定的時間傳輸完畢 3. 每段訊息傳輸速率一致且固定 上述系統是以回合制傳輸的，一回合內能傳輸一些訊息，並接收所有被傳遞的訊息，可能還會做某些local的計算 ::: 若系統完全同步，在最多${f}$個server故障時，只須${f + 1}$回合就能達成共識，但現實系統不可能完全同步，那現實中要多同步才能解決共識的問題？ 因此提出了 ==**部份同步**(**最終同步**)== 概念的系統，也就是說在某段期間可能是不同步的，但沒關係，只要系統穩定的同步運行夠久，最終還是能達成同步，達成共識。近期某些研究證明，此類系統共識保守估計至少需要${f + 2}$回合來達成穩定的同步 此外，在完全同步系統中任何的數量的server故障都能夠解決，在非同步系統只要一個節點失敗共識就不可能達成，部份同步(最終同步)系統，整個系統有${n}$個server，那此系統故障節點==最多只能少於${n / 2}$==，否則無法達成共識 另一種解決方法是 *Failure detectors*，Chandra 和 Toueg 提出並證明failure detector Ω 是解決共識問題的最弱條件，其封裝一個領導者選舉服務，就算某些節點故障了，他也擁有夠多資訊來達成共識，這在實際系統中相當常用，通常稱為 primary/master :::warning 接著探討第二個問題，若系統中有${f}$個節點故障，那我們能達到consistency的最大程度是多少？ ::: Chaudhuri 提出 *set agreement*的概念，和*consensus*不同之處在於最後的輸出值可以不同，以一擁有k個節點的集合為例，${k-agreement}$最多有${k}$個不同的輸出值，有較弱的一致性 *consensus*就是 ${1-agreement}$，另一篇論文證明了 ==${k-agreement}$可以能容忍最多${k - 1}$個節點故障，因此*consensus*無法容忍任何節點故障。== 換句話說，==${k - 1}$個節點故障了，${k-agreement}$就是系統consistency能達成的上限了== ### Practical Implications :::info 既然在容易產生分區的系統中，consistency和availability兩者無法兼得勢必得犧牲一個，我們接著來探討兩者取捨之間的差異。 ::: 有趣的是，實際的系統可能會將大系統切分為多個子系統，子系統可能會有不同的取捨方式，甚至兩者無法保證，但仍舊有不俗的表現。 - **Best Effort Availability** 在網路相當穩定且可靠，不常出現故障，不易產生分區的情形下（e.g.所有節點在同個datacenter)，我們傾向選擇Consistency guarantee、best effort Availability，也就是盡力達成availability但不保證。 Google的Chubby Lock是個典型的例子，Chubby的每個"Cell"都位於同個datacenter，網路相當穩定不易形成分區，因此提供了strong consistenct、high availability - **Best Effort Consistency** 在某些系統中availability是不可割捨的且更需要快速得到response，就算回傳結果未必是最新的也無傷大雅。 Web Cache系統是個典型的例子，由於網頁的使用者位於全球各地，使用者提出了一個request，鄰近的server cache可以快速回傳response給使用者。若cache更新了，但將所有cache更新需要一些時間，不同使用者可能看到不同的網頁內容，雖然內容有點過時了，但沒關係，因為使用者沒有耐心等候網頁更長的載入時間，因此response速度才是最關鍵的，可犧牲一些consistency。 - **Trading Consistency for Availability** Consistency和Availability的取捨需要一些精準的調整，舉例來說對某些服務來說一小時前的舊資料是可以接受的，但無法接受一天前的舊資料，或是前一小時的網路狀況很好，因此我們應該提高consistency的程度，另一方面，若存在一個長時間的分區可能無法達到當初設計的consistency程度 以航班座位預訂系統為例，最初空位比較多，就算consistency程度比較低，資料是過時比較久的也沒問題，但隨著空位越來越少，我們也需要更精準的資料來確定沒有超賣座位，因此需要拉高consistency的標準，這例子就非常需要動態調整consistency的程度。 - **Segmenting Consistency and Availability** 許多系統不只有一個統一的要求，系統的某些部份可能需要strong consistency，另一些可能需要high availability，下面探討一些可能被分割的維度。 * **Data partitioning** : 不同的資料型態可能需要不同程度的consistency and Availability。 以購物平台為例，購物車需要較高的availability以快速回應用戶的requests，偶爾的incosistent是可接受的;商品資訊顯示稍微過時的資訊也沒關係，但是結帳/帳單/購物紀錄需要相當高的cosistent，因為使用者會因為結帳跟當初顯示的資訊不同而生氣。 * **Operation partitioning** : 不同操作可能需要不同程度的consistency and Availability。 舉個簡單的例子，一個資料庫若只進行*讀取*的操作的話，能保證高availability，但在分區存在的時候，對資料進行修改可能沒有回應，就沒有availability可言。 此外，不同類型的update可能需要不同程度的consistency，一個*購買*的操作要guarantee consistency，但在*查詢*的操作，可能回傳過時的資訊。 * **Functional partitioning** : 將service劃分不同的subservice，每個subservice可能有不同的需求。 像前面提及的Chubby在提供coarse-grain locks需要strong consistency，但也有提供另一項服務處理DNS解析，提供相對較弱的consistency但high availability，因此就算是同個服務也可能有不同程度的consistency & availability 的取捨 * **User partitioning** : 網路的分區及性能往往跟實際的地理距離有關，將用戶根據地理位置分群是個明智之舉 像是Craigslist在美國東西岸都擁有datacenter，Craigslist讓加州的用戶連上西岸的server來得到更高的availability，且連上西岸data center的用戶間，能達到更穩定、更高的consistency，東岸也是如此。 某些社群網站也是做類似的用戶分群，因為東岸的用戶往往是和東岸的用戶互動，根據地理距離能更容易達到更好的表現。 * **Hierarchical partitioning** : 某些系統可能會具有階層的組織，可以根據階層來分割 最上層的組織可能是包含全球的資料庫，往下層可能是根據地區分割成更小的資料庫，在不同階層提供不同的consistency & availability ### The CAP Theorem in Future Systems - Scalability : 如果一個系统能輕鬆的增大規模、有效率地利用新資源以處理loading 就具Scalability 因此strongly consistency也會隨著系統規模變大變得更難以達成 - Tolerating attacks : CAP theorem關注的是網路分區，也就是某些Server間可能無法可靠的溝通。 但隨著網路攻擊越來越頻繁，越來越難以忽略，像是每天可能都會有DDOS等攻擊，若系統要考慮這些情況，我們無法簡單將其視為分區來處理，而需要更多的思考理解。 - Mobile wireless networks : CAP Theorem 起初是針對WAN所提出的 時至今日，越來越多的網路流量來自行動裝置，有許多情況的取捨跟之前相同，也有許多需要難以解決需要重新提出解決方案的情境，因為行動網路的特性相當不同，常常發生封包遺失相當頻繁且延遲劇烈變化，根據應用程式可能還要考慮行動裝置的地理位置。