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证明.png

取舍

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

CP 模型

牺牲一定的可用性，保证一致性和分区容错性。一个简单的中心式算法能够满足CP要求，一个中心节点维护了数据，其他节点接收到客户端的请求后，自动把请求重定向到中心节点，从中心节点获取到ack后，再把数据响应给客户端。

如果系统需要保证强一致性，可以选择CP模型来进行实现。

CP.png

CA模型

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

AP模型

牺牲系统的强一致性，保证可用性和分区容错性。没有了一致性的束缚，系统中的节点可以将初始值V0响应给每个请求，从而满足可用性的要求。当然实际使用 中系统还是能够提供一定的弱一致性保证。比如分布式系统中，节点使用的本地缓存，可以通过设置有效时间，当有效时间过后，重新加载本地缓存保证了一定的一致性。

生活中的例子

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

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

老板娘：“7元”；

老板：“6元”

这个小故事中，我们把老板娘和老板，分别看作是分布式系统中的两个节点，按照上面我们介绍的可能模型，这是一个AP模型，牺牲了一定了一致性。

AP.png

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

CP1.png

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

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

参考

【1】https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/

【2】https://github.com/psyho/dyplom/blob/master/bibliografia/brewers-conjecture/BrewersConjecture-SigAct.pdf