阅读 332

带有插图的验证CAP定理

前言

本篇文章不仅仅是一篇译文,也是学习 CAP 定理,所以文章不仅仅只是翻译
复制代码

原本地址:An Illustrated Proof of the CAP Theorem

开始

CAP 定理是分布式系统中的基本定理,任何声明是分布式的系统最多可以有两个下列中的属性(该定理在 2000 年由计算机科学家 Eric Brewer 提出,由Gibert和Lynch证明)

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

本指南会带有图片的总结GibertLynch's对于CAP定理的说明和验证

什么是CAP定理

CAP 定理声明了在分布式系统中无法同时实现一致性,可用性,分区容错性。听起来很简单,但是以上三点分别又是什么意思呢?所说的分布式系统又是什么意思呢?

在本部分,我们会介绍一个简单的分布式系统和解释他的可用性,一致性还有分区容错性。为了正式说明系统和三种属性,请参考 GilbertLynch'c的论文(访问不到了)

分布式系统

来思考一个简单的分布式系统,本系统由两个服务组成,G1和G2服务都提供保存了相同变量 V,他的初始值是V0,G1和G2可以相互通讯,并且可以和外部客户端通讯。下面就是我们系统的样子

客户端可以请求对两个服务器的读或写,当其中服务器接收到请求,它执行它想要的任意计算,然后把结果响应给客户端,举个例子,客户端想要(执行)写(操作)的示意图
客户端想要读取的示意图
现在我们已经知道了系统的流程,接下来,回顾什么是一致性,可用性,和分区容错性。

一致性

以下是 Glibert 和 Lynch对一致性的解释

任意读的操作必须返回最近一次完成写操作后的值(读取任意服务器)
复制代码

在一致的系统中,当客户端对任意服务器写入值得到相应后,它期望通过读取能够从任意服务器中得到那个值

这是一个没有实现一致性的示意图

我们的系统写入V1到G1服务器中,并得到了响应,但是我们从G2中读取时,依然是V0的旧数据

一个实现一致性系统的示意图

在这个系统中,G1将其值复制到G2,在向客户发送确认之前。因此,当客户端从G2读取时,它获得V的最新值:v1(突然发现小写v看着更舒服。。)

可用性

以下是Gilbert和Lynch对可用性的说明。
系统中非故障节点收到的每个请求都必须产生响应 在实现可用性的系统中,如果客户端发送请求到服务器,如果服务器并没有崩溃,那么服务器必须对该请求响应到客户端。服务器不能忽视任意的请求

分区容错性

以下是Gilbert和Lynch对可用性的说明。
网络中允许节点丢失对其他节点发送的多条信息 意思是G1和G2发送给对方的任何信息都有可能丢失。如果所有的信息都被丢失(网络通信都会有失败的可能),那么我们的系统是这个样子(下图是之前的读写,同步操作都丢失的情况,这是我的理解)

为了实现分区容错,我们的系统必须能够在任意网络分区中提供服务(这是翻译后的,是不是觉得前后没什么关联,可能我中文不太好,有点懵,其实就是网络中其中一个节点在不可用后,其他的节点依然能够提供服务)

证明CAP定理

我们已经了解了CAP定理,接下来,我们要证明分布式系统不可能同时拥有这三个特性。 假设分布式系统实现了三个特性,第一件事就是对我们的系统分区。像下面的示意图。

下一步,我们的客户端请求向G1写入v1,因为我们的系统实现了可用性,所以必须响应这个请求。并且这个内部网络是分区的,无论怎么样,G1不能够同步v1到G2,Gilbert 和 Lynch称这个执行阶段为 α1
然后,我们的客户端发出读取的请求到G2,因为我们的系统是可用的,G2必须响应。又因为我们的系统分区了,G2无法通过G1同步数据修改值v。G2会返回v0,Gilbert 和 Lynch称这个执行阶段为 α2

我们假设分布式系统实现了三大特性,但我们刚才的演示中,其中一个节点存在执行到了请求,而另外的节点数据并没有一致,因此,不存在同时实现了三种特性的分布式系统

业内应用

现在就不是译文啦,而是拓展

一致性和可用性的冲突

案例

当请求向G1写v1,那么为了实现G2的一致性,此时应该上锁,直到G1将v1同步到G2,此时不可读不可写,并没有做到可用性。反之亦然

取舍

互联网上有这么多的分布式系统,开发者会根据业务场景,选择折中的解决方案
例如订单系统,访问库存系统,如果通信失败,就要在可用性和一致性之间做出选择。

  1. 停止系统服务进行错误恢复
  2. 继续服务但是降低一致性

所以大多数分布式系统都是选择实现AP或CP
比如分布式存储,现在大多数实现的是 可用性+最终一致性
系统响应必定需要延时,如果,一致性同步时间小于或等于响应时间,那么在保证分区容错和可用的基础上,用户在感官和体验上是可以达到CAP的(如果分布式系统部署在同一个机房,那么这个延迟基本可以忽略了)

参考文献

Wike:CAP定理
阮一峰:CAP定理的含义
InfoQ:CAP理论十二周年回顾

关注下面的标签,发现更多相似文章
评论