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

外部链接

编辑

参见

编辑