外贸做消防的网站,网页微信看朋友圈,html5做网页网站,网络营销和市场营销的区别文章目录 数据库系统原理与实践 笔记 #12事务管理和并发控制与恢复(续)并发控制SQL-92中的并发级别基于锁的协议基于锁的协议的隐患锁的授予封锁协议两阶段封锁协议多粒度粒度层次的例子意向锁类型相容性矩阵多粒度封锁模式基于时间戳的协议基于时间戳协议的正确性基于有效性检… 文章目录 数据库系统原理与实践 笔记 #12事务管理和并发控制与恢复(续)并发控制SQL-92中的并发级别基于锁的协议基于锁的协议的隐患锁的授予封锁协议两阶段封锁协议多粒度粒度层次的例子意向锁类型相容性矩阵多粒度封锁模式基于时间戳的协议基于时间戳协议的正确性基于有效性检查的协议事务Ti的有效性检测 恢复系统故障分类恢复机制数据访问恢复和原子性基于日志的恢复机制数据库修改事务提交并发控制和恢复Undo和Redo操作事务的Undo和Redo 从故障中恢复的Undo和Redo从故障中恢复时 检查点 数据库系统原理与实践 笔记 #12
事务管理和并发控制与恢复(续)
并发控制
数据库必须提供一种机制来保证所有调度(目标)是 冲突可串行化可恢复性最好是无级联 一个策略是一个时间只允许一个事务即产生一个串行调度但是并发性能差目标建立一个能够保证串行化的并发控制协议
SQL-92中的并发级别
可串行化(serializable)—通常保证可串行化的执行可重复读(repeatable read)—只允许读取已提交数据一个事务对相同数据的重复读取要返回相同的值(其他事务不得更改该数据)已提交读(read committed)—默认只允许读取已提交的数据但不要求可重复读未提交读(read uncommitted)—允许读取未提交数据以上所有隔离性级别都不允许脏写即如果一个数据项已经被另外一个尚未提交或中止的事务写入则不允许对该数据项执行写操作通过命令显式设置隔离性级别
set transaction isolation level serializable基于锁的协议
锁是用来控制对数据项的并发访问的一种机制给数据加锁有两种方式 排他锁(X)对数据项即可写又可读使用lock-X指令共享锁(S)对数据项只能读使用lock-S指令 unlock指令释放锁申请锁请求发送给并发控制管理器只有在并发控制管理器授予所需锁之后事务才能继续其操作锁相容性矩阵 表示为comp(A, B)
SXStruefalseXfalsefalse 指令之间的冲突对应于锁类型之间的不相容性 如果被请求所与数据项上已有的锁相容那么事务可以被授予该锁 一个数据项可以同时有多个共享锁如果一个事务在某个数据项上拥有排他锁那么其他事物不能再在这个数据项上加任何锁 如果一个锁不能被授予那么请求该锁的事务必须等待直到该数据项上的其他不相容锁全部释放然后再授予锁 事务执行锁的例子 T 2 : l o c k − S ( A ) ; r e a d ( A ) ; u n l o c k ( A ) ; l o c k − S ( B ) ; r e a d ( B ) ; u n l o c k ( B ) ; d i s p l a y ( A B ) ; T_2:lock-S(A);\\ read(A); \\ unlock(A); \\ lock-S(B); \\ read(B);\\ unlock(B); \\ display(AB); T2:lock−S(A);read(A);unlock(A);lock−S(B);read(B);unlock(B);display(AB); 上述锁无法有效地保证可串行化—如果A在read B的时候被其他事务更新了那么最后的和将会是错误的答案 需指定合理的封锁协议一组规定事务何时对数据项进行加锁、解锁的规则。封锁协议限制了可能的调度数目
基于锁的协议的隐患 考虑下面的调度 T 3 T_3 T3和 T 4 T_4 T4都无法被处理—排他锁lock-S(B)导致 T 4 T_4 T4等待 T 3 T_3 T3释放其在B上的锁而排他锁lock-X(A)导致 T 3 T_3 T3等待 T 4 T_4 T4释放其在A上的锁 这样的情况称为死锁(deadlock)要处理 T 3 T_3 T3或 T 4 T_4 T4其中一个死锁必须回滚并释放锁 大多数封锁协议都会产生死锁 如果并发控制管理器设计得差也有可能导致饿死(starved) 并发控制协议可以通过良好的设计能够避免事务饿死
锁的授予
避免事务饿死的授权加锁方式当事务 T i T_i Ti申请对数据项Q加M型锁时并发控制管理器授权加锁的条件需满足 1.不存在在数据项Q上持有与M型锁冲突的锁的其他事务2.不存在等待对数据项Q加锁且**先于 T i T_i Ti申请加锁的事务 这样一个加锁申请就不会被其后的加锁申请阻塞
封锁协议
令 { T 0 , T 1 , . . . , T n } \{T_0, T_1, ..., T_n\} {T0,T1,...,Tn}是参与调度S的一个事务集如果存在数据项Q使得 T i T_i Ti在Q上持有A型锁。后来 T j T_j Tj在Q上持有B型锁且comp(A,B)false则我们称 T i T_i Ti先于 T j T_j Tj记为 T i → T j T_i\rightarrow T_j Ti→Tj 如果 T i → T j T_i\rightarrow T_j Ti→Tj这一优先意味着在任何等价的串行调度中 T i T_i Ti必须出现在 T j T_j Tj之前 如果调度S是那些遵从封锁协议规则的事务集的可能调度之一我们称调度S在规定的封锁协议下是合法的一个封锁协议当且仅当其所有合法的调度为冲突可串行化时我们称它保证冲突可串行性换句话说对于任何合法的调度其关联的事务优先关系是无循环的
两阶段封锁协议
这是一个能够保证冲突可串行化调度的协议阶段1增长阶段 事务可以获得锁事务不能释放锁 阶段2缩减阶段 事务可以释放锁事务不能获得新锁 封锁点在调度中该事务获得其最后加锁的位置增长阶段结束点两阶段封锁协议保证可串行化可以证明事务可以按照封锁点来排序一种可串行化次序两阶段封锁不能保证不发生死锁两阶段封锁下很有可能发生级联回滚 为了避免这个问题将该协议修改为严格两阶段封锁协议 严格两阶段封锁协议要求未提交事务所写的热河数据在该事务提交之前均以排他方式加锁防止其他事务读取这些数据强两阶段封锁协议更加严格要求是提交之前不得释放任何锁在这个协议下事务可以按其提交顺序串行化
多粒度
将多个数据聚成一组作为同步单元无需单独对单个数据项进行加锁多粒度允许各种大小的数据项并定义数据粒度的层次结构可以图形化的表示为树如果一个事务显式地对树中的某个节点加了锁那么它也给所有统一模式下的该节点的子节点隐式地加了锁锁的力度 细粒度树的低层高并发性锁开销多粗粒度树的高层低并发性锁开销少
粒度层次的例子
如事务 T i T_i Ti需判定某个节点如 r b 1 r_{b_1} rb1是否可以加锁必须从根结点进行遍历至该节点开销大 意向锁类型
除了排他锁及共享锁类型多粒度下还有其他三种锁类型 共享型意向锁(IS)将在树的较低层进行显式封锁但只能加共享锁排他型意向锁(IX)将在树的较低层进行显式封锁可以加排他锁或共享锁共享排他型意向锁(SIX)以该节点为根的子树显式地加了共享锁并且在树的更底层显式地加排他锁 意义意向锁允许较高层的节点被加上共享锁或排他锁而无需从树根遍历到子孙节点来检验锁的相容性提升锁相容检验的效率
相容性矩阵
所有所类型的相容性矩阵
多粒度封锁模式
事务 T i T_i Ti按如下规则对数据项Q加锁 1.必须遵从锁类型相容函数2.必须首先是封锁树的根节点并且可以加任意类型的锁3.仅当事务 T i T_i Ti当前对Q的父节点具有IX或IS时对结点Q可加S或IS锁4.仅当事务 T i T_i Ti当前对Q的父节点具有IX时对节点Q可加X、SIX或IX锁5.仅当 T i T_i Ti未曾对任何节点解锁时 T i T_i Ti可对节点加锁(满足两阶段封锁)6.仅当 T i T_i Ti当前不持有Q的子节点的锁时 T i T_i Ti可对节点Q解锁 加锁按自顶向下的顺序锁的释放按自底向上的顺序
基于时间戳的协议
对于系统中每个事务 T i T_i Ti我们把一个唯一的固定时间戳和它联系起来此时间戳记为 T S ( T i ) TS(T_i) TS(Ti)该时间戳是在事务 T i T_i Ti开始执行前由数据库系统赋予的。若事务 T i T_i Ti已被赋予时间戳 T S ( T i ) TS(T_i) TS(Ti)并且有一新事务 T j T_j Tj进入系统则 T S ( T i ) T S ( T j ) TS(T_i)TS(T_j) TS(Ti)TS(Tj)事务的时间戳决定了串行化顺序每个数据项Q需要与两个时间戳值相关联 W-timestamp(Q)表示成功执行write(Q) 的所有事务的最大时间戳R-timestamp(Q)表示成功执行read(Q) 的所有事务的最大时间戳 时间戳排序协议保证任何有冲突的read或write操作按照时间戳顺序执行假设事务 T i T_i Ti发出指令read(Q) 1.若 T S ( T i ) TS(T_i) TS(Ti) W-timestamp(Q)则 T i T_i Ti需要读入的Q值已被覆盖read操作被拒绝 T i T_i Ti回滚2.若 T S ( T i ) ≥ TS(T_i)\ge TS(Ti)≥W-timestamp(Q)执行read操作R-timestamp(Q)被设置为max(R-timestamp(Q), T S ( T i ) TS(T_i) TS(Ti)) 假设事务 T i T_i Ti发出指令write(Q) 1.若 T S ( T i ) TS(T_i) TS(Ti) R-timestamp(Q)则 T i T_i Ti所需更新Q的值已过时write操作被拒绝 T i T_i Ti回滚2.若 T S ( T i ) TS(T_i) TS(Ti) W-timestamp(Q)则 T i T_i Ti试图写入的Q值已过时write操作被拒绝 T i T_i Ti被饿死3.其他情况执行write操作将W-timestamp(Q)设置为 T S ( T i ) TS(T_i) TS(Ti)
基于时间戳协议的正确性
时间戳排序协议保证冲突可串行化冲突操作按时间戳的顺序来处理保证无死锁不存在等待可能有长事务饿死可能产生不可恢复的调度事务可恢复性与事务提交顺序有关
基于有效性检查的协议
有效性检查协议适用于大部分只读事务的情况 要求每个事务 T i T_i Ti在其生命周期中按两个或三个阶段执行 1.读阶段事务 T i T_i Ti的所有write操作都是对局部临时变量进行的2.有效性检查阶段事务 T i T_i Ti进行有效性检查判断是否可以write操作而不违反可串行性3.写阶段如果 T i T_i Ti已通过有效性检查则保存任何写操作结果的临时局部变量值被复制到数据库中。只读事务不进入此阶段 每个事务必须按照以上顺序经历这些过程。然而并发执行的事务三个阶段可以是交叉执行的每个事务 T i T_i Ti都有三个不同的时间戳 Start( T i T_i Ti)事务 T i T_i Ti开始执行的时间Validation( T i T_i Ti)事务 T i T_i Ti完成读阶段 利用时间戳Validation( T i T_i Ti)的值通过时间戳排序技术决定可串行化顺序以增加并发性即 T S ( T i ) V a l i d a t i o n ( T i ) TS(T_i) Validation(T_i) TS(Ti)Validation(Ti)
事务Ti的有效性检测
对于任何满足 T S ( T k ) T S ( T i ) TS(T_k) TS(T_i) TS(Tk)TS(Ti)的事务 T k T_k Tk必须满足下面两条件之一 F i n i s h ( T k ) S t a r t ( T i ) Finish(T_k) Start(T_i) Finish(Tk)Start(Ti) S t a r t ( T i ) F i n i s h ( T k ) V a l i d a t i o n ( T i ) Start(T_i) Finish(T_k) Validation(T_i) Start(Ti)Finish(Tk)Validation(Ti)并且需保证 T k T_k Tk锁写的数据项集与 T i T_i Ti所读数据项集不想交即 T k T_k Tk的写操作不会影响到 T i T_i Ti的读操作 则有效性检测通过 T i T_i Ti可以进入写阶段并提交否则测试失败 T i T_i Ti中止有效性检查协议能够自顶预防级联回滚保证无死锁
恢复系统
故障分类
事务故障 逻辑错误由于某些内部条件而无法继续正常执行系统错误系统进入一种不良状态如死锁结果事务无法继续正常执行 系统崩溃硬件故障或者是数据库软件或操作系统的漏洞导致易失性存储器内容丢失并使得事务处理停止磁盘故障由于磁头损坏或故障造成磁盘块上的内容丢失 毁坏是可探测的磁盘驱动器用校验和来检测故障
恢复机制
保证数据库一致性以及事务的原子性的算法称为回复算法 在正常事务处理时采取措施保证有足够的信息可用于故障恢复故障发生后采取措施将数据库内容恢复到某个保证数据库一致性、事件原子性及持久性的状态 存储器类型 易失性存储器(volatile storage)易失性存储器中的信息在系统崩溃时通常无法保存下来非易失性存储器(nonvolatile storage)非易失性存储器中的信息在系统崩溃时可以保存下来稳定存储器(stable storage)稳定存储器中的信息永不丢失
数据访问 物理块是位于磁盘上的块 缓冲块是临时位于主存的块 磁盘和主存间的块移动是由下面两个操作引发的**input(B)**传送物理块B到主存**output(B)**传送缓冲块B至硬盘并替换磁盘上相应的物理块 例子 每个事务 T i T_i Ti有一个私有工作区用于保存 T i T_i Ti所访问及更新的所有数据项的拷贝 T i T_i Ti的工作区中保存的每一个数据项X记为 x i x_i xi 使用下面两个操作里完成数据在工作区和系统缓冲区之间的传递 read(X) 将数据项X的值赋予局部变量 x i x_i xiwrite(X) 将局部变量 x i x_i xi的值赋予缓冲块中的数据项X注意: output( B x B_x Bx) 不需要立刻在write(X)后执行。系统会在它认为合适的时候执行output操作 事务必须在第一次访问X之前执行read(X)**write(X)**可以在事务被提交前的任意时刻执行
恢复和原子性
为保证原子性我们必须在修改数据库本身之前首先向稳定存储器输出信息描述要做的修改目的确保由中止事务所做的修改不会持久保存与数据库中即回滚该中止事务基于日志的恢复系统
基于日志的恢复机制
日志保存于稳定存储器中日志是日志记录的序列它记录数据库中的所有更新活动当一个事务 T i T_i Ti开始时它记录 T i s t a r t T_i \ start Ti start事务 T i T_i Ti执行write(X) 前日志记录 T i X , V 1 , V 2 T_i\ X, V_1, V_2 Ti X,V1,V2 V 1 V_1 V1是在write之前X的值(旧值) V 2 V_2 V2是需要写入X的值(新值)当 T i T_i Ti结束了最后一条指令时 T i c o m m i t T_i\ commit Ti commit写入日志当事 T i T_i Ti中止时日志记录 T i a b o r t T_i\ abort Ti abort使用日志的两种方法延迟的数据库修改事务提交后还未修改立即的数据库修改事务提交前已修改
数据库修改
立即修改模式允许在事务提交前将未提交的事务更新至缓冲区或磁盘延迟修改模式直到事务提交时都没有更新到缓冲区/磁盘简化了恢复但是多了存储本地副本的开销日志记录的更新必须在数据项被write(数据库修改)之前完成
事务提交
当事务将其关于提交的日志记录输出到稳定存储器时该事务被认为已提交之前的所有日志记录必须都已经输出事务提交时由该事务执行的write操作结果可能仍在缓冲区随后被输出
并发控制和恢复
在并发事务中所有事务共享一个磁盘缓冲区和日志一个缓冲块中的数据项可以来自多个事务的更新假设如果一个事务 T i T_i Ti习概了一个数据项那么在 T i T_i Ti提交前其他事务不能修改同一个数据项(即不允许脏写) 未提交事务的更新不能被其他事务所见可以通过在被更新数据项上获取排他锁并持有该锁直到事务提交位置来保证严格两阶段封锁 不同事务的日志记录在日志中穿插(interspersed)存储
Undo和Redo操作
对日志记录 T i , X , V i , V 2 T_i, X, V_i, V_2 Ti,X,Vi,V2的Undo操作将旧值 V 1 V_1 V1写入X对日志记录 T i , X , V 1 , V 2 T_i, X, V_1, V_2 Ti,X,V1,V2的Redo操作将新值 V 2 V_2 V2写入X
事务的Undo和Redo
undo( T i T_i Ti) 将事务 T i T_i Ti所更新的所有数据项的值恢复成旧值回到 T i T_i Ti的最后一条日志记录 每次数据项X被恢复成旧值日志记录 T i , X , V T_i, X, V Ti,X,V会被写入当事务的undo操作完成时日志记录 T i a b o r t T_i \ abort Ti abort被写入 redo( T i T_i Ti) 将事务 T i T_i Ti所更新的所有数据项的值置为新值从 T i T_i Ti的第一条日志记录开始执行这个情况下没有任何日志记录
从故障中恢复的Undo和Redo
从故障中恢复时
当日志是以下状态时事务 T i T_i Ti需要undo操作 有日志 T i s t a r t T_i\ start Ti start没有日志 T i c o m m i t T_i\ commit Ti commit和 T i a b o r t T_i\ abort Ti abort 当日志是以下状态时事务 T i T_i Ti需要进行redo操作 有日志 T i s t a r t T_i\ start Ti start有日志 T i c o m m i t T_i\ commit Ti commit或 T i a b o r t T_i\ abort Ti abort 如果事务 T i T_i Ti之前执行了undo操作 T i a b o r t T_i\ abort Ti abort被写入到日志接着故障发生。为了从故障中恢复 T i T_i Ti要执行redo操作这样的redo操作重新执行了原先的所有操作包括重新存储旧值称为重复历史看起来很浪费但是最大程度地简化了恢复
检查点
对于日志中的所有事务做Redo/Undo 1.如果系统已经运行了很长一段时间那么处理整个日志很浪费时间2.那些已经将输出更新到数据库的事务没必要redo 流线型恢复过程周期性地执行检查点 1.将当前位于主存的所有日志记录输出到稳定存储器上2.将所有修改了的缓冲块输出到磁盘上3.将一个日志记录 c h e c k p o i n t L checkpoint\ L checkpoint L输出到稳定存储器执行检查点时所有数据更新都停止 恢复时我们仅考虑在检查点前最近开始的事务 T i T_i Ti及在 T i T_i Ti后开始的事务 从日志末尾反向扫描找到最近的 c h e c k p o i n t L checkpoint\ L checkpoint L记录只要在L未提交/中止的事务或者在检查点后开始的事务需要redo或undo检查点之前的已提交或者中止的事务已经将其更新输出到了稳定存储器 undo操作可能需要一些早期的日志 继续从日志末尾反向扫描直到找到在L的每个事务 T i T_i Ti的记录 T i s t a r t T_i\ start Ti start
