1985年Lynch证明了异步通信中不存在任何一致性的分布式算法(FLP Impossibility)。
2000年,Eric Brewer在PODC的研讨会上提出了一个猜想(CAP理论猜想):一致性、可用性和分区容错性三者无法在分布式系统中被同时满足,并且最多只能满足其中两个!
2002年,Lynch与Gilbert证明了Brewer猜想,论文链接(可访问).
在分布式系统中CAP定理是一个基础定理,证明了在分布式系统中不可能同时获得以下三个属性。
以上定义来源于Lynch与Gilbert的论文中给出的定义。
论文采用了反证法的方式:假设存在一种算法A同时满足Consistency、Availability、Partition tolerance。
那么我们来模拟一个反例请求。
假设我们有两个节点组成的集群。
由此证明了,在分布式系统中,CAP不可能同时满足。
既然在分布式系统中,不能同时满足CAP,那么设计人员就要根据实际需求进行取舍,我们来看下常见的模型。
CP 模型
牺牲一定的可用性,保证一致性和分区容错性。一个简单的中心式算法能够满足CP要求,一个中心节点维护了数据,其他节点接收到客户端的请求后,自动把请求重定向到中心节点,从中心节点获取到ack后,再把数据响应给客户端。
如果系统需要保证强一致性,可以选择CP模型来进行实现。
CA模型
不存在分区容错,也就是没有网络丢失的可能。单体应用中不会因为节点间的数据通信导致消息丢失。在分布式系统中,由于存在节点间网络交互,所以分区容错性是 必须要考虑的点,可以不考虑CA模型。
AP模型
牺牲系统的强一致性,保证可用性和分区容错性。没有了一致性的束缚,系统中的节点可以将初始值V0响应给每个请求,从而满足可用性的要求。当然实际使用 中系统还是能够提供一定的弱一致性保证。比如分布式系统中,节点使用的本地缓存,可以通过设置有效时间,当有效时间过后,重新加载本地缓存保证了一定的一致性。
我周末去市场,要买包酸菜,回家做酸菜鱼。
我:来到酸菜摊位前,拿起一包酸菜,问:“这酸菜多少钱一包”
老板娘:“7元”;
老板:“6元”
这个小故事中,我们把老板娘和老板,分别看作是分布式系统中的两个节点,按照上面我们介绍的可能模型,这是一个AP模型,牺牲了一定了一致性。
故事继续,当老板说完6元后,只看到老板娘恶狠狠的盯着老板。那么如果老板不想再次出这种问题,应该咋办呢?看下图
老板接收到价格询问后,可以询问老板娘酸菜什么价,然后再回复我。此场景中如果老板娘耳背,迟迟不回复老板信息,那么对整体的可用性造成一定影响,所以这是一种CP的选择。
故事结尾:我买了这包酸菜,给老板扫了7块钱,我觉得我血赚,大家觉得呢。
参考
【1】https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。