第七章 恢复系统.ppt

1、第七章 恢复系统,因为有故障，才需要恢复。计算机可能发生的故障：电源、软件、机房失火、人为破坏等。恢复机制是数据库系统必不可少的组成部分，一旦故障发生，数据库必须保持事务的原子性和持久性。,71 故障分类,72 存贮器结构,73 恢复与原子性,74 基于日志的恢复,75 影子分页,78 非易失性存储器数据的恢复,79 高级恢复技术,77 缓冲区管理,76 并发事务的恢复,71 故障分类,1 事务故障： a. 逻辑错误。事务由于某些内部条件而无法继续正常执行。如：非法输入、找不到数据、溢出等 b.系统错误。系统进入一种不良状态（如死锁），结果事务无法正常执行。 2 系统崩溃：硬件故障，或数据库软

2、件、操作系统漏洞，导致易失性存储器内容的丢失，并使得事务处理终止。而非易失存储器完好。 3 磁盘故障：在数据传送操作过程中由于磁头损坏或故障造成磁盘上数据的丢失。,恢复算法： 在正常事务处理时采取的措施，保证有 足够的信息可用于故障恢复。 故障发生后采取的措施，将数据库内容 恢复到某个保证数据一致性，事务原子 性及持久性的状态。,72 存贮器结构,1存贮器类型 易失存储器：主存、高速缓存 非易失存储器：磁盘、磁带 稳定性存储器：通过一些技术手段实现 2稳定存贮器的实现 RAID,3数据访问 给一些概念和记号,数据库常驻在磁盘上，以块为单位存贮。一块可以包含多个数据项。假设没有数据块是跨块的。

3、输入/出操作以块为单位，磁盘上的块为物理块，临时位于主存的块为缓冲块。内存中用以存放块的区域称为缓冲区。,磁盘和主存间的块移动由下面两个操作完成。,(1)input（B） 传送物理块B至主存。 (2)output（B） 传送缓冲块B至磁盘，并 替换磁盘上相应的物理块。,Ti的私有工作区，在事务初始化时创建，事务提交或中止时删除。Ti的工作区中保存的每一个数据项X记为Xi，Ti通过在其工作区和系统缓冲区之间传送数据与数据库交互，所用的两个操作：,(1)Read(x)将数据项X的值赋予局部变量xi。 a.若X所在的块Bx，不在内存，则发指 令input(Bx)。 b.将缓冲块Bx中X的值赋予xi

4、(2)Write(x)将局部变量xi的值赋予缓冲块 中的数据项X。 a.若X所在的块Bx不在内存，则发指令input(Bx)。 b.将xi的值赋予缓冲块Bx中的X,73 恢复与原子性,发生故障和简单的故障恢复过程，可能导致数据库的不一致。为了保持原子性的目标，需记录对数据修改的描述信息。 例：考虑事务Ti，将￥50从帐户A转到帐户B，A和B的初值分别为1000和2000，假设Ti执行过程中系统发生崩溃，且发生在output(BA)之后， output(BB) 之前，由于内存的内容丢失，无法知道事务的结局。可以调用恢复过程。,重新执行Ti,A的值变为900而不是950，系统产生不一致。 不重新执

5、行Ti,A的值变为950而B的值为2000 ，系统仍然不一致。,74 基于日志的恢复,日志：记录数据库中的所有更新活动。包括以下段 : *事务标识是执行Write操作的事务的唯一标识 *数据项标识是所写数据项的唯一标识，通常是数据项在磁盘上的位置。 *旧值是数据项的写前值。 *新值是数据项的写后值。 日志记录： ：事务Ti开始 ：事务Ti对Xj执行写操作，Xj的写前值是V1，写后值是V2。 ：事务Ti提交 ：事务Ti中止,事务执行写操作前，生成该次写操作的日志。 为了使用日志恢复数据库，日志必须放在稳定存储器上。,1延迟的数据库修改 延迟修改技术通过在日志中记录所有的数据库修改，将一个事务的所

6、有write操作拖延到事务部分提交时才执行，从而保证事务的原子性。 当事务部分提交时，日志上有关该事务的信息被用来执行延迟写。在事务完成其执行前系统崩溃，或事务中止，则忽略日志上的信息。 事务Ti的执行过程：Ti开始执行前，向日志中写入记录，Ti的一次write(X)操作，导致向日志中写入一条新记录。当Ti部分提交时，向日志中写入记录。,当Ti部分提交时，日志中相关的记录用来执行延迟写。执行更新时可能发生故障，更新前将日志记录写到稳定存储器上。然后进行更新，事务提交。,仍然用银行的例子说明： T0：read(A) T1: read(C) A:=A-50 C:=C-100 write(A) wr

7、ite(C) read(B) B:=B+50 write(B) 设执行顺序，执行前，A,B,C的值分别为1000，2000，700。,日志： ,利用日志，可以恢复易失性存储器上的信息丢失 恢复过程： redo(Ti):将事务Ti更新的所有数据项的值置为新值。 故障发生后，恢复子系统检查日志，以确定需要重新执行的事务。 事务Ti需要重新执行，当且仅当日志中有和。 如果系统在事务完成后崩溃，用日志信息可以将系统恢复到系统完成后的一致状态。, 此时发生崩溃，系统重新启动，不必做redo A,B的值仍为1000和2000。, 此时发生崩溃，系统重新启动，做redo（T0) A的值950, B的值205

8、0 ,C的值700, 此时发生崩溃，系统重新启动，做redo（T0)和redo（T1)。A的值950, B的值2050 ,C的值600,2立即的数据库修改 立即更新技术允许数据库修改在事务仍处于活跃状态时就进行数据库修改。活跃事务所做的数据库修改称为未提交修改。发生故障时，利用日志记录将数据库恢复成旧值。用undo操作完成。 事务Ti的执行过程：Ti开始执行前，向日志中写入记录，Ti的一次write(X)操作，导致向日志中写入一条新记录。当Ti部分提交时，向日志中写入记录。,还用银行的例子。日志： ,利用日志，可以恢复易失性存储器上的信息丢失 恢复过程： undo(Ti):将事务Ti更新的所有

9、数据项恢复为 旧值 。 redo(Ti):将事务Ti更新的所有数据项的值置为新值。 故障发生后，恢复子系统检查日志，以确定哪个事务需要redo，哪个需要undo。,事务Ti需要redo，当且仅当日志中有和。 事务Ti需要undo，当且仅当日志中有而没有。, 此时发生崩溃，系统重新启动，发现有而没有,T0的操作必须取消。执行undo(T0)。, 此时发生崩溃，系统重新启动，做undo(T1)和redo（T0)。, 此时发生崩溃，系统重新启动，做redo（T0) 和redo(T1),3检查点 从前面的例子可以看出，如果日志很大，搜索过程耗时，而且有些可能是处理过的日志记录，虽然重新处理不会有不良后

10、果，但是会使恢复过程加长。 为降低恢复过程的开销，引入检查点。 在日志文件中周期的加入检查点。,75 影子分页,1影子分页方法 影子分页技术是影子拷贝技术的改进。某些情况下，影子分页技术比基于日志的方法需要更少的磁盘访问，但是影子分页技术有它的缺点。 影子分页技术的主要思想是在一个事务的生存周期维护两张页表：当前页表和影子页表。事务开始时两张页表相同，影子页表在事务执行过程中不发生改变。当前页表在事务执行write操作时可能改变。所有input和output操作使用当前页表定位磁盘上的数据库页。,2恢复方法 将影子页表存入非易失存储器，保存了事务执行前的数据库状态 。当系统崩溃或事务中止，可以

11、恢复数据库到事务执行前状态。事务提交后，当前页写到非易失存储器，可以成为新的影子页，下一个事务开始执行。成功的恢复要求在系统崩溃后能在磁盘上找到影子页表。简单的方法是在稳定存储器上设置固定的区域记录影子页表的磁盘地址。当系统崩溃后重新启动时，拷贝影子页表至主存，并且用它进行后续事务处理。中止事务的恢复是自动的，不需要调用undo操作。,提交一个事务时，必须： 1）保证主存中所有被该事务修改过的缓冲页都被 写到磁盘上； 2）将当前页表写到磁盘上，注意不能覆盖影子页 表； 3）将当前页表的磁盘地址写到记录影子页表的地 址的稳定存储器的固定区域，覆盖旧的影子页 表的地址。于是当前页表就成了影子页表。

12、 如果故障发生在第3）步之结束前，系统重启后，系统状态恢复到该事务执行前的时刻，故障发生在第3）步结束后，该事务的执行结果被保存。,与基于日志的恢复相比，消除了日志记录输出 的开销，恢复速度明显加快。缺点有： 提交开销。使用影子分页技术，事务提交时要输出多个块（实际数据块、当前页表和当前页表的磁盘地址）。基于日志的机制只要写日志记录。 数据分片。在第二章中，为了加快数据传输速度，将相关的数据库页存储在临近的磁盘块。影子分页技术在数据更新时使得数据库页改变了存储位置。 垃圾回收。当一个事务提交时，包含该事务所修改数据旧值的数据库页不能再被访问，变成垃圾页。它们的信息已经是无用的信息，但是又不是空

13、闲空间。需要周期性的找出所有垃圾页将它们加入空闲页列表。,76 并发事务的恢复,到目前为止，我们只考虑了只有一个事务在执行情况的恢复，下面讨论如何修改和扩展基于日志的恢复机制以处理多个事物并发的情况。不论有几个并发事务，系统只有一个磁盘缓冲区和一个日志，缓冲块由所有事务共享。,1.与并发控制的关系 恢复机制很大程度上依赖于所用的并发控制机制。为回滚一个失败事务，必须撤消该事务所做的更新。假设事务T0必须被回滚，并且被T0更新的数据项Q必须恢复成旧值。当使用基于日志的机制进行恢复时，利用日志记录中的撤消信息进行恢复。现在假设T1在T0回滚前对Q也做了一次更新。如果T0被回滚，T1所做的更新就会丢

14、失 因此，事务T更新了数据项Q，在T提交或回滚前不允许其他事务修改Q。使用严格两阶段封锁协议就可以保证这一点。,2.事务回滚 利用日志记录回滚失败的事务Ti。日志的扫描由后至前进行。对日志中形如的日志记录，数据项Xj的值被恢复成旧值V1。当发现日志记录时，停止日志扫描。 3.检查点 在前面我们利用检查点减少系统从崩溃中恢复时必须扫描的日志记录数目。由于不考虑并发，恢复时只考虑如下事务： 最近一次检查点后开始的那些事务。 若有的话，最近一次检查点时活跃的那个事务。,如果允许并发执行，情况会更复杂一些，因为在最近一次检查点时可能有几个事务都是活跃的。在并发事务处理系统中，检查点日志记录的形式为，其

15、中L为检查点时活跃事务的列表。 4.重启动恢复 当系统从崩溃中恢复时，它构造两张表：redo-list/undo-list。 undo-list由需要撤消的事务构成， redo-list由需要重做的事务构成。这两张表在恢复时构造，由后至前扫描日志，直到发现第一个记录： 对于每个形如的记录，将Ti加入redo-list。 对于每个形如的记录，如果Ti不属于redo-list，则将Ti加入undo-list 。,构造完redo-list/undo-list后,恢复过程继续做如下工作: 1)从最后一个记录开始由后至前重新扫描日志,并且对undo-list 中事务Ti的每一个日志记录执行undo操作,

16、忽略redo-list中事 务的日志记录。当找到undo-list中的所有事务Ti所对应的 记录都被找到时，扫描停止。 2）找出日志中的最后一个记录。注意如果步骤 已经过了最近的检查点记录，这一步可能要 由前至后扫描。 3) 从最近一个记录开始由前至后扫描日志,并且 对redo-list中事务Ti的每一个日志记录执行redo操作,忽略 undo-list中事务的日志记录。,77 缓冲区管理,本节考虑几个细节，它们对实现故障恢复机制非常重要，并且能保证数据一致性但是只增加少量与数据库交互的开销。,日志记录缓冲,前面的讨论，我们假定每个日志记录在创建时都被输出到了稳定存储器。该假定大大增加了系统的

17、开销，原因是通常向稳定存储器输出是以块为单位的。一个日志记录比一个块小的多。 解决办法是一次输出多个日志记录。将多个日志记录先集中在日志缓冲区，在输出到稳定存储器。 这样，在日志记录输出到稳定存储器前，系统发生故障时，日志记录完全丢失。因此必须对恢复技术增加一些要求，以保证事务的原子性。,1）在日志记录输出到稳定存储器后，事务Ti进入提交状态。 2）在日志记录输出到稳定存储器前，与事务Ti有关的所有日志记录必须已经输出到稳定存储器。 3）主存中的数据块输出到数据库（非易失存储器）前，所有与数据块中数据有关的日志记录必须已经输出到稳定存储器。 后面两个规则成为先写日志（WAL)规则。,数据库缓冲,数据库存储在非易失性存储器（磁盘）上，需要时将数据块调入主存。在调入新块时B2，按照缓冲区管理的策略，将一块B1输出。如果B1已经修改过，那么B1必须在输入B2前就输出。输出日志记录的规则限制了数据块的自由输出。如果B2的输入使得必须输出B1,那么与B1中数据有关的日志记录必须在B1之前输出到稳定存储器上。因此： *输出日志记录至稳定存储器； *将块B1输出到磁