跳至主要內容

分布式基础

bugcode大约 78 分钟分布式JAVA分布式锁java

分布式基础

分布式的发展历程

单点集中式

特点:App、DB、FileServer都部署在⼀台机器上。并且访问请求量较少

应⽤服务和数据服务拆分

特点:App、DB、FileServer分别部署在独⽴服务器上。并且访问请求量较少

使⽤缓存改善性能

特点:数据库中频繁访问的数据存储在缓存服务器中,减少数据库的访问次数,降低数据库的压⼒

应⽤服务器集群

特点:多台应⽤服务器通过负载均衡同时对外提供服务,解决单台服务器处理能⼒上限的问题

数据库读写分离

特点:数据库进⾏读写分离(主从)设计,解决数据库的处理压⼒

反向代理和CDN加速

特点:采⽤反向代理和CDN加快系统的访问速度

分布式⽂件系统和分布式数据库

特点:数据库采⽤分布式数据库,⽂件系统采⽤分布式⽂件系统

随着业务的发展,最终数据库读写分离也将⽆法满⾜需求,需要采⽤分布式数据库和分布式⽂件系统来⽀撑,分布式数据库是数据库拆分后的最后⽅法,只有在单表规模⾮常庞⼤的时候才使⽤,更常⽤的数据库拆分⼿段是业务分库,将不同业务的数据库部署在不同的机器上

从集中式到分布式

集中式的特点

所谓的集中式系统就是指由一台或多台主计算机组成中心节点,数据集中存储于这个中心节点中,并且整个系统的所有业务单元都集中部署在这个中心节点上,系统的所有功能均由其集中处理。也就是说,在集中式系统中,毎个终端或客户端机器仅仅负责数据的录入和输出,而数据的存储与控制处理完全交由主机来完成。集中式系统最大的特点就是部署结构简单。由于集中式系统往往基于底层性能卓越的大型主机,因此无须考虑如何对服务进行多个节点的部署,也就不用考虑多个节点之间的分布式协作问题。

分布式的特点

定义:分布式系统是一个硬件或者软件组件分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统。

  • 分布性:分布式系统的多态计算机在空间上呈现随机分布的特点,同时机器的分布也会随时变动。
  • 对等性:分布式系统中计算机没有主从之分,各个计算机之间是对等存在的分布式系统中有两个副本的概念,一个是数据副本,存储冗余数据保证数据不会丢失,一个是服务副本,指的是多个节点都可以提供同样的服务,每一个节点都有能力接收外部的请求并且处理。
  • 并发性:分布式系统中多个节点之间,可以并发性的访问一些公共的资源。也就是说数据之间可以共享。
  • 缺乏全局时钟:空间上各个进程呈现随机分布,进程之间可以通过交换消息来相互通信。因此在分布式系统中,很难界定两个事件究竟谁先谁后,原因是分布式系统中缺乏一个全局的时钟。
  • 故障总是随时发生:随时随地都有可能发生任何故障。

分布式系统中可能发生的故障

通信异常:分布式计算机之间需要相互通信,由于网络原因,可能发生网络异常,无法通信,出现延迟。

网络分区:出现通信异常后,有可能分布式系统中某一个区域内的计算机还可以相互通信,这样这一小部分集群需要应对外部提供服务,所以就对分布式一致性提出一个更大的挑战。

三态:由于网络原因,科恩那个出现三种状态,成功,失败,超时。

节点故障:某个节点出现宕机。

分布式系统的设计目标

  • 可扩展性:通过对服务,存储的扩展,来提高系统的处理能力,通过对多台服务器的协同工作,来完成单台服务器无法处理的任务,尤其是高并发或者大数据量的任务。

  • 高可用:单点故障不会影响整体服务,单点故障指的是系统中某一个组件一旦失效,会让整个系统无法工作。高可用通常指的是单点故障问题。

  • 无状态:无状态的服务才能满足部分机器宕机不影响全部,可以随时进行系统扩展的需求。有状态的话一旦节点宕机,会发生数据的丢失。

  • 可管理:便于运维,出现问题后能不能及时发现定位。

  • 高可靠:同样的请求返回同样的数据,数据的更新能够持久化,数据不会丢失。也就是满足幂等性原则。

分布式事务

事务( Transaction)是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元(Unit),狭义上的事务特指数据库事务。一方面,当多个应用程序并发访问数据库时,事务可以在这些应用程序之间提供一个隔离方法,以防止彼此的操作互相干扰。另一方面,事务为数据库操作序列提供了一个从失败中恢复到正常状态的方法,同时提供了数据库即使在异常状态下仍能保持数据一致性的方法。

事务具有四个特征,分别是原子性( Atomicity)、一致性( Consistency)、隔离性( Isolation)和持久性( Durability),简称为事务的ACID特性。

ACID特性

  • 原⼦性(Atomicity):⼀个事务(transaction)中的所有操作,要么全部完成,要么全部不完成,不会结束在中间某个环节。事务在执⾏过程中发⽣错误,会被恢复(Rollback)到事务开始前的状态,就像这个事务从来没有执⾏过⼀样。

    • 全部执行成功
    • 全部不执行

  • ⼀致性(Consistency):事务的一致性是指事务的执行不能破坏数据库数据的完整性和一致性,一个事务在执行之前和执行之后,数据库都必须处于一致性状态。也就是说,事务执行的结果必须是使数据库从一个一致性状态转变到另一个一致性状态,因此当数据库只包含成功事务提交的结果时,就能说数据库处于一致性状态。而如果数据库系统在运行过程中发生故障,有些事务尚未完成就被迫中断,这些未完成的事务对数据库所做的修改有一部分已写入物理数据库,这时数据库就处于一种不正确的状态,或者说是不一致的状态。

    • 在事务开始之前和事务结束以后,数据库的完整性没有被破坏。这表⽰写⼊的资料必须完全符合所有的预设规则,这包含资料的精确度、串联性以及后续数据库可以⾃发性地完成预定的⼯作。⽐如A有500元,B有300元,A向B转账100,⽆论怎么样,A和B的总和总是800元

  • 隔离性(Isolation):数据库允许多个并发事务同时对其数据进⾏读写和修改的能⼒,隔离性可以防⽌多个事务并发执⾏时由于交叉执⾏⽽导致数据的不⼀致。事务隔离分为不同级别,

    • 读未提交(Read uncommitted):该隔离级别允许脏读取,其隔离级别最低。换句话说,如果一个事务正在处理某一数据,并对其进行了更新,但同时尚未完成事务,因此还没有进行事务提交;而与此同时,允许另一个事务也能够访问该数据。举个例子来说,事务A和事务B同时进行,事务A在整个执行

      阶段,会将某数据项的值从1开始,做一系列加法操作(比如说加1操作)直到变成10之后进行事务提交,此时,事务B能够看到这个数据项在事务A操作过程中的所有中间值(如1变成2、2变成3等),而对这一系列的中间值的读取就是未授权读取。

    • 读提交(read committed):它和读未提交非常相近,唯一的区别就是授权读取只允许获取已经被提交的数据。同样以上面的例子来说,事务A和事务B同时进行,事务A进行与上述同样的操作,此时,事务B无法看到这个数据项在事务A操作过程中的所有中间值,只能看到最终的10。另外,如果说有一个事务C,和事务A进行非常类似的操作,只是事务C是将数据项从10加到

      20,此时事务B也同样可以读取到20,即授权读取允许不可重复读取。

    • 可重复读(repeatable read):可重复读取( Repeatable Read),简单地说,就是保证在事务处理过程中,多次读取同一个数据时,其值都和事务开始时刻是一致的。因此该事务级别禁止了不可重复读取和脏读取,但是有可能出现幻影数据。所谓幻影数据,就是指同样的事务操作,在前后两个时间段内执行对同一个数据项的读取,可能出现不一致的结果。在上面的例子,可重复读取隔离级别能够保证事务B在第一次事务操作过程中,始终对数据项读取到1,但是在下一次事务操作中,即使事务B(注意,事务名字虽然相同,但是指的是另一次事务操作)采用同样的查询方式,就可能会读取到10或20。

    • 和串⾏化(Serializable):串行化( Serializable)是最严格的事务隔离级别。它要求所有事务都被串行执行,即事务只能一个接一个地进行处理,不能并发执行。

不同等级能解决的问题:

事务隔离级别越高,就越能保证数据的完整性和一致性,但同时对并发性能的影响也越大。通常,对于绝大多数的应用程序来说,可以优先考虑将数据库系统的隔离级别设置为授权读取,这能够在避免脏读取的同时保证较好的并发性能。尽管这种事务隔离级别会导致不可重复读、虚读和第二类丢失更新等并发问题,但较为科学的做法是在可能出现这类问题的个别场合中,由应用程序主动采用悲观锁或乐观锁来进行事务控制。

  • 持久性(Durability):事务处理结束后,对数据的修改就是永久的,即便系统故障也不会丢失。

分布式事务

在集中式系统中,可以很容易实现一套基于ACID特性的事务处理系统;

分布式事务是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于分布式系统的不同节点之上。通常一个分布式事务中会涉及对多个数据源或业务系统的操作。

一个分布式事务可以看作是由多个分布式的操作序列组成的,可以把这一系列分布式的操作序列称为子事务。因此,分布式事务也可以被定义为一种嵌型的事务,同时也就具有了ACID事务特性。但由于在分布式事务中,各个子事务的执行是分布式的,因此要实现一种能够保证ACID特性的分布式事务处理系统就显得格外复杂

CAP理论

CAP理论告诉我们,一个分布式系统不可能同时满足一致性(C: Consistency)、可用性(A: Availability)和分区容错性(P: Partition tolerance)这三个基本需求,最多只能同时满足其中的两项。

⼀致性(Consistency):

在分布式环境中,一致性是指数据在多个副本之间是否能够保持一致的特性。在一致性的需求下,当一个系统在数据一致的状态下执行更新操作后,应该保证系统的数据仍然处于一致的状态。如果一个系统对一个写操作返回成功,那么之后的读请求必须返回这个新的数据,如果返回失败,那么所有的读操作都不能读取到这个新的数据, 对调用者而言保证了数据的一致性。

可⽤性(Availability):

任何⼀个节点挂了,其他节点可以继续对外提供服务,所有的读写请求在一定的时间内可以得到响应,可终止,不会一直等待。不会因为一台节点挂掉而导致整个集群无法对外提供服务。

可用性是指系统提供的服务必须一直处于可用的状态,对于用户的每一个操作请求总是能够在有限的时间内返回结果。

分区容错性(⽹络分区,存在节点间网络的传输)Partition tolerance:

⼀个数据库所在的机器坏了,如硬盘坏了,数据丢失了,可以新增⼀台机器,然后从其他正常的机器把备份的数据同步过来,在网络分区的情况下,被分隔的节点仍能够对外提供服务。

分区容错性约束了一个分布式系统需要具有如下特性:分布式系统在遇到任何网络分区故障的时候,仍然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障。

网络分区是指在分布式系统中,不同的节点分布在不同的子网络(机房或异地网络等)中,由于一些特殊的原因导致这些子网络之间出现网络不连通的状况,但各个子网络的内部网络是正常的,从而导致整个系统的网络环境被切分成了若干个孤立的区域。需要注意的是,组成一个分布式系统的每个节点的加入与退出都可以看作是一个特殊的网络分区。

在单点服务的情况下,CAP理论没有什么问题,因为没有节点之间的网络传输,也就是没有P的存在,但是在分布式的情况下,由于分区容错性必然存在,但是CAP三者有不能共存,所以在分布式架构中,p是一定要保证的,也就是只能从C,A中取其一。也就是只能保证CP或者AP,也就是说A,C在P存在的情况下模式不能共存的。

可以考虑一种情景,加入节点D和节点E之间存在网络传输,也就是存在网络分区,P存在的前提,并且两个节点之间的网络不可达,那么如果要保证C,也就是数据的一致性,那么此时就不能对外提供服务,必须保证网络可达后数据同步完成后才能对外提供服务,也就是满足一致性,试想,如果数据不一致,那么对外提供服务使用的数据就是旧的数据。

另外一种情况是如果要保证服务的可用性,那么即使数据的一致性没有得到保证也要对外提供服务,那么此时就不能考虑数据的一致性,也就是不能等待数据同步完成后提供服务,必须把对外提供服务放在第一位,这个时候只能不考虑数据的一致性,使用旧的数据对外提供服务,所以在P存在的情况下,C和A只能取其一。

所以目前存在的中间件,只有CP或者AP两种架构:

  • CP:牺牲可用性来保证一致性
  • AP:牺牲一致性来保证服务的可用性;

CAP理论的特点:CAP只能满.其中2条

  • CA(放弃P):将所有的数据放在⼀个节点。满⾜⼀致性、可⽤性。
  • AP(放弃C):放弃强⼀致性,⽤最终⼀致性来保证。
  • CP(放弃A):⼀旦系统遇⻅故障,受到影响的服务器需要等待⼀段时间,在恢复期间⽆法对外提供服务。
  1. 从CAP定理中我们可以看出,一个分布式系统不可能同时满足一致性、可用性和分区容错性这三个需求。
  2. 另一方面,需要明确的一点是,对于一个分布式系统而言,分区容错性可以说是一个最基本的要求。为什么这样说,其实很简单,因为既然是一个分布式系统,那么分布式系统中的组件必然需要被部署到不同的节点,否则也就无所谓分布式系统了,因此必然出现子网络。而对于分布式系统而言,网络问题又是一个必定会出现的异常情况,因此分区容错性也就成为了一个分布式系统必然需要面对和解决的问题。因此系统架构设计师往往需要把精力花在如何根据业务特点在C(一致性)和A(可用性)之间寻求平衡。

举例说明CAP理论

有3台机器分别有3个数据库分别有两张表,数据都是⼀样的

  • Machine1-db1-tbl_person、tbl_order
  • Machine2-db2-tbl_person、tbl_order
  • Machine3-db3-tbl_person、tbl_order
  1. 当向machine1的db1的表tbl_person、tbl_order插⼊数数据时,同时要把插⼊的数据同步到machine2、machine3,这就是⼀致性,也就是多个节点上面的数据要保持一致。
  2. 当其中的⼀台机器宕机了,可以继续对外提供服务,把宕机的机器重新启动起来可以继续服务,这就是可⽤性,某一台机器宕机,不会影响对外提供的服务。
  3. 当machine1的机器坏了,数据全部丢失了,不会有任何问题,因为machine2和machine3上还有数据,重新加⼀台机器machine4,把machine2和machine3其中⼀台机器的备份数据同步过来就可以了,这就是分区容错性,数据存在副本,保证容错机制。

BASE理论

BASE是 Basically Available(基本可用)、 Soft state(软状态)和 Eventually consistent(最终一致性)三个短语的简写,BASE理论在CAP理论的基础之上做出妥协,弱化了CAP理论。降低了发生分区容错对一致性和可用性的要求,其核心思想是即使无法做到强一致性( Strong consistency),但每个应用都可以根据自身的业务特点,采用适当的方式来使系统达到最终一致性( Eventual consistency)。

  • 基本可⽤(bascially available)
  • 软状态(soft state)
  • 最终⼀致性(Eventually consistent)

基本可⽤

基本可用是指分布式系统在出现不可预知故障的时候,允许损失部分可用性—但请注意,这绝不等价于系统不可用。以下两个就是“基本可用”的典型例子。允许损失部分可⽤性(服务降级、⻚⾯降级),或者响应的时间变长。

软状态

弱状态也称为软状态,和硬状态相对,是指允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进数据同步的过程存在延时。允许分布式系统出现中间状态。⽽且中间状态不影响系统的可⽤性。

  • 这⾥的中间状态是指不同的data replication之间的数据更新可以出现延时的最终⼀致性
  • 如CAP理论⾥⾯的⽰例,当向machine1的db1的表tbl_person、tbl_order插⼊数数据时,同时要把插⼊的数据同步到machine2、machine3,当machine3的⽹络有问题时,同步失败,但是过⼀会⽹络恢复了就同步成功了,这个同步失败的状态就称为软状态,因为最终还是同步成功了。

例如淘宝下单:加入购物车,待支付,支付中,已支付状态,并不会直接从加入购物车然后一下子变为已支付状态,存在中间状态,但是不会对最终结果造成影响。存在中间状态,可以给系统提供一个缓冲的时间。

最终⼀致性

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

data replications经过⼀段时间达到⼀致性。节点之间的数据同步可以存在延迟,但是一定的时限之后必须达成数据的一致性,状态变为最终的状态。

总的来说,BASE理论面向的是大型高可用可扩展的分布式系统,和传统事务的ACID特性是相反的,它完全不同于ACID的强一致性模型,而是提出通过牺牲强一致性来获得可用性,并允许数据在一段时间内是不一致的,但最终达到一致状态。但同时,在实际的分布式场景中,不同业务单元和组件对数据一致性的要求是不同的,因此在具体的分布式系统架构设计过程中,ACID特性与BASE理论往往又会结合在一起使用。

数据一致性在CAP理论中指的是强一致性,而在BASE理论中指的是最终一致性,并不是相同意义上的一致性.

2P/3P

在分布式系统中,每一个机器节点虽然都能够明确地知道自己在进行事务操作过程中的结果是成功或失败,但却无法直接获取到其他分布式节点的操作结果。因此,当一个事务操作需要跨越多个分布式节点的时候,为了保持事务处理的ACID特性,就需要引入个称为“协调者( Coordinator)”的组件来统一调度所有分布式节点的执行逻辑,这些被调度的分布式节点则被称为“参与者”( Participant)。协调者负责调度参与者的行为,并最终决定这些参与者是否要把事务真正进行提交。基于这个思想,衍生出了二阶段提交和三阶段提交两种协议。

2P= Two Phase commit ⼆段提交(RDBMS(关系型数据库管理系统)经常就是这种机制,保证强⼀致性)

3P= Three Phase commit 三段提交

说明:2P/3P是为了保证事务的ACID(原⼦性、⼀致性、隔离性、持久性)

2P的两个阶段

通常,二阶段提交协议也被认为是一种强一致性协议,用来保证分布式系统数据的一致性。目前,绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理的,利用该协议能够非常方便地完成所有分布式事务参与者的协调,统一决定事务的提交或回滚,从而能够有效地保证分布式数据一致性,因此二阶段提交协议被广泛地应用在许多分布式系统中。

阶段1 提交事务请求(投票阶段)询问是否可以提交事务

  1. 事务询问。

协调者向所有的参与者发送事务内容,询问是否可以执行事务提交操作,并开始等待(发生阻塞)各参与者的响应

  1. 执行事务。

各参与者节点执行事务操作,并将Undo和Redo信息记入事务日志中。

  1. 各参与者向协调者反馈事务询问的响应。

如果参与者成功执行了事务操作,那么就反馈给协调者Yes响应,表示事务可以执行;如果参与者没有成功执行事务,那么就反馈给协调者No响应,表示事务不可以执行

由于上面讲述的内容在形式上近似是协调者组织各参与者对一次事务操作的投票表态过程,因此二阶段提交协议的阶段一也被称为“投票阶段”,即各参与者投票表明是否要继续执行接下去的事务提交操作。

阶段2 执⾏事务提交(commit、rollback) 真正的提交事务

在阶段二中,协调者会根据各参与者的反馈情况来决定最终是否可以进行事务提交操作,正常情况下,包含以下两种可能。

执行事务提交:假如协调者从所有的参与者获得的反馈都是Yes响应,那么就会执行事务提交。发送提交请求。

  1. 发送提交请求:协调者向所有参与者发送commit请求。
  2. 事务提交:参与者接收到 Commit请求后,会正式执行事务提交操作,并在完成提交之后释放在整个事务执行期间占用的事务资源
  3. 反馈事务提交结果:参与者在完成事务提交之后,向协调者发送Ack消息。完成事务。
  4. 协调者接收到所有参与者反馈的Ack消息后,完成事务。

中断事务

假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

  1. 发送回滚请求:协调者向所有参与者节点发出 Rollback请求

  2. 事务回滚:参与者接收到 Rollback请求后,会利用其在阶段一中记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源

  3. 反馈事务回滚结果:参与者在完成事务回滚之后,向协调者发送Ack消息。

  4. 中断事务:协调者接收到所有参与者返回的ACK消息后,完成中断事务。

以上就是二阶段提交过程中,前后两个阶段分别进行的处理逻辑。简单地讲,二阶段提交将一个事务的处理过程分为了投票和执行两个阶段,其核心是对每个事务都采用先尝试后提交的处理方式,因此也可以将二阶段提交看作一个强一致性的算法。下图展示了两个阶段的场景:

事务提交

事务中断

优缺点

优点:原理简单,实现方便

缺点:

  • 同步阻塞:二阶段提交协议存在的最明显也是最大的一个问题就是同步阻塞,这会极大地限制分布式系统的性能。在二阶段提交的执行过程中,所有参与该事务操作的逻辑都处于阻塞状态,也就是说,各个参与者在等待其他参与者响应的过程中,将无法进行其他任何操作。
  • 数据不一致:在二阶段提交协议的阶段二,即执行事务提交的时候,当协调者向所有的参与者发送 Commit请求之后,发生了局部网络异常或者是协调者在尚未发送完 Commit请求之前自身发生了崩溃,导致最终只有部分参与者收到了 Commit请求。于是,这部分收到了 Commit请求的参与者就会进行事务的提交,而其他没有收到 Commit请求的参与者则无法进行事务提交,于是整个分布式系统便出现了数据不一致性现象。
  • 单点问题: 协调者的角色在整个二阶段提交协议中起到了非常重要的作用。一旦协调者出现问题,那么整个二阶段提交流程将无法运转,更为严重的是,如果协调者是在阶段二中出现问题的话,那么其他参与者将会直处于锁定事务资源的状态中,而无法继续完成事务操作。

针对两阶段存在的问题,提出三阶段提交协议进行改进。

3P的三个阶段

3PC,是 Three--Phase commit的缩写,即三阶段提交,是2PC的改进版,其将二阶段提交协议的“提交事务请求”过程一分为二,形成了由 Can Commit、 PreCommit和 do commit

三个阶段组成的事务处理协议,其协议设计如图2-3所示。

  • 阶段1:是否提交-询问是否可以做事务提交
  • 阶段2:预先提交-预先提交事务
  • 阶段3:执⾏事务提交(commit、rollback)真正的提交事务

说明:3P把2P的阶段⼀拆分成了前⾯两个阶段,先询问一遍是否可以提交,然后在做预提交命令。

阶段一: CanCommit

  1. 事务询问:协调者向所有的参与者发送一个包含事务内容的 can commit请求,询问是否可以执行事务提交操作,并开始等待各参与者的响应。

  2. 各参与者向协调者反馈事务询问的响应参与者在接收到来自协调者的 can Commit请求后,正常情况下,如果其自身认为可以顺利执行事务,那么会反馈Yes响应,并进入预备状态,否则反馈No响应。

阶段二: PreCommit

在阶段二中,协调者会根据各参与者的反馈情况来决定是否可以进行事务的 PreCommit操作,正常情况下,包含两种可能。

执行事务预提交,假如协调者从所有的参与者获得的反馈都是Yes响应,那么就会执行事务预提交。

  1. 发送预提交请求:协调者向所有参与者节点发出 pre Commit的请求,并进入 Prepared阶段。

  2. 事务预提交:参与者接收到 pre Commit请求后,会执行事务操作,并将Undo和Redo信息记录到事务日志中。

  3. 各参与者向协调者反馈事务执行的响应:如果参与者成功执行了事务操作,那么就会反馈给协调者Ack响应,同时等待最终的指令:提交( commit)或中止( abort)

中断事务:假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

  1. 发送中断请求。协调者向所有参与者节点发出 abort请求。中断事务。

  2. 无论是收到来自协调者的 abort请求,或者是在等待协调者请求过程中出现超

    时,参与者都会中断事务。

阶段三: do Commit

该阶段将进行真正的事务提交,会存在以下两种可能的情况。

执行提交

  1. 发送提交请求。进入这一阶段,假设协调者处于正常工作状态,并且它接收到了来自所有参与者的Ack响应,那么它将从“预提交”状态转换到“提交”状态,并向所有的参与者发送 doCommit请求。

  2. 事务提交,参与者接收到 doCommit请求后,会正式执行事务提交操作,并在完成提交之后释放在整个事务执行期间占用的事务资源。

  3. 反馈事务提交结果,参与者在完成事务提交之后,向协调者发送Ack消息

4.完成事务,协调者接收到所有参与者反馈的Ack消息后,完成事务。

中断事务

进入这一阶段,假设协调者处于正常工作状态,并且有任意一个参与者向协调者反

馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务,

  1. 发送中断请求,协调者向所有的参与者节点发送 abort请求。

  2. 事务回滚。参与者接收到 abort请求后,会利用其在阶段二中记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源。

  3. 反馈事务回滚结果。参与者在完成事务回滚之后,向协调者发送Ack消息。

  4. 中断事务。协调者接收到所有参与者反馈的Ack消息后,中断事务。

需要注意的是,一旦进入阶段三,可能会存在以下两种故障

  1. 协调者出现问题。
  2. 协调者和参与者之间的网络出现故障。

无论出现哪种情况,最终都会导致参与者无法及时接收到来自协调者的 do commit或是abort请求,针对这样的异常情况,参与者都会在等待超时之后,继续进行事务提交。

优缺点

三阶段提交协议的优点:相较于二阶段提交协议,三阶段提交协议最大的优点就是降低了参与者的阻塞范围,并且能够在出现单点故障后继续达成一致。

三阶段提交协议的缺点:三阶段提交协议在去除阻塞的同时也引入了新的问题,那就是在参与者接收到 pre Commit消息后,如果网络出现分区,此时协调者所在的节点和参与者无法进行正常的网络通信,在这种情况下,该参与者依然会进行事务的提交,这必然出现数据的不一致性。

选举算法Quorum机制,WARO

WARO

WARO是一种简单的副本控制协议,写操作时候,只有当所有的写操作都更新成功之后,这一次写操作才算成功,否则视为失败。优先保证读取成功,任何一个节点读取到的数据都是最新的数据,牺牲了更新服务的可用性,只要有一个副本发生宕机了,写服务就不会成功,但是只要有一个节点存活,那么就可以对外提供读服务。

kafka中的ack确认机制就是使用waro协议。kafka对WARO协议进行了优化,只需要保证ISR中的节点返回ack即可。

简单来说就是更新写操作需要所有的节点全部在线参与,而读取服务只要有一个节点即可提供服务。

Quorum机制

10个副本,一次成功更新3个,那么至少读取8个副本的数据,这里面至少有一个副本更新成功数据,可以保证读取到了最新的数据,无法保证强一致性,也就是无法实现任何时刻任何用户或者节点都可以读取到最近一次成功提交的副本数据,需要配合一个获取最新成功提交的版本号的metadate服务,这样可以确定最新已经成功提交的版本号,然后从已经读取到的数据中就可以确认最新写入的数据。

简单理解就是写操作不要求全部节点全部在线,需要N个节点在线即可,然后读取,然后数据成功写入这N个节点,读取的时候,读取10-N+1个节点数,这样保证有一个节点的数据是更新的。

在主从架构和选举算法中,上面这两种协议应用都是比较广泛的。

Paxos一致性算法

Paxos算法介绍

一种基于消息传递且具有高度容错特性的一致性算法。

这里所说的一致性指的是CAP理论中强一致性，解决的是集群中多个节点之间的数据一致性问题,只是一种算法思想和模型,可以理解为一种协议。raft算法和zookeeper中的zab算法都是借鉴了paxos算法的思想。

Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏整个系统的一致性。

Paxos算法解决的是一个分布式系统中如何就某一个值(决议)达成一致,一个典型的场景是,在一个分布式数据库系统中,如果各个节点的初始状态是一致的,每一个节点执行相同的操作序列,那么他们最后也可以得到一个一致的状态,为了保证每一个节点执行相同的操作序列,需要在每一条指令上面执行一个“一致性算法”用来保证每一个节点看到的指令是一致的,在Paxos算法 中,有三种角色:Proposer(提议者),Acceptor(接受者),Learners(记录员)。

proposer将发起提案(value)给所有accpetor,超过半数accpetor获得批准后,proposer将提案写入accpetor内,最终所有accpetor获得一致性的确定性取值,且后续不允许再修改。

Paxos算法过程

  • Proposer提议者:只要Proposer发出的提案Propose被半数以上的Acceptor接受,Proposer就被认为该提案例的value被确定了。

  • Acceptor接受者:只要Acceptor接受了某一个提案,Acceptor就认为该提案例的value被选定了。

  • Learner记录员:Acceptor告诉Learner那个value被选中,Learner就认为哪一个value被选定。

Paxos算法分为两个阶段:对于一个 Proposer来说,获取那些已经被通过的提案远比预测未来可能会被通过的提案来得简单。因此, Proposer在产生一个编号为N的提案时,必须要知道当前某一个将要或已经被半数以上 Acceptor批准的编号小于N但为最大编号的提案。并且, Proposer会要求所有的 Acceptor都不要再批准任何编号小于N的提案—这就引出了如下的提案生成算法。

阶段一(Proposer生成提案prepare请求):

Proposer选择一个新的提案编号N,然后向某个 Acceptor集合的成员发送请求,要求该集合中的 Acceptor做出如下回应。

  1. 向 Proposer承诺,保证不再批准任何编号小于M的提案。
  2. 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案。

我们将该请求称为编号为N的提案的 Prepare请求。

如果 Proposer收到了来自半数以上的 Acceptor的响应结果,那么它就可以产生编号为N、 Value值为Vn的提案,这里的Ⅴn是所有响应中编号最大的提案的 Value值。当然还存在另一种情况,就是半数以上的 Acceptor都没有批准过任何提案,即响应中不包含任何的提案,那么此时Ⅴn值就可以由 Proposer任意选择。

在确定提案之后, Proposer就会将该提案再次发送给某个 Acceptor集合,并期望获得它们的批准,我们称此请求为 Accept请求。需要注意的一点是,此时接受 Accept请求的Acceptor集合不一定是之前响应 Prepare请求的 Acceptor集合—这点相信读者也能够明白,任意两个半数以上的 Acceptor集合,必定包含至少一个公共 Acceptor

阶段二(Acceptor接受提案accept请求):

根据上面的内容,一个 Acceptor可能会收到来自 Proposer的两种请求,分别是 Prepare请求和 Accept请求,对这两类请求做出响应的条件分别如下。

  • Prepare请求: Acceptor可以在任何时候响应一个 Prepare请求
  • Accept请求:在不违背 Accept现有承诺的前提下,可以任意响应 Accept请求。

因此,对 Acceptor逻辑处理的约束条件,大体可以定义如下。

一个 Acceptor只要尚未响应过任何编号大于N的 Prepare请求,那么它就可以接受这个编号为N的提案。

值得一提的是, Paxos算法允许 Acceptor忽略任何请求而不用担心破坏其算法的安全性。

阶段三(Learn学习阶段)

Proposer将形成的决议发送给所有Linteners。

过程细节优化

我们分别从 Proposer和 Acceptor对提案的生成和批准两方面来讲解了Paxos算法在提案选定过程中的算法细节,同时也在提案的编号全局唯一的前提下,获得了一个满足安全性需求的提案选定算法,接下来我们再对这个初步算法做一个小优化。尽可能地忽略 Prepare请求:

假设一个 Acceptor收到了一个编号为M的 Prepare请求,但此时该 Acceptor已经对编号大于Mn的 Prepare请求做出了响应,因此它肯定不会再批准任何新的编号为M的提案,那么很显然, Acceptor就没有必要对这个 Prepare请求做出响应,于是 Acceptor可以选择忽略这样的 Prepare请求。同时, Acceptor也可以忽略掉那些它已经批准过的提案的 Prepare请求。

通过这个优化,每个 Acceptor只需要记住它已经批准的提案的最大编号以及它已经做出Prepare请求响应的提案的最大编号,以便在出现故障或节点重启的情况下,也能保证P2c的不变性。而对于 Proposer来说,只要它可以保证不会产生具有相同编号的提案,那么就可以丢弃任意的提案以及它所有的运行时状态信息。

算法过程

阶段一:

  1. Proposer选择一个提案编号Mn,然后向 Acceptor的某个超过半数的子集成员发送编号为Mn的 Prepare请求。

  2. 如果一个 Acceptor收到一个编号为Mn的 Prepare请求,且编号Mn大于该 Acceptor已经响应的所有 Prepare请求的编号,那么它就会将它已经批准过的最大编号的提案作为响应反馈给 Proposer,同时该 Acceptor会承诺不会再批准任何编号小于Mn的提案。

举个例子来说,假定一个 Acceptor已经响应过的所有 Prepare请求对应的提案编号分别为1、2、5和7,那么该 Acceptor在接收到一个编号为8的 Prepare请求后,就会将编号为7的提案作为响应反馈给 Proposer.

阶段二:

  1. 如果 Proposer收到来自半数以上的 Acceptor对于其发出的编号为Mn的 Prepare请求的响应,那么它就会发送一个针对[Mn,Vn]提案的 Accept请求给 Acceptor,注意,Vn的值就是收到的响应中编号最大的提案的值,如果响应中不包含任何提案,那么它就是任意值。

  2. 如果 Acceptor收到这个针对[Mn,Ⅴn]提案的 Accept请求,只要该 Acceptor尚未对编号大于Mn的 Prepare请求做出响应,它就可以通过这个提案。

算法流程

  1. Prepare: Proposer(提案者)生成全局唯一且递增的Proposal ID,向所有Acceptor发送Propose(提案)请求,这里无需携带提案内容,只携带Proposal ID即可。

  2. Promise(承诺): Acceptor收到Propose请求后,做出“两个承诺,一个应答”。

    1. 不再接受Proposal ID小于等于(注意:这里是<= )当前请求的Propose请求。
    2. 不再接受Proposal ID小于(注意:这里是< )当前请求的Accept请求。
    3. 不违背以前做出的承诺下,回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID,没有则返回空值。

  3. Propose(提案): Proposer(提案者)收到多数Acceptor(接收者)的Promise(承诺)应答后,从应答中选择Proposal ID最大的提案的Value,作为本次要发起的提案。如果所有应答的提案Value均为空值,则可以自己随意决定提案Value。然后携带当前Proposal ID,向所有Acceptor发送Propose请求。

  4. Accept: Acceptor收到Propose请求后,在不违背自己之前做出的承诺下,接受并持久化当前Proposal ID和提案Value。

  5. 4

情况一

有A1, A2, A3, A4, A5 5位议员,就税率问题进行决议。

  • A1发起1号Proposal的Propose,等待Promise承诺;
  • A2-A5回应Promise;
  • A1在收到两份回复时就会发起税率10%的Proposal;
  • A2-A5回应Accept;
  • 通过Proposal,税率10%。

情况二

现在我们假设在A1提出提案的同时, A5决定将税率定为20%

  • A1,A5同时发起Propose(序号分别为1,2)
  • A2承诺A1,A4承诺A5,A3行为成为关键
  • 情况1:A3先收到A1消息,承诺A1。
  • A1发起Proposal(1,10%),A2,A3接受。
  • 之后A3又收到A5消息,回复A1:(1,10%),并承诺A5。
  • A5发起Proposal(2,20%),A3,A4接受。之后A1,A5同时广播决议。

情况三

现在我们假设在A1提出提案的同时, A5决定将税率定为20%

  • A1,A5同时发起Propose(序号分别为1,2)
  • A2承诺A1,A4承诺A5,A3行为成为关键
  • 情况2:A3先收到A1消息,承诺A1。之后立刻收到A5消息,承诺A5。
  • A1发起Proposal(1,10%),无足够响应,A1重新Propose (序号3),A3再次承诺A1。
  • A5发起Proposal(2,20%),无足够相应。 A5重新Propose (序号4),A3再次承诺A5。
  • ……

这也是paxos算法存在的不足之处,当由多个提案者的时候,会出现情况三这种问题。

为了保证 Paxos算法流程的可持续性,以避免陷入上述提到的“死循环”,就必须选择个主 Proposer,并规定只有主 Proposer才能提出议案。这样一来,只要主 Proposer和过半的 Acceptor能够正常进行网络通信,那么但凡主 Proposer提出一个编号更高的提案,该提案终将会被批准。当然,如果 Proposer发现当前算法流程中已经有一个编号更大的提案被提出或正在接受批准,那么它会丢弃当前这个编号较小的提案,并最终能够选出个编号足够大的提案。因此,如果系统中有足够多的组件(包括 Proposer、 Acceptor和其他网络通信组件)能够正常工作,那么通过选择一个主 Proposer,整套 Paxos算法流程就能够保持活性。

小结

二阶段提交协议、三阶段提交协议和 Paxos这三种典型的一致性算法。可以说,这三种一致性协议都是非常优秀的分布式一致性协议,都从不同方面不同程度地解决了分布式数据一致性问题,使用范围都非常广泛。

其中二阶段提交协议解决了分布式事务的原子性问题,保证了分布式事务的多个参与者要么都执行成功,要么都执行失败。但是,在二阶段解决部分分布式事务问题的同时,依然存在一些难以解决的诸如同步阻塞、无限期等待和“脑裂”等问题。三阶段提交协议则是在二阶段提交协议的基础上,添加了 Pre Commit过程,从而避免了二阶段提交协议中的无限期等待问题。而 Paxos算法引入了“过半”的理念,通俗地讲就是少数服从多数的原则。同时, Paxos算法支持分布式节点角色之间的轮换,这极大地避免了分布式单点的出现,因此 Paxos算法既解决了无限期等待问题,也解决了“脑裂”问题,是目前来说最优秀的分布式一致性协议之一。

Raft算法

什么是 Raft 算法

首先说什么是 Raft 算法:Raft 是一种为了管理复制日志的一致性算法。

分布式一致性算法,raft算法会首先选举出leader,leader完全负责replicated log的管理,leader负责接受所有客户的更新请求,然后把更新的数据同步到所有的follower节点,并且在安全的时候执行这些请求,如果leader故障,会从follower中重新选择出新的leader来管理。

什么是一致性呢？

Raft 的论文这么说的:一致性算法允许一组机器像一个整体一样工作,即使其中一些机器出现故障也能够继续工作下去。

这里的一致性针对分布式系统。

什么是管理日志呢？

一致性算法是从复制状态机的背景下提出的,复制状态机通常都是基于复制日志实现的,这个日志可以理解为一个比喻,相当于一个指令。

关于状态机的描述:

多个节点上,从相同的初始状态开始,执行相同的一串命令,产生相同的最终状态。实际上,与其说是一致,其实可以泛化为分布式的两个节点状态存在某种约束。

复制状态机通常都是基于复制日志实现的,保证复制日志相同就是一致性算法的工作了。

典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

对于 Raft 更重要的应该是 易于理解。从 Raft 的论文题目就可以看出:In Search of an Understandable Consensus Algorithm (Extended Version)。这里的易于理解是相对于 Paxos 的,在他的论文中,和 Paxos 做了大量针对 易于理解 的对比和统计测试。

Raft 将一致性算法分解成了几个关键模块,例如领导人选举、日志复制和安全性。

而和一致性最相关的就是前面 2 个模块:领导人选举和日志复制。

日志序列:每一个节点上维持着一份持久化Log,通过一致性协议算法,保证每一个节点中的log保持一致。并且顺序存放,这样客户端就可以在每一个节点中读取到相同的数据。

状态机:日志序列同步到多数节点时候并且返回成功,leader将该日志提交到状态机,并且在下一次心跳通知所有节点提交状态机(携带最后提交的lastIndex)

何时出发选举Leader

  • 集群初始化时候,都是Follower,随机超时,变成Candidate(也就是如果超时,那么一个follower就变为Candidate,开始向其他节点拉票),发起选举。
  • 如果Follower在election timeout内没有收到来自Leader的心跳,那么主动触发选举。

领导人选举

Raft 通过选举一个高贵的领导人,然后给予他全部的管理复制日志的责任来实现一致性。

而每个 server 都可能会在 3 个身份之间切换:

  • 领导者:处理所有额度客户端的请求(如果客户端的请求是发送给Follower的,Follower会将请求重新定向给Leader)
  • 候选者:用于选举产生新的Leader候选人。
  • 跟随者:不会发送任何的请求,只会简单的响应来自Leader或者Candidate的请求。

而影响他们身份变化的则是 选举。当所有服务器初始化的时候,都是 跟随者,这个时候需要一个 领导者,所有人都变成 候选者,直到有人成功当选 领导者。

Term:任期,Leader从产生的那一刻到重新选举为止为一个任期,每一个节点都维持着当前的任期领导。每一个Leader都维护一个Id,分发给所有的Follower,保证让所有的Follower直到当前的Leader是哪一个节点。这个Id也是递增的序列。

  • Id可以防止脑裂的发生(就是一个集群中同时存在两个Leader节点),比如由于网络原因,Leader和某一个Follower之间没有心跳,或者说超时,那么此时这个Follower就会变为Candidate,选举Leader,为自己拉票,如果选举成功,那么他自己会生成一个Id,然后分发给集群中的Follower节点,但是如果旧的Leader收到的话,因为这个Id比自己的Id号码大,所以他自己就会重新变为Follower节点。这样可以防止脑裂发生。
  • term是递增的,存储在log日志当中的Entry对象中,Entry对象中也会存储Id号,代表当前的entry是在哪一个term时期写入的。
  • 每一个时期只能有一个Leader或者没有(选举失败)
  • 每一次rpc通信时候传递该Leader的Id号,如果rpc收到的Id号大于本地的号,切换为Follower,小于本地任期号则返回错误信息。

角色转换如下

而领导者也有宕机的时候,宕机后引发新的 选举,所以,整个集群在选举和正常运行之间切换,具体如下图:

从上图可以看出,选举和正常运行之间切换,但请注意, 上图中的 term 3 有一个地方,后面没有跟着 正常运行 阶段,为什么呢?

  • 答:当一次选举失败(比如正巧每个人都投了自己),就执行一次 加时赛(这里像是和zookeeper中的选举一样,每一个节点首先投出子集一票,如果没有成为leader的话,就重新投票),每个 Server 会在一个随机的时间里重新投票,这样就能保证不冲突了。所以,当 term 3 选举失败,等了几十毫秒,执行 term 4 选举,并成功选举出领导人。

接着,领导者周期性的向所有跟随者发送心跳包来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息,也就是选举超时,那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。

要开始一次选举过程,跟随者先要增加自己的当前任期号并且转换到候选人状态。然后请求其他服务器为自己投票。那么会产生 3 种结果:

  1. 自己成功当选
  2. 其他的服务器成为领导者
  3. 僵住,没有任何一个人成为领导者

注意:

  • 每一个 server 最多在一个任期内投出一张选票(有任期号约束),先到先得。
  • 要求最多只能有一个人赢得选票。
  • 一旦成功,立即成为领导人,然后广播所有服务器停止投票阻止新得领导产生。

僵住怎么办？ Raft 通过使用随机选举超时时间(例如 150 - 300 毫秒)的方法将服务器打散投票。每个候选人在僵住的时候会随机从一个时间开始重新选举。

选举过程:从发出选举节点的角度

  1. 增加节点本地的term,切换到candidate状态。
  2. 投自己一票,其他的节点投票逻辑:每一个节点同一个任期内最多只能投一张票,候选人知道的信息不能够比自己少,也就是状态机中的数据一定是最新的,通过term id和last-log-Index来保证,先来先得。
  3. 然后在给其他节点发送RequestVote请求(拉票请求),包含term参数,
  4. 等待回复
    1. 如果收到大多数的投票,赢得选举,将自己切换为Leader即可,立刻给所有节点发送心跳消息。
    2. 如果本节点是投票节点,被告知别人当选,切换为Follower状态,(前提是收到的Id比原来旧的Id大,切换为Follower状态)
    3. 一段时间内既没有收到大部分的投票,有没有收到leader的心跳通知,则保持candidate重新发出选举。

以上,就是 Raft 所有关于领导选举的策略。

日志复制

一旦一个领导人被选举出来,他就开始为客户端提供服务。

客户端发送日志给领导者,随后领导者将日志复制到其他的服务器。如果跟随者故障,领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。

下图表示了当一个客户端发送一个日志给领导者,随后领导者复制给跟随者的整个过程。

4 个步骤:

  • 客户端提交
  • 复制数据到所有跟随者
  • 跟随者回复 确认收到
  • 领导者回复客户端和所有跟随者 确认提交。

可以看到,直到第四步骤,整个事务才会达成。中间任何一个步骤发生故障,都不会影响日志一致性。

详细过程

日志序列同步:日志序列需要存储在磁盘进行持久化,崩溃时候可以从日志恢复

  1. 客户端发送命令给Leader。
  2. Leader把日志条目加载自己的日志序列中。Leader不能删除和修改自己的日志,只可以做追加操作。
  3. Leader发送AppaenEntries RPC请求给所有的follower。携带了preLogIndex(前一条日志的序列号),preLogTerm(前一条日志的任期号)。每一个节点上面都有这两个参数

follower收到后,进行日志序列的匹配

  1. 匹配上则追加到自己的日志序列中
  2. 匹配不上则拒绝请求,Leader将日志index调小,重新同步直到匹配上,然后leader将匹配上的数据位置后面的数据全部发送到followerj节点,follower将leader的日志序列覆盖到本地中

一旦新的日志序列条目变为majority的了,也就是多数follower节点响应同步成功,将日志序列应用到状态机中

  1. Leader在状态机里提交自己日志序列的条目,也就是持久化日志,然后返回结果给客户端
  2. Leader下次发送AppendEntries RPC时候,告知follower已经净提交的日志序列的条目信息(lastIndex)
  3. follower收到RPC之后,提交到自己的状态机里面。

小结

Raft 算法如同他的论文名字一样:寻找一种易于理解的一致性算法,这里的 易于理解 是相对于 Paxos 的,的确,Paxos 实在过于复杂了。

而如何实现易于理解？

答:Raft 将一致性算法分成了2部分:领导选举,日志复制。

领导选举基于一个随机的时间来保证不会冲突(如果冲突的话)。
而日志复制则类似于 2PC。

通常 5 个节点,只要不超过 2 个节点死亡都不会影响系统的运行。保证了系统的可用性,通过领导者的日志复制,实现了系统的一致性。

ZAB协议(原子消息广播协议)

什么是zab协议

在 ZooKeeper中,主要依赖ZAB协议来实现分布式数据一致性,基于该协议, ZooKeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。具体的,ZooKeeper使用一个单一的主进程(master)来接收并处理客户端的所有事务请求,并采用ZAB的原子广播协议,将master服务器数据的状态变更以事务 Proposal的形式广播到所有的副本进程(follower)上去。

ZAB协议的这个主备模型架构保证了同一时刻集群中只能够有一个主进程来广播服务器的状态变更,因此能够很好地处理客户端大量的并发请求。

ZAB协议是为分布式协调服务zookeeper专门设计的一种支持崩溃恢复的原子广播协议,实现分布式数据的一致性,所有客户端的请求都是写入到leader进程当中(区别于paxos算法中可有多个提案者,zab协议中只能有一个提案者),然后由Leader同步到其他的节点中,成为Follower节点,在集群数据同步的过程中,如果出现Follower节点崩溃或者Leader进程崩溃时,都会通过Zab崩溃恢复协议来保证数据的一致性。

ZAB协议的核心是定义了对于那些会改变 ZooKeeper服务器数据状态的事务请求的处理方式:

  • 即:所有事务请求必须由一个全局唯一的服务器来协调处理,这样的服务器被称为 Leader服务器,而余下的其他服务器则成为 Follower服务器。
  • Leader服务器负责将一个客户端事务请求转换成一个事务 Proposal(提议),并将该 Proposal分发给集群中所有的Follower服务器。
  • 之后 Leader服务器需要等待所有 Follower服务器的反馈,一旦超过半数的 Follower服务器进行了正确的反馈后,那么 Leader就会再次向所有的 Follower服务器分发 Commit消息,要求其将前一个 Proposal进行提交。
  • 广播阶段简单可以理解为一个弱化的2pc协议。

ZAB 协议全称:Zookeeper Atomic Broadcast(Zookeeper 原子广播协议)。

ZAB 协议定义:ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议。下面我们会重点讲这两个东西。

基于该协议,Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。具体如下图所示:

上图显示了 Zookeeper 如何处理集群中的数据。所有客户端写入数据都是写入到 主进程(称为 Leader)中,然后,由 Leader 复制到备份进程(称为 Follower)中。从而保证数据一致性。从设计上看,和 Raft 类似。

那么复制过程又是如何的呢？复制过程类似 2PC,ZAB 只需要 Follower 有一半以上返回 Ack 信息就可以执行提交,大大减小了同步阻塞。也提高了可用性。

简单介绍完,开始重点介绍消息广播和崩溃恢复(崩溃恢复之后,有数据的同步过程)。整个 Zookeeper 就是在这两个模式之间切换。 简而言之,当 Leader 服务可以正常使用,就进入消息广播模式,当 Leader 不可用时,则进入崩溃恢复模式。

协议过程

ZAB协议包括两种基本的模式,分别是崩溃恢复和消息广播。当整个服务框架在启动过程中,或是当 Leader服务器出现网络中断、崩溃退出与重启等异常情况时,ZAB协议就会进入崩溃恢复模式并选举产生新的 Leader服务器。

当选举产生了新的Leader服务器,同时集群中已经有过半的机器与该 Leader服务器完成了状态同步(也就是数据同步)之后,ZAB协议就会退出恢复模式。其中,所谓的状态同步是指数据同步(这个操作是在选举leader之后进行的操作),用来保证集群中存在过半的机器能够和 Leader服务器的数据状态保持一致。

当集群中已经有过半的 Follower服务器完成了和 Leader服务器的状态同步,那么整个服务框架就可以进入消息广播模式了。

当一台同样遵守ZAB协议的服务器启动后加入到集群中时,如果此时集群中已经存在一个 Leader服务器在负责进行消息广播,那么新加入的服务器就会自觉地进入数据恢复模式:找到 Leader所在的服务器,并与其进行数据同步,然后一起参与到消息广播流程中去。

正如上文介绍中所说的, ZooKeeper设计成只允许唯一的一个 Leader服务器来进行事务请求的处理。 Leader服务器在接收到客户端的事务请求后,会生成对应的事务提案并发起一轮广播协议;而如果集群中的其他机器接收到客户端的事务请求,那么这些非 Leader服务器会首先将这个事务请求转发给Leader服务器。

当 Leader服务器出现崩溃退出或机器重启,亦或是集群中已经不存在过半的服务器与该Leader服务器保持正常通信时,那么在重新开始新一轮的原子广播事务操作之前,所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态,于是整个ZAB流程就会从消息广播模式进入到崩溃恢复模式,也就是选举产生新的leader。

一个机器要成为新的 Leader,必须获得过半进程的支持,同时由于每个进程都有可能会崩溃,因此,在ZAB协议运行过程中,前后会出现多个 Leader,并且每个进程也有可能会多次成为 Leader。

进入崩溃恢复模式后,只要集群中存在过半的服务器能够彼此进行正常通信,那么就可以产生一个新的 Leader并再次进入消息广播模式。

举个例子来说,一个由3台机器组成的ZAB服务,通常由1个 Leader、2个 Follower服务器组成。某个时刻,假如其中一个 Follower服务器挂了,整个ZAB集群是不会中断服务的,这是因为 Leader服务器依然能够获得过半机器(包括 Leader自己)的支持。接下来我们就重点讲解一下ZAB协议的消息广播和崩溃恢复过程。

消息广播

ZAB 协议的消息广播过程使用的是一个原子广播协议,类似一个二阶段提交过程。对于客户端发送的写请求,全部由 Leader 接收,Leader 将请求封装成一个事务 Proposal,将其发送给所有 Follwer ,然后,根据所有 Follwer 的反馈,如果超过半数成功响应,则执行 commit 操作(先提交自己,再发送 commit 给所有 Follwer)。

基本上,整个广播流程分为 3 步骤:

  1. 将数据都复制到 Follwer 中,也就是预提交。
  1. 等待 Follwer 回应 Ack,最低超过半数即成功
  1. 当超过半数成功回应,则执行 commit ,同时提交自己

通过以上 3 个步骤,就能够保持集群之间数据的一致性。实际上,在 Leader 和 Follwer 之间还有一个消息队列,用来解耦他们之间的耦合,避免同步,实现异步解耦。

还有一些细节:

  1. Leader 在收到客户端请求之后,会将这个请求封装成一个事务,并给这个事务分配一个全局递增的唯一 ID,称为事务ID(ZXID),ZAB 协议需要保证事务的顺序,因此必须将每一个事务按照 ZXID 进行先后排序然后处理。
  2. 在 Leader 和 Follwer 之间还有一个消息队列,用来解耦他们之间的耦合,解除同步阻塞。
  3. zookeeper集群中为保证任何所有进程能够有序的顺序执行,只能是 Leader 服务器接受写请求,即使是 Follower 服务器接受到客户端的请求,也会转发到 Leader 服务器进行处理。
  4. 实际上,这是一种简化版本的 2PC,不能解决单点问题。等会我们会讲述 ZAB 如何解决单点问题(即 Leader 崩溃问题)

崩溃恢复

刚刚我们说消息广播过程中,Leader 崩溃怎么办？还能保证数据一致吗？如果 Leader 先本地提交了,然后 commit 请求没有发送出去,怎么办？

实际上,当 Leader 崩溃,即进入我们开头所说的崩溃恢复模式(崩溃即:Leader 失去与过半 Follwer 的联系),下面来详细讲述。

  1. 假设1:Leader 在复制数据给所有 Follwer 之后崩溃,怎么办？也就是与提交阶段leader崩溃。
  2. 假设2:Leader 在收到 Ack 并提交了自己,同时发送了部分 commit 出去之后崩溃怎么办？

针对这些问题,ZAB 定义了 2 个原则:

  1. ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。
  2. ZAB 协议确保丢弃那些只在 Leader 提出/复制(预提交),但没有提交的事务。

所以,ZAB 设计了下面这样一个选举算法:

能够确保提交已经被 Leader 提交的事务,同时丢弃已经被跳过的事务。

针对这个要求,如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群中所有机器编号(即 ZXID 最大)的事务,那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。

而且这么做有一个好处是:可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

这样,我们刚刚假设的两个问题便能够解决。假设 1 最终会丢弃调用没有提交的数据,假设 2 最终会同步所有服务器的数据。这个时候,就引出了一个问题,如何同步？

数据同步

当崩溃恢复之后,需要在正式工作之前(接收客户端请求),Leader 服务器首先确认事务是否都已经被过半的 Follwer 提交了,即是否完成了数据同步。目的是为了保持数据一致。

当所有的 Follwer 服务器都成功同步之后,Leader 会将这些服务器加入到可用服务器列表中。

实际上,Leader 服务器处理或丢弃事务都是依赖着 ZXID 的,那么这个 ZXID 如何生成呢？

答:在 ZAB 协议的事务编号 ZXID 设计中,ZXID 是一个 64 位的数字,其中低 32 位可以看作是一个简单的递增的计数器,针对客户端的每一个事务请求,Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。

而高 32 位则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID,并从该 ZXID 中解析出对应的 epoch 值,然后再对这个值加一。

高 32 位代表了每代 Leader 的唯一性,低 32 代表了每代 Leader 中事务的唯一性。同时,也能让 Follwer 通过高 32 位识别不同的 Leader。简化了数据恢复流程。

基于这样的策略:当 Follower 链接上 Leader 之后,Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对,比对结果要么回滚,要么和 Leader 同步。

负载均衡的策略有哪些

轮询

将请求按照先后到达的时间分配到服务器上面,他均衡的对待后面的每一台服务器,而不关心服务器实际的连接数和当前系统的负载量。缺点是每一台服务器可能配置不一样,按照相同方式分配任务,可能导致有的服务器负载量很大,而有的很小,效率低,浪费资源。

加权轮询法

不同的后端服务器可能机器的配置和当前系统的负载并不相同,因此他们的抗压能力也不相同,给配置高负载低的服务器配置更高的加权,让其处理更多的请求,而配置低负载高的机器,给其分配较低的权重,降低其系统的负载,加权轮询可以很好的处理不同配置的服务器负载量不同的问题,并将请求顺序按照权重先后分配给服务器,简单来说就是把轮询方式的优化,给配置高,负载低的服务器分配更多的请求。

随机法

通过系统的随机算法,根据后端服务器的列表大小来随机的选取其中的一台服务器进行访问,由概率统计理论可以得知,随着客户端调用服务端的次数增多,其实实际的效果越来越接近于平均分配调用到后端的每一台服务器,也就是轮询方式的结果,这两种方式效果差别不是很大。

加权随机法

与加权轮训法一样,加权随机法根据后端服务器的配置,系统的负载分配不同的权重,不同的是,他是按照权重随机请求后端服务器,并不是顺序请求。

源地址哈希法

源地址哈希法的思想是根据获取客户端的IP地址,通过哈希函数得到一个数值,用该数值对服务器列表的大小进行取模运算,得到的结果便是客户端要访问的服务器的序号,采用源地址哈希法进行负载均衡,统一IP地址的客户端,当后端服务器的列表不发生变化时候,他每次都会映射到同一台后端服务器进行访问。

使用这种方式最大的好处是可以共享session。

最小连接数法

最小连接数算法比较灵活这智能,由于后端服务器的配置不尽相同,对于请求的处理有快有慢,他是根据后端服务器当前的连接情况,动态的选取其中当前积压连接数最少的一台服务器来处理当前的请求,尽可能的提高后端服务器的利用效率,将请求合理的分配到每一台后端服务器上。也就是每一台服务器有一个最小的连接数目,如果某一台服务器最小连接数目全部用完,那么新来的连结请求将分配到其他的服务器上面。

集群,分布式,SOA和微服务的概念及区别

单机&集群

早期的话,通常将服务部署到一台服务器上,由于客户量比较少,所以可以扛得住访问,但是随着客户量的增加,一台服务器不足以应对所有客户的访问,那么就增加多台服务器,把我们的服务部署到多台机器上面,这样可以增大并发访问的量,在这里,这多个节点的地位通常是平等的,每一个节点都可以提供完整的服务,并且每一台服务器上面部署的实例是一致的,所以此时就衍生出了集群的概念。

其实集群强调的就是多台服务器的地位是对等的,而且每一个节点都提供完整的服务。

  • 不同的服务器部署同一套应用服务对外提供访问,实现服务的负载均衡或者互备(热备,主从等),指的是同一种组件的多个实例,形成的逻辑上的整体,单个节点可以提供完整的服务,集群是物理形态。

分布式

比如集群中的一个节点实例,可能包含很多的功能,A,B,C三个模块的功能。A模块的访问量最大,B,C访问量远远小于模块A的访问量,所以B,C不需要进行扩展,我们可以仅仅对A模块进行分布式部署,将A模块进行单独部署,单独为一个实例。那么A,B,C三个模块工作时候可能需要协调工作,所以分布式强调的是多个节点之间相互协调对外提供服务。

而集群中每一个节点部署的是相同的实例,但是不同节点之间也有协作和交互,所以集群和分布式之间的概念很模糊,没有明确的界限。

  • 服务的不同模块部署在不同的服务器上面,单个节点不能提供完整的服务,需要多个节点之间协调提供服务(也可以是相同组件部署在不同的节点上,但是节点之间通过复杂的交换信息协作提供服务),分布式强调的是协调的工作方式。

集群强调节点与节点之间的功能对等,对外提供服务,而分布式强调节点与节点之间协调对外提供服务,但是集群多个节点之间也需要交互协作,所以二者之间界限模糊。

SOA

如果把模块A,B,C进行分布式部署,可能后面涉及很多模块,多个模块之间存在相互的调用和交互关系,比较复杂,维护成本很高,所以此时就出现了SOA,主要就是为了解决系统之间交互过于复杂的问题,SOA是面向服务的概念。

比如系统中多个模块需要进行交互,那么每一个模块都需要维护其他模块所在的地址和其他信息,这样系统臃肿而复杂,而SOA的做法是引入了总线ESB,所有模块之间的交互都是通过总线进行,总线维护各个模块的地址,而每一个模块不在需要维护其他模块的地址信息,这样系统就解耦了,而各个模块只需要知道ESB总线在哪里即可。

但是这也是系统的瓶颈,所有额模块之间的交互都需要通过ESB总线,那么系统的效率就取决于ESB总线,ESB会成为一个单点的瓶颈。可以说微服务的出现就是为了解决单点瓶颈问题。

  • 面向服务的架构,一种设计方法,其中包含多个服务,服务之间通过相互依赖最终提供一系列的功能,一个服务通常以独立的形式存在于操作系统的进程中,各个服务器之间通过网络调用。
    • 中心化实现:ESB企业服务总线,各个服务通过ESB总线进行交互,解决异构系统之间的连通性,通过协议的转换,消息解析,消息路由把服务提供者的数据传送到服务的消费者,很重,有一定的逻辑,可以解决一些共用逻辑的问题。
    • 去中心化实现:微服务

微服务

在SOA上做的升华,微服务架构强调的一个重点是业务需求要彻底的组件化和服务化,原有的单个业务系统会拆分为多个可以独立开发,设计,运行的小应用,这些小应用之间通过微服务完成交互和继承

更加强调服务单一职责,还在SOA的范畴之内,只不过把服务的粒度拆解的更加细。

轻量级通信,去掉ESB总线,采用restAPI通信。

分布式事务有哪些解决方案

要区别于本地事务,数据库中的事务。

  • 基于XA协议(专门用来解决分布式事务的协议):两阶段提交和三阶段提交,需要数据库层面支持。mysql支持XA协议。

  • 基于事务补偿机制的:TCC,基于业务层面实现。

  • 本地消息表:基于本地数据库+mq,维护本地状态(进行中),通过mq调用服务,完成后响应一条消息回调,将状态改成完成,需要配合定时任务扫描,重新发送消息调用服务,需要保证幂等性。

  • 基于事务消息:mq(消息中间件来支持事务消息)

XA协议

包含两阶段提交和三阶段提交

其中TM是事务管理器,负责提交一个一个的事务,起到协调的作用,而RM是处理一个一个的事务。

第一阶段(prepare):每一个参与者执行本地事务但是不进行提交,进入ready状态,并通知协调者已经准备就绪。

第二阶段(commit):当协调者确认每一个参与者都ready之后,通知参与者进行commit操作,如果有参与者fail,则发送rollback命令,各个参与者进行回滚,保证数据的一致性。

问题:

  • 单点故障问题:一旦事务管理器出现故障,整个系统不可用(参与者都会阻塞),因为释放不掉锁资源。
  • 数据不一致:在阶段二,如果事务管理器只发送了部分commit消息,此时网络发生异常,那么只有部分参与者接受到commit消息,也就是说只有部分参与者提交了事务,使得系统的数据不一致。
  • 响应时间较长:参与者和协调者资源都被锁住,提交或者回滚之后才能够释放。
  • 不确定性:当事务管理器发送commit之后,并且此时只有一个参与者收到了commit,那么当该参与者与事务管理器同时宕机之后,重新选举的事务管理器无法确定该条消息是否提交成功。

三阶段提交协议:主要是针对两阶段的优化,解决了2PC单点故障的问题,但是性能问题和不一致问题仍然没有根本解决。

三阶段提交在开始有一个预提交命令,可以用来检测是否所有的库都正常在线,用来探测数据库是否存活,如果存活才可以进行接下来的提交,因为如果库宕机,而事务管理器发出了sql命令,那么会锁住资源。

阶段一用来检测所有的库是否都是正常的,preCommit对应于二阶段提交中的第一阶段,用来发出sql命令,锁定资源。三阶段提交比二阶段提交多了一个探测的命令。探测机制提高了两阶段的成功率。

三阶段提交解决了单点故障问题:如果事务管理器挂掉,那么所有的RM都会阻塞,无法释放资源。所以在三阶段提交中引入一个超时机制

引入了超时机制解决参与者阻塞的问题,如果参与者一直没有收到协调者发送的doCommit命令,那么等待时间超时后,参与者就会进行本地提交,自己进行提交,不在收到协调者控制,2PC只有协调者有超时机制。但是数据不一致和不确定性并没有解决。这里的超时机制是对于参与者而说的,也就是说参与者一直收不到命令,就会进行自动提交。

而对于两阶段提交,如果事务管理器一直也没有收到RM返回的消息,那么等待时间超时,事务管理器就会自动发送回滚命令。

上面两个超时机制针对的对象不一样,针对数据库而言,在两阶段提交中没有超时机制,在三阶段提交中有超时机制。

  1. 第一阶段:canCommit阶段,协调者询问事务参与者,是否有能力完成此次事务,
    1. 如果返回yes,那么就进入第二阶段
    2. 有一个返回no或者等待响应超时,则中断事务,并且向所有的参与者发送abort请求。
  2. 第二阶段:PreCommit阶段,此时协调者会向所有的参与者发送PreCommit请求,参与者收到后开始执行事务操作,参与者执行完成事务操作后(此时属于未提交事务的状态),就会向协调者反馈ACK确认,表示我已经准备好提交了,并等待协调者下一步的命令。
  3. 第三阶段:DoCommit阶段,在阶段二中如果所有的参与者节点都返回了ack确认,那么协调者就会从预提交状态转变为提交状态,然后向所有的参与者节点发送doCommit请求,参与者节点在收到提交请求后就会各自执行事务的提交操作,并且向协调者反馈ack确认消息,协调者收到所有参与者的ACK确认消息后完成事务,相反,如果有一个参与者为完成preCommit的反馈ack确认或者反馈超时时候,那么协调者就会向所有的参与者节点发送abort请求,从而中断事务。

两阶段=执行sql命令+commit/rollback

三阶段=canCommit(提高成功率)+preCommit+doCommit+引入参与者超时机制,避免单点故障和参与者锁住资源不释放

优点:相比二阶段提交,三阶段提交降低了阻塞范围,在等待超时后协调者或参与者会中断事务。避免了协调者单点问题,阶段 3 中协调者出现问题时,参与者会继续提交事务。

缺点:数据不一致问题依然存在,当在参与者收到 preCommit 请求后等待 do commite 指令时,此时如果协调者请求中断事务,而协调者无法与参与者正常通信,会导致参与者继续提交事务,造成数据不一致。

简述TCC事务模型

TCC(补偿事务),里面有三种操作:

  • Try:做资源预留,是在业务层面的操作,并不需要事务的支持。
  • Confirm:提交。
  • Cancle:取消事务。

针对每一个操作,都要注册一个与其对应的确认和补偿(撤销)操作。

  • Try操作业务检查及资源的预留情况
  • Confirm做业务的确认操作
  • Cancle实现一个与Try相反的操作既回滚操作

TM首先发起所有额度分支事务的Try操作,任何一个分支事务的Try操作执行失败,TM将会发起所有分支事务的Cancle操作,如果Try操作全部成功,TM将会发起所有分支事务的Confirm操作,其中Confirm/Cancle操作如果执行失败,TM会进行重试。

之所以有重试操作,所以需要满足幂等性要求:

Confirm 和 Cancel 操作满足幂等性,如果 Confirm 或 Cancel 操作执行失败,将会不断重试直到执行完成。

Confirm 阶段也可以看成是对 Try 阶段的一个补充,Try+Confirm 一起组成了一个完整的业务逻辑。Cancel 取消执行,释放 Try 阶段预留的业务资源

Cancel:当 Try 阶段存在服务执行失败, 进入 Cancel 阶段

TCC模型对业务的侵入性比较强,改造的难度较大,每一个操作都需要有Try,Confirm,Cancle三个接口实现。

TCC中会添加事务日志,如果Confirm或者Cancle阶段出错,则会进行重试,所以这两个阶段需要支持幂等性,如果重试失败,则需要人工介入进行恢复处理等。

总结

TCC 事务机制相对于传统事务机制(X/Open XA),TCC 事务机制相比于上面介绍的 XA 事务机制,有以下优点:

  • 性能提升:具体业务来实现控制资源锁的粒度变小,不会锁定整个资源。
  • 数据最终一致性:基于 Confirm 和 Cancel 的幂等性,保证事务最终完成确认或者取消,保证数据的一致性。
  • 可靠性:解决了 XA 协议的协调者单点故障问题,由主业务方发起并控制整个业务活动,业务活动管理器也变成多点,引入集群。

缺点: TCC 的 Try、Confirm 和 Cancel 操作功能要按具体业务来实现,业务耦合度较高,提高了开发成本。

如何理解RPC

远程过程调用

RPC要求在调用方放置被调用的方法的接口,调用方只要调用了这些接口,就相当于调用了被调用方法的实际方法,十分易用,于是,调用方可以像调用内部接口一样调用远程的方法,而不是用封装参数名和参数值等操作。

包含:

  1. 动态代理,封装调用细节
  2. 序列化和反序列化,数据的传输与接收
  3. 通信,可以选择七层的http,四层的tcp/udp。
  4. 异常处理等。

首先,调用方调用的是接口,必须为接口构造一个类的实现,显然,要使用动态代理,这样,调用方的调用就被动态代理接收到了。

第二,动态代理接收到调用后,应该想办法调用远程的实际实现,包括下面几步:

  • 识别具体要调用的远程方法的IP,端口。
  • 将调用方法的传入参数进行序列化。
  • 通过通信将请求发送到远程的方法中。

这样,远程的服务器就接收到了调用方的请求,他应该:

  • 反序列化各个调用参数。
  • 定位到实际要调用的方法,然后输入参数,执行方法。
  • 按照调用的路径返回调用的结果。
分布式
bugcode