下载掌阅APP，畅读海量书库
立即打开
1985年，Fischer、Lynch和Patterson三位学者证明了异步通信中不存在任何一致性的分布式算法（FLP impossibility），即在异步通信场景中，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性。因此，人们开始寻找分布式系统设计的各种因素。既然一致性算法不存在，找到一些设计因素并进行适当的取舍以最大限度地满足系统需求，就成为当时的重要议题。
2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM的分布式计算原则（Principles of Distributed Computing）研讨会上，首次提出了著名的CAP猜想。两年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了Brewer教授CAP猜想的可行性。从此，CAP理论正式在学术上成为分布式计算领域的公认定理，并深深地影响了分布式计算的发展。
CAP定理是指对于一个分布式计算系统来说，不可能同时满足一致性（consistency）、可用性（availability）和分区容错性（partition tolerance），这三项基本需求，最多只能同时满足其中的两项。
● 一致性：所有节点访问同一份最新的数据副本。在分布式系统中的所有数据备份在同一时刻具有同样的值。
● 可用性：对数据更新具备高可用性。集群中的部分节点出现故障后，集群整体还能响应客户端的读写请求。
● 分区容错性：当分布式系统集群中的某些节点无法联系时仍能正常提供服务。分区是指是否允许集群中的节点之间无法通信。由于是分布式系统，必须满足分区容错性，因为网络的不可靠性必定会导致两个机器节点之间无法进行网络通信，从而导致数据无法同步。
CAP猜想在被证实和规范化后，被正式称为CAP定理，极大地影响了大规模Web分布式系统的设计。当在分布式存储系统中应用CAP定理时，最多只能实现上述两项需求。而由于当前的网络硬件肯定会出现延迟或丢包等问题，因此分区容错性是必须要实现的。所以，我们在设计分布式系统时只能在一致性和可用性之间进行权衡。
事实上，在设计分布式应用系统时，这三项基本需求最多只能同时实现两项，不可能三者兼顾，如图1-14所示。
图1-14 CAP定理的应用
如果选择分区容错性和一致性，那么即使有节点出现故障，操作必须既一致又能顺利完成，所以必须100%保证所有节点之间有很好的连通性。这是很难做到的。因此，最好的办法就是将所有数据放到同一个节点中。但显然这种设计是不满足可用性的，即一旦系统遇到网络分区或其他故障，受到影响的服务就需要等待一定的时间，因此在等待期间系统无法对外提供正常的服务，即不可用，如BigTable、HBase。
如果要满足可用性和一致性，那么为了保证可用性，则数据必须要有副本（replica）。因此，系统显然无法容忍分区。当同一数据的两个副本被分配到两个无法通信的分区时，会返回错误的数据，如关系数据库。另外，需要明确的一点是，对于一个分布式系统而言，分区容错性是一个最基本的要求，因为分布式系统中的组件需要被部署到不同的节点。
最后分析满足可用性和分区容错性的情况。要满足可用性，说明数据必须要在不同节点中有副本。还必须保证在产生分区的时候操作仍然可以完成。那么，操作必然无法保证一致性，如Dynamo、Cassandra、SimpleDB。
为了让读者更好地理解CAP定理的概念，下面通过一个具体的分布式应用的例子进行说明。如图1-15所示，假如有两个应用 A 和 B 分别运行在两个不同的服务器 N 1 和 N 2 上。 A 负责向它的数据仓库（主存储器）写入数据，而 B 则从另一个数据库副本（备份存储器）读取数据。服务器 N 1 通过发送数据更新消息给服务器 N 2 来实现同步，以达到两个数据库之间的一致性。客户端应用程序调用put（ d ）方法更新数据 d 的值，应用 A 会收到该命令并将新数据通过write()方法写入它的数据库，然后服务器 N 1 向服务器 N 2 发送消息以更新在另一个数据库副本里的 d′ 的值，随后客户端应用调用get（ d ）方法想要获取 d 的值， B 会收到该命令并调用read()方法从仓库副本里读出 d′ 的值，此时 d′ 已经更新为新值，因此，整个系统看起来是一致的。
图1-15 分布式系统CAP问题实例
假如服务器 N 1 和 N 2 之间的通信被切断了（网线断了），如果希望系统是容错的，则将两个数据库之间的消息设定为异步消息，那么系统仍然可以继续工作，但是数据库副本内的数据不会更新，随后用户读到的数据便是过期的数据，这就造成数据的不一致。即使将数据更新消息设定为同步的也不行，这会使服务器 N 1 的写操作和数据更新消息成为一个原子性事务，一旦消息无法发送，服务器 N 1 的写操作就会随着数据更新消息发送失败而回滚，导致系统无法使用，违背了可用性。
CAP定理告诉我们，在大规模的分布式系统中，分区容错性是基本要求，所以要对可用性和一致性有所取舍。对于上面的实例，我们可以选择使用最终一致模型，数据更新消息可以是异步发送的，但如果服务器 N 1 在发送消息时无法得到确认，那么它就会重新发送消息，直到服务器 N 2 上的数据库副本与服务器 N 1 达到一致为止，而客户端则需要面临不一致的状态。实际上，如果你从购物车中删除一个商品记录，它很可能再次出现在你的交易记录里，但是显然，相对于较高的系统延迟来说，用户可能更愿意继续他们的交易。对于大多数Web应用来说，牺牲一致性来换取高可用性是主要的解决方案。