关于面试:CAP定理

CAP 定理

CAP 定理的倒退

1985 年 Lynch 证实了异步通信中不存在任何一致性的分布式算法（FLP Impossibility）。

2000 年，Eric Brewer 在 PODC 的研讨会上提出了一个猜测（CAP 实践猜测）：一致性、可用性和分区容错性三者无奈在分布式系统中被同时满足，并且最多只能满足其中两个！

2002 年，Lynch 与 Gilbert 证实了 Brewer 猜测，论文链接(可拜访).

什么是 CAP 定理

在分布式系统中 CAP 定理是一个根底定理，证实了在分布式系统中不可能同时取得以下三个属性。

• Consistency，一致性，在分布式系统中一个产生在 写操作 实现后的 读操作 必须返回这个值或者一个更新的写操作值
• Availability，可用性，零碎中非故障节点接管的每个申请都必须产生响应。
• Partition tolerance，分区容错，一个节点发送给另一个节点的音讯，因为网络起因容许失落任意多的音讯。

以上定义来源于 Lynch 与 Gilbert 的论文中给出的定义。

证实

论文采纳了反证法的形式：假如存在一种算法 A 同时满足Consistency、Availability、Partition tolerance。

那么咱们来模仿一个反例申请。

假如咱们有两个节点组成的集群。

• 因为算法 A 满足 CAP，依据分区容错性（Partition tolerance）假如两个节点之间的音讯都失落。
• 客户端向其中一个节点发动了写申请申请实现后，数据从 V0→V1；因为节点之间的音讯都失落，所以另一个节点数据还是 V0；
• 客户端向两个节点，都发送了读申请，依据可用性（Availability），两个节点都会对申请产生相应，一个节点响应了数据 V1，另一个相应数据 V0；
• 因为一个节点返回了数据 V0，这个数据是一个写操作实现之后的数据，违反了一致性的定义(Consistency)。

由此证明了，在分布式系统中，CAP 不可能同时满足。

取舍

既然在分布式系统中，不能同时满足 CAP，那么设计人员就要依据理论需要进行取舍，咱们来看下常见的模型。

CP 模型

就义肯定的可用性，保障一致性和分区容错性。一个简略的核心式算法可能满足 CP 要求，一个核心节点保护了数据，其余节点接管到客户端的申请后，主动把申请重定向到核心节点，从核心节点获取到 ack 后，再把数据响应给客户端。

如果零碎须要保障强一致性，能够抉择 CP 模型来进行实现。

CA模型

不存在分区容错，也就是没有网络失落的可能。单体利用中不会因为节点间的数据通信导致音讯失落。在分布式系统中，因为存在节点间网络交互，所以分区容错性是 必须要思考的点，能够不思考 CA 模型。

AP模型

就义零碎的强一致性，保障可用性和分区容错性。没有了一致性的解放，零碎中的节点能够将初始值 V0 响应给每个申请，从而满足可用性的要求。当然理论应用 中零碎还是可能提供肯定的弱一致性保障。比方分布式系统中，节点应用的本地缓存，能够通过设置无效工夫，当无效工夫过后，从新加载本地缓存保障了肯定的一致性。

生存中的例子

我周末去市场，要买包酸菜，回家做酸菜鱼。

我：来到酸菜摊位前，拿起一包酸菜，问：“这酸菜多少钱一包”

老板娘：“7 元”；

老板：“6 元”

这个小故事中，咱们把老板娘和老板，别离看作是分布式系统中的两个节点，依照下面咱们介绍的可能模型，这是一个 AP 模型，就义了肯定了一致性。

故事持续，当老板说完 6 元后，只看到老板娘恶狠狠的盯着老板。那么如果老板不想再次出这种问题，应该咋办呢？看下图

老板接管到价格询问后，能够询问老板娘酸菜什么价，而后再回复我。此场景中如果老板娘耳尖，迟迟不回复老板信息，那么对整体的可用性造成肯定影响，所以这是一种 CP 的抉择。

故事结尾：我买了这包酸菜，给老板扫了 7 块钱，我感觉我血赚，大家感觉呢。

参考

【1】https://mwhittaker.github.io/…

【2】https://github.com/psyho/dypl…