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"页面存档备份,存于互联网档案馆

外部連結

參見