（计算机软件与理论专业论文）利用预测及预取技术的web+cache系统和exgdsf算法.pdf

利朋颐测股 6 l i 议坎术的w e b c a c h e 系统和e x g d s f 算法 图表索弓 h1 、l ：w e bc a c h e 在互联网r 1 1 的分布 i 冬l2 、l ：一般的w e b c a c h e 系统 i 矧2 、2 ：n a s a 口j 出中的清求遵循z i p f 法则 i 钭2 、3 ：n a s a | 1 志中的请求遵循时间局部性 h 2 、4 ：+ 般的w e bc a c h e 算法 蝌2 、5 ：g d s i z e 算法 1 ；! 】2 、6 ：利用预取技术的w 曲c a c h e 系统 h3 、l ：构建关联图的步骤 i 冬 3 、2 ：w e b 日志片断 3 、3 ：对预测模型的测试结果( e p a ) l 剞3 、4 ：对预测模型的测试结果f n a s a ) h4 、l ：预取过程 4 、2 ：利用预取技术的w e bc a c h e 系统的关键部分 【矧4 、3 ：e x g d s f 算法 图5 、l ：模拟过程 灰5 、l ：对命中率和字节命中率测试的结果( e p a ) 农5 、2 ：对命中率和字常命中率测试的结果( n a s a ) 农5 、3 ：对相对延迟和相对网络流量测试的结果( e p a ) 表5 、4 ：对相对延迟和相对网络流量测试的结果( n a s a ) 1 j5 、2 ：肘命中率和字节命中率测试的结果f z p a ) 圈5 、3 ：对命中率和字节命中率测试的结果( n a s a ) 吲5 、4 ：对相对延迟率和相对网络流量测试的结果( e p a ) l 纠5 、5 ：对相对延迟率和相对网络流量测试的结果( n a s a ) 图5 、6 ：不同c a c h e 容量下的预取次数( e p a ) h5 、7 ：不同c a c h e 容量下的预取次数m a s a ) _一加川m肿舯m弼引弱粥n埘弘弼m 利用颅测放颅耿技术的w c bc a c h e 系统和e x - g d s f 算法 摘要 如何解决网络的延迟问题一直是i n t e r n e t 研究领域中最主要的课题之一，在 这个问题上w e bc a c h e 和w e b 预取是两个非常有效的技术。然而，以前大多数 的研究者只是局限于其中的一项技术进行研究。本文提出了一个将两种技术结合 起来的系统，在这个系统中，对预取强度，替换策略和预取带来的网络负载等问 题都进行了研究。 这个整合系统的核心是一个基于w 如同志挖掘的预测模型系统，在利用这个 模型预测能力的基础上，本文提出了一个将预取技术和c a c h e 结合起来的算法， 称为e x g d s f 算法。 本文利用现实的w e b 日志并通过模拟技术对我们的算法性能进行了测试。通 过实验，本文研究了e x g d s f 在减少网络延迟和增加网络负载之间的平衡问题， 并f l 对c a c h e 容量大小对预取性能的影响进行了探讨。 关键词：w e bc a c h e ，w e b 预取，预测模型，替换算法。 、一 k k ， a b s t r a c t r e d u c i n gw e bl a t e n c yi s o n eo ft h ep r i m a r yc o n c e m so ft h ei n t e r a c tr e s e a r c h w e bc a c h ea n dw e b p r e f e t c ha r et w o e f f e c t i v et e c h n i q u e st oa c h i e v et h i s h o w e v e r ， m o s to f p r e v i o u sr e s e a r c h e sa d d r e s so n l yo n eo f t h e s et w ot e c h n i q u e s w ep r o p o s ea n o v e ls y s t e mt oi n t e g r a t ew e bc a c h ea n dw e bp r e f e t c h i nt h i ss y s t e m ，p r e f e t c h i n g a g g r e s s i v e n e s s ，r e p l a c e m e n tp o l i c y a n di n c r e a s e dn e t w o r kt r a f f i cc a u s e d b y p r e f e t c h i n g a r ea l lt a k e ni n t oa c c o u n t t h ec o r eo f o u r i n t e g r a t e ds y s t e mi sa n e f f e c t i v ep r e d i c t i o nm o d e lb a s e do n w e bl o gm i n i n g b yu t i l i z i n gt h ep r e d i c t i o np o w e ro ft h em o d e l ，w ed e v e l o pa n i n t e g r a t e dp r e f e t c h i n ga n dc a c h ea l g o r i t h m ，e x g d s e w ec o n d u c ts i m u l a t i o n st oe x a m i n et h ee f f e c t i v e n e s so f o u r a l g o r i t h mb yu s i n g r e a l i s t i cw e bl o g s w es h o wt h et r a d e o f fb e t w e e nt h e l a t e n c yr e d u c t i o na n dt h e i n c r e a s e dn e t w o r kt r a f f i ca c h i e v e db ye x g d s ew eh a v ea l s od i s c u s s e dw h e t h e r c a c h es i z eh a se f f e c to nt h ep e r f o r m a n c e o f p r e f e t c h i n g k e yw o r d s ：w e bc a c h e ，w e bp r e f e t c h i n g ，p r e d i c t i o nm o d e l ，r e p l a c e m e n ta l g o r i t h m 利用顾测殷顺耳】( 技术的w e b ( a c h c 系统和e x g d s f 算法 第一章概述 本章我们将对w e bc a c h e 和w e b 预取技术做一个简单的介绍，然后回顾一 下以前在此领域所做的工作，并说明我们做这项研究的目的。 1 1w e bc a c h e 及预取技术的应用 随着i n t e m e t 规模的迅速膨胀，用户数量的急剧增加，解决网络拥塞现象愈 发显得重要了。据统计，w e b 页面浏览已经成为i n t e m e t 中最主要的活动之一， h t t p 访问大约占i n t e m e t 中7 5 一8 0 的网络流量。由于大多数w e b 对象或文 档，比如h t m l 页面，嵌入的图片、视频，以及j a v a 小应用程序等都是静态 的，可以在用户和网站之间建立一些缓存，用来存储用户以前访问的静态w e b 对象，这样对提高网络性能有非常重要的作用。 这就是w e bc a c h e 技术的基本思想，在性能比较高的系统中保存些从网站 服务器取来的对象，当用户再次访问的时候，可以快速的获取。 w e bc a c h e 的作用有以下几点： 节省网络带宽。用户请求的文档可以在c a c h e 端得到满足，不需要由远 端的服务器经i n t e m e t 传给用户。另外c a c h e 中的对象可以被多个用户使 用，这样就大大减少了用户的带宽总量。 增加网络的可靠性。当服务器不可访问时，用户可以在w e bc a c h e 中得 到请求对象。 减轻服务器的负担。用户的请求很多可以在c a c h e 中得到满足，不需访 问服务器，从而可以有效的减轻服务器的负载。 减少网络延迟。被缓存的文档可以马上传给用户，由于c a c h e 和用户一 般离的比较近，这样响应时间就大大缩短了。 减少网络延迟对上网冲浪或者进行电子商务活动的用户非常重要，人们利用 i n t e m e t 去访问远端w e b 站点的各种各样的信息，他们总是希望快速得到响应而 不愿等待太久。 另一个提高网络性能的技术是w e b 的预取技术。与w e bc a c h e 技术比较， 预取技术首先预测用户将来的请求，并且在用户请求之前，将预测到的w e b 对 象预取到c a c h e 中，这样当用户以后真正请求这些对象时，它们已经在c a c h e 中了。如果预取的对象是正确的，就可以省去到w e b 站点获取请求对象的时问。 但是如果预取系统做的预测是错误的，将会造成对服务器负载的增加和网络带宽 的浪费。f 确预取的关键是具有一个精确的预测模型，本文将在第3 、4 章详细 讨论。 利用预测及颅取技术的w e bc a c h e 系统和e x g d s f 算法 1 2w e bc a c h e 在互联网中的分布 w e b c a c h e 可以在i n t e r a c t 的不同地方存在，如图1 ： 图 1 、1w e bc a c h e 在互联网中的分布 在客户端，w e b 浏览器有自己的c a c h e ，通常浏览器的c a c h e 容量很小。 现在有一些产品可以扩展或替换浏览器的c a c h e 系统，使其具有更大的容量和更 先进的页面替换算法【l o 】。有一些研究是关于在客户端进行w e b 对象预取工作的 f 2 3 ，2 6 ，由于客户端的w e b 对象不能做到共享，相同的对象要在不同的客户端 都留有备份，这样并没有节省带宽总量，相反，如果局域网内的所有用户都进行 预取的话，由不正确预测所造成的网络拥挤将是非常严重的。 c a c h e 技术广泛的应用在代理服务器( p r o x ys e r v e r ) 中，代理服务器位 于客户端与w e b 服务器之间，客户端的请求和w e b 服务器端的响应都经过代理 服务器。如果代理服务器发现客户请求的文档已经存在c a c h e 中，它可以马上把 c a c h e 中的文档返回给用户，它代理用户到w e b 站点获取文档，并将其存放在 c a c h e 中，最终返回给用户。代理服务器一般存在于网络的边缘部分，例如网关 或防火墙中，它们通常为许多内部用户服务。通常来讲代理服务器端的c a c h e 对于节省骨干网带宽，提高响应速度等有很重要的作用 1 0 】。代理服务器同时也 比较适合实施预取技术，一个非常突出的好处是，预取到代理服务器中的文档可 以被许多内部用户共享，这样由预取所造成的网络负载问题就减轻了很多。 为了提高w e b 服务器的可用性，c a c h e 系统也可以以另外一种“相反” ( r e v e r s e ) 的方式来配置，例如，反向代理服务器( r e v e r s ep r o x ys e r v e r ) 。它 与普通代理服务器的区别在于，反向代理服务器是靠近w e b 服务器的，而一般 利用颅测成颅取技术的w e b c a c h e 系统柙e x g d s f 算法 的代理服务器是靠近客户端的。用户的请求首先经过反向代理服务器再到达w e b 服务器。反向代理服务器中的c a c h e 通常保存着最经常访问的数据，并通过优化 提岛访问速度，可以在很大程度上减轻w e b 服务器的负担。反向代理服务器也 可以用来实施预取技术，由于它与w e b 服务器一般以高速的局域网相联，由预取 带来的网络负载基本可以忽略。但是另一方面，正是由于它与w 曲服务器以高 速网络相联，在减少网络延迟方面性能不会有太大的提高。 i j 面所介绍的几种c a c h e 方案通常同时存在，共同提高互联网的性能。 我们主要研究代理服务器中的缓存及预取技术，但是我们的研究对浏览器和反向 代理服务器同样适用。 1 3 与本项研究相关的工作 在减少文件系统延迟方面预取技术有比较重要的作用 3 3 ，2 4 】。随着 i n t e m e t 规模的迅速增长，近几年来很多研究者丌始关注此项技术在互联网中的 应用【1 4 ，2 5 ，2 l ，1 7 ，2 7 】。然而这些研究并没有把预取与w e bc a c h e 技术结合 起来考虑，这方面的研究还是一个有待探索的领域。 1 9 9 8 年，m a r k a t o s 等人提出了一个叫做”t o p 1 0 ”的预取模型 2 5 1 。他们的 基本思想是在客户端或p r o x y 服务器中为每一个w e b 站点保留1 0 个最常访问的 文档，用户的请求大部分都是这些站点中最常访问的文档，他们的请求常常可以 在本地或p r o x y 处得到满足，这样可以大大缩减响应时问。并且由于对每个站点 只预取1 0 个文档，在用户或代理服务器进行预取时，并不会对网络流量造成太 大的影响，尤其是部署在p r o x y 服务器中时，预取的文档一方面可以共享，另一 方面可以缩减总的网络流量。他们的研究成果表明在增加网络流量大约1 0 的情 况下，访问的命中率达到了6 0 2 5 1 。这种方案比较容易实施，但是如果考虑 w e bc a c h e 的因素，这种方案的效果就会大受影响。因为一个c a c h e 系统总是要 把经常访问的文档保留，把不经常访问的替换出去，如果”t o p1 0 ”在c a c h e 中， 那么它们应该不会被替换，这样就没有必要进行预取了。 1 9 9 9 年，d u c h a m p 基于超链接的w e b 预取方法【1 7 】。其基本思想是预取 当前页面中超链接引用的文档，w e b 服务器收集页面间的引用信息，并将它们附 加在发给用户的响应信息中，用户通过这些信息进行预取。他们的研究表明在增 加网络流量2 4 的情况下，降低了5 2 3 的网络延迟。 1 9 9 6 年，p a d m a n a b h a m 和m o g u l 研究了单纯的w e b 预取技术带来的收益 与增加的网络负载之间的关系 2 6 j 。研究表明，强度越大的预取系统越能减少网 络延迟。但是他们没有研究当预取与w e bc a c h e 结合后，预取的强度对网络性能 有什么样的影响。对文件系统的研究结果表明，当预取与缓存相结合时，强度太 利用颅测成预取技术的w e b c a c l l c 系统和e x - g d s f 算法 大的预取系统对减少网络延迟有害 1 9 ，1 5 1 。原因在于，强度太大的预取系统会 迫使更多的缓存中的文档被替换，在这些被替换掉的文档中有一部分是近期将经 常访问的。 总起来说，以前的研究主要集中在预取系统的性能上，然而他们没有研究 w e bc a c h e 和预取技术之间的相互作用，在研究预取技术时没有探索c a c h e 的管 理问题。 1 4 研究动机 我们相信w e bc a c h e 技术与预取技术可以而且应该结合起来进行研究。我 们认为，应用户要求取到的文档和系统预取到的文档可以存放在同一个c a c h e 中， 并可以遵循同样的替换策略。 预取技术的关键是建立一个精确的预测模型，它用来预测用户将来的请 求。根据有限的用户访问纪录，比如w e b 同志或p r o x y 日志，来建立一个精确 的预测模型是一个比较大的挑战。 我们将主要研究以下几个问题： 怎样去建立一个预测模型预测用户的请求? 怎样将预取技术与w e bc a c h e 技术结合起来? 预取技术的实施，一方面会减少网络延迟，另一方面会增加网络流量。 如何来平衡二者之间的关系? 1 、5 论文的结构 接下来的论文是这样组织的： 第二章，介绍一些常用的w e bc a c h e 的算法，并且介绍了w e b 访问模式的 特征，这些特征促进了c a c h e 算法的改进。 第三章，通过对w e b 日志的挖掘，建立我们的预测模型，并对其性能进行 评测。 第四章，我们分离部署预取和预测模型，建立了利用预取技术的c a c h e 系 统模型，并提出了e x g d s f 算法。 第五章，运用模拟器对利用预取技术的c a c h e 系统进行模拟，并对e x g d s f 算法进行了评测，同时研究了本系统在提高网络性能和增加网络负载之间的平衡 问题，最后对c a c h e 容量对预取性能的影响情况进行了探讨。 第六章，对我们的研究进行了总结，并提出了一些未来的研究方向。 利用顶测发颅取技术的w e bc a c h e 系统和e x g d s f 算法 第二章w e bc a c h e 系统及替换算法 w e bc a c h e 技术在提高网络性能方面有非常重要的作用，近些年有很多关 于这方面的研究。本章，我们回顾一下有关的研究。 2 1w e bc a c h e 系统构架 2 1 1 系统中的术语及约定 本文中我们将用户所请求的w e b 对象，例如h t m l 页面、图片等统一称 为w e b 文档。 我们假设所研究的c a c h e 容量比用户请求的任何一个文档都要大，如果用 户请求的文档在c a c h e 中，那么这个请求可以马上得到响应，我们称之为一次“分 乒”( ah i t ) 。相反，如果c a c h e 中不存在用户请求的文档，那么必须要求w e b 站点返回此文档，并将它存在c a c h e 中，我们称之为一次“石尹”( am i s s ) 。 由于c a c h e 只有有限的容量，当没有足够的容量来存放一个新取来的文档 时，c a c h e 中原来存在的一些文档就必须被释放。用来决定需要替换哪些文档的 算法，称为页面替换算法。 在p r o x y 端的c a c h e 系统同一时间内可以对多个请求进行响应。我们假定多 个响应之问在c p u 处理时间及网络传输速率等各方面不会互相干扰，并且用户 请求的文档必须先保存在c a c h e 中，才能返回给用户。 2 1 2 一般的w e bc a c h e 系统 一个w e bc a c h e 系统的核心部分通常包括以下几部分： c a c h e 管理器：整个系统的控制中心，协调处理其他各部件的操作。 元数据：存储了缓存对象的一些索引信息，便于快速访问。它通常还保 存一些附加的信息，例如，一个对象的最近访问时间，访问频率等。 页面替换算法：是c a c h e 系统的核心，它用来决定是否将一个新来的对 象放进缓存，如果存储空间满的话，它来决定将哪个对象替换出c a c h e 为新来对象让出空阳j 。 c a c h e 存储器：一些物理存储空间，用来保存w e b 对象。 c a c h e 系统在用户和w e b 服务器之间，与两者进行交互。 利用预测及颅取技术的w e bc a c h e 系统和e x g d s f 算法 下图是一个一般的w e bc a c h e 系统的框架和工作流程： l l 用户目 ： 7 c a c h e 臂理器 一 ：7 _ w e b 服务器i 易猡。 夕攥。 li 1r l 页面替换算 _ 一元数据l c a c h e 存储器 法ap 1 p 2 p n 图2 、1 一般的w e b c a c h e 系统 1 、用户向c a c h e 管理器发出对页面p 的请求； 2 、c a c h e 管理器在元数据中查找页面p ，以确定p 是否已经在缓存中。如果 找到，执行3 ；否则，执行4 ； 3 、c a c h e 管理器将页面p 载入到c a c h e 存储器中，执行l o ； 4 、c a c h e 管理器从远端的w e b 站点请求页面p ； 5 、远端站点返回页面p ： 6 、c a c h e 管理器调用页面替换算法a ； 7 、a 收集c a c h e 中w e b 对象的必要信息； 8 、a 做出是否接收p 的决定。如果p 被接收了，并且存储器已没有足够的 空白】接纳p ，那么a 将一些对象替换出缓存。 9 、如果p 被拒绝了，执行1 0 ：否则，c a c h e 管理器将p 存入c a c h e 存储器 中； 1 0 、c a c h e 管理器更新元数据信息，使之与新的c a c h e 状态同步： l i 、c a c h e 管理器将页面p 返回给用户。 2 1 3 性能评价指标 w e b c a c h e 系统的主要目标是减少网络延迟时间，延迟时间是指用户发出请 求和得到响应之问的时问差。网络延迟来源于很多方面，查询域名服务器( d n s ) ， 建立连接，以及在用户和服务器之间传输请求和响应等都需要时间。w e b 服务器 在处理一个请求的时候同样也需要花费时间，尤其是在其负载比较严重的时候。 在我们定义网络延迟计算模型之前，我们先介绍一下当前广泛运用的两个指标： 利用颅测及预取技术的w e bc a c h e 系统和e x g d s f 算法 命中率( h i tr a t e ) 和字节命中率( b y e h i tr a t e ) 。 良父2 、1 ：镛聱是在w e bc a c h e 中命中的请求数与用户总请求数之阆的眈率。 良义2 、2 t 字节命中率是在w e bc a c h e 中命中的字节数s 用户总请求字节数之 i d # l b 当雾。 实际上，命中率和字节命中率是有些矛盾的两个概念，要使两个指标都达到 最高是非常困难的一件事【1 3 】。网络延迟与上面两个定义比起来要复杂一些。在 我们的研究中，我们用相对延迟率这个概念来衡量c a c h e 系统的性能。 凫_ 5 l 2 、3 ；挂贰延退翠是指使用c a c h e 系统霹网络的延迟s 不使用c a c h e 系统 时网络延迟之闯的比率， 定义2 、4 ：相对网络流量屈措刎w e b 厥务器2 自f 廊p r o x y 膨务器之膨矽手蓣彩与 甬户请求的所在字节的比率。 根据上述定义，如果没有c a c h e 系统的话，相对网络延迟和相对网络流量都 应该是1 0 0 。显而易见的是，相对延迟率与相对网络流量越低，c a c h e 系统的 性能就越高。例如，c a c h e 系统如果达到3 0 的相对延迟率的话，这就意味着它 真正降低了7 0 的网络延迟。 2 。2w e b 请求特征 对w e b 服务器负载以及用户访问模式特征的研究促进了w e bc a c h e 算法的 改进 3 ，7 ，9 】。这些特征对于我们研究预取技术与c a c h e 系统的结合很有帮助。 2 2 1 齐普夫法则( z i p f sl a w ) 齐酱夫法则是以美国哈佛大学语言学教授g e o r g ek i n g s l e yz i p f ( 1 9 0 2 1 9 5 0 ) 的名字命名的。最初的研究是来表示文章中单词出现的次数( 频率) 与出现次数 排名之间的关系，假设一个单词在文章中出现次数为p ，出现次数排名为i ，那 么它们遵循下面的关系： p = k i o ( 2 1 ) 这里，c t 是一个接近l 的数，k 是一个常数。 g l a s s m a n 首次将齐普夫法则运用到w e b 页面请求中来1 2 0 】。他们跟踪了d e c 公司的网站，收集了大约1 0 0 0 0 0 条h t t p 请求，最后发现这些请求的分布符合 利用颅测及预取拉术的w e bc a c h e 系统和e x g d s f 算法 齐普夫法则，k 是一个常数并且a = l 。1 9 9 5 年，b e s t a v r o s 等人从波士顿大学计 铮机系网站收集了5 0 0 0 0 0 条w e b 访问纪录，经过分析发现其分布符合齐普夫法 则，并且得到c t = 0 9 8 6 1 8 。1 9 9 6 年，a l m e i d a 等人在对许多w e b 服务器的日志 进行挖掘之后发现对这些服务器访问的分布也符合齐普夫法则 1 】。 通过齐普夫法则我们知道，用户请求一个w e b 文档的可能性与其出现频率的 排名成反比例关系。简单的讲就是一个w e b 文档出现的频率越高，用户访问它 的几率就越大。 一些研究者对n a s a 网站的日志进行了研究，这个日志纪录了从1 9 9 5 年7 月lf i 到1 l 同共l o 天的w e b 访问纪录，共有6 3 9 9 1 7 条请求和大约3 6 0 0 个u r l 。 他们通过程序进行统计，最后的结果如图： 图2 、2n a s a 日志中的请求遵循z i p f 法则 从上图可以发现，大约8 0 的w e b 请求是对访问频率排名在2 0 p a 内的文 档进行访问的，而另外8 0 的文档，只有2 0 的请求会访问到。这可以说明将 经常访问的文档保留在c a c h e 中有助于提高c a c h e 性能的事实，同时也告诉我们 在设计c a c h e 算法时要将w e b 文档的访问频率这个因素考虑在内。 2 2 2 访问的时间局部性( t e m p o r a ll o c a l i t y ) w e b 访问的另一个特征是时删局部性，有研究表明，对再次访问同一文档的 时问通常距离上次的访问时间很短，最近访问的文档最有可能在最近的将来再次 被访问到。这一特征恰好可以说明l r u 算法在w e bc a c h e 中广泛应用的事实。 1 9 9 6 年，a l m e i d a 等人在对n c s a ，b u ，s d s c 等w e b 日志的研究之后发现的 利用预测及颅取技术的w e bc a c h e 系统和e x g d s f 算法 这一特征【1 】。a r l i t t 和w i l l i a m s o n 通过对其他f l 志的研究也发现了这一规律 6 。 1 9 9 7 年，c a o 等人在对d e c 代理服务器跟踪之后同样发现了这样的特征。1 9 9 8 年，r i z z o 对意大利某大学的代理服务器的日志研究后也得到同样的结论【2 9 】。 下图是一些研究者对n a s a 同志分析统计之后得到的结果： 图2 、3n a s a 同志中的请求遵循时间局部性 上图表明，距离上次访问时问越短的文档，越有可能再次访问到，随着距上 次访问时间的增加，其被访问的可能性迅速减小。 通过上面对w e b 访问特征的分析，我们发现w e b 文档具有某种“不平等性”， 在设计c a c h e 算法的时候要考虑这种特征，尽量将最常访问的文档保留在c a c h e 中。 2 3w e bc a c h e 算法 目前有很多w e bc a c h e 算法，难易不一，性能也有很大差别。我们将主要 介绍一下近期的一些研究，下面的算法是对现在一些常用算法的一般化表示。 p r o c e s se a c h r e q u e s td o c u m e n t i nt u r n ： l e tc u r r e n tr e q u e s td o c u m e n tb e p i f p i sa l r e a d yi nc a c h e u p d a t e d o c u m e n t p sk e y v a l u ek 0 ) e l s e w h i l et h e r ei sn o te n o u g hr o o mi nc a c h ef o r p 利用预测发顶取技术的w e bc a c h e 系统和e x g d s f 算法 b e g i n l e tl 2 m i n ( k ( q j ) ) ，f o ra l l 毋i nc a c h e e v i c t qs u c ht h a tk ( g ) = l e n d l o a d p i n t oc a c h e s e tp sk e yv a l u ek p ) 图2 、4 般的w e b c a c h e 算法 我们可以看到c a c h e 算法进行替换的一般过程，算法将新请求的文档放到 c a c h e 中，如果没有足够的空问，就把权值( k ) 最小的文档替换出来，直到c a c h e 有足够的容量容纳新的文档。 2 3 1 现有的替换算法 在这一节，我们介绍一些替换策略，下一章我们将着重介绍g r e e d y d u a l s i z e 算法和g r e e d y d u a l - s i z e - f r e q u e n c y 算法。 l e a s t - r e c e n t l y u s e d ( l r u ) ：替换掉最近最少访问的文档。这是一个比较 传统的算法，在c p uc a c h e 和虚内存系统中性能是非常好的，但是在w e bc a c h e 领域中工作的并不是很好，因为它只考虑当前的一些请求，并且不考虑文档的大 小。 l e a s t - f r e q u e n t l y - u s e d ( l f u ) ：替换掉访问次数最少的文档。这个算法保 留那些经常访问到的w e b 文档，而将很少访问的文档替换出去。此算法的缺点 是，如果一些文档旦具有很高的访问次数后，即使将来它们永远不会被访问， 它们也不会被替换出去，传统的l f u 算法对这种情况没有任何的控制机制。 s i z e 3 5 ：替换最大的文档。这个算法可以得到很高的命中率( h i t r a t e ) ， 但是字节命中率( b y t e h i tr a t e ) 却很低。 l r u t h r e s h o l d 5 算法和l r u 很相似，只是它不会将一些大于某个阈值 的文档存进c a c h e 中。 l o g ( s i z e ) + l r u 【5 】算法替换l o g ( s i z e ) 值最大的文档，如果s i z e 值相同的话， 将替换最近最少访问的文档。 l t y p e r - g 3 5 算法是l f u 算法的扩展，它考虑了最近访问时间和文档的大 j 、。 利用预测及顶取技术的w e bc a c h e 系统和e x g d s f 算法 l o w e s t l a t e n c y f i r s t 3 4 算法的目标是将平均延迟时间最小化。它跟踪所 有文档的下载时问，并且将最小下载时问的文档替换掉。 h y b r i d 3 4 为每个文档定义了一个计算权值的公式，并且替换掉最低权值 的文档。对任一文档p ，h y b r i d 的公式定义如下： ( c s + w b ，b s ) n p w n z p 其中，c 。是连接到服务器用的时间，b 。是与服务器之间的带宽，n o 是p 取到c a c h e 中后访问的次数，z d 是文档p 的大小( 字节数) ，w b 和w 。是常数。 研究表明，s i z e 算法在命中率( h i tr a t e ) 方面比l f u ，l r u ，l r u t h r e s h o l d ， l o g ( s i z e ) + l r u ，h y p e r - g 和p i t k o w r e c k e r 等算法要优秀 5 ，3 5 1 ，在字节命中率 ( b y t eh i tr a t e ) 方面l r u 要比s i z e 做的好。a r l i t t 等人还发现，基于s i z e 的算 法在命中率方面要出色一些，而基于f r e q u e n c y 的算法可以有效的减少网络拥塞 【4 】。w o o s t e r 的研究结果是，h y b i d 算法在减少网络延迟方面比 l o w e s t l a t e n c y f i r s t 算法要好【3 4 】，但是h y b r i d 算法参数多而复杂，这种策略只 能在理论层面上研究，真正实现比较困难。 1 9 9 7 年，c a o 和i r a n i 提出了一组算法，称之为g r e e d y d u a l s i z e 算法 【1 3 ，从那时开始，不同的扩展g r e e d y d u a l s i z e 算法相继被提出【1 5 ，2 2 】。研究 表明，这一系列算法是目前性能最好的w e bc a c h e 算法【4 ，2 2 】。 2 3 2g i ) 一s i z e 和g d s f 算法 1 9 9 1 年，y o n g 提出了操作系统中使用的g r e e d y - d u a i ( g d ) 算法 3 6 1 ，它 比较适用于内存中的页面，它们具有相同的大小，不同的存取代价。g d 算法为 每一个页面分配一个权值k ，开始时k 被赋值为取到这个页面所花费的代价，当 需要做出替换的时候，具有最小权值( m i n k ) 的页面被替换，并且c a c h e 中所 有页面的权值都要减去m i n k 。如果c a c h e 中的页面p 再次被访问到，其权值k 恢复成它的原始值( 即原来取到此页面的代价值) 。这样，最近访问的页面可以 保持比较大的权值k ，具有更大的可能性保留在c a c h e 中【3 6 】。 1 9 9 7 年，在g d 算法的基础上，c a o 和i r a m i 提出了关于w e bc a c h e 的 g r e e d y d u a l s i z e ( g d s i z e ) 算法 1 3 1 。为了提高g d 算法的效率，g d s i z e 算法保 持了一个膨胀因子l ，并且让页面初始的权值k 偏移l 。这样就避免了替换发生 时，c a c h e 中的所有页面都要进行一次减法。当一个文档p 被用户请求时，g d s i z e 算法计算它的权值k ： k ( p ) = l + c ( p ) s ( p )( 2 3 ) 利用颅测及预取技术的w e bc a c h e 系统和e x - g d s f 算法 在这晕，c ( p ) 是取p 到c a c h e 中所花费的代价，s ( p ) 是文档p 的大小，l 是一个 膨胀因子，开始时为o ，以后被更新为最近替换掉的文档的权值。下面是g d s i z e 算法： i n i t i a l i z el = o p r o c e s se a c h r e q u e s td o c u m e n t i nt u r n ： l e tc u r r e n t r e q u e s t e dd o c u m e n t b ep i f pi sa l r e a d yi nc a c h e k ( p ) = l + c ( p ) s ( p ) e l s e w h i l et h e r ei sn o t e n o u g h r o o mi nc a c h ef o r p b e g i n l e tl = m i n ( k ( q i ) ) ，f o ra l lq ji nc a c h e e v i c t q s u c ht h a tk ( q ) 2 l e n d l o a d p i n t oc a c h e k ( p ) = l + c ( p ) s ( p ) e n d 图2 、5 g d s i z e 算法 根据c o s t 值的不同，g d s i z e 算法的性能也不相同。当每个文档的c o s t 值都设为1 的话，称为g d s i z e ( 1 ) ，与s i z e 算法比较相似，g d s i z e ( 1 ) 算法给比 较大的文档赋予比较小的权值，这样，如果最近没有被再次访问的话，这些文档 很容易被替换出c a c h e 。通常，g d s i z e ( 1 ) 以牺牲字节命中率为代价，换取较高 的命中率。为了在字节命中率和命中率之间达到一种平衡，g d s i z e 算法将代价 值c o s t 设为2 + s ( p ) 5 3 6 ，这是当请求文档不在c a c h e 中时，p r o x y 向w e bs e r v e r 发送和接收数据包总量的估计值。 g d s i z e 算法的缺点是，它不考虑一个文档在过去的访问次数。假设两个 文档具有相同的文件大小，一个经常被访问，另外一个在过去的访问次数很少， 如果它们在几乎相同的时间被访问，它们有相同的l 值，同时也具有相同的权 值，当g d s i z e 算法要从这两个文档之间替换掉一个的时候，它只能随机的替换 其中的一个，而不能做到保留经常访问的，替换掉很少访问的文档。 利用预测及预取技术的w e bc a c h e 系统和e x - g d s f 算法 为了解决这个问题，c h e r k a s o v a 扩展了g d s i z e 算法，将访问次数作为计 算权值的一个参数考虑 1 5 】。这个算法称为g r e e d y d u a l - s i z e f r e q u e n c y ( g d s f ) 算法。文档p 的权值计算公式如下： k ( p ) = l + f ( p ) + c ( p ) s ( p )( 2 4 ) 其中，f ( p ) 是文档p 被访问的次数，当文档p 第一次取到c a c h e 中的时候，f ( p ) 置为1 ，当p 在c a c h e 中被命中的时候，更新f ( p ) = f ( p ) + l 。 与g d s i z e 类似，根据c o s t 值的不同，g d s f 算法也有很大的差别。当 c ( p ) = l 时，g d s f 算法可以达到非常高的命中率，我们称之为g d s f ( 1 ) 。当 c ( p ) = s ( p ) 时，权值的计算公式为： k ( p ) = l + f ( p )( 2 5 ) 文档p 的权值只由膨胀因子l 和访问次数f ( p ) 来确定，g d s f 算法的这个特例可 以获得很高的字节命中率，称为l f u d y n a m i c - a g i n g ( l f u d a ) 算法【2 】。实际上， l f u d a 可以看做是l f u 算法的一个扩展，只是比l f u 多了一个膨胀因子l 。 由于在提高页面命中率和减少网络延迟方面g d s f ( i ) 算法的性能最好 1 3 1 ， 我们试图将其与我们的预取方法相结合，并且在命中率，字节命中率和相对延迟 等性能方面做一下比较。 2 4 预取技术在w e bc a c h e 系统中的应用 ：p i 预挲列已爿预竿理 = ； l 用户高 ；，。“弘一。 ；+ 、汐l ， ，| 弋，7 一e b 服服务器i l g 9 - a ；，b 一i 1 il 絮一一i c a c h e 存储器 l 预测模型i p 1 。p 2 p nil 图2 、6 利用预取技术的w e b c a c h e 系统 利用顶删及颅取技术的w e b c a c h e 系统和e x - g d s f 算法 如前面所述，对于w e bc a c h e 技术和预取技术，以前的研究者都是独立进行 研究，很少有将两者结合的研究工作。在图2 、1 一般w e b c a c h e 系统的基础上， 我们引入了预取技术，提出一个利用预取技术的w e bc a c h e 系统。如上图2 、6 。 上图是我们提出的一个运用预取技术的w e bc a c h e 系统，与一般的w e b c a c h e 系统相比较，增加了预测模型、预测队列、预取代理等部分，并提出了自 己的页面替换算法，对这些内容本文将在以下各章中详细论述。 对上图中的流程，虚线部分是利用预取技术后新增加的，其余部分与图2 、l 中的基本相同，说明如下： 1 、用户向c a c h e 管理器发出对页面p 的请求； 2 、c a c h e 管理器在元数据中查找页面p ，以确定p 是否已经在缓存中。如果 找到，执行3 ；否则，执行4 ； 3 、c a c h e 管理器将页面p 载入到c a c h e 存储器中，执行1 0 5 4 、c a c h e 管理器从远端的w e b 站点请求页面p ，并发出预测请求； a 、w e b 服务器将当前的请求发给预测模型： b 、预测模型根据当前的请求进行预测，将预测信息返回w e b 服务器： 5 、w e b 站点返回页面p ，并将预测信息一并发回； c 、c a c h e 管理器把预测信息添加到预测队列中； 6 、c a c h e 管理器调用页面替换算法a ； 7 、a 收集c a c h e 中w 曲对象的必要信息； i 、替换算法参考预测队列中的信息做出替换决定； 8 、a 做出是否接收p 的决定。如果p 被接收了，并且存储器已没有足够的 空问接纳p ，那么a 将一些对象替换出缓存。 9 、如果p 被拒