精华内容
下载资源
问答
  • 数据库并发控制、锁的简单理解并发控制并发优点三大并发问题结果可串行化锁锁简介两段锁协议防——死锁预防治——死锁检测并发控制、锁小结 并发控制 并发优点  为什么要并发,或者说并发有什么好处?   1、并发...

    并发控制


    并发优点

     为什么要并发,或者说并发有什么好处?
      1、并发可以改善CPU等资源的资源利用率,提高系统效率。(这里类比操作系统,有些进程在等待IO的时候,可以把CPU让出来给别的进程用)
      2、不同事物可能访问数据库的不同内容,这样可以提高数据库的利用率。(数据库里面那么多表,一个事物也就访问几个或者十几个,不并发太浪费了些)

    三大并发问题

    刚刚说了并发的好处,在提到第二个好处的时候,对于“访问数据库不同的内容”,如果两个事物访问数据库的内容有交叉怎么办?以下图为例:
    在这里插入图片描述
    因此在并发过程中会遇到并发冲突的问题,只有解决好了这些问题,并发才能较为顺利的完成。

    • 1、丢失修改——写-写冲突
    • 2、读脏数据——写-读冲突
    • 3、不可重复读——读-写冲突

    接下来分析一下这三个并发问题:

    • 1.丢失修改。也就是说:其中一个事物对数据库的修改会被另一个并发事务覆盖,从而导致这个事务所作的修改被覆盖了。举个例子:
    事务T1事务T2
    Read(x)
    Read(x)
    x = x+2
    x = 5*x
    write(x)
    write(x)

    假设x的初值为6,事务T1修改完x之后,x的值为8,之后被写回到数据库中。但是刚写回数据库,就被事务T2计算的x结果30覆盖了,就好像T1这个事务啥都没干一样。

    • 2、读脏数据。所谓读脏数据,就是读取正在更新的数据。因为事务在进行一半的时候,很有可能因为故障或者因为其他原因要进行回退的,如果另一个事务T2读了事务T1正在更新的数据,就会因为T1的回退而产生多米诺效应,也要跟着回退。举个例子:
    事务T1事务T2事务T3
    write(x)
    read(x)
    y = x+1
    write(y)
    read(y)
    z = y+2
    write(y)
    故障 -> RollBack

    当事务T1出现故障需要滚回的时候,事务T2要受到事务T1的影响滚回,同时事务T3也要受到事务T2的影响滚回,整个恢复过程就会出现多米诺现象。

    • 3、不可重复读。就是事务在工作过程中,在前面读取的内容和在后面读取的内容不相同。举个例子:
    事务T1事务T2
    Read(x)
    temp = x +3write(x)
    Read(x)
    x = x +1
    write(x)

    上面这个例子中,事务T1在前面读取了x的内容用于计算,后面又想修改x的内容于是又读了一次x,结果后面读的x和前面读的x内容不一样了,那数据库的可信度就受到了质疑。

    结果可串行化

    正是因为上述的问题会给事务并发带来严重的不良影响,所以我们肯定想尽可能的避免出现上面的问题。但避免之前,我们要知道我们的事务并发会不会出现上述的问题,即要先判断出来有没有出现上述问题,之后才能进行进一步的处理。

    这个判断的方法就是 结果可串行化。它是判断并发运行事务对数据库产生结果是否正确的准则

    那么什么是结果可串行化呢?在了解这个概念之前,需要了解另一个概念——并发的特点。

    并发有一个特点:交给计算机并发执行的内容,执行结果与它们的执行顺序无关。什么意思呢?举个例子
    现在有三个程序A、B、C,A是对 学生表 写东西,B是读 玩具表 中的内容,C是从 西瓜表 中读取西瓜信息。那么这三个程序谁先执行谁后执行那都无所谓吧,它们的结果都是一样的。

    前面提到的下面这个过程:

    事务T1事务T2
    Read(x)
    Read(x)
    x = x+2
    x = 5*x
    write(x)
    write(x)

    事务T1和T2执行先后顺序不同,它的结果也是不一样的。即(假设x初始为6)
    T1->T2 x结果是 5*8 = 40
    T2->T1 x结果是 30+2 = 32
    那么这两个事务就不能丢给计算机并发处理。

    OK在了解完上述并发的特点之后,我们就可以提出结果可串行化的概念了。

    结果可串行化:如果n个事务并发的结果是这n个事务串行结果中的一种,那么这n个事务就是结果可串行化的。举个例子:
    现在有T1、T2、T3三个事务,它们的串行结果就是它们的排列组合的结果,结果有3!种 = 6种。下面列出它们排列组合的结果:
       1、T1->T2->T3
       2、T1->T3->T2
       3、T2->T1->T3
       4、T2->T3->T1
       5、T3->T1->T2
       6、T3->T2->T1
    假设把这三个事务拿去并发,最后结果就是5的结果(这6种中的一种),OK那这三个事务就是结果可串行化的

    OK在上面的内容中我们已经能够判断出事务并发会不会出问题了,那下面我们就用锁解决那些会出问题的并发事务

    锁简介

    上锁指的是对资源的一种控制方式。锁大致分为三种锁:共享锁S,排他锁X,更新锁U
    其中共享锁S和排他锁X基本的封锁类型共享锁又称读锁,排他锁又称写锁。U锁在读之后写之前可以当作共享锁,在准备写的时候升级成排他锁。这样在写之前其他想读的事物也可以读,推迟排他的时间。
    用行表示一个数据对象上已经拥有的锁,用列表示某个事务要新申请的锁,表格里的内容表示能否申请成功,做出下面的相容矩阵

    \没有锁S锁U锁X锁
    S锁YYYN
    U锁YYNN
    X锁YNNN

    这里可以理一下这张表的逻辑,结合后面深入分析之后再过来看这张表会有一个更清晰的认识。

    用好锁,可以使得资源可以被很好的分配而不产生冲突。但是锁如果使用不当则会出现以下两种情况:

    • 活锁
    • 死锁

    活锁,类似于操作系统中进程的“饥饿”现象。一个事务等待别的事物释放锁的时间过长,甚至出现永远等待的情况。举个例子:

    事件事件
    T1对资源x申请S锁
    T2对资源x申请S锁T对资源x申请X锁
    T1对资源x释放S锁T等待
    T3对资源x申请S锁T等待
    T2对资源x释放S锁T等待
    T4对资源x申请S锁T等待
    T5对资源x申请S锁T等待
    T3对资源x释放S锁T等待
    T等待

    这里发现明明T申请锁的时间在很前面,但是它就是用不到锁,等待时间过长。(确实很气)

    死锁,就是事物在等待资源的过程中形成了等待环路。死锁如果不加以干涉,事物就永远无法进行下去。举个例子:

    事务Ta事务Tb
    对R1资源申请X锁对R2资源申请X锁
    对R1资源申请X锁
    对R2资源申请X锁事务Tb等待Ta锁释放
    事务Ta等待Tb锁释放事务Tb等待Ta锁释放

    这样双方互相等待形成死循环。

    封锁协议解决三大并发问题

    封锁协议是针对共享锁S和排他锁X提出的解决三大并发问题的方法。
    一共有三个级别的封锁:

    • 一级封锁协议:事物T在修改数据R之前必须先对其加X锁,直到事物结束才能释放。
    • 二级封锁协议:在一级基础上增加事物T在读数据R之前必须对其加S锁,读完后可立刻释放S锁
    • 三级封锁协议:在一级基础上增加事物T在读数据R之前必须对其加S锁,直到事物结束才释放

    给个表加以理解:
    在这里插入图片描述

    两段锁协议

    为了保证并发的正确性,数据库管理系统通过两段锁协议的方法实现并发调度的可串行性,即 若并发的所有事务均遵循两段锁协议,那么对这些事务的任何并发调度策略都是可串行化的。(用反证法可以证明)

    那么两段锁协议的内容又是什么呢?所谓两段锁协议是指所有事物必须分为两个阶段对数据项进行加锁和解锁

    • 扩展阶段:在对任何数据进行读、写操作之前,首先要申请并获得对该数据的封锁。
    • 收缩阶段:在释放一个封锁之后,事物不再申请和获得任何其他封锁。

    遵循两段锁协议有没有可能发生死锁呢?这里要和后面的一次封锁法做区分,两段锁协议是可能发生死锁的,比如下例:

    事务T1事务T2
    对B申请S锁
    对A申请S锁
    对A申请X锁
    等待事务T2释放对A申请X锁
    等待事务T2释放等待事务T1释放

    防——死锁预防

    防的思想主要在于:破坏死锁产生的必要条件,比如不让死锁形成环。
    防的方法主要有以下三种方法:

    • 1、一次封锁法
    • 2、顺序封锁法
    • 3、事务重试法(Transaction Retry)。

    其中前两种方法在操作系统中也提到过,但是不适合现代数据库,第三种方法在实际数据库中有使用。下面对这三种方法进行如下分析:

       1.一次封锁法:在事务的最开始就获得所有的锁,不然事务不继续运行。即对所有要用到的数据在最开始就进行加锁。这样做扩大封锁的范围降低了系统的并发度;而且事先很难精确要加锁的数据(可能有的数据要用到别的数据),因此要进一步扩大封锁范围,也要降低系统并发性。

       2.顺序封锁法给资源排序,所有的事物都按这个顺序进行封锁。但是就拿表资源来说,一个数据库中有成千上万个表,对这么多表进行排序本身就会有开销,而且数据库更新、删除表的操作很频繁,因此这样的排序及其不稳定;而且事物的封锁请求也是随着事物的执行动态决定的,很难预知。所以不太可行。

       3.事务重试法:给每个事物安排一个时间戳作为TID,之后通过比较事物的年龄决定哪个事物优先获得资源。核心思想为年龄大的事务先获得资源。事务重试法分为两种情况:等待死亡法基伤等待法

    • a)等待死亡法:Ta -> Tb即Ta等待Tb只有当Ta的年龄比Tb大的时候才等待。如果Ta比Tb小,而且Ta要等待Tb,那么Ta就会把自己滚回然后sleep挂起,等待一段时间之后再以原来的时间戳再次运行。(这样这个年轻的事务到后面还是会变成元老,这样它就不用再把自己滚回了)通过这种方式只有 年老 -> 年轻 单方向的等待,就不会产生死锁。当然活锁也不会产生,因为那个刚开始年轻的事务的时间戳是不变的,当比它更老的事务完成以后,它就是最老的了。

    • b)基伤等待法:Ta -> Tb即Ta等待Tb只有当Ta的年龄比Tb小的时候才等待。否则Ta会把Tb滚回(kill掉),之后Tb自己sleep挂起,然后Ta把资源抢过来。和等待死亡法核心思想一样。

    治——死锁检测

    治的思想主要在于:允许死锁发生,但是我要把死锁检测出来,同时经过处理把死锁断开

    治的方法主要有以下两种:

    • 1.超时法
    • 2.等待图法

    超时法顾名思义就是设置一个timeout时限,如果一个事务的等待超过了规定时限就认为发现死锁。由于这个时限不好设置,一些小系统可以用,大系统一般用不了。

    等待图法就是创建一个有向图G=<V,E>,其中结点是事务,边是事务等待情况。如果这个有向图出现了环路,就认为出现了死锁。这种方法在大系统中使用广泛。
    那环路是什么时候去检测呢? 出现新的边的时候 或者 周期性检查
    在检查出有环路之后如何解决死锁问题呢?——选择一个“牺牲者”,一般来说选择一个处理死锁代价最小的事务,将其撤销,释放该事务持有的所有的锁,使得其他事务运行下去,最后将被撤销的事务恢复。

    并发控制、锁小结

    1、对于并发控制来说,结果可串行化可以用来判断是否出现了并发的三大问题(可串行化证明一定可以并发,所以一定没有三大问题),并发的三大问题分别是:丢失修改、读脏数据和不可重复读。

    2、锁:基本锁有两种,X锁和S锁。如果锁使用不当会出现死锁和活锁现象。了解三大封锁协议是如何解决三大并发问题的。

    3、两段锁协议是结果可串行化的充分条件。

    4、了解死锁预防的三种方法和死锁检测的两种方法。

    展开全文
  • 在内部,PostgreSQL利用多版本并发控制( MVCC, Multi- Version Concurrency Control)来维护数据的一致性。这就意味着当检索数据时,每个事务看到的只是一段时间之前的数据快照,而不是数据的当前状态。这样,如果对...

    2021@SDUSC

    目录

    概述

    MVCC相关数据结构

    MVCC与快照

     总结


    概述

    PostgreSQL为开发者提供了丰富的管理数据并发访问的工具。在内部,PostgreSQL利用多版本并发控制( MVCC, Multi- Version Concurrency Control)来维护数据的一致性。这就意味着当检索数据时,每个事务看到的只是一段时间之前的数据快照,而不是数据的当前状态。这样,如果对每个数据库会话进行事务隔离,就可以避免一个事务看到其他并发事务的更新而导致不一致的数据。
    使用多版本并发控制的主要优点是对检索(读取)数据的锁请求与写数据的锁请求并不冲突,所以读不会阻塞写,而写也从不阻塞读。这就极大地提高了并发处理能力。
     

    多版本并发示例
    事务T1事务T2表A的变化事务T2的查询结果
    BEGINSELECT*FROM A;AA
    UPDATEA->AA
    SELECT * FROM A;A
    COMMIT
    SELECT * FROM A;AA

    MVCC相关数据结构

    在PostgreSQL系统中,更新数据时并不是用新值覆盖旧值,而是在表中另开辟一片空间来存放
    新的元组,让新值与旧值同时存放在数据库中,通过设置一些参数,让系统识别它们。
    PostgreSQL的数据以元组的形式存放在表中,同时存储该元组相关的描述信息,这些信息存储
    在HeapTupleFields中。
     

     
    typedef struct HeapTupleFields
    {
    TransactionId t_ xmin;//创建此tuple的XID .
    TransactionId t_ xmax;//删除此Tuple的XID
    union {
    ComnandId t_cid;//创建或者删除Tuple的command ID(即Cmin和Cmax),也可能两者都保存
    TransactionId t_ xvac;//清理操作的事务ID
    }t_ field3 ;
    }HeapTupleFields;
    

    从HeapTupleFields结构中可以看出,Xmin、Cmin、Xmax、Cmax和Xvac这五个字段被保存在三个物理空间中,Xmin 和Xmax分别有独立的字段存储,而Cmin、Cmax 和Xvac共享一个字段。因为Cmin和Cmax都只在创建或删除事务的运行期间内有效,而一般情况下,在同一个事务中创建并
    删除同一个元组的概率比较低,Cmin 和Cmax同时存在有效值的概率也就很小,所以把它们放在同一个物理空间中。如果一个事务确实创建并删除了同一个元组,则我们使用一个ComboCommandID来保存Cmin和Cmax。Combo Command ID保存的是一个到实际Cmin和Cmax的映射。另一方面,Xvac字段只由VACUUM FULL命令设置,此时并不需要Cmin和Cmax。
    在PostgreSQL中,Combo Command ID是32位的,所以可以映射到2个{ Cmin, Cmax} 组合。在最坏的情况下,每个命令把它之前所有命令创建的元组都删除掉,假设这些命令总共有N个,那
    么,系统需要的Combo Command ID有N*(N+1)/2个。在这种最坏的情况下,Combo Command ID最多可以保存92682个命令。在实际应用中,用户在达到这个命令限制之前,就已经耗尽了内存和硬盘空间,所以,把ComboCommandID设置成32位是足够的。.
    除了存储元组的事务、命令控制信息外,还需要存储元组的相关控制信息。这些信息存储在元
    组的头部HeapTupleHeaderData中。
     

    typedef struct HeapTupleHeaderData
    {
    union
    {HeapTupleFields t_ heap;
    DatumTupleFields t_ datum;
    }t_ choice ;
    ItemPointerData t_ ctid;//本元组或者新新元组的当前TID
    uint16  t_ infomask2;//标志位(属性、标志位的数量)
    uint16  t_ infomask;//标志位(元组的事务信息)
    uint8   t_ hoff;//头部长度
    bits8   t_ bits[1];//填充位,起标记作用
    } HeapTupleHeaderData;
    

    一个新元组被保存在磁盘中的时候,其t_.ctid就被初始化为它自己的实际存储位置。如果这个元组被更新了,该元组的L ctid 字段就指向更新后的新元组。由此可以看出,一个元组是最新版本的,当且仅当它的xmax空或者它的t ctid 指向它自己。如果要找到某个元组的最新版本,只需遍历由t _ctid构成的链表即可。
    在HeapTupleHeaderData中,还有一个重要的字段(1_ infomask) 用来表示当前元组的事务信息
     

    tdefine HEAP_ HASNULL  0x0001
    tdefine HEAP_ HASVARWI DTH 0x0002
    #define HEAP_ HASEXTERNAL 0x0004
    idefine HEAP_ HASOID  0x0008
    户以上四种标志不涉及元组可见性判断,用于表示元组本省的基本信息*/
    idefine HEAP_ COMBOCID 0x0020 //复合命令
    #define HEAP. XMAX_ EXCL LOCK 0x0040 // xmax 持有排他锁
    tdefine HEAP_ XMAX_ SHARED LOCK 0x0080 /* xmax持有共享锁*/
    *如果LOCK位被设置了,表示Xmax只是锁住了该元组,没有完成删除*/
    tdefine HEAP_ IS_ LOCKED (HEAP_ _XMAX_ EXCL_ LOCK | \
    HEAP_ XMAX_ SHARED LOCK)
    #define HEAP_ XMIN_ COMMITTED 0x0100 //t_ xmin已提交
    tdefine HEAP_ XMIN_ INVALID 0x0200 //t_ xmin 无效/中断
    #define HEAP_ XMAX_ COMMITTED 0x0400 /* t_ xmax已提交*/
    #define HEAP_ XMAX_ INVALID 0x0800 /* t_ xmax无效/中断*/
    #define HEAP_ XMAX_ IS_ MULTI 0x1000 /*组合事务*/
    tdefine HEAP_ UPDATED 0x2000 /*更断后的新元组*/
    

    MVCC的基本原理如图所示,有两个并发执行的事务T1、T2, T1将元组C更新为C',但T1没有提交,此时假如事务T2要对该元组进行查询,它会通过C和C'中的头信息中的Xmin和Xmax及tjinfomask 来判断出C为其有效版本,而C'为无效版本。

    MVCC与快照

    快照( SnapShot)记录了数据库当前某个时刻的活跃事务列表。通过快照,可以确定某个元组
    的版本对于当前快照是否可见。

    typedef struct SnapshotData
    {
    SnapshotSatisfiesFunc satisfies;//函数指针
    TransactionId xmin;//所有XID< xmin对当前快照可见
    TransactionId xmax; //所有XID>= xmax对当前快照可见
    uint32 xcnt;//当前活跃事务的长度
    TransactionId * xip;、/当前活跃事务的链表
    int32 subxcnt;//当前活跃子事务个数
    TransactionId *subxip;//当前活跃子事务的链表
    CommandId curcid;//当前命令的序号
    uint32 active_ count;//在活跃快照链表里的引用计数
    uint32 regd_ count;//在已注册的快照链表里的引用计数
    bool copied;//是否为共享内存中的全局快照
    } SnapshotData; 
    

    SnapshotData的结构对于事务的可见性判断提供了统一操作接口,其中satisfies 函数指针指向
    前面介绍的MVCC相关判断函数,通过该接口可以判断指定的事务ID对于当前快照是否可见。
    在PostgreSQL系统中,默认有7种形式的快照,分别是:
    SnapshotData SnapshotNowData - {HeapTupleSatisfiesNow};
    SnapshotData SnapshotSel fData = {HeapTupleSatisfiesSelfl;
    SnapshotData SnapshotAnyData = { HeapTupleSatisfiesAny}; 
    SnepshotDato snopshotToastDato - {HeapTupleSatisfiesToast};
    SnapshotData Cur rentSnapshotData = (HeapTupleSat isfiesMVCC);
    SnapshotData SecondarySnapshotData={HeapTupleSatisfiesMVCC};
    #define InitDi rtySnapshot (snapshotdata) \
    ( (snapshotdata). satisfies = HeapTupleSatisfiesDirty)
    其中,不同的快照用于不同形式的可见性判断,需要注意的是如果当前事务的隔离级别是可串行化,那么只存在CurrentSnapshotData, 不存在SecondarySnapshotData, 而在读已提交的隔离级别,这两种快照都存在。

     总结

    本周分析了postgreSQL中多版本并发控制机制,下周要分析一下日志处理相关内容,欢迎批评指正。

    展开全文
  • 与基于加锁的并发控制不同,基于时间戳的并发控制并不试图通过互斥关系来维护可串行化, 而是先提前选择一个串行化顺序,再根据这个顺序来执行事务, 为了建立这个顺序,事务管理器需要对每个事务T进行初始化时分配...

    与基于加锁的并发控制不同,基于时间戳的并发控制并不试图通过互斥关系来维护可串行化, 而是先提前选择一个串行化顺序,再根据这个顺序来执行事务, 为了建立这个顺序,事务管理器需要对每个事务T进行初始化时分配一个时间戳。

    时间戳时一种专门用来唯一标识每个事务并将事务排序的标识符。 唯一性、单调性是时间戳的特性,即每个时间戳都是唯一的,事务管理器生成的事务必须单调递增。

    一种方式是维护一个全局的计数器,但这在分布式系统中是一个比较困难的问题。 还有一种方式是让每个节点根据本地的局部计数器独立分配时间戳。 为了维护唯一性,每个节点会将直接的标识号附加到计数器值的后面, 即时间戳是一个二元组:<局部计数器,节点ID>。节点ID作为附加在较低位, 只有在两个事务被分配了相同的局部计数值时,节点ID才能派上用场。 而每个节点访问自己的时钟,这里的时钟可以是物理时钟、逻辑时钟、混合时钟、全局时钟等等方式, 主要看分布式数据库时钟选取问题,各种时钟都有自己的优劣,需要谨慎选取。
    综合上面的信息可知,可以按照时间戳来对事务的操作进行排序了。 时间戳排序(timestamp ordering,TO)的规则如下: TO规则给定事务Ti和Tj中的两个冲突操作Oik和Ojl,当且仅当ts(Ti)<ts(Tj)时,Oik会在Ojl之前执行。 ts即是对于事务T分配的唯一时间戳。

    使用TO规则的调度会将每一个操作与已经调度过的冲突操作进行比较,如果新的操作属于一个较新的事务, 那么就接收它;否则它就会被拒绝,然后将相应的事务赋予新的时间戳并重新启动。

    这个思路提供了基于时间戳的调度,可以保证生成可串行化的排序,不过,只有当调度程序接收到所有 需要调度的操作,时间戳之间才能比较。如果操作一个接一个传递给调度器,那么就需要以高效的方式检测 每个操作是否按照合法顺序进入。这样,每个数据项x需要被赋予两个时间戳:读时间戳rts(x)、写时间戳wts(x)。 读时间戳表示读取x的所有事务的时间戳的最大值,写时间戳表示写入x的所有事务的时间戳的最大值。 这时,当一个操作需要访问某个数据项时,调度程序就可以根据读时间戳和写时间戳来判断是否有时间戳更大的事务 访问了该数据项。

    从构架上来看,事务管理器负责为每个新的事务分配时间戳,并将这个时间戳附加到事务的数据库操作上。 调度器的职责是记录读和写的时间戳,并进行可串行化排序检查。

    基于时间戳的并发控制也是由传统关系型数据库最早提出的,分布式的TO算法也是由单机TO算法延伸而来。 在《数据库系统概念》一书的15.4章节详细介绍了基于时间戳的协议。

    基本TO

    基本TO是TO规则的直接实现,协调事务管理器为每个事务分配时间戳,为每个数据项选定存储节点, 并且将相关数据库操作发送到这些节点上。

    基本TO的规则是:

    • 事务管理器读或者写数据项均不需要锁
    • 每个数据项x都带有成功读/写最后一个事务的时间戳:rts和wts。
    • 为每个操作检查时间戳:如果事务试图访问“未来”的对象,将重启或取消。

    读取规则:
    • 如果ts(t)<wts(x),则t需要读取的x值已经被覆盖。读取被拒绝,并回滚。 换句话说,这违反了事务t对写x的时间戳排序,需要取消t并重启分配新的ts
    • 否则允许t对x进行读,更新rts(x)=max(rts(x),ts(t)),制作一个x的本地副本,以确保t的可重复读

    写规则:
    • 如果ts(t)<rts(x)或者ts(t)<wts(x),取消或者重启t
    – ts(t)<rts(x)时,事务t产生的x值是先前所需要的值,所以write操作被拒绝,t取消或重启。
    – ts(t)<wts(x)时,t试图写入的x已过时,因此写操作被拒绝,t取消或重启
    • 否则允许t对x进行写并更新wts(x),同时制作x一个本地副本,以确保t的可重复读

    一种更快速的方式是使用thomas写规则(数据库系统概念15.4.3),这里不再展开。

    扩展到分布式,采用分布式中的时间戳方案通过事务管理器将时间戳分配给所有的读和写操作, 每个数据管理器(DM)的调度程序都会跟踪迄今为止为每个数据对象处理的所有读写操作中的最大时间戳。

    read(x,ts)=rts(x),对数据对象x带有时间戳ts的读取请求, write(x,v,ts)=wts(x),向数据对象x写入带有时间戳ts的写入请求,写入值是v。 基本算法同上边的读取和写规则,只是增加了分布式节点间的消息处理,所以在设计上会稍有不同。 首先,某一个操作如果被拒绝,那么整个事务就需要重新分配新的时间戳,然后重启, 这保证了事务的重试的机会,这意味着基本TO不会死锁;当一个已接收的操作被传递到数据处理器时, 调度器必须在该操作完成之前避免向数据处理器再发送另一个虽然冲突,但也被接受的操作。 同时,每个节点的数据处理器上的数据操作如何保证故障转移和一致性也是设计时需要考虑的事情。

    基本TO的算法描述可以查找相关论文。

    保守TO

    基本TO不会让操作进行等待,而是将其重启。这种方法可以有效避免死锁,但也有劣势, 即过多的重启会对性能造成不利的影响。保守TO试图通过减少失误重启的次数来降低系统的负载。 保守TO采用了Lamport的逻辑时钟的做法来进行时钟同步,避免出现单个节点的时钟落后其他节点太多的情况。

    相对于基础TO,保守TO的思路是每个调度器建立一个缓冲区,每个事务的操作都放在缓冲区内, 然后再排序之后执行操作,而不是和基本TO一样即时执行。缓冲区中的操作时不会被拒绝的。 保守特性来源于其执行每个操作的方式,对于基础TO来说,每当接收一个操作就立即执行, 与之相对的是,保守TO会将操作进行延迟,直到可以确认今后调度器不会再接收到时间戳更小的操作。 如果这个条件可以保证,那么调度器就不会拒绝任何一个操作,不过这种方式有可能引入死锁。
    保守TO会减少重启次数,但不能完全避免事务重启。除非采用更保守的TO:仅当队列里至少有一个操作时, 调度器才可以选择一个操作发送给数据处理器。这样做可以保证调度器在接收到每个操作时, 时间戳都能大于或等于当前队列中的操作的时间戳。如果没有事务需要处理,事务管理器以 一定的间隔向其他调度器发送伪信息,以便以后发送的操作都比伪信息时间戳大。 这种极端保守的TO调度程序会让每个节点都顺序执行事务。

    多版本TO

    多版本TO是另一种试图避免重启带来开销的方法。在多版本TO中,更新并不改变数据库; 每个写操作都建立一个数据的新版本。每个版本都标记一个建立它事务的时间戳, 这样多版本TO就可以在存储空间和时间上做一个平衡。这样,数据库处理事务可以按照时间戳 顺序执行。

    多版本TO的处理:

    1. Ri(x)会转化为x的某一版本的读。首先找到x的一个版本Xv,这个版本时间戳比ts(Ti)小, 但比其他早于Ti事务的其他版本的时间戳都大。读取到的值就是这个时间戳的点的值。如图, 这时,Ri可以读取到的值是Xv。

    2. Wi(x)转化成带有Wi(xw),满足ts(xw)=ts(Ti),并且它被发送给数据处理程序时, 当且仅当,没有其他时间戳大于ts(Ti)事务读取了x的一个版本Xr,满足ts(xr)>ts(xw), 换句话说,如果调度程序已经处理了图中的Rj(xr):ts(Ti)<ts(Xr)<ts(Tj)时,Wi(x)被拒绝。
      Ri
      | | ↓ |
      ---------±-------±---------±--------> 时间戳
      | | |
      Xk Xv Xw

                    Wi   Rj
       |        |   ↓    ↓   |
      

    ---------±-------±-----------±--------> 时间戳
    | | xw |
    Xl Xk Xr
    如图,如果Wi被接受的话,事务管理器会建立x的版本xw,这个版本本该被Rj读取,但由于 Rj执行时xw并不存在,如果只能读取到Xk,会出现历史错误。

    总结

    无论是前边介绍的加锁还是基于时间戳的并发控制,都是悲观的,也就是先假设事务之间的冲突比较频繁, 它们不允许两个事务同时对同一个数据项进行冲突的访问,因此,任意一个操作都可以按照这个步骤来执行: 有效性验证,读,计算,写。一般来说,这个顺序对于更新事务以及它的操作来说都是有效的。 而目前来说,一般使用的分布式并发控制,都是乐观并发控制(OPTIMISTIC CONCURRENCY CONTROL OCC)。 虽然本文和加锁的并发控制介绍的并非是时下流行的乐观并发控制,但可以增加对传统关系型数据库的并发控制的了解, 并且这些理论都是后续的基于MVCC的乐观并发控制的基础。

    以上为基于时间的并发控制。「分布式技术专题」是国产数据库hubble团队精心整编,专题会持续更新,欢迎大家保持关注。

    展开全文
  • 下是单版本;上是多版本; 左是悲观;右是乐观

     下是单版本;上是多版本;

    左是悲观;右是乐观

    展开全文
  • MySQL并发控制

    2021-01-19 13:17:07
    MySQL对并发的处理主要应用了两种机制——是“锁”和“多版本控制”。锁锁分为读锁和写锁两种,也称作共享锁和排他锁。因为多个读操作同时进行是不会破坏数据的,所以读锁是共享的,多个读操作可以同时进行,互不...
  • mysql并发控制

    2021-01-19 01:15:28
    mysql并发控制当有多个查询需要同时修改同一个数据,就会产生并发控制的问题。mysql可以在两个层面进行并发控制:服务器层和存储引擎层。mysql通过加锁实现并发控制:⑴锁有两类:读锁:共享锁,即一个读锁不会阻塞...
  • 那就是在调用关联方系统的时候需要限流,因为提供服务方是保险的核心系统,大家应该都懂这种系统支持的并发不会大,为了保护双方系统的可用性,作为调用方我们在调用的时候也会做一个限流控制。 这种场景在工作中很....
  • 主要内容:数据库的并发控制机制,顾名思义,是用来控制数据库的并发操作的机制。控制的目的是为了保证数据完整和数据一致性。何为数据一致性?在数据库的并发操作中,多个事务同时读取同一份数据,要保证多个事务...
  • 务处于何种状态,以此确定是撤销该事务所做出的所有修改操作,还是将修改的操作重新执行。(2)一致性一致性要求事务执行完成后,将...事务的一致性属性要求事务在并发执行的情况下事务的一致性仍然满足。它在逻辑上不...
  • 一、并发控制定义 在数据库中,并发控制是指在多个用户/进程/线程同时对数据库进行操作时,保证事务的一致性和隔离性,同时最大程度地并发。 并发控制的目的是保证一个用户的工作不会对另一个用户的工作产生不合理...
  • 并发控制

    2021-02-20 21:51:38
    dubbo中的并发控制 分为客户端并发控制和服务器端并发控制 <dubbo:service interface="com.haha.people" excutess="10"/> 限制com.haha.people这个接口的所有方法
  • 文章目录并发控制的种类什么是时间戳时间戳并发控制的原理如何判定是否存在冲突基于时间戳的调度规则1. 保留对数据元素操作的最大时间戳2. 判断并处理 读-写,写-读,写-写冲突读-写冲突处理写-读冲突处理写-写冲突...
  • 目录前言一、并发控制概述二、封锁三、封锁协议1.一级封锁协议2.二级封锁协议3.三级封锁协议四、活锁和死锁1.活锁2.死锁五、并发调度的可串行性六、两段锁协议参考 前言 在单片机系统中,事务的并发执行实际上是这些...
  • DB2和 Oracle的并发控制(锁)的比较_Oracle应用_脚本之家 简介:DB2和 Oracle的并发控制(锁)的比较 【相关问答推荐】: 多线程 - java的notify/notifyAll:如何notify指定的线程? java - Spring Security开启...
  • golang并发控制之channel

    2021-09-07 10:16:59
    并发控制之channel 我们考虑一种场景,协程A在执行过程中需要创建子协程A1、A2、A3…An,协程A创建完子协程后就等待子协程退出。针对这种场景,Go提供了三种解决方案。 Channel:使用channel控制子协程 WaitGroup:...
  • 一、快照读与当前读快照读(SnapShot Read) 是一种一致性不加锁的读,是 InnoDB 并发如此之高的核心原因之一。在 READ COMMITTED 事务隔离级别下,一致性不加锁的读是指,总是读取被锁定行的最新一份快照数据,因此...
  • 如何利用 JavaScript 实现并发控制

    千次阅读 2020-12-31 08:10:00
    一、前言  在开发过程中,有时会遇到需要控制任务并发执行数量的需求。  例如一个爬虫程序,可以通过限制其并发任务数量来降低请求频率,从而避免由于请求过于频繁被封禁问题的发生。  接下来,...
  • 文章目录理论MySQL的四种隔离级别事务隔离级别要解决的问题脏读不可重复读幻读实验准备实验过程读未提交(Read Uncommitted)1....四种隔离级别,它们分别在不同的程度上为并发操作的正确调度提供一定的保证,本次
  • 这里需要先对OCC(Optimistic Concurrency Control)指代的概念做一个说明, 从广义上理解,OCC表示一种乐观并发控制的思想,只在事务提交时对事务是否符合串行化进行验证; 而悲观并发控制(Pessimistic ...
  • PostgreSQL 的并发控制 PostgreSQL中定义的两种隔离级别 PostgreSQL 中的三种锁 SpinLock LWLock LWLock的数据结构 总结 概述 上周结束了postgreSQL的事务处理源码分析,这个周分析一下PostgreSQL并发控制的...
  • 2.基于时间戳的并发控制 1.什么是时间戳? 不用锁,能否进行并发控制? 时间戳(TIMESTAMP) 一种基于时间的标志,将某一时刻转换成的一个数值。 时间戳具有唯一性和递增性。 事务的时间戳 事务T启动时,系统将该...
  • mysql的并发控制

    2021-01-18 18:08:46
    1、并发控制MySQL提供两个级别的并发控制:服务器级(the server level)和存储引擎级(the storage engine level)。加锁是实现并发控制的基本方法,MySQL中锁的粒度:(1) 表级锁:MySQL独立于存储引擎提供表锁,例如,...
  • 数据库并发控制

    2021-12-02 16:28:34
    多个事务并发调度的执行结果与它们串行调度的执行结果一致,则这个并发调度被称为“可串行化调度”(Serializable Schedule)。 冲突(Conflict) 如果事务调度中的两个操作交换执行顺序会改变它们所属的事务运行...
  • 今天我们分享mysql中MVCC多版本并发控制原理的详解 一、MVCC定义 1、MVCC简介 MVCC,全称Multi-Version Concurrency Control,即多版本井发控制,MVCC是一种并发控制的方法,一般在数据库管理系统中,实现对数据库...
  • RDS MySQL 8.0 语句级并发控制背景为了应对突发的数据库请求流量,资源消耗过载的语句访问,SQL 访问模型的变化, 并保持 MySQL 实例持续稳定运行,AliSQL 版本设计了基于语句规则的并发控制,Statement Concurrency...
  • MySQL 的多版本并发控制(MVCC) 是干啥的?MySQL 的多版本并发控制(MVCC) 是干啥的?点击蓝色“架构文摘”关注我哟加个“星标”,每天上午 09:25,干货推送!来源:https://segmentfault.com/a/1190000037557620作者...
  • MVCC多版本并发控制原理及实现

    千次阅读 2020-12-30 13:19:57
    什么是 MVCCMVCC (Multiversion Concurrency Control) 中文全程叫多版本并发控制,是现代数据库(包括 MySQL、Oracle、PostgreSQL 等)引擎实现中常用的处理读写冲突的手段,目的在于提高数据库高并发场景下的吞吐性能...
  • ElasticSearch的并发控制问题1.存储系统并发控制的基本解决思路2.ElasticSearch采用的并发控制 1.存储系统并发控制的基本解决思路 采用悲观锁 这种方式,是说我确定一定会有较大或者非常大的可能产生并发,那么我...
  • MySQL的多版本并发控制(MVCC)是什么? 一、什么是多版本并发控制 多版本并发控制技术的英文全称是 Multiversion Concurrency Control,简称 MVCC。 多版本并发控制(MVCC) 是通过保存数据在某个时间点的快照来实现...
  • 一、为什么要进行并发控制 1.1 三种典型的不一致现象 1.2 并发控制的缘由 1.3 并发控制及相应的事务处理技术是DBMS的核心技术 二、什么是事务 2.1 事务的概念 事务:事务是数据库管理系统提供的控制数据操作的一种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 618,743
精华内容 247,497
关键字:

并发控制