CMU 15445 14.二阶段锁定 + homework 4

DBMS包含一个锁管理器，用于决定事务是否可以锁定。 它了解系统内部的最新情况。
•共享锁（S-LOCK）：允许多个事务同时读取同一对象的锁。 如果一个事务持有共享锁，则另一个事务可以获取该共享锁。
•独占锁定（X-LOCK）：允许事务修改对象。 此锁与任何其他锁不兼容。 一次只能有一个事务持有独占锁。

使用锁执行：
1.事务从锁管理器请求锁（或升级）。
2.锁管理器根据其他事务当前持有的锁来授予或阻止请求。
3.当不再需要时，事务释放锁。
4.锁管理器更新其内部锁表，然后把锁给其他等待的事务。

二阶段锁定

两阶段锁定（2PL）是一种悲观的并发控制协议，用于确定是否允许事务访问数据库中的对象。协议不需要知道事务将提前执行​​的所有查询。

image.png
image.png

阶段＃1：膨胀
•每个事务都从DBMS的锁管理器请求它所需的锁。
•锁管理器授予/拒绝锁定请求。
阶段＃2：收缩
•事务在释放第一个锁后立即进入此阶段。
•允许事务仅释放先前获取的锁。它无法在此阶段获得新锁。
就其本身而言，2PL足以保证conflict serializability。它生成precedence graph是无环的。
2个缺点：
但它很容易出现级联中止，即当事务中止并且现在必须回滚另一个事务时，这会导致浪费很多资源。

image.png

还有一些可序列化的潜在计划，但2PL不允许这种计划（锁会限制并发）。

严格的2pl

事务只在完成时释放锁。 确实没有像普通2PL那样shrinking的阶段。
如果事务写入的值在该事务完成之前未被其他事务读取或覆盖，则调度是严格的。
这种方法的优点是DBMS不会导致级联中止。
同时只要把原来的值赋值回去就可以实现abort了。

为什么呢？
我们看一下s2pl的时序图

image.png

再看下abort是怎么做的
先undo，随后记log，然后unlock

image.png

下面要解决的就是2pl 的死锁问题

死锁问题的解决思路分为2种，一种是死锁预防，一种是死锁检测。

image.png
image.png

死锁检测

DBMS 创建 wait-for图：如果事务Ti等待事务Tj释放锁，从Ti到Tj有一条边。系统将定期检查等待图中的环，然后决定如何打破它。
•当DBMS检测到死锁时，它将选择“受害者”事务进行回滚以中断循环。
•受害者事务将重新启动或中止，具体取决于应用程序如何调用它
•选择受害者时需要考虑多个事务属性。没有一个选择比其他选择更好。 2PL DBMS都做不同的事情：
1.按年龄（最新或最旧的时间戳）。
2.按进度（执行的最少/大多数查询）。
3.已锁定的项目数量。
4.通过我们必须用它回滚的＃个事务。
5.过去重启事务的次数
•回滚长度：选择要中止的受害者事务后，DBMS还可以决定回滚事务的更改的距离。可以是整个事务，也可以是足够的操作（部分事务）足以来打破僵局

image.png

死锁预防

当txn尝试获取另一个txn持有的锁时，DBMS会杀死其中一个以防止死锁。
该方法不需要wait-for图或检测算法。

根据时间戳分配优先级（例如，旧的意味着更高的优先级）。
这些方案保证没有死锁，因为在等待锁时只允许一个方向。 当事务重新启动时，其（新）优先级是其旧时间戳。
•Wait-Die（“Old等待Young”）：如果T1具有更高的优先级，则T1等待T2。 否则T1中止
•wound-wait（“Young等待old”）：如果T1具有更高的优先级，则T2中止。 否则T1会等待。

关于死锁检测 和 死锁预防，把作业搞懂 应该就没啥问题了。
https://15445.courses.cs.cmu.edu/fall2018/files/hw4-sols.pdf

粒度锁

如果一个事务要更新十亿个元组，它必须向DBMS的锁管理器询问十亿个锁。
这将是缓慢的，因为我们必须在锁管理器的内部锁表数据结构中获取锁存器。

相反，我们希望使用锁层次结构，允许事务在系统中采用更粗粒度的锁。 为此层次结构中的某些内容获取锁定会隐式获取其所有子项的锁定。

意图锁定允许更高级别的节点以共享或独占模式锁定，而无需检查所有后代节点。 如果节点处于意图模式，则在较低级别进行显式锁定。

•Intention-Shared（IS）：表示使用共享锁在较低级别显式锁定。
•Intention-Exclusive（IX）：表示使用独占锁或共享锁在较低级别显式锁定。
•Shared + Intention-Exclusive（SIX）：以该节点为根的子树在共享模式下显式锁定，显式锁定在低级别使用独占模式锁定。

image.png image.png image.png
image.png
image.png

同样把作业里的QUESTION 3理解清楚就搞清楚这个了。

总结

应用程序通常不会手动设置锁。 但有时它可以为DBMS提供一些提示来帮助它提高并发性：
SELECT ... FOR UPDATE：执行选择，然后在获取的元组上设置独占锁
2PL几乎用于所有DBMS。 它自动提供正确的交错事务操作。
但它必须能够应对死锁的问题。