轻量级内存数据库研究

1背景 随着改革开放以来我国各行各业信息化的飞速发展，我国军事信息化也有很大的进步，随着从军事日常到战时、从后方到前方、从上级到基层等所有军事业务日益深入的信息化，以及指挥功能的日益电子化、流程化，现有主要以大型磁盘数据库为存储方式的状态已

1     背景

随着改革开放以来我国各行各业信息化的飞速发展，我国军事信息化也有很大的进步，随着从军事日常到战时、从后方到前方、从上级到基层等所有军事业务日益深入的信息化，以及指挥功能的日益电子化、流程化，现有主要以大型磁盘数据库为存储方式的状态已经不能完全满足电子战、无人战争、闪电战对数据的大批量、快速访问的需求。迫切需要一个能够实现快速数据访问的机制。

微观上，目前应用程序可能原来根本不用数据库，而把数据保存在文本文件中，但随着需求的越来越复杂、数据的越来越庞大，应用在数据存储方面的处理逻辑也会越来越复杂，运行效率也越来越低，因此如果有一个能和存取本地文件一样快速、且更加便利、透明化的数据存储机制，就能够解决应用发展的问题。

本文就以此为出发点，设计了一个能够快速反应的轻量级内存数据库系统，并说明了该系统的主要关键技术与主要环节的设计方案。

2     概述

2.1    轻量级内存数据库的定义

轻量级内存数据库，是一个较新的研究领域,目前对轻量级内存数据库还没有权威、公认的定义。其主要特点是其主拷贝或“工作版本”常驻内存。轻量级内存数据库是在传统的磁盘数据库技术基础上发展而来的，是将数据库保存在内存中，避免经由缓冲区管理器对数据的间接访问，使轻量级内存数据库比传统的磁盘数据库系统拥有更好的响应时间和吞吐量。目前，国外已经有了轻量级内存数据库的产品，但还没有一个产品能象Oracle、Sybase、SqlServer、DB2一样能被业界所公认与广泛使用，多数轻量级内存数据库都还是停留在实验室的研究阶段，轻量级内存数据库技术的应用就更不广泛了，其原因是还有很多需要进一步研究的技术问题。

2.2    轻量级内存数据库的的优点

传统的基于磁盘的关系数据库的特点都已经被业界所广泛接受了，而轻量级内存数据库是新事务，它不能替代传统关系数据库，但它在一些特定的场合中有比传统关系数据库体积更加小、管理成本更低、效率更快的特点，下面将描述轻量级内存数据库相对与传统关系数据库的主要优势：

1） 由于内存和磁盘的访问效率有很大的差距，导致内存数据库的主存的访问速度是纳秒级而磁盘的访问速度是毫秒级；

2） 由于省去了磁盘访问的I/O调用，内存数据库主要是内存里面的指针操作，因此对CPU指令的调用大大减少了；

3） 事务处理无需I/O，极大提高了系统性能；

4） 不再需要缓冲区管理器，消除了磁盘和内存之间数据拷贝开销；

5） 在数据组织与管理中，广泛使用指针，简化了内存管理，降低了空间开销

3     轻量级内存数据库的设计

轻量级内存数据库是数据库的一种，它的主要功能与传统关系数据库一样，也是完成数据的组织、访问、维护功能。本系统以CPU和内存空间的高效利用为设计目标，具备常规数据库的主要管理功能，包括数据的DML、DDL、数据库事务、备份、恢复等；在数据标准上，遵从标准的SQL92标准；具有一定的安全性；支持绝大多数的数据类型；在接口与使用上与普通数据库一样，都可以使用ADO编程；在性能上，内存数据库通过把用户进程直接把整个数据库映射到它们的本地地址空间并直接访问数据，避免了在当今典型磁盘商用数据库中的昂贵的远程过程调用和缓冲区管理器之间的交互。

3.1    体系结构

轻量级内存数据库的系统体系结构如下图所示：

 

 

 

3.2    功能模块描述

3.2.1      应用层

应用层主要包括使用轻量级内存数据库作为数据处理机制的所有应用程序，这些应用可能原来是用大型关系数据库来保存数据的，但大型数据库的运行效率可能达不到应用的需求；也可能原来是以文件为存储的，但文件的存储方式比较复杂，要应用自身来处理数据存储的逻辑。采用本文的轻量级内存数据库就能很好的解决这些问题，即能提高效率，又能降低数据存储的逻辑。

3.2.2      外部接口层

为了提高轻量级内存数据库的可用性，必须对外提供C以及C++访问接口，目前数据库访问最简单、方便的接口就是ADO接口，因此，本内存数据库必须提供OLE DB接口，基于OLE DB接口，DELPHI、Visual C++、VB程序也可以方便使用内存数据库了。

3.2.3      事务管理层

轻量级内存数据库的事务处理包括事务预分析、并发控制、调度管理、恢复机制，内存数据库的重要特性是高效率，因此，这里的事务处理除了完成事务逻辑一致性与时序一致性的功能外，还要有高效率。

（1）事务调度。内存数据库系统是用来处理具有高效率的工作负载的事务处理系统，主要表示要满足事务的持续时间。包括事务对各种资源的调度，及对各个事务占用CPU的调度，多个并发运行事物之间的数据、I/O和内存等资源的调度。

（2）并发控制。与传统的数据库相同，内存数据库中的事务并发运行并存取共享数据因此彼此潜在的存在相互干扰，导致更新丢失、数据不一致、级联回滚等问题。并发控制就是要控制并发事物之间的相互作用，使实时数据库的一致性不被破坏。

本系统的并发控制是基于锁机制的。加锁对象的大小称为锁的粒度，一般可以对整个数据库、关系、页或记录进行加锁。锁的粒度小则并发程度高，维护锁的开销也大；锁的粒度大，并发度低，维护锁的开销小。锁的类型有共享锁S与排它锁X。有的系统为解决多粒度加锁问题引入意向锁概念，对任意结点加锁时，必须先对它的上层结点加意向锁，相应地增加了意向共享锁IS、意向排它锁IX。为了使用方便，将共享锁与意向排它锁结合在一起形成SIX锁。申请加锁应按自顶向下的次序；释放锁时应按自底向上的次序进行。

（3）恢复管理。指在事务失败时，努力将数据库恢复到正确状态

3.2.4      数据存储层

数据存储层的主要功能是处理对数据的访问，包括内存数据库本身的状态以及应用的数据，它包括数据定义、数据存取、数据处理、日志管理、配置文件管理、T树索引这些模块。

（1）   数据定义：该模块主要功能是用来管理内存数据库的数据字典的，它包括数据字典的插入、删除、修改操作；

（2）   数据存取：该模块是负责对用户数据进行快速存取的，包括用户数据的添加、删除、修改、查询操作；

（3）   数据处理：该模块是用来对用户数据进行类型转换、数据合法性检测、主键唯一性检查、约束冲突等功能；

（4）   日志管理：引入日志管理的主要目的是提高轻量级内存数据库的可靠性，以便在遭遇应用崩溃时，能够进行恢复操作，因此就在日志中记录内存数据库做过的所有操作与数据。

（5）   配置文件管理：本系统中的配置文件是保存了对数据库运行策略参数的文件。

（6）   T树索引管理：T树是一种适用于内存数据库系统的索引结构，它是为了适合主存的存储特性而提出的一种索引。T树是结合B树以及AVL树的特征而成的平衡二叉树。 T树有三种不同类型的节点。具有两个子树的节点称为内部节点；具有一个孩子的节点称为半叶节点；不具有孩子的节点称为叶节点。对于每个内部节点N，除了包含一些元素和一些控制信息外，总有一个左（右）孩子指针指向的左（右）子树。当T树中节点按升序排列时，该节点中的最左元素是最小元素，该节点的最右元素是最大元素，任何左（右）子树节点中的元素都小于（大于或等于）该节点的最小（大）元素。本系统就是采用T树来进行索引的管理与存储的，因此，能大大提高内存数据库访问的效率。

 

3.2.5      资源管理层

资源管理层包括CPU管理、时间管理、内存管理、I/O调度管理。由于数据库事务是应用对数据库访问的核心主旋律，因此，资源管理的具体功能也将穿插在事务处理的各个功能中。这里资源管理包括一个I/O调度管理的原因是，因为内存数据库也包含一个操作日志文件，同时内存数据库在不活动状态时为了保持数据不丢失，最终要存储到磁盘中，这些文件都要保存在物理磁盘中的，因此，本内存数据库也有I/O调度的问题。

3.2.6      数据实体层

数据实体是所有的数据信息的存在形式，包括存储在内存中的内存数据字典以及内存数据、以及存储在磁盘中的日志文件、数据文件和内存数据库配置文件。

3.2.7      运行控制

运行控制是指为了让内存数据库正常运行，而必须具有的功能，主要包括内存数据库的加载、卸载、线程管理。

（1）   数据库加载：内存数据库并不要求所有数据都放在内存，而只要求数据的“工作版本在内存即可。数据的加载是为了满足事务的正常运行，加载时，也是需要按照一些参数进行判定的。

（2）   数据库卸载：本模块的功能是在内存数据库在任务运行结束后，需要将内存数据固化到磁盘存储中。

（3）   线程管理：内存数据库的线程包括全局状态监控线程、用户事务线程、日志线程等。由于内存数据库一般都是以组件、动态链接库的形式存在的，不是以单独的运行进程而是嵌入在其他应用中运行的，因此，这就需要根据事件来管理内存数据库自身的线程。

4     轻量级内存数据库的关键技术

由于轻量级内存数据库在研究与实现的过程中所涉及的技术很多，包括数据组织、数据保护、内存数据库中的索引、日志策略、日志I/O瓶颈问题、检查点策略、数据库的重启装载、并发控制、SQL解析与组装等，由于篇幅与版面关系，我们在此不一一详述，下面我们只针对内存数据库的加载与T树索引进行说明。

4.1       轻量级内存数据库加载技术

本系统采用同步加载技术，使事务处理与大部分数据装载同步进行。这样就能大大地减少内存数据库的启动等待时间。

同步加载策略将传统数据库技术与内存数据库技术相结合，目的是使内存数据库能尽快响应事务请求，减少等待数据库加载而不能进行事务处理的时间，使系统能象基于磁盘的数据库系统那样在装载部分数据后就能响应用户的请求。当整个数据库同步装载完毕后，又能具有内存数据库的对于内存的高效访问。也就是，该技术继承了基于磁盘的数据库的较快速加载特性，也保留了内存数据库对事务的快速响应的优点。

下面是装载线程的算法。

1)申请获得数据库装载位图的锁。

2)顺序检查数据库装载位图，若发现（某些连续的）页不在内存中，重复下面的操作，直到这些连续的页面都在内存中。

a.释放数据库装载位图的锁。

b.获得装载锁。

c.对于这些连续的页面，当还有没装入的页面时。

a)申请数据库装载位图的锁。

b)重新检查该连续页面装载情况，得到真正未装载的页面范围

c)释放数据库装载位图的锁。

d)若还有没完成装载的页面，顺序装载这些页面。

d.申请数据库装载位图的锁。

e.更新数据库装载位图，反映最新的装载情况。

f.释放数据库装载位图的锁。

g.释放装载锁

h.申请数据库装载位图的锁

3)释放数据库装载位图锁。

 

4.2       T树索引结构的实现技术

前面曾提过，本系统使用T树来管理轻量级内存数据库的存储空间。

我们定义一个类TTree，用来对轻量级内存数据库的空间进行管理，它管理的范围包含第32个数据库页面后的所有数据库空间。这个区域中的每个自由空间都是该T树某个节点（Class fTtreeNode）内的一个元素。整个TTree的元素根据自由空间的起始地址按升序排列。另外，每个fTtreeNode里的控制信息还分别包含左子树、右子树和当前节点最长的自由空间，这些信息是为了方便地进行空间分配。fTtreeNode的成员变量如下：

offs_t left;            //左子树的指针

offs_t leftMaxLength;   //左子树中最大自由空间的大小

offs_t right;           //右子树的指针.

offs_t rightMaxLength;  //右子树中最大的自由空间大小

offs_t currMaxLength;   //该节点的所有元素中最大的空间大小

nat2 nItems;            //该节点的有效元素数

int1 balance;           //以该节点为根的平衡情况，为右子树比左子树多的层数

fTTreeItemitem[FREE_TREE_PAGESIZE];//存放元素的数组

其中，left和right为数据库的偏移量，根据数据库所在内存的起始地址及该偏移量就可以找到左（右）子树根节点；FREE_TREE_PAGESIZE是每个fTtreeNode最多拥有fTTreeItem的个数。

TTree是根据T树的思想构造起来的，所以也有平衡操作，但有特殊性。首先，它存储的元素为自由空间的起始位置和自由空间的长度，而非记录的RID（或称对象标识OID）；另外、由于该T树只用于数据库自由空间的管理，也就只有请求分配空间与释放空间的操作，所以它不存在查找操作，只存在插入和删除。它的插入和删除操作与一般的T树不同，插入是由于数据库释放某块空间（有起始位置和长度）时，将该空间对应的元素插入到TTree中，在插入的过程中，若与该自由空间相邻的前、后区域已经在自由空间树中，需要合并这些自由区域，可能将三个元素合为一个，也可能将两个元素合为一个。

5     轻量级内存数据库的实现情况

由于本项目用户的特殊需求（即目前绝大多数应用都直接连接Oracle数据库，而且绝大多数应用都是基于C/S架构的、ADO访问Oracle的胖客户端应用）的关系，为了使得用户在引入内存数据库时尽可能的节省成本与时间，我们在设计轻量级内存数据库的时候，必须重点考虑下面这些问题：内存数据库与Oracle的方便移植、内存数据库的数据类型与Oracle的一致性、内存数据库所支持的SQL语法与Oracle的一致性；内存数据库访问接口与Oracle的一致性。下面就这些问题的实现情况进行说明：

5.1       数据类型的实现情况

轻量级内存数据库实现了多数的Oracle数据类型，包括：Number、Int、Integer、Varchar、Varchar2、char、Date、Time、DateTime、Boolean、string。

当然作为有高效率要求的内存数据库，也有不支持的类型，这里主要是指二进制大数据类型Blob、Long Raw、Raw、BFile这四种数据类型，因为对这些二进制大对象的处理本来就是耗费时间的，而且因为内存数据库由于物理内存的容量是固定的，不太适合支持二进制大对象类型，而实际上的需求也是如此，即如果用户有使用到这些类型的数据，那么用户就会改而使用Oracle数据库了。

5.2       对SQL92的支持情况

轻量级内存数据库支持标准SQL92的绝大多数功能：支持的对象类型包括table, indexe, trigger, and view；支持的数据库的DML数据库操作语言的包括INSERT, DELETE, UPDATE, SELECT；对DDL数据定义方面，支持Alter Table、Create Table、Drop Table、Alter View、Create View、Drop View、Alter Index、Create Index、Drop Index；在事务方面支持BEGIN Transaction, COMMITTransaction, ROLLBACK Transaction等命令；在约束方面支持UNIQUE, NOTNULL, CHECK，Primary Key等关键字。

5.3       对OLE DB接口的实现情况

轻量级内存数据库实现了对ADO通用功能的支持，方法是实现一个标准的OLE DB提供者程序，OLE DB内部是内存数据库。下面是实现的OLE DB接口以及接口图：

5.4       性能测试情况：

经过大批量数据的测试，通过测试工具LoadRunner7.8本轻量级数据库以100，000，000条记录进行插入、删除、查询、更改操作，操作的结果如下：

Insert操作1条记录：:23微秒；

Select操作1条记录： 16 微秒；

Update操作1条记录：10微秒；

Delete操作1条记录：93微秒；

可见，本内存数据库的效率已经比Oracle数据库的秒级提高了多个数量级。

6     结论

通过轻量级内存数据库项目的研究，我们对内存数据库的原理有了比较深刻的了解；通过该数据库的实现，我们对内存数据库的关键技术有了比较全面的掌握。经过测试与使用表明，与其他内存数据库向比较，该内存数据库的功能、性能、使用方便性方面都有很大的优势。目前，该内存数据库已经被用在指挥应用软件中，作为数据缓冲的核心了；同时本单位的虚拟数据库项目也用本内存数据库作为虚拟数据视图的数据库实现了。