南阳师院第十三届“张衡杯”大学生课外学术科技作品竞赛
申报作品
一种内存数据库快速日志恢复技术研究
姓 名： * * * 学 号： 12345678900 专 业： 网络方向 院 系： 计算机与信息技术学院 指导老师： * * *
摘 要
恢复技术是保证内存数据库运行可靠的关键，传统的基于日志的恢复技术会对系统性能产生很大的负面影响。针对此提出了内存数据库系统快速日志恢复技术，它控制日志的产生数量，使得在系统崩溃并重新启动时，能以最快的速度恢复到系统崩溃前的最近一致点上。
关键字：内存数据库；日志恢复；检查点
Quickly Log Recovery Technology Of MMDB
Hu Hui hui (1.College of Computer and Information Technology, Nanyang Normal University,
Nanyang 473061, China; 2.College of Compuert Science and Tecnology,Beijing University of
Tecnology,Beijing,100022,China)
Abstract The recovery technology is a key to ensure running credibility of MMDB，the tradition recovery technology is based on log may raise the effect on system performance.This paper puts force the a quickly log recovery technology。It controls log quantity and recovers the system to the nearest breakdown point as fast as it can, when system breaks down and restarts.
Key Words: MMDB; log recover; checking point.
目录
引言
内存数据库（MMDB）把数据全部或者当前工作部分驻留在内存中，消除了传统磁盘数据库系统中I/O瓶颈，提高了系统的性能和吞吐量，但是由于所有操作都作用于内存数据库的主拷贝上，数据库极易遭到操作系统和应用软件造成的破坏，因此MMDB的恢复技术十分关键[1]。日志（Logging）恢复是传统的MMDB恢复技术之一，它能满足当前MMDB系统对事务响应和快速系统恢复的要求，但是在大量事务吞吐量情况下造成的日志暴增带来很大问题，会对MMDB性能产生很大影响[2]。
本文提出MMDB系统快速日志恢复技术，它是在不阻碍系统正常运行的情况下，控
1 制日志的产生数量，使得在系统崩溃并重新启动时，能以最快的速度恢复到系统崩溃前的最近一致点上。
1 系统构架设计
快速恢复模型的整体架构如图1所示。事务处理模块负责根据用户请求产生事务，并由事务管理器调度。事务管理器将负责各个事务的日志记录，交给日志产生规则处理。检查点模块根据日志产生规则产生的日志数量动态调整检查点启动时间[3]。当日志记录数达到一定值时，检查点程序启动。它读取所有日志记录，交给日志筛选器。日志筛选器根据筛选算法，从当前所有日志项中筛选出实际有效的日志记录，并将这些有效日志记录交给日志分发结点。日志分发结点主要做两项工作：第一是它将日志传送给日志磁盘管理器，由其负责将日志回写到日志磁盘上，第二是日志分发结点将日志传送给备份更新发生器。备份更新发生器利用快速恢复算法，触发各类更新操作，根据日志更新磁盘上的数据。 该快速恢复模型具有如下的特点：
①快速恢复模型以日志驱动方式做检查点，异步更新磁盘上的备份数据镜象。 ②系统只维护全局Redo日志，以Redo日志来驱动备份更新发生器，各个事务维护私有Redo日志和Undo日志在事务提交时将私有Redo日志写入全局Redo日志中。
事 务发生器日志筛选算法事务管理器事务处理日志产生规则日志分发结点快速恢复算法日志回写归档磁盘日志磁盘检查点处理
图1 快速恢复模型的整体架构
③使用日志筛选算法，近一步减少Redo日志的数量，提升检查点程序的性能。 ④备份数据镜象只反应已提交事务的更新状态，因此在系统重载时不需要回退未提交的事务。
⑤快速恢复算法为并发重载算法。在系统恢复过程中，能继续接受新事务的请求。
2 快速日志驱动检查点
快速日志驱动检查点的基本思想是，检查点程序仍然由日志来驱动，根据读取到
2 的日志项来更新数据镜象上的内容，维持数据镜象与内存中数据库的基本同步。但是，与以往日志驱动检查点算法不同的是，它通过日志产生规则和日志筛选算法两个策略克服了以往日志驱动检查点算法中日志数量可能过快增长的问题[4] [5]。
2.1 日志产生规则
快速日志驱动检查点算法中设立的日志产生规则是：系统中日志被分为全局日志和私有日志两类。系统只维护全局Redo日志，而不维护Undo日志，由事务自身维护私有的Redo日志和Undo日志。在事务提交时，依照事务提交的先后顺序，将事务的私有Redo日志添加到全局Redo日志中。因此，在事务运行过程中，会产生Redo日志和Undo日志。Redo日志用于在系统恢复过程中，重做已提交事务。而Undo日志用于在事务Abort时回退事务，或者在系统恢复过程中回退未提交的事务。如果恢复模型的设计能够保证系统恢复过程中，没有需要回退的未提交事务，那么系统只需要读取Redo日志而不需要读取Undo日志。因而系统只需要维护全局的Redo日志，而不需要维护Undo日志，将Undo日志交给事务自身维护，Undo日志只用于事务自身Abort时回退。这样就可以减少全局日志的总量。
图2具体描述了全局日志和私有日志的使用。在事务T1，T2， T3的内存空间内，各自维护自己的私有Redo日志和Undo日志。在非易失性内存(SRAM)上，MMDB系统开辟全局Redo日志缓冲区，让事务在提交时事务的私有Redo日志写入该缓冲区。检查点程序将定期读取日志缓冲区中的数据，将日志写入磁盘，并驱动检查点程序更新磁盘镜象数据。
Redo Log事务T1Undo LogMMDBRedo Log事务T2Undo LogRedo Log事务T3Undo Log私有日志SRAMRedo全局日志缓冲区
图2 全局日志和私有日志
各事务将按如下阶段操作日志：
①事务启动时，需要在事务的各自空间内建立私有Redo日志和私有Undo日志，并将在私有Redo日志中写入事务启动记录。
3 ②事务运行过程中，事务的每次更新操作，需要在私有Redo日志中添加Redo记录，并在私有Undo日志中添加Undo记录。 ③事务提交时，需要按如下步骤完成：
㈠向事务的私有Redo日志内添加事体Commit记录。 ㈡将事务的私有Redo日志写入全局Redo日志中。
㈢释放事务的私有Redo日志和私有Undo日志，释放事务所占用的其他资源，完成提交。
④事务Abort时，需要按照如下步骤完成：
㈠事务反向扫描私有Undo日志，回退事务的更新操作。
㈡释放事务的私有Redo日志和私有Undo日志，释放事务所占用的其他资源，结束事务。
由此可见，事务只在提交时才将私有Redo日志写入全局日志缓冲区。从而也保证了检查点程序运行时，只看到己提交事务的Redo日志，磁盘上的数据镜象也只反映已提交事务的更新操作。
2.2 日志筛选算法
用日志产生规则能明显减少日志产生的数量，但是在更新事务吞吐量较大的情况下，检查点程序从全局日志缓冲区读取Redo日志时，仍然可能会面对Redo日志量过大的问题，产生的原因是这样的：如果对一份数据做两次更新操作，那么两个事务各自产生一条对同一物理地址上值更新的物理日志，但只有第2次更新事务产生的日志为有效的。本文利用日志筛选算法来避免日志量过大问题，该算法认为，当LOG1（T1，addr，valuel）和LOG2（T2, addr, value2）按照事务的提交顺序通过日志筛选器时，当T1的提交时间在T2提交时间前，那么只有LOG2（T2, addr, value2）被认为是有效，而LOGI（T1，addr，valuel）被忽略。日志筛选器需要关注物理日志中被修改值的地址的相关性。对相同修改地址的物理日志依据日志的提交顺序进行筛选，该算法的示意图如图３所示。为加快日志的筛选速度，将全日志缓冲区划分为多个区域，这将日志记录中操作地址具有空间相关性的日志按照所属事务的提交顺序聚合在一个区域内，能加速日志筛选算法的筛选速度。使得在筛选过程中，只需在小范围内（也就是一个区域）搜索可以被筛选的日志。当全局Redo日志缓冲区中的某一个区域满时，就唤醒检查点程序，将这一区域中的Redo日志写入日志磁盘，并驱动备份更新发生器更新磁盘上的数据镜象。 [6]
T(1) Page 3T(1) Page 5T(1)T(1)T(1)Page 3Page 5Page nT Commit事务T(1)日志序列日志检查与分配T(m) page 0T(m) page 0Page (0~3)Page (4~7)T(1) Page nT(k) page mPage (n~n+3)Page (k~k+3)全局Redo日志缓冲区图3 日
图3 志筛选算法
3 快速恢复算法
在系统崩溃后，MMDB系统需要通过恢复过程，将数据库恢复到崩溃前的最近一致点上。在系统恢复过程中，重载程序将数据从磁盘镜象上加载到MMDB系统中，同时根据日志，重做（Redo）或者取消（Undo）部分事务，来恢复数据库的一致性。 快速恢复算法如下：
①当系统崩溃重启时，先启动日志检查和分配程序，检查非易失性内存（SRAM）中提供给事务提交时用于写入私有Redo日志的缓冲区中是否有完整写入的Redo日志。如果有完整的Redo日志，则日志检查和分配程序将这些完整的日志分配到全局Redo日志缓冲区的不同区域中。
②统计全局Redo日志缓冲区中的日志数量，并标记这些日志。当前Redo日志缓冲区中的日志将被用于恢复内存中MMDB系统的一致性，同时也要用于维护磁盘上数据镜象的一致性。
③恢复程序从磁盘数据镜象上加载一些重要的系统表以后，MMDB系统可以启动，并可以接受新事务的请求。系统的正常事务处理和系统恢复过程同时进行。 ④触发检查点程序从全局Redo日志缓冲区中读取日志，驱动备份更新发生器更新磁盘上的数据镜象。在这个过程中，驱动备份更新发生器向缓冲区管理区询问将被更新的记录所在的镜象数据页面是否已经被加载到内存中。如果己经被加载，则不但需要更新磁盘上的镜象数据页，还需要更新内存中的数据页面。如果全局Redo日志缓冲区中所有被标记的日志都已经被用于驱动备份更新发生器，那么此时备份更新发生器可以告诉重载程序恢复工作已经完成，没有其他镜象页面需要更新。
⑤MMDB在接受新事务的请求时，对于事务所访问到的数据，如果数据还没有被加载到内存中时，则系统向重载程序要求将所需数据从磁盘镜象上加载到内存中。此时，重载程序先要检查要求加载的数据页面是否会被备份更新发生器修改。如果是，则需
5 要等待备份更新发生器更新镜象页面后再加载到内存中，否则就直接将镜象页面加载到内存中。
⑥当所有镜象都加载完成后，MMDB系统恢复过程结束。
4 结束语
恢复技术是保证内存数据库运行可靠的关键技术。传统日志恢复技术由于存在产生过多不必要的日志的缺点，对系统性能带来负面影响。本文研究了一种新的日志恢复技术来尽可能的减少日志数量，并在此基础上提出了快速日志恢复算法，此恢复技术算法简单可以大大的节约系统的资源。然而，内存数据库恢复是一个十分复杂而庞大的技术，所以该方法还有待完善。
参考文献
[1]刘云生，潘琳.实时数据库系统的内存数据库组织与故障恢复[J].小型微型计算机系统.2005,22(5):611-613.[2]刘云生，廖国琼，付蔚.一个支持实时内存数据库的恢复系统[J].小型微型计算机系统.2003,24(3):460-464 [3]SONGGH，YANHCS，SHIJY.ZEDB：An in-memory database system for real-time meage proceing applications [A].Proc of the 6th Int Conf on Computer Aided Design & Computer Graphics (CAD/CG\'99)[C].Shanghai: Wen Hui Publishers 1999.238-242.[4]LiX,EichMH.Post-crash log proceing for fuzzy check pointing main memory databases[J].Proc Of Int Conf on Database Engineering，IEEE，1993,117-124.[5]龙玉国,耿协坚.嵌入式实时内存数据库恢复子系统的设计[J].计算机工程与应用.2004,17:179-180 [6]宋广华,杨长生.基于混合日志的内存数据库恢复子系统[J].浙江大学学报(理学版).2001,28(3):164- 168
