基于影子页面和混合日志的MMDB恢复方法

鲍程锋， 杨小虎

(浙江大学计算机科学与技术学院，浙江杭州310027)

0 引 言

内存数据库，简单的说就是数据库的“工作版本”(也可以是整个数据库)常驻内存的数据库系统[1]，即任意时刻，任意一个活动事务所操作的数据集都在内存中。由于内存数据库是针对内存设计的，数据库不再是按照某种数据模型组织起来并存放在磁盘中的数据集合，而是作为内存中可寻址的数据集，活动事务只与内存打交道，而不需涉及磁盘I/O，所以内存数据库相对于传统的磁盘数据库来说，存取速度更快，且存取的时间是可预测的。然而由于内存的易失性，内存数据库必须在磁盘上保留备份，使得发生系统崩溃等故障的情况下，能使数据库恢复到一致性状态[2]。这就导致数据库更新的备份、日志的存储以及异常恢复大量的磁盘I/O操作，所以设计高效的系统模型以及恢复策略是内存数据库的关键技术之一。

本文讨论了通过结合影子页面[4]技术、混合日志策略以及模糊检查点[6]思想的内存数据库的组织结构，并在此内存数据库结构下，如何实现内存数据库数据以及日志的快速备份，以及当内存数据库出现事务故障或者系统故障时，如何通过磁盘上内存数据库的备份文件和日志文件，来快速恢复内存数据库到一致性状态。

1 内存数据库模型和故障恢复策略

1.1 系统模型

系统模型如图1所示，内存数据库主要由以下几个部分组成，内存数据库区，影子页面区，私有日志区，全局日志区。

图1 系统模型

每个事务都有自己独立的私有日志区，这样可以避免多个事务之间对日志区访问的严重竞争。当某一个事务要对内存数据库中某一个页面进行更新操作时，首先要复制一份与这个将要被更新页面一模一样的页面，称为这个被更新的数据库页面的影子页面，所有的更新操作首先作用在这个影子页面上，当事务夭折时，直接撤销对应的影子页面和私有日志，而无需记录Undo日志；当该事务已提交，并且已经把私有日志区的日志文件更新到全局日志区时，再把数据库中的该页面替换为其对应的影子页面并置脏页位。另外通过一个独立的进程不断的把全局日志区的日志刷新到磁盘日志文件上。

1.2 事务过程

在本系统模型中，我们采用影子页面技术来完成对内存数据库页面的更新操作。对所有要被更新的数据库页面都复制一个跟原页面相同的副本(影子页面)，更新发生在影子页面上，而不是原数据库页面上，如果事务成功提交，把当前数据库页面替换成其对应的影子页面，如果事务失败，则丢弃影子页面。由于不是直接在当前页上做修改，当前页的信息在事务未成功提交前仍存在，所以可以不用记录事务Undo类型日志。当事务由于异常情况终止时，只要撤销其对应的影子页面和日志文件即可。通过这种方法，可以减少日志文件的大小和恢复时的重做过程，可以提交恢复的效率。

当一个事务开始执行时，首先获得要修改的数据库页面的锁，并复制一个该页面对应的影子页面，事务在这个影子页面上做相应的修改数据的操作，并将对应的日志写到其对应的私有日志区，如果事务失败，则丢弃该事务对应的影子页面和私有日志区的日志文件即可，也就是事务故障的恢复并不涉及磁盘I/O，系统可以快速从事务故障中恢复；如果事务正常提交，则执行事务的提交过程。事务提交过程(见图2)如下：

(1)首先，获得全局日志缓冲区的锁，复制日志文件到全局日志缓冲区，在检查点过程时，复制的是物理日志；在非检查点过程时，复制的是逻辑日志。当复制日志文件过程结束，释放全局日志缓冲区的锁。

(2)把当前内存数据库页面替换成其对应的影子页面。

(3)丢弃内存数据库老页面和其对应的私有日志区日志文件。

(4)释放所有锁。

(5)如果全局日志缓冲区中还有这个事务对应的日志文件未被刷新到磁盘文件，则等待相应的日志文件的备份完成。

在一般的事务执行过程中，日志先被存放在私有日志区中，这样可以有效的减少对全局日志缓冲区的竞争，并且由于只有正常提交的事务的私有日志区日志才会被复制到全局日志缓冲区，然后刷新到磁盘，所以当系统出现故障重启之后，只要根据日志进行重做即可[8]。

图2 事务提交过程

在事务提交的第一步中，锁定全局日志缓冲区后，需要确定复制物理日志还是逻辑日志到全局日志缓冲区，我们使用一个由检查点进程维护的全局变量，chkpt_flag来确定。具体算法如下：

由于全局日志缓冲区的锁是同步的，也就是说检查点进程不能在事务写日志时，写BC或者EC到全局日志缓冲区，并设置监测变量，所以事务日志不会出现部分是物理日志，部分是逻辑日志的情况。

1.3 混合日志

由于本系统模型采用模糊检查点的策略，检查点进程备份内存数据库文件以及全局日志缓冲区的日志文件到磁盘上的数据库文件和日志文件时，并不阻塞一般事务的执行过程。这样就会导致检查点过程刷新内存数据库中部分已被更新的脏页面备份到磁盘上的备份数据库中，这样的情况下，只有通过记录物理的日志的方式才能使得内存数据库恢复到一致性状态。但是如果系统中全部采用物理日志类型的日志就会出现另外一个问题，由于物理日志类型的日志数据量庞大，那么在日志的备份以及根据日志重做方面会消耗大量的时间，系统在执行一般事务，以及发生故障之后的恢复等操作将会变的异常缓慢，这将成为内存数据库的瓶颈。

为了解决以上两种情况，达到既能在内存数据库不一致情况下发生故障时把内存数据库恢复到故障前的一致性状态，又能减少日志文件大小的效果，我们采用混合日志的策略进行日志记录。当系统运行在两个检查点进程间的时候，并不进行备份操作，即，系统不刷新内存数据库中的脏页面到磁盘上的备份数据库中。因此在这种情况下，不会发生部分已被更新的脏页面被刷新到备份数据库的不一致状况。所以，当系统运行在两个检查点进程之间的时候，可以使用逻辑日志类型的日志进行日志记录。逻辑日志类型的日志可以保证内存数据库在一致性状况下发生故障时，进行重做，使得内存数据库恢复到发生故障之前的状态。当检查点进程正在运行时，我们必须使用物理日志。因为此时，系统正在不断备份内存数据库的脏页面到磁盘数据库上，一般事务的更新操作也在同时进行，所以有可能备份了部分已被更新的脏页面到磁盘上，而此时数据库正处于不一致状态，如果发生系统故障，必须使用物理日志才能使得内存数据库回到故障发生之前的状态。

通过以上的分析，采用混合日志策略如下：当检查点进程正在运行时，使用物理日志，当系统处于两个检查点进程之间时，使用逻辑日志。既可以减少日志量，又可以对部分已更新的脏页被刷新到磁盘备份数据库时发生系统故障的情况进行故障恢复。

1.4 检查点过程

检查点过程主要是把内存数据库的脏页刷新到磁盘上的备份数据库中。为了使检查点过程不阻塞事务，本系统模型采用模糊检查点方法[3,6]，就是在检查点过程不对刷新的脏页加锁，事务对页面可读写。一般模糊检查点过程算法如下：

采用模糊检查点策略能够使得检查点进程和事务并行，不需要在运行检查点进程时阻塞事务进程的运行。然而采用模糊检查点策略可能会违反WAL(write-aheadlogging)规则[7]。考虑以下情况，当利用影子页面方式更新时，事务首先把日志写到日志页面，接着刷新影子页面的脏数据到内存数据库中，然后事务等待日志页面被刷新到磁盘，如果此时，检查点进程也同时在运行，那就可能导致部分已经更新到内存数据库的脏数据被更新到磁盘上的备份数据库，而此时对应的日志页面还没有被更新到磁盘，这就违反了WAL(write-aheadlogging)规则。如果在这种情况下，发生系统故障，因为磁盘上没有对应日志文件，磁盘的备份数据库就不能恢复到一致性状态。我们采用乒乓策略[5]作为备份方法来避免在做检查点时违反了WAL(write-ahead logging)规则。因为乒乓策略总是维护两个备份数据库，检查点进程交替的在两个数据库之间进行备份操作，所以，当前进行更新操作的数据库页面的原始页面总是存在的，所以这样就能使得备份数据库恢复到一致性状态。检查点的执行过程如下：

(1)首先，不断的循环直到获取全局日志缓冲区的锁，并对全局日志缓冲区加锁，接着记录检查点过程开始标记(BC)到全局日志缓冲区，以区分检查点开始前和开始后提交的日志。

(2)释放全局日志缓冲区的锁。

(3)把数据库的脏页复制到临时缓冲区，并清除脏页位，然后将临时缓冲区的内容刷新到磁盘上备份数据库对应的页面。

(4)取得全局日志缓冲区的锁，写检查点结束的标记(EC)到全局日志缓冲区。

(5)释放全局日志缓冲区的锁。

(6)等待全局日志缓冲区的日志刷新到磁盘，直到检查点结束标记，EC，被刷新到磁盘日志文件。然后记录检查点开始标记，BC，的位置，并设置BC为内存数据故障恢复重做起点。

下面一个问题是系统如何根据备份的数据库文件和日志文件把内存数据库恢复到发生故障之前的状态？在这个过程中需要对数据库文件进行重装以及根据redo日志文件进行重做。那么如何确定redo日志重做起点就成为系统的关键。在本文描述的系统模型中，我们采用混合日志，即在检查点过程中使用物理日志，在检查点进程间采用的逻辑日志。我们可以使用物理日志对部分更新的数据库文件页面进行恢复，而逻辑日志则无法将部分更新的数据库文件页面恢复到之前的一致性状态。考虑以下情况，如图3所示，在检查点进程写BC到全局日志缓冲区的时候，一般事务T1正在更新内存数据库的页面，那么这些部分更新的内存数据库的页面可能被刷新到磁盘上的备份数据库文件中。而由于事务 T1开始于检查点进程开始之前，T1采用逻辑日志。因此当发生故障的情况下，系统无法根据日志文件进行内存数据库的恢复。鉴于以上情况，我们采用推迟检查点备份起点策略，系统等待事务T1的更新操作结束才开始检查点的备份操作，这样检查点进程就可以避免备份部分被更新的数据库页面，并且其对应的日志类型是逻辑日志的情况。事务 T2更新内存数据库文件页面也可能部分被刷新到磁盘上的备份数据库中，但是其日志记录开始于BC之后，所以其对应的日志类型是物理日志，系统可以根据日志文件将内存数据库恢复到一致性状态。根据以上描述，由于本系统模型采用延迟的检查点备份起点策略，所以只要记录上一次完整的检查点过程的开始位置(BC)，并将其作为日志重做起点，就可以把重装后的内存数据库恢复到发生故障之前的一致性状态。

图3 延迟备份策略

2 故障恢复

2.1 事务故障

对于事务故障，由于我们采用影子页面技术，事务在提交之前，系统维护一个与数据库原页面一模一样的影子页面，事务所作的修改都发生在影子页面上。因此，当发生事务故障时，我们只需要丢弃该事务所涉及的所有影子页面，清空其私有日志缓冲区即可。也就是说事务故障恢复并不涉及磁盘I/O，使得恢复过程非常迅速。

2.2 系统故障

以下将对于不同时刻发生的系统故障，重做开始位置的确定进行分析。

如图4所示，系统故障可能发生在检查进程间，也可能发生在检查点过程中：

(1)当出现图4中系统故障1时，即系统故障发生在两个检查点进程之间，磁盘数据库处于第K个检查点进程完成后的状态。根据前文的分析可知，对于BCK后第K个检查点备份点之前已经完成的对内存数据库页面的更新操作都将被完整的刷新到磁盘数据库上，而之后对内存数据库的更新可能部分被刷新到磁盘数据库，存在不确定性，因此这种情况下，BCK是redo日志的重做起点。

(2)当出现图4中系统故障2时，即系统故障发生在检查点过程中。这种情况下，同样只能保证BCK后第K个检查点备份点之前的对内存数据库的更新被刷新到磁盘数据库，而无法保证之后的更新完整的被刷新到磁盘数据库，因此，同样BCK是redo日志的重做起点。

从以上分析可知，由于采用了延迟备份的检查点策略，系统故障发生后恢复的redo起点是最近一次完整检查点过程的开始位置BC处。即只需提供例子中BCK后的日志即可，而无需导入全部的日志文件，减少了日志量，使得恢复过程更加迅速。

图4 系统故障情况

3 性能分析

本节将通过比较采用混合日志和完全采用物理日志两种策略所产生的日志量，来说明本文所采用的内存数据库恢复方法在恢复性能上的优势。

假设内存数据库有N个分区，并且采用连续的检查点策略，即当前一个分区的检查点过程结束之后，紧接着开始后一个分区的检查点过程。并且假设每一个分区检查点过程中，事务对分区访问所产生的日志个数均为S，则一个分区检查点过程所产生的日志个数为SN，所以一个完整的检查点过程所产生的日志个数为(SN)N。设一个物理日志大小为P，一个逻辑日志大小为Q，记一个完整的检查点过程所产生的日志量为 ChkptLogSize，一个完整的恢复过程重做的日志量为 ApplyLogSize。则当在完全采用物理日志的情况下，有

在采用混合日志的情况下，一个分区检查点过程所产生的日志量为SP+SQ(N-1)，则

由以上分析可知，ChkptLogSizephysical/ChkptLogSizehybrid=NP/(P+NQ-Q)，ApplyLogSizephysical/ApplyLogSizehybrid=(NP+P)/(2P+NQ-Q)，由于P比Q大的多，所以，ChkptLogSizephysical/ChkptLogSizehybrid和 ApplyLogSizephysical/ApplyLogSizehybrid都大于1，即采用混合日志策略比采用物理日志策略所产生的日志量和恢复过程所需的日志量都要小，使得检查点过程和恢复过程都有更好的性能表现。

4 结束语

本文设计了一种基于影子页面和混合日志的内存数据库恢复方法，并结合模糊检查点的思想以及延迟备份策略，使得在处理事务故障时，无需磁盘I/O操作，检查点过程和事务执行过程并行，并且由于记录的日志量大大减少，使得内存数据库在系统故障后能快速恢复。将来我们研究的重点是该方法在分段的内存数据库中的应用以及检查点进程周期的确定等问题。

[1]许贵平,蔡博克.支持实时内存数据库不间断服务的恢复技术[J].计算机工程,2008,34(6):70-71.

[2]王珊,肖艳芹,刘大为,等.内存数据库关键技术研究[J].计算机应用,2007,27(10):2353-2357.

[3]廖国琼,刘云生,肖迎元.实时内存数据库分区模糊检查点策略[J].计算机研究与发展,2006,43(7):1291-1296.

[4]黄琳,路京,林中.基于影子页面的MMDB的数据恢复方法[J].计算机工程与设计,2008,29(10):2470-2473.

[5]Qin Xiongpai,Xiao Yanqin,Cao Wei,et al.A parallel recovery scheme for update intensive main memory database[C].Otago:PDCAT,2008:509-516.

[6]陈安龙.内存数据库中数据恢复技术的研究与实现[D].杭州:浙江大学计算机学院,2006.

[7]肖迎元,刘云生,廖国琼,等.一种实时动态数据库故障恢复策略[J].软件学报,2007,18(10):2516-2527.

[8]Using oracle in-memory database cache to accelerate the oracle database[EB/OL].http://www.oracle.com,2009.