（计算机软件与理论专业论文）主动实时内存数据库的存储与恢复.pdf

华中科技大学硕士学位论文 摘要 主动实时数据库( a r t s d b m s ) 完善地集成了传统数据库、实时系 统及主动规则的技术与机制。主动实时数据库系统的高效性要求以内存数 据库( m m d b ) 作为底层支持，论文以自行研制开发的主动实时数据库系 统a r t s d b m s 为基础，对此系统的底层支持一一内存数据库子系统 a r t s m m d b 的体系结构、数据存储、数据组织与数据安置进行了详细分 析与设计。在此基础上，重点研究与讨论了a r t s m m d b 的恢复与重装。 f 内存数据库系统中的恢复较常规驻留磁盘的数据库系统有很大的差 别，而且由于内存的易失性，其采用的恢复技术是否行之有效，不仅对系 统的可靠程度起着决定性作用，而且对系统的运行效率也有很大影响，是 衡量系统性能优劣的重要指标。) 文中给出了一套完整的恢复模型，将模糊 检验点( f u z z yc h e c k p o i n t i n g ) 技术与l a w ( l o g g i n ga f t e rw r i t e ) 日志 协议相结合，简化了系统崩溃后系统恢复工作起始点的确定，减少恢复工 作量，缩短恢复时间，最终提高恢复效率。这对实时系统而言十分可贵， 可使整个系统在尽可能短的时间内从灾难中恢复，从而满足实时事务的截 止期要求，减少实时事务超截止期的发生。o 7 内存数据库的脆弱性使得数据库的重装极为重要，也是内存数据库恢 复过程中的重要环节，直接影响恢复性能和系统整体执行效果。) 文中的基 于数据优先级的a r t s m m d b 的重装针对主动实时数据库的系统特性设 计，为不同特性的数据分配不同重装优先级，进而采用不同的重装策略装 入，达到以最短时间装入最有效数据的目的，从而在尽可能短的时间内重 启a r t s d b m s 到可工作状态。重装技术加以必要修改可用于内存数据库 的初装。 关键词：主动实时数据库；内存数据峁；数据组织：内存数据库恢复 内存数据库重装 华中科技大学硕士学位论文 a b s t r a c t t h ea c t i v er e a l - t i m ed a t a b a s es y s t e m ( a r t s d b m s ) s e a m l e s s l yi n t e g r a t e t r a d i t i o n a id a t a b a s e s ，r e a l t i m e s y s t e m s a sw e l la sa c t i v e n e s sr u l e c o n c e p t s ， t e c h n i q u e sa n d m e c h a n i s m s m a i nm e m o r yd a t a b a s e ( m m d b ) t e c h n o l o g yb e c o m e s n e c e s s a r yb e c a u s e o ft h e h i g hp e r f o r m a n c er e q u i r e m e n to fr e a l - t i m e d a t a b a s e ( r t d b s ) t h ea c t i v er e a l t i m em a i nm e m o r yd a t a b a s es y s t e m ( a r t s m m d b ) i sw h a tt h i st h e s i sf o c u s e so n b a s e do nt h er e s e a r c hw o r k ，t h e d e s i g n a n d i m p l e m e n t a t i o no fa r t s d b m s ，i no u rl a b ，t h ei m p o r t a n tt h e o r ya n dt e c h n o l o g y i s s u e so fa r t s m m d ba r em a i n l ya p p r o a c h e d ，w h i c hi n c l u d et h ea r t s m m d b a r c h i t e c t u r e ，t h ee f f e c t i v ed a t ao r g a n i z a t i o n ，d a t ap l a c i n gs t r a t e g ya n daf e a s i b l e d a t a b a s e s t o r a g eh i e r a r c h y t h e a r t s - m m d br e c o v e r ym o d e la n dr e l o a d a l g o r i t h m a r es t u d i e da n d a n a l y z e di nd e t a i l t h em m d br e c o v e r yi so fg r e a td i f f e r e n c ef r o mt r a d i t i o n a ld i s k - r e s i d e n t d a t a b a s es y s t e m s b e c a u s eo ft h ev o l a t i l i t yo fm a i nm e m o r y ，w h e t h e rt h er e c o v e r y t e c h n o l o g y i na r t s m m d bi sv a l i di sac r i t i c a le l e m e n ti nd e t e r m i n a t i o no ft h e r e l i a b i l i t y a n de f f i c i e n c yo fa r t s - m m d b ac o m p l e t ea r t s m m d br e c o v e r y m o d e li s p r o v i d e d h e r e t h e f u z z yc h e c k p o i n t i n gt e c h n i q u e a n d l a w l o g p r o t o c o l ( l o ga f t e rw r i t e ) a r ec o m b i n e di na r t s m m d br e c o v e r ym o d e l ，w h i c h s i m p l i f i e st h el o c a t i o no f t h ev e r ys t a r t i n gp o i n ti nt h er e c o v e r yp r o c e s s i tc a ns a v e r e c o v e r yc o s ta n d r e s t a r tt h ew h o l e s y s t e m a ss o o na sp o s s i b l e t h i si so f g r e a tv a l u e i nr e a l t i m ed a t a b a s es y s t e m ，f o rt h ef a s td a t a b a s er e c o v e r yc a nm e e tt h er e a l t i m e t r a n s a c t i o nd e a d l i n ew e l l ，a n dr e d u c et h e m i s s i n g d e a d l i n er a t eo fr e a l t i m e t r a n s a c t i o n se f f i c i e n t l y t h ev u l n e r a b i l i t yo fm m d bm a k e st h er e l o a d i n go fm m d b v e r yi m p o r t a n t ， w h i c hi n f l u e n c e s s y s t e mp e r f o r m a n c eg r e a t l y a n dr e l o a d i n g i sa n i m p o r t a n t c o m p o n e n ti n t h ew h o l er e c o v e r yp r o c e d u r e a c c o r d i n gt ot h i s ，ad a t ap r i o r i t y r e l o a dt e c h n i q u ei si l l u s t r a t e di nd e t a i l d i f f e r e n td a t ar e l o a ds t r a t e g i e sa r ec h o s e n u 华中科技大学硕士学位论文 a c c o r d i n gt o t h ed a t ap r i o r i t yt h e s y s t e ma s s i g n sb yt h e i rc h a r a c t e r i s t i c s u s i n g l i m i t e dt i m et og e tf a s ta n de f f i c i e n td a t ar e l o a dp e r f o r m a n c ec a nb ea c h i e v e d t h e n b ea r t s - m m d bc a l lb e b r o u g h tu pi n u s ej u s ta f t e rs o m e h i g hp r i o r i t yd a t aa r ei n m a i nm e m o r yi nam u c hs h o r t e r p e r i o do f t i m e t h er e l o a dt e c h n o l o g yc a na l s ob e u s e di nt h ei n i t i a t i o no fa r t s m m d bu n d e rs o m e m i n u t ea n d n e c e s s a r y m o d i f i c a t i o n k e y w o r d s ：a c t i v er e a l t i m ed a t a b a s es y s t e m ；m a i n m e m o r yd a t a b a s e ；d a t a o r g a n i z a t i o n ；m a i nm e m o r yd a t a b a s es y s t e mr e c o v e r y ；m a i nm e m o r yd a t a b a s e s y s t e mr e l o a d i i i 华中科技大学硕士学位论文 1 绪论 三十年来，数据库理论与技术的发展极其迅速，其研究取得了丰硕成果， 其应用日益广泛，时至当今信息社会，它几乎( 也应该) 无所不在。以三大经 典( 层次、网状、关系) 系统为代表的传统数据库技术对于管理结构简单、 操作简单、完全格式和结构化且较稳定的数据已经证明是很成功的，因而在 一类重要但有限的传统商务和管理的事务性应用领域中获得了普遍而有效 的应用。然而，过去的十几年尤其是近年来，在这个数字化信息爆炸社会 里，新的过程与工程型、时间关键型、动态不确定型、主动规则型、非规范 超大型等现代( 非传统) 的应用不断涌现，例如，生产过程控制、电力或数 据网管理、空中交通管制、办公室工作流程控制、紧急情况的分析和估计、 协同处理和证券交易等等。这些应用一方面需要维护大量共享数据和控制知 识；另一方面其应用活动有很强的时间性，要求在定的时刻或和一定的 时间区段内自外部环境采集数据，按彼此间的联系存取已获得的数据和处理 采集的数据，再及时做出响应。同时，它们所处理的数据往往是“短暂”的， 即只在一定的时间范围内有效，过时则无意义，所以这种应用同时需要数据 库技术和实时数据处理技术。因此，自八十年代中期以来，数据库的研究呈 现了一个“百花齐放”的局面，其中尤其是时态数据库、实时数据库、主动 数据库、内存数据库及其“完善集成”( s e a m l e s si n t e g r a t i o n ) 等现代数据库 理论与技术【2 3 1 已成为当今数据库研究领域的重要热点。 1 1 现代数据库应用的特性与要求 随着应用的深入和应用领域的不断扩大，对数据库提出了新的更高的要 求，例如：要求数据库系统引入“时间维”，能处理数据与时间的关系、事 务的定时限制( 典型地为截止期) ；具有主动能力，能监视系统数据库的状 态，在特定的状态出现或状态变迁时主动地执行某一任事务，这中间不需 要用户的干预。实时数据库系统的功能特性与实时应用的特性和要求紧密相 关，必须首先进行应用分析以明确其性质与要求，从而确定实时数据库系统 华中科技大学硕士学位论文 r t d b s ( r e a r - t i m ed a t a b a s es y s t e m ) 的设计目标、功能、特性、系统模型。 这种应用具有以下特征( 或要求) ： 1 结构复杂性任务往往具有各种结构上的相互联系，无结构的、原子 和隔离的传统事务模型不完全适用，而有的要求嵌套或层次结构事务，有的 要求分裂和合并、通信与数据交换或长寿事务【4 。】等，因此必须开发各种具 有复杂结构的复杂事务模型。 2 可计划性现代应用环境中的活动具有各种要求与限制，如计算时间 要求、资源要求、通信要求、执行次序限制、执行时间限制、定位限制( 在 分布式系统情况下) 【5 “等，必须事先知道何任务( 事务) 何时很可能被执 行，它们分别有何种要求与限制以便能计划安排各种任务或事务。 3 分布规律性任务( 事务) 通常是周期的，但也有非周期或随机的， 有的是长寿的，为了调度必须事先知道各种任务( 事务) 的类型及任务( 事 务) 到达的分布率。对于长寿事务【_ 7 】这无关紧要，对周期事务问题也好解决， 但对非周期和随机事务则很困难。可以将一个非周期事务的两个体现( 具体 执行) 间的最小间隔时间视为其周期，从而将所有的硬实时事务都当作周期 事务来处理。对于随机事务则只能动态处理。 4 时间性现代应用的时间性表现在两个方面：一是它们所使用的数据 随时间而变化，即不但要处理对象的“当前”值，还要处理其变化的历史： 二是应用处理的定时性，即查询和事务有定时限制，如截止期等。 5 可靠性工程领域中的许多应用，尤其是一些关键应用不能失误，因 此它们具有“容错”性，当发现其中的任务要失败时，有“应急”能力，可 自动执行功能替换或补偿任务；或者干脆就是并行地执行任务的多个版本， 让至少有一个版本正确执行，其结果一致，而让不正确版本的结果无效。 6 合作性现代应用中任一事务总是“合作”进行的，除了前面所述的 结构联系外，彼此间还有许多联系，如共享数据联系，通信联系，时间上的 联系等，我们必须弄清事务间存在何种联系。 7 不可逆性现代应用中的许多活动是不可逆的，例如对应于火箭“点 火”的事务，记录飞行体的位置、速度、方向的事务等，它们都是不可逆的。 对于这种事务，还原重起动是毫无意义的，所以必须为实时事务恢复开发 新的概念、技术与方法。 华中科技大学硕士学位论文 基于以上分析，支持这类现代应用的数据库应具有下列功能特性： f 1 ) 事务有复杂的结构( 模型) ，如层次或嵌套、分裂、合并等； f 2 ) 事务能彼此协调、合作地并发执行，故要求事务间有强的可见性； f 3 ) 事务的及时性比正确性更重要，有时宁愿及时地获得部分正确的信 息，而不愿要正确但己过时( 无效) 的信息： ( 4 ) 因上述各点，事务调度和并发控制的可串行化协议不一定必要，而必 须要“识时”协议和“时间正确”的调度与并发控制f 8 ，j ： ( 5 ) 一般数据是二维的：值与时间，除值以外，每个数据有一个与之相联 的“有效”时区。大多情况下，事务只允许存取有效数据，故事务必须能处 理数据的时标( t i m es t a m p ) 和有效期( v a l i d i t yi n t e r v a l ) ； ( 6 ) 恢复不一定就意味着数据库状态的完全复原； ( 7 ) 需要预分析和处理以便所需要的数据、计算时间及处理资源在适当的 时候是可用的，因而能按截止期完成。 ( 8 ) 现代应用往往要求监视数据库状态，在特定的状态或状态变迁出现 时，自动进行条件评价，当条件满足时自动触发某一活动0 0 ，即具有主动性。 综上所述，现代数据库的应用要求主动、实时、内存数据库的完善集成， 当然这并不是在概念、方法、技术上的简单迭加，而需要在系统理论与实现 技术上进行全面的研究，尤其是在事务模型、特征、正确性标准、事务处理 及系统的存储体系结构等方面要做出深入的探讨。 1 2 主动实时内存式数据库管理系统 1 2 1 实时数据库系统的特征 实时数据库系统( r t d b s ) 中事务和数据都可以具有显式的定时限制， 系统的正确性不仅依赖于事务执行的逻辑结果，还依赖于逻辑结果产生的时 间【1 0 l 。近年来，它已经引起了数据库和实时系统两个领域里的研究工作者 们的极大关注。数据库研究工作者旨在利用数据库技术来解决实时系统中的 数据管理问题，实时系统研究工作者则致力于为r t d b s 提供时间驱动调度 和资源分配算法【l “。数据库与实时系统的结合导致了实时数据库的产生，它 集成两者的概念与要求以同时处理实时性与一致性，这使得事务的调度与处 华中科技大学硕士学位论文 理等问题要复杂和困难得多。 在r t d b s 中，事务由下列特性( 概念) 确定： ( 1 ) 可见性事务执行时可查看另一事务的能力： ( 2 ) 正确性事务的时间正确性、事务本身的逻辑正确性及事务提交时数 据库状态的一致性； ( 3 ) 可恢复性发生故障时使数据库成为某种被认为是正确状态的能力； ( 4 ) 永久性事务记录其结果到数据库及识别其中数据的有效期的能力； ( 5 ) 可预报性事先预测一个事务是否会满足其时限的能力： ( 6 ) 不可逆性有些事务的执行不能像传统意义上那样a b o r t 和 r e s t a r t ，事务执行的失败可能需要别的事务来“补偿”或“替代”。 1 2 2r t d b s 的关键问题 r t d b s 与传统数据库在概念、原理、结构、算法等方面都存在着很大 的差别，而最根本的区别就在于数据与事务的定时限制。实时数据库系统的 设计与实现有许多新的问题要解决，这里介绍其中最主要的： 1 数据模型及语言 要开发实时数据模型，必须设计允许用户说明实时数据模型中所含的语 义知识和以各种方式使用它的实时数据定义和查询语言，说明“复杂事务” 的结构及相互作用的实时事务执行说明语言。 2 事务模型与特性 必须扩展具有a c i d ( a t o m i c i t y 、c o n s i s t e n c y 、i s o l a t i o n 、d u r a b i l i t y ) 特 性的传统事务模型，开发新的“复杂事物”模型，它可以具有嵌套的层次内 部结构、分裂或合并结构、交互合作或通信结构等。 3 事务处理 要能够控制所有可执行事务的执行顺序，并需给事务分派基于截止期的 优先级，然后按优先级进行调度。 此外，并发控制是实时事务处理的又一个方面，对于r t d b s 的并发控 制，应允许非可串行化事务的执行。于是，要开发新的并发控制的正确性标 准，进而实现新的并发控制技术。事实上研究这些新的并发控制协议的文献 4 华中科技大学硕士学位论文 资料已经很多，如“乐观”、“时标排序”、“多版本”协议等1 1 2 l 。 4 数据存储管理 在r t d b s 中数据存储的一个主要问题就是如何消除数据库存取中的磁 盘存取延迟，一种解决方法是采用“内存数据库”作为底层支持【1 3 】。 5 恢复问题 恢复在传统数据库系统中尚且是一个复杂问题，更何况在r t d b s 中， 此时它显得更为复杂【l “，因为，第一，恢复过程会影响正在进行的事务，使 有的事务超截止期，而这是硬实时事务不可接受的：第二，r t d b s 中的数 据特征不同于传统数据库，允许暂时的数据不一致性以换取定时限制的要 求；第三，在r t d b s 中数据是短暂的，有的活动是“不可逆”的，数据库 的恢复并不意味着完全的“还原”。另外，以m m d b ( m a i n m e m o r yd a t a b a s e 、 作为r t d b s 的底层，则恢复问题由于底层介质的特质而显得更为复杂。这 些都要求开发新的恢复技术与机制，考虑时间和资源两者的可用性来确定最 佳时机及策略，以不致危害系统性能。 1 2 3 主动数据库技术对实时数据库的支持 实时应用往往要求系统具有自动监控能力，当特定情形发生，如出现例 外或错误时，能够迅速地自动进行处理与恢复，以免造成不良后果。 然而，传统的数据库管理系统是“被动”的，即仅当用户或应用程序显 式地请求时，它们才执行事务或查询，要监视数据库的状态和情形的发生只 有两种办法u 副： ( 1 ) 周期地不断查询； ( 2 ) 嵌入条件评价与活动调用到应用程序中。 这两种办法都不理想，前者除引起“抖动”外，还浪费大量资源，而且 查询周期难以确定：后者则打乱了软件设计的模块性，把有关定义事件与条 件、表示条件查询、决定条件评价及其时机的负担都转移给了应用程序员， 且对事件、条件及活动的任何修改都将要求修改相关的应用程序。因此，要 想很好地满足实时应用的要求，就必须引入主动机制。 引入了主动机制的实时数据库管理系统扩展了以下功能 ”1 ： ( 1 ) 用户可以显式地定义想要监视的情形( 事件与条件) ； 华中科技大学硕士学位论文 ( 2 ) 系统自动探测与评价情形的出现； ( 3 1 一旦说明的情形出现，则触发执行相应的活动。 这些功能除了支持外部应用以外，还可用于实现或扩展d b m s 本身的功 能，如完整性及安全性控制、导出数据、瞬像及视图实质化的处理、基于规 则的推理以及报警、性能测试等。 在复杂的实时数据库应用中，除了由事务生成的事件( 事务事件、对象 事件) 外，还有大量重要的定时器或时钟事件、外部环境的实时事件，它们 都要依靠主动机制提供的触发器( 或e c a ) 结构来建模这些事件及其与触 发事务的关联i l “。许多由事件驱动且又有定时限制的活动都必须依赖主动机 制的支持。把主动机制引入实时数据库系统，形成主动实时数据库系统 a r t d b s ( a c t i v er e a l t i m ed a t a b a s es y s t e m ) ，为实时应用提供了更有效的支 持i t 7 1 。 1 2 4 内存数据库对主动实时数据库的支持 在主动实时数据库( a r t d b s ) 中，要求系统能较准确地估计事务的执 行时间，但对基于磁盘的数据库系统而言，由于事务要频繁地进行内外存数 据交换、磁头的定位时间、缓冲区管理和页面缺乏等问题，事务的平均估算 执行时间和最坏情况执行时间的差距非常大。如果将主动实时数据库系统建 立在内存数据库的基础之上，那将大大减少事务运行中的不可确定因素，为 系统准确估算事务的运行时间使之具有一定的动态可预报性提供有力的支 持，有利于实时事务定时限制的满足。同时事务处理过程中没有内外存数据 i o ，事务执行的时间大大缩短，对事务处理带来一些方便，如并发控制的 粒度可以适当放大，这是因为事务因并发控制造成的相互等待时间短，增大 并发控制粒度可以减少系统开销，提高系统效率。 另一方面，随着v l s i 技术的高速发展，半导体存储器的成本不断下降， 而密度却指数级地增长，硬件的发展带来i o 、c p u 、内存三大瓶颈的突破， 这些都使得内存数据库( m m d b ) 8 。”j 不但必要，而且可行。有关内存数 据库技术的讨论，特别是内存数据库的恢复是本文研究的重点，在后续节中 有进一步阐述。 6 华中科技大学硕士学位论文 1 3 国内外研究动态 国外尤其是美国在主动数据库、实时数据库和内存数据库等领域的研究 己进行了多年，已达到了一定的理论深度并付诸实践，而且取得了丰硕的成 果，但还未将主动数据库、实时数据库和内存数据库系统的理论和技术进行 有机的集成。 在主动数据库研究方面，国外已开发出了嵌入e c a ( 事件一条件一活动) 规则的各种系统模型，研究并解决了有关不同类型事件、条件以及触发事务 与被触发活动间关系的说明、识别与处理问题。典型代表有h i p a c 、o d e 、 s t u r b u r s t 等。主动数据库扩充了传统的数据模型，支持对e c a 规则的定 义、操作及规则本身的一致性保证。主动数据库语言不仅耍描述般数据的 定义和操作，而且要能描述规则、事件等。规则的描述包括规则的定义、规 则的增删改、规则的抑制和激活，事件的描述包括事件的定义、事件在语句 中的引用等。一些主动数据库系统采用面向对象数据模型，用对象统一描述 数据和规则。例如h i p a c 系统中规则就是一个实体类，每一条规则是该类 中的一个对象实例。 有关实时数据库的研究始于8 0 年代，1 9 8 2 年美国贝尔实验室的 d k b a r c l a y 等人研制了第一个专用实时数据库管理系统。随后十多年来， 各国的学者就实时数据库系统的设计和实现技术、崩溃恢复、并发控制、事 务调度等方面作了些研究，代表系统有z i p r t d b m s 【2 ”。实时数据库系统 应提供实时数据库语言来描述数据和事务的时间约束。z i p r t d b m s 的应用 编程界面是一组函数调用，由程序员自己构造有效的查询，还没有一个实时 的s q l 编程界面。 国内，华中理工大学现代数据库与信息系统科研组最早开展了a r t d b s 的独创性研究，提出了r t d b s 与a d b s ( a c t i v e d a t a b a s es y s t e m ) 的结合机制 并开发出一个原型系统a r t s i 2 t 】和a r r c s 。目前，该科研组正在和国内 一家投资公司合作，逐步将这些成果向产品化方向转化。 1 4 论文研究的主要内容 本篇论文主要以a r t s d b m s 中的内存数据库子系统a r t s m m d b 为核 7 华中科技大学硕士学位论文 心讨论与研究了支持主动实时数据库的内存数据库技术，包括内存数据库存 储组织、恢复、重装等相关内容。第二节主要是a r t s d b m s 整体系统介绍， 同时对a r t s m m d b 内存数据库系统进行概述：第三节阐述了a r t s m m d b 的存储结构、数据组织与安置策略的实现和相关算法；第四节重点给出了 a r t s m m d b 的一个完整的恢复模型；第五节在上节给出的恢复模型之基础 上讨论了a r t s m m d b 的重装策略：最后对全文进行小结。 华中科技大学硕士学位论文 2 主动实时内存数据库系统a r t s m m d b 2 1a r t s d b m s 的系统结构 a r t s d b m s 是一个基于内存数据库的主动实时数据库的实验产品，是 一个易于扩展的主动实时数据库管理系统。它包括套扩展的s q l 语言， 可以描述主动实时的语义；采用内存数据库作底层支持【2 2 1 ，以提供高效的数 据存储和存取能力，支持一定的事务的可预报性；具有“识时机制”以支持 实时事务的定时限制；它引入了主动机制，允许用户显式说明并自动地监视 与评价特定的情形，当指定情形出现时自动地触发执行一定的活动。系统力 求体积小、灵活高效、可移植和可裁剪。 2 1 1 功能组成与体系结构 a r t s d b m s 的体系结构如图2 1 所示。逻辑上，a r t s d b m s 可分为三 大部分：数据说明子系统d a t as p e c i f i c a t i o n 、数据库运行控制系统 d b c s ( d a t a b a s ec o n t r o ls y s t e m ) 和内存数据库子系统a r t s m m d b 。 数据说明予系统d a t as p e c i f i c a t i o n 包括四个部分： ( 1 ) d a t ad e f i n i t i o n 处理数据定义语句及建立与维护数据字典d d ； ( 2 ) a r tp r o p e r t ys p e c i f i c a t i o n 处理事件和触发器定义语句及建立与维护 事件库e b 和触发器库t b ； ( 3 ) s t a t i c t r a n s a c t i o np r e - a n a l y s i s 进行实时事务在数据说明阶段的静态 预分析处理及建立与维护事务表t t ； ( 4 ) a p p l i c a t i o ns p e c i f i c a t i o n 编译处理应用程序及管理应用程序库p b 。 数据库运行控制系统d b c s 是在数据字典、事件库、触发器库、事务表 和应用程序库这些数据基的基础上实现数据库的管理、控制与操纵的。其主 要任务是事务处理和数据存取，此外，系统初启时进行初始化。当事务到达 时，先进行事务的初始动态预分析处理，然后进行事务处理。事务处理包括 数据操纵、触发器管理和事务管理三个部分。 9 华中科技大学硕士学位论文 删 图2 1a r t s d b m s 体系结构 ( 1 ) 数据操纵负责数据库的操作( 包括数据的插入、删除、修改和查询 等) 和数据库控制( 包括完整性、安全性控制等) ； ( 2 ) 触发器管理主要功能包括事件的探测、处理与发信号；情形( 条件) 的监视与评价；被触发活动的执行处理。 ( 3 ) 事务管理主要负责各种事务管理操作：b e g i n 、c o m m i t 、a b o r t 、 e n d 等：实时优先级分派；实时调度算法；实时并发控制策略。 要保证主动实时数据库的一致性及满足实时事务的时间限制，事务调度 和并发控制是关键。a r t s d b m s 采用一种多级调度策略，即对实时事务与 1 0 华中科技大学硕士学位论文 非实时事务、硬事务与软事务采用不同的调度策略 2 3 】。并发控制则采用一种 乐观方法与封锁机制相结合的策略，既维护数据库的一致性又尽量满足事务 的实时性。 a r t s d b m s 采用内存数据库技术进行数据管理，数据操作在内存数据 库中进行。a r t s m m d b 管理子系统的主要功能是：内存工作区管理；数据 库组织和管理，包括内存版本m - d b 和外存版本s - d b ；数据库存取：内外 存数据交换：恢复处理，包括备份、检验点、日志、恢复算法等。a r t s m m d b 子系统在下一节中详细讨论。 2 1 2 执行模型 a r t s d b m s 的系统执行模型及其工作原理简要描述如下： 1 系统初启阶段 系统初始化按以下步骤执行： ( 1 ) 系统数据结构初始化。 ( 2 ) 内存数据库管理完成内存数据初装，包括对数据字典内容的初装。 ( 3 ) 启动事务管理、主动触发等核心模块。 2 系统运行阶段 ( 1 ) 事务管理模块基于事务的实时级别和时间紧迫度等给事务分派优先 级，事务按优先级降序进行调度。 ( 2 ) 事务执行过程中的b e g i n 、c o m m i t 、a b o r t 和e n d 阶段都调用对应的 事务原语，同时想事务事件探测器发送事务操纵消息。 ( 3 ) 事务对数据的存取有数据操纵模块来实现。数据操纵结合事务优先级 对数据存取进行并发控制。数据存取成功以后应向对象事件探测器发送对象 操纵消息。 ( 4 ) 内存数据库管理模块完成内外存数据交换，物理数据检索和存取，同 时进行日志和数据字典管理，确定数据库检验点( c h e c k p o i n t ) 以便实现数 据库故障恢复。 ( 5 ) 各种操作原语、事务原语以及时钟和外部中断原语在成功完成后都会 华中科技大学硕士学位论文 通知主动机制相应的系统行为已发生。 ( 6 ) 主动监控器启动事件探测器、处理器进行探测处理。 ( 7 ) 探测到某事件发生后，监视器挂起触发事务，调用情形评价器按触发 器优先级降序评价所有被激活的触发器的情形。 ( 8 ) 若评价结果为真，则按被触发活动的指定方式执行相应的活动；若评 价结果为假，可选择执行一定的补偿处理操作。 f 9 ) 解挂触发事务。 2 1 3 功能特性 与传统的d b m s 相比，a i u j d b m s 具有以下特点： 1 兼容现有数据库管理系统的数据语言，构造实时数据模型，增强对事 务的动态预处理能力，提供一种主动实时数据库数据语言a r t d b l ，它能 同时描述事务的定时特性、主动特性两者，它还包括一种扩展的结构化查询 语言e s q l ，支持实时数据查询： 2 提供了一种“完善”集成数据库、实时处理、主动机制和内存数据库 管理技术的系统结构风范： 3 引入“情形”的概念以简化e c a 结构为s a ( s i t u a t i o n 。a c t i o n ) 模 型，实现事务能触发新的活动事务，且使定时限制与其他( 关于数据库状 态或状态变迁等) 限制在语义与处理上统一： 4 扩展了传统事务模型及其a c i d ( a t o m i c i t y 、c o n s i s t e n c y 、i s o l a t i o n 、 d u r a b i l i t y ) 特性； 5 实现了一种实时事务优先级分派策略，并提出了基于e 可串行化标准 的并发控制协议，以支持实时事务调度； 6 为支持事务的定时限制和优先级调度，开发了一种事务的预分析与预 处理技术； 7 建立了种“内存数据库”的概念、原理与体系结构； 8 实现了有效的m m d b 空间组织、存取及相关的恢复技术。 1 2 华中科技大学硕士学位论文 2 2a r t s m m d b 内存数据库系统引论 传统的磁盘数据库在事务运行中要频繁地进行内外存数据交换，这使得 系统性能大为降低，事务的运行时间也难以估计。内存数据库的“工作版本” 常驻内存，事务在运行过程中可消除内外存i o ，可更准确地估算其运行时 f 司，很好地满足实时事务的定时限制和主动实时要求。 然而，内存数据库与运行在大缓冲区条件下的传统数据库有着本质区 别。这是由于，即使数据库的缓冲区足够大，以致可使整个数据库或其“工 作版本”，常驻内存，因而i o 极少，系统性能很好，但它是针对磁盘特性 的，是在假定数据库常驻磁盘的情况下设计的，故仍然不可能具有m m d b 的各种功能特性和优点。例如，它的索引结构还是针对磁盘存取的，数据的 存取仍然必须经过缓冲管理。t o b i nj l e h m a n 等人对其实现的常驻内存数据 库系统s t a r b u r s t 进行了专门的性能测试研究，他们以一个子系统采用内存数 据管理，而另一子系统采用传统的磁盘数据库管理。为了准确和便于比较， 后者的数据也完全置于内存缓冲区中，两者在事务执行期间均无内外存数据 交换，实验结果表明，前者的速度比后者快2 3 到7 1 倍【2 ”。由此可见，在 m m d b 中关于查询处理、并发控制和恢复等的算法与数据结构都进行了重 设计与重构造，它们以c p u 和内存的高效使用而不是磁盘的存取和存储为 目标，两种方法在数据格式和数据结构及用来访问、查找和操纵数据的算法 等方面不一样。 2 2 1 内存数据库的概念 首先，必须确定什么叫“内存数据库”，对此过去曾有过各种不同的说 法，不同的概念决定着采用不同的系统结构、执行模型、实现策略、方法与 技术。我们以为内存数据库的本质特征是其主拷贝或“工作版本”常驻内存， 其形式化的定义如下 2 5 1 ： 、 定义2 j 设有数据库系统d b s ，d b 为d b s 中的数据库，d b m ( t ) 为在 时刻td b 在内存的数据集。d b m ( t ) c d b 。t s 为d b s 中所有可能的事务的 集合，a t ( t ) 为在时刻t 处于活动状态的事务集，a t ( t ) c t s 。d 。( t ) 为事务t 在时刻t 所操作的数据集，d 。( t ) c _ d b 。若在任一时刻t ，均有： 华中科技大学硕士学位论文 v t e a t ( t ) d t ( t ) c d b m ( t ) 成立，d b 为一个内存数据库，简记为m m d b 。 按此定义，m m d b 的“工作版本”( 当然也可以是整个数据库) 常驻内 存，任何一个事务在执行过程中没有内外存间的数据i o 。显然，它需要一 定的内存容量，但并不要求任何时刻整个数据库都必须常驻内存。在定义 2 1 中，数据库的主拷贝是常驻内存的。当事务提交时数据库的外存版本可 以不必立即反映出事务提交后的结果；并且当系统崩溃时应首先恢复在内存 中的数据库主拷贝。 内存数据库的设计应突破传统磁盘数据库系统的设计思路，对物理数据 库的组织、数据库的存取方法、查询处理及优化、并发控制与恢复机制设计 新模式及新算法，有效利用内存空间，发挥内存可直接定址访问的优点，提 高系统性能。 2 2 2 内存数据库系统研究现状 国外对内存数据库的研究自八十年代中期以来，已经引起了数据库界的 极大关注。人们对内存数据库系统的体系结构、存取方法、事务的提交处理、 并发控制以及数据库恢复等关键技术进行了大量的研究和探讨，并取得了丰 富的研究成果，出现了许多试验性的原型系统。例如： ( 1 ) m a r s 是美国s o u t h e r nm e t h o d i s t 大学开发的一个内存数据库管理系 统【2 酣。其体系结构包括两个处理器，其中一个是专用的恢复处理器，同时采 用稳定的非易失内存来支持m m d b 的恢复机制。其并发控制仍采用两段式 封锁方法，但以整个关系作为封锁的粒度。 ( 2 ) m m - d b m s 是w i s c o n s i n 大学研制的内存数据库管理原型系统【2 6 】，它 充分发挥了内存指针的优越性，如临时关系用指向各原关系中元组的指针阵 列表示等，它采用变种的h a s h 方法来存取无序数据，用t 树索引来存取有 序数据。 ( 3 ) t p k 是p r i n c e t o n 大学实现的多处理器内存数据库管理系统【2 们，可同 时进行四种操作：输入、执行、输出和检验点。 人们对m m d b 系统的体系结构、存取方法、事务的并发控制、事务的 1 4 华中科技大学硕士学位论文 提交处理以及m m d b 的故障恢复技术等在理论和实践上进行了大量的研 究、探讨，并取得了一定的研究成果。 2 2 3 内存数据库系统与常驻磁盘数据库系统的比较 内存数据库系统m m d b 与通常的常驻磁盘数据库系统d r d b s ( d i s k r e s i d e n td a t a b a s es y s t e m ) 的区别 2 7 1 主要表现在下列几个方面： 1 存储介质 在磁盘数据库系统中，数据常驻磁盘，磁盘拷贝的数据需按一定的数据 交换策略被调到内存缓冲区后才能被存取。而在内存数据库系统中，数据库 的内存版本为主拷贝，是系统的“工作版本”，其中的数据可被事务直接存 取，其磁盘拷贝主要用于恢复和转存。虽然在两种系统中，对于个给定的 数据对象，都可能存在内存和磁盘两个拷贝，但两者的性质和作用、结构与 存取方法都有根本的不同。在m m d b s 中，事务的“工作数据”在内存，而 它是针对数据库系统的内存拷贝工作的，在其执行过程中没有内外存的i o 。 这样就消除了事务处理的i o 瓶颈问题，从而也极大地提高了系统的性能和 吞吐量。 2 系统特性 内存系统与磁盘系统具有不同的特性，这是引起m m d b s 和d r d b s 之 间的差别的根本所在，主要表现在下列方面： ( 1 ) 内存和磁盘在存取时间上有若干数量级的差别。内存的存取时间在 1 0 “ 秒的数量级而磁盘在5 1 0 。3数量级； ( 2 ) 内存是易失性的( v o l a t i l e ) ，而磁盘是永久性的( p e r m a n e n t ) 存储器，即 当系统断电时，前者所在信息立即消失，来电时也不会恢复，而后者则反之， 继电时保持信息不会消失，再来电时即原样可使用； ( 3 ) 存储格式不同。内存是字节或字编址的，可磁盘是块存储设备； ( 4 ) 数据的存储组织方法对性能影响不同。不同的组织方式对磁盘而言的 性能影响远比对内存影响大，如顺序存取与随机存取的时间对内存没有什么 变化，而对磁盘则几乎有数量级的差别； ( 5 ) 存取方式不同。内存可由处理机直接存取，磁盘则不能；但内存比磁 盘更易于受到来自程序错误的直接数据破坏。 华中科技大学硕士学位论文 这些差异几乎要影响数据库管理的每一方面，进而形成m m d b s 自己的 技术特征。 3 算法设计目标 在d r d b s 中，i 0 是系统的“瓶颈”，系统的算法设计目标是最少的i o 和最大的磁盘空间利用率，即访问磁盘的次数最小，磁盘空间的有效使用率 最大。而在m m d b s 中，外存的i o 己不再是“瓶颈”，系统的算法设计目 标是c p u 和内存空间的高效使用。 4 并发控制 在d r d b s 中，一个数据的加琐开销远远小于它的处理，包括存取的开 销，因此，为了提高事务