分布式系统理论基础二-CAP

2024-09-06 22:38

本文主要是介绍分布式系统理论基础二-CAP,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


GitHub:https://github.com/wangzhiwubigdata/God-Of-BigData

                   关注公众号,内推,面试,资源下载,关注更多大数据技术~大数据成神之路~预计更新500+篇文章,已经更新50+篇~ 

引言

CAP是分布式系统、特别是分布式存储领域中被讨论最多的理论,“什么是CAP定理?”在Quora 分布式系统分类下排名 FAQ 的 No.1。CAP在程序员中也有较广的普及,它不仅仅是“C、A、P不能同时满足,最多只能3选2”,以下尝试综合各方观点,从发展历史、工程实践等角度讲述CAP理论。希望大家透过本文对CAP理论有更多地了解和认识。

CAP定理

CAP由Eric Brewer在2000年PODC会议上提出[1][2],是Eric Brewer在Inktomi[3]期间研发搜索引擎、分布式web缓存时得出的关于数据一致性(consistency)、服务可用性(availability)、分区容错性(partition-tolerance)的猜想:
It is impossible for a web service to provide the three following guarantees : Consistency, Availability and Partition-tolerance.
 
该猜想在提出两年后被证明成立[4],成为我们熟知的CAP定理:

  • 数据一致性(consistency):如果系统对一个写操作返回成功,那么之后的读请求都必须读到这个新数据;如果返回失败,那么所有读操作都不能读到这个数据,对调用者而言数据具有强一致性(strong consistency) (又叫原子性 atomic、线性一致性 linearizable consistency)
  • 服务可用性(availability):所有读写请求在一定时间内得到响应,可终止、不会一直等待
  • 分区容错性(partition-tolerance):在网络分区的情况下,被分隔的节点仍能正常对外服务

在某时刻如果满足AP,分隔的节点同时对外服务但不能相互通信,将导致状态不一致,即不能满足C;如果满足CP,网络分区的情况下为达成C,请求只能一直等待,即不满足A;如果要满足CA,在一定时间内要达到节点状态一致,要求不能出现网络分区,则不能满足P。
 
C、A、P三者最多只能满足其中两个,和FLP定理一样,CAP定理也指示了一个不可达的结果(impossibility result)。

91ac5357657dbc883f5b40725f7b4140.png

CAP的工程启示

CAP理论提出7、8年后,NoSql圈将CAP理论当作对抗传统关系型数据库的依据、阐明自己放宽对数据一致性(consistency)要求的正确性[6],随后引起了大范围关于CAP理论的讨论。
 
CAP理论看似给我们出了一道3选2的选择题,但在工程实践中存在很多现实限制条件,需要我们做更多地考量与权衡,避免进入CAP认识误区[7]。

1、关于 P 的理解

Partition字面意思是网络分区,即因网络因素将系统分隔为多个单独的部分,有人可能会说,网络分区的情况发生概率非常小啊,是不是不用考虑P,保证CA就好。要理解P,我们看回CAP证明中P的定义:
In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.
 
网络分区的情况符合该定义,网络丢包的情况也符合以上定义,另外节点宕机,其他节点发往宕机节点的包也将丢失,这种情况同样符合定义。现实情况下我们面对的是一个不可靠的网络、有一定概率宕机的设备,这两个因素都会导致Partition,因而分布式系统实现中 P 是一个必须项,而不是可选项。
 
对于分布式系统工程实践,CAP理论更合适的描述是:在满足分区容错的前提下,没有算法能同时满足数据一致性和服务可用性[11]:
In a network subject to communication failures, it is impossible for any web service to implement an atomic read/write shared memory that guarantees a response to every request.

2、CA非0/1的选择

CAP定理证明中的一致性指强一致性,强一致性要求多节点组成的被调要能像单节点一样运作、操作具备原子性,数据在时间、时序上都有要求。如果放宽这些要求,还有其他一致性类型:

  • 序列一致性(sequential consistency):不要求时序一致,A操作先于B操作,在B操作后如果所有调用端读操作得到A操作的结果,满足序列一致性

  • 最终一致性(eventual consistency):放宽对时间的要求,在被调完成操作响应后的某个时间点,被调多个节点的数据最终达成一致

可用性在CAP定理里指所有读写操作必须要能终止,实际应用中从主调、被调两个不同的视角,可用性具有不同的含义。当P(网络分区)出现时,主调可以只支持读操作,通过牺牲部分可用性达成数据一致。

工程实践中,较常见的做法是通过异步拷贝副本(asynchronous replication)、quorum/NRW,实现在调用端看来数据强一致、被调端最终一致,在调用端看来服务可用、被调端允许部分节点不可用(或被网络分隔)的效果。

3、跳出CAP

CAP理论对实现分布式系统具有指导意义,但CAP理论并没有涵盖分布式工程实践中的所有重要因素。
 
例如延时(latency),它是衡量系统可用性、与用户体验直接相关的一项重要指标。CAP理论中的可用性要求操作能终止、不无休止地进行,除此之外,我们还关心到底需要多长时间能结束操作,这就是延时,它值得我们设计、实现分布式系统时单列出来考虑。
 
延时与数据一致性也是一对“冤家”,如果要达到强一致性、多个副本数据一致,必然增加延时。加上延时的考量,我们得到一个CAP理论的修改版本PACELC:如果出现P(网络分区),如何在A(服务可用性)、C(数据一致性)之间选择;否则,如何在L(延时)、C(数据一致性)之间选择。
 
小结以上介绍了CAP理论的源起和发展,介绍了CAP理论给分布式系统工程实践带来的启示。
 
CAP理论对分布式系统实现有非常重大的影响,我们可以根据自身的业务特点,在数据一致性和服务可用性之间作出倾向性地选择。通过放松约束条件,我们可以实现在不同时间点满足CAP(此CAP非CAP定理中的CAP,如C替换为最终一致性)。
 
有非常非常多文章讨论和研究CAP理论,希望这篇对你认识和了解CAP理论有帮助。
 
[1] Harvest, Yield, and Scalable Tolerant Systems, Armando Fox , Eric Brewer, 1999
[2] Towards Robust Distributed Systems, Eric Brewer, 2000
[3] Inktomi’s wild ride - A personal view of the Internet bubble, Eric Brewer, 2004
[4] Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web, Seth Gilbert, Nancy Lynch, 2002
[5] Linearizability: A Correctness Condition for Concurrent Objects, Maurice P. Herlihy,Jeannette M. Wing, 1990
[6] Brewer’s CAP Theorem - The kool aid Amazon and Ebay have been drinking, Julian Browne, 2009
[7] CAP Theorem between Claims and Misunderstandings: What is to be Sacrificed?, Balla Wade Diack,Samba Ndiaye,Yahya Slimani, 2013
[8] Errors in Database Systems, Eventual Consistency, and the CAP Theorem, Michael Stonebraker, 2010
[9] CAP Confusion: Problems with ‘partition tolerance’, Henry Robinson, 2010
[10] You Can’t Sacrifice Partition Tolerance, Coda Hale, 2010
[11] Perspectives on the CAP Theorem, Seth Gilbert, Nancy Lynch, 2012
[12] CAP Twelve Years Later: How the “Rules” Have Changed, Eric Brewer, 2012
[13] How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, Lamport Leslie, 1979
[14] Eventual Consistent Databases: State of the Art, Mawahib Elbushra , Jan Lindström, 2014
[15] Eventually Consistent, Werner Vogels, 2008
[16] Speed Matters for Google Web Search, Jake Brutlag, 2009
[17] Consistency Tradeoffs in Modern Distributed Database System Design, Daniel J. Abadi, 2012
[18] A CAP Solution (Proving Brewer Wrong), Guy’s blog, 2008
[19] How to beat the CAP theorem, nathanmarz , 2011
[20] The CAP FAQ, Henry Robinson

这篇关于分布式系统理论基础二-CAP的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1143323

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

c++基础版

c++基础版 Windows环境搭建第一个C++程序c++程序运行原理注释常亮字面常亮符号常亮 变量数据类型整型实型常量类型确定char类型字符串布尔类型 控制台输入随机数产生枚举定义数组数组便利 指针基础野指针空指针指针运算动态内存分配 结构体结构体默认值结构体数组结构体指针结构体指针数组函数无返回值函数和void类型地址传递函数传递数组 引用函数引用传参返回指针的正确写法函数返回数组

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。

分布式系统的主要考虑

异构性:分布式系统由于基于不同的网路、操作系统、计算机硬件和编程语言来构造,必须要考虑一种通用的网络通讯协议来屏蔽异构系统之间的禅意。一般交由中间件来处理这些差异。缺乏全球时钟:在程序需要协作时,它们通过交换消息来协调它们的动作。紧密的协调经常依赖于对程序动作发生时间的共识,但是,实际上网络上计算机同步时钟的准确性受到极大的限制,即没有一个正确时间的全局概念。这是通过网络发送消息作为唯一的通信方式