您的当前位置：首页论文终稿(王飞)

论文终稿(王飞)

来源：尔游网

分类号

学号 612100200672093

密级公开

学校代码 10487

硕士学位论文

嵌入式移动实时数据库系统的

恢复策略研究

学位申请人：王飞

学科专业：计算机软件与理论指导教师：卢炎生教授答辩日期： 2008年5月28日

A Thesis Submitted to Huazhong University of Science and Technology for the Degree of Master of Engineering

Research on Recovery Strategy of Embedded

Mobile Real-time Database System

Candidate : Wang Fei Major

: Computer Software and Theory

Supervisor : Prof. Lu Yansheng

Huazhong University of Science and Technology

Wuhan 430074, P.R.C.

May, 2008

独创性声明

本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。

学位论文作者签名：

日期：年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

保密□，在_____年解密后适用本授权书。

本论文属于

√。不保密□

（请在以上方框内打―√‖）

学位论文作者签名：

日期：年月日

指导教师签名：

日期：年月

华中科技大学硕士学位论文

摘要

随着计算机嵌入式技术的快速发展和移动技术的不断进化和完善，嵌入式移动设备的性能得到很大的提高，同时各种应用对实时性的要求也越来越高。由移动计算、实时应用结合传统数据库技术而形成的嵌入式移动实时数据库系统已成为数据库领域的热点课题，数据库系统的恢复是其中的关键技术，恢复系统要充分考虑资源、时效、应用环境的，满足恢复的实时性和移动性。

嵌入式移动实时数据库系统的恢复系统除了要满足传统恢复系统的基本特性外，还要着重考虑移动主机端的日志存放、基站端的日志存放、过区切换策略、检查点策略等问题。使用短暂日志和动态检查点频率的两级日志恢复算法AR-2LL-ELDCF (Algorithms for Recovery based on 2-Level Log Using Ephemeral Log & Dynamic Checkpoint Frequency)是一种有效的恢复策略。

AR-2LL-ELDCF算法使用短暂日志的思想，在移动主机端只保存一般恢复时需要的undo日志，称为有效短暂日志，同时将过期短暂日志发送到基站保存以满足之后的审计需要；如果有效短暂日志在移动主机端保存不下，则发送到基站进行保存，需要恢复时就从基站读取有效短暂日志数据。

AR-2LL-ELDCF算法使用动态检查点频率，使有效短暂日志的大小合适，尽可能在移动主机端可以全部保存，以便系统崩溃后可以迅速恢复。该算法的过区切换策略与有效短暂日志传输到基站的策略紧密结合，可以在需要基站保存有效短暂日志的情况下缩短恢复时间。

关键词：移动实时恢复，短暂日志，两级日志，过区切换

华中科技大学硕士学位论文

Abstract

With 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. Embedded 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 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 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, which 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 ephemeral 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 transfer, which can reduce the recovery time.

Keywords: Mobile real-time recovery, Ephemeral log, 2-Level log, Handoff

华中科技大学硕士学位论文

摘要 ............................................................................................................... I ABSTRACT ................................................................................................... II 1 绪论

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 一种嵌入式移动实时数据库系统的恢复策略

3.1嵌入式移动实时数据库系统恢复模型 ............................................... (18) 3.2基于两级日志的嵌入式移动实时恢复算法 ....................................... (24) 3.3本章小结 ................................................................................................ (39)

III

华中科技大学硕士学位论文

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）得到了越来越广泛的应用，成为计算机应用系统中不可缺少的组成部分。同时，许多应用场合对数据查询处理的需求也越来越高：要求随时随地查询所需的数据，并且需要在限定时间内得到回应，这就需要有一种能满足这些需求的嵌入式移动实时数据库系统（Embedded Mobile Real-Time Database System，EMRTDBS）。

与传统数据库系统相比，由于嵌入式移动实时环境的特性，它可以支持更多新的应用：公共信息发布，用户通过无线便携设备了解新闻、股票、天气等信息资源，并及时做出决策；军事作战，每个士兵都作为的系统单元，实时处理战场信息并与服务器进行交互，服务器综合各单元的移动信息指挥整个战场行动；移动电子商务，随着用户所处地点的变迁，数据库查询将总是显示最新有效的商务信息，满足商务用户对位置相关和异地操作的特殊要求。本课题组的目标便是开发出一个嵌入式移动实时环境下的数据库管理系统，支持移动终端的嵌入式数据库和中心服务器数据库的运行和管理。

和普通的数据库系统一样，嵌入式移动实时数据库系统可能会由于一些不可预知的软硬件故障而影响事务的正确运行，造成数据库中的数据丢失甚至破坏数据库，给数据库的一致性和可靠性维护带来挑战。而恢复系统的作用正是在出现故障后将数据库中数据从不一致的状态恢复到某种逻辑一致的状态。

各种现有数据库系统运行情况表明：数据库系统采用的恢复技术是否行之有效,不仅对系统的可靠程度起着决定性作用，而且对系统的运行效率也有很大影响，是衡量系统性能优劣的重要指标。由于移动环境的移动性和易错性[1]等特点，嵌入式移动实时数据库系统可能要面对更多的故障，需要更频繁地进行恢复。同时，嵌入式

华中科技大学硕士学位论文

移动实时数据库系统要满足各种应用的实时性要求，遇到故障后的快速恢复是系统达到实时性要求的重要保证。

嵌入式移动实时数据库是传统数据库发展的新阶段，可以满足许多应用场景的需要，特别是对武器制导这种对实时性、移动性和嵌入性要求很高的应用更为重要，而恢复系统作为保障整个数据库系统在故障情况下迅速恢复正常运行的子系统，其重要性不言而喻，有着非常重大的理论和实际意义。

1.2 嵌入式移动实时数据库系统的特点

1.2.1 嵌入式系统

嵌入式系统是以计算机技术为基础，根据应用的具体需求来量身定制的专用计算机系统，它的软硬件可裁剪，同时对功能、可靠性、成本、体积、能耗等有严格的要求。

恢复子系统的设计要充分考虑这些硬件的性能问题，如电源有限和内存有限的问题。嵌入式系统一般使用电池供电，要尽量节能才能延长使用时间；同时内存相比一般PC机也是很小的，要使用尽可能小的内存完成需要的功能。在系统设计时要做相应的优化和设计，以充分利用系统资源，提高应用效率。 1.2.2 移动数据库系统

移动数据库系统模型如图1.1所示。由于移动环境的移动性、连接的频繁断接性、网络条件的多样性、网络通信的非对称性、系统的高伸缩性和低可靠性以及资源有限性等特点，使得移动事务相比传统的分布式事务具有移动性、长事务、易错性和异构性等特点[1]。传统的ACID特性已经不能很好的表征移动事务的一致性，要为恢复系统的一致性准则找出新的标准，同时要解决过区切换对恢复系统的影响。

华中科技大学硕士学位论文

MH4MH3BS3基站(BS)BS1MH1固定网络BS2MH2移动主机(MH)无线网络

图1.1 移动数据库系统模型

1.2.3 实时数据库系统

实时事务不同于传统事务，它不是以ACID特性作为正确性标准的。实时数据库

的数据和事务都可以具有定时特性或显式的定时，系统的正确性不仅依赖于逻辑结果，还依赖于逻辑结果产生的时间[2]。有时候为了要满足实时性的需要，可能要以牺牲一部分的一致性作为代价。

实时数据库与传统数据库最大的区别在于其一部分数据和事务是“实时”的，即有时间的。 1．实时数据

数据的“实时”性表现为有效期，超过有效期的数据是无效的，需要重新读入进行刷新。这部分数据的正确性不仅取决于数据库内的完整性和逻辑一致性，还取决于其有效期是否满足。

要保持数据库中的实时数据尽量处在有效状态，在此提出时态一致性的概念。对实时数据库中的一个数据对象d，其被观测或采样的时刻记为ot(d)，其绝对有效时间的结束又称外部有效期记为evi(d)，对象在数据库中记录的当前值记为v(d)，则实时数据对象可以用一个三元组表示为d: [3]。

定义1.1 实时数据d具有绝对时态一致性，当且仅当d的当前值满足数据库内部的完整性和一致性逻辑要求且ct(d)－ot(d)≤evi(d)，其中ct(d)为当前检测时间。

华中科技大学硕士学位论文

定义1.2 用来作决策或导出一个新数据的一组数据称为一个相互（相对）一致集，每个数据集都与一相对有效期（Relative Validity Interval）相联，记为Rrvi 。

定义1.3 当且仅当d1,d2∈R有| ot(d1)－ot(d2) |≤Rrvi ，R是一个相互一致集。 2．实时事务

事务的“实时”性表现为截止期，超过截止期的事务会影响整个数据库的一致性。依照实时事务的特征，一般按如下几种方法将实时事务分类。

（1）按关键性分类

根据实时事务的时限的性质，即事务超过截止期后对系统带来的影响分类，可将实时事务分为硬实时事务、软实时事务和固实时事务三类[4]：

硬实时事务超截止期会导致恶果（价值函数取大且可能不断增加的负值）。它对应于安全危急性活动。

软实时事务超截止期仍有一定的价值，且价值不断下降，直到某一时刻（称为最终有效时间）降到零，此后保持为零（不会为负）。

固实时事务一旦到达截止时间，其价值立即降为零，此后固定为零（也不会为负）。显然，它是软实时事务在最终有效时间与截止时间重合情况的特例。

图1.2所示为这三种实时事务的价值函数，其中横轴t表示时间，纵轴v表示这个事务的价值，s为事务的开始时间，d是截止期，e表示事务价值降为0的时间。

vvvtsesetsetd(a)硬实时事务d(b)软实时事务d(c)固实时事务

图1.2 三类实时事务的价值函数

（2）按功能分类

华中科技大学硕士学位论文

一个实时数据库系统以两种方式直接与现实世界交互作用，一是关于现实世界状

态或事件的信息被记录到数据库中，二是事务可以启动各种影响现实世界的活动。这就导致如下事务分类方法：

数据接收事务记录现实世界的状态或发生的事件到数据库中。它是简单的只写事务；为了保持数据库的“外部一致”和跟踪记录，它应是短的、周期的，且应是被立即执行（不能等待和阻塞）的硬实时事务。为了保证其定时的满足，它可能会引起对数据库一致性的破坏。

数据处理事务类似传统数据库的事务。它对数据库中的数据进行读写，通过对已有数据的运算得到新的数据。

控制事务引起现实世界中有关活动的执行。像数据接收事务一样，这种事务是很短的，尽管所引起的现实活动可能要执行很长时间。它通常也是硬实时的。这种事务还可以作为数据处理事务的子事务而被调用，而它本身也可以触发子事务，比如以一子事务来检测所引起的现实活动。

随着嵌入式移动实时数据库应用市场需求的与日俱增，越来越多的商家都投入到这个大的开放性的市场中，也出现了一系列各具特色的商业产品。在国外，有Sybase提供业界领先解决方案的SQL Anywhere，Oracle针对移动计算推出的Oracle Lite，IBM的DB2 satellite及DB2 Everyplace，以及微软的MSDE引擎等等；在国内，也逐步由理论研究转向实际产品开发，较有代表性的有东北大学的OpenBASE Mini，金仓研发的“小金灵”系统等。现在嵌入式移动实时数据库已经形成了较为成熟的产业，成为嵌入式系统不可缺少的部分，但是相对国外数据库的发展模式而言，国内起步较晚、应用面较小、应用领域也不够广，同时存在着理论研究、原型设计与产品商业化分离的不足。不过随着计算终端的小型化，应用领域的不断扩展，可以预见，不久的将来其应用将进入到移动互联网、移动电子商务政务、移动物流、移动金融系统、移动新闻等多个商业与经济领域。

华中科技大学硕士学位论文

1.3 恢复

恢复子系统是数据库系统不可缺少的组成部分，传统数据库系统恢复策略的研究已经非常深入，分别对应于嵌入式、移动、实时环境的恢复也已研究颇多。

Davis于1973年在文献[5]和[6]中提出了控制区域（Soc）的思想，随后演变成了事务的概念。Chandy等人在文献[7]中描述了数据库系统的回滚和恢复的分析模型。

Verhofstad在文献[8]中针对不同的故障形式提出了七种恢复技术,包括：救助程序、增量备份、审计跟踪、微分文档、备份当前版本、多重拷贝、仔细替换。Haerder和Reuter在文献[9]中对恢复原理进行了全面的阐述。 1.3.1 传统数据库系统的恢复

传统数据库系统的恢复技术本身涉及到多个方面，如日志记录、备份与恢复的机制与策略、检查点技术等。

但是传统恢复策略没有考虑实时、移动及嵌入式特性对于恢复策略的影响，传统的分布式事务恢复策略也不能直接应用于移动恢复中来。 1.3.2 实时数据库系统的恢复

实时恢复以传统的恢复技术为基础，同时要充分考虑数据及事务的实时性对于恢

复策略的影响。

所谓“实时”，就是能在规定时间内完成规定的操作，实时恢复必须足够迅速，在系统崩溃或事务失败后在尽可能短的时间内将系统恢复到上一个一致状态，使系统能够尽可能快地重新投入使用。同时，恢复策略带来的运行时开销要足够小，不能影响系统正常运行时的实时性。

实时恢复也要对数据进行区别对待，比如重要数据和硬实时事务要使用的数据要首先恢复，保证系统的硬实时事务截止期能够满足，而其他一些数据可以在稍后再进行恢复。

有时候为了保证系统的实时性，可以牺牲一些一致性。有些数据会周期性的从外

华中科技大学硕士学位论文

界读入进行更新，这些数据在恢复时可以不用考虑，在下次更新中会成为有效数据。

对实时数据库系统的恢复策略的研究虽然没有传统数据库系统的恢复研究成果多，但是也已经比较深入。

Huang的博士论文[10]是最早研究实时数据库恢复策略的论文之一，文献[11]是他博士论文中实时恢复策略思想的精简。他提出实时内存数据库的四种恢复技术，这些技术同时适用于时态和非时态数据，同时考虑了时态数据的有效性。这四个日志技术的区别在于一般操作过程中的无效数据是否计入日志，以及时态、非时态数据的日志是否保存在同一个日志缓冲中。他还提出了更新频率有效间隔（update-frequency-valid-interval）检查点策略。在这个策略中，非时态数据基于更新频率分区，而时态数据基于它们的有效期分区。含有最经常更新页面的非时态数据的分区（称为热分区）将比其他分区有更多的检查点。时态数据，尤其是那些有效期很短的，将尽可能频繁地刷新到磁盘中。这样，恢复过程只需处理相对较少的日志信息即可。因此，这个设计的目的在于用运行时的检查点开销来换取较少的恢复时间。同时，希望时态数据的频繁刷新可以保证临时数据在失效之前被使用。为了减少检查点带来的负载，对于有效期小于某个预先定义的阈值的时态数据不记录其日志，也不设置检查点。

Gruenwald和Cheng在文献[12]中提出基于日志类型的实时内存数据库日志技术。事务类型日志（TTL）通过增加一定的日志空间，减少了redo的代价，也减少了事务处理过程中内存访问的次数。当数据库中时态数据的比例超过50%后，TTL的性能超过了Huang提出的使用多缓冲的时态-非时态日志技术。

Sivasankaran在文献[13]中讨论了实时主动数据库中的数据的特征及数据存放、日志和恢复如何满足性能要求，同时也讨论了实时主动数据库中影响数据存放、日志和恢复的事务特征。他强调需要设计一个新的日志恢复算法来解决优先级反转问题（优先级反转，即高优先级的请求要为低优先级的请求做一些工作，如一个事务提交后要刷新自己的以及比自己优先级低的事务的日志）的迫切性[14]，而传统数据库日志和恢复算法不适用了面向优先级的实时数据库。他提出了数据特征的分类方法以及从数据类型和事务类型衍生出的两个数据类，同时提出一套适用于RTDB的

华中科技大学硕士学位论文

算法。

文献[15]提出了一种识时的（Time-Cognizant）日志恢复策略，使用条件日志（Conditional Logging）的思想，将数据分为重要时态数据（Critical Variant Data）、重要非时态数据（Critical Invariant Data）和非重要数据（Non-Critical Data）分别进行日志记录。这里的非重要数据都是非时态数据，对于非重要时态数据不进行日志记录，因为这类数据恢复后一般也超过了有效期，不如重新从环境中读取。重要时态数据的日志分多个文件记录，每个文件中日志产生的时间是连续的，不同日志文件的时间是不交叉的，恢复的时候，同一个文件中的日志被看作一个整体，要么全部有效，要么全部无效，这样缩短了判断日志数据时候有效的时间。同时，将重要数据的日志记录在非挥发性RAM（Non-Volatile Random Access Memory, NVRAM）中，而将非重要数据记录在磁盘（Disk）中，这样当故障发生时，可以在预定的时间内恢复重要数据，使系统恢复正常运转，然后再在后台恢复非重要数据，缩短了恢复需要的时间，提高实时性。并且在系统正常运转过程中不做过多的检查点，将日志对系统性能的影响降至最低。与文献[10]的方法相比，该方法在平时正常运行时的额外开销较小，恢复时间稍微长一点，但是在时态数据有效期较短的情况下，恢复时间的差距并不是很大。

文献[16]将实时日志分为实时事务日志、实时数据日志和活动日志三类，并考虑嵌入式环境的特点，给出记录日志的如下规则：短时限时序数据对象不记录更新日志；数据的更新程度小于某个阈值则不记录更新日志。这样可以大大减少记录时序数据更新日志的存储开销，加快恢复速度。同时，对于不同类型的数据采用不同的数据库修改技术：时序数据对象采用立即更新技术，使时序数据的最近状态能及时反应到数据库中去；非时序数据则采用延迟更新方式。提出识时恢复正确性准则，将事务分为数据接收事务、数据处理事务和控制事务三种，基于识时恢复正确性准则给出这三种事务的恢复算法。 1.3.3 移动数据库系统的恢复

移动事务由于其自身的特点，如移动性、连接的频繁断接性、网络条件的多样性、

华中科技大学硕士学位论文

网络通信的非对称性、系统的高伸缩性和低可靠性以及资源有限性等，使得在恢复时要特别考虑移动性对恢复系统的影响。

要保证在移动环境中可以正确、迅速地恢复数据库到一致状态，要充分考虑移动事务相对于传统事务的各种特征，要着重考虑过区切换时日志的存放和传输策略以达到快速恢复的要求。

在移动数据库系统的恢复研究方面，文献[17]中提到了备份处理镜像的同步方法和异步方法，以及过区切换时日志传输的懒惰模式和悲观模式。备份处理镜像的同步方法是在每一个写事件（改变数据库状态的事件，可以是用户输入或基站传入的信息）之后都备份“增量”的处理镜像，而异步模式则是在一定数目的写事件或一定的时间间隔后才备份处理镜像，这相当于传统数据库的检查点方法。对于过区切换时的日志传输策略，在懒惰模式中，日志存放在BS（Base Station）中，MU（Mobile Unit）移动到一个新BS中时要在这个新BS中存放旧BS的指针，这个指针用来在发生故障时使用分布在多个BS中的日志进行恢复。这个模式的优点是切换时的网络开销相对较小，因为不需要传送日志信息，但是不幸的是这个模式需要的恢复时间很长。在悲观模式中，整个日志和检查点在切换时都传送到新BS中，因此恢复时间很短但是切换时需要大量的数据传输。

文献[18]中给出两个模式，这两个模式基于MU的移动，使用的检查点和悲

观日志。这两个模式中，日志分布的BS列表在切换时进行传送。在基于距离的模式中，在MU移动的距离达到某个预先定义的值后进行日志规整。在基于频率的模式中，当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恢复的时候不用从很多

华中科技大学硕士学位论文

的BS收集日志信息。如果MH从region1移动到region2，则前一个指定BS把日志全部传送到新的指定BS。同时该文章还讨论了在过区切换时发生故障的情况及对策。 1.3.4移动实时数据库系统的恢复

关于移动实时数据库系统的恢复策略几乎没有专门的文章研究，只是在某些研究

移动恢复策略的论文中提到了如何满足实时要求，但是没有深入讨论。在文献[17]中，作者提出备份处理镜像时使用同步方法适用于有硬实时要求的场合，同时，过区切换传输日志时使用悲观策略也可以在一定程度上满足实时环境下快速恢复的需要。文献[19]提出的方法将所有日志集中在一个地方，以便于支持硬实时需求下的快速恢复。但是它们都不是专门为实时环境研究的，只是稍微考虑了一下实时性的需求。

1.4 本文组织

本论文的组织结构安排如下：

第一章介绍嵌入式移动实时数据库系统的基本理论和应用背景，简单概括该环境

下数据及事务的新特点，以及恢复所要面临的问题，着重讨论了实时环境下和移动环境下的恢复策略研究现状；

第二章介绍了恢复系统的基本理论和方法，讨论了实时环境下和移动环境下的恢

复系统应考虑的问题；

第三章根据课题的具体要求提出一种两级日志恢复模型，针对此模型分析了已有

的恢复算法的不合适之处，提出改进思想，设计出一种使用短暂日志和动态检查点频率的两级日志恢复算法；

第四章应用第三章中的算法开发出一个恢复原型系统，并选定模拟嵌入式移动实

时环境的参数，在该原型系统上对算法进行性能评价实验；

第五章对全文工作进行总结，并指出以后研究工作的方向。

华中科技大学硕士学位论文

2 恢复的基本理论和方法

虽然目前计算机硬软件技术已经发展到相当高的水平，但硬件的故障、系统软件和应用软件的错误、操作员的失误以及恶意的破坏仍然是不可避免的。为了保证各种故障发生后，数据库中的数据都能从错误状态恢复到某种逻辑一致的状态，数据库管理系统中恢复子系统是必不可少的。各种现有数据库系统运行情况表明：数据库系统所采用恢复技术是否行之有效，不仅对系统的可靠程度起着决定性作用，而且对系统的运行效率也有很大影响，是衡量系统性能优劣的重要指标。

传统DBMS的恢复技术本身涉及到多个方面，如日志记录、备份与恢复的机制与策略、检查点技术等。对传统数据库系统的恢复策略的研究已经非常深入，分别对应于嵌入式、移动、实时环境的恢复研究也已取得较丰富的理论与实际成果。

2.1日志

2.1.1 日志的作用

日志是事务操作的一个序列，每个日志记录记载有关某个事务已做的事的某些情况。几个事务的执行可以是\"交错的\"。如果系统崩溃，日志将被查阅，以重建崩溃发生时正在执行的事务。

日志在数据库系统的恢复中起着非常重要的作用，可以用来进行事务故障恢复和系统故障恢复，并协助后援副本进行介质故障恢复。

要使日志在恢复中正确达到将数据库系统恢复到某个一致状态的目的，登记日志文件时必须遵守日志先写协议(WAL)。 2.1.2 日志先写协议（WAL）

为保证数据库是可恢复的，登记日志文件时必须遵循两条原则[20]： 1.登记的次序必须严格按并发事务执行的时间次序；

华中科技大学硕士学位论文

2.必须先将日志缓存中的日志信息写入日志文件，后将数据缓存中的数据写到数据库的数据文件。

数据缓冲管理器将脏数据页写到磁盘和日志管理器将对应这个修改的日志记录写到日志文件是两个不同的操作。系统有可能在这两个操作之间发生故障，即这两个写操作只完成了一个。如果系统先写了数据库修改，而在日志记录中没有登记这个修改，则以后就无法恢复这个修改了。如果先写日志，但没有修改数据库，按日志文件恢复时最多执行一次不必要的撤销操作，并不会影响数据库的正确性。所以为了安全，一定要先写日志文件，即首先把日志记录写到日志文件中，然后写数据库的修改。这就是“先写日志文件”的原则。 2.1.3 日志技术

日志记录方式根据收集日志信息的表示级别，可分为物理日志和逻辑日志[21]。根据修改前或后数据库状态和被记录状态的转换，可分为状态日志和转换日志。状态日志反映了一个对象修改前或后的状态；转换日志反映了从一个状态到下一个状态的转变。这两种日志记录方式交叉混合，产生了逻辑转换日志、物理状态日志记录、物理转换日志记录，但逻辑日志和状态日志不能混合[21]。

要缩短崩溃后系统恢复所需要的时间，较小的日志可以达到这个目的，故出现了比较新的短暂日志记录(Ephemeral Logging，EL)[22]技术，继而出现了以EL为基础的扩展短暂日志记录(eXtended Ephemeral Logging，XEL)[23,24,25]、临时短暂日志(Temporal Ephemeral Logging，TEL)[13]、高速缓冲短暂日志记录(Cache Ephemeral Logging，CEL)[23]等。它们的特点是使日志尽可能小，在适当的时候丢弃日志，并在提高系统性能的同时而不会损失恢复性能。

2.2检查点技术

2.2.1 检查点的作用

在使用日志时，原则上在系统发生故障后的恢复过程中，故障恢复模块需要检查

华中科技大学硕士学位论文

所有的日志记录。由于事务的交叉执行，即使某个事务提交并刷新对应的COMMIT日志记录后，系统仍不能删除前面的日志记录，因为前面可能包含一个尚未提交的事务的日志。

在这种情况下，日志的长度就不断地增长。一方面由于日志文件不能重用，就要不断提供新的存储设备来满足日志的要求；另一方面，恢复的效率非常低下，每次恢复都从日志的起始位置进行。

解决上述问题的一个有效的方法就是周期性地对日志设置检查点，检查点机制使得数据库系统可以定期的减小日志的长度，确定对系统恢复无任何作用的日志。

将数据库在内存中的更新页周期性地存储到磁盘，并将日志输出到稳定存储器上，同时将一个日志记录输出到稳定存储器上，以保存系统状态的操作叫做检查点[26]。检查点技术给系统的平时运行带来了一定的开销，但是可以大大减少恢复时的开销。通过评估检查点的间隔可使系统可用性最大或平均响应时间最小

[27]

。

2.2.2 检查点的分类

根据触发检查点产生的事件对检查点进行分类[21,28]，包括有：（1）面向事务的检查点(TOC，Transaction-Oriented Checkpoint)

TOC在每个事务完成后都要求在磁盘上写下检查点的信息，这样写盘的操作会频繁发生，I/O次数增加，增加了运行时的负担，导致系统性能很差。故对支持大应用程序的DBMS而言，TOC显然不是合适的选择。

（2）事务一致性检查点(TCC，Transaction-Consistency Checkpoint)

TCC则是每隔一个较长的时间段产生一次，要求此时没有活动的更新事务。TCC是全局的，它存储所有的事务对数据库的修改。当TCC成功完成后，产生一个事务一致性的数据库。但TCC方法导致长时间不能使数据库进行更新，这对于大型多用户DBMS来说不太现实[21]。

（3）活动一致性检查点(ACC，Action-Consistency Checkpoint)

由于每个事务都由一个操作系列组成，这些操作可看作DML语句。ACC可在没

华中科技大学硕士学位论文

有操作处理(即无DML)时产生，此时系统处于操作级别的静止状态，这比TCC减少了很多操作。ACC不会导致事务的过长时间的延迟，故比较现实。但当它使用较大的缓冲区时，代价仍然很高。

（4）模糊检查点(FUZZY Checkpoint)。

模糊检查点技术综合了静止检查点和ACC的特点[9,21]。静止检查点要求在检查点期间不能接受新的事务，等待所有当前活动事务提交并将更新刷新到稳定存储器才可以接受新的事务。而使用模糊检查点技术时在检查点期间可以接受新的事务，在使用undo/redo日志的情况下，模糊检查点期间只需要记录当前活动事务列表和将所有脏页刷新到稳定存储器中。在执行检查点最耗时的刷新脏页这个时间段，FUZZY检查点仍允许事务继续执行。它缩短了系统处于静止状态的时间，提高了系统在检查点时的并发度。

2.3传统恢复策略的分类

传统数据库系统的故障恢复主要有基于日志的技术和基于影子分页[29]的技术。影子分页的优点是没有写日志的开销，并且恢复的代价很小。但影子分页有很多缺陷：包括数据碎片多、要进行垃圾回收、不适用于有并发事务的情况、提交负担高等。所以大多数主流DBMS都采用了基于日志的恢复技术。

根据一些不同的分类准则，可以对恢复算法或策略分类。 2.3.1 根据三个层次对恢复策略的分类

数据库系统的恢复策略可根据页面替换、事务结束处理、检查点这三个层次对其分类。

页面替换可分为偷窃的(STEAL)和非偷窃的(NO-STEAL)[9,21]。STEAL方法可在任何时候将修改页写盘，灵活性强。NO-STEAL方法则要求在事务结束前，所有修改页都保存在缓冲区，这要求数据库缓冲区足够大。NO-STEAL方法的好处是避免了在系统冲突或者事务失败时显式的UNDO，系统性能高；但对并发事务时，它所

华中科技大学硕士学位论文

要求的缓冲区空间理论上是无限大，在实际条件上难于满足。NO-STEAL方法常常用在主存数据库系统中。

事务结束处理分为强制(FORCE)方法和非强制(NO-FORCE)方法[9,21]。强制方法要求在提交操作阶段之前把所有脏页更新到数据库，这使某些热点页被频繁的多次写盘，I/O次数增加，降低了系统性能；非强制方法对在事务结束时脏页的更新与否不作要求，可以延迟更新[21]。

检查点可根据前面提到的分为：面向事务检查点TOC、事务一致性检查点TCC、活动一致性检查点ACC、模糊检查点FUZZY。其中的TOC是和FORCE方法联系在一起。

2.3.2 基于日志的恢复策略分类

基于日志的主要有UNDO/REDO（撤销/重做），NO-UNDO/REDO（无撤销/重做），UNDO/NO-REDO（撤销/无重做）等方法。

Kumar、Hsu[30]及Kumar、Son[31]最近的两本书详细讨论了恢复机制，包括对现在存在的多个关系数据库系统的恢复机制进行了描述。每个恢复算法都属于四类中的一类，这四类是以有没有undo日志、有没有redo日志组合而成的。如果允许未提交的事务写数据库，则需要undo日志；如果允许事务在写数据库前提交，则需要redo日志。实践中，既有undo又有redo的算法是商用系统中实现的唯一一类[32]。这是因为如果以磁盘为介质，没有redo日志或者没有undo日志都会给一般的操作带来较大的负载。

(1)UNDO/NO-REDO恢复

此种恢复策略在系统正常运行时采用偷窃(STEAL)/强制(FORCE)方法。STEAL意味着数据库的缓冲区（CACHE）管理器可在事务提交前刷新脏页到数据库。FORCE意味着CACHE管理器必须在事务提交前刷新所有脏页到数据库。

UNDO/NO-REDO恢复的一个缺点是：对长时间事务，事务回滚要在日志中回溯很远。它的主要问题在于FORCE策略的使用。在FORCE方法下，数据库缓冲区中的脏页必须全部在事务完成前写入数据库，这对于频繁更新的页，要多次写数据库，

华中科技大学硕士学位论文

代价很大。

UNDO/NO-REDO恢复的另一个缺点在于没有保存重做信息。没有重做信息意味着对介质故障的恢复是不可能的。如果要考虑介质故障，必须记录重做信息。

在文献[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管理器管理CACHE的能力。当运行长时间事务时，在理论上需要消耗无的CACHE空间。

在文献[34]中，对REDO恢复进行了剖析，定义了一个运行时的操作装载图，它的次序远比并发控制的冲突次序弱。此文献中描述了如何根据系统的状态、日志、缓冲区等进行REDO恢复，是在传统REDO日志的基础上更为精细的控制。

(3)UNDO/REDO恢复

基于日志的UNDO/REDO恢复策略是最具有弹性和较优性能的。它在系统正常运行时采用STEAL/NO-FORCE策略。它使CACHE管理器较少依赖于恢复管理器，根据正常的CACHE替换策略向数据库刷盘。它对数据库的更新可以是即刻的或延迟的，这意味着UNDO恢复和REDO恢复都需要。

为保证对事务提交更新的永久性，对比UNDO/NO-REDO恢复，UNDO/REDO恢复在提交时刻强制写重做信息到日志优于强制写更新页到数据库，因为对日志的顺序写比对数据库的随机写快的多，性能上有很大的优势。

华中科技大学硕士学位论文

2.4 经典的恢复算法ARIES

ARIES(Algorithm for Recovery and Isolation Exploiting Semantics)算法在文献[35]中首次详细阐述了其核心内容。它的关键特征为：物理日志和操作日志（逻辑日志）；基于页的重做；逻辑UNDO；基于写日志优先原则和原地更新策略；支持部分事务回滚；支持细粒度的并发控制；弹性的存储管理；恢复性；快速恢复和并行性；STEAL/NO-FORCE的缓冲区管理策略。ARIES是使用STEAL、NO-FORCE的一种非常通用的恢复算法。由于ARIES算法的简单、有效、灵活性，使其很快从原型系统中脱颖而出，不仅成为此后IBM数据库系统恢复算法的基础，并在其商品化的数据库产品中得以广泛应用。ARIES中的一些成功的做法也为其他公司推出的DBMS所借鉴，如Sybase、Ingres等。

2.5移动实时数据库系统恢复的相关理论

移动实时恢复技术基于传统的恢复技术，但是要考虑更多的因素，包括显式的截止期对于恢复速度的要求，以及移动环境下诸如弱链接、低链路速度等各种特点对于恢复策略的影响。

对于移动实时环境下的恢复策略的研究几乎没有，但是分别对于移动情况下和实时情况下的恢复策略理论研究已经颇有成果，主要包括根据数据类型、事务类型对日志进行分类记录，根据访问频率设置检查点的频率，将日志存放在非挥发RAM中，移动环境下的过区切换日志传输策略等。

2.6 本章小结

本章介绍了恢复系统对于整个数据库系统正常运行的重要作用，简要介绍了国内

外常见的一些恢复方法和策略，讨论了实时环境下和移动环境下设计恢复算法时需考虑的一些问题。

华中科技大学硕士学位论文 3 一种嵌入式移动实时数据库系统的恢复策略

3.1嵌入式移动实时数据库系统恢复模型

3.1.1 嵌入式移动实时数据库管理系统框架

本课题组的任务是研究数据库系统基本理论在嵌入式移动实时环境下的应用和

实现，并最终开发出适用于军事作战环境需要的数据库管理系统，称为EMRTDBMS ( Embedded Mobile Real-time Database Management System )，其应该达到如下要求：

（1）微内核结构

由于嵌入式设备的处理芯片、存储容量等资源，同时该系统还要运行在嵌入式设备的RTOS中，RTOS本身也会使用一些内存，所以该系统的内核要足够小，要可以在内存容量有限（如内存只有256kB）的情况下运行

（2）功能模块可裁剪

该系统必须适应各种嵌入式客户端的应用环境，系统功能应该可以根据应用需要和资源（如内存容量的）进行适当裁剪和组装，能不受移动终端地提供服务。

（3）支持标准SQL，同时进行适当扩充

系统需要提供对SQL92标准的子集的支持，至少满足复杂查询、增加、删除、更新等数据操作功能和简单的建删表、建删视图等数据定义功能，同时由于该系统对实时性的需求，要对SQL进行适当扩充，以满足显式定义时间的需要。

（4）移动性及数据同步

移动客户主机通过无线网络与中心服务器通信，虽然无线网络环境很差，但要最大限度保证数据的同步，在移动断接的情况下首先满足弱一致性，待网络恢复后更新保持全局数据的一致性。

（5）实时性

由于该系统要工作在作战环境等对实时性要求很高的环境下，所以该系统应该有

华中科技大学硕士学位论文

很好的实时性，包括数据的实时性、事务的实时性、以及出现故障后系统恢复的实时性等。

嵌入式移动实时DBMS包括服务器和客户端两个部分，之间通过无线网络进行

连接，其系统结构如图3.1所示：

移动主机MH1应用EMRTDB Client EDB 移动主机MHm移动主机MH2BS1中心服务器CS移动连接管理移动主机MH3BS2EMRTDB Server CDB BSn„„„„BS3„„„„„„„„移动主机MH4„„„„„„„„移动网络固定网络

图3.1 嵌入式移动实时DBMS系统结构图

中心服务器CS（Central Server）是整个系统的服务器，其上安装有嵌入式移动

华中科技大学硕士学位论文

实时数据库系统的服务器端，存放所有的数据，管理与移动主机的连接。

移动基站BS（Base Station）是连接中心服务器和移动主机的纽带，由于无线信号的传播范围有限，必须使用移动基站来扩大移动信号的覆盖区域。移动基站通过高速有线网络与中心服务器连接，使用无线网络与其所覆盖区域内的移动主机进行通信，当移动主机离开当前基站进入另一个基站时，这两个基站要处理移动主机过区切换的问题。

移动主机MH（Mobile Host）是系统的最终使用者，每个移动主机上有自己的嵌入式数据库，整个数据库管理系统的客户端部分功能可以局部地在移动主机上执行，在用户不需要获取当前全局数据的情况下，EMRTDBMS Client能完成用户任务。当用户执行移动事务时，移动主机先部分执行该事务，维持本地数据一致性，再提交给中心服务器数据库以保证全局数据同步，针对无线网络环境要设置断接重连机制和数据缓存机制，中心服务器上根据时间特性和网络状况合理地接收数据，EMRTDBMS Server执行移动事务并更新中心数据库，然后提供一定的广播机制将最新的数据库状态传送给所有有相关应用需求的移动客户主机，维持全局数据的一致性。

3.1.2 实时数据库系统恢复模型

传统的数据库系统使用顺序日志，采用Steal缓冲管理策略（允许数据缓冲区的

脏数据写入磁盘）和No-Force的提交策略（允许事务提交前不将更新写入磁盘）。No-Force策略的提出是因为磁盘访问很慢，而Steal策略是为了防止数据缓冲区没有足够空间。传统的日志恢复策略对于所有数据和日志都在磁盘上的数据库是最优的，但是由于日志是顺序的，在恢复过程中无法识别时间和优先级，这无法满足面向优先级的抢占式的实时数据库的要求。

在实时数据库系统中，通常情况下CPU调度、I/O调度和并发控制冲突处理都是基于事务的优先级的[36]。但是传统日志和恢复技术是顺序的，在这样一个面向优先级的抢占式实时数据库系统中不能很好地工作。

因此EMRTDBS所用的恢复策略不能采用传统的日志技术，而是要对其进行相

华中科技大学硕士学位论文

应的改进。如今对实时恢复的研究已经比较深入，包括对日志进行分区记录（按数据的重要性、实时性分区，或按事务的重要性、实时性分区）、对不同类别的数据采用不同的恢复策略、使用非挥发性RAM（Non-volatile RAM）作为稳定存储介质等。

EMRTDBS又有自己独特的特点，它分为服务器端和嵌入式客户端两个部分，因此要同时考虑服务器端的重负载特性和客户端的嵌入式特性。

服务器端负责整个系统中所有事务的执行，因此负载会比较重，要保证其恢复系统在正常运行时的低开销和在恢复时的高速度，但是这两者是矛盾的，需要在它们之间找到一个平衡点。使用NVHSS（Non-Volatile High Speed Store）技术可以提高系统的I/O性能[37]，进而提高恢复系统的性能。作为NVHSS技术之一的SSD（Solid State Disk，固态盘）技术在文献[38]中已经提到，经过近20年的发展，该技术已经成熟并且在慢慢普及，在服务器端使用固态硬盘可以大幅提升系统的I/O性能进而提高系统的实时性。同时，为了保证恢复过程的实时性，服务器端应采用当前研究成果中常用的多日志技术，对数据和事务进行分类，分别记录日志，分别进行恢复。

客户端由于安装在移动主机的嵌入式系统中，因而要充分考虑嵌入式设备的特性，如存储空间少、能量有限等。嵌入式一般使用Flash芯片作为稳定存储介质，其容量小速度快。根据这个特性，在选择日志策略时可以选择传统日志策略不会用到的steal/force策略（即事务更新的脏数据可以在事务提交前刷新到稳定存储器，事务提交时必须将该事务的所有更新数据刷新到稳定存储器中，传统日志一般使用steal/no-force策略），同时由于其稳定存储器的容量，故应使用短暂日志[37]，即在日志不再需要时将之丢弃。使用steal/force策略只需记录undo日志，不需要redo日志，也可以节省一定的存储空间。 3.1.3 移动数据库系统恢复模型

移动数据库系统的恢复过程和传统数据库系统相比复杂得多，主要由于移动环境的以下特有的特性[39]：

 位置不固定：用户从一个地方移动到另一个地方，MH在网络中的位置变化

了。

华中科技大学硕士学位论文

 断连性：一个MH可能与系统断开连接。断连状态下，移动主机不能发送或

接收信息，需要交换信息的协议在这种情况下不能正常工作。这种情况下，检查点协议应该提供一个本地恢复机制使MH从它自己的故障中恢复过来。  电池能量有限：MH通常是用电池来供电的，网络传输和磁盘访问是消耗电

量的主要操作。为了使电量的消耗最小化，检查点协议应该减少其添加到应用消息上的信息量，同时应该尽量避免发送额外信息，还要使磁盘访问尽可能少。

 故障种类繁多：MH的故障可以分为两个不同的大类：硬故障和软故障。硬

故障是不可修复的故障，例如MH摔烂了，丢了或者被偷了。软故障不会永久损坏MH，例如电池没电了造成内存内容丢失，或者操作系统崩溃了。  随时的切换：MH随时都可能面临过区切换问题。过区切换可能会影响恢复

过程，这主要由于需要恢复的MH的位置可能不是立即可知的。

 无线网络的弱连接性：BS和MH有不可靠的无线链路连接，可能会很慢。对移动恢复的研究主要集中在对过区切换的处理上，包括过区切换时日志的传输策略、过区切换时发生故障的恢复方法等。这些研究都将日志存放在基站上，恢复时需要从基站读入日志进行恢复。在该系统中，由于在客户端采用短暂日志并且只记录undo日志，那么日志对于空间的需求就少了很多，所以在客户端存放日志，需要恢复时直接使用本地存储的日志进行恢复，同时在基站存放客户端的所有日志和进程映像，以备客户端的短暂日志大小也超出稳定存储器容量的情况，以及在客户端的稳定存储器出现故障时进行恢复。

在过区切换的处理上，如果移动主机的每次过区切换都将存放在上个基站的日志全部传输到当前移动到的基站，那么给平时的操作带来很大负担，因为过区切换是很频繁的动作；而如果每次过区切换都只是保存指向上个基站的指针，那么如果恢复时需要用到基站的日志，则会严重影响恢复速度。如何在两者之间找到一个平衡点是本文的目标。

移动恢复模型中的过区切换示意图如图3.2所示，具体的过区切换日志传输策略在下面的部分进行详述。

华中科技大学硕士学位论文

可能出现日志传输BS1存放MH1的所有日志和进程映像BS2MH1存放本机短暂日志过区切换MH1存放本机短暂日志图3.2 移动恢复模型中的过区切换示意图

使用当前基站以及之前所处基站3的日志进行恢复„„BS1存放MH1的部分日志BS2存放MH1的部分日志2使用当前基站日志进行恢复MH1存放本机短暂日志1使用本地短暂日志进行恢复

图3.3 移动恢复模型中的恢复过程示意图

发生故障需要恢复时，先使用本机的短暂日志进行恢复，如果本机存放的短暂日

华中科技大学硕士学位论文

志信息对于恢复来说不充分，则需要到当前基站取得更多日志信息进行恢复。大多数情况下当前基站的日志信息足够移动主机的恢复，如果当前基站也没有足够的日志信息，那么需要找到该移动主机之前经过的基站，从这些基站读取日志信息进行恢复。移动恢复模型中的恢复过程示意图如图3.3所示，一般的情况下经过第一个步骤可以取得足够的日志来进行恢复，如果第一步不足以取得所有所需的日志，需要进行第二步甚至第三步来取得日志进行恢复。

3.2基于两级日志的嵌入式移动实时恢复算法

所谓两级日志，就是分别在移动主机和基站上存放每个移动主机的日志，而对于中心服务器的日志，则由中心服务器自己按照经典实时恢复的方法进行管理。上一节介绍了实时恢复和移动恢复的基本思想和模型，这一节详细讨论嵌入式移动实时数据库系统中采用的使用短暂undo日志和动态检查点频率的两级日志恢复算法AR-2LL-ELDCF(Algorithms for Recovery based on 2-Level Log Using Ephemeral Log & Dynamic Checkpoint Frequency)。 3.2.1 算法概述

该算法研究的主要内容是嵌入式移动实时数据库系统中客户端的短暂日志策略和过区切换时当前基站与上一基站之间的日志及各个主机进程映像的传输策略。其中客户端的短暂日志策略的研究内容主要包括短暂日志传输到基站的策略、短暂日志的检查点策略以及短暂日志的丢弃策略；过区切换时当前基站和上一基站之间的日志及各个移动主机进程映像传输策略主要研究在什么时机进行日志和进程映像的传输和规整，以便使日志策略在平时的开销小一些，同时在恢复时迅速一些。

使用短暂日志的思想在文献[37]中出现过，但是[37]对每个事务都记录一个短暂undo日志，没有检查点，事务结束后丢弃它的日志。由于嵌入式设备的稳定存储器有限，为每个事务都记录一个日志是不现实的，本文的算法中对短暂日志的使用进行了改进，使用一定的检查点策略，使它可以用于多个事务共享一个日志文件的情

华中科技大学硕士学位论文

况。

进程映像（process image）是每个移动主机在基站的介质备份，用于移动主机出现介质故障时的恢复。由于使用undo日志，在介质崩溃的情况下无法通过日志恢复系统的状态，所以需要进程映像作为介质备份。进程映像一般使用增量备份的方法，主要有同步备份和异步备份两种方式[17]。本文的算法中使用异步方式备份进程映像。

过区切换处理在每个研究移动数据库系统恢复的文献中都会提及，研究的主要是过区切换时日志在基站间的传输策略，目前的研究成果主要有以下几种策略：1、懒惰模式，每次过区切换都只是保存指向上个基站的指针，不传输日志，恢复时根据这些指针依次从上游基站传输日志到当前基站，继而发送日志到移动主机进行恢复；2、悲观模式，每次过区切换都传输日志到当前基站，恢复时只要访问当前基站的日志即可；3、基于距离的模式，当移动主机移动距离达到某个阈值时，就进行日志规整（Log Unification），也就是将上游基站的相应日志都传输到当前基站并重组成一个新的完整日志；4、基于频率的模式，移动主机的过区切换次数达到某个阈值就进行日志规整；5、将所有基站范围分为若干区域（region），每个区域指定一个基站（DBS）收集日志。在本文的算法中，使用一个新的过区切换传输策略，它根据移动主机的短暂日志状态来决定什么时候进行日志规整。为了保证系统恢复的实时性，本文使用和短暂日志密切配合的过区切换时日志传输的策略，即基于移动主机短暂日志饱和度的过区切换日志传输策略。

3.2.2 嵌入式移动实时数据库系统服务器端的日志策略

嵌入式移动实时数据库系统服务器端安装在中心服务器上，和传统的实时数据库系统环境类似，虽然需要通过移动连接管理程序与客户端进行通信，但是服务器端数据库系统本身不涉及嵌入式和移动的环境，因而可以只考虑实时性对数据库系统恢复策略的要求而不必考虑嵌入式和移动环境的影响因素。

当前对实时恢复策略的研究大都对数据库中的数据进行了分类[10,11,15,16]，然后对不同类的数据分别使用不同的日志策略。但是如果对数据分类，那么用户在定义数据的时候就必须显式的指定数据的类别，这给用户带来了很大的额外负担，而且有

华中科技大学硕士学位论文

些数据可能会随着时间的变化而改变其类别。对数据进行分类的方法对于数据量很大的实际系统来说是不现实的，所以在本系统中没有对数据进行分类。

随着固态硬盘（SSD）技术的成熟，固态硬盘也慢慢走向普及，在EMRTDBS服务器端使用固态硬盘存放数据和日志可以加快访问稳定存储器的速度，从而大大提高数据库系统的性能，提高系统的实时性。由于固态硬盘的使用，脏数据和日志的刷新操作不再是系统的性能瓶颈，为了进一步满足实时性要求，数据库服务器端采用Steal/Force策略，即脏数据在事务提交前就可刷新到硬盘，事务提交后该事务的更新必须马上刷新到硬盘，这样数据的更新可以尽快地体现在系统中，同时只需要记录undo日志，相比redo/undo日志来说可以节省一部分硬盘空间。

为了方便叙述，本文将数据更新对应的undo日志表示为来表示，其中T是执行该更新语句的事务编号，D表示被更新的数据，bv是数据的前映像值。undo日志必须遵循如下两条规则[40]：

U1: 如果事务T更新了数据库元素D，那么日志记录必须在D的

新值刷新到硬盘之前进行刷新操作，即要符合WAL协议。

U2: 如果事务提交，那么Commit日志记录必须在该事务的所有更新已写到磁

盘后马上刷新到磁盘，即Force策略。

数据库系统服务器端的并发量很大，所以应采用元组作为封锁粒度。一般的undo日志策略要求commit之前将该事务的所有更新刷新到磁盘，然后再写commit日志并刷新到磁盘。但是由于事务的并发性，缓冲区的某个页可能被两个事务T1和T2都更新过，T1提交前，应该刷新该页，那么即使T2还没有要提交，它的更新也要被刷新到稳定存储器。同时，由于系统的缓冲区有限，当缓冲区容不下更新数据时，要将一部分脏数据先刷新到硬盘，即使对应的事务还没有要提交。这也是为什么要采用Steal策略的原因。

对于每个事务来说，日志记录及刷新的详细算法如下： StealUndoLog (T) {

WRITE ;

华中科技大学硕士学位论文

}

其中WRITE表示在缓冲区中对日志的写操作，FLUSH表示将缓冲区中的内容刷新到稳定存储器中。设该事务有n的更新操作，那么正常情况下为该事务一共需要记录n+2条日志记录（n个更新操作的日志记录、日志记录和日志记录），刷新日志的操作在最坏情况下需要在每条日志记录都后进行一次，即n+2次；对于数据页的刷新在最坏情况下需要n次。所以对于一个有n个更新操作的事务，其日志的时间复杂度在最坏情况下是O(n)。

需要注意的是，这个算法表示的是某个事务的日志记录和刷新过程，不同的事务可能同时在运行，所以对于某个事务来说，它的脏数据页和日志页可能更早地刷新到稳定存储器中，不过这和Steal策略不冲突，最后可以将数据库系统恢复到某个一致状态。

为了减少恢复时需要处理的日志数量，同时考虑到数据库系统服务器端事务并发量很大的特点，本文采用模糊检查点（fuzzy checkpoint）策略，这样在检查点期间允

for every operation in T { }

FLUSH log; FLUSH dirty pages; WRITE ; FLUSH log;

do the operation in buffer pages; WRITE ;

if(page buffer is full || log buffer is full) { }

FLUSH log; FLUSH dirty pages;

华中科技大学硕士学位论文

许新的事务开始运行，可以保证实时性。 3.2.3 移动客户端日志的维护

移动客户端使用短暂undo日志，即在日志段所对应的事务已经提交或终止、日志不再为一般情况的恢复（即稳定存储器损坏之外的故障恢复）所需要的时候，将相应的日志段丢弃，这样可以在移动客户端有限的稳定存储器中只保存尽量少的必要日志，只有当移动主机无法容纳短暂undo日志的时候才将其放在当前基站进行存储，在恢复时可以尽量使用本机日志进行恢复，减少恢复时由于网络通信带来的延迟。同时，将每个移动客户端的所有日志在基站进行存储，可以当做审计时的评判参考。移动客户端和基站端的两级日志保证在移动主机出现故障时可以尽快地完成恢复。

对使用短暂日志进行实时恢复的研究文献中一般都使用面向事务的日志，为每个事务都单独记录日志，这样不用记录检查点，而且事务一结束就可以将它对应的日志丢弃，这种方法比较简单，但是开销比较大。EMRTDBS使用的短暂日志不是面向事务的，而是所有事务共用一个短暂日志，使用模糊检查点策略，将不需要的日志传输到基站，进而丢弃。

虽然使用了短暂日志，但是如果某个事务持续时间过长导致日志长度超过移动主机的稳定存储器容量，也需要将日志传输到基站进行存储，这种情况下恢复时需要从基站读取日志进行恢复。

移动客户端的事务并发量相比数据库系统服务器端要小得多，但是为了保证其实时性，选择使用模糊检查点策略，这样即使在一个长事务的运行过程中执行检查点，也不会出现因为这个长事务没有结束而造成其他事务无法开始的状况。

为了叙述方便，本文引入两个概念，过期短暂日志和有效短暂日志：

定义3.1 过期短暂日志（Overdue Ehpemeral Log）：经过检查点阶段后在移动主机端丢弃的那部分日志，即一个模糊检查点完成后其日志文件里之前的部分。

定义3.2 有效短暂日志（In-Use Ehpermeral Log）：经过检查点阶段后在移动主

华中科技大学硕士学位论文

机端保留的那部分日志和之后新写入的日志，即一个模糊检查点完成后其日志文件里之后的部分直到下个检查点完成前新写入的日志。

移动客户端的短暂undo日志必须遵循如下规则：

规则1: 将脏数据页刷新到稳定存储器之前，必须先将对应的日志记录刷新到稳

定存储器中，即要符合日志先写协议（WAL）；

规则2: 如果事务提交，那么Commit日志记录必须在该事务的所有更新已写到

稳定存储器后马上刷新到稳定存储器，即Force策略。

规则3: 当数据缓冲区的大小已经容不下新的脏数据时，就将一部分未提交的脏

数据写入稳定存储器，即Steal策略。

规则4: 在执行了一个完整的模糊检查点过程之后，将过期短暂日志传输到基站

进行存储，在移动主机本地删除这部分日志；同时将该主机的增量进程映像备份到当前基站。

规则5: 如果日志缓冲区的大小已经容不下新的日志，将当前的短暂日志（有效

短暂日志）传输到基站进行存储，移动主机的缓冲区清空，接受新的日志。

为了区分出移动主机传输到基站的日志是过期短暂日志（规则4）还是有效短暂日志（规则5），需要设置一个标记，确认移动主机传输到基站的日志类别。

嵌入式设备的稳定存储器的容量有限，而日志会占用很多的稳定存储器空间。为了保证嵌入式设备的正常运行，要为日志文件的大小设置一个上限Vlog_max，设移动主机端的日志缓冲区大小为Vlog_buffer。由于无线网络的低速率、不稳定性特点，如果在规则5中等待短暂日志文件的大小已经达到Vlog_max无法再容纳新的日志之后再将当前短暂日志传输到基站，可能会出现网络不通，日志无法传输，因而无法写新日志，也就无法继续执行事务的情况。所以要在短暂日志文件占满Vlog_max大小的空间之前就开始将日志传输到基站，这里本文设置一个阈值，规定当移动主机的短暂日志文件大小达到Vlog_max-Vlog_buffer后，就开始将移动基站的短暂日志开始向基站传输，这样就不会出现日志缓冲区的日志大小加上短暂日志文件的大小超过Vlog_max的情况，可以防止出现由于日志文件已满而无法执行事务的情况。

华中科技大学硕士学位论文

同时日志记录过程中还有检查点的动作，前面的规则没有具体体现检查点的动作。检查点是在所有并发的事务记录日志的过程中定期执行的，检查点结束后要将过期短暂日志传输到基站，然后在移动主机端丢弃这部分日志，同时将移动主机的进程映像增量备份到基站。所以在如下两种情况下要将日志传输到基站：1)移动主机的日志文件大小达到阈值；2)检查点完成后将部分日志传输到基站。下面详细介绍移动主机使用的检查点策略。

移动主机端使用模糊检查点策略，以提高实时性。模糊检查点的步骤包括： 1. 写入日志记录，并将日志刷新到稳定存储器。

其中T1,„,Tm是所有正在运行的事务，即活跃事务。

2. 等待T1,„,Tm中的每一个提交或终止，但期间允许其他事务开始。 3. 当T1,„,Tm都完成（提交或夭折）后，在日志中写入并将

日志刷新到稳定存储器。

4. 将日志记录之前的日志传输到当前基站，并在

本地丢弃这部分日志；同时将该主机的增量进程映像备份到当前基站。如果能尽可能地使移动主机可以存放下所有的有效短暂日志，那么在恢复时就不需要从基站取日志，可以加快恢复速度。决定有效短暂日志长度的一个重要因素是检查点的频率，一般情况下检查点都是以某个固定的时间间隔来周期性地执行，如果检查点执行的频率过高会增加一般运行时的负载，而频率过低的话又会使有效短暂日志过长。所以本文采用动态的检查点频率，以使短暂日志尽量可以在本地完全存放。设检查点执行间隔时间为TCKP，设置检查点计数器CCKP记录自从上次执行规则5对应动作以来所经历的检查点的个数，设置定时器TRCKP。若一个检查点过程结束后CCKP增加为3，则将TCKP置为原来的1.1倍，并将CCKP置零；当遇到需要执行规则5对应的动作时，将TCKP置为原来的一半，并且将CCKP置0；每个检查点完成后，TRCKP清零；因为太过频繁的检查点会严重影响系统的性能，所以设置检查点时间间隔阈值TCKPmin，如果TCKP低于TCKPmin则不再减小。

移动主机的检查点策略如算法1所示。 MH_CKP(T1,„,Tm )

华中科技大学硕士学位论文

{

}

算法1 移动主机的检查点算法

WRITE ； wait for T1,„,Tm to Commit or Abort； WRITE ； FLUSH log；

TRANSFER the Overdue Ehpemeral Log to BS; DISCARD the Overdue Ehpemeral Log in MH; BACKUP incremental process image to BS; CCKP++； if（CCKP==3） { }

TCKP= TCKP*1.1； CCKP=0；

设算法1中的这m个未提交事务中每个事务平均还有n个操作，那么m个事务一共还有m*n个操作，要记录m*(n+1)个日志记录；而TRANSFER操作和DISCARD操作是以日志块为单位进行的，不是以单条记录为单位，其执行时间是常数。故该算法的时间复杂度是O(m*n)，其中m是未提交的事务个数，n是每个未提交事务的平均操作个数。

对于移动主机的每个事务来说，日志记录、刷新以及向基站传输的详细过程如算法2所示。

MH_TranLog (T) {

WRITE ;

华中科技大学硕士学位论文

for every operation in T { }

FLUSH log; FLUSH dirty pages;

if(size of log file >= Vlog_max-Vlog_buffer) {

TRANSFER the In-Use Ehpemeral Log to BS; if（TCKP /2>= TCKPmin）

TCKP= TCKP /2;

do the operation in buffer pages; WRITE ;

if(page buffer is full || log buffer is full) { }

FLUSH log; FLUSH dirty pages;

if(size of log file >= Vlog_max-Vlog_buffer) { }

TRANSFER the In-Use Ehpemeral Log to BS; if（TCKP /2>= TCKPmin）

TCKP= TCKP /2;

else

TCKP = TCKPmin;

else

TCKP = TCKPmin;

华中科技大学硕士学位论文

}

算法2 数据库系统客户端每个事务的日志记录算法

}

WRITE ; FLUSH log;

if(size of log file >= Vlog_max-Vlog_buffer) { }

TRANSFER the In-Use Ehpemeral Log to BS; if（TCKP /2>= TCKPmin）

TCKP= TCKP /2;

else

TCKP = TCKPmin;

其中WRITE和FLUSH所代表的操作已经在前面讲过，TRANSFER表示将短暂日志文件传输到当前基站中。设该事务有n个操作，则需要记录n+2个日志记录，最多需要进行n+2次日志刷新操作和n次数据页的刷新操作；在极端情况下，TRANSFER操作需要进行n+2次，故最坏情况下该算法的时间复杂度是O(n)。

需要注意的是，移动主机的数据库系统客户端也有事务并发，这个算法表示的是某个事务的日志记录和刷新过程，不同的事务可能同时在运行。

移动主机的日志记录整体算法如算法3所示。 MH_Log( ) {

while(1) {

for every Ti in Active_Trans_Quee {

华中科技大学硕士学位论文

}

算法3 移动主机日志记录整体算法

}

do MH_TranLog(Ti) parallelly; if(TRCKP>= TCKP) { }

MH_CKP(Active_Trans_Quee); TRCKP=0;

其中，Active_Trans_Quee表示当前活动事务队列。设一共有m个事务执行，平均每个事务的执行时间是t，每个事务有n个操作，检查点间隔时间TRCKP的平均值

mt是tr，则该算法要为这m个事务记录m(n2)个日志记录，最多要执行个检trmt2个日志记录。查点，最多一共要记录m(n2)tr3.2.4 基站日志的维护和过区切换处理

基站保存着它所覆盖范围内所有移动主机的过期短暂日志（即一般故障下恢复时不再需要的日志），也可能保存着某些移动主机因为没有足够空间存放而传输到基站来存放的有效短暂日志（即移动主机故障后恢复时一定要用到的短暂日志）。

为了保证移动主机恢复需要使用基站存放的日志时可以尽快得到需要的日志，基站为每个移动主机都保存一个日志文件，当移动主机传输新的日志到基站时，将这些日志写到该移动主机在基站存放的对应日志文件的尾部。同时，要为存放在基站的每个日志文件设置一个偏移标识，这个偏移标识之前的日志都是过期日志，仅用于移动主机的稳定存储器出现故障的情况下的恢复；该偏移标识之后的日志是移动

华中科技大学硕士学位论文

主机的有效短暂日志，移动主机的任何恢复都需要用到这部分日志。

当移动主机从一个基站BS1的覆盖区域移动到另一个基站BS2的覆盖区域时发生过区切换。将日志从之前各个基站传输到当前基站并存放在一个日志文件里的过程称为日志规整。过区切换时日志的传输及规整策略是很值得研究的问题，因为它直接关系到移动主机发生故障以后从基站取得所需日志的速度。

由于本文在移动主机端使用短暂日志，那么在移动主机可以完全存储它的短暂日志的情况下，恢复时不需要从基站取得日志，仅使用本地的短暂日志即可恢复。这种情况下，即使使用前面所提到的懒惰模式也不会增加恢复时的时间，反而可以降低平时正常运行时的负载。但是因为移动主机端可能会出现事务持续过久导致检查点过程很长，从而造成短暂日志过大无法在本地完全存储需要放在基站进行存储的情况，这种情况下如果还使用懒惰模式则恢复的时候可能需要从之前的基站取出日志进行恢复，会增加恢复所需要的时间。

EMRTDBS中使用的过区切换日志传输算法和移动主机的短暂日志策略密切相关。当移动主机的短暂日志文件大小没有达到Vlog_max-Vlog_buffer之前，其短暂日志不会传输到基站，出现一般故障后的恢复也只需要用到本地的短暂日志，不需要用到基站的日志。但是当移动主机的短暂日志文件大小超过Vlog_max-Vlog_buffer之后，需要将短暂日志传输到基站进行存储，这时如果移动主机出现故障则需要基站的日志用来恢复，所以在算法中，当移动主机向基站传输有效短暂日志完成之后，当前基站就对该移动主机的日志进行规整(Unification)，即从该移动主机之前经过的各基站取得对应的日志文件，并在当前基站形成一个完整的日志文件，之前各基站的这些日志文件就可以删除。

使用这个思想，如果移动主机的短暂日志文件大小很少达到Vlog_max-Vlog_buffer，那么很多时间都只保存指向前一基站的指针，就相当于懒惰模式，会有两种情况使恢复时间很长：1)当移动主机出现稳定存储器崩溃的故障后，需要通过很长的链路从之前经过的基站取得进程镜像和日志进行恢复，如图3.4所示；2)移动主机执行一次规则4的动作后，进行了多次过区切换后崩溃，需要从之前经过的基站取得有效短暂日志，如图3.5所示。因此本文设定一个阈值Cunification，当移动主机的过区切换次

华中科技大学硕士学位论文

数达到这个阈值就进行日志和进程镜像的规整，以避免出现上面所说的情况。阈值Cunification的大小可以根据移动主机出现稳定存储器崩溃的频率来确定。

BS1存放MH1的部分短暂日志和进程映像BSn存放MH1的部分短暂日志和进程映像MH1存放本机短暂日志„„„MH1存放本机短暂日志过区切换过区切换发生介质故障,需要使用之前经过的基站BS1...BSn的日志和进程镜像进行恢复图3.4 移动主机发生介质故障时的恢复示意图

BS1存放MH1的部分短暂日志和进程映像BSn存放MH1的部分短暂日志和进程映像MH1存放本机短暂日志„„„MH1存放本机短暂日志过区切换移动主机执行规则4的动作，将有效短暂日志传输到基站BS1过区切换移动主机发生一般故障，需要从BS1取得有效短暂日志进行恢复图3.5 移动主机发生一般故障的一种情况

华中科技大学硕士学位论文

如果移动主机在向基站传输日志的时候发生过区切换，也不会出现问题，在日志规整时将前一基站的日志传输到当前基站进行规整即可，因为日志的LSN是唯一的，不会出现同一个日志记录出现多次的情况，但要保证日志不会丢失，这不是本文研究的重点。

综上，基站日志维护和过区切换日志传输算法规则如下：

1. 基站为其覆盖范围内的每个移动主机维护一个日志文件，并设置偏移标识，

这个标识前是过期短暂日志，标识后是有效短暂日志。

2. 当基站收到其覆盖范围内的移动主机发送过来的过期短暂日志时，将这部分

日志添加到该主机的日志文件末尾，并将偏移标识放在文件末尾。 3. 当基站收到其覆盖范围内的移动主机发送过来的有效短暂日志时，将这部分

日志添加到该主机的日志文件末尾，偏移标识位置保持不变，然后对这个移动主机的日志和进程映像进行规整，并将该移动主机的过区切换计数器置零。

4. 对于刚进入该基站覆盖范围的移动主机，若它的过区切换次数已达到阈值定

义的那个值，对该移动主机的日志和进程映像进行规整，并将该移动主机的过区切换计数器置零；否则，只维护一个指向该移动主机前一个基站的指针即可。

3.2.5 提交处理

设Ti是某移动主机上的一个事务，当Ti开始执行时，将其加入活动事务列表；当Ti结束执行预提交时要执行以下步骤：

 刷新缓冲中的日志到稳定存储器中。  刷新Ti更新过的脏页数据到稳定存储器中。  在日志中写入记录并刷新。  释放Ti所持有的锁。

事务Ti的编号增加到已提交队列时就算完全提交了，然后系统执行如下的提交后处理步骤：

华中科技大学硕士学位论文

 将Ti从活动事务队列中移除。

 查看Ti是不是检查点过程中最后提交的事务，若是，则完成检查点，将过期

日志传输到基站，并在本地丢弃过期日志。

3.2.6恢复处理

系统中的恢复处理包括中心服务器的恢复处理、基站的恢复处理和移动主机的恢复处理，这里主要研究移动主机的恢复处理。

移动主机的故障主要分为如下三类： 1. 移动主机的稳定存储器失效；

2. 移动主机掉电或系统崩溃，需要重新启动； 3. 移动主机损坏，无法使用。

前两类故障都可以使用日志和进程镜像进行恢复使数据库系统还原到某个一致的状态，称为可恢复故障；第三类则是不可恢复故障，本文不做研究。

对于第一类故障，需要同时使用进程镜像进行恢复，这需要从基站取得进程映像，这属于容错的范畴，不进行深入讨论。

对于第二类故障，只需要使用有效短暂日志进行恢复，对于有效短暂日志的存储位置有如下三种情况：

情况1. 移动主机存储所有的有效短暂日志。这也是最理想的情况，只需要使用

本地的日志就可以完成恢复，不需要通过无线网络从基站取得日志，大大缩短恢复时间。

情况2. 部分或全部有效短暂日志存储在当前基站。这种状态出现在移动主机传

输有效短暂日志到基站并且在未移动出这个基站的覆盖范围就发生故障的情况下，恢复时需要从当前基站取得日志，恢复时间比情况1长一些。

情况3. 部分或全部有效短暂日志存储在移动主机之前经过的某个基站。这种状

态出现在移动主机传输有效短暂日志到基站并且发生一次或多次过区切换后发生故障的情况下，恢复时需要从前面某个基站取得日志，恢复时间在这3种情况中最长。需要注意的是，有效短暂日志不可能存放在该

华中科技大学硕士学位论文

基站的之前的第Cunification个基站中，因为经过Cunification次过区切换后一定要进行日志的规整动作。

上面三种情况取得恢复所需要的日志后，从尾部开始扫描日志。在扫描过程中，记住所有的和记录的事务Ti，放入已提交队列中。同时在其扫描过程中，如果遇到日志记录，则：

1) 如果Ti的Commit或Abort记录已被扫描到，Ti在已提交队列中，则什

么也不做，因为Ti已经提交，不需要撤销；或者Ti已经终止，其对数据库的影响已经消除，不需要再次undo。

2) 否则，Ti是一个未完成的事务，需要将数据库中Dj的值改为vb，撤销

完Ti的所有操作后，需要为未完成的事务Ti写入一个日志记录，然后刷新日志。然后，数据库系统中新的事务可以开始执行。

如果遇到记录，则查找Ti是否在已提交队列中，如果在，则不执行任何动作，否则在日志中写入一条记录。

3.3本章小结

本章先根据EMRTDBMS系统的需求提出了一种嵌入式移动实时环境下的实时、移动恢复模型及其处理过程，之后基于这一模型选用了两级日志存储的框架，进行日志恢复策略和过区切换策略分析，提出了动态检查点频率的思想，给出使用短暂日志和动态检查点频率的两级日志恢复算法AR-2LL-ELDCF(Algorithms for Recovery based on 2-Level Log Using Ephemeral Log & Dynamic Checkpoint Frequency)，并分别从日志的记录、基站日志的维护、过区切换的处理以及恢复处理各个环节详细描述了算法的思想和过程。

华中科技大学硕士学位论文

4 系统实现与性能评价

4.1原型系统设计与实现

由于课题目前尚处于系统的开发阶段，系统的部分基本功能（数据的定义和操纵等）已经实现，但是并不完善，还没有实现事务管理器，因而暂时没有一个完整的嵌入式移动实时数据库系统环境来支持实际应用。所以，为了模拟实现上一章的日志恢复算法，本文在linux环境下使用C语言作为开发工具，使用gcc和makefile来进行编译，使用KDbg进行程序的调试。在系统已有功能的基础上，模拟实现移动主机端的短暂日志，实现了一个基本能反映短暂日志记录和恢复全过程的原型系统，为日后实现完整的EMRTDBMS提供技术参考。 4.1.1 模块设计

对应3.2节中的两级日志恢复算法，这一原型系统主要应包含如下几个模块：

（1）数据操纵模块，这是当前系统已有的功能，包括根据SQL数据操纵语句生

成语法树、根据语法树产生查询树和根据查询树进行数据操纵；

（2）数据刷新模块，当前系统没有实现脏数据页刷新的控制，在该原型系统中，

实现了一个简单的脏数据刷新模块；

（3）随机事务产生模块，为模拟移动主机端的事务并发运行，采用一个函数在

移动主机端批量生成事务；

（4）事务执行模块，每个事务都是一组整体运行的操作集合，调用数据操纵模

块来执行事务中的每个语句；

（5）日志记录模块，在事务执行过程中，为事务的每个操作语句记录短暂undo

日志；

（6）网络传输模块，模拟实现移动客户端和基站之间的短暂日志传输，由于不

存在真实的无线网络支持，只能以程序设置延迟的方式进行仿真；

华中科技大学硕士学位论文

（7）基站日志管理模块，由于不存在无线网络支持，基站的日志管理通过本地

其他文件存储日志来模拟。

（8）恢复模块，在系统发生故障重启后根据短暂日志信息进行恢复。

图4.1反映了系统运行过程中以上各模块的交互。

移动主机端基站端事务执行数据刷新模块恢复模块事务实例数据操纵日志记录基站日志管理随机事务产生无线网络传输图4-1 日志恢复原型系统结构

4.1.2 主要数据结构

系统中最重要的数据结构是日志的结构，因为整个恢复系统的基础就是日志，恢复模块需要根据移动主机本地的和基站的（如果需要的话）日志来进行恢复。

在该原型系统中，在内存中预留一个页作为日志缓冲区，移动主机端的日志文件大小上限由程序中的一个宏来指定，基站端日志文件的大小没有上限。在内存的一个页面内维护日志信息，需要刷新时就刷新到本地日志文件中，若本地日志文件的大小达到了一个阈值或刚执行完一个模糊检查点操作，就将本地日志文件的日志输出到另一个文件以模拟将其传输到基站。

在本系统的设计中，日志文件保存了所有需要的信息，恢复时只需要访问移动主机本地日志文件和基站日志文件即可。

华中科技大学硕士学位论文

1、日志的结构

一个Update操作对应的日志记录格式如图4.2所示。

LSN(4字节) ：日志编号 LogType(1字节)：日志类型，此处为（LOGTYPE_OPERATION） TranID(4字节) ：事务ID LogSize(4字节)：本日志的大小 PreSize(4字节)：前一个日志的大小（为了便于undo时的后向扫描） OpType(1字节) ：操作类型 TableID(2字节)：表的ID RowID(4字节) ：对应元组的ID Old ：当OpType是OPTYPE_UPDATE时才有，表示修改前的旧值图4.2 Update操作对应的日志记录的格式

其中各属性的具体含义如下：

 LSN – 日志记录的顺序编号，其值是日志记录在日志文件中的位置偏移。

 LogType – 日志记录的类型，可以是如下这些宏所定义的值。其中有两个检

查点类型，分别对应模糊检查点的开始和结束。 #define LOGTYPE_BEGIN 1 #define LOGTYPE_COMMIT 2 #define LOGTYPE_ABORT 3 #define LOGTYPE_CHECKPOINT1 4 #define LOGTYPE_CHECKPOINT2 5 #define LOGTYPE_OPERATION 6

 TranID – 日志对应的事务编号，若是检查点则没有事务编号。  LogSize – 当前日志记录的大小。

 PreSize – 前一条日志记录的大小，用于反向扫描时根据从后一条日志记录定

位到前一条日志记录。

 OPType – 操作的类型，只有当LogType是LOGTYPE_OPERATION时才有

这项，OPType可以是如下所示的宏所定义的值。由于该系统现在还没有实现删除操作，该原型系统在随机事务生成模块中只使用了update操作，日志记录中也只有update日志记录、各种事务控制日志记录和检查点日志记录。

#define OPTYPE_UPDATE 11

#define OPTYPE_INSERT 12

华中科技大学硕士学位论文

#define OPTYPE_DELETE 13

 Ob – 日志记录对应更新的数据项的标识符，只有当LogType是

LOGTYPE_OPERATION时才有这项。在本系统中，Ob由对应的表ID和元组ID来标识。

 Old – 日志记录中对应数据项的前映像，即旧值，只有当OPType是

OPTYPE_UPDATE时才有这项。 2、日志文件的结构

基站日志文件内容的存储示意图如图4.3所示。

InitLsn：4字节日志记录1 日志记录2 LastLSN：4字节日志记录3 LastLogSize：4字节 „„ „„ „„ „„ „„ 图4.3 基站日志文件内容的存储示意图

移动主机日志文件内容的存储示意图如图4.4所示。

InitLsn：4字节日志记录1 LastLSN：4字节日志记录2 LastLogSize：4字节 „„ PrevLogSize：4字节 „„ 日志记录3 „„ „„ „„ 图4.4 移动主机日志文件内容的存储示意图

移动主机日志缓冲中内容的存储示意图和图4.4一样，不同的是一个是在内存中，一个是在文件中。

其中重要属性如下（这些属性在本文中称为日志文件或缓冲的“头部”信息）：  InitLsn – 表示对应的日志文件或日志缓冲中第一条日志记录的LSN，对于基

站日志文件，如果不考虑将日志备份到磁带的操作，其InitLsn应该是0。LSN是每个日志记录唯一的顺序编号，其值是该日志记录在基站日志文件中的位置偏移，即使日志记录还没有传送到基站，也应按照对应基站日志文件的位

华中科技大学硕士学位论文

置偏移来计算它的LSN。

 LastLSN – 表示对应的日志文件或日志缓冲中最后一条日志记录的LSN。  LastLogSize – 表示对应的日志文件或日志缓冲中最后一条日志记录的大小，

如果该域值为0，则表示对应的日志文件或缓冲区中还没有日志记录。  PrevLogSize – 该项只存在于移动主机的日志文件和日志缓冲中，用于在特

定条件下计算当然日志记录的PreSize项。当移动主机日志缓冲中没有日志记录而移动主机日志文件中有日志记录时，新生成的日志记录必须参考日志缓冲中的PreLogSize来确定该日志记录的PreSize；如果日志缓冲中已有日志记录，则新日志记录的，则可根据日志缓冲中的LastLogSize来确定该日志记录的PreSize。

4.1.3 系统实现的关键技术

该系统中的关键技术是一般运行时对日志文件的记录、维护，检查点的运行，以及恢复时对日志文件进行从后到前的扫描并恢复数据库系统到一致状态。同时，由于系统目前没有实现事务管理器和脏数据页的刷新，随机事务的生成和脏数据页刷新也是比较关键的问题。 1、随机事务的生成

系统中的事务都是模拟转帐操作的事务，即从一个帐户A转一笔钱到另一个帐户B，根据用户输入的数字决定事务的数目。每个事务的转入帐户和转出帐户都是随机的（转入帐户和转出帐户不能是同一个），转帐的金额也是随机的，所有的事务是并发执行的，实现一个简单的锁，保证某个事务没有提交之前，其他事务不能访问该事务正在访问的帐户。同时，系统在任一时刻都以一定的概率发生故障而崩溃，以便恢复系统的演示。

为了生成随机事务，使用C语言中的随机函数rand( )生成随机数，根据生成的随机数来确定当前是开始一个新事务还是继续执行未完成的其他事务。事务开始的顺序是一定的，事务编号从1到n，但是事务结束的时间是没有顺序的。随机事务中的转出和转入帐号，以及转账金额也都是根据随机数函数来生成的。

华中科技大学硕士学位论文

2、脏数据页的刷新

原有系统中没有实现脏数据页刷新操作，而是将内存中的若干连续页面映射到一个文件，由操作系统来负责刷新，不能控制刷新的时机。在本原型系统中，实现了简单的刷新操作，由于表数据很少，将这些数据在若干连续页面来维护，需要刷新时，将这些页面以二进制格式全部刷新到对应文件中。缓冲区管理和数据刷新不是本文研究的重点，所以只实现了一个很简单的刷新操作。 3、日志文件的记录和维护

该原型系统中在基站日志文件、移动主机日志文件和移动主机日志缓冲区中都有日志记录，三者的日志记录在一般情况下是不重合的，即某个日志记录在特定时间只能出现在这三个地方的某一处。

由于基站日志文件、移动主机日志文件和日志缓冲区中头部信息格式各有不同，该原型系统中定义如下的宏来方便对日志文件和日志缓冲的访问，同时便于以后要修改这些头部信息时的程序维护：

#define LOGBSHEADERSIZE

#define LOGBSPOS_INITLSN #define LOGBSPOS_LASTLSN #define LOGBSPOS_LASTLOGSIZE

#define LOGMHHEADERSIZE #define LOGMHPOS_INITLSN #define LOGMHPOS_LASTLSN #define LOGMHPOS_LASTLOGSIZE #define LOGMHPOS_PREVLOGSIZE

#define LOGPAGEHEADERSIZE #define LOGPAGEPOS_INITLSN #define LOGPAGEPOS_LASTLSN #define LOGPAGEPOS_LASTLOGSIZE #define LOGPAGEPOS_PREVLOGSIZE

(U32SIZE*3) 0

U32SIZE (U32SIZE*2) (U32SIZE*4) 0

U32SIZE (U32SIZE*2) (U32SIZE*3) (U32SIZE*4) 0

U32SIZE (U32SIZE*2) (U32SIZE*3)

同时，为了方便对日志记录中每个属性的读写以及以后程序的维护，定义如下这些宏：

#define LOGHEADERSIZE (U32SIZE*5+U8SIZE*2+U16SIZE) #define LOGPOS_LSN 0

华中科技大学硕士学位论文

#define LOGPOS_LOGTYPE #define LOGPOS_LOGSIZE #define LOGPOS_PRESIZE #define LOGPOS_TRANID #define LOGPOS_OPTYPE #define LOGPOS_TABLEID #define LOGPOS_ROWID

U32SIZE

(U32SIZE+U8SIZE) (U32SIZE*2+U8SIZE) (U32SIZE*3+U8SIZE) (U32SIZE*4+U8SIZE) (U32SIZE*4+U8SIZE*2)

(U32SIZE*4+U8SIZE*2+U16SIZE)

一条日志记录产生之后，最先存放在日志缓冲区中，然后要刷新到移动主机日志文件中，最后要传输到基站的日志文件中，关键问题是日志刷新和传输中的控制。

日志缓冲区在如下4种情况下需要刷新：

1. 由于数据缓冲区满了，需要刷新数据的时候，要先刷新日志； 2. 某个事务提交了，要刷新日志缓冲区；

3. 日志缓冲区满了，要进行刷新以接收新的日志记录； 4. 模糊检查点执行完毕，要刷新日志缓冲区。

刷新日志缓冲区时，需要将日志缓冲中的各日志记录顺次写到移动主机日志文件最后一条日志的后面，并修改移动主机日志文件头部各域的信息和日志缓冲头部各域的信息。

移动主机的日志文件在如下2种情况下需要传送到基站进行存储：

1. 移动主机日志文件的容量超过了阈值，需要将移动主机日志文件传输到基站

日志文件。这个阈值的大小设置为移动主机日志文件容量上限与日志缓冲区大小的差，这样可以保证每次刷新操作都不会出现移动主机日志文件无法存储下日志缓冲区的日志记录的情况。

2. 进行完一个完整的模糊检查点后，需要将之前的日志记

录传输到基站。但是如果在后因为移动主机日志文件的容量超过了阈值而进行过了日志传输的操作，则检查点完成后不再进行日志传输。

4、模糊检查点的实现

检查点需要在系统的运行过程中定期的进行，以保证在系统需要恢复的时候不必

处理太多的日志。

华中科技大学硕士学位论文

使用标准C语言难以实现定期执行检查点的功能，但是可以使用Linux环境下的信号来实现。使用alarm( )函数设置下个检查点开始的时间，那么当到达这个预定时间的时候，内核会产生一个SIGALRM信号，使用signal( )函数设置捕获SIGALRM信号的函数，在这个函数中进行开始模糊检查点的操作。关键代码如下所示：

void SetCheckPointTimer()

{

if(signal(SIGALRM,BeginFuzzyCheckPoint)==SIG_ERR) {

printf(\"Signal Error!\\n\"); exit(-1); }

alarm(checkpointInterval); }

void BeginFuzzyCheckPoint(int signo) {

if(aActiveTrans[0]==0) {

printf(\"There is no uncommited transactions!\\n\"); WriteCheckPointLog(LOGTYPE_CHECKPOINT1); EndFuzzyCheckPoint(); return; }

RecordActiveTrans();

WriteCheckPointLog(LOGTYPE_CHECKPOINT1); SetCheckPointFlag(); }

void EndFuzzyCheckPoint() {

WriteCheckPointLog(LOGTYPE_CHECKPOINT2); TransferLogToBS(LOG_OVERDUE); ClearCheckPointFlag(); SetCheckPointTimer(); }

其中，BeginFuzzyCheckPoint是开始执行检查点操作的函数，EndFuzzyCheckPoint是结束执行检查点进行收尾工作的函数。检查点的执行流程图如图4.5所示。

华中科技大学硕士学位论文

开始调用SetCheckPointTimer()函数设置检查点执行时间捕获SIGALRM信号，写入日志记录到日志缓冲中Y(Tm,Tm+1,„,Tn)为空？N捕获要写入日志缓冲的日志记录Ti是(Tm,Tm+1,„,Tn)中最后提交的事务？YN写入日志记录到日志缓冲中，将不再需要的日志传输到基站调用SetCheckPointTimer()函数再次设置检查点执行时间

图4.5 检查点的执行流程图

需要注意的是检查点的执行是没有结束的，它存在于程序运行的任何时间，直到程序退出。 5、恢复处理

由于在恢复的同时也要记录日志，如对于未提交事务，当处理到它的

华中科技大学硕士学位论文

日志记录时，要在日志末尾写入一个日志记录。所以在该系统中恢复时逆向扫描日志所用的日志缓冲区是于记录日志的缓冲区的。

恢复过程的流程图如图4.6所示。

开始将最后一条日志记录设为当前处理日志记录当前日志记录是或N当前日志记录是N当前日志记录是NYYY将Ti加入已提交事务列表Ti已提交YN对Update进行UndoTi已提交YN写入日志记录当前日志记录是需要处理的最后一个N将当前处理日志记录移动到前一个Y结束

图4.6 恢复过程的流程图

该恢复过程流程图展示了对于每个需要处理的日志记录如何处理以达到恢复数

据库系统到一致状态的目的，但是这个流程图忽略了如何逆序扫描每一个需要处理的日志记录的细节。逆序扫描日志记录的流程图如图4.7所示。

华中科技大学硕士学位论文

开始计算所需要读取的最大LSNm，该值小于等于MH日志文件的InitLsn？NMH日志文件中从InitLsn到LSNm之间的日志记录小于日志缓冲区大小？Y将MH日志文件中从InitLsn到LSNm的日志文件装入缓冲区，并设置缓冲区头部的信息YNNBS日志文件中从InitLsn到LSNm之间的日志记录小于日志缓冲区大小？Y将BS日志文件中从InitLsn到LSNm的日志文件装入缓冲区，并设置缓冲区头部的信息将MH日志文件中从LSNm往前的，大小为缓冲区容量的日志文件装入缓冲区，并设置缓冲区头部的信息将BS日志文件中从LSNm往前的，大小为缓冲区容量的日志文件装入缓冲区，并设置缓冲区头部的信息根据缓冲区头部信息LastLsn得到要处理的LSNc，定位缓冲区的最后一条日志记录该日志记录是吗？N该日志记录是并且Flag==1吗？N对该日志记录进行相应处理该日志记录的PreSize域是0吗（即已经到了日志最前端)？NYLSNc-PreSize为下一个要处理的日志记录，其值小于缓冲区的InitLsn吗？N定位当前处理日志为LSNc-PreSize对应的日志YFlag置为1YY结束LSNm=LSNc-PreSize

图4.7 逆序扫描日志记录的流程图

华中科技大学硕士学位论文

该流程图不考虑没有日志记录需要处理的情况，即一定有日志记录需要用来进行恢复。在该流程图中，Flag的初始值是0，用来记录是否曾经扫描到日志记录。 4.1.4 系统运行效果

系统在Linux系统中以控制台的方式运行，没有图形界面。系统运行的总体流程如图4.8所示。

开始载入表数据文件，并打印到屏幕上进入恢复模块，查看需要恢复与否？Y进行恢复N进入随机事务生成模块，提示用户输入要执行的事务数目根据用户输入的数目生成随机事务，执行事务，记录日志，需要时将日志传输到基站进行存储，每执行完一个操作，系统以一定的概率模拟崩溃打印模拟崩溃后或正常完成后的数据，并输出提示信息结束

图4.8 系统运行的总体流程

程序运行界面如图4.9到4.12所示。

华中科技大学硕士学位论文

图4.9 程序运行界面(1)

图4.10 程序运行界面(2)

华中科技大学硕士学位论文

图4.11 程序运行界面(3)

图4.12 程序运行界面(4)

华中科技大学硕士学位论文

4.2 算法性能评价

4.2.1 模拟实验参数

影响嵌入式移动实时数据库系统恢复系统性能的主要指标有一般运行时的负载、恢复所需时间、日志所占空间等。由于没有移动环境，所以关于移动环境的无线传输等动作都是使用延时来模拟。

模拟实验运行在一台Pentium4 1.8G CPU、512M内存的PC主机，原型系统的实验参数如表4.1所示。

表4.1 模拟实验参数选择

移动主机端短暂日志容量上限MHLogFileSize 移动主机端日志缓冲大小BufferSize 一页日志上行所需时间Tup 一页日志从当前BS下行所需时间Tdown 一页日志从非当前BS下行所需时间Tdown 对某移动主机的日志规整所需时间Tunification 事务到达速率ST 单个事务平均日志大小SizeTL 执行每条语句后的崩溃概率执行每条语句后发生过区切换的概率检查点周期TCKP初始值过区切换阈值Cunification ’20KB 4KB 4s 1s 2s 1s 20~60个/分钟 0.4KB 10% 10% 30s 3

本系统模拟的是使用GPRS无线网络的情况，其实际上行速率约为10kpbs，实际下行速率为40kpbs左右，即上传和下载的速度约为1KB/S和4KB/S，所以一页（4KB）日志上行和下行的时间分别为4s和1s。事务到达速率ST在不同的使用环境中会有不同的数据，本系统为了方便演示选取为20~60个/分钟。在真实的系统中会

华中科技大学硕士学位论文

出现有时多个事务一起到来要排队等待处理、有时没有事务到来系统处于空闲状态的情况，在该模拟系统中，随机事务产生模块事务操作是顺序的，虽然是并发执行的，但是不会出现多个事务同时到来或系统处于空闲状态的情况。平均日志大小SizeTL也和具体应用相关，本系统中的事务都是简单的转账操作，事务平均日志大小为2KB，在其他的应用中这两个数据可能会有不同的值。检查点周期TCKP初始值则是要根据事务达到速率和单个事务平均日志大小来计算，使有效短暂日至尽可能可以在移动主机本地完全存储。虽然系统运行中会自动调整TCKP的值，但是如果初始情况下就给TCKP设置一个合理的值，会让恢复系统更加高效稳定。TCKP的计算公式是：TCKPMHLogFileSizeBufferSize。但这只是理论上的值，由于检查点要持续一

(ST/60)SizeTL定的时间，可能在这段时间内日志文件容量达到阈值需要传输日志到基站，为了防止这种情况的发生，需要将TCKP的值再设置得小一些。 4.2.2 实验结果分析

由于检查点间隔是根据事务到达速率、移动主机日志文件容量、日志缓冲大小等因素计算得到初始值的，可以保证系统刚开始运行的时候能尽量将所有有效短暂日志都存放在移动主机本地。在事务长度和到达率变化不大的情况下，动态检查点频率也可以使移动主机的本地日志文件容纳的下所有有效短暂日志，从而在恢复时只使用本地日志即可，有较高的实时性。当事务长度和到达率有较大变化时，可能需要将有效短暂日志存放到基站，恢复时需要从基站读取日志数据，恢复会较慢。所以本文得到这样的结论：使用AR-2LL-ELDCF算法对于稳定的缓慢变化的事务到达速率和事务长度来说，可以把所有有效短暂日志存放在本地，恢复有很好的实时性；如果事务到达速率变化较快时，可能造成本地无法存放所有有效短暂日志，恢复时的实时性会受到一些影响。而对移动恢复的研究一般都将日志全部存放在基站，所以使用本文中的方法可以使恢复速度明显提高。

过区切换策略和将有效短暂日志传输到基站的策略一起作用，使发生故障需要从基站取得日志恢复时，基站的日志尽可能在当前基站存放，特殊情况下不在当前基

华中科技大学硕士学位论文

站的也可以通过少于Cunification次的查找上一基站操作找到存放日志的基站，继而取得日志进行恢复。该过区切换策略是懒惰模式和悲观模式的折中，但是由于系统使用两级日志模式，使得基站日志对于恢复速度的影响变小，同时过区切换策略和有效短暂日志传输到基站的策略紧密结合，使得过区切换时日志的规整时机更好，整个系统有较好的综合性能。

根据不同的事务到达速率，比较本文提出的算法和懒惰模式、悲观模式下恢复所需的时间。由于崩溃时刻是随机选择的，崩溃发生时刻和上一个检查点完成时刻的时间间隔直接影响恢复时需要处理的日志记录数，也直接影响恢复所需时间。为了屏蔽随机性，在这个实验中把崩溃时刻控制在检查点完成后日志缓冲区第二次装满之前，那么在懒惰模式和悲观模式下恢复时只需从基站取一页的日志进行恢复。实验结果如图4.13所示。

43.53恢复所需时间(S)2.521.510.50203040事务到达速率(个/分钟)5060懒惰模式悲观模式AR-2LL-ELDCF图4.13 事务达到速率对恢复时间的影响

可见AR-2LL-ELDCF算法在事务到达速率恒定在某个值的时候具有很好的恢复实时性，其检查点时间间隔设置可以保证在本地存储所有有效短暂日志，同时由于

华中科技大学硕士学位论文

检查点频率和事务到达速率相关，恢复时需要处理的日志大小在一定程度上是和事务达到速率无关的，所以恢复时间和事务达到速率关系也不大。而悲观模式和懒惰模式都把日志存放在基站，恢复时需要从基站取得日志，需要较长的时间，懒惰模式更是需要从之前的基站取得日志，恢复所需时间更长。同时，悲观模式和懒惰模式的检查点频率是恒定的，恢复时所需处理日志会随着事务到达速率的增加而增加，恢复时间也跟着增加。如果在该试验中不对崩溃时刻进行控制，那么悲观模式和懒惰模式需要更多的恢复时间，因为它们需要从基站获取不止一页的日志才能完成恢复。

再设事务到达速率以一定的速度增加，比较本文提出的算法和懒惰模式、悲观模式下恢复所需的时间。同样把崩溃时刻控制在某个检查点完成后日志缓冲区第二次装满之前，实验结果如图4.14所示。

43.53事务到达速率初始值为20个/分钟恢复所需时间(S)2.521.510.50051015202530事务到达率变化速率(事务到达速率增量/分钟)懒惰模式悲观模式AR-2LL-ELDCF图4.14 事务到达率变化速率对恢复时间的影响

可见在事务到达速率变化的情况下，AR-2LL-ELDCF算法所需的恢复时间有所增加，这是由于事务到达率的增加致使按照原有检查点间隔会导致本地无法完全存

华中科技大学硕士学位论文

储有效短暂日志的情况，恢复时需要从基站取得日志进行恢复。但是AR-2LL-ELDCF算法的日志规整策略能最大限度地保证恢复所需日志可以在当前基站找到，所以在一般较坏的情况下，AR-2LL-ELDCF算法所需的恢复时间和悲观模式相当，极端情况下才会接近懒惰模式所需的恢复时间。

在一般运行时，移动主机在三种不同的算法下负载相当，主要是记录日志、传输日志到当前基站的负载，有差别的是三种不同的算法下基站的负载情况。基站的负载主要是进行日志规整的负载，由于该负载情况和事务达到速率关系不大，本文就只做定性的分析：悲观模式下基站的负载最重，因为移动主机每次过区切换是相应的基站都要进行对应移动主机的日志规整，加重了基站的负载；懒惰模式下基站的负载最轻，因为它不会进行日志规整，只是保持指向上一基站的指针，但是它的恢复时间是最长的；AR-2LL-ELDCF算法在平时的负载介于懒惰模式和悲观模式之间，同时它的恢复时间在一般情况下平均是最好的，但是对于单次的恢复，AR-2LL-ELDCF算法所需的时间可能很短，也可能比悲观模式长很多，只是平均下来所需恢复时间最短。

4.3 本章小结

为了模拟使用AR-2LL-ELDCF算法进行日志记录和故障后恢复的过程，本章实现了一个原型系统，给出了该系统的主要模块设计及关键数据结构与实现技术，在此系统的基础上，结合国内外研究者对嵌入式移动实时环境的模拟参数，分别从运行时负载、恢复时间等方面进行系统性能测试，实验结果显示了该算法具有相对较好的综合性能。

华中科技大学硕士学位论文

5 总结与展望

5.1 工作总结

嵌入式移动实时由于其在日常生活和军事应用等各方面的巨大应用前景成为当前研究的热点。由于嵌入式设备的低可靠性和移动环境的不稳定性，恢复系统对于整个系统的正常运行尤为重要。本文选择嵌入式移动实时数据库系统移动客户端的恢复策略作为研究重点，在分析研究了国内外研究现状的基础上，提出了基于短暂日志、使用动态检查点频率的两级日志策略。

具体来说，主要包括以下的几个方面：

1) 对嵌入式移动实时数据库系统及其关键技术进行了阐述和分析。

2) 分析嵌入式移动实时恢复技术的要点，从总体上说明选用两级日志策略的原因和优点。

3) 提出了使用短暂日志和动态检查点频率的两级日志恢复算法AR-2LL-ELDCF，将短暂日志分为有效短暂日志和过期短暂日志两部分，通过使用动态调整的检查点间隔时间来使有效短暂日志尽可能在移动主机本地存放，以便恢复时可以迅速恢复。同时使用与有效短暂日志传输到基站的策略紧密结合的过区切换策略，使系统在平时负载和恢复速度之间找到一个平衡。

4) 介绍了原型系统的总体框架和各模块功能的详细说明。通过性能分析和实验证明AR-2LL-ELDCF有较好的综合性能。

5.2 将来展望

通过对嵌入式移动实时数据库系统中恢复问题的研究，本文提出了提出了基于短暂日志、使用动态检查点频率的两级日志策略AR-2LL-ELDCF。虽然AR-2LL-ELDCF有较好的综合性能，但是仍然存在一些不足。在今后的研究工作中，

华中科技大学硕士学位论文

需要在以下几个方面对AR-2LL-ELDCF进行进一步的研究和改善：

1) AR-2LL-ELDCF在事务长度和事务到达率变化幅度较大的情况下会出现检查点间隔时间剧烈变化的情况，在今后的工作中需要研究出一种更好的算法保证检查点间隔时间的平稳变化。

2) 该系统中的事务是为了演示恢复效果随机生成的简单事务，没有事务管理器，而且没有移动环境的支持，只能通过延时来模拟无线网络的传输过程。随着以后课题组项目的推进，需要在真实的移动环境下实现该恢复算法。

华中科技大学硕士学位论文

致谢

时光如同清澈的山泉从身边缓缓淌过，带走了我的幼稚和无知，留下了丰富的知识与美好的回忆，两年的硕士生活承载了许许多多的生活点滴，老师的关怀和同学的帮助让我的每一个进步中都凝聚着实验室大家庭的温暖，这是我人生中无比宝贵的财富。在此，我要对这一切表示衷心的感谢。

首先要感谢我的导师卢炎生教授。卢老师高尚的人品、渊博的学识、幽默的谈吐、

宽广的胸襟，无不让我深深折服。学业上，卢老师指引我的方向，带我走进学术的殿堂；生活上，卢老师给我悉心的关怀，为我创造了良好的学习环境和科研环境。在此谨对卢老师表示最诚挚的谢意!

再要感谢的是课题组三位老师潘鹏、赵小松、吴海，在论文的撰写和系统的实现

上他们给了我很多的指导和帮助。同时还要感谢同课题组的周明杰、白丹、周露、胡志鹏、祝晖、邓君、许白峰、马思懿、胡陆军等同学，在和他们的交流中我获得了很多知识，在系统的实现上他们给了我很多帮助。

感谢同实验室的张超、倪铭、温贤鑫、袁昌龙、王平等同学，感谢他们在生活和

学习上给予我的无私帮助。

感谢我的父母，是他们给我最无私的爱、最深切的关怀，让我在一个温暖的环境

中成长。

感谢我的女友汪粒，给我最坚定的支持，陪我走过这么多年。最后衷心感谢所有关心帮助过我的老师、同学和朋友们！

华中科技大学硕士学位论文

参考文献

[1] K徐进辉, 徐明. 移动数据库事务处理模型研究. 计算机工程与科学, 2004,

26(4):62～65

[2] 刘云生,卢炎生,王道忠.实时数据库系统(RTDBS)及其特征.华中理工大学学

报,1994,22(6):66～70

[3] K Ramamritham. Real-Time Databases. International Journal of Distributed and

Parallel Databases, 1993,1(2):99~126

[4] 刘云生,李国徽,卢炎生．实时数据库的事务处理．计算机世界,1999,(40)：C1O～

C13

[5] Lawrence A. Bjork. Recovery Scenario for A DB/DC System. in: Proceedings of the

ACM Annual Conference. Atlanta. 1973. New York: ACM Press,1973. 142～146 [6] Charles T. Davies. Recovery Semantics for A DB/DC System. in: Proceedings of the

ACM Annual Conference. Atlanta. 1973. New York: ACM Press,1973. 136～141 [7] K.M Chandy, J.C Brown, C.W Diisley et al. Analytic Models for Rollback and

Recovery Strategies in Database Systems. IEEE Transaction on Software Engineering, 1975,1(1):100～110

[8] JOOST S. M. VERHOFSTAD. Recovery Techniques for Database Systems. Acm

Computing Surveys,1978,10(2):177～195

[9] Theo haerder, Andreas Reuter. Principles of transaction-oriented database recovery.

Acm Computing Surveys,1983,15(4): 287～317

[10] Huang J. Recovery Techniques in Real-Time Main Memory Databases: [PhD Thesis].

University of Oklahoma, 1995.

[11] Huang J., Gruenwald L. Crash recovery for real-time main memory database systems.

in: Proceedings of the 1996 ACM symposium on Applied Computing. Philadelphia. 1996. New York: ACM Press,1996. 145～149

华中科技大学硕士学位论文

[12] Gruenwald L., Cheng S.J. A logging technique based on transactions types for

real-time databases. in: Bestavros A. and Fay-Wolfe V. eds. Real-Time Database and Information Systems—Research Advances. 1997. Kluwer Academic Publishers. 379～392.

[13] Sivasankaran R.M., Ramamritham K., Stankovic J. et al. Data placement, logging and

recovery inreal-time active databases. In Proc.Int. Workshop on Active and Real-Time Database Systems, 1995. 1～15

[14] Sivasankaran R.M., Ramamritham K., Stankovic J.A. Logging and recovery

algorithm for real-time database. Technical Report, Department of Computer Science, University of Massachusetts,1997.

[15] Lih Chyun Shu, Jonh A. Stankovic, Sang H. Son. Achieving bounded and predictable

recovery using real-time logging. Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium. New York, 2002: 286～297

[16] 廖国琼,刘云生.基于实时日志的嵌入式实时数据库恢复策略.计算机学

报,2007,30(4):672～679

[17] P. Krishna, N. H. Vaidya, D. K. Pradhan. Recovery in Distributed Mobile

Environments. in: Proceeding of The IEEE Workshop on Advances in Parallel and Distributed Systems, 1993. 83～88

[18] L. Alvisi, and K. Marzullo, Message Logging: Pessimistic, Optimistic, Causal, and

Optimal. IEEE Trans. Software Eng, 1998, 4(2): 149～159

[19] Dua Ruchika, Bhandari Saurabh. Recovery in Mobile Database System. in:

Proceedings of International Conference on Wireless and Mobile Communications. 2006. 32～37

[20] 萨师煊,王珊.数据库系统概论.北京:高等教育出版社,2002. 247～257

[21] Andreas Reuter. Performance Analysis of Recovery Techniques. ACM Transactions

on Database Systems,1984,9(4):526～559

[22] J. S. Keen, W. J. Dally. Performance Evaluation of Ephemeral Logging. in:

华中科技大学硕士学位论文

Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. Washington D.C. 1993. New York: ACM Press,1993. 187～196

[23] Richard Dean Regan. High Performance Ephemeral Logging for Database Systems:

[Dissertation for the Degree of Doctor of Philosophy(Computer Science)]. Polytechnic University,2001.

[24] J. S. Keen, W. J. Dally. XEL: Extended Ephemeral Logging for Log Storage

Management. in: Proceedings of the Third International Conference on Information and Knowledge Management. Gaithersburg, Maryland, United States.1994. New York:ACM Press,1994. 312～321

[25] J. S. Keen, W. J. Dally. Extended Ephemeral Logging: Log Storage Management for

Applications with Long Lived Transactions. ACM Transactions on Database Systems,1997,22(1):1～42

[26] Taesoon Park，Junguk L. Kim. A Checkpointing Recovery Approach in A Distributed

System on the CSMA/CD Network. in: Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing. Kansas City, Missouri, United States.1992. New York:ACM Press,1992.614～623

[27] Raj Sekhar pamnla, pradip k srimeni. Checkpointing Strategies for Database Systems.

in: Proceedings of the 15th annual conference on Computer Science. St. Louis, Missouri, United States. 1987. New York:ACM Press,1987. 88～97

[28] 于秀云.对数据库恢复策略的性能分析.计算机研究与发展,1998,35(12):1135～

1141

[29] Jim Gray, Paul McJones, Mike Blasgen et al. The recovery manager of the System R

database manager. ACM Computing Surveys,1981,13(2):223～243

[30] Kumar V., Hsu M. Recovery Mechanisms in Database Systems. Prentice-Hall PTR,

1998.

[31] Kumar V., Son S.H. Database Recovery. Kluwer International, 1998.

[32] Weikum G., Vossen G. Transactional Information Systems: Theory, Algorithms, and

华中科技大学硕士学位论文

the Practice of Concurrency Control and Recovery. Morgan Kaufmann Publishers,2002

[33] A. Reuter. A fast transaction-oriented logging scheme for undo recovery. IEEE

Transactions on Software Engineering,1980,6(4):348～356

[34] David Lomet, Mark Tuttle.A theory of redo recovery. in: Proceedings of the 2003

ACM SIGMOD international conference on Management of data. San Diego, California.2003. New York: ACM Press, 2003. 397～406

[35] C. Mohan, D. Haderle, B. Lindsay，et al. ARIES: a transaction recovery method

supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Transactions on Database Systems, 1992,17(1): 94～162

[36] Robert K. Abbott, Hector Garcia-Molina. Scheduling real-time transactions: a

performance evaluation. ACM Transactions on Database Systems,1992,17(3):513～560

[37] Lam Kan-Yiu, Kuo Tei-Wei. Real-Time Database Systems: Architecture and

Techniques. Boston: Kluwer Academic Publishers, 2001.109～124

[38] PG. Copeland, PT. Keller, PR. Krishnamurthy, et al. The case for safe RAM. in:

Proceedings of the 15th international conference on Very large data bases.19. San Francisco: Morgan Kaufmann Publishers Inc, 19. 327～335

[39] Nuno Neves, W. Kent Fuchs. Adaptive Recovery for Mobile Environments. ACM

Press,1997,1:68～74

[40] Hector Garcia-molina, Jeffrey D. Ullman, Jennifer Widom. 数据库系统实现. 第一

版. 杨冬青, 唐世渭, 徐其钧. 北京：机械工业出版社，2001. 310～326

华中科技大学硕士学位论文

附录攻读学位期间参与的科研项目

[1] “十一五”国家部委级科技预研项目《嵌入式移动实时数据库系统》

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文