> For the complete documentation index, see [llms.txt](https://wandersofb.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wandersofb.gitbook.io/blog/cmu15445/note/two-phase-locking-concurrency-control.md).

# Two-Phase Locking Concurrency Control

上一节说到 DBMS 在解决 Isolation 时会有并发冲突，此时需要 schedule 来调节事务之间的序列，最明显的是 conflict serializability 和 view serializability。

我们需要一种方式来实现正确的 execution schedule 而且不需要提前知道整个 schedule。

### Transaction Locks

DBMS 使用 **锁** 来动态的生成 execution schedule 来让事务是可序列化的，而且不需要提前知道事务的读写情况。这些锁帮助数据库当它们要多次读写时的并发访问。DBMS 会实现一个 lock manager 来决定一个是事务是否获取锁，它会提供一个全局的视野来看系统内部发生了什么。

有两种基本的锁（类似于读写锁）：

* **Shared Lock (S-LOCK):** 允许多个事务读相同的对象。如果一个事务持有了共享锁，那么其他事务也可以持有。
* **Exclusive Lock (X-LOCK):** 独占锁只允许一个事务修改对象。这个锁会阻止其他的事务来修改或者读这个对象。

DBMS 内部的 lock manager 会管理内部 lock table 那个事务持有那个锁，那个事务等待获取那个锁。

### Two-Phase Locking

两阶段锁是一种悲观协议（pessimistic），它使用锁来决定一个事务是否应该访问那些在数据库里的对象。此协议并不需要提前知道事务中的所有的查询。阶段的对象指的时事务。

**Phase #1– Growing:** 在增长阶段，每个事务都需要从 lock manager 中获取它需要的锁。由 lock manager 来决定是否给予事务相应的锁。 **Phase #2– Shrinking:** 在事务进入增长阶段之后释放第一个锁的瞬间他就进入了缩小阶段，在缩小阶段事务只允许释放锁，不允许获取锁。

![](https://585989843-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwvMe53hGZfVBc8lZpyoq%2Fuploads%2Fgit-blob-88068ed2d6a1a1c749869cf90624d2c72e5bbc09%2Ffdsafevds.png?alt=media)

2PL 是充分满足 conflict serializability，它生成的调度的依赖图是无环的。但是它是可能会出现 *cascading aborts*，当一个事务 abort 的时候，另一个使用了它所修改对象的事务必须要回归，这就造成了浪费工作。

![](https://585989843-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwvMe53hGZfVBc8lZpyoq%2Fuploads%2Fgit-blob-d9971d54931a026737afbb9db59015ef33252c05%2Ftwo-phase-lock.png?alt=media)

#### Strong Strict Two-Phase Locking

强严格两阶段锁其实就是多加了一个限制，只有当事务提交的时候才会释放锁。

![](https://585989843-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwvMe53hGZfVBc8lZpyoq%2Fuploads%2Fgit-blob-cc8482f49354440069c01f573ac97b2a463d3d1d%2Fstrong-strict-lock.png?alt=media)

这个方法的优势是不会出现级联中断，然而古尔丹，代价是什么？更少的吞吐量。这是一个更悲观的协议。

![](https://585989843-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwvMe53hGZfVBc8lZpyoq%2Fuploads%2Fgit-blob-9652496e5f2878eac73dfb5ffc0ab45ea718a762%2Funiverse-of-schedule.png?alt=media)

### Deadlock Handling

死锁是事务之间为了获取锁而形成了环形等待，都在等待彼此释放。有两种办法可以解决死锁：检测和阻止。

**Approach #1: Deadlock Detection**

为了检测死锁，DBMS 创建了 *waits-for* 图，其中事务是结点，如果 $$T\_i$$ 等待 $$T\_j$$ 释放一个锁那么存在一条从 $$T\_i$$ 到 $$T\_j$$ 的有向边。

系统会创建一个后台线程定时的检测是否出现了环，会做出决定怎么来破坏环。

当 DBMS 检测到死锁的时候，他会选择一个受害者事务，杀死它，来解决环。受害者事务要么重新启动，要么依据应用怎么调用它。

DBMS 会考虑多个事务属性来选择 victim：

1. By age (newest or oldest timestamp).
2. By progress (least/most queries executed).
3. By the *#* of items already locked.
4. By the *#* of transactions needed to rollback with it.
5. *#* of times a transaction has been restarted in the past (to avoid starvation).

在选择一个受害者事务中断之后，DBMS 可以选择回滚多远的事务改变，它可以要么回滚整个事务，或者回归到足够破坏死锁。

**Approach #2: Deadlock Prevention**

取而代之的让事务去获取任何它们需要的锁然后解决死锁，死锁预防是在它们造成死锁的之前来阻止死锁的出现，MYSQL 是这样做的。 一旦有事务要获取一个死锁，那么 DBMS 会杀死形成死锁的事务的其中一个。为了实现这个，事务会被分配一个时间戳属性，老的事务有更高的优先级。

有两种方法在死锁预防下杀死事务：

* **Wait-Die (“Old Waits for Young”):** 如果 requesting 事务比 holding 事务有着更高的优先级，那么它等待，否则它中断。
* **Wound-Wait (“Young Waits for Old”):** 如果 requesting 事务比 holding 事务有着更高的优先级，那么 holding 事务中断并且释放锁，否则 requesting 事务等待。

### Lock Granularities（锁粒度）

如果一个事务要更新 1 亿的元组，那么他要向 DBMS 的 lock manager 申请 1 亿次锁。这显然是很慢的，但是我们又必须需要获取锁来更新数据库的元数据。

为了避免这种开销，DBMS 可以使用一种 **lock hierarchy** 来允许事务获取一些更粗粒度的锁。例如它可以获取一个表的锁而不是表内所有的元组的锁。当一个事务获取对象的锁的时候，它已经隐式的获取了它的子对象的所有的锁。

![](https://585989843-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwvMe53hGZfVBc8lZpyoq%2Fuploads%2Fgit-blob-ffffa62869e57797487f56d6615a238cd33014d3%2Flock-of-hierarchy.png?alt=media)

**Intention locks** 允许更高层级的结点来获取 shared or exclusive mode。如果一个结点是在 intention mode，那么显式，它的锁是被应用在了子孙树的低级层级。

* **Intention-Shared (IS):** 表示使用共享锁在较低级别进行显式锁定。
* **Intention-Exclusive (IX):** 使用排他锁或共享锁指示较低级别的显式锁定。
* **Shared+Intention-Exclusive (SIX):** 以该节点为根的子树在共享模式下显式锁定，并且显式锁定在较低级别使用独占模式锁定完成。