并发控制

主要讲述锁在数据库并发的时候如何实现事物隔离级别

两阶段封锁

有一种条件叫做两段锁(two-phase locking, 2PL),在这种令人吃惊的条件下,我们可以保证 一致事务的合法调度是冲突可串行化的。

• 在每个事务中,所有封锁请求先于所有解锁请求。 2PL 中所指的“两阶段”是获得锁的第一阶段和放弃锁的第二阶段。两阶段封锁像一致性一样,是对一个事物中的动作顺序进行限制的条件

图7-13,我们可以看到 两阶段封锁事务如何同调度器进行正确的交互以保证一致性,而非2PL事务允许不一致的(因 非冲突可串行化)行为。

2.锁模式:

一种用于读(共享锁,读锁) ,一种用于写(排它锁,写锁)

在某些情况下面还有一些共享锁升级为排它锁:

我们可能很想知道如果一个想要读X并写入新值的事务T首先获得X上的一个共享锁 而仅在后来当T准备好写入新值时将锁升级为排他的(即除了它在X上已经持有的共享锁外,在申请X上的一个排他锁),这样做是否更友好一些。没有理由阻止事务在同一数据库 一同方式的锁提出申请。我们沿袭u(X)释放X上事务T: 持有的所有锁的惯例。

在下面的例子中,事务T1 可以和T2 并发地执行其计算,而如果T1 最初在B上取得排他锁的话,这是不可能的。这两个事务是,

这里,T1读A和B并对它们执行某种(可能很冗长的)计算,最终使用其结果来为B写入新的值 请注意,T1先获得B上的一个共享锁,而后来,当它完成涉及A和B的计算后,再申请B 的一个排他锁。事务T2. 只读A和B,而并不写。

图7-17 给出了这些动作一个可能的调度。T2, 在T1, 前获得B上的共享锁,但在第4行,T1, 也能以共享方式封锁B。因此, T1有了A和B,能够使用它们的值进行其计算。只有等到T1试图 将其在B上的锁升级为排他的时,调度器才必须拒绝这一请求并迫使T1 等待T2 释放它在B上的 锁。那时候,T1;获得它在B上的排他锁,然后完成。

请注意,如果T1 最初在读B前就请求B上的排他锁,那么这一请求将被拒绝,因为T2 已经 有B上的共享锁。T1在没有读到B的情况下就不能执行其计算,因此在T2 释放其锁后T1 有更多 的事情需要做。所以,只使用排他锁时T1 完成得比它使用升级策略时晚。

例7.16 不幸的是,不加区别地使用升级将会引入新的并且可能更严重的死锁。假设T1, 和 T2. 分别读数据库元素A,并为A写入新值。如果两个事务都使用升级方法,首先获得A上的共享锁,然后将其升级为排他锁。那么只要T1和T2,几乎同时开始,图7-18 所示的事件序列就将会发生

3.时间戳并发控制

1:事实上不可行的行为

图7-35 T 开始过后,U 在T 开始过后进行一个写入X,然后T在读取X,事务T 的读取过完,图36 同理的得事务T 过晚的写

当发生一下两种情况时候需要终止事务T

2:脏数据的问题

由于U最终因为某些原因导致U 终止,然后T 已经读取了X值,所有这个时候可能会产生脏读

另一个潜在的问题如图7-38 所示其中,时间戳比T晚的事务 U先写X。正确的动作是什么都不做。显然不会有另一个事务V应该读T的X值却读到U的值,因为如果V 它将因为过晚的读而中止。以后对V执行的读将需要U的X值或一个更晚写入的X不是T的。这一想法,即与操作在写时间更晚的写操作已发生时可以被跳过,称为Thomas写法则

例7.26 图7-39 给出了的3个事务T1、T2和T3的一个调度,这3个事务访问3个数据库元 素A、B和C。事件发生的实际时间照常随页面向下而增大。但是,我们还指明了事务的时间戳

以及元素的读写时间。在开始时,每个数据库元素具有的读时间和写时间均为0。事务的时间戳 是在它们通知调度器自己开始执行时获得的。请注意,尽管T1执行第一个数据访问,它并不具有最小的时间戳。假设T2 第一个通知调度器自己开始执行,接着是T3而T1最后开始。

在第一个动作中,T1读B。由于B的写时间小于T1的时间戳,此读在事实上可实现因而允许发生。B的读时间被置为T1的时间戳 200。第2和第3个读动作类似地是合法的,导致各数据 库元素的读时间被置为读它的事务的时间戳。

在第4步,T,1写B。由于B的写时间不大于T的时间戳,此写在事实上可实现。由于B的 写时间不大于T1的时间戳,我们必须真正执行此写。我们这样做时,B的写时间增加到200,即 执行写操作的事务T1的时间戳。

接下来,T2试图写C。但是,C已经被事务T3所读,T3理论上的执行时间是175,而T2将 在时间150 写它的值。因此,T2 试图做的事将导致事实上不可实现的,因而T2必须回滚。

最后一步T3 写A。由于A的读时间150 小王T的时间戳 175,此写是合法的。但是,已经有 一个较晚的A值存储在

多版本时间戳,R3 可以读取A150版本

4.有效性确认并发控制(OCC)

当有效确认被用作并发控制机制时,对每个事务T,调度器必须被告知T 所读和写的数据库元素集合,分别是集合RS(T)和写集合WS(T) 事务分三个阶段来执行:

1 读. 在第一阶段,事务从数据库中读集合中的所有元素. 事务还在其局部地址空间中计算它将要写的所有值

2 有效性确认 在第二阶段调度器通过比较该事物与其他事务的读写集合来确认该事物的有效性,如果有效性确认失败,则回滚 否则进入阶段三

3 写 在第三阶段,事务往数据库中写入其写集合中的元素的值

调度器需要维护三个集合:

1.START ,已经开始但尚未完成有效性确认的事务集合.对这个集合中的每个事务T,调度器维护START(T),即事务T开始的时间

2.VAL,已经确认有效性但尚未完成第3阶段写的事务.对这个集合中的每个事务T,调度器维护START(T) 和VAL(T) ,即T确认的时间.请注意VAL(T) 也是假设的中串行执行顺序中所设想的T的执行时间

3.FIN,已经完成3阶段的事务,对这样的事务T,调度器记录START(T),VAL(T) 和FIN(T),即T完成的时间,原则上这个结合将增长,但是我们将看到的,如果对任意活跃事务U(即对任何在START或VAL中的U),事务T满足FIN(T)

有效性确认规则:

可能会发生如下错误

1.假设存在事务U 满足:

U 在VAL或FIN 中 即U 已经经过有效性确认

FIN(U) >START(T) 即U 在T开始前还么有完成

RS(T) ∩ WS(U) 非空,特别的 设其包含数据库元素X

那么U 有可能在T 读X 后写X,事实上U 甚至可能还么有写X,U写了X但并不及时的一种情况.

2.假设存在事务U 满足:

U在VAL中,即U有效性确认成功

FIN(U) >VAL(T) 即U在T 进入其有效性确认阶段以前么有完成

WS(T) ∩WS(U) ≠∅ 特别的 设X 同时在两个写集合中

这时潜在的问题如图,T 和U 都必须写X的值,而如果我们确认T的有效性,他就有可能在U钱写X,而如果我们确认T 的有效性,他就有可能在U钱写X,由于我们不能确定,我们回滚T 以保证他不会违反假设的T在U 后的串行顺序

两个问题是T的写可能事实上不可能实现的唯一情形,在图43,如果U在T 开始前完成,那么T 肯定应该读取到U或者某个更晚的事务所有写的X值 在图44中,如果U在T有效性确认前完成,那么U肯定在T钱写X,因此我们可以用下面的关于事务T有效性确认的规则来概括

.对于所有经过有效性确认切在T开始前没有完成的U,即对于满足FIN(U) >START(T)的U,检查是否RS(T) ∩WS(U) ＝ ∅

.对于所有已经过有效性确认且在T有效性确认前么有完成的U,即对于满足FIN(U)>VAL(T) 的U 检查是否WS(T) ∩WS(U) ＝ ∅

1.U的有效性确认:当确认U的有效性时没有其他确认事务,因为什么也不需要检测.U的有效性成功确认并未数据库元素D写入一个值

2.T的有效性确认:当确认T的有效性时候,U已确认但尚未完成.因此 我们必须检查T的读写结合是否满足于WS(U) = 没有公共元素,由于RS(T) = 而WS(T) = 两个检查都成功,因而确认T的有效性

3.V的有效性确认:当确认V的有效性时,U已经确认和完成,T已经确认但尚未完成,并且V 在U 完成前开始 因此 我们必须用RS(V) 与WS(V)二者来和WS(T) 比较但是需用RS(V) 来和WS(U)比较 我们发发现

RS(V) ∩ WS(T) = ∩ = ∅

WS(V)∩ WS(T) = ∩ = ∅

RS(V) ∩WS(U)= ∩=∅

因此V 的有效性确认成功

4.W的有效性确认:当确认W的有效性时,我们发现U在W 开始前已经结束,因此在W于U 之间不执行任何比较,T在W 确认前完成但尚未在W开始前完成,因此我们比较RS(W)和WS(T) V已经确认但尚未完成,因此我们需要用RS(W) 与WS(W)二者来和 WS(V) 比较

RS(W) ∩ WS(T) = ∩ =

RS(W) ∩ WS(V) =∩ =

WS(W)∩ WS(V) = ∩ = ∅

由于交集并非都为空,W的有效确认不能确认,相反的W 被回滚且不为A 或C 写入值

note:如果我们运行在多处理器上,并且有多个调度器进程,那么就有可能一个在确认T,而另一个在确认U,如果是这样,我们需要依赖多处理器系统提供某种同步机制来使确认成为原子的动作

三种并发控制机制的比较:

封锁:锁表空间与被封锁元素个数成正比

时间戳:再不成熟的实现中,每个数据库元素的读时间和写时间都需要空间,不管该元素是否被访问,但是更精细实现会将最早的活跃事务以前的所有的时间戳看做负无穷,并且不记录他们,我们可以类似锁表那样将读的时间和写的时间记录在一张表中,其中只给出那些最近已经被访问过的数据元素

有效性确认:空间用于每个当前活跃事务已经少量几个在某当前活跃事务开始后完成的事务的时间戳和读写集合

封锁推迟事务但避免回滚,即使当相互影响高时,时间戳和有效性确认不推辞事务,但是能导致其回滚,而这一个推迟的一种更严重的形式,并且浪费资源

如果互相影响低,那么时间戳和有效性确认都不会导致太多的回滚,通常开销很低相比2pl

当回滚必要时,时间戳比较有效性的确认更找的捕获某些问题