首页 > 编程语言 >1.理论、算法、协议

1.理论、算法、协议

时间:2023-12-09 16:22:39浏览次数:33  
标签:协议 CAP 理论 ZooKeeper 系统 AP 算法 一致性 节点

1.CAP 理论

  CAP 也就是 Consistency(一致性)Availability(可用性)Partition Tolerance(分区容错性) 这三个单词首字母组合。

在理论计算机科学中,CAP 定理(CAP theorem)指出对于一个分布式系统来说,当设计读写操作时,只能同时满足以下三点中的两个:

  • 一致性(Consistency) : 所有节点访问同一份最新的数据副本
  • 可用性(Availability): 非故障的节点在合理的时间内返回合理的响应(不是错误或者超时的响应)。
  • 分区容错性(Partition Tolerance) : 分布式系统出现网络分区的时候,仍然能够对外提供服务。
什么是网络分区?
  分布式系统中,多个节点之间的网络本来是连通的,但是因为某些故障(比如部分节点网络出了问题)某些节点之间不连通了,整个网络就分成了几块区域。

CAP 理论中分区容错性 P 是一定要满足的,在此基础上,只能满足可用性 A 或者一致性 C。分布式系统理论上不可能选择 CA 架构,只能选择 CP 或者 AP 架构。 比如 ZooKeeper、HBase 就是 CP 架构,Cassandra、Eureka 就是 AP 架构,Nacos 不仅支持 CP 架构也支持 AP 架构。

 

为啥不可能选择 CA 架构呢?

  举个例子:若系统出现“分区”,系统中的某个节点在进行写操作。为了保证 C, 必须要禁止其他节点的读写操作,这就和 A 发生冲突了。如果为了保证 A,其他节点的读写操作正常的话,那就和 C 发生冲突了。

选择 CP 还是 AP 的关键在于当前的业务场景,没有定论,比如对于需要确保强一致性的场景如银行一般会选择保证 CP 。

如果网络分区正常的话(系统在绝大部分时候所处的状态),也就说不需要保证 P 的时候,C 和 A 能够同时保证。

 

常见的可以作为注册中心的组件有:ZooKeeper、Eureka、Nacos:

  • ZooKeeper 保证的是 CP。 任何时刻对 ZooKeeper 的读请求都能得到一致性的结果,但是, ZooKeeper 不保证每次请求的可用性比如在 Leader 选举过程中或者半数以上的机器不可用的时候服务就是不可用的。
  • Eureka 保证的则是 AP。 Eureka 在设计的时候就是优先保证 A (可用性)。在 Eureka 中不存在什么 Leader 节点,每个节点都是一样的、平等的。因此 Eureka 不会像 ZooKeeper 那样出现选举过程中或者半数以上的机器不可用的时候服务就是不可用的情况。 Eureka 保证即使大部分节点挂掉也不会影响正常提供服务,只要有一个节点是可用的就行了。只不过这个节点上的数据可能并不是最新的。
  • Nacos 不仅支持 CP 也支持 AP。
由于 Quorum 模式下的读请求不会触发各个 ZooKeeper 节点之间的数据同步,因此在某些情况下还是可能会存在读取到旧数据的情况,导致不同的客户端视图上看到的结果不同,这可能是由于网络延迟、丢包、重传等原因造成的。
ZooKeeper 为了解决这个问题,提供了 Watcher 机制和版本号机制来帮助客户端检测数据的变化和版本号的变更,以保证数据的一致性。

 

2.BASE理论

 BASE 理论本质上是对 CAP 的延伸和补充,更具体地说,是对 CAP 中 AP 方案的一个补充。
  AP 方案只是在系统发生分区的时候放弃一致性,而不是永远放弃一致性。在分区故障恢复后,系统应该达到最终一致性。这一点其实就是 BASE 理论延伸的地方。

BASE 理论三要素:

基本可用

  基本可用是指分布式系统在出现不可预知故障的时候,允许损失部分可用性。但是,这绝不等价于系统不可用。

什么叫允许损失部分可用性呢?
· 响应时间上的损失: 正常情况下,处理用户请求需要 0.5s 返回结果,但是由于系统出现故障,处理用户请求的时间变为 3 s。
· 系统功能上的损失:正常情况下,用户可以使用系统的全部功能,但是由于系统访问量突然剧增,系统的部分非核心功能无法使用。

软状态

  软状态指允许系统中的数据存在中间状态(CAP 理论中的数据不一致),并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

最终一致性

  最终一致性强调的是系统中所有的数据副本,在经过一段时间的同步后,最终能够达到一个一致的状态。因此,最终一致性的本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性。

分布式一致性的 3 种级别:
· 强一致性:系统写入了什么,读出来的就是什么。
· 弱一致性:不一定可以读取到最新写入的值,也不保证多少时间之后读取到的数据是最新的,只是会尽量保证某个时刻达到数据一致的状态。
· 最终一致性:弱一致性的升级版,系统会保证在一定时间内达到数据一致的状态。业界比较推崇是最终一致性级别,但是某些对数据一致要求十分严格的场景比如银行转账还是要保证强一致性。

 

 

 

                                     

 

 

标签:协议,CAP,理论,ZooKeeper,系统,AP,算法,一致性,节点
From: https://www.cnblogs.com/cjhtxdy/p/17891081.html

相关文章

  • AMQP协议中的,消息队列RabbitMQ,ActiveMQ,Apache Kafka区别是什么?
    都是基于AMQP协议来的一种实现方式。参考chatGPT4回答请使用Markdown表格来展示RabbitMQ、ActiveMQ和ApacheKafka之间的区别:维度RabbitMQActiveMQApacheKafka语言ErlangJavaScala/Java协议AMQP、STOMP、MQTTAMQP、STOMP、OpenWire自定义协议......
  • 电台覆盖区域的贪心算法
    1.贪心算法电台覆盖区域求最优解问题题目:假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让所有的地区都可以接收到信号广播台覆盖地区K1“北京”,“上海”,“天津”K2“广州”,“北京”,“深圳”K3“成都”,“......
  • 详解十大经典排序算法(六):快速排序(QuickSort)
    算法原理分区(Partition):选择一个基准元素,将数组分为两个子数组,小于基准的放在左边,大于基2准的放在右边。递归排序:对左右两个子数组分别进行快速排序。合并:不需要实际的合并操作,因为在分解和递归排序阶段已经完成了排序。算法描述快速排序是一种基于分治思想的高效排序算法,由英国......
  • 最小费用组最大流——EK算法
    时间复杂度O(nm^2),理论上限//n,m,s,t,分别代表该网络的点数n,网络的边数m,源点编号s,汇点编号t。constintN=5010,M=100010,INF=1e8;intn,m,S,T;structedge{intv,c,w,ne;}e[M];inth[N],idx=1;//从2,3开始配对intd[N],mf[N],pre[N],vis[N];intflow,cost;voidadd(inta,......
  • Python算法——快速排序
    快速排序(QuickSort)是一种高效的分治排序算法,它选择一个基准元素,将数组分成两个子数组,小于基准的放在左边,大于基准的放在右边,然后递归地排序子数组。快速排序通常比冒泡排序和选择排序更高效,特别适用于大型数据集。本文将详细介绍快速排序的工作原理和Python实现。快速排序的工作原......
  • Top Tree 相关理论扯淡
    目录前言TopCluster分解与TopTree从树分块说起簇、簇操作、树的簇表示法基于重量平衡的静态TopTree动态TopTree簇与TopTree的性质静态TopTree的应用树上信息合并链上修改与查询子树修改与查询维护动态直径例1:【2023集训队互测Round12】不跳棋维护动态重心维护动......
  • 基于小波变换的分形信号r指数求解算法matlab仿真
    1.算法运行效果图预览   2.算法运行软件版本matlab2022a 3.算法理论概述       基于小波变换的分形信号r指数求解算法是一种利用小波变换和分形理论对信号进行分析的方法。下面将详细介绍这种算法的原理和数学公式。         分形信号是一种......
  • 智能AI算法解决各行业中的皮带跑偏、异物问题的有效方法
    随着工业化的发展,皮带输送机已经成为各行业中不可或缺的重要设备,但是在使用过程中,由于各种原因,皮带常常出现跑偏问题,给生产运营带来了诸多困扰。不仅仅是矿山行业,钢铁、火电、港口等行业也都面临着皮带跑偏问题。那么,对于这些行业,如何解决皮带跑偏问题呢?矿山行业是皮带输送机的主要......
  • 基于FPGA的图像缩小算法实现,包括tb测试文件和MATLAB辅助验证
    1.算法运行效果图预览   将FPGA的处理结果导出到matlab中显示图像效果:   2.算法运行软件版本vivado2019.2 matlab2022a 3.算法理论概述      图像放小算法主要通过抽取算法实现,常见的抽取算法最大值抽取,和均值抽取。其示意图如下所示:    ......
  • KMP算法
    1.暴力匹配暴力匹配算法的步骤如下:遍历主串中的每个可能的起始位置,从第一个字符开始。对于每个起始位置,逐个比较主串和模式串中对应位置的字符。如果发现不匹配的字符,即主串和模式串中对应位置的字符不相等,将模式串向右移动一个位置,继续比较。如果模式串完全匹配主串中的一......