事务隔离性实现

在多个事务并发执行时，事务的隔离性不一定能保持。为保持事务的隔离性，系统必须对并发事务之间的相互协作加以控制；这种控制是通过一种称为并发控制来实现。下面将介绍多种机制，但是没有哪种机制明显是最好的。每种机制都有优势。在实践中，最常用的是俩阶段封锁和快照隔离。本篇文章的主要内容就是分别介绍下面几种并发控制机制。

基于封锁的协议
基于时间戳的协议
多版本机制

基本概念

这里先补充几个概念，后面会多次用到。

read操作表示从磁盘读数据到内存，write操作表示从将数据写回磁盘。不考虑缓存这些概念，就是简单的读数据到内存，写数据到硬盘。文章后面说道这俩个操作都是这个意思。

可恢复调度

这里首先举一个例子,有俩个事务，T6和T7，调度情况如下

T6	T7
read(A) write(A)	-
-	read(A) commit
read(B)
看上面俩个事务，T6中我们是截取了一个事务中的一段操作，所以没有commit和abort。现在我们来分析上面调度。T7执行read(A)指令后立即提交。因此T7提交时T6仍处于活跃状态。现在假定T6在提交前发生故障。T7已读取了由T6写入的数据项A的值。因此，我们说T7依赖于T6。因此我们必须终止T7以保证事务的原子性。但是T7已提交，不能再中止。这样就出现了T6发生故障后不能正确恢复的情形。
因此这个调度是不可恢复调度的一个例子。一个可恢复调度应该满足：对于每个事务T和J，如果J读取了事务T所写的数据项，则T应先于提交。

无级联调度

下面是一个级联调度例子

T8	T9	T10
read(A) read(B) write()A	-	-
-	read(A) write(A)
-	-	read(A)
abort
上面就是一个级联调度，由于T8的回滚，导致后面T9和T10俩个事务的回滚。
几连调度导致撤销大量工作，使我们不希望发生的。我们希望对调度加以限制，避免级联回滚发生。
无级联调度：对于事务T和J，如果J读取了先前有T所写的数据项，则T必须在J读这个数据项前进行提交。无级联调度一定是可恢复调度。

基于封锁的协议

确保隔离性的方法之一就是对数据项以互斥的方式进行访问，实现此需求最常用的方法是只允许事务访问当前事务持有锁的数据项。
锁大致分为俩种：

共享锁：事务T获取了数据项Q的共享锁(记为S)则T可读但不能写Q
互斥锁：事务获取了数据项Q的互斥锁(记为X)则T可写可读Q。
每个事务根据自己对数据项Q进行的操作申请合适的锁。在并发控制中，锁的申请是由并发控制管理器管理的，事务只有在并发控制管理器授予锁后才能继续事务的操作。而上面俩种锁又会存在相容性情况：如果事务A在Q数据项上加锁，事务B可以在数据向Q上立即获得锁，则说这个锁是相容的否则就是不相容。共享和互斥锁的相容性矩阵如下：

-	s	x
s	yes	no
x	no	no
但是事务对于自己需要操作的数据项进行上锁不一定能够保证数据的一致性。如果在数据使用前进行上锁，使用后立即释放锁，也有可能导致数据的不一致性。但是如果在事务开始前申请所有数据项的锁，事务结束或者中止时释放所有的锁，又会导致事务的并发性比较低。
基于上述情况，需要求数据库系统中的事务都遵从称为封锁协议的一组规则，这组规则规定事务何时对数据项进行加锁、解锁。下面将介绍一个使用比较广泛的封锁协议。

俩阶段封锁协议

此协议要求每个事务分来个阶段提出加锁和解锁申请：

增长阶段：事务可以申请锁，但不能释放锁。
缩减阶段：事务可以释放锁，但不能申请锁。

最初事务处于增长阶段，事务根据需要获取锁。一旦事务释放了锁，他将进入缩减阶段，并且不能再发出加锁请求。
俩阶段锁的缺点：

俩阶段锁可能会发生死锁。
可能发生级联回滚。但是级联回滚可以通过俩阶段锁修改为严格俩阶段封锁协议加以避免。这个协议出了要求是俩阶段之外，还要求事务持有所有互斥锁必须在事务提交后方可释放。这就保证事务修改的数据项在没有提交前辈其他事务读取到。

此外俩阶段封锁协议还有一个变体就是强俩阶段封锁协议，要求事务提交之前不得释放任何锁。在整个阶段可以允许锁转换，有俩种转换：将共享锁转换为互斥锁称为锁升级，将互斥锁转换为共享锁称为锁降级。锁升级只能发生在增长阶段，锁降级只能发生在缩减阶段。

严格俩阶段封锁与强俩阶段封锁（含锁转换）在商用数据库系统中广发使用。
下面介绍一种简单却广泛使用的机制，它基于来自事务的读、写请求，自动地为事务产生适当的加锁、解锁指令：

当事务T进行读操作时系统就产生一条申请共享锁的指令，然后执行read操作
当事务T执行写操作时，系统首先检查事务T是否已经持有该数据项的共享锁，如果持有则发出锁升级执行，然后进行写操作。否则系统直接发出申请互斥锁指令，接着执行写操作。
当一个事务提交或终止后，该事物持有的所有锁操作都被释放。

这里补充一点：在锁授予时，如果不加以控制，会导致某个事务产生饿死现象，使得事务可能永远不能取得进展。我们可以通过如下方式授权事务加锁请求来避免事务饿死：事务T申请对数据项Q加M型锁时，并发控制管理器授权锁的条件是：

不存在在数据项Q上持有与M型锁冲突的锁的其他事务
不存在等待对数据项Q加锁且先于T申请加锁的的事务。

死锁处理

前面说过，封锁协议会产生死锁。那么如何处理死锁呢。首先看看死锁的定义：如果存在一组事务集，该集合中的每个事务都在等待集合中另一个事务，因此产生了一个环，我们就说系统处于死锁状态。
处理死锁主要由俩种主要方法：

死锁预防保证系统永远不会进入死锁状态
允许系统进入死锁状态，然后试着用死锁检测与死锁恢复机制进行恢复。

上面俩种方法都有可能引起事务回滚。相对来说，如果系统产生死锁的概率相对较高，则通常使用死锁预防机制，否则使用死锁检测与恢复机制会更有效。死锁检测与恢复机制带来的各种开销，不仅包括在运行时需要维护必要信息及执行检测算法的代价，还要包括从死锁中恢复的损失。

死锁预防

预防死锁有俩种方法。一种是通过对加锁请求进行排序或要求同时获得所有的锁来保证不会发生循环等待。另一种方法比较接近死锁恢复，每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。

第一种方法下最简单的机制要求每个事务在开始之前封锁他的所有数据项。此外，要么一次全部封锁要么全部不封锁。这个协议主要由俩个缺点：
1. 在事务开始前通常很难预测哪些数据项需要封锁
2. 数据项使用率可能很低，因为许多数据可能封锁很长时间却用不到。
  或者对所有的数据项加一个次序，同时要求事务只能按次序规定的顺序封锁数据项，但是这个很难实现如何确定数据项的数据。因此不常用。
第二种方法就是抢占与回滚。抢占机制就是，如果满足某种条件，事务可以抢占其他事务的数据项来保持继续的运行。
抢占机制会首先为每个事务提供一个唯一的时间戳，系统通过时间戳来决定事务应该等待还是回滚。如果事务回滚，则事务保持原来的时间戳。基于时间戳主要由以下来钟不同的死锁预防机制
1. 基于非抢占机制。当事务T1申请的数据项当前被T2持有，仅当T1事务开始的时间早于T2，允许T1进行等待，否则T1进行回滚。
2. 基于抢占机制。当事务T1申请的数据项当前被T2持有，仅当T1事务开始的时间早于T2，允许T2进行等待，否则T2回滚。

上述俩种机制都会面临的主要问题是可能发生不必要的回滚。
还有一种简单的机制，锁超时，就是如果申请事务至多等待一段给定的时间，如果获取不到锁，则进行回滚。但是确定时间的长短比较难。时间短了，事务的回滚比较多，造成不要的浪费。如果已经发生死锁，等待时间设置的比较久，从而造成事务不必要的等待。因此，基于超时的机制应用有限。

死锁检测与恢复

如果系统没有采用保证不产生死锁的协议，呢么系统必须采用检测与恢复机制。检测系统状态的算法周期性地进行激活，判断有无死锁发生，如果有则采用恢复算法，让系统从死锁中恢复。实现这一点，系统必须：

维护当前数据项分配给事务的有关信息，以及任何尚未解决的数据项的请求信息。
提供一个使用这些信息判断系统是否进入死锁状态的算法。
当检测算法判断存在死锁时，从死锁中恢复。

死锁检测

可以采用称为等待图的有向图来精确描述系统中事务的关系。其中顶点集是有事务来描述，边是由事务之间的关系来描述。当事务T申请的数据项被J持有，那么就有一条从T到J的边。当数据项被申请到后，就把这条边删除。
当且仅当数图中包含环时，系统中存在死锁，该环中的每个事务处于死锁状态。要检测死锁必须维护一个等待图，并周期的激活一个等待图搜索算法。
何时激活死锁检测算法，取决于俩个因素

死锁发生频度怎么样
有多少事务将受到死锁的影响

死锁恢复

当检测到系统中存在死锁时，系统必须从死锁中欧冠恢复。解除死锁最通常的做法是回滚一个或多个事务。采取的动作主要由三个

选择牺牲者：需要决定回滚哪个事务来打破死锁，这个事务的代价又必须很小。但是代价很小的定义很多，回滚的事务比较少，回滚事务的等待时间最小等等一些列的回滚代价。
回滚：一旦决定回滚事务，就要判断事务回滚多远能够解除死锁。最简单的做法是彻底回滚。但是比较浪费。另一种是部分回滚，就必须在维护额外的信息，来确定回滚哪些数据项上的操作就能就出死锁。
饿死：在系统中，有可能一个事务总被选成牺牲者，这样这个事务总不能完成事务，这样就会产生饿死。因此在选择回滚事务的时候，保证一个事务被选择牺牲的次数有限。

多粒度

在并发控制中，如果我们以数据项为单位进行加锁，则必须要对事务中所有使用的数据项一个个的加锁，这中操作很浪费时间。如果我们能够将多个数据项作为一个同步单元，这样我们加锁的操作就会大大的减少。

因此出现了一种允许系统定义多级粒度的机制。这是通过允许各种大小的数据项并定义数据粒度的层次结构，其中小的数据项嵌套在大粒度数据项中实现，这种层次化结构可以图形化的表示成树。如下图，

上图中，最高层是代表整个数据库，下面俩个节点代表数据库中的表，然后是表中的数据。
现在如果希望对其中的叶子节点加锁，则需要从根节点到到叶子节点进行遍历，看路径上是否有与自己加的锁不相容的锁，如果有则加锁必须等待。但是这种操作会使得我们需要遍历树来进行确认，如果我们有一种方法，能够从根节点或者需要加锁的叶子节点的其中一个父节点就能判断加锁是否会有冲突，这可以大大节约时间。

因此，引入了一种新的类型的锁，意向锁。这时在给某个节点加锁时，就提出了一个新的要求，必须先给他的父节点加上某中类型的意向锁，才能给需要加锁的节点加上与意向锁类型相容的共享锁或者互斥锁。则通过父节点就能够判断出是否会有冲突。
意向锁的类型如下

共享型意向锁（IS）：如果父节点加上这种类型的锁，其子节点只能加共享锁。
互斥型意向锁（IX）：如果父节点加上这种类型的锁，其子节点可以是共享锁或者互斥锁。
这俩种锁和前面介绍的互斥和共享锁的相容性如下图：

-	IS	IX	S	X
IS	true	true	true	false
IX	true	true	false	false
S	true	false	true	false
X	false	false	false	false

多粒度封锁协议要求加锁从上往下，如果有有自己要加的锁不相容的锁，则进行等待。而释放锁是从下往上。

基于时间戳的协议

前面我们讲解的封锁协议中，每一对冲突事务的次序是在执行时由二者申请的，如果发生冲突，则由谁先执行就决定后一个事务的锁能不能加成功个，如果相容则成功，不相容则等待。而另外一种是由预先选定好的顺序决定的，最常用的就是时间戳排序机制。

时间戳

对于系统中的每个事务T，会把一个唯一的固定时间戳和他关联起来。该时间戳是由事务在进入系统时就确定下来的。时间戳的选取主要由俩种：

系统时钟的值作为时间戳
使用逻辑计数器，每赋予一个时间戳，计数器增加计数。

事务的时间戳决定了事务的调度顺序，如果T1 < T2，则说明T1比T2早进入系统，因此必须保证所产生的调度等价于事务T1出现在事务T2之前的调度中。

同时要实现这个机制，每个数据项Q需要与来个时间戳相关联：

写时间戳：表示成功执行写数据项Q的事务中最大的时间戳，也就是进系统最晚的事务的时间戳
读时间戳：表示成功执行度数据项Q中事务最大的时间戳。

时间戳排序协议

多版本并发控制机制

到目前为止讲述的并发控制机制要么延迟一项操作要么中止该操作的事务来保证可串行性。类如。read操作可能由于相应的值还未写入而延迟，或因为他要读取的值已被覆盖而被拒绝执行。如果每一个数据项的旧值拷贝保存在系统中，这些问题就可以避免。

在多版本并发控制机制中，每个write操作会创建数据项的一个新版本。当事务发出一个read操作，并发控制管理器选择数据项的一个版本进行读取。但是如何快速而且容易的判定哪个版本的数据项也很关键。

多版本并发控制机制主要由俩种：多版本时间戳排序和多版本俩阶段封锁

多版本时间戳排序

这个是结合时间戳排序协议的多版本协议。和前面时间戳协议一样，每个事务都会和一个唯一的时间戳关联。对于一个数据项Q，会有一个版本序列Q1、Q2 。。。。，每个版本Qk包含三个数据字段：

Content是Qk版本的值
写时间戳：创建Qk版本的事务的时间戳
读时间戳：所有成功读取Qk版本的事务的最大时间戳

如果事务发出写操作，创建一个数据项Q的新版本Qk，版本的Content字段保存事务写入的值，系统将写时间戳和读时间戳初始化为事务的时间戳。每当一个新的事务读取Qk的值且读时间戳小于这个读事务的时间戳就会更新读时间戳。

下面展示多版本时间戳排序机制的俩条规则：

假设事务T发出read或write操作，令Q满足如下条件的版本，其写时间戳是小于或等于T的最大时间戳。(事务T表示一些列的事务)

如果事务T发出Read操作，则返回Q的内容
如果事务T发出write操作，且T的时间戳小于Q的读时间戳，也就是事务T比Q版本最大读时间戳对应的事务进系统要早。则系统回滚事务T。另一方面，如果T的时间戳等于Q的时间戳，则覆盖Q的内容。否则(T的时间戳大于Q的最大读时间戳)，创建Q的一个新版本。