基于日志的数据库恢复
数据库系统中的非灾难性故障所导致的数据不一致问题,常用的解决方法是基于日志的恢复技术。
查阅资料，研究探讨此类恢复技术的基本方法及其实现算法。
事务日志及在数据库恢复中的作用
一、事务日志的工作原理
实际上，事务中的数据操作首先在数据库缓冲区中进行，缓冲区中有用来记录操作活动的数据页和日志页。
当事务运行到Commit Transaction时，日志页从缓冲区写入磁盘，而后数据页再从缓冲区写入磁盘，即遵循“先写日志”的原则。
如果先写了日志而没有来得及修改实际数据，则在下一次的正常启动或恢复过程中，DBMS检查日志里的记录，将数据的更新补录到数据库中。
因此遵循“先写日志”的原则，可以严格地保持事务日志和实际数据更新的一致性。
事务的所有日志记录都链接在一起，当系统出现故障时，通过恢复（前滚）或撤消（回滚）事务能够最大限度地恢复数据库。
二、基于事务日志的数据库恢复思路
假如某数据库系统在T1时刻做了一次完整的备份，由于某种原因在T2时刻(T2>T1)出现了故障，丢失了重要的数据。
一般的数据恢复思路是利用T1时刻的数据备份将数据库恢复到T1时刻的状态，T1至T2时间段更新的数据则丢失，即做到不完全恢复。
实际上如果充分利用T1至T2 时间段的事务日志，我们完全可以将数据库恢复到T2时刻的状态，即完全的数据库恢复。
因为T1至T2时间段的事务日志是按照时间顺序详细记录了这一时间段的事务处理信息，如图所示。
如果我们在T1状态的基础上，重新依次运行这些事务，就可以将数据库由T1状态逐步推演到T2时刻的状态，实现数据库的完整恢复。
此外，还可以根据需要在T1与T2之间某个时间点停留，即把数据库恢复到过去某个特定的时间点。
基于事务日志的数据库恢复技术
一、利用事务日志进行数据库恢复的操作步骤
当数据库出现故障时，恢复到当前故障点应按下面的次序进行操作：
①备份当前活动事务日志；
②还原星期一晚上22:00 创建的数据库完全备份；
③依次还原自星期一晚上22:00 后创建的差异数据库备份，直至星期二9:00 的差异备份为止；
④依次应用星期二9:10 、9:20 创建的事务日志备份
⑤应用步骤①创建的当前活动事务日志作最后还原。
ARIES 数据库恢复算法的分析
一、ARIES 简介
ARIES(Algorithm for Recovery and Isolation Exploiting Semantics) ，该算法出现于IBM 的Almaden 研究中心在1992年完成的一项名为Starburst 的大型数据库原型系统研究项目中，该算法基于后备复本和日志。
它试图以概念上相对简单且系统化的方式，提供一套能确保事务原子性和持久性的、具有良好性能的的恢复管理算法。
它能与绝大多数并发控制机制很好的协调工作。
ARIES 数据结构由日志记录、页结构、事务表与脏页表四部分组成。
二、ARIES恢复管理算法综述
当系统崩溃后重启时，恢复管理器将被激活，并按以下三个阶段进行处理：–分析（Analysis）：鉴别崩溃发生时，缓冲区中的脏页和当时仍活跃的事务。
–重做（Redo）：重做从日志的适当起点（比如，被修改的最早脏页对应日志记录）开始的所有动作，恢复系统到崩溃时的DB状态。
–撤消（Undo）：撤消上次崩溃时所有未提交事务的动作效果，使DB只反映已提交事务的影响。
三、一个简单的ARIES日志片段示例
分析阶段将能分析识别出：
–崩溃时仍活跃事务:T1,T3；
–已提交事务T2
–崩溃时的脏页P1、P3和P5。
在重做阶段，提交事务T2的所有动作，必须按日志顺序重新应用一次。
最后，在撤销阶段，T1和T3的所有动作，必须按日志记录的相反顺序，依次逐个
撤销。
四、AREIS数据结构
ARIES数据结构由日志记录、页结构、事务表与脏页表四部分组成。
1、日志记录
日志既可为己提交事务的重做(redo)和未提交事务的撤消(undo)提供信息源，
也为介质恢复提供途径。
ARIES要对任何事务的可能引起可恢复数据对象发生改变
的操作作日志，并采用先记后写的WAL协议，日志记录之数据结构包括以下数据
域：
(1)日志顺序码（log sequence number）：以下简称LSN
(2)日志类型( Type)：通常有四种，即常规更新记录(Update)、补偿日志记录
(compensation log record 简称CLR)、与提交协议有关的记录（如二步提交协议中的准备提交）或非事务相关记录（如OS文件的返回）。
(3)事务标识符(Transaction ID):标识引发所记录操作的事务。
(4)前日志顺序码(Previous LSN):表示由同一事务写入的前一个日志记录的日
志顺序码。
(5)页标识符(Page ID)：用于标识“更新”与“补偿”记录中的更新所作用的
页。
通常由对象标识符与页在对象中的页序号两部分组成。
(6)撤消下一个日志顺序码(UndoNext LSN)：仅在补偿日志记录中使用，其给
出事务卷回过程中该事务要处理的下一个日志记录的LSN.
(7)数据(Data):用以记录所实施的更新的redo/undo数据。
2、页结构
页数据结构指在数据库的每一页辟出一块小空间作为页日志顺序码(Page-LSN)域，用以描述在该页上所作的最近的更新或补偿操作所对应的日志记录的LSN.页结
构由单一的数据域页日志顺序码组成。
3、事务表
设立该表主要用于在系统失效后的重启动恢复时跟踪记录活动事务的状态，从而为该过程要进行的撤消提供依据。
事务表的数据结构包括四个域。
其中事务标识
符和撤消下一日志顺序码同前述含义，另两个域为：
(1)状态(state):用于表示活动事务的可能状态，由于ARIES对事务的提交采用一
种类二阶段提交的协议，所以活动事务有两种可能的状态，其一为准备提交而未提
交状态，称为准备态(prepared)；另一种为未准备提交(unprepared)状态。
(2)最后的日志顺序码(Last LSN):表示该事务所写的最后一个日志记录的日志顺
序码。
4、脏页表
脏页表中的每一数据项包含页标识符(Page ID)和恢复日志顺序码(Recovery LSN)两个数据域。
前者用于标识相应的脏页，后者用于指明有关该页的可能未存到稳定
存储器中的更新在日志中的开始位置。
脏页表有两种用途。
一为在系统正常运行过
程中用作缓冲区(buffer pool)脏页表，且系统在作检查点(checkpoint 或CHKPT)时，
将该表包含在其记录中。
另一用途是作为重启动(restart)脏页表以记录系统失效时
可能的脏页。
恢复前的准备工作
为满足可能的恢复之需，数据库系统在正常运行过程中，ARIES除要求系统作后备复本和为更新操作作日志外，还要设立保存点和检查点。
一、保存点
保存点( SavePoint)可在事务正常运行过程的任一点设立，每当设立保存点时，相应事务最近的日志记录的LSN被作为保存日志顺序码(Save KN)存入虚拟内存中。
以后在事务运行过程中，系统或事务均可要求将事务卷回(rollback)到任一个有效(outstanding)保存点，只要提供相应的Save KN信息。
二、检查点
由于遵循WAL规则，即使事务提交，也可能未写入稳定数据库，为减少系统在重启动恢复时的工作量，一般的DBMS在系统正常运行过程中在日志中设置检查点(checkpoint)。
检查点可以是提交一致(commit-consistent)、缓冲一致(cache-consistent)或模糊(fuzzy)形式。
ARIES 采用的模糊形式不要求作检查点时所有缓冲脏页被强制写入外存，而是借助于缓冲管理上的窃取策略，即充分利用Buffer Manager 或DB Writer 等一些系统进程在后台持续地将脏页刷出，所以检查点可在事务运行过程中异步地设立，提高了系统在作检查点时的运行效率，显得更加合理与灵活。
ARIES的检查点以写开始检查点（begin-CHKPT)日志记录为开始，然后作一个结束检查点（end-CHKPT)日志记录，在该记录中包括正常运行过程中的事务表、缓冲区脏页表以及文件映射信息（如表空间、索引空间、事务拥有的锁信息等），待所有相关的检查点信息刷入外存时，再在外存中一特定的被称为主记录(master-record)的位置存入该检查点的begin-CHKPT 的日志记录顺序码，作为重启动恢复程序的入口。
算法描述
一、分析阶段
分析阶段至少需要完成以下三个基本任务：
–确定重做阶段的日志扫描起点。
–确定崩溃时，缓冲区中的脏页。
–识别崩溃时，仍活跃的、必须撤消的事务。
分析阶段扫描处理算法
二、REDO阶段
主要任务：重复历史(重构崩溃时的状态) 具体算法描述
三、UNDO阶段处理描述。