ch54 并发控制

事务并发

多用户数据库系统，允许多个用户同时使用的数据库系统

飞机定票数据库系统
银行数据库系统

特点：在同一时刻并发运行的事务数可达数百上千个
事务并发执行带来的问题

会产生多个事务同时存取同一数据的情况
可能会存取和存储不正确的数据，破坏事务隔离性和数据库的一致性

数据库管理系统必须提供并发控制机制，并发控制机制是衡量一个数据库管理系统性能的重要标志之一

隔离性：不受到其他事务的影响，独立完成自己的

一致性：数据库中只包含成功事务提交的结果

多事务执行方式

事务串行执行

事务是用来描述业务的，是业务要求all or nothing。
如果三个事务分别可以all or nothing，那么事件的顺序无关紧要。
但实际上，需要考虑三个事务的顺序不同会不会导致不同的结果。如果结果错误，实际上是对事务本身的定义错误。

例子：T1阶段，对CPU和DB进行操作，分为AB甲乙阶段

A阶段没使用DB，甲乙阶段没使用CPU，B阶段没使用DB

不能实现错峰访问资源。
串行逻辑上提供了多事务执行的正确结果。为其他方式提供了正确答案

交叉并发方式

单一资源：同时只能分配给一个事务（数据资源一般认为是单一资源）

微观上没有并发，宏观上是并发的（在T1还没执行完时，T2,T3也执行了）。

同时并发方式

在关系型数据库中，默认对于一个数据资源的增删改只有一个入口，大多情况是交叉并发方式

并发控制

事务是并发控制的基本单位
并发控制机制的任务

对并发操作进行正确调度
保证事务的隔离性
保证数据库的一致性

不一致性例子

这种情况称为数据库的不一致性，是由并发操作引起的。
在并发操作情况下，对T1、T2两个事务的操作序列的调度是随机的。
若按上面的调度序列执行， T1事务的修改就被丢失。
原因：第4步中T2事务修改A并写回后覆盖了T1事务的修改

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

丢失修改（Lost Update）
不可重复读（Non-repeatable Read）
读“脏”数据（Dirty Read）

记号

R(x):读数据x
W(x):写数据x

丢失修改

丢失修改带来的副作用最大

不可重复读

事务执行期间（事务还没有结束），多次读取数据不一致。显然，如果在B事务中的两次访问数据D期间，事务A对数据D进行了修改，对于事务B而言就形成了不可重复读。
不可重复读是指事务T1读取数据后，事务T2执行更新操作（写入新数据，或者在某个时刻rollback，rollback是一种潜在的更新操作），使T1无法再现前一次读取结果。
不可重复读包括三种情况，后两种不可重复读有时也称为幻影现象（数据的突然出现或突然消失）（Phantom Row) :

事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不同的值
事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按相同条件读取数据时，发现某些记录神秘地消失了。
事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入了一些记录，当T1再次按相同条件读取数据时，发现多了一些记录。

脏读

B事务读取到了A事务修改过尚未提交的数据
读“脏”数据是指：

事务T1修改某一数据，并将其写回磁盘
事务T2读取同一数据后， T1由于某种原因被撤销
这时T1已修改过的数据恢复原值， T2读到的数据就与数据库中的数据不一致
T2读到的数据就为“脏”数据，即不正确的数据

三者区别

丢失修改：事务T1的提交的更新会事务T2覆盖
不可重复读：事务T1在不同时刻对同一数据进行读的结果不同（强调的是同一个事务在整个事务过程中对同一笔数据进行读取，每次读取结果都不同。）-被T2修改了/删除了/增加了
脏读：两个不同的事务T1，T2，T1修改了数据，T2读取了T1修改后的数据，与数据库中的数据（由于T1回滚了）不一致

不可重复读
（针对其他提交前后，读取数据本身的对比）不可重复读取是指同一个事务在整个事务过程中对同一笔数据进行读取，每次读取结果都不同。如果事务1在事务2的更新操作之前读取一次数据，在事务2的更新操作之后再读取同一笔数据一次，两次结果是不同的，所以，Read Uncommitted也无法避免不可重复读取的问题。
幻读
（针对其他提交前后，读取数据条数的对比） 幻读是指同样一笔查询在整个事务过程中多次执行后，查询所得的结果集是不一样的。幻读针对的是多笔记录。在Read Uncommitted隔离级别下，不管事务2的插入操作是否提交，事务1在插入操作之前和之后执行相同的查询，取得的结果集是不同的，所以，Read Uncommitted同样无法避免幻读的问题。

数据不一致性及并发控制

数据不一致性：由于并发操作破坏了事务的隔离性
并发控制就是要用正确的方式调度并发操作，**使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性 **
对数据库的应用有时允许某些不一致性，例如有些统计工作涉及数据量很大，读到一些“脏”数据对统计精度没什么影响，可以降低对一致性的要求以减少系统开销

并发控制的主要技术

封锁(Locking)
时间戳(Timestamp)
乐观控制法
多版本并发控制(MVCC)

ch55 封锁

封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁
加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。
封锁是实现并发控制的一个非常重要的技术
一个事务对某个数据对象加锁后究竟拥有什么样的控制由封锁的类型决定。
基本封锁类型
- 排它锁（Exclusive Locks，简记为X锁）
- 共享锁（Share Locks，简记为S锁）

排他锁与共享锁

排他锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁为止。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。
共享锁又称为读锁。若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁为止。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。

【注意】

之所以看起来它们能够控制对数据的读取和修改，这需要依赖每个事务在读取和修改数据之前必须要遵守某种约定，这就是：如果要求在某些条件下，某事务需要加某种锁才能对数据进行操作，那么，所有其它事务在遇到同样情况下，也强制必须先加锁才能对数据进行操作，如果加锁加失败，则该事务需要等待。而锁之间是有排斥法则的，所以可以通过这个法则来间接实现对数据读取和修改上的限制。

排他锁对应的要求条件往往是在对数据的修改之前，共享锁对应的则是读取。也就是说，如果对事务启用排他锁，往往意味着，任何事务在修改数据之前都要先加排他锁（但是并不一定代表读取数据时也要先加锁）。如果对事务启用共享锁，往往意味着任何事务在读取数据之前都要先加共享锁。不过，可以自行规定加锁时机。

相容矩阵

封锁协议

在运用X锁和S锁对数据对象加锁时，需要约定一些规则，这些规则为封锁协议（Locking Protocol）。

何时申请X锁或S锁
持锁时间
何时释放

对封锁方式规定不同的规则，就形成了各种不同的封锁协议，它们分别在不同的程度上为并发操作的正确调度提供一定的保证。

一级封锁协议

一级封锁协议
事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。

正常结束（COMMIT）
非正常结束（ROLLBACK）

一级封锁协议可防止丢失修改，并保证事务T是可恢复的。
在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。

可以防止丢失修改：因为X锁保证了其他事务不能同时对该数据进行修改
不能保证不可重复读：因为一级封锁协议只是规定了写数据之前要加X锁，并不代表读数据之前也要加锁。所以，当T1读取数据的时候，T2事务是可以对同一数据进行修改，也就造成了不可重复读的现象。
不能保证不可读“脏”数据：同理，T1读取事务的时候，并不能阻止T2的修改和回滚操作，也就造成了T1读取的数据和数据库不一致的情况

并没有对读操作进行限制，不在乎读到的数据是否正确

二级封锁协议

二级封锁协议是指,在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。
二级封锁协议可以防止丢失修改和读“脏”数据。

可以防止丢失修改：因为是建立在一级封锁协议的基础上（写之前要加X锁）
可以防止读脏数据：因为在读取的时候加入了S锁，也就保证了其他事务不对该数据进行修改，也就不会产生由于修改回滚导致取出的数据和数据库不一致（或者说读取到未提交的修改的数据的）的现象
不能保证可重复读：因为读完数据后即可释放S锁（无需等待事务结束），所以释放完S锁后，其他事务可以对该数据进行修改，也就会造成不可重复读的现象。因为事务并没有结束，所以会出现同一事务的不同时刻，会读取到不同的结果

在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。
x锁是既可以读，也可以写的
添加S锁，实际上是判断读取的时候是否有数据在修改。

有X锁的时候，不能加入S锁-修改的时候不能读取
有S锁的时候，不能再加入X锁-读取的时候不能再修改。
有S锁的时候，可以再加入S锁-可以多个事务同时读取数据

三级封锁协议

三级封锁协议是指,在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁,直到事务结束才释放。与二级最大的区别是释放时间
三级封锁协议可防止丢失修改、读脏数据和不可重复读

可以解决不可重复读问题：因为事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放，所以在事务执行期间，所读取到的数据不可能被修改了

如果是二级

T2的XlockB则可以获得，可以对B进行修改
加锁最大的开销：加锁后其他操作难以有有效的方式进行并发，不能够见缝插针地利用数据库资源

封锁协议小结

活锁

随机发生

如果不采用FCFS的策略时

死锁

死锁的预防

产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。
预防死锁的发生就是要破坏产生死锁的条件

一次封锁法

一次封锁法，要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行
存在的问题

降低系统并发度
难于事先精确确定封锁对象
- 数据库中数据是不断变化的，原来不要求封锁的数据，在执行过程中可能会变成封锁对象，所以很难事先精确地确定每个事务所要封锁的数据对象。
- 解决方法：将事务在执行过程中可能要封锁的数据对象全部加锁，这就进一步降低了并发度。

顺序封锁法

顺序封锁法，预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。
存在的问题

维护成本
- 数据库系统中封锁的数据对象极多，并且随数据的插入、删除等操作而不断地变化，要维护这样的资源的封锁顺序非常困难，成本很高。
难以实现
- 事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的顺序去施加封锁

死锁的诊断

数据库管理系统在解决死锁的问题上更普遍采用的是诊断并解除死锁的方法
在操作系统中广为采用的预防死锁的策略并不太适合数据库的特点

超时法

超时法，如果一个事务的等待时间超过了规定的时限，就认为发生了死锁
优点：实现简单
缺点：有可能误判死锁时限若设置得太长，死锁发生后不能及时发现

等待图法

等待图法，并发控制子系统周期性地（比如每隔数秒）生成事务等待图，检测事务。如果发现图中存在回路，则表示系统中出现了死锁。

事务等待图是一个有向图G=(T，U)
T为结点的集合，每个结点表示正运行的事务
U为边的集合，每条边表示事务等待的情况
若T1等待T2 ，则T1 ， T2之间划一条有向边，从T1指向T2

死锁的解除

解除死锁

选择一个处理死锁代价最小的事务，将其撤消
释放此事务持有的所有的锁，使其它事务能继续运行下去

ch56 事务调度

并发调度的可串行性

数据库管理系统对并发事务不同的调度可能会产生不同的结果
串行调度是正确的
**执行结果等价于串行调度的调度也是正确的，称为可串行化调度 **

可串行化调度

可串行化(Serializable)调度
- 多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同
可串行性(Serializability)
- 是并发事务正确调度的准则
- 一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度

可串行化调度的例子

串行调度-正确的调度

不可串行化调度-错误的调度

可串行化调度-正确的调度

冲突可串行化

概念

冲突可串行化

一个比可串行化更严格的条件
商用系统中的调度器采用

冲突操作：是指不同的事务对同一数据的读写操作和写写操作：

Ri(x)与Wj(x) /事务Ti读x，Tj写x，其中i≠j/
Wi(x)与Wj(x) /事务Ti写x，Tj写x，其中i≠j/

其他操作是不冲突操作
不能交换（Swap）的动作:

同一事务的两个操作
不同事务的冲突操作
一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’，如果Sc’是串行的，称调度Sc是冲突可串行化的调度
若一个调度是冲突可串行化，则一定是可串行化的调度
可用这种方法判断一个调度是否是冲突可串行化的

冲突可串行化调度

两段锁协议

数据库管理系统普遍采用两段锁协议的方法实现并发调度的可串行性，从而保证调度的正确性
两段锁协议，指所有事务必须分两个阶段对数据项加锁和解锁

在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
在释放一个封锁之后，事务不再申请和获得任何其他封锁

“两段”锁的含义，**事务分为两个阶段 **

第一阶段是获得封锁，也称为扩展阶段
- 事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
第二阶段是释放封锁，也称为收缩阶段
- 事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁

事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。
若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的
若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议

两段锁协议与一次封锁法

两段锁协议与防止死锁的一次封锁法

一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议
但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁

ch57 封锁粒度

**封锁对象的大小称为封锁粒度(Granularity) **
封锁的对象：逻辑单元，物理单元
例：在关系数据库中，封锁对象：

逻辑单元: 属性值、属性值的集合、元组、关系、索引项、整个索引、整个数据库等
物理单元：页（数据页或索引页）、物理记录等

选择封锁粒度原则

封锁粒度与系统的并发度和并发控制的开销密切相关。

封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小
封锁的粒度越小，并发度较高，但系统开销也就越大

例

若封锁粒度是数据页，事务T1需要修改元组L1，则T1必须对包含L1的整个数据页A加锁。如果T1对A加锁后事务T2要修改A中元组L2，则T2被迫等待，直到T1释放A。
如果封锁粒度是元组，则T1和T2可以同时对L1和L2加锁，不需要互相等待，提高了系统的并行度。
又如，事务T需要读取整个表，若封锁粒度是元组，T必须对表中的每一个元组加锁，开销极大

多粒度封锁

多粒度封锁(Multiple Granularity Locking)
在一个系统中同时支持多种封锁粒度供不同的事务
选择选择封锁粒度，同时考虑封锁开销和并发度两个因素, 适当选择封锁粒度

需要处理多个关系的大量元组的用户事务：以数据库为封锁单位
需要处理大量元组的用户事务：以关系为封锁单元
只处理少量元组的用户事务：以元组为封锁单位

多粒度树

多粒度封锁协议

允许多粒度树中的每个结点被独立地加锁
对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
在多粒度封锁中一个数据对象可能以两种方式封锁：
- 显式封锁: 直接加到数据对象上的封锁
- 隐式封锁:是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁
显式封锁和隐式封锁的效果是一样的

显式封锁和隐式封锁

系统检查封锁冲突时

要检查显式封锁
还要检查隐式封锁

例如，事务T要对关系R1加X锁

系统必须搜索其上级结点数据库、关系R1
还要搜索R1的下级结点，即R1中的每一个元组
如果其中某一个数据对象已经加了不相容锁，则T必须等待

对某个数据对象加锁，系统要检查

该数据对象有无显式封锁与之冲突
所有上级结点
- 检查本事务的显式封锁是否与该数据对象上的隐式封锁冲突：(由上级结点已加的封锁造成的）
所有下级结点
- 看本次事务添加的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突

即：

与自己已经有的显式封锁是否冲突
与自己已经有的隐式封锁是否冲突
下级结点的封锁与自己要给下级结点带来的隐式封锁是否冲突

意向锁

引进意向锁（intention lock）目的：提高对某个数据对象加锁时系统的检查效率
有了意向锁，系统就无需逐个检查下一结点的显式封锁
如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁
对任一结点加基本锁，必须先对它的上层结点加意向锁
例如，对任一元组加锁时，必须先对它所在的数据库和关系加意向锁

意向共享锁-IS锁

意向共享锁(Intent Share Lock，简称IS锁)

如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。
例如：事务T1要对R1中某个元组加S锁，则要首先对关系R1和数据库加IS锁

意向排他锁-IX锁

意向排它锁(Intent Exclusive Lock，简称IX锁)

如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。
例如：事务T1要对R1中某个元组加X锁，则要首先对关系R1和数据库加IX锁

共享意向排他锁-SIX锁

共享意向排它锁(Share Intent Exclusive Lock，简称SIX锁)

如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX = S + IX。
例：对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）。

意向锁的相容矩阵

T1加S锁,T2只能加S和IS锁。
X锁排他，pass。
**因为加S所后，对应数据的子节点都隐式的加了S锁，所以加IX锁表示其子节点拟加X锁(确实逻辑上可能不会对子节点加锁，但是只要有这个可能性就要保证正确性)**，X排他，pass。SIX锁同理。
T1加X锁，T2只能干等着。因为X锁排他，优先级最高

T1加IS锁，T2不能加X锁。因为T1有对其子节点加S锁的可能而T2扼杀了这个可能性。
至于T2为什么能加IX锁是因为I锁只是意向锁，所以是可行的，若事务有非意向锁，根据相容矩阵再次判定。SIX锁综上同理。

T1加IX锁，T2不能加S，X，SIX锁的原因不再赘述。(不能加SIX锁的原因，可参考不能加S锁)
T1加SIX锁，T2只能加IS锁。

不能加S，X，IX，SIX锁的原因分别是：
T2加S，T1无法完成SIX锁的IX部分
T2加X，T1首先就无法完成S锁，更别说SIX锁

T2加IX，表示T2意向修改对象子节点，而T1要读对象，若T2修改其子节点便产生并发错误。故pass

T2加SIX，综合上面S和IX的情况。pass

（S锁就是已经加上去了，IS锁就是有可能不加S锁）

锁的强度

具有意向锁的多粒度封锁方法

申请封锁时应该按自上而下的次序进行
释放封锁时则应该按自下而上的次序进行
具有意向锁的多粒度封锁方法

提高了系统的并发度
减少了加锁和解锁的开销
在实际的数据库管理系统产品中得到广泛应用

例如：事务T1要对关系R1加S锁

要首先对数据库加IS锁
检查数据库和R1是否已加了不相容的锁(X或IX)
不再需要搜索和检查R1中的元组是否加了不相容的锁(X锁)