CAP定理

一个分布式系统只能满足三个特性其中两个的定理

理論計算機科學中,CAP定理(CAP theorem),又被稱作布魯爾定理(Brewer's theorem),它指出對於一個分佈式計算系統來說,不可能同時滿足以下三點[1][2]

  • 一致性(Consistency) (等同於所有節點訪問同一份最新的數據副本)
  • 可用性Availability)(每次請求都能獲取到非錯的響應——但是不保證獲取的數據為最新數據)
  • 分區容錯性英語Network partitionPartition tolerance)(以實際效果而言,分區相當於對通信的時限要求。系統如果不能在時限內達成數據一致性,就意味着發生了分區的情況,必須就當前操作在C和A之間做出選擇[3]。)

根據定理,分佈式系統只能滿足三項中的兩項而不可能滿足全部三項[4]。理解CAP理論的最簡單方式是想像兩個節點分處分區兩側。允許至少一個節點更新狀態會導致數據不一致,即喪失了C性質。如果為了保證數據一致性,將分區一側的節點設置為不可用,那麼又喪失了A性質。除非兩個節點可以互相通信,才能既保證C又保證A,這又會導致喪失P性質。

歷史

編輯

這個定理起源於加州大學柏克萊分校(University of California, Berkeley)的計算機科學家埃里克·布魯爾在2000年的分佈式計算原理研討會英語Symposium on Principles of Distributed Computing(PODC)上提出的一個猜想[5]在2002年,麻省理工學院MIT)的賽斯·吉爾伯特英語Seth Gilbert南希·林奇英語Nancy Lynch發表了布魯爾猜想的證明,使之成爲一個定理[1]

吉爾伯特和林奇證明的CAP定理比布魯爾設想的某種程度上更加狹義。定理討論了在兩個互相矛盾的請求到達彼此連接不通的兩個不同的分佈式節點的時候的處理方案。

參考文獻

編輯
  1. ^ 1.0 1.1 Nancy Lynch and Seth Gilbert, 「Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services」頁面存檔備份,存於互聯網檔案館), ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.
  2. ^ "Brewer's CAP Theorem"頁面存檔備份,存於互聯網檔案館), julianbrowne.com, Retrieved 02-Mar-2010
  3. ^ CAP理论十二年回顾:"规则"变了. InfoQ. [2014-08-28]. (原始內容存檔於2014-09-03). 
  4. ^ "Brewers CAP theorem on distributed systems"頁面存檔備份,存於互聯網檔案館), royans.net
  5. ^ Eric Brewer, "Towards Robust Distributed Systems"頁面存檔備份,存於互聯網檔案館

外部連結

編輯

參見

編輯