db_9 事务处理技术
db_9 事务处理技术
事务
概念
事务(Transaction)是用户定义的数据库操作序列，这些操作要么都做，要么都不做， 是一个不可分割的工作单位。
事务是数据库恢复和并发控制的基本单位
一个应用程序可以包含多个事务
事务的开始与结束可以由用户显式控制
DBMS 按缺省规定自动划分事务
特性（ACID）
- 原子性
- 事务中包括的所有操作要么都做，要么都不做
- 恢复实现
- 一致性
- 事务执行的结果必须是使数据库从一个一致性状态，变到另一 个一致性的状态
- 原子性实现
- 隔离性
- 一个事务的执行不能被其它事务干扰
- 即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰
- 并发控制实现
- 持久性
- 一个事务一旦提交之后，它对数据库的影响必须是永久的
- 其它操作或故障不应该对其执行结果有任何影响
- 恢复实现
可能被破坏：
多个事务并发运行时，不同事务的操作交叉进行
事务在运行过程中被强行停止
利用数据库并发控制机制以及数据库恢复机制保证事务的特性不被破坏，从而保证 数据库数据的正确、有效
数据库恢复
数据库恢复技术
定义：
数据库管理系统必须具有把数据库从错误状态恢复到某一已知正确状态的功能
通过数据库管理系统的恢复子系统实现
数据库恢复子系统的意义：
- 保证事务的原子性。实现事务非正常终止时的回滚
- 当系统发生故障以后，数据库能够恢复到正确状态
故障种类
- 事务内部的故障
- 可预期的：事务根据内部的测试条件，确定是否回滚
- 不可预期的：指不能由应用程序处理的事务故障，如死锁，运算溢出，违反完整性规则等
- 不会破坏数据库
- 事务撤销UNDO
- 系统故障
- 软故障，是指造成系统停止运行的任何事情，使得系统要重新启动
- 如硬件错误，操作系统故障，停电等
- 这类故障打断所有正在运行的事务，使事务都异常中止
- 不会破坏数据库
- UNDO+重做REDO
- 介质故障
- 硬故障，外存故障，如磁盘损坏，瞬时强磁场干扰等
- 破坏全部或部分数据库
- 影响正在存取这部分数据的所有事务
- 计算机病毒
- 不会破坏数据库
- 多数病毒对数据进行非法修改
数据库恢复的基本原理
冗余
利用存储在系统别处的冗余数据来重建或恢复修正数据库
恢复的实现技术
建立冗余数据：
数据转储与登录日志文件
数据转储
是DBA定期地将整个数据库复制到磁带或另一个磁盘上保存起来的过程
这些备用的数据文本称为后备副本或后援副本
重装后备副本只能将数据库恢复到转储时的状态
转储状态
- 静态转储
- 系统中无事务运行时进行的转储操作
- 并且转储过程中，不允许对数据库进行任何存取、修改
- 优点：保证副本的数据一致性
- 缺点：由于转储必须等待正在运行的事务结束才能开始，而新的事务必须等待转储结束才能执行，降低了数据库的可用性
- 动态转储：转储期间允许对数据库进行存取或修改
- 优点：不影响数据库的可用性
- 缺点：不能保证副本上的数据正确、有效
- 还必须把转储期间各事务对数据库的修改记录下来，建立日志文件
- 后援副本加上日志文件就能把数据库恢复到某一时刻的正确状态
转储方式
- 海量转储
- 海量转储指每次转储全部数据库
- 增量转储
- 增量转储指每次只转储上一次转储后更新过的数据。
登录日志文件
日志是用来记录事务对数据库更新操作的文件
日志文件格式：
记录为单位
数据块为单位
- 事务标识以及更新前和更新后的数据块
日志文件作用：
- 事务故障和系统故障恢复必须使用日志文件
- 在动态转储方式中必须建立日志文件，后备副本和日志文件综合起来才能有效地恢复数据库
- 在静态转储方式中，用日志文件恢复转储结束时刻到故障点间的事务
日志文件写入规则：
登记的次序严格按并发事务执行的时间顺序
必须先写日志文件，后写数据库
故障恢复策略
（1）事务故障的恢复
UNDO
在不影响其它事务的情况下，强行回滚，撤消已做的修改
- 反向扫描日志文件，查找该事务的更新操作
- 对该事务的更新操作（插入、删除、修改）执行 逆操作，即将日志记录中的“更新前的值”写入数据库
- 如此处理下去，直到读到该事务的开始标志
（2）系统故障的恢复
UNDO 未完成的事务
REDO 已完成的事务
- 未完成的事务对数据库的更新可能已经写入数据库
- 已提交事务对数据库的更新可能还留在缓冲区未写入数据库
- 正向扫描日志文件
- 找出故障发生前已经提交的事务，将其事务标识记入重做（REDO）队 列
- 同时找出故障发生时尚未完成的事务，将其事务标识记入撤销（UNDO）队列
- 对撤销队列中的各个事务进行UNDO处理
- 对重做队列中的各个事务进行REDO处理
（3）介质故障的恢复
装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致状态
对于动态转储的副本，还需要装入转储开始时刻的日志文件副本，将数据库恢复到一致状态
装入转储以后的日志文件副本，重做已经完成的事务
检查点技术
在检查点之前提交的事务，在数据库恢复处理时不必重做
- 日志文件中新增检查点记录
检查点记录的内容：
- 建立检查点时刻所有正在执行的事务清单
- 这些事务最近一个日志记录的地址
系统中增加一个重新开始文件，用来记录各个检查点记录在日志文件中的地址
- 恢复子系统动态维护日志文件，即周期性地执行如下操作
- 将当前日志缓存中的所有日志记录写入磁盘的日志文件上
- 在日志文件上写入一个检查点记录
- 将当前数据缓存的所有数据记录写入磁盘的数据库中
- 把检查点记录在日志文件中地址写入重新开始文件
- 利用重新开始文件定位最近检查点记录
- 找到检查点时刻运行事务清单
- 由该检查点记录得到检查点建立时刻所有正在运行的事务清单ACTIVE-LIST，把ACTIVE-LIST暂时放入 UNDO-LIST
- 确定需要撤消和重做的事务：从检查点开始正向扫描日志文件
- 如果有新开始的事务Ti，把Ti暂时放入UNDO-LIST
- 如果有提交的事务Tj，把Tj从UNDO-LIST队列移入到REDO-LIST 队列
- 执行撤消或重做动作：对UNDO-LIST中的每一个事务执行UNDO操作 ，对REDO-LIST中的每个事务执行REDO操作
数据库镜像
根据DBA的要求，自动把整个DB或其中的关键数据复制到另一个磁盘上
由DBMS 自动保证镜像数据库与主数据库的一致性
并发控制
概述
并发执行优点：
- 提高系统的吞吐量
- 减少平均响应时间
并发执行问题：
多个事务同时存取同一数据
- 丢失更新
- “脏”数据的读出
- 不能重复读
基本思想
基本思想：
并发控制就是要合理调度并发事务，避免并发事务之间的互相干扰造成数据的不一致性
基本手段
封锁机制
还包括
- 封锁
- 时间戳排序协议
- 事务隔离级别
- 乐观控制法
- 多版本并发控制
封锁
基本封锁类型
封锁就是事务T在对某个数据对象如表、记录等操作之前， 先向系统发出请求，对其加锁，从而对该数据对象有了一 定的控制权
- 排它锁 X锁
- 事务T对数据对象R加上X锁，则只允许T读取和修改R，其它事务对R的任何封锁请求都不能成功， 直至T释放R上的X锁
- 共享锁 S锁
- 事务T对数据对象R加上S锁，则事务T可以读取但不能修改R，其它事务只能对R加S锁，而不能对R加X锁，直到T释放R上的S锁
相容矩阵
封锁协议
一级封锁协议：防止丢失修改
协议内容：
- 事务T在修改数据R之前必须对其加X锁，直到事务结束才释放
- 事务结束包括正常结束(COMMIT)和非正常结束(ROLLBACK)
二级封锁协议：防止读“脏”数据
协议内容：
一级封锁协议
事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁
三级封锁协议：保证数据可重复读
协议内容：
一级封锁协议
事务T在读取R之前必须对其加S锁，直到事务结束才释放
封锁粒度
封锁粒度：封锁对象的大小
封锁对象：
属性值、属性值集合、元组、关系、某索引项、整个索引、整个 数据库、物理页、块等
封锁粒度大，则并发度低，封锁机构简单，开销小
封锁粒度小，则并发度高，封锁机构复杂，开销高
多粒度封锁
多粒度树
根结点是整个数据库，表示最大的粒度
叶结点表示最小的粒度
多粒度封锁协议
- 允许多粒度树中的每个结点被独立地加锁
- 对一个结点加锁意味着这个结点的所有子结点也被加以同样类型的锁
- 显式封锁是应事务的要求直接加到数据对象上的封锁
- 隐式封锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁
- 显式封锁与隐式封锁的效果是一样的
加锁时检查
- 检查对象本身
- 是否与该数据对象上的显式封锁冲突
- 检查对象的所有上级结点
- 是否与该数据对象上的隐式封锁冲突
- 检查其所有下级结点
- 是否与该数据对象下级的显式封锁冲突
- 检查对象本身
意向锁
该结点的下层结点正在被加锁
对任意节点加锁时，必须先对其上级节点加意向锁
申请封锁按自上而下的次序进行
释放封锁时，应按自下而上的次序进行
在对象加锁时，不再检查下级结点的封锁，只需检查对象和它的上级结点
- 意向共享锁（IS）
- 如果要对一个数据对象加IS锁，表示它的后裔结点意拟（意向）加S锁
- 意向排它锁（IX）
- 如果要对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁
- 意向共享排它锁（SIX）
- 如果要对一个数据对象加SIX锁，表示对它加S锁，再加IX锁
- SIX=S+IX
我们尝试解释一下相容矩阵
S不能与含X的一起
（A对r加S锁，则r及其子节点均加S锁，故r及其子节点不能加X锁。也就是说B不能对r加X，IX，SIX这些包含X的锁）
X不能与任何一起（显然）
IX可以和IS、IX一起
（若A对r加IX锁，则r到该节点路径上的节点全加IX锁，该节点及其子节点全加X锁。为了保证加了X锁的那个子节点上面不加其他的锁，故B一定不能对r加X，S，SIX锁）
SIX只与IS可以
（若A对r加SIX锁，对则r先加了S锁，释放后再加IX锁（一次操作中的先后次序），r的子节点分别对应加锁
故B不能对r加{X，SIX，IX锁}并上{X，S，SIX锁}）
IS只与X不可以
（若A对r加IS锁，那么r到要加S锁的节点路径上的节点全加IS锁，该节点及其子节点全加S锁。故B不能对其加X锁。至于IX，SIX锁是可以加的，因为对应要加锁的子节点可能不同，相同时再按X，S锁的相容矩阵判别即可）
活锁与死锁
活锁
某一事务可能永远等待
简单策略：先来先服务
死锁
两个事务彼此等待，永远无法结束
死锁预防
一次封锁法
- 每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行
- 并发度低
顺序封锁法
- 预先对数据对象规定一个封锁顺序
- 实现难度大
死锁检测
超时法
- 一个事务的等待时间超过了规定的期限，就认为发生了死锁
等待图法
事务等待图$G=(T,U)$
T是结点（事务） U是边（事务等待哪个事务）
存在回路则死锁
死锁恢复
- 选择一个处理死锁代价最小的事务，将其撤销
- 释放此事务持有的所有锁，使其他事务得以继续运行下去
- 对于所撤销的事务所作的操作必须加以恢复
事务调度可串行性
- N个事务的一个调度S
- N个事务所有操作的一个序列S，表示这些操作的执行顺序
- 这个序列满足：对于每个事务T，如果操作i在事务T中先于操作k执行，则在S 中操作i也必须先于操作k执行
可串行化调度：
- 多个事务的并发执行是正确的 当且仅当 其结果与按某一次序串行执行这些事务时的结果相同
可串行性是并行事务正确性的准则
- 一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度
冲突操作
- 不同事务对同一数据的读-写操作以及写-写操作
- 事务Ti读x，Tj写x —— Ri(x)与Wj(x)
- 事务Ti写x，Tj写x —— Wi(x) 与Wj(x)
冲突可串行化的调度：
- 一个调度Sc在保证冲突操作次序不变的情况下，可以通过交换两个事务不冲突操作的次序，得到另一个串行调度
- 冲突可串行化调度一定是可串行化调度（充分条件）
Sc1= R1(A)W1(A)R2(A)W2(A)R1(B)W1(B)R2(B)W2(B)
Sc1= R1(A)W1(A)R2(A)R1(B)W2(A)W1(B)R2(B)W2(B)
Sc1= R1(A)W1(A)R1(B)R2(A)W2(A)W1(B)R2(B)W2(B)
Sc1= R1(A)W1(A)R1(B)R2(A)W1(B)W2(A)R2(B)W2(B)
Sc2 = R1(A)W1(A)R1(B)W1(B)R2(A)W2(A)R2(B)W2(B)
不是冲突可串行化但可串行化的例子：
T1=W1(Y)W1(X) T2=W2(Y)W2(X) T3=W3(X)
L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)
L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)
执行结果相同
两段锁协议（2PL）
在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
在释放一个封锁之后，事务不再获得任何其它封锁
获得锁——拓展阶段
释放锁——收缩阶段
L=R1(A)R2(C)W1(A)W2(C)R1(B)W1(B)R2(A)W2(A)
事务遵守两段锁协议，这些事务的并发调度一定是可串行化调度（充分条件）
遵守两段锁的事务仍可能发生死锁
一次封锁法
- 每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行
两段锁
其他并发控制手段
事务隔离级别
不可重复读：一个事务中两次读取的数据内容不一致
幻读：一个事务中按照某个条件先后两次读取数据库，两次读取结果的条数不同
| 隔离级别 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|
| 读未提交 | 允许 | 允许 | 允许 |
| 读已提交 | 不允许 | 允许 | 允许 |
| 可重复读 | 不允许 | 不允许 | 允许 |
| 可串行化 | 不允许 | 不允许 | 不允许 |
- 悲观并发控制（适合事务冲突较多）
- 假定会发生并发冲突，事前控制，避免冲突发生
- 三段封锁协议
- 两段锁控制
乐观并发控制（适合事务冲突较少）
- 假设不会发生并发冲突，事后控制，只 在提交操作时检查，做冲突处理
- 时间戳排序协议
- 回滚事务
- 给每个事务分配一个全局唯一的时间戳，使得所有事务有单调顺序
- 事务只能访问该事务时间戳前面的数据
- 冲突可串行化调度
- 两个事务冲突,通常终止其中一个,将其回滚并重新调度，赋予新的时间戳
- 乐观并发控制协议（OCC）
- 重启事务
- 读阶段：从数据库中读取需要的数据，存放于事务私有工作区；在工作区进行写操作
- 验证阶段：有效性检查测试是否满足所需的隔离级别。若检测失败 ，终止事务，然后重启；否则进入写阶段
- 写阶段：将私有工作区中的更新数据刷新到数据库里
多版本并发控制（MVCC）
- 空间复用的多版本信息
- 版本是数据库中数据对象的一个快照，记录数据对象某个时刻的状态
- 事务对数据进行写操作时，产生该数据的一个新版本
- 事务对数据进行读操作时，读取事务开始时该数据的最新版本
- 解决读写冲突的无锁并发控制
- 现了读已提交和可重复读，但不能解决丢失更新问题
