CAP定理，又称CAP原则和作布鲁尔定理，指的是在一个分散式系统中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容忍性）这三个基本需求，最多只能同时满足其中的2个。理解CAP理论的最简单方式是想像两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设定为不可用，那幺又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。
基本介绍
- 中文名：CAP定理
- 外文名：CAP theorem
- 领域：理论计算机科学
- 特性：一致性、可用性、分区容错性
- 套用：分散式系统
- 原则：只能满足三项中的两项
简介
CAP定理起源于计算机科学家埃里克·布鲁尔在2000年的分散式计算原则研讨会（Symposium on Principles of Distributed Computing（PODC））上提出的一个猜想。在2002年，麻省理工学院（MIT）的赛斯·吉尔伯特和南希·林奇发表了布鲁尔猜想的证明，使之成为一个定理。吉尔伯特和林奇证明的CAP定理比布鲁尔构想的某种程度上更加狭义。定理讨论了在两个互相矛盾的请求到达彼此连线不通的两个不同的分散式节点的时候的处理方案。理论首先把分散式系统中的三个特性进行了如下归纳：
- 一致性（C）：在分散式系统中的所有数据备份，在同一时刻是否同样的值。即数据保持一致，在分散式系统中，可以理解为多个节点中数据的值是一致的。同时，一致性也是指事务的基本特徵或特性相同，其他特性或特徵相类似。
- 可用性（A）：在集群（由多个独立的计算机通过高速的通信网路连线起来的,具有单一系统映象的高性能计算机系统。）中一部分节点故障后，集群整体是否还能回响客户端的读写请求。（可用性不仅包括读，还有写）。
- 分区容忍性（P）：集群中的某些节点在无法联繫后，集群整体是否还能继续进行服务。
定理证明
一致性：所有在分散式系统上的操作有一个总体上的顺序，每一个操作看起来就像是在一个单独的瞬间完成的。这就要求分散式系统的运行就像是在一个单节点上一样，在一个时间回响一个操作。
可用性：对于一个可用性的分散式系统，每一个非故障的节点必须对每一个请求作出回响。也就是，该系统使用的任何算法必异步网路
在异步网路模型中，没有统一时钟，所有节点仅根据接收到的讯息和本地的计算进行决策。
定理一：在一个异步网路模型中，没有可能实现一个满足以下属性的读写数据对象：1、可用性；2、一致性。对于所有对等运算（包括讯息会丢失的）。
证明：假设存在一个算法A满足这些条件：一致性、可用性、分区容忍性。我们构造一次A的执行，包括一个返回非一致结果的请求。假设网路包含至少两个节点，那幺它可以被分为不相关的非空集合：{G，H}。假设所有G和H之间的通讯讯息都丢失，这是可能的。如果这时在G上有一个写操作，接着H上有一个读操作，那幺读操作将无法返回早些的写操作。
推论一：在一个异步网路模型中，没有可能实现一个满足以下属性的读写数据对象：1、可用性，所有对等运算；2、一致性，所有对等运算，但讯息不会丢失。
证明：主要问题是在异步网路模型中一个算法没有办法去判断一个讯息是否丢失或者在传输通道中被延迟。因此，如果在运算中不会丢失任何讯息的前提下存在一个能够保证一致性的算法，那幺该算法也能够在所有运算（讯息可能丢失）情况下保证一致性。这将与定理一矛盾。
部分同步网路：假设一个部分同步的网路模型，在这里，所有的节点都有一个时钟，并且所有的时钟以一个相同的速度增长。然而，这些时钟并不是同步的，在相同的时间，它们显示不同的时间值。事实上，时钟扮演计时器的角色：处理器可以根据本地状态变数去衡量流逝了多少时间。一个本地的计时器可以用来调度某事件之后的多长时间间隔进行另一个操作。进一步地，假设每一个讯息要幺在给定的时间s内到达，要幺丢失。并且，所有的节点在给定时间t内处理完一个接收到的讯息。
定理二：在一个部分同步网路模型中，没有可能实现一个满足以下属性的读写数据对象：1、可用性；2、一致性。对于所有对等运算（包括讯息会丢失的）。
证明：但是在部分同步模型中，类似与异步模型推论一的结论就不存在了，因此推论一的假设基于节点无法判断一个讯息是否丢失。而在部分同步模型中，存在部分同步算法可以在所有讯息传送正常的情况下返回一致性的数据，而仅仅在讯息丢失时返回非一致性数据。对于读或写请求，节点传送一个讯息给另一个节点，如果讯息返回了，那幺节点传送请求的数据；如果讯息在给定的2s+t时间内没有返回，那幺该节点断定讯息丢失了，节点就可能返回一个不一致的请求数据。须最终终止。当同时要求分区容忍性时，这是一个很强的定义：即使是严重的网路错误，每个请求必须终止。
分区容忍性：为了定义分区容忍性，假定网路满足如下条件：网路是可能丢失从一个节点发往另一个节点的任意讯息，当网路被分区（隔断）时，所有从一个分区的节点发往另一个分区的讯息将会丢失。一致性要求每个回响必须是一致的，即使系统内部的讯息没有被正确地传送。可用性要求从客户端接收请求的任一节点必须被回响，即使任意的讯息可能没有被正确地传送。
分散式系统
分散式系统（distributed system）是建立在网路之上的软体系统。正是因为软体的特性，所以分散式系统具有高度的内聚性和透明性。因此，网路和分散式系统之间的区别更多的在于高层软体（特别是作业系统），而不是硬体。内聚性是指每一个资料库分布节点高度自治，有本地的资料库管理系统。透明性是指每一个资料库分布节点对用户的套用来说都是透明的，看不出是本地还是远程。在分散式资料库系统中，用户感觉不到数据是分布的，即用户不须知道关係是否分割、有无副本、数据存于哪个站点以及事务在哪个站点上执行等。