（计算机应用技术专业论文）一种代理缓存替换算法的改进及相关问题的研究.pdf

摘要 摘要 本文分析汇总了目前存在的各种数据缓存模型，全面和系统地归纳总 结了代理缓存的概念、分类和特点，并阐述了代理缓存替换策略的应用和 研究现状。在此基础上，提出了一种改进的代理缓存替换策略的算法。本 算法使用文档大小、访问频率、文档访问剩余寿命作为计算文档价值的关 键词，在提出的替换策略上，对文档的访问频率作一个更精确的计算，即 基于m d 5 算法的访问频率的计算。该算法旨在找出缓存中占相当比例的 复制文档，从而能够充分利用w w w 的特性、提高缓存的性能、文档命中 率和系统的检索效率以及避免了缓存污染。模拟实验表明该算法是可行的 并具有优越性。 此外，针对该算法的缓存系统中一些相关的问题进行了系统深入的分 析并提出了相应的解决方案。这些问题包括，如何解决缓存的一致性，如 何解决系统的路由策略以及如何为了更好地提高性能而引入的文档预送策 略。本文在考虑路由策略时，为了节省资源及提高效率，将路由表和目录 表统一，既顾及了路由，又考虑了缓存的一致性。另外，本文在分析了基 于u r l 模式的预送及其改进的策略的基础上，提出了一种基于用户访问行 为分析的网站图模型的预送。通过对用户访问行为进行跟踪和分析，使得 我们预送最有价值的主页副本，提高了空间利用率、命中率以及大大降低 了访问延迟。 关键词代理缓存；替换策略；缓存致性；路由策略；预取预送：剩余 寿命 燕山火学工学硕十学位论文 a b s t r a c t i nt h i sp a p e r , s e v e r a ld a t ac a c h em e d a l sw e r ec o l i e c t e da n da n a l y z e d t h e c o n c e p t i o n c l a s s i f i c a t i o na n dc h a r a c t e r i s t i co fp r o x yc a c h ew e r eg e n e r a l i z e d a n ds u m m a r i z e d a n dg i v e dab r i e fi n t t o d u c t i o no nt ot h es i t u a t i o no f a p p l i c a t i o na n dr e s e a r c ho np r o x yc a c h er e p l a c e m e n tp o l i c y i nt h i sb a s i s ，w e p r o p o s e dai m p r o v e m e n tp r o x yc a c h er e p l a c ep o l i c ya l g o r i t h m t h i s a r t i c l e u s e dd o c u m e n ts i z e ，a c c e s sf r e q u e n c ya n dd o c u m e n ta c c e s sr e m a i nl i f ea st h e k e y o fi t s c o m p u t i n g e l e m e n t s t h e r e p l a c e m e n tp o l i c y w h i c hh a db e e n p r o p o s e dh a dam o r ea c c u r a t ec a l c u l a t et o a c c e s sf r e q u e n c y i tw a sb a s e do n m d 5c h e c k s u m t h i sa l g o r i t h mw a si no r d e rt of i n dt h e s ec o p yd o c u m e n t s w h i c hw a so c c u p i e dc o r r e s p o n d i n gr a t i oi np r o x yc a c h e ，s oa st oa d e q u a t e l y u t i l i z ew w wa c c e s s c h a r a c t e r i s t i c ，i m p r o v ep r o x y c a c h e s p e r f o r m a n c e ， a c h i e v eh i g hd o c u m e n th i tr a t e ，a c c e l e r a t es e a r c he f f i c i e n c yo ft h es y s t e ma n d a v o i dc a c h ep o l l u t i o n t h em e d a le x p e r i m e n t a t i o nt h a tw eh a dm a d ep r e c i s e l y t e s t i f i e st h er e c e i v a b i l i t ya n ds u p e r i o r i t yo f t h ea l g o r i t h m w h a t sm o r e ，o t h e rr e l a t e dp r o b l e m sw e r ea n a l y z e ds y s t e m a t i c a l l ya n dw e o f f e r e d c o r r e s p o n d e n c e s o l u t i o n s t h e s e p r o b l e m s i n c l u d e dh o wt ot a c k l e c a c h ec o n s i s t e n c y ，h o wt os o l v er o u t es t r a t e g yo f t h es y s t e ma n dh o wt or e s o l v e t h ep r e s e n d i n gs t r a t e g y , w h i c hw e r eq u o t e dt oi m p r o v et h ep e r f o r m a n c eo ft h e s y s t e m f o rt h ep u r p o s eo fs a v i n gr e s o u r c e sa n dm a k i n ge f f i c i e n c y ，t h er o u t e l i s t sa n dd i r e c t o r yl i s t sw e r eu n i f i e dw h i l et h i n k i n ga b o u tr o u t es t r a t e g y t h e c a c h es y s t e mc o n s i d e r sb o mr o u t ea n dc a c h ec o h e r e n c e w ep r o p o s e da s i t e g r a p hm o d e lp r c s c n d i n gd u et o t h eb e h a v i o rp a t c e mo fu s e rr e q u e s t sf o r h o m e p a g e s a n dp r e s e n d e d t h em o s tu s e f u lc o p yt oc a c h et h r o u g ht h eb e h a v i o r w h a tw ed i dc o u l de l e v a t et h es p a c eu t i l i z a t i o n ，h i tr a t i oa n d g r e a t l yd e t r a c tt h e a c c c s sd e l a y k e y w o r d s p r o x yc a c h e ；r e p l a c e m e n tp o l i c y ；c a c h ec o n s i s t e n c y ；r o u t e ；s t r a t e g y p r e s e n d i n g ；r e m a i nl i f e 第l 章绪论 1 1引言 第1 章绪论 2 0 世纪6 0 年代美国国防部以a r p a n e t 为主干网建立起i n t e r n e t ，当 时参加这个项目的只有少数的几所美国大学和网络研究机构。到了1 9 8 5 年，n s f ( n a t i o n a ls c i e n c ef o u n d a t i o n ) 开始涉足t c p s p 协议的研究与开发 中，并投入巨资建立了主干网n s f n e t ，逐渐代替a r p a n e t 成为i n t e r n e t 新的主干网。不久，一些研究机构和厂商也将t c p i p 协议加入到计算机 操作系统中，发展成为基于t c p i p 的i m e m e t 。在1 9 9 8 年，接入i m e m a 的计算机己经达到了5 0 0 0 万台。i d c 0 n t e r n e t d a t a c e n t e r ) 数据表明，1 9 9 8 年有1 0 0 0 万人访问w w w ，到2 0 0 0 年已达到3 2 亿人。 正是由于w w w 的出现，才带来i m e r n e t 的迅速发展。w w w 是 i n t e r n e t 上那些支持超文本传输协议h t t p ( h y p e r t e x tt r a n s p o r tp r o t o c 0 1 ) 2 的客户机与服务器的集合。1 9 8 9 年3 月，t i mb e r n e r sl e e 提出一项使科学 家们能很容易翻阅同行们的文章的计划。为了支持这个计划，t i m 创建了 一种新的语言来传输和呈现文本文档，即标记语言h t m l ( h y p e rt e x t m a r k u pl a n g u a g e ) ”j 。h t m l 是通用标记语言s g m l ( s t a n d a r dg e n e r a l i z e d m a r k u pl a n g u a g e ) 4 1 的一个子集。用于操纵h t m l 和其他w w w 文档的协 议称为h t t p 。h t t p 基于请求响应模型，通过客户机和服务器彼此发送 消息的方式工作，提供一个能分布多媒体信息的高速系统。它使用统一资 源定位u r l ( u n i f o r m r e s o u r c el o c a t o r ) 5 1 标识l m e r n 吼上的数据对象，并将 这种数据对象称为网页( p a g e ) 。为了获取w 曲服务器上的个网页，客户 机需要发出的访问请求称为h t t p 请求，而w e b 服务器提供该网页的过程 称为一次响应。1 9 9 2 年7 月，w w w 在c e r n 内部广泛地得到了应用，在 1 9 9 2 年，w w w 只是作为i m e m e t 的一种应用存在，每个月所占网络流量 为7 4 m b ，排在所有i n t e r n e t 上包传送数目的第1 8 位。而在2 0 0 3 年w w w 业务是i m e m e t 上包传送数日的第一位，w w w 流量正以每月2 5 的速度 燕山大学工学硕士学位论文 激增【6 j 。 随着w w w ( w o r l d w i d ew e b ) 业务的迅速增加，i n t e r n e t 变得极度拥挤。 有数据表明i n t e r n e t 开始进入一种不健康的发展方向，两年前可以达到l o k b s 的传输率，而现在只能达到lk b s 。引起一些网络专家对i n t e r n e t 的 未来高度关注并产生忧虑。另一方面，一些热门的w e b 服务器由于负载过 重而变得反应迟缓，迸一步降低了w w w 的服务质量，这种趋势越来越严 重。许多基于w w w 的大型公共信息系统，如电子图书馆( d i g i t a ll i b r a r y ) 、 网上公告系统( b b s ) 、搜索引擎( s e a r c he n g i n e ) 和远程教育( d i s t a n c e l e a r n i n g ) 等，由于涉及的信息量十分庞大，用户访问频率也很高，需要在 实时性和吞吐量方面都具有较高性能的w e b 服务器的支持。i n t e r n e t 的未 来应用领域如，基于w e b 服务器的网上贸易( i n t e r n e tb u s i n e s s ) 、点播视频 ( v i d e o0 1 3 d e m a n d ) 、虚拟现实( v i r t u a lr e a l i t y ) 、网络会议( i n t e r n e tc o n f e r e n c e ) 等，都对w e b 服务器的性能提出了更高的要求。 w 幽服务器面临两方面的挑战：负载的不断增加和负载的多样性。前 者要求w e b 服务器的性能相应提高，后者要求w 曲服务器的功能不断丰 富。由于w 曲服务器分布在i n t e r n e t 上，具有规模大、信息量多、结构复 杂、负载重等特点，一些统计数据表明w 曲服务器有可能成为i n t e r n e t 应 用的瓶颈。因此，很多研究机构和厂商都在针对w w w 服务的特性，研究 和开发更高性能的w e b 服务器。 1 2 几种改善w w w 的方法 目前，计算机界通过对客户机、 研究来改善w e b 性能。 ( 1 ) 更高处理能力的w e b 服务器 w e b 服务器以及i n t e r n e t 网络设施的 采用更高处理能力的w e b 服务器可 以减少w e b 服务器对h t t p ( h y p e r t e x tt r a n s p o r tp r o t o c 0 1 ) 请求进行分析和 处理的时间。随着w w w 应用的发展，h t m l 开始支持动态网页，这些网 页是w 曲服务器根据用户的h t t p 请求动态产生的，通常都涉及到对w e b 服务数据库的操作。因此，虽然w e b 服务器返回给客户机的是一个网页响 应，在w e b 服务器上要进行的计算、检索等操作量相当大，这就要求w e b 2 第1 章绪论 服务器有较高的c p u 性能。通常采用购买更高档服务器的方法来提高性 能，但这种方法不具有可扩展能力，并且成本较高。发展的趋势是采用服 务器集群技术，多个服务器通过局域网连接，协同对客户机的h t t p 请求 进行处理。这种技术提供可扩展、高可用性的w e b 服务器平台，因此具有 很好的应用前景【6 j 。提高w e b 服务器处理能力的另一种技术是预取 ( p r e f e t c h i n g ) ”，即通过预测用户可能访问的网页，并将这些网页事先存储 在存取时间短的存储空间上，以此来减少获取网页的响应时间 8 , 9 1 。 ( 2 ) 减少网络流量通过减少网络流量从而降低对网络带宽的要求，可 以很好地改善w w w 服务的质量。目前主要采取的技术是客户机和网络缓 存技术。缓存技术通过将用户以前请求的响应缓存在靠近用户的客户机或 服务代理服务器上，当用户再次发出相同的请求时，请求并没有到达原本 服务器，而是将缓存副本作为响应返回给用户。通过缓存可以大大地降低 客户机和w e b 服务器之间的信息流量，且用户可以更快地获得响应。缓存 技术已经成为解决w w w 服务质量下降的主要技术手段，从1 9 9 4 年以来， 在这方面的研究工作已取得一些成果：减少网络流量的另一种方法就是修 改h t t p 协议，减少为了建立连接所需要的信息交换次数，h t t p l 1 版本 就是改进的结果。 ( 3 ) 增加i n t e r n e t 网络带宽由于接入i n t e r n e t 的用户数的日益增长，他 们对w w w 服务发出的h t t p 请求已经远远超过了目前i n t e r n e t 的带宽允 许范围，造成一些请求得不到响应或者是响应延迟过长。因此，合理地增 加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 ( n e x t g e n e r a t i o ni m e r n e t ) 和i n t e r n e t 2 计划i l o j 都着重于改善i n t e r n e t 的带宽，其目 标是使i n t e r n e t 的带宽可以达到g b p s 量级，以提供更好的研究和开发平台。 1 1 3 课题的提出及研究意义 w o r l d w i d e w e b 可以被视为一个遍布全球的分布式信息系统，提供数 燕山大学工学硕士学位论文 据共享。人们利用w w w 获取信息、了解信息和发布信息。随着基于w w w 应用的飞速增长，其用户数成指数级增长，而网络速度不尽人意。虽然可 以通过设备升级及提高带宽满足要求，但通过对网络时延的分析发现，传 输时延主要是由传输数据链路的长度决定的。为了提高响应速度，减少时 延，引入了缓存技术，即将经常访问的w e b 文件放置到用户的附近。引入 w e b 缓存机制无疑是一个非常重要可行的方法，w e b 缓存的基本思想是以 存储空间换取i n t e r n e t 带宽，其意义在于w e b 缓存可以有效地减少网络通 信量、减轻服务器的负担和减少用户等待时间。 实现w e b 缓存机制的方式一般有3 种【l “，即客户端、服务器端以及代 理服务器端缓存机制，英中，效率最高的当推代理服务器缓存机制。所以 本文研究的就是代理服务器的缓存机制，其重中之重则是代理缓存的替换 策略。首先我们来简单介绍一下代理服务器。代理服务器处在客户机和服 务器之间，是接受和解释客户端连接并把请求发起到服务器的新连接的网 络节点。对于远程的服务器而言，代理服务器是客户机，它向服务器提出 各种服务申请；对于客户机而言，代理服务器则是服务器，它接受客户机 提出的申请并提供相应的服务。 代理缓存p r o x yc a c h e 是一个试图改善效率的过程。把经常被请求的 w w w 信息拷贝在代理服务器的硬盘中，即存储在本地文件中，靠近信息 使用者，以后对这些信息的请求就可以直接访问代理缓存，不必再连接到 远程服务器上。信息的拷贝集合被称为缓存。代理服务器缓存机制的工作 方式如图1 一l 所示。 图1 - 1缓存机制的工作方式” f i g 1 1w o r k i n g m o d eo f c a c h e l l 2 】 毒 第1 章绪论 当用户对某个网站的页面进行访问的时候，首先将请求送到代理服务 器，如果代理服务器中存放有该页面的副本，则服务器直接提供给用户作 为响应；如果代理服务器中没有该页面的副本，那么将请求复位到驻留网 站，然后将所获得的页面传给用户，并在服务器上保留一个副本。因此代 理服务器缓存机制可以有效地减少网络的通信量、减轻网络服务器的负担 和减少用户的等待时间以及增加网络的可靠性。w e b 缓存系统应具有快速 访问、健壮性、透明性、可扩展性、自适应性及负载平衡等特性。 实施优点如下1 1 3 】： ( 1 ) 减少网络带宽的消耗，从而减少网络流量和网络拥塞。 ( 2 ) 减少了访问延迟，这是由于两方面的原因：一是，频繁访问的网页 由附近的w e b 代理服务器取回，而不是远程的服务器，这样传输延迟降低 了；再者，由于网络流量的减少和远程服务器负载的降低，使取回没缓存 的网页的时间也相对地减少了。 ( 3 ) 增加可用性。由于网络原因或者远程服务器故障导致远程服务的不 可用，但此时客户可以从w e b 代理服务器取回一份缓存，这样加强了w e b 服务的健壮性。 ( 4 ) 降低远程w e b 服务器的工作负载。由于在网络上缓存数据的存在， 减少了直接访问w 曲服务器的次数。 ( 5 ) 安全性的增强。通过w e b 代理服务可以进行用户访问控制、限制用 户的访问范围、内容过滤等。 ( 6 ) 提供用私有i p 访问i n t e r n e t 的方法。有限的i p 资源的不足，已经 突出。使用代理服务器使一个集团，只要拥有一个外部i p 就可拥有对 i n t e r n e t 的访问。 ( 7 ) 提供了一种管理手段。在代理服务器上可以对用户进行管理，还可 实现流量计费等功能。 ( 8 ) w e b 缓存还带来一个副作用，那就是让我们不得不对一个组织的使 用模式进行一系列的研究。 当然，w 曲代理服务器的使用也有一些缺点： ( 1 ) 一个主要的缺点是由于w e b 代理服务器上缺乏适当的缓存更新机 燕山大学工学硕士学位论文 制导致客户可能看到过期的网页( w e b 服务器上的相应网页已经有了变 化) 。 ( 2 ) 由于缓存未命中导致代理服务额外的处理带来的访问延迟的增加。 f 3 ) 单一的代理服务器带来单点故障。 f 4 ) 代理服务器的缓存的使用减少了远程的源服务器的“点击率”，这 样，使拥有这些服务器的组织的统计信息减少，他们可能因此希望不用缓 存他们的网页。 所以，围绕w 曲代理服务器的研究就是怎样更大地发挥它的优势。和 传统的内存缓存一样，w e b 缓存的一个关键性问题是缓存内容的替换策略。 现有的大多数代理缓存器是基于传统内存页调度机制来实现。比如，最近 最少使用( l r u ) 策略，它在内存缓存中被认为是一个有效的算法，但在w e b 环境中却不是一个好的替换策略，其原因是，w e b 文档大小的可变性很大 ( 从几百个字节到几兆) 且必须在i n t e r n e t 上传输，会经历很大延迟。而在内 存缓存中，缓存对象( 页) 的大小和通信延迟都是不变的【1 4 】。另外，w 扎文 档的访问来自不同用户，而内存中对页的访问来自单个程序。因此，很自 然地要求有适合环境的新的缓存机制。本文提出了一种代理缓存替换策略 的改进算法。 1 4 研究现状 由于代理缓存的存储容量是有限的，当其存储区已被文档占满后，新 的文档就无法存储，这时需要按照事先约定好的某种策略，将一部分当前 不再具有存储价值的文档替换出去，因此替换策略的好坏决定了代理缓存 的文档命中率、文档字节命中率等指标，所以代理缓存的核心部分为其替 换策略。 代理缓存的替换策略工作的过程可以分为两个阶段口习：第一个阶段按 照一个或多个关键值( k e y ) 对缓存中的文档进行排序；第二个阶段，从排序 结束的列表头上去掉一个或多个文档直到满足某个规则，这个规则通常是 缓存存储区有足够的空间可以容纳要放入的文档。实际上代理缓存韵替换 6 第1 章绪论 策略也是当这个规则不满足的情况下开始工作。 正像上面提到的，使用不同的替换策略会有不同的命中率，不同的策 略其实现复杂程度不同，因此替换策略的研究对代理缓存性能是非常重要 的。一个好的代理缓存替换策略，是来源于对w w w 业务访问的深刻认识。 因此，目前所提出的替换策略大部分来源于对w w w 访问特性的分析，如 l r u ( 1 e a s t r e c e n t l y u s e d ) 最近最少使用算法，l f u ( 1 c a s t f r e q u e n t l y u s e d ) 最少 使用算法，s i z e ，l r v ( 1 0 w e s t 1 a t e n c y f t r s t ) ，g r e e d y d u a l s i z e 等等。可以用 来排序的关键值基本有访问频率、访问延迟、文档大小、访问流逝时间等 等，而使用这些关键值作为排序的关键字也因此可能采用不同的方法，如 l o g ( s i z e ) 。 由参考文献【1 6 ，1 7 1 8 可以总结出以下算法： ( 1 ) l r u 算法l r u 算法是从缓存文件中选取最长时间没有被使用的 文件来作为被替换的对象。l r u 在参考流中即在显示临时位置特性处工作 的很好，这种特性是指，最近被引用的文件在不久的将来很可能再次被使 用。l r u 算法经常在计算机系统中被使用。例如内存缓存、文件系统缓存、 指令，数据缓存等。其优点是实现简单，在内存缓存中很有效；其缺点是没 有考虑文档的大小和延迟时间。其派生出的一种算法l r u t h r e s h o l d 算法利 用了一个访问特性即大于某个阈值的w e b 文档极少被访问，该对象不被缓 存。p i t k o w r e c k e r 算法则在l r u 算法的基础上利用了另一个访问特性，如 果文档都是今天访问的，则将最大的w e b 文档替换。 ( 2 ) l f u 算法l f u 算法是一个经典的缓存清理算法。它基于静态页面 的访问特性，以缓存对象的使用次数作为缓存区清理的依据，优先清除那 些使用频率较低的对象，对于缓存中的每一个文件维持一个引用记数。在 每个缓存数据命中的时候，这个被请求文件的引用记数值就增加；当缓存 数据没命中的时候，如果这时缓存空间不足以增加被请求文件时，最低引 用记数的文件将被替换出缓存区。其优点也是实现简单，其缺点除了l r u 的缺点外，如果没有失效机制，可能会导致过时的文档将永远留在缓存器 内。h y p e r - g 算法是对l f u 算法的一种扩展，增加了最后一次使用的时间和 目标大小的考虑，使用访问频率作为第一关键字，在访问频率相等时再分 燕山大学工学硕士学位论文 别使用最后一次访问时间和文档大小作为第二和第三关键字。 ( 3 ) l f u a g i n g ( l e a s tf r e q u e m l yu s e dw 池a g i n g ) 算法即带有时间变 化的最不经常使用算法，类似l f u 。当拷贝新的文档进入缓存，并且缓存 没有足够空间时，将最少使用的文档替换出缓存。但是，该算法尝试去处 理l f u 的问题。用l f u 算法一些文档引用数目可以达到非常高，以至于他 们几乎不会被取代，即使这些文档再也不会被使用。通过限制和变化引用 数目f 例如降低) ，l f u a g i n g 算法试图确保这种情况不会发生。 h ) f b r ( f r e q u e n c yb a s e dr e p l a c e m e n t ) 算法以频率为基础的替换算 法，使用引用频率和年龄的联合来决定如何替换。f b r 把缓存区分成三部 分：新的一部分、中间的一部分以及旧的一部分。当数据刚刚被存入缓存 区，首先把它放在新的部分的开始( 最常使用m r u ) ：随着文件变旧，以l r u 为基础，缓存数据被从新的部分取出，转移到中间部分；如果文件持续存 放时间持续增大，例如仍在缓存中，但是不会再被引用，它最终将从中间 部分移至旧的部分。只有旧的部分里的文件是缓存替换策略的候选者。当 缓存中的数据命中时，被引用的文件放八新部分的开始( m r u ) 。如果命中 的缓存文件在中间或旧的部分，它的引用数目增加：如果文件已经在新的 部分，它的引用数目不增加。当发生缓存没命中的时候，根据缓存替换算 法，旧的部分里最少使用的被替换掉，可以选择最低引用数目的最久没有 被使用的文件。f b r 也可以作为一个时间增加算法。 ( 5 ) s i z e 算法首先清除大文档，其优点是移出大文档，可以保留更多 的小文档，产生更高的请求命中率：其缺点是可能使小文档永远留在缓存 器中，使字节命中率降低，而且当再次下载大文档时，占用网络资源都很 多。l o g ( s i z e ) + l r u 算法替换具有最大的l o g ( s i z e ) 值的文档，如果有多个 同样的l o g ( s i z e ) 值的文档，则替换最不常被访问的文档( l r u ) 。 ( 6 ) g d - s i z e ( g r e e d y d u a l ) 算法这是个基于代价的贪婪算法。缓存器 中的文档都应该有相应的价值h ，当网页被带进缓存器时，该网页的h 值为 1 s i z e ，发生替换时，最小h 值的文档( m i r t h ) 被换出，剩下的文档的h 值变 为替换前的h 值减去m i r t h 值。若文档被再次访问，则恢复其原来的值。该 算法的优点是不再被访问的文档会被清除，克服了s i z e 算法的缺点，还可 第1 章绪论 以使用更复杂的价值函数，然而1 s i z e 函数的缺点是没有考虑文档使用率 和网络延迟。还有一种g r e e d y d u a l s i z e 算法，该算法赋予每一个缓存中的 文档一个h 值，h 的初始值为c s ，c 为文档带入缓存的开销，s 为文档大小， 当替换发生时，选出h 值最小的文档将其替换出去，并将所有的缓存中的 文档的h 值减去这个最小的h 值，而文档访问命中时，则将文档的h 值恢复 为c s ，其中c 可以为1 ，p a c k e t s ，l a t e n c y 等等，这些正是此算法的灵活之 处。也可以根据不同的需要变换c ，达到提高命中率和降低网络开销的目 的，g r e e d y - d u a l - s i z e 的主要贡献是应用的灵活及在算法中考虑了文档的年 龄问题。 ( 7 ) l r v ( 1 0 w e s t r e l a t i v ev a l u e ) 算法算法中考虑了获取文档的代价、文 档的大小，并利用对w e b p r o x y 访问日志的分析，计算文档下一次被访问、 一段时间后被访问的概率，最后形成一个计算公式，其值即为替换的依据。 其优点是字节命中率优于其它算法；其缺点是，由于是对轨迹分析得到的， 参数的选取依赖于特殊的轨迹。 ( 8 ) l l f ( 1 0 w e s t l a t e n c y f l _ r s t ) 算法使用访问w e b 文档时的延时来作为 替换的标准，在替换发生时优先考虑访问延时最小的w e b 文档。 ( 9 ) 混合( h y b i r d ) 算法旨在减少整体延迟时间，它不但考虑链接服务 器的时间和到服务器的网络带宽，还考虑了页面的大小和页面的访问次数， 并把它们有效地结合起来。用一个函数来计算每个页面的权值，替换时将 选择最小权值的页面。 ( o ) m i x 算法它将几种文档属性综合起来考虑，算法的代价函数为 墨：堑堑： r ，- 1 、 t r e f 3 + s 、。1 7 式中n r e f 是文档在缓存里的访问数，t r e f 为现在的时间减去最近访问的时 间，l 是参数。其优点是在特定的参数下( n = 0 1 ，r 2 r 3r 41 ) ，性能 表现很好，其缺点是参数选取复杂。 ( 1 1 ) l n c ( 1 e a s t n o r m a l i z e d - c o s t ) 算法即最小正规化代价算法，它是根 据引用率评估w e b 文档的代价。引用率是一个反映文档未来被访问的可能 性大小的量，由文档的访问历史和现在流逝的时阀组成，和文档单元价值 9 燕山大学上学硕士学位论文 一起形成一个公平、一致性的代价。该算法是一个高效的算法，它有l r u 算法的简洁，对文档代价的计算既不需要保留以前的访问记录，又不需要 有复杂的参数估计，同时还能迅速地体现文档访问率的变动情况。 1 5 衡量替换策略优劣的指标 影响缓存替换算法优劣的因素是多方面的，所以缓存替换因子的确定 需要对影响替换算法的相关因素进行分析。具体说来，可主要从以下几方 面进行考虑。 ( 1 ) 属性不同缓存文件属性在系统中，w e b 数据可以分为p r i v a t e 年g p u b l i c 两种，具有p u b l i c 属性的w e b 数据可以同时被多个用户访问，而具有 p r i v a t e 属性的w e b 数据却只能被某些特定的用户使用。显然具有p r i v a t e 属 性的w e b 数据对将来的访问并没有什么价值，因而将被优先清除。具有 p r i v a t e 属性的w e b 数据主要包括c g i b i n 脚本、需要身份验证的w e b 页面等。 只有g e t 方法请求的w e b 数据才具有p u b l i c 属性；另外，缓存数据的一个 重要属性就是生存期，生存期短的数据意味着，缓存数据很快就要成为过 期的、无效的数据，显然长期保存对这样的数据对以后的访问是没有太大 意义的，这也是替换算法中应该考虑的一个重要因素。 ( 2 ) 请求间隔请求间隔是指连续的对文档的请求之间的间隔。由于用 户请求的数据具有短期局部性，故我们认为用户请求间隔小的文档在将来 被请求的机会也会更大( 就像后面章节将提到的剩余寿命就是基于访问时 间间隔的策略改进的) 。l r u 算法就是把请求间隔最大的文档淘汰，所以它 是减小缓存文档的平均请求间隔的最好算法。 ( 3 ) 先前访问的次数文档先前被访问的次数，可以用来作为估计将来 会不会再次被请求的辅助参考。被用户端请求访问次数多的文件，一般是 被大家关注的热门的信息，这样的内容所以通常可以认为是在以后也会被 频繁访问的，所以值得保留。 ( 4 ) 文档的大小文档的大小是缓存考虑的一个重要因素。在代理缓存 服务器中，缓存的文档大小各异。在同样缓存大小的缓存区中，显然缓存 l o 第1 章绪论 较小的文档可以使缓存中能够包含更多的文档，这样可以提高缓存的命中 率，而且用户访问较多的通常也是这些较小的文档。所以出于这种考虑会 为了提高性能而要缓存较小的文档。 ( 5 ) 获取一个文档的代价文档下载的延迟，也就是要获取一个文档所 需要的代价，这也是一个值得考虑的因素。如果文档下载时所需要的代价 很大，那么就比那些较容易获得的文档更应该保留在缓存中。 衡量一个缓存替换策略的主要指标有以下几种： ( 1 ) 文档命中率当用户通过缓存访问w e b 时，缓存通过自己的缓存或 直接访问w e bs e v e r 来提供用户所要访问的文档，如果缓存通过自己的缓存 提供用户所要访问的文档，则称之为一次命中，反之如果缓存通过直接访 问w e bs e v e r 来提供用户所要访问的文档，则称之为一次不命中，则文档命 中率按以下公式计算： h = 命中的次数用户访问文档的总次数 ( 2 ) 文档字节命中率文档字节命中率和文档命中率很相似，只是计算 单位改为字节数，文档字节命中率按以下公式来计算： b = 命中的字节数用户访问文档的总字节数 其中，命中的字节数为命中文档的大小的总和；用户访问文档的总字节数 为访问文档的大小的总和。 ( 3 ) 文档分组( p a c k e t ) 命中率将文档字节命中率中的总字节数转化为 总分组数( 根据t c p i p 协议，按照一次访问约等于2 + 文档大小字节数5 3 6 来计算) ，就得到了文档分组( p a c k e t ) 命中率，其计算公式为； p = 命中的分组数用户访问文档的总分组数 其中，命中的分组数为命中文档的分组数的总和。 1 。6 论文组织结构 本文通过对现有的代理缓存技术进行分析和研究，总结归纳了代理缓 存的分类、特点及其核心部分缓存的替换策略，以及替换策略的研究 现状，并在此基础上对一种新的替换策略做了改进。一种基于m d 5 算法 燕山大学工学硕士学位论文 的改进【”】，并且进行了模拟实验，得出的数据证明该策略的改进是有意义 的。同时给出了怎样维护缓存的一致性问题【2 0 ，2 1 2 1 及一些相关的问题，如 为了进一步提高缓存的性能而进行的缓存的预取预 2 3 , 2 4 - 2 5 1 送策略、本缓存 的路由管理【2 6 】等。本文的框架如下： ( 1 ) 在第1 章里，我们主要指出为了提高w e b 性能而研究出的几种方法 以及在此基础上本课题进行研究的必要性和意义。 ( 2 ) 在第2 章里，我们主要介绍了一些有关缓存，有关替换策略的基本 概念和研究现状，以便让读者更好地了解作者的构思及所要阐述的内容。 ( 3 ) 本文的重点在第3 章里，第3 章首先表达了缓存替换策略是怎样改 进的，然后引出m d 5 的一系列说明，包括说明m d 5 是什么、为什么引入 m d 5 以及m d 5 的算法步骤，并且为这种改进的策略做了模拟实验，其提 高的性能表明该方法的可行性。最后还在此基础上，提出了怎样维护缓存 的一致性策略。 ( 4 ) 第4 章，我们对缓存替换策略的相关问题做了相应的分析和改进。 为了更进一步提高缓存性能和文档的命中率等，我们设计了一种预送方案， 但基于预取、预送算法的复杂性和繁琐性，我们没有做出具体的算法描述， 只是一种简单的构思。最后针对本缓存替换策略提出了基于其的路由方法。 1 2 第2 章理论基础 第2 章理论基础 2 1 p r o x yc a c h e 概述 2 1 1 p r o x yc a c h e 的发展 p r o x yc a c h e 从最初代理简单c a c h e 功能，到以后逐渐发展，开始对 c a c h e 提出许多协议，直至出现独立c a c h e 产品，其间发展经历了如 下阶段1 2 7 ： ( 1 ) 1 9 9 6 年前c e r np r o x y 共享软件实现最简单的缓存功能。c e r n 层 叠( c e r nc a s c a d i n g ) 提供通过代理链的h t t p 转发，让缓存路由，但是 没有商业化的代理服务器。 ( 2 ) 1 9 9 6 年以第一代c e r np r o x y 技术为基础，更新的第二代 h a r v e s t s q u i d 提出层次代理c a c h e 技术。h a r v e s tp r o j e e t 提出了i c p 协议， 改善了i n t e r n e tw e b 性能和可升级性。1 9 9 6 年起出现了许多商业化的代理 服务器软件，大部分功能简单。而1 9 9 6 年同期，m i c r o s o f t 、n e t s c a p e 推 出他们面向企业级的代理服务器m sp r o x y1 0 、n sp r o x y1 0 ，他们支持多 种协议，提供w 曲缓存。 ( 3 ) 1 9 9 7 年大部分代理服务器软件厂商推出了其产品的后续版本，在功 能上有所增强，支持更多协议，并提供更完善的管理功能。由于基本功能 不会有太大改变，9 8 年以来各厂商尽量提高自己服务器的性能，许多厂商 已经把缓存作为单独的产品推出，而且另外还有许多其它的缓存，诸如对 关系数据库的缓存产品的出现，如c a c h e4 是e d b m s 产品。 2 1 2 可缓存性 w e b 对象的复杂性使w e b 缓存系统中数据的可缓存性有其独特性。据 专家统计，在w e b 访问中遇到的不可缓存的对象的数量在1 5 一5 0 之 燕山火学工学硕士学位论文 问【2 8 】，不可缓存对象的存在影响了缓存系统的有效性。 代理服务器认为一些w e b 对象是不可缓存的，有下面几个主要方面的 原因 2 9 ： 首先，些w e b 对象从本质上是不能缓存的。例如，它在取回时需要 首先通过认证，所以不能缓存。而一些w e b 对象是用户相关的或上下文相 关的，这样有不同的用户请求或请求的上下文不同时其结果是不一样的。 其次，缓存一些w e b 对象意义不大或者保存它们代价太大，那它们都 是不可缓存的。有一些对象改变的太快，如动态产生的对象，常常在下次 请求时前次的缓存已经无效了，这时缓存就没有多大意义了；还有一些太 大了，要缓存它们就要将许多小的对象“挤”出去，这样使缓存的效率从整 体上降低了。所以，通常w e b 代理服务器对可缓存的w e b 对象的大小设置 一个门限值。 最后，一些w e b 对象是由源服务器设置成不可缓存的，虽然它们本来 对代理服务器来说是可缓存的。 下面有几个方面是决定w e b 对象是可以缓存的 3 0 1 ： 首先，根据请求方法：h t t p 1 0 中有三种方法：g e t ，h e a d 和p o s t ； h t t p 1 1 中有：g e t 、h e a d 、p o s t 、p u t 、d e l e t e 、o p t i o n 和t r a c e 。 只有g e t 和h e a d 两种方法可以缓存。但这并不意味着缓存的意义不大 了，因为h t t p 请求中用g e t 方法的请求占有约9 8 。 其次，根据h t t p 状态码：根据h t t p 1 1 ，可以将h t t p 状态码分为三 类：可缓存，否定缓存和不可缓存。 最后，根据h t t p 头：在h t t p 消息头中有以下域的消息实体表明此响 应是不可缓存的：没有“l a s tm o d i f i e d ”；有“s e tc o o k i e ”；有 p r a g m a ： n o c a c h e ”；有“a r t h o r i z a t i o f f ；以及“c a c h e c o n t r o l ”说明是私有数据或不可 缓存等。 2 1 3 p r o x yc a c h e 类型 代理缓存服务器的分类从不同方面考虑，有各自划分的方式，总的来 说可以从以下几方面进行划分。 1 4 第2 章理论基础 2 1 3 1从用户的角度划分从用户的角度出发对代理缓存服务器进行划 分，可以分为非透明的代理缓存服务器和透明的代理缓存服务器【3 ”。 ( 1 ) 非透明的代理缓存服务器一般的代理服务器，虽然可以自动地代 理用户的i n t e r n e t j 艮务请求，使用与整个i n t e r n e t