分布式一致性算法,你确定不了解一下?

 

 

集中式与漫衍式

集中式

就是将所有的营业都部署在一个中心主机(节点)上,所有的功效都由这个主机集中处置。

特点

部署结构简朴、不需要思量多个主机之间的漫衍式协作问题。

漫衍式

漫衍式系统:指将硬件或者软件组件部署在差别的网络盘算机上,彼此之间仅仅通过新闻通报举行通讯和协调的系统。

特点

  1. 漫衍性:多台盘算机可空间上随意漫衍,跨机房、跨都市都可以。
  2. 对等性:漫衍式系统中没有主/从之分,都是对等的节点或者服务。
    • 副本:指漫衍式系统对数据或服务冗余,以此提供高可用。
    • 数据副本:是指在差别的节点上持久化一份数据,当某一个节点上存储的数据丢失时,可以从副本上读取到该数据,这是漫衍式系统数据丢失问题最为有用的手段。
    • 服务副本:指多个节点提供同样的服务,每个节点都有能力吸收来自外部的请求并举行响应的处置。
  3. **并发性:**漫衍式系统中的多个节点,可能会并发地操作一些共享资源,诸如数据库或漫衍式存储等。
  4. **缺乏全局时钟:**一个典型的漫衍式系统是由一系列在空间上随意漫衍的历程组成,历程彼此之间通过新闻举行通讯。因此,无法判断两个事宜谁先谁后。可使用逻辑时钟。
  5. **故障总是会发生:**除非需求指标允许,在系统设计时不能放过任何异常情形。如宕机、网络分区、网络超时等。

每一次漫衍式系统的请求与响应三态:乐成,失败,超时。

超时情形:

  1. 没有乐成发送到吸收方,在发送历程中发生信息丢失。
  2. 乐成发送到吸收方,并乐成处置,但返回给发送方历程中发生信息丢失。

以是需要有幂等。

漫衍式事务

漫衍式事务是指事务的介入者支持事务的服务器资源服务器以及事务管理器划分位于漫衍式系统的**差别节点之上。**通常一个漫衍式事务中会涉及对多个数据源或营业系统的操作。漫衍式事务也可以被界说为一种嵌套型的事务,同时也就具有了ACID事务的特征。

CAP理论

  • Consistency(一致性):数据一致更新,所有数据更改都是同步的(强一致性)。

  • Availability(可用性):好的响应性能

  • Partition tolerance(分区容错性) :可靠性

分区容错性:漫衍式系统在遇到任何网络分区故障的时刻,任然需要保证对外提供知足一致性和可用性的服务,除非是整个网络环境都发生了故障。

网络分区:是指在漫衍式系统中,差别的节点漫衍在差别的子网络(机房或异地网络等)中,由于一些特殊的缘故原由导致这些子网络之间泛起网络不连通的状态,但各个子网络的内部网络是正常的,从而导致整个网络的环境被切成了若干个伶仃的区域。

分布式一致性算法,你确定不了解一下?

定理:任何漫衍式系统只可同时知足二点,没法三者兼顾。

需要凭据现实营业举行取舍。

分布式一致性算法,你确定不了解一下?

  • CA系统(放弃P):指将所有数据(或者仅仅是那些与事务相关的数据)都放在一个漫衍式节点上,就不会存在网络分区。以是强一致性以及可用性获得知足。
  • CP系统(放弃A):若是要求数据在各个服务器上是强一致的,然而网络分区会导致同步时间无限延伸,那么如此一来可用性就得不到保障了。坚持事务ACID(原子性、一致性、隔离性和持久性)的传统数据库以及对效果一致性异常敏感的应用通常会做出这样的选择。
  • AP系统(放弃C):这里所说的放弃一致性,并不是完全放弃数据一致性,而**是放弃数据的强一致性,而保留数据的最终一致性。**若是即要求系统高可用又要求分区容错,那么就要放弃一致性了。由于一旦发生网络分区,节点之间将无法通讯,为什么知足高可用,每个节点只能用内陆数据提供服务,这样就会导致数据不一致。一些遵守BASE原则数据库,(如:Cassandra、CouchDB等)往往会放宽对一致性的要求(知足最终一致性即可),一次来获取基本的可用性。

BASE理论

  • Basically Available基本可用:指漫衍式系统在泛起不能预知的故障的时刻,允许损失部门可用性——但不是系统不能用。
    • 响应时间上的损失:如果正常一个在线搜索0.5秒之内返回,但由于故障(机房断电或网络不通),查询效果的响应时间增加到1—2秒。
    • 功效上的损失:若是流量激增或者一个请求需要多个服务间配合,而此时有的服务发生了故障,这时需要举行服务降级,进而珍爱系统稳定性。
  • Soft state软状态:允许系统在差别节点的数据副本之间举行数据同步的历程存在延迟。
  • Eventually consistent最终一致:最终数据是一致的就可以了,而不是时时高一致。

BASE头脑主要强调基本的可用性,若是你需要High 可用性,也就是纯粹的高性能,那么就要以一致性或容错性为牺牲。

一致性协议

一致性协议:为了使基于漫衍式系统架构下的所有节点举行事务处置历程中能够保持原子性和一致性而设计的一种算法。通常有二阶段提交协议、三阶段提交协议、PaxosZookeeper的ZAB协议、Raft、Pbft等。

2PC、3PC引入了两个观点。

**协调者:**卖力统一调剂漫衍式节点的执行逻辑

介入者:被调剂的漫衍式节点

2PC:Two-Phase Commit二阶段提交协议

二阶段主要接纳:先实验,后提交。

分布式一致性算法,你确定不了解一下? 分布式一致性算法,你确定不了解一下? 分布式一致性算法,你确定不了解一下?

2PC优瑕玷

  • 二阶段优点:原理简朴,实现利便;解决漫衍式事务的原子性,要么所有执行乐成,要么所有执行失败
  • 二阶段瑕玷
    1. 同步壅闭:在提交执行历程中,各个介入者都在守候其他介入者响应的历程中,将无法执行其他操作。
    2. 单点问题:只有一个协调者,协调者挂掉,整个二阶段提交流程无法执行;更为严重是,在阶段二时,协调者泛起问题,那介入者将会一直处于锁定事务状态中,无法继续完成事务操作。
    3. 数据不一致:在阶段二,协调者发送了Commit请求后,发生了网络故障,导致只有部门介入者收到commit请求,并执行提交操作,就导致数据不一致问题。
    4. 太过守旧:阶段一中,若介入者泛起故障,协调者无法收到介入者的询问反馈,只能通过自身超时机制来中止事务。这样的计谋显得过于守旧。

3PC:Three-phase Commit 三阶段提交协议

由于2PC有许多问题,以是在2PC基础上,改善为3PC:canCommit、preCommit、doCommit三个阶段。

改善点:

  1. 3PC是将2PC的第一阶段分为两个阶段,先提议事务询问,再执行事务。
  2. 同时在协调者、介入者中引入超时机制。

分布式一致性算法,你确定不了解一下?3PC-第一阶段 分布式一致性算法,你确定不了解一下? 分布式一致性算法,你确定不了解一下?3PC-事务中止1 分布式一致性算法,你确定不了解一下?3PC-第三阶段 分布式一致性算法,你确定不了解一下?3PC-事务中止2

3PC优瑕玷

  • 三阶段优点:

    • 降低了二阶段的同步壅闭局限(在第二阶段,只要介入者收到preCommit请求,就会执行事务,今后,不管能不能收到协调者的doCommit请求,都市执行事务提交,不会泛起壅闭问题)
    • 解决单点问题:进入阶段三会泛起两种情形: 1:协调者泛起问题; 2:协调者与介入者之间泛起网络故障;
      • 都导致介入者无法收到doCommit请求,但介入者在超时之后都市提交事务
  • 三阶段瑕玷

    高德智慧景区随身听播放器框架设计与实现

    • 数据不一致:介入者收到preCommit请求,此时若是泛起网络分区,协调者与介入者之间无法举行正常网络通讯,介入者在超时之后照样会举行事务提交,就会泛起数据不一致。

以是2PC、3PC各有优瑕玷,可凭据现实营业场景举行选择。既然2PC、3PC都市发生数据不一致。下面我们来看一看漫衍式领域常用的一致性算法。

Paxos算法

Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的基于新闻通报具有高度容错特征的一致性算法,是现在公认的解决漫衍式一致性问题最有用的算法之一。 Paxos算法解决的问题是一个漫衍式系统若何就某个值(决议)杀青一致。

Paxos以及下面的RAFT都假设不存在拜占庭将军问题,只思量节点宕机、网络分区、新闻不能靠等问题。属于CFT(Crash Fault Tolerance)算法。

系统中有三种角色proposers,acceptors,和 learners。可以一个节点多个角色。

  1. proposers 提出提案,提案信息包罗提案编号和提议的 value;
  2. acceptor 收到提案后可以接受(accept)提案,若提案获得多数派(majority)的 acceptors 的接受,则称该提案被批准(chosen);
  3. learners 只能“学习”被批准的提案。

多数派:指 n / 2 +1 。n为总节点数目。

Paxos算法分为两个阶段。详细如下:

  • 阶段一:

    • Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求

    • 若是一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(若是有的话)作为响应反馈给Proposer,同时该Acceptor答应不再接受任何编号小于N的提案

      例如:一个acceptor已经响应过的所有prepare请求对应的提案编号划分为1、2、。。。。5和7,那么该acceptor在吸收到一个编号为8的prepare请求后,就会将编号为7的提案作为响应反馈给Proposer。

  • 阶段二

    • 若是Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对**[N,V]提案Accept请求半数以上的Acceptor。注重:V就是阶段一收到的响应中编号最大的提案的value**,若是响应中不包罗任何提案,那么V就由Proposer自己决议(随便值)
    • 若是Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于NPrepare请求做出过响应,它就接受该提案

分布式一致性算法,你确定不了解一下?

注重:Proposer可以随时抛弃提案,而且提出新的提案;Acceptor也可以随时响应,接受编号更大的提案。

思索:若是两个Proposer还处于第一阶段时,相互提出编号更大的提案?会发生什么?

这时刻会泛起“活锁”状态,陷入了无限死循环中(破坏了算法活性)。

那需要怎么防止呢?

可以选出一个主Proposer,只有主Proposer可以提出提案。

至于怎么选择,不属于Paxos的范围,可以参考RAFT使用竞选,谁快谁当选;也可以参考PBFT的依次成为leader等。

RAFT算法

RAFT算法分为两个阶段:Leader选举,日志复制。也有三种角色,划分为:

  1. Leader(领导者):卖力发送要举行共识的数据,若是客户端发送的数据不是发送到Leader而是其他角色,其他角色会举行转发至Leader。
  2. Follower(追随者):介入共识的角色
  3. Candidate(候选者):若是Follower没有收到Leader的心跳响应跨越150——300ms,会举行Leader选举。

每个节点的身份都可以是以上三种中的其一。

  • Leader选举阶段

    • 所有节点初始状态为Follower状态,此时没有Leader,一定会与Leader的心跳超时(一样平常150——300ms,随机的,这样就是想谁先发出竞选,谁当选leader),此时Candidate就会发出leader竞选给其他节点(人人快选我啊,leader挂掉了);其他节点收到竞选请求,会响应赞成,当一个Candidate收到大多数(n/2 + 1)节点的回复,就成为leader。然后与Candidate保持心跳毗邻。Raft有个Term(任期)的观点,只有在发生Leader选举阶段,term+1,示意新的leader发生,挂掉的节点,或者挂掉的leader重启后,会发现自己的term小于最新的,此时就会切换到日志复制,去同步之前丢失的新闻。
    • 若是同时有多个Candidate发出竞选,而且都没有获得大多数投票,会一直举行竞选,直到选出leader
  • 日志复制(是一个2PC提交)

    • leader收到客户端或者其他节点转发过来需要共识的值,会追随心跳一起广播给其他节点,举行写入
    • 其他节点写入后响应乐成给leader,当leader收到大多数的follower响应的乐成,发出commit下令
    • 其他节点收到commit后,举行事务提交,响应乐成为leader,leader收到大多数的commit乐成,Raft完成。

    若是leader没有挂掉,或者发生网络分区,就会一直是这个leader举行事务提议。

我这里只是对于算法正常流程的形貌,强烈推荐动画版RAFT(看不懂算我输,不外记得回来点个赞,哈哈哈)

总结

本文从集中式到漫衍式理论CAP、BASE以及2PC、3PC流程,形貌了漫衍式事务常用的头脑;再详细说明晰Paxos以及Raft算法流程等。Paxos以及Raft算法属于CFT算法范围,都能容忍最多n/2(向下取整)的节点泛起宕机、网络分区等的强一致性算法。Paxos属于对照艰涩的算法,工程实现对照复杂,但其头脑很有借鉴意义。有兴趣的可以去看看Paxos的推导历程,个人认为很有意思,能够想明了每一步,对于明白其他算法,也大有辅助;也可以去看看Zookeerper的ZAB算法,后面有机遇专门写一篇。但这些算法不能真正意义上用于区块链共识,究竟leader说什么,其他节点就会执行,没有节点之间的共识历程。那什么算法可以用于区块链共识呢?

参考书籍

《从Paxos到Zookeeper++漫衍式一致性原理与实践++》

参考链接

PAXOS算法

RAFT动画版

本文使用 mdnice 排版

原创文章,作者:28x29新闻网,如若转载,请注明出处:https://www.28x29.com/archives/24339.html