分布式系统理论之 CAP 定理

什么是 CAP 定理

CAP 由 Eric Brewer) 在 2000 年 PODC 会议上提出，是 Eric Brewer 在 Inktomi 期间研发搜索引擎、分布式 web 缓存时得出的关于数据一致性 (consistency)、服务可用性 (availability)、分区容错性 (partition-tolerance) 的猜想：

It is impossible for a web service to provide the three following guarantees : Consistency, Availability and Partition-tolerance.

C 代表 Consistency 一致性， A 代表 Availability 可用性， P 代表 partition-tolerance 分区容错性。

数据一致性 (consistency)：如果系统对一个写操作返回成功，那么之后的读请求都必须读到这个新数据；如果返回失败，那么所有读操作都不能读到这个数据，对调用者而言数据具有强一致性 (strong consistency) (又叫原子性 atomic、线性一致性 linearizable consistency)
服务可用性 (availability)：所有读写请求在一定时间内得到响应，可终止、不会一直等待
分区容错性 (partition-tolerance)：在网络分区的情况下，被分隔的节点仍能正常对外服务

在某时刻如果满足 AP，分隔的节点同时对外服务但不能相互通信，将导致状态不一致，即不能满足 C；如果满足 CP，网络分区的情况下为达成 C，请求只能一直等待，即不满足 A；如果要满足 CA，在一定时间内要达到节点状态一致，要求不能出现网络分区，则不能满足 P。即 C、A、P 三者最多只能满足其中两个。

论证

如图所示，是我们证明 CAP 的基本场景，网络中有两个节点 N1 和 N2，可以简单的理解 N1 和 N2 分别是两台计算机，他们之间网络可以连通，N1 中有一个应用程序 A，和一个数据库 V，N2 也有一个应用程序 B 和一个数据库 V。现在，A 和 B 是分布式系统的两个部分，V 是分布式系统的数据存储的两个子数据库。

fb6d8e8e-1cc2-4ab2-8691-6010d8a4c0cd

在满足一致性的时候，N1 和 N2 中的数据是一样的，V0=V0。
在满足可用性的时候，用户不管是请求 N1 或者 N2，都会得到立即响应。
在满足分区容错性的情况下，N1 和 N2 有任何一方宕机，或者网络不通的时候，都不会影响 N1 和 N2 彼此之间的正常运作。

如图所示，这是分布式系统正常运转的流程，用户向 N1 机器请求数据更新，程序 A 更新数据库 V0 为 V1。分布式系统将数据进行同步操作 M，将 V1 同步的 N2 中 V0，使得 N2 中的数据 V0 也更新为 V1，N2 中的数据再响应 N2 的请求。

04910e6c-a768-4b8c-b9a0-0149006803d4

根据 CAP 原则定义，系统的一致性、可用性和分区容错性细分如下：

一致性：N1 和 N2 的数据库 V 之间的数据是否完全一样。
可用性：N1 和 N2 的对外部的请求能否做出正常的响应。
分区容错性：N1 和 N2 之间的网络是否互通。

这是正常运作的场景，也是理想的场景。作为一个分布式系统，它和单机系统的最大区别，就在于网络。现在假设一种极端情况，N1 和 N2 之间的网络断开了，我们要支持这种网络异常。相当于要满足分区容错性，能不能同时满足一致性和可用性呢？还是说要对他们进行取舍？

bcf62eb4-d42e-4380-95de-dd4bdad228d8

假设在 N1 和 N2 之间网络断开的时候，有用户向 N1 发送数据更新请求，那 N1 中的数据 V0 将被更新为 V1。由于网络是断开的，所以分布式系统同步操作 M，所以 N2 中的数据依旧是 V0。这个时候，有用户向 N2 发送数据读取请求，由于数据还没有进行同步，应用程序没办法立即给用户返回最新的数据 V1，怎么办呢？
这里有两种选择：

第一：牺牲数据一致性，保证可用性。响应旧的数据 V0 给用户。
第二：牺牲可用性，保证数据一致性。阻塞等待，直到网络连接恢复，数据更新操作 M 完成之后，再给用户响应最新的数据 V1。

这个过程，证明了要满足分区容错性的分布式系统，只能在一致性和可用性两者中，选择其中一个。

权衡 Trade-off

通过 CAP 理论，我们知道无法同时满足一致性、可用性和分区容错性这三个特性，那要舍弃哪个呢？

CA without P

如果不要求 P（不允许分区），则 C（强一致性）和 A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此 CA 的系统更多的是允许分区后各子系统依然保持 CA。

CP without A

如果不要求 A（可用），相当于每个请求都需要在 Server 之间强一致，而 P（分区）会导致同步时间无限延长，如此 CP 也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

AP wihtout C

要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的 NoSQL 都属于此类。

最终一致性

根据 CAP 定理，我们要不是选择 C（一致性）而放弃 A（可用性），就是反过来。但现实世界的情况，往往不是这么地非黑即白。依照不同的商业逻辑与使用情境，在两者间取得平衡的设计是非常普遍的。
举例来说，对于 C（一致性）而言，我们把 CAP 定理所定义的一致性称为 强一致性（strong consistency）。适合处理像是金钱、付款这种对资料同步高度要求的任务。但相对的，扩展性、可用性就会比较局限（想像一下，若数据库的数量持续地增加，同步所有数据的成本也会不断上升）。
与强一致性相对的是所谓的最终一致性（eventually consistency）。当使用者更新某笔资料时，也许因为网路暂时中断或延迟，没有即时同步到另一个资料库。我们还是让其他使用者可以继续存取资料（不是最新的也没关系），但最终，我们保证这笔资料一定会同步（最后的结果还是对的）。