[科普中国]-CAP定理

CAP定理，又称CAP原则和作布鲁尔定理，指的是在一个分布式系统中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容忍性）这三个基本需求，最多只能同时满足其中的2个。理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设置为不可用，那么又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。

简介CAP定理起源于计算机科学家埃里克·布鲁尔在2000年的分布式计算原则研讨会（Symposium on Principles of Distributed Computing（PODC））上提出的一个猜想。在2002年，麻省理工学院（MIT）的赛斯·吉尔伯特和南希·林奇发表了布鲁尔猜想的证明，使之成为一个定理。吉尔伯特和林奇证明的CAP定理比布鲁尔设想的某种程度上更加狭义。定理讨论了在两个互相矛盾的请求到达彼此连接不通的两个不同的分布式节点的时候的处理方案。理论首先把分布式系统中的三个特性进行了如下归纳：

一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。即数据保持一致，在分布式系统中，可以理解为多个节点中数据的值是一致的。同时，一致性也是指事务的基本特征或特性相同，其他特性或特征相类似。

可用性（A）：在集群（由多个独立的计算机通过高速的通信网络连接起来的,具有单一系统映象的高性能计算机系统。）中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（可用性不仅包括读，还有写）1。

分区容忍性（P）：集群中的某些节点在无法联系后，集群整体是否还能继续进行服务。

定理证明一致性：所有在分布式系统上的操作有一个总体上的顺序，每一个操作看起来就像是在一个单独的瞬间完成的。这就要求分布式系统的运行就像是在一个单节点上一样，在一个时间响应一个操作。

可用性：对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是，该系统使用的任何算法必异步网络

在异步网络模型中，没有统一时钟，所有节点仅根据接收到的消息和本地的计算进行决策。

定理一：在一个异步网络模型中，没有可能实现一个满足以下属性的读写数据对象：1、可用性；2、一致性。对于所有对等运算（包括消息会丢失的）。

证明：假设存在一个算法A满足这些条件：一致性、可用性、分区容忍性。我们构造一次A的执行，包括一个返回非一致结果的请求。假设网络包含至少两个节点，那么它可以被分为不相关的非空集合：{G，H}。假设所有G和H之间的通讯消息都丢失，这是可能的。如果这时在G上有一个写操作，接着H上有一个读操作，那么读操作将无法返回早些的写操作。

推论一：在一个异步网络模型中，没有可能实现一个满足以下属性的读写数据对象：1、可用性，所有对等运算；2、一致性，所有对等运算，但消息不会丢失。

证明：主要问题是在异步网络模型中一个算法没有办法去判断一个消息是否丢失或者在传输通道中被延迟。因此，如果在运算中不会丢失任何消息的前提下存在一个能够保证一致性的算法，那么该算法也能够在所有运算（消息可能丢失）情况下保证一致性。这将与定理一矛盾。

部分同步网络：假设一个部分同步的网络模型，在这里，所有的节点都有一个时钟，并且所有的时钟以一个相同的速度增长。然而，这些时钟并不是同步的，在相同的时间，它们显示不同的时间值。事实上，时钟扮演计时器的角色：处理器可以根据本地状态变量去衡量流逝了多少时间。一个本地的计时器可以用来调度某事件之后的多长时间间隔进行另一个操作。进一步地，假设每一个消息要么在给定的时间s内到达，要么丢失。并且，所有的节点在给定时间t内处理完一个接收到的消息。

定理二：在一个部分同步网络模型中，没有可能实现一个满足以下属性的读写数据对象：1、可用性；2、一致性。对于所有对等运算（包括消息会丢失的）。

证明：但是在部分同步模型中，类似与异步模型推论一的结论就不存在了，因此推论一的假设基于节点无法判断一个消息是否丢失。而在部分同步模型中，存在部分同步算法可以在所有消息传送正常的情况下返回一致性的数据，而仅仅在消息丢失时返回非一致性数据。对于读或写请求，节点发送一个消息给另一个节点，如果消息返回了，那么节点发送请求的数据；如果消息在给定的2s+t时间内没有返回，那么该节点断定消息丢失了，节点就可能返回一个不一致的请求数据。须最终终止。当同时要求分区容忍性时，这是一个很强的定义：即使是严重的网络错误，每个请求必须终止。

分区容忍性：为了定义分区容忍性，假定网络满足如下条件：网络是可能丢失从一个节点发往另一个节点的任意消息，当网络被分区（隔断）时，所有从一个分区的节点发往另一个分区的消息将会丢失。一致性要求每个响应必须是一致的，即使系统内部的消息没有被正确地发送。可用性要求从客户端接收请求的任一节点必须被响应，即使任意的消息可能没有被正确地发送。

分布式系统分布式系统（distributed system）是建立在网络之上的软件系统。正是因为软件的特性，所以分布式系统具有高度的内聚性和透明性。因此，网络和分布式系统之间的区别更多的在于高层软件（特别是操作系统），而不是硬件。内聚性是指每一个数据库分布节点高度自治，有本地的数据库管理系统。透明性是指每一个数据库分布节点对用户的应用来说都是透明的，看不出是本地还是远程。在分布式数据库系统中，用户感觉不到数据是分布的，即用户不须知道关系是否分割、有无副本、数据存于哪个站点以及事务在哪个站点上执行等。

本词条内容贡献者为:

方正 - 副教授 - 江南大学