Chap11. 并发控制beta
WARNING
本章内容未完成，ppt截图和笔记还没整理完毕
I.Motivation and Problem
并发操作可能带来什么问题？ 并发操作使多个事务之间可能产生相互干扰，破坏事务的隔离性（Isolation）
丢失更新（Lost update）
- 两次提交写导致的写覆盖
脏读（Dirty read / Uncommitted update）
- 脏读是指一个事务读取了另一个事务还未提交的数据，当另一个事务回滚时，读取该数据的事务将读取到错误的数据。因为write会写到buffer中，而read首先检查buffer有没有才会去读磁盘
- 由于Rollback导致的提交事务的写失效破坏了其他事务的原子性
- DBMS中不允许出现Dirty write 在任何情况下都要求X锁保留到事务结束（严格二阶段锁）
- 脏数据：事务在内存中更新了但还未最终提交的数据
不一致分析（Inconsistent analysis）
事务读了过时的数据，不是数据库的当前状态
- 不可重复读 Nonrepeatable read：事务内读的数据被其它事务update或者delete了
- 比如事务T专门用于求总和，在执行过程中关系内insert了一条记录，那么事务T得到的结果就是不准确的
- 幻像读 Phantom read：事务内读到的数据内容被其它事务的insert操作改变了
II. 可串性的概念
可串化调度Serialzable Schedule：如果一个调度的结果与某一串行调度执行的结果等价，则称该调度是可串化调度，否则是不可串调度 冲突操作
- 如果调度中一对连续操作是冲突的，则意味着如果它们的执行顺序交换，则至少会改变其中一个事务的最终执行结果
- 如果两个连续操作不冲突，则可以在调度中交换顺序
III. 冲突可串性及其判定方法*
冲突可串性
- 冲突等价: 如果调度S1,S2可以通过一系列非冲突的操作交换得到,则称这两个调度冲突等价
- 冲突可串性: 如果一个调度与串行调度冲突等价,则称这个调度满足冲突可串性（通过交换可以变成串行调度）
- 定理
- 如果一个调度满足冲突可串性,则该调度为可串化调度
- 给定一个调度S，构造S的优先图P(S)，若P(S)中无环，则S满足冲突可串性
IV. 锁的相关概念：S、X、U、IS、IX等
X锁（Exclusive Locks）：也称作写锁，排它锁。若事务T对数据R加X锁，那么其它事务要等T释放X锁以后，才能获准对数据R进行封锁。只有获得R上的X锁的事务，才能对所封锁的数据进行修改
S锁（Share Locks）：也称读锁。
- 如果事务 T 对数据 R 加了 S 锁，则其它事务对 R 的X锁请求不能成功，但对 R 的 S 锁请求可以成功。这就保证了其它事务可以读取 R 但不能修改 R ，直到事务 T 释放 S 锁。
- 当事务获得 S 锁后，如果要对数据 R 进行修改，则必须在修改前执行Upgrade(R)操作，将 S 锁升级为X锁（Update Lock）
U锁（Update Lock）：能升级的读锁
- 如果事务取得了数据R上的更新锁，则可以读R，并且可以在以后升级为 X 锁
- 单纯的S锁不能升级为 X 锁
- 如果事务持有了 R 上的 Update Lock，则其它事务不能得到 R 上的 S 锁、X 锁以及 Update 锁（排他）
- 如果事务持有了 R 上的 S Lock，则其它事务可以获取 R 上的 Update Lock
**IS锁（Intent Share Lock）**意向共享锁，意向读锁
- 如果对某个结点加 IS(IX)锁，则说明事务要对该结点的某个下层结点加S (X)锁；
- 对任一结点 P 加 S(X)锁，必须先对从【根结点到 P 的路径】上的所有结点加 IS(IX)锁
**IX锁（Intent Exclusive Lock）**意向排它锁，意向写锁
V. 2PL 的含义？如何使用 2PL 保证并发事务的可串行性？
2PL 两阶段锁协议
- 如果一个调度S中的所有事务都是两段式事务，则该调度是可串化调度
VI. 事务的隔离级别*
- Insight 1：隔离级别是针对连接（会话）而设置的，不是针对一个事务
- Insight 2：不同隔离级别影响读操作
未提交读（脏读） Read Uncommitted
- 允许读取当前数据页上的任何数据，不管数据是否已提交（随便读）
- 事务不必等待任何锁，也不对读取的数据加锁（没有锁机制）
提交读
- 保证事务不会读取到其他未提交事务所修改的数据（可防止脏读）
- 事务必须在所访问数据上加S锁，数据一旦读出，就马上释放持有的锁
可重复读
- 保证事务在事务内部如果重复访问同一数据（记录集），数据不会发生改变。即，事务在访问数据时，其他事务不能修改正在访问的那部分数据
- 可重复读可以防止脏读和不可重复读取，但不能防止幻像
- 事务必须在所访问数据上加 S 锁，防止其他事务修改数据，而且S锁必须保持到事务结束
可串化
- 保证事务调度是可串化的
- 事务在访问数据时，其他事务不能修改数据，也不能插入新元组
- 事务必须在所访问数据上加S锁，防止其他事务修改数据，而且S锁必须保持到事务结束
- 事务还必须锁住访问的整个表（表锁）
- 不会出现丢失更新
VII. 死锁*
- 已持有锁并互相请求对方的锁（或者多个事务请求组成了环）
- 两个事务同时想要升级写锁为 X 锁（另一个事务的 S 锁与 X 锁互斥，无法升级）
死锁检测 Deadlock Detecting
- 超时机制
- 事务超过时间没完成就Abort
- 等待图
Ti→Tj，表示Ti必须等待Tj释放所持有的某个锁才能继续执行- 有环表示产生了死锁
死锁预防 Deadlock Prevention
按序加锁 Priority Order
- 把要加锁的数据库元素按某种顺序排序
- 事务只能按照元素顺序申请锁
时间戳 Timestamp
- 每个事务开始时赋予一个时间戳
- 如果事务
T被Rollback然后再Restart，T的时间戳不变 Ti请求被Tj持有的锁，根据Ti和Tj的timestamp决定锁的授予
Wait-Die Scheme 等待－死亡
T请求一个被U持有的锁
- 若
T更早开始，等待U释放锁 - 若
T更晚才开始，DIE并等待被重新调度，时间戳不变
Wound-Wait Scheme 伤害－等待
T请求一个被U持有的锁
- 若
T更早开始，T抢夺U的锁，Urollback 等待重新开始 - 若
T更晚才开始，等待U释放锁
两种方式比较
- Wait-Die: RB次数多，但每次RB开销小
- Rollback 总是发生在请求锁阶段，因此要 Rollback 的事务操作比较少，但 Rollback 的事务数会比较多
- Wound-Wait: RB 次数少，但每次 RB 开销大
- 发生 Rollback 时，要 Rollback 的事务已经获得了锁，有可能已经执行了较长时间，因此 Rollback 的事务操作会较多，但 Rollback 的事务数预期较少，因为可以假设事务开始时总是先请求锁
- 请求锁时 WAIT 要比 WOUND 要更普遍，因为一般情况下一个新事务要请求的锁总是被一个较早的事务所持有
VIII. 乐观并发控制技术
适用场景：如果大部分事务都是只读事务，则并发冲突的概率比较低；即使不加锁，也不会破坏数据库的一致性；加锁反而会带来事务延迟
“读不加锁，写时协调”
- 基于事后协调冲突的思想，用户访问数据时不加锁；如果发生冲突，则通过回滚某个冲突事务加以解决
- 使用“有效性确认(Validation)”确定哪些事务发生冲突
有效性确认协议
每个更新事务Ti在其生命周期中按以下三个阶段顺序执行
- 读阶段：数据被读入到事务
Ti的局部变量中。此时所有write操作都针对局部变量，并不对数据库更新 - 有效性确认阶段：
Ti进行有效性检查，判定是否可以将write操作所更新的局部变量值写回数据库而不违反可串性- 基于行版本检查（时间戳）
- 基于值比较检查
- 写阶段：若
Ti通过有效性检查，则进行实际的写数据库操作，否则回滚Ti