CMU 15-445/645-笔记-17-两阶段锁

2023-02-24 23:28 作者:dengluzhanghao 0人读过 | 我要投稿

> 草，这期没有 Andy 了

## 上期回顾

## Observation

在一个真实的系统中，需要一种方式在运行时能做到，保证所有的 Schedule 的执行都是正确的，并且不需要提前知道整个 Schedule 的情况

当事务提交给数据库执行时，数据库并不会得到该事务的所有的 Schedule

没法去查看数据库 client 要做什么，以及预测它们的操作是否是 Serializable 的，所以就需要一种协议，一种能并行执行这些事务的系统，同时还需要保证隔离性

所以就需要锁，之前提到过悲观锁和乐观锁，今天要研究的就是两阶段锁

## 锁的执行

在能执行 R(A) 之前，去 Lock 管理器那里拿到 A 的锁，该 Lock 管理器会去判断你是否有权去访问这个 tuple，它维护了一些关于哪个持有锁的元数据，并在系统中强制使用锁协议

接着，T2 开始执行

假设目前处于一个单线程的环境，同一时间我们只会执行其中一个事务

T2 目前要获取到这个锁，因为它最终要在下面执行 R(A) 和 W(A)，但它被 Lock 管理器拒绝，因为 T1 已经拿着这把锁了

那么 T2 唯一能做的事情就是等待

然后 T1 执行 W(A) 和 R(A)，最后把锁释放，那么 Lock 管理器就会告诉 T2 可以拿锁了，最后做完 T2 要做的事情就把锁释放掉

## 课程目标

- 锁类型

- 两阶段锁

- 死锁原因

- 层级锁(通过这个，可以减少在系统中使用锁的数量，更高效的使用锁)

- 隔离级别不在本节课讨论范围之内

## Locks vs. Lathes

latch 是用来保护线程所访问的当前数据结构所在的内存不被瞎乱写

lock 是用来保护数据库中的逻辑结构，比如数据库表中那些 tuple，防止事务彼此间发生冲突

通过使用 latch，能避免编程时遇到的死锁问题，比如 B+ Tree 的访问

## 基本锁类型

- 共享锁(读操作)

- 独占锁(写操作)

有点类似之前提到过的 Read Latch 和 Write Latch

在某个对象已经有了一个 Shared Lock 的情况下，不能再去发放该对象的 Exclusive Lock

## 锁的执行

Lock 管理器会基于它内部的元数据来决定是否有权去拥有这个 Lock

Lock 管理器不一定会对持有该 Lock 的时间长度有所限制，所以这个应当取决于事务

当事务完成时，取决于该事务是否要去释放这个 Lock

例子

事务负责去获取和释放锁，Lock 管理器负责分发这些 Lock

但是这里会出现不可重复读的情况

## 并发控制协议

这里要用的就是两阶段锁，它允许数据库系统始终以保证 Confilict Serializable Schedule 的情况下来分发 Lock，因为现在没必要去限制系统中的并行性，可以尝试在同一时间执行多个事务

在不生成那些 Unserializable Schedule 或者违反隔离性要求的情况下，希望能获取到事务方面的高吞吐量

### 两阶段锁

1. Growing 阶段

允许该事务去获取它需要的那个 Lock，而这个 Lock 是 Lock 管理器给的

事务执行完操作后，它会去释放这个 Lock，告诉 Lock 管理器，用完这个 Lock 了

2. Shrinking 阶段

上述过程之后，该事务就会处于 Shrinking 阶段，然后该事务就不再允许它获取更多的 Lock 了

用图的方式表示就是如下

一个违反两阶段锁的例子就是如下

因为这个事务释放了一部分 Lock，然后它又去获取了一些 Lock

例子

如果遵循两阶段锁这个协议，就会得到 Conflict Serializable 的 Schedule，保证依赖图是无环的

但是单独使用两阶段锁并不保证不会遇上脏读的情况，可能会遇上 Cascading Abort

### Cascading Aborts

T2 读取了一个来自 T1 的值，因为 T1 这个事务被中止了，它并没有被提交，所以实际上它并不在系统中

因为 T1 被中止了，现在也必须将 T2 中止，因为 T2 读取的那个值并不再生效

因为一个事务的中止会导致另一个事务的中止，所以需要在数据库写的回滚逻辑会越来越复杂

而由于 T2 已经执行了一堆复杂的逻辑，并对系统化执行了一大堆写操作，而后要中止这个 T2 事务，所以也就浪费了大量的时间

### 两阶段锁 Observations

有些 Schedule 是 Serializable 的，但在两阶段锁中并不允许

用到了锁，就会略微限制系统的并发性

当遇上脏读的情况时，可能会导致 Cascading Aborts

怎么解决这个问题呢?

使用 Strong Strict Two Phase Locking (强严格两阶段锁)

死锁的情况也会遇到，所以需要一种检测机制来解决这个问题

### 强严格两阶段锁

当事务执行完，要进行提交时，才去释放锁

Growing 阶段，会根据需要不断地获取锁，直到提交时才去释放这些锁，这可以防止遇上跨事务时所遇到的脏读问题以及 Cascading Aborts 问题

注意上图中，所有的锁都会在事务结束时释放掉，所以严格意义上来讲这里并没有 Shrinking Phase 阶段

strict 这个单词对于并发控制来说拥有特定的意义，直到提交事务时，该事务所做的修改才会被系统中其他执行的事务看到

这能简化中止逻辑，因为那些中止的事务必须要将它们所操作的值变回原样，这样的话，就无须担心系统中这些事务会去读取那些未提交的值了。否则，它们就得保存它们自己的元数据，或者通过某种方法回滚它们之前所做的修改

例子

不使用两阶段锁的例子(会得出一个错误的输出结果)

在一开始时，A B 两个账户中分别都有 1000 $

T1 已经拿到了 A 的 Exclusive Lock，并执行 R(A)，因为接下来需要执行 A = A - 100

T2 想要获取 A 的 Shared Lock，因为 T2 后面要执行 A + B，所以它没法此时获取到这个 Lock，它只能等待

T1 释放 Lock 之后，T2 拿到了 A 对应的 Shared Lock，并执行 R(A)，然后 T2 释放 Lock

> 注意这里并没有使用到两阶段锁

T2 也会获取 B 对应的 Shared Lock，因为要执行 R(B)，所以 T1 需要等待

最终，T2 释放了这个 Lock，T1 拿到了 B 对应的 Exclusive Lock，执行了 B = B + 100，释放 Lock 并提交。但是此时 A + B 计算为 1900，因为它读取到了一个不一致的状态。它读取到了 T1 已经完成的部分工作结果，这意味着 T1 已经将该信息泄漏到系统的其他地方

使用两阶段锁的例子

在 T1 进入 Shrinking 阶段之前，它去获取了 B 对应的 Exclusive Lock，T2 原地等待获取它需要的那些 Lock。

T1 对 B 的操作执行完毕，才会释放 A 对应的 Lock

那么这个就会出一个正确的输出结果

另一个使用两阶段锁的例子

T2 需要等待一整个 T1 执行的时间，严格两阶段锁有效地控制了事务的有序执行

也就是说，事务会去获取你所需要用到的所有锁并一直持有，直到事务要到提交的时候才做释放

用上图来说，就是保证 T2 中存在的任何会引起冲突的操作都会被强制按照某种顺序执行

## Schedules 的包含关系

## 死锁问题

死锁其实就是事务间彼此依赖成环，它们都在等待对面释放它们所需要的锁

如图所示，现在这 2 个事务都在等待获取彼此手上的 Lock

那么就需要某种方式来打破这种僵局

1. 检测

2. 预防

### 检测

系统会使用一个后台线程来进行死锁检测，简单来说，就是去查看 Lock 管理器中的元数据，构建一个 waits-for 图，图中每一个节点就是一个事务，每一条线会指向另一个节点，该节点持有着另一端那个节点想要获取的锁

例子

T3 想获取 A 的 Exclusive Lock，但是 T1 已经拿到了 A 对应的 Shared Lock，于是死锁了

### 处理死锁

简单来说，就是选择一个 Victim(牺牲者)，干掉它

选择一个事务，然后将它回滚，回滚多少内容取决于具体实现

可以只回滚部分查询来释放锁，以此移除掉死锁

但是在系统中需要权衡构建这些 waits-for 图的频率，因为是开的后台程序去做的检测，如果频率过高，很可能会浪费 CPU 资源来构建这些图，并且也可能检测不出什么死锁

所以需要考虑的是，在不检测死锁的情况下，陷入死锁状态的可接受时长是多少

另一种处理方式就是 Victim Selection

干掉某个 Victim 时，可以去看下时间戳最小的那个事务，因为到最后会有一个环，选一个干掉就好了

也可以去查下这个 Victim 已经完成的工作量，或者它已经执行的查询数量

同样也可以查下这个 Victim 它拿了多少个 Lock

然后就是如果遇上 Cascading Abort 问题，需要看下要回滚的事务数量

还有一种处理方式就是 Rollback Length

可以最小程度去中止某个事务，即仅回滚该事务中的个别查询所做的修改

或者缓慢地释放掉部分锁

在 MySQL 中，可以通过

```

SET GLOBAL innodb_lock_wait_timeout = 10;

```

来设置检测死锁的频率

当 MySQL 尝试去获取锁时，如果发现其中存在着死锁的情况，它会尝试重启事务

在 PostgreSQL 中，可以通过

```

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

```

设置该事务的隔离级别为 Serializable

在数据库中有一些可调参数，可以通过调整它们来改变数据库系统寻找死锁的主动性

### 预防

如果能够阻止死锁发生，那么也就不需要去构建 waits-for 图了，也就意味着不需要这个后台任务了，也就不需要杀死进程或者事务了

一种简单的做法是根据时间戳来分配优先级，比如较老的事务有更高的优先级

另一种做法是较年轻的事务有更高的优先级

例子

T1 的优先级比 T2 高，但 T2 先拿到锁，所以 T1 是较老的那个事务

- Wait-Die: T1 会等待获取这个锁

- Wound-Wait: T1 会干掉 T2，T2 需要进行重启

T1 还是比 T2 先执行，T1 拥有的时间戳较老，T1 的优先级更高， T1 会先拿到这个锁

- Wait-Die: T2 会被干掉

- Wound-Wait: T2 会一直等待

如果能以某种顺序去获取 Lock，就会让死锁的解决变得更高效，甚至可以完全避开死锁问题

为了避免死锁问题，简单来说就发放一种类型的 Lock

当一个事务重启时，它的优先级(时间戳)是什么

是和原来一样，为啥

为了不能让事务陷入 Starvation 的状态，所以当事务重启时，要确保它依然使用的是和之前相同的时间戳

## Observation

因为每次事务都要做这种锁管理的方式，所以不可能将所有的这些就交给 Lock 管理器，因为这样做在遇到要管理更新很多个 tuple 的场景时，开销就很大了

那么怎么做合适呢?

就是往系统里面引入某种 hierarchy(分层)，或者是使用不同粒度的 Lock

## Lock 保证

那么 Lock 的粒度怎么分呢?

可以在 tuple、page、table 上使用 Lock，如果要对一个 table 上 10 亿条 tuple 进行更新操作，那么有没有可能，只需要对整个 table 用一个 Exclusive Lock 就行了

本质上就是通过这种分层的模型来减少，在 Lock 管理器中的需要操作的 Lock 的总数量的访问

### Lock 分层

如图所示，可以系统的不同层面使用这些 Lock

数据库系统以这种层次结构来表示往它里面插入的那些表和 tuple

例子

上图中，因为银行账户余额正在进行修改，所以需要 Exclusive Lock 和 Shared Lock

Intention Lock 是在数据库分层这个树上的较高层处使用的，以此来提示其他事务在该系统的分层的较低层面做什么事情，它会试着增加系统的并行性

### Intention Locks

对于其他事务来说，Intention Lock 是一种提示

如果在这个树上有一个 Intention Shared Lock，那么子树的根节点就是在这个节点上，而该节点的下方某处会有一个显式的 Shared Lock，对于 Intention Exclusive Lock 也是如此，在子树根节点下方某处，会有一个显式的 Exclusive Lock

另外一种 Lock 类型就是 Shared + Intention-Exclusive 模型

在这个节点上有一个显式的 Shared Lock，在子树下方的所有东西上，都会有一个与之对应的 Shared Lock。而在子树下方的某处地方，也有一个显式的 Exclusive Lock

基本上就是在某个 tuple 上使用 Exclusive Lock，然后在整个 table 上使用一个 Shared Lock，这样就可以做到，可以读取表中的所有的值，但只会去更新其中某个值

### 兼容性

### Lock 协议

为了获取一个 Shared Lock，至少要在父节点处加一个 Intention-Shared Lock

对于 Exclusive Lock/ Intention-Exclusive / Shared + Intention-Exclusive Lock 也是类似的，至少要在父节点处加一个 Intention-Exclusive Lock

例子(这是一个两层结构的系统)

T1 开始执行，在 Tuple1 上加一个 Shared Lock，以此来读取 Tuple1 的内容，但是在这之前会先在父节点上加一个 Intention-Shared Lock

这里会作为一个提示，在该节点下面，会有一个显式的 Shared Lock

接着 T2 开始执行，它想要更新 Tuple n 的内容，并且要在这个上面加上一个显式的 Exclusive Lock

然后就是在父节点上加上 Intention Exclusive Lock，然后再在 Tuple n 上加上 Exclusive Lock

另一个例子

T1 要去读取所有的 tuple，并对其中一个 tuple 进行更新，所以它会去获取一个 Shared + Intention-Exclusive Lock，意味着它给整个 table 加了一个 Shared Lock，那么就可以读取该 table 中所有 tuple 的所有属性，而 Shared + Intention-Exclusive Lock 的意思是，它至少会去更新下方其中某一个 tuple(在这个例子中是 tuple n)