CAP理论及其证明

今天药忘吃喽~ 2021-09-24 22:14 334阅读 0赞

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

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

# 何为CAP理论？ #

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

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

# 分布式系统 #

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

客户端可以读取和修改任意一个服务端的值。当服务端收到请求，他会做相应处理后回复客户端。如果是写请求执行过程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]

如果是读请求，执行过程如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 2]

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

# 一致性 #

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

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

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

下图所示是有个不保证一致性的系统：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 3]

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

下图是一个保证一致性的系统：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 4]

在这个系统中，当客户端向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的信息可能会丢失，如果所有的信息都丢失了，我们的系统可能就会变成这样。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 5]

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

# 证明 #

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

假设存在一个同时满足一致性、可用性和分区容错性的分布式系统。首先我们把这个系统分成两个部分，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 6]  
接下来客户端将G1中的v从v0改成v1，因为要满足可用性的要求，G1必须响应客户端的写入请求，但是因为网络的问题，G1没法将数据同步到G2。Gilbert和Lynch将这个阶段称为alpha1阶段，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 7]

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

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

## 原文链接 ##

https://mwhittaker.github.io/blog/an\_illustrated\_proof\_of\_the\_cap\_theorem/

[Perspectives on the CAP Theorem]: https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/483392bbac0a4fa394ba9991bc215950.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/015592d599ca412091a531f41366cebf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210923/5b325bb1f6494f3f9e1a994e7959e511.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210923/a1d6c88d8c4747f98bb43d11bc92cc41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210923/997088af54554f6a9941cae8d99dfaad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210923/3a1567f6accf420fb8fe9eadb2fa3eef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20210923/139f555938a841e3bc2c0a735f4fd4a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20210923/6b1556cce9164bab8e62972c92623a31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20210923/de2c974a70fc480a9b47b3fbb2253c05.png