（计算机应用技术专业论文）web集群缓存系统中代理缓存技术的研究.pdf

摘要摘要随着i n t e r n e t 迅猛发展，出现了访问延迟过长、服务器过载等一系列问题。代理缓存技术能很好的解决上述问题，并得到了广泛应用。然而由于用户的增多和w e b 流量的迅速增加，单个代理缓存的性能难以满足实际需要，因此本课题对集群缓存系统的研究，具有很强的现实意义。本文着重从以下几个方面进行深入地研究和探讨。首先，在缓存副本的存储方面，针对目前没有注意到对象的类型、访问次序等信息联系的现状，采用面向站点的存储结构，方便智能化管理。其次，在副本管理方面，鉴于目前没有将一致性和替换算法很好结合起来的现状，本文设计了替换一致性算法r c a ( r e p l a c e m e n tc o n s i s t e n ta r i t h m e t i c ) 。它能较好地反映w e b 用户访问的特点而且计算简便，体现了替换和一致性结合起来的优越性。再次，在代理问通信协作方面，提出了新的协作代理缓存机制n c p c p ( n e wc o o p e r a t i v ep r o x yc a c h ep r o t o c 0 1 ) 。它通过重定向的方法减少系统内部的通信量，使用访问登记表减轻管理器的负担。只转发请求，在集群中避免不必要的对象复制，大大提高了集群缓存系统的整体命中率。最后，通过理论分析证明了n c p c p 的性能要优于c r i s p ( c a c h i n ga n dr e p l i c a t i o nf o ri n t e r n e ts e r v i c ep e r f o r m a n c e ) 和i e p ( i m e r n e tc a c h ep r o t o c 0 1 ) ，并通过实验，验证了n c p c p 的整体命中率高于c r i s p 和i c p 。为今后的进一步研究提供了宝贵经验。关键词w e b 集群缓存系统；代理缓存；替换策略；一致性策略：协作代理缓存茎生查堂三兰堡主兰堡笙墨a b s t r a c tw i t ht h er a p i de x p a n s i o no fi n t e r n e t ，i th a sc o m ef o r t ht h a tt h ed e l a yo fa c c e s s ，t h eh e a v yl o a d so f w e bs e r v e r sa n ds oo i l w e bp r o x yc a c h i n gt e c h n i q u ed r o v i d e sas o l u t i o nt ot h ea b o v ep r o b l e m s i ti sn o ww i d e l ya p p l i e do ni n t e m e t h o w e v e r , w i t ht h er a p i di n c r e a s ei nc l i e n t sa n dw e bf l u x ，t h ep e r f o r m a n c eo fs i n g l ec a c h ec a nh a r d l ys a r i s f yt h i ss i t u a t i o n t h e r e f o r e ，i th a sg r e a ta c t u a ls i g n i f i c a n c et or e s e a r c ho np r o x yc a c h ei nac l u s t e r - b a s e dw e bc a c h i n gs y s t e mi nt h ea r t i c l e s e v e r a la s p e c t sa r ep r o b e di n t oa sf o f l o w s ：f i r s t l y ，i nt h es t o r eo f c a c h e do b j e c t s ，a i m i n ga tn o tp a y i n ga t t e n t i o nt ot h er e l a t i o n s h i po fi n f o r m a t i o n t h es i t e o r i e n t e dc a c h es t r u c t u r ei su s e dt os u p p o r ti n t e l l i g e n tp r o c e s sb e t t e r s e c o n d l y , i nt h em a n a g e m e n to fc a c h e do b j e c t s ，a i m i n ga tn o tc o m b i n e dr e p l a c e m e n tp o l i c yw i t hc o n s i s t e n c yp o l i c y , an e wa l g o r i t h mc a l l e dr c a( r e p l a c e m e n tc o n s i s t e n ta r i t h m e t i c ) i sp r o p o s e da n dd e s i g n e d i tc a nr e f l e c tw e ba c c e s sc h a r a c t e r i s t i c sb e t t e ra n dc a l c u l a t ee a s i l y i ts h o w st h es u p e r i o r i t yo f c o m b i n i n gc a c h er e p l a c e m e n tp o l i c yw i t hc o n s i s t e n c yp o l i c y t h i r d l y ，i nt h ec o m m u n i c a t i o na m o n gc a c h ep r o x i e s ，n c p c p e wc o o p e r a t i v ep r o x yc a c h ep r o t o c 0 1 ) i sp r o p o s e d b yu s i n gr e d i r e c t i o n , t h ec o m m u n i c a t i o ni nt h es y s t e mw i l lh eg r e a t l yr e d u c e d ；u s i n ga c c e s sr e g i s t e rf o r m , t h el o a do nt h em a n a g e rw i l la l s ob er e d u c e d o n l yt h er e q u e s tw i l lb es e n tt ot h ep e e rp r o x y , s ot h er e d u n d a n td u p l i c a t e sa m o n gp r o x i e sa r eg r e a t l yr e d u c e d t h ew h o l eh i t - r a t ei si n c r e a s ec o r r e s p o n d i n g l y f i n a l l y ，a f t e ra n a l y z e di nt h e o r y ，i ti sp r o v e dt h a tt h ep e r f o r m a n c eo fn c p c pi sb e t t e rt h a nc r i s p ( c a c h i n ga n dr e p l i c a t i o nf o ri n t e r n e ts e r v i c ep e r f o r m a n c e ) a n di c p ( i n t e r n e tc a c h ep r o t o c 0 1 ) i ti sa l s op r o v e dt h a tt h ew h o l ei ia b s t r a c th i t r a t eo fn c p c pi sh i g h e rt h a nt h a to fc r i s pa n di c pi no u re x p e r i m e n ts o m ep r e c i o u se x p e r i e n c ei sp r o v i d e df o rt h ef u t u r er e s e a r c h k e y w o r d sc l u s t e r - b a s e dw e bc a c h i n gs y s t e m ；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 o n s i s t e n c y p o l i c y ；c o o p e r a t i v ep r o x yc a c h ei l l燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文( ( w e b 集群缓存系统中代理缓存技术的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字宙嫱鹰燕山大学硕士学位论文使用授权书( ( w e b 集群缓存系统中代理缓存技术的研究系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。保密口，在年解密后适用本授权书。本学位论文属于不保密口。( 请在以上相应方框内打“4 ”)储签名：暂香婧日期：勿辟钠日导师签名：蓐节向备日期：沙乃年砂月占日第1 章绪论第1 章绪论自2 0 世纪9 0 年代以来，计算机网络在全球范围内得到迅速普及和延伸，几乎己深入到人类生活的任何一个领域，因此网络性能成为备受关注的问题。目前w e b 缓存技术已经成为最有效、应用最广泛的w w w ( w o r l dw i d ew e b ) 加速技术。本课题研究的目的就是将集群技术和w e b 缓存技术结合起来，更好地改善网络性能，解决网络拥塞、响应延迟过长等问题。1 1 课题研究背景与科学意义w w w 是i n t e r n e t i 支持超文本传输协议h t t p ( h y p e rt e x tt r a n s p o r tp r o t o c 0 1 ) 的客户机与服务器的集合，是全球最大的分布式信息系统。w w w的出现使得i n t e r n e t 上的信息访问产生了质的飞跃，带来i n t e r n e t 迅速发展。它利用超文本标记语言h t m l ( h y p e rt e x tm a r k u pl a n g u a g e ) 1 1 1 及其扩展集来组织信息的内容，并将文本、图形、多媒体信息有机地结合在一起，提供给用户一种简便、快捷和友好的信息访问方式。用于操纵h t m l 和其他w w w 文档的协议称为h t t p ，它是一种简单的无状态协议，具有良好的快速转移能力，非常适合超文本的连接特性，方便用户快速搜索和定位自己需要的信息。1 9 9 2 年7 月，w w w 在欧洲粒子物理研究所内部得到广泛应用。1 9 9 2年，w w w 只是作为i n t e r n e t 的一种应用存在，每月所占网络流量为7 4m b ，排在所有i n t e r n e t 上包传送数目的第1 8 位。而在2 0 0 3 年w w w 业务是i n t e r n e t 上包传送数目的第一位，w w w 流量正以每月2 5 的速度激增【2 】。仅中国为例，中国互联网络信息中一心c n n i c ( c h i n ai n t e m e tn e t w o r ki n f o r m a t i o nc e n t e r ) 最新发布的第十一次中国互联网络发展状况统计报告数据显示，截止到2 0 0 2 年1 2 月3 1 日，我国上网计算机总数达到2 0 8 3燕山大学工学硕士学位论文万，上网用户总数达到5 9 1 0 万，与上一次( 半年前) 的统计数据相比，分别增长了2 9 1 和2 9 o ；而与1 9 9 8 年7 月的统计数据相比，在四年半的时间里，两项数据的增长幅度分别高达3 7 4 倍和4 9 3 倍。据统计，截至到2 0 0 2 年，全球网站数量已经超过8 7 1 2 0 0 0 个。随着a d s l 、光纤入户等接入网带宽技术的广泛应用，全球i n t e r n e t 用户已经超过一亿，而且仍呈现出指数增长的趋势 3 j 。但是由于w w w 流量激增，目前的网络带宽有限，再加上访问用户的激增和对“热点”数据的频繁访问，使得i n t e r n e t 变得极度拥挤，出现了访问延迟、通信错误增多、服务器过载等一系列问题。虽然可以升级设备、提高带宽来满足要求，但硬件设施的发展速度远远跟不上网站和用户数量的增加。这引起一些网络专家对i n t e r n e t 的未来高度关注并产生忧虑。为了提高w w w 服务的质量，许多组织和研究人员提出了许多改进的建议和措施，例如：h n p 协议的加强、w e b 专用图片文件格式的开发、网关上的压缩技术、w e b 服务器的集群、热门网站的复制和镜像，以及w e b 缓存和预取等等。经过十年的研究，人们充分证明了用户请求中存在大量的共享性和局部性，并且对网络中瓶颈的分布规律作了估计。综合这些研究结果，可以将w w w 网络的特性归纳为以下几点：( 1 ) h t t p 对象占所有i n t e m e t 访问请求的7 5 0 0 - - 8 0 ，它的分布服从形如f 2 i 。( 0 o t 1 ) 的z i p f 分布，a 体现了对象的共享性的大t j x 4 。( 2 ) 单个用户访问的时间局部性，即一个文件在被访问k 次后再次被访问的概率是1 k 5 , 6 。( 3 ) 7 1 的访问请求集中在1 5 - 2 8 的共享对象上，对象的大小和访问频率成反比，并且访问集中在少量被大量用户共享的文件上【7 】。( 4 ) 用户对少数被大量共享对象的访问呈现两级分布，即用户群可能存在很强的区域性；也可能被全球用户所共享。( 5 ) 对象被访问的频率与它的改动频率没有明显的统计规律；1 访问频率最高的对象每天平均的变化率反而低于1 0 的对象i 盯。这些实验结果表明：通过c a c h e 来减少网络流量和用户访问延迟的可行性，以及通过大规模c a c h e 系统来实现更高命中率和空间共享的必要性。2第1 章绪论因此w e b 缓存技术会成为最有效、应用最广泛的w w w 加速技术p j 。w e b 缓存的基本思想是以存储空间换取i n t e r n e t 带宽，其意义在于w e b缓存可以有效地减少网络通信量、减轻服务器的负载和降低用户等待时间。实现w e b 缓存机制的方式一般有3 种，即客户端、服务器端和代理服务器端缓存机制“o j 。很多研究表明：代理服务器缓存机制是解决w w w 访问速度慢、服务器负载过重和网络拥塞等问题的最好方法 1 ”。然而随着i n t e r n e t 用户的增多，w e b 流量的持续增加，单个代理缓存服务器的缓存能力和服务能力都十分有限，可扩展性也较差，而且一旦代理过载，客户网络和外界的联系就会中断。特别是在大型的i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 出口以及校园网的出口等处，都迫切需要高性能的缓存服务器，因此研究人员提出各种方法来增强缓存服务器的性能。使用集群技术来增强缓存服务器的处理能力是目前最为有效的方法之一。集群缓存技术【1 2 叫4 1 充分利用了集群技术的优势，将集群技术和缓存技术结合起来，增强了单个缓存服务节点的性能。它利用现有的集群技术和缓存服务器软件来构建一个具有单一系统映像的( s i n g l es y s t e mi m a g e ) 、可伸缩性的( s c a l a b l e ) 集群缓存系统，并在代理节点之间引入代理协作机制，使多个代理节点相互协作。集群缓存系统能提高缓存命中率，同时分散热点数据，均衡各代理服务器的负载，避免了单个代理失效的问题，因此能很好的解决上述瓶颈问题。目前很多大的i s p 的出口处和合作缓存系统的高层节点都采用了集群缓存技术，充分发挥高性能缓存的优势。1 2 国内外研究现状集群缓存系统大致由三部分组成：集群系统、缓存技术和缓存通信机制。下面分别介绍这三部分的研究现状。1 2 1集群技术的研究现状英国国家j a n e tc a c h es e r v i c e 用w e b 集群缓存系统，为英国1 5 0 所以上的大学提供w e bc a c h e 服务。通过代替原有的5 0 多台相互独立的c a c h e燕山大学工学硕士学位论文服务器，大大提高了用户的上网速度口”。可见，通过负载调度可以抚平单台服务器访问的毛刺，提高整个系统的资源利用率。国内进行集群缓存系统方面研究的大学和研究机构也不少，清华大学郑纬民教授主持的高性能计算所对集群系统在负载均衡 1 6 a 7 l 、文件请求分配【1 8 】、高性能计算等方面有着系统的研究。国防科技大学的章文嵩博士发起并领导开发的l v s ( l i n u xv i r t u a ls e r v e r ) t 20 】是集群系统的典型代表。l v s 集群采用i p 负载均衡技术和基于内容请求分发技术，将负载调度器、服务器池和共享存储系统通过高速网络相连接，有效避免了当系统规模扩大时互联网络成为整个系统的瓶颈。还有中国科技大学、北京理工大学、中科院计算所等等致力于集群技术的研究，但是大多停留在研究阶段，尚未达到成熟的可应用水平。1 2 2 缓存技术的研究现状缓存技术【2 1 0 2 】是一个复杂的课题，它需要解决替换策略 2 3 - 2 5 l 、一致性策略、体系结构等诸多问题，在国际上已经形成一个独立的主流研究领域。其中致性策略和替换策略的研究一直是提高代理缓存系统性能的两个研究方向，这些也是本文要讨论的重点内容之一。使用不同的替换策略会有不同的命中率，不同的策略其实现复杂程度不同，因此替换策略的研究对代理缓存性能是非常重要的。常用的一些替换算法会在后续章节做详细介绍。在缓存一致性方面，目前已经提出了一些成熟可靠的缓存一致性检验算法模型 2 6 - - 2 8 1 。但是，这些研究通常是将这两种策略作为两种独立的机制单独研究，很少将这两种策略结合起来一起研究。在国内外，只发现了三篇文献涉及到这个研究内容。j s h i m 等人基于最优化模型，提出了l n c r - w 3 u 算法【2 9 1 ，它根据代价函数来考虑取回每一网页放入缓存的延迟和按照t t l ( t i m et ol i v e ) 来验证每一个网页的新鲜程度以决定是否替换。但是它只考虑了网页大小及其访问延迟，没有考虑访问次数、类型等，而且计算相当复杂。b k r i s h n a m u r t h y 等人分别用两种缓存一致性策略和两种替换策略的四种组合来研究它们之间的相互影响t 3 0 】，其主要研究成果有：4第1 章绪论( 1 ) 当缓存容量为所需要缓存总容量的15 - 2 5 时，缓存替换策略对成本影响很大；当缓存容量更大时，缓存一致性策略对成本影响很大。( 2 ) 缓存策略中加入缓存一致性策略能提高代理缓存系统的整体性能。( 3 ) 随着h t t p 协议的日益完善，缓存一致性策略和替换策略还会继续影响网络成本，好的一致性策略和好的替换策略相结合能减少网络成本。j a g u i l a r 等人提出了缓存自适应一致性替换机制 3 ”，在保证一致性的前提下，利用共享缓存存储单元的状态信息来觉察用户的访问行为，在替换阶段对不同的访问对象采用不同的替换策略。但是要考虑很多参数，实现较为困难，只是理论上的探讨，没有任何实验依据。由此可见，代理缓存的一致性策略和替换策略若能很好地结合起来，代理缓存系统可以获得更好的整体性能。因此，对它们进行更深入地研究具有较强的理论和实践意义。1 2 3 缓存通信机制的研究现状国外的些研究机构从2 0 世纪9 0 年代末就开始对缓存系统的体系结构及其代理节点间的通信协议进行研究，许多科研院所及公司都参与其中。h a r v e s t 系统 3 2 的开发者提出的i c p ( i n t e r n e tc a c h ep r o t o c 0 1 ) 协议吲以及c i s c oc a c h ee n g i n e 采用的w c c p ( w e bc a c h ec o n t r o lp r o t o c 0 1 ) 协议。这种通信协议可以实现c a c h e 间地单播或多播通信，实现起来相对简便，一般采用树状体系结构，因而可以适应于不同的c a c h e 系统结构。但是随着节点的增加，网络流量非常可观。a d a p t i v ec a c h e 研究小组为网状体系结构设计了基于组播的通信协议。在查询时，消息只在组内和相关组的组间传递，而不必扩散到全网，网络流量要少于h a r v e s t 系统中基于i c p 的多播通信。c r i s p ( c a c h i n ga n dr e p l i c a t i o nf o ri n t e r n e ts e r v i c ep e r f o r m a n c e ) t 3 4 1 、s u m m a r yc a c h e 【3 5 等平面c a c h e 体系结构通过访问目录摘要的方式来实现c a c h e 问的查询通信。针对目录摘要的查询改善了前两种方式查询方式的盲目性，提高了系统的命中率。但是解决目录摘要的更新、维护以及一致性等问题会带来新的通信负荷。燕山大学工学硕士学位论文微软提出的c a r p ( c a c h ea r r a yr o u t i n gp r o t o c 0 1 ) 协议p 刨只需要通过一次h a s h 映射就可以完成查询任务，而且也免除了对目录摘要的维护；由于h a s h 本身的静态特点无法适应网络c a c h e 系统的动态性能，文献 3 7 ，3 8 】针对这一问题提出了一致性散列函数( c o n s i s t e n th a s h ) 的解决方案。清华大学信息网络研究中心的姜彩萍、吉林大学的杨子木等教授通过对集中管理式w e b 缓存系统进行了详细地研究，并给出了相关的性能分析的方法和结果，但是集中式结构会带来新的瓶颈问题。北京理工大学计算机科学与工程系的古志明教授等人，在基于集群的w e b 缓存服务器上引入摘要缓存机制，使系统实现单一缓存映像，达到快速访问的目的，减轻了系统里请求分配器的负担，但是只要缓存副本发生变化，所有代理的摘要都要做相应的更新，保持一致性方面有待继续加强。1 3 课题研究内容及预期目标本文在广泛调研和对大量中外文献分析的基础上，结合当前集群缓存技术发展的前沿，针对本文的研究问题，主要完成以下几个方面的研究工作及预期目标：第一，使用l v s 构造一个w e b 集群缓存系统，该系统的主要功能是为客户提供高性能的代理缓存服务，具有良好的单一系统映像性和可伸缩性，并针对集群缓存系统的特点，对其内部各代理缓存进行详细深入地研究。第二，在缓存副本的存储方面，采用面向站点的存储方案，注意到对象的类型、访问次序等信息的联系，不仅能方便查询，还能更好的实现个性化服务的功能。第三，在缓存副本的管理方面，提出将替换策略和一致性结合在一起的r c a ( r e p l a c e m e mc o n s i s t e n ta r i t h m e t i c ) 算法，以较小的代价从代理缓存中提供更新鲜的资源给用户，充分体现替换和一致性结合起来的优越性；第四，在代理协作方面，通过在系统内部的各代理节点之间使用本文提出的新的通信协作机制n c p c p ( n e wc o o p e r a t i v ep r o x yc a c h ep r o t o c o l l ，来有效减少缓存对象的冗余度和系统内部的通信开销，从而降低节点的处6第1 章绪论理负载，减少响应时间的延迟。代理缓存与代理协作将是本文工作的重点。第五，刘- n c p c p 在理论证明和具体实验中进行评价，并指出今后值得继续研究和探索的问题。1 4 本文的组织结构本论文的组织结构安排如下：第1 章绪论部分对集群缓存技术的现状分析后，直接指出课题研究工作的出发点和目标，剖析研究课题的实质，对当前国内外研究现状进行综述，指出存在的问题以及亟待解决的问题。对本文的研究内容、目标、方法和预期研究结果进行概述，多层次反应本课题的科学意义和实用价值。第2 章剖析集群缓存系统的结构模型，认真分析代理缓存技术的工作原理、分类、目前存在的问题以及评价代理缓存的性能参数等集群缓存系统中的相关理论。第3 章认真总结代理缓存的相关管理技术，包括现有的代理替换策略、一致性策略、代理协作机制等等，为今后的研究奠定理论基础。第4 章结合本集群缓存系统自身的特点，对整个系统并发性，动态文档的过滤，各代理对缓存副本的存储结构与对象的检索，以及本人提出的替换一致性算法r c a 进行详细地设计。第5 章提出新的代理协作机制n c p c p ，并详细设计其工作过程、副本摘要的更新问题等，最后通过公式推导，理论上证明n c p c p 在缓存效率、时间延迟和系统开销方面都优于传统的i c p 和c m s p 。第6 章在本集群缓存系统中实现n c p c p ，并通过具体实验证明n c p c p的整体命中率高于i c p 和c r i s p 。最后对本课题进行归纳和总结，对所提出的问题、任务的解决程度及取得的进展进行表述，指出研究中获得的几个新观点、新思路和新方法，对课题研究的意义和应用前景进行评价和预测，同时指出进一步研究的设想和建议。燕山大学工学硕士学位论文第2 章集群缓存系统的理论概述及分析随着w e b 流量和访问用户的增加，单个缓存的性能越来越有可能成为系统的瓶颈，因此w e b 集群缓存系统的应用具有十分重要的现实意义。2 1集群缓存系统结构模型的剖析基于l v s 的c a c h e 集群的体系结构如图2 1 所示。一。图2 - 1 基于l v s 的c a c h e 集群2 0 】f i g 2 - 1c a c h ec l u s t e rb a s e dl v s 口0 1一般来说，l v s 集群采用三层结构，主要组成部分为：( 1 ) 负载调度器( l o a db a l a n c e r ) 它是整个集群对外的前端机，负责将客户请求发送到一组服务器上执行，而客户认为服务是来自个i p 地址：第2 章集群缓存系统的理论概述及分析( 2 ) 服务器池( s e r v e rp 0 0 1 ) 是一组真正执行客户请求的服务器，执行的服务有w e b 、c a c h e 、m a i l 和d n s ( d o m a i nn a m es y s t e m ) 等；( 3 ) 共享存储( s h a r e ds t o r a g e ) 它为服务器池提供一个共享的存储区，这样很容易使得服务器池拥有相同的内容，提供相同的服务。负载调度器、服务器池和共享存储系统通过高速网相连，如1 0 0m b p s交换网络、m y r i n e t 和g i g a b f f 网络等。使用高速的网络，主要为避免当系统规模扩大时互联网络成为整个系统的瓶颈。负载调度器，一般采用i p 负载均衡技术，可以使整个系统有较高的吞吐率：当一台c a c h e f l 艮务器在本地硬盘中未命中当前请求时，它可以通过相关通信机制来查询其它c a c h e f l e 务器是否有请求对象的副本，若存在，则从邻近的c a c h e 服务器取回该对象的副本，这样可以进一步提高c a c h e 服务的命中率。l v s 集群中实现的三种i p 负载均衡技术分别是v s n a t ( v i r t u a ls e r v e rv i an e t w o r ka d d r e s st r a n s l a t i o n ) 、v s t u n ( v i r t u a ls e r v e rv i ai pt u n n e l i n g )和v s d r ( v i r t u a ls e r v e rv i a d i r e c t r o u t i n g ) 。i p 负载均衡软件i p v s 在内核中的连接调度算法上已实现了以下八种调度算法：轮叫调度( r o u n d r o b i ns c h e d u l i n g ) 、加权轮叫调度( w e i g h t e dr o u n d - r o b i ns c h e d u l i n g ) 、最小连接调度( l e a s t c o n n e c t i o ns c h e d u l i n g ) 、加权最小连接调度( w e i g h t e dl e a s t - c o n n e c t i o ns c h e d u l i n g ) 、基于局部性的最少链接( l o c a l i t y b a s e dl e a s tc o n n e c t i o n ss c h e d u l i n g ) 、带复制的基于局部性最少链接( l o c a l i t y b a s e dl e a s tc o n n e c t i o n sw i t hr e p l i c a t i o ns c h e d u l i n g ) 、目标地址散列调度( d e s t i n a t i o nh a s h i n gs c h e d u l i n g ) 、源地址散列调度( s o u r c eh a s h i n gs c h e d u l i n g ) 。2 2 代理缓存基本理论的概述及分析缓存( c a c h e ) 技术最先应用于p c 机，是一种硬件设备，用于减少c p u 和内存之间的速度差异。其工作原理是基于程序访问的局部性，包括时间局部一眭( t e m p o r a ll o c a l i t y ) 和空间局部性( s p a t i a ll o c a l l y ) 。具有时间局部性的访问行为可以从缓存中得到好处，而具有空间局部性的访问行为会从预取9燕山大学工学硕士学位论文中获益。w e b 缓存技术的思想正是来源于p c 机中的硬件c a c h e 技术。在客户机或专用的缓存服务器上开辟一片硬盘区作为i n t e r n c t 数据传送的缓存区，暂存用户以往访问过的w e b 文档，以备客户下次访问。已有研究人员证明，w e b 文档的受欢迎程度、文档的访问频率和请求间隔三者有密切的关系：越受欢迎的文档，被访问的越频繁，请求间隔也越小。它们之间的关系符合z i p f 规律，即受欢迎程度排在第i 位的文档被访问的概率和i 成反比【3 ”。z i p f 规律可表示为：最( fj = a i( 2 1 )，n、一1式中，q = iy 1 f l ，n 为文档总数。l 百z i p f 规律说明过去经常被访问的文档在将来很可能被再次访问，而最近刚刚访问过的对象比很久以前访问的对象更有可能在不久的将来被再次访问，这也就是所谓的“时间局部性”。根据i n t e r n e t 上的统计资料表明，超过8 0 的客户经常访问的是2 0 的热门站点【4 0 1 。w e b 访问的群体行为符合时间局部性，因此w e b 缓存的实现有充足的现实依据。w e b 缓存的优点总结如下：减少网络带宽的消耗；减少了访问延迟；增加可用性；降低远程w e b 服务器的工作负载；增强网络安全性：提供用私有i p 访问i n t e r n e t 的方法；提供了一种管理手段。由此可见，采用w e b缓存机制无疑是一个投资少、效率高的提高访问速度的方法。2 ，2 1w e b 缓存的分类根据缓存所在的位置，w e b 缓存可分为客户端缓存、代理缓存和服务器端缓存三种j 。( 1 ) 客户端缓存客户端缓存通常是在浏览器上实现的。例如，我们熟悉的n e t s c a p e ，i n t c r n e te 印l o r e r 等都具有缓存机制【4 2 j ，浏览器把一定时期内用户访问过的文档都存储起来，当用户重新访问同样的文档时，就可以从浏览器的缓存中取出，而不需要重新建立h t t p 连接。( 2 ) 代理缓存应用在代理端的缓存也叫做代理缓存服务器，或者简称代理缓存。代理缓存是指：一个既作为服务器又作为客户的中间程序，它1 0第2 章集群缓存系统的理论概述及分析的功能是代替其它客户发起请求，它将这些请求在自己内部作处理，或者将它们传递( 可能要做些转换) 到其它服务器。引入了代理服务器以后，在t c p i p 网络中，通信过程变成：客户端发起请求，该请求被送到代理服务器；代理服务器分析该请求，先查看自己缓存中是否有请求数据，如果有就直接传送给客户端，如果没有就代替用户向服务器发出请求。服务器响应以后代理服务器将响应的数据传送给客户端，同时在自己的缓存中保留一份该数据的拷贝。这样，再有客户端请求相同的数据时，代理服务器就可以直接将数据传送给客户端，而不需要再向服务器发起该请求。代理缓存服务器处在客户机和服务器之间，对于远程的服务器而言，代理服务器是客户机，它向服务器提出各种服务申请；对于客户机而言，代理服务器则是服务器，它接受客户机所提出的申请并提供相应的服务。( 3 ) 服务器端缓存服务器端的缓存机制通常是在服务器上使用内存作为缓存空间，加快服务器的反应能力和增加服务器的吞吐量。当服务器响应用户对某个数据请求后，在内存缓存空间中保留一个副本，下次如果有相同的访问请求，就直接将缓存空间中的副本提供给用户。2 2 2w e b 缓存的比较客户端缓存机制将远程分布式的信息尽量本地化，从而可以加快客户端请求的响应速度。但是由于缓存容量小，网页命中率较低，每个客户机都有自己的缓存，但不能共享缓存数据，造成缓存数据冗余，因此客户端缓存的内容和效果相当有限。服务器端缓存机制的目的不是提高网页访问的命中率，而是为了减少读写磁盘和访问数据库的次数，虽然能降低用户的访问延迟，但对服务器的要求较高，增加了服务器硬件和软件的复杂度。与其它两种w e b 缓存方式相比，代理缓存的目标在于：减少客户机和w 曲服务器间的网络流量，降低对网络带宽的消耗：加速响应，降低耵t p请求的访问延迟；提供信息共享，降低客户机的空间浪费和维护开销。因此代理缓存具有减少网络流量、减少用户访问延迟、减轻服务器的负载、提高w e b 服务的健壮性、能够分析用户的访问模式等显而易见的优点。除此之外，我们还希望它同时拥有快速访问、健壮性、透明性、可扩展性、燕山大学工学硕士学位论文适应性、稳定性、负载平衡、处理异质能力，简单性等性质来更好的满足广大用户的需求。2 2 3 代理缓存的分类代理缓存服务器的分类总的来说可以从以下几方面进行划分 4 3 1 。( 1 ) 被动缓存( p a s s i v ec a c h i n g ) 用户直接发送请求给代理服务器，代理首先检查其缓存内容，若有此对象且没有过时，则将其返回给用户。若已过时，则必须从原服务器上取回最新的对象，再返回给用户。虽然增加了延迟，但是由于更新对象是由客户请求来触发的，因此能有效的利用带宽，减少不必要的网络通信量。( 2 ) 主动缓存( a c t i v ec a c h i n g ) 是对被动缓存的附加，帮助减少用户在刷新w e b 页面时的等待时间。代理服务器观察缓存中的文件，如果文件到了过期时间就会自动发送请求给原服务器，取回最新的文件。虽然代理不等用户请求就重新请求页面，若页面不再使用就浪费了时间和带宽，反而增加了网络上的通信量，但是主动缓存将重新获取w e b 页面的工作放在非高峰时间，因而能有效减少高峰时期内的通信量。( 3 ) 否定缓存( n e g a t i v ec a c h i n g )当代理尝试去解析对不存在或不能被定位或访问的u r l 的请求时候，发生否定缓存。在这种情况下代理缓存否定结果，以便将来对此u r l 的请求，被快速的解析。( 4 ) 层次缓存( h i e r a r c h i c a lc a c h i n g ) 允许信息从靠近或最近的代理服务器取回，从而不必再连接到原w e b 服务器。如果只是单个缓存，那么它失效时可能成为瓶颈。而且单个缓存可用的存储量是有限的，层次型缓存则能够满足可升级性和聚集几个组的大量请求的目的。2 2 4 代理缓存的工作原理的分析代理缓存的工作流程如下：( 1 ) 客户端向代理服务器发出请求，并给出请求的网页地址；( 2 ) 代理服务器首先在本地缓存中查找，如果找到并且网页没有过期，转5 ，否则转3 ：1 2第2 章集群缓存系统的理论概述及分析( 3 1 代理服务器通过i n t e r n e t 向w e b 服务器发出请求，给出客户端希望访问的网页地址；( 4 ) w e b 服务器将该网页内容响应给代理服务器，代理服务器将其拷贝并存储到缓存中，如果缓存中存在过期的网页，则更新；( 5 ) 代理服务器将网页响应给请求的客户端。代理缓存的工作流程如图2 2 所示。图2 - 2 代理缓存的工作流程图f i g 2 - 2w o r k f l o wo f p r o x yc a c h e2 2 5 评价代理缓存系统的性能指标任何技术都存在性能评价问题。代理缓存系统也有其自身的性能评价指标m ，主要有以下几种：( 1 ) 命中率命中率h r ( h i tr a t e ) 是评价代理缓存系统性能的最主要的指标。代理服务器在本地缓存中找到用户所要访问的网页，则称为一次命燕山大学工学硕士学位论文中；反之称为一次缺失。命中率高，说明直接从代理缓存空间获得的网页副本响应的成功率高，从而大大减少代理服务器到w 曲服务器获取网页的次数，降低响应延迟。其计算方法为：h r ：墅( 2 2 )：兰芷!f 2 2 )式中，占，= 害梨戮，掰是请求的所有数。( 2 ) 字节命中率w e b 缓存是以网页为单位的，而网页的大小是可变的，因此不同的网页的命中对代理缓存系统性能的影响是不同的。实际上，用户更希望代理缓存系统能对一些大网页进行缓存，特别是在多媒体的信息访问中，这样可以更加有效的减少带宽的消耗，降低访问延迟。为此引进另一个性能评价指标字节命中率b h r ( b y t eh i tr a t e ) 。它和命中率相似，只是计算单位改为字节数。字节命中率是对命中率的一个补充，主要用来说明代理缓存系统所命中的价值，因此，可用字节命中率来评价代理缓存的空间利用率。其计算方法为：职：至醴：1 s i上一卜u式中，研是请求的所有数，玩= 芑亲絮器，s 是f 次请求的文档的大小。( 3 ) 访问延迟是指从用户发出第一个h t t p 请求开始，到用户接收到该请求的响应为止经历的时间。由于代理缓存系统的目标就是降低访问延迟。因此可用访问延迟这个指标进行评价。代理服务器可能从缓存空间获得网页副本作为响应，也可能将请求转发到w e b 服务器以获得响应。因此，访问延迟应该是以上两种情况的平均值。( 4 ) 空间利用率它是评价代理缓存空间的利用情况。提高缓存空间的利用率意味着代理服务器不必购买更多的存储介质就可以为更多的网页提供代理缓存。然而，对缓存空间利用率的研究还不够。实际上，空间利用1 4第2 章集群缓存系统的理论概述及分析率是命中率和字节命中率的中间参数，可以用它来解释代理缓存系统中命中率和字节命中率可能出现的不一致。2 2 6 代理缓存系统存在问题的归纳要完全实现代理缓存的目标，使其具有相应的性质，达到理想的性能，并非易事。因为代理缓存也有一些缺点，还存在着以下一些问题：第一，代理缓存中的数据需要不断更新，如果缺少一个合适的代理更新机制，客户获得的数据可能是陈旧数据。保证其一致性非常重要。第二，如果代理缓存缺失，额外的处理会增加访问延迟，因此要尽量提高缓存命中率以减少缓存缺失。替换策略的好坏决定了命中率、字节命中率等指标，所以替换策略的研究仍是研究热点。第三，为了保证服务质量，使代理服务器能满足不断增加的访问需求，避免单点失效，有两种解决方法：一是升级服务器硬件，但是成本高且不易扩展；二是采用集群技术，通过不同的代理服务器间相互协作来降低成本，实现资源共享，提高服务性能。这种方法能有效解决单个服务器造成的瓶颈，但是需要更深入的研究代理缓存的体系结构，并不断完善响应的协议和实现技术。第四，有关代理位置、代理路由和动态数据缓存等问题的研究很少，需要进一步地进行研究和解决实际应用中遇到的问题。2 3 本章小结本章首先剖析了w e b 集群缓存系统的体系结构，其次认真总结了系统中代理缓存的相关理论。通过比较，说明代理缓存是w e b 缓存三种方式中最有效的缓存方式。然后具体分析代理缓存的分类、工作原理，进步说明了代理缓存技术成为解决w e b 访问速度慢、服务器负载重和网络阻塞等问题的主流技术的原因。最后给出代理缓存系统的性能评价指标，并指出了代理缓存技术目前还存在的一些问题。燕山大学工学硕士学位论文第3 章代理缓存管理技术的分析代理缓存管理是指代理缓存服务器对本地缓存文档的管理，包括了缓存文档检索、替换算法和一致性校验。当客户请求某个w e b 文档时，代理缓存服务器需要检索自己的本地缓存空间，判断是否已经缓存有该w e b 文档的副本；如果已缓存，则需对该副本进行一致性校验，检查其是否有效；当缓存空间已满或者将近满的时候，服务器必须按照某种替换