并发控制

概述

事务特性

定义

数据库系统（DBMS）：一个数据库系统由一个不可再分（indivisible）的、互不重叠（non-overlapping）的数据对象（data objects）的集合构成：$\{o_1,o_2,\dots ,o_n\}$，每一个object都有一个取值范围（domain of values）。这个系统的一个状态（state）就是一个从object到value的映射。数据库的操作有 $read(r(o_i))$ 和 $write(w(o_i))$。

数据库事务（transaction）：一个事务 $T_i$ 是一个偏序集${\prec }_i$：
$$T_i\subseteq \{b_i\}\cup \{r_i(x),w_i(x)\mid x\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\}\cup \{a_i,c_i\}.$$
其中，$a_i$ 代表abort；$c_i$ 代表commit；$b_i$ 代表begin。$T_i$ 由 $b_i$ 开始，$a_i$ 和 $c_i$只能存在一个，并且是 $T_i$ 的最终操作。为了简洁，$b_i$ 和 $c_i$ 经常被省略。

如果操作 $o_i(x)$ 和 $o_i’(x)$ 属于 $T_i$，那要么 $o_i(x){\prec }_i{o}_i’(x)$，要么 $o_i’(x){\prec }_i{o}_i(x)$。

$T_i$ 中写操作 $w_i(x)$ 写入数据对象 $x$ 的值是一个关于 $T_i$ 之前（由 ${\prec }_i$ 定义）所有读取的值的函数。比如在 $T_1:r_1(x)r_1(y)w_1(z)$ 中，$z$ 的值是关于 $x$ 和 $y$ 的某个函数 $f(x,y)$，也就是说我们没有对写操作做任何假设，写入的值可能会取决于 $T_i$ 观察到的所有值。

调度（schedule）： 调度定义为 $S=(\tau ,{\prec }_S)$，其中：

• $\tau$ 是事务的集合；
• ${\prec }_S$ 是 $\tau$ 中事务中的数据操作的偏序，并满足： $\forall T_i\in \tau ,{\prec }_i\subseteq {\prec }_S$，也就是说，调度会保持每个事务中操作自己的顺序。

串行调度（serial schedule）：事务按顺序依次执行的调度。

可串行化的（serializable）：如果一个调度 $S=(\tau ,{\prec }_S)$ 等价于 某个串行调度 $S’=(\tau ,{\prec }_{S’})$，那么 $S$ 就是可串行的。这里”等价于“的概念不同，又衍生出几种可串行的定义：

• 终态可串行（final state serializability）：

  我们说两个调度 $S_1$ 和 $S_2$ 是终态等价的（final state equivalent），如果它们满足：

  • 它们涉及的事务相同；以及
  • 在所有对写操作的解读下($w_i(x)$可能是任何关于之前读取的数据的函数$f$)，对于所有的初始状态 $I$，$I\stackrel{S_1}{\to }{I}_1,I\stackrel{S_2}{\to }{I}_2$，有 $I_1=I_2$。这里等于的含义是数据库的状态(映射)相同。

  我们定义：如果一个调度 $S=(\tau ,{\prec }_S)$ 终态等价于 某个串行调度 $S’=(\tau ,{\prec }_{S’})$，那么 $S$ 就是终态可串行化的。在不特别说明的情况下，我们说可串行指的即是终态可串行。

• 冲突可串行（conflict serializability）：

  我们说两个调度 $S_1$ 和 $S_2$ 是冲突等价的（conflict equivalent），如果它们满足：

  • 它们涉及的事务相同；以及
  • 它们对冲突操作（conflicting operations）的排序相同。

  我们定义：如果一个调度 $S=(\tau ,{\prec }_S)$ 冲突等价于 某个串行调度 $S’=(\tau ,{\prec }_{S’})$，那么 $S$ 就是冲突可串行的。

数据库状态一致性：遵循设计者想要的所有隐含的或声明的约束的数据库状态被称为是一致的。数据库上的操作保持一致性是指，它们将一个一致的数据库状态转换到另一个。

并发控制：并发执行的事务之间的相互影响可能导致数据库状态的不一致，即使各个事务能保持状态的正确性，而且也没有任何故障发生。因此，不同事务各个步骤的执行顺序必须以某种方式进行规范。该规范是由DBMS的调度器部件完成，而保证并发执行的事务能保持一致性的整个过程称为并发控制。

并发事务一致性：多个事务同时访问一个数据库是很正常的。隔离执行的事务是假定能保持数据库一致性的。保证并发操作的事务也保持数据库一致性是调度器的任务。

并发控制机制

基于封锁

以下章节介绍了基于封锁的并发控制机制：

• 使用锁的可串行化实现
• 多种锁模式的封锁系统
• 封锁调度器的一种体系结构
• 数据库元素的层次

基于时间戳

以下章节介绍了基于时间戳的并发控制机制：

• 使用时间戳的并发控制

基于有效性确认

以下章节介绍了基于有效性确认的并发控制机制：

• 使用有效性确认的并发控制

串行调度和可串行调度

事务的正确性原则：如果事务在没有其他任何事务和系统错误的情况下执行，并且在它开始时数据库处于一致的状态，那么当事务结束时数据库仍然处于一致的状态。

调度

调度是一个或多个事务的重要动作的一个序列。当研究并发控制时，重要的读写动作发生在主存缓冲区中，而不是磁盘上。也就是说，某个事务T放入缓冲区的数据库元素A在该缓冲区中可能不仅被T还被其它访问A的事务读或写。

串行调度

如果一个调度的动作组成首先是一个事务的所有动作，然后是另一个事务的所有动作，依次类推，那么这一调度是串行的。不允许动作的混合。通常情况下，数据库终态是与事务执行顺序有关的。

事务T：<T,X,X+100>，事务U：<U,X,2*X>，X的初始值为25

那么调度(T,U)完成后X在主存中的值为250，而调度(U,T)完成后X在主存中的值为150

可串行化调度

事务的正确性原则告诉我们，每个串行调度都将保持数据库状态的一致性。但还有其他能保证可保持一致性的调度。通常，如果存在串行调度S’，使得对于每个数据库初态，调度S和调度S’的效果相同，我们就说这个调度S是可串行化的。

一致的状态可以认为，假设在初始状态有数据库元素A，B满足A=B，那么在任意调度后仍有A=B。

假设在调度完成后，A和B上实施了不同的运算（这里我们忽略了事务的细节），例如：A:=(A+100)*2，B:=(B)*2+100。那么，这样就出现了不一致的情况，这种调度是并发控制机制必须避免的行为类型。

可串行性保证并发执行的事务能保持数据库状态的正确性。

事务和调度的记法

事务语义的影响

仍以上述为例，但将乘2改为加200，那么有A:=(A+100)+200，B:=(B+200)+100。

巧合的是，A和B在实施不同运算之后仍相等。

上述巧合的例子表明调度可串行化与事务的细节是有关系的。不幸的是，**调度器考虑事务所进行计算的细节是不现实的。**由于事务通常不仅包括SQL或其他高级语句书写的代码，还包括通用编程语言编写的代码，不可能确切地说出事务具体在做什么事。但是，调度器的确能看到来自事务的读写请求，于是能够知道每个事务读哪些数据库元素，以及它可能改变哪些元素。通常假定：

• 事务T所写的任意数据库元素A被赋予的值[不发生任何算术巧合地]依赖于数据库的状态。

Any database element A that a transaction T writes is given a value that depends on the database state in such a way that [no arithmetic coincidences occur].

事务和调度的记法

如果我们假设“没有巧合”，那么**只有事务执行的读和写需要考虑，而不涉及真实的值。**因此，我们可以用
$$r_i(X),w_i(X)$$
分别表示事务$T_i$读和写数据库元素X。这里我们规定事务$T_i$是具有下标i的动作序列，$T=\{T_1,T_2,...,T_k\}$为事务的集合。事务集合T的调度S是一个动作序列，其中对T中的每个事务$T_i$，$T_i$中的动作在S中出现的顺序和其在$T_i$自身定义中出现的顺序一样。我们说S是组成它的事务动作的一个交错。

冲突可串行化

冲突

对于调度中一对连续的动作，若它们满足：如果它们的顺序交换，那么涉及的事务中至少有一个的行为会改变。那么我们就称这个两个动作是冲突的。

对于两不同事务 $T_i,T_j$，对以下的两个动作：

我们得到的结论是，不同事务的任何两个动作可以交换，除以下情况外：

1. 它们涉及同一数据库元素。
2. 至少有一个是写。

将这一想法进行扩展，我们可以接受任一调度，进行任意非冲突的交换，目标是将该调度转换为一个串行调度。如果我们能做到这一点，那么初始的调度是可串行化的，因为它对数据库状态的影响在我们做每一个非冲突交换时是不变的。我们引申出以下两个概念：

冲突等价：如果通过一系列相邻动作的非冲突交换能将原调度转换为另一个调度，我们说两个调度是冲突等价的。

冲突可串行化：如果一个调度冲突等价于一个串行调度，那么我们说该调度是冲突可串行化的。

冲突可串行化是可串行化的一个充分条件。

对调度S，可串行化指的是如果有一个串行调度S’的执行结果与S相同，那么就认为S是可串行化的；而冲突可串行化是指若S经过若干次非冲突的交换，得到的调度S’‘是串行调度，那么就认为S是冲突可串行化的。这里表明若S是冲突可串行化的，那么就一定存在一个串行调度S’’，且执行结果与S相同，故S也是可串行化的。

为什么冲突可串行化不是可串行化的必要条件？

我们考虑事务T1,T2,T3以及以下两个调度：
$$\begin{gathered} S_1:w_1(Y);w_1(X);w_2(Y);w_2(X);w_3(X); \\ {S}_2:w_1(Y);w_2(Y);w_1(X);w_2(X);w_3(X); \end{gathered}$$
可以看出S1和S2执行后的结果是相同的，且S1是串行调度。也就是说，调度S2是可串行化的。然而，对数据库元素X或Y，我们发现都无法交换冲突的动作，那么，调度S2是非冲突可串行化的。

优先图

检查调度S并决定它是否是冲突可串行化相对而言比较简单。

已知调度S，其中涉及事务T1和T2，可能还有其他事务，我们说T1优先于T2，并记为
$$T_1{<}_S{T}_2,$$
如果有T1的动作A1和T2的动作A2，满足：

1. 在S中A1在A2之前。
2. A1和A2都涉及同一数据库元素。
3. A1和A2中至少有一个是写动作。

这里正是我们不能交换A1和A2顺序的情况。因此，在任何冲突等价于S的调度中，A1将会出现在A2前。所以，冲突等价的串行调度（若有）必然使T1在T2前。我们可以使用一种记号来概括这种顺序关系，很自然的想到可以用图来表示。

优先图（precedence graph）：优先图的结点是调度中的事务。我们用整数i来表示事务Ti。如果$T_i{<}_S{T}_j$，则有一条从结点i到结点j的弧。

我们可以构造S的优先图，并判断其中是否有环来判断调度S是否冲突可串行化。如果有，那么S不是冲突可串行化的。如果该图是无环的，那么S是冲突可串行化的，而且结点的任何一个拓扑排序都是一个冲突等价的串行顺序。

证明

我们证明如下命题：

若调度S的优先图无环，则S是冲突可串行化的；若有环，则S是非冲突可串行化的。

Proof：

(I) 若有环，不妨设为$T_1\to T_2\to ...T_n\to T_1$。假设存在冲突可串行化调度（则也存在可串行化调度），那么T1的所有动作应于Tn之前，而$T_n\to T_1$表明$T_n{<}_S{T}_1$，即Tn中存在动作在T1之前，矛盾。

(II) 若无环，可对事务的个数n用数学归纳法证明。

BASIS：若n=1，即只有一个事务，那么其自然是可串行化的。

INDUCTION：设调度S由以下n个事务组成
$$T_1,T_2,...,T_n,$$
且S的优先图是无环的。那么，对于有向无环图来说，至少有一个结点没有入边，不失一般性，我们记该结点为$T_i$。则调度S中不存在这样的动作：不属于事务$T_i$的、在$T_i$某个动作之前的且与之冲突的动作。否则，我们就要在该事务与$T_i$之间加一条指向$T_i$的弧。

现在，我们可以将调度S划分为
$$(\text{Actions of}{T}_i),(\text{Actions of the other n - 1 transactions}).$$
注意到原优先图是无环的，去掉$T_i$的一条出边仍是无环的。对于剩下的$n-1$个事务，由数学归纳法知其是冲突可串行化的，再加上位于动作序列前部的均属于$T_i$的动作，则证明整个调度S是冲突可串行化的。∎

如果我们去掉T1优于T2的条件3，那么易证在满足该优先条件的优先图中，若优先图无环，则调度S是可串行化的。

证明基于该命题即是平凡的：对任意2个事务T1、T2，若仅存在T1指向T2的弧，则说明T1的动作均在T2之前。

该结论在基于树的封锁协议中应用。

使用锁的可串行化实现

我们考虑调度器最常用的体系结构，这种结构在数据库元素上维护“锁”以防止非可串行化的行为。直观地说，事务获得在它所访问的数据库元素上的锁，以防止其他事务几乎在同一时间访问这些元素并因而引入非可串行化的可能。在本节中，我们用一个简单的封锁模式来介绍封锁的概念，该模式只有一种锁。

锁

调度器的责任是接受来自事务的请求，或者允许它们在数据库上操作，或者将它们推迟直到允许它们继续执行是安全的时候。调度器使用锁表指导决策。

requests from transactions -> Scheduler <--> lock table
								  |
								  v
					Serializable schedule of actions

调度器转发请求，当且仅当该请求的执行不可能在所有活跃事务提交或中止后使数据库处于不一致的状态。我们称基于封锁（locking）的调度器为封锁调度器（locking scheduler）。封锁调度器像大多数调度器种类一样，事实上实现的是冲突可串行化。

当调度器使用锁时，事务在读写数据库元素以外还必须申请和释放锁。锁的使用必须在两种意义上都是正确的，一种适用于事务的结构，另一种适用于调度的结构。

• 事务的一致性：动作和锁必须按预期的方式发生联系：

  (a) 事务只有先前已经在数据库元素上被授予了锁并且还没有释放锁时，才能读或写该数据库元素。

  (b) 如果事务封锁某个数据库元素，它以后必须为该元素解锁。

• 调度的合法性：锁必须具有其预期的含义：

  (a) 任何两个事务都不能封锁同一元素，除非其中一个事务已经先释放其锁。

我们扩展动作的记法：

• $l_i(X)$：事务$T_i$请求数据库元素X上的锁（加锁）。
• $u_i(X)$：事务$T_i$释放它在数据库元素X上的锁（解锁）。

那么，上述关于锁的表述可以为：

• 事务的一致性：动作和锁必须按预期的方式发生联系：

  (a) 若事务$T_i$有动作$r_i(X)$或$w_i(X)$，那么前面必须有$l_i(X)$，且二者之间没有$u_i(X)$。

  (b) $l_i(X)$后面必须有$u_i(X)$。

• 调度的合法性：锁必须具有其预期的含义：

  (a) 如果调度在动作$l_i(X)$之后有$l_j(X)$，那么两者之间必须有$u_i(X)$。

如果调度器产生的事务的动作序列满足以上几条，则我们称为该调度为合法调度。

封锁调度器

基于封锁的调度器的任务是，当且仅当请求将产生合法调度时同意请求。如果请求未被同意，发出请求的事务被延迟，直到调度器某时刻同意了该请求。为了帮助进行决策，调度器有一个锁表，对于每个数据库元素，如果其上有锁，那么锁表指明当前持有该锁的任务。当我们假设只有一种锁时，该表可被看作是关系Locks(element, transaction)。调度器仅需维护这一关系即可。

两阶段封锁（2PL）

有一种条件叫做两阶段锁（two-phase locking，2PL）：

• 2PL：在每个事务中，所有封锁请求先于所有解锁请求。

在这种情况下，可以保证一致事务的合法调度是冲突可串行化的。即对某个一致事务的合法调度，我们通过2PL封锁模式，可使其变为冲突可串行化的。

注意到，这里是对事务动作序列进行的限制，而在调度中可能出现先解锁后加锁的行为。即请求是封锁先于解锁，而动作则不一定。

这里两阶段指的是获取锁的第一阶段和释放锁的第二阶段。两阶段封锁像一致性一样，是对一个事务中动作的顺序进行限制的条件。服从2PL条件的事务被称为两阶段封锁事务，或2PL事务。

不是数据库选择去实现条件更苛刻的冲突可串行化，而是由于2PL较易实现（或者说冲突可串行化易于验证），且恰好基于2PL可以实现冲突可串行化，所以在商业系统中普遍采用了冲突可串行化。

证明

我们证明如下命题：

使用2PL事务、满足事务一致性的合法调度是冲突可串行化的。

Proof：

对事务个数n用数学归纳法。

BASIS：若n=1，即只有一个事务，那么其自然是可串行化的。

INDUCTION：设调度S由以下n个事务组成
$$T_1,T_2,...,T_n,$$
不失一般性，我们假设在S中第一个出现解锁动作的事务是$T_i$，解锁动作设为$u_i(X)$。接下来我们分两步证明：

1. 事务$T_i$可以直接移动到S的最前部。

2. 当事务$T_i$在最前部时，可以将S划分为

   $$(\text{Actions of}{T}_i),(\text{Actions of the other n - 1 transactions}).$$

步骤2是显然的。由步骤2我们得到：由数学归纳法可知后n-1个事务是一致的2PL合法调度，我们将其转换为冲突可串行化调度，从而证明了S是冲突可串行化的。

下面我们用反证法证明步骤1。

对$T_i$的某个动作，不妨设为$w_i(Y)$，假设在该动作之前有与之冲突的事务，不妨设为$w_j(Y)$（$r_j(Y)$也一样），那么，动作序列可能如下
$$...;w_j(Y);...;u_j(Y);...;l_i(Y);...;w_i(Y);...$$
而X是第一个解锁的，那么S可能形如
$$...;u_i(X);...;w_j(Y);...;u_j(Y);...;l_i(Y);...;w_i(Y);...$$
我们发现，事务$T_i$先进行了解锁，后进行了加锁，这与2PL事务矛盾！∎

多种锁模式的封锁系统

上节的封锁模式阐明了在封锁背后的重要思路，但它过于简单因而不是一个实用的模式。主要的问题在于，事务T即使只想读数据库元素X而不写它，也必须获得X上的锁。因为我们不能避开锁的获得，当其他事务在写X时可能会导致冲突。然而，若几个事务都不允许写X时，不允许几个事务同时读X就是没有理由的。

我们自然就想到了一个新的封锁模式：含有两种不同锁的模式，分别用于读（称为共享锁，读锁）和写（称为排他锁，写锁）。

共享锁与排他锁

在事务满足一致性要求时：

• 共享锁（Shared lock，read lock）：当一个事务持有共享锁时，禁止其他事务写。
• 排他锁（Exclusive lock，write lock）：当一个事务持有排他锁时，禁止其他事务读和写。

我们考虑使用上述两种不同类型的锁的封锁调度器。对任何数据库元素，其上：

• 有一个排他锁，或
• 有任意数目的共享锁。

如果我们想要写X，那么需要有X上的一个排他锁。如果仅想读X，那么我们倾向于只获得共享锁。

我们新引入两个记号，用来表示共享锁与排他锁：

• $s{l}_i(X)$：表示事务$T_i$申请数据库元素X上的一个共享锁。
• $x{l}_i(X)$：表示事务$T_i$申请数据库元素X上的一个排他锁。

在含有共享锁与排他锁的封锁系统中，事务的一致性、事务的2PL以及调度的合法性表述为：

• 事务的一致性：如果不是持有排他锁就不能写，并且如果不是持有某个锁就不能读。具体地，

  (a) $r_i(X)$前面必须有$s{l}_i(X)$ 或 $x{l}_i(X)$，且二者之间没有$u_i(X)$。

  (b) $r_i(X)$前面必须有 $x{l}_i(X)$，且二者之间没有$u_i(X)$。

• 事务的2PL：封锁必须在解锁之前。具体地，

  (a) 对任意的数据库元素Y，在任何两阶段封锁事务$T_i$中，任何$s{l}_i(X)$或$s{l}_i(X)$动作之前不能有$u_i(Y)$动作。

• 调度的合法性：一个元素或者可以被一个事务排他地封锁，或者可以被几个事务共享地封锁，但不能二者兼有之。具体地，

  (a) 如果$x{l}_i(X)$出现在了调度中，那么对于$i\ne j$，后面不能跟有$x{l}_j(X),s{l}_j(X)$，除非中间间隔了$u_i(X)$。

  (b) 如果$s{l}_i(X)$出现在了调度中，那么对于$i\ne j$，后面不能跟有$x{l}_j(X)$，除非中间间隔了$u_i(X)$。

上述“不能二者兼有之”的原因是：排他锁禁止其他事务读。但对于同一个事务，允许其在同一个元素上既持有排他锁又持有共享锁。

我们在上节证明一致性的2PL事务的合法调度是冲突可串行化的，该结论同样适用于具有共享锁和排他锁的系统。

相容性矩阵

调度器需要一个关于在已知同一数据库元素上可能已经持有锁的情况下何时能同意封锁请求的策略。相容性矩阵就是一个描述锁-管理策略的简单方法。含有共享锁与排他锁的封锁系统的相容性矩阵为：

We can grant the lock on X in mode C if and only if for every row R such that there is already a lock on X in mode R by some other transaction, there is a “Yes” in column C.

锁的升级

占有X上的共享锁的事务T对其他事务来说是友好的，因为其他事务在T被允许访问X的同时也被允许访问X。因此，我们考虑能否先获取共享锁，再获取排他锁，即将锁升级。具体地，对一个想要读X并写入新值的事务T，首先获得X上的一个共享锁，且仅在后来当T准备好写入新值时将锁升级为排他锁（即除了它在X上已经持有的共享锁外再申请X上的一个排他锁）。没有理由阻止事务在同一数据库元素上对不同方式的锁提出申请。

下面两个2PL事务可以并发地执行计算：
$$\begin{gathered} T_1:s{l}_1(A);r_1(A);s{l}_1(B);r_1(B);x{l}_1(B);w_1(B);u_1(A);u_1(B); \\ {T}_2:s{l}_2(A);r_2(A);s{l}_2(B);r_2(B);u2(A);u2(B); \end{gathered}$$

事务T1读A和B并对它们执行某种（可能冗长的）计算，最终将结果写入B。而事务T2仅读A和B。那么，**若事务T1在一开始读B时就对B申请排他锁，有可能因事务T2持有B的共享锁而遭到拒绝。**此时仅能等待T2释放B的锁之后才能读B。

一个可能的调度为

T1	T2
$s{l}_1(A);r_1(A);$
	$s{l}_2(A);r_2(A);$
	$s{l}_2(B);r_2(B);$
$s{l}_1(B);r_1(B);$
$x{l}_1(B)\text{Denied}$
	$u2(A);u2(B);$
$x{l}_1(B);w_1(B);u_1(A);u_1(B);$

然而，不幸的是，不加区别地使用升级将会引入新的并且可能更严重的死锁。考虑如下两个事务：
$$\begin{gathered} T_1:s{l}_1(A);r_1(A);x{l}_1(A);w_1(A);u_1(A); \\ {T}_2:s{l}_2(A);r_2(A);x{l}_2(A);w_2(A);u_2(A); \end{gathered}$$
可能的调度是：

T1	T2
$s{l}_1(A);r_1(A);$
	$s{l}_2(A);r_2(A);$
$x{l}_1(A)\text{Denied}$
	$x{l}_2(A)\text{Denied}$

这里两个事务分别获取到A的共享锁后，又想升级为排他锁；那么，在上述调度下两个事务申请在A上的排他锁都将被拒绝，且形成死锁。结果就是：永远等待，或者等到系统发现死锁的存在，中止两个事务中的一个，而给另一个事务A上的排他锁。为避免这种情况出现，我们将在下文介绍一种新的封锁模式。

更新锁

更新锁（Update lock）可以避免上述死锁的问题，我们记

• $u{l}_i(x)$：事务$T_i$申请读X而不是写X的权限。但只有更新锁可以升级为写锁，而读锁不能升级。

当X上已经有共享锁时我们可以授予X上的更新锁，但是一旦X上有了更新锁，我们就禁止在X上加其他任何种类的锁。相容性矩阵为

**更新锁在我们申请时像一个共享锁，在持有时像一个排他锁。**更新锁意在告诉调度器，该锁将要更新，后续不要让其他事务持有该锁。

我们仍考虑上述例子的两个事务，但对于先读后写的事务，对相应的数据库元素授予更新锁而不是写锁：
$$\begin{gathered} T_1:u{l}_1(A);r_1(A);x{l}_1(A);w_1(A);u_1(A); \\ {T}_2:u{l}_2(A);r_2(A);x{l}_2(A);w_2(A);u_2(A); \end{gathered}$$
我们再回到上述调度，会发现不存在死锁问题：

T1	T2
$u{l}_1(A);r_1(A);$
	$u{l}_2(A)\text{Denied}$
$x{l}_1(A);w_1(A);u_1(A);$
	$u{l}_2(A);r_2(A);x{l}_2(A);w_2(A);u_2(A);$

这是因为，在事务T1获取到A的更新锁后，其表现出排他锁的效果，导致T2无法再获取到A的任何锁。然而，这一封锁系统实际上阻碍了T1和T2的并发执行。

增量锁

在某些情况下，有一种很有用的锁被称为增量锁。前提是，很多事务都只通过增加或减少存储的值来对数据库进行操作。

增量动作一个有用的性质是这些动作相互之间是可以交换的，因为如果两个事务都给同一个数据库元素加上常数，根据加法交换律可知顺序不影响最终的结果。另一方面，增量与读或写都不能交换：如果在A增加之前或之后读它，得到的结果是不同的；如果在其他事务写A之前或之后增加它，结果也会不同。

我们记事务中引入的增量动作为INC(A,c)，这一动作将常数c加到数据库元素A上。正规地，我们使用INC(A,c)表示以下步骤的原子执行：
$$\text{INC}(A,c):=\text{WRITE}(A,t);t:=t+c;\text{READ}(A,t);$$
与增量动作对应，我们需要一个增量锁。增量锁的记号为

• $i{l}_i(X),in{c}_i(X)$：事务$T_i$在数据库元素X上增加某个常数的动作，具体常数可忽略。

这里增加的含义是：假设X是单独的一个数，我们为其加上或减去一个常数，而不是进行运算，例如乘法。

增量动作和增量锁的事务一致性、冲突和合法调度需要一些修改，具体为：

• 事务的一致性：

  (a) 一致的事务只有在它持有X上的增量锁时才能在X上进行增量动作。但增量锁并不能赋予读或写动作的权力。

• 调度的合法性：

  (a) 在一个合法的调度中，任何时候都可以有任意多个事务在X上持有增量锁。但是，如果某个事务持有X上的增量锁，那么其他事务同时在X上既不能持有共享锁又不能持有排他锁。

• 对 $i\ne j,in{c}_i(X)$ 与 $r_j(X),w_j(X)$ 冲突，但与 $in{c}_j(X)$ 不冲突。

相容性矩阵为

总结

锁的种类

事务一致性、冲突和合法调度

基于锁（基本）

• 事务的一致性：动作和锁必须按预期的方式发生联系：

  (a) 事务只有先前已经在数据库元素上被授予了锁并且还没有释放锁时，才能读或写该数据库元素。

  (b) 如果事务封锁某个数据库元素，它以后必须为该元素解锁。

• 调度的合法性：锁必须具有其预期的含义：

  (a) 任何两个事务都不能封锁同一元素，除非其中一个事务已经先释放其锁。

基于共享锁与排他锁

• 事务的一致性：如果不是持有排他锁就不能写，并且如果不是持有某个锁就不能读。具体地，

  (a) $r_i(X)$前面必须有$s{l}_i(X)$ 或 $x{l}_i(X)$，且二者之间没有$u_i(X)$。

  (b) $r_i(X)$前面必须有 $x{l}_i(X)$，且二者之间没有$u_i(X)$。

• 事务的2PL：封锁必须在解锁之前。具体地，

  (a) 对任意的数据库元素Y，在任何两阶段封锁事务$T_i$中，任何$s{l}_i(X)$或$s{l}_i(X)$动作之前不能有$u_i(Y)$动作。

• 调度的合法性：一个元素或者可以被一个事务排他地封锁，或者可以被几个事务共享地封锁，但不能二者兼有之。具体地，

  (a) 如果$x{l}_i(X)$出现在了调度中，那么对于$i\ne j$，后面不能跟有$x{l}_j(X),s{l}_j(X)$，除非中间间隔了$u_i(X)$。

  (b) 如果$s{l}_i(X)$出现在了调度中，那么对于$i\ne j$，后面不能跟有$x{l}_j(X)$，除非中间间隔了$u_i(X)$。

基于更新锁（修改）

• 事务的一致性：

  (a) 一致的事务只有在它持有X上的增量锁时才能在X上进行增量动作。但增量锁并不能赋予读或写动作的权力。

• 调度的合法性：

  (a) 在一个合法的调度中，任何时候都可以有任意多个事务在X上持有增量锁。但是，如果某个事务持有X上的增量锁，那么其他事务同时在X上既不能持有共享锁又不能持有排他锁。

• 对 $i\ne j,in{c}_i(X)$ 与 $r_j(X),w_j(X)$ 冲突，但与 $in{c}_j(X)$ 不冲突。

共享锁、排他锁、更新锁的例子

对事务$T_1,T_2,T_3$以及其调度
$$S:r_1(A);r_2(B);r_3(C);r_1(B);r_2(C);r_3(D);w_1(A);w_2(B);w_3(C);$$

1. 插入共享锁和排他锁，并插入解锁动作。如果一个读动作后面没有同一事务对相同元素的写动作，在仅靠它的前面放置一个共享锁。在每一个其他的读或写动作前面放置一个排他锁。在每个事务的结束时放置必要的解锁。
   $$\begin{gathered} x{l}_1(A);r_1(A);x{l}_2(B);r_2(B);x{l}_3(C);r_3(C); \\ s{l}_1(B);r_1(B);s{l}_2(C);r_2(C);s{l}_3(D);r_3(D); \\ {w}_1(A);u_1(A);u_1(B);w_2(B);u_2(B);u_2(C);w_3(C);u_3(C);u_3(D); \end{gathered}$$

   可能发生的调度是什么？

   T1	T2	T3
   $x{l}_1(A);r_1(A);$
   	$x{l}_2(B);r_2(B);$
   		$x{l}_3(C);r_3(C);$
   $s{l}_1(B)\text{Denied}$
   	$s{l}_2(C)\text{Denied}$
   		$s{l}_3(D);r_3(D);$
   $w_1(A);u_1(A);$
   	$w_2(B);u_2(B);$
   		$w_3(C);u_3(C);u_3(D);$
   $s{l}_1(B);r_1(B);u_1(B);$
   	$s{l}_2(C);r_2(C);u_2(C);$

2. 以一种允许升级的方式插入共享锁和排他锁。在每个读事务前面放置一个共享锁，在每个写动作前面放置一个排他锁。在末尾放置必要的解锁。
   $$\begin{gathered} s{l}_1(A);r_1(A);s{l}_2(B);r_2(B);s{l}_3(C);r_3(C); \\ s{l}_1(B);r_1(B);s{l}_2(C);r_2(C);s{l}_3(D);r_3(D); \\ x{l}_1(A);w_1(A);u_1(A);u_1(B);x{l}_2(B);w_2(B);u_2(B);u_2(C);x{l}_3(C);w_3(C);u_3(C);u_3(D); \end{gathered}$$

   发生的调度是什么？

   | T1 | T2 | T3 |
   | --------------------------------- | -------------------------------- | -------------------------------- |
   | $s{l}_1(A);r_1(A);$ | | |
   | | $s{l}_2(B);r_2(B);$ | |
   | | | $s{l}_3(C);r_3(C);$ |
   | $s{l}_1(B);r_1(B);$ | | |
   | | $s{l}_2(C);r_2(C);$ | |
   | | | $s{l}_3(D);r_3(D);$ |
   | $x{l}_1(A);w_1(A);u_1(A);u_1(B);$ | | |
   | | $x{l}_2(B);w_2(B);u_2(B);u_2(C);$ | |
   | | | $x{l}_3(C);w_3(C);u_3(C);u_3(D);$ |

   这些动作是以与请求完全相同的顺序执行的；也就是说，调度器没有任何延迟。

3. 插入共享锁、排他锁和更新锁，并插入解锁动作。在每一个不会升级的读动作前放置一个共享锁，在每一个将升级的读动作前放置一个更新锁，在每一个写动作前放置一个排他锁。在事务的末尾放置必要的解锁。
   $$\begin{gathered} u{l}_1(A);r_1(A);u{l}_2(B);r_2(B);u{l}_3(C);r_3(C); \\ s{l}_1(B);r_1(B);s{l}_2(C);r_2(C);s{l}_3(D);r_3(D); \\ x{l}_1(A);w_1(A);u_1(A);u_1(B);x{l}_2(B);w_2(B);u_2(B);u_2(C);x{l}_3(C);w_3(C);u_3(C);u_3(D); \end{gathered}$$
   发生的调度是什么？

   T1	T2	T3
   $u{l}_1(A);r_1(A);$

| | $u{l}_2(B);r_2(B);$ | |
| | | $u{l}_3(C);r_3(C);$ |
| $s{l}_1(B)\text{Denied}$ | | |
| | $s{l}_2(C)\text{Denied}$ | |
| | | $s{l}_3(D);r_3(D);$ |
| $x{l}_1(A);w_1(A);u_1(A);$ | | |
| | $x{l}_2(B);w_2(B);u_2(B);$ | |
| | | $x{l}_3(C);w_3(C);u_3(C);u_3(D);$ |
| $s{l}_1(B);r_1(B);u_1(B);$ | | |
| | $s{l}_2(C);r_2(C);u_2(C);$ | |

更新锁阻止了第四和第五个共享锁请求（$s{l}_1(B)\&s{l}_2(C)$），所以$T_1$和$T_2$被延迟了，而$T_3$被允许继续。情况与第1部分完全一样，但由更新锁升级为排他锁。

封锁调度器的一种体系结构

上述内容介绍了不同的封锁机制，我们接下来考虑使用这些模式之一的调度器是如何实现的。我们基于以下几个原则来描述一个简单的调度器：

• 事务本身不会申请封锁，或我们不能依赖于事务做这件事。在读、写以及其他访问数据的动作流中插入锁的动作是调度器的任务。
• 事务不释放锁，而是调度器在事务管理器告诉它事务将提交或中止时释放锁。

即加锁和解锁均是调度器的行为。

插入锁

调度器接受来自事务的请求，通过维护一个锁表来控制事务对数据库元素的访问。缩表可能部分地或全部位于主存中。通常，锁表使用的主存不是用于查询执行和日志的缓冲池的一部分。锁表是DBMS的另一组成部分，并且将像DBMS的其它代码和数据那样由操作系统为其分配空间。

事务请求的动作通常通过调度器传送并在数据库上执行。但在某些情况下，事务等待一个锁而被推迟，其请求（暂时）不被传送到数据库。

               From transactions
                        |
                        v READ(A);WRITE(B);COMMIT(X);...
             <-  Scheduler,Part I
      lock              |
      table             V LOCK(A);READ(A);...
             <-  Scheduler,Part II
                        |
                        V READ(A);WRITE(B);...
                     Database

调度器分为两个部分，执行如下动作：

1. 第I部分接受事务产生的请求流，并在所有数据库访问操作如读、写、增量和更新前插入适当的锁动作。不管调度器使用什么样的封锁模式集合，调度器的第I部分必须从其中选择适当的封锁方式。数据库访问操作接下来被传送到第II部分。

2. 第II部分接受由第I部分传来的封锁和数据库访问动作序列，并正确地执行它们中的每一个。对于一个封锁或数据库访问请求，首先要判断提出请求的事务T是否由于某个锁不能被授予因而已经被推迟：

   2.1 若被推迟，则将这个动作加入一个最终必须为事务T执行的动作列表中。

   2.2 若未被推迟，即前面它所申请的所有锁已经被授予，则判断其动作种类：

   2.2.1 如果动作是数据库访问，则这一动作被传送到数据库并被执行。

   2.2.2 如果动作是封锁，则通过锁表判断锁能否被授予：

   ​ 2.2.2.1 如果被授予，则修改锁表，将刚授予的锁包括进去。

   ​ 2.2.2.2 如果未被授予，那么锁表中必须加入一项以表明该锁已被申请。调度器的第II部分接着推迟事务T直到锁被授予时。

3. 当事务T提交或中止时，事务管理器将通知第I部分，第I部分于是释放T持有的所有锁。如果有事务等待这些锁中的任何一个，第I部分将通知第II部分。

4. 当第II部分被告知某个数据库元素X上的锁可以获得时，它决定接下来能获得X上的锁的一个或多个事务。获得锁的一个或多个事务被允许尽可能多的执行被推迟的动作，直到它们完成或达到另一个不能被授予的封锁请求。

我们考虑以下几种封锁模式对应的调度器的实现：

• 仅有一种锁：调度器第I部分只要看见访问X的请求，就为其加锁。当事务提交或中止时，第I部分就释放该事务的锁并遗忘该事务的一切。

• 共享-排他-更新封锁模式：我们考虑以下两个事务
  $$\begin{gathered} T_1:r_1(A);r_1(B);w_1(B); \\ {T}_2:r_2(A);r_2(B); \end{gathered}$$
  传给调度器第I部分的消息不仅包括读或写请求，还必须包括关于同一元素上将有动作的指示。例如，当$r_1(B)$被传进来时，调度器需要直到后面有$w_1(B)$动作（或可能有这样的动作）。调度器是可以得知的，如果事务是一个查询，则不包含写动作；如果事务是一个SQL更新数据库命令，则可知该事务可能涉及读和写事务。

  假设调度为

  T1	T2
  $s{l}_1(A);r_1(A);$
  	$s{l}_2(A);r_2(A);$
  	$s{l}_2(B);r_2(B);$
  $u{l}_1(B);r_1(B);$
  $x{l}_1(B)\text{Denied}$
  	$u2(A);u2(B);$
  $x{l}_1(B);w_1(B);$
  $u_1(A);u_1(B);$

  调度器分为如下步骤进行处理：

  1. 第I部分接收事务T1的$r_1(A)$动作，由于后续T1不再写A，那么调度器第I部分为其加上$s{l}_1(A)$，发出动作序列$s{l}_1(A);r_1(A);$.同时第II部分接收动作，将$s{l}_1(A)$加入锁表；将$r_1(A)$传递至数据库。
  2. 第I部分接收事务T2的$r_2(A)$动作，同上。
  3. 第I部分接收事务T1的$r_2(B)$动作，同上。
  4. 第I部分接收事务T1的$r_1(B)$动作，同时该锁可能升级的警示信息到达调度器，调度器第I部分因此发送$u{l}_1(B);r_1(B);$动作序列给第II部分。第II部分查锁表得知此时**B仅有其他事务的共享锁，故允许为其授予更新锁。**随后将$r_1(B)$传递至数据库。
  5. 第I部分接收事务T1的$w_1(B)$动作，由于发生写动作，此时调度器将更新锁升级为排他锁，并发出动作序列$x{l}_1(B);w_1(B);$.然而，第II部分通过查锁表知此时**B有其他事务的(共享)锁，故拒绝了事务T1授予排他锁的请求。**此动作因此被推迟，第II部分将该动作存储起来等待后续执行。
  6. 第I部分接收第II部分事务T2提交的信息，第I部分释放T2持有的A和B上的锁，随后通知第II部分A和B上的锁已释放。
  7. 第II部分得知A和B上的锁已释放，并发现现在可以获取B上的排他锁，$x{l}_1(B);w_1(B);$ 得以执行。它将此锁加入锁表，并继续最大限度地执行存储的来自T1的动作。这里将$w_1(A)$传递至数据库。
  8. T1被提交，通知调度器第I部分，第I部分将A和B的锁释放。

锁表

锁表的结构

锁表是将数据库元素与有关该元素的封锁信息联系起来的一个关系表，我们可以用二元组的集合来表示：
$$\begin{gathered} \text{Lock table}=\{(x,y)|x\in X,y\in Y\}, \\ \text{where X is a set of database elements, Y is a set of locking infomations.} \end{gathered}$$
自然地，我们想到这个表可以用一个散列表来实现，使用数据库元素（地址）作为散列码。任何未被封锁的元素不在表中出现，故表的大小只与被封锁的元素的个数有关，而与数据库元素的个数无关。

封锁信息的数据结构

我们考虑使用共享-排他-更新封锁模式的封锁信息结构，伪代码如下所示：

typedef struct LockingInfo {
    int groupMode; // 组模式
    bool waiting;  // 等待位
    List locks;    // 锁列表
}

typedef struct Lock {
    Tran transactionName; // 事务名
    Mode mode;            // 封锁模式 {S,X,U}
    boolean wait;         // 是否等待？
    Tnext tnext;          // 同一事务的表项链接,将同一事务的所有项链接起来
    Lock next;            // 下一表项,将该数据库元素对应的所有事务链接起来
}

对于二元组$(A,L)$，在共享-排他-更新封锁模式中，我们分析其封锁信息：

• groupMode:表示事务申请A上的一个新锁时所面临的最苛刻的条件。对于一个封锁请求，我们可通过比较该请求与目前组模式来决定授予/拒绝封锁请求。规则为：

  (a) S：表示被持有的只有共享锁。

  (b) U：表示有更新锁和若干共享锁。

  © X：表示只有一个排他锁，没有其它的锁。

• waiting:为true表明至少有一个事务在等待A上的锁。

• locks:表示包含当前在A上持有锁或等待锁的事务的链表。每个列表元素包含的有效信息为：

  • transactionName:持有锁或等待锁的事务名称。
  • mode:该锁的模式。
  • wait:该事务是持有锁还是在等待锁。
  • tnext:将本事务的所有项链接起来，在事务提交或中止的时候会用到，以使得我们能比较容易地找到需要释放的所有锁。
  • next:列表下一个元素。

封锁与解锁的处理

封锁请求的处理

我们考虑事务T请求A上的锁。若A没有锁表项，说明A上无锁，我们为其创建一个锁表项。若A有锁表项，我们就通过groupMode来决定锁的授予情况。若groupMode为

• S(共享锁)：可授予共享锁和更新锁。若T的请求为共享锁，则可授予；若T的请求为更新锁，则groupMode改为U，并授予更新锁。
• U(更新锁)：无法授予其它锁（除同一事务自身申请与U锁相容的锁），因此T的请求被拒绝，而在列表中加入T申请的锁，并修改waiting=true。
• X(排他锁)：与更新锁情况一致。

不管锁是否被授予，新的列表项通过tnext和next字段链接起来。调度器可以直接从锁表(LockingInfo)获取所需信息而不需要查看锁的链表(locks)。

解锁请求的处理

我们考虑事务T请求A解锁。我们按如下步骤进行：

1. 查找A的锁的链表(locks)，删除与事务T有关的元素。

2. 判断T持有的锁与组模式是否相同。若

   2.1 不同(例如T持有S锁，组模式为U锁)，那么不需要改变组模式（这是因为组模式永远持有”最强的“锁,如果与组模式不同，一定是T持有的锁较弱）。

   2.2 相同，那么不得不检查整个链表以找出新的锁模式。若T持有的锁为

   ​ 2.2.1 共享锁(S)：需要判断是否有其它事务持有共享锁，新的组模式被设为S或暂时置空。若被置空，需判断是否有等待中的锁。若 无，则将A从锁表中删除（我们永远不会看到组模式为”nothing“的情况，因为此情况下该元素既无锁也没有锁请求，锁表中不应该存 在该项）；若有，进行第3步。下同。

   ​ 2.2.2 更新锁(U)：由于事务只能持有一个更新锁，该锁被释放时，新的组模式被设为S或被置空。

   ​ 2.2.3 排他锁(X)：我们知道不会有其它锁，新的组模式暂时被置空。

3. 若waiting=true，说明有等待中的锁准备被授予。我们有以下几种策略来授予新锁：

   (a) 先来先服务(First-come-first-served)。

   (b) 共享锁优先(Priority to shared locks)。

   © 升级优先(Priority to upgrading)。

数据库元素的层次

我们主要关注在数据中存在树结构时出现的两个问题：

1. 第一类树结构是可封锁元素的层次结构。可封锁的数据库元素既包括较大的元素（例如关系）也包括较小的元素（例如容纳关系中几个元组的块，或单个元组）。我们需要不同粒度的锁加在其上。该类结构在存储层面是嵌套关系，例如关系R包含元组。
2. 第二类树结构是本身就组织为树这种数据结构的数据，例如B-树索引。我们可以将B-树的结点看作数据库元素，然而，仅使用上述封锁模式的并发控制算法性能较低，需要引入一种新的方法。该类结构在存储层面是树关系，需要通过父结点访问子结点。

可封锁元素

本节我们讨论第一类树结构：可封锁元素的层次结构。

多粒度的锁

在上文中，数据库元素是一个抽象的概念，而不是一个具体的表示。不同操作系统用不同大小的数据库元素封锁，例如元组、页或块，以及关系。

我们举例说明有些场景下使用较小粒度的锁较好，有些场景则不然。

场景	适用锁的粒度	描述
银行数据库	较小（页或块）	如果将关系作为数据库元素，并且因此对整个关系只使用一个锁，则系统只能允许极少的并发。比较好的方案是仅对单独的页或数据块上锁，这样一来，就可以同时更新数据位于不同页上的账户信息，提高了并发度。
文档数据库	较大（整个文档）	文档可能不时地被编辑，但大多数事务将检索整个文档。如果我们使用粒度较小的锁，例如图片、语句或单词，只会增加不必要的开销。而比较明智的方案是将整个文档作为数据库元素，由于大多数事务是只读的，封锁只是为了避免读一个正在编辑中的文档。

还有一些应用既能使用大粒度锁又能使用小粒度锁，但应避免非可串行化行为。

警示锁

解决管理不同粒度锁这一问题的方法牵涉另一种锁类型，称为警示锁（warning lock）。这样的锁在数据库元素形成嵌套或层次结构时很有用。例如由关系->块->元组组成的层次结构中，

1. 关系是最大的可封锁元素。
2. 每个关系由一个或多个块或页组成，每个块或页上存储了关系的元组。
3. 每个块包含一个或多个元组。

警示协议

在数据库元素的层次上管理锁的规则由警示协议构成，它既包括普通（ordinary）锁又包括警示（warning）锁。我们描述普通锁是S和X时的封锁模式，而警示锁将通过在普通锁前加前缀I（意为”意向，intention to“）表示。

警示协议（warning protocol）的规则为：

1. 要在任何元素上加上S或X锁，我们必须从层次结构的根开始。
2. 如果我们处于我们将要封锁的元素的位置，则不需要进一步查找。我们请求该元素上的S或X锁。
3. 如果我们希望封锁的元素在层次结构中更靠下，那么我们在这一结点上加一个警示锁（IS或IX）。当前结点上的锁被授予后，我们继续向适当的子结点（其子树包含我们希望上锁的结点）行进。接下来我们适当地重复步骤2和3，直到达到我们需要的结点。

我们同样要定义在加入警示锁的封锁系统的相容性矩阵：

我们可以这样理解：

1. 若数据库元素X上有意向锁，则表示事务会读或写X的部分元素（而不是全部元素）。
2. 若数据库元素X上有读或写锁，则表示事务会读或写X的全部。
3. 在不同的意向锁同时存在时，虽然有可能发生冲突，但我们允许其在更低层次解决冲突，在该层次予以授予。
4. 在意向锁和读写锁同时存在时，如有可能发生冲突，那么就拒绝后请求的锁。

我们考虑上述相容性矩阵。对第1行，先有IS锁，表明会读X的某一部分，此时后请求的意向锁均予以授予；读锁不会产生冲突，也予以授予；而写锁会导致冲突，则被拒绝。同理，后3行也适用于上述规则。

意向锁的组模式

在前述封锁模式（例如共享-排他-更新）中，我们注意到锁是有”优势的“，即只要有可能同时将数据库元素以M或N方式封锁，我们说M优于（dominates）N，如果

• N在行或列上有否，M在对应行或列的位置上有否。

对于共享-排他-更新（SXU）封锁模式的相容性矩阵

	S	X	U
S	是	否	是
X	否	否	否
U	否	否	否

无论从行来看，还是列来看，只要U在某一项有否，X必定有否，那我们就说X优于U，因其授予的条件更苛刻。同理，U优于S。我们有X>U>S。

由于优势的锁总是授予条件更苛刻，所以有优势锁的好处是我们可以**用一个组模式(groupMode)概括多个锁的效果，**从而使得调度器仅需查看锁表就可以获取所需信息，而不需要扫描锁的链表。

然而，加入意向锁的封锁模式存在了互相不优于对方的锁，例如S和IX。此外，一个数据库元素可能同时持有S和IX，只要它是同一事务申请的（我们没有理由拒绝由同一事务申请的不同锁，因为不存在冲突）。事务可能申请这两个锁，如果它希望读取整个元素并写入部分元素。那么，没有一个锁模式能概括这种情况。此时，我们可以设想另一种封锁方式SIX，它的行和列除IX外均为否（本质上对行和列做”与&“操作）。如果一个事务有S和IX方式的锁而没有X方式的锁时，封锁方式SIX将充当其组模式。

事实上，如果我们组合任意两种锁，假设为XU锁，那么就相当于对X和U的行、列做”与&“操作：
$$\begin{gathered} \text{XU row}=\text{(No,No,No)}\&\text{(No,No,No)}=\text{(No,No,No)}; \\ \text{XU col}=\text{(No,No,No)}\&\text{(Yes,No,No)}=\text{(No,No,No)}; \end{gathered}$$
那么，XU是与U等价的锁，故我们在此意义下也可认为$X\ge U$(X优于U)。

利用上述规则，我们来看共享-排他-增量封锁模式的相容性矩阵

	S	X	I
S	是	否	否
X	否	否	否
I	否	否	是

可以看出S与I互相不优于对方。但当我们组合两个锁SI时，发现其行列均为”否“，这表明SI与X等价。那么，在数据库元素持有S和I锁时，我们就可以用X来表示其组模式。

考虑两个事务作用于同一个关系的例子。设事务T1读关系R的A=a字段，事务T2写A=b字段。那么，加锁顺序为

• 事务T1对R加IS锁，随后得到2个R的元组t1,t2，为其加S锁
• 事务T2对R加IX锁（IS与IX相容），随后得到1个R的元组t3，为其加X锁

幻象与插入的正确处理

当事务创建一个可封锁元素的新的子元素时，有时候可能出错。问题在于我们只能封锁已经存在的项，封锁并不存在但以后可能被插入的数据库元素没有简单的方法。

对于两个事务T1和T2，以及关系R：T1查询R上D元素的个数，T2写入一个D元素$D_3$；T1和T2均写入数据库元素X；R上原有D元素为$D_1,D_2$。

我们考虑如下调度：
$$r_1(D_1);r_1(D_2);w_2(D_3);w_2(X);w_1(L);w_1(X);$$
其中$D_1,D_2,D_3$均是关系R上的元组。$w_2(D_3)$表示事务T2插入一条元组。$w_1(L)$表示事务T1读取到的D元素的个数。那么，在警示协议下，该调度是合法的：

• 事务T1对R加IS锁，对$D_1,D_2$加S锁
• 事务T2对R加IX锁，插入一条元组$D_3$

上面的调度不是可串行化的，因为

1. X具有T1写入的值而不是T2，因而(T1,T2)调度不等价
2. 由于原调度读取到的L值为2，而(T2,T1)调度下读取到的值为3，故也不等价

上述例子的问题是，关系R有一个幻象(Phantom)元组，该元组应该被上锁却没有上锁,因为在获得锁时它还不存在(T1读时若存在，则有S锁)。但是，有一种避免幻象发生的简单办法：**我们必须将元组的插入或删除看作整个关系上的写操作。**这样一来，上述例子中T2必须获取R上的X锁，这与T1在R上的IS锁不相容，那么就会被延迟，直到T1提交或中止之后执行。

树协议

本节我们讨论第二种树结构：本身即为树的数据。这里树的结点没有形成基于包含关系的层次。在一定程度上，数据库元素是不相交的片段，但到达结点的唯一方式是通过其父结点，B-树就是这样一个例子。

基于树封锁的动机

我们考虑B-树索引，这一系统中将单个结点(即块)看作可封锁数据库元素。结点是正确的封锁粒度，因为将更小的片段看作元素不会带来任何好处，而将整个B-树看作一个数据库元素(粒度较大)阻止了在使用锁时通过构成本节主题的机制所能获得的那一类并发。

在PostgreSQL中，使用一种称为B-link tree的数据结构作为索引，支持并发控制算法。其中每个结点均为一个内存块，填充了尽可能多的叶子结点。

注意到，若我们使用标准的诸如共享-排他-更新封锁模式，并且使用两阶段封锁，那么B-树的并发使用几乎是不可能的。原因在于，每个使用索引的事务必须从封锁B-树的根结点开始。如果事务是2PL的，那么在它不能解锁根，直到它获得B-树结点和其它数据库元素上所有需要的锁。此外，由于原则上任何插入或删除的事务可能最终重新B-树的根，事务至少需要根结点上的一个更新锁，或更新锁不能获得时的一个排他锁。因此，任何时刻都只有一个非只读事务能访问B-树。

但是，在大多数情况下，我们几乎可以立即推断B-树结点不会被重写，例如：

• 插入单个元组，子结点不满时。
• 删除单个元组，使得子结点的键和指针大于最小值。

因此，一旦事务移动到根的子结点并发现未改变根时，我们释放根上的锁是有益的。同样适用于B-树任何内部结点上的锁。不幸的是，提早释放根上的锁会违背2PL，因此我们不能确定访问B-树的几个事务的调度是可串行化的。解决方法是为访问像B-树这样的树结构数据的事务采用专门的协议。这一协议违背2PL，但使用访问元素必须沿树向下这样一个事实来保证可串行性。

访问树结构数据的规则

树协议：对树结构加锁的限制构成了树协议。

我们假设只有一种锁，封锁请求为 $l_i(X)$ （这一思路可以推广到其它任何封锁方式集合），并且事务是一致的，调度是合法的，但事务上没有2PL要求。对锁的限制为：

1. 事务的第一个锁可以在树的任何结点上。
2. 只有事务当前在父节点上持有锁时才能获取后续的锁。
3. 结点可以在任何时候解锁。
4. 事务不能对一个它已经解锁的结点重新上锁，即使它在该结点的父结点上仍持有锁。

下面是一个基于树协议的封锁模式的例子：

设有树结构数据

和三个事务T1,T2,T3。其中T1从A开始读写ABCD，T2从B开始读写BE，T3从E开始读写EF。那么，可能的调度为

T1	T2	T3
$l_1(A);r_1(A);$
$l_1(B);r_1(B);$
$l_1(C);r_1(C);$
$w_1(A);u_1(A);$ 注意到，此时BC的锁均已获取，且T1后续不再修改A，则我们可以释放A上的锁
$l_1(D);r_1(D);$
$w_1(B);u_1(B);$
	$l_2(B);r_2(B);$
		$l_3(E);r_3(E);$
$w_1(D);u_1(D);$
$w_1(C);u_1(C);$
	$l_2(E)\text{Denied}$
		$l_3(F);r_3(F);$
		$w_3(E);u_3(E);$
	$l_2(E);r_2(E);$
		$w_3(F);u_3(F);$
	$w_2(B);u_2(B);$
	$w_2(E);u_2(E);$

T1不是2PL事务，而T2和T3是。在这种锁协议下，该事务是可串行化的。

证明

我们证明如下命题：

树协议在调度中锁涉及的事务上必然包含一个串行顺序。

为证明此命题，定义先后次序为：如果在调度S中，事务Ti和Tj封锁同一个结点，而Ti先封锁该结点，我们就说

$T_i{<}_S{T}_j$。

在上述例子中，调度S表明如下先后访问关系：

• T1较T2先访问B。
• T3较T2先访问E。

那么，调度S的优先图为

由于调度S的优先图无环，则其是可串行化的。等价的可串行化调度为(T1,T3,T2)或(T3,T1,T2)。

引理1：若两事务有几个二者都要封锁的元素，则这些元素被封锁的顺序相同。

Proof：我们考虑两个事务T1,T2，它们封锁两个或更多共同的项。首先，每个事务封锁的元素形成一颗树元素的集合，并且两个事务封锁的元素的交集也是一颗树。我们找出它们都需要封锁的元素，并假设T1先封锁这棵树的根。这些元素按任意一种封锁顺序(即T1实际封锁的顺序)排序：$X_1,X_2,...,X_n$，其中$X_1$为最高的元素(根)，排在前面的元素为后面元素的祖先结点(也包括父结点)。那么，基于上述树协议，对该元素及接下来需要封锁的元素$X_1,X_2,...,X_n$，T2总是会慢一步封锁。否则，假设T2先一步封锁了$X_i(1<i\le n,i=1$是显然矛盾的)，那么，T2在封锁$X_i$时要先获得其父结点$X_j(1\le j<i)$的锁，这是因为只有父结点加锁后才能为子结点加锁。这样层层向前推进，直到根结点$X_1$，即T2先于T1封锁了$X_1$，这与T1先于T2封锁$X_1$矛盾！至此我们证明了，若T1先封锁$X_1$，则T1总是会先封锁$X_i(1<i\le n)$。那么，我们也就确定了这棵树的封锁顺序，即由根出发到叶子节点的某个排序。∎

引理2：对事务$T_1,T_2,...,T_n$，若$T_i$在$T_j$前封锁根，那么$T_i$在$T_j$前封锁每一个$T_i$与$T_j$都要封锁的点，即$T_i{<}_S{T}_j$。

**Proof：**根据引理1易证。∎

接下来我们证明本节开始的命题，而该命题等价于遵循树协议、由上述定义的先后次序的优先图中无环。

Proof：我们对于树的结点个数n用数学归纳法证明。

BASIS：若n=1，即只有一个结点，那么事务封锁根的顺序即是串行调度的顺序。

INDUCTION：如果树中不止一个结点，那么我们要考虑根的每一个子树，在该子树中封锁一个或多个结点的事务集合。注意到，封锁根的事务可能属于多个子树，但不封锁根的事务仅属于一个子树。

不妨设根为R，子树个数为k，子树由$S{T}_1,S{T}_2,...,S{T}_k$表示。由归纳假设可知，封锁任一子树结点的所有事务都有一个串行的顺序。我们只需将不同子树的串行顺序混合起来。

设封锁R的事务的顺序构成的序列为$S_R$,封锁子树$S{T}_i(1\le i\le k)$的事务的串行顺序为$S_i$。那么，一定有
$$S_{ij}:=S_i\cap S_j\subset S_R,\forall 1\le i,j\le k.$$
由引理2可知，$S_{ij}$ 中的事务封锁 $T_i$ 或 $T_j$ 每一个公共结点的顺序都与它们封锁根的顺序一样，$S_{ij}$中的任意两个事务不可能在 $S_i,S_j$ 中出现的顺序不同。具体地，我们假设 $T_1,T_2\in S_i\cap S_R,T_2,T_3\in S_j\cap S_R$，且T1,T2,T3在 $S_R$ 中的顺序(封锁根的顺序)为$(T_1,T_2,T_3)$.那么，$T_1,T_2$封锁$S{T}_i$的顺序为$(T_1,T_2)$，$T_2,T_3$封锁$S{T}_j$的顺序为$(T_2,T_3)$。也就是说，出现在$S_R$中的事务的顺序决定了任一子树的封锁顺序。我们可以从封锁根的事务开始建立所有事务的一个串行顺序，将这些事务按正确顺序排放后，我们把不封锁根的那些事务按照某周与其子树的串行顺序不冲突的顺序散布其中。∎

使用时间戳的并发控制

接下来，我们考虑封锁以外的，某些系统中用来保证事务可串行性的两种方法：

1. 时间戳(Timestamping)：为每个事务分配一个”时间戳“。记录上次读和写每个数据库元素的事务时间戳，将这些数值与事务时间戳比较，根据事务的时间戳以确保串行调度等价于实际事务的调度。
2. 有效性确认(Validation)：当要提交一个事务时，检查事务和数据库元素的时间戳；这一过程被称为事务的”有效性确认“。根据事务的有效性确认时间排列的串行调度必须等同于实际调度。

这两种方法是乐观的(optimistic)，因为它们都假设没有非可串行化行为发生，并且只在违例很明显时进行修复。与此相反，所有封锁方法假设如果不预防事务陷入非可串行化行为中，事情就会出错。乐观的方法不同于封锁的地方在于，当确实发生问题时唯一的补救措施是中止并重启试图参与非可串行化行为的事务。与此相反，封锁调度器推迟事务，但不中止它们。

时间戳

为了使用时间戳作为并发控制的方式，调度器需要赋给每个事务T一个唯一的数：

• $TS(T)$：事务T的时间戳。

**时间戳必须在事务首次通知调度器自己将开始时按升序发出。**产生时间戳的两种方法是：

1. 使用系统时间作为时间戳，只要调度器操作不会快到在一个时钟周期内给两个事务赋予时间戳。
2. 调度器维护一个计数器。每当一个事务开始时，计数器加1，而新的值成为该事务的时间戳。这种方法中，时间戳与时间无关，但它们具有任何时间戳产生系统都需要的重要性质：开始较晚的事务比开始较早的事务的时间戳要高。

不管使用什么时间戳产生方法，调度器都必须维护当前活跃事务及其时间戳的一张表。

为了使用时间戳来作为并发控制的方式，我们需要将每个数据库元素X与两个时间戳以及一个附加位联系起来：

1. $RT(X)$：X的读时间，它是读X的事务中最高的时间戳。
2. $WT(X)$：X的写时间，它是写X的事务中最高的时间戳。
3. $C(X)$：X的提交位。该位为真，当且仅当最近写X的事务已经提交。这一位的目的是为了避免出现事务T读另一事务U所写数据然后U中止这一的情况。T脏读”未提交数据“这一问题肯定有可能导致数据库状态变得不一致，而任何调度器都需要防止脏读的机制。

Although commercial systems generally give the user an option to allow dirty reads, as suggested by the SQL isolation level READ UNCOMMITTED.

事实上不可实现的行为(Physically Unrealizable Behaviors)

调度器的体系结构和规则保证：

• 调度器假设事务的时间戳顺序也是它们看起来执行的串行顺序。

因此，调度器的任务除了分配时间戳和更新数据库元素的RT,WT,C之外，还要检查是否在读写发生的任何时候，如果每个事务在对应其时间戳的那一刻瞬时执行的话，事实上发生的事可能会发生。如果不是，我们说这一行为是事实上不可实现的。

Thus the job of the scheduler, in addition to assigning timestamps and updating RT, WT, and C for the database elements, is to check that whenever a read or write occurs, what happens in real time could have happened if each transaction had executed instantaneously at the moment of its timestamp. If not, we say the behavior is physically unrealizable.

可能发生的问题有两类：

1. 过晚的读：事务T试图读取数据库元素X，但X的写时间表明X现有的值是T理论上执行以后写入的：即$TS(T)<WT(X)$。

   T start -> U start -> U writes X -> T reads X (READ TOO LATE)

   解决办法是中止T。

2. 过晚的写：事务T试图写数据库元素X。但是，X的读时间表明另外的某个事务应该读到T写入的值但却读到另外的某个值：即$WT(X)<TS(T)<RT(X)$。

   T start -> U start -> U reads X -> T writes X (WRITE TOO LATE)

   这里$RT(X)>TS(T)$，表明X已经被一个理论上在T后执行的事务U所读(而U理论上应该读T写入的值)，而$WT(X)<TS(T)$说明X写入的时间在事务开始之前(其它事务写入的)，表明在X被U读取时X的值未被覆盖。

   解决办法是取消T将其值写入X这一任务，使U能读它。

脏数据问题

提交位的设计是为了帮助解决一类问题。其中一个问题是脏读。我们先看一个例子：

U start -> U writes X -> T start -> T reads X (DIRTY READ) -> U aborts

其中，事务T读X，而X是最近被U写入的。U的时间戳小于T的时间戳，且在实际中T的读发生在U的写之后，因此这一事件看来在事实上是可实现的。但是，有可能在T读U写入的值之后，事务U中止。因此，最好将T的读推迟到U提交或中止之后。我们可以断定U尚未提交，因为提交位C(X)为假。

另一个潜在的问题是：

T start -> U start -> U writes X -> T writes X -> T commits -> U aborts

这里时间戳比T晚的事务U先写X。当T试图写时，正确的行动是什么都不做。显然，没有其他事务V应当读取T的X的值却读到U的值，因为如果V试图读取X，它将因为过晚的读而中止：

T start -> V start -> U start -> U writes X -> V reads X (READ TOO LATE) -> T writes X …

以后对V执行的读将需要U的X值或一个更晚写入的X值，而不是T的值。这个想法，即写操作在写时间更晚的写操作已发生时可以被跳过(写时间更晚的写操作会覆盖原写操作，故原写操作无需执行，如上例中的T writes X不应被执行)，被称为Thomas写法则。

但是，Thomas写法则有一个潜在的问题。如果像上述例子那样，U后来中止了，那么它的X应该被删掉，并且前一个值和写时间应该被恢复，这里X应该恢复到T写入的值。由于T已提交，且我们跳过了T的写，那么此时的损坏已来不及修复。

我们可以采取一个简单有效的策略来解决上述问题，它基于下面假设的基于时间戳的调度器所具有的能力：

• 当事务T写数据库元素X时，写是”尝试性的(tentative)“，且在T中止时可以被撤销。随后提交位$C(X)$被设为假，调度器保存X的旧值和原有WT(X)的一个拷贝。

基于时间戳的调度器

我们现在可以概括调度器为了保证不会发生事实上不可实现的事所必须遵守的规则。

首先，作为对来自事务T的读写请求的反应，调度器的选择为：

(a) 同意请求。

(b) 中止T并重启具有新时间戳的T(中止再加上重启常称为回滚)。

© 推迟T，并在以后决定是中止T还是同意请求(如果请求是读并且此读可能是脏的)。

时间戳调度器规则

1. 假设调度器收到请求$r_T(X)$:

   (a) $TS(T)\ge WT(X)$：此读是事实上可实现的。

   ​ i. $C(X)$为真，同意请求。如果$TS(T)>RT(X)$，置$RT(X):=TS(T)$（此处有更新读时间之意）；否则不改变$RT(X)$。

   ​ ii. $C(X)$为假，推迟T直到$C(X)$为真或写X的事务中止。

   (b) $TS(T)<WT(X)$：此读是事实上不可实现的。回滚T；即中止T并以一个新的更大的时间戳重启它。

2. 假设调度器收到请求$w_T(X)$:

   (a) $TS(T)\ge RT(X),TS(T)\ge WT(X)$：此写是事实上可实现的并且必须执行，而无需考虑$C(X)$的值，这是因为即使前一个$WT(X)$回滚了，但因在事务$T$之前，故事务$T$的写覆盖了该值，最终结果没有改变。

   ​ i. 为X写入新值。

   ​ ii. 置$WT(X):=TS(T)$（此处有更新写时间之意）。

   ​ iii. 置$C(X):=\text{false}$（此处事务尚未提交）。

   (b) $TS(T)\ge RT(X),TS(T)<WT(X)$：此写是事实上可实现的，但X中已经有一个更晚的值。

   这里”更晚的值“，指的是在事务T之后开始的事务U进行了写操作，即$TS(T)<TS(U)$，此时$WT(X)$被更新为U开始的时间$TS(U)$，从而有$TS(T)<WT(X)$这种情况出现。另外，当事务U事实上在T之后发生时，调度器认为U对X的写入覆盖了T对X的写入。若此时U提交，即$C(X)$为真，那么就忽略T对X的写操作。

   ​ i. 如果$C(X)$为真，那么前一个X的写已经提交，我们只需忽略$T$的写；我们允许$T$不对数据库做任何改变而继续进行下去（Thomas写法则）。

   ​ ii. 如果$C(X)$为假，那么我们需要推迟T直到$C(X)$为真或写X的事务中止（可规避Thomas写法则的问题，若等待直到$C(X)$为真，可如i一样忽略T的写；若写X的事务中止，那么T执行写操作）。

   © $TS(T)<RT(X)$：此写是事实上不可实现的，而T必须被回滚。

3. 假设调度器收到提交T的请求：它必须（使用调度器维护的一个列表）找到T所写的所有数据库元素X，并置$C(X):=\text{true}$。如果有任何等待X提交的事务（从调度器维护的另一个列表中找到），这些事务被允许继续进行。

4. 假设调度器收到中止T的请求：假设调度器收到了中止T的请求，或决定像在1b和2c那样回滚，那么任何等待T所写元素X的事务必须重新尝试读或写，看这一动作在T的写被中止后是否合法。