cmu15445 并发控制理论实现-两阶段锁

OBSERVATIONhahhaha

• 上节课研究的是怎么在最后判断两条事务的执行计划在完成之后可不可以串行化

• 本节课来找到方法来保证执行计划是正确的，不需要提前知道怎样执行的

• 使用锁来保护数据库对象

• 基础加锁思想

• 锁管理器引出

AGENDA

LOCKS VS.LATCHES

• 今天谈论的是宏观的 lock

• 操作的是表，行 。逻辑对象

BASIC LOCK TYPES 基础锁矩阵

• S-LOCK:Shared locks for reads. 共享锁 读锁

• X-LOCK:Exclusive locks for writes. 排他锁 写锁

EXECUTING WITH LOCKS 执行用锁的过程

• 事务获取锁

• 锁管理器同意或者搁置请求

• 事务释放锁

• 锁管理器更新内部锁表
• 它跟踪哪些事务持有哪些锁以及哪些事务正在等待获取任何锁。

EXAMPLE

• 无脑加锁也没法避免写读冲突

• 自然引出两阶段锁

CONCURRENCY CONTROL PROTOCOL: 2P

• 两阶段锁定（2PL）是一种并发控制协议，用于确定txn是否可以动态访问数据库中的对象。

• 该协议不需要提前知道txn将执行的所有查询。

TWO-PHASE LOCKING

• 阶段1：成长
• 每个txn都从DBMS的锁管理器请求它需要的锁。
• 锁管理器授予/拒绝锁请求。

• 第2阶段：收缩
• txn只允许释放它以前请求的锁.
• txn不能获取新锁。

EXAMPLE

2PL-CASCADING ABORTS

• 二阶段锁保证基于冲突的串行化

• 保证不会出现环

• 二阶段锁有问题

• cascade abort 无法避免级联回滚

EXAMPLE

• T2 写是在 T1 临时版本写的，当 T1 abort ，T2 也必须回滚

• T2 脏读了 读了没提交的

Rigorous 2PL 防止脏读

• txn只允许在结束后释放锁，即commit 或abort

• 只允许冲突可串行化的计划，但它通常比某些应用程序所需的更强大。

• 如果 txn 写入的值在该 txn 完成之前没有被其他txn读取或覆盖，则计划是严格的。
• 不能同时两个事务操作一个数据对象 

• 优点：
• 不会引发级联回滚。
• 中止的txns可以通过恢复(修改后的元组的原始值) 来撤消。

EXAMPLE

• 没两阶段锁的时候会发生问题

• 用二阶段锁会等待

• 可能级联回滚

• 强二阶段锁

• 提交时候解锁

• 没级联回滚问题

UNIVERSE OF SCHEDULES

• Strong Strict 2PL 既满足基于冲突串行化

• 又满足 无级联回滚

2PL 还有可能有死锁问题/

• 两阶段锁并不能解决死锁问题

• 一阶段加锁，二阶段释放锁

• 但是图中一阶段的锁互相等待

• T1 想给 B 加锁，T2 想给 A 加锁

• 但是他们的锁都被加过了，没释放

• 死锁了

2PL DEADLOCKS

• 检测

• 预防

DEADLOCK DETECTION 检测用图

• 等待图

• 节点：事务

• 边：事务需要等待另一事务释放锁

• 成环了

• 三个事务卡住

• 锁增长阶段不许解锁

DEADLOCK HANDLING

• 解决方法就是 淘汰一个事务 来破坏这个环

• 重启，还是搁置取决于业务

• 周期性检测死锁，性能需要

• 选择淘汰的标准
• 时间短的
• sql 少的
• 干掉加锁多的
• 是不是回滚过
• 重启过多少次 重启多的不淘汰，客户要疯

• 回滚长度
• 全量
• 部分

DEADLOCK PREVENTION 死锁预防 用策略

• 高优先级代表老时间戳

• 等待死亡（“老等待年轻”）
• 老事务等待年轻的释放锁
• 其他直接自杀

• 伤口等待（“年轻人等待老人”）
• 老事务抢锁，并年轻的锁持有者自杀
• 其他直接等

• 总得思路别互相等待

• 为啥用这种方法能预防死锁

• 只有一种等待机制，要么老等新，要么新等老

• 如果一个事务重开了，他的优先级保持不变

• 为啥？保证他不会被再重开，他早晚会变成老的，符合上边说的一种机制

• 所有这些示例都具有从数据库对象到锁的一对一映射。

• 如果txn想要更新十亿个行，那么它必须获得十亿个锁。

• 获取锁比获取锁更昂贵，即使该锁可用。

• 锁的粒度在行级别 tuple

LOCK GRANULARITIES 锁粒度

• 当txn想要获取锁时，DBMS可以决定该锁的颗粒度（即范围）。

• 理想情况下，DBMS应该获得txn需要的最少数量的锁。

• 并行性与开销之间的权衡。更少的锁，更大的粒度vs.更多的锁，更小粒度。

INTENTION LOCKS 意向锁 （是一种标记不是锁）

• 如果 table 带了意向锁，那么下边的 tuples 是有锁的

• 意图锁允许将更高级别的节点锁定在共享或独占模式下，而无需检查所有后代节点。

• 如果一个节点被意向锁锁住，那么一些txn正在树的较低级别执行显式锁定。

INTENTION LOCKS 意向锁分类 IS\ IX\ SIX

• IS 表示使用共享锁在较低级别进行显式锁定。

• IX 表示使用独占锁在较低级别进行显式锁定。

• SIX 以该节点为根的子树在共享模式下显式锁定，并且显式锁定在较低级别使用独占模式锁完成。

兼容锁矩阵

LOCKING PROTOCOL 锁定协议

• 上级 node 必须有 IS 意向共享锁 才能在 下级加 共享锁或者意向共享锁

• 上级 node 必须有 IX 意向独占锁 才能在 下级加 独占锁 意向独占锁 意向共享独占锁

EXAMPLE

• 读 tuple1 过程

• IS 和 IX 可同时存在

EXAMPLE2

• T1 扫描并更新，读加写，对表加 SIX，对更新的 tuple 加 X

• 因为已经对表加了 SIX，所以不需要在下边加 S

• T2 点查 ，给 tuple 加 S

• 上层加 IS

• IS 和 ISX 兼容

• T3 扫描

• S 卡住了，被 SIX卡了，表示下边有数据在修改，不能扫

• 等 T1，T2做完了再做

• T2 点查完毕

• T3 开始扫表

• 这样做 T3可以在表的层级别去等待，防止下探去做无意义的扫描

• 意向锁有助于提高并发性

• 帮助我们使用更少的锁

LOCK ESCALATION 锁升级

• 当获取太多低级锁时，锁升级会动态要求使用粗粒度锁。

• 这减少了锁管理器必须处理的请求数量。

LOCKING IN PRACTICE

• 您通常不会在txns中手动设置锁。

• 有时您需要向DBMS提供提示以帮助它提高并发性。

• 显式锁在对数据库进行重大更改时也很有用。

LOCK TABLE

• 用户自己设置

• 备份时候用

SELECT...FOR UPDATE

• For update 加 X

• For share 加 S

CONCLUSION

• 大部分数据库都是 2PL

• 放心的让事务并发执行

• 本节介绍了并发控制理论的实现方式之一

• 下节会介绍并发控制的另一种实现方式 Timestamp Ordering(T/O)