请选择 进入手机版 | 继续访问电脑版

[分布式系统] CAP理论 简介说明

计算机科学 计算机科学 1619 人阅读 | 0 人回复

历史背景

CAP 理论首次出现于1998年秋[5 Eric Brewer, "CAP twelve years later: How the 'rules' have changed", Computer, Volume 45, Issue 2 (2012), pg. 23–29. doi:10.1109/MC.2012.37.]。

它于1999年作为CAP原理发表[10 Armando Fox and Eric Brewer, "Harvest, Yield and Scalable Tolerant Systems", Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174–178. doi:10.1109/HOTOS.1999.798396]

并以是加州理工大学伯克利分校的 Eric Brewer 教授在 2000 年 7 月的 ACM PODC 会议上首次提出的[11 Eric Brewer, "Towards Robust Distributed Systems"]。

image.png

它是 Eric Brewer 在 Inktomi 期间研发搜索引擎、分布式 Web 缓存时得出的关于数据一致性( C:Consistency )、服务可用性( A:Availability )、分区容错性( P:Partition-tolerance )的一个著名猜想:

It is impossible for a web service to provide the three following guarantees : Consistency, Availability and Partition-tolerance.

文稿下载地址:

https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

https://gitee.com/crazybytex/some-documents/blob/master/Towards_robust_distributed_systems.pdf

2002年,也就是在这个猜想提出的 2 年以后,来自麻省理工学院的 Seth Gilbert 和 Nancy Lynch 从理论上证明了 Eric Brewer 教授的 CAP 猜想是成立的 [1 Seth Gilbert and Nancy Lynch, "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services", ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51–59. doi:10.1145/564585.564601]

https://en.wikipedia.org/wiki/CAP_theorem维基百科中有详细说明:

According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.[5] It was published as the CAP principle in 1999[10] and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[11] In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem.[1]

[5]https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/

[10]https://ieeexplore.ieee.org/document/798396

https://gitee.com/crazybytex/some-documents/blob/master/Harvest,%20yield,%20and%20scalable%20tolerant%20systems.pdf

[11]https://www.podc.org/podc2000/brewer.html

https://dl.acm.org/doi/10.1145/343477.343502

[1]https://dl.acm.org/doi/10.1145/564585.564601

从此,CAP 理论在学术上正式成为了分布式领域公认的定理,并深刻影响着分布式系统的发展。

概念

image.png

Consistency Every read receives the most recent write or an error. Availability Every request receives a (non-error) response, without the guarantee that it contains the most recent write. Partition tolerance The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes. When a network partition failure happens, it must be decided whether to do one of the following:

  • cancel the operation and thus decrease the availability but ensure consistency
  • proceed with the operation and thus provide availability but risk inconsistency.

Consistency

一致性

是指所有节点在同一时刻的数据是相同的,即更新操作执行结束并响应用户完成后,所有节点存储的数据会保持相同。

也就是说,系统中对一个数据的读和写虽然很可能是包含多个子步骤并且会持续一段时间才能执行完,但是在调用者看来,读操作和写操作都 必须是单个的即时完成的操作,不存在重叠。对一个写操作,如果系统返回了成功,那么之后到达的读请求都必须读到这个新的数据;如果系统返回失败,那么所有的读,无论是之后发起的,还是和写同时发起的,都不能读到这个数据。

Availability

可用性,是指系统提供的服务一直处于可用状态,对于用户的请求可即时响应。

指的是所有的读和写都必须要能终止,比如无期限的等待或者阻塞都是不符合的,重点是"有限时间内"和"返回结果"。

Partition tolerance

分区容错性,是指在分布式系统遇到网络分区的情况下,仍然可以响应用户的请求。网络分区是指因为网络故障导致网络不连通,不同节点分布在不同的子网络中,各个子网络内网络正常

注意其实不仅仅是网络问题,节点故障也属于分区容错性的范畴,不能在时限内达成数据一致性,就意味着发生了分区的情况。

换句话说:因为一些故障,使得有些节点之间不连通了,整个网络就分成了几块区域。你的忍耐程度是多少?

不保证P,其实就是无法接收容忍网络分区。

选择

如下图所示,CAP只能同时满足两个(此处的只能满足是指出现问题的情况下,如果一切正常,分布式系统是要对外能够提供一致性和可用性的)

image.png

文稿中关于舍弃不同部分的举例

image.png

因为网络是不可靠的,但是分布式系统又是必须要借助网络进行通信,没有一个分布式系统能够安全地避免网络故障,因此通常情况下,必须容忍网络分区。(通常情况)

否则一旦网络出现问题,便不再提供服务,整个系统都无效,分布式系统就变得没有意义。

而在存在分区的情况下,可以选择两个选项:一致性或可用性。

当选择一致性而不是可用性时,如果由于网络分区而无法保证特定信息是最新的,系统将返回错误或超时;

当选择可用性而不是一致性时,系统将始终处理查询并尝试返回信息的最新可用版本,即使由于网络分区,它无法保证信息是最新的;

示例

如下图所示系统

image.png

C:Server1 和 Server2 中的数据始终保持一致,即 Server1和 Server2保存的内容要始终保持相同;

A:用户无论访问 Server1 还是 Server2,都会得到即时响应;

P:Server1 和 Server2 之间即使出现网络故障也不会影响 Server1 和 Server2 分别处理用户的请求。

正常情况下,系统无论是Server1还是Server2,接到用户请求时,都可以正确的处理请求,然后将数据互相同步,达成一致。

满足P

正常情况下,网络不存在问题,但是如果一旦存在问题,网络不连通,也就是Server1 和 Server2不能正常通信,无法发送数据同步。

如果满足P,也就是“Server1 和 Server2 之间即使出现网络故障也不会影响 Server1 和 Server2 分别处理用户的请求。”

两种处理方式:

选择C,也就是保障一致性,但是现在网络不连通,无法同步保障一致性,只能阻塞住用户的请求,一直卡着,只到网络连通之后,继续通信同步,达成一致性之后,再返回响应,此时不能够及时响应用户,就无法保障可用性A;

选择A,也就是保障可用性,但是现在网络不通,无法同步保障一致性,又要立刻给用户提供响应,返回数据,因为没办法通信同步,就没办法保证数据是一致的,也就是无法保障一致性C;

以上说明CAP三者是不可以并存的,只能选择两个。

两两组合,只有CP、AP、CA三种,上面说明了CP、AP的情况。

当一套系统在发生分区故障后,客户端的任何请求(指的是写请求)都被卡死或者超时,但是,系统的每个节点总是会返回一致的数据,则这套系统就是 CP 系统,经典的比如 Zookeeper。

如果一套系统发生分区故障后,客户端依然可以访问系统,但是获取的数据有的是新的数据,有的还是老数据(数据很可能不一致,但是正常提供服务),那么这套系统就是 AP 系统,经典的比如 Eureka。

满足C

如果满足C,也就是“Server1 和 Server2 中的数据始终保持一致”。

如果此时希望继续满足A,也就是“用户无论访问 Server1 还是 Server2,都会得到即时响应”

可是如果网络出现故障,Server1 和 Server2无法进行通信同步,就无法达到一致性,也就是无法继续运行了,所以不允许无法接受网络出现故障,那样就无法保障CA。

如果不允许网络出现故障, 那么Server之间可以互相通信同步,数据必然可以达成一致,也必然可以对用户的请求进行即时响应。

此处的不允许网络出现故障,其实就是完全无法容忍网络分区。

小结

说了很多关于选择的注意事项,但是有一点需要强调的是,并不是说每一时刻都无法保障,无法保障CAP的意思是指如果出现了一些问题,我们还想扛过这个问题,就需要做出一些取舍。

如果系统正常,网络正常,那么其实CAP是同时都有得到保障的,这一点需要注意。

而一旦出问题,就需要做出权衡取舍,FLP不可能理论也算是论证了这一点,在异构网络中,分布式系统不存在完美的算法可以达到一致性,只能是进行不断的取舍、权衡。

CAP是一种学术理论,并不是工程实践理论,给分布式系统的设计指明了思路,但是不是直接开发的纲领。

而且针对于CAP的抉择,并不是说整个系统全都要使用同一种选择,系统的不同部分,是可以运用不同的策略的。

比如电商系统下单、支付、扣减库存等需要保障C,但是用户修改昵称这种就可以保障A。

CAP 的不足

CAP 定理本身是没有考虑网络延迟的问题的,它认为一致性是立即生效的,但是,要保持一致性,是需要时间成本的,这就导致往往分布式系统多选择 AP 方式。

在实践中一致性和可用性并不仅仅是二选一的问题,只是一些重要性的区别。

当强调一致性的时候,并不表示可用性是完全不可用的状态。比如,Zookeeper 只是在 master 出现问题的时候,才可能出现几十秒的不可用状态,而别的时候,都会以各种方式保证系统的可用性。

而强调可用性的时候,也往往会采用一些技术手段,去保证数据最终是一致的。CAP 定理并没有给出这些情况的具体描述。 CAP 理论从工程角度来看只是一种状态的描述,它告诉大家当有错的时候,分布式系统可能处在什么状态。但是,状态是可能变化的。状态间如何转换,如何修补,如何恢复是没有提供方向的。

common_log.png 转载务必注明出处:程序员潇然,疯狂的字节X,https://crazybytex.com/thread-234-1-1.html

文章被以下专栏收录:

    黄小斜学Java

    疯狂的字节X

  • 目前专注于分享Java领域干货,公众号同步更新。原创以及收集整理,把最好的留下。
    包括但不限于JVM、计算机科学、算法、数据库、分布式、Spring全家桶、微服务、高并发、Docker容器、ELK、大数据等相关知识,一起进步,一起成长。
热门推荐
[若依]微服务springcloud版新建增添加一个
[md]若依框架是一个比较出名的后台管理系统,有多个不同版本。
[CXX1300] CMake '3.18.1' was not
[md][CXX1300] CMake '3.18.1' was not found in SDK, PATH, or
java 解析modbus 协议 Modbus4j应用 使用mo
[md]本文记录使用java开发modbus协议程序,与串口进行连接,使用