为什么会出问题, 如何带来不一致性, 如何解决(封锁怎么去做, 兼容/排他锁, 写锁读锁, 三种协议, 要会举例)
死锁活锁, 解决方式
事务调度基本概念(串行, …可串行化, 两段锁, 和一次封锁的区别)
意向锁
并发控制
并发带来的问题: 多个事务同时存取同一数据, 可能会存取/存储不正确的数据, 破坏事务隔离性和数据库的一致性.
数据库必须提供并发控制机制.
多事务执行方式
- 串行执行 → 每个时刻只有一个事务运行, 后一个事务必须等待前一个事务结束才能开始运行(不能充分利用和共享系统资源)
- 交叉并发方式 → 单处理器系统中, 并发存在的形式是”并行事务”的”并行操作”在同一个处理器上轮流交叉运行. 不是真正的并行, 但是能减少处理器的空闲时间, 提高系统效率
- 同时并发方式 → 多个处理器上同时运行多个事务, 最理想, 受制于硬件环境, 需要更复杂的并发控制机制
并发控制
并发控制的基本单位: 事务.
并发控制的任务: 正确调度并发操作, 保证事务隔离性(事务的执行之间不互相干扰), 从而保证数据库一致性.
不一致性的内容:
- 丢失修改: 同时读取/写入共享资源, 导致写入丢失(飞机票问题)
- 不可重复读: 事务读取数据后, 事务执行更新操作(修改/删除/新增), 使得无法复现前一次的读取结果
- 读脏数据: 读到修改后的数据, 但是该修改随后可能被撤销, 这样对于撤销后的时间节点来说, 事务读到的就是错误的数据
不一致性的产生: 并发事务的调度序列随机, 可能破坏事务的隔离性.
主要技术: 封锁, 时间戳, 乐观控制法, 多版本并发控制
封锁
事务T在对某个对象进行操作之前, 先向系统发出请求, 对该对象加锁. 加锁之后到释放之前, 其他的事务不能更新该对象.
封锁类型
参考OS中的读者-写者锁问题.
- 排它锁(X锁, exclusive), 又称写锁. 一个数据对象被加上X锁后, 释放之前其他任何事务都不能再对该数据对象加任何类型的锁
- 共享锁(S锁, share), 又称读锁. 一个事务为数据对象加上S锁后只能读该对象. 其他事务在该S锁释放之前只能再对该对象加S锁并读取, 不能写或加X锁.
封锁协议
协议规定:
- 什么操作需要申请X锁或S锁
- 持锁时间
- 何时释放
不同封锁协议在不同程度上保证并发操作的正确调度. 封锁协议级别越高, 一致性保证程度越高.
X锁 | ㅤ | S锁 | ㅤ | 一致性保证 | ㅤ | ㅤ | |
操作结束释放 | 事务结束释放 | 操作结束释放 | 事务结束释放 | 不丢失
修改 | 不读“脏”数据 | 可重复
读 | |
一级封锁协议 | ✅ | ✅ | |||||
二级封锁协议 | ✅ | ✅ | ✅ | ✅ | |||
三级封锁协议 | ✅ | ✅ | ✅ | ✅ | ✅ |
- 一级封锁协议(只管写): 事务T在修改数据R之前必须先对其加写锁, 直到事物结束才释放.
- 可以防止丢失修改, 并保证T可恢复
- 不能保证读者的安全性, 即不保证不可重复读和脏读
- 二级封锁协议: 在一级的基础上加上: 读之前加读锁, 读完释放.
- 可以防止丢失修改和读脏数据(写事务提交/回滚之前不能读)
- 读完就释放, 不能保证不可重复读
- 三级封锁协议: 在一级的基础上加上: 读之前加读锁, 事务结束才释放.
- 可以防止丢失修改, 不可重复读和脏读, 并发程度最低
活锁
实际上是饥饿现象, 可能有事务的请求一直被插队, 永远等待
避免: 使用先来先服务策略, 按照请求的先后次序排队并获得锁.
死锁
多个事务互相等待别人持有的锁
产生条件: 多个事务都已经封锁了一些对象, 然后又请求对已经被其他事务封锁的数据对象加锁, 出现死等待(参考OS中死锁的四个条件)
预防方案:
- 一次封锁法(对应OS中静态申请资源): 要求每个事务必须一次性将所有要用到的数据全部加锁, 否则就不占有锁
- 问题: 并发程度低, 难以实现精确确定所有需要封锁的对象
- 顺序封锁法(对应OS中全序): 预先为数据对象规定一个封锁的顺序
- 问题: 对象不断变化, 维护封锁顺序困难且开销高
诊断并解除方案(数据库中更普遍采用):
- 超时法: 如果一个事务的等待时间超过规定时限, 就认为发生了死锁
- 优点: 实现简单
- 缺点: 时长短可能误判, 时长长可能不能及时发现死锁
- 等待图法: 并发控制子系统周期性生成事务等待图, 如果发现图中有环路则说明出现了死锁
- 解除方案: 选择一个处理代价最小的事务, 将其撤销并释放该事物持有的所有的锁, 打破环路.
事务调度
对同一组并发事务的不同调度可能产生不同结果
串行调度一定正确
并发调度的可串行性
- “可串行化调度”: 多个事务的并发调度方法是正确的, 当且仅当其结果与按某一次序串行地执行这些事务时的结果相同.
- “可串行化”: 并发事务正确调度的准则. 一个并发调度当且仅当可串行化时才是正确调度.
- “冲突可串行化”(比可串行化更严格): 在保证两个事务中冲突操作的相对次序不变的情况下, 交换两个事务中不冲突操作的顺序得到的调度满足可串行性(与某个串行执行序列等价), 则称该调度满足冲突可串行性.
- 非形式化解释: 存在一个不冲突的、一步接一步的执行顺序, 它能产生和并行执行一模一样的最终结果
- 冲突操作: 两个不同事物中对同一数据的读写或写写操作.
- 不能交换次序的动作: 同一事物的两个操作, 不同事物的冲突操作.
- 若满足冲突可串行化, 则一定满足可串行化(就算固定一部分相对顺序也可以满足可串行性, 充分不必要).
- 等价于一个串行调度, 所以是冲突可串行化的调度.
两段锁协议
DBMS普遍采用两段锁协议实现并发调度的可串行性, 即正确性.
两段锁协议: 所有事务必须分两个阶段对数据项加锁/解锁
- 在对任何数据项进行读/写操作之前, 事务首先要获得对该数据的封锁
- 释放一个封锁之后, 事务不再申请和获得任何其他封锁
含义: 事务分为两个阶段: 获得封锁(扩展阶段, 只能申请不能释放), 释放封锁(收缩阶段, 只能释放不能申请)
并发都事务遵守两段锁协议 对这些事务的任何并发调度策略都是可串行化调度(充分不必要)
防止死锁措施中的一次封锁法要求一次性全部加锁, 故满足两段锁协议.
两段锁协议通过限制事务获取和释放锁的顺序, 强制了一种“逻辑上的先后顺序”, 使得所有的冲突都按照一个线性的、无环的方式解决. 这种无环的特性正是可串行化（更具体地说是冲突可串行化）的保证
然而满足两段锁协议的事务并不一定要一次性全部加锁, 故有可能发生死锁.
封锁粒度
封锁粒度: 封锁对象(逻辑单元/物理单元)的大小
关系数据库中可能的封锁对象:
- 逻辑单元: 属性值、属性值的集合、元组、关系、索引项、整个索引、整个数据库等
- 物理单元: 页（数据页或索引页）、物理记录等
封锁粒度与系统的并发度和并发控制的开销密切相关.
- 封锁粒度越大, 数据库能封锁的数据单元就越少, 并发度越小, 系统开销越小
- 封锁粒度越小, 数据库能封锁的数据单元就越多, 并发度越大, 系统开销越大
多粒度封锁: 在一个系统中同时支持多种封锁粒度供不同的事务选择.
选择封锁粒度需要同时考量封锁开销和并发程度两个因素, 需要适当选择封锁粒度.
- 需要处理多个关系的大量元组的用户事务: 以数据库为封锁单位
- 需要处理大量元组的用户事务: 以关系为封锁单位
- 只处理少量元组的用户事务: 以元组为封锁单位
多粒度树: 以树形结构表示多级封锁粒度, 根节点为整个数据库(最大粒度), 叶节点为最小粒度
多粒度封锁中一个数据对象可能显式(自身封锁)/隐式(由于上级节点封锁导致自身封锁)封锁, 二者效果相同.
系统对某数据对象封锁时要同时检查施加在该对象上的显式和隐式封锁, 还要检查该对象的下级节点是否有冲突的封锁(检查自身, 上级和下级, 即子树和到根节点的路径均要检查).
这样检查效率很低 → 引入意向锁来帮助提前判断加锁是否合法(思路类似于逻辑表达式短路求值)
意向锁
目的: 提高对某个数据对象加锁时系统的检查效率
- 如果对一个节点加意向锁, 则说明该节点的下层节点正在被加锁.
- 对任意节点加基本锁, 必须先对其所有的上层节点加意向锁, 例如对元组加锁时必须先对它所在的数据库和关系加意向锁.
常用意向锁
- 意向共享锁(IS锁): 如果对一个数据对象加IS锁则表示它的后代节点有加S锁的意向. 如果要对某个元组加S锁则要先对其所在的关系和数据库加IS锁
- 意向排它锁(IX锁): 如果对一个数据对象加IX锁则表示它的后代节点有加X锁的意向. 如果要对某个元组加X锁则要先对其所在的关系和数据库加IX锁
- 共享意向排它锁(SIX锁): 如果对某一个数据对象加SIX锁则表示对它加S锁再加IX锁. 如对某个表加SIX锁则表示该事务要读整个表(故对整个表加S锁), 同时会更新个别元组(故加IX锁)
解读:
- SIX锁表示本事务要读整个表且知道即将更新的内容, 故不允许其他事务修改表中成分, 故只能与读某一部分的IS锁兼容(读写同一条目的冲突由读/写锁负责), 绝对不允许其他事务写某一部分或读整个表.
- IX锁表示要修改表中的条目, 多个IX锁修改的条目可能不同, 故两个IX锁可以兼容. 写同一条目的冲突由写锁负责.
- 纯读的锁之间互相兼容(IS和S).
锁的强度
锁的强度指对其他锁的排斥程度.
申请封锁时用强锁代替弱锁时安全的, 反之则不然.
具有意向锁的多粒度封锁方法:
- 申请封锁时按照自上而下次序进行
- 释放封锁时按照自下而上次序进行
意向锁的存在提高了系统并发度, 减少加锁和解锁检查的开销, 得到了广泛应用.
“短路判断”举例: 假设事务T1要对关系R1加S锁
- 首先对数据库加IS锁
- 检查数据库和R1是否已加了不相容的锁(X或IX)
- 不再需要搜索和检查R1中的元组是否加了不相容的锁(X锁)
