精华内容
下载资源
问答
  • 两段锁协议

    千次阅读 2017-07-14 15:15:28
    并发控制:所谓并发控制,是指多用户共享的系统中,许多用户可能同时对同一数据进行操作。 调度:指的是事务的执行次序。 串行调度:多个事务依次串行执行,且只有当一个事务的所有操作都执行完后才执行另一个事务...

    我们都知道,事务调度一般有串行调度和并行调度,那首先来了解几个概念。

    并发控制:所谓并发控制,是指多用户共享的系统中,许多用户可能同时对同一数据进行操作。

    调度:指的是事务的执行次序。

    串行调度:多个事务依次串行执行,且只有当一个事务的所有操作都执行完后才执行另一个事务的所有操作。只要是串行调度,执行的结果都是正确的。

    并行调度:利用分时的方法同时处理多个事务。但是并行调度的调度结果可能是错误的,可能产生不一致的状态,包括有:丢失修改,不可重复读和读脏数据。

    其实比较明显的是虽然串行调度能够保证调度结果的正确性,但是却限制了系统并行性的发挥,不能有效利用资源,但是并行调度的调度结果又可能出现错误,而且可能不具有串行,正是因为这样,有一个具有串行调度效果的并行调度方法,而两段锁协议就是保证并行事务可串化的方法。

    两段锁协议:是指所有的事务必须分两个阶段对数据项加锁和解锁。即事务分两个阶段,第一个阶段是获得封锁。事务可以获得任何数据项上的任何类型的锁,但是不能释放;第二阶段是释放封锁,事务可以释放任何数据项上的任何类型的锁,但不能申请。

    第一阶段是获得封锁的阶段,称为扩展阶段:其实也就是该阶段可以进入加锁操作,在对任何数据进行读操作之前要申请获得S锁,在进行写操作之前要申请并获得X锁,加锁不成功,则事务进入等待状态,直到加锁成功才继续执行。就是加锁后就不能解锁了。

    第二阶段是释放封锁的阶段,称为收缩阶段:当事务释放一个封锁后,事务进入封锁阶段,在该阶段只能进行解锁而不能再进行加锁操作。

    这里举个例子说明:

    事务T1遵守两段锁协议,其封锁序列是:
    Lock A, Read A, A:=A+100, Write A, Lock B, Unlock A, Read B, Unlock B, Commit;
    可以证明,若并发执行的所有事务均遵守两段锁协议,则对这些事务的任何并发调度策略都是可 串行化的。
    最后,说一下什么是 可串行化:多个事务的并发执行是正确的,当且仅当其结果与某一次序串行地执行它们时的结果相同,称这种调度策略是可串行化调度。

    展开全文
  • 两段锁协议 封锁的粒度 多粒度封锁 意向 的强度   前提 并发控制技术与前一篇提到的数据库恢复技术是主要的事务处理技术,同时并发控制机制和数据库恢复机制是数据库管理系统(DBMS)的重要组成部分。 ...

    主要内容

    两种基本封锁类型 

    封锁协议

    活锁

    死锁

    多粒度封锁

    意向锁

    锁的强度


     

    前提

    并发控制技术与前一篇提到的数据库恢复技术是主要的事务处理技术,同时并发控制机制和数据库恢复机制是数据库管理系统(DBMS)的重要组成部分。

    单处理机系统中,事务的并行执行实际上是这些并行事务轮流交叉运行。这种并行执行方式称为交叉并发方式(interleaved concurrency)。虽然单处理机系统中的并行事务并没有真正地(物理上)并行运行,但是减少了处理机和各设备的空闲时间,提高了系统的效率。

    多处理机系统中,当事务数小于处理机数时,每个处理机可以运行一个事务,实现真正意义上的并行运行。这种并行执行方式称为同时并发方式(simultaneous concurrency)

    当多个用户并发地操作数据库时,就有可能出现多个事务同时存取同一数据的情况,这种情况可能会破坏事务的一致性和数据库的一致性,所以数据库管理系统(DBMS)必须提供并发控制机制。并发控制机制是衡量一个DBMS性能的重要标志之一。


     

    并发操作带来的数据不一致性

    以下三类数据不一致性的主要原因是并发操作破坏了事务的隔离性

    1)丢失修改(lost update):

    事务T1和T2先后读入同一数据并修改,T1先提交,T2后提交,T2提交的结果将覆盖T1的结果,导致T1的修改被丢失。

    2)不可重复读(non-repeatable read):

    事务T1读入某一数据后(未进行操作),T2对同一数据进行了操作(修改、插入、删除),当T1再次读入该数据时,得到与前一次不同的值(或者多了、少了某些记录)。这种不一致性与丢失修改的理想情况相反。

    3)读“脏”数据(dirty read):

    事务T1修改某一数据后将其写入磁盘,事务T2读入修改后的数据,此时T1由于某种原因被撤销(ROLLBACK),被T1修改的数据恢复原值,导致T2读入的数据与数据库中的数据不一致。


     

    封锁

    事务T在对某个数据对象,如表、记录等操作之前,需要先向系统发出加锁请求,在事务T释放它的锁之前,其他事务不能对此数据进行修改。

     

    两种基本封锁类型 

    1)排他锁(exclusive locks,X锁):

    排他锁又称为写锁。事务T对数据对象A加上X锁后,只允许事务T对A进行读取和修改,其他事务不能对A加任何类型的锁,直到T释放它的X锁为止。从而保证了其他事务在T释放A上的X锁之前不能对A进行读取和修改。

    2)共享锁(share locks,S锁):

    共享锁又称为读锁。事务T对数据对象A加上S锁后,事务T只能对A进行读取,而不能修改。其他事务可以继续对A加上S锁,但是不能加X锁,直到T释放它的S锁为止。从而保证了其他事务可以读取A,但是在T释放A上的S锁之前不能对A进行修改。

    *需要注意的是,同一事务可以不断对某个数据对象加锁,不需要等锁的释放。

     

    封锁协议

    1)一级封锁协议:

    定义:事务T在修改数据A前,必须先对A加X锁,直到事务结束才释放因此X锁又被称为写锁,意为修改。

    目的:解决“丢失修改”的不一致问题,即在下一个事务操作前,先把上一个事务的修改操作结束。

    实现:事务T1的X锁→事务T2的X锁

    事务T1对数据对象A加上X锁后,只有等事务T1(修改)结束,释放X锁,事务T2才能对A加锁并进行操作(读取、修改)。

     

    2)二级封锁协议:

    定义:在一级封锁协议的基础上,增加事务T在读取数据A前,必须先对A加S锁,读完后即可释放因此S锁又被称为读锁,意为读取。

    目的:在一级封锁协议的基础上,进一步解决“读‘脏’数据”的不一致问题,即在下一个事务读取前,先等上一个事务的撤销操作结束。

    实现:事务T1的X锁→事务T2的S锁(读取数据后释放S锁)

    事务T1对数据对象A加上X锁后,只有等事务T1(修改、撤销)结束,释放X锁,事务T2才能对A加锁并进行操作(读取)。

     

    3)三级封锁协议:

    定义:在一级封锁协议的基础上,增加事务T在读取数据A前,必须先对A加S锁,直到事务结束才释放(与二级的区别)

    目的:在二级封锁协议的基础上,进一步解决“不可重复读”的不一致问题,即在下一个事务修改前,先等上一个事务的重复读操作结束。

    实现:事务T1的S锁(事务结束后释放S锁)→事务T2的X锁

    事务T1对数据对象A加上S锁后,只有等事务T1(重复读取)结束,释放S锁,事务T2才能对A加X锁并进行操作(修改)。


     

    活锁和死锁

    和操作系统一样,封锁的方法可能引起活锁和死锁等问题。

     

    活锁

    根据事务的优先级顺序,可能会出现某个事务永远在等待封锁的情况,即事务T1封锁了数据对象A后,T2、T3陆续请求封锁,但是T1释放锁后,系统优先批准了T3的请求,T2仍然在等待。

    最简单的解决方法就是先来先服务(FCFS),不考虑事务的优先级。

     

    死锁

    事务T1封锁了数据A,事务T2封锁了数据B,然后T1请求封锁B,与此同时T2也请求封锁A,但因为两个事务的请求都需要等待对方释放锁,这样就出现了永远在等待对方的死锁。

    在数据库中,解决死锁问题主要有两类方法:预防和诊断解除。

    1)预防:

    1. 一次封锁法:每个事务一次将所有要使用的数据加锁,否则事务不能继续执行。

    带来的问题:阻碍了其他事务对数据的利用,从而降低了系统的并发度。

    2. 顺序封锁法:预先对数据规定一个封锁顺序,所有事务都按照这个顺序加锁,保证“先到先得”。

    带来的问题:需要处理的信息太多,开销大,成本高。

     

    2)诊断与解除:

    1. 超时法:某个事务的等待时间超过规定时间,则系统判定为死锁。

    带来的问题:规定时间过短,可能误判死锁;规定时间过长,可能不能及时发现死锁。

    2. 等待图法:并发控制子系统周期性地生成事务等待图,动态地反映所有事务的等待情况。如果发现图中存在回路,则表示系统中出现了死锁。

    解除方法:通常撤销一个处理代价最小的事务,释放此事务持有的所有锁,使其他事务得以继续运行下去。


     

    并发调度的可串行性

    可串行性是并发事务正确调度的准则。

    当且仅当多个事务的并发执行结果,与按某一次序的串行执行结果相同,这种并发调度策略才是可串行化调度,即具有可串行性。

     

    例子(《数据库系统概论(第5版)》p318):

    事务T1:读B;A=B+1;写A

    事务T2:读A;B=A+1;写B

     

    那么如何判断可串行化调度呢?

    我们需要引入一个概念——冲突操作,冲突操作是指不同事务对同一个数据读写写写操作,其他操作都属于不冲突操作。

    很容易理解,对于同一数据的操作,不可能一边在读,同时另一边在写,更不可能两边都在写,这是不符合逻辑的。

     

    在一个调度策略中,交换两个事务的不冲突操作的次序,得到另一个调度策略,如果另一个调度策略的执行结果与原来的调度相同,则称原来的调度为冲突可串行化调度

    冲突可串行化调度是可串行化调度的充分条件,但不是必要条件。


     

    两段锁协议

    为了保证并发调度的正确性,DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。

    目前DBMS普遍采用两段锁协议(TwoPhase Locking,2PL)来实现,所有事务遵守两段锁协议是可串行化调度的充分条件,但不是必要条件。

     

    两段锁的含义:

    1)第一阶段(扩展阶段):所有事务对数据加锁,但不能解锁;

    2)第二阶段(收缩阶段):所有事务对数据解锁,但不能加锁。

    *需要注意的是,不同事务对同一数据的加锁仍遵循两种锁的特性以及封锁协议。

     

    预防死锁的一次封锁法遵守两段锁协议;但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁,因此遵守两段锁协议的事务可能发生死锁。


     

    封锁的粒度

    封锁粒度(granularity)是指封锁对象的大小。

    封锁对象可以是逻辑单元,也可以是物理单元。以关系数据库为例,逻辑单元包括属性值、属性值的集合、元组、关系、索引项、索引表乃至整个数据库;物理单元包括页(数据页或索引页)、物理记录等。

     

    封锁粒度与系统的并发度并发控制的开销有关:封锁粒度越大,数据库能封锁的数据单元越少,并发度越小,系统开销也变小。

    一般来说,处理个别元组的事务以元组为封锁粒度;处理某个关系的大量元组的事务以关系为封锁粒度;处理多个关系的大量元组的事务以数据库为封锁粒度。

     

    多粒度封锁

    在一个系统中,提供多种封锁粒度给不同的事务选择,这种封锁方法称为多粒度封锁( multiple granularity locking)

    • 定义多粒度树:多粒度树的根结点是整个数据库,表示最大的封锁粒度,叶结点是最小的封锁粒度,如元组、属性值等。
    • 封锁协议:给一个结点加锁的同时,该结点的所有后裔结点也会被加上同样的锁。对于该结点来说,这种加锁方式为显式封锁,而对于其后裔结点来说,这样的方式为隐式封锁

    在多粒度封锁中,显式封锁和隐式封锁的效果是一样的,因此系统检查封锁冲突时,不仅要检查显式封锁,还要沿着多粒度树上下检查隐式封锁。

    显然,这样的检查方法效率很低。为此人们引进了一种新型锁,称为意向锁(intention lock)

     

     

    意向锁

    对任何一个结点加锁时,必须先对它的上层结点加意向锁。

     

    三种常用的意向锁:

    1)意向共享锁(IS锁):

    对一个数据对象加IS锁,表示它的后裔结点拟(意向)加S锁

    事务T1对数据对象A加上IS锁后,事务T2可以继续加除X锁以外的锁。

    2)意向排他锁(IX锁):

    对一个数据对象加IX锁,表示它的后裔结点拟(意向)加X锁

    事务T1对数据对象A加上IX锁后,事务T2只能继续加IS或IX锁

    3)共享意向排他锁(SIX = S+IX锁):

    对一个数据对象先加S锁,再加IX锁。例如对某个表加SIX锁,则表示该事务要读(S)整个表,同时会更新(IX

    )个别元组。

    事务T1对数据对象A加上SIX锁后,事务T2只能加IS锁

     

    在具有意向锁的多粒度封锁方法中,任意事务T要对一个数据对象加锁,必须先对它的上层结点加意向锁。

    申请封锁时应该按自上而下的次序进行,释放封锁时则应该按自下而上的次序进行。(栈结构)

     

    具有意向锁的多粒度封锁方法提高了系统的并发度,减少了加锁和解锁的开销,已经在实际的DBMS产品中得到广泛使用。

     

    锁的强度

    锁的强度是指它对其他锁的排斥程度。

    一个事务在申请封锁时,以强锁代替弱锁是安全的,反之不然。

    强度排序:

    X > SIX > S / IX > IS

     

    展开全文
  • mysql中的两段锁协议和三级封锁协议

    千次阅读 2019-04-17 09:14:42
    两段锁协议 一个事务中一旦开始释放,就不能再申请新锁了。事务的加锁和解锁严格分为两个阶段,第一阶段加锁,第二阶段解锁。 目的 :”引入2PL是为了保证事务的隔离保证并发调度的准确,多个事务在并发的...

    两段锁协议

    一个事务中一旦开始释放锁,就不能再申请新锁了。事务的加锁和解锁严格分为两个阶段,第一阶段加锁,第二阶段解锁。

    目的 :”引入2PL是为了保证事务的隔离性,保证并发调度的准确性,多个事务在并发的情况下依然是串行的。

    封锁定理:

    如果事务是良构的且是两阶段的,那么任何一个合法的调度都是隔离的。

    2PL和2PC

    **2PL,两阶段加锁协议:主要用于单机事务中的一致性与隔离性。**主要是在MySql(仅限innodb)中使用的。
    2PC,两阶段提交协议,用于分布式事务。

    S2PL(Strict 2 PL)

    SQL是千变万化、条数不定的,数据库很难在事务中判定什么是加锁阶段,什么是解锁阶段。因此规定:

    1. 在事务中只有提交(commit)或者回滚(rollback)时才是解锁阶段,
    2. 其余时间为加锁阶段。
      在这里插入图片描述
      两阶段加锁对数据库性能的影响详见该文章(很好的文章,仔细看看):https://blog.csdn.net/qq4165498/article/details/76855139

    封锁协议:

    运用X锁和S锁对数据对象进行加锁时约定的规则就是封锁协议。

    目的是在不同程序上保证数据的一致性。

    三级封锁协议

    1. 一级封锁:修改数据加x锁直到事务结束才释放。在此协议中,仅仅是读数据是不需要加锁的,所以只能解决丢失修改问题,不能解决脏读和不可重复读。
    2. 二级封锁:在一级封锁的基础上,加了一条:T事务在读取数据R之前必须先对其加上S锁,读完释放S锁。可以解决丢失修改和脏读(加了读锁就可以防止在读的期间其他事务进行修改,但是读完之后,事务结束之前,依然可能会其他事务进行修改,导致不可重复读)。
    3. 三级封锁协议:一级封锁协议加上事务T在读取数据R之前必须先对其加S锁,直到事务结束才释放。:解决了丢失修改、脏读和不可重复读的问题。
    展开全文
  • 但事实上,ZooKeeper并没有完全采用Paxos算法,而是使用了一种称为ZooKeeperAtomic Broadcast (ZAB, ZooKeeper 原子消息广播协议)的协议作为其数据一致性的核心算法。 ZAB协议是为分布式协调服务ZooKeeper专门设计的一...

    一、ZAB 协议简介

    在深入了解ZooKeeper之前,认为ZooKeeper就是Paxos算法的一个实现。但事实上,ZooKeeper并没有完全采用Paxos算法,而是使用了一种称为ZooKeeper Atomic Broadcast (ZAB, ZooKeeper 原子消息广播协议)的协议作为其数据一致性的核心算法。

    ZAB协议是为分布式协调服务ZooKeeper专门设计的一种支持崩溃恢复的原子广播协议。
    ZAB协议并不像Paxos算法那样,是一种通用的分布式一致性算法,它是一种特别为ZooKeeper设计的崩溃可恢复的原子消息广播算法。

    在ZooKeeper中,主要依赖ZAB协议来实现分布式数据一致性,基于该协议,ZooKeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。具体的,ZooKeeper使用一个单一的主进程来接收并处理客户端的所有事务请求,并采用ZAB的原子广播协议,将服务器数据的状态变更以事务Proposal的形式广播到所有的副本进程上去。ZAB协议的这个主备模型架构保证了同一时刻集群中只能够有一个主进程来广播服务器的状态变更,因此能够很好地处理客户端大量的并发请求。另一方面,考虑到在分布式环境中,顺序执行的一些状态变更其前后会存在一定的依赖关系,有些状态变更必须依赖于比它早生成的那些状态变更,例如变更C需要依赖变更A和变更B。这样的依赖关系也对ZAB协议提出了一个要求:ZAB协议必须能够保证一个全局的变更序列被顺序应用,也就是说,ZAB协议需要保证如果一个状态变更已经被处理了,那么所有其依赖的状态变更都应该已经被提前处理掉了。(意思就是已经处理的事务请求不会再处理,不能丢失)最后,考虑到主进程在任何时候都有可能出现崩溃退出或重启现象,因此,ZAB协议还需要做到在当前主进程出现上述异常情况的时候,依旧能够正常工作。

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

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

    二、协议内容

    ZAB协议包括两种基本的模式,分别是崩溃恢复和消息广播。

    什么时候会进行Leader选举?
    当整个服务框架在启动过程中,或是当Leader服务器出现网络中断、崩溃退出与重启等异常情况时,ZAB协议就会进入恢复模式并选举产生新的Leader 服务器。

    什么时候进入消息广播模式 和 数据恢复模式?

    当选举产生了新的Leader服务器,同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后,ZAB协议就会退出恢复模式。其中,所谓的状态同步是指数据同步,用来保证集群中存在过半的机器能够和Leader服务器的数据状态保持一致。
    当集群中已经有过半的Follower 服务器完成了和Leader 服务器的状态同步,那么整个服务框架就可以进入消息广播模式了。当一台同样遵守ZAB协议的服务器启动后加入到集群中时,如果此时集群中已经存在一个Leader服务器在负责进行消息广播,那么新加入的服务器就会自觉地进入数据恢复模式:找到Leader 所在的服务器,并与其进行数据同步,然后一起参与到消息广播流程中去。

    当Leader服务器出现崩溃退出或机器重启,亦或是集群中已经不存在过半的服务器与该Leader服务器保持正常通信时,那么在重新开始新一轮的原子广播事务操作之前,所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态,于是整个ZAB流程就会从消息广播模式进入到崩溃恢复模式。
    一个机器要成为新的Leader,必须获得过半进程的支持,同时由于每个进程都有可能会崩溃,因此,在ZAB协议运行过程中,前后会出现多个Leader, 并且每个进程也有可能会多次成为Leader.进入崩溃恢复模式后,只要集群中存在过半的服务器能够彼此进行正常通信,那么就可以产生一个新的Leader并再次进人消息广播模式。

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

    消息广播

    ZAB协议的消息广播过程使用的是一个原子广播协议,类似于一个二阶段提交过程。针对客户端的事务请求,Leader 服务器会为其生成对应的事务Proposal, 并将其发送给集群中其余所有的机器,然后再分别收集各自的选票,最后进行事务提交,如图所示就是ZAB协议消息广播流程的示意图。
    在这里插入图片描述

    ZAB协议中涉及的二阶段提交过程的不同之处?

    在ZAB协议的二阶段提交过程中,移除了中断逻辑,所有的Follower 服务器要么正常反馈Leader提出的事务Proposal,要么就抛弃Leader服务器。同时,ZAB协议将二阶段提交中的中断逻辑移除意味着我们可以在过半的Follower 服务器已经反馈Ack之后就开始提交事务Proposal 了,而不需要等待集群中所有的Follower服务器都反馈响应。当然,在这种简化了的二阶段提交模型下,是无法处理Leader 服务器崩溃退出而带来的数据不一致问题的,因此在ZAB协议中添加了另一个模式,即采用崩溃恢复模式来解决这个问题。另外,整个消息广播协议是基于具有FIFO(先进先出)特性的TCP协议来进行网络通信的,因此能够很容易地保证消息广播过程中消息接收与发送的顺序性。

    什么是ZXID?

    在整个消息广播过程中,Leader服务器会为每个事务请求生成对应的Proposal来进行广播,并且在广播事务Proposal之前,Leader服务器会首先为这个事务Proposal分配一个全局单调递增的唯一ID, 我们称之为事务ID (即ZXID)。

    由于ZAB协议需要保证每一个消息严格的因果关系,因此必须将每一个事务Proposal按照其ZXID的先后顺序来进行排序与处理。具体的,在消息广播过程中,Leader服务器会为每一个Follower服务器都各自分配一个单独的队列,然后将需要广播的事务Proposal 依次放入这些队列中去,并且根据FIFO策略进行消息发送。每一个Follower服务器在接收到这个事务Proposal 之后,都会首先将其以事务日志的形式写入到本地磁盘中去,并且在成功写入后反馈给Leader服务器一个Ack响应。当Leader服务器接收到超过半数Follower的Ack响应后,就会广播一个Commit消息给所有的Follower服务器以通知其进行事务提交,同时Leader自身也会完成对事务的提交,而每一个 Follower服务器在接收到Commit消息后,也会完成对事务的提交。

    崩溃恢复

    什么时候进入崩溃恢复模式?

    ZAB协议的这个基于原子广播协议的消息广播过程,在正常情况下运行非常良好,但是一旦Leader服务器出现崩溃,或者说由于网络原因导致Leader服务器失去了与过半Follower的联系,那么就会进入崩溃恢复模式。

    在ZAB协议中,为了保证程序的正确运行,整个恢复过程结束后需要选举出一个新的Leader服务器。因此,ZAB协议需要一个高效且可靠的Leader选举算法,从而确保能够快速地选举出新的Leader。同时,Leader选举算法不仅仅需要让Leader自己知道其自身已经被选举为Leader,同时还需要让集群中的所有其他机器也能够快速地感知到选举产生的新的Leader服务器。

    基本特性
    根据上面的内容,我们了解到,ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功,那么应该在所有的机器上都被处理成功,哪怕机器出现故障崩溃。接下来我们看看在崩溃恢复过程中,可能会出现的两个数据不一致性的隐患及针对这些情况ZAB协议所需要保证的特性。

    特性一:
    ZAB协议需要确保那些已经在Leader服务器.上提交的事务最终被所有服务器都提交。

    假设一个事务在Leader服务器上被提交了,并且已经得到过半Follower服务器的Ack反馈,但是在它将Commit消息发送给所有Follower机器之前,Leader服务器挂了
    在这里插入图片描述
    上图中的消息C2就是一个典型的例子:在集群正常运行过程中的某一个时刻,Leader服务器先后广播了消息PI、P2、C1、P3和C2,其中,当Leader服务器将消息C2(C2是CommitOfProposal2的缩写,即提交事务Proposal2)发出后就立即崩溃退出了。针对这种情况,ZAB协议就需要确保事务Proposal2最终能够在所有的服务器上都被提交成功,否则将出现不一致。

    特性二:
    ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务。

    如果在崩溃恢复过程中出现一个需要被丢弃的提案,那么在崩溃恢复结束后
    需要跳过该事务Proposal,如下图。
    在这里插入图片描述

    假设初始的Leader 服务器Server1 在提出了一个事务P3之后就崩溃退出了,从而导致集群中的其他服务器都没有收到这个事务Proposal。于是,当Serverl恢复过来再次加入到集群中的时候,ZAB协议需要确保丢弃Proposal3这个事务。

    结合上面提到的这两个崩溃恢复过程中需要处理的特殊情况,就决定了ZAB协议必须设计这样一个Leader 选举算法:
    能够确保提交已经被Leader 提交的事务Proposal, 同时丢弃已经被跳过的事务Proposal。

    针对这个要求,如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号(即ZXID最大)的事务Proposal,那么就可以保证这个新选举出来的Leader一定具有所有已经提交的提案。因为每次提交事务ZXID都会自增,更为重要的是,如果让具有最高编号事务Proposal 的机器来成为Leader, 就可以省去Leader 服务器检查Proposal的提交和丢弃工作的这一步操作了。

    三、数据同步

    完成Leader选举之后,在正式开始工作(即接收客户端的事务请求,然后提出新的提案)之前,Leader服务器会首先确认事务日志中的所有Proposal是否都已经被集群中过半的机器提交了,即是否完成数据同步。

    ZAB协议的数据同步过程

    所有正常运行的服务器,要么成为Leader,要么成为Follower并和Leader保持同步。Leader服务器需要确保所有的Follower服务器能够接收到每一条事务Proposal,并且能够正确地将所有已经提交了的事务Proposal应用到内存数据库中去。具体的,Leader服务器会为每一个Follower服务器都准备一个队列,并将那些没有被各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器,并在每一个Proposal消息后面紧接着再发送一个Commit消息,以表示该事务已经被提交。等到Follower服务器将所有其尚未同步的事务Proposal都从Leader服务器上同步过来并成功应用到本地数据库中后,Leader服务器就会将该Follower服务器加入到真正的可用Follower列表中,并开始之后的其他流程。上面讲到的就是正常情况下的数据同步逻辑。

    ZAB协议是如何处理那些需要被丟弃的事务Proposal 的。

    在ZAB协议的事务编号ZXID设计中,ZXID是一个64位的数字,其中低32位可以看作是一个简单的单调递增的计数器,针对客户端的每一个事务请求,Leader服务器在产生一个新的事务Proposal的时候,都会对该计数器进行加1操作;而高32位则代表了Leader周期epoch的编号,每当选举产生一个新的Leader服务器,就会从这个Leader服务器上取出其本地日志中最大事务Proposal的ZXID,并从该ZXID中解析出对应的epoch值,然后再对其进行加1操作,之后就会以此编号作为新的epoch,并将低32位置0来开始生成新的ZXID。ZAB协议中的这一通过epoch编号来区分Leader周期变化的策略,能够有效地避免不同的Leader服务器错误地使用相同的ZXID编号提出不一样的事务Proposal的异常情况,这对于识别在Leader崩溃恢复前后生成的Proposal非常有帮助,大大简化和提升了数据恢复流程。基于这样的策略,当一个包含了上一个Leader 周期中尚未提交过的事务Proposal 的服务器启动时,其肯定无法成为Leader, 原因很简单,因为当前集群中一定包含一个Quorum集合,该集合中的机器一定包含 了更高epoch的事务Proposal, 因此这台机器的事务Proposal肯定不是最高,也就无法成为Leader 了。当这台机器加入到集群中,以Follower角色连接上Leader服务器之后,Leader服务器会根据自己服务器上最后被提交的Proposal 来和Follower服务器的Proposal进行比对,比对的结果当然是Leader 会要求Follower进行一个回退操作一回退到一个确实已经被集群中过半机器提交的最新的事务Proposal。 举个例子来说,在上图中,当Serverl连接上Leader后,Leader 会要求Serverl去除P3。

    四、ZAB算法描述

    整个ZAB协议主要包括消息广播和崩溃恢复两个过程,进一步可以细分为三个阶段,分别是发现(Discovery).同步(Synchronization) 和广播( Broadcast)阶段。组成ZAB协议的每一个分布式进程,会循环地执行这三个阶段,我们将这样一个循环称为一个主进程周期。

    阶段一:发现

    阶段-.主要就是Leader选举过程,用于在多个分布式进程中选举出主进程,准Leader L和Follower F的工作流程分别如下。

    步骤F.1.1 Follower F将自己最后接受的事务Proposal 的epoch值CEPOCH发送给准Leader L。

    步骤L.1.1当接收到来 自过半Follower 的epoch值消息后,准Leader L会生成新的epoch值消息给这些过半的Follower。
    关于这个epoch值e’,准Leader L会从所有接收到的epoch值消息中选取出最大的epoch值,然后对其进行加1操作,即为e’。

    步骤F.1.2当Follower接收到来自准Leader L的新的epoch值消息后,如果其检测到当前的epoch值小于e’,那么就会将当前epoch值赋值为e’,同时向这个准Leader L反馈Ack消息。在这个反馈消息(ACK-E(F.p,hr))中,包含了当前该Follower的最后一个处理的事务,以及该Follower的历史事务Proposal集合。当LeaderL接收到来自过半Follower的确认消息Ack之后,LeaderL就会从这过半服务器中选取出一个FollowerF,并使用其作为初始化事务集合le’。
    关于这个FollowerF的选取,对于Quorum中其他任意-一个FollowerF’,F需要满足以下两个条件中的一个:
    CEPOCH(F’p) < CEPOCH (F.p) 需要小于最后一个提交事务的epoch值。
    (CEPOCH (F’p)= CEPOCH(F.p))&(F’zxid <F.zxid或F’zxid= F.zxid) 需要等于最后一个提交事务的epoch值并且zxid小于Follower f处理过的历史事务Proposal中最后一个事务Proposal 的事务标识ZXID。
    至此,ZAB协议完成阶段一的工作流程。.

    阶段二:同步

    在完成发现流程之后,就进入了同步阶段。在这一阶段中,Leader L和FollowerF的工
    作流程分别如下。

    步骤L.2.1 Leader L会将e’(最大的epcho值)和Ie’(初始化事务集合)以NEWLEADER(e’,Ie’)消息的形式发送给所有Quorum(认定整个集群是否可用的一种方式)中的Follower。

    步骤F.2.1当Follower 接收到来自Leader L的NEWLEADER(e’,le’)消息后,如果Follower发现CEPOCH (F.p) ≠e’, 那么直接进入下一轮循环,因为此时Follower发现自己还在上一轮,或者更上轮,无法参与本轮的同步。如果CEPOCH (F.p)= e’,那么Follower就会执行事务应用操作。最后,Follower 会反馈给Leader,表明自己已经接受并处理了所有L中的事务Proposal。

    步骤L.2.2当Leader接收到来自过半Follower 针对NEWLEADER(e’,Ie’)的反馈消息后,就会向所有的Follower发送Commit消息。至此Leader完成阶段二。

    步骤F.2.2当Follower收到来自Leader的Commit消息后,就会依次处理并提交所有在Ie’中未处理的事务。至此Follower完成阶段二。

    阶段三:广播
    完成同步阶段之后, ZAB协议就可以正式开始接收客户端新的事务请求,并进行消息广播流程。

    步骤L.3.1 Leader L接收到客户端新的事务请求后,会生成对应的事务Proposal,并根据ZXID的顺序向所有Follower发送提案<e’,<v,z>>,其中epoch(z) = e’

    步骤F.3.1Follower根据消息接收的先后次序来处理这些来自Leader的事务Proposal,并将他们追加到hp中去,之后再反馈给Leader。

    步骤L.3.1当Leader 接收到来自过半Follower 针对事务Proposal <e’,<v,z>>的Ack消息后,就会发送Commit <e’,<v,z>>消息给所有Follower,要求它们进行事务的提交。
    步骤F.3.2当Follower F接收到来自Leader的Commit <e’,<v,z>>消息后,就会开始提交事务Proposal<e’,<v,z>>。 需要注意的是,此时该FollowerF必定已经提交了事务Proposal<v’,z’>
    以上就是整个ZAB协议的三个核心工作流程。

    五、ZAB 与Paxos算法的联系与区别

    ZAB协议并不是Paxos算法的一个典型实现,在说ZAB和Paxos之间的区别之前,我们首先来看下两者的联系。

    • 两者都存在一个类似于Leader进程的角色,由其负责协调多个Follower进程的运行。
    • Leader进程都会等待超过半数的Follower做出正确的反馈后,才会将一个提案进行提交。
    • 在ZAB协议中,每个Proposal中都包含了一个epoch值,用来代表当前的Leader周期,在Paxos算法中,同样存在这样的一个标识,只是名字变成了Ballot。

    在Paxos算法中,一个新选举产生的主进程会进行两个阶段的工作。第一阶段被称为读阶段,在这个阶段中,这个新的主进程会通过和所有其他进程进行通信的方式来收集上一个主进程提出的提案,并将它们提交。第二阶段被称为写阶段,在这个阶段,当前主进程开始提出它自己的提案。在Paxos算法设计的基础上,ZAB协议额外添加了一个同步阶段。在同步阶段之前,ZAB协议也存在一个和Paxos算法中的读阶段非常类似的过程,称为发现(Discovery)阶段。在同步阶段中,新的Leader会确保存在过半的Follower已经提交了之前Leader周期中的所有事务Proposal。 这一同步阶段的引入,能够有效地保证Leader在新的周期中提出事务Proposal之前,所有的进程都已经完成了对之前所有事务Proposal的提交。一旦完成同步阶段后,那么ZAB就会执行和Paxos算法类似的写阶段。总的来讲,ZAB协议和Paxos 算法的本质区别在于,两者的设计目标不太一样。

    不同点总结:
    ZAB协议主要用于构建一个高可用的分布式数据主备系统,例如ZooKeeper
    Paxos算法则是用于构建一一个分布式的一致性状态机系统。

    六、运行状态

    在ZAB协议的设计中,每-一个进程都有可能处于以下三种状态之一。

    • LOOKING: Leader选举阶段
    • FOLLOWING: Follower 服务器和Leader保持同步状态
    • LEADING:Leader服务器作为主进程领导状态
    展开全文
  • 【问题2】 (1)出现问题:客户1购买后写入库存量值被覆盖,库存量不能体现客户1已经购买,属于丢失修改造成的数据一致性。 (2)重写后的序列: I1(A) I2(A) Xlock(A) X1=R1(A) x1=x1-a1 W(A,x1) Unlock(A)...
  • 一、并发调度 并发调度啥意思? 就是当很多事务同时执行的时候应该...可串行是并发事务正确调度的准则。 比如: 事务 T1: 读 B A=B+1;写回 A; 事务 T2: 读 A B=A+1;写回 B; 假设 A、B 的初始值都是 2,串行
  • 如何保证分布式系统数据一致性

    万次阅读 2018-12-24 10:26:05
    面试的时候,有面试官问到:选取你比较熟悉的项目,谈谈如何在做容灾负载的时候数据一致性问题,具体点比如你里面的派单,如何保证一个司机不在同一时间内接到个订单,然后保证实时性?  一般的解决方案是在派单...
  • 分布式一致性协议

    千次阅读 2019-01-26 19:52:04
    一致性(Consistency)是指多副本(Replications)问题中的数据一致性。关于分布式系统的一致性模型有以下几种: 强一致性 当更新操作完成之后,任何多个后续进程或者线程的访问都会返回最新的更新过的值,直到这...
  • 保证数据库的一致性 数据一致性:由于并发操作破坏了事务的隔离性 并发控制就是要用正确的方式调度并发操作,使一个用户事务的执行不受其他事务的干扰,从而避免造成数据的不一致性 并发控制带来的问题 并发...
  • zookeeper如何保证数据一致性

    千次阅读 2019-08-10 10:56:57
    zookeeper如何保证数据一致性 zookeeper(简称zk),是动物园管理员的意思,动物对应服务节点,如上图中的hadoop的标志是小象,hive的标志是昆虫,zk是这些分散的动物节点的管理者、协调者。 zk应用于分布式场景中...
  • 微服务系统中的数据一致性,你都会了吗

    万次阅读 多人点赞 2021-09-17 23:11:34
    你好,我是看山。 从单体架构到分布式架构,从巨石架构到微服务...需要注意一下,本文所设计的数据一致性,不是多数据副本之间保持数据一致性,而是系统之间的业务数据保持一致性。 本地事务 在早期的系统中,我们可.
  • 分布式一致性协议:Raft算法详解

    万次阅读 2019-05-24 21:37:40
    在分布式系统中,有很多复杂的理论,从CAP理论到BASE理论,我们不断的在可用性以及一致性之间做出抉择,每一部分都相当复杂,就分布式一致性而言,又有许多协议,从2PC到3PC再到paxos算法,到ZAB协议,再到Raft算法...
  • 浅析数据一致性

    万次阅读 多人点赞 2016-02-19 15:27:38
    什么是数据一致性?  在数据有多分副本的情况下,如果网络、服务器或者软件出现故障,会导致部分副本写入成功,部分副本写入失败。这就造成各个副本之间的数据不一致,数据内容冲突。 实践中,导致数据不一致的情况...
  • 总线LOCK和缓存一致性协议

    千次阅读 2019-05-27 16:41:04
    随着多核时代的到来,并发操作已经成了很正常的现象,操作系统必须要有一些机制和原语,以保证某些基本操作的原子性,比如处理器需要保证...有种机制:总线锁定和缓存一致性。 我们知道,CPU和物理内存之间的通...
  • 一致性协议总览

    千次阅读 2018-03-23 20:36:09
    一致性模型 一致性模型本质上是进程与数据存储的约定,主要是用于解决分布式系统中数据复制时保持一致性的问题 一致性协议 一致性模型就像是接口,而一致性协议就像是接口的具体实现
  • 微服务架构下的数据一致性保证

    千次阅读 2018-09-30 17:30:08
    设计到系统,其中绕不开的就是数据一致性,从本地事务,到后来的分布式事务,都能够有效的保证数据一致性。但是在微服务架构中,这种方式都不是最好的选择。 1. 使用本地事务和分布式事务保证一致性 在传统的...
  • 保证分布式数据一致性的6种方案

    万次阅读 2018-07-30 17:17:07
    在电商等业务中,系统一般由多个独立的服务组成,如何解决分布式调用时候数据一致性?  具体业务场景如下,比如一个业务操作,如果同时调用服务 A、B、C,需要满足要么同时成功;要么同时失败。A、B、C 可能是多...
  • 阶段提交协议(two phase commit protocol,2PC)可以保证数据的强一致性,许多分布式关系型数据管理系统采用此协议来完成分布式事务。它是协调所有分布式原子事务参与者,并决定提交或取消(回滚)的分布式算法。...
  • redis中如何保证缓存数据一致性

    千次阅读 2019-11-04 22:13:53
    当有个线程A、B,同时对一条数据进行操作,一开始数据库和redis的数据都为tony,当线程A去修改数据库,将tong改为allen,然后线程A在修改缓存中的数据,可能因为网络原因出现延迟,这个时候线程B,将数据修改成了...
  • 面试问题(如何保证分布式数据最终一致性

    万次阅读 多人点赞 2018-03-01 10:51:42
    保证分布式系统数据一致性的6种方案编者按:本文由「高可用架构后花园」群讨论整理而成。有人的地方,就有江湖有江湖的地方,就有纷争问题的起源在电商等业务中,系统一般由多个独立的服务组成,如何解决分布式调用...
  • 1,一致性协议 阶段提交协议与Raft协议、Paxos协议 ①阶段提交协议 在分布式系统中,每个节点虽然可以知晓自己的操作时成功或者失败,却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时,为了...
  • volatile和Cache一致性协议之MESI

    万次阅读 热门讨论 2017-08-14 17:46:06
     所以就出现了缓存一致性协议。最出名的就是Intel 的MESI协议,MESI协议保证了每个缓存中使用的共享变量的副本是一致的。它核心的思想是:当CPU写数据时,如果发现操作的变量是共享变量,即在其他CPU中也存在该变量...
  • Nacos 源码分析(五) 一致性协议Distro

    千次阅读 2020-05-07 20:33:16
    这个为临时数据一致性协议 distro协议的关键点: distro协议是为了注册中心而创造出的协议; 客户端与服务端有个重要的交互,服务注册与心跳发送; 客户端以服务为维度向服务端注册,注册后每隔一...
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
     HashMap的数据结构: 在java编程语言中,最基本的结构就是种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的...
  • 从本文开始,笔者将花三到四篇文章的篇幅,介绍Paxos算法。包括它的理论基础、基本实现、变种实现,其它保证最终一致性的算法,等等。
  • 目录 1. 传统应用的事务管理 1.1 本地事务 1.2 分布式事务 2. 微服务下的事务管理 3. 实现微服务下数据一致性的方式 3.1 可靠事件通知模式 ...再介绍微服务下的数据一致性之前,先简单地介绍一...
  • ZAB和Raft一致性协议的对比 日志同步流程不同 ZAB 协议流程数据同步客户端连接到任意服务端,被重定向到leader上,向leader发送事务请求,leader使用类似二阶段提交的步骤,先向follower发送事务请求,待接到过半...
  • zookeeper怎么保证一致性的(ZAB协议)

    千次阅读 2019-08-16 16:37:08
    怎么保证一致性,是依赖了ZAB协议 解释:ZAB协议是伪分布式协调服务Zookeeper专门设计的一种崩溃恢复的原子广播协议种基本的模式: 崩溃恢复 消息广播 这个模式是相辅相成的 消息广播模式就是zoo...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 181,339
精华内容 72,535
关键字:

两段锁协议是保证数据一致性的协议