一种新的嵌入式内存数据库的设计方法

0引言

随着硬件的发展，内存的容量在不断扩大，人们长期思考的将全部或大部分数据存放在 内存中运行成为可能。同时，嵌入式设备在日常生活中得到广泛应用，如何对其内部日益繁 多的数据进行管理显得很关键。当前嵌入式内存数据库产品很多，大多数产品由于各方面的 限制，在性能和市场前景方面表现欠佳。在嵌入式内存数据库研究领域，新的存储与索引方 法被不断提出，同时面向对象的程序设计语言java作为当前主流开发语言，在多线程和死锁 处理方面有其独特之处，为提出新的嵌入式内存数据库的设计方法，及基于事务模型的恢复 方法提供了可能。

1嵌入式内存数据库概述

嵌入式内存数据库的设计一般采取两种思路：一种是对传统的大型数据库进行裁剪和改 进，很多处理问题的方法仍采用传统数据库的方法，某些方法在嵌入式内存数据库不适用则 做些稍微改进，这种思路没有逃离传统数据库设计思想的束缚。另一种则是根据嵌入式内存 数据库自身的特点，提出新的体系结构，存储结构和恢复机制，以满足嵌入式内存数据库的 要求。目前，第二种方法被普遍采用和推崇，本文新的设计方法就采用后者。


1.2嵌入式内存数据库的体系结构

在新的体系结构中，我们采用关系数据模型，最上层提供外部查询接口，支持多种常用 语言如C,java等语言连接数据库。第二层是对SQL语句进行解析的查询命令分解与优化层， 这一层下面是两个重要的模块：数据组织与管理和事务管理器。其中，数据组织与管理模块 完成常用的索引和数据组织工作，事务管理器具有创建事务，调度事务，回收事务的功能。 内存工作区是该体系结构最重要的模块，全部数据操作及日志处理在这里进行，它在事务处 理时为每一个事务分配一个内存工作区，其中存放数据和日志。日志管理器管理内存工作区 中的日志，而恢复管理器则在系统出现故障时起作用。该数据库大部分操作在内存工作区中 运行，只有当发生检查点操作和数据库备份，及系统恢复时才与外面的磁盘打交道，因此该 数据库是典型的嵌入式内存数据库。上述体系结构图如图1所示：


2．数据的存储与索引

嵌入式内存数据库通常在内存受限的环境中进行，CPU能直接操纵内存中的数据，且数 据经常由于各种故障而丢失。因此合理的有效利用内存资源，减少内存开销和CPU指令数， 使内存空间得到高效利用很关键，为此我们引用了一种新的存储与索引方法--T树。

T树是将AVL树和B树结合在一起而得出的一种新的数据结构，T树也是一种二叉树，只不 过每个结点(称为T结点)都包含多个元素。每个T结点都包含一系列从小到大排序后的元素和 三个指针，指针分别指向父结点和左右结点。某一T结点A的左结点中必会包含比A结点中最 小元素小的最大元素，而A结点的右结点中必会包含比A结点中最大元素大的最小元素。因为 是二叉树，所以T树具有AVL树固有的二分查找特性，又因为每个结点包含多个元素,其又包 含了B树良好的更新和存储特性的优点。对T树来说，因插入和删除数据所造成的数据移动通 常可以局限在一个结点内进行，和AVL树一样，T树也是通过旋转来使树达到平衡的, 但其所 需要的旋转操作的次数远少于AVL树[ 2 ]。T树结点结构如图2所示:


3基于事务处理的恢复模块设计

本嵌入式内存数据库，我们采用了基于多线程的事务模型，利用java语言作为开发语言， Eclipse3.2为开发工具，充分采用java语言的多线程机制和面向对象的思想来开发数据库。

在该事务模型中，我们将事务作为一个线程来看待，理由如下:(1)java语言有自己独特 的多线程机制，具有开始状态，各种活动状态，结束状态，把线程作为一个事务整体运行， 能够满足事务需求的各种操作，及自身的ACID属性。(2)java语言有多线程处理时的同步操 作，事务处理时可以利用这种思想处理多事务之间的并发控制操作[ 3 ] 。我们利用事务管理 器创建事务，并在影子内存工作区为每一个事务分配相应的影子内存工作区，其中包括该事 务应处理的数据和日志，可以说该模型是影子内存技术和日志处理技术的完美结合。其中， 新的事务模型和处理机制如下图3所示。


3.1 日志操作

对每一个事务Ti分配一个内存工作区WAi，兼做影子内存和日志两种功能。在事务进入 提交状态之前，将修改记录放入影子内存中，当Ti进入提交状态时，由提交处理根据WAi中 的记录对MDB作相应修改。我们称这种修改为"日志驱动修改"。当某一事务Tj由于某种原 因夭折时，只需释放其相应的影子内存工作区WAj即可, 而无需对数据库进行UNDO操作。因 此在本文中我们采用Redo日志。这样，不仅可以大大节省内存空间，同时也简化了Abort(夭 折)处理。同时，为了便于对影子内存工作区的管理,给每一个影子内存工作区WAi设置一时 间戳TWAi,用来表示对应事务提交过程结束的时间。在处理日志提交时，我们充分利用事务 预提交和组提交的优点来设计。具体过程如下，每一个已提交事务的WAi进行预提交，按时 间先后顺序组成链表LiST(WAi)，其结构如下:

事务进入提交阶段，提交处理(COMMIteR)对MDB作"日志驱动修改"。当上述事务都完成时，进行一次组提交，将上述事务的处理结果和日志写入磁盘，这样可以减少磁盘I/O操作的次数。

3.1.1事务提交算法

事务提交具体算法如下：设WAi为活动事务Ti的影子内存工作区，则事务Ti在时刻t的提 交处理算法为COMMITER(WAi，t)[ 4 ]。
输入：WAi--事务Ti的影子工作区；t--某一个时间点。
输出：0--执行成功；1--执行失败。
步骤: ①依据WAi中的记录，对内存中所有要被事务Ti修改的数据块执行上锁操作；② 对已上锁的数据块, 根据WAi中的记录执行相应的更新操作；③在WAi中写入一个提交记录； ④用当前时间t为WAi设置时间戳TWAi；⑤将WAi加入到影子工作区队列的尾部；⑥将事务表 中该事务的状态标志位从运行状态改为提交状态；⑦对在步骤①中上锁了的数据块解锁。

3.1.2日志提交算法

在事务处理中，用于恢复的日志对WA的处理算法为LOGGER(WAq)，日志提交算法如下：
输入：WAq--影子工作区队列。
输出：0--执行成功；1--执行失败。
步骤：①检查WAq 是否为空,若不空,则从队列头取出第一个影子工作区WAx；若为空， 则挂起；②将WAx中的记录写入外存的日志文件LOG中；③释放WAx；④将事务表中相应于WAx 的事务的状态标志位从提交改为撤销；⑤转步骤①循环执行。

3.2检查点操作

检查点操作包括静止检查点和非静止检查点。静止检查点要求操作过程中，数据库处于 静止状态，检查点结束后，开始新的事务。在嵌入式内存数据库对实时性要求很高静止检查 点很明显不能满足要求，因此我们采用非静止检查点。

在CHECKPOINT操作期间，由于采用的是Redo日志，提交事务所做的修改拷贝到磁盘的时 间可能比事务提交的时间晚得多，且采用预提交和组提交技术，我们要考虑检查点发生时的 活动事务，及在检查点进行前将影子内存工作区中，已提交的事务和日志刷新到磁盘中作为 备份。执行检查点的步骤如下[5 ]：


3.3重装与恢复

恢复涉及到两个步骤，首先是重装，将数据库备份装入MMDB 中；然后是恢复，根据日 志和检验点执行相应操作使数据库恢复到系统崩溃之前最近的一致性状态。检查点可以帮我 们缩小日志的范围，减少日志占用的空间资源，根据最后一个检查点记录是START还是END， 有以下两种情况。