空间实时内存数据库恢复机制研究与实现

杜 晔，郭丽丽

(1.中国科学院光电研究院，北京100094;2.中国科学院空间应用工程与技术中心，北京100094;3.中国科学院研究生院，北京100094)

0 引言

空间应用对数据管理的实时性和可靠性有着较高的要求。传统数据库旨在处理持久稳定的数据，无法满足实时应用的需要，而内存数据库 (Main Memory Database，MMDB)由于其工作版本常驻内存，所有数据的存取和管理在内存中完成，访问速度比传统数据库高1-2个数量级，对于实时性要求较高的空间数据管理系统是一个较好的选择。然而由于内存具有易失性，内存数据库必须在磁盘或其他非易失性存储器存储器中保存备份，以防止程序错误、系统掉电等系统故障带来的数据损失。但备份所需要的大量磁盘I/O操作将影响系统效率，因此高效的恢复策略是内存数据库的关键技术之一。目前较广泛应用的是用基于日志和检查点的方法来对内存数据库进行恢复。为了减少日志的数量，常采用本地更新 (in Place Update)的方式来对数据进行操作，记录日志时仅需要记录被修改数据的后像(after image)，即Redo日志。同时为了减少系统恢复所需要的日志数量，使用检查点将MMDB备份到磁盘。

Swallow是为空间应用研发的实时内存数据库，本文针对Swallow内存数据库结构，研究并设计了一个基于日志驱动修改、影子页面技术、模糊检查点思想的内存数据库恢复机制，主要包括:设计了基于日志驱动修改的事务执行算法，减少了需记录日志的数量并提高了事务故障的恢复效率;设计了日志快速提交算法以提高事务并发度;设计了系统的检查点策略，减少系统恢复需要的日志量以及检查点运行时对系统效率的影响。在此恢复机制下，实现了Swallow内存数据库数据和日志的快速备份以及在内存数据库出现事务故障和系统故障时的快速恢复策略。最后通过实验证明了该恢复机制的高效性。

1 Swallow恢复模型概述

Swallow的主要模块有事务管理器，内存池页面管理器，存储管理模块和恢复模块。内存中的数据以分页的形式存在，通过内存池页面管理器进行统一的管理和维护，在此之上提供了数据库的常用接口 (如表、关键字和数据的增删查改等)，同时页面管理器维护一个脏页表，记录了从上次检查点之后被更新过的页面。系统通过多线程来支持多个事务并发，并由事务管理器在系统中维护一个事务信息表，系统每接收一个新的事务线程，都在事务信息表里记录相关信息。存储管理模块负责MMDB和磁盘数据库文件的数据交换。恢复模块包括全局日志的写入，检查点的执行以及故障后的系统恢复。

图1是Swallow的恢复模型。事务对MMDB的修改是由日志驱动的，某个事务要对MMDB中的页面进行更新操作时，并不直接对MMDB进行修改，只是将其Redo日志记录在其对应的私有日志区里，事务进入提交阶段后，将其对应的私有日志放入全局日志缓冲，写日志线程定期将全局日志缓冲刷新到磁盘的日志文件里，事务提交完成后由页面管理器根据日志对MMDB进行相应修改。若事务尚未进入提交阶段就夭折则直接释放其对应的私有日志，不对MMDB进行操作，不需记载Undo日志。

图1 系统恢复模型

根据Redo日志的先写日志 (write ahead logging，WAL)规则，事务提交时应将该事务的所有日志都写入日志中，才能进行事务对数据库的更改，这意味着事务提交必须有I/O过程，对实时性较强的内存数据库系统将是很大的性能瓶颈，此处的设计参考了预提交协议和成组提交协议，在事务私有日志已放入全局日志缓冲后即对MMDB进行更新，然后释放锁，以提高了内存事务的并发度。但在将MMDB的数据刷新到外存时仍需要遵守WAL规则，即在一个检查点开始前需要将已提交事务的日志刷新到磁盘日志文件。

检查点操作是为了减少恢复时需要读取的日志数量，将内存数据库中的脏页刷到磁盘数据库文件进行持久性备份的过程。静态检查点要求检查点过程中系统处于完全停滞状态，对实时性要求较强的空间实时内存数据库这是无法接受的。传统的模糊检查点不对待刷新的脏页上锁，检查点过程中事务对MMDB的页面可读写，这样保持的磁盘备份极易违反WAL规则。Swallow的检查点设计为与事务并发进行，检查点对页面加读锁，保证事务的一致性;同时为了在检查点过程中减少对事务的影响，在检查点执行过程中，若事务需要访问的页面被检查点锁住，则页面管理器复制一个当前页面并记录为该页面的影子页面，此后事务对该页面的修改都在影子页面里进行，等到检查点完成后，将对应的影子页面替代原页面即可。当系统中脏页数量达到一个阈值后，页面管理器唤醒检查点线程进行检查点操作。检查点完成后，在日志中记录新的重做起点。由于检查点是事务一致的，系统故障后，装入磁盘的数据库文件并利用读取的磁盘日志文件从重做起点对MMDB进行Redo操作即可恢复到一个最近的一致性状态。

这个恢复模型的特点有:仅需要记载Redo日志，事务失败则直接丢弃日志，无需回滚操作，因此对于事务故障的恢复是实时的，且日志驱动的修改方式保证事务在提交前不直接在MMDB中修改数据，事务读写的并发性得到了提高;事务对MMDB的修改采取预提交方式，当私有日志放入全局缓冲即可对MMDB进行修改，减少了传统提交方式需要等到日志写到磁盘后才能修改MMDB的I/O需要;利用全局日志缓冲和成组提交方式减少了日志带来的磁盘I/O;检查点的设计利用了影子页面，结合了事务一致性检查点和模糊检查点的优点，减小了检查点过程对事务的正常执行的影响。

2 主要数据结构和算法

2.1 主要数据结构

(1)脏页表:MMDB中的每个页面具有一个外页头，存储了该页的相关信息 (如页号、是否为脏页，影子页面指针等)，内存池页面管理器通过外页头来对页面进行组织。内存池中维护了一个脏页表，当页面被修改后即将该页的脏页位置1并加入脏页表。在检查点线程将脏页刷入磁盘后，将脏页位置0。脏页表中的所有页面将在下一次检查点的时候刷入磁盘数据库文件。

(2)事务信息表:事务管理器每一个新接收的事务将其加入事务信息表，表中记录了事务的标识号TransID，事务状态标识TransState和日志头指针，其中事务状态包括1开始，2提交，3夭折，4完成。日志头指针指向事务的私有日志。

(3)事务私有日志:图2是事务日志的格式，事务的日志共有3种类型:事务开始 (TransBeginLog)，Redo节点(TransOperationLog)和事务提交 (TransCommit)。TransBe-ginLog中记录了事务的ID号以及日志的长度 (LogLength);TransCommitLog中记录了事务完成时的时间戳。事务进行的Redo日志其实是一个数据操作链表，每个链表元素是一个TransOperationLog结构体，记录了这个操作的类型及相关数据。事务执行时，为每一个事务建立一个链表，记录下事务需要对数据库进行的所有修改，当事务提交时，链表中的操作会被依次执行，当事务夭折时，删除链表。

图2 事务日志格式

(4)全局日志缓冲:全局日志是一个临界区资源，提交的事务线程对其进行同步访问。事务将私有日志挂载到全局日志链时需先获得其写锁，不同事务按照提交的先后顺序将私有日志链挂载到全局日志链上去，这保证了数据库状态的一致性。当日志缓冲达到一定数量或者检查点线程通知将要开始一个检查点时，写日志线程将全局日志缓冲写入磁盘。

2.2 事务执行算法

本系统采取了日志驱动修改的方式来完成内存数据库页面的更新操作。对要更新的数据库页面，事务在提交前并不直接进行修改，而是将所有的更新操作都记录在私有日志里。如果事务成功提交，内存页面管理器根据事务的私有日志对内存中的数据库页面进行修改;如果事务失败，则丢弃事务的私有日志，内存数据库不会受到任何影响。由于没有对内存数据库的页面直接进行修改，所以不必记录事务的Undo日志。

系统接收了一个新的事务后，将其加入事务信息表，由TransState标识事务的状态，事务开始执行阶段的算法如下:

输入:事务ID，事务私有日志指针

输出:执行成功返回_OK，失败返回_Error。

步骤1 在事务日志区写入一条TransBeginLog;

步骤2 获得事务要修改的页面的锁;

步骤3 将事务对页面的修改操作即TransOperationLog挂到事务的Redo日志链上，将LogLength加1;

步骤4 重复2和3，如果事务正常提交，则进入“事务提交”处理;如果事务失败则进入“事务夭折”处理。

“事务提交”算法描述如下:

输入:事务私有日志指针，待挂载全局日志缓冲，当前时间

输出:执行成功返回_OK，失败返回_Error。

步骤1 在事务私有日志链尾部写入一条TransCommitLog并记录时间戳，将TransBeginLog的Loglength修改为当前值;

步骤2 获得全局日志缓冲的锁，将事务的私有日志链挂到全局日志缓冲上;

步骤3 内存页面管理器根据事务的私有日志链将事务的所有修改执行，修改过的页的脏页位标识置为1;

步骤4 释放事务拥有的锁;

步骤5 将事务状态标识TransState标记为提交;根据先写日志规则，等待该事务对应的Redo日志全部刷新到磁盘后，事务才完全成功。

按照Redo日志的规则，修改数据库数据前应保证相关的日志记录都保存到了磁盘，因此，在步骤4时事务并没有完全结束，此时使用了预提交技术，在事务日志刷新到磁盘前就释放所有的锁，减小了事务对资源的竞争，提高了事务的并发度。

“事务夭折”算法描述如下:

输入:事务ID，事务私有日志指针

输出:执行成功返回_OK，失败返回_Error。

步骤1 将事务状态标识TransState标记为夭折;

步骤2 删除事务在内存中的Redo日志链表。

2.3 日志写入算法

全局缓冲日志写入磁盘的时机有两个，一是系统开始一个新的检查点前，通知写日志线程将所有的日志写入磁盘，二是当全局日志缓冲里的日志达到一定数量后成批写入磁盘。由于每个事务开始的日志中都记载了事务日志的长度，日志写入磁盘线程在取日志时以事务为单位取出，也就是同一事务的日志一定是在同一批被取出并写入硬盘。为减少日志写入磁盘线程和事务线程挂载日志时对全局日志缓冲的竞争，全局日志采取双缓冲队列的方式。日志写入磁盘线程的算法为:

输入:待写日志缓冲队列，待挂载日志缓冲队列

步骤1 检查当前待写日志缓冲队列是否为空，若不空则从当前日志缓冲队列中取出一组日志缓冲，若为空则转1.1;

步骤1.1检查待挂载日志缓冲队列是否为空，若不为空则获得其写锁，将其置为待写日志缓冲队列，将原来的待写日志缓冲队列置为待挂载日志缓冲队列，若为空则挂起;

步骤2 将取出的日志缓冲写入外存的日志文件中;

步骤3 释放取出的日志缓冲

步骤4 根据事务开始日志中TransID的值将事务信息表中对应的事务状态从提交改为完成;

步骤5 转步骤1。

2.4 检查点算法

由于检查点过程涉及到大量磁盘I/O操作，检查点的模式和执行频率对系统性能较大。本系统中，检查点是非连续的，启动的频率由系统中脏页比例决定，当脏页链中的节点数量与总页面数量之比达到一个阈值后，页面管理器唤醒检查点线程进行检查点操作。

Swallow的检查点方法借鉴了事务一致检查点的思想和影子页面的技术，在检查点进行过程中对MMDB加读锁，确保事务的一致性，同时利用影子页面来使检查点进行过程中事务对MMDB的读写不受影响，达到模糊检查点的效果。由于事务对MMDB的更改使用日志驱动的方法，因此当检查点线程成功获得脏页的读锁时，MMDB一定处于事务一致性的状态。检查点过程中，若有事务提交的页面仍被检查点锁住，内存页面管理器就复制一个被锁住脏页的影子页，事务提交的修改在影子页面上进行，修改完后将脏页链表中该脏页的影子指针指向影子页面，此后若还有别的事务对该页面进行操作，都从影子页面进行读取或操作。直到检查点释放了该页的锁后，用相应的影子页替代原来的页面，仍然置脏页位，这样在下一次检查点时会被刷到磁盘。

检查点算法如下:

输入:全局日志缓冲，脏页表，磁盘数据库映像

步骤1 检查点线程启动，获取全局日志缓冲的锁，并记录一条检查点开始的日志BClog，以区分检查点启动前后的日志;

步骤2 释放全局日志缓冲的锁;

步骤3 根据WAL规则 (磁盘数据库被更改前必须先记录Redo日志)，将BClog之前的事务日志都刷新到磁盘日志中;

步骤4 获取脏页表中所有脏页的读锁，依次将脏页复制到临时缓冲区，释放读锁，脏页位置0，然后将临时缓冲区的数据刷新到磁盘数据库的对应页面上;

步骤5 获取全局日志缓冲的锁，写入一条检查点结束的日志EClog;

步骤6 释放全局日志缓冲的锁;

步骤7 在日志文件的头结构中记录下本次BCLog在日志文件中的位置，即LastBC;

步骤8 通知页面管理器将所有的影子页面替代原页面(影子页面的脏页位已由事务在修改时置为1)。

至此，一个检查点过程已经完全完成。以下分析证明这个检查点是事务一致的 (见图3):

图3 检查点与系统故障

(1)在BCi之前已经提交的事务T1，它的日志在检查点启动时已强制刷入硬盘，T1对MMDB的修改也已在BCi之前完成，检查点将其产生的脏页刷新到了磁盘;

(2)在BCi之前已经启动但是尚未提交的事务T2，在BC前并未修改MMDB，BCi后它对MMDB的修改反映在MMDB的影子页中，因此这一次检查点中不会记录T2对MMDB的影响;

(3)在BCi之后才启动的事务T3，与T2同理，它对MMDB的影响不会被检查点所记录。

由上可知，在检查点完成之前提交的事务信息已全部由检查点刷入磁盘，磁盘备份目前的状态是BC时MMDB的一个事务一致性映像。因此在BC之前的磁盘日志文件已经没用了，为节省空间可将其删除。

2.5 检查点算法

对于事务故障，由于事务在提交前并未将其对数据库的修改反应到MMDB中而只是记录在私有Redo日志里，因而事务故障时只要丢弃事务在内存中的Redo日志链即可，并不涉及磁盘I/O或MMDB读写，因此恢复过程非常迅速。

对于系统故障，恢复包括重装和重做两个阶段。即将磁盘中的数据库映像加载到内存，再根据Redo日志对数据库做Redo操作。系统故障发生的时间可能在检查点过程中和非检查点过程中，如图3所示。

(1)若系统故障发生时不在检查点过程中，如图中故障1，由检查点算法可知，此时磁盘数据库备份的状态是ECi时的状态，也就是BCi之前提交的事务对MMDB的修改已刷新到磁盘，之后提交的事务尚未反映到磁盘中，因此将BCi作为重做的起始点，从磁盘日志文件中读取BCi之后的Redo日志对MMDB进行Redo操作。

(2)如果系统故障发生在检查点过程中，如图中故障2，此时磁盘数据库备份已刷入了部分在BCi后提交事务产生的脏页，但并不完整，因此仍需要从BCi开始重做。

综上，系统故障后恢复的重做起点是最近一次完整的检查点的开始位置处，也就是上文我们在磁盘日志文件里记录的LastBC。因此恢复的算法为:

步骤1 将磁盘的数据库映像导入内存;

步骤2 从LastBC处开始读取Redo日志，根据Redo日志链对数据库做Redo操作。

3 性能测试及分析

Swallow的恢复机制通过在事务提交、日志和检查点上的研究与设计，使得内存数据库在遇到事务故障和系统故障时能够快速得到恢复，并且该机制不会对系统的性能造成太大的影响，通过实验测试，对比了Swallow和开源内存数据库 FastDB、SQLite的恢复机制及系统性能。其中，FastDB有两种运行模式，磁盘模式和无盘模式，前者会产生磁盘文件，后者则不产生磁盘文件，仅在内存中操作;类似地，SQLite同样有内存模式和磁盘模式。Swallow分别测试在恢复机制正常运行以及关闭恢复机制，在内存索引结构中进行操作时的性能情况。

测试环境:PC机，Intel双核处理器，主频2.40GHz，内存1G

软件环境:

(1)自主开发的空间实时内存数据库系统Swallow、用于对比的内存数据库FastDB、SQLite。(2)编写随机数据生成程序用于产生实验数据，数据内容为Key-data记录，单条记录长度不大于10字节 (3)编写测试程序分别调用以上数据库的接口进行实验

实验方法:

(1)通过随机数据生成器生成10000条和100000记录分别插入数据库，每次插入作为一个单独的事务，计算出数据库的平均事务处理能力TPS;

(2)通过非正常退出程序来模拟系统崩溃，记录恢复需要的时间。

测试结果如表1所示。

表1 内存数据库性能测试结果

实验结果可以看出，在不加入恢复机制的情况下三款数据库的TPS在一个数量级上，但FastDB和SQLite在使用磁盘数据后性能下降非常巨大，这是频繁的磁盘I/O带来的。Swallow在自动进行检查点和日志记录的情况下性能也有所下降，但相比其它两个数据库高出了一个数量级。在这个机制下，Swallow的系统故障恢复时间与FastDB和SQLite相比相差并不大，数据损失率则由事务级增加到日志成组提交的每组大小。考虑到系统故障的发生概率较小，而牺牲的少量数据保证了系统性能的大幅度改善，这个恢复机制是有着良好的表现的。

4 结束语

本文设计了一个空间实时内存数据库Swallow的恢复机制，综合了日志驱动修改、影子页面、预提交和模糊检查点的思想，达到了日志、检查点过程不影响事务并发执行，减轻磁盘I/O对系统效率的影响。日志驱动修改使得系统无须记载Undo日志，事务故障不需要回滚即可直接恢复，系统故障后也能迅速确定恢复起点，在保证数据库可靠性的同时也降低了对系统实时性的影响。

［1］Hector Garcia-Molina，Jeffey D Ullman，Jennifer Widom.Database systems:The complete book［M］.Upper Saddle River，New Jersey:Prentice Hall，2008.

［2］WANG Shan，XIAO Yanqin，LIU Dawei，et al.Research of main memory database ［J］.Computer Applications，2007，27(10):2353-2357(in Chinese).［王珊，肖艳芹，刘大为，等.内存数据库关键技术研究 ［J］.计算机应用，2007，27(10):2353-2357.］

［3］GAN Shan，GUO Lili.Research on access mechanism of real-time memory database systems for space:MCacheTree［J］.Computer Engineering and Design，2010，31(17):3827-3830(in Chinese).［甘杉，郭丽丽.航天实时内存数据库存取机制MCacheTree的研究 ［J］.计算机工程与设计，2010，31(17):3827-3830.］

［4］HUANG Lin，LU Jing，LIN Zhong.Recovery method for main memory database systems based on shadow paging［J］.Computer Engineering and Design，2008(5):2470-2473(in Chinese).［黄琳，路京，林中.基于影子页面的MMDB的数据恢复方法［J］.计算机工程与设计，2008(5):2470-2473.］

［5］FENG Yuao.Fault recovery strategy research on the real-time embedded memory database ARTs-EDB［D］.Wuhan:Huazhong U-niversity of Science and Technology，2008(in Chinese).［冯宇傲.嵌入式实时内存数据库ARTs_EDB的故障恢复策略研究［D］.武汉:华中科技大学，2008.］

［6］XIAO Y Y，LIU Y S，LIAO G Q，et al.Real-time commitment in one-phase for distributed real-timetransactions［J］.Journal of Huazhong University of Science and Technology(Nature Science Edition)，2006，34(3):1-4.

［7］CHEN Anlong.Research and implement of recovery in main memory database［D］.Ningbo:Zhejiang University，2006(in Chinese).［陈安龙.内存数据库中数据恢复技术的研究与实现［D］.宁波:浙江大学，2006.］

［8］QIN Xiongpai，XIAO Yanqin，CAO Wei，et al.A parallel recovery scheme for update intensive main memory database［C］//Otago:PDCAT，2008:509-516.

［9］XIAO Yingyuan，LIU Yunsheng，LIAO Guoqiong，et al.A realtime dynamic database crash recovery strategy［J］.Journal of Software，2007(10):2516-2527(in Chinese).［肖迎元，刘云生，廖国琼，等.一种实时动态数据库故障恢复策略［J］.软件学报，2007(10):2516-2527.］

［10］LI Zhengyu，CHEN Lei.Research on the testing method and performance evaluating and testing for database［J］.Electronic Design Engineering，2011(2):4-6(in Chinese).［李征宇，陈磊.数据库性能评测指标及其测试方法研究［J］.电子设计工程，2011(2):4-6.］