（计算机软件与理论专业论文）实时内存数据库的内外存数据交换处理.pdf

华中科技大学硕士学位论文 = = = = ；= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一 ： 摘要 在实时数据库中，要求实时事务在截止期内提交，并存取能反映不断变化的外 部环境的数据，例如温度和股票价格。因为磁盘i o ，传统的数据库不能满足事务和 数据的定时限制。而在内存数据库中大部分的磁盘i o 在系统正常运行时已经被避 免。 传统的内存数据库系统大都假设内存足够大以至于能够容纳整个数据库，后援 备份数据库存储在外存。这种策略在内存不够大的时候就无法工作。尤其是在嵌入 式系统中，内存的大小普遍受到限制。 一个理想的替代策略是仅仅保证个事务在运行时，没有磁盘i o 的阻塞。内存 受限的内存数据库的初始化和数据交换策略很好的实现了内存受限的内存数据库的 概念。在此基础上实现的a r t s e d b 的性能测试表明此策略很好的适应了内存受限 的情况。 在静态预分析提取出的事务和数据信息的基础上，该策略综合考虑了事务的优 先级和数据的特性，包括数据的及时性和存取频率。超存取过程使得事务可以在它 的全部数据进入内存以前启动，减少了错过截止期的概率。这种策略拓宽了内存数 据库对于嵌入式实时系统的实际应用范围。 关键字：实时数据库，内存数据库，数据交换 华中科技大学硕士学位论文 a b s t r a c t 1 1 1r e a l t i m ed a t a b a s e s i ti sd e s i r a b l et oe x e c u t et r a n s a c t i o n sw i t h i nt h e i rd e a d l i n e s u s i n gf r e s h ( t e m p o r a l l yc o n s i s t e n t ) d a t aw h i c hc a nr e f l e c t t h e c o n t i n u o u s l yc h a n g i n g e x t e r n a le n v i r o n m e n t s ，e g ，c u r r e n tt e m p e r a t u r eo rs t o c kp r i c e s t r a d i t i o n a ld a t a b a s e sc a n n o t s u p p o r t t i m ec o n s t r a i n t sa n dd a t a t e m p o r a lc o n s i s t e n c y f o rd i s ki o s w h i l ei n m m d b s ( m a i nm e m o r yd a t a b a s e ) ，m o s t o f d i s ki o sh a sb e e nr e m o v e d d u r i n gt h en o r m a l p r o c e s s i n g t r a d i t i o n a lm m d b sa s s u m et h a tt h ee n t i r ed a t a b a s e sa r es t o r e di nv o l a t i l em a i n m e m o r y , w h i l et h e i rb a c k u pc o p i e sa r ek e p ti n a na r c h i v ed a t a b a s e ( a d ) r e s i d i n go i l s e c o n d a r ys t o r a g e t h i sa p p r o a c hc a nn o tw o r kw h e nt h ev o l a t i l em a i nm e m o r yi s n o t l a r g ee n o u g h ，e s p e c i a l l yi ne m b e d d e ds y s t e m s w i t hl i m i t e dm a i n m e m o r y t h ea p p e a l i n ga l t e r n a t i v ei sj u s tt og u a r a n t e et h a tn od i s ki o sb l o c kat r a n s a c t i o n w h e n r u n n i n gi t i nt h i sp a p e r , i n i t i a l i z a t i o na n d d a t ae x c h a n g es c h e m e sa r ep r o p o s e dt o r e a l i z et h en e wd e f l n i t i o no fm m d bw i t hl i m i t e dm a i nm e m o r y , b a s e do nw h i c ha n a r t s e d bi sr e a l i z e d i t sp e r f o r m a n c ei n d i c a t e st h a tt h ei n i t i a l i z a t i o na n dd a t ae x c h a n g e s c h e m ea d a p t sw e l lt ot h el i m i t e dm a i nm e m o r y t h es c h e m et a k e st r a n s a c t i o n p r i o r i t ya n d d a t ac h a r a c t e r i s t i c ss u c ha st e m p o r a l i t ya n d a c c e s sf r e q u e n c yi n t oa c c o u n tf o rt h ed a t ae x c h a n g e m o s to f t h es c h e m ei sb a s e do nt h e r e s u l to fs t a t i c p r e a n a l y s i s o ft r a n s a c t i o nf o ra r t s e d b ，w h i c hd i s t i l l s t h et i m e i n f o r m a t i o n ，d a t ac h a r a c t e r i s t i c s ，a n d a c c e s sp r o c e s s e so ft h et r a n s a c t i o n t h e “s u p e r a c c e s sp r o c e s s ”m a k e sat r a n s a c t i o ns t a r t e db e f o r ei t sw h o l e d a t a s e tp l a c e di na r t s e d b ， r e d u c i n gt h ep r o b a b i l i t yo fm i s s i n gd e a d l i n e t h i sn e wa p p r o a c hg r e a t l yi m p r o v e st h e p r a c t i c a b i l i t yo f m m d b st oe m b e d d e dr e a l - t i m ed a t a b a s e k e y w o r d ：r e a l - t i m ed a t a b a s e ，m a i nm e m o r yd a t a b a s e ，d a t ae x c h a n g e i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：、之墨幺专 日期：, 4o o 修乎月；。日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密口。 ( 请在以上方框内打“”) 学位论文作者签名 日期：z ，绎午月；。日 指导教师签名 日期：6 砰年，月；日 华中科技大学硕士学位论文 1 1 课题背景 1绪论 数据库技术是计算机科学的重要分支之一，它已经成为计算机系统和应用系统 的重要支柱。从六十年代开始，数据库技术从第一代的层次和网状数据库发展为第 二代的关系数据库模型和面向新一代的应用技术j 。 数据库技术在商务和事务性应用领域中的广泛应用，随着应用的深入和应用领 域的不断扩大，对数据库又提出了新的更高的要求。为此人们开始探索数据库的新 的研究方向，如分布式数据库、多媒体数据库、数据库与人工智能的结合演绎 数据库和知识库及面向对象的数据库系统等。这些应用对数据库提出了新的要求， 其中有相当一部分是传统数据库不能满足的，如在实对应用方面，传统数据库技术 遇到了强有力的挑战，传统数据库的局限性，使其在军事指挥、航空及航天控制系 统、雷达信号和跟踪识别、交通控制系统以及电力系统控制等方面的应用受到了诸 多限制。传统的数据库系统不适应实时应用要求主要原因是它不考虑数据及与数据 处理相联系的定时限制；维护数据的一致性、完整性与安全性的对象是持久数据； 事务模型和调度策略也是侧重最大限度的提高事务吞吐率和减少响应时间，而不关 心各个事务的特定的时间约束。为了解决这些问题，八十年代后期人们提出了实时 数据库系统的概念，开辟了数据库研究的新天地。传统的数据库管理系统也无法满 足些非传统的应用如网络管理，空中交通管制，c i m 以及工程设计等的需求。这 些非传统的应用要求在没有用户或应用程序的干预下，系统能够自动的监视数据库 状态的改变，并依据状态的改变执行相应的活动。主动数据库提供的机制可以解决 这些问题。 本课题组的研究项目a r t s e d b 在继承华中科技大学数据库与信息系统科研组 最早开展的a r t d b m s 的研究成果的基础上，根据新的应用需求，结合了实时、主 动、内存数据库的各项特征而进行的研究课题。a r t s e d b 不同于传统的数据库，它 华中科技大学硕士学位论文 是实时主动数据库，具有实时数据库的特性：有完备的事务模型，传统的平坦原子 事务模型已不适应实时环境的要求，需要复杂的事务模型如循环事务模型( 1 0 0 p t r a n s a c t i o n s ) ，嵌套事务模型( n e s t e dt r a n s a c t i o n s ) 等；系统具有及时性，对于实时应用 而言及时性某种程度上比正确性更有意义，并非所有的数据都是持久的，许多数据 是短暂的，只在指定时限内有效；事务具有合作性，事务之间存在着相关性，要求 合作；系统要求一致性，包括内部一致性和外部一致性。a r t s e d b 除具有上述的实 时数据库特性外，还融入了主动数据库( a c t i v ed a t a b a s e ) 的一些特点。主动数据库与 传统的数据库系统的区别在于传统的数据库是被动的，仅当用户或应用程序显示请 求时才执行相应的动作，因此可以说传统的数据库是用户或程序驱动的。而主动数 据库是数据驱动的，它不仅能够向用户提供数据库中当前有效的数据，还能够根据 用户或应用程序预先设置的条件或数据库内部状态，主动提供信息给用户或应用程 序。 1 2 国内外概况 1 2 1内存数据库的研究现状 有两大因素决定着内存数据库的研究与发展。一是现代应用要求数据库有强的 功能和高的性能。传统的数据库基本用于商务和事务应用，而现代应用主要是：集 成的办公系统，包括信息检索与过滤( f i l t e r i n g ) 、超文本、超媒体等应用；工程型应 用，包括过程控制、c a d c a m 、c i m s 、指挥控制、实时数据处理、网络( 如电话、 电力和数据网等) 管理；人工智能，如自然语言处理、专家系统、知识处理、演绎与 推理或规则系统、机器人与机器视觉等。这种现代( 非传统) 应用要求新型的现代数据 库系统支持，尤其是想保证“硬实时”这样的性能要求，传统的常驻磁盘数据库系 统对这些是无能为力的。 另一因素是存储量很大而廉价的内存的成功使用。现已有1 g b 的d r a m ，许多 现在的d b m s 已经可以在1 g b 的内存上运行；在过去的十多年中，单个d r m a 芯 片的b i t 数几乎以每三年翻两番的速率在增长。当前对这种增长率似乎还没有一个 可见的尽头。今年d b m s 可望有2 5 6 g b 工作内存。而内存的价格在过去的2 0 年中 华中科技大学硕士学位论文 几乎降到原来的百分之一。由于上述的理由，自2 0 世纪8 0 年代早期开始，研究者 们就进行将整个数据库或它的大部分放在内存的研究上。通过将数据库的“主版本” 常驻内存可使系统性能获得很大的改善，如i o 操作大量减少、事务的状态转换机器 相联的c p u 高速缓存的替换大量减少、锁的竞争下降、更有效的内存查找结构和查 询处理可被使用等。 对在数据库系统中使用大内存，人们经历过两种主要的途径。一是让缓冲池很 大，以至使每一事务所需数据的大部分甚至全部都保持在内存。这种方法与传统的 数据库无任何区别，只不过缓冲区很大而己，数据常驻磁盘，数据库的磁盘版本仍 是“主版本”或“工作版本”。采用这种方法是，使磁盘存取最少必然还是算法设计 的主要性能目标。另一种主要途径使内存常驻数据库法，它使用内存作为数据库的 主要存储，即数据库的内存版本使“主版本”或“工作版本”，而磁盘版只是做后备。 这样关于查询处理、并发控制和恢复等的算法与数据结构都必须重新设计与重构造， 他们以c p u 和内存的高效使用，而不是磁盘的存取和存储为目标。两种方法在数据 格式和数据结构及用来访问、查找和操纵数据的算法等方面不一样，前者不能算内 存数据库，只有后者才是。 2 0 世纪8 0 年代中期以来，内存数据库引起了越来越多的数据库研究者们的兴 趣，对至今日，人们已对它的体系结构、数据组织与存取方法、事务处理、并发控 制和恢复技术等方面进行了大量的探讨与研究，取得了丰富的成果。在体系结构方 面，为了支持m m d b s 的恢复，人们从系统硬、软件支持上着手，开发了多种结构 形式，如使用多处理机结构，以一处理机专用于有关恢复方面的处理：以专用的 n v r a m 做活动日志、工作区等。 在存取方法方面，人们开发了许多新的、利于内存数据存取的数据存储组织与 索引结构及存取策略，如“多目录h a s h ”结构、t 一树索引等。在研究中，人们发现 对当整个数据库都在内存时，a v l 树比b 一树提供更好的性能。 在事务及查询处理方面，主要在事务的提交及与之相联的日志记录、查询优化， 尤其是联机查询的优化、进行了多方面的研究，开发了一些有效的技术a 如开发了 “提前提交”策略，即事务提交时，只要有关的日志记录写入固定的缓冲区，即可 华中科技大学硕士学位论文 释放事务的锁，而无需等日志写入磁盘后。这样可减少阻塞延迟，加速并发事务的 响应时间。 在并发控制发面，人们进行了多方面的实验研究，提出了二级层次封锁协议方 案、乐观并发控制方法、使用可扩展的h a s h i n g 技术的方法等。但究竟哪种方法更适 台m m d b s ，尚未见到有关的分析、评价文章。有的也就用标准的2 - p l ，有的甚至 认为在m m d b s 中干脆就不要并发控制，而用“完全串行”执行。串行执行对短事 务也许可行，但当事务很长时，串行执行显然是行不通的。 在内存数据库的恢复方面，研究集中在检验点操作及相应日志的记录、内存数 据库装入与重装等，如f u z z y ( 模糊) 检验点策略、b l a c k w h i t e ( 黑伯) 策略、 c o p y o n u p d a t e ( 变更拷贝) 检验点等。对内存数据装入有有序装入、带优先级的 装入、考虑存取频率的装入、以及组合优先级和频率等的所谓“聪明”装入等策略。 1 2 2 内存数据库对实时数据库的支持 现代数据库应用有着与传统的商务或事务型应用不同的要求：事务有定时限制； 数据有“时间一致性”，有“有效期”。实时事务及其数据都具有定时限制，事务的正 确性不仅依赖其逻辑结果，还依赖于结果产生的时间，因此要求系统能较高准确的 预报事务的运行时间。实时数据库系统( r e a l t i m ed a t a b a s es y s t e m ，简称r t d b s ) 就是其 数据和事务均可以有显式的定时限制的数据库系统，系统的正确性不仅依赖于事务产 生的逻辑结果，而且依赖于逻辑结果产生的时间。这就要求r t d b s 能够较准确地估 计事务在系统中的运行时间，但以磁盘数据库系统而言，存在着许多不可预报的因素， 其中重要的原因之一是磁盘数据的i o 。而对于内存数据库而言，由于整个数据库或 “工作”部分已经放入内存，一个事务在执行过程中没有i o ，则为系统较准确的估 算和安排事务的运行时间，使之具有较好的动态可预报性提供有力的支持，同时也 为实现事务的定时限制打下了基础。 m m d b s 较之通常的磁盘数据库更为脆弱，更易受到多种系统故障的伤害，因为除 了介质故障，事务与系统故障也都可以直接伤害数据库，每次恢复都必须自后援存储 器重装。因此，m d b 的装入( 包括初装与重装) 更为频繁，其作用对系统来说显得至关 重要。 华中科技大学硕士学位论文 12 3 内存受限的内存数据库 国际上，传统的内存数据库都假设全部的外存数据库都在内存，外存数据库作为 后援数据库。可是当内存不能容纳整个外存数据库的时候，这种方法就不能工作。 一些实时数据库甚至还基于外存数据库，这也反应了内存数据库本身研究的难度。 而如何在内存不足的情况下，恰当的安排数据交换的时机和策略，从而保证内存数 据库的概念，进而满足实时数据库的要求，就更是一个创新的难题。目前，国际上 还没有实现内存受限情况下的内存数据库的原型系统。 1 3 课题的研究内容 a r t s e d b 是一种实时主动数据库系统。其数据交换部分的研究内容包括： 1 3 1用数据交换帮助实现内存受限的内存数据库的概念 为了消除磁盘o ，传统的内存数据库假设内存可以容纳全部的外存数据库，外 存数据库作为后援数据库弘。j 1 ，这样就回避了数据装入，换出的问题。可是当内存不 能容纳整个外存数据库的时候，这种方法就不能工作。一些实时数据库甚至还基于 外存数据库一j ，这也反应了内存数据库本身研究的难度。而如何在内存受限的情况下， 恰当的安排数据交换的时机和策略，从而保证内存数据库的概念，进而满足实时数 据库的要求，就更是一个创新性难题。数据交换就是根据实时事务的预分析和内存 受限的具体情况来实现内存数据库的概念。从内存数据库的初始化开始，到数据库 运行时的装入换出，数据交换实现了一套完整的策略。 1 3 2内存受限的内存数据库的初始化 由于内存数据库并不能容纳全部的外存数据库，所以内存数据库初始化的时候， 需要选择装入最应该被装入的数据。但是在内存数据库初始化的时候，内存到底能 容纳多少事务的数据还是个未知数，事务类型、开始时间、结束时间等标准的相互 冲突，都给事务的选择带来了难度。在静态预分析的基础上，把全部分析好的事务 排成一个队列。内存数据库初始化的时候从队列的第一个事务开始装入，无论内存 有多大，装入的数据都是最应该装入的数据。 华中科技大学硕士学位论文 1 3 3 内存受限的内存数据库的数据装入与换出 内存数据库初始化成功以后，系统开始运行。如果接纳一个事务后发现其数据 不在内存。仍然要进行数据装入。为了让系统能正常的运行，尽量减少因数据装入 而造成超过截止期的事务数目增多，要对启动数据装入的时机，策略进行深入的研 究。 换入数据的时候如果达到内存的阈值，就有要启动数据换出。如何将数据换出 对系统已经接纳的事务的运行的影响降低到最小是数据换出策略的主要目标。 1 3 4 数据交换与其他部分的联系 由于内存受限这一现实条件，数据交换与a r t s e d b 的其他部分有了更多的联 系。 ( 1 ) 据交换与查询优化的联系。由于传统的查询优化是以减少i o 为目的的。而 内存数据库在个事务执行的时候是没有磁盘i o 的。如果接纳的事务的数据没有在 内存数据库中，则需要数据交换统一处理。所以数据交换就和查询处理有了联系。 查询优化依赖于数据的存储方法、索引的结构等。传统的查询优化的目标是减少磁 盘的存取量，以此为目的查询优化方法不适用于内存数据库。目前对内存数据库的理 论和技术进行了许多研究和探讨，如内存数据库的数据存储结构、数据组织管理、并 发控制等 5 , 6 】。虽然存储空间和c p u 代价常常作为评价查询优化的主要依据，但系统 讨论查询优化处理还鲜有文献论述【“。在内存数据库系统中，由于事务存取的数据集 在内存中，内存数据库系统查询优化的目标是节省内存和c p u 时间。为了达到这一目 标，先要为内存数据库选用合适的数据存储结构，在此基础上设计高效的关系代数操 作算法，再利用等价定理进行逻辑优化，在执行时进行物理优化。 ( 2 1 数据交换与并发控制的联系。由于内存资源的紧张和一个事务的数据集全部 在内存而使事务执行的效率数量级的提高，时空的矛盾在内存数据库中，更侧重于 节约内存空间。同时节约了内存空间就可以让更多的事务更早的执行又可以节约时 间。个能够节约内存，并且可以满足数据交换运行时机的并发控制策略就是数据 交换所要求的。 华中科技大学硕士学位论文 2a r t s e d b 系统分析 a r t s b d b 是在l i n u x 环境下研究开发的一个基于客户服务器模式的主动实 时内存数据库管理系统。a r t s e d b 支持事务的定时限制，支持触发器机制，同时 以内存数据库为底层支持，具有高效的数据存储和存取功能。本章主要介绍 a r t s e d b 的整体结构，内存受限的内存数据库的概念、数据交换在a r t s e d b 中 的作用和与其他子系统之间的关系。 2 1a f 玎- e d b 的体系结构 a r t s e d b 的体系结构如图2 1 所示。 a r t s e d b 主要由以下几大模块构成： ( 1 ) 数据定义( d a t ad e f i n i t i o n ) 与数据说日) j ( d a t as p e c i f i c a t i o n ) 数据定义模块的功 能如下： 扩展的s q l 语言( e s q l ) 、及嵌入主语言c 的d m l 的处理； 数据字典d d 的建立与维护； 事件的定义及事件库( e b ) 的维护；触发器库( t b ) 的维护； 事务( 包括事务间结构关系) 的定义及事务表维护； 应用程序的定义及应用链接库的管理。 ( 2 ) 事务处理模块的主要功能如下： 各种事务操作原语：b e g i n 、c o m m i t 、a b o r t 、e n d ； 主动实时事务优先级的合理分派； 事务执行的有效调度及并发控制。 ( 3 ) 主动机制部分的主要功能如下： 事件( 特别是复合事件) 的探测； 条件( 特别是复合条件) 的评价； 规则的静态分析： 华中科技大学硕士学位论文 通知事务处理模块调度被触发活动或直接调度被触发的活动。 ( 4 ) 内存管理模块功能如下： 内存与缓冲区的管理； 有效的数据存取路径；合理的数据装入算法； 适当的内外存数据交换策略； 恢复处理，包括备份、检验点、日志等。 f 5 ) 数据操纵( d a t a m a n i ) 部分跟传统数据库类似，实现对数据库的插入、删除、 修改等操作；查询优化。 图2 1a r t s e d b 的体系结构 8 华中科技大学硕士学位论文 2 2 内存数据库的相关概念 2 2 1内存数据库定义 在内存没有足够大以容纳全部外存数据库的时候，内存数据库定义如下： 定义2 1 ：设有数据库系统d b s ，d b 为d b s 中的数据库，d b m ( t ) 为在时刻 t ，d b 在内存的数据集，d b m ( t ) d b 。t s 为d b s 中所有可能的事务的集合， a t ( t ) 为在时刻t 处于活动状态的事务集，a t ( t ) c t s 。d t ( t ) 为事务t 在时刻 t 所操作的数据集，d t ( t ) c _ d b 。若在任一时刻t ，均有： v t a t ( t ) d t ( t ) d b m ( t ) 成立，则称d b s 为一个内存数据库系统，简写为m m d b s ；d b 为一个内存数 据库，简写为m m d b 【i j 。 除了内存不必足够的大以容纳全部的外存数据库，a r t s e d b 的架构在整体上和 国际上传统的内存数据库的是相似的。为了提高数据交换的效率，内存和外存被划分 成固定的大小，并且内存的段的大小等于外存的块。 2 2 2 实时数据库的静态预分析事务 为了更好的满足实时事务的定时限制，实时数据库把可以静态预分析的实时事 务和对系统影响比较大的非实时事务进行静态的预分析，进行知识提取和构造，为 数据交换提供一些必需的信息： ( 1 ) 事务类型：硬实时事务，软实时事务，非实时事务。 ( 2 ) 事务的开始时间，包括绝对开始时间和相对开始时间。 ( 3 ) 事务的截止期，包括静态截止期和相对截止期。 f 4 1 事务的存取过程集，也就是事务对数据的约束条件。如果约束条件中包含动 态执行时才能获得的信息，则静态预分析不提取对应的约束条件。所以按照静态预 分析的存取过程集取得的数据要大于等于事务实际需要的数据。 ( 1 ) 数据的有效期，是指数据库中的数据反应的外部环境与真实的现实世界是否 一致。当事务存取了超过数据有效期的数据，就不能保证事务的正确性。 华中科技大学硕士学位论文 ( 2 ) “超存取过程集”，由于实时数据库宁可要不完整但及时的数据也不要完整但 过时的数据。所以如果一个静态预分析的实时事务被接纳的时候，其数据集不在内 存。启动的是由其“超存取过程集”组成的“超事务”，可以使原事务在有一部分数 据集进入内存后就可以启动，“超存取过程的实现算法见文献 8 a1 们。 ( 3 ) 最坏事务数据装入时间的静态估计。通过判断一个事务所存取的全部关系在 外存有多少块的记录和系统i o 一次所花费的时间，静态估计装入一个事务的数据， 在最坏情况下，需要多长时间。 定义2 2 ：这样一个静态预分析事务t 可以表示为一个7 元组：，a ，rp ，一，c ，t ) ， ( 1 ) e = e 1 ，e 2 ，e n ) 为事件的集合，往往是外部事件。 ( 2 ) a = a l ，a 2 ，a n ) 为关于数据库活动的集合。 ( 3 ) r = r l ，r 2 ，m ) 为对系统环境反应的集合。 ( 4 ) p = p l ，p 2 ，p n ) 为对应于a 的存取过程集合。 ( 5 ) 一为定义于e ，a ，r 上的偏序关系。 ( 6 1c 为控制结构的集合，有4 种控制结构。 ( 7 1t 为实时事务的定时限制。 定义2 3 ：p 。是p ；的超存取过程， d ( p ，) _ d d ( p ，) ，p 。的存取数据集是“的子集 p 。+ d o e s n o tu p d a t ed ( p 。+ ) ，n 不进行更新操作 定义2 4 ：r 是t 的超事务：( p ) p = p ， o i n ) 为定义在p 上的偏序集，和t 中的相同 2 3a r t s e d b 中数据交换的作用 内存数据库并未假定任何时候整个数据库都在内存，还需要外存支持，因而依 然有对外存的y o 。因此，内外存数据交换策略成为内存数据库的一个重要问题。 内存数据库( m m d b ) 的定义未要求( 也不应该要求) 内存要足够大，以致整个数据 华中科技大学硕士学位论文 库始终都在内存。故系统仍然要借助外存的能力，通过提供一种内外存数据交换策 略来支持m m d b 。数据交换策略必须考虑如下特征： ( 1 ) 活跃性：即数据被存取的频率； ( 2 ) 数据流行性：指数据库中数据所反映的现实世界状态与现实世界当前的真实 状态的一致性程度。具体说来，以下几个因素决定数据的交换策略： 高易变的实时数据必须常驻内存0 d b 中，不能被交换出去，否则经磁盘存 取可能造成数据失效； 活跃或高频数据应常驻内存0 一d b 中，一般不应被交换出去。这是因为按l u r 的“预言”思想，交换出去的数据应是“未来”较少被访问f 低频) 的数据，最近最少 使用“预示”未来一段时间也会最少使用； 立即流行的数据在第一个处理请求以前不能被交换出去，因为它“立即”就 要被存取了； 高优先级事务的数据在事务的活动期不能被交换出去。尤其当事务是周期性 的事务时，其数据应尽可能常驻内存0 d b ，避免被交换出去。为此可给内存中的每 一数据赋以“优先级天花板”，即存取它的各事务的优先级的最高者，每当要交换时， 选取“优先级天花板”最低者换出： 非永久数据和关键数据最好不要换出。非永久数据无须换出，不久就成为无 用，交换反而增加系统负担。关键数据至关重要，要保证对它的存取的有效性；另一 方面，每当变更时，都必须保留稳定( 非易逝) 副本，这又提供了一种交换时机综合 上述因素，可构造对于任数据x 的“交换函数”p 1 ： 8 巡! 苎2 三里! ! y f l 2 旦! ! i ! ! g 曲过亚坚逝嵝( 盐当旦里m ! 出1 6 k ( 鬯1 其中v ( x ) 是x 的有效期，q ( x ) 为x 的平均存取频率，c ( x ) 为x 的流行性程度( 即 可延时处理的延时长度) ，p c ( x ) 为x 的“优先级天花板”，其值越大，交换函数值越 低，d ( x ) 表示x 的永久性程度( 即需保存的时间长度) ，k ( x ) 为x 的关键性程度，当 x 1 o 时，则表示x 刚变更，需留稳定副本，正是好的交换时机，w i ( i = l ，2 ，6 ) 为加权， 它需要针对系统的实际情况和应用语义灵活动态地选定适当值。每当有交换要求对， 计算各s w ( x ) 的值，取其最大者交换出内存。要注意的是，对于某一数据，其s w ( x ) 华中科技大学硕士学位论文 值将随时间的推移和活动事务的不同而变化，因为各项都是动态变化的。下面介绍 一种具体的交换模型。 2 4 数据交换的实现模型 2 ，4 ，1 内存数据库图 在m m d b s 中，事务的“工作数据”在内存中，它针对数据库的内存主拷贝工作。 在一个事务的执行过程中，事务没有内外存数据交换。这时系统的“瓶颈”主要是有 限的内存空间和大量的事务数据之间的矛盾。因而，在内存数据库的物理组织上主要 考虑提高数据空间的利用率及加速各种操作的执行速度。内存数据库图是一种有效 的内存组织方式，能极大地节约内存数据空间【1 。 设d b 为一个关系的集合，r 表示其中的关系，t 表示关系的元组，d i ( i = l ，2 ，n ) 表示 各关系属性对应的不同值域( d o m a i n ) ，令t d b 和v i ) b 分别为d b 的所有元组的集合 和所有属性值的集合，即 t d b = t r i r e d b ；v d b u d f i - - 1 式中，t r 为关系r 的所有元组的集合，即t r = 绯r 八r d b l 。令r k ( t ) 表示r 的元组t 的第k 个属性值。这里给出内存数据库图的形式定义。 定义：一个关系集的内存数据库图( m m d b g ) 是一个“标值”的( v a l u e d ) 双向图 g ( x ，a ) ，其中x = ( t d b ，v d b ) 为g 的顶点集；a 为其边集，当且仅当t t d b ，v v d b ( r k ( t ) = v ) 时，一个“标值”为r k 的边( t ，v , r k ) ea 。 从定义可以看出，一个m m d b g 由一个元组顶点子集，一个属性值顶点子集和连 接这两个子集的边集构成。元组顶点集中包含了d b 中的所有元组；属性值顶点子 集中包含了d b 中的所有属性值；m m d b g 中的每条边( t ，v , r k ) 为具有权值的边，其权 值标识了属性值v 为关系r 中元组t 的第k 个属性，它连接一个元组顶点t 和一个属 性值顶点v 。这样，一个元组顶点便可以通过带权值的边与其所有的属性值链接。一 个属性值顶点也可以通过带权值的边与所有和它相关的元组链接。 华中科技大学硕士学位论文 2 , 4 2 内存受限的内存数据库模型 a r t s e d b 是由本实验室自主开发的d b m s ，也是用来进行性能测试的系统。 如图2 2 所示，a r t s e d b 的系统架构设计成适应在内存受限的情况，更好的在外存 数据库不能全部装入内存的条件下实现m m d b ，传统的内存数据库的架构如图2 3 所示。在a r t s e d b 中，主存储器是易失内存m 1 ，全部事务的数据集都存储在m 1 ， 所以m 1 被称为o d b ( o 筋c i a ld a t a b a s e ) 。临对的数据如目志被记录在t - d b 中。 为了安全并快速的存取系统数据包括数据字典，应用程序库，事件库，触发器库和 事务表也被记录在t d b 中。m d b ，s - d b 和后援数据库a - d b 的存储结构是相同 的：因为数据交换和刷新外存数据库都是以页为单元，它们被分成固定的相同大小 的页来存储记录以提高效率。 图2 2a r t s - e d b 的架构 图2 3 传统m m d b 的架构 华中科技大学硕士学位论文 图2 4m m d b 的内存分区 如图2 4 所示，m d b 按照区段式来分配内存，每个区对应一个关系，包含这个 关系在内存的元组。事务缓冲区是为事务运行时分配的内存而准备的，以存放事务 的中间和最终结果。内存数据库的阈值只是在内存数据库初始化的时候是确定不变 的，当系统运行以后，可以动态调整阈值的大小，只要保证m m d b 的数据和事务缓 冲区的数据没有交叉存放即可。m m d b 分配空间尽量的从高地址向低地址，而事务缓 冲区则尽量的从低到高，这样就可以最大限度的使用内存。 2 4 3 基于内存受限的内存数据库的数据交换模型 为了消除磁盘i o ，传统的内存数据库假设内存可以容纳全部的外存数据库，外 存数据库作为后援数据库，这样就回避了数据装入，换出的问题。可是当内存不能 容纳整个外存数据库的时候，这种方法就不能工作。一些实时数据库甚至还基于外 存数据库，这也反应了内存数据库本身研究的难度。而如何在内存受限的情况下， 恰当的安排数据交换的时机和策略，从而保证内存数据库的概念，进而满足实时数 据库的要求，就更是一个创新性难题。目前，还没有听说国外已经有实现内存受限 情况下的内存数据库的原型系统。内存受限的内存数据库初始化和数据交换的策略 很好的解决了这个阀题，并在此基础上实现了主动实时内存数据库一a r t s - e d b 。 如图2 5 所示，内存数据库初始化主要由l o a d e r 负责。而内存受限的内存数据 库的数据交换，则如图2 6 所示，主要由e x c h a n g e r 负责。 ( 1 1 内存受限的内存数据库的初始化 1 4 华中科技大学硕士学位论文 图2 5 内存数据库初始化模型图 ( 2 ) 内存受限的内存数据库的数据交换 2 5 小结 图2 6 数据交换模型图 本章给出了a r t s e d b 的体系结构图，介绍了内存受限的内存数据库的相关概 念，强调了数据交换对于内存受限的内存数据库的作用，最后阐述了数据交换的实 现模型。为深入，细致的描述数据交换的实现打下了基础。 华中科技大学硕士学位论文 3 内存受限的内存数据库的初始化 3 1 内存数据库初始化的数据选择 实时数据库系统是事务与数据在其中都可以有定时特性或显式的定时限制的数 据库系统。实时数据库事务体现了实时任务和传统数据库事务两者的特征，但并非它 们在概念、技术、机制上的可以简单集成。实时事务超过截止期可能带来灾难性后 果其高性能要求以内存数据库( m m d b ) 作为其底层支持，以使系统对 事务的执行能预先做出安排。对于内存数据库的定义有很多种不同的说法，判断 一个数据库是否为内存数据库的标准是看其数据库的主拷贝或“工作版本”是否常 驻内存。所以内存数据库初始化的数据选择也成为了实时内存数据库第一个要解决 的问题。 3 1 1影响数据装入的主要因素 有两方面的因素影响m d b 的数据装入以及与外存数据交换的策略，一方面是数 据本身的特性，另一方面是应用( 或事务) 的特征： ( 1 ) 数据易变性，是指数据的变更速率。实时数据有着不同的变化速率，有的随时间 的推移而频繁地变化，有的很长时间才变，而有的甚至是静态的。令d e v i 表示数据d 的 “外部有效期”【1 2 j ，i d e v i l 表示d e v i 的长度。若 d e v i l t 2 ，则是( 或认为是) 稳定( 或不易变) 的，t l 和t 2 为由应 用语义决定的两个闽值。 f 2 ) 活跃性，是指数据被存取的频率。对数据库的存取也有所谓的“8 0 - 2 0 ”规律， 即大部分的数据库存取集中在少部分的某些数据上，所以这种数据的存取频率很高， 称为活跃数据。显然，应该使活跃数据能便于有效存取。 ( 3 1 数据的流行性，是指数据库中数据所反映的现实世界的状态与现实世界的真 实状态的时间一致性程度。它可以用当前时间一c 与d e v i 之间的时序关系 t 来描述： 若tc d e v i ，则它是“当前流行”的；若tc m 的时候，说此实时事务的数据不必现在就装入。所谓的n m 可以理 解为n x * m ，在a r t s e d b 中x 初始值设定为5 。 所以当不能满足以上条件的时候，就称该实时事务的数据是在初始化的时候就要装 华中科技大学硕士学位论文 入的。反之，则是可以暂不装入，即定时启动装入的实时事务。在这个定义的基础上， 静态预分析事务链表( 在a r t s e d b 中表示为i n m e mt r a nl i n e ) 的形成策略如下： ( 1 ) 队列的开始是随机发生的硬实时事务。由于硬实时事务如果超过了截止期会 给系统带来毁灭性的后果，所以随机发生的硬实时事务的数据应该最先被调入内存。 ( 2 ) 其次是周期事务的数据。由于实时数据库的周期事务频繁的执行，如果不能 保证数据在内存，就会发生“抖动”，严重影响系统的效率，所以周期事务的数据也 应该被调入内存。 ( 3 ) 然后是内存数据库初始化时就应该把数据调入内存，否则会超过截止期的硬 实时事务。如果在装入以上三种事务的数据的过程中，内存耗尽，则内存数据库初 始化失败。 f 4 ) 接下来同3 ，装入内存数据库初始化时就应该装入的软实时事务。 ( 5 ) 然后装入的是随机发生的软实时事务的数据。 ( 6 ) 如果在以上两类事务的装入过程中，内存耗尽，则内存数据库虽然初始化成 功，但是性能堪忧。 ( 7 ) 接下来为所有定时启动的实时事务设置定时器，在开始时间t s 前y * m 的时 间t l 启动该事务的数据装入，在a r t s e d b 中，y 的初始值是2 ，以保证该事务的 数据可以换入。把设置了定时器的实时事务按照t 1 和非实时事务的t s 按照时f 日qj i n 序 排列，随机发生的非实时事务排在最后。如果事务的开始时间相同，则截止期和数 据有效期最早的最优先。如果在装入此类事务的过程中，内存耗尽或者内存足够大 把全部队列的事务都装入完毕，都宣布内存数据库初始化成功完成。 以上的装入顺序保证了无论内存有多大，装入的数据从事务类型，事务的开始 时间和截止期，以及数据的有效期来看都是最应该装入的数据。 3 2内存数据库的初始化策略 3 2 1内存数据库初始化策略 在静态预分析事务链表( i n m e m t r a n l i n e ) 的基础上， 初始装入的策略本应 很简单：只需要顺序装入即可。可是和数据换出结合起来考虑以后，在实现初始装 华中科技大学硕士学位论文 入的时候，运用了一些技巧，为巧妙地实现数据换出中选择换出数据的策略打下了 基础。 当装入静态预分析事务链表( i n m e r nt r a nl i n e ) 的第一个节点数据的时候，在 i i l m e mt r a nl i n e ( 数据结构为一个双向的链表) 里面要记录关系号和段号。当第2 个装入的时候就判断是否已经在内存数据库了，如果是，则不记录；如果否，则记 录。依次类推，直到内存数据库初始化完毕。此时第n 个元素记录的是前面n 1 个 静态预分析的事务不用而它自己用的数据。 假设事务正装入的数据集是d ：，其实际需要的全部数据集为d 0 当第n 个事务装 入完数据后，其记录的数据是： d 。= d ：- ( d ：u d ；d ：一) = d ：一( d ：u d ：或一，) 3 2 2 内存数据库初始化数据装入策略的优点 由于数据换出