（计算机应用技术专业论文）基于三层架构的语义缓存技术的研究.pdf

华 中 科 技 大 学 硕 士 学 位 论 文 摘要 目 前， 大量的 数据存储在数据库服务器之中， 成千上万的用户访问 和分析这些数 据。 缓存技术通过在本地缓存数据， 并使用缓存数据回答查询， 缓减数据库服务器以 及网络的负担。 在众多的缓存技术中语义缓存技术表现出明显的 优势， 语义缓存保存查询的结果 及其语义描述。 语义缓存由 互不相交的语义区域组成， 每一个语义区域包括语义描述 及其数据指针。 语义缓存将一个查询裁剪为试探查询和剩余查询， 试探查询由本地的 语 义 缓存回答， 而剩余 查询以s q l语 句形式交由 服务 器回 答， 两部 分结果 一起形 成 整个查询的结果。 基于三层架构的 语义缓存技 术( t h r e e - t ie r - b a s e d s e m a n t i c c a c h e t e c h n o l o g y , t s c t ) 将语义缓存技术和流行的三层架构的结合起来， 是对基子客户机 朋 良 务器系统的 语义缓存技术的技术改进。 它同时在客户机和应用服务器进行语义缓存， 充分利用客 户机和应用服务器中的缓存数据回答用户查询，极大地提高了缓存的性能。 t s c t兼顾联机事务处理和联机分析处理两类应用模式，并具有很高的扩展性， 通过简单地扩展应用服务器的规模，t s c t能够适应海量数据和大规模并发的应用环 境。 t s c t 使用p a x ( p a r t i t i o n a t t r i b u t e a c r o s s ) 页面 模式 来存储缓 存数据。 p a x页 面模 式在页面内 将同 属一个字段的 数据连续存储， 不仅有利于谓词评价， 而且可以 提高仅 涉及关系表少数字段查询的效率， p a x页面模式还有效地提高了位于主存和处理器之 间c a c h e 的利用率。 t s c t预先选择、计算和缓存一些聚集视图， 并利用这些聚集视 图回答聚集查询，从而避免在线计算，大大提高聚集查询的响应速度二聚集视图的预 先选择综合考虑视图的尺寸和查询频率，以缓存具有较大效益的聚集视图;聚集视图 的 计算则使用高效的b u c算法， b ii c算法自 底向 上划分事实表， 一次计算出 被选择的 全部聚集视图。t s c t使用不同的策略处理日常查询和聚集查询。对于前者，t s c t根 据语义区域与查询区域之间的不同匹配情况，将查询精确裁剪为试探查询和剩余查 询; 对于后者， t s c t 根据聚集视图 间的计算依 赖关系， 选 择合适的 聚集视图回答查询。 关键词:缓存，语义缓存，三层架构，聚集视图，查询导出 华 中 科 技 大 学 硕 士 学 位 论 文 ab s t r a c t n o w a d a y s , w i t h l a r g e q u a n t it i e s o f d a t a s t o r e d i n d a t a b a s e s e r v e r a n d d a t a a c c e s s e d a n d a n a l y z e d b y t h o u s a n d s o f u s e r s , a n e ff e c t i v e w a y t o r e l e a s e t h e h e a v y l o a d o f t h e d a t a b a s e a n d n e t w o r k i s t o t a k e u s e o f c a c h e t e c h n o l o g y t h r o u g h w h i c h t h e d a t a a r e c a c h e d i n t h e l o c a l s y s t e m a n d q u e r i e s a r e a n s w e r e d b y u s i n g t h e c a c h e d a t a . a m o n g a i l t h e c a c h e t e c h n o lo g i e s , t h e s e m a n t i c c a c h e t e c h n o l o g y m a n i f e s t s d i s t i n c t i v e a d v a n t a g e s , t h r o u g h w h i c h t h e d a t a a n d t o g e t h e r w i t h t h e i r s e m a n t i c d e s c r ip t i o n s a r e c a c h e d . t h e s e m a n t i c c a c h e c o n s i s t s o f d i s j o in t s e m a n t i c re g i o n s , a n d e a c h s e m a n t i c re g i o n i n c l u d e s a d e s c r i p t i o n a n d a c o r r e s p o n d in g d a t a p o i n t e r . i n s e m a n t i c c a c h e t e c h n o l o g y e n v i r o n m e n t , a t f i r s t , a q u e ry i s s p l i tt e d i n t o t w o d i s j o i n t q u e r i e s , p r o b e q u e ry a n d re m a i n d e r q u e ry . a n d t h e n t h e p r o b e q u e ry i s a n s w e r e d b y l o c a l c a c h e s y s t e m a n d t h e r e m a i n d e r q u e ry i s a n s w e r e d b y t h e b a c k g r o u n d d a t a b as e s e r v e r . f i n a l l y t h e t w o p a r t s o f a n s w e r s a r e m e r g e d i n t o o n e f ina l r e s u l t a s a g r e a t i m p r o v e m e n t o v e r s e m a n t i c c a c h e t e c h n o l o g y b a s e d o n c l i e n t / s e r v e r s y s t e m , t s c t ( t h r e e - t i e r - b as e d s e m a n t i c c a c h e t e c h n o l o g y ) , c o m b i n e s t h e s e m a n t i c c a c h e t e c h n o l o g y w it h t h e p o p u l a r t h r e e - t i e r a r c h i t e c t u r e , g r e a t l y i m p r o v e s t h e e ff e c t o f c a c h e s y s t e m , t h r o u g h w h i c h t h e q u e ry re s u l t i s c a c h e d in t o b o t h t h e c l i e n t a n d t h e a p p l i c a t i o n s e r v e r a n d t h e c a c h e d a t a a r e f u l ly u s e d t o a n s w e r q u e r i e s . t s c t i s f i t f o r t h e a p p l i c a t i o n s o f b o t h o l a p a n d o l t p , a n d i s a l s o h i g h l y s c a l a b l e . i t c a n b e e as i l y a d a p t e d t o t h e a p p l i c a t i o n o f h u g e d a ta a n d t h e a p p l i c a t i o n e n v i r o n m e n t o f h i g h p a r a l l e l i s m w it h t h e n u m b e r o f a p p l i c a t i o n s e r v e r s i n c re as e d . t s c t t a k e s u s e o f t h e p a x ( p a r t i t i o n a t t r i b u t e a c ros s ) p a g e s c h e m a t o o r g a n i z e t h e c a c h e d a t a , i n w h i c h a l l t h e d a t a b e l o n g in g t o a fi e l d a r e p h y s i c a l l y s t o r e d t o g e t h e r . i n t h i s w a y , t h e p re d i c a t e e v a l u a t i o n a n d t h e p e r f o r m a n c e o f q u e r i e s i n v o l v in g f e w f i e l d s o f a re l a t i o n a r e b e tt e re d , a n d t h e p e r f o r m a n c e o f t h e c a c h e b e t w e e n c p u ( c e n t r a l p r o c e s s i n g u n it ) a n d t h e m a i n m e m o ry i s a l s o i m p r o v e d . t s c t p r e - s e l e c t s , c o m p u t e s a n d s t o re s s o m e a g g r e g a t i o n v i e w s , a n d u s e s t h e s e v i e w s t o a n s w e r q u e r i e s i n o r d e r t o a v o i d t h e o n - li n e c o m p u t a t i o n a n d s p e e d u p t h e a n s w e r i n g o f a g g r e g a t i o n q u e r i e s . t h e p r e - s e l e c t i o n o # a g g re g a t i o n v i e w s t a k e s i n t o a c c o u n t b o t h t h e s i z e a n d t h e q u e r y i n g fr e q u e n c y o f t h e a g g r e g a t i o n v i e w s . t h e c o m p u t a t io n o f a g g r e g a t i o n v i e w s i s i m p l e m e n t e d t h r o u g h t h e e f fi c i e n t b u c a l g o r it h m , 华 中 科 技 大 学 硕 士 学 位 论 文 w h ic h p a r t i t i o n s t h e f a c t t a b l e i n a b o tt o m - u p w a y a n d c o m p u t e s t h e w h o l e s e l e c t e d a g g r e g a t i o n v i e w s a t o n e t i m e . t s c t t a k e s u s e o f d i ff e re n t s t r a t e g ie s t o p r o c e s s u s u a l q u e r i e s a n d a g g r e g a t i o n q u e r i e s . a s f o r t h e f o r m e r , t s c t s p l i t s t h e q u e r y e x a c t l y i n t o t h e p r o b e q u e ry a n d th e r e m a i n d e r q u e r y a c c o r d i n g t o d i ff e r e n t m a t c h ty p e s . a s f o r t h e l a tt e r , t s c t s e l e c t s a n a p p r o p r i a t e a g g r e g a t i o n v i e w t o a n s w e r t h e q u e r y a c c o r d i n g t o t h e c o m p u t a t i o n d e p e n d e n c y a m o n g a g g r e g a t i o n v i e w s k e y w o r d s : c a c h e , s e m a n t i c c a c h e , t h r e e - t i e r s y s t e m, a g g r e g a t i o n v i e w , q u e ry d e r i v a t i o n 一 一 - - 一 一 一 - 一 一 ， 一 i i i 独创性声明 本人声明 所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究 成果。尽我所知，除文中己 经标明引 用的内 容外， 本论文不包含任何其他 个人或集体已 经发表或撰写过的研究成果。 对本文的研究做出贡献的个人和集体， 均已 在文中以明 确方式标明。 本人完全意识到本声明的法律结果由 本人承担。 4 4 z 月 1日 豁辞 妇叶 朴眺 学位论文版权使用授权书 本学位论文作者完全了 解学校有关保留、使用学位论文的规定，即:学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。 本人授权华中科技大学可以 将本学位论文的 全部或部分内容编入有关数 据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口 ，在 本论 文 属于/ 不保密瑟名 年解密后适用本授权书。 ( 请在以上方框内打 “ a r ) 4 4 t l 月 龙日 指导教师签名 日期 矛 甩 脚 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论 1 . 1 课题的来源、目的及意义 随着互联网和电子商务的迅猛发展， 大型数据库管理系统己经越来越多地受到超 大规模数据量和高强度瞬时并发访问的折磨和考验，目 前， 企业级数据库面临的主要 挑战有: ( 1 ) 管理的数据越来越多， 企业的数据有集中化趋势， 数据量达到了t b级， 甚 至是p b级，单个表存储的记录数以亿计; ( 2 )并发访问的用户数目 越来越多，达到了百万计; ( 3 ) 用户对系统的要求越来越高，希望各种操作能够瞬间完成; ( 4 ) 用户提交的查询要求越来越复杂， 这些查询往往读取大量的细节数据，并 执行复杂的聚集计算。 大 型数 据库管理系统的 执行 效率低下， 包括 联机事务处理( o n - l i n e t r a n s a c t i o n p r o c e s s i n g , o up ) 和联机分 析处 理( o n - l i n e a n a b l i c a l p r o c e s s i n g , o l a p ) ，已 经越来成 为制约整个企业信息系统的性能和效率提升的瓶颈。 配置更高档次的硬件，调整数据 库管理系统的参数，固然能够提高系统的性能， 但是，这些方法代价昂贵，并且只能 有限度地提高系统的性能，信息处理的瓶颈仍是数据库管理系统。 同时，伴随着联网技术和移动技术的不断进步，用户不必停留在固定的位置，甚 至可以 携带移动( 如笔记本、 手机和p d a等) 设备自 由 移动， 随时随地查询异地的数据 库 服务 器。 在 这种带宽 低、费 用高、 断 接频繁i i i 的 通信 环境中， 数据库服务器 长时间 的 处理 用户 提交的查 询( 检索记 录或者处理数据) ， 或者通过网 络传输大量的 数 据都是 不 现实的 12 1 ， 长时间的 连 接将 加重用户的 经济负 担， 并 且加大这种本来就不 稳定的连 接 的 断 线 概 率 3 . 4 1 在众多的数据库优化方法中，缓存技术得到了 业界的 广泛关注。类似于程序执行 的局部性，用户的查询也存在局部性，在许多情况下，不到 5 %的关系表占用了数据 库系 统 超过5 0 % 的f o时 间 5 1 。 用户 访问了 一 块 收 据 后， 在 不 久的 将来 很可能 再次 访 问它，这就是访问的时间局部性;用户访问了一块数据后， 很可能接着访问临近的数 据块，这就是访问的空间局部性; 最重要的访问局部性是语义局部性，即用户往往按 华 中 科 技 大 学 硕 士 学 位 论 文 二二二二二二留二二二.二二二二二二二二二二二二二二吕二二二二二 照下述模式访问数据库: 首先提交一个查询， 接着调整选择条件， 或者施加更多的选 择条件，显然，后来的查询可以由先前查询的结果全部或者部分导出。因此，通过在 客户端缓存数据，尽可能地在本地回答查询，避免了从数据库服务器提取数据， 然后 借助通信网络传输到客户端，大大减轻了数据库服务器和网络的负担，同时加快了查 询的响应速度。 语义缓存技术通过缓存查询的结果及其语义描述信息， 能够发掘蕴藏在查询谓词 中的语义信息来组织查询结果，相比传统缓存而言，能更有效地利用缓存， 减轻服务 器和网络的负担。 同时， 现在三层架构乃至多层架构己经成为数据库应用系统的主流。 三层架构克服了传统的客户机/ 服务器( c l i e n t / s e r v e r , c / s ) 结构的局限 性， 将应用的 表 现逻辑、业务逻辑和数据处理相互分离，技术优势明。三层架构为语义缓存技术提供 了广阔的发展空间。 而当前语义缓存技术的仍然构建在 c / s 架构之上，因此语义缓存 技术由c / s 架构转变为三层架构成为必然 本课题正是为了满足日 益复杂应用需求和适应计算机技术进步的需要， 研究了三 层架构下的语义缓存技术。 通过在客户机和应用服务器中缓存查询的结果及其描述， 尽可能地利用本地缓存的内容回答查询，以避免不必要的服务器端的数据检索和处 理，以及通过网络传输数据，从而提高数据库系统的性能。 1 . 2 国内外研究概况 缓存技术根本的设计目的是组织和存储那些访问频度较高的数据项，并且基于这 些数据项全部或者部分回答查询， 使得服务器能够减少1 / o次数、 节省c p u时间、 以 及降低客户端与服务器端的通信开销， 允许用户快速获得查询的结果， 从而大幅提高 系统的 整体性能。因此， 本节从缓存的表示与组织、 利用缓存回答查询以及缓存项的 置换三个方面介绍在语义缓存方面国内外的研究概况。 1 .2 . 1 语义级存的表示与组织 与传统缓存技术缓存数据库的 元组 i u p l e s ) 或页面( p a g e s ) 不同， 语义缓存技术缓存 查询的结果及其语义描述信息， 能够发掘蕴藏在查询谓词中的语义信息来组织查询结 果， 以 达到更有效管理缓存的目 的。 语义缓存( s e m a n t i c c a c h e ) 是一些添加了 相关语义 描述信息的 数据项的 一 个集合， 文献 6 称这 些数 据项为 语义区 ( s e m a n t i c r e g i o n s ) ， 文 献 7 则 称 之为语义片段 ( s e m a n t i c s e g m e n t s ) 。 在移动计 算环境中 ， 有 人 把这种具 有动态 华 中 科 技 大 学 硕 士 学 位 论 文 变 化 性以 及时间 和空 间 特性的 语义 缓 存 称为 移动 子 集s a t 。 在o l a p环 境下 ， 数 据在 本 质 上 是 多 维 的 ， 语 义 缓 存 一 般 被 称为 多 维 块 ( m u l t id im e n s i o n a l c h u n k ) 0 1 。 一 般 使 用 五 元 组 方式 描 述缓 存 项， 即 ( s r , s a , s p , s o , s w ) ， 不 过 其蕴 含的内 容在 各 人 看 来 有 所不同 。 文献 6 仅仅缓存涉及一个关系表的查询， s r 是出 现在fr o m子句中的关系表， s a 是出 现在s e l e c t 子句中的 属性集i s p 是出现在w h e r e 子句中 选择条件。 文献 7 通过扩展s a i 即把那些能够从选择条件中推导出，但是不在s a 的属性纳入属性集s a 之中。 虽然缓 存的内 容仍然限于单个关系表的查 询， 但是能够从缓存中回答出 更多的查询。 文献 1 1 考虑了缓存连接查询的可能性， 即s r 可以包括多个关系表， s a 可以 包括来自 多个关系 表的 属性， s p 可以 包括 连接谓词。 文献 l o 在提出 基于 多维块进 行语义缓存的时 候， 并 没有对其做出形式化的描述， 不过纵观全文，不难发现，所谓的多维块不过是在各个 维选取一段区 间 长度可以 为 零 ) 后， 位于多 维空间中的 子空间而己。 语 义缓存既 可以 存储真正的 数据， 也 可以 存 储指向 底层数 据库数据的指 针1 1 2 . 1 3 1 虽然指针方式更加节省空间， 并允许访问关系表的所有字段， 而不只是投影属性。 但是， 指针方式不适合于分布式环境，真正的数据仍然需要通过网络从服务器传输到客户 端; 指针方式同样也不适合于缓存项涉及聚集计算的查询， 涉及聚集计算的查询仍然 需要 重新计 算一遍。 文献 6 以 元组方式组 织缓 存数据， 即 将每一个缓存项与一个指针 关联， 该指针指向 一个元 组的 链表。 文献口 借鉴了 关系 数据库中的 磁盘管理方式， 一个缓存项的数据被存储在一个一个的物理页面之中， 这些页面的位置被依次记录在 s 。 之中。 1 .2 . 2 语义级存的查询处理 缓存的根本目的在于利用所缓存的数据全部或者部分回答用户提交的查询， 因此， 所有的缓存模式， 不管是集中式系统中的缓冲管理， 还是传统的分布式系统中的元组 i 页面缓存， 或者是基于查询及其描述的语义缓存， 都避免不了这一核心问题。 学者们 在基于单个语义缓存项导出查询方面做了大量的 研究工作， 但是， 关于如何利用整个 语义缓存空间来计算查询，仍然需要进一步的研究。 文献 1 4 第 一次 提出了“ 查 询修 剪” ( q u e r y t r im m i n g ) 的 概念，即 在查 询与缓 存项 相交时，将查询裁剪为两个不相交的片段，一块与缓存项相交，另一块与缓存项不相 交。 文献 6 更进一步， 分别将这两个不相交的片段称为试探查询(p r o b e q u e r y ) 和剩余 查 询( r e m a i n d e r q u e r y ) 。 但是， 这两篇文章 没有就如何处理 这两部查询 给出 具体的办 法。 文献 1 5 - 1 6 ) 对缓存项和查询之间的关系进行了分类， 其中， 文献 1 6 对每一种情 华 中 科 技 大 学 硕 士 学 位 论 文 况都提出了相应的查询处理方法， 但是， 这篇文章没有从理论上证明 其正确性。 文献 1 7 】 考虑了 语义缓存的可回答性问 题，并给出了 相应的 判定算法， 遗憾的是，它只适 合于l d a p ( l i g h t w e i g h t d i re c t o r y a c c e s s p r o t o c o l) 访问 环境。 文 献 1 0 从多 维 块的 角 度 考虑缓存和查询， 因此， 查询的结果很自 然地被分解成两个部分， 一部分在缓存之中， 一部分可以从后台计算而来。 检查缓存和查询之间的可满足关系仅仅是利用缓存回答查询的第一步。文献 1 8 - 1 9 的 研究 表明， 如果考 虑不 等于比 较， 即 使 在整 数域， 这也是一 个n p 难问 题。 另外， 即使缓存项的内容包含了查询的全部结果， 如果某些属性出现在查询的选择条 件之中， 但是在缓存项中 这些属性被投影掉了， 那么， 仍然不能从缓存计算出查询i i 7 , 2 0 。 文 献 6 仅 仅处 理s e l e c t 查 询， 并 且 把 整 个 语 义 区 域 当 着 一 个 整 体 来 计 算 相 应 的 试 探查询 和剩 余查询。 文献 7 能 够处理s e l e c t - p r o j e c t 查 询， 既 从单个缓存项， 也从整个 缓存空间来处理查询， 同时提供了 优化措施， 使得试探查询和剩余查询能够并行执行。 文献t 川继续了 文献叨的 工作， 并 有所扩展， 使得连 接查询有可能 从缓存中 得到回 答。 受制于这一问题的复杂性， 本研究仅仅在查询和缓存项在单属性比较项上相交时对查 询进行裁剪。 1 . 2 .3 语义级存的it换策略 缓存置换策略是缓存技术的一个重要内 容，它的优劣对缓存体系结构的性能有比 较大的 影响。 传统的 缓存 置换方 法有f i f o ( f ir s t in f i r s t o u t ) l2 1 -2 3 , c lo c k (2 2 -2 4 l r u ( l e a s t r e c e n t ly u s e d ) s , -2 a 等 ， 它 们 都 是 基 于 时 态 位 置 ( 即 最 近 被 访 问 的 数 据 项 很 可能在不久的将来再次被访问的 特性) 的。 随着语义缓存技术的出 现， 人们认识到语义 信息的重要作用， 逐渐把它应用到缓存替换方法中，出 现了基于时态位置和空间位置 ( 即与最近被访问的数据项在物理位置上接近的其他数据项很可能在不久的将来再次 被 访问 的 特 性 ) 的m d f ( m a n h a t t a n d i s t a n c e f u n c t io n ) ( 和t l l ( t w o l e v e l l r u ) 2 s 等算 法。 ( 1 ) f i f o算法。 f i f o算法直 接选择 最早进 入系统的 数 据项 进行淘汰。 该算法认 为最早进入系统的数据项在以 后不再使用的可能性比后进入系统的数据项不再被使 用的可能性要大。也就是说， 进入系统的数据项是按照时间 顺序逐一被访问， 数据项 被访问的频度相同并且在将来不再被访问。 如此， 数据项的访问局部性特性就不复存 在或没有意义了。 ( 2 ) c l o c k / g c lo c k算 法。 在 c lo c k 算法中 ， 将 所 有 数 据 项 ( 在 本 算 法中 指 页耐 一一-一 - 一- 4 华 中 科 技 大 学 硕 士 学 位 论 文 通过一个循环链表相关联， 每个数据项和一个比 特位( b i t ) 相关联， 用它来指示在最近 一次选择指针的循环中该数据项是否被引用过。当需要替换数据项时，选择当前指针 指向的数据项，如果与该数据项相关的比特位为1 则将它置0 ，指针前进指向下一个 数据项。第一个被找到的、比 特位为0 的数据项将会被替换。 c l o c k 算法实质上是对 l r u算法的 模拟， 它们有着相似的缓存命中率2 2 1 在 g c l o c k算法中，每个数据项和一个计数器相关联，当数据项第一次放入缓存 时， 与之相关联的计数器被置于一个初始的 权值， 这个值可能随着数据项类型的不同 而不同。当数据项被引用时，计数器增加或重置。当需要替换数据项时，c l o c k指针 循环地扫描链上的数据项，同时减少相关联计数器的计数值， 直到找到一个计数值为 0的计数器，与这个计数器相关联的数据项被作为替换项。当选择恰当的权值时， g c l o c k 算法的性能比c l o c k 算法要好一些2 6 1 ( 3 ) l r u i l r u - k算法。 l r u算法假设将来的行为是现在行为的延伸， 认为最近 使用过的数据项在将来被访问的概率较大， 并且数据项最近一次被访问的时刻离现在 越远，它今后被访问的可能性也越小，越适宜被替换。 虽然l r u算法在各种软件系统中被广泛应用，但是，l r u算法在做出替换决定 时利用的信息很少。 比如， l r u算法不能区分有较多引用计数的数据项和有较少引用 计数的数据项。 数据项一旦被放入缓存中， l r u算法就会给它一个很长的生命期， 而 不管该数据项是否在将来不再被引用， 这使得 l r u算法不能很好地适应可能存在大 量随机存取的移动计算环境。 l r u - k算法解决了这一个问题。 它利用更多的历史存取记录来做出替换决定， 其 基本思想是:记录前 k次数据项的引用时刻，过去第 k次引用时刻距现在最远的数 据项将被替换。 l r u - k算法能够有效隔离短期内被频繁访问然后不再被使用的数据项 的干扰， 对于容量较小的移动缓存系统有较大作用。 虽然l r u - k比l r u更有效， 但 是它需要更多的处理开销，并且每个记录需要k个存储时刻的空间。 ( 4 ) t l l 算法。 t l l 是在l r u - k方法的基础上改进而来。 它把当前缓存中的语 义区域组织成一个个的簇( c l u s t e r ) ，在簇内部按照各个语义区域最后被访问时间 戮的 早晚顺序构成一个链表， 每个语义片段属于且仅属于一个簇， 每个簇具有最后一次被 访问的时间戮标记。 根据新到来的语义区域与当前各个簇中 语义区域的语义关系， 对 之进行簇的分配。当需要淘汰语义片段时， 首先选择具有最 “ 老”时间戳标记的簇作 为待淘汰项，这是第一级。然后从该簇中依次选取具有最 “ 老”时间戮标记的语义区 域进行淘汰，这是第二级。 如果此时的缓存空间仍然不能满足需要， 那么， 重复上述 华 中 科 技 大 学 硕 士 学 位 论 文 操作。 如果该簇不再含有任何语义区域， 此簇不再存在， 那么再找出当前具有最“ 老” 时间戳标记的簇进行淘汰。 ( 5 ) m d f 算 法。 m d f 使 用 一个 距离 值函 数为 缓 存中 每 个可 能的 替 换 单 元 ( 论 文中 是语义区域) 分配一个置换权值， 由 这个值来选择淘汰项。 在这个算法中， 置换权值是 基于语义缓存的使用情况确定的。 md f为每一个从客户端提交查询的结果在缓存中 对应的语义区域关联一个权值， 这个权值就是ma n h a t t a n d i s t a n c e 的相反数。 ma n h a tt a n d i s t a n c e是当前缓存中语义区域的几何重心到达当前最后一次被访问的语义区域的几 何重心之间的距离值。当要淘汰一个数据项时， 选择具有最小置换权值的数据项进行 淘汰。 1 .3 论文的研究内容 论文关注大型数据库系统在处理现代应用模式时所面临的主要性能挑战，即海量 数据、大规模并发和复杂计算，主要研究如何利用语义缓存提高基于数据库的应用的 整体性能。因此，将流行的三层架构同语义缓存技术结合起来，并研究与此相关的关 键技术。主要开展的工作如下: ( 1 )研究和跟踪与语义缓存相关的国际上成熟的和最新的技术，包括语义缓存 的表示与组织、 基于语义缓存的查询导出、 语义缓存的置换和更新、以及语义区域的 拆分和合并等: ( 2 ) 将语义缓存技术集成到三层架构中，同时在客户端和应用服务器端进行语 义缓存， 兼顾o l t p 应用和o l a p 应用， 尽可能在本地回答查询， 从而提高整个系统 的性能; ( 3 )语义缓存的置换会带来语义区域的动态调整问题，采用动态合并策略和优 化的算法，目的在于提高语义缓存本身的利用率; ( 4 ) 在语义缓存系统中引入p a x页面模式在物理上组织语义缓存的数据，目的 在于提高处理器和主存之间c a c h e 的利用率; ( 5 ) 考虑o l a p 应用模式的 特点， 在语义缓存系统中引 入聚集视图的语义缓存， 动态选择、 计算和缓存一些具 有较大效益的聚集视图，目 的 在于快速响应聚集查询。 一. 一一 华 中 科 技 大 学 硕 士 学 位 论 文 2 语义缓存技术的理论分析 缓存技术使得工作不必从头开始，能够充分享受先前的工作成果。 在语义缓存技 术出现后， 管理和利用这些成果变得更加方便和高效。 语义缓存技术改变了 缓存技术 的发展方向， 推动了 缓存技术的发展步伐。 简单地说， 语义缓存即是缓存查询的结果 及其 s q l描述。 下面通过对比 语义缓存技术和传统缓存技术， 对语义缓存技术的 机 理进行理论分析。 2 . 1 传统级存技术的分析 缓存技术是一种传统的计算机技术，在各种各样的系统中都不同程度使用到缓存 技术，大多数系统是为了平衡磁盘和主存在访问速度和存储容量方面存在的巨大差 9 巨 。 2 . 1 . 1 操作系统的级存管理 操作系统使用缓冲管理器( b u f f e r m a n a g e r ) 向 上屏蔽底层的 磁盘管理器， 使得缓冲 管理器之上的 应用感觉不到磁盘的存在，由缓冲管理器与磁盘通信，完成实际的读写 操作。 2 . 1 .2 传统数据库管理系统的级存份理 传统数据库管理系统的缓存管理包括，缓冲管理器和聚集视图两方面。 数据库管理系统使用自己的缓冲管理器负责读写磁盘， 数据被缓冲管理器以页面 为单位从磁盘读出， 被存放在缓冲池( b u ff e r p o o l ) 中， 不仅用于回 答本次查询， 而且可 以 用来回答后续的查询。 缓冲池是一段连续的主存空间，为了 便于管理， 被划分成固 定大小 ( 与物理页面同 大小) 的小块，图2 . 1 示意了 数据库管理系统的缓冲池。 数据库管理系统之所以 不重用操作系统的缓冲管理器， 原因在于数据库管理系统 经常能够了 解上层操作( 如扫描、 联接等) 的访问 模式， 从而能够使用预调入( p r e f e t c h i n g ) 技 术以 优化 连 续的 磁 盘 读操 作 2 7 1 ， 另 外一 个原因 就 是 数 据 库 管 理 系 统需 要 底 层的 缓冲 管理器支持强制写佣于灾难恢复 ) 的能力， 而这是 操作系统的缓冲管理器所不具备的。 数据库管理系统的缓冲管理经常使用的置换策略包括l r u , c l o c k 及其变种。 一-一 一 7 华中科技大学硕士学位论文 2 语义缓存技术的理论分析 缓存技术使得工作不必从头开始，能够充分享戮先前的工作成果。在语义缓存技 术出现后，鬻理和利用这魑成果变得鼹加方便和高效。语义缓存技术改变了缓存技术 魏发震方舄，箍动了缓菇技零魏发震疹伎。麓摹姥落，语义缓存帮是缓存蠢璃豹结果 及其s q l 描述。下面通过对比语义缀存技术和传统缓存技术，对语义缓存技术的机 理进行理论分析。 2 1 传统缓存技术的分析 缓存技术是一种传统的计算机技术，在各种各样的系统中都不同程度使用到缓存 技术，大多数系统是为了乎簿磁盘葶馨圭存在谤竭速度帮存赣窖爨方瑟存在黪曩大差 距。 2 1 1 操像燕统的缓存繁理 操终系统使蠲缓 串譬疆器( b u f f e rm a n a g e r ) 上群蔽底层静磁惫管理器，镁得缓冲 管理器之上的应用感觉不到磁盘的存在，由缓冲管理器与磁盘通信，完成实际的读写 操作。 2 1 2 传统数据库警建系统的缓存警瑷 传统数据库管理系统的缓存管理包括，缓冲管瑗器和聚集视图两方面。 数据露簿理系统使嗣蠡己夔缓_ 孛繁理嚣受责读霹磁盘，数据被缓砖管理器黻瑟瑟 为单位从磁擞读出，被存放在缓冲池( b u f f e rp 0 0 1 ) 中，不仅用于回答本次查询，而且可 以用来回答后续的查询。缓冲池是段连续的主存窳间，为了便于管理，被划分成固 定大小( 与物理页面同大小) 蛇小块，圈2 。l 示意了数摄库管理系统的缓冲漶。 数据露簿理系统之掰强不薹霸揉体系统豹缓抟篱理器，豫爨在于数器霹赣疆系统 经常能够了解上层操作( 如扫描、联接等) 的访问模式，从而能够使用预调u k ( p r e f e t e h i n g ) 技术以优化涟续的磁盘读操作1 2 w ，另外一个原因就是数据库管理系统需要底层的缓冲 管理器支持强翻写矮子灾难蔹复) 戆戆力，瑟这是撩佟系统戆缓洚管瑾器繇不爨备筑。 数据库管理悉统的缓冲管理经常使用的熏换策略包括l r u 、c l o c k 及其变种。 7 孥中科技大学硕士学位论文 图2 1 数据库管理系统的缓冲池 实化视图( m a t e r i a l i z e dv i e w ) 也可以看作是一种缓存策略。洳定义一个视图的时 候，一般柬谖哭存罐定义该褪图弱查键诿訇。摇反，一个实倦褫强是一个其内察已经 计算并存储了的视图。大多数商业数猫库管理系统赢持实纯视豳技术，通过熬予底层 的关系表( 一个或者多个) 或者视图预怒义视图，并予以实化，可以在提高系缆性能方 蕊起到很大昭 乍用。当然，数据库管壤系统支持视瀚并不是仅仅蹬于提赢性筑方蘧浆 考虑，同辩考虑到了安全方面静覆蠢，帮通过褫甏瓣藏用户无毅存敬的数据簿对象。 显然，实化视图技术只能葬是静态的缓存技术，实化视图必须事先定义，不能根据用 户的访问模式进行动态的调整。考虑下面这个视图，它计算每一个雇员所负责项目的 预算总额： c r e a t em a t e r i a l i z e dv i e wt o t a l b u d g e ta s s e l e c te m p l o y e e e n a m e ，s u m ( p r o j e c t 。p b u d g e t ) f r o me m p l o y e e ，p r o j e c t w h e r ee m p t o y e n o p r o j e c t e n o g r o u pb ye m p l o y e e e n a m e 如果需要频繁查询某个雇员所负责项目的预算总额，那么借助实化视图t o t a l 。b u d g e t ， 只罴读取一条元缀裁霹滋霆答霜户弱粪谗请求了，大夫提蹇了巷诲懿响应速痰。 2 1 3 客户机，月厦务器系统的缓存管理 在客户桃，服务器系绫( c l i e n t s e r v e rs y s t e m ) 系绫孛，提赢浆缝的性能粒霹扩展睦 翦关键闷慰楚如何充分利用客户端静鲶理器和存储器资源，函魏，绝太多蒙这样的系 统利用了数据传送( d a t as h i p p i n g ) 机制。在数据传邀模式中，客户机负责执行大部分 的查询，当焱询处理所需的数据不在本地时，首先向服务器请求榈应的数据，数据鲍 裂本麸鞭务器传回到客户援，然螽客户捷继续魏行焱诲。爻了减少延运帮阖辍务器兹 交互，大多数数据传送祭绕利用客户端的主存磁盘缀存从服务器传送过来的数据，以 8 华中科技大学硕士学位论文 备将来的髯次使用。在数据传送体系中嵌入缓存功熊后，客户机在本地找不到所需的 数据项时向服务器提出数据请求命令，服务器负责接受数据请求命令，并向客户机提 貘稳应豹数援疆，因鼗，客户撬窝爨务器之藏豹交曩爱蓥予“聪裁驱动”( f a u l t - d r i v e n ) 的。在数据传送系统中，客户机管理缀存数据所使用的技术来源予传统的数据库管理 系统中的缓冲管理技术，即客户机的缀存被当作是一个存储数据项的缓冲池，客户机 爨髓数据颈麴标识，或豢 霉援整拿缓移空凌，来定像攀拿魏数攥矮。数据传送系统使 用的缓存模式包括页面和元组两种缓存模式。 在页面缓存模式【2 8 2 9 】中，客户机和服务器之间传送的基本单位是页面。客户机接 收查询，两下执行到请求攀个夏瑟除羧。如果某个炎嚣不在本蟪缓存之中，国服务器 发出请求。服务器响应客户枧请求，将该页面瓢存储系统中取氆，通过瞬络将其传回 给客户机。需要指出的熄，在一个页瑚之中，真正满足查询要求的元组的比例是很少 验。客户枫对于缓存数攥的管理与传缆躲基于页露的数据缓冲管理是差不多的。如果 客户枫有可藤豹索雩l ，就霹以基于索葶| 属缝送行部分稿描，帮搬灞索雩| f 蟊莱索孳| 页残 靶，同样需鬻从服务器取回) 访问满足搬询要求的页网；如果没有可用的索引，那么必 须扫描整个关系表，在受蕊脱靶时从服务器取回该顾厩。同缓冲管理器一样，贝面缓 存整舔簿鼙熬嚣换燕珞，