（计算机软件与理论专业论文）嵌入式内存数据库引擎的研究与实现.pdf

摘要 磁盘数据的存取和传输到内存的速度一直是计算机系统的性能瓶颈。虽然 现在磁盘转速和总线速度已经有了很大提高，但磁盘容量的大幅度增大又减缓 了对其上数据的存取速度。数据库作为一种高效的组织和管理数据的软件，过 去一直是以磁盘作为存储介质，随着嵌入式软件技术的发展和内存容量的大幅 度提高，嵌入式内存数据库应运而生。在通信领域，随着人们需求的发展，出 现了很多业务数据短小但业务量急速增大同时又对交换速度要求很高的通信业 务，如手机短信。面对这些新设备和新业务，嵌入式内存数据库技术有了一个 很好的展示自己的舞台。 内存数据库( m m d b ) 把数据库的主拷贝( 即“工作版本”) 常驻在内存，使系 统性能得到了极大的提高。但是，由于所有操作直接作用于内存中的数据库主 拷贝上，数据库极易受到操作系统和应用软件错误造成的破坏， 因此蛐v l d b 的 恢复技术如备份、检验点( c h e c k p o i n t ) 和重启动( r e s t a r t ) 等都较常规的磁 盘数据库( d r d b ) 复杂。本文首先介绍了内存数据库的基础理论它的定义、 它的特点以及它目前的发展现状，并以短消息业务为例，分析了内存数据库适 用于通信行业的可行性；然后详细讨论了内存数据库在3 g 平台中的实现流程和 特点。 在以上研究和分析的基础之上。本文设计和实现了一个适用于3 g 平台的嵌 入式内存数据库系统。该系统中实现了表、索引、队列等数据库核心对象及其 提供的接口；然后，结合其在3 g 平台上应用有分布式特点，实现了主备同步和 处理器间同步等多种同步流程：最后，以短消息业务为例，进行了系统负荷分 析和性能测试，证明了本系统的有效性和适用性。 内存数据库要求数据库常驻内存并且在一个事务的活动期间没有i o ，日 志、检查点作为保证内存数据库健壮性的关键技术，其中的i 0 次数和时间对 系统性能起着至关重要的作用。本文在实现表、索引等数据库核心功能的基础 之上，提出了一种适用于内存数据库的恢复算法，详细讲述了曰志、检查点、 恢复、数据库分段等过程。其中对u n d o 日志和r e d o 日志的灵活使用使该算法 能有效提高系统性能。 关键词：内存数据库、索引、系统恢复、物理日志、检查点 a b s t r a c t t h ea c c e s ss p e e d0 nd a t ai nd i s ka n dt h et r a n s m i s s i o nt i m ef r o md i s k t om e m o r ya r ea 1 1a l o n gt h ep e r f o r m a n c eb e r t l e n e c ki nc o m p u t e rs y s t e m ， a l t h o u g ht h ew h e e ls p e e do fd i s ka n db u ss p e e dh a v e i n c r e a s e dg r e a t l y ， t h ei n c r e a s eo fd i s kc a p a c i t yd e c r e a s et h ea c c e s ss p e e d d a t a b a s e ，a s a h i g he f f i c i e n c ys o f t w a r e t h a ti su s e di nd a t ao r g a n i z i n ga n d m a n a g e m e n t ， u s et h ed i s ka 1 1 a l o n ga s t h e s t o r a g e m e d i u mi nt h ep a s t e m b e d d e d m a i n _ m e m o r yd a t a b a s e c o m ei n t ob e i n ga l o n gw i t ht h e d e v e l o p m e n t o f e m b e d d e dt e c h n i q u ea n dt h ei n c r e a s e o f m e m e o r yc a p a c i t y i n c o m m u n i c a t i o n sf i e l d ，w i t hd e v e l o p m e n t o f p e o p l e sd e m a n d ，m a n y o p e r a t i o n sa p p e a rw i t hs h o r to p e r a t i o nd a t ab u tl a r g eo p e r a t o nn u m b e r ， w h i c ha s kv e r yh i g he x c h a n g er a t e ，s u c ha sm o b i l en o t e i nt h ef a c eo f t h e s en e wo p e r a t i o n sa n dn e we q u i p m e n t ，e m b e d d e dm a i nm e m e o r yd a t a b a s e t e c h n i q u eh a sag o o ds t a g et o s e to u ti t s e l f m a i n9 e m o r yd a t a b a s e ( m m d b ) m e a n st h a tt h em a i nc o p yo fd a t a b a s e ( w o r k i n ge d i t i o n ) i si nm a i n _ m e m o r ya l l t h ew h i l e ，s ot h ep e r f o r m a n c e o fs y s t e mi si n c r e a s e dg r e a t l y b u ta l lo ft h ed a t a b a s eo p e r a t i o n sa c c e s s d i r e c t l yo nm a i nm e m o r yw o r k i n ge d i t i o n ，d a t a b a s es y s t e m w i l lb r e a kv e r y e a s i l yb e c a u s eo ft h eo sa n da p p l i c a t o ns o f t w a r ee r r o r s ot h er e c o v e r y t e c h n i q u eo fm m d b ，s u c ha sl o g 、c h e c k p o i n t 、r e s t a r tr e c o v e r y 、b a c ku p e t c ，i sm o r ec o m p l e xt h a nd i s kr e l a t i o nd a t a b a s e ( d r d b ) f o c u s i n go n i t ， t h i sp a p e rf i r s t l yd i s c u s s e st h eb a s i ct h e o r yo fm m d b ，i t sd e f i n i t i o n ，i t s c h a r a c t e r i s t i c ，i t sd e v e l o p m e n ta c t u a l i t ya n di t sf e a s i b i l i t yw i t ht h e e x a m p l eo fs h o r tm e s s a g eo p e r a t i o n t h e ni td i s c u s s e st h ei m p l e m e n tf l o w a n dt h ec h a r a c t e r i s t i ci n3 ga p p l i c a t i o n o nt h eg r o u n do fa 1 1t h e s ea n a l y s i sa n dr e s e a r c h ，t h em a i nw o r ko f t h i sp a p e ri st h ed e s i g na n dr e a l i z a t i o no fae m b e d d e d m a i n m e m o r y d a t a b a s ee n g i n ew h i c ha d a p t e dt o3 gs o f t w a r ef l a t ，i n c l u d i n gd e t a i l e d d e s i g no fd b c o r ek e r n e lo b j e c t sa n dt h e i ri n t e r f a c e ，s u c ha st a b l e 、 i n d e x 、q u e u ee t c ，a n dt h ei m p l e m e n to fv a r i o u ss y n c h r o n i z a t i o nf l o w ， s u c ha sm a i n s t a n d b ys y n c h r o n i z a t i o n 、s y n c h r o n i z a t i o ni nc p u se t c t h e s y s t e ml o a da n dp e r f o r m a n c ea n a l y s i s a r ei n c l u d e df i n a l l y 瑚d bd e m a n d st h a tt h e r ei sn o t a n y i o o p e r a t i o n sd u r i n g a t r a n s a c t i o np r o c e s s i n g ，s ot h ei ot i m ed u r i n gt h el o ga n dc h e c k p o i n t ， i sv e r yi m p o r t a n tt ot h es y s t e mp e r f o r m a n c e o nt h eg r o u n do fd b c o r e ， t h i s p a p e r d i s c u s s e sa r e c o v e r y a r i t h m e t i cw h i c ha d a p t e dt o m m d b ， i n c l u d i n gp h y s i c a ll o g 、c h e c k p o i n t 、d a t a b a s es e g m e n t 、l o g i c a ll o ge t c t h ef l e x i b l eu s eo fu n d ol o ga n dr e d ol o gt h e r e i n t oi m p r o v e st h es y s t e m p e r f o r m a n c e k e y w o r d s ：e m b e d d e d m a i n m e m o r yd a t a b s e 、i n d e x 、r e c o v e r y 、p h y s i c a ll o g 、 c h e c k p o i n t 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：! 墨蓬、日期舢年2 月帅 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 邂 日期：出伪，年2 月，日 术语、定义和缩略语 术语、定义 前后台静态数据同步：由后台配置修改引起的从后台到前台的静态数据同步 主备静态数据同步：从主用机到备用机的静态数据同步 m p 与p p 间静态数据同步：从m p 到其归属的p p 单板之间的静态数据同步 缩略语 m p ：m a i np r o c e s s o r 主处理器 p p ：p e r i p h e r a lp r o c e s s o r 外围处理器 o m p ：o p e r a t i o nm a i np r o c e s s o r 系统控制管理处理板 c m p ：c o n t r o lm a i np r o c e s s o r ( 呼叫) 控制处理板 b s c ：b a s i cs t a t i o nc o n t r o l r n c ：r a d i on o d ec o n t r o l o a m ：o p e r a t o ra d m i n i s t r a t i o nm a n a g e m e n t v l r ：v i s i t e dl o c a lr e g i s t e r 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 1 1 论文背景 第一章引言 在当代社会，市场经济和科学技术不断并行发展，i t 和通信更是走在 了时代的最前端，各种通讯技术和手段不断普及，带宽不断增加，通讯业务 用户和类型迅速增加，电信服务商不断提供各种增值业务以提高带宽的利用 率，同时业务类型逐渐从窄带向宽带发展以满足不同的服务质量( q o s ) 的 要求。这给电讯设备带来了新的挑战：首先是设备系统必须具备更高效的信 令消息处理能力，其次是设备必须具备高度的业务扩充能力，能根据不同的 情况迅速开发新的业务和功能。这两方面都需要在硬件和软件两个层面上进 行优化。计算机硬件设备的更新换代速度基本上保持在1 2 到2 4 个月翻一倍， 处理器速度和总线速度的加快，内存容量的不断扩大，集成电路和芯片技术 的发展，使得开发高处理能力和高容量的通信设备成为可能。 一直以来，磁盘数据的存取和传输到内存的速度一直是计算机系统的性 能瓶颈。虽然现在磁盘转速和总线速度已经有了很大提高，但磁盘容量的大 幅度增大又减缓了对其上数据的存取速度。数据库作为种高效的组织和管 理数据的软件，过去一直是以磁盘作为存储介质，随着嵌入式软件技术的发 展和内存容量的大幅度提高，嵌入式内存数据库应运而生。在通信领域，随 着人们需求的发展，出现了很多业务数据短小但业务量急速增大同时又对交 换速度要求很高的通信业务，如手机短信。面对这些新设备和新业务，嵌入 式内存数据库技术有了一个很好的展示自己的舞台。 第三代移动通信网络3 g 网络的建设和实施，让3 g 软件平台的研究与实 现成了各大设备提供商在软件研发方面又一大竞争的热点。本课题来源于中 兴通讯3 g 软件平台项目中的嵌入式内存数据库子系统，其研究目的就在于 设计并实现个适合于通信行业的、高效的、易扩展的嵌入式内存数据库系 统。 1 2 论文组织结构 第一章介绍了论文背景和论文组织结构。 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 第二章介绍了内存数据库相关的基本理论知识、数据存储、事务处理、 恢复等，介绍内存数据技术在通信行业中的应用，以及对未来内存数据库技 术的展望。 第三章讨论和分析建立了内存数据库引擎的模型。 第四章介绍了该模型公共数据结构设计。 第五章介绍了d b c o r e 的接口设计。 第六章进行了系统负荷控制和性能分析。 第七章深入探讨了内存数据库的系统恢复机制 第八章总结了整个系统的不足之处，提出了进一步完善的工作。 电子科技大学硕士学位论文嵌入式内存数据库弓 擎的研究与实现 第二章嵌入式内存数据库技术及应用 2 1 嵌入式内存数据库技术发展的现状 数据库理论与技术的发展极其迅速，其应用r 益广泛，在当今的信息社 会中，它几乎无所不在。以关系型为代表的三大经典( 层次、网状、关系) 型数据库在传统的( 商务和管理的事务型) 应用领域获得了极大成功，然而 它们在现代的( 非传统) 工程和时间关键型应用面前却显得软弱无力，面临 着新的严峻的挑战，由此而导致了嵌入式实时数据库的产生和发展。在实时 应用中，事务在运行前的操作逻辑( 操作类型、顺序等) 、数据集及其结构、 行为以及时间的相关性等都是可预分析的。然而，对磁盘数据库而言，数据 的i 0 是造成事务执行时间不确定、预报不准确的关键因素。为此，要求以 大内存作为实时数据库的主要存储介质，使一个事务在活动期间没有i 0 ， 以达到较准确的预报，从而满足实时事务的定时限制。但这要解决两个问题， 就是适当的数据安置和适时的内外存交换。随着内存技术的高速发展，内存 数据库技术日益成熟，在非实时系统中也得到了广泛的应用。 内存数据库( m m d b ) 把数据库的主拷贝( 即“工作版本”) 常驻在内存， 使系统性能得到了极大的提高。但是，由于所有操作直接作用于内存中的数 据库主拷贝上，数据库极易受到操作系统和应用软件错误造成的破坏，而且， 数据库恢复所包含的i 0 操作( 如做日志、备份等) 在事务运行不需要i 0 操作的内存数据库系统中也显得极为突出。因此，内存数据库的恢复机制对 系统性能有重要的影响作用，内存数据库的恢复较之传统的磁盘数据库的恢 复要复杂得多，也关键得多。数据恢复是内存数据库可靠、实用的关键，恢 复技术的研究已成为m m d b 研究领域最热门的课题。 2 2 内存数据库的定义 内存数据库的定义不应涉及内存的大小、存取数据所需i 0 的多少、数 据何时进入及怎样才能留驻内存等这些具体的实现技术，而只包含数据库常 驻内存( 而不是磁盘) 、事务( 不是系统) 的数据存取只涉及内存的意思。 其本质特征是其“主拷贝”或“工作版本”常驻内存，即活动事务只与实时 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 内存数据库的内存拷贝打交道。显然，它要求较大的内存量，但并不要求任 何时刻整个数据库都能存放在内存，即内存数据库系统还是要处理i o 。传 统的磁盘数据库即使缓冲区足够大，以致可以容纳所有数据也不能算是一个 m m d b 。因为它是针对磁盘特性、在数据库常驻磁盘的假定下设计的。例如， 索引结构还是针对磁盘存取的，数据的存取仍必须经过缓冲区管理等。内 存数据库的组织与管理要求新的适于内存特点的数据结构和算法，对于数 据的组织与安置、数据库存取、内外存数据交换、查询处理及优化、并发控 制及数据库恢复都需要研究新的策略与机制。 内存数据库是一个较新的研究领域，结合各方面参考，现给出如下定义： 定义：设有数据库d b ，d b m ( t ) 是t 时刻d b 在内存中的数据集，d b m ( 力真包含于d b ：7 5 为所有事务的集合，at ( r ) 是t 时刻的活动事务 集，彳t ( t ) 真包含于，& 口t ( t ) 为，在f 时刻的操作数据集，df ( ，) 真包含于d b ；若在任一时刻t ，均有： 对任一事务有7 at ( 幻，d ( ，) 真包含于d b m ( t ) 成立，则 称d b 为一个内存数据库，简记为m m d b 。 按此定义，m m d b 的“工作版本”( 当然也可以是整个数据库) 常驻内存， 任何一个事务在执行过程中没有内外存间的数据i o 。显然，它需要定的 内存容量，但并不要求整个数据库都必须常驻在内存。 2 3 内存数据库的特点 2 - 3 1 内存数据库数据存储的组织和管理 一个m m d b 的逻辑整体主要由两个部分构成，即内存版本与外存版本 1 。 主存储器是易失内存，它存放m m d b 的“工作版本”。它在逻辑上被 划分为若干分区，一个分区用来存放一个关系的数据。每个分区又物理地由 若干相互链接的块组成。一块是一个固定长度的连续区域，它是内外存i o 的单位，也是内存分配、回收以及对m m d b 进行恢复的单位。索引与数据记 录分离存放。 n v r a m ( n ov o l a t i l er a m ) 兼有内存读写速度快和在后备电池维护的 情况下非易失的特点，但价格昂贵，不便插拔，广泛用于嵌入式系统，并可 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 与f l a s h r a m 配合使用，充当f l a s h r a m 写缓冲区。尤其对于实时系统的 那些紧急且需要永久保存的数据，当写入f l a s h r a m 会错过它的截止期时， 可将它先写入n v - r a m ，紧急事务的日志也可写在n v r a m 中。 由于主存储器是易失的，所以可用少量不易失内存n v r a m 作为磁盘高 速缓存或临时的固定存储器，存入其中的数据再依其永久性要求移或不移到 磁盘上。从而支持实时高性能要求。比如，把对数据库的修改写入到n v r a m 里的曰志里，可以很好地支持数据库的快速恢复；表明事务间相关性的“全 局性锁表”、“事件库”、“触发器库”等系统数据结构的永久性可能使 之成为系统的潜在瓶颈，将它们放入n v r a m 使之成为既是永久的、又可高 速存取的数据，则能更好地支持系统的功能与性能要求。n v - r a m 是主存储 器的拓延，目前可用u p s 、固态磁盘或磁盘c a c h e 等实现。主存数据与n v r a m 数据一起统称为m m d b 的“内存版本”。 磁盘存储器用来存放未在内存的那一部分数据库数据，同时也用作数据 库恢复的备份，我们称之为“外存版本”。为便于实现内外存间的数据交换， 可将磁盘数据在逻辑上划分为与内存块同样长度的定长块，建立相同类型的 索引。 档案式磁带存储器用来存放数据库以前某个完整状态的映象，我们称之 为后援数据库。它是脱机的，仅用于m m d b 的安全保护和数据的长期档案式 保存。 2 3 2 事务处理 当内存数据库用于非实时系统时，除了日志和系统恢复的具体方式跟传 统数据库差异比较大以外，事务处理过程与传统数据库的事务处理相似：然 而，当内存数据库用于实时系统时，既实时内存数据库中，事务处理由于受 到了时间上的限制，传统数据库的事务处理已经不再适用。传统的“a c i d ” 的事务概念及模型对实时事务不适合。实时事务表现出了许多不同的特征， 如实时性和相关性。虽然实时事务的正确性与传统事务一样，也包括数据库 状态正确性和事务执行正确性两个方面，但其含义与内容有很大的不同。在 实时事务中，数据库状态正确性包含内部一致性和时间一致性，事务执行正 确性则包含其结果正确性、行为正确性、结构正确性和时间正确性等。事务 调度也要采取相关的实时调度算法。本文中讨论的内存数据库引擎针对非实 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 时系统。 2 3 3 系统恢复 数据库的备份是数据库的副本以及一些控制信息，在出现故障的情况 下，可以随时用它进行恢复。数据库备份最小化了数据丢失，能够让您使用 恢复过程，从备份副本中重新构造失败的数据库。有多种类型的失败导致需 要恢复数据库。其中包括语句失败、用户错误、进程失败、数据库实例失败、 媒介失败等。但不是所有类型的失败都需要进行人工交互。但是，在内存数 据库系统中，由于所有操作都直接作用于内存中的数据库主拷贝上，数据库 极易受到操作系统和应用软件错误造成的破坏，因此m m d b 的恢复技术如备 份、检验点( c h e c k p oi 1 9t ) 和重启动( r e s t a r t ) 等都较常规的磁盘数据库 ( d r d b ) 复杂。人们从体系结构、事务提交、日志系统到备份、检验点算法 等各个方面进行了大量的研究和探索。日志管理是内存数据库恢复机制中至 关重要的一环。由于内存有易失性，日志最好保存于另一稳妥的介质上( 如 磁盘、非易失内存等) ，而对日志的i o 操作又将在某种程度上影响m m d b 的性能，可能成为瓶颈影响系统的事务吞吐量。为此，人们研究了各种各样 的解决办法，比如构造非易失内存用于保存部分日志；采用“成组提交” 4 的技术，使用影子内存技术等来解决日志瓶颈问题。在检验点方面，为 了提高系统效率，通常力图使检验点操作和事务处理同时进行。为了提高速 度指标和综合性能，m m d b 系统往往利用附加的硬件设备如非易失内存、专 用的日志处理器、检验点处理器等来支持高效、快速的数据恢复。 2 4 内存数据库在通信行业中的应用 随着我国经济和通信技术的高速发展，通信业务的不断普及，国内外各 大通信设备提供商都在自己的通信产品中引入了各种各样的新技术，以提高 产品性能，加强竞争力。目前，华为、中兴、康为等短信设备提供商已经在 其短消息设备中实现了内存数据库，设备的短消息处理速度得到了极大的提 高。其主要思想是尽可能用内存里的业务操作替代原来的大量数据库操作。 短消息中心在典型情况下，处理一条短消息要经过短消息始呼m o ，短 消息终呼m t ，短消息终呼响应m t a c k 三个阶段。在非内存数据库版本中， 所有的m 0 ，m t ，m t a c k 都与物理数据库进行交互。完成一条短消息的处理， 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 前后需要1 3 次数据库操作，包括7 次查询，1 次插入，5 次更新。由于各个 过程数据均保存在数据库中，业务实现过程比较简单容易，但另一方面由于 大量与数据库系统交互，导致系统的处理能力不高，难以满足应用需求，因 此提出内存数据库方案以期获得性能上的提升，达到单模块至少1 0 0 条秒 的设计目标。 在短消息业务中，内存数据方案主要依据短消息系统的这样一个处理特 点：所有通过m o 到达短消息系统的短消息都具有一定的处理周期( 以下简称 短消息生命周期s ml i f e c y c l e ) ，在一定的系统处理能力( 假设1 0 0 条秒) 下，在有限的短消息l i f e c y c l e ( 假设2 0 0 秒计) 内，短消息系统要处理的 数据量总是有限的，以至于可以将其保存在系统内存中。 如果我们将短消息业务处理要用到的用户数据全部加载到内存中，则从 m o 到m t a a k 的过程中只需要约1 次查询( 查询目的用户当前短消息索引数 据) ；对于需要重试的短消息，也等同看待为系统处理一条短消息，另一方 面，由于短消息处理到达m t a c k 时，其已没有必要进一步保留在内存中，因 此，我们可以将l i f e c y c l e 己结束的短消息下载保存到数据库中并释放其占 用的内存，用于新的短消息处理。在数据下载到数据库时由于大量数据状态 已不再变化，可以并行下载保存，大大提高数据库操作效率。对于无m t a c k 的短消息，我们采用超时机制进行处理。当检测到某短消息超时时，系统强 行结束其l i f e c y c l e 。 从上面的分析可以看出，只要系统有足够的内存，内存数据方案将大大 提高系统性能。最终制约内存数据方案处理能力的因素是内存数据库的数据 下载操作和目的用户动态短消息数据的动态加载。 电子科技大学硕士学位论文嵌入式内存数据库9 1 擎的研究与实现 第三章面向3 g 平台嵌入式内存数据库引擎的设计 3 1 3 g 平台中数据库子系统整体架构 3 1 1 数据库系统各功能模块在3 g 平台系统中的位置 3 g 软件平台包括图3 - 1 所示的除0 s 和b s p 外的6 大软件子系统。其中， 业务处理子系统 系统控制0 a m 和网管 予系统子系统 d b 子系统信令子系统承载子系统 操作系统子系统 内核 ( 0 s 支撑平台) ! b s p d r i v e r 图3 i3 g 软件平台系统分布图 d a t a b a s e 子系统负责管理平台的物理资源和平台实现的信令、协议的配 置信息，同时向其它子系统提供数据库访问接口。它工作于操作系统之上。 承载子系统向业务子系统、信令子系统、o a m 和网管子系统提供a t m 、 i p 、等方面的承载服务。它工作于操作系统和d a t a b a s e 子系统之上。 信令子系统实现窄带n o 7 信令、宽带n o 7 信令、i p 信令、网关控制信 令，向业务处理子系统提供服务。它工作于操作系统、d a t a b a s e 子系统和承 载子系统之上。 系统控制子系统负责对整个系统的监控、启动、版本下载等。它工作于 操作系统和d a t a b a s e 子系统之上。 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 o a m 和网管子系统提供平台与网管后台的统一接口，负责对平台的协议、 信令进行配置和管理。以及提供必要的统计数据。它工作于操作系统、承载 子系统、d a t a b a s e 子系统之上。 业务处理子系统实现系统提供的各种业务。它工作于操作系统、承载子 系统、信令予系统、d a t a b a s e 子系统之上。 数据库子系统分布在3 g 平台各处理器上。从结构上看数据库子系统属 于分布式数据库系统；主器为平台各个子系统提供数据支持，并为将来其上 的扩展业务提供支持易扩充机制的数据库模型。 3 1 2 数据库子系统内部模块划分 数据库子系统内部划分五大功能模块，支持数据来源为r a m 、f l a s h 、 硬盘特定格式以及商用数据库等多种介质。五大功能模块分别是：输入输出 模块、对象管理模块、业务处理模块、维护管理模块及平台系统工具包。相 互关系和层次参见下面的图3 - 2 。 输入输出模块( i 0 模块) 负责完成整个平台所有与硬件介质相关的 数据、装载、转储、存储空间管理等等相关功能。 对象管理模块是整个平台的核心模块( d b c o r e ) ，完成主体功能，即对内 存数据、表、索引、锁等等系列对象的核心组织功能，对整个系统的性能高 低有决定性的影响。提供简易的内部并发控制手段。 业务处理模块是针对数据库平台的用户提供的使用接口层，完成对内存 数据库的访问服务。可以支持a p i 方式及类s q l 访问方式。支持分布式数据 访问方式。 维护管理模块完成对整个平台系统的监控及管理，包括探针、告警、日 志、实时业务跟踪、远程网络访问等等系列功能的实旌。 平台系统工具包针对各模块均有完善的工具支持，具体如下： 介质层工具；各类特定介质的数据存储文件检索、修改、生成。 对象管理模块工具：根据对象属性区别性选择生成主体程序框架，若无 特殊要求，生成的代码可直接用于对象管理。 i 0 模块工具：根据内存数据库分布模型，生成数据装载、转储及内 存数据存储空间管理等框架代码；业务处理子系统工具，常规a p i 代码生成。 维护管理模块工具：接口跟踪、日志等输出文件的检索、管理工具。 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 其他：各类对象( 表、索引) 设计及相关说明文档生成。 f = = = = f ：= = = = j 1 兰竺 ii 堡垒 l 图3 - 2d b m s 整体架构 本论文将详细介绍对象管理子系统d b c o r e 的设计和实现，并将对日志 和系统恢复进行探讨和研究。 3 2d b c o r e 3 2 1 核心对象概述 数据库d b c o r e 的核心对象包括表、索引和队列。这三个对象为数据的 定义、描述、操作和维护提供了支持。如图3 3 所示，从下至上，数据管理 分为三个层次。 第一层次为抽象基类：对象基类中的核- t l , 对象是数据管理的基础，通过 在核心对象的基础上完成实例化，实现了对数据本身和联系的定义。扩展对 象用于数据维护，扩展对象加上工作区对象和数据库的同步模块( 此二者没 有在上图中体现出来) 相当于完成了数据库系统中的数据库软件的功能。第 一层次中的单向队列是供表对象和同步对象内部使用。它仅仅是一个内部数 据结构，它用于管理表对象和同步对象的内部数据。 第二层次为对象实例：第二层次的任务利用第一层次提供的对象完成实 例化，赋予数据具体的含义。图中，表实例的意思可以理解为一个具体有实 际意义的表。如局间中继表。表实例除了数据之外，还可以有自己的索引实 例、双向队列实例、同步实例、监控实例以及通过重载得到方法实例。 内存数据库。叫暮 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 核心 ，爿裹实例。，d 表实例：f f 衰实 辩 獗 i t 呵t 裹实例爹。 爿 表实例2 ff 衰实 $ 中。 警 产睾申i 豫 i i 一 i r p 多 删犁 p 矽 _ 7 磊羔j ! 、芏啊队! ；、内軎e 耋砉掏 图3 - 3 数据库对象关系 第三层为应用实例：应用实例是面向具体的应用的。以应用为目标，从 对象实例中获取需要的数据，组成一个面向应用的数据视图。可以把第三层 理解为第二层经过实例化的数据对象中若干数据实例表的相关字段的一个 再生数据关系或称为虚关系。 关系数据库是由一系列的有着相互依赖关系的二维表组成的，表对象是 用来定义和描述二维表的特征和方法的数据对象，每个二维表就是表对象的 一个实例。为了加速对二维表元组的检索，需要对二维表建立特定关键字的 索引，索引对象是用来描述不同类型和算法的索引的一种数据对象。一个特 定二维表的索引表就是索引对象的一个具体实例。 双向队列对象是描述通讯资源中涉及的各种形式的队列的一种数据对 象。存在于交换机软件中的各种资源队列都是双向队列对象的具体实例。它 专门用于管理资源，实现对资源的快速检索。从快速检索这一点来看，它的 功能同索引相似。不过，它专为管理资源而设计，因此管理资源更有效。 主备失步对象用于动态数据的主各同步，主备同步的作用在于可以保证 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 动态数据的主备实时同步，当主板出现异常时，不会丢失大量的动态信息： 或当主备切换时可以利用间步所备份的数据进行正常置作。 监控对象的作用是为了防止资源处于吊死状态。由于m p 宕机等原因， 导致系统分配的资源得不到释放，以至于业务因资源分配失败而无法正常进 行，为避免此类情况的发生，就需要对资源的活动情况进行监控，及时释放 这类资源。 监控对象内部要维护若干类资源的双向资源监控队列，分别用于记录该 类资源某个时间段内的占用状况，这个双向资源监控队列可以利用现有的资 源状态队列。 单向资源队列对象是供表对象和同步对象内部使用的对象，它用于辅助 表对象和同步对象的功能实现。表对象用于辅助内存的管理，表对象要对大 量的记录进行管理，而这些记录的存储需要内存。在表对象中内存是通过静 态分配方式一次申请足够的内存实现的，然后在对各个表记录的内存进行分 配，这时就要解决一个问题，在表对象为表对象分配内存时，要快速知道那 块内存是空闲的，那块已被占用。而单向资源队列对象就是对这些空闲内存 块做一记录，以备快速定位。在同步对象中，需要记录哪个哪些记录处于失 步状态，为此需要有个队列来维护这些失步记录信息，这是单向资源队列在 同步对象中的作用。 除以上几个对象外，系统还提供了探针对象，专门用于测试之用。它为 后台观测前台的数据提供了方便。其数据观测对象包括所有以上其他对象。 之所以要专门设计探针供测试之用，是因为前台的特点如软件和硬件的限制 等，不便于对前台的数据进行观察，所以提供探针功能以方便观测。 3 2 2系统对象设计原理和处理流程 本子系统是按照面对对象的方法进行设计的，因此在叙述系统处理流程 时以子系统的各个对象为主线，而同步流程和监控流程设计上有其自身特 点，对它们的叙述以过程为主线。 本子系统的数据分为数据表、索引、队列、同步实例、监控实例、单向 资源队列六大类。其中数据表为数据库组织的核心，然后为数据定位的方便 建立索引，为资源管理的方便建立了队列，出于数据同步的需要建立了同步 实例，出于资源监控的需要，建立了监控实例，而单向资源队列作为辅助数 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 据表和同步实例的内存管理之用。 以上除单向资源队列外每一类数据都定义为系统的数据对象类，系统对 于同对象类的数据统一定义，统一管理。一个具体的数据对象称为某一数 据对象类的数据实例。系统为表、索引、队列、同步、监控的所有数据实例 统一分配唯一一个3 2 位整数加以标识，称为数据实例旬柄。对数据实例的 存取都是通过数据实例旬柄进行的。采用这种方式的一个优点是数据管理的 稳定性不随着数据实例的增加而变化，有利于系统的稳定。另一个优点是便 于数据对象类的扩充，由于不同数据对象类别分别管理，数据对象类之间的 独立性确保在扩充数据对象类后，不破坏原有数据的安全性。 单向资源队列作为在表对象和同步对象内部使用的对象。没有统分配 句柄。相关的表通过保存单向资源队列对象的指针实现操作。 3 2 2 1 表对蒙 表对象包括两部分，对象属性和对象方法。对象的属性描述了对象的基 本特征，所有该对象的实例均具有这些特征。对象的方法规定了操纵对象实 例的几个基本方法，这些方法可能随着二维表对象实例的不同而不同，因此， 在设计对象方法时需要能够在需要时重定义对象的方法，支持对象方法的重 定义是数据库d b m s 设计的一个重要方面。在交换机中，不同的二维表描述 不同的物理对象或逻辑对象，不同的物理或逻辑对象不可能用表中的三种基 本方法完全实现对象的操纵，所以需要对不同的对象实例进行相应的方法扩 充。在此着重叙述一下对象的注册、记录存放过程。 ( i ) 对象的注册定义 二维表对象是d b m s 的一个重要组成部分，索引对象和队列对象都是建 立在二维表对象基础上的。一个具体的二维表对象实例在运行之前必须在系 统注册登记才能被系统识别。注册定义一个具体的二维表的方法步骤如下， 其中 为可选部分，对于有些二维表不需要索引或队列管理： 注册一个空表： 在所注册的空表中逐个增加字段； 提供为所有二维表对象预定义的若干方法； 为二维表建立存储区： 注册二维表的索引对象 ： 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 为索引建立存储区 ： 注册队列对象 ； 为队列建立存储区 。 ( 2 ) 记录的存放 表中有大量的记录。这些记录存在数组当中。在插入表时，首先要在这 个记录数组当中，找到一个空闲的即不含有记录的数组元素，然后，再将记 录写在该位置的内存中。为加快查找空闲记录的速度，需要表在插入记录前， 就知道记录数组中空闲的内存。为此，表维护了一个空闲记录队列，该队列 保存了表中所有的空闲记录。每次表在插入记录前，首先从空闲记录队列中 获得空闲内存位置，然后，在该位置写入记录。而在每次删除记录时，也要 将删除后的记录位置信息插入空闲队列。以此，空闲队列保存所有的空闲记 录信息。 3 2 2 2 索引对象 1 、索引处理流程顺序索引和哈希索弓i 索引是为加速二维表的检索速度而设置。即要根据某个数据实例表中某 个字段的值快速地找到相应的记录。为什么说是快速地定位呢? 假如不采用 某种技术手段，那要根据字段值找到相应记录，只能通过一条一条的搜索数 据实例表记录，然后再获得相关字段的值，再根据同已知字段值的比较结果 才能获得满足条件得记录。这样的查找效率显然是不能让人满意的。于是， 索引对象的出现就在意料之中了。 索引是给这些需要经常查找的字段维护一张索引表，索引表中的记录有 字段值( 或者是字段值经过映射的信息) 信息和相应记录的位置( 记录号) ， 字段值( 或者是字段值经过映射的信息) 作为索引记录表的关键字。于是查 找记录可以通过先查找索引表获得记录号，然后就可以从表中获碍记录。不 过这样就又产生一个问题如何根据这些字段值( 或者是字段值经过映射的信 息) 查找到索引记录的位置呢? 这是索引设计的关键问题，在本系统中主要 采用两种不同的方法，一个是顺序索引，另一个是哈希索引。 顺序索引的实质是被查找的字段值和相应的记录号在根据字段值大小 在内存中顺序存放索引记录。于是在索引中根据字段值查找记录值可以通过 二分查找等一些快速查找方法得出字段值相应的记录号。查找速度获得指数 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 增长。如图3 4 所示： 索日 记录表 t u p l e k e y n t u p l e k e y ( n 一1 ) t u p l e k e y l t u p l e k e y o 图3 - 4 顺序索引原理 哈希索引是另外一种思路，参见图3 - 5 和图3 6 它是根据以索引字段 值为变量进行某种映射，由该映射结果得到索引字段信息在索引表内存中的 位雹。根据字段值和映射结果之间是否一一对应又分成散列哈希索引和一次 哈希索引。 散列索引是不同的字段值可能会有相同的映射结果。为解决映射冲突， 要在冲突映射值后维护一个冲突相关记录号队列又称哈希桶。然后为真正找 到记录，还要遍历该哈希队列，然后利用表中的索引字段信息获得该记录的 关键字，直到找到记录关键字与索引关键字相等的记录为止。 而一次索引字段值和映射结果之间是一一对应的，无须维护哈希桶。在 本子系统中根据查找字段是由一个字段还是由两个字段共同查找相应记录 来分类，而分成一次一维索引，一次二维索引和一次三维索引。 2 、利用重载实现索引 哈希索引的种类很多，随着散列哈希索引的广泛应用，也将会产生更多 的方法。为扩充的方便，以及保证思路的简洁，本系统中利用重载实现索引， 电子科技大学硕士学位论文嵌入式内存数据库引擎的研究与实现 哈希映射h ( x ) 记录表记录号索f 字段x 、 哈希索引表 f 哈希索引值h ( x ) 记录号、 t_- r 2 t u p l e k e y 2h