事务与并发 II
1 导言
在最后一个注释中，我们介绍了作为ACID性质之一的隔离概念。让我们在这里重新审视我们的定义：
- 隔离：每个Xact的执行与其他执行隔离。实际上，DBMS将交错许多XACT的动作，而不是按顺序依次执行。DBMS将确保每个Xact的执行就像它自己运行一样。
本说明将详细介绍DBMS如何能够在保证隔离的同时交错许多事务的操作。
2.两阶段锁
什么是锁，为什么它们有用？锁基本上允许事务读取和写入数据。例如，如果事务T1正在从资源A读取数据，则需要确保没有其他事务同时修改资源A。因此，想要读取数据的事务将请求在适当资源上的共享（S）锁，而想要写入数据的事务则将请求在相应资源上的排他（X）锁。只有一个事务可以对资源持有独占锁，但许多事务可以对数据持有共享锁。两阶段锁定（2PL）是一种确保数据库使用冲突可串行化调度的方案。2PL的两个规则是：
交易必须在读取前获得S（共享）锁，在写入前获得X（独占）锁。
在释放任何锁后，事务无法获取新锁——这是通过锁定实现可串行化的关键！
这样做的问题是它不能防止级联中止。例如
T1更新资源A，然后释放对A的锁定。
T2从A读取。
T1中断。
在这种情况下，T2也必须中止，因为它读取了未提交的值A。
为了解决这个问题，我们将使用严格的两相锁定。严格的2PL与2PL相同，只是当事务完成时所有锁一起释放。
3 锁管理
现在我们知道了锁的用途和类型。我们将了解锁管理器1如何管理这些锁和解锁（或获取和释放）请求，以及它如何决定何时授予锁。
LM维护一个哈希表，该哈希表以被锁定资源的名称为键。每个条目包含一个授权集（一组授权锁/持有每个资源锁的事务）、锁类型（S或X或我们尚未引入的类型）和等待队列（由于与已授权的锁冲突而无法满足的锁请求队列）。见下图：
当锁请求到达时，锁管理器将检查授权集中或等待队列中的任何Xact是否需要冲突锁。如果是，请求者将被放入等待队列。如果不是，则请求者被授予锁，并被放入授权集。
此外，Xacts可以请求锁升级：这是具有共享锁的Xact可以请求升级到独占锁的情况。锁管理器将在队列的前面添加此升级请求。
下面是一些如何处理队列的伪代码；请注意，它并没有明确说明在促销等情况下应该做什么，但这是一个很好的概述。
请注意，此实现不允许队列跳过。当请求在队列跳过实现下到达时，我们首先检查是否可以根据资源上持有的锁授予锁；如果无法授予锁，则将其放在队列的后面。释放锁并处理队列时，授予与当前持有的锁兼容的任何锁
有关队列跳过和伪代码的示例，请参阅附录。然而，它依赖于您对多粒度锁定的理解，因此请确保先阅读第7节以理解示例。
4 死锁
我们现在有了一个锁管理器，如果存在冲突锁，它将请求者放入等待队列。但是，如果T1和T2都持有资源上的S锁，并且都尝试升级到X，会发生什么？T1将等待T2释放S锁，以便它可以获得X锁，而T2将等待T1释放S，以便它能够获得X锁。此时，两个事务都无法获得X锁，因为它们正在等待对方！这称为死锁，一个XACT循环等待锁被彼此释放。
4.1避免
解决死锁的一种方法是尽量避免陷入死锁。我们将根据年龄分配Xact的优先级：现在-开始时间。如果$T_i$想获得$T_j$持有的锁，我们有两种选择：
- Wait-Die: 如果$T_i$具有更高的优先级，则$T_i$等待$T_j$；否则$T_i$将中止
- Wound-Wait: 如果$T_i$具有更高的优先级，$T_j$中止；否则，$T_i$会等待
4.2检测
虽然我们在上面的方法中避免了死锁，但我们最终中止了许多事务！相反，我们可以尝试检测死锁，如果发现死锁，则中止死锁中的一个事务，以便其他事务可以继续。
我们将通过创建和维护“等待”图来检测死锁。如果满足以下条件，该图对于每个Xact将有一个节点，并且从$T_i$到$T_j$有一条边，如果：
- $T_j$ 持有资源X的锁
- $T_i$ 尝试获取资源X上的锁，但是$T_i$ 在拿到期望的锁之前， $T_j$ 必须释放在资源X上的锁
例如，下图具有从T1到T2的边，因为T2获取B上的锁后，T1尝试获取B上冲突的锁。因此，T1等待T2。
如果一个事务$T_i$正在等待另一个事务$T_j$（即，从$T_i$到$T_j$有一条边），则$T_i$不能获取任何新锁。因此，事务 $T_k$ 将不会等待资源X上的 $T_i$，除非 $T_i$ 在开始等待 $T_j$ 之前获得了X上的冲突锁。
考虑下面的示例，同时请记住，调度中只显示锁获取，而不是锁释放。
当$T_2$ 请求一个在资源A上冲突的S锁的时候，从$T_2$ 到 $T_1$ 将连一条边，因为 $T_1$ 持有 X 锁 。当 $T_2$ 等待 $T_1$ 结束资源A的使用的时候，$T_2$ 中的任何操作都不能执行，直到他被移除等待队列。这也是为什么 $T_3$ 在请求B上的S锁时，不用等待 $T_2$ ，因为$T_2$ 在等待$T_1$的过程中从来没有获取到B上的X锁。 同样的，当 $T_3$ 想要获得A上的X锁的时候 ，只用等待 $T_1$ 因为在这个时候只有$T_1$ 在资源 A 上和$T_3$ 有互斥的锁。注意在这个时候$T_2$ 和 $T_3$ 在资源 A 的等待队列里。
我们将定期检查图中表示死锁的循环。如果发现一个循环，我们将在循环中“杀死”一个Xact并中止它以打破循环。
重要提示：“等待”图用于周期检测，与我们之前讨论的冲突依赖关系图（在前一个note中）不同，后者用于确定事务调度是否可序列化。
5 锁粒度
现在我们已经理解了锁定的概念，我们想知道实际锁定什么。是否要锁定包含要写入的数据的元组？还是页面？还是桌子？或者甚至是整个数据库，以便在我们处理数据库时，没有事务可以写入该数据库？正如你所猜测的，我们所做的决定将根据我们所处的情况有很大的不同。
让我们将数据库系统视为以下树：
顶层是数据库。下一级是表，后面是表的页面。最后，表本身的记录是树中的最低级别。
请记住，当我们在一个节点上放置一个锁时，我们也会隐式地锁定它的所有子节点（直观地说，可以这样想：如果您在一个页面上放置了一个锁，那么您就隐式地在所有记录上放置了锁，并阻止其他任何人修改它）。因此，您可以看到我们希望如何能够向数据库系统指定我们真正希望将锁放在哪个级别；它允许我们在树的不同级别上放置锁。
我们将有以下新的锁定模式：
IS：更精细的粒度的S意向锁。
IX：更精细的粒度d额X意向锁。注意：两个事务可以在同一资源上放置一个IX锁——它们在这一点上没有直接冲突，因为它们可以在两个不同的子级上放置X锁！因此，我们将其留给数据库管理器，以确保它们不会在同一节点上放置X锁，同时允许在同一资源上使用两个IX锁。
- SIX：等价于同时施加了S锁和IX锁。如果我们希望防止任何其他事务修改较低级别的资源，但希望允许它们读取较低级别，则这很有用。在这里，我们说在这个级别上，我要求共享锁；现在，任何其他事务都不能对该子树中的任何内容声明独占锁（但是，它可能会对未被该事务修改的内容声明共享锁，即我们不会将X锁置于其上的内容。这留给数据库系统处理）。
有趣的是，请注意，任何其他事务都不能在具有SIX锁的节点上声明S锁，因为这将在整个树上放置两个事务的共享锁，这将阻止我们修改该子树中的任何内容。唯一与SIX锁兼容的锁是IS。
以下是兼容性矩阵：；将轴解释为事务T1和事务T2。例如，考虑条目X，S–这意味着T1不可能在资源上持有X锁，而T2在同一资源上持有S锁。NL代表无锁。
5.1 多粒度锁定协议
每个Xact从层次结构的根开始。
要在节点上获得S或IS锁，必须在父节点上保持IS或IX。
要在节点上获得X或IX，必须在父节点上保持IX或SIX。
必须以自下而上的顺序释放锁。
还实施了2阶段和锁兼容性矩阵规则
协议是正确的，因为它相当于在层次结构的叶级直接设置锁。