[翻译]CAP理论及其证明

莺歌燕舞

CAP是所有分布式系统的基础理论，任何分布式系统只能满足以下三种状态中的任意两种。  

• 一致性(Consistency)
  
• 可用性(Availability)
  
• 分区容错性(Partition tolerance)
  

何为CAP理论？


CAP理论是指一个分布式系统不能同时满足一致性、可用性和分区容错性。听起来简单，但一致性、可用性和分区容错性分别是指啥？甚至分布式系统是啥？  

在这篇文章中，我们会引入一个简单的分布式系统来解释清楚何为可用性、一致性、和分区容错性。更多信息可以参考Gilbert和Lynch的论文Perspectives on the CAP Theorem。   

分布式系统


假设我们有这样一个简单的分布式系统，它包含两个服务G1和G2，这俩服务都保存着同一变量v，其初始值是v0。 G1和G2之间可以互相沟通，同时他们也可以和其他的客户端沟通，如下图所示：



客户端可以读取和修改任意一个服务端的值。当服务端收到请求，他会做相应处理后回复客户端。如果是写请求执行过程如下图所示：




如果是读请求，执行过程如下图：




现在我们已经建立了一个简单的分布式系统，接下来我们分别看下一致性、可用性和分区容错性。  

一致性


Gilbert和Lynch的论文中是这样描述一致性的：

any read operation that begins after a write operation completes must return that value, or the result of a later write operation
在某个写操作完成之后的任何读操作都必须返回该写操作写入的值，或者再之后的写操作写入的值。

在一个一致性的系统中，如果一个客户端写入了某个值到任意一个服务端上，并且得到了服务端的确认，那么客户端再去读的时候，不管是读的哪个服务，都期望拿到写入后的值或者是更新的值。   

下图所示是有个不保证一致性的系统：



客户端向G1发送了写请求将v的值从v0变更到v1，然后也得到了G1的写入成功确认，但从G2读到的数据还是旧的数据v0。   

下图是一个保证一致性的系统：



在这个系统中，当客户端向G1写入数据v1后，G1也会把数据同步到G2，当G1 G2都完成数据更新后，G1才会告诉客户端写入成功。 之后不过是客户端从G1读还是从G2读，读到的都是最新的值v1。  

可用性


Gilbert和Lynch的论文对可用性的描述如下：

every request received by a non-failing node in the system must result in a response任何一个在线的节点收到的请求必须都做出相应。

在保证可用性的系统中，如果客户端向某个没有宕机的服务端发送了请求，服务端必须响应客户端的请求，不能选择忽略掉客户端的请求。   

分区容错性


Gilbert和Lynch的论文对分区容错性的描述如下：

the network will be allowed to lose arbitrarily many messages sent from one node to another允许网络丢失从一个服务节点到另外一个服务节点的任意信息

这就意味着在我们的分布式系统中，G1发送给G2的信息可能会丢失，如果所有的信息都丢失了，我们的系统可能就会变成这样。



为了保证分区容错性，我们的系统必须在任意个不通的网络分区下正常工作。  

证明


现在我们已经了解了什么是一致性、可用性和分区容错性，接下来我们证明下为什么一个分布式系统不能同时满足这三者。

假设存在一个同时满足一致性、可用性和分区容错性的分布式系统。首先我们把这个系统分成两个部分，如下图：

接下来客户端将G1中的v从v0改成v1，因为要满足可用性的要求，G1必须响应客户端的写入请求，但是因为网络的问题，G1没法将数据同步到G2。Gilbert和Lynch将这个阶段称为alpha1阶段，如下图：




再然后，假设有个客户端从G2读了v的值，因为满足可用性要求，G2也必须正常响应，因为网络的问题，G2没有更新到G1的数据，所以G2只能返回v0，Gilbert和Lynch将这个阶段称为alpha2阶段，如下图：




在这里G1返回v1，G2只能返回v1，产生了不一致，和我们的假设相悖，所以证明同时满足一致性、可用性和分区容错性的分布式系统不存在。  

原文链接


https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/

本文来自https://blog.csdn.net/xindoo

原文地址：https://zhuanlan.zhihu.com/p/269642747