计算机信息论文存储区数据恢复及其实现机制研

　　摘 要 针对一个支持主动实时事务的内存数据库管理系统ARTsMMDBS,讨论内存数据库的恢复处理及其实现机制,其内容包括事务提交和日志管理的恢复处理机制、检验点算法及故障恢复与重装算法等。用“影子内存工作区”兼做“影子”和“日志”,在事务提交时,采用“日志驱动”修改数据库的方法,既节省了内存空间,又简化了Abort处理。检验点及恢复与重装算法,把大量的恢复活动分离开来,尽量与事务处理并行执行,为内存数据库的高效实现提供了有力支持。

　　关键词：计算机信息论文,数据库,数据恢复,检验点,重装

　　内存数据库(MMDB)把数据库的主拷贝(即“工作版本”)常驻在内存[1],使系统性能得到了极大的提高。但是,由于所有操作直接作用于内存中的数据库主拷贝上,数据库极易受到操作系统和应用软件错误造成的破坏,因此MMDB的恢复技术如备份、检验点(Checkpoint)和重启动(restart)等都较常规的磁盘数据库(DRDB)复杂。而且,数据库恢复所包含的IO操作(如做日志、备份等)在事务运行不需要IO操作的内存数据库系统中也显得极为突出。因此,内存数据库的恢复机制对系统性能有重要的影响作用,内存数据库的恢复较之传统的磁盘数据库的恢复要复杂得多,也关键得多。

　　数据恢复是内存数据库可靠、实用的关键,恢复技术的研究已成为MMDB研究领域最热门的课题。人们从体系结构、事务提交、日志系统到备份、检验点算法等各个方面进行了大量的研究和探索。日志管理是内存数据库恢复机制中至关重要的一环。由于内存有易失性,日志最好保存于另一稳妥的介质上(如磁盘、非易失内存等),而对日志的IO操作又将在某种程度上影响MMDB的性能,可能成为瓶颈影响系统的事务吞吐量。为此,人们研究了各种各样的解决办法,比如构造非易失内存用于保存部分日志;采用“成组提交”的技术[2]来解决日志瓶颈问题等等。在检验点方面,为了提高系统效率,通常力图使检验点操作和事务处理同时进行。为了提高速度指标和综合性能,MMDB系统往往利用附加的硬件设备如非易失内存、专用的日志处理器、检验点处理器等来支持高效、快速的数据恢复。

　　本文针对一个支持主动实时事务[3]的内存数据库管理系统ARTsMMDBS,从内存数据库的特性出发,对日志管理、事务提交、检验点算法及恢复处理等方面进行了研究和探讨,介绍了一种合理可靠的内存数据库恢复机制。

　　1 事务的提交处理和日志管理

　　在支持主动实时事务的内存数据库管理系统ARTsMMDBS中,对每个活动事务Ti,系统为之分配一个“影子内存工作区”WAi,它兼有人们通常使用的“影子内存”和日志的双重作用。在事务Ti进入提交状态之前,它并不真正修改数据库(MDB),只是将其要对MDB所作的修改记录到相应的影子内存工作区中,当Ti进入提交状态时,由提交处理根据WAi 中的记录对MDB作相应修改。我们称这种修改为“日志驱动修改”[4]。当某一事务Tj由于某种原因夭折时,只需释放其相应的影子内存工作区WAj即可,而无需对数据库进行UNDO操作。这样,不仅可以大大节省内存空间,同时也简化了Abort(夭折)处。

　　ARTsMMDBS中事务的执行模型和恢复机制如图1所示。在该模型中,事务可以有如下4种状态:

　　1)活动状态——处于BEGIN(开始)和COMMIT(提交)之间。处于该状态的事务称为活动事务。

　　2)提交状态——完成了提交处理。此时的事务称为已提交事务。

　　3)夭折——事务的执行失败。该类事务称为夭折事务。

　　4)撤消——系统从事务表中撤消日志记录已写入外存文件中的已提交事务。

　　每个事务在数据字典的事务表中均有一个表项,记载它们的事务标识符(TID)、到达时间(AT)、截止时间(DT)、运行时间估算(RT)及当前状态(STATUS)等信息。在该执行模型中,日志操作(LOGGER)与事务处理同步地将WA中的日志记录写入到外存的日志文件(LOG)中,以便在系统发生故障时进行数据库恢复。检验点操作(CHECKPOINTER)定期地对MMDB进行操作,把内存版本(MDB)[5]的状态反映到外存,并向外存的LOG文件写CHECKPOINT记录。在系统发生故障时,数据库重装处理(RELOADER)将数据库外存版本(SDB)[5]中的MMDB的最近快照装入内存,然后,恢复处理(RECOVERY)利用LOG中的日志记录对快照进行向前恢复。为了便于对“影子内存工作区”的管理,给每一个“影子内存工作区”WAi设置一时间戳TWAi,用来表示对应事务提交过程结束的时间。每一个已提交事务的WAi按时间先后顺序组成链表,其结构如下:

　　WA1—→WA2—→WA3—→…WAn

　　TWA1

　　事务进入提交阶段,提交处理(COMMITER)对MDB作“日志驱动修改”。设WAi为活动事务Ti的影子内存工作区,则事务Ti在时刻t的提交处理算法为

　　COMMITER(WAi , t)

　　输入:WAi——事务Ti的影子工作区;t——某一个时间点。

　　输出:0——执行成功;-1——执行失败。

　　步骤:①依据WAi中的记录,对内存中所有要被事务Ti修改的数据块执行上锁操作;②对已上锁的数据块,根据WAi中的记录执行相应的更新操作;③在WAi中写入一个提交记录;④用当前时间t为WAi设置时间戳TWAi;⑤将WAi加入到影子工作区队列的尾部;⑥将事务表中该事务的状态标志位从运行状态改为提交状态;⑦对在步骤①中上锁了的数据块解锁。

　　经提交处理后,事务从运行状态转变为提交状态。凡存取提交事务所修改过的数据的

　　事务称为该提交事务的依赖事务。

　　从提交处理过程可以看出,WA队列是按事务提交的时间先后顺序排列的。日志操作

　　LOGGER对WA的处理按队列顺序进行,这就保证了提交事务比它的依赖事务先进入撤

　　消状态,从而保证了数据库状态的一致性。LOGGER对WA的处理算法为

　　LOGGER(WAq)

　　输入:WAq——影子工作区队列。

　　输出:0——执行成功;-1——执行失败。

　　步骤:①检查WAq是否为空,若不空,则从队列头取出第一个影子工作区WAx;若为空,则挂起;②将WAx中的记录写入外存的日志文件LOG中;③释放WAx;④将事务表中相应于WAx的事务的状态标志位从提交改为撤消;⑤转步骤①循环执行。

　　2 CHECKPOINT算法

　　常规DBMS做检验点操作时,通常要求数据库处于静止状态,即当前事务执行完了、而又没有(或不让)新事务开始。在MMDB中,CHECKPOINT操作较DRDB的工作量大大增加,在实时环境[2]下,这种延时是系统所无法接受的,根据MMDB的特点,可设计一种新颖的CHECKPOINT算法,将事务的活动和CHECKPOINT处理同时进行。

　　采用时间戳来确定做CHECKPOINT操作时哪些数据库段需要写入外存。时间戳TCP表示当前CHECKPOINT操作的开始时间,再为每个在内存的数据库段设置时间戳TSEG,指明其最后被修改的时间。

　　在CHECKPOINT操作期间,当COMMITER为一个事务进行提交处理并试图去修改一个数据库段s时,s的时间戳TSEG便和TCP相比较。如果TSEG〈TCP且s.change为真,则为s创建一个新的版本s′,并且在s中保持一个指向s′的指针。事务对段s的修改仍可在其上进行。

　　设△mem为在TCP时刻所有TSEG

　　CHECKPOINT(△WA,△mem)

　　输入:△WA——满足条件TWAi

　　输出:△mem满足条件TSEG

　　步骤:①如果△WA非空,则把其中的每个影子内存区WAi中的日志记录写到外存的LOG文件中。②如果△mem非空,则对其中的每个段s,执行:(a)如果在s中存在一个指向s′的指针且s′.change=TRUE,则将s′写入外存;(b)释放s′,将s中指向s′的指针置为空。

　　为了获得CHECKPOINT操作的行为一致,在向外存的LOG文件中写CHECK-POINT记录并设置TCP时,系统要处于静止状态,一旦CHECKPOINT记录写入外存的LOG文件中,事务的活动便可开始进行,以后的CHECKPOINT活动便可和事务处理并行进行。

　　3 ARTsMMDB的恢复与重启动

　　当系统发生故障须重启动时,整个恢复过程包括重装与恢复两个阶段,分别由RELOADER和RECOVER实现。由于采用了日志驱动修改机制,故系统重启后,事务处理可立即在WA中进行,同时RELOADER和RECOVER可以与事务处理并行运行,而无须等到MMDB完全恢复后再启动事务运行[6]。系统对每个由RELOADER装入的DB段X都设置了X.stale(待恢复)位。若一个段X被RELOADER调入内存后又被RECOVER用日志记录使其恢复到离系统崩溃最近的一致状态,则置X.stale为假,否则为真。

　　设在时刻t,系统正处于对MMDB的恢复阶段,DBm(t)为在此时已被RELOADER调入内存的数据库段的集合,WA[T]为某一事务T的影子内存区,当事务T要存取MMDB时将触发以下恢复算法:

　　RECOVER(WA[T],t)

　　输入:WA[T]——事务T的影子内存区;t——某一时间点。

　　输出:0——执行成功;-1——执行失败。

　　步骤:对所有段X∈DBm(t),执行:①如果X.stale=TRUE,则从外存的LOG文件中找出所有关于段X的日志记录。②根据①中找出的日志记录对段X进行恢复操作以使X接近于系统刚刚崩溃时的状态。

　　对于重装过程,考虑各实时事务运行的紧迫程度,相应地采取考虑事务优先级的装入算法。其目标是最先装入最紧迫事务要使用的数据。

　　RELOADER(sd,segr)

　　输入:sd——系统数据;segr——当前运行事务所要存取的数据库段。

　　输出:0——执行成功;-1——执行失败。

　　步骤:①装入系统数据sd;②装入segr;③将装入因子ff的初值置为1;④检测ff是否等于系统设置的阀值threval,若ff=threval则停止;否则转步骤⑤;⑤根据事务的优先级大小相应地装入其要存取的数据库段,且ff=ff+1;⑥转至步骤④。

　　其中,系统阀值threval根据系统中内存容量的大小和DB大小而定,若内存大到足以

　　容纳整个DB,则可将它定为整个DB段数。

　　这种恢复与重启动算法不仅考虑了MMDB恢复之后第一个要运行事务的数据要求,

　　而且力求使恢复过程尽可能与事务处理并行进行,大大缩短了事务的等待响应时间。

　　4 结 语

　　内存数据库的恢复机制是使MMDB具有实用性的关键。对内存数据库的修改操作采

　　用“影子内存工作区”、“日志驱动修改”的策略,不仅简化了abort处理,而且还可大大节

　　省内存空间。尽量使恢复处理与事务处理并行进行,并在重装算法考虑了实时事务的优先

　　级,保证了优先级高的事务所需的数据先装入内存,为系统在发生故障后仍能满足实时事

　　务的时限约束提供了有力支持。

　　参考文献

　　1 吴绍春,胡国玲,舒良才.一种内存数据库定义及其相关技术探讨.江汉石油学院学报,1996,18(4):91-94

　　2 Eliezer Levy,AviSiW Aers chatz. Incremental recovery in main memory database systems. IEEEtran-saction,1992, 4(6):529-540

　　3 Yunsheng Liu.OnReal-Time Database Transactions.CM PSCI Tech. Report,Univ.ofMass.,1994

　　4 胡国玲.支持主动实时事务的内存数据库原理:[博士学位论文].武汉:华中理工大学计算机系,1996

　　5 吴绍春,李国徽,胡国玲等.内存数据库组织与管理方法.计算机与数字工程,1997,3(1):91~94

　　6 EichHA.Classification and comparison of main memory database recovery techniques.Proc.Int.

　　Conf.on Data Eng.1987,(2):332~339