数据库保护学习.pptx

事务概念事务定义事务是由一系列操作序列构成的程序执行单元，这些操作要么都做，要么都不做，是一个不可分割的工作单位。例如银行转帐。SQL中事务的定义事务以Begin transaction开始，以Commit work或 Rollback work结束。Commit work表示提交，事务正常结束。Rollback work表示事务非正常结束，撤消事务已做的操作，回滚到事务开始时状态。第1页/共58页事务概念示例银行转帐：事务T从A帐户过户50￥到B帐户。T：read(A);A:=A 50;write(A);read(B);B:=B+50;write(B);read(X)：从数据库传送数据项X到事务的工作区中。write(X)：从事务的工作区中将数据项X写回数据库。第2页/共58页事务概念事务特性(ACID)原子性(Atomicity)事务中包含的所有操作要么全做，要么全不做。原子性由恢复机制实现。一致性(Consistency)事务的隔离执行必须保证数据库的一致性。事务开始前，数据库处于一致性的状态；事务结束后，数据库必须仍处于一致性状态。数据库的一致性状态由用户来负责。如银行转帐，转帐前后两个帐户金额之和应保持不变（意大利香肠）。第3页/共58页事务概念隔离性(Isolation)系统必须保证事务不受其它并发执行事务的影响。对任何一对事务T1，T2，在T1看来，T2要么在T1开始之前已经结束，要么在T1完成之后再开始执行。隔离性通过并发控制机制实现。持久性(Durability)一个事务一旦提交之后，它对数据库的影响必须是永久的。系统发生故障不能改变事务的持久性。持久性通过恢复机制实现。第4页/共58页事务状态活动状态活动状态失败状态失败状态部分部分提交状态提交状态提交状态提交状态中止状态中止状态初始状态初始状态事务无法继事务无法继续正常执行续正常执行事务回滚，数据库恢事务回滚，数据库恢复到事务开始前状态复到事务开始前状态最后一条语最后一条语句被执行后句被执行后成功完成，永成功完成，永久写入数据库久写入数据库第5页/共58页并发执行并行 Vs 串行基本比较并行事务会破坏数据库的一致性。串行事务效率低。并行的优点一个事务由不同的步骤组成，所涉及的系统资源也不同。这些步骤可以并发执行，以提高系统的吞吐量。系统中存在着周期不等的各种事务，串行会导致难于预测的时延。如果各个事务所涉及的是数据库的不同部分，采用并发会减少平均响应时间。第6页/共58页并发执行核心问题在保证一致性的前提下最大限度地提高并发度。事务执行示例T1:read(A);A:=A 50;write(A);read(B);B:=B+50;write(B);T2:read(A);temp:=A0.1 A:=A temp;write(A);read(B);B:=B+temp;write(B);从A过户50￥到B从A过户存款的10%到B开始状态：A=1000￥B=2000￥A+B=3000￥第7页/共58页并发执行 read(A);A:=A 50;write(A);read(B);B:=B+50;write(B);read(A);temp:=A0.1 A:=A temp;write(A);read(B);B:=B+temp;write(B);T1T2A=950￥B=2050￥结束状态：A=855￥B=2145￥A+B=3000￥串串行行调调度度1 1第8页/共58页并发执行 read(A);A:=A 50;write(A);read(B);B:=B+50;write(B);read(A);temp:=A0.1 A:=A temp;write(A);read(B);B:=B+temp;write(B);T1T2A=900￥B=2100￥结束状态：A=850￥B=2150￥A+B=3000￥串串行行调调度度2 2第9页/共58页并发执行事务的调度事务的执行顺序称为一个调度，表示事务的指令在系统中执行的时间顺序。一组事务的调度必须保证包含了所有事务的操作指令一个事务中指令的顺序必须保持不变。串行调度在串行调度中，属于同一事务的指令紧挨在一起。对于有n个事务的事务组，可以有n！个有效调度。并行调度在并行调度中，来自不同事务的指令可以交叉执行。当并行调度等价于某个串行调度时，则称它是正确的。第10页/共58页并发执行 read(A);A:=A 50;write(A);read(B);B:=B+temp;write(B);T1T2A=950￥B=2000￥结束状态：A=855￥B=2145￥A+B=3000￥read(B);B:=B+50;write(B);read(A);temp:=A0.1 A:=A temp;write(A);A=855￥B=2000￥A=855￥B=2050￥并并行行调调度度3第11页/共58页并发执行 read(A);A:=A 50;B:=B+temp;write(B);T1T2A=1000￥B=2000￥结束状态：A=950￥B=2100￥A+B=3050￥write(A);read(B);B:=B+50;write(B);read(A);temp:=A0.1 A:=A temp;write(A);read(B);A=900￥B=2000￥A=950￥B=2000￥A=950￥B=2050￥并并行行调调度度4第12页/共58页并发执行SQL中一致性级别的定义serializable：一个调度的执行必须等价于一个串行调度的结果。repeatable read：只允许读取已提交的记录，并要求一个事务对同一记录的两次读取之间，其它事务不能对该记录进行更新。read committed：只允许读取已提交的记录，但不要求可重复读。read uncommitted：允许读取未提交的记录。第13页/共58页并发执行read(A);A1:=A;read(B);B1:=B;A1+B1=2950;read(B);B:=B+50;write(B);T1T2A=1000￥B=2000￥read(A);A:=A 50;write(A);读读脏脏数数据据第14页/共58页并发执行 read(A);A1:=AT1T2A=1000￥B=2000￥read(A);A:=A 50;write(A);read(B);B:=B+50;write(B);不不能能重重复复读读read(B);B1:=BA1+B1=3050A=950￥B=2050￥第15页/共58页并发执行select*from SCwhere CNO=C01 and SNO=S01T1T2发生幻象insert into SC values(S01,C01,null)第16页/共58页可恢复性事务的恢复：一个事务失败了，应该能够撤消该事务对数据库的影响。如果有其它事务读取了失败事务写入的数据，则该事务也应该撤消。可恢复调度read(A);write(A);T1T2read(B);commit;read(A);commit不可恢复的调度不可恢复的调度可恢复调度：可恢复调度：对于每对事务对于每对事务T1T1与与T2T2，如果如果T2T2读取了读取了T1T1所写的数所写的数据，则据，则T1T1必须先于必须先于T2T2提交提交第17页/共58页可恢复性无级联调度read(A);read(B);write(A);T1T2read(A)write(A);级联调度：级联调度：由于一个事务故障而由于一个事务故障而导致一系列事务回滚导致一系列事务回滚无级联调度：无级联调度：对于每对事务对于每对事务T1T1与与T2T2，如果如果T2T2读取了读取了T1T1所写的所写的数据，则数据，则T1T1必须在必须在T2T2读读取之前提交取之前提交T2read(A)无级联调度必是可恢复调度无级联调度必是可恢复调度第18页/共58页可串行化如何判定并行调度与一个串行调度等价？冲突指令指令的顺序考虑一个调度S中的两条连续指令（仅限于read与 write操作）Ii与Ij，分别属于事务Ti与Tj，Ii=read(Q),Ij=read(Q)Ii=read(Q),Ij=write(Q)Ii=write(Q),Ij=read(Q);Ii=write(Q),Ij=write(Q);在 情况下，Ii与Ij的次序无关紧要。其余情况下，Ii与Ij的次序不同，其执行结果也不同，数据库最终状态也不同。第19页/共58页可串行化冲突指令当两条指令是不同事务在相同数据项上的操作，并且其中至少有一个是write指令时，则称这两条指令是冲突的。如在、情况下，Ii与Ij 是冲突的。非冲突指令交换次序不会影响调度的最终结果。冲突等价如果调度S可以经过一系列非冲突指令交换转换成调度S，则称调度S与S是冲突等价的。第20页/共58页可串行化read(A);write(A);read(B);write(B);T1T2read(B);write(B);并并行行调调度度3read(A);write(A);read(A);write(A);read(B);write(B);T1T2write(B);read(A);write(A);read(B);read(A);write(A);read(B);write(B);write(B);read(A);write(A);read(B);read(A);write(A);read(B);write(B);write(B);read(A);write(A);read(B);第21页/共58页可串行化冲突可串行化当一个调度S与一个串行调度冲突等价时，则称该调度是冲突可串行化的。如并行调度3是冲突可串行化的。read(A);T1T2write(A);write(A);非冲突串行化的例子：存在结果相同，但非冲突等价的调度。第22页/共58页可串行化read(A);A:=A-50write(A);T1T2冲突指令冲突指令T1T2read(B);B:=B-10write(B);read(B);B:=B+50write(B);read(A);A:=A+10write(A);read(A);A:=A-50write(A);read(B);B:=B+50write(B);read(B);B:=B-10write(B);read(A);A:=A+10write(A);A=950￥B=2000￥A=950￥B=1990￥A=950￥B=2040￥A=960￥B=2040￥A=960￥B=2040￥A=950￥B=2050￥第23页/共58页可串行化视图可串行化考虑关于某个事务集的两个调度S，S，若调度S，S满足以下条件，则称它们是视图等价的：对于每个数据项Q，若事务Ti在调度S中读取了Q的初始值，那么Ti在调度S中也必须读取Q的初始值。对于每个数据项Q，若事务Ti在调度S中执行了read(Q)，并且读取的值是由Tj产生的，那么Ti在调度S中读取的Q值也必须是由Tj产生的。对于每个数据项Q，若在调度S中有事务执行了最后的write(Q)，则在调度S中该事务也必须执行最后的write(Q)。第24页/共58页可串行化注：条件、保证两个调度中的每个事务都读取相同的值，从而进行相同的计算；条件、保证两个调度得到最终相同的系统状态。read(A);write(A);read(B);write(B);read(A);write(A);read(B);write(B);T1T2 read(A);write(A);read(B);write(B);read(A);write(A);read(B);write(B);T1T2由由T1T1产生的产生的A A值值调度执行前的调度执行前的A A值值非视图等价非视图等价第25页/共58页可串行化 read(A);write(A);read(B);write(B);read(A);write(A);read(B);write(B);T1T2read(B);write(B);read(A);write(A);T1T2由由T1T1产生的产生的A A值值 read(A);write(A);read(B);write(B);由由T1T1产生的产生的A A值值视图等价视图等价第26页/共58页可串行化视图可串行化如果某个调度视图等价于一个串行调度，则称该调度是视图可串行化的。冲突可串行化调度一定是视图可串行化的。存在视图可串行化但非冲突可串行化的调度。read(Q);T1T2write(Q);write(Q);write(Q);T3视图等价视图等价盲目写操作盲目写操作第27页/共58页可串行化冲突可串行化判定优先图(precedence graph)一个调度S的优先图是这样构造的：它是一个有向图G=（V，E），V是顶点集，E是边集。顶点集由所有参与调度的事务组成，边集由满足下述条件之一的边Ti Tj组成：在Tj执行read(Q)之前，Ti执行write(Q)。在Tj执行write(Q)之前，Ti执行read(Q)。在Tj执行write(Q)之前，Ti执行write(Q)。第28页/共58页可串行化T1T2并并行行调调度度3 3T1T2read(A);write(B);T1T2write(A);read(B);write(B);并并行行调调度度4read(A);write(A);read(B);T1T2read(A);write(A);read(B);write(B);read(B);write(B);read(A);write(A);第29页/共58页可串行化如果优先图中存在边TiTj，则在任何等价于S的串行调度S中，Ti都必须出现在Tj之前。冲突可串行化判定准则如果调度S的优先图中有环，则调度S是非冲突可串行化的。如果图中无环，则调度S是冲突可串行化的。T1T2T1T2并行调度并行调度3 3是冲是冲突可串行化的突可串行化的并行调度并行调度4 4是非是非冲突可串行化的冲突可串行化的第30页/共58页可串行化与冲突可串行化等价的串行顺序串行顺序可由拓扑排序得到，求出与优先图的偏序相一致的线序。T1T3T2T4T1T2T3T4T1T3T2T4第31页/共58页可串行化视图可串行化判定read(Q);T1T2write(Q);write(Q);write(Q);T3T1T2T3无用的写操作无用的写操作第32页/共58页可串行化带标记的优先图的构造设调度S包含了事务T1,T2,Tn，设Tb,Tf是两个虚事务，其中Tb为S中所有write(Q)操作，Tf为S中所有read(Q)操作。在调度S的开头插入Tb，在调度S的末尾插入Tf，得到一个新的调度S。如果Tj读取Ti写入的数据项的值，则加入边Ti Tj。删除所有关联无用事务的边。如果在优先图中不存在从Ti到Tf的通路，则Ti是无用事务。对于每个数据项Q，如果Tj读取Ti读取写入的Q值，Tk执行write(Q)操作且TkTb，则：第33页/共58页可串行化如果Ti=Tb且TjTf，则在带标记的优先图中插入边Tj Tk。如果TiTb且Tj=Tf，则在带标记的优先图中插入边Tk Ti。如果TiTb且TjTf，则在带标记的优先图中插入边Tk Ti与Tj Tk。其中p是一个唯一的，在前面边的标记中未曾用过的大于0的整数。第34页/共58页可串行化read(A);T1T2write(A);write(A);T1TfTbT20000第35页/共58页可串行化read(Q);T1T2write(Q);write(Q);write(Q);T3T1T2T3Tb0Tf0000第36页/共58页可串行化read(Q);T1T2write(Q);write(Q);write(Q);T3T1T2T3Tb0Tf0000read(Q);11第37页/共58页可串行化T1T2T3Tb0Tf00001T1T2T3Tb0Tf00001第38页/共58页并发控制封锁的定义封锁就是一个事务对某个数据对象加锁，取得对它一定的控制，限制其它事务对该数据对象使用。并发控制的基本方法就是封锁。封锁的类型排它锁（X锁，eXclusive lock）：事务T对数据对象R加上X锁，则其它事务对R的任何封锁请求都不能成功，直至T释放R上的X锁。共享锁（S锁，Share lock）：事务T对数据对象R加上S锁，则其它事务对R的X锁请求不能成功，而对R的S锁请求可以成功。第39页/共58页并发控制相容矩阵相容矩阵相容请求相容请求不相容请求不相容请求第40页/共58页并发控制封锁粒度封锁对象：属性值、属性值几何、元组、关系、某索引项、整个索引、整个数据库、物理页、块。封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度小，则并发度高，封锁机构复杂，开销高。理想的情况是只封锁与规定的操作有关的的数据对象，这些数据对象称作事务的完整性相关域。第41页/共58页并发控制封锁协议保持到事务结束时才释放的锁称作长锁。在事务中途就可以释放的锁称作短锁。0级封锁协议级封锁协议BEGIN短X锁EOTlock-X(A);read(A);A:=A 50;write(A);rollback；read(A);A1:=A;T1 T2 不能保证不能保证孤立退出孤立退出第42页/共58页并发控制1级封锁协议级封锁协议BEGIN长X锁EOTread(A);A1:=A 1;lock-X(A);A:=A1 1;write(A);commit；lock-X(A)read(A);A:=A 1;write(A)；commit；T1 T2 不能保证不能保证丢失修改丢失修改第43页/共58页并发控制2级封锁协议级封锁协议BEGIN 短S锁长X锁EOTlock-S(A);read(A);A1:=A;unlock(A);lock-S(A);read(A);A1:=A;unlock(A);commit；lock-X(A)read(A);A:=A 1;write(A)；commit；T1 T2 不能保证不能保证可重复读可重复读第44页/共58页并发控制3级封锁协议级封锁协议BEGIN 长S锁长X锁EOT第45页/共58页并发控制封锁方法直接封锁事务对它要进行存取的数据对象直接申请加锁。第46页/共58页并发控制分层封锁数据对象从大到小有一种层次关系，当封锁了外层数据对象时也就意味着同时封锁了它的所有内层数据对象。数据库数据库段段关系关系元组元组第47页/共58页并发控制意向（预约）封锁在分层封锁中，封锁了上层节点就意味着封锁了所有内层节点。如果有事务T1对某元组加了S锁，而事务T2对该元组所在的关系加了X锁，因而隐含地X封锁了该元组，从而造成矛盾。引入意向锁I（Intend）：当为某节点加上I锁，表明其某些内层节点已发生事实上的封锁，防止其它事务再去显式封锁该节点。I锁的实施是从封锁层次的根开始，依次占据路径上的所有节点，直至要真正进行显式封锁的节点的父节点为止。第48页/共58页并发控制相容矩阵第49页/共58页并发控制更精细的相容矩阵第50页/共58页并发控制死锁(Deadlock)定义两个事务都封锁了一些数据对象，并相互等待对方释放另一些数据对象以便对其封锁，结果两个事务都不能结束，则发生死锁。死锁发生的条件互斥条件：事务请求对资源的独占控制。等待条件：事务已持有一定资源，又去申请并等待其它资源。非抢占条件：直到资源被持有它的事务释放之前，不可能将该资源强制从持有它的事务夺去。第51页/共58页并发控制循环等待条件：存在事务相互等待的等待圈。定理：在条件成立的前提下，条件是死锁存在的充分必要条件。R2R1R3第52页/共58页并发控制解决死锁的方法预防死锁预先占据所需的全部资源。所有资源预先排序。预先确定存取顺序。事务退出已占有资源。死锁检测和恢复第53页/共58页并发控制两段锁协议(Two-phase Locking)内容：在对任何数据进行读写之前，事务首先要获得对该数据的封锁。在释放一个封锁之后，事务不再获得任何其它封锁。即事务分为两个阶段：生长阶段：获得封锁。收缩阶段：释放封锁。定理：若所有事务均遵从两段锁协议，则这些事务的所有并行调度都是可串行化的。第54页/共58页并发控制示例lock-S(A)lock-S(B)lock-X(C)unlock(A)unlock(C)unlock(B)遵从两段锁协议。lock-S(A)unlock-S(A)lock-S(B)lock-X(C)unlock(C)unlock(B)不遵从两段锁协议。遵从两段锁协议仍可能发生死锁lock-S(A);lock-X(B);wait.lock-S(B)lock-X(A)wait T1 T2 T1:lock-S(A)lock-S(B)unlock(A)unlock(B)T2:lock-S(A)lock-S(B)unlock(A)unlock(B)第55页/共58页恢复定义恢复是把数据库从错误状态恢复到某一正确状态的功能，从而确保数据库的一致性。恢复的基本原理是冗余，即数据库中任一部分的数据可以根据存储在系统别处的冗余数据来重建。日志日志文件是用来记录数据库的每一次更新活动的文件，由系统自动记录。日志内容包括：记录名、旧记录值、新记录值、事务标识符、操作标识符等。第56页/共58页恢复基本的恢复操作：对圆满事务所做过的修改操作应执行redo操作，即重新执行该操作，修改对象被赋予新记录值。对夭折事务所做过的修改操作应执行undo操作，即撤消该操作，修改对象被赋予旧记录值。先写日志的原则（WAL）对于尚未提交的事务，在将DB缓冲区写到外存之前，必须先将日志缓冲区内容写到外存去。如果先写DB，则可能在写的中途发生系统崩溃，导致内存缓冲区内容丢失，而外存DB处于不一致状态，由于日志缓冲区内容已破坏，导致无法对DB恢复。日志记录将要发生何种修改。写入DB表示实际发生何种修改。第57页/共58页感谢您的观看。第58页/共58页