（计算机应用技术专业论文）web流量特征模型的研究和应用.pdf

郑州人学坝i 。学位论立 w e b 流鞋特征模型的研究和鹰用 摘要 w e b 缓存技术是提高w e b 性能的一种有效方法。w e b 缓存管理是w e b 缓存技术 的核心问题，研究w e b 访问特征的数学模型是有效进行w e b 缓存管理的基础。通过对 w e b 用户的行为跟踪，对w e b 对象访问特征的深入研究分析，发现w e b 对象访问具有 以下几个共同特征：( 1 ) w e b 对象流行度符合z i p f 定律；( 2 ) w e b 对象大小服从重尾分 布；( 3 ) w e b 对象访问具有局部性特征等。 访问局部性特征对缓存和预取系统的性能和设计方面有很大的影响。网络访问的 局部性特征包括时问局部性和空问局部性，利用数学建模方法研究局部性特征对于缓 存和预取系统的设计及性能提高具有重要的作用。通过分析和讨论，本文利用信息熵 和变异系数建立了网络流量局部性特征新的度量方法，信息熵比z i p f 定律更能反映访 问流的时间局部性，变异系数则解决了访问流的相同文档问的空间局部性建模问题。 实验和分析表明这些参数能较好地描述网络访问流的局部性特征，而且易于使用。 w e b 日志生成模拟器可以按用户指定的w e b 访问特征生成模拟日志，为研究w e b 缓存系统性能提供了理论基础。本文通过分析w e b 对象访问特征，采用数学模拟方法 分别模拟了w e b 对象流行度特征、w e b 对象大小重尾分布特征以及w e b 访问的时间 局部性特征，设计并实现了一个w e b 流量特征模拟生成器w e b s i m g e n ，并通过实验 验证了这个模拟器的有效性。基于两层代理缓存结构，利用模拟生成的日志，用a d f 模型( a g g r e g a t i o n 、d i s a g g r e g a t i o n 和f i l t e r i n g ) 对模拟w e b 流量的访问特征和性能进 行测试，实验结果表明模拟日志具有和真实日志类似的特性。本文还利用w e b s i m g e n 模拟器生成的访问r 志以及真实的访问日志对常用的w e b 缓存替换算法( l r u ，l f u ， g d s f ) 进行了细致的性能评估，通过实验进一步证明：在两层代理缓存结构中，当低 一级缓存用l r u 或l f u 替换算法时，高一级的缓存用g d s f 替换算法能达到比较高 的命中率。由于该流量模拟器具有较大的灵活性，其为进一步提高w e b 缓存性能和预 取技术的研究提供了重要依据。 关键字：w e b 缓存，齐普夫定律，w e b 访问特征，时间局部性，空间局部性，w e b 预 取，模拟器 第1 页 郑州人学硕i 。学位论文 w e b 流董特缸f 模犁的研究和应用 a b s t r a c t w 曲c a c h i n gt e c h n o l o g yi sa l le f f e c t i v ea p p r o a c ht oi m p r o v i n gw e bp e r f o r m a n c e t h e m a n a g e m e n to fw e bc a c h i n gi st h ek e yi s s u eo fw e bc a c h i n gt e c h n o l o g y , a n dt h es t u d yo f m a t h e m a t i c a lm o d e lo fw 曲r e f e r e n c ec h a r a c t e r i s t i c si st h eb a s i so fe f f e c t i v em a n a g e m e n t o fw e bc a c h i n g b yt h es t u d yo ft h er e f e r e n c eb e h a v i o ro fw e bu s e r sa n dt h er e f e r e n c e c h a r a c t e r i s t i c so fw 曲o b j e c tp r o f o u n d l y , s o m ec o m m o nc h a r a c t e r i s t i c si d e n t i f i e di np r o x y w o r k l o a d sc a nb ef o u n d ：( 1 ) t h ew e bo b j e c tp o p u l a r i t yo f t e nf o l l o w sz i p f sl a w ；( 2 ) t h ef i l e s i z ed i s t r i b u t i o nf o rw e bd o c u m e n t sf o l l o w sh e a v y - t a i l e d ；( 3 ) r e f e r e n c e l o c a l i t y c h a r a c t e r i s t i c se x i s t si nt h ew e b p r o x yr e f e r e n c es t r e a m l o c a l i t yc h a r a c t e r i s t i c so fw e br e f e r e n c es t r e a m sh a v eg r e a ti m p a c to np e r f o r m a n c 七 a n dd e s i g no fc a c h i n ga n dp r e f e t c h i n gs y s t e m al o c a l i t yc h a r a c t e r i s t i co fw 曲r e f e r e n c e s t r e a m si n c l u d e st h et e m p o r a ll o c a l i t ya n dt h es p a t i a ll o c a l i t y u s i n gm a t h e m a t i c a lm o d e l m e t h o dt os t u d yt h el o e a l i t yp r i n c i p l ep l a y sa ni m p o r t a n tr o l eo nt h ed e s i g na n dp e r f o r m a n c e i m p r o v i n go fc a c h i n ga n dp r e f c t c h i n gs y s t e m t h r o u g ha n a l y z i n ga n dd i s c u s s i o n ，an e w m e t h o dt om o d e lw e bw o r k l o a dl o c a l i t yc h a r a c t e r i s t i c si se s t a b l i s h e db a s e do nt h es t u d yo f e n t r o p ya n dc o e f f i c i e n to fv a r i a t i o n e n t r o p yc a nr e f l e c tt h et e m p o r a ll o c a l i t yb e t t e rt h a n z i p f sl a w , a n dt h ec o e f f i c i e n to f v a r i a t i o nc a nb eu s e dt os o l v et h ep r o b l e mo f m o d e l i n go f s p a t i a ll o c a l i t yb e t w e e nt h es a l l l ef i l e s e x p e r i m e n t sa n dd i s c u s s i o n ss h o wt h a tt h e s em e t r i c s c a nd e p i c tl o c a l i t yc h a r a c t e r i s t i c sm o r ep r o p e r l ya n da r em u c he a s i e rt ou s e 1 1 1 ew e b p r o x yw o r k l o a dg e n e r a t o rc a ng e n e r a t es y n t h e t i cw o r k l o a di nt e r m so fw e b r e f e r e n c ec h a r a c t e r i s t i c sa p p o i n t e db yt i g e r s ，w h i c hp r o v i d e st h et h e o r e t i c a lb a s i so n s t u d y i n gw e bc a c h es y s t e m s as y n t h e t i cw e bw o r k l o a dg e n e r a t o r ( w e b s i m g e n ) i s d e s i g n e d ，i m p l e m e n t e da n dv a l i d a t e di nt e r m so f m a t h e m a t i cm o d e le s t a b l i s h e db yt h ew e b c h a r a c t e r i s t i c si nt h i sp a p e r b a s e do nat w o l e v e lc a c h i n gp r o x ys t r u c t u r ea n dt h es y n t h e t i c w e bw o r k l o a dt r a c e s ，t h es i m u l a t e de x p e r i m e n t sm a k eu s eo fa d f ( a g g r e g a t i o n 、 d i s a g g r e g a t i o n a n d f i l t e r i n g ) m o d e l t oe v a l u a t et h er e f e r e n c ec h a r a c t e r i s t i c sa n d p a - f o r m a n c eo fs y n t h e t i cw e bw o r k l o a d n ee x p e r i m e n t a lr e s u l t sh a v es h o w nt h a tt h e s y n t h e t i ct r a c e sh a v et h es i m i l a rp e r f o r m a n c ec h a r a c t e r i s t i c sw i t ht h er e a lm l e s w 曲c a c h e r e p l a c e m e n ta l g o r i t h m s ( l r u ，l f u ，g d s f ) a r ea l s oe v a l u a t e dc a r e f u l l yu s i n gs y n t h e t i c w o r k l o a dg e n e r a t e db yw e b s i m g e na n dr e a lw o r k l o a d t h ee x p e r i m e n ts h o w st h a ti nt h e t w o - l e v e lc a c h i n gh i e r a r c h yi ft h el o w e rl e v e lp r o x i e su s et h el r uo rt h el f up o l i c y , t h e g d s fp o l i c yi st h eb e s tp o l i c ya tt h eu p p e rl e v e l t h eg e n e r a t o rh a sg r e a tf l e x i b i l i t y , w h i c h c a np r o v i d ea ni m p o r t a n tb a s i sf o rf u r t h e ri m p r o v i n gw e bc a c h i n gp e r f o r m a n c ea n dt h e s t u d yo f p r e f e t c h i n gt e c h n o l o g y 第1 l 页 郑州人学帧i 学位论文 w e b 流量特征模型的研究和麻用 k e y w o r d ：w e bc a c h i n g ；z i p f sl a w ；w e br e f e r e n c ec h a r a c t e r i s t i c s ；t e m p o r a li o c a l i t y ； s p a t i a ll o c a l i t y ；w e bp r e f e t c h i n g ；s i m u l a t o r 第1 i l 页 郑州人学顾卜位论文 w e b 流量特秆模型的研究和j 通用 图表目录 图2 一l 缓存体系结构图7 图2 2w e b 系统模型8 表4 一l 实验使用的同志数据2 4 图4 - 1 访问距离( i a d ) 的累积概率分布2 5 图4 2 熵值关系图2 5 图4 3 变异系数关系图2 6 图5 - 1 两层结构的代理服务器模拟模型2 8 图5 2a d f 模型2 8 图5 3w e b 负载生成过程3 0 图5 - 4 流行度与排名的关系图3 3 图5 5 文档大小的l l c d 图3 3 图5 - 6 低级缓存的命中率3 4 表5 - 1 低级缓存的命中率3 4 图5 7 高级缓存的命中率3 5 表5 2 高级缓存的命中率( 模拟日志)3 5 表5 3 高级缓存的命中率( 真实日志) 3 5 图5 - 8 两层代理缓存结构的性能( 真实只志)3 8 图5 - 9 两层代理缓存结构的性能( 模拟日志)3 9 第v i 页 郑州人学琐i 学位论文 w e b 流罐针”模掣的研究和腑用 第一章绪论 1 1互联网所面临的问题及解决方案 w w w 自1 9 9 1 年诞生以来，由于其多媒体信息的传输和良好的交互性而倍受青睐， 从而成为i n t e r n e t 上发展最快、最广泛、最实用的分布式多媒体网络信息系统。随着 w w w 技术的飞速发展，人们己越来越依赖网络获取信息。i n t e r - n e t 已经成为一个全 球的、分布式的、动态的信息仓库，大量的信息访问也突出了i n t e r n e t 目前存在的问 题：由于网络用户爆炸式增长造成网络流量激增，在有限的带宽条件下，人们在获取网 络信息时不得不忍受严重的时间延时和更多的通信费用。这愈来愈成为网络使用的瓶 颈。 从i n t e r n e t 整体发展情况看，虽然i n t e r n e t 的网络基础设施有了很大发展，但网 络设施的发展远跟不上网络应用和网络用户的快速增长，这就使得网络流量不断增 大，网络负载只趋严重，相伴而来的是w e b 访问延迟的急剧增加。因此，如何缩减w e b 访问延迟、改善w w w 服务质量已经成为改善i n t e r n e t 应用环境的主要目标。 w e b 流量是所有i n t e m e t 流量中最主要的成分，因此，解决w e b f j i 务所面临的问题是 解决i n t e r n e t j j 艮务所面临问题的关键。如何缩减w e b 访问延迟、改善w w w , 9 1 i 务质量已经 成为改善i n t e r n e t 应用环境的主要目标。 通常所说的w e b 访问延迟包括：连接延迟、请求延迟和网络延迟。连接延迟是指建 立一个连接所花费的时问。请求延迟是指在建立连接后，完成数据传输所花费的时间。 网络延迟是指由带宽和电信号传输的物理限制所决定的传输时间。 虽然引起w e b 浏览速度缓慢的因素很多，但其中主要的因素有： ( 1 ) w e b 服务器吞吐能力不足所引起的服务时间的延长，显然在超负荷运转或磁 盘速度比较慢时w e b 浏览要花更多的时间； ( 2 ) 网络带宽不足所引起的传输时间的延长； ( 3 ) 不完善网络协议引起传输时间的延长，例如h t t p1 o 协议要求对于一个h t m l 文档中的每个传输对象都要单独建立一个连接，这不可避免会引起一些不必要的开销。 网络传输时间延迟包括网络线路传输延迟和中问路由器路由处理延迟。网络传输 延迟可从两方面来减少：一方面增加网络带宽、提高中间路由器性能，即提高网络传 输速度和减少信息路由排队时间；另一方面就是通过减少进入网络的信息量来降低对 网络带宽的占有。后者主要可通过缓存、预取来实现。 解决网络延迟、提高服务质量的办法主要有两种1 “5 1 【6 1 【刀：一是从网络的物理性能 上提升：强化w e b 服务器的处理能力、增加网络带宽、提高客户机性能、在网络容易发 生拥堵的节点设置镜像服务器、采用w e b 服务器集群技术等。然而，网络基础设施建设 第l 页 郑州人学坝i 学位论文w e b 流釜特甜摸掣的研究和府用 需要大量的投资而且建设周期长，而且用户的需求也会随着网络物理性能的提高而上 升到一个新的台阶，仅靠这种方式是不够的。二是从网络相对性能上考虑，设法提高 现有系统的利用率，主要包括：缓存技术( c a c h i n g ) 、c d n 技术( c o n t e n td e l i v e r y n e t w o r k ) 、改进网络协议( p r o t o c 0 1 ) 、顸取技术( p r e f e t c h i n g ) 等。由于c d n 是缓 存技术的发展，在同样的网络协议下，以上技术手段可以归结为两种：即缓存技术和 预取技术。 w e b 缓存是一个提高w e b 性能非常有效的方法，w e b 缓存的基本思想是以存储空日j 换 取i n t e r n e t 带宽，其意义在于w e b 缓存可以有效地减少网络通信量、减轻服务器的负载 和降低用户等待时间。它可以位于网络的不同位置：客户机端，代理服务器端，服务 器端，在客户机端，浏览器软件充分利用系统内存和磁盘空问缓存最近访问过的文档 副本以满足随后对同样文档的访问；在服务器端，把最近常被访问的文档缓存在内存 中，当其它用户对这些文档访问时可直接在内存中进行，省去了对磁盘的访问时问； 代理服务器位于网络中，可以有多个层次代理，它接受用户的访问请求，在检查自己 没有此文档副本后去w e b l 务器取来相应文档传给客户，同时缓存此文档的副本以满足 将来其它用户的访问。 预取技术是对缓存技术的补充，也可以称为主动缓存技术，是当用户正在处理刚 刚响应的w e b 对象期间试图获取将要访问的w e b 对象的过程。w e b 预取技术的前提是用户 访问的空间局部性原理，其基本思想是：根据用户当前的访问请求和历史访问记录， 预测用户将来可能发出的访问请求，在用户浏览当前w e b 页面时将预测的内容预先取到 本地高速缓存中，这样用户在真正要访问这些页面时只需从本地高速缓存下载，对用 户来说，屏蔽了w e b 对象在服务器端的处理时间和在网络上传输的延迟时间，从而在很 大程度上达到减小用户访问延迟的效果。w e b 预取的实质是由时间局部性向空间局部性 的扩展。 代理服务器缓存可以很大程度上减少客户机端与服务器端的通信请求，同时可以 缓解w e b , 1 l l 务器的负载，这样可以减少网络上重复信息的传送，用户的访问延迟也可以 相应降低。w e b 缓存替换策略是w e b 缓存管理的核心部分，它是w e b 缓存高效率工作的基 础。客户机、代理服务器以及服务器中的缓存空间都是有限的，当缓存空间被占满时， 当新的w e b 文档到来时，系统必须决定把哪些历史文档剔除出去，以腾出足够空间缓存 新的w e b 文档。代理缓存的替换策略是根据某个标准去替换缓存副本的，这个标准的好 坏是非常重要的。替换策略的工作过程可分为两个阶段：首先，按照某个标准对缓存副 本进行排序；其次，从排好序的列表头换出一个或多个缓存副本，直到满足某个规则 为止，而这个规则通常是缓存有足够的剩余空间来容纳要换入的网页副本。 第2 页 郑州人学颂卜位论文w e b 流量特行模掣的研究和一用 1 2 课题的研究背景 w e b 缓存可以大大提高w e b 系统的性能，但同时也提出许多问题，w e b 缓存在应用 中最大的问题就是w e b 缓存管理。研究w e b 访问特征是有效进行w e b 缓存管理的基础， 对w e b 网站的规划设计也具有非常积极的作用。 网络访问流在研究中有许多值得做的工作，尤其是网络对象的请求序列。在对w e b 缓存的研究中，一些研究者发现不同的w e b 页面访问特征对w e b 缓存替换策略有一定 的影响。但究竟这种影响有多大却不是很好回答，例如，为了研究个特定的w e b 访 问特征( 例：流行度特征) 如何影响不同的替换算法，我们需要仅在这个特定w e b 访 问特征( 流行度特征) 上变化的w e b 历史访问日志，很显然，这种历史日志我们无法 得到，而且也不存在。 研究w e b 访问特征的数学模型是进行有效w e b 缓存管理的基础。w e b 同志生成模 拟器对于研究w e b 缓存系统有很大地帮助，目前有两种方法模拟生成w e b 访问同志2 1 1 4 l ： 1 日志驱动方法，这种方法利用对历史同志进行变换来模拟生成新的日志，它易 于实现但灵活性差，因为生成的r 志依赖于已有的历史日志。这种模拟器有 s p e c w e b 9 9 ，w e b b e n c h ，s u r g e 等。 2 数学模拟方法，这种方法在充分研究w e b 对象访问特征的基础上，通过建立 数学模型来模拟生成w e b 日志，它通过设定一个或多个参数来生成特定的w e b 日志， 这种方法可在短时间内生成多个用户所需的r 志。它灵活性大，但实现复杂，具有难 度。 本文在模拟同志时采用的是第二种方法，即数学模拟的方法，因为它克服了日志 驱动方法的缺点，而且实现起来也更加的灵活，更容易满足实际需要。 1 3 研究内容和论文组织 如何缩减w e b 访问延迟是w e b 研究中的一个重要方面。w e b 访问延迟依赖诸多因素如 网络带宽、发送延迟、传播延迟等。目前解决该问题的主要方案是缓存技术和预取技 术。利用数学建模方法研究访闯特征对于缓存和预取系统的设计及性能提高具有重要 的作用。 本论文的主要工作和创新点： 1 利用信息熵和变异系数建立了网络流量局部性特征新的度量方法，利用信息熵为访 问流的时问局部性特征建模，利用变异系数为访问流的相同文档间的空间局部性特征 建模，实验表明这些参数能较好地描述网络访问流的局部性特征。 2 通过分析各个w e b 对象访问特征，设计并实现了一个w e b 同志模拟生成器 w e b s i m g e n 。通过使用w e b s i m g e n 模拟器生成的只志，基于两层代理缓存结构和a d f 第3 页 郑州人学硕l 学位论文w e b 流罐特舒模掣的研究和腑用 模型( a g g r e g a t i o n 、d i s a g g r e g a t i o n 和f i l t e r i n g ) 对模拟w e b 流量的访问特征和性能进 行测试，结果表明模拟器能较好地生成模拟日志，为进一步研究w e b 缓存技术和预取 技术提供了依据。 本论文内容安排如下： 第一章，绪论，主要介绍互联网概述、互联网所面临的问题及解决方案和课 题的研究背景以及论文的主要内容。 第二章，w e b 缓存技术背景，首先介绍w e b 缓存的基本概念，以及缓存的系统 结构和分类，然后讨论了缓存替换算法及其各自的特点，最后介绍了缓存工作原 理的数学模型。 第三章，w e b 访问特征，主要介绍了当前发现的w e b 流量的一些主要特征，并 对每个模型用一个数学模型来描述它，这一章是后面工作的基础，模拟器是主要 基于这些访问特征来模拟网络访问流量的。 第四章，w e b 访问流的局部性特征建模，提出了对w e b 访问局部性特征建模的新 的数学模型。通过分析和讨论，利用信息熵和变异系数建立了网络流量局部性特征新 的度量方法，用信息熵来为访问流的时间局部性特征建模，用变异系数为访问流的空 问局部性特征建模。信息熵比z i p f 定律更能反映访问流的时日j 局部性，变异系数解决 了访问流的相同文档问的空间局部性建模问题。 第五章，w e b s i m g e n 模型研究和应用，是本文的核心。首先通过分析w e b 对象 访问特征，采用数学模拟方法分别模拟了w e b 对象流行度特征、w e b 对象大小重尾分 布特征、w e b 访问的时问局部性特征，设计并实现了一个w e b 日志模拟生成器 w e b s i m g e n ，并通过实验验证了这个模拟器的有效性。这种模拟器不仅可以模拟生成 w e b 对象访问日志，而且具有很大地灵活性，克服了使用w e b 对象历史日志的许多缺 点，为进一步研究w e b 缓存技术和预取技术提供了依据。利用模拟生成的只志和a d f 模型( a g g r e g a t i o n 、d i s a g g r e g a t i o n 和f i l t e r i n g ) 对模拟w e b 流量的访问特征和性 能进行测试，实验结果表明模拟同志具有和真实日志类似的特性。为了评估多层缓存 结构的性能，利用两层的代理缓存结构，详细地对各种不同替换算法的结合性能进行 测试，试验得出g d s f 替换算法的性能相对比较高，而且验证了可以利用不同的算法结 合来提高多层缓存结构的性能。 第六章，结论与展望，对本文的工作进行了总结，并指出今后需要进一步研究 的问题和方向。 第4 页 郑州人学硕i 。学位论文w e b 流量特玎模掣的研究和府用 第二章w e b 缓存技术背景 w c b 缓存是处于用户和w 曲服务器之间的信息缓冲机制，该技术的基本思想是： 把经常访问的信息( w e b 文档) 存放到用户的附近( 或本地) ，以便后续的访问能够 从客户机或本地服务器获得该信息，而不必访问远地w c b 服务器。w c b 缓存通过信息 的本地化来减少网络流量和加快浏览速度，它可以从两方面改善用户感觉到的网络性 能：一方面，当从本地为用户提供服务时，缓存屏蔽了广域网延迟和服务器的处理时 间，加快了响应的速度；另一方面，缓存还可以屏蔽广域网节点的暂时不可用性，从 而使网络显得更加稳定。 2 1w e b 缓存 w 曲缓存是一个提高w e b 性能非常有效的方法，研究表明w e b 缓存命中率可以达 到3 0 - - 5 0 5 】【lo 】。它可以位于网络的不同位置：客户端，代理服务器端，服务器端。 w e b 缓存是利用w e b 页面访问的局部性特征，在性能比较高的系统中保存一些从w e b s e v e r 取来的w 曲资源，当用户再次访问的时候，可以快速的获取，它可以在一定程 度上节省网络宽带、减轻服务器负载、减少网络延迟。 2 1 1 代理服务器的类型 代理服务器提供的缓存服务还可以联结在一起，构成层次性缓存模型，在 i n t e r n e t 缓存协议( i c p ，i n t e r n e tc a c h ep r o t o c 0 1 ) 中详细描述了代理服务器模型 的规范。它又分为三种类型： ( 1 ) 转发代理( f o r w a r dp r o x y ) 用户浏览器将请求直接发送给转发代理服务器，转发代理服务器从域名服务器 ( d n s ) 获得原始服务器的i p 地址，并从原始服务器获得w e b 对象，转发代理服务器存储 获得的对象，并将拷贝返送给用户浏览器。对于此后相同的用户请求，转发代理服务器 直接将存储的对象发送给用户。转发代理的优点是允许用户自己决定是否使用代理服 务。缺点是每一个用户的浏览器都需要进行代理配置，对于企业用户来说这会增加管理 工作，而对i s p 用户来说，这可能是一件很难完成的工作。 ( 2 ) 透明代理( t r a n s p a r e n tp r o x y ) 透明代理由路由器或交换机等网络设备截获用户的w e b 访问请求，检测到t c p 端口 号为8 0 ( h t t p 的t c p 端口号为8 0 ，该端口为缺省监测对象，也可以设置监测其它需要的 端口) 时便重定向至c a c h e 服务器。从网络配置的角度来看，透明代理比转发代理复杂， 因为透明代理包含网络路由的设置或增添额外的设备，但是透明代理无需对用户端进 行配置，这对企业用户和i s p 而言，不仅大大简化了网管工作，而且方便实现i n t e r n e t 第5 页 郑州人学颂i 坞位论文 w e b 流量特行模型的研究和麻用 提速，缓解主干压力。 ( 3 ) 反向代理( r e v e r s ep r o x y ) 反向代理是种原始服务器端的加速方法。它作为代理c a c h e ，不针对浏览器用户 而针对一台或多台特定w e b 服务器。实施反向代理，只要将i n t e r n e tc a c h e 设备放置 在一台或多台w e b 服务器前端即可。通过i ) n s 服务器解析后的l p 地址是i n t e r n e t c a c h e 的i p 地址，而非原始w e b 服务器的i p 地址，用户浏览器的访问请求直接发送到 i n t e r n e tc a c h e 设备，只有无法缓存的请求才被i n t e r n e tc a c h e 设备转发给原始服务 器处理。因此，反向代理可以大大缓解原始服务器的负载。在以上三种基本工作方式中， 前两种用于加速浏览器，第三种用于加速源w e b 服务器。 2 1 2 常见的w e b 缓存体系结构 一个缓存系统的性能取决于其客户群的大小，客户群越大，缓存的内容被再次请 求的可能性就越高。相互合作的c a c h e 组可能会提高命中率而提高缓存系统的性能，因 此缓存系统的体系结构应确保代理问能够有效地进行合作。典型的缓存体系结构有以 下几种：层次式、分布式和混合式。 ( 1 ) 层次式缓存体系结构 h a r v e s t 3 0 i 1 3 1 1 项目首先提出了层次式w e b 缓存体系结构。在层次式缓存体系结构 中，c a c h e 在网络呈多级配置，如图2 1 的( a ) 所示。为简单起见，假定有四级：底层c a c h e 、 局域层c a c h e 、区域层c a c h e 、广域层c a c h e 。底层是客户浏览器c a c h e ，当客户端c a c h e 不能满足客户的请求时，该请求被转发到局域层c a c h e ，如果仍然得不到满足，则该请 求被转发到区域层c a c h e 直至广域层c a c h e 。如果该请求在各级c a c h e 中都得不到满足， 则请求最终被转发到服务器。然后服务器对该请求的响应自项向下地发送给客户，在 沿途的每一个中间层c a c h e 中留下一个副本。请求相同内容的其它请求则自下而上地进 行转发，直到在某一级c a c h e 中得到满足。 层次式缓存体系结构带宽效率高，点击率较高的w e b f 勾容可以快速高效地分布到网 络中。但该体系结构也存在一些不足【3 ”： ( 1 ) 建立层次式缓存体系结构，缓存服务器必须配置在网络中关键的访问点 上，缓存服务器间需相互合作； ( 2 ) 每一级c a c h e 都会带来额外的延迟； ( 3 ) 高层c a c h e 可能会成为瓶颈并带来较长的排队延迟； ( 4 ) 同一个内容的多个副本被保存在不同的c a c h e 中，整个系统c a c h e 空间利用率不高。 ( 2 ) 分布式缓存体系结构 针对层次式缓存结构的上述缺陷，一些研究者提出了分布式缓存体系结构，在这 种结构中，只有低层c a c h e ，如图2 1 的( b ) 所示。分布式w e b 缓存结构中，没有超出局 域层的中f 自j c a c h e 层，c a c h e 之问相互协作以处理失效。为了确定将客户请求转发给哪 第6 页 郑州人学硕卜学位论文w e b 流董特征模型的研究和麻用 一个局域层c a c h e 来获取失效的内容，每一个局域层c a c h e 保留一份其它局域层c a c h e 中缓存内容的目录信息，以便发生失效时将客户请求准确地转发到相应的局域层c a c h e 缓存阵列路由协议c a r p t 3 0 3 ( c a c h ea r r a yr o u t i n gp r o t o c 0 1 ) 是一种分布式缓存方案， 它将u r l 空间分割成不同的部分，将每一部分指定给一组松散耦合的c a c h e 组，每个 c a c h e 只能缓存具有指定给它的u r l 的w e b 内容，从而可以根据客户请求内容的u r l 来确 定将请求转发给哪一个c a c h e 在分布式缓存结构中，大多数的网络流量都发生在网络底层，不容易产生网络拥 塞，c a c h e 空间利用率高，且可以更好地实现负载共享，容错性更好。然而，一个大规 模的分布式缓存系统的配置可能会遇到几个问题：连接次数较多、带宽要求高、管理困 难【3 l 】。 ( 3 ) 混合式缓存体系结构 混合式体系结构如图2 1 的( c ) 所示，同级c a c h e 采用分布式缓存结构，相互合作。 h a r v e s t 集团设计的互联网缓存协议i c p ( t h ei n t e r n e tc a c h ep r o t o c 0 1 ) 支持从r t t 最小的父c a c h e 或邻居c a c h e 中获取相应的内容。 ( a ) 层次模型( b ) 分布式模型( e ) 混合式模型 小圆指的是客户端，带阴影的椭圆指的是代理缓存( p r o x yc a c h e ) ，直线指的是缓存闻 交流路径( c a c h ec o m m u n i c a t i o np a t h ) ，图2 1 缓存体系结构图 w e b 缓存系统的核心部分通常包括以下几部分： 缓存管理器：整个系统的控制中心，协调处理其他各部件的操作。 元数据：存储了缓存对象的一些索引信息，便于快速访问。它通常还保存一些 附加的信息，例如，一个对象的最近访问时问，访问频率等。 页面替换算法：是缓存系统的核心，它用来决定是否将一个新来的w e b 页面放 进缓存，如果存储空间已满，它用来决定将哪个页面替换出缓存为新来的w e b 页面让 出空间。 c a c h e 存储器：用来保存w e b 页面的物理存储空间。 缓存系统在用户和w e b 服务器之间，与两者进行交互。图2 - 2 是一般的w e b 缓存 第7 页 郑州人学坝l 壕位论文w e b 流量特秆模型的研究和心用 系统的模型和工作过程。 ( 1 ) 用户向缓存管理器发出页面p 的请求； ( 2 ) 缓存管理器在元数据中查找页面p ，以确定p 是否已经在缓存中。如果找到， 执行( 3 ) ；否则，执行( 4 ) ； ( 3 ) 缓存管理器将页面p 载入到c a c h e 存储器中，执行( 1 0 ) ； ( 4 ) 缓存管理器从远端的w e b 站点请求页面p ； ( 5 ) 远端站点返回页面p ： ( 6 ) 缓存管理器调用页面替换算法a ； ( 7 ) a 收集缓存中w e b 对象的必要信息； ( 8 ) a 做出是否接收p 的决定，如果p 被接收了，并且存储器已没有足够的空间存 放p ，那么a 将一些对象替换出缓存； ( 9 ) 如果p 被拒绝了，执行( 1 0 ) ；否则，缓存管理器将p 存入c a c h e 存储器中； ( 1 0 ) 缓存管理器更新元数据信息，使之与新的c a c h e 状态同步； ( 1 1 ) 缓存管理器将页面p 返回给用户。 2 2 缓存替换策略 图2 2w e b 系统模型 由于缓存的存储容量是有限的，当其存储区被占满后，新的文档就无法存储，这 时需要按某种策略将某些文档替换出去，替换策略的好坏决定了缓存的文档命中率 ( h i t r i t i o ) 、文档字节命中率( b y t eh i t r a t i o ) 等指标，从而在很大程度上决定缓存 系统的性能。w 曲缓存替换策略方面已有大量的研究嘲捌，w 西缓存替换策略分成以 下四种类型： ( 1 ) 基于访问次数的替换策略 l f u ( l e a s tf r e q u e n t l yu s e d ) ：替换访问次数最少的文档。这个算法保留那些经 第8 页 郑州人学硕1 学位论文w e b 流量特缸模型的研究和麻用 常访l u j 的w c b 文档，将缓存空白j 中被访问次数最少的网页副本换出。算法的本质是采 用文档的流行度作为替换的依据。l f u 的优点是实现简单，只需对每个缓存副本维持 一个计数器。缺点是没有考虑网页的年龄、大小和获取网页的访问延迟。改进的算法 有l f u a g i n g ，将网页副本的年龄作为算法的辅助因素，避免了缓存“污染”。 ( 2 ) 基于访问时间问隔的替换策略 l r u ( l e a s t r e c e n t l yu s e d ) ：替换最近最少访问的文档。当引用序列表现出明显 的时间局部性时该算法会有出色的表现。在c p uc a c h e 和虚拟内存系统中性能比较突 出，但在w e bc a c h e 领域中工作表现一般。l r u 算法利用访问请求的时间局部性。l r u 算法实现简单，在h a r v e s t 和s q u i d 等代理缓存系统中都得到了应用。和l f u 算法类似， l r u 的缺点是没有考虑网页的大小和获取网页的延迟。如果某个将要被换入的网页副 本很大，就有可能需要将多个小缓存副本换出，这样会严重影响命中率。因此派生出 很多基于l r u 改进的替换算法，如l r u t h r e s h o l d 。 ( 3 ) 基于网页大小的替换策略 s i z e 算法的思想是替换最大的文档。当缓存剩余空间不够容纳一个需要调入的对 象时，缓存中最大的文档将被替换出缓存，以便容纳更多的小文件。其优点是：因为 换出的空间相对大，随后可以容纳很多小网页副本，所以可能会产生较高的命中率。 然而字节命中率可能偏低，而且再次下载大网页时，会占用较多的网络资源。 g d s i z e 算法为避免s i z e 的缺点，达到提高命中率和降低网络开销的目的，引进膨 胀因子，g d s i z e 算法计算权值k 的方法是：k ( d ) = l + c ( d ) s ( d ) 。其中，c ( d ) 表示取d 到 c a c h e 所花费的代价，s ( d ) 是文档的大小，l 是一个膨胀因子，开始时为0 ，以后被更 新为最近替换掉的文档的权值。主要不足在于，它不考虑一个文档在过去的访问次数。 当两个对象的l 和k 相同时，要随机选择替换对象从而可能造成不合理。 ( 4 ) 基于目标函数模型的替换策略 通常都使用多个性能参数形成目标函数，或对访问历史进行分析，并预测将来的 访问趋势。优点是考虑的因素相对比较全面，换出的缓存副本从理论上性能较好。但 由于计算方面受访问历史的限制，也受计算时问的限制，不可能完全准确，不一定得 到最好的性能，另外还可能增加一些访问延迟。 h y b r i d 算法目的在于降低网络总延迟。该算法设计了一个函数用来计算每个文档 的保留价值。当计算完所有文档的函数值后，价值最小的文档将被替换出缓存。 g d s f ( g r e e d yd u a ls i z ef r e q u e n c y ) 改进了g d s i z e 算法的不足，文档的权值计算 公式为：k ( d ) = l + f ( d ) + c ( d ) s ( d ) ，其中，f ( d ) 是文档撤访问的次数。 目前的w 曲缓存替换各有自己的特点。如l r u 、l f u 、s i z e 等实现简单，但在提 高页面命中率和减少网络延迟方面性能不是很好，而h v b r i d 算法，虽然在减少网络延 迟方面性能较好，但算法较为复杂，实现起来较为困难。已有的研究表明，w e b 的替 第9 页 郑州人学坝l 学位论文w e b 流量特矸模型的研究和应用 换算法中，g d s f 算法目前具有比较高的性能。 在本文讨论的缓存与预取模型中，将使用以上所介绍的四种典型的替换策略： l r u 、l f u 、g d s f 。 2 3 衡量缓存替换算法性能的主要指标 2 3 1 缓存文档命中率 当用户通过缓存访问w e b 时，缓存通过自己的缓存或直接访问w e bs e r v e r 来提供 用户所要访问的文档，如果缓存通过