内存数据库技术在嵌入式控制系统中的应用研究

冯文飞 毛洪川 韩洁 徐聪

摘要：论文通过分析嵌入式控制系统的数据管理需求，利用内存数据库实时性强、磁盘数据库安全性高的特点，在对内存数据库的数据结构、并发控制算法和查询处理算法进行优化设计和仿真验证的基础上，提出了内存数据库管理实时数据、磁盘数据库管理记录数据的整体数据管理解决方案。本文所建立的数据管理模型和内存数据库模型也可推广至类似系统应用中。

关键词：内存数据库（MMDB）；关系型磁盘数据库（DRDB）；并发控制算法；查询优化算法

中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2018）05-0127-03

1 引言

磁盘数据库（DRDB，Disk-Resident Database）系统，数据存放在外部存储器（如磁盘、FLASH盘等装置）上进行管理，使用时数据的存取操作需通过缓冲区调度和I/O操作实现，可能会造成频繁地访问外部存储器操作，会由于应用场景不同引起同样的事务处理时间的不确定，较难满足系统实时性要求较高的应用需求。但数据存储于外部存储器上，安全性较高，数据恢复机制成熟、可靠。

内存数据库，也称为主存数据库（MMDB，Main Memory Database）是数据库技术的发展的新成果，其解决方案是“近乎于”将整个数据库放在内存里，重新设计其数据结构、查询处理算法、并发控制算法和数据恢复算法，以期更有效地利用CPU 和内存[1]。与传统DRDB相比， MMDB的数据存取和事务处理均为内存读写，无需 I/O操作，其速度远远快于磁盘读写速度，且同一事务处理的时间确定性很高，可满足对实时性要求较高的系统应用需求。但其工作版本直接存放于内存中，极容易遭受操作系统和应用软件的破坏，需设计完善的保护机制或数据恢复机制。

嵌入式控制系统中，主要的数据管理需求一般有两类：一类是传感器上报数据的管理，另一类是系统工作数据的记录与重演。对于传感器数据，一般需要实时完成排序、筛选、更新、删除等处理，来实现解算处理、数据融合、指令生成、显示输出等功能，对实时性要求较高，且一般需多个进程（或任务）并行处理，因此采用MMDB，设计其数据结构、并行控制算法和查询处理算法。针对数据记录和数据重演需求，记录是仅需及时、完备地将系统工作数据记录到外部存储器上；重演时能够按照同步时钟控制要求从外部存储器读取记录的数据即可，因此选用关系型DRDB，通过提高缓冲区空间，进行最小化磁盘 I/O 算法设计[1]，可达到接近MMDB的性能，满足性能要求，并确保数据的安全性。

2 关系型DRDB和MMDB特点分析

2.1 关系型DRDB的特点

层次型数据库适合表示数据记录之间一对多的联系，不便于表示多对多和多对一的联系。网状型数据库的数据结构较为复杂，设计困难。 与层次型和网状型相比，关系型MMDB具有以下特点：

（1）描述的一致性，且利用公共属性连接；（2）采用的表结构简单、直观；（3）有严格的理论基础（关系代数），且语言表达简练。

其缺点是：进行查询操作时，需要执行查表、拆表、并表等处理，时间不确定。

2.2 MMDB的特点

与DRDB相比，MMDB具有以下特点：

（1）数据的存取和事务处理直接对内存操作，无需 I/O操作，大幅提高速度；（2）在事务执行前将所需数据集调入内存，提交时把所有对数据库修改写回磁盘，不再需要对缓冲区进行管理，消除了磁盘和内存之间数据拷贝开销；（3）对内存可根据需要采用顺序存取或随机存取方式，性能基本一致；

其缺点是：对内存的直接存取，容易因操作系统和应用软件的錯误遭受破坏。

2.3 MMDB和DRDB的对比

MMDB的工作版本存放在内存中，直接存取数据，不需要对缓冲区进行管理，因此其体系结构与DRDB有明显的差异。一般的DRDB和MMDB的结构对比图见图1。

如图1所示， DRDB采用内存缓冲区管理机制，需要把应用所需的数据复制到内存缓冲区，应用在缓冲区里取所需数据。数据存取过程为先计算出待取记录的磁盘地址，然后调用缓冲区管理器，查询该记录对应的块是否在缓冲区中，若在则直接调用；若不在缓冲区且缓冲区已满，需采取相应算法进行数据置换。增大缓冲区可以明显提高磁盘数据库的性能，如把缓冲区增大到可以存储所有数据，并进行最小化磁盘I/O的算法设计，可达到接近内存数据库MMDB的性能[2]。

MMDB直接访问内存，不需数据缓冲区和进行缓冲区管理。Tobin J.Lehman等人曾对此进行了专门的性能测试，测试案例为：子系统A采用MMDB，子系统B采用DRDB，且将子系统B所需的数据完全存放在内存缓冲区，保证两者在事务处理期间没有磁盘 I/O。测试结果表明，MMDB比DRDB快2.3倍～7.1倍[3]。

MMDB工作时，数据库的主拷贝常驻于内存，任何一个事务在执行过程中没有内外存储器之间的数据 I/O，使得数据库系统性能得到极大提高。同时，由于所有操作直接作用于内存中的数据库主拷贝，操作系统和应用软件的错误极易使数据库受到破坏，因此MMDB的恢复与DRDB相比较更为关键和复杂。MMDB的恢复机制一般仍采用日志、备份等方式，仍通过I/O操作实现，因此MMDB的恢复机制对数据库性能有着非常重要的影响。

3 嵌入式控制系统中MMDB的设计与应用

嵌入式控制系统中主要应用MMDB管理传感器数据或指令数据，这类数据的特点是数据根据外部环境“实时”产生，数据具有“定时处理”和“短暂有效”的特性，要求在一定时刻或一定的时间期限内自外部环境采集数据，进行数据存取、处理，并做出响应[3]。故障时恢复的数据无“实效性”，不能继续使用，MMDB不需要考虑设计数据恢复机制，避免了数据库进行备份和日志时的I/O操作，确保了MMDB数据存取和事务处理的实时性。

分析了MMDB在嵌入式控制系统中的应用需求后，其结构就可描述为如图2所示的图形。

该类数据管理的特点决定MMDB需频繁地执行数据添加、数据删除、数据更新、排序及查询操作，且这些操作往往由不同的进程（或任务）来实现，因此MMDB的数据结构、查询优化和并发控制成为了设计的关键，并需结合数据结构和并发控制算法的设计，来着重进行数据库的保护机制设计。

3.1 数据结构

为适应不同数据格式的数据管理（添加、更新、删除、排序、查询等）操作，设计时采用双向链表的数据结构，构成环形的数据缓冲区，如图3所示。

MMDB数据结构中每一个数据节点均采用如下的结构体形式：

typedef struct _DATA_NODE

{

unsigned char 数据标识；

unsigned char 数据长度；

unsigned char 数据报文[M]；

struct _DATA_NODE * Up；

struct _DATA_NODE * Down；

}DATA_NODE；

上述的数据结构形式，即可存储同一类型（数据报文格式和长度相同）的数据，也可用于存储不同类型（数据报文格式和长度不同）的数据。当某MMDB中存储的数据需进行排序和查询操作时，建议仅存储同一类型的数据；若仅用于数据存储和多进程间的数据交互应用，可用于存储不同类型的数据。

3.2 优化查询算法

采用本文3.1章节描述的数据结构，可实现MMDB的数据添加、更新、删除、排序、查询等操作，但每次在进行数据查询时，需根据查询内容，对已存储的数据节点中，选取某数据节点，根据报文协议约定解析出数据报文字符串中要查询的字段后，与待查询内容比较来确定该数据节点是否为查询结果，若是则可进行数据读取、数据更新或数据删除操作，若不是，则对下一个数据节点进行查询处理。因每次查询操作，均需对数据报文字符串进行解析，因此效率较低。

为提高查询效率，对原始的查询算法进行优化，采用“牺牲空间换取效率”的策略，即在设计数据结构时，事先将使用该MMDB所需的查询字段独立定义，进行数据添加和更新操作时一次完成数据解析，之后的数据查询操作可直接比对查询字段，不需进行多次数据解析处理，大幅提升查询效率。

优化查询算法设计后的MMDB数据结构中每一个数据节点均采用如下的结构体形式：

typedef struct _DATA_NODE

{

unsigned char 数据标识；

unsigned char 数据长度；

unsigned char 数据报文[M]；

数据类型1 查询字段1；

数据类型2 查询字段2；

… …

数据类型n 查询字段n；

struct _DATA_NODE * Up；

struct _DATA_NODE * Down；

}DATA_NODE；

以一次数据更新操作为例，两种查询处理算法的工作流程对比如图4所示。

图4中，原始查询算法中，每一次查询中的每一个数据节点的比较均需读取数据报文进行解析，并记录待查询字段，与目标值比较来确定是否为查询结果。在优化后的查询算法中，每一个数据节点仅需读取待查询字段，得到查询结果后。在数据更新时仅需多进行一次查询字段的更新操作即可。经测算，在10K条级别的数据管理应用中，优化后的查询算法效率提高95%以上，存储空间仅增加10%左右。

根据数据库系统存储的数据内容和使用方式，在查询优化设计时，也可考虑借鉴成熟的关系数据库排序和查询算法和技术，如索引顺序存取、B树等技术[4]。但在数据量级别较小（10K条数据以下）的情况下，效率提高不明显，因此不建议采用更为复杂的数据结构。

3.3 并发控制算法

在实时多任务嵌入式控制系统中，一般由多个任务/进程通过上下文切换和任务调度控制机制来实现多任务调度，应用系统无法事先获取某个任务的运行状态。对于某个数据库而言，往往是多个任务都需要对其进行处理和操作，比如，有数据接收任务，需要实时地对数据库进行数据查询和数据更新或数据添加操作；有显示任务和数据处理任务需要实时地从数据库中查询和读取数据；有接收人工输入的任务需要从数据库中查询和删除数据。多任务对某一数据库中的处理就需要设计数据库系统的并发控制算法来实现。

对于有嵌入式操作系统支持的嵌入式系统应用中，操作系统通常会提供信号量机制（同步信号量、互斥信号量、计数信号量等）来完成多任务间的同步或互斥操作。此时，MMDB系统可以利用信号量实现并发控制，如图5所示。

某些嵌入式系统应用中，若无操作系统支持或操作系统供任务间的信号量同步/互斥机制时，需应用软件设计专用保护信号来模拟实现信号量同步/互斥机制，完成对数据库使用时的并发控制和数据安全保护。

图5中，T1时刻，任务1启动对某数据库的数据处理操作，需先获取到该数据库的保护信号量（若不能获取，需等待）；到T3时刻，任务1完成数据处理后，释放该数据库的保护信号量，供完成其它数据处理的任务（包括任务1本身的下一次数据处理操作）捕获。

T2时刻，任务2启动对该数据库的数据处理操作，但此刻信号量被任务1占用，任务2不能获取需，就需等待，直至T3时刻，任务2获取到该数据库的保护信号量后方可对该数据库进行处理，到T4时刻，任务2完成数据处理后，释放该数据库的保护信号量，供完成其它数据处理的任务（包括任务2本身的下一次数据处理操作）捕获。

关于多个任务等待获取信号量时，任务间是依据任务优先级抢占还是时间片轮训方式获取信号量，属操作系统的信號量机制和应用系统设计范畴，不加详述。

4 结语

本文描述的内存数据库技术已在多个嵌入式系统中得以应用，可满足大多数实时嵌入式系统的数据管理需求。基于具体使用环境，可在数据结构和查询算法方面进行适当调整设计，可有更广泛的应用。目前，部分商用和开源的嵌入式数据库采用B树算法完成查询算法设计[4]，经测算，在10K条级别以下的数据管理应用中，与本文设计的查询算法效率相当。

参考文献

[1]Tobin J.Lehman， Michael J.Carey， A Study of Index Structures for Main Memory Database Management Systems， Proceedings of the Twelfth International Conference on Very LargeDataBases， Kyoto，August，1986.

[2] David J DeWitt， Randy H Katz， Frank Olken，et al.， Implementation techniques for main memory database systems，Proc，ACM SIGMOD Conf，1984.

[3]刘云生.现代数据库技术[M].北京：国防工业出版社，2001.

[4]Robert Sedgewick.算法Ⅰ-Ⅳ（C++实现）：基础、数据结构、排序和搜索[M].北京：中国电力出版社，2004.