分布式系统的 CAP 定理

你的名字 2022-05-17 06:00 188阅读 0赞

CAP定理指出，在一个分布式系统中，对于一致性、可用性、分区容错这三个特性，不可能同时满足，而是必须有所舍弃。我们设计分布式系统时，必须在三者之间（尤其是一致性和可用性之间）有所取舍和平衡。  
  
**作者：**王克锋  
**出处：**[https://kefeng.wang/2018/08/01/distributed-cap/][https_kefeng.wang_2018_08_01_distributed-cap]  
**版权：**[自由转载-非商用-非衍生-保持署名][-_-_-]，转载请标明作者和出处。

## 1 概述 ##

### 1.1 概念 ###

CAP定理(CAP theorem)，又被称作布鲁尔定理(Brewer's theorem)，是分布式系统中的一个基本定理。  
它指出任何分布式系统(Distributed System)中，最多具有一致性、可用性、分区容错这三个特性中的两个。  
也就是说，三个特性无法兼顾，必须有所取舍。  
![relations.jpg][]

### 1.2 历史 ###

*  1998年，加州大学(University of California)的计算机科学家埃里克·布鲁尔(Eric Brewer)提出该原理，并于次年出版；
 *  2000年，Eric Brewer 在的分布式计算原则研讨会(Symposium on Principles of Distributed Computing)上提出该猜想；
 *  2002年，麻省理工学院(MIT)的赛斯·吉尔伯特和南希·林奇发表了布鲁尔猜想的证明，使之成为一个定理。

## 2 三个特性 ##

### 2.0 初始状态 ###

我们假定一个非常简易的、只有 G1/G2 两台服务器构成的分布式系统：  
G1/G2 之间可以相互通信，两者都有相同的变量v，初始值都是v0。  
客户端 C 与 G1/G2 都可以通信，读写操作可以从 G1/G2 中任选。

初始状态，如下图：  
![distributed-init.png][]

客户端读取，如下图：  
![distributed-read.png][]

客户端写入，如下图：  
![distributed-write.png][]

### 2.1 一致性(Consistence) ###

一致性是指，各节点的数据保证一致（每次成功写入之后，无论从哪个节点读取，都能读取到最新数据），相当于向所有节点的写操作是原子操作（要么全部失败要么全部成功）。一致性有三种策略（CAP指的是强一致性）：

*  强一致性：写操作完成后，后续的读操作都能看到最新数据；
 *  弱一致性：能容忍部分或全部都看不到最新数据；
 *  最终一致性：经过一段时间后，都能看到最新数据。

不一致的情形，写操作至G1，但未（或尚未）同步至G2，就从G2读读取。如下图：  
![consistency-false.png][]

一致的情形，写操作至G1，成功同步至G2之后，才允许进行读操作。如下图：  
![consistency-true.png][]

### 2.2 可用性(Availability) ###

可用性是指，每次向未崩溃的节点发送请求，总能保证收到响应数据（允许不是最新数据）。  
参照前面“一致性”中的两种情形，可见一致性和可用性无法兼顾：

*  若要保证一致性：则必须进行节点间数据同步，同步期间数据锁定，导致期间的读取失败或超时，破坏了可用性；
 *  若要保证可用性：则不允许节点间同步期间锁定，这又破坏了一致性。

### 2.3 分区容错(Partition tolerance) ###

分区容错是指，容许节点 G1/G2 间传递消息的差错（延迟或丢失），而不影响系统继续运行。  
分布式系统中，必须满足 CAP 中的 P，此时只能在 C/A 之间作出取舍。

CAP 经常被误解为“三选二”，但实际上必须满足P，然后在 C/A 之间做出选择。

## 3 CAP 的证明 ##

反证法。假设可以同时满足一致性、可用性、分区容错这三个特性，由于满足分区容错，可以切断 G1/G2 的连线，如下图：  
![prove.png][]

*  当 C 把 v1 写入 G1 后，由于可用性，G1 必须成功响应（由于 G1/G2 不通，G2 仍旧是 v0）；
 *  然后，C 向 G2 读取数据，由于可用性，G2 必须成功响应，但响应的值是陈旧的 v0；
 *  可见，C 写入了 v1，但读到了 v0，没有满足一致性，可见三个特性不可能同时满足。

## 4 CAP 的应用 ##

CAP 理论，被看成分布式系统（尤其是分布式存储）的理论基础。

*  舍弃P(选择C/A)：单点的传统关系型数据库 DBMS(MySQL/Oracle)，但如果采用集群就必须考虑P了；
 *  舍弃A(选择C/P)：是分布式系统要保证P，而且保证一致性，如 ZooKeeper / Redis / MongoDB / HBase；
 *  舍弃C(选择A/P)：是分布式系统要保证P，而且保证可用性，如 CoachDB / Cassandra / DynamoDB。

对于一个分布式系统来说，CAP三者中，

*  P是基本要求，只能通过基础设施提升，无法通过降低 C/A 来提升；
 *  然后在 C/A 两者之间权衡。

一个还不错的策略是：保证可用性和分区容错，舍弃强一致性，但保证最终一致性，比如一些高并发的站点（秒杀、淘宝、12306）。最终近似于兼顾了三个特性。

## 5 参考资料 ##

[WikiPedia - CAP theorem][]  
[CAP理论十二年回顾：”规则”变了][CAP]  
[An Illustrated Proof of the CAP Theorem][]  
[Gilbert and Lynch’s paper - Perspectives on the CAP Theorem][Gilbert and Lynch_s paper - Perspectives on the CAP Theorem]

[https_kefeng.wang_2018_08_01_distributed-cap]: https://kefeng.wang/2018/08/01/distributed-cap/
[-_-_-]: https://creativecommons.org/licenses/by-nc-nd/3.0/deed.zh
[relations.jpg]: /images/20220517/e78aab4c781a4ec499d596907d741504.png
[distributed-init.png]: /images/20220517/28790e1c6087418c98f66bec0e56e380.png
[distributed-read.png]: /images/20220517/c3622b42310448c2b7d69cbc3e276ae8.png
[distributed-write.png]: /images/20220517/e708854fd16347aeb2d28bba79f9ec5e.png
[consistency-false.png]: /images/20220517/ecfe46efbc7e41b98370b9a83c51d7fd.png
[consistency-true.png]: /images/20220517/8ae31e1ec4fa48298f562d45d1162b1b.png
[prove.png]: /images/20220517/d7d4a620c87140539c6244e986efc340.png
[WikiPedia - CAP theorem]: https://en.wikipedia.org/wiki/CAP_theorem
[CAP]: http://www.infoq.com/cn/articles/cap-twelve-years-later-how-the-rules-have-changed
[An Illustrated Proof of the CAP Theorem]: https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/
[Gilbert and Lynch_s paper - Perspectives on the CAP Theorem]: https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf