（计算机软件与理论专业论文）web数据库服务器在线视图动态选择问题研究.pdf

山东大学硕士学位论文 摘要 随着i n t e m e t 的高速发展，产生了海量的w 曲信息，其中动态网页占了很大 的部分。然而动态内容比静态内容需要更大的资源需求，并且给w 曲服务器带 来了一个很大的问题，就是伸缩性。 动态网站的缓存能够解决伸缩性的问题，然而同时带来的一个问题就是采用 缓存技术必须将数据请求和数据更新进行耦合，因为如果将对象更新而使缓存失 效，这将必然使得下一次的请求需要重新进行计算。举例来说，假设有个缓存用 来储存动态产生的网页，在一般情况下，我们有8 0 的点击比率，也就是说只有 2 0 的页面需要重新计算。如果我们稍微更新一部分数据，那么有很大比例的缓 存页面就会失效，同时，点击率也会急速下降。这样就会导致平均相应时间的急 速上升，进一步有可能导致服务器的饱和。视图物化能够解决这个问题，因为它 能够将服务请求和数据更新进行解耦。 选择那一种视图去物化，即物化视图选择问题，已经在数据仓库方面有了很 多的研究。但是数据仓库在更新的时候是离线的，与此不同，大多数的w e b 服 务器在进行后台的数据库更新和维护的时候都是和用户的在线请求并行的。因 此，在w e b 的环境下，选择哪种视图物化，必须动态地决定，需要同时考虑性 能和数据更新。 在本文中，我们提出了o v i ) s ( 0 ) ，一种在线视图选择问题的自适应算法。 o v d s ( 0 ) 就像系统中的把手一样，决定运行时哪些视图被物化( 缓存和数据一 起更新) ，哪些只是被缓存而被尽量复用。参数。对应对于系统来说可以接受的 数据有效性的一个级别。 关键词视图物化；数据有效性；性能 山东大学硕士学位论文 a b s t r a c t t h er a p i dd e v e l o p m e n to fi n t e m e tg e n e r a t e sas t a g g e r i n ga m o u n to fw e b c o n t e n t , e s p e c i a l l yd y n a m i cw e bc o n t e n t h o w e v e r , d y n a m i cc o n t e n th a ss i g n i f i c a n t l y h i g h e rr e s o u r c ed e m a n d st h a ns m i l ew e bp a g e s ( a tl e a s to n eo r d e ro fm a g n i t u d e ) a n d c r e a t e sah u g es c a l a b i l i t yp r o b l e ma tw e bs e e 陪 d y n a m i cw e bc a c h i n gh a sb e e np r o p o s e dt os o l v et h i ss e a l a b i l i t yi s s u e 1 1 l e b i g g e s tp r o b e mo fe m p l o y i n gc a c h i n gt e c h n i q u e sf o rd y n a m i cw e bc o n t e n ti st h e c o u p l i n go fs e r v i n ga c e e s sr e q u e s t sa n dh a n d i n go fu p d a t e s ，s i n c ea nu p d a t et h a t m v m i d a t e sac a c h e do b j e c tw i l l r e s u l ti nt h eo b j e c tb e i n gr e c o m p u t e do nt h en e x t a c c e s sr e q u e s t f o re x a m p l e i m a g i n eac a c h et h a tc 髓s t o r ed y n a m i c a l l yg e n e r a t e d w e bp a g e s d u r i n gn o r m a lo p e r a t a o nw eg e ta l l8 0 h i tr a t e ( w h i c hm e a n st h a to n l y 2 0 o ft h ep a g e sw i l ln e e dt ob er e c e m p u t e d ) i fw eg e tas m a l ls u r g ei nt h eu p d a t e s t r e a m , a b i g p e r c e n t a g e o f t h ec a c h e d p a g e sc o u l d b e i n v a l i d a t e d , a n d t h e h i tr a t e w i l l d r o ps i g n i f i c a n t l y as u d d e nd r o pi nh i tr a t el e a d st oas u d d e ni n c r e a s ei nt h ea v e r a g e r e s p o n s et i m ea n dp o s s i b l yt os e r v e rs a t u r a t i o n v i e wm a t e r i a l i z a t i o nc a ns o l v et h i s p r o b l e m , s i n c ei td e c o u p l e st h es e r v i n go fa c c e s sr e q u e s t sf r o mt h eh a n d l i n go f t h e u p d a t e s s e l e c t i n gw h i c hv i e w st om a t e r i a l i z e ，t h ev i e ws e l e c t i o np r o b l e m , h a sb e e n s t u d i e de x t e n s i v e l yi nt h ec o n t e x to fd a t aw a r e h o u s e s h o w e v e r , t m l i k ed a t a w a r e h o u s e s ，w h i c ha r eo f f - l i n ed u r i n gu p d a t e s ，m o s tw e bs e r v o r sm a i n t a i nt h e i r b a c k e n dd a t a b a s e so n l i n ea n dp e r f o r mu p d a t e sc o n c u r r e n t l yw i mu s e ra c e e s s e s t h e r e f o r e ，i nt h ec o n t e x to ft h ew e b ，s e l e c t i n gw h i e hv i e w st om a t e r i a l i z em u s tb e d e c i d e dd y n a m i c a l l ya n dn e e d st oc o n s i d e rb o t l lp e r f o r m a n c ea n dd a t af r e s h n e s s i nt h i sp a p e r , w ep r e s e n to v d s ( 0 ) ，a na d a p t i v ea l g o r i t m af o rt h eo n l i n ev i e w s e l e c t i o np r o b l e m 0 v d s ( 0 ) a c t sa sak n o bi nt h es y s t e m ，d e t e r m i n i n ga lr u n i l m e w h i c hv i e w ss h o u l db em a t e r i a l i z e d ( c a c h e da n dr e f r e s h e di m m e d i a t e l y u p d a t e s ) a n dw h i c ho n e ss h o u l dj u s tb ec a c h e da n dr e - u s e da sn e c e s s a r y p a r a m e t e r0 c o r r e s p o n d st ot h el e v e lo fd a t af r e s h n e s st h a ti sc o n s i d e r e da c c e p t a b l ef o rt h ec u r r e n t a p p l i c a t i o n ， k e yw o r d s v i e wm a t e r i a l i z a t i o n ，d a t af r e s h n e s s ，p e r f o r m a n c e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：彳牡日 期：坦弛， 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：啦导师签名他日期：坐f j 山东大学硕士学位论文 1 1 引言 第1 章绪论 随着i n t e m e t 及其应用技术的不断发展，w e b 上可利用的信息越来越多，并 且每天仍然在快速地增长。目前w e b 上的内容非常丰富，几乎涵盖了人类所有 涉及的领域，如科技、艺术、教育、商业、政治等，网页资源浩如烟海。在起初 阶段，i n t e m e t 服务主要是提供一些静态的页面，发布一些对用户来说不是很及 时和更新不太频繁的信息，而且维护量不大，对w 曲服务器的性能要求不是很 高；随着i n t e r a c t 技术的不断发展，为了能够为用户提供快速、丰富、及时的数 据信息，w 曲服务器现已能够动态的产生多彩的网页，例如现在许多网站提供的 实时地新闻播报、现场直播和一些最新的资讯信息等内容，为用户方便的查阅信 息提供了很大的便利。但对于w e b 服务器而言，提供动态的页面比提供静态页 面需要占用更多的系统资源，随着用户访问的增多和数据更新频率的越来越高， 进一步加剧了服务器的负担，使得页面的访问速率异常的缓慢。 如何有效地解决这个问题，现在一般都是利用动态缓存( d y n a m i cc a c h i n g ) 技术。它利用对访问过的网页进行存储来避免用户下一次访问该网页时再次访问 网络服务器，用户可以直接在c a c h e 上得到所需要的数据。然而，缓存更多的被 用于对静态网页的访问进行优化，对于大量产生的动态网页，缓存技术常常显得 无能为力。例如，我们假设一个能够存储动态网页的缓存一般情况下有8 0 的命 中率，如果这时对于数据的更新频率突然加大，则缓存中的大量页面将被标注为 失效：相应的，缓存的命中率将大大的降低，随之而来的是查询响应的平均时间 大大增加，甚至导致服务器的饱和和崩溃。 对于这个问题，物化w e b v i e w 是一种有效的解决方案。物化视图是在数据 库查询优化中首先采用的技术，它是指在数据仓库中将一部分查询视图预先进行 计算并加以无力存储，这样可以有效地加快数据仓库对查询的相应速度。它已成 为提高系统多维分析性能的重要手段。然而，一定约束条件下物化视图集的选择 属于n p - h a r d 问题，一直是数据仓库界研究的热点。通常，当定义一个视图时， 数据库只存储定义该试图的查询语句，而一个物化试图是一个其内容已计算并存 山东大学硕士学位论文 储了的视图。在许多情况下，读一个物化视图的内容比通过执行定义该视图的内 容要快得多。w e b v i e w 是指由基础数据通过程序或者数据库查询而创建的 h t m l x r a l 块或页面，通常我们通过访问网络所得到的页面都是这些w e b v i e w 或 者是由它们所组成的，对w e b v i e w 进行物化并实现将结果存储下来能够大大地 加快用户访问的速率，并能够提高系统的性能。由于w e b v i e w 的物化将把对 w e b v i e w 的访问和更新分开，因此它不会出现类似于缓存中更新频率加快而的 导致的数据访问速度突然降低的情况。 1 2 国内外研究现状 动态缓存技术已经有了广泛的研究与应用，客户端缓存，p r o x y 缓存和服务 器端缓存技术等都被用于对数据访问的优化。在w e b 应用程序中，使用缓冲有 三个方面的优点：一是减少交互的通讯量，即减少在进程和机器间的传输量；二 是降低系统中的处理量，即减少使用查询的次数；三是降低磁盘访问次数。从以 上的三个方面可以看出，数据缓存技术是以空间换取时间的方式，从而提高数据 相应的及时性和w e b 应用程序的可扩展性。然而缓存技术主要是用来避免网络 上静态网页的重复传输，它是基于失效的模式，更适用于静态页面较多的情况。 w e b v i e w 物化已经做了不少的工作，文献【2 】提出了一个离线状态下的物化 w e b v i e w 代价模型，然而在在线动态更新的情况下这种方法并不适用，文献【3 】 分别对在服务器端和数据库端物化w e b v i e w 进行了试验，并得出在服务器端进 行物化能取得更好的综合性能。文献【4 】提出了一个扩展的网络三层模型，在应 用服务器与数据库之间加了一个同步缓存，描述了一种动态调整w e b v i e w 的物 化选择方法，然而对于数据新鲜度的定义和服务器平均响应时间的定义显然很难 让人满意。 1 3 课题研究的主要内容 对w e b v i e w 进行物化存储能提高服务器对数据的平均相应时间，以降低用 户访问数据的时间，然而，物化也会使用户访问无法得到最新鲜有效的数据。在 极端的情况下，对所有的w e b v l e w 进行物化会得到最低的服务器的平均响应时 间，同时数据的有效性也最低；如果所有的w e b v i e w 都不进行物化，每次访问 山东大学硕士学位论文 都通过对数据库的查询来得到数据，则数据的有效性为最高，当然服务器的响应 时间也会降到最低。因此，在w 曲的环境下，必须在线决定选择对哪些w e b v i e w 进行物化，并需要同时考虑系统性能和数据的有效性。在本文中，我们提出了 o v d s ( 0 ) 思想，一种在线视图动态选择的自适应算法。o v d s ( 0 ) 决定运 行时哪些视图被物化，哪些只是被缓存而被尽量复用。参数0 是针对系统可以接 受的数据有效性的一个级别。 本课题的主要工作包括： 1 ) 提出了新的服务器的性能衡量指标； 2 ) 提出了一个w 曲e w 在线视图物化选择算法，保持服务器性能的稳定。 山东大学硕士学位论文 第2 章基本概念 系统结构是把系统的功能组织成互相连接的模块。每个模块是系统的一个组 件，执行一些相关的功能。好系统机构的目的就是把功能需求合理的分组成模块， 把模块组织成系统以满足所有的要求。 2 1 系统架构 最早的数据库系统是单层的。所有的功能都包含在一个大系统中，并且用户 “哑”终端连接到系统上。后来，随着终端用户工作站获得计算能力，一些处理 和功能渐渐的从单层系统中分离出来，分散到客户服务器结构中的终端用户( 客 户端) 机器上。客户端子系统具有格式化和简单处理功能，而服务器保留了大多 数数据管理功能。随着数据库的增长以及需要连接到企业系统中，三层结构对简 化客户访问分布在多个独立服务器上的多个数据库是必需的。中间层使得客户应 用程序通过一个通用接口可以连接多个d b m s 。 w 曲数据库系统把w 曲服务器集成为系统中的一个模块，并且使用w 曲传 输协议( 例如h t t p ) 在层与层之间进行通信。w e b 数据库系统可能是客户一服务 器结构、三层或n 层结构，其中三层结构是目前最流行的结构。在三层结构方法 中，d b m s 把数据传输给w e b 服务器，w 曲服务器把数据发送给w e b 浏览器。 在n 层结构中，一系列数据库和应用服务器给一个( 或多个) w e b 服务器发送数 据，w 曲服务器然后把数据发送给客户端。 图1 给出了一个简单的w e b 数据库系统的三层系统结构。该系统包含三个 模块： d b m s 提供数据库存储和访问。该模块的技术选择包括关系型d b m s 、 面向对象的d b m s 、x m l d b m s 、或者文件系统。 中间层提供一个w e b 服务器，可以访问d b m s 的数据并使客户端可以 4 山东大学硕士学位论文 访问数据。中间层的技术选择包括w e b 服务器、具有c g i 脚本的w 曲服务器、 具有s e r v e n j e t 的w e b 服务器、具有j a v as e w e rp a g e s 的w e b 服务器、具有数据 库连接的商用中间层或应用服务器。 客户端提供一个用户接口，具有通过中间层的功能。客户端也可能是另 一个应用，如b 2 b 环境中的一个应用。客户端的技术选择通常包含浏览器、j a v a a p p l e t 、或j a v a 应用程序。 我们对典型的3 层体系结构的w 曲服务器进行扩充，在应用服务器和数据 库服务器之间增加异步缓存模块( 如图1 所示) 。在新的结构下，w e b 服务器接 受用户的请求，应用服务器负责w e b 工作流管理，缓存模块充当一种中介，而 不是应用服务器直接面向数据库服务器。与传统的在数据更新时缓存就失效不 同，异步缓存中的数据可以被物化，在数据更新的时候立即进行更新。 2 2 物化视图理论基础 2 2 1 数据仓库理论 图1 系统结构图 f i g 1s y s t e ma r c h i t e c t u r e 数据库系统作为数据管理手段，从它诞生开始，就主要用于事务处理。经过 数十年的发展，在这些数据库中己经保存了大量的日常业务数据。传统的业务系 统一般直接建立在这种事务处理环境上，它以数据库为中心，从事事务处理、批 处理和部分相对简单的决策分析等数据处理工作。随着技术的进步，人们试图让 计算机担任更多的工作，希望计算机更多地参与数据分析与决策制定领域，实现 商业智能；而数据库技术也一直力图使自己能胜任从事务处理、批处理到复杂的 决策分析处理等各种类型的信息处理任务。然而人们逐渐认识到，事务处理和分 析处理具有不同的特征，事务处理系统无法解决分析处理系统必须解决的数据集 成、动态集成、历史数据和数据综合等问题，直接使用事务处理环境来支持决策 山东大学硕士学位论文 是行不通的。要提高分析和决策的效率和有效性，分析型处理及其数据必须与操 作型处理及其数据相分离。必须把分析型数据从事务处理环境中提取出来，按照 d s s e c i s i o ns u p p o r ts y s t e m ，决策支持系统) 处理的需要进行重新组织，建立单 独的分析处理环境。数据仓库正是为了构建这种新的分析处理环境而出现的一种 数据存储和组织技术。 与传统的操作型系统不同，数据仓库中，概要的、总体的数据比细节的、单 条的记录更重要，其数据可能来源于多个操作型数据库，包含大量的( ( g 级甚至 t 级) 历史数据，支持即席的、复杂的查询，这些查询通常需要访问大量记录， 进行复杂的连接、聚合运算，因此，在数据仓库中，查询吞吐量和查询响应时间 比事务吞吐量显得更重要。 o l a p ( o n 1 i n ea n a l y t i c a lp r o c e s s i n g ) 技术使数据仓库能够快速响应重复而 复杂的分析查询，从而使数据仓库能有效地用于联机分析。o l a p 的多维数据模 型和数据聚会技术可以组织并汇总大量的数据，以便能够利用联机分析和图形工 具迅速对数据进行评估。当分析人员搜寻答案或试探可能性时，在得到对历史数 据查询的回答后，经常需要进行进一步查询。 在传统数据库中，视图是从一个或多个基表导出的表。视图被认为是一个 逻辑上的概念。数据库中一般只存储视图的定义，而不存储视图中的数据。 数据仓库中存储的数据是由底层数据库或其他数据源中的数据经提炼、加 工而成的。从这个角度来看，它类似于数据库系统中视图的概念。但数据仓库系 统中的视图与传统数据库中的视图概念又不尽相同，它不仅仅是一个逻辑上的概 念，同时也是物理存在的。 在数据仓库系统中，不仅存储着视图的定义信息，同时也物理地存储着视图 中的数据，我们称这种视图为物化视图或者实体化视图。 2 2 2 物化视图技术 物化视图技术是数据仓库中常用的提高查询性能的重要的技术之一。 物化视图，也称为实化视图，就是一些经过简单的数据预处理，譬如，连接、 投影、分组等，生成的存储在数据仓库中的实实在在的表。也就是说，物化视图 是提前对数据仓库中的数据进行连接、计算，把可能用到的查询结果先保存起来。 山东大学硕士学位论文 通过这样的预计算，对数据仓库的大部分查询就可以直接通过对物化视图的查询 或简单计算得到结果。而且在物化视图上可以进一步使用索引等提高查询效果酏 手段，从而可以大大降低数据仓库的查询响应时间。 由于数据仓库查询要从海量数据里面得到精简的汇总结果，物化视图对于提 高数据仓库的性能非常重要，所以在数据仓库设计过程中，物化视图不是可有可 无的补充，同时数据仓库中的物理结构中的一部分。 物化视图在提高系统性能的同时也带来了许多新的问题。数据仓库中的数据 来源于其他独立的传统数据库，当这些数据库的原始数据发生变化( 插入、删除、 更新) 时，数据仓库中的物化视图与原始数据变化应保持同步，即需进行视图维 护( v i e w m a i n t e n a n c e ) ，以保证在源数据发生变化后视图也是最新的。存储实视图 要占据存储空间，进行视图维护要占据c p u 时间，这样存储过多的视图不仅占 据过多的空间，还会使得视图维护代价过高。由于数据的属性连接组合非常多， 鉴于空间限制和将来维护的原因，只能选择其中一部分实体化( m a t e r i a l i z e d ) 如 何选择以及选择哪些视图进行实体化就成为目前数据仓库研究的重要内容。视图 的选择直接影响用于决策支持的数据质量和数据仓库的效率和维护代价。 关于物化视图问题大致可以分为三个子问题：物化视图选择、物化视图维护 和用物化视图进行查询优化，这三个子问题当中还包括一些视图的相关问题，如 视图大小评估，计算视图的依赖性、视图存储的有效结构。 视图选择问题的目标是在给定的约束条件下( 如视图实体化时间、视图存储 空间大小、总的视图维护时间等) ，在数据仓库中选择合适的视图集加以物化， 来减少总的查询响应时间和视图维护的代价目前所提出的算法主要有两种：一 种是已知查询的集合和物化视图的可利用空间，选择哪些视图来最大限度地提高 系统的性能：另一种是从视图维护代价的大小这一角度出发来进行视图选择 数据仓库是存储供查询和决策分析用的集成化信息仓库，其数据来源于对上 一级或外部数据源进行的抽取、转化、加载。为了减少系统的响应时间，有效地 提高数据仓库查询的性能，对部分视图进行物化是构筑数据仓库的一个重要策 略。那么为了为使物化视图与源数据保持一致，当源数据发生变化时，如何使数 据仓库视图及时地反映源的变化，即视图维护问题，是数据仓库众多热点技术中 的一个重要分支，物化视图维护作为数据仓库维护技术中的一个关键技术，其研 7 山东大学硕士学位论文 究已成为数据仓库研究的一个专题。 视图维护的第一个问题是数据的抽取。由于企业应用环境非常复杂，它们可 能分布在不同的地理位置，使用不同的数据库和操作系统平台，如何追踪和同步 数据源到目标系统的定义，研究提取和转换数据的方案，包括解决转换时产生的 不一致的或不精确的数据，保证它能提供一个自动化的和可靠的移动和维护数据 方法，使数据随业务需求不断得到刷新，是仓库视图维护应该解决的问题。 数据仓库维护的另一个重要问题是，如何执行查询与定时维护而不相互妨 碍，特别在查询和定时维护长时间运行的时候。我们知道，对某一元组，即使读 取会话与维护事务同时进行也不会相互影响，因为从概念上，它们是在不同的版 本上进行的。但当同时访问某数据块或存在交叉存取事务时，如何利用锁与时间 戮协议来保证事务的串行，以维护仓库数据的一致性，也是物化视图维护要解决 的问题之一。 已有的维护策略主要分为两种：定时维护和联机维护。所谓的定时维护是指， 维护是在事务提交之后在给定的时间点上进行的，它把己有的更新信息写在一个 更新事务中发给目标节点。当前的数据仓库产品，主要采用这种方法。它们对视 图的维护都采用晚间作业，即利用夜晚时间对数据仓库进行刷新维护。这种策略 的优点是降低了通信量，避免与查询的冲突，并且事务回滚所引起的代价也小， 只需放弃本地的更新即可，与其它节点无关。但是这种方法的缺点是，当一个事 务预提交( p r e c o m m i t ) 时，它并不知道是否能够成功提交，要等到更新信息传播 到其它节点之后才能知道是否存在数据冲突，而这时的事务回滚代价较大。当事 务间有值依赖时，还会引起级联回滚。另外，定时维护不能保证数据的实时性。 另一维护策略是联机增量式维护。它是指每个维护操作包含在执行事务中， 并且要同步传播到目标节点上，与事务提交时所有的维护一起提交，以保证维护 的增量进行。这种方法简单地保证了事务的串行性，它的事务执行可看作是目标 数据库中事务执行的简单扩展，但是它的缺点是通信开销大，事务的平均响应时 间长。 另外，联机维护方法在事务回滚时，要通知每个目标节点放弃维护，增加了 事务回滚的代价。这种维护策略主要是用在对数据的即时性要求高，如战场决策 方面，或通讯质量高的部门进行。 山东大学硕士学位论文 2 3 物化视图选择问题 在数据仓库的物理设计过程中，选择要物化的视图是很重要的。设计者希望 获得好的查询性能，同时获得低的维护代价，然而他们是矛盾的。物化视图的选 择问题要尽可能的考虑各种对整个系统有利的、不利的因素，找出最好的符合物 化视图设计目标的方案。 很显然，物化视图的数量越多，使用物化视图能够回答的查询就越多，从 而越有利于缩短系统响应查询的时间，提高效率。然而物化视图选择还要考虑很 多负面因素。 首先物化视图需要占用存储空间，物化视图技术属于一种空间换时间的技 术，物化很多的视图，对于存储空间的要求可能是难以接受的。对于有n 个维的 数据立方体，假设每个维只有一个级，其所有的视图个数为2 4 ，全部物化的大小 可能为所有基表的几倍，甚至几十倍。 其次，当物化视图的源数据发生变化时，建立在其上的物化视图需要维护， 以保持数据一致性。对于数据量具大的数据仓库来说，维护物化视图是不小的开 销。在存储设备日益降价的时代，维护代价更是物化选择要考虑的首要不利因素。 基于以上两点，物化视图并不是越多越好，物化所有的视图更是不可行的。 不但会占用大量的存储空间，而且会有很大的维护开销。但是，如果不采用任何 物化措施，那么查询响应时间会很长，也不可取。通常的做法是通过一定的算法， 选择出部分的视图进行物化，来寻求一种效率跟开销之间的平衡。在可以接受的 开销内，达到最好的性能。 在物化选择中通常考虑的因素有用户访问频率、基关系得更新频率、查询 代价、视图维护代价、系统的存储空间限制。通常考虑被物化的视图是那些具有 很高的用户访问频率的视图或被普遍用来计算其他视图的视图。 2 4w e b p a g e 结构图 在一个w 曲系统当中存在3 种数据对象：关系、w e b v i e w w e b p a g e 。 关系是在数据库服务器中存储结构化的数据的一个对象。 w e b v i e w 是h t m l 或者x m l 片段。它通常是由数据库查询结果( 如：数 9 山东大学硕士学位论文 据库视图) 在h t m l 格式下或者x m l 语义标签的作用下而产生的。我们假定 w 曲e w 可以由任何形式的数据库查询形成。 w e b p a g e 是由多个w e b v i e w 构成的，即接受用户请求而返回的页面。 我们说一个w e b v i e ww j 源于关系m ，如果、7 巧包含由基于关系m 的查询 而产生的数据。一个w e b 页面p k 源于w j ，如果p k 包含、) l j j 。 这些数据对象之间的联系我们可以用一种有向无环的w e b p a g e 结构图来描 述。图中的节点对应于关系、w e b v i e w 和w e b p a g e 。只有当节点b 是直接来源于 节点a 时，a 到b 的边才存在。一个节点可以有多个双亲，因此节点的入度可以 大于l ；关系是图中的根，它们是0 入度的：w e b p a g e 是叶子，它们是0 出度的。 图2w e b 页面结构图 f i g 2w e bp a g ed e r i v a t i o ng r a p h 图2 是这种w e b 页结构图的一个例子。我们假定数据库中含有3 个关系( r l ， r 2 ，r 3 ) ，4 个w e b v i e w ( w l ，w 2 ，w 3 ，w 4 ) 和2 个页面口l ，e 2 ) 。实际中，一个站点 通常具有上千个w e b 页面，每个页面上有许多h r m l 或咀。片段。然而，我 们希望有相当数量的w e b v i e w 可以在这些页面中共享。比如：想象一个个性化 的新闻站点。每个用户都会选择自己感兴趣的类型的新闻( 比如：当地、国际和 经济新闻) ，指定天气预报的城市和给出一系列能够计算他( 她) 的有价证券的 股票代码及购买价格和数量。尽管上述的要素的组合很可能是唯一的，但是除了 标准的导航和表示片段外，仍然会有一定数量的股票或者城市w e b v i e w 可以被 成千上百的用户所共享。 山东大学硕士学位论文 2 5 物化策略 当一个用户访问具有动态内容的页面时，其所提交的请求都会被异步缓存模 块( 简称a c s ) 所拦截。a s c 根据以下三种策略之一维护所有的w e b v i e w 。 ( 1 ) 虚拟物化w e b v i e w 是在用户的访问请求时产生的，并且不对查询的结果 进行缓存。在这种情况下，虽然数据的有效性比较好，但访问的性能非常低。 ( 2 ) 不物化w e b v i e w 首先在用户第一次访问请求后产生，并把结果缓存在 a c s 。如果源数据没有更新，则用户以后每次访问该w i b e w 时都将直接适用 缓存中的数据：如果该w e b v i e w 的数据源进行更新操作，则将该w e b v i e w 标识 为失效，在下一次访问时将重新生成该w e b v i e w 。该方法类似于传统的缓存技 术。 ( 3 ) 完全物化w e b v i e w 在生成后被缓存在缓存中，并且数据源每次更新后都 会对该w e b v i e w 进行自动更新。对w e b v i e w 的访问都是通过对a c s 中相应内 容得读取来进行的，因而，平均响应时间在3 种方法中最快。然而，如果把所有 的视图都物化，虽然平均响应时间很低，但会得到最低的数据质量。 不物化策略是的用户能够尽可能的得到新鲜有效的数据，并且在该种策略 下，服务器对用户的平均响应时间要比虚拟物化策略低得多。因此，如果假设对 过期的不物化w e b v i e w 进行失效操作代价很小，那么不物化策略的性能肯定高 于虚拟物化策略。鉴于此，我们不采用虚拟物化的方法。完全物化和不物化的区 别在于前者在源数据更新后通过后台进程对w e b v i e w 进行不断的更新，而后者 在源数据更新后将w e b v i e w 标识为无效。在本文中，我们仅考虑h t m l w 曲e w 。仅处理h t m lw 曲v i e w 意味着从一些w e b v i e w 产生另一些w 曲v i e w 的成本是可以忽略不计的。因此，本文仅考虑从关系数据直接产生的w 出v i e w 的物化问题。我们在文献 5 ，6 】中指出，如果w e b v i e w 被物化，那么它们的响应 时间可以明显地减少，从而可以补偿物化给系统后台所造成的负担。 山东大学硕士学位论文 3 1 性能定义 第3 章性能参数 我们设定一个时间间隔t ，观察在这段时间间隔内的请求的数量，并同时计 量系统对每一个请求的响应时间。 定义1 性能是通过系统对用户请求的平均响应时间来衡量的。 特别指出，我们衡量的时间是从请求来到开始到响应结束。统计所有请求的 响应时间，可以为我们如何提高w e b 服务器的性能提供依据和参考。 对于每一个访问用户来说，提高w e b 服务器的性能也许对他们的访问效果 没有明显的变化。假若在服务器端的响应时间有十倍的改善( 比如：从1 0 0 毫秒 到l o 毫秒) ，终端用户仍然有可能察觉不到，因为响应消息到达终端用户需要在 网络传输上会有几秒的时间延迟，但是十倍性能的改善可以极大提高服务器的扩 展性能：同样的服务器设置可以为l o 倍的用户服务，或者可以处理l o 倍的负载 而无需额外的硬件成本。 3 2 数据质量定义 在过去，人们忽略了数据密集型的w e b 服务器所产生的数据的“优良性”。 然而，随着w e b 服务器被越来越多地用到一些重要的领域( 比如：股票市场信 息) ，衡量和提高为用户提供的数据的质量是非常重要的。w e b 服务器的一个公 共的特征是：它们是一直在线的。由于这个特性，需要我们在对源数据的进行更 新的同时应该考虑对用户请求的结果进行更新。因此，服务器提供数据的有效性 是衡量数据质量的最重要的方面。 定义2 数据密集型w e b 服务器的数据质量是平均w e b 页面数据有效性。 当一个关系需要更新时，在服务器端，依据它所产生的关系和其他所有的数 据对象都将变成过时的；在客户端，在它们被全部更新前，所访问的页面内容也 是过时的。 山东大学硕士学位论文 ： 更新到的时间 -d l # u 口，1 1 日j _ 。| i l 触发更新 卜- ，：、 鱼：! ! 。 坠三：竺：墨堑塞盛盟堕旦 英荔时i ； ； _ 卜一 ：物化的试图过时 图3 视图过时的例子 f i g 3s t a l e n e s se x a m p l e 蹴过时l d h 叫 ：过时 ； 我们用一个例子说明这个问题( 如图三所示) 。假设图2 中只有w l 和w 2 是物化的，如果对于r l 的更新在t l 时刻到达，那么r 1 是过时的，直到t 2 t l ， 即对r l 的更新完成。尽管我们没有考虑关系的缓存，关系r l 仍然是过时的， 因为在t l 和t 2 之间更新没有完成。另外一个方面，物化的w e b v i e w w l 从t 1 开 始是过时的，直到t 3 t 2 ，它的刷新完成。如果对关系r 3 的更新在t 4 到时，那 么关系r 3 在时间t 5 更新完成前的【t 4 ，t 5 】的时间间隔内被认为是过时的，同样， 没有物化的网页视图w 3 和w 4 在时间间隔 t 4 ，t s f 司也将是过时的。另一方面， 物化的网页视图w 2 从时间“在他的刷新完成前直到t 6 t 5 之间也将是过时的。 我们标识四种可以认为是过时的数据对象：关系，非物化网页视图，物化网 页视图和网页。 关系是过时的当对他们的更新已经到达，但还没有执行前。 非物化网页视图是过时的当对他们的父关系的更新已经到达但还没有执 行前。 物化网页视图是过时的如果这个网页视图没有被刷新( 在父关系的更新之 后) 。 网页是过时的如果父网页视图是过时的。 为了度量网页的有效性，我们观察在一定时间间隔t 内的访问流和更新流 山东大学硕士学位论文 量，我们可以把在间隔时间t 内的访问流作为一个n 个访问请求的序列。 ，a x ，a x + l ，a x + 2 ，a x + n l ， 访问请求a x 被标记为( 巧，戗) ，这里t x 是访问网页巧的请求到达的时间， 每一个网页p i 由许多的h t m l 代码片断( 网页视图) 组成。 我们定义在时间t k 时，网页视图w i 的有效性函数如下； ( w i , t k ，= 戚羹淼。k 淼) ( 1 ) 我们认为一个网页视图w l 是过时的主要有两种情况，一是如果、) 1 7 i 是物化 的，但是已经失效了；二是晰没有物化但是存在一个对其父关系的挂起更新。 除此之外，网页视图w i 是新鲜的。 为了来量化对每一个访问请求返回数据的有效性，我们认为网页是基于多个 网页视图构成的，一个简单的测定有效性的方法是通过要求一个网页的所有的网 页视图是新鲜的，即可认为此网页是新鲜的。在此方案下，即使其中的一个网页 视图是过时的，这整个网页将会被标记为过时的。在很多场合，象这样的涉及网 页新鲜度的一个很严格的布尔体系是不适当的。例如，一个具有股票信息和天气 信息的页面不能被认为是完全过时的，因为即使所有股票价格是过时的，但是天 气信息是很少过时的。由此我们采用一种均衡的定义，我们把网页有效性设为一 个介于0 和l 之间的有理数，为0 则表示完全过时，为1 则表示完全有效，通过 在时间1 l 【的访问请求a k = ( 巧，t k ) 来计算f ( a k ) ，我们可以得到网页巧的有 效性值。组成该网页的所有网页视图新鲜度的加权和公式如下： i ( a k ) 。，( 乃，t ) = a i , jx ，( 嫩，“) ( 2 ) 这是n j 是在网页p j 里的网页视图的数量，而面是一个加权因子。加权因子 画为每一个网页视图来定义，并且经常被用于量化在一个网页中不同网页视图 的重要性。在每一个网页中的加权因子的和必须是l 。当一个网页视图w i 不再 是网页p j 的一部分，那么相应的加权因子为0 ，或萄= 0 ，缺省的，加权因子 被设为a i j = l 细，这里n j 是网页巧中网页视图的数量，加权因子也可以由用户 自己定义。n 次访问请求的数据的总的质量被表示为： 1 4 山东大学硕士学位论文 , t + n - - t o o d - - 1x 朋 )( 3 ) i 霉t 3 3 在线视图选择问题 在一个w e b 服务器中，选择哪些网页视图去物化将对系统的性能和数据的 有效性产生很大的影响。我们假设物化所有的视图，这样机器的会提供很好的性 能，但会使提供的数据质量很低。相反地，我们不对所有的视图进行物化，虽然 会提供很高的数据质量，但性能会很低。 我们定义在线视图选择问题如下：在连续的访问和更新流面前，动态的选择 哪些网页视图去物化，使提供的数据的质量q o d 保持在一个可以接受的水平上， 从而使整个系统的性能达到最大化。 在2 4 节我们给出了q o d 的定义，并给出了一个可以接受的数据有效性的 级别是一个阈值o 【0 ，1 1 ，举个例子，我们假设给定一个阙值0 = 0 ，9 ，那么这 将意味着9 0 的访问将会被提供有效数据( 或者说系统提供的网页是由大概9 0 的有效的网页视图组成的) 。 我们强调w e b 系统视图选择问题的特性在于“在线选择”，原因有两个。首 先，因为更新是伴随着访问在线执行的，除了性能外我们必须考虑提供的数据的 有效性；其次，因为访问和更新是连续进入系统的，提供解决视图选择问题的任 何算法都必须在运行时动态的决定，并且能够在负载改变的情况下自适应的能 力。 为了使问题简单化，在此我们假设得到了如图2 中的网页结构图，并且对于 每个网页和w e b v i e w 的数据访问和更新的代价都已知。由于w 曲v i e w 所占的空 间相对较小( 平均为3 0 k b ) ，而此处的缓存通常是数十甚至数百g b 的硬盘，因 此本文不考虑缓存的空间问题。对于物化w e b v i e w 而言，对基础数据的每次修 改都会导致它的一次更新，这个更新可以使增量更新也可以完全更新，对h t m l 形式的文件用增量更新显然比较困难，所以本文中假设所有的更新都是完全更 新。 山东大学硕士学位论文 第4 章在线视图选择 4 10 v d s 算法 传统的视图选择算法工作在离线状态并且假设全部的访问和更新都是已知 的。这样的算法不能工作在在线的环境中，因为w e b 系统需要选择算法必须能 够实时动态的决定物化计划。而且，在线环境下的更新往往是和访问同时发生的。 这使得提供的数据的有效性成为一个很重要的因素，而w e b 服务负载的不可预 知性也使得在线视图选择算法必须能够适应变化的w e b 访问和更新。 在这部分我们描述o v d s ( 0 ) ，一种在线视图动态选择算法，o 是一个用户 指定的q o d 的阈值。o v d s ( 0 ) 努力的把提供给用户的数据的质量维持在阈值0 之上，并且把平均响应时间降的尽可能的低。此外，o v d s 还监控着访问流以防 止服务器堵塞。 o v d s ( o ) 是自适应的，它存在两种工作模式：被动模式和主动模式。当在 被动模式时，这种算法搜集统计当前的访问流量，并且接收观测的q o d 的反馈， 周期性的，该算法进入主动模式，这时他将决定当前的物化计划是否需要改变以 及该如何做。 通过不断的监测提供的数据的q o d ，o v d s ( o ) 判断在下面两种情况下来改 变物化计划。 q o d 过剩 当我