第七章 恢复系统

第七章恢复系统第1页，共54页，2023年，2月20日，星期三因为有故障，才需要恢复。计算机可能发生的故障：电源、软件、机房失火、人为破坏等。恢复机制是数据库系统必不可少的组成部分，一旦故障发生，数据库必须保持事务的原子性和持久性。第2页，共54页，2023年，2月20日，星期三7．1故障分类7．2存贮器结构7．3恢复与原子性7．4基于日志的恢复7．5影子分页7．8非易失性存储器数据的恢复7．9高级恢复技术7．7缓冲区管理7．6并发事务的恢复第3页，共54页，2023年，2月20日，星期三7．1故障分类第4页，共54页，2023年，2月20日，星期三1．事务故障：a.逻辑错误。事务由于某些内部条件而无法继续正常执行。如：非法输入、找不到数据、溢出等b.系统错误。系统进入一种不良状态（如死锁），结果事务无法正常执行。2．系统崩溃：硬件故障，或数据库软件、操作系统漏洞，导致易失性存储器内容的丢失，并使得事务处理终止。而非易失存储器完好。3．磁盘故障：在数据传送操作过程中由于磁头损坏或故障造成磁盘上数据的丢失。

第5页，共54页，2023年，2月20日，星期三

恢复算法：①在正常事务处理时采取的措施，保证有

足够的信息可用于故障恢复。②故障发生后采取的措施，将数据库内容

恢复到某个保证数据一致性，事务原子

性及持久性的状态。第6页，共54页，2023年，2月20日，星期三7．2存贮器结构

第7页，共54页，2023年，2月20日，星期三1．存贮器类型易失存储器：主存、高速缓存非易失存储器：磁盘、磁带稳定性存储器：通过一些技术手段实现2．稳定存贮器的实现RAID第8页，共54页，2023年，2月20日，星期三3．数据访问给一些概念和记号数据库常驻在磁盘上，以块为单位存贮。一块可以包含多个数据项。假设没有数据块是跨块的。输入/出操作以块为单位，磁盘上的块为物理块，临时位于主存的块为缓冲块。内存中用以存放块的区域称为缓冲区。第9页，共54页，2023年，2月20日，星期三磁盘和主存间的块移动由下面两个操作完成。(1)input（B）传送物理块B至主存。(2)output（B）传送缓冲块B至磁盘，并

替换磁盘上相应的物理块。第10页，共54页，2023年，2月20日，星期三Ti的私有工作区，在事务初始化时创建，事务提交或中止时删除。Ti的工作区中保存的每一个数据项X记为Xi，Ti通过在其工作区和系统缓冲区之间传送数据与数据库交互，所用的两个操作：(1)Read(x)将数据项X的值赋予局部变量xi。

a.若X所在的块Bx，不在内存，则发指令input(Bx)。b.将缓冲块Bx中X的值赋予xi(2)Write(x)将局部变量xi的值赋予缓冲块

中的数据项X。

a.若X所在的块Bx不在内存，则发指令input(Bx)。b.将xi的值赋予缓冲块Bx中的X第11页，共54页，2023年，2月20日，星期三7．3恢复与原子性

第12页，共54页，2023年，2月20日，星期三发生故障和简单的故障恢复过程，可能导致数据库的不一致。为了保持原子性的目标，需记录对数据修改的描述信息。例：考虑事务Ti，将￥50从帐户A转到帐户B，A和B的初值分别为1000和2000，假设Ti执行过程中系统发生崩溃，且发生在output(BA)之后，output(BB)之前，由于内存的内容丢失，无法知道事务的结局。可以调用恢复过程。第13页，共54页，2023年，2月20日，星期三

重新执行Ti,A的值变为900而不是950，系统产生不一致。不重新执行Ti,A的值变为950而B的值为2000，系统仍然不一致。第14页，共54页，2023年，2月20日，星期三7．4基于日志的恢复

第15页，共54页，2023年，2月20日，星期三日志：记录数据库中的所有更新活动。包括以下段:*事务标识是执行Write操作的事务的唯一标识*数据项标识是所写数据项的唯一标识，通常是数据项在磁盘上的位置。*旧值是数据项的写前值。*新值是数据项的写后值。日志记录：<Ti,start>：事务Ti开始<Ti,Xj,V1,V2>：事务Ti对Xj执行写操作，Xj的写前值是V1，写后值是V2。<Ti,commit>：事务Ti提交<Ti,abort>：事务Ti中止

第16页，共54页，2023年，2月20日，星期三

事务执行写操作前，生成该次写操作的日志。为了使用日志恢复数据库，日志必须放在稳定存储器上。

第17页，共54页，2023年，2月20日，星期三

1．延迟的数据库修改延迟修改技术通过在日志中记录所有的数据库修改，将一个事务的所有write操作拖延到事务部分提交时才执行，从而保证事务的原子性。当事务部分提交时，日志上有关该事务的信息被用来执行延迟写。在事务完成其执行前系统崩溃，或事务中止，则忽略日志上的信息。事务Ti的执行过程：Ti开始执行前，向日志中写入记录<Ti,start>，Ti的一次write(X)操作，导致向日志中写入一条新记录。当Ti部分提交时，向日志中写入记录<Ti,commit>。

第18页，共54页，2023年，2月20日，星期三当Ti部分提交时，日志中相关的记录用来执行延迟写。执行更新时可能发生故障，更新前将日志记录写到稳定存储器上。然后进行更新，事务提交。

第19页，共54页，2023年，2月20日，星期三仍然用银行的例子说明：T0：read(A)T1:read(C)A:=A-50C:=C-100write(A)write(C)read(B)B:=B+50write(B)设执行顺序<T0,T1>，执行前，A,B,C的值分别为1000，2000，700。第20页，共54页，2023年，2月20日，星期三日志：<T0,strat><T0,A,950><T0,B,2050><T0,commit><T1,strat><T1,C,600><T1,commit>第21页，共54页，2023年，2月20日，星期三利用日志，可以恢复易失性存储器上的信息丢失恢复过程：

redo(Ti):将事务Ti更新的所有数据项的值置为新值。故障发生后，恢复子系统检查日志，以确定需要重新执行的事务。事务Ti需要重新执行，当且仅当日志中有<Ti,start>和<Ti,commit>。如果系统在事务完成后崩溃，用日志信息可以将系统恢复到系统完成后的一致状态。

第22页，共54页，2023年，2月20日，星期三

<T0,strat><T0,A,950><T0,B,2050>此时发生崩溃，系统重新启动，不必做redoA,B的值仍为1000和2000。

第23页，共54页，2023年，2月20日，星期三

<T0,strat><T0,A,950><T0,B,2050><T0,commit><T1,strat><T1,C,600>此时发生崩溃，系统重新启动，做redo（T0)A的值950,B的值2050,C的值700

第24页，共54页，2023年，2月20日，星期三

<T0,strat><T0,A,950><T0,B,2050><T0,commit><T1,strat><T1,C,600><T1,commit>此时发生崩溃，系统重新启动，做redo（T0)和redo（T1)。A的值950,B的值2050,C的值600第25页，共54页，2023年，2月20日，星期三2．立即的数据库修改立即更新技术允许数据库修改在事务仍处于活跃状态时就进行数据库修改。活跃事务所做的数据库修改称为未提交修改。发生故障时，利用日志记录将数据库恢复成旧值。用undo操作完成。

事务Ti的执行过程：Ti开始执行前，向日志中写入记录<Ti,start>，Ti的一次write(X)操作，导致向日志中写入一条新记录。当Ti部分提交时，向日志中写入记录<Ti,commit>。第26页，共54页，2023年，2月20日，星期三还用银行的例子。日志：<T0,strat><T0,A,1000，950><T0,B,2000，2050><T0,commit><T1,strat><T1,C,700，600><T1,commit>第27页，共54页，2023年，2月20日，星期三利用日志，可以恢复易失性存储器上的信息丢失恢复过程：

undo(Ti):将事务Ti更新的所有数据项恢复为旧值。redo(Ti):将事务Ti更新的所有数据项的值置为新值。故障发生后，恢复子系统检查日志，以确定哪个事务需要redo，哪个需要undo。

第28页，共54页，2023年，2月20日，星期三

事务Ti需要redo，当且仅当日志中有<Ti,start>和<Ti,commit>。事务Ti需要undo，当且仅当日志中有<Ti,start>而没有<Ti,commit>。

第29页，共54页，2023年，2月20日，星期三

<T0,strat><T0,A,1000，950><T0,B,2000，2050>此时发生崩溃，系统重新启动，发现有<T0,strat>而没有<T0,commit>,T0的操作必须取消。执行undo(T0)。

第30页，共54页，2023年，2月20日，星期三

<T0,strat><T0,A,1000，950><T0,B,2000，2050><T0,commit><T1,strat><T1,C,700，600>此时发生崩溃，系统重新启动，做undo(T1)和redo（T0)。

第31页，共54页，2023年，2月20日，星期三

<T0,strat><T0,A,1000，950><T0,B,2000，2050><T0,commit><T1,strat><T1,C,700，600><T1,commit>此时发生崩溃，系统重新启动，做redo（T0)和redo(T1)

第32页，共54页，2023年，2月20日，星期三3．检查点从前面的例子可以看出，如果日志很大，搜索过程耗时，而且有些可能是处理过的日志记录，虽然重新处理不会有不良后果，但是会使恢复过程加长。为降低恢复过程的开销，引入检查点。在日志文件中周期的加入检查点。第33页，共54页，2023年，2月20日，星期三7．5影子分页

第34页，共54页，2023年，2月20日，星期三1．影子分页方法

影子分页技术是影子拷贝技术的改进。某些情况下，影子分页技术比基于日志的方法需要更少的磁盘访问，但是影子分页技术有它的缺点。影子分页技术的主要思想是在一个事务的生存周期维护两张页表：当前页表和影子页表。事务开始时两张页表相同，影子页表在事务执行过程中不发生改变。当前页表在事务执行write操作时可能改变。所有input和output操作使用当前页表定位磁盘上的数据库页。第35页，共54页，2023年，2月20日，星期三

2．恢复方法将影子页表存入非易失存储器，保存了事务执行前的数据库状态。当系统崩溃或事务中止，可以恢复数据库到事务执行前状态。事务提交后，当前页写到非易失存储器，可以成为新的影子页，下一个事务开始执行。成功的恢复要求在系统崩溃后能在磁盘上找到影子页表。简单的方法是在稳定存储器上设置固定的区域记录影子页表的磁盘地址。当系统崩溃后重新启动时，拷贝影子页表至主存，并且用它进行后续事务处理。中止事务的恢复是自动的，不需要调用undo操作。第36页，共54页，2023年，2月20日，星期三

提交一个事务时，必须：1）保证主存中所有被该事务修改过的缓冲页都被写到磁盘上；2）将当前页表写到磁盘上，注意不能覆盖影子页表；3）将当前页表的磁盘地址写到记录影子页表的地址的稳定存储器的固定区域，覆盖旧的影子页表的地址。于是当前页表就成了影子页表。如果故障发生在第3）步之结束前，系统重启后，系统状态恢复到该事务执行前的时刻，故障发生在第3）步结束后，该事务的执行结果被保存。第37页，共54页，2023年，2月20日，星期三

与基于日志的恢复相比，消除了日志记录输出的开销，恢复速度明显加快。缺点有：提交开销。使用影子分页技术，事务提交时要输出多个块（实际数据块、当前页表和当前页表的磁盘地址）。基于日志的机制只要写日志记录。数据分片。在第二章中，为了加快数据传输速度，将相关的数据库页存储在临近的磁盘块。影子分页技术在数据更新时使得数据库页改变了存储位置。垃圾回收。当一个事务提交时，包含该事务所修改数据旧值的数据库页不能再被访问，变成垃圾页。它们的信息已经是无用的信息，但是又不是空闲空间。需要周期性的找出所有垃圾页将它们加入空闲页列表。第38页，共54页，2023年，2月20日，星期三7．6并发事务的恢复

第39页，共54页，2023年，2月20日，星期三到目前为止，我们只考虑了只有一个事务在执行情况的恢复，下面讨论如何修改和扩展基于日志的恢复机制以处理多个事物并发的情况。不论有几个并发事务，系统只有一个磁盘缓冲区和一个日志，缓冲块由所有事务共享。

第40页，共54页，2023年，2月20日，星期三1.与并发控制的关系恢复机制很大程度上依赖于所用的并发控制机制。为回滚一个失败事务，必须撤消该事务所做的更新。假设事务T0必须被回滚，并且被T0更新的数据项Q必须恢复成旧值。当使用基于日志的机制进行恢复时，利用日志记录中的撤消信息进行恢复。现在假设T1在T0回滚前对Q也做了一次更新。如果T0被回滚，T1所做的更新就会丢失因此，事务T更新了数据项Q，在T提交或回滚前不允许其他事务修改Q。使用严格两阶段封锁协议就可以保证这一点。

第41页，共54页，2023年，2月20日，星期三2.事务回滚利用日志记录回滚失败的事务Ti。日志的扫描由后至前进行。对日志中形如<Ti,Xj,V1,V2>的日志记录，数据项Xj的值被恢复成旧值V1。当发现日志记录<Ti,start>时，停止日志扫描。3.检查点在前面我们利用检查点减少系统从崩溃中恢复时必须扫描的日志记录数目。由于不考虑并发，恢复时只考虑如下事务：最近一次检查点后开始的那些事务。若有的话，最近一次检查点时活跃的那个事务。第42页，共54页，2023年，2月20日，星期三

如果允许并发执行，情况会更复杂一些，因为在最近一次检查点时可能有几个事务都是活跃的。在并发事务处理系统中，检查点日志记录的形式为<checkpointL>，其中L为检查点时活跃事务的列表。

4.重启动恢复当系统从崩溃中恢复时，它构造两张表：redo-list/undo-list。undo-list由需要撤消的事务构成，redo-list由需要重做的事务构成。这两张表在恢复时构造，由后至前扫描日志，直到发现第一个<checkpoint>记录：对于每个形如<Ti,commit>的记录，将Ti加入redo-list。对于每个形如<Ti,start>的记录，如果Ti不属于redo-list，则将Ti加入undo-list。第43页，共54页，2023年，2月20日，星期三

构造完redo-list/undo-list后,恢复过程继续做如下工作:1)从最后一个记录开始由后至前重新扫描日志,并且对undo-list中事务Ti的每一个日志记录执行undo操作,忽略redo-list中事务的日志记录。当找到undo-list中的所有事务Ti所对应的<Ti,start>记录都被找到时，扫描停止。2）找出日志中的最后一个<checkpointL>记录。注意如果步骤已经过了最近的检查点记录，这一步可能要由前至后扫描。3)从最近一个<checkpointL>记录开始由前至后扫描日志,并且对redo-list中事务Ti的每一个日志记录执行redo操作,忽略undo-list中事务的日志记录。第44页，共54页，2023年，2月20日，星期三7．7缓冲区管理

第45页，共54页，2023年，2月20日，星期三

本节考虑几个细节，它们对实现故障恢复机制非常重要，并且能保证数据一致性但是只增加少量与数据库交互的开销。第46页，共54页，2023年，2月20日，星期三日志记录缓冲前面的讨论，我们假定每个日志记录在创建时都被输出到了稳定存储器。该假定大大增加了系统的开销，原因是通常向稳定存储器输出是以块为单位的。一个日志记录比一个块小的多。解决办法是一次输出多个日志记录。将多个日志记录先集中在日志缓冲区，在输出到稳定存储器。这样，在日志记录输出到稳定存储器前，系统发生故障时，日志记录完全丢失。因此必须对恢复技术增加一些要求，以保证事务的原子性。第47页，共54页，2023年，2月20日，星期三1）在日志记录<Ti,commit>输出到稳