基于两步备份机制的内存数据库恢复方法研究

梁智兴 罗军

重庆大学计算机学院 重庆 400044

0 引言

内存数据库(main memory database,MMDB)区别于传统磁盘数据库(disk resident database,DRDB)，一般数据库的数据存取是针对磁盘设计的，事务操作涉及磁盘I/O，速度较慢。而内存数据库其数据存取针对内存设计，其“主拷贝”常驻内存，活动事务只与内存打交道，数据库则不再作为大量存储文件看待而作为内存中可寻址的大量数据，这使得存取速度快速、存取时间易于预测，提高了数据库性能，使内存数据库在实时系统等环境要求下表现良好。但由于内存的易失性，MMDB必须在磁盘或者其它非易失性存储器中保存它的备份，以防系统崩溃等故障导致内存中数据丢失。而数据库的备份、日志存储及异常情况下的系统恢复需要执行大量费时的磁盘I/O操作，这必将成为系统的瓶颈，影响系统正常的事务处理能力。

本文借鉴 Song's No-Log Recovery Mechanism采用了两步恢复机制。即，第一步，当事务提交时，数据处理器把影子内存(Shadow Memory)中的脏页备份到备份缓冲区中；第二步，恢复处理器把备份缓冲区中的脏页备份到归档磁盘的备份数据库中，结合影子内存技术，在增加稳定内存(stable memory)的情况下，设计一种用备份取代日志和检查点的恢复方法。此种方法，无需记录日志，同时，既可以减少恢复时间，又可确保响应时间的快速性和可预测性，更进一步的，它在两个分开的区域分别执行事务处理和备份，最小化避免了彼此之间的冲突。

1 MMDB数据恢复方法概述

当系统出现各种故障时，确保数据库快速恢复到一致性状态是M M D B恢复方法的目标。目前，对于M M D B的数据恢复方法已经有了不少研究，比较典型的有预提交、成组提交、检查点、影子页面等技术。其中预提交技术可以增加事务并发度，但不会减少I/O次数；分组提交技术可以减少系统的磁盘I/O瓶颈，但会增加事务提交处理的平均时间；检查点方面，较之非模糊检查点、模糊检查点、日志驱动检查点三类，目前有研究表明模糊检查点的性能在与事务并发方面表现最好，因为模糊检查点进程不加任何锁，不阻塞事务的正常执行，但是模糊检查点更新的数据库映像无法保证事务一致性，系统故障后通过较复杂的恢复算法把数据库恢复到较近的事务一致性状态，而且在检查点过程中读写无法并发。非模糊检查点分为动作一致性和事务一致性检查点，它们都在检查点时刻对脏页加锁，影响到事务的正常运行，但是它们备份出来的数据库由于满足事务一致性恢复算法相对简单。影子页面技术是所有要更新的页都复制副本影子页，更新发生在这些影子页上，如果事务成功提交，影子页成为当前页，否则影子页丢弃，它可以节省记录事务UNDO日志，但占用内存空间比较大。

2 基于两步备份机制的MMDB恢复方法

在这节里，首先描述两步备份恢复机制的系统配置，然后详细介绍当系统出现事故后，事务处理、系统备份以及系统恢复的详细流程。

2.1 两步备份恢复机制的系统配置

图1显示，恢复机制配置主要包括数据库处理器(DP)，恢复处理器(RP)，内存数据库(MMDB)，影子内存(SMEM)，备份缓冲区(Backup Buffer)以及备份数据库(Backup DB)。其中MMDB和SMEM是置于易失性内存当中，备份缓冲区则置于非易失性固定内存之中，而永久磁盘刚存放备份数据库。MMDB储存基本的数据库及在影子内存中确实被执行的所有数据更新。当事务引发M M D B中的一个更新操作时，它并不直接改变M M D B中的数据，而是在相应的影子内存的影子页中修改数据，当事务提交时，脏页回写MMDB。两步备份恢复方法与其它恢复方法不同在于，当事务提交后，DP首先将影子内存的脏页备份到备份缓冲区中，最后把备份缓冲区中的脏页备份到磁盘备份数据库中。为了更好说明恢复和事务处理，在此作以下说明。

（1）Transaction Page List(TPList，事务页表)，指影子内存中，针对当前事务的一张连续的页信息表，当事务提交时，这些页被拷贝到备份缓冲区中，同时，追加到BackupList表中。

（2）Usable Page List(UsabIeList，可用页表)，指影子内存所有页中，当前已执行事务所涉及到的一张连续的可重复使用的页表。已提交事务及当前事务所使用过的页均属于这个表。

（3）Shadow Memory Area Free Page List(SFreeList，影子内存区空闲页表)，指影子内存区空闲页表。

（4）Backup Page List(BackupList，备份页表)，指备份缓冲区中一张连续的页表，这些页将由RP负责将它备份到备份数据库。

（5）Backup Buffer Free Page List(BFreeList，备份缓冲区空闲页表)，指备份缓冲区中连续的空闲页清单。

由于在存取数据方面，内存比磁盘快得多，因此，锁的争夺就不像在传统磁盘上那样激烈，基于这个原因，可以通过选择整个数据库作为锁的粒度，从而避免并发控制消耗。许多研究也证明，这样确实有利于提高M M D B性能。

2.2 事务处理

事务处理流程如下：

（1）开始事务

（2）对于事务的每一个操作opi

①假设opi是读操作

a．如果读操作opi所涉及的页pagek在TPLIST中，则直接读；

b．如果读操作opi所涉及的页pagek不在TPLIST中，则读M M D B中的页。

② 假设opi是写操作

a．如果写操作opi所涉及的页pagek不在UsableList中 ；

I．从SFreeList中分配一个空闲页；

II．将MMDB中的页pagek拷贝到上步分配的空闲页中 ；

III．追加pagek的影子页到UsableList；

b．追加pagek的影子页到TPList；

c．更新pagek影子页。

（3）事务处理过程

①事务终止

a．比较UsableList和TPList，在UsableList 中删除TPList中的页；

b．释放TPList 里页并把他们追加到SFreeList；

c．置TPList为空。

② 事务提交

a．拷贝TPList里的所有页到Backup Buffer；

b．在BackupList中，追加上一步已拷贝的页；I．对于TPList中每页pagei，如果它不在BackupList中或者正处于备份过程中，则把它追加到 BackupList；

II．否则，删除pagei前一个拷贝页，并且使指针指向当前页pagei；

c．对TPList中每页，回写pagei至MMDB；

d．置TPList为空。

（4）结束事务

以上就是事务处理的步骤。下面进一步给出详细解释。

如果当前事务需要更新MMDB中的页时，它首先搜索UsableList，确认此页是否在SMEM中。如果此页在UsableList中，则直接更新页，否则，在SMEM中分配一个页空间，并把MMDB中所对应的页内容拷贝到刚分配的页空间来。当进行读操作时，如果所涉及到的页在TPList中，影子内存中的页应该可以读(这是因为同一事务所对应的写操作映射在影子内存中而不是MMDB中)，否则MMDB中的页可以读。

当事务提交时，所有已经更新的页被拷贝到Backup Buffer及被追加到BackupList，最后回写MMDB。如果某页因为同一个逻辑页号仍然保留在备份缓冲区中而没被拷贝到Backup DB，则不得不把它从Backup Buffer 和 BackupList删除，然后，当前页被拷贝至 Backup Buffer 和 BackupList中。如果相同的逻辑页备份正处于进程中，则当前页不进行删除操作，直接被拷贝到Backup Buffer 和 BackupList中。当TPList中的所有页被拷贝到Backup Buffer 和 attached to BackupList中，则事务提交程序结束。

图1 两步备份恢复机制配置

一般的基于影子页面的恢复技术，在事务提交后，将影子内存区的影子页全部删除。但在这里，两步备份机制却让他们留在影子内存区中，这是因为它们后面的事务可以继续使用它们。

当前事务的终止步骤就非常简单，丢弃脏页即可(因为更新操作发生在影子内存中)。

2.3 备份步骤

一般的MMDB恢复技术都采用检查点技术，就是周期地将MMDB中数据备份到磁盘。本文所提的两步备份机制不采用检查点技术，而是直接把Backup Buffer的页备份到Backup DB。这种备份由于没有MMDB的参与，也就不会影响事务的处理。但可能由于Backup Buffer没有空闲空间，事务提交会延迟，但这种情况在其它系统中由于其它种种原因也是不可避免的。

RP备份BackupList中的页，备份步骤如下：

① RP从BackupList中把他们删除；

② RP把他们追加到BFreeList。

2.4 恢复步骤

当系统出现故障时，由于没必要写任何日志，快速恢复成为可能。stable memory维护的页因为没有undo 和 redo操作，也就没有必要进行备份。系统重启后的第一项工作(重载Backup Buffer中的页至MMDB)只要花很短的时间就可在main memory 和stable memory中完成 ，尽管在恢复过程中，系统可能再次出现故障，但数据库系统仍然保持数据一致性，这是因为BackupList 中的页还在stable memory 中。

恢复步骤如下：

（1）系统重启；

（2）加载BackupList 中的所有页至MMDB；

（3）载入任务完成，开始新的事务。

如果新事务需要页时，在MMDB中对它进行搜索。

①如果搜索失败，从backup DB 中重载此页到MMDB。

②否则，正常处理事务。

2.5 最坏情况性能分析

由于本文所提出的机制是在Song's No-Log Recovery Mechanism 的改进，自然也就选用Song's模型来做比较，分析两步备份机制最坏情况下的性能。这里主要评价和比较最坏情况下的事务响应时间指标。

图2 说明了分析模型所关联的五个参数及它们所代表的意思。本文假设main memory (RAM)足够容纳整个数据库和相应的影子页面，stable memory 大小也足够容纳需要的信息，并且不会出现故障，事务连续被处理，stable memory 的存取时间比RAM慢2倍(相关研究表明stable memory 的存取时间比RAM慢2至4倍)。

最坏情况下，一个事务包含N个更新操作，每个更新操作存取不同的页，将被更新的页不在SMEM中，这样的话，N个页就应该从MMDB拷贝到SMEM。在Song's 的模型中，响应时间计算如下(RT 表示响应时间) ：

在两步备份机制中，事务响应时间可以按如下计算：

按上面假设，stable memory存取时间比RAM慢两倍，则可以用2* CMRead代替CSRead，2* CMWrite代替CSWrite，则两种机制的响应时间为

从上面得出的结果可知，在考虑stable memory存取时间比RAM慢两倍的情况下，两种算法的响应时间基本相同。

如果stable memory存取时间比RAM慢4倍，则用4* CMRead代替CSRead，4*CMWrite代替CSWrite，则两种机制的响应时间为

基于上面的比较，由此可见，两步备份机制的响应时间相对来说更快。

以上是通过理论推理得出来的结论，其实，我们也可换种角度来分析。在Song's 的模型中，它利用Stable Memory作为影子内存，而本文采用的两步备份机制是在main memory中划出一块适当大小区域作为影子内存，当事务处理涉及到的页越多时，MMDB和影子内存打交道的次数越多，由于main memory存取速度比Stable memory快，两步备份机制的响应时间也就比Song's 的提出的模型响应时间快。

图2 Parameters for the analytical model

综上所述，在最坏情况下，两步备份机制比Song's No-Log Recovery Mechanism具有更快的响应时间。

3 结束语

本文所提的两步恢复机制模型相比一般的恢复机制具有更快的响应时间，原因有三：一是由于使用部分主存作为影子内存，数据存取时间比使用 stable memory 更快，这样也就降低了页从M M D B到S M E M的复制损耗。第二，本文考虑到事务进程都是在主存中执行的，通过直接将备份缓冲区的脏页刷到备份磁盘中，消除了检查点对事务进程的干扰。最后，由于没有undo/redo日志，也就消除了记录日志时产生的磁盘I/O。在接下来的工作中，可以考虑研究没有stable memory硬件支持，具有更快的响应时间的恢复方法。

[1] E. M. Song, Y. K. Kim, C. H. Ryu, et. al., "No-Log Recovery Mechanism Using Stable Memory For Real-Time Main Memory Database Systems", RTCSA '99, IEEE CS.December 1999.

[2] G.Copeland, T.Keller, R.Krishnamurthy,and M.Smith, "The case for safe RAM", In proceedings 15th Int. Conference on Very Large Databases.1989.

[3] HUANG Lin, LU Jing, LIN Zhong, "Recovery method for main memory database systems based on shadow paging ",Computer Engineering and Design Vol.29, NO.10.May 2008.

[4] Eliezer Levy and Abraham Silberschatz, "incremental Recovery in Main Memory Database Systems," In IEEE Transactions on Knowledge and Data Engineering.Vol. 4, No. 6. Dec. 1992.