内容简介:CAP定理指出,在一个分布式系统中,对于一致性、可用性、分区容错这三个特性,不可能同时满足,而是必须有所舍弃。我们设计分布式系统时,必须在三者之间(尤其是一致性和可用性之间)有所取舍和平衡。作者:王克锋出处:
CAP定理指出,在一个分布式系统中,对于一致性、可用性、分区容错这三个特性,不可能同时满足,而是必须有所舍弃。我们设计分布式系统时,必须在三者之间(尤其是一致性和可用性之间)有所取舍和平衡。
作者:王克锋
出处: https://kefeng.wang/2018/08/01/distributed-cap/
版权: 自由转载-非商用-非衍生-保持署名 ,转载请标明作者和出处。
1 概述
1.1 概念
CAP定理(CAP theorem),又被称作布鲁尔定理(Brewer's theorem),是分布式系统中的一个基本定理。
它指出任何分布式系统(Distributed System)中,最多具有一致性、可用性、分区容错这三个特性中的两个。
也就是说,三个特性无法兼顾,必须有所取舍。
1.2 历史
- 1998年,加州大学(University of California)的计算机科学家埃里克·布鲁尔(Eric Brewer)提出该原理,并于次年出版;
- 2000年,Eric Brewer 在的分布式计算原则研讨会(Symposium on Principles of Distributed Computing)上提出该猜想;
- 2002年,麻省理工学院(MIT)的赛斯·吉尔伯特和南希·林奇发表了布鲁尔猜想的证明,使之成为一个定理。
2 三个特性
2.0 初始状态
我们假定一个非常简易的、只有 G1/G2 两台服务器构成的分布式系统:
G1/G2 之间可以相互通信,两者都有相同的变量v,初始值都是v0。
客户端 C 与 G1/G2 都可以通信,读写操作可以从 G1/G2 中任选。
初始状态,如下图:
客户端读取,如下图:
客户端写入,如下图:
2.1 一致性(Consistence)
一致性是指,各节点的数据保证一致(每次成功写入之后,无论从哪个节点读取,都能读取到最新数据),相当于向所有节点的写操作是原子操作(要么全部失败要么全部成功)。一致性有三种策略(CAP指的是强一致性):
- 强一致性:写操作完成后,后续的读操作都能看到最新数据;
- 弱一致性:能容忍部分或全部都看不到最新数据;
- 最终一致性:经过一段时间后,都能看到最新数据。
不一致的情形,写操作至G1,但未(或尚未)同步至G2,就从G2读读取。如下图:
一致的情形,写操作至G1,成功同步至G2之后,才允许进行读操作。如下图:
2.2 可用性(Availability)
可用性是指,每次向未崩溃的节点发送请求,总能保证收到响应数据(允许不是最新数据)。
参照前面“一致性”中的两种情形,可见一致性和可用性无法兼顾:
- 若要保证一致性:则必须进行节点间数据同步,同步期间数据锁定,导致期间的读取失败或超时,破坏了可用性;
- 若要保证可用性:则不允许节点间同步期间锁定,这又破坏了一致性。
2.3 分区容错(Partition tolerance)
分区容错是指,容许节点 G1/G2 间传递消息的差错(延迟或丢失),而不影响系统继续运行。
分布式系统中,必须满足 CAP 中的 P,此时只能在 C/A 之间作出取舍。
CAP 经常被误解为“三选二”,但实际上必须满足P,然后在 C/A 之间做出选择。
3 CAP 的证明
反证法。假设可以同时满足一致性、可用性、分区容错这三个特性,由于满足分区容错,可以切断 G1/G2 的连线,如下图:
- 当 C 把 v1 写入 G1 后,由于可用性,G1 必须成功响应(由于 G1/G2 不通,G2 仍旧是 v0);
- 然后,C 向 G2 读取数据,由于可用性,G2 必须成功响应,但响应的值是陈旧的 v0;
- 可见,C 写入了 v1,但读到了 v0,没有满足一致性,可见三个特性不可能同时满足。
4 CAP 的应用
CAP 理论,被看成分布式系统(尤其是分布式存储)的理论基础。
- 舍弃P(选择C/A):单点的传统关系型数据库 DBMS(MySQL/Oracle),但如果采用集群就必须考虑P了;
- 舍弃A(选择C/P):是分布式系统要保证P,而且保证一致性,如 ZooKeeper / Redis / MongoDB / HBase;
- 舍弃C(选择A/P):是分布式系统要保证P,而且保证可用性,如 CoachDB / Cassandra / DynamoDB。
对于一个分布式系统来说,CAP三者中,
- P是基本要求,只能通过基础设施提升,无法通过降低 C/A 来提升;
- 然后在 C/A 两者之间权衡。
一个还不错的策略是:保证可用性和分区容错,舍弃强一致性,但保证最终一致性,比如一些高并发的站点(秒杀、淘宝、12306)。最终近似于兼顾了三个特性。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 分布式理论之CAP定理(布鲁尔定理)
- 分布式系统 - CAP定理
- 分布式系统 | CAP 定理图解
- 面试官:说说分布式的CAP定理?
- 分布式的 CAP 定理和一致性模型
- 科普 | 分布式共识的工作原理,Part-2:共识问题与 FLP 不可能定理
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Kotlin程序员面试算法宝典
孙伟、楚秦 / 机械工业出版社 / 2018-12 / 69
本书是一本讲解程序员面试笔试算法的书籍。在写法上,除了讲解如何解答算法问题以外,还引入了例子辅以说明,以便读者能够更加容易地理解。 本书将程序员面试笔试过程中的各类算法类真题一网打尽。在题目的广度上,通过各种渠道,搜集了近3年来几乎所有IT企业面试笔试算法高频题目,所选择题目均为企业招聘使用题目;在题目的深度上,本书由浅入深、庖丁解牛式地分析每一个题目,并提炼归纳,同时,引入例子与源代码、时......一起来看看 《Kotlin程序员面试算法宝典》 这本书的介绍吧!