基本介紹
- 中文名：CAP定理
- 外文名：CAP theorem
- 領域：理論計算機科學
- 特性：一致性、可用性、分區容錯性
- 套用：分散式系統
- 原則：只能滿足三項中的兩項
簡介,定理證明,分散式系統,
簡介
CAP定理起源於計算機科學家埃里克·布魯爾在2000年的分散式計算原則研討會（Symposium on Principles of Distributed Computing（PODC））上提出的一個猜想。在2002年，麻省理工學院（MIT）的賽斯·吉爾伯特和南希·林奇發表了布魯爾猜想的證明，使之成為一個定理。吉爾伯特和林奇證明的CAP定理比布魯爾構想的某種程度上更加狹義。定理討論了在兩個互相矛盾的請求到達彼此連線不通的兩個不同的分散式節點的時候的處理方案。理論首先把分散式系統中的三個特性進行了如下歸納：
- 一致性（C）：在分散式系統中的所有數據備份，在同一時刻是否同樣的值。即數據保持一致，在分散式系統中，可以理解為多個節點中數據的值是一致的。同時，一致性也是指事務的基本特徵或特性相同，其他特性或特徵相類似。
- 可用性（A）：在集群（由多個獨立的計算機通過高速的通信網路連線起來的,具有單一系統映象的高性能計算機系統。）中一部分節點故障後，集群整體是否還能回響客戶端的讀寫請求。（可用性不僅包括讀，還有寫）。
- 分區容忍性（P）：集群中的某些節點在無法聯繫後，集群整體是否還能繼續進行服務。
定理證明
一致性：所有在分散式系統上的操作有一個總體上的順序，每一個操作看起來就像是在一個單獨的瞬間完成的。這就要求分散式系統的運行就像是在一個單節點上一樣，在一個時間回響一個操作。
可用性：對於一個可用性的分散式系統，每一個非故障的節點必須對每一個請求作出回響。也就是，該系統使用的任何算法必異步網路
在異步網路模型中，沒有統一時鐘，所有節點僅根據接收到的訊息和本地的計算進行決策。
定理一：在一個異步網路模型中，沒有可能實現一個滿足以下屬性的讀寫數據對象：1、可用性；2、一致性。對於所有對等運算（包括訊息會丟失的）。
證明：假設存在一個算法A滿足這些條件：一致性、可用性、分區容忍性。我們構造一次A的執行，包括一個返回非一致結果的請求。假設網路包含至少兩個節點，那么它可以被分為不相關的非空集合：{G，H}。假設所有G和H之間的通訊訊息都丟失，這是可能的。如果這時在G上有一個寫操作，接著H上有一個讀操作，那么讀操作將無法返回早些的寫操作。
推論一：在一個異步網路模型中，沒有可能實現一個滿足以下屬性的讀寫數據對象：1、可用性，所有對等運算；2、一致性，所有對等運算，但訊息不會丟失。
證明：主要問題是在異步網路模型中一個算法沒有辦法去判斷一個訊息是否丟失或者在傳輸通道中被延遲。因此，如果在運算中不會丟失任何訊息的前提下存在一個能夠保證一致性的算法，那么該算法也能夠在所有運算（訊息可能丟失）情況下保證一致性。這將與定理一矛盾。
部分同步網路：假設一個部分同步的網路模型，在這裡，所有的節點都有一個時鐘，並且所有的時鐘以一個相同的速度增長。然而，這些時鐘並不是同步的，在相同的時間，它們顯示不同的時間值。事實上，時鐘扮演計時器的角色：處理器可以根據本地狀態變數去衡量流逝了多少時間。一個本地的計時器可以用來調度某事件之後的多長時間間隔進行另一個操作。進一步地，假設每一個訊息要么在給定的時間s內到達，要么丟失。並且，所有的節點在給定時間t內處理完一個接收到的訊息。
定理二：在一個部分同步網路模型中，沒有可能實現一個滿足以下屬性的讀寫數據對象：1、可用性；2、一致性。對於所有對等運算（包括訊息會丟失的）。
證明：但是在部分同步模型中，類似與異步模型推論一的結論就不存在了，因此推論一的假設基於節點無法判斷一個訊息是否丟失。而在部分同步模型中，存在部分同步算法可以在所有訊息傳送正常的情況下返回一致性的數據，而僅僅在訊息丟失時返回非一致性數據。對於讀或寫請求，節點傳送一個訊息給另一個節點，如果訊息返回了，那么節點傳送請求的數據；如果訊息在給定的2s+t時間內沒有返回，那么該節點斷定訊息丟失了，節點就可能返回一個不一致的請求數據。須最終終止。當同時要求分區容忍性時，這是一個很強的定義：即使是嚴重的網路錯誤，每個請求必須終止。
分區容忍性：為了定義分區容忍性，假定網路滿足如下條件：網路是可能丟失從一個節點發往另一個節點的任意訊息，當網路被分區（隔斷）時，所有從一個分區的節點發往另一個分區的訊息將會丟失。一致性要求每個回響必須是一致的，即使系統內部的訊息沒有被正確地傳送。可用性要求從客戶端接收請求的任一節點必須被回響，即使任意的訊息可能沒有被正確地傳送。
