【CMU 15-445】Lecture 16: Two-Phase Locking Concurrency Control 学习笔记

本节课主要介绍两阶段锁协议。

Transaction Locks

对于并发事务的可串行化，可以使用事务锁实现。事务锁（lock）不同于数据锁（latch），数据锁的目的是保证多线程执行的正确性，事务锁是为了实现多事务执行的可串行性。
两种基本的锁：

• Shared Lock（S-LOCK）：共享锁，可由多个读事务共享
• Exclusive Lock（X-LOCK）：排他锁，只能被一个写事务持有

事务需要从DBMS中的lock manager申请事务锁，且需要满足一些锁协议来保证正确性与可串行性。

Two-Phase Locking

两阶段锁协议（2PL），是一个悲观的并发控制协议。

• Phase One – Growing：在增长阶段，每个事务只会向lock manager申请锁
• Phase Two – Shrinking：当事务释放第一个锁时，就会进入第二个阶段，此后只允许释放锁，不允许申请锁

2PL保证冲突可串行化，因为它保证Lecture15提到的冲突图是无环的。但是2PL会存在两个问题：

• 脏读导致级联中止
• 死锁

级联终止

级联中止（cascading aborts）现象，脏读导致的，如下图所示。该现象可以使用两阶段锁协议的改进版本，严格两阶段锁协议（Strong Strict 2PL）解决。

Strong Strict Two-Phase Locking

严格两阶段锁协议，是两阶段锁协议的变种，它要求事务在提交时再去释放所有锁。这避免了脏读现象的发生，也解决了级联中止问题，但是这个锁协议会减少很多并行度（因为过于悲观了）。

Deadlock Handling

有两种方法可以解决两阶段锁协议中的死锁问题：

• Deadlock Detection：死锁检测
• Deadlock Prevention：死锁预防

Deadlock Detection

可以使用等待图进行死锁检测，当检测到死锁时（图中存在环路时），则系统自动中止某些事务以打破死锁。死锁检测需要权衡检测频率与打破死锁前的等待时间，太频繁会加大负担，不频繁会使得死锁等待时间变久。

Deadlock Prevention

死锁预防的思想是，为每个事务赋予一个时间戳，当一个事务请求一个已被其他事务获取到的锁时，根据当前请求事务的时间戳与持有锁事务的时间戳来决定是否中止某个事务来预防死锁。
有两种方式来预防死锁：

• Wait-Die：当请求事务的时间戳小于持有锁的事务，则请求事务等待；否则请求事务中止
• Wound-Wait：当请求事务的时间戳小于持有锁的事务，则请求事务抢占锁，持有锁的事务中止；否则请求事务等待

Wait-Die保证了等待锁的时间戳顺序是从大到小；Wound-Wait保证了等待锁的时间戳顺序是从小到大；故可以预防死锁。

Lock Granularities

当一个事务想要更新上亿条记录，则它必须请求获取上亿个排他锁，这会增大DBMS的开销，因为向lock manager请求锁也需要时间。
于是，提出了不同粒度的锁，如下图所示，当更新的记录属于同一个表时，可以直接获取该表的锁，表下所有的页面及记录将会被隐式的锁住。

但是，当某个事务只想请求获取一个记录的锁时，它需要顺着该记录向上走，确定走到根（也就是数据库层）的路径上是否有一个祖先节点获取过与申请锁互斥的锁，如果获取过则请求失败，因为该记录已经被隐式的锁住了（且与即将申请的矛盾）。
这种遍历会增大DBMS的开销，因此，提出了Intention lock用于辅助判断能否成功申请锁，包含以下三种：

• Intention-Shared(IS)：表示被锁住的节点的子树中，将有一个节点会获取共享锁
• Intention-Exclusive(IX)：表示被锁住的节点的子树中，将有一个节点会获取排他锁
• Shared+Intention-Exclusive(SIX)：表示被锁住的节点的子树中，所有节点都会获取共享锁，且有一个节点会获取排他锁

它们的兼容性表格如下图所示：

基于层级锁结构与这三种意向锁，假设一个事务想要请求某条记录的共享锁时，它需要先申请路径上所有祖先节点的意向锁，根据兼容性表判断是否可行。就不用反方向再判断一遍啦。