（计算机应用技术专业论文）数据库结果集缓存的研究与实现.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 随着社会信息化程度越来越高，各种各样的应用系统处理的数据量也就越 来越大，因此，怎样提高数据库访问的响应速度就显得尤为重要。结果集缓 存就是一种能够提高数据库响应速度的查询优化技术。结果集缓存把查询结 果或者查询的中间结果存储在内存中，用户在进行查询操作时，可以通过直 接匹配的方法，从内存中获取所需要的数据，避免了直接访问大量的原始基 表以及耗时的连接操作，有效的提高了查询的执行效率。 本文首先介绍了结果集缓存的概念，并阐述在查询系统中结果集缓存所处 的位置。其次研究了实现结果集缓存需要的三个技术点：内存空间管理；事 务管理以及缓存一致性管理。在这些研究中，提出了适用于结果集缓存的改 进算法。最后在国产数据库o s c a r 上设计并实现了服务器端结果集缓存，重点 对内存分配算法，内存索引算法，缓存替换策略，缓存失效处理，并发控制 做了深入研究。并对客户端结果集缓存的主要技术难点缓存一致性算法，提 出了解决方案和详细设计。 本文的组织结构是：首先介绍了结果集缓存的概念，对o r a c l e 数据库的 结果集缓存功能做了调研分析，结合国产数据库o s c a r 分析了实现结果集缓存 的可行性；其次分析实现结果集缓存需要解决的技术难题；最后在论文其他 章节就这些难题，给出了适用于结果集缓存的算法和策略。经测试表明，本 文设计的结果集缓存，在数据变更较少查询请求较多的应用环境下，提升了 数据库的查询响应性能。 关键词：结果集缓存：内存管理：并发控制：失效机制；缓存一致性 a b s t r a c t a l o n gw i t ht h ec o n t i n u o u sa c c e l e r a t i o no ft h es o c i a li n f o r m a t i o np r o c e s s ，d a t a q u a n t i t yw h i c hn e e db ed e a l tb yav a r i e t yo fa p p l i c a t i o n sb e c o m em u c hb i g g e r ，s o i ts e e m se s p e c i a l l yi m p o r t a n tt oi m p r o v et h ed a t a b a s ea c c e s ss p e e do ft h er e s p o n s e r e s u l tc a c h ei sau s e f u lq u e r yo p t i m i z a t i o nt e c h n i q u ef o ri m p r o v i n gd a t a b a s e r e s p o n s ec a p a c i t y w h e nu s e r sq u e r yd a t a b a s e ，m er e s u l tc a c h e c a l ld i r e c t l y r e t u r nt h eq u e r yr e s u l tb ys t o r i n gq u e r yr e s u l t si nac a c h et a b l e b e c a u s eo f a v o i d i n g s e a r c h e sf o r t h e h u g et a b l e a n dt h et i m e c o n s u m i n gc o n n e c t i o n s o p e r a t i o n s ，t h er e s u l tc a c h ei m p r o v e ss q lq u e r ye f f i c i e n c y t h i sp a p e rf i r s t l yi n t r o d u c e st h ec o n c e p to ft h er e s u l tc a c h e ，a n de x p o u n d st h e p o s i t i o no ft h er e s u l tc a c h ei nt h eq u e r ys y s t e m s e c o n d l y , t h r e et e c h n o l o g i e st o a c h i e v er e s u l tc a c h ea r es t u d i e d ：m e m o r y s p a c em a n a g e m e n t ；t r a n s a c t i o n m a n a g e m e n t ；c a c h ec o n s i s t e n c ym a n a g e m e n t i nt h e s e s t u d i e st h ep a p e rp u t s f o r w a r d si m p r o v e da l g o r i t h mf o rt h er e s u l tc h a c h e f i n a l l yt h es e r v e rr e s u l tc a c h e i sd e s i g n e da n di m p l e m e n t e di nt h ed o m e s t i cd a t a b a s eo s c a r i ti ss t u d i e dd e e p l y t h a tt h em e m o r ya l l o c a t i o na l g o r i t h m ，t h em e m o r yi n d e xa l g o r i t h m ，t h ec a c h e r e p l a c e m e n ts t r a t e g ya n dt h ec a c h ef a i l u r et r e a t m e n t t h ep a p e ra l s op r o v i d e s a s o l v i n gs c h e m ea n dad e t a i l e dd e s i g no ft h ed a t ac o n s i s t e n c ym a i n t e n a n c eb e t w e e n t h es e r v e ra n dt h ec l i e n t t h es t r u c t u r eo ft h i sp a p e ri s ：f i r s t l yt h ep a p e ri n t r o d u c e st h ec o n c e p to ft h e r e s u l tc a c h e r e s e a r c h e st h er e s u l tc a c h eo fo r a c l ed a t a b a s e ，a n dm a k e s a f e a s i b l ea n a l y s i so ft h er e s u l tc a c h ei m p l e m e n t a t i o ni nt h ed o m e s t i cd a t a b a s e o s c a r ；s e c o n d l y ，t h ep a p e re n u m e r a t e ss e v e r a lt e c h n i c a lp r o b l e m so ft h er e s u l t c a c h e ，a n df i n a l l yt h ea l g o r i t h ma n ds t r a t e g yt oa c h i e v et h er e s u l tc a h c ei sg i v e n 。 m e a s u r e m e n tr e s u l t si n d i c a t et h a tt h ed e s i g no ft h er e s u l tc a c h ei sv e r yu s e f u lf o r i m p r o v i n gt h ep e r f o r m a n c eo fr e a d - i n t e n s i v ew o r k l o a d s k e yw o r d s ：r e s u l tc a c h e ，m e m o r ym a n a g e r m e n t ；p r o b l e m c o n c u r r e n c yc o n t r o l ； f a i l u r em e c h a n i s m ：c a c h ec o n s i s t e n c y 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密d 使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：伯夺施 日期：硼2 。& ， 指导柳签名：丁绑 日期：朋乎多刃 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进 行研究工作所得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体己经发表或撰写过的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 本文借鉴了国外数据库的新功能r e s u l t c a c h e ，分析了在国产 数据库o s c a r 中实现结果集缓存功能的可行性。对实现结果集缓存 所需解决的技术难题做了深入研究，最终设计并实现了结果集缓 存的功能模块。 文中主要研究了3 个方面的问题：结果集缓存的内存空间管 理，结果集缓存的事务管理和客户端缓存一致性。通过分析现有 的算法和策略，分别给出了适用于结果集缓存的解决方案和详细 设计。经测试表明，本文设计的结果集缓存模块，在数据源相对 稳定的情况下，对o s c a r 数据库的查询性能提升比较明显。 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景 第1 章绪论 随着社会信息化程度越来越高，特别是数据库技术的革新，大数据量的数 据库越来越多。各种商业应用、政府应用、国防应用等等，都促使数据库的 容量成几何级数增长。随着数据库的容量增长，人们要想从如此大的数据量 中准确快速地找到自己想要的信息，这对数据库的研究人员提出了很高的要 求。如何改进传统的数据库管理系统( d b m s ) 查询技术，使其适应新的需求， 这成了改进d b m s 性能的关键问题。一个d b m s 要想得到人们的认可，关键 的一点就是它的查询功能要能满足人们的需求。而查询功能中最重要的一点 就是它的响应时间，响应时间越短，给出的数据越准确，那么这个d b m s 就 越能得到人们的欢迎。o r a c l e ，m ss q ls e r v e r 等大型商用d b m s 的成功不 仅在于它们的存储技术，更重要的是它们的查询优化技术。 为了尽快地执行用户查询，查询优化成了一种有效地手段。经分析，人们 发现在查询中花费时间比较多的是两种操作：一种是连接运算( 包括笛卡尔 积运算) ，在这种连接操作中参加运算的元组越多，花费的时间越长i x 2 】。为了 提高连接运算的速度，查询优化器一般尽可能地将投影和选择操作移动到查 询树较低的层次，通过减少元组的数目大大减少了参与运算的数据，所用的 时间也大大减少；另一种是对大数量基表的聚集查询，在这种查询中基表的 数据量越大，需要扫描的物理元组也就越多，花费的时间也就更长。一些优 化器将聚集作为一个操作符号，在查询优化的时候予以考虑【3 4 】。但这些方法 只能有限地减少查询执行的时间。 另一种方法是在数据库中预先存储查询的结果或查询的中间结果，即采用 结果集缓存技术。结果集缓存是一种特殊的缓存，在数据库中不仅存储了s q l 查询的定义还存储了它们的结果。结果集缓存的定义中可能包含了耗时的连 接和聚集操作，在有相同的查询被提交时，如果查询条件完全匹配则直接把 这个结果返回给用户，而不是直接对原始的海量数据进行处理，加快了查询 的执行。 结果集缓存最先是被m y s q l 数据库所使用的，其名称为q u e 巧c a c h e 【5 1 。 西南交通大学硕士研究生学位论文第2 页 q u e r y c a c h e 是根据s q l i 吾句来c a c h e l 拘。一个s q l 查询如果以s e l e c t 开头，那么 m y s q l f l 艮务器将尝试对其使用q u e r y c a c h e 。每个c a c h e 都是以s q l 文本作为 k e y 来保存。在应用q u e r y c a c h e 之前，s q l 文本不会被作任何处理。也就是说， 两个s q l 语句，只要相差哪怕是一个字符( 例如大小写不一样；多一个空格 等) ，那么这两个s q l 将使用不同的c a c h e 。m y s q l 中提供的q u e r y c a c h e 只能 缓存单个查询结果，而且对查询不能做任何的嵌套查询操作。 结果集缓存后来被o r a c l e1 l g 所采用，其名称为r e s u l tc a c h e 【6 】。r e s u l t c a c h e 也是根据s q l 语句来c a c h e 的。r e s u l tc a c h e 与q u e r yc a c h e 的不同之处 是，r e s u l tc a c h e 是通过在查询语句中加入h i n t 标识符来确定缓存哪些数据的， 这样可以更加精准的让客户选择需要缓存哪些查询结果。r e s u l tc a c h e 同时支 持嵌套查询，就是可以把r e s u l t c a e h e 当作执行计划的中一个算子，当需要连 接操作时直接从r e s u l t c a c h e 中获取数据，这一点是q u e r y c a c h e 所不能够支持 的。 对于结果集缓存的研究，是随着d b m s 的发展而不断改进，主要研究内容包 括：结果集缓存内存管理、结果集缓存维护和结果集缓存查询重写，其目的 就是不断地提出更加有效的算法。现在结果集缓存不单用于预计算复杂查询， 还用来提供决策支持系统，移动计算等等方面。不仅大型的商用d b m s 拥有结 果集缓存功能，那些开源的小型的d b m s 也正在被一些数据库开发者加上结果 集缓存功能，以使它们能逐步适应大规模的使用。 本文对结果集缓存的研究，是基于国产神州o s c a r 数据库开发的。神州 o s c a r 数据库是我国自主研发的国产数据库，提供多版本的并发控制，支持几 乎所有的s q l 结构，还支持多种语言开发的应用程序。本文在o s c a r 数据库 上增加结果集缓存的功能，改进大数据量复杂计算的查询功能，提高了数据 库的查询响应性能。 1 2 研究的重要意义 国产神舟o s c a r 数据库，是拥有完全自主知识产权的企业级大型、通用对 象关系型数据库管理系统。它是北京神舟航天软件技术有限公司集多年的数 据库研发经验，在国家科技部和中国航天科技集团的大力支持下研制成功的， 是“十五”8 6 3 重大软件专项“大型通用数据库管理系统及其应用”的研制成果， 是一个在功能、性能、实用性、稳定性、安全性以及可扩展性等方面能够满 西南交通大学硕士研究生学位论文第3 员 足电子政务、电子商务、企业信息化以及国防工业等敏感部门信息化建设需 求的大型通用数据库产品。 经过多年对数据库产品的开发与研究，已经使神舟o s c a r 数据库满足人们 的各种需求。开发人员正在研究如何使神舟o s c a r 数据库能够在大数据量的应 用场合，在查询响应性能上有更好的提升。目前神舟o s c a r 数据库在海量数据 的情况下，查询响应速度还有待提高。在优化查询系统性能时，有两个重要 的策略：一个是实现物化视图功能；另一个是实现结果集缓存功能。使用物 化视图功能，可以在进行复杂运算时，节约很多时间大大提高了数据库的查 询性能。但是随着技术的进步，内存资源的获取更加容易，所以就产生了一 种新的技术，结果集缓存技术。结果集缓存技术直接把查询的结果或中间结 果，直接存储在内存中，从而极大的提高了查询速度。 现在很多大型商用数据库，比如o r a c l e 和m y s q l 都增加了结果集缓存的 功能，为了使神舟o s c a r 数据库的查询系统更能适应海量数据使用的需求，必 须借鉴其它大型的商用d b m s 在这方面的成功经验，因此在o s c a r 数据库中实 现结果集缓存是很有必要的。通过对o s c a r 数据库的系统进行分析，我们发现 在o s c a r 数据库中实现结果集缓存是完全可行的。在研究了o s c a r 数据库的查询 系统工作机制，和o r a c l e ，m y s q l 等商用数据库系统的结果集缓存工作情况 工作原理后，提出了在o s c a r 数据库中实现结果集缓存的一系列策略。 1 3 本文的主要内容和工作 本文在对神舟o s c a r 数据库进行分析研究后，提出了在神舟o s c a r 数据库实 现结果集缓存需要的几种策略，并结合结果集缓存的实际应用情况提出了相 应的改进算法。然后设计结果集缓存的模型，最终在神舟o s c a r 数据库中实现 了结果集缓存的功能，并且经过测试表明，结果集缓存对于数据相对稳定的 场合下，对查询性能的提升效果相当明显。 在本论文中，主要研究的内容和完成的工作如下： ( 1 ) 分析了数据库查询处理流程，给出了实现结果集缓存的可行性。 ( 2 ) 研究并实现了结果集缓存的内存空间管理策略，设计了适用于结果 集缓存的动态内存配策略，改进了动态哈希表的扩展算法，给出了缓存的替 换策略。 ( 3 ) 研究并实现了结果集缓存的事务管理模型，设计了适应于结果集缓 西南交通大学硕士研究生学位论文第4 页 存的失效处理机制，数据恢复机制和并发控制机制。 ( 4 ) 研究并设计了客户端缓存的数据一致性算法，给出了实现客户端结 果集缓存的结构设计。 ( 5 ) 设计了结果集缓存的功能模型，并在神，1 1 0 s c a r 数据库中实现了结果 集缓存的功能。 全文共分六章。 第一章：绪论。 第二章：结果集缓存概述。一 第三章：结果集缓存的内存空间管理。 第四章：结果集缓存的事务管理。 第五章：缓存一致性研究与客户端设计。 第六章：系统测试。 西南交通大学硕士研究生学位论文第5 页 第2 章结果集缓存概述 2 1 结果集缓存概念 结果集缓存的工作原理是，提前对数据库系统中复杂的查询进行计算和 连接，把得到的查询结果先保存起来。通过这样的预计算，对数据库的大部 分查询就可以矗接通过对结果集的查询得到结果，这样大大地提高了数据库 的响应性能。 ( 1 ) 使用结果集缓存的目的，是为了提高查询性能；结果集缓存对应用 透明，增加和删除结果集缓存不会影响应用程序中s q l 语句的正确性和有效 性；结果集缓存需要占用内存空间。 ( 2 ) 使用方法，当一个用户对查询结进行缓存后，其他用户可以共享这 个结果集缓存。如果连接的用户中有某个用户对结果集缓存所依赖的基表做 了修改( 包括增，删，改和修改权限) ，那么将导致结集缓存失效，所以其他用 户再次访问相同的查询时，将无法使用结果集缓存。 结果集缓存对数据库系统，特别是大型数据库系统的查询性能有很大的 提升。这是一种以空间换时间的机制，通过使用这种机制，可以实现更少的 物理读和写，更少的c p u 计算时间，更快的响应速度。数据库和数据仓库中 的结果集缓存主要用于预先计算并保存表连接或聚集结果等耗时较多的操作 的结果，这样，在执行查询时，就可以避免进行这些耗时的操作，从而快速 的得到结果。 结果集缓存的作用主要表现在下面四个方面： 1 ) 降低网络负担 2 ) 创建大规模配置环境 3 ) 可以实现数据的子集化 4 ) 可以实现不连接计算 西南交通大学硕士研究生学位论文第6 页 2 2o r a c l e 结果集缓存介绍 缓存技术始终是提高性能的重要技术，在o r a c l e l l g q b o r a c l e 为用户提供 了一种新的缓存技术：结果集缓存。顾名思义，这个新特性的含义就是将查 询的结果集c a c h e 起来，以便随后相同的查询请求可以直接利用，从而避免了 再次查询。在o r a c l e 的官方文档中称，通过这种新技术，可以对于读频繁的系 统，提升2 0 0 系统性能。下图2 1 和2 2 是o r a c l e 文档中给出的结果集缓存的应 用例子： 1 1 1 2 1 未使用结果集缓存时的执行计划吲 西南交通大学硕士研究生学位论文第7 页 图2 2 使用了结果集缓存的执行计划1 通过上图我们可以清晰的观察到结果集缓存的作用。在图2 1 中未使用结 果集缓存时，视图v 要通过执行投影和聚集操作来生成，如果计算视图的操作 很费时的话，将会导致整个查询的响应速度下降。在图2 2 中使用了结果集缓 存技术，我们通过预先把视图v 缓存了起来，从而在执行相同的查询时，不需 要再重复的计算视图v ，大大的提高了查询的响应速度。 在o r a c l e l l g 中结果集缓存分为服务器端结果集缓存和客户端结果集缓 存，下面将分别对它们做简要介绍： 2 2 1 服务器端结果集缓存 服务器端结果集缓存允许查询结果被缓存到服务器端的s g as h a r e dp o o l 中，缓存的结果在所有s e s s i o n 间共享。o r a c l e 通过数据的修改情况自动管理 结果集缓存的时效，用以确保数据的一致性。o r a c l e 管理员也可以通过p l s q l 来监听和管理结果集缓存。 另外o r a c l e 还引入了一个新的初始化参数来控制这个结果集缓存的大小： r e s u l t _ c a c h e _ m a x s i z e 。可以在s y s t e m 、s e s s i o n 、t a b l e 或者语句级别来设置 西南交通大学硕士研究生学位论文第8 页 c a c h e 的使用。在语句级可以使用一个新的h i n t 来控制是否缓存查询结果。 结果集缓存在服务器端的位置如下图2 3 所示： a s q l 语句 e i s q l 请求 | b c 语法分析 o d b c刨 客 圉 服 户 务 器 端 o l e d b 端 结果接收_ 诊 吣 n e t 掣掣 p r o v i z e r 应 呵 输出s q l 结果集 图2 3 服务器端结果集缓存示意图 在应用程序中为了激活o r a c l e 服务器端结果集缓存，我们可以使用两种 途径： 第一种途径是设置结果集缓存参数r e s u l t _ c a c h e _ m o d e 为f o r c e ，令所有的 s q l 语句结果集都被缓存。 例子：s e l e c ta lf r o mt a b l e l 当r e s u l t _ c a c h e _ m o d e 设置为f o r c e 后，系统会把查询后的结果集缓存到服 务器c a c h e 中。想要解除这个设定，只能通过重新设置参数r e s u l t _ c a c h e _ m o d e 来实现； 第二种途径是使用h i n t 标识符，当结果集缓存参数r e s u l t c a c h e _ m o d e 不 为f o r c e 时，我们可以使用h i n t 来激活结果集缓存。标识符h i n t 的写法如下： * + r e s u l tc a c h e * ，使用方法如下。 例子：s e l e c t * + r e s u l tc a c h e * a lf r o mt a b l e l 通过合理的使用h i n t 标示符，我们可以自由的控制缓存的内容。把那些 不经常发生变动的表查询缓存起来，可以提高应用程序的运行速度。 西南交通大学硕士研究生学位论文第9 页 2 2 2 客户端结果集缓存 客户端结果集缓存允许查询结果被缓存到客户端的内存中，客户端结果集 缓存在o c i 进程中，可以被该进程中的多个s e s s i o n 或者线程共享。客户端结 果集缓存通过一个新的初始化参数来控制：c l i e n tr e s u l t _ c a c h e _ s i z e1 8 1 当该参 数大于o 时，该功能被启用。同样的，该功能也可以在s y s t e m 、s e s s i o n 、t a b l e 或者语句级来设置。 通过在服务端设置参数而不是客户端设置，可以集中的管理该特性，但是 也可以在各个客户端单独进行设置，客户端的设置将覆盖服务端的设置。通 过把结果缓存到客户端后，查询请求甚至不需要到数据库中去执行该查询， 而是直接的从客户端获取结果，这可以有效的减少服务器的访问压力，提高 服务器的响应速度。下图为2 4 客户端结果集缓存的示意图： 八 s o l 语句 v 。 豳 j d b c o d b c 客 服 户 务 端 o l e d b 器 端 慧 n e t 皇! p r o v i z 查询执行 从缓存中 e r 获取数据 2 l 。、。1 一 。v 输出s q l 结果集 图2 4 客户端结果集缓存示意图 在默认情况下客户端结果集缓存是关闭的，我们可以通过设置客户端结 果集缓存参数c l i e n t _ r e s u l t _ c a c h es i z e 大于零，来激活客户端结果集缓存。客户 端结果集缓存的其他使用方法和服务器端的结果集缓存大致相同，它们之间 西南交通大学硕士研究生学位论文第1o 页 的唯一差别是客户端结果集缓存需要考虑客户端与服务器端的数据的一致 性。o r a c l e 为此增加了一个客户端结果级缓存延迟参数c l i e n t _ r e s u l t _ c a c h el a g ， 它的作用是确定客户端数据与服务器端数据的最大延迟时差，当客户端在 c l i e n t _ r e s u l t _ c a c h e _ l a g 时间内都未访问服务器获取结果集缓存校验信息时，客 户端会强制的访问服务器以获取当前的结果集缓存校验值，以保证客户端结 果集缓存的时效性。 2 3 结果集缓存在o s c a r 数据库中实现的可行性分析 随着结果集缓存技术在o r a c l e 中的成功使用，为了进一步提高国产数据库 o s c a r 的系统性能，o s c a r 开发小组决定在o s c a r 数据库中增添结果集缓存的功 能，下面将介绍国产数据库o s c a r 的系统构架，并结合o s c a r 的查询机制，分析 实现结果集缓存的可行性。 2 3 1o s c a r 数据库简介 神舟o s c a r 数据库，是拥有完全自主知识产权的企业级大型、通用对象关 系型数据库管理系统。它是北京神舟航天软件技术有限公司与浙江大学等高 等院校合作，在科技部重大软件专项“大型通用数据库管理系统及其应用”和 航天科技集团的大力支持下研制成功的，也是目前科技部经费支持力度最大 的国产数据库产品。其目标是以市场需求为驱动，研制一个在功能、性能、 实用性、稳定性、安全性以及可扩展性等方面能够满足电子政务、企业信息 化、电子商务以及国防工业等敏感部门信息化建设需求的大型通用数据库产 品，并在这些领域中逐步替换国外数据库系统。神舟o s c a r 数据库系统性能稳 定、功能完善，可广泛应用于各类企事业单位、政府机关，尤其是国防、航 天、航空等事关国家政治、军事、经济安全的各要害单位的信息化建设。神 舟数据库系统的成功研制和应用，一方面将可育咖底解决由于广泛应用国外 数据库产品可能带来的信息安全问题，另一方面也将在系统软件领域极大地 推动我国民族软件产业的发展。 ( 1 ) 特点分析 神舟o s c a r 数据库在设计中采用了一些先进的相关技术，并吸收了一些当 前流行数据库的常用技术，具备以下特点： 西南交通大学硕士研究生学位论文第11 页 1 ) 通用的数据库管理系统 神舟o s c a r 数据库管理系统支持w n i d o w s 、l i n u x 以及s o l a r i s 等多种主 流操作系统平台，应用j v a a 技术定制各种数据库管理工具，具有很好的跨平 台支持能力；神舟o s c a r 数据库管理系统采用成熟的关系数据模型作为核心的 数据模型，支持通用数据查询语言s q l ，因此可以在各行业中广泛应用口。 2 ) 支持多种计算模式 神舟o s c a r 支持包括集中式结构、客户服务器结构、w e b 浏览器w e b 应 用服务器数据库服务器多层结构等多种应用体系结构，能满足i n t e m e t i n t e r n e t 环境下的各种应用要求。 3 ) 符合国际标准的数据查询语言 神舟o s c a r 所提供的数据查询语言s q l ，完全符合s q l 9 2 入门级标准， 并部分支持对s q l 9 9 中定义的抽象数据类型a d t 的扩展支持。在系统核心 的查询处理过程中，直接执行对复杂工程数据对象和关系数据的融合处理。 4 ) 海量数据管理能力 神舟o s c a r 实现了可扩展的逻辑和物理双层存储结构管理，因此具有管理 海量数据存储的能力。神舟o s c a r 支持的数据库最大容量达到t b 级别，支持 的单表最大容量也达到t b 级别，同时支持的单个大对象的最大容量达到 4 g b ，并实现了对数据库内表数目的无限制和表中记录数目的无限制支持。 5 ) 高效的数据处理能力 神舟o s c a r 实现完整的查询优化策略，支持高效的查询执行方案，具备稳 定高效的数据处理能力。同时支持大对象数据管理：支持图形、图像、声音、 文字、视频等多媒体数据管理：实现复杂对象数据和关系数据的统一管理；并支 持用户自定义数据类型的扩展。 6 ) 多层次的数据库安全机制 神舟o s c a r 实现了可靠的用户身份认证，支持自主存取控制和安全的网络 连接，并提供对d b a 、普通用户、数据对象和特定数据操作的各种安全审计。 神舟o s c a r 还对数据的存放和传输提供了多种加密机制以满足不同应用的要 求。 7 ) 丰富的数据库管理工具 神舟o s c a r 提供各种基于g u i 的交互式智能管理工具，包括系统安装和卸 载、d b a 工具、交互式s q l 、性能监测与调整以及作业自动调度等，并提供 与o a c r e l 、s q l s e v r e r 等主要大型商用数据库管理系统以及t x t 、o d b c 等 标准格式之间的数据迁移工具。 西南交通大学硕士研究生学位论文第12 页 ( 2 ) o s c a r 数据库系统的体系结构 o s c a r 数据库管理系统采用分层次的模块化设计方法，具体分为管理工 具、应用程序接口、数据库内核三个主要的层次。o s c a r 数据库管理系统的层 次结构如图2 5 所示。 - - 、 攮作茅缝 、_ i 茁 硝。j 般t ” 厂圄圄圄、 图2 5o s c a r 数据库系统的层次结构巧 管理工具提供备份恢复、性能优化、作业调度、数据转换、d a b 管理、 交互查询等多种工具。这些工具主要提供给数据库管理和操作人员，使它们 能够通过图形化的工具方便地管理o s a c r 系统。应用程序接口主要提供给程 序员使用。包括通用的o d c b ，d j c b 接口以及嵌入式s q l 等。对于想使用 o s c a r 数据库系统作后台数据库来开发数据库应用程序的程序员，o s c a r 的应 用程序接口和其它主流数据库管理系统能够提供的一样完备。在数据库内核 部分，其上层包括数据字典、查询分析、查询优化、公共模块、执行管理和 命令管理几个部分：下层包括同志管理、索引管理、文件管理和事务管理几个 部分。其中和日志管理密切相关的有文件管理和事务管理两个模块。文件管 理部分为日志管理模块提供了对物理文件的读写接口，并且负责管理日志组 和同志文件成员。事务管理主要利用了同志管理模块，通过日志管理模块来 西南交通大学硕士研究生学位论文第13 页 组织日志，写入日志以及读取日志，并且通过日志记录来进行故障恢复。另 外还有与o s c a r 系统运行息息相关的三种文件，数据文件、日志文件以及控制 文件。日志文件是日志模块负责维护的，用于保存事务日志，是故障恢复的 依据。数据文件是存放数据库中数据的，是数据记录存放的地点。控制文件 则保存了一些控制信息，用于维护数据库的启动参数和其它控制信息等。 2 3 2o s c a r 数据库查询流程 o s c a r 是真正执行用户查询的服务器端进程，每一个用户都有一个专用的 s e s s i o n 为它服务，随用户连接产生，随用户断开而消亡。所有s e s s i o n 访问共 享内存段中的数据缓存和日志缓存，但每一个s e s s i o n 都有自己私有的数据字 典缓存。 以下为数据库查询的基本流程图： 输入s q l 语句 0 语法分析 一 语法解析器 o ，眨司、 0 s c 数a 据 、 语意分析 语意分析器r 库 数 内 、数型叫 、j 据 库 部 n查询优化 - t b 优化器 内 数 据 日志文件 部 、7 、 太 j 模 块 淄 查询执行 执行器 j 输出满足条件的s q l 语句 图2 1 数据库查询流程 从图2 1 可以看出，从功能和处理的流程上划分，o s c a r 的查询处理子系 统可以分为语法解析器、语意分析器、优化器和执行器。 语法解析器：主要的功能是经过s q l 语法分析，验证数据的s q l 请求的 西南交通大学硕士研究生学位论文第14 页 语法是否正确，如果正确则进行下一步语意分析。 语意分析器：主要的功能是通过对s q l 语句进行语意分析，验证s q l 请 求中涉及的列和表在数据库中是否存在。如果通过验证则根据s q l 请求生成 q u e r y 查询树。 优化器：这部分的功能是，把已经解析和重写完毕的命令转换成计划树 p l a n ( p l a n ，即关系代数的等价形式) 。基本的过程也是两步：一是根据关系代 数的相关定理简化查询树结构( q u e r y ) ，二是采用动态规划的策略选择 o i n 的顺序和具体的算法。至此，物理计划已经形成，同时传递到执行器准备执 行。 执行器：根据上面的计划树( p l a n ) 执行并返回结果。执行器的整体结构 是采用迭代器来尽可能地实现管道化或流水线操作。 本文中所研究的结果集缓存包括服务器端结果集缓存和客户端结果集缓 存： 对于服务器端结果集缓存，本文是在查询处理流程中的执行器模块实现 的。因为查询语句执行到执行器时，已经获取了相应的执行计划和查询的h i n t 标识符，并且用户已经通过了权限检查，无需担心数据库不安全访问的问题， 实现的服务器端结果集缓存的查询条件已经具备，本文的服务器端结果集缓 存的实现选择了在执行器模块中完成的。 对于客户端结果集缓存，其数据的存储方式与查询流程同客户端基本相 同，其数据的查询流程比较服务器端结果集缓存要稍微复杂一点，因为当开 启了客户端结果集缓存后，查询数据时，首先是查询本地的结果集缓存是否 与查询请求相匹配，如果匹配则直接获取查询数据，如果不匹配才需要向服 务器端发送查询请求。对客户端结果集缓存本文主要探讨了客户端结果集缓 存的数据一致性问题，并给出了设计方案。 2 4 结果集缓存研究的问题 题： 要实现服务器端结果集缓存和客户端结果集缓存主要面临着3 个技术问 ( 1 ) 如何管理结果集缓存的内存空间。 ( 2 ) 如何保证结果集缓存事务的正确性。 ( 3 ) 如何保证客户端与服务器端的数据的一致性。 西南交通大学硕士研究生学位论文第15 页 首先我们要解决的问题就是如何管理结果集缓存的内存空间。结果集是存 储在内存中的，能够分配给结果集缓存应用的内存是有限的。如何利用有限 的内存资源，既提高结果集缓存的执行速度，又能尽量的节约内存空间，是 我们首先要研究的问题。本人通过分析目前主流的动态内存分配算法，内存 索引索引算法和缓存替换算法，提出了适用于结果集缓存的对应算法，并加 以实现，提高了结果集缓存的执行速度与执行性能。 其次当结果集合缓存被使用时，如何确保事务执行的正确性，也是我们需 要面对的一个问题。为了保证数据的正确性，当结果集的基表发生变化时， 应该确保对应的结果集缓存失效，避免用户读到结果集缓存里的过期数据。 当用户进行并发访问时，应采用适当的并发控制策略，保证用户访问的正确 的进行。本人首先给出了结果集缓存的失效策略和数据恢复实现方案，然后 分析了目前的并发控制机制，结合本文的实际需求，给出了适用于结果集缓 存的并发控制机制，并最终加以了实现。 再次为了实现客户端结果集缓存，我们必须要解决的一个问题就是，客户 端中缓存的数据如何与服务器端基表的数据保持一致性。当服务器端的基表 数据发生变化时，我们应该使所有缓存了依赖该表的结果集尽快失效，如果 不进行失效处理，那么用户将访问到过期的数据。如何能有效的保持客户端 与服务器端的数据一致性，并且尽量的减少网络通信和服务器的访问压力是 解决这个问题的难点。本文结合目前主流的一致性算法，提出了适用于客户 端结果集缓存的策略，并最终给出了详细的设计方案。 西南交通大学硕士研究生学位论文第16 页 第3 章结果集缓存的内存空间管理 3 1 动态内存分配 实现结果集缓存首先要解决的第一个问题是，当结果集缓存需要内存时， 如何动态的分配内存。 比较传统的方法是直接调用系统函数m a l l o c o 来获取要分配的内存，但是 这种获取内存的方法效率并不尽人意，因为每次调用m a l l o c o 时，系统都会重 新扫描物理内存寻找可用的内存块，这是相当费时的。 目前大多数基于c ，c + + 的应用程序是采用一次分配多次利用8 9 1 的方法， 来提高内存的分配速度。这种方法的思想是：一次获取足够的内存，然后自 己建立一套内存管理机制，每当有内存请求时，直接从已有的大块内存中获 取可用的内存地址返回给应用程序，经验表明这种内存管理机制有效的提高 了内存分配的速度。但是这种机制的要面对的一个问题就是，分配内存时一 定会产生内存碎片，如何有效的减小内存碎片，并且提高内存管理的效率， 这是这种策略的一大难题。 下面将通过比较现有的各种内存分配算法，最终提出适用于结果集缓存的 两阶段动态预分配内存策略和基于位图的内存分配算法。 3 1 1 内存碎片 内存碎片l l o 1 l l 是内存分配中一个无法逃避的问题。任何内存分配算法都会 产生内存碎片。下面就内存碎片产生的原因展开详细分析。 内存分配程序浪费内存的基本方式有三种：即额外开销、内部碎片以及外 部碎片： 额外开销：内存分配程序需要存储一些描述其分配状态的数据，这些存储 的信息包括任何一个空闲内存块的位置、大小和所有权，以及其它内部状态 详情。一般来说，一个运行程序存放这些额外信息最好的地方是它管理的内 存。 内存碎片：内存分配程序需要遵循一些基本的内存分配规则。例如，所有 西南交通大学硕士研究生学位论文第17 页 的内存大小必须是2 的n 次方( 视内存管理结构而定) 。内存分配程序把刚好 大于预定大小的内存块分配给客户。例如，当某个客户请求一个1 3 字节的内 存块时，它可能会获得1 6 字节，这样后面的5 个字节就会被浪费掉。由所需 大小四舍五入而产生的多余空间就叫内部碎片。 外部碎片：外部碎片的产生是当已分配内存块之间出现未被使用的差额 时，就会产生外部碎片。例如，一个应用程序分配五个连续的内存块，经过 若干操作使中间的两个内存块处于了空闲状态。内存分配程序可以重新使用 中间内存块供将来进行分配，但不太可能分配的块正好与空闲内存一样大。 倘若在运行期间，内存分配程序需要的内存块虽然小于两个剩余内存块的总 和，但却大于任何单独的空闲内存块。这时如果不进行碎片整理，就会出现 虽然已有内存可以满足程序的请求，但是却无法获取内存的情况。这种内存 碎片，我们称之为外部碎片。 在程序开发过程中，额外开销的内存碎片是程序能够正确运行的保证。一 般情况下外部碎片很难被回收利用的，所以大多数的动态内存分配策略都是 通过适当的容许内存碎片的方法，来减少或杜绝外部碎片的产生。下面将介 绍几种动态内存分配算法，并对它们进行分析。 3 1 2 内存分配策略研究 内存分配算法1 1 2 1 3 a 4 】的目的是从首次获取的大内存池中分配足够大的内存 块给应用程序，不同的算法策略采用不同的方法来寻找大小合适的内存块。 下面将分析一下现有的动态内存分配算法： ( 1 ) 顺序适配策略：这种分配策略是最基础的分配策略。顺序适配是基 于内存空闲块的单向链表或双向链表的，当需要内存块时，直接从空闲链表 中获取所需要的内存块的。基于这种分配策略的算法有最快适配算法，最先 适配算法，下次适配算法和最坏适配算法。 这种分配策略并不是一种好的分配策略，因为分配内存的时间取决于空 闲链表的搜索时间，而空闲链表的搜索时间具有不确定性，这是我们不愿意 使用顺序分配策略的原因之一。而且这类算法的另一个缺点是，经过多次内 存分配后，往往会产生极小的无法被重新利用的内存碎片，这是我们所无法 接受的。 ( 2 ) 多链表分配策略：这种分配策略的思想是使用一组链表，每一个链 西南交通大学硕士研究生学位论文第18 页 表负责管理一种大小的内存块，当应用程序请求内存时，根据所需内存块的 大小找到相应的内存块空闲链表，从该链表中获取所需的内存块。在这种算 法中不同链表所管