CMU 15-445 -- Two Phase Locking - 14

CMU 15-445 -- Two Phase Locking - 14

引言

本系列为 CMU 15-445 Fall 2022 Database Systems 数据库系统 [卡内基梅隆] 课程重点知识点摘录，附加个人拙见，同样借助CMU 15-445课程内容来完成MIT 6.830 lab内容。

上节课介绍了通过 WW、WR、RW conflicts 来判断一个 schedule 是否是 serializable 的方法，但使用该方法的前提是预先知道所有事务的执行流程，这与真实的数据库使用场景并不符合，主要原因在于：

1. 请求连续不断。时时刻刻都有事务在开启、中止和提交
2. 显式事务中，客户端不会一次性告诉数据库所有执行流程

因此我们需要一种方式来保证数据库最终使用的 schedule 是正确的 (serializable)。不难想到，保证 schedule 正确性的方法就是合理的加锁 (locks) 策略，2PL 就是其中之一。

Lock Types

DBMS 中锁通常被分为两种，Locks 和 Latches，二者的主要区别如下：

本节关注的是事务级别的锁，即 Locks。Locks 有两种基本类型：

• S-LOCK：共享锁 (读锁)
• X-LOCK：互斥锁 (写锁)

二者的兼容矩阵如下表所示：

如下图所示：DBMS 中有个专门的模块，lock manager，负责管理系统中的 locks，每当事务需要加锁或者升级锁的时候，都需要向它发出请求，lock manager 内部维护着一个 lock table，上面记录着当前的所有分配信息，lock manager 需要根据这些来决定赋予锁还是拒绝请求，以保证事务操作重排的正确性和并发度。

在这里插入图片描述

一个典型的 schedule 执行过程如下所示：

在这里插入图片描述

但仅仅在需要访问或写入数据时获取锁无法保证 schedule 的正确性，举例如下：

在这里插入图片描述

事务 T1 前后两次读到的数据不一致，出现了幻读，这与顺序执行的结果并不一致。于是我们需要更强的加锁策略，来保证 schedule 的正确性。

Two-Phase Locking

2PL 是一种并发控制协议，它帮助数据库在运行过程中决定某个事务是否可以访问某条数据，并且 2PL 的正常工作并不需要提前知道所有事务的执行内容，仅仅依靠已知的信息即可。

2PL，顾名思义，有两个阶段：growing 和 shrinking：

在这里插入图片描述

在 growing 阶段中，事务可以按需获取某条数据的锁，lock manager 决定同意或者拒绝；在 shringking 阶段中，事务只能释放之前获取的锁，不能获得新锁，即一旦开始释放锁，之后就只能释放锁。下图就违背了 2PL 的协议：

在这里插入图片描述

2PL 本身已经足够保证 schedule 是 serializable，通过 2PL 产生的 schedule 中，各个 txn 之间的依赖关系能构成有向无环图。但 2PL 可能导致级联中止 (cascading aborts)，举例如下：

在这里插入图片描述

由于 T1 中止了，T2 在之前读到 T1 写入的数据，就是所谓的 “脏读”。为了保证整个 schedule 是 serializable，DBMS 需要在 T1 中止后将曾经读取过 T1 写入数据的其它事务中止，而这些中止可能进而使得其它正在进行的事务级联地中止，这个过程就是所谓的级联中止。

事实上 2PL 还有一个增强版变种，Rigorous 2PL，后者每个事务在结束之前，其写过的数据不能被其它事务读取或者重写，如下图所示：

在这里插入图片描述

Rigorous 2PL 可以避免级联中止，而且回滚操作很简单。

下面我们以转账为例，对 Non-2PL、2PL 和 Rigorous 2PL 分别举例：

在这里插入图片描述

• T1：从 A 向 B 转账 100 美元
• T2：计算并输出 A、B 账户的总和

Non-2PL 举例：

在这里插入图片描述

由于 T2 读到了 T1 写到一半的数据，结果不正确，输出的是 1900。可以看到它的并发程度很高。

2PL 举例：

在这里插入图片描述

2PL 输出的结果正确，为 2000，同时可以看到它的并发程度比 Non-2PL 的差一些，但看着还算不错。

Rigorous 2PL 举例：

在这里插入图片描述

Rigorous 2PL 输出的结果同样是正确的，可以看到它的并发程度比 2PL 更差一些。

回到 universe of schedules，cascading aborts 也是 schedule 的一个特性，它与 serializable 并无直接关系，因此将 cascading aborts schedule 考虑进来，可以得到下图：

在这里插入图片描述

Deadlock Detection & Prevention

2PL 无法避免的一个问题就是死锁：

在这里插入图片描述

死锁其实就是事务之间互相等待对方释放自己想要的锁。解决死锁的办法也很常规：

• Detection：事后检测
• Prevention：事前阻止

Deadlock Detection

死锁检测是一种事后行为。为了检测死锁，DBMS 会维护一张 waits-for graph，来跟踪每个事务正在等待 (释放锁) 的其它事务，然后系统会定期地检查 waits-for graph，看其中是否有成环，如果成环了就要决定如何打破这个环。

waits-for graph 中的节点是事务，从 Ti 到 Tj 的边就表示 Ti 正在等待 Tj 释放锁，举例如下：

在这里插入图片描述

当 DBMS 检测到死锁时，它会选择一个 “受害者” (事务)，将该事务回滚，打破环形依赖，而这个 “受害者” 将依靠配置或者应用层逻辑重试或中止。这里有两个设计决定：

1. 检测死锁的频率
2. 如何选择合适的 “受害者”

检测死锁的频率越高，陷入死锁的事务等待的时间越短，但消耗的 cpu 也就越多。所以这是个典型的 trade-off，通常有一个调优的参数供用户配置。

选择 “受害者” 的指标可能有很多：事务持续时间、事务的进度、事务锁住的数据数量、级联事务的数量、事务曾经重启的次数等等。在选择完 “受害者” 后，DBMS 还有一个设计决定需要做：完全回滚还是回滚到足够消除环形依赖即可。

Deadlock Prevention

Deadlock prevention 是一种事前行为，采用这种方案的 DBMS 无需维护 waits-for graph，也不需要实现 detection 算法，而是在事务尝试获取其它事务持有的锁时直接决定是否需要将其中一个事务中止。

通常 prevention 会按照事务的年龄来赋予优先级，事务的时间戳越老，优先级越高。有两种 prevention 的策略：

• Old Waits for Young：如果 requesting txn 优先级比 holding txn 更高则等待后者释放锁；更低则自行中止
• Young Waits for Old：如果 requesting txn 优先级比 holding txn 更高则后者自行中止释放锁，让前者获取锁，否则 requesting txn 等待 holding txn 释放锁

举例如下：

在这里插入图片描述

无论是 Old Waits for Young 还是 Young Waits for Old，只要保证 prevention 的方向是一致的，就能阻止死锁发生，其原理类似哲学家就餐设定顺序的解决方案：先给哲学家排个序，遇到获取刀叉冲突时，顺序高的优先。

Hierarchical Locking

上面的例子中所有的锁都是针对单条数据 (database object)，如果一个事务需要更新十亿条数据，那么 lock manager 中的 lock table 就要撑爆了。因此需要有一些手段能够将锁组织成树状/层级结构，减少一个事务运行过程中需要记录的锁的数量。

当我们说一个事务获取了“锁”时，意味着该事务对数据库中的某些资源获得了特定类型的访问控制。锁用于确保事务能够有序地访问共享资源，防止冲突并维护数据一致性。

锁的范围取决于被锁定的资源的粒度：

1. 在属性级别：对属性进行锁定意味着事务限制了对表中某个特定数据属性（列）的访问。这种类型的锁是最细粒度的，它仅影响一个元组（行）中的单个属性。
2. 在元组级别：对元组进行锁定意味着事务限制了对整个表中某个特定行的访问。这确保了在锁定保持期间其他事务不能修改或读取该特定元组。
3. 在页面级别：对页面进行锁定意味着事务限制了对包含多个元组的数据块的访问。锁覆盖了页面中的所有元组。
4. 在表级别：对表进行锁定意味着事务限制了对整个表的访问。这确保了对整个表的独占访问，防止其他事务在锁定期间访问任何部分。

高效的锁管理目标是让事务获得所需的最少数量的锁，同时仍然保持数据完整性和防止冲突。锁管理是数据库管理系统中非常重要的部分，它确保了并发操作的正确性和数据的一致性。

在这里插入图片描述

对于复杂的操作和多个资源的情况，可能涉及到多个锁的获取。在数据库管理系统中，通常会使用锁树（Lock Tree）来管理这些锁。对于叶节点（即最终的资源），可能需要获取 Exclusive Lock 和 Shared Lock，具体取决于具体操作。对于较高层级的节点，可以使用特殊的意向锁（Intention Lock）来表示事务对子节点的意图。

intention locks

意向锁是一种在数据库管理系统中用于优化锁管理的机制。当事务需要在树状结构中的某个节点上获取共享锁或独占锁时，可以首先尝试获取该节点上的意向锁。意向锁表示了在该节点下可能存在其他子节点上已经获得的共享或独占锁。

通过使用意向锁，事务可以避免在整个子树上逐一检查是否已经获得了相关的锁，从而减少锁管理的开销，提高并发控制的效率。如果某个节点上已经存在意向锁，那么数据库系统可以推断出在该节点的子节点上已经有相应的锁，而无需进一步检查。

意向锁本身不直接影响数据的读写，它只是用于提供关于锁状态的信息，以优化锁的获取和释放过程。通过这种优化，数据库系统可以更高效地处理并发操作，确保事务的正确执行和数据的一致性。

意向-共享锁（Intention-Shared，IS）：

• 意向-共享锁表示在较低级别节点上已经显式获取了共享锁。如果一个事务获取了意向-共享锁，那么说明在该节点的子节点上已经获得了共享锁。其他事务可以获取该节点的共享锁，但不能获取独占锁。

意向-独占锁（Intention-Exclusive，IX）：

• 意向-独占锁表示在较低级别节点上已经获取了独占锁或共享锁。如果一个事务获取了意向-独占锁，那么说明在该节点的子节点上已经获得了独占锁或共享锁。其他事务可以获取该节点的共享锁，但不能获取独占锁。

Shared + 意向-独占锁（Shared+Intention-Exclusive，SIX）：

• SIX 锁 = S 锁 + IX 锁。对目标表加上 SIX 锁后，S 锁这一属性保证了别的事务能知道我们要读取目标表的所有 record，它们就不会去并发地更新任意的 record；
• IX 锁这一属性保证了别的事务能知道我们要更新目标表的一部分 record，它们就不会去并发地读取所有的 record。

这里是引用

意向锁的兼容性:

在这里插入图片描述

加锁协议

在数据库管理系统中，每个事务都会在数据库层次结构的最高级别上获取适当的锁：

• 要在节点上获取 S（共享锁）或 IS（意向-共享锁），事务必须至少持有其父节点上的 IS（意向-共享锁）。
• 要在节点上获取 X（独占锁）、IX（意向-独占锁）或 SIX（共享+意向-独占锁），事务必须至少持有其父节点上的 IX（意向-独占锁）。

这些规则确保了并发事务在数据库层次结构中获取适当的锁来保持数据的一致性和正确性。通过在最高级别上获取适当的锁，数据库系统可以避免冲突和数据不一致的问题，并保证事务能够正确地执行。同时，意向锁（IS 和 IX）的使用可以优化锁管理，减少不必要的锁检查，提高并发控制的效率。

两级继承体系加锁示例:

在这里插入图片描述

在这里插入图片描述

示例二: 存在多个事务同时操作时

• T1 : Scan R and update a few tuples.
• T2 : Read a single tuple in R.
• T3 : Scan all tuples in R.

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

锁升级

当获取太多低级锁时，锁升级动态请求粗粒度锁。这可以减少Lock Manager需要处理的锁请求数量。

最佳实践

我们通常无需在事务中手动设置锁，有时候我们需要给DBMS一些提示，让他来帮助我们提升并发度。

当需要对数据库执行一些较大改动时，显式指定锁或许是个不错的选择。

显式加锁的相关SQL语句

如果我们需要显示对某个表加锁，可以使用如下这些方式，这部分实现并不属于SQL标准一部分:

• Postgres/DB2/Oracle Modes: SHARE, EXCLUSIVE
• MySQL Modes: READ, WRITE

在这里插入图片描述

如何我们想在查询的时候，对满足要求的元组加上互斥锁，可以采用如下方式:

在这里插入图片描述

当然，也可以设置加上共享锁:

• Postgres: FOR SHARE
• MySQL: LOCK IN SHARE MODE

小结

2PL封锁协议用在大部分的DBMS中。

能够自动在多个事务中协调，并为每个事务生成一个正确的执行序列，可以通过如下方式:

• Locks + protocol(2PL,SS2PL,…)
• Deadlock detection + handling
• Deadlock prevention

本节对应教材PDF