上节课介绍了通过 WW、WR、RW conflicts 来判断一个 schedule 是否是可串行化 (serializable) 的方法，但使用该方法的前提是预先知道所有事务的执行流程，这与真实的数据库使用场景并不符合，主要原因在于：
- 请求连续不断。时时刻刻都有事务在开启、中止和提交
- 显式事务中，客户端不会一次性告诉数据库所有执行流程
因此我们需要一种方式来 保证数据库最终使用的 schedule 是正确的 (serializable)。不难想到，保证 schedule 正确性的方法就是合理的加锁 (locks) 策略，2PL 就是其中之一。
1 Transaction Locks
我们之前提到 DBMS 中的两种锁 Locks 与 Latches，二者的区别：
| Locks | Latches | |
|---|---|---|
| Separate | User transactions | Threads |
| Protect | Database Contents | In-Memory Data Structures |
| During | Entire Transactions | Critical Sections |
| Modes | Shared, Exclusive, Update, Intention | Read, Write |
| Handle deadlock by | Detection & Resolution Waits-for, Timeout, Aborts | Avoidance Coding Discipline |
| Kept in | Lock Manager | Protected Data Structure |
本节关注的是事务级别的锁，即 Locks。Locks 有两种基本类型：
- S-LOCK：共享锁 (读锁)，允许多个事务在同一时间读取同一对象。
- 若一个事务持有一个 S 锁，那么另一个事务也可以获得相同的 S 锁。
- X-LOCK：互斥锁 (写锁)，允许一个事务修改一个对象。
- 这个锁对任何其他锁都是不兼容的。每次只有一个事务可以持有排他性锁。
相容性矩阵：
| S-LOCK (shared) | X-LOCK (exclusive) | |
|---|---|---|
| S-LOCK (shared) | ✅ | ❌ |
| X-LOCK (exclusive) | ❌ | ❌ |
DBMS 中有个专门的模块 Lock Manager，负责管理系统中的 locks。每当事务要加锁/升级锁/释放锁时，都要向它发出请求。
lock manager 内部维护着一个 lock table，上面记录着当前的所有分配信息，lock manager 需要根据这些来决定赋予锁还是拒绝请求，以保证事务操作重排的正确性和并发度。
但仅仅在需要访问或写入数据时获取锁无法保证 schedule 的正确性，我们需要更强的加锁策略：
2 Two-Phase Locking
两阶段封锁协议 (2PL) 是一种悲观的并发控制协议，它使用锁来帮助数据库在运行过程中决定某个事务是否可以访问某条数据，并且 2PL 的正常工作并不需要提前知道所有事务的执行内容，仅仅依靠已知的信息即可。
2PL，顾名思义，有两个阶段：
Phase #1– Growing: 事务可按需获取某条数据的锁，lock manager 授予/拒绝这些锁请求。
Phase #2– Shrinking: 事务只能释放之前获取的锁，不能获得新锁。即一旦开始释放锁进入 Shrinking 阶段，之后就只能释放锁。
2PL 本身已经足够保证 schedule 是可串行化的 (serializable)，通过 2PL 产生的 schedule 中，各个 txn 之间的依赖关系能构成有向无环图。但 2PL 可能导致 级联中止 (cascading aborts)：当一个事务中止 (abort) 时，会导致另一个事务也必须回滚。这导致了工作的浪费。
2PL 优点：保证了 schedule 的可串行化。
2PL 缺点：有些潜在的 schedule 是可序列化的，但是 2PL 不允许它执行，一定程度限制了并发。
2PL 存在的问题：
- 仍存在脏读 —— Solution：强二阶段封锁协议 (Strong Strict 2PL, 又称 Rigorous 2PL)
- 可能导致死锁 —— Solution：死锁检测和预防
2.1 Strong Strict Two-Phase Locking
Strong Strict 2PL 是 2PL 的变体，不仅要求封锁是两阶段的，还要求事务持有的所有锁必须在事务提交后才能一次性释放。
这个要求能保证未提交事务所写的任何数据在该事务提交前，都以排他模式封锁，从而防止其他事务读取到这些数据。由此避免了级联中止。
优点：不会产生级联中止；DBMS 可通过将被修改的 tuple 恢复为原始值，来 abort 事务。
缺点：产生了更悲观的 schedule，限制了并发。
? 下面我们以转账为例，对 Non-2PL、2PL 和 Rigorous 2PL 分别举例：
-- T1: 从 A 向 B 转账 100 元--
BEGIN
A = A - 100
B = B + 100
COMMIT
-- T2: 计算并输出 A、B 账户的总和 --
BEGIN
ECHO A + B
COMMIT
Universe of Schedules：\(SerialSchedules ⊂ StrongStrict2P L ⊂ ConflictSerializableSchedules ⊂ V iewSerializableSchedules ⊂ AllSchedules\)
若在 universe of schedules 中考虑级联中止，它是 schedule 的一个特性，与 serializable 并无直接关系。
3 Deadlock Handling
2PL 无法避免的一个问题就是死锁：
死锁：事务之间互相等待对方释放自己想要的锁。
解决死锁的方式有两种：死锁检测 (detection)、死锁预防 (prevention)
3.1 Deadlock Detection
死锁检测是一种事后行为。为了检测死锁，DBMS 会维护一张 waits-for graph，来跟踪每个事务正在等待 (释放锁) 的其它事务，然后系统会定期地检查 waits-for graph 看其中是否有成环，如果成环了，就要决定如何打破这个环。
waits-for graph 中的节点是事务，从 Ti 到 Tj 的边表示 Ti 正在等待 Tj 释放锁，
当 DBMS 检测到死锁时，它会选择一个 "受害者" (事务)，将该事务回滚，打破环形依赖，而这个 "受害者" 将依靠配置或者应用层逻辑重启 (restart) 或中止 (abort)，中止更为常见。
这里有三个决定要设计：
- 检测死锁的频率：检测死锁的频率越高，陷入死锁的事务等待的时间越短，但消耗的 cpu 也就越多。这是个典型的 trade-off，通常有一个调优的参数供用户配置。
- 如何选择合适的 "受害者" (选择受害者的指标)：
- 事务持续时间
- 事务的进度
- 事务锁住的数据数量
- 级联事务的数量
- 事务曾经重启的次数
- 选择完 "受害者" 后，还要决定回滚 txn 的更改的程度：完全回滚 or 回滚到足够消除环形依赖即可。
3.2 Deadlock Prevention
Deadlock prevention 是一种事前行为，采用这种方案的 DBMS 无需维护 waits-for graph，也不需要实现 detection 算法，而是在事务尝试获取其它事务持有的锁时直接决定是否需要将其中一个事务中止。
通常 prevention 会按照事务的年龄来赋予优先级，事务的时间戳越老，优先级越高。有两种 prevention 的策略：
Wait-Die ("Old Waits for Young")：如果 requesting txn 优先级比 holding txn 更高 (老) 则等待后者释放锁；更低则自行中止Wound-Wait ("Young Waits for Old")：如果 requesting txn 优先级比 holding txn 更高 (老) 则后者自行中止释放锁，让前者获取锁；否则 requesting txn 等待 holding txn 释放锁
无论是 Old Waits for Young 还是 Young Waits for Old，只要保证 prevention 的方向是一致的，就能阻止死锁发生，其原理类似哲学家就餐设定顺序的解决方案：先给哲学家排个序，遇到获取刀叉冲突时，顺序高的优先。
当 txn abort 后 restart 时，它的 (新) 优先级是它的原始时间戳，这是为了防止饥饿。
4 Lock Granularities
上面的例子中所有的锁都是针对单条数据 (database object)，如果一个事务需要更新十亿条数据，那么 lock manager 中的 lock table 就要撑爆了。为了避免这种开销，DBMS 可以使用一个锁的层次结构，允许事务在系统中获取更多的粗粒度的锁。当一个事务在这个层次结构中获取一个对象的锁 (显式锁) 时，它就隐含地获取了其所有子对象的锁 (隐式锁)。—— Hierarchical Locking
? 它可以在有 10 亿个 tuple 的表上获取一个锁，而不是获取 10 亿个单独的锁。
这是个并发程度与开销的 trade-off：锁越少，则粒度更粗，开销更少，但并发程度更低；锁越多，则粒度越细，并发程度更高，但开销更大。
Database Lock Hierarchy:
- Database level (Slightly Rare)
- Table level (Very Common)
- Page level (Common)
- Tuple level (Very Common)
- Attribute level (Rare)
意向锁 (Intention Lock)：意向锁允许将更高级别的节点锁定为共享或独占模式，而无需检查所有后代节点。如果节点处于意向模式，则显式锁定在树中的较低级别完成。
- 意向共享锁 Intention-Shared (IS)：若一个节点被加上 IS 锁，则将在树的较低层使用 S 锁进行显式锁定。
- 意向排他锁 Intention-Exclusive (IX)：若一个节点被加上 IX 锁，则将在树的较低层使用 X 或 S 锁进行显示锁定。
- 意向共享排他锁 Shared+Intention-Exclusive (SIX)：若一个节点被加上 SIX 锁，则对以该节点为 root 的树使用 S 锁显示锁定，且将在树的较低层使用 X 锁进行显示锁定。 SIX 锁可理解为 S + IX
相容性矩阵：
| IS | IX | S | SIX | X | |
|---|---|---|---|---|---|
| IS | ✅ | ✅ | ✅ | ✅ | ❌ |
| IX | ✅ | ✅ | ❌ | ❌ | ❌ |
| S | ✅ | ❌ | ✅ | ❌ | ❌ |
| SIX | ✅ | ❌ | ❌ | ❌ | ❌ |
| X | ❌ | ❌ | ❌ | ❌ | ❌ |
多粒度封锁协议：采用?这些锁类型保证可串行性。每个事务 T 按?规则对数据项 Q 加锁：
- 事务 T 要遵循上图所示锁类型相容函数。
- 事务 T 必须先封锁树的根结点，并可加任意类型的锁。
- 仅当 T 对 Q 的父结点具有 IX 或 IS 锁时，T 对结点 Q 可加 S 或 IS 锁。
- 仅当 T 对 Q 的父结点具有 IX 或 SIX 锁时，T 对结点 Q 可加 X、SIX 或 IX 锁。
- 仅当 T 未曾对任何结点解锁时，T 可对结点加锁（即 T 是两阶段的）。
- 仅当 T 当前不持有 Q 的子结点的锁时，T 可对结点Q 解锁。
意向锁有助于提升并发：
- Intention-Shared (IS)：意图以更精细的粒度获取 Slock。
- Intention-Exclusive (IX)：意图以更精细的粒度获取 Xlock。
- Shared+Intention-Exclusive (SIX)：类似同时有 S 和 IX。
锁粒度升级（Lock granularity escalation）：若在锁层级中有太多的锁，则可在更粗粒度级别加 S 或 X 锁来替代。这减少了 Lock Manager 必须处理的请求的数量。
5 Locking In Practice
实践中，通常不会在 txns 中手动设置锁。
有时您需要向 DBMS 提供提示以帮助它提高并发性。 在对数据库进行重大更改时，显式锁也很有用。
显式锁定表 (不属于标准 sql) ：
- Postgres/DB2/Oracle Modes: SHARE, EXCLUSIVE
- MySQL Modes: READ, WRITE
LOCK TABLE <table> IN <mode> MODE; -- Postgres/DB2/Oracle --
SELECT 1 FROM <table> WITH (TABLOCK, <mode>); -- SQL Server --
LOCK TABLE <table> <mode>; -- MySQL --
执行 select，然后在匹配的 tuples 上设置排他锁：
SELECT * FROM <table> WHERE <qualification> FOR UPDATE;
也可以在匹配的 tuples 上设置共享锁：
- Postgres：FOR SHARE
- MySQL：LOCK IN SHARE MODE