《嵌入式移动实时数据库系统的恢复策略研究.doc》由会员分享，可在线阅读，更多相关《嵌入式移动实时数据库系统的恢复策略研究.doc（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、摘 要随着计算机嵌入式技术的快速发展和移动技术的不断进化和完善，嵌入式移动设备的性能得到很大的提高，同时各种应用对实时性的要求也越来越高。由移动计算、实时应用结合传统数据库技术而形成的嵌入式移动实时数据库系统已成为数据库领域的热点课题，数据库系统的恢复是其中的关键技术，恢复系统要充分考虑资源、时效、应用环境的限制，满足恢复的实时性和移动性。嵌入式移动实时数据库系统的恢复系统除了要满足传统恢复系统的基本特性外，还要着重考虑移动主机端的日志存放、基站端的日志存放、过区切换策略、检查点策略等问题。使用短暂日志和动态检查点频率的两级日志恢复算法AR-2LL-ELDCF (Algorithms for
2、Recovery based on 2-Level Log Using Ephemeral Log & Dynamic Checkpoint Frequency)是一种有效的恢复策略。AR-2LL-ELDCF算法使用短暂日志的思想，在移动主机端只保存一般恢复时需要的undo日志，称为有效短暂日志，同时将过期短暂日志发送到基站保存以满足之后的审计需要；如果有效短暂日志在移动主机端保存不下，则发送到基站进行保存，需要恢复时就从基站读取有效短暂日志数据。AR-2LL-ELDCF算法使用动态检查点频率，使有效短暂日志的大小合适，尽可能在移动主机端可以全部保存，以便系统崩溃后可以迅速恢复。该算法的过区切
3、换策略与有效短暂日志传输到基站的策略紧密结合，可以在需要基站保存有效短暂日志的情况下缩短恢复时间。 关键词：移动实时恢复，短暂日志，两级日志，过区切换AbstractWith the rapid development of embedded technique and mobile technique, the performance of embedded mobile devices has been greatly enhanced. Various applications have more and more requirements on real-timing. Embedde
4、d Mobile Real-time Database System which integrates the mobile computation, real-time application and traditional database technology become a focus in the research of database, in which recovery technique is the key technique. The recovery system in this system should consider about the limitation
5、of resource, time and efficiency, so that the recovery could fit the demand of real-time and mobile characteristic. Besides maintaining the characteristics of traditional recovery, the mobile real-time recovery should focus on how to store the log file in mobile hosts and base stations, strategy of
6、handoff, and strategy of checkpointing. Algorithms for Recovery based on 2-Level Log Using Ephemeral Log & Dynamic Checkpoint Frequency (AR-2LL-ELDCF) is an effectual strategy of recovery in embedded mobile real-time database. AR-2LL-ELDCF uses ephemeral log and only store in-use ephemeral log, whic
7、h is useful at ordinary recovery, in mobile hosts. The overdue ephemeral log is transferred to base stations to store for the needs of audit. If the in-use ephemeral log is too large to store in the mobile host, it is sent to the base station. In this case it is needed to download the in-use ephemer
8、al log to mobile host before recovery. AR-2LL-ELDCF uses dynamic checkpointing frequency to control the size of in-use ephemeral log, so that it can be completely stored in the mobile host as far as possible. The strategy of handoff is closely cooperating with the stategy of in-use ephemeral log tra
9、nsfer, which can reduce the recovery time.Keywords: Mobile real-time recovery, Ephemeral log, 2-Level log, Handoff目 录摘 要IABSTRACTII1 绪论1.1 课题背景(1)1.2 嵌入式移动实时数据库系统的特点(2)1.3 恢复(6)1.4 本文组织(10)2 恢复的基本理论和方法2.1日志(11)2.2检查点技术(12)2.3传统恢复策略的分类(14)2.4 经典的恢复算法ARIES(17)2.5移动实时数据库系统恢复的相关理论(17)2.6 本章小结(17)3 一种嵌入式
10、移动实时数据库系统的恢复策略3.1嵌入式移动实时数据库系统恢复模型(18)3.2基于两级日志的嵌入式移动实时恢复算法(24)3.3本章小结(39)4 系统实现与性能评价4.1原型系统设计与实现(40)4.2 算法性能评价(54)4.3 本章小结(58)5 总结与展望5.1 工作总结(59)5.2 将来展望(59)致 谢(61)参考文献(62)附录 攻读学位期间参与的科研项目(66)1 绪论1.1 课题背景随着社会生活各个方面的信息化程度越来越高，数据库管理系统（Database Management System，DBMS）得到了越来越广泛的应用，成为计算机应用系统中不可缺少的组成部分。同时，
11、许多应用场合对数据查询处理的需求也越来越高：要求随时随地查询所需的数据，并且需要在限定时间内得到回应，这就需要有一种能满足这些需求的嵌入式移动实时数据库系统（Embedded Mobile Real-Time Database System，EMRTDBS）。与传统数据库系统相比，由于嵌入式移动实时环境的特性，它可以支持更多新的应用：公共信息发布，用户通过无线便携设备了解新闻、股票、天气等信息资源，并及时做出决策；军事作战，每个士兵都作为独立的系统单元，实时处理战场信息并与服务器进行交互，服务器综合各单元的移动信息指挥整个战场行动；移动电子商务，随着用户所处地点的变迁，数据库查询将总是显示最新
12、有效的商务信息，满足商务用户对位置相关和异地操作的特殊要求。本课题组的目标便是开发出一个嵌入式移动实时环境下的数据库管理系统，支持移动终端的嵌入式数据库和中心服务器数据库的运行和管理。和普通的数据库系统一样，嵌入式移动实时数据库系统可能会由于一些不可预知的软硬件故障而影响事务的正确运行，造成数据库中的数据丢失甚至破坏数据库，给数据库的一致性和可靠性维护带来挑战。而恢复系统的作用正是在出现故障后将数据库中数据从不一致的状态恢复到某种逻辑一致的状态。各种现有数据库系统运行情况表明：数据库系统采用的恢复技术是否行之有效,不仅对系统的可靠程度起着决定性作用，而且对系统的运行效率也有很大影响，是衡量系统
13、性能优劣的重要指标。由于移动环境的移动性和易错性1等特点，嵌入式移动实时数据库系统可能要面对更多的故障，需要更频繁地进行恢复。同时，嵌入式移动实时数据库系统要满足各种应用的实时性要求，遇到故障后的快速恢复是系统达到实时性要求的重要保证。嵌入式移动实时数据库是传统数据库发展的新阶段，可以满足许多应用场景的需要，特别是对武器制导这种对实时性、移动性和嵌入性要求很高的应用更为重要，而恢复系统作为保障整个数据库系统在故障情况下迅速恢复正常运行的子系统，其重要性不言而喻，有着非常重大的理论和实际意义。1.2 嵌入式移动实时数据库系统的特点1.2.1 嵌入式系统嵌入式系统是以计算机技术为基础，根据应用的具
14、体需求来量身定制的专用计算机系统，它的软硬件可裁剪，同时对功能、可靠性、成本、体积、能耗等有严格的要求。恢复子系统的设计要充分考虑这些硬件的性能问题，如电源有限和内存有限的问题。嵌入式系统一般使用电池供电，要尽量节能才能延长使用时间；同时内存相比一般PC机也是很小的，要使用尽可能小的内存完成需要的功能。在系统设计时要做相应的优化和设计，以充分利用系统资源，提高应用效率。1.2.2 移动数据库系统移动数据库系统模型如图1.1所示。由于移动环境的移动性、连接的频繁断接性、网络条件的多样性、网络通信的非对称性、系统的高伸缩性和低可靠性以及资源有限性等特点，使得移动事务相比传统的分布式事务具有移动性、
15、长事务、易错性和异构性等特点1。传统的ACID特性已经不能很好的表征移动事务的一致性，要为恢复系统的一致性准则找出新的标准，同时要解决过区切换对恢复系统的影响。图1.1 移动数据库系统模型1.2.3 实时数据库系统实时事务不同于传统事务，它不是以ACID特性作为正确性标准的。实时数据库的数据和事务都可以具有定时特性或显式的定时限制，系统的正确性不仅依赖于逻辑结果，还依赖于逻辑结果产生的时间2。有时候为了要满足实时性的需要，可能要以牺牲一部分的一致性作为代价。实时数据库与传统数据库最大的区别在于其一部分数据和事务是“实时”的，即有时间限制的。1实时数据数据的“实时”性表现为有效期，超过有效期的数
16、据是无效的，需要重新读入进行刷新。这部分数据的正确性不仅取决于数据库内的完整性和逻辑一致性，还取决于其有效期是否满足。要保持数据库中的实时数据尽量处在有效状态，在此提出时态一致性的概念。对实时数据库中的一个数据对象d，其被观测或采样的时刻记为ot(d)，其绝对有效时间的结束又称外部有效期记为evi(d)，对象在数据库中记录的当前值记为v(d)，则实时数据对象可以用一个三元组表示为d: 3。定义1.1 实时数据d具有绝对时态一致性，当且仅当d的当前值满足数据库内部的完整性和一致性逻辑要求且ct(d)ot(d)evi(d)，其中ct(d)为当前检测时间。定义1.2 用来作决策或导出一个新数据的一组
17、数据称为一个相互（相对）一致集，每个数据集都与一相对有效期（Relative Validity Interval）相联，记为Rrvi 。定义1.3 当且仅当d1,d2R有| ot(d1)ot(d2) |Rrvi ，R是一个相互一致集。2实时事务事务的“实时”性表现为截止期，超过截止期的事务会影响整个数据库的一致性。依照实时事务的特征，一般按如下几种方法将实时事务分类。（1）按关键性分类根据实时事务的时限的性质，即事务超过截止期后对系统带来的影响分类，可将实时事务分为硬实时事务、软实时事务和固实时事务三类4：硬实时事务超截止期会导致恶果（价值函数取大且可能不断增加的负值）。它对应于安全危急性活动
18、。软实时事务超截止期仍有一定的价值，且价值不断下降，直到某一时刻（称为最终有效时间）降到零，此后保持为零（不会为负）。固实时事务一旦到达截止时间，其价值立即降为零，此后固定为零（也不会为负）。显然，它是软实时事务在最终有效时间与截止时间重合情况的特例。图1.2所示为这三种实时事务的价值函数，其中横轴t表示时间，纵轴v表示这个事务的价值，s为事务的开始时间，d是截止期，e表示事务价值降为0的时间。图1.2 三类实时事务的价值函数（2）按功能分类一个实时数据库系统以两种方式直接与现实世界交互作用，一是关于现实世界状态或事件的信息被记录到数据库中，二是事务可以启动各种影响现实世界的活动。这就导致如下
19、事务分类方法：数据接收事务记录现实世界的状态或发生的事件到数据库中。它是简单的只写事务；为了保持数据库的“外部一致”和跟踪记录，它应是短的、周期的，且应是被立即执行（不能等待和阻塞）的硬实时事务。为了保证其定时限制的满足，它可能会引起对数据库一致性的破坏。数据处理事务类似传统数据库的事务。它对数据库中的数据进行读写，通过对已有数据的运算得到新的数据。控制事务引起现实世界中有关活动的执行。像数据接收事务一样，这种事务是很短的，尽管所引起的现实活动可能要执行很长时间。它通常也是硬实时的。这种事务还可以作为数据处理事务的子事务而被调用，而它本身也可以触发子事务，比如以一子事务来检测所引起的现实活动。
20、随着嵌入式移动实时数据库应用市场需求的与日俱增，越来越多的商家都投入到这个大的开放性的市场中，也出现了一系列各具特色的商业产品。在国外，有Sybase提供业界领先解决方案的SQL Anywhere，Oracle针对移动计算推出的Oracle Lite，IBM的DB2 satellite及DB2 Everyplace，以及微软的MSDE引擎等等；在国内，也逐步由理论研究转向实际产品开发，较有代表性的有东北大学的OpenBASE Mini，人大金仓研发的“小金灵”系统等。现在嵌入式移动实时数据库已经形成了较为成熟的产业，成为嵌入式系统不可缺少的部分，但是相对国外数据库的发展模式而言，国内起步较晚、
21、应用面较小、应用领域也不够广，同时存在着理论研究、原型设计与产品商业化分离的不足。不过随着计算终端的小型化，应用领域的不断扩展，可以预见，不久的将来其应用将进入到移动互联网、移动电子商务政务、移动物流、移动金融系统、移动新闻等多个商业与经济领域。1.3 恢复恢复子系统是数据库系统不可缺少的组成部分，传统数据库系统恢复策略的研究已经非常深入，分别对应于嵌入式、移动、实时环境的恢复也已研究颇多。 Davis于1973年在文献5和6中提出了控制区域（Soc）的思想，随后演变成了事务的概念。Chandy等人在文献7中描述了数据库系统的回滚和恢复的分析模型。Verhofstad在文献8中针对不同的故障形
22、式提出了七种恢复技术,包括：救助程序、增量备份、审计跟踪、微分文档、备份当前版本、多重拷贝、仔细替换。Haerder和Reuter在文献9中对恢复原理进行了全面的阐述。1.3.1 传统数据库系统的恢复传统数据库系统的恢复技术本身涉及到多个方面，如日志记录、备份与恢复的机制与策略、检查点技术等。但是传统恢复策略没有考虑实时、移动及嵌入式特性对于恢复策略的影响，传统的分布式事务恢复策略也不能直接应用于移动恢复中来。1.3.2 实时数据库系统的恢复实时恢复以传统的恢复技术为基础，同时要充分考虑数据及事务的实时性对于恢复策略的影响。所谓“实时”，就是能在规定时间内完成规定的操作，实时恢复必须足够迅速，
23、在系统崩溃或事务失败后在尽可能短的时间内将系统恢复到上一个一致状态，使系统能够尽可能快地重新投入使用。同时，恢复策略带来的运行时开销要足够小，不能影响系统正常运行时的实时性。实时恢复也要对数据进行区别对待，比如重要数据和硬实时事务要使用的数据要首先恢复，保证系统的硬实时事务截止期能够满足，而其他一些数据可以在稍后再进行恢复。有时候为了保证系统的实时性，可以牺牲一些一致性。有些数据会周期性的从外界读入进行更新，这些数据在恢复时可以不用考虑，在下次更新中会成为有效数据。对实时数据库系统的恢复策略的研究虽然没有传统数据库系统的恢复研究成果多，但是也已经比较深入。Huang的博士论文10是最早研究实时
24、数据库恢复策略的论文之一，文献11是他博士论文中实时恢复策略思想的精简。他提出实时内存数据库的四种恢复技术，这些技术同时适用于时态和非时态数据，同时考虑了时态数据的有效性。这四个日志技术的区别在于一般操作过程中的无效数据是否计入日志，以及时态、非时态数据的日志是否保存在同一个日志缓冲中。他还提出了更新频率有效间隔（update-frequency-valid-interval）检查点策略。在这个策略中，非时态数据基于更新频率分区，而时态数据基于它们的有效期分区。含有最经常更新页面的非时态数据的分区（称为热分区）将比其他分区有更多的检查点。时态数据，尤其是那些有效期很短的，将尽可能频繁地刷新到磁
25、盘中。这样，恢复过程只需处理相对较少的日志信息即可。因此，这个设计的目的在于用运行时的检查点开销来换取较少的恢复时间。同时，希望时态数据的频繁刷新可以保证临时数据在失效之前被使用。为了减少检查点带来的负载，对于有效期小于某个预先定义的阈值的时态数据不记录其日志，也不设置检查点。Gruenwald和Cheng在文献12中提出基于日志类型的实时内存数据库日志技术。事务类型日志（TTL）通过增加一定的日志空间，减少了redo的代价，也减少了事务处理过程中内存访问的次数。当数据库中时态数据的比例超过50%后，TTL的性能超过了Huang提出的使用多缓冲的时态-非时态日志技术。Sivasankaran在
26、文献13中讨论了实时主动数据库中的数据的特征及数据存放、日志和恢复如何满足性能要求，同时也讨论了实时主动数据库中影响数据存放、日志和恢复的事务特征。他强调需要设计一个新的日志恢复算法来解决优先级反转问题（优先级反转，即高优先级的请求要为低优先级的请求做一些工作，如一个事务提交后要刷新自己的以及比自己优先级低的事务的日志）的迫切性14，而传统数据库日志和恢复算法不适用了面向优先级的实时数据库。他提出了数据特征的分类方法以及从数据类型和事务类型衍生出的两个数据类，同时提出一套适用于RTDB的算法。文献15提出了一种识时的（Time-Cognizant）日志恢复策略，使用条件日志（Condition
27、al Logging）的思想，将数据分为重要时态数据（Critical Variant Data）、重要非时态数据（Critical Invariant Data）和非重要数据（Non-Critical Data）分别进行日志记录。这里的非重要数据都是非时态数据，对于非重要时态数据不进行日志记录，因为这类数据恢复后一般也超过了有效期，不如重新从环境中读取。重要时态数据的日志分多个文件记录，每个文件中日志产生的时间是连续的，不同日志文件的时间是不交叉的，恢复的时候，同一个文件中的日志被看作一个整体，要么全部有效，要么全部无效，这样缩短了判断日志数据时候有效的时间。同时，将重要数据的日志记录在非挥
28、发性RAM（Non-Volatile Random Access Memory, NVRAM）中，而将非重要数据记录在磁盘（Disk）中，这样当故障发生时，可以在预定的时间限制内恢复重要数据，使系统恢复正常运转，然后再在后台恢复非重要数据，缩短了恢复需要的时间，提高实时性。并且在系统正常运转过程中不做过多的检查点，将日志对系统性能的影响降至最低。与文献10的方法相比，该方法在平时正常运行时的额外开销较小，恢复时间稍微长一点，但是在时态数据有效期较短的情况下，恢复时间的差距并不是很大。文献16将实时日志分为实时事务日志、实时数据日志和活动日志三类，并考虑嵌入式环境的特点，给出记录日志的如下规则：
29、短时限时序数据对象不记录更新日志；数据的更新程度小于某个阈值则不记录更新日志。这样可以大大减少记录时序数据更新日志的存储开销，加快恢复速度。同时，对于不同类型的数据采用不同的数据库修改技术：时序数据对象采用立即更新技术，使时序数据的最近状态能及时反应到数据库中去；非时序数据则采用延迟更新方式。提出8条识时恢复正确性准则，将事务分为数据接收事务、数据处理事务和控制事务三种，基于识时恢复正确性准则给出这三种事务的恢复算法。1.3.3 移动数据库系统的恢复移动事务由于其自身的特点，如移动性、连接的频繁断接性、网络条件的多样性、网络通信的非对称性、系统的高伸缩性和低可靠性以及资源有限性等，使得在恢复时
30、要特别考虑移动性对恢复系统的影响。要保证在移动环境中可以正确、迅速地恢复数据库到一致状态，要充分考虑移动事务相对于传统事务的各种特征，要着重考虑过区切换时日志的存放和传输策略以达到快速恢复的要求。在移动数据库系统的恢复研究方面，文献17中提到了备份处理镜像的同步方法和异步方法，以及过区切换时日志传输的懒惰模式和悲观模式。备份处理镜像的同步方法是在每一个写事件（改变数据库状态的事件，可以是用户输入或基站传入的信息）之后都备份“增量”的处理镜像，而异步模式则是在一定数目的写事件或一定的时间间隔后才备份处理镜像，这相当于传统数据库的检查点方法。对于过区切换时的日志传输策略，在懒惰模式中，日志存放在B
31、S（Base Station）中，MU（Mobile Unit）移动到一个新BS中时要在这个新BS中存放旧BS的指针，这个指针用来在发生故障时使用分布在多个BS中的日志进行恢复。这个模式的优点是切换时的网络开销相对较小，因为不需要传送日志信息，但是不幸的是这个模式需要的恢复时间很长。在悲观模式中，整个日志和检查点在切换时都传送到新BS中，因此恢复时间很短但是切换时需要大量的数据传输。文献18中给出两个模式，这两个模式基于MU的移动，使用独立的检查点和悲观日志。这两个模式中，日志分布的BS列表在切换时进行传送。在基于距离的模式中，在MU移动的距离达到某个预先定义的值后进行日志规整。在基于频率的模
32、式中，当MU的切换次数达到某个预先定义的值后进行日志规整。规整日志之后，距离和切换次数都清零。这两个模式是懒惰模式和悲观模式的折中。文献19把整个移动主机的有效活动范围分为多个region，每个region有多个BS范围，在一个region中有一个指定BS来负责收集移动主机的日志，而当MH（Mobile Host）移动到不是指定BS的其他BS1时，这个BS1也存放一些日志，当MH离开BS1移动到BS2，BS1仍然存放MH的日志，以免MH又移动回来；当MH从BS2移动到BS3时，BS1就认为MH不太可能马上回来了，就把自己存放的MH的日志信息发送给指定BS，并从本地删除这些日志信息。这样MH恢复
33、的时候不用从很多的BS收集日志信息。如果MH从region1移动到region2，则前一个指定BS把日志全部传送到新的指定BS。同时该文章还讨论了在过区切换时发生故障的情况及对策。1.3.4移动实时数据库系统的恢复关于移动实时数据库系统的恢复策略几乎没有专门的文章研究，只是在某些研究移动恢复策略的论文中提到了如何满足实时要求，但是没有深入讨论。在文献17中，作者提出备份处理镜像时使用同步方法适用于有硬实时要求的场合，同时，过区切换传输日志时使用悲观策略也可以在一定程度上满足实时环境下快速恢复的需要。文献19提出的方法将所有日志集中在一个地方，以便于支持硬实时需求下的快速恢复。但是它们都不是专门
34、为实时环境研究的，只是稍微考虑了一下实时性的需求。1.4 本文组织本论文的组织结构安排如下：第一章介绍嵌入式移动实时数据库系统的基本理论和应用背景，简单概括该环境下数据及事务的新特点，以及恢复所要面临的问题，着重讨论了实时环境下和移动环境下的恢复策略研究现状；第二章介绍了恢复系统的基本理论和方法，讨论了实时环境下和移动环境下的恢复系统应考虑的问题；第三章根据课题的具体要求提出一种两级日志恢复模型，针对此模型分析了已有的恢复算法的不合适之处，提出改进思想，设计出一种使用短暂日志和动态检查点频率的两级日志恢复算法；第四章应用第三章中的算法开发出一个恢复原型系统，并选定模拟嵌入式移动实时环境的参数，
35、在该原型系统上对算法进行性能评价实验；第五章对全文工作进行总结，并指出以后研究工作的方向。2 恢复的基本理论和方法虽然目前计算机硬软件技术已经发展到相当高的水平，但硬件的故障、系统软件和应用软件的错误、操作员的失误以及恶意的破坏仍然是不可避免的。为了保证各种故障发生后，数据库中的数据都能从错误状态恢复到某种逻辑一致的状态，数据库管理系统中恢复子系统是必不可少的。各种现有数据库系统运行情况表明：数据库系统所采用恢复技术是否行之有效，不仅对系统的可靠程度起着决定性作用，而且对系统的运行效率也有很大影响，是衡量系统性能优劣的重要指标。传统DBMS的恢复技术本身涉及到多个方面，如日志记录、备份与恢复的
36、机制与策略、检查点技术等。对传统数据库系统的恢复策略的研究已经非常深入，分别对应于嵌入式、移动、实时环境的恢复研究也已取得较丰富的理论与实际成果。2.1日志2.1.1 日志的作用日志是事务操作的一个序列，每个日志记录记载有关某个事务已做的事的某些情况。几个事务的执行可以是交错的。如果系统崩溃，日志将被查阅，以重建崩溃发生时正在执行的事务。日志在数据库系统的恢复中起着非常重要的作用，可以用来进行事务故障恢复和系统故障恢复，并协助后援副本进行介质故障恢复。要使日志在恢复中正确达到将数据库系统恢复到某个一致状态的目的，登记日志文件时必须遵守日志先写协议(WAL)。2.1.2 日志先写协议（WAL）为
37、保证数据库是可恢复的，登记日志文件时必须遵循两条原则20：1.登记的次序必须严格按并发事务执行的时间次序；2.必须先将日志缓存中的日志信息写入日志文件，后将数据缓存中的数据写到数据库的数据文件。数据缓冲管理器将脏数据页写到磁盘和日志管理器将对应这个修改的日志记录写到日志文件是两个不同的操作。系统有可能在这两个操作之间发生故障，即这两个写操作只完成了一个。如果系统先写了数据库修改，而在日志记录中没有登记这个修改，则以后就无法恢复这个修改了。如果先写日志，但没有修改数据库，按日志文件恢复时最多执行一次不必要的撤销操作，并不会影响数据库的正确性。所以为了安全，一定要先写日志文件，即首先把日志记录写到
38、日志文件中，然后写数据库的修改。这就是“先写日志文件”的原则。2.1.3 日志技术日志记录方式根据收集日志信息的表示级别，可分为物理日志和逻辑日志21。根据修改前或后数据库状态和被记录状态的转换，可分为状态日志和转换日志。状态日志反映了一个对象修改前或后的状态；转换日志反映了从一个状态到下一个状态的转变。这两种日志记录方式交叉混合，产生了逻辑转换日志、物理状态日志记录、物理转换日志记录，但逻辑日志和状态日志不能混合21。要缩短崩溃后系统恢复所需要的时间，较小的日志可以达到这个目的，故出现了比较新的短暂日志记录(Ephemeral Logging，EL)22技术，继而出现了以EL为基础的扩展短暂
39、日志记录(eXtended Ephemeral Logging，XEL)23,24,25、临时短暂日志(Temporal Ephemeral Logging，TEL)13、高速缓冲短暂日志记录(Cache Ephemeral Logging，CEL)23等。它们的特点是使日志尽可能小，在适当的时候丢弃日志，并在提高系统性能的同时而不会损失恢复性能。2.2检查点技术2.2.1 检查点的作用在使用日志时，原则上在系统发生故障后的恢复过程中，故障恢复模块需要检查所有的日志记录。由于事务的交叉执行，即使某个事务提交并刷新对应的COMMIT日志记录后，系统仍不能删除前面的日志记录，因为前面可能包含一个尚
40、未提交的事务的日志。在这种情况下，日志的长度就不断地增长。一方面由于日志文件不能重用，就要不断提供新的存储设备来满足日志的要求；另一方面，恢复的效率非常低下，每次恢复都从日志的起始位置进行。解决上述问题的一个有效的方法就是周期性地对日志设置检查点，检查点机制使得数据库系统可以定期的减小日志的长度，确定对系统恢复无任何作用的日志。将数据库在内存中的更新页周期性地存储到磁盘，并将日志输出到稳定存储器上，同时将一个日志记录输出到稳定存储器上，以保存系统状态的操作叫做检查点26。检查点技术给系统的平时运行带来了一定的开销，但是可以大大减少恢复时的开销。通过评估检查点的间隔可使系统可用性最大或平均响应时
41、间最小27。2.2.2 检查点的分类根据触发检查点产生的事件对检查点进行分类21,28，包括有：（1）面向事务的检查点(TOC，Transaction-Oriented Checkpoint)TOC在每个事务完成后都要求在磁盘上写下检查点的信息，这样写盘的操作会频繁发生，I/O次数增加，增加了运行时的负担，导致系统性能很差。故对支持大应用程序的DBMS而言，TOC显然不是合适的选择。（2）事务一致性检查点(TCC，Transaction-Consistency Checkpoint)TCC则是每隔一个较长的时间段产生一次，要求此时没有活动的更新事务。TCC是全局的，它存储所有的事务对数据库的修
42、改。当TCC成功完成后，产生一个事务一致性的数据库。但TCC方法导致长时间不能使数据库进行更新，这对于大型多用户DBMS来说不太现实21。（3）活动一致性检查点(ACC，Action-Consistency Checkpoint)由于每个事务都由一个操作系列组成，这些操作可看作DML语句。ACC可在没有操作处理(即无DML)时产生，此时系统处于操作级别的静止状态，这比TCC减少了很多操作。ACC不会导致事务的过长时间的延迟，故比较现实。但当它使用较大的缓冲区时，代价仍然很高。（4）模糊检查点(FUZZY Checkpoint)。模糊检查点技术综合了静止检查点和ACC的特点9,21。静止检查点要
43、求在检查点期间不能接受新的事务，等待所有当前活动事务提交并将更新刷新到稳定存储器才可以接受新的事务。而使用模糊检查点技术时在检查点期间可以接受新的事务，在使用undo/redo日志的情况下，模糊检查点期间只需要记录当前活动事务列表和将所有脏页刷新到稳定存储器中。在执行检查点最耗时的刷新脏页这个时间段，FUZZY检查点仍允许事务继续执行。它缩短了系统处于静止状态的时间，提高了系统在检查点时的并发度。2.3传统恢复策略的分类传统数据库系统的故障恢复主要有基于日志的技术和基于影子分页29的技术。影子分页的优点是没有写日志的开销，并且恢复的代价很小。但影子分页有很多缺陷：包括数据碎片多、要进行垃圾回收
44、、不适用于有并发事务的情况、提交负担高等。所以大多数主流DBMS都采用了基于日志的恢复技术。根据一些不同的分类准则，可以对恢复算法或策略分类。2.3.1 根据三个层次对恢复策略的分类数据库系统的恢复策略可根据页面替换、事务结束处理、检查点这三个层次对其分类。页面替换可分为偷窃的(STEAL)和非偷窃的(NO-STEAL)9,21。STEAL方法可在任何时候将修改页写盘，灵活性强。NO-STEAL方法则要求在事务结束前，所有修改页都保存在缓冲区，这要求数据库缓冲区足够大。NO-STEAL方法的好处是避免了在系统冲突或者事务失败时显式的UNDO，系统性能高；但对并发事务时，它所要求的缓冲区空间理论
45、上是无限大，在实际条件上难于满足。NO-STEAL方法常常用在主存数据库系统中。事务结束处理分为强制(FORCE)方法和非强制(NO-FORCE)方法9,21。强制方法要求在提交操作阶段之前把所有脏页更新到数据库，这使某些热点页被频繁的多次写盘，I/O次数增加，降低了系统性能；非强制方法对在事务结束时脏页的更新与否不作要求，可以延迟更新21。检查点可根据前面提到的分为：面向事务检查点TOC、事务一致性检查点TCC、活动一致性检查点ACC、模糊检查点FUZZY。其中的TOC是和FORCE方法联系在一起。2.3.2 基于日志的恢复策略分类基于日志的主要有UNDO/REDO（撤销/重做），NO-UN
46、DO/REDO（无撤销/重做），UNDO/NO-REDO（撤销/无重做）等方法。Kumar、Hsu30及Kumar、Son31最近的两本书详细讨论了恢复机制，包括对现在存在的多个关系数据库系统的恢复机制进行了描述。每个恢复算法都属于四类中的一类，这四类是以有没有undo日志、有没有redo日志组合而成的。如果允许未提交的事务写数据库，则需要undo日志；如果允许事务在写数据库前提交，则需要redo日志。实践中，既有undo又有redo的算法是商用系统中实现的唯一一类32。这是因为如果以磁盘为介质，没有redo日志或者没有undo日志都会给一般的操作带来较大的负载。(1)UNDO/NO-REDO
47、恢复此种恢复策略在系统正常运行时采用偷窃(STEAL)/强制(FORCE)方法。STEAL意味着数据库的缓冲区（CACHE）管理器可在事务提交前刷新脏页到数据库。FORCE意味着CACHE管理器必须在事务提交前刷新所有脏页到数据库。UNDO/NO-REDO恢复的一个缺点是：对长时间事务，事务回滚要在日志中回溯很远。它的主要问题在于FORCE策略的使用。在FORCE方法下，数据库缓冲区中的脏页必须全部在事务完成前写入数据库，这对于频繁更新的页，要多次写数据库，代价很大。UNDO/NO-REDO恢复的另一个缺点在于没有保存重做信息。没有重做信息意味着对介质故障的恢复是不可能的。如果要考虑介质故障，
48、必须记录重做信息。在文献33中提出了一种基于事务的为UNDO恢复的快速日志记录方法。(2)NO-UNDO/REDO恢复此种策略在系统正常运行时采用非偷窃(NO-STEAL)/非强制(NO-FORCE)方法(原地更新策略下，NO-STEAL意味着NO-FORCE)。NO-STEAL意味着CACHE管理器不能在事务提交之前刷新脏页。NO-UNDO/REDO策略的主要优点是在于在正常运行时有较好的性能。对数据库修改的刷新可采用延迟更新，即可在提交之后刷新数据库。延迟更新使得更新与事务是异步的，它允许CACHE管理器在方便的时候才去刷新脏块；并可一次收集较多的块，甚至收集一组相邻的块来刷新，这可以改进系统性能。NO-UNDO/REDO策略的另一个优点在于它对UNDO代价较高的操作特别有用。此种策略的主要缺点在于应用了NO-STEAL方法，这限制了CACHE管理器