袁文亮 钟宝荣 何先平

（1.池州学院 数学与计算机科学系，安徽 池州 247000；2.长江大学 计算机科学学院，湖北 荆州 434023；3.长江大学 信息与数学学院，湖北 荆州 434023）

基于逻辑日志的内存数据库恢复子系统设计

袁文亮1钟宝荣2何先平3

（1.池州学院 数学与计算机科学系，安徽 池州 247000；2.长江大学 计算机科学学院，湖北 荆州 434023；3.长江大学 信息与数学学院，湖北 荆州 434023）

根据嵌入式系统环境的特点及其恢复需要，提出一种基于逻辑日志的嵌入式内存数据库恢复子系统设计模式，该子系统采用一主两副的节点模式，保证了数据对象恢复时状态与逻辑日志写时状态的一致性.经过验证试验表明该子系统有效地减少了日志信息量，缩短了系统的恢复时间，提高了系统的性能.

内存数据库；逻辑日志；检验点；恢复

0 引言

现代数据库应用有着与传统的商务或事务型应用不同的要求：事务有定时限制，数据有“时间一致性”，有“有效期”.实事事务及其数据都具有定时限制，事务的正确性不仅依赖其逻辑结果，还依赖结果产生的时间，因此要求系统能较高准确地预报事务的运行时间［1］.实事数据库系统（RTDBS）就是其数据和事务均可以有显式的定时限制的数据库系统，系统的正确性不仅依赖事务产生的逻辑结果，还要依赖于逻辑结果产生的时间.这就要求RTDBS能够较准确地估计事务在系统中的运行时间，但以磁盘数据库系统而言，存在着愈多不可预报的因素，其中重要的原因之一就是磁盘数据的I／O操作［2－4］.而对于内存数据库而言，由于整个数据库或“工作”部分已经访入内存，一个事务在执行过程中没有I／O，则为系统较准确的估算和安排事务的运行时间，使之具有较好的动态可预报性提供有力的支持，同时也为实现事务的定时限制打下了基础［5］.

由于MMDB较之通常的磁盘数据更为脆弱，更易受到多种系统故障的伤害，因为除了介质故障，事务与系统故障也都可以直接伤害数据库，所以对于基于RTMMDB的系统来说，故障发生后，能准确及时地恢复数据库至关重要［6－7］.

本文详细阐述采用基于逻辑日志（logical logging）的恢复子系统，给出了基于逻辑日志的检验点策略及故障恢复策略.

1 基于逻辑日志恢复子系统LDMRS

恢复子系统由一个主节点和两个副节点组成，主节点向用户提供服务，而两个副节点不向用户提供服务，它们只为主节点提供数据刷出和故障恢复服务.正常情况下，主节点响应用户的请求，执行事务，副节点维护事务日志和执行外存数据库的更新.当故障发生，利用某一个副节点来恢复主节点，如图1所示.

该子系统中，事务管理模块为每一个事务单独分配一个私有日志缓冲区和私有数据缓冲区，并采用延迟的数据库修改策略.对每一个事务的操作（包括读操作、写操作、事务提交、事务夭折），先是把事务所更新的数据放在其私有数据缓冲区内，日志管理器负责为该事务在私有日志缓冲区创建一条对应的逻辑日志记录.当一个事务的提交日志被写入其私有日志缓冲区后，私有日志缓冲区的内容才同时刷到两个副节点的日志缓冲区，副节点负责将其日志缓冲区内容刷到外存.该事务的日志写完后，其私有数据缓冲区的更新才能被写入到MMDB.

图1 恢复子系统结构

2 主要数据结构

为了恢复的需要，系统在内存中创建并维护两个表和一个链表：事务信息表（TIL）、MMDB页表和数据信息链表（DIL）.TIL表由事务管理器创建并维护，为进入系统的每一个事务创建并维护一条记录，每一条记录包含两个域：TID和State表示事务标识；State表示该事务所处状态.MMDB页表为MMDB中每一个数据页维护一项，每一项包括四个域：PID，BID，Ubit和Tbit.其中PID为MMDB中数据页的标识.BID表示数据页PID在两个副节点的外存数据库中所对应的数据块的逻辑块号.Ubit为更新位，用来表示MMDB数据页PID的更新是否已经传输到了副节点，Ubit为1表示数据没有被传输，Ubit为0表示数据被传输，PID和某个节点的BID处在一致性状态.Tbit为标识位，标识MMDB数据页PID是否在检验点执行期间被更新，Tbit为1，表示该数据页被更新，Tbit为0，表示数据页没有被更新.MMDB页表由恢复管理器负责维护.DIL链表的结点有三个域：PID，BID和Data，其中PID为MMDB中数据页，它对应在副节点的外存数据库中所对应的数据块的逻辑块号是BID，该数据页的内容为Data.

3 日志和检查点模式

子系统中有三类日志，其中TID为事务调度任务在创建该事务时赋予的编号.Length表示该日志记录的长度.T＿type取值1，2，3，分别表示事务的开始、夭折和提交.body是逻辑日志体，C＿type取1，2，分别表示检验点开始、结束.TIL（事务信息表）用来记录检验点开始时系统中事务的相关信息.

根据故障后恢复的需要，在检验点开始后，可以将事务分成如下3个集合（忽略处于夭折状态的事务）：T1是检验点开始前已经提交的事务集；T2是当前是活跃的或当前时刻之后建立的事务集，它的提交时间发生在检验点结束之前；T3是当前是活跃的或当前时刻之后建立的事务集，它的提交时间发生在检验点结束之后.很明显，这次检验点的T1是上次检验点的T2，T3的并集.

系统采用动态检验点模式，检验点进程和事务并发执行.根据预先设置的阈值，当MMDB页表中脏页所占比率大于时，检验点进程被触发.可以通过调整值来达到调整检验点的执行频率.

检验点进程的执行过程描述如下：根据节点选择变量的值，判断本次检验点执行时，脏数据应该刷入哪个副节点（为了描述方便，假设这次选择的节点为Pa）；读取事务信息表的内容，写入Begin＿Checkpoint日志到Pa日志文件；根据MMDB页表依次将脏数据传输到Pa节点的DIL链表中，同时修改相应的Ubit位（将Ubit位置0）.在具体刷新每一脏页到SDB时，采用互斥量以确保在刷新过程中不会被并发事务所修改.T2类事务提交时，将其逻辑日志刷到副节点，私有数据区的数据刷入MMDB，更新的数据页的Tbit置1，Ubit置0，该数据在此次检验点期间不被传输.检验点结束.T2类事务变成下一次检验点的T1类事务，将Tbit置0，Ubit置1；写End＿checkpoint日志记录到Pa日志文件；Pa节点根据DIL.BID把DIL.Data刷到外存；根据Pa节点数据库更新Pb节点数据库.

4 恢复

故障发生以后，迅速而有效地恢复对内存数据库而言至关重要.对事务故障（事务夭折），由于采用了延迟写技术，事务对数据库的更新在事务提交后才能真正写入数据库.因而，对这类故障只需释放事务的私有数据缓冲区和对应的活动日志区即可，无需对数据库执行部分Undo操作.如果是已提交事务在修改内存数据库时出现故障，可以重新从事务的私有数据缓冲区刷出数据.

对于系统故障，它导致系统非正常终止，MMDB遭到破坏，造成了数据的丢失，从而导致一些新近提交的事务（它们对数据的更新已经写入了MMDB，但是尚未或尚未完全刷新外存数据库）的效果丢失.系统重启后，这部分事务必须被Redo，以确保事务的持久性.系统故障的恢复中，有如下三种情况（假设脏数据先刷入Pa节点）：

1）如果故障发生时，Pb节点也已经更新完毕，T2类事务中全部事务的日志已经刷到了两个节点，T3类事务中已提交事务的日志也刷入到了两个节点.此时，T1类事务的数据库更新已经刷到两个副节点，故此类事务无需Redo.但是T2类事务和T3类事务中已提交事务数据库更新尚未开始刷出，此类事务必须Redo.恢复时任取某一个副节点，从日志文件尾反向扫描，直到遇到End＿checkpoint日志，该位置就是本类故障的Redo起始点.

2）如果故障发生时，Pb节点尚未更新完毕.此时，T1类事务的数据库更新已经刷到Pa节点，T2类事务中全部事务的日志已经刷到了两个节点，T3类事务中已提交事务的日志也刷入到了两个节点，所以其恢复策略是利用Pa节点恢复MMDB，然后利用1）中的Redo起始点，重做检验点结束到故障发生期间提交的事务.在恢复主节点同时，恢复Pb节点.

3）如果故障发生时，当最后一次检验点尚未结束.此时T1类事务的数据库更新尚未完全刷到Pa节点.T2类事务部分提交，已提交的事务需要Redo，T3类事务尚未提交，无需Redo.取Pb节点，从日志文件尾反向扫描，直到遇到End＿checkpoint日志（它是前一次检验点的结束，扫描过程经过本次检验点的Begin＿Checkpoint日志），该位置就是本类故障的Redo起始点.其恢复策略是利用Pb节点恢复MMDB，从Redo起始点重做T1类事务和已提交的T2类事务.在恢复主节点同时，恢复Pa节点.

5 性能分析

物理日志要求日志记录中记录数据库元素的新值、旧值或二者都记录.逻辑日志包括了比物理日志更高层的数据库描述以及数据库的状态转移情况，它指出逻辑值的改变，不涉及物理值.逻辑日志大小一般只有物理日志大小的1／2～1／4［4］.

6 结束语

本系统很好地解决了因日志信息量大，内存数据库备份恢复时间过长的问题.通过建立两个副节点，在满足逻辑事务重做条件的同时，还使主节点在事务提交时避免I／O操作，提高了系统的性能.在数据操作比较频繁的嵌入式内存数据库系统中，具有很好的应用价值.下一步研究工作为解决T2类事务的数据库修改刷出延迟的问题，它延长了系统的恢复时间，但可以接受，因为在基于物理日志的恢复系统中，它也是需要Redo的.

图2 不同系统的日志操作开销

［1］Eliezer L，Avi S.Incremental recovery in main memory database systems［J］.IEEE Transactions on Knowledge and Data Engineering，1992，4（6）：529-540

［2］肖迎元，刘云生，刘小峰，等.嵌入式实时内存数据库故障恢复技术［J］.计算机科学，2005，32（8）：77-79

［3］许贵平，蔡博克.支持实时内存数据库不间断服务的恢复技术［J］.计算机工程，2008，34（6）：70-71

［4］宋广华，杨长生.基于混合日志的内存数据库恢复子系统［J］.浙江大学学报，2001，38（2）：164-168

［5］吴绍春，胡必鑫，梁少华，等.内存数据库恢复及其实现机制［J］.江汉石油学院学报，1998（2）：101-105

［6］邱元杰，刘心松，杨 峰.一种高效的分布式并行数据库日志机制［J］.计算机研究与发展，2004，41（11）：1 942-1 948

［7］Ciaccio G，Ehlert M，Schnor B.Exploiting gigabit ethernet ca-pacity for cluster applications［A］.In：Proc of the 27th Annual IEEEConf on Local Computer Networks（LCN 2002）［G］.Tampa，Florida：IEEE Computer Society Press，2002：669-678

A Main-Memory Database Recovery Subsystem Based on Logical Logging

Yuan Wenliang1Zhong Baorong2He Xianping3
（1.Department of Mathematics and Computer Chizhou College，Chizhou 247000；2.School of Computer Science Yangtze University College，Jingzhou 434023；3.School of Information and Mathematics，Yangtzg University，Jingzhou 434023，China）

We introduce a embedded main-memory database recovery subsystem based on logical logging.The system uses a mode of one main and two minor nodes，which ensure the consistency of state when data objects are recovering and logical logging is writing.This system reduces the amount of logging information effectively，shortens recovery time of system and improves the performance of the system.

MMDB；logical logging；checkpointing；recovery

王映苗】

1672-2027（2011）03-0064-04

TP392

A

2011-03-28

国家自然科学基金项目（60873021／F0201）；安徽省池州学院院级科研重点项目（XK0902）.

袁文亮（1979-），男，湖南娄底人，硕士，池州学院数学与计算机系讲师，主要从事现代数据库理论研究.

book=67,ebook=133