[翻译]CAP理论及其证明

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

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

何为CAP理论?

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

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

分布式系统

假设我们有这样一个简单的分布式系统,它包含两个服务G1和G2,这俩服务都保存着同一变量v,其初始值是v0。 G1和G2之间可以互相沟通,同时他们也可以和其他的客户端沟通,如下图所示:
[翻译]CAP理论及其证明_第1张图片

客户端可以读取和修改任意一个服务端的值。当服务端收到请求,他会做相应处理后回复客户端。如果是写请求执行过程如下图所示:
[翻译]CAP理论及其证明_第2张图片

如果是读请求,执行过程如下图:
[翻译]CAP理论及其证明_第3张图片

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

一致性

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

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

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

下图所示是有个不保证一致性的系统:
[翻译]CAP理论及其证明_第4张图片

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

下图是一个保证一致性的系统:
[翻译]CAP理论及其证明_第5张图片

在这个系统中,当客户端向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的信息可能会丢失,如果所有的信息都丢失了,我们的系统可能就会变成这样。
[翻译]CAP理论及其证明_第6张图片

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

证明

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

假设存在一个同时满足一致性、可用性和分区容错性的分布式系统。首先我们把这个系统分成两个部分,如下图:
[翻译]CAP理论及其证明_第7张图片

再然后,假设有个客户端从G2读了v的值,因为满足可用性要求,G2也必须正常响应,因为网络的问题,G2没有更新到G1的数据,所以G2只能返回v0,Gilbert和Lynch将这个阶段称为alpha2阶段,如下图:
[翻译]CAP理论及其证明_第8张图片

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

原文链接

https://mwhittaker.github.io/...

你可能感兴趣的