`
beagoodboy
  • 浏览: 95582 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论
阅读更多
CAP定理指在设计分布式系统时,一致性(Consistent)、可用性(Availability)、Partition Tolerance(分区容忍性)三个属性不可能同时满足,该定理也叫做布鲁尔定理。CAP定理明确了分布式系统所能实现系统的局限性,目前互联网中的很多分布式系统是基于首要满足可用性和分区容忍性而设计的。在这里,不打算提及目前火热的Cassandra、Voldemort等分布式存储系统,而是打算介绍一下CAP定理。

形式化描述
一致性:所有在分布式系统上的操作有一个总体上的顺序,每一个操作看起来就像是在一个单独的瞬间完成的。这就要求分布式系统的运行就像是在一个单节点上一样,在一个时间响应一个操作。

可用性:对于一个可用性的分布式系统,每一个非故障的节点必须对每一个请求作出响应。也就是,该系统使用的任何算法必须最终终止。当同时要求分区容忍性时,这是一个很强的定义:即使是严重的网络错误,每个请求必须终止。

分区容忍性:为了定义分区容忍性,假定网络满足如下条件:网络是可能丢失从一个节点发往另一个节点的任意消息,当网络被分区(隔断)时,所有从一个分区的节点发往另一个分区的消息将会丢失。一致性要求每个响应必须是一致的,即使系统内部的消息没有被正确地发送。可用性要求从客户端接收请求的任一节点必须被响应,即使任意的消息可能没有被正确地发送。

异步网络
在异步网络模型中,没有统一时钟,所有节点仅根据接收到的消息和本地的计算进行决策。
定理一:
在一个异步网络模型中,没有可能实现一个满足以下属性的读写数据对象:
1、可用性
2、一致性
对于所有对等运算(包括消息会丢失的)
证明:
假设存在一个算法A满足这些条件:一致性、可用性、分区容忍性。我们构造一次A的执行,包括一个返回非一致结果的请求。假设网络包含至少两个节点,那么它可以被分为不相关的非空集合:{G,H}。假设所有G和H之间的通讯消息都丢失,这是可能的。如果这时在G上有一个写操作,接着H上有一个读操作,那么读操作将无法返回早些的写操作。■
推论一:
在一个异步网络模型中,没有可能实现一个满足以下属性的读写数据对象:
1、可用性,所有对等运算
2、一致性,所有对等运算,但消息不会丢失
证明:
主要问题是在异步网络模型中一个算法没有办法去判断一个消息是否丢失或者在传输通道中被延迟。因此,如果在运算中不会丢失任何消息的前提下存在一个能够保证一致性的算法,那么该算法也能够在所有运算(消息可能丢失)情况下保证一致性。这将与定理一矛盾。■

部分同步网络
假设一个部分同步的网络模型,在这里,所有的节点都有一个时钟,并且所有的时钟以一个相同的速度增长。然而,这些时钟并不是同步的,在相同的时间,它们显示不同的时间值。事实上,时钟扮演计时器的角色:处理器可以根据本地状态变量去衡量流逝了多少时间。一个本地的计时器可以用来调度某事件之后的多长时间间隔进行另一个操作。进一步地,假设每一个消息要么在给定的时间s内到达,要么丢失。并且,所有的节点在给定时间t内处理完一个接收到的消息。
定理二:
在一个部分同步网络模型中,没有可能实现一个满足以下属性的读写数据对象:
1、可用性
2、一致性
对于所有对等运算(包括消息会丢失的)
证明:
证明方法与定理一一样。■
但是在部分同步模型中,类似与异步模型推论一的结论就不存在了,因此推论一的假设基于节点无法判断一个消息是否丢失。而在部分同步模型中,存在部分同步算法可以在所有消息传送正常的情况下返回一致性的数据,而仅仅在消息丢失时返回非一致性数据。对于读或写请求,节点发送一个消息给另一个节点,如果消息返回了,那么节点发送请求的数据;如果消息在给定的2s+t时间内没有返回,那么该节点断定消息丢失了,节点就可能返回一个不一致的请求数据。

理论参考价值
在Google使用廉价的PC机搭建了强大的、高可靠的计算和存储平台之后,互联网公司一致性地选择使用PC集群支撑全部的业务,这个理论指明了实现满足可用性、分区容忍性的分布式系统是可行的,并且该分布式系统在没有故障的情况下可以提供良好的一致性读写。

参考
Lynch, Nancy, and Seth Gilbert. “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services.” ACM SIGACT News, v. 33 issue 2, 2002, p. 51-59.
分享到:
评论

相关推荐

    Brewer’CAP原理--CAP定理

    CAP定理指在设计分布式系统时,一致性(Consistent)、可用性(Availability)、Partition Tolerance(分区容忍性)三个属性不可能同时满足,该定理也叫做布鲁尔定理。CAP定理明确了分布式系统所能实现系统的局限性...

    掌握 CAP 定理,以及每个的含义和 CAP 定理的应用.docx

    CAP 定理最初是由加州大学伯克利分校的计算机科学家埃里克·布鲁尔(Eric Brewer)在 2000 年的 ACM PODC 上提出的一个猜想,也因此被叫做布鲁尔定理。后来在 2002 年,麻省理工学院的赛斯·吉尔伯特(Seth Gilbert...

    CAP定理的详细讲述

    CAP定理的详细讲述,附带详细参考文献,方便读者查阅。

    jinghongdaxiong#Grokking-System-Design#CAP定理1

    CAP定理认为,在设计分布式系统时,我们只能选择以下两种:一致性: 所有节点在同一时间看到相同的数据。但是,如果网络中有一个分区,那么在客户机从最新的分区中读取

    elgchat#elgchat#分布式CAP定理1

    1.商品服务写入主数据库成功, 则想从数据库查询数据也成功 2.商品服务写入主数据库失败,则向从数据库查询也失败 1. 写入主数据库后要数据同步到从数据库 2.

    java面试最全八股文

    CAP原则(CAP定理)、BASE理论 一、CAP原则 一致性与可用性的决择编辑 取舍策略 BASE理论 基本可用 最终一致性 小结: 与NoSQL的关系编辑 CAP的是什么关系 为什么会是这样 选择权衡 延伸 分布式系统的典型应用 分布式...

    分布式数据库Cassandra 一致性详解.zip

    1.CAP定理理与Cassandra 1.1 Cassandra优势 2.Cassandra ⼀一致性实现 2.1 CAS 2.2 Quorum读写 2.3 不不⼀一致产⽣生原因 2.4 Hinted handoff 2.5 Read repair 2.6 Manual repair 3.Cassandra应⽤用场景 ...

    分布式事务的详细介绍。

    CAP原则又称CAP定理,指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、 Partition tolerance(分区容错性),三者不可得兼。 CAP原则是NOSQL数据库的基石。 分布式系统的CAP理论: ...

    2021年数据库研究报告

    数据库设计CAP定理 一致性Consistency 可用性Availability 分区容错性Partition-Tolerance NoSQL数据库BASE原则 基本可用Basically Available 软状态Soft state 最终一致性Eventual consistency 单体系统到分布式...

    新美大MySQL数据一致性探索.zip

    同时,文档还探讨了分布式系统中的数据一致性问题,包括CAP定理、BASE理论等,并提出了相应的解决方案。此外,文档还提供了一些实用的工具和方法,帮助读者更好地理解和实践数据一致性。总的来说,这是一份理论与...

    cap-faq:CAP常见问题

    对于分布式系统工程师来说,没有一个主题比经常引用,经常被误解的CAP定理更具争议性。 该常见问题解答的目的是解释有关CAP的知识,以帮助定理新手快速入门,并解决一些常见的误解或分歧。 当然,我很可能在这里犯...

    事务讨论笔记

    CAP定理是由加州大学伯克利分校Eric Brewer教授提出来的,他指出WEB服务无法同时满足一下3个属性: 一致性(Consistency) : 客户端知道一系列的操作都会同时发生(生效) 可用性(Availability) : 每个操作都必须以...

    大数据期末知识点总结.pdf

    CAP定理: 定理: ⼀个分布式系统不可能同时满⾜⼀致性、可⽤性和分区容错性三个系统需求,最多只能同时满⾜俩个系统需求。在考虑满⾜系统需求时,要 根据实际需要来选择关注点,进⽽采⽤相应的策略。 函数式编程...

    beauty of architecture

    从CAP定理看设计哲学 5.架构治理 企业架构治理 企业内EA领导团队的建制 数据治理标准体系-DAMA MIT企业架构成熟度模型 企业架构实施绩效的七个度量指标 7 Key Enterprise Architecture Metrics 延伸阅读业务...

    2019Java微服务架构 2.0-全网首发-网盘地址

    004-微服务的优点.mp4章节1-什么是微服务\千锋java教程:005-微服务的缺点.mp4章节1-什么是微服务\千锋java教程:006-CAP 定理与 BASE 理论mp4.mp4章节1-什么是微服务\千锋java教程:007-如何应对高并发.mp4章节10-...

    1.分布式架构面试题汇总.zip

    Eureka 服务注册中心 与客户端一起通过心跳机制完成服务注册与发现 通过搭建集群完成故障转移达到高可用性的目的,因为去中心化,满足了CAP定理中的AP原则(侧重可用性)

    nosql驱动程序:nosql驱动程序

    CAP定理,AXP 2015,JWN 2016 C CAP中的一致性实际上意味着线性化,这是一个非常具体(非常强烈)的一致性概念。 特别地,即使C也代表“一致性”,它与ACID中的C无关。 线性化的含义如下。 如果操作B在操作A成功...

    OneSlide:OneSlide是一种学习格式,其中一张幻灯片涵盖了一个技术主题

    算法:CAP定理 C ++:堆栈和堆上的内存分配 Java:受谁保护? Java:PECS js:...休息vs ...传播 待办事项 js:设置对象 js:数组功能方法 Java:接口与类 Java:空值与可选值 Java:清单:ArrayList与LinkedList ...

    DBD_Assignment2

    什么是CAP定理? 一致性,可用性,分区容限。 Et DB Paradigme kanifølgeCAP teorien kun有2 ud af de 3 fordele。 一致性:Altid具有adgang til den seneste数据。 可用性:等系统在100%轮胎后均可使用skalv

    cqrs-clean-eventual-consistency:使用清洁架构,多个数据库和最终一致性的CQRS

    CQRS分布式混沌,CAP定理 :floppy_disk: 如何使用? 您需要以下一些工具: 码头工人 Visual Studio 2019 .Net Core 3.0 :bullseye: 清洁建筑 这是此微服务模板的基本架构: 尊重策略规则,依赖性始终指向内部...

Global site tag (gtag.js) - Google Analytics