数据库并发控制之并发调度

落日映苍穹つ 2021-09-27 15:20 880阅读 0赞

### 一、并发调度的可串行性 ###

##### 1、可串行化调度 #####

**定义 ：** 多个事务的并发执行是正确的，当且仅当其结果与按某一次串行地执行这些事务时的结果相同，称这种调度策略为可串行化调度。  
可串行性是并发事务正确调度的准则。按这个准则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。

##### 2、冲突可串行化调度 #####

并发事务的不听调度：  
![并发事务的不同调度][70]  
**冲突操作：** 不同的事务对同一数据的读写操作和写写操作。  
Ri（x）与Wj（x） -->事务Ti读x，Tj写x，其中i≠j  
Wi（x）与Wj（x） -->事务Ti读x，Tj写x，其中i≠j  
其他操作是不冲突操作。  
不同事务的冲突操作和同一事务的两个操作是不能交换的。对于Ri（x）与Wj（x），若改变二者的次序，则事务Ti看到的数据库状态就发生了改变，自然会影响到事务Ti后面的行为。对于Wi（x）与Wj（x），改变二者的次序也会影响数据库的状态，x的值由等于Tj的结果变成了Ti的结果。  
一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc‘，如果Sc’是串行的，称调度Sc为冲突可串行化的调度。若一个调度是冲突可串行化，则一定是可串行化的调度。因此可以用这种方法来判断一个调度是否是冲突可串行化的。

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

### 二、两段锁协议 ###

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

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

所谓“两段”的含义是，事务分为两个阶段：  
第一阶段是获得封锁，也称为扩展阶段，在这个阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁；  
第二阶段是释放封锁，也称为收缩阶段，在这个阶段，事务可以是否任何数据项上的任何类型的锁，但是不能再申请任何锁。

> 若并发执行的所有事务均遵守两端锁协议，则对这些事务的任何并发调度策略都是可串行化的。

示例：遵守两段锁协议的可串行化调度  
![遵守两段锁协议的可串行化][70 1]  
事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的；但是，若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议。  
**备注：** 两段锁协议和防止死锁的一次封锁法的异同：

1.  一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。
2.  两段锁协议：并不要求事务必须一次将所有要使用的数据全部加锁，印象遵守两段锁协议的事务可能发生死锁。
3.  一次封锁法遵守两段锁协议。

### 三、封锁的粒度 ###

封锁对象的大小称为封锁粒度。封锁对象可以是逻辑单元，也可以是物理单元。以关系数据库为例，封锁对象可以是这样一些逻辑单元：属性值、属性值的集合、元组、关系、索引项、整个索引直至整个数据库；也可以是这样一些物理单元：页（数据页或索引页）、物理记录等。  
封锁粒度与系统的并发度和并发控制的开销密切相关。

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

###### 1、多粒度封锁 ######

在一个系统中同时支持多种封锁粒度供不同的事务选择，这种封锁方法称为多粒度封锁。  
多粒度树示例：三级粒度树  
![三级粒度树][70 2]  
其中，根节点就是整个数据库，表示最大的数据粒度。叶结点表示最小的数据粒度。数据库的子结点为关系，关系的子结点为元组。  
多粒度封锁协议允许多粒度树多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点页被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以两钟方式封锁，显式封锁和隐式封锁。

1.  显式封锁：应事务的要求直接加到数据对象上的锁；
2.  隐式封锁：该数据对象没有被独立加锁，是由于其上级节点加锁而使该数据对象加上了锁。  
    多粒度封锁方法中，显式封锁和隐式封锁的效果是一样的，因此系统检查封锁冲突时不仅要检查显式封锁还要检查隐式封锁。  
    一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；再检查其所有上级结点，看本事务的显示封锁是否与该数据对象上的隐式封锁（即由于上级结点已加的封锁造成的）冲突；还要检查其所有下级结点，看它们的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突。

##### 2、意向锁 #####

为了解决多粒度封锁的检查方法效率低的问题，数据库管理系统无须逐个检查下一级结点的显式封锁，引进了一种新型锁–意向锁。  
**含义：** 如果对一个结点加意向锁，则说明该结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。

1.  意向共享锁（IS锁）  
    如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。
2.  意向排他锁（IX锁）  
    如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。
3.  共享意向排他锁（SIX锁）  
    如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S+IX。

> 所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的，反之则不然。

在具有意向锁的多粒度封锁方法中，任意事务T要对一个数据加锁，必须先对它的上层结点加意向锁。申请封锁时应该按自上而下的次序进行，释放封锁时应该按自下而上的次序进行。  
加上意向锁后锁的相容矩阵与偏序关系图：  
![加上意向锁后锁的相容矩阵与偏序关系][70 3]  
**具有意向锁的多粒度封锁方法提高了系统的并发度，减少了加锁和解锁的开销。**

> 选择封锁粒度时应该同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以追求得最优的结果。一般来说，需要处理某个关系的大量元组的事务可以以关系为封锁粒度；需要处理多个关系的大量元组的事务可以以数据库为封锁粒度；而对于一个处理少量元组的用户事务，以元组为封锁粒度就比较合适了。

### 四、其他并发控制机制 ###

并发控制的方法除了封锁技术外还有时间戳方法、乐观控制法和多版本并发控制等。

##### 1、多版本并发控制 #####

> 多版本并发控制（MVCC）是指在数据库中通过维护数据对象的多个版本信息来实现高效并发控制的一种策略。

版本是指数据库中数据对象的一个快照，记录了数据对象某个时刻的状态。数据库系统的数据对象保留多个版本，以提高系统的并发操作程度。

在多版本机制中，每个write(Q)操作都创建Q的一个新版本，这样一个数据对象就有一个版本序列Q1,Q2,…,Qm与之相关联。每一个版本Qk拥有版本的值、创建Qk的事务的时间戳W-timestamp(Qk)和成功读取Qk的事务的最大时间戳R-timestamp(Qk)。其中，W-timestamp(Qk)表示数据项Q上成功执行write(Q)操作的所有事务中的最大时间戳，R-timestamp(Qk)表示在数据项上Q上成功执行read(Q)操作的所有事务中的最大时间戳。  
封锁方法与MVCC示意图：  
![封锁方法与MVCC示意图][MVCC]  
用TS(T)表示事务T的时间戳，TS(Ti)<TS(Tj)表示事务Ti在事务Tj之前开始执行，多版本协议描述如下：  
假设版本Qk具有小于或等于TS(T)的最大时间错。若事务T发出read(Q)，则返回版本Qk的内容。若事务T发出write(Q)，则：

1.  当TS(T)<R-timestamp(Qk)时，回滚T；
2.  当TS(T)=W-timestamp(Qk)时，覆盖Qk的内容。  
    否则，创建Q的新版本。  
    若一个数据对象的两个版本Qk和Ql，其中W-timestamp都小于系统中最老的事务的时间戳，那么这两个版本中较旧的那个版本将不再被用到，因而可以从系统中删除。

> 多版本并发控制利用物理存储上的多版本来维护数据的一致性。这就意味着当检索数据库时，每个事务都看到一个数据的一段时间前的快照，而不管正在处理的数据当前的状态。多版本并发控制和封锁机制相比，主要的好处是消除了数据库中数据对象读和写操作的冲突，有效地提高了系统的性能。

##### 2、改进的多版本并发控制 #####

多版本并方控制方法有利于提高事务的并发度，但也会产生大量的无效版本，而且在事务结束时刻，其所影响的元组的有效性不能马上确定。因此多版本协议可以进一步改进。区分事务的类型为只读事务和更新事务。对于只读事务，发生冲突的可能性很小，可以采用多版本时间戳。对于更新事务，采用较保守的两阶段封锁（2PL）协议。这样的混合协议称为MV2PL。  
除了传统的读锁（共享锁）和写锁（排他锁）外，引进一个新的封锁类型，称为验证锁（C锁）。封锁的相容矩阵如下：  
![验证锁的 相容矩阵][70 4]  
在这个相容矩阵中，读锁和写锁变得是相容的了。这样当某个事物写数据对象的时候，允许其他事务读数据（写操作生成一个新版本，读操作就是读旧版本）。一旦写事务要提交的时候，必须首先获得在那些加了锁的数据对象上的验证锁。由于验证锁和读锁是不相容的，所以为了得到验证锁，写事务不得不延迟它的提交，直到所有被它加上写锁的数据对象都被所有那些正在读它们的事务释放。一旦写事务获得验证锁，系统就可以丢弃数据对象的旧值，使用新版本，然后释放验证锁，提交事务。  
这样，系统最多只要维护数据对象的两个版本。多个读操作可以和一个写操作并发地执行。这种情况是传统的2PL所不允许的，提高了读写事务之间的并发度。

##### 3、时间戳方法 #####

给每一个事务盖上一个时标，即事务开始执行的时间。每个事务具有唯一的时间戳，并按照这个时间戳来解决事务的冲突操作。如果方式冲突操作，就回滚具有较早时间戳的事务，以保证其他事务的正常执行，被回滚的事务被赋予新的时间戳并从头开始执行。

##### 4、乐观控制法 #####

乐观控制法又称为验证方法。  
乐观控制法认为事务执行时很少发生冲突，因此不对事务进行特殊的管制，而是让它自由执行，事务提交前再进行正确性检查。如果检查后发现该事务执行中出现过冲突并影响了可串行性，则拒绝提交并回滚该事务。

> M2PL把封锁机制和时间戳方法相结合，维护一个数据的多个版本，即对于关系表上的每一个写操作产生r的一个新版本，同时会保存前一次修改的数据版本。M2PL和封锁机制相比，主要的好处是在多版本并发控制中对读数据的锁要求与写数据的锁要求不冲突，所以读不会阻塞写，而写也从不阻塞读，从而使读写操作没有冲突，有效地提高了系统的并发性。

[70]: /images/20210923/2a28ecebaca8474da8f3269247c60119.png
[70 1]: /images/20210923/2d99efd6e45d44a2b3d85c95a159abbe.png
[70 2]: /images/20210923/cd19ba0c5ab44de9b3ce5501018bfde7.png
[70 3]: /images/20210923/7efcade94cad47f5acea2e463e97ec57.png
[MVCC]: /images/20210923/5a540226adc547eda05ad527838730f7.png
[70 4]: /images/20210923/790c709716b348bea234f4e3b966a766.png