第7章 事务管理2.ppt

第7章事务管理 第7章事务管理 恢复 保证事务在并发执行时满足ACID准则的技术 并发控制 保证事务在并发执行时满足ACID准则的技术 事务管理 transactionmanagement 7 1恢复引论 故障的可能性总是存在的 解决故障的措施有二 一是尽可能提高可靠性 二是恢复 这里主要讨论发生故障后 恢复数据库至一致状态的技术 即恢复技术 系统发生故障时 可能会导致数据的丢失 loss 要恢复丢失的数据 必须有后备副本 对于恢复 数据冗余是必需的 1 单纯以后备副本为基础的恢复技术2 以后备副本和运行记录为基础的恢复3 基于多副本的恢复技术 恢复技术大致可以分为下列三种 1 单纯以后备副本为基础的恢复技术 从文件系统继承而来 周期性的把磁盘上的数据库转储 dump 到脱机存放的磁带上 失效 取后备副本 取后备副本 取后备副本 更新丢失 更新丢失 增量转储 ID 单纯以后备副本为基础的恢复技术 优点 实现简单 不增加数据库正常运行时的开销 缺点 不能恢复到数据库的最近一致的状态 多用于文件系统以及小型的不重要的数据库系统 2 以后备副本和运行记录为基础的恢复 运行记录 log或journal 由系统维护 一般包括下列内容 1 前像 BeforeImage BI 当数据库被一个事务更新时 所涉及的物理块更新前的映像 image 称为该事务的前像 BI 前像以物理块为单位 有了前像可以使数据库恢复到更新前状态 对应操作undo 撤销 2 后像 AfterImage AI 当数据库被一个事务更新时 所涉及的物理块更新后的映像 image 称为该事务的后像 AI 后像也以物理块为单位 有了后像 即便更新的数据丢失了 仍然可以使数据库恢复到更新后的状态 相当于重做一次更新 对应操作redo 重做 问题 前像 BI 后像 AI 和事务操作的关系 修改 有前像有后像插入 没前像有后像删除 有前像没后像 3 事务状态 记录每个事务的状态 以便在恢复时作不同的处理 COMMIT和NOTCOMMIT 提交 Commit 成功执行 doall 回卷 Rollback或Abort 消除事务对数据库的影响 donothing 对恢复而言 至少要区分一个事务是否提交 实现方法 最近后备副本 运行记录 基于后备副本与运行记录的恢复如上图所示 当数据库失效时 取出最近后备副本 然后根据运行记录 对未提交的事务用前像卷回 向后恢复 backwardrecovery 对已提交的事务 必要时用后像重做 向前恢复 forwardrecovery 这种恢复技术 需保持运行记录 这将会影响数据库的正常工作速度 但可以使数据库恢复到最近一致状态 大多数商品化DBMS采用这种恢复技术 3 基于多副本的恢复技术 如果系统中有多个DB副本 且这些副本具有独立的失效模式 independentfailuremode 则可利用这些副本互为备份 用于恢复 此技术在分布式数据库系统中应用的较多 近年来 由于硬件价格的下降 也采用镜像磁盘 mirroreddisks 技术 写数据时 两个磁盘都写入同样的内容 当一个磁盘的数据丢失时 可以用另一个磁盘的数据来恢复 两盘同时故障的概率可以假设为零 下面主要讨论第二种恢复技术 7 2运行记录的结构 运行记录的存储要避免与数据库 全军覆没 运行记录 log 一般不能和数据库放在同一磁盘上 以免两者皆失 假设log和DBMS同时失效的概率为零 一般假设log不会损坏 若运行中DBMS测得log损坏 则采取强制措施 例如拒绝新事务 完成已提交事务 停止运行 修复log 运行记录的结构因DBMS而异Log基本内容 1 活动事务表 activetransactionlist ATL 记录所有正在执行 尚未提交的事务的标识符 transactionidentifier TID 2 提交事务表 committedtransactionlist CTL 记录所有已提交事务的标识符 3 前像文件 可以看成一个堆文件 每个物理块有个块标识符BID blockidentifier BID由TID 关系名和逻辑块号组成 逻辑块号在关系中是唯一的 如果一个事务需要卷回 可以在前像文件中找出该事务的所有前像块 按照逻辑块号写入到关系的对应块 从而消除该事务对数据库的影响 undo满足幂等性 undo undo undo undo x undo x 因此 undo失败可以再undo 4 后像文件 结构与前像文件相仿 不过记的是后像 在恢复时 可按提交事务表中的事务次序 按逻辑块号 写入其后像 这相当于按提交的次序重做各个事务 redo满足幂等性 redo redo redo redo x redo x 取后备复本后 之前的运行记录就失去了价值 对恢复来说 只要保留最近后备复本以后的运行记录 但运行记录仍可能很大 可采用下列措施减小运行记录规模 1 不保留已提交事务的前像2 有选择性的保留后像3 合并后像 对给定逻辑块号的物理块 如多次更新 可只保留最近的后像 如何判断该做undo还是redo呢 下一节 将解决这个问题 7 3更新事务的执行与恢复 1提交规则 CommitRule 后像必须在事务提交前 写入非易失性存储器 DB或log 更新事务执行时 应遵守下两条规则 2先记后写规则 LogAheadRule 如果后像在事务提交前写入数据库 则必须把前像先写入log 在执行一个更新事务时 按后像写入DB的时间 有三种可能的方案 即后像不能仅留在内存中 三种更新策略 a 后像在事务提交前完全写入DBTID activelistB I Log 按LogAheadRule A I DB TID commitlistdeleteTIDfromactivelist 在这种情况下 如果出现故障 如何恢复 Restart时 对每个TID 查两个list b 后像在事务提交后写入数据库TID activelistA I Log 按commitrule TID commitlistA I DBdeleteTIDfromactivelist 在这种情况下 如果出现故障 如何恢复 Restart时 对每个TID 查两个list c 后像在事务提交前后写入数据库TID activelistA I B I Log 按2rules A I DB partiallydone TID commitlistA I DB completed deleteTIDfromactivelist 在这种情况下 如果出现故障 如何恢复 Restart时 对每个TID 查两个list 思考 方案3均匀的将写入DB的I O操作分散在事务提交前后 有什么优点 有利于磁盘均衡负载 7 5消息的处理 一个事务常常要给用户发送有影响的消息 message 不是指需要用户输入的指示消息 例如 付款2000元 以及 立即执行下一步处理 等 发送消息也是事务执行结果的一部分 应该遵循 要么不做 要么全做 的原则 但是 消息往往难以用 undo 操作来消除其影响 因此 在事务结束前 消息不能发出 只有等事务结束后才能发出 消息发送委托消息管理 messagemanager MM 子系统执行 事务执行时 将需要发送的消息转给MM MM为每个事务建立一个消息队列 MM Ti 当事务正常结束时 包括提交和回卷 事务通知MM发送消息 当事务因故障被撤销时 MM将把该事务的消息丢弃 为了保证消息能可靠的发送给有关用户 MM采用 发送 确认 方式传递 MM对事务委托发送的消息 在事务正常结束前 允许事务增加和删除 一旦事务结束 MM就把消息存于不易失存储器中 7 6失效的类型及恢复的对策 一种恢复方法通常只对某些类型的失效有用 通常的失效可以分为以下三类 1 事务失效 transactionfailure 事务应不可预知的原因而夭折 例如 数据库中没有要访问的数据 输入数据类型不对 除数为零等 事务失效时DB未被破坏 系统控制在手 且事务失效一定发生在事务提交前 恢复措施 MM丢弃该事务的消息队列 如果需要 进行undo操作 从ATL删除该事务的TID 释放该事务所占资源 2 系统失效 systemfailure 系统 包括OS和DBMS 崩溃 需要重新启动 restart DB未被破坏 但系统失去控制 例如 掉电 除数据库存储介质以外的软 硬件故障等 恢复措施 重新启动OS和DBMS 恢复DB致一致状态 对未提交的事务进行undo操作对已提交的事务进行redo操作 只有当数据库恢复到一致状态后 才允许用户访问数据库 系统中 活动事务表 ATL 的长度是有限的 由于累积效应 提交事务表 CTL 可能很长 为了减少恢复时大量redo操作的工作量 在运行过程中 DBMS每隔一定时间在运行记录中设置一个检查点 checkpoint CP 在检查点 DBMS强制写入所有已提交事务的后像 显然 在最近检查点以前提交的事务 恢复时 不用redo 取CP过程一般如下 暂停事务的执行 写入上一个CP以后所提交事务的后像 在log的CTL中记下检查点 恢复事务的执行 取CP很影响系统的正常运行 而只有在发生系统失效时 才有其减少redo工作量的效益 3 介质失效 mediafailure 磁盘发生故障 DB被破坏 修复系统 必要时更新磁盘 如果系统 OS和DBMS 崩溃 重新启动系统 加载最近后备副本 用log中的后像重做取最近后备副本后提交的所有事务 恢复措施 7 7并发控制 7 7 1数据库系统中的并发 1 串行访问 serialaccess 事务顺序执行 2 并发访问 concurrentaccess DBMS可同时接纳多个事务 事务可在时间上重叠执行 交叉并发 interleavedconcurrency 单CPU系统 各个事务交叉使用CPU 同时并发 simultaneousconcurrency 多CPU系统 多个事务在CPU中同时运行 7 7 2并发的目的 1 提高系统资源利用率 2 改善短事务响应时间 例如 两个事务T1和T2 T1长 先交付 T2短 稍后交付 如果串行执行 则T2必须等T1 响应时间很长 7 7 3并发引起的问题 事务若不加控制的并发执行 会产生什么问题 1 丢失更新 lostupdate Read x Read x x x 1 Write x x 2 x Write x 2 读脏数据 dirtyread read t x write t read t y rollback 3 读值不可复现 unrepeatableread Read x Write x Read x 事务并发执行时可能会有两种冲突 写 写 读 写 写 写冲突在任何情况下都应避免 读 写冲突一般情况下应避免 但某些应用场合可以容忍 7 7 4并发控制的正确性准则 思考 多个事务并发执行 结果怎么估计 假设数据库系统中 某一时刻并发执行的事务集为 T1 T2 Tn 调度 Schedule S是对n个事务所有操作的顺序的一个安排 在S中 不同事物的操作可以交叉 但必须保持各个事务的操作的原有次序 注意 操作是调度的基本单位 设Write简写为W Read为R R和W用其所属事务号为下标 上图的调度可表示为 S R1 x W2 x R1 x 对同一事务集 可能有很多种调度 如果其中两个调度S1和S2 在数据库的任何初始状态下 所有读出的数据都一样 留给数据库的最终状态也一样 则称S1和S2是等价的 又称为目标等价 viewequivalence 偏重语义 难以判断 还有一种更实用的等价定义 称为冲突等价 conflictequivalence 容易实现 冲突操作有读 写冲突和写 写冲突两种 可表示为 Ri x 和Wj x Wi x 和Wj x i j 冲突操作的执行次序会影响执行结果 不冲突操作的次序可以互换 不致影响执行结果 凡是通过调换S中不冲突操作得到的新的调度 称为S的冲突等价调度 如果两个调度是冲突等价的 一定是目标等价的 反之未必 若调度S在数据库中产生的效果 与这组事务的某个串行执行序列的结果相同 则称这个调度S是可串行化的 serializable 例如 对事务集 T1 T2 T3 的一个调度 S R2 x W3 x R1 y W2 y S 是串行调度 故S是冲突可串行化的 也是目标可串行化的 冲突可串行化的调度一定是目标可串行化的吗 目标可串行化的调度一定是冲突可串行化的吗 目标可串行化的调度未必是冲突可串行化 例如 调度S R1 x W2 x W1 x W3 x 无冲突等价调度 但却可以找到一个调度S S R1 x W1 x W2 x W3 x 与S目标等价 目标可串行化 冲突可串行化 多个事务串行执行后 DB仍保持一致状态 可串行化调度与事务的某个串行执行等价 当然也保持数据库的一致状态 因此 在一般的DBMS中 都是以可串行化作为并发控制的正确性准则 可串行化 并发控制的正确性准则 问题 不同的调度 不同的等价串行序列 不同的执行结果 n 关于目标等价与冲突等价 调度 是系统对n个并发事务的所有操作的顺序的一个安排 目标等价 两个调度s1和s2 如果在同样的初始条件下执行 对数据库产生的效果完全相同 则称s1和s2是目标等价的 冲突操作 R W W W 冲突操作的执行顺序会影响执行效果 不冲突操作 R R 虽有写操作 但作用对象不同 如Ri x 和Wj y 冲突等价 凡是通过调换s中的不冲突操作所得的新调度 称为s的冲突等价调度 性质 如两调度是冲突等价的 则一定是目标等价的 反之未必正确 串行化也分为目标可串行化和冲突可串行化 例1 对事务集 T1 T2 T3 的一个调度ss R2 x W3 x R1 y W2 y R1 y R2 x W2 y W3 x s 因为s 是串行调度 所以s是冲突可串行化的 例2 s R1 x W2 x W1 x W3 x 无冲突等价调度 但却可以找到一个调度s s R1 x W1 x W2 x W3 x 与s目标等价 目标可串行化的测试算法是NP难度的 冲突可串行化覆盖了绝大部分可串行化的调度实例 所以今后如无特别说明 可串行化均指冲突可串行化 前趋图有向图G V 顶点的集合 包含所有参与调度的事务 E 边的集合 通过分析冲突操作来决定 如果下列条件之一成立 可在E中加边Ti Tj Ri x 在Wj x 之前Wi x 在Rj x 之前Wi x 在Wj x 之前最后 看构造好的前趋图中是否有环路 如果有 则该调度不可串行化 否则 可串行化 可串行化时 决定等价串行调度序列的算法 由于无环路 必有入度为0的顶点 将它们及其有关的边从图中移去并将这些顶点存入一个队列 对剩下的图作同样处理 不过移出的顶点要队列中已有顶点之后 重复1 2直至所有顶点移入队列为止 例对 T1 T2 T3 T4 的一个调度sS W3 y R1 x R2 y W3 x W2 x W3 z R4 z W4 x 它是否可串行化 如可串行化找出其等价的串行执行序列 S W3 y R1 x R2 y W3 x W2 x W3 z R4 z W4 x 并发控制的任务就是对并发执行的事务加以控制 使之按某种可串行化的调度序列来执行 T1 T2 T3 T4 7 8加锁协议 LockProtocol 封锁法是最基本的并发控制方法之一 它可以有多种实现方式 Xlocks Onlyonetypeoflock forbothreadandwrite 相容矩阵 NL nolockX XlockY 相容N 不相容 防止连锁卷回现象的发生 多米诺骨牌 事务结束 EOT TwoPhaseLocking Def1 Inatransaction ifalllocksprecedeallunlocks thenthetransactioniscalledtwophasetransaction Thisrestrictioniscalledtwophaselockingprotocol Def2 Inatransaction ifitfirstacquiresalockontheobjectbeforeoperatingonit itiscalledwell formed 2PL not2PL Theorem IfSisanyscheduleofwell formedand2PLtransactions thenSisserializable 王书p151证明 结论 Well formed 2PL serializableWell formed 2PL unlockupdateatEOT serializableandrecoverable 不会有多米诺现象 Well formed 2PL holdingalllockstoEOT stricttwophaselockingtransaction S X 锁Slock ifreadaccessisintended Xlock ifupdateaccessisintended 1 使用 S X 锁要防止活锁现象发生2 规定 先生请 先服务 S U X 锁 U锁 updatelock ForanupdateaccessthetransactionfirstacquiresaU lockandthenpromoteittoX lock 目的 减少排他时间 提高并发度 减少死锁 7 9死锁的检测处理和防止 死锁 循环等待 谁也无法得到全部资源 活锁 虽然其它事务都在有限长的时间内释放了资源 但某事务就是无法得到想要的资源 活锁较简单 只需稍加修改调度策略 如FIFO死锁 1 防 不允许发生 2 治 允许 能消除 死锁的检测 超时法 某事务等待时间超过某个定值 便认为发生了死锁 该事务被终止 等待图法G V 事务集 Ti TiisatransactioninDBS i 1 2 n E TiwaitsforTj i j 若图中有环路则说明已经发生死锁 何时检测 一旦某个事务等待 周期性进行 死锁的处理 如何处理死锁 选出牺牲事务 最年轻 卷回代价最小 终止牺牲事务释放它所有的锁及资源该事务等待一段时间重启动该事务 系统进行o