（计算机应用技术专业论文）web对象可缓存性与一致性问题研究.pdf

原创性声明 i i i i r ll iill1 1 1 lrrri l l lr l lliif y 18 3 3 4 15 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 己在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者： 器三走 日期：7 。o 年3 - 月工6e l 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者： 暴寿 日期：w u 年3 - 月6 同 摘要 摘要 w e b 缓存技术是w e b 加速技术的关键。该技术的运用需要解决两个问题： 一是判断w e b 对象是否可缓存，尽量避免缓存污染，预测缓存该对象的效率； 二是保证缓存对象与源服务器对象一致，在源对象更新后缓存对象采用相应的一 致性算法进行更新，衡量更新的效率。 为了解决w e b 对象是否可缓存的问题，根据影响对象可缓存性的几个因素， 提出了基于请求方式、哪状态码及h 1 曙参数的w 曲对象可缓存性评价模型， 分析讨论了w e b 对象可缓存性评价指标。利用w e b 对象可缓存度及可缓存率的 概念，研究w e b 对象的可缓存性；采用缓存加速比指标，度量w e b 缓存效率。 为了解决如何衡量一致性算法效率的问题，提出了w e b 缓存一致性模型， 模型由用户请求模型与对象更新模型组成，根据模型的有效命中率和缓存命中率 来衡量一致性算法的效率。实验表明：有效命中占缓存命中的比率越高，一致性 算法效率越高，用户请求得到有效对象的几率越大，网络资源能得到更加合理的 利用。 关键词：w e b 缓存可缓存性评价模型缓存加速比一致性模型 a b s t r a c t w e bc a c h i n gi so n eo ft h ek e yi s s u e so fw e ba c c e l e r a t i o nt e c h n o l o g y t h e r ea r c t w op r o b l e m ss h o u l dt ob er e s o l v e db e f o r ew e bc a c h i n gc a nb ep u ti n t op r a c t i c e f i r s t l y , w es h o u l dd e t e r m i n e w h e t h e rt h ew e bo b j e c t sc a nb ec a c h e da n dt h ee f f i c i e n c y o fc a c h i n gt h eo b j e c t s s e c o n d l y , w i t ht h ed y n a m i cc o n t e n ta n dp e r s o n a ls e r v i c e si n t h ew e bs e r v i c eg r o w i n g ，c a c h ec o n s i s t e n c ya s s u r a n c eb e c o m e sm o r ec h a l l e n g i n g 弛o r d e rt or e s e a r c hw e bo b j e c t s c a c h e a b i l i t ya n di m p r o v ee f f i c i e n c y o fw e b c a c h es v s t e m ，t h ee v a l u a t i o nm o d e lo fw e bc a c h e a b l eo b j e c t s ，w h i c hb a s e d o nr e q u e s t m e t h o d s h t r pr e s p o n s es t a t u sa n d 哪p a r a m e t e r s ，w a sp r o p o s e d c a c h e a b i l i t y h d e x 孤dc a c h e a b i l i t yp e r c e n t a g e si ne v a l u a t i o nm o d e la l ee m p l o y e dt o e v a l u a t e e a c h e a b i l i t yo fw e bo b j e c t ，w h i l ew e b c a c h e se f f i c i e n c yc a nb em e a s u r e db yv a l u e so f c a c h es p e e d u pi nt h i sp a p e rt h e n ，t h em o d e lo fw e bc a c h ec o n s i s t e n c y , m a d eu po f u s e rf e q u e s t sm o d e la n do b j e c tu p d a t e sm o d e l ，i sp r o p o s e df o rm e a s u r ee f f i c i e n c yo f c o n s i s t e n c ya l g o r i t h m a c c o r d i n gt o s e l v e fh i ta n dc a c h eh i ti nt h i sm o d e l ，t h e e f f i c i e n c yo fc o n s i s t e n c ya l g o r i t h mc a nb em e a s u r e d e x p e r i m e n t a l r e s u l t ss h o wt h a t ： t h em o r es e r v e rh i t s ，t h eh i g h e re f f i c i e n c yo fw e bc o n s i s t e n c ya l g o r i t h m ，w h i c hw e b r e s o u r s e sc a nb eu s e dm o r ee f f i c i e n t l y k e y w o r d s ：w e bc a c h e ；c a c h e a b i l i t y ；e v a l u a t i o nm o d e l ；c a c h es p e e d 。u p ；c o n s i s t e n c y m o d e l i l 目录 目录 摘要i a b s t r a c t 1l 目录j 1 il 图的目录+ vi 表的目录vi l 1 绪论j 1 1 1 互联网络概述1 1 2 互联网面临的困境和解决措施3 1 2 1 互联网面临的困境3 1 2 2 解决措施4 1 3 选题依据7 1 4 研究课题描述7 2w e b 缓存理论基础9 2 1 缓存分类9 2 1 1 客户端缓存( c a c h ea ) 9 2 1 2 代理缓存c a c h eb ) 。9 2 1 3 服务器端代理缓存c a c h ec ) 1 0 2 2w c b 缓存模型1 0 2 3w e b 缓存替换算法。1 2 2 4w e b 缓存性能参数1 6 2 4 1 吞吐量1 6 2 4 2 请求命中率与字节命中率。1 7 2 4 3 延迟时间1 8 2 4 4 缓存加速比1 8 2 5 本章小结2 0 3w e b 对象可缓存性评价模型2 1 l h 目录 3 1 可缓存性的影响因素2 1 3 1 1 请求方式2 1 3 1 2 册1 1 状态码2 1 3 1 3 册参数2 2 3 1 4u r l 属性2 3 3 1 5 对象规模2 3 3 2 可缓存性评价模型j ：2 4 3 3 实验设计及性能分析。2 6 3 3 1 实验设计2 6 3 3 2 实验结果与分析2 7 3 4 本章小结2 8 4w e b 缓存一致性模型研究2 9 4 1w e b 缓存一致性算法2 9 4 1 1 生存时间算法。3 0 4 1 2 客户端轮询算法。3 1 4 1 3 服务失效算法3 1 4 1 4 刷新控制算法3 2 4 1 5 一致性算法性能比较3 2 4 2 w e b 缓存一致性模型一3 3 4 2 1 用户请求模型3 3 4 2 2 对象更新模型3 3 4 2 3 基本假设3 4 4 3 有效命中率与缓存命中率3 4 4 4 实验设计及性能分析。3 5 4 4 1 实验设计3 5 4 4 2 实验结果与分析3 6 4 5 本章小结3 9 5 结论与展望4 0 5 1 结论4 0 5 2 进一步的工作4 0 目录 参考文献4 1 致谢4 4 个人简历4 5 作者在攻读硕士学位期间完成的论文4 5 v 目录 图的目录 图1 1 中国网民人数增长情况2 图2 1 缓存系统分类。9 图2 2 缓存替换算法的处理流程：12 图3 1 基于可缓存率( c p ) 的请求命中率比较2 7 图3 2 基于可缓存率( c p ) 的缓存加速比比较2 8 图4 1 缓存一致性算法的处理流程3 0 图4 2t = i 时有效命中率与入r 关系3 7 图4 3t = 0 5 时有效命中率与入r 关系3 7 图4 4t = i 时缓存命中率与入r 关系3 8 图4 5t = 0 5 时缓存命中率与入r 关系3 8 图4 6 相关更新时间r = 1 时最佳t t l 算法的缓存命中率与入r 关系。3 8 v i 目录 表的目录 表1 1 世界互联网用户增长及分布情况表2 表1 2 中国网页特征表3 表2 - 1 典型w e b 缓存替换算法比较15 表2 2w e b 缓存替换算法的分类比较16 表3 1 三类w e b 对象的h t t p l 1 状态码2 2 表3 2 不可缓存w e b 对象的h t t p 参数设置2 2 表3 3 头部代理服务器参数取值表- 2 4 表3 4 日志数据情况表2 6 表3 5 日志数据详细情况统计表2 7 l 1 绪论 1 绪论 随着w e b 应用的日益广泛，人们越来越依赖于网络获取知识、了解信息， 致使i n t e r n e t 用户爆炸式增长，以致出现了以下问题：一方面用户的增多使服务 器的负载过重，不能及时响应用户的请求；另一方面有限的网络带宽以及数据传 输链路的延迟，造成了网络拥塞，影响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 1 互联网络概述 互联网产业经历了十余年的发展，已经渗透到社会生活的方方面面。随着计 算机技术和通信技术的发展，用户对互联网的需求不断增长，促使了i n t e m e t 的 迅速发展，互联网已成为人们获取信息的重要源泉。随着上网设备成本的下降和 居民收入水平的提高，互联网正逐步走进千家万户。i n t e r n e t 主干网的容量差不 多以每年6 0 的速度扩充。2 0 1 0 年1 月发布的第二十五次中国互联网络发展 状况统计报告数据显示【l l 截至2 0 0 9 年1 2 月3 1 日，中国网民数量已经达到 3 8 4 亿，普及率达到2 8 9 。网民规模较2 0 0 8 年底增长8 6 0 0 力人，年增长率为 1 绪论 2 8 9 。中国网民规模已经跃居到世界第一位。 45 4 3 5 3 z5 2 1 5 1 o 5 0 夏1 0 5 0 6 溅1 2 撇0 6 戮1 2 及) 吼0 6 及聊1 22 0 0 0 6 嬲1 2 及) 0 9 1 2 图1 1 中国网民人数增长情况 根据最新统计数据1 2 1 ，截至2 0 0 9 年，世界网民数量已达到1 , 7 3 3 ，9 9 3 ，7 4 1 人， 网民平均普及率为2 5 6 ( 如表1 - 1 所示) 。由此可看出，随着网络技术的发展， 网络信息内容的r 益丰富，世界网民人数不断增加。今后i n t e r n e t 网络的发展规 模几乎是无人可以预测的。 表1 1 世界互联网用户增长及分布情况表 非洲9 9 1 ，0 0 2 ，3 4 26 7 ，3 7 1 ，7 0 0 6 8 3 9 1 , 3 9 2 4 亚洲 3 ，8 0 8 ，0 7 0 ，5 0 37 8 3 ，2 5 7 ，2 3 0 1 9 4 4 2 6 5 4 5 9 欧洲8 0 3 ，8 5 0 ，8 5 84 1 8 ，0 2 9 ，7 9 6 5 2 0 2 4 1 2 9 7 8 中东2 0 2 ，6 8 7 ，0 0 55 7 ，4 2 5 ，0 4 6 2 8 3 3 3 1 , 6 4 8 2 北美3 4 0 ，8 3 1 ，8 3 12 5 2 ，9 0 8 ，0 0 0 7 4 2 1 4 6 1 3 4 o 拉美及加勒比 5 8 6 ，6 6 2 ，4 6 81 7 9 ，0 3 1 ，4 7 9 3 0 5 1 0 3 8 9 0 8 大洋洲3 4 ，7 0 0 ，2 0 12 0 ，9 7 0 ，4 9 0 6 0 4 1 2 1 7 5 2 总计6 ，7 6 7 ，8 0 5 ，2 0 81 , 7 3 3 ，9 9 3 ，7 4 1 2 5 6 1 0 0 0 3 8 0 3 网页是互联网内容资源的直接载体，网页的规模在一定程度上反映了互联网 内容的丰富程度。自2 0 0 3 年开始，中国的网页规模一直保持在高位增长。截至 2 0 0 9 年底【1 】，中国网页总数超过3 3 6 亿个，较2 0 0 8 年增长率超过1 0 0 。网页 的增长速度与网站的增速基本一致。 2 1 绪论 表1 2 中国网页特征表 近几年来，由w e b 2 0 所带来的视频分享、社区类服务分享技术得到了高速 发展，网络信息资源日益丰富。各种各样的网络信息资源在促进网络基础设施不 断改进的同时，也消耗了大量的网络链路带宽。虽然网络基础设施得到了不断的 改善，但网络基础设施的发展速度远远跟不上网络信息内容的增长速度。目前的 网络面对日益增长的信息资源，在大量信息不断发布的情景下已显得力不从心。 各种各样的信息充斥着网络的每条链路。 1 2 互联网面i 临的困境和解决措施 1 2 1 互联网面临的困境 由于互联网络内容的日益丰富以及网络技术的快速发展，特别是w w w 网 络诞生以来，i n t e r n e t 网络已经成为人们获取信息的重要来源【1 】【2 l 。从整个网络的 发展情况来看，网络基础设施的发展速度远远滞后于网络信息资源的增长速度， 目前各种信息资源充斥于网络的各个链路，导致网络信息流量急剧增加，网络负 载和网络拥塞日益严重，不能很好的保证用户的服务质量( q o s ) 3 1 。 据中国互联网络发展状况统计报告称1 1 j ：中国宽带网民达到3 8 4 亿人， 较上年有了很大增幅；但虽然普及率很高，但宽带接入速度远远落后于互联网发 达国家。同时手机网民年增加1 2 亿，达到2 3 3 亿，占网民总数的6 0 8 ，手机 上网人数达到3 0 7 0 万，占网民总数的8 ，手机上网已成为互联网用户新的增长 点。因此，在无线环境下，w e b 缓存带来的性能收益和网络负载之间的平衡会因 为带宽变得更为重要。文献 1 2 d p 讨论了移动w r e b 缓存和预取，并对不同缓存大 小和无线网络带宽下的性能模型如平均响应时间、缓存命中率进行了估算。因此， 3 1 绪论 如何有效地利用相对少的网络资源，降低用户可感知访问延迟，提高i n t e m e t 网 络服务质量，已经成为一个急需解决的问题。 造成网络延迟的原因通常可分为三个方面：( 1 ) 服务器处理延迟。( 2 ) 链路传 输延迟。( 3 ) 网络连接延迟。服务器处理延迟是指服务器在收到请求后，处理相 应信息所需要的时间。链路传输延迟是指由网络带宽以及电信号传输所造成的信 息在网络链路中的传输延迟。网络连接延迟是指由各种网络协议所决定的建立网 络连接所需要的时间。 目前，造成用户获取访问信息速度缓慢的原因主要有以下几个方面： ( 1 ) 网络基础设施发展速度缓慢、网络带宽的不足必然会延长网络信息的传 输速度。目前网络基础设施虽然有了一定程度的发展，但其发展速度明显落后于 网民日益增长的需要，落后于信息资源的增长速度。 ( 2 ) 部分网络协议存在缺陷。例如哪协议要求每次获取w e b 对象时建立 一次网络连接，这必然会引起额外的网络开销，造成了网络带宽的严重浪费。 ( 3 ) 由服务器处理能力不足所引起的服务时间过长。很明显，超负荷运转的 w e b 服务器是无法满足用户的浏览需要的。 1 2 2 解决措施 可通过以下三个方面来降低网络的访问延迟，提高服务质量： ( 1 ) 加快网络基础设施建设，提高网络带宽和传输速度。从物理性能方面提 高整个网络的传输速度。 ( 2 ) 改善网络协议，修订网络协议存在的缺陷。 ( 3 ) 采取一些技术措施，例如：w e b 缓存技术、内容分发网络、网格技术等， 以此来降低用户可感知的网络访问延迟，提高网络服务质量。 理想的解决方案应该是：通过网络基础设施的改善以及网络协议的修订来解 决网络延迟问题。首先从网络的整个发展过程可以看出，虽然网络的基础设施有 了很大的发展，i n t e m e t 主干网的带宽每年几乎以6 0 的速度增长，但其发展速 度仍远远落后于网络用户以及网络应用的增长速度。其根本原因是网络基础设施 的改善需要较大的投资，而且建设的周期较长。其次网络协议的修订是一个复杂 的过程，涉及到很多细节，牵涉面大，因此修订协议必须十分小心。 目前，更通用的解决方案是：通过采取一系列的技术措施，在当前的网络硬 件环境条件下，遵循通用的网络协议，来改善网络的服务质量。主要的技术措施 包括以下几个方面【6 】1 7 】【8 】： ( 1 ) w e b 缓存技术( w e bc a c h i n g ) 缓存技术是减轻服务器负载、降低网络拥塞、增强w w w 可扩展性的有效 4 1 绪论 方法，是处于用户端与服务器端的信息缓冲机制。其基本思想是：利用用户访问 的时间局部性( t e m p o r a ll o c a l i t y ) 原理，将用户访问过的内容在缓存中存放一 个副本，当该内容下次被再次访问时，不必连接到远程服务器，而是由缓存中保 留的副本来提供。缓存技术可有效地减少用户访问延迟，提高服务质量。具体体 现在以下几点： 应用缓存技术可以有效的减少网络流量，从而减轻网络拥塞； 如果用户所需信息存在于缓存中，则用户可直接从其中获取信息，而不 必连接到远程的服务器，缓存技术屏蔽了广域网延迟和服务器的处理时间，加快 了响应的速度，可以明显的降低用户可感知的访问延迟。 由于用户可从本地缓存或代理服务器缓存中获取信息，因此可降低远程 服务器的负载。 如果远程服务器或网络发生故障而造成远程服务器无法响应时，用户可 以从代理服务器中获取缓存的内容副本。因此缓存还可以屏蔽广域网节点的暂时 不可用性，从而使网络显得更加稳定。 w e b 缓存技术带来的好处实际上是通过两种机制实现的：一是时间局部性原 理；二是有效性检验方法。需要注意的是，并不是所有的w e b 对象都是可以被 缓存的，研究表吲4 】【5 j ：在w e b 对象中不可缓存的对象占据了1 5 - - 5 0 。 在带来好处的同时，w e b 缓存技术也可能造成以下问题： 用户请求可能得到已经过时的w e b 对象。 若访问的对象不在缓存中，则用户的可感知访问延迟会由于缓存系统的 存在而增加。因此在设计缓存系统时，应努力做到缓存命中率的最大化以及失效 代价的最小化。 若w e b 缓存技术设计不得当，会使w e b 缓存服务器成为整个系统的瓶颈。 目前，围绕w e b 缓存技术及其最优化问题已经进行了广泛而深入的研究， 其关注点主要是w e b 缓存算法的优化和缓存加速技术。 ( 2 ) 内容分发网络c d n l 7 1 ( c o n t e n td i s t r i b u t i o nn e t w o r k ) c d n 通常被称为内容分发网络( c o n t e n td i s t r i b u t i o nn e t w o r k ) ，有时也被称 作内容传递网络( c o n t e n td e l i v e r yn e t w o r k ) ，是缓存技术的延续与发展。缓存技 术是一种基于请求的技术，即“拉”的技术，内容分发网络c d n 是从另一个角 度解决网络拥塞问题的有效手段，采用“推的技术。其核心思想是将内容从中 心推到边缘靠近用户的地方。通过访问者的i p 地址判定它来自何方，将其指向 “最近 的内容服务器。这里“最近 指的是网络延迟最小。这样，不但有效提 高了用户访问内容的性能，而且有效减轻了中心设备和骨干网络的压力。通过 c d n ，在现有的i n t e r n e t 中增加一层新的网络架构，可以将内容服务从原来的单 5 1 绪论 一中心结构变为分布式的结构。将网站的内容发布到最接近用户的网络边缘，使 用户可以就近取得所需要的内容，提高用户访问的响应速度。 内容分发网络可分为两个方面：( 1 ) 内容分发，强调c d n 作为透明的信息承 载平台，是指内容从信息源分布到c d n 网络边界的过程；( 2 ) 内容传递，强调 c d n 作为信息的提供和服务平台，是指用户通过c d n 获取信息的过程。 c d n 作为一种提高网络内容传输速度、节省主干网络带宽的技术得到了广 泛的推广。从目前已经运营的c d n 网络的情况来看，c d n 作为一种支持大规模 高质量的流媒体服务的关键技术。对于提高流媒体的服务质量，降低骨干网络的 带宽的作用非常明显。但由于c d n 缺乏统一韵技术标准，因此在发展上受到了 一定的限制。 ( 3 ) w e b 预取技术( w e bp r e f e t c h i n g ) w e b - 预取技术是一种主动地高速缓存技术，主要利用了用户访问的空间局部 性原理。其核心思想是：根据用户的历史访问信息和当前正在访问的w e b 对象， 通过预测模型预测用户即将访问的w e b 对象，利用用户浏览信息时的空闲时间， 提前将用户即将访问的w e b 对象取回到缓存中，当用户真正访问该信息时，只 需从缓存中直接获得。因此w e b 预取技术屏蔽了网络的传输时间和服务器处理 信息的时间，大大缩短了用户可感知的访问延迟。w e b 预取技术是对w e b 缓存 技术的进一步发展。 ( 4 ) 基于网格的w 曲缓存技术 网格1 8 】通过高速互联网络将异构的各种各样的资源连接集成在一起，实现资 源的高度共享。在网格系统中加入缓存，可以屏蔽客户端延迟。如m m 的c a c h i n g g r i d ，南京大学的李文中博士等人提出的网格协同缓存系统( g c a c h i n g ) 和基于 网格的层次w e b 缓存系统的缓存放置和替换算法等【9 1 【1 0 i 1 1 。 i b m 公司将w 曲缓存和网格技术结合，提出了c a c h i n gg r i d 9 1 ，检测到客户 请求率升高时或是请求延迟的q o s 降低时提供缓存服务。具体做法是将来源于 集群中的一部分结点注册成缓存代理客户机。c a c h i n gg r i d 具有较高的商业利用 价值，但由于可变性因素太多，实时建模比较难实现。 g c a c h i n g ( ag r i d b a s e dc o o p e r a t i v ec a c h i n gs y s t e m ) 1 2 0 】则是基于网格环境的 协同缓存系统，它是通过网格中各个代理缓存服务器之间的协同工作，充分利用 网格中的存储资源，达到分散网格中的热点数据，减少网络拥塞，降低用户访问 延迟的目的，从而提供更好的服务。 g h c ( ag r i d b a s e dh i e r a r c h i c a lw e bc a c h i n ga r c h i t e c t u r e ) 1 1 j 采用基于网格的 层级式w e bc a c h i n g 体系结构，在网格环境中建立层级式c a c h e ，将w e b 缓存 组织成树形层次结构。g h c 用h c p r ( h i e r a r c h i c a lw e bc a c h i n gp l a c e m e n ta n d 6 1 绪论 r e p l a c e m e n t ) 算法来实现层级式缓存系统的协同放置与替换。此系统的缺点是 网络开销较大，难于管理和实现用户请求的转发。 1 3 选题依据 w e b 2 0 技术促进了网络娱乐、信息获取、交流沟通、商务交易等应用的高 速发展【，各种各样的网络信息资源消耗了大量的网络链路带宽，尤其是网络音 乐、游戏、视频等应用更是占用大量网络链路带宽。虽然网络基础设施得到了不 断的改善，但其发展速度远远跟不上网络信息内容的增长速度。目前的网络面对 曰益增长的信息资源，在大量信息不断发布的情景下已显得力不从心，大量的带 宽被占用，网络阻塞日益严重。导致了用户访问延迟的增加，用户服务质量得不 到保证。如何改善用户可感知的访问延迟，提高服务质量已成为一个迫切需要解 决的问题。 常用的缓存技术虽然在一些应用中被广泛使用，但还存在一定的缺陷。文献 1 3 1 表明：一些缓存替换算法虽易于实现，但时间复杂度较大，缓存实现的代价 高。有些算法虽然有较高的命中率，但并不能保证用户请求获得较高的服务质量。 因此对缓存技术的研究和改进又有了新的需求。除了替换策略外，一致性策略【1 5 l 对w e b 缓存应用的影响日渐显著。而w e b 对象的可缓存性在一定程度上影响着 w e b 缓存效率，对于不可缓存的对象或是缓存效率不高的对象，用户请求不通过 缓存，而直接从服务器响应。这样可以大大缩短用户的可感知访问延迟，平滑网 络的流量，有效的利用网络资源；同时，w e b 缓存一致性问题影响着整个缓存系 统的效率。因此研究w e b 对象的可缓存性及缓存对象的一致性问题对于提高网 络性能，改善服务质量有着十分重要的意义。 1 4 研究课题描述 服务器负载、发送延迟、传输延迟、网络带宽是影响访问延迟的主要因素， 如何有效地减少用户可感知的访问延迟时间一直是i n t e m e t 网络研究的热点。网 络缓存是解决该问题的有效方法。自w e b 2 0 技术推出以来，网络动态内容同益 增加，以往的缓存技术在一些应用中的弊端也逐渐显露。w e b 对象的可缓存性是 缓存加速关键技术。其核心是在建立有效的w e b 对象可缓存性评估模型，预测 该对象是否可以缓存及缓存的效率如何。另外，对缓存一致性的研究与建模，能 有效的衡量一致性算法的效率，为改进一致性算法、提高缓存效率提供了依据。 论文的主要工作及成果如下： 研究w e b 对象可缓存性的影响因素：请求方式、哪状态码、哪参数、 7 1 绪论 u r l 属性等，对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 缓存系统的性能。 第五部分结论与展望。对论文的工作进行了总结，并指出今后需要进一步 研究的问题和方向。 8 2 w e b 缓存理论基础 2w e b 缓存理论基础 w e b 缓存技术是w e b 加速技术的关键，缓存技术研究的重点主要包括：( 1 ) 缓存系统结构：研究如何按照层次、分布、混合方式组织等问题；( 2 ) 缓存替换 算法：研究如何缓存、缓存哪些对象、缓存替换算法等问题；( 3 ) 缓存一致性算 法：研究缓存对象如何与源服务器数据保持一致的问题；( 4 ) 缓存系统性能参数： 如何定量的衡量缓存系统的效率。因此在w e b 缓存技术中，需要解决的问题包 括如何高效的替换、更新缓存数据及如何定量的评价缓存系统的效率。其中缓存 替换算法和一致性算法对缓存性能起着至关重要的作用。 2 1 缓存分类 如图2 1 所示，根据缓存的工作机制和在网络上不同的实现位置，缓存系统 可分为三类。 c l i e n t i c a c h e ac a c h eb 2 1 1 客户端缓存( c a c h ea ) 图2 1 缓存系统分类 i c a c h e c 通常是由浏览器在用户本地实现，这些浏览器给客户提供一定时间内访问过 的网页信息的缓存机制，如n e t s c a p e 公司的n a v i g a t o r 和c o m m u n i c a t o r 浏览器。 这种缓存机制的主要特点是缓存的对象是w e b 页面，而且每个页面的信息长度 有限，使用的一致性算法和替换算法都比较简单。由于这种缓存离终端用户最近， 所以如果用户请求的对象在本地缓存中，那么响应时间最短，但本地缓存的w e b 对象不能被网络共享。 2 1 2 代理缓存( c a c h eb ) 9 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 对象可以被许多用户共享，这 在一定程度上减轻了网络负载问题。 2 1 3 服务器端代理缓存( c a c h ec ) w e b 服务器既要提供静态对象，又要提供动态内容，在接收到大量请求的同 时还要能确保服务质量，为了达到这个目标，可以在w e b 服务器的前端放置代 理缓存，该缓存保存经常被访问的w e b 页面。这样如果用户请求的w e b 对象在 缓存中，就可以直接从w e b 缓存中获取该对象。在w e b 服务器前端设置的w e b 缓存能够明显地减少服务器开销，适当的降低访问延迟。 2 2w e b 缓存模型 研究表明【1 9 1 ：w 曲对象呈现时间、空间局部性；w e b 请求服从z i p f - l i k e 定 律；w e b 对象大小服从重尾分布；用户在一个网站中的浏览深度服从逆高斯分布。 因为w e b 缓存算法设计多基于对象浏览特征和用户访问特征，所以对w e b 缓存 工作机制的研究与建模尤为重要。 通过分析w e b 缓存工作机制，w e b 缓存模型可以描述如下：假设w e b 服务 器中有n 个可使用对象，w e b 缓存容量为m ；请求序列r = r 1 ，r 2 ，r m ) 导致缓存空间的一个状态序列为s = s 1 ，s 2 ，s m ) ，且s o 为缓存的初始状态， 当被请求对象r 。到达缓存后缓存内容s 。变化有3 种： ( 1 ) 若r t 已经存在于缓存中。当r t 有效时，则缓存内容不变；否则从服务器 下载r t 并放入缓存； ( 2 ) 若r i 不在缓存，且is 。l = 1 ，对于c a c h e a b i l i t y _ i n d e x = 1 的w e b 对象，每次请求 必须发送至服务器来确认该对象的有效性，但这与c a c h e a b i l i t y _ i n d e x = - 1 的有效 性检测不同，当c