常见分布式理论(CAP、BASE)和一致性协议(Gosssip、Raft)

2022年01月16日 阅读数:2
这篇文章主要向大家介绍常见分布式理论(CAP、BASE)和一致性协议(Gosssip、Raft),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

image.png

1、CAP理论与BASE理论:

一、什么是 CAP 理论:

  • C:Consistency 一致性:指强一致性,分布式系统中的全部节点在同一时刻具备一样的值、都是最新的数据副本,一致性保证了无论向哪台服务器写入数据,其余的服务器能实时同步数据
  • A:Availability 可用性:部分结点宕机不影响整个集群对外提供服务,每次向未故障的节点发送请求,服务节点总能保证在有限的时间内处理完成并进行响应,从用户角度来看就是不会出现系统操做失败或者访问超时等问题,可是系统内部可能会出现网络延迟等问题
  • P:Partition Tolerance 分区容错性:因为网络的问题错综复杂,若是某个节点由于网络等问题形成数据不一致,或者数据延迟好久才同步过来,虽然会影响部分节点数据的时效性,可是服务节点依然是可用的,分布式系统要能容忍这种状况的,也就是说,尽管网络上有部分消息丢失,但系统仍然可继续工做。

分布式系统中,CAP是没法同时知足的,只能知足CAP中的两种,所以在设计分布式架构时,必须作出取舍,而对于分布式系统,分区容忍性是基本要求,必需要知足,不然就失去了价值。由于是节点宕机和网络故障大几率事件,很难避免,而当出现这种状况时,不可能同时保持一致性和可用性,因此设计分布式系统,就是在一致性和可用性之间取一个平衡。算法

image

那为何说在P知足的状况下,为何说CA不能同时知足呢?咱们来经过假设看一看,若是CA同时知足会怎么样:数据库

(1)假设如今要求知足C(一致性),那么就是说全部的节点在某一刻提供的数据都必须一致,咱们知道在P的状况,是不可能保证的,要保证的话,就只能把其余节点所有干掉,好比禁止读写,那这其实就是和A是相悖的(某些节点虽然延迟,可是节点自己可用)安全

(2)假设如今要求知足A(可用性),那么就是说只要节点自己没什么问题,就能够对外提供服务,哪怕有点数据延迟,很明显这确定是和C相悖的。服务器

二、一致性的类别:

CAP 是分布式事务处理的理论基础,在分布式事务的最终解决方案中通常选择牺牲一致性来换取可用性和分区容错性,但这里的 “牺牲一致性” 并非彻底放弃数据的一致性,而是放弃强一致性而换取弱一致性。一致性通常能够分为如下三种:markdown

(1)强一致性:在任意时刻,全部节点中的数据是同样的,系统中的某个数据被成功更新后,后续任何对该数据的读取操做都将获得更新后的值。好比传统数据库的事务特性 ACID,就是追求强一致性模型。网络

一个集群须要对外部提供强一致性,就务必会损耗可用性,只要集群内部某一台服务器的数据发生了改变,那么就须要等待集群内其余服务器的数据同步完成后,才能正常的对外提供服务。架构

(2)弱一致性:系统中的某个数据被更新后,后续对该数据的读取操做可能获得更新后的值,也多是更改前的值,但即便过了不一致时间窗口后,后续对该数据的读取也不必定是最新值。分布式

(3)最终一致性:是弱一致性的特殊形式,虽然不保证在任意时刻任意节点上的同一份数据都是相同的,但通过一段时间后,全部服务节点间的数据最终会达到一致的状态ide

弱一致性即便过了不一致时间窗口,后续的读取也不必定能保证一致,而最终一致性过了不一致窗口后,后续的读取必定保证一致。性能

三、什么是 BASE 理论:

BASE 理论是指,Basically Available(基本可用)、Soft-state( 软状态)、Eventual Consistency(最终一致性),是基于CAP定理演化而来,是对CAP中一致性和可用性权衡的结果。核心思想是即便没法作到强一致性,但每一个业务根据自身的特色,采用适当的方式来使系统达到最终一致性。

  • BA 基本可用:指分布式系统在出现故障的时候,容许损失部分可用性,保证核心可用。但不等价于不可用。好比:搜索引擎0.5秒返回查询结果,但因为故障,2秒响应查询结果;网页访问过大时,部分用户提供降级服务等。
  • 软状态:软状态是指容许系统存在中间状态,而且该中间状态不会影响系统总体可用性,即容许系统在不一样节点间副本同步的时候存在延时。
  • 最终一致性:系统中的全部数据副本通过必定时间后,最终可以达到一致的状态,不须要实时保证系统数据的强一致性。

不少时候咱们并不要求数据的强一致性,而 BASE 经过牺牲强一致性来得到更好的可用性,因此 BASE 理论的适用性更普遍,好比更适合面向的是大型高可用可扩展的分布式系统

柔性事务和刚性事务:柔性事务知足BASE理论(基本可用,最终一致),刚性事务知足ACID理论。

2、一致性协议:

一、Gossip协议:

集群每每是由多个节点共同组成的,当一个节点加入集群或者一个节点从集群中下线的时候,都须要让集群中其余的节点知道,这样才能将数据信息分享给新节点而忽略下线节点。

image

如上图,A、B、C 节点之间能够互相传递消息,可是D节点在下线以后会被广播告诉其余存活节点。这样的广播协议就是今天要说Gossip协议,Gossip协议也叫Epidemic协议(流行病协议),当一个消息到来时,经过Gossip协议就能够像病毒同样感染所有集群节点。Gossip的过程是由一个种子节点发起的,当一个种子节点有信息须要同步到网络中的其余节点时,它会随机的选择周围几个节点散播消息,收到消息的节点也会重复该过程,直至最终网络中全部的节点都收到了消息。这个过程可能须要必定的时间,因此不能保证某个时间点全部的节点都有该条消息,可是理论上最终全部节点都会收到消息,所以它是一个最终一致性协议。

Gossip协议的特色:

  • (1)Gossip协议是周期性散播消息,每隔一段时间传播一次
  • (2)被感染的节点,每次能够继续散播N个节点
  • (3)每次散播消息时,都会选择还没有发送过的节点进行散播,不会向发送的节点散播
  • (4)同一个节点可能会收到重复的消息,由于可能同时多个节点正好向它散播
  • (5)集群是去中心化的,节点之间都是平等的
  • (6)消息的散播不用等接收节点的 ack,即消息可能会丢失,可是最终应该会被感染

下面咱们来看个例子:

image

① 种子节点是A

② A节点选择B、C节点进行散播

③ C散播到D,B散播D和E,能够发现D收到两次

④ D散播到F,最终整个网络都同步到了消息

Gossip有点相似图的广度优先遍历算法,通常用于网络拓扑结构信息的分享和维护,好比 Redis 集群中节点的运行状态就是使用 Gossip 协议进行传递的。

二、Raft一致性协议:

分布式协议的难点之一就是数据的一致性,当由多个节点组成的集群中只有一个节点收到数据,咱们就算成功的话,风险太大,当要求全部节点都收到数据才响应成功,性能又太差,因此通常会在数据的安全和性能之间作个折中,只要保证绝大部分节点同步数据成功,咱们就算成功。比较知名的一致性算法有Raft算法,被普遍应用于许多中间件中,接下来咱们就看看Raft算法是实现分布式系统的不一样节点间的数据一致性的,也就是说客户端发送请求到任何一个节点都能收到一致的返回,当一个节点出故障后,其余节点仍然能以已有的数据正常进行。

首先介绍下在Raft算法中,几种状况下每一个节点对应的角色:

  • (1)Leader节点:同大多数分布式中的Leader节点同样,全部数据的变动都须要先通过Leader
  • (2)Follower节点:Leader节点的追随者,负责复制数据而且在选举时候投票的节点
  • (3)Candidate候选节点:参与选举的节点,就是Follower节点参与选举时会切换的角色

2.一、Leader 选举:

系统在刚开始的时候,全部节点都是Follower节点,这时都有机会参与选举,将本身变成Candidate,变成Candidate的节点会先投本身1票,同时告诉其它节点,让它们来投票,当拿到超过半数以上的投票时,当前Candidate就会变成Leader节点。可是若是每一个Follower节点都变成Candidate那么就会陷入无限的死循环,因而每一个Follower都一个定时器,而且定时器的时间是随机的,当某个Follower的定时器时间走完以后,会确认当前是否存在Leader节点,若是不存在再把本身变成Candidate。

image

① 因为A节点的定时器时间最短(10ms),因此A会成为Candidate。

② A投本身一票,并告诉B、C来投票,B、C也投出本身的赞成票后,A就会变成Leader节点,同时会记录是第M任。这个M是作版本校验的,好比一个编号是10的节点,收到了一个编号是9的节点的投票请求,那么就会拒绝这个请求。

在Leader节点选举出来之后,Leader节点会不断的发送心跳给其它Follower节点证实本身是活着的,其余Follower节点在收到心跳后会清空本身的定时器,并回复给Leader,由于此时不必触发选举了。

若是Leader节点在某一刻挂了,那么Follower节点就不会收到心跳,所以在定时器到来时就会触发新一轮的选举,流程仍是同样。可是若是恰巧两个Follower都变成了Candidate,而且都获得了一样的票数,那么此时就会陷入僵局,为了打破僵局,这时每一个Candidate都会随机推迟一段时间再次请求投票,固然通常状况下,就是先来先得,优先跑完定时器的Candidate理论成为Leader的几率更大。

选举流程大体如上,接下来咱们来看看数据日志的复制。

2.二、数据日志的复制:

当Leader节点收到客户端Client的请求变动时,会把变动记录到log中,而后Leader会将这个变动随着下一次的心跳通知给Follower节点,收到消息的Follower节点把变动一样写入日志中,而后回复Leader节点,当Leader收到大多数的回复后,就把变动写入本身的存储空间,同时回复client,并告诉Follower应用此log。至此,集群就变动达成了共识。

(1)正常状况下的日志复制:

image

① 一开始,Leader 和两个 Follower 都没有任何数据。

② 客户端发送请求给 Leader,储存数据 “sally”,Leader 先将数据写在本地日志,这时候数据状态仍是 Uncommitted (还没最终确认,使用红色表示)

③ Leader 给两个 Follower 节点发送 AppendEntries 请求,数据在 Follower 上没有冲突,则将数据暂时写在本地日志,Follower 的数据也仍是 Uncommitted

④ Follower 将数据写到本地后,返回 OK。Leader 收到后成功返回,只要收到的成功的返回数量超过半数 (包含Leader),Leader 将数据 “sally” 的状态改为 Committed。( 这个时候 Leader 就能够返回给客户端了)

⑤ Leader 再次给 Follower 发送 AppendEntries 请求,收到请求后,Follower 将本地日志里 Uncommitted 数据改为 Committed。这样就完成了整个复制日志的过程,三个节点的数据是一致的

(2)Network Partition 网络分区状况下日志复制:

在 Network Partition 的状况下,部分节点之间没办法互相通讯,Raft 也能保证这种状况下数据的一致性

① 一开始有 5 个节点处于同一网络状态下,以下图:

image

② Network Partition 将节点分红两边,一边有两个节点,一边三个节点:

image

③ 两个节点这边已经有 Leader 了,来自客户端的数据 “bob” 经过 Leader 同步到 Follower。

image

④ 只有两个节点,少于3个节点,因此 “bob” 的状态还是 Uncommitted。因此在这里,服务器会返回错误给客户端

image

⑤ 另一个 Partition 有三个节点,进行从新选主。

image

⑥ 客户端数据 “tom” 发到新的 Leader2,并经过和上节网络状态下类似的过程,同步到另外两个 Follower;但由于这个 Partition 有3个节点,超过半数,因此数据 “tom” 都 Commit 了。

image

image

image

⑦ 网络状态恢复,5个节点再次处于同一个网络状态下。可是这里出现了数据冲突 “bob" 和 “tom"

image

⑧ 三个节点的 Leader2 广播 AppendEntries

image

⑨ 两个节点 Partition 的 Leader 自动降级为 Follower,由于这个 Partition 的数据 “bob” 没有 Commit,返回给客户端的是错误,客户端知道请求没有成功,因此 Follower 在收到 AppendEntries 请求时,能够把 “bob“ 删除,而后同步 ”tom”,经过这么一个过程,就完成了在 Network Partition 状况下的复制日志,保证了数据的一致性。

image