(计算机软件与理论专业论文)适用于集群的缓存服务器算法优化.pdf_第1页
(计算机软件与理论专业论文)适用于集群的缓存服务器算法优化.pdf_第2页
(计算机软件与理论专业论文)适用于集群的缓存服务器算法优化.pdf_第3页
(计算机软件与理论专业论文)适用于集群的缓存服务器算法优化.pdf_第4页
(计算机软件与理论专业论文)适用于集群的缓存服务器算法优化.pdf_第5页
已阅读5页,还剩55页未读 继续免费阅读

(计算机软件与理论专业论文)适用于集群的缓存服务器算法优化.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

华中科技大学硕士学位论文 摘要 | 随着因特网的飞速发展和用户的爆炸式增多以及对象或文件大小的增加( 如多媒体 流对象) ,带宽和网络延迟越来越成为人们所关心的问题。低带宽和网络延迟带来的用 户长时间的等待已经达到用户难以容忍的地步。高效的利用有限的带宽,减少用户等待 、 时间至关重要。旷 为了提高系统性能,减少用户等待延迟,许多方法应运而生。传统的解决方法有升 级服务器硬件设施,如:内存与c p u ,在客户端开辟一段缓存等等。但这些却带来了新 的问题,如:增加了费用却不能有效的解决上述问题,对用户不透明,服务器负载也依 然很重等诸多问题。 采用缓存代理服务器已经被证明能有效的减少网络拥塞、延迟和服务器负载。其基 本思想是:在系统缓存中,维护一个即高效又小的搜索结果集,以至于如果用户请求能 直接在该缓存中服务该请求,减少了许多拥塞和延迟。而缓存服务器的核心是缓存置换 算法一当一个请求到来时,如何选择和替换w e bc a c h e 中的页面,从而更有效的服务 客户的请求。 采用集群架构,通过改进缓存置换算法和增加全局缓存的功能,实现了适用于集群 的缓存代理服务器。实验结果表明改进的置换算法有效的提高了缓存服务器的系统性 能,有效的减少了用户等待延迟。 系统地分析s q u i d 一2 4 6 的源代码和流程,了解和掌握其实现的关键技术,并在 s q u i d 一2 4 6 中实现了原型系统。原型系统还支持流协议,实现了流缓存代理服务器的雏 形。 关键词:缓存代理服奔;流协设j 缓存置疾螽法:全局凄篝 华中科技大学硕士学位论文 := = = = # ;= = 一 a b s t r a c t w i t ht h e e x p l o s i v e g r o w t h o ft h ei n t e m e t ,t h e e x p l o s i o n i nt h en u m b e ro f i n t e m e t i n t r a n e tu s e r sa n dt h ei n c r e a s ei no b j e c t f i l es i z e s ,b a n d w i d t h a n dn e t w o r kl a t e n c ya r e m o r ea n dm o r ec o n c e m e d i t sn o ts u f f e r e df r o mt h el o n g w a i tf o ru s e r sd u et ol o wb a n d w i d t h a n d h i g hn e t w o r kl a t e n c y s o i t sv e r yi m p o r t a n tf o ru st od e c r e a s ew a i tt i m ea n du s el i m i t e d b a n d w i d t he f f e c t i v e l y i no r d e rt oi m p r o v es y s t e mp e r f o r m a n c ea n dd e c r e a s eu s e r s w a i tt i m e ,m a n ym e t h o d s c o m e u p o n t r a d i t i o n a ls o l u t i o n sa r eu p d a t i n g s e r v e rh a r d w a r e ,f o re x a m p l e ,m e m o r ya n d c p u b u t m a n yp r o b l e m sa r ey e t i n t r o d u c e dd u et oh i g h c o s t ,o p a c i t y t ou s e r sa n d h i g h s e r v e rl o a d c a c h es e r v e rh a sb e e np r o v e ne f f e c t i v et or e d u c en e t w o r kt r a f f i c ,l a t e n c ya sw e l la s s e r v e rl o a d s i t sb a s i ci d e ai s :m a i n t a i n i n gah i g he f f e c t i v eb u ts m a l ls e to f s e a r c h i n gr e s u l ti n t h es y s t e mc a c h ei no r d e rt or e d u c em u c ht r a f f i ca n dl a t e n c yi fu s e rr e q u e s tc a nb es e r v e d f r o mt h ec a c h ed i r e c t l y b u tk e yt oc a c h es e r v e ri sc a c h er e p l a c e m e n ta l g o r i t h m 一- w h e na r e q u e s ti sc o m i n g ,h o wt oc h o o s ea n dr e m o v et h ep a g eo f w e bc a d l ei no r d e rt os e r v e rt h e c l i e n tr e q u e s tm o r e e f f i c i e n t l y w eu s ec l u s t e rs t r u c t u r e ,i m p r o v ec a c h e m a n a g e m e n ta l g o r i t h ma n d i n c r e a s et h ef u n c t i o n o fg l o b a lc a c h e ,t h e nr e a l i z ec a c h ep r o x ys e r v e ri nt h ec l u s t e rf i n a l l y d u et o u s i n gt h e s e t e c h n o l o g i e s ,w e c a l ls e ef r o mo u r e x p e r i m e n t s t h a to u r a l g o r i t h mi m p r o v e t h es y s t e mp e r f o r m a n c e f o rc a c h es e r v e ra n dr e d u c eu s e r sw a i tt i m e e f f e c t i v e l y a p r o t o t y p es y s t e mi si m p l e m e n t e di nt h es q u i d 2 4 6 ,s ow en e e da n a l y s i si t ss o u r c e c o d ea n df l o wa n dm a s t e rt h ek e y t e c h n o l o g i e s t h i ss y s t e ma l s os u p p o r t ss t r e a m i n gp r o t o c o l i no r d e rt or e a l i z et h e s t r e a m i n gc a c h es e r v e rf i n a l l y k e y w o r d s :c a c h ep r o x ys e r v e r ;s t r e a m i n gp r o t o c o l ;c a c h er e p l a c e m e n ta l g o r i t h m ;g l o b a l c a c h e l i 华中科技大学硕士学位论文 := = = = = = = = = = = = = 日= = = = = = = = = = = = = = = = = = = = 一 1 1 问题的提出 1 绪论 随着因特网的飞速发展和用户的爆炸式增多以及对象或文件大小的增加( 如多媒体 流对象) ,w e b 请求已经成为因特网拥塞最主要的原因【j 】。因此,如果没有好的系统设计, 网络与真实服务器将成为瓶颈。如何高效的利用有限的带宽? 如何减少延迟到用户可以 忍受的地步? 如何有效的减少真实服务器的负载? n s f n e t 从1 9 9 3 年开始进行的网络流量分析项目结果显示,8 0 的网络流量是由w e b 访问造成的,而其中4 0 的w e b 流量由重复性访问造成,并且这- - l :t ;例在不断增大 2 1 。 因此,带宽和延迟问题均暴露无疑。 传统的内容检索模型( 如w e b ,f t p , n n t p , ) 显然是不能解决以上问题,因为许多 用户反复的传输同样的i n t e m e t i n t r a n e t 链接来取同一个内容,并且,用户访问的内容随 着i n t e r n e t i n t r a n e t 的增长越来越远。 采用缓存代理服务器已经被证明能有效的减少网络拥塞、延迟和服务器负载f 3 ) 。其 基本思想是:在系统缓存中,维护一个即高效又小的搜索结果集,以至于如果用户请求 能直接在该缓存中服务该请求,减少了许多拥塞和延迟。而缓存服务器的核心是缓存置 换算法一当一个请求到来时,如何选择和替换w e bc a c h e 中的页面,从而更有效的服 务客户的请求。 本文研究在集群架构下,通过改进缓存置换算法和增加全局缓存功能,实现适用于 集群的缓存代理服务器一一集群缓存服务器。利用集群高可扩展性和高可用性,实现可 扩展和高可用的集群缓存服务器。 1 2 缓存服务器优点 1 ) 减少网络带宽消耗。当缓存服务器从本地缓存中取数据服务客户时,它减少了 本应通过广域网从原服务器获取请求的个数。 1 华中科技大学硕士学位论文 2 ) 减少w e b 延迟。被缓存的对象可立即服务于客户,且缓存服务器相对原服务器 来说离客户更近,因此用户能得到更快的响应。响应时间对于一个在线的w e b 系统来 说是关键。 3 ) 网络更可靠。当原服务器关闭时,许多对象可以从缓存中服务,因此对用户来 说原服务器的关闭是透明的。让用户认为网络很可靠。 4 ) 减少w e b 服务器的工作负载。更少的请求要求从原服务器中获取,从而提高了 动态网页如c g i 请求的吞吐量。 1 3 因特网的缓存结构 如下图1 1 所示,w e b 缓存可以执行在网络的不同位置: 1 ) w e b 浏览器缓存。在客户端,w e b 浏览器通常拥有自己的缓存系统( c a c h e a ) 。 通常该缓存比较小,缓存置换算法通常采用f i f o 或l r u ,该算法很容易实现但效率低。 由于它是最接近用户的缓存,因此如果该缓存命中的话,将提供最短的响应时间。然而, 存储在该缓存中的w e b 对象并没有被局域网中其它用户共享。一个文档可能被不同用 户搜索。 图1 1 因特网的缓存结构图 一。 2 华中科技大学硕士学位论文 :- = = = = = = = = = = = = = = = = = = = ;= = = = = ;= = = = = = = = 2 ) p r o x yc a c h i n g 。一个代理服务器通常位于一个网络的边界,如在一个公司、机 构网关或防火墙,服务许多的内部用户( c a c h e b ) 。它截取所有的来自客户的h 订p 请 求和响应,如果它发现请求的对象在它的缓存中,它就直接将该对象返回给用户。如果 没有发现,该服务器代理用户从原服务器中取出该对象,存储在它的缓存中,同时将该 对象传给用户。因为这种类似h u b 的属性,代理服务器是理想的地方执行缓存与预取。 由于被缓存的对象被所有的局域网用户共享,p r o x yc a c h i n g 的使用节省了带宽,提高 了响应时间,增加了静态w e b 对象的可用性1 4 j 。 3 ) 透明缓存。代理缓存的方式要求w e b 浏览器配置( 如设置i p 地址和端口号) 。 透明缓存通过截取h 1 v r p 请求并重定向到w e b 缓存服务器中。两种透明缓存如图1 1 所 示:交换机透明缓存( c a c h ec ) 和路由器透明缓存( c a c h ed ) 。交换机透明缓存充当 负载平衡器,用于减少开销。路由器透明缓存使用基于策略的路由将请求定向到合适的 缓存。一般来说,交换机更具有诱惑,因为它价格更便宜些。 4 ) r e v e r s e p r o x yc a c h i n g 。一个w e b 服务器通常服务静态文件和动态产生的查询结 果。一个服务器期望能服务更多的请求,且确保服务质量。要达到这个要求,一个代理 缓存系统被按“r e v e r s e ”方式放在靠近w e b 服务器的地方,如r e v e r s e p r o x ys e r v e r 。该 缓存服务器比客户更接近w e b 服务器( c a c h e e ) 。该缓存通常存储最频繁访问的静态数 据,并被优化来更快的服务数据。通过服务大多数的静态数据,原服务器能更多的处理 动态数据。该代理服务器的另一个优点是可以平滑网络拥塞。这在p u s h 缓存中已经被 广泛研究1 5 】。 上述缓存服务器彼此相互独立。它们通常共存且集体提高w e b 访问的整体性能。 在我们的研究中,我们主要研究代理服务器和逆代理服务器,尽管我们的方式- i p a 被运 用在浏览器缓存和其它缓存系统中。 1 4 缓存服务器的研究现状 c a c h e 服务器( c a c h es e r v e r ) 可以是一台普通的p c 服务器加上c a c h e 软件( 如 s q u i d 、i n k t o m i ) 构成,也可以是软硬件系统和一台专门的c a c h e 服务器( 如c a c h e f l o w ) 。 目前较流行的c a c h es e r v e r 主要有以下几种: 一。 华中科技大学硕士学位论文 c a c h e f l o w 服务器现改名为b l u ec o a t 。它是商业专用设备,有自己的软件和硬件, 通过w e b 界面进行操作,使用了专利算法来提高访问速度和命中率,具有高可靠性。其 工作原理为:当它被配置为缓存服务器时那些被优化的设施智能的管理用户的请求。当 一个用户选择一个u r l 地址,请求首先到达b l u ec o a t 的8 0 端口安全设备进行安全认 证与授权。如果来自请求页的对象已经在b l u ec o a t 设备的缓存中,则它们立即服务于 用户。如果对象不在本地缓存,b l u e c o a t 安全设备充当一个用户代理,通过因特网与 原服务器进行通讯。当对象从原服务器中取得,该对象的一个副本被发送给用户,同时, 也在本地缓存该对象来服务所有接下来的请求。整个过程被监控和日志用于报告和计划 目的。b l u e c o a t 具有如下优点:1 ) 它采用专一的w e b 知识体系结构,因而允许企业处 理所有的w e b 请求协议,如:h t t p ,h t t p s ,f t p ,m i c r o s o f ts t r e a m i n g ( m n l s 和h t t p 流) , r e a ls t r e a m i n g ( r t s p 和h t t p 流) ,q u i c k t i m es t r e a m i n g ( r t s p 流) ,m p 3 ,f l a s h 和数 百种其它w e b 对象类型。2 ) 它采用延迟攻击算法( 1 a t e n c y a t t a c k i n g ) ,如对象流水线 算法( o b j e c tp i p e l i n i n g ) 。该算法不是串行的获取对象,而是同时打开许多的与原服 务器的t c p 连接,并行的获取对象。对象被直接发送到用户,使得浏览器尽可能不会超 时。速度提高了5 0 。3 ) 动态自适应性更新缓存的对象,使得本地保存准确的最新数 据,加快响应时间。传统的缓存服务器发送本地缓存对象给用户前,先发送一个“r e f r e s h c h e c k ”给原服务器检查对象是否为最新对象,造成用户忍受一次网络延迟,降低了响 应时间。b l u ec o a t 采用自适应更新算法,通过分析对象的行为,选择一些频繁被访问 的对象进行更新检查。与用户请该对象保持异步,从而不影响响应时间,提高了性能。 i n k t o m i 的t r a f f i ce d g e 是一个智能的、基于内容的服务器,为商业软件。它缓 存和发送所有的富媒体( r i c hm e d i a ) 与传统媒体。它具有以下优点:1 ) 同时发送w e b 内容、流媒体等给许多客户。2 ) 通过在网络边界( 物理上更接近用户) 存储频繁访问 的内容,来提高性能,减少带宽。3 ) 通过缓存静态的和所有主要的流媒体格式在一个 集成e d g e 设备,来减少硬件费用。4 ) 易集成其它协议。 s q u i d 为自由软件,可以运行在多种平台上,与商业产品对比,它的缺点是命中率 和执行效率相对较低。其优点为:1 ) 支持多种协议,如h t t p 。h t t p s ,f t p ,g o p h e r 等; 2 ) 采用单进程实现而没有使用线程包,可移植性和性能好:3 ) 采用置换策略和预取技 一 4 华中科技大学硕士学位论文 术,提高缓存命中率和减少响应延迟;4 ) 开发适用于缓存服务器的应用层文件系统, 提高了i 0 读写性能,服务更多的请求。 w c o l 自从1 9 9 4 年开发以来,一直研究w e b 请求的预取算法的缓存服务器。它采用 预取用户请求页的链接页来实现预取。它被设计为多进程代理系统,支持对称多处理器 系统,但功能很不全,需要改进。 1 5 集群缓存服务器 1 5 1 集群缓存服务器的重要性 集群是一种分布式处理系统,由很多连接在一起的独立计算机组成,像一个单独集 成的计算资源一样协同处理【6 】o 随着网络技术和并行编程环境的发展,集群以价格低、可靠性好、吞吐率高、系统 资源丰富等优点正成为当前并行处理系统研究的热点【7 】。在世界计算机5 0 0 强的排名中, 有1 8 8 台计算机采用的是集群体系结构,百分比为2 7 6 。其中,安装在p i t t s b u r g h s u p e r c o m p u t i n gc e n t e r 的由康柏公司研制的a l p h a s e r v e rs ce s 4 5 ig h z 更是名列第 二【9 】。 缓存服务器要求处理大量的请求,如果这些请求大部分保存在缓存服务器中,则缓 存命中率大大的提高,性能也就大大的提高。特别是对于逆缓存( r e v e r s ec a c h e ) , 缓存命中率要求很高,否则w e b 服务器的负载很重,服务质量和服务请求的数量均会大 大减少。采用集群架构,将集群与缓存服务器有效的结合起来,形成了具有集群优势的 缓存代理服务器。具体有如下优点: 1 ) 提高缓存命中率。采用集群缓存服务器,将各个节点的缓存全部共享,形成一 个巨大的单一的缓存,对于用户来说,好象拥有一个巨大的缓存为其服务,从而缓存命 中率大大提高。 2 ) 提高可扩展性a 随着大量的用户的频繁请求,单个缓存服务器负载会很重,从 而导致服务质量的下降,甚至可能导致不用代理时速度反而会更快些。即使可能该代理 的平均吞吐量很低,但其峰值吞吐量却可能很高,这就需要代理服务器具有可扩展性。 一 华中科技大学硕士学位论文 集群缓存服务器具有集群可扩展性的优点,满足了这一需求。 3 ) 提高可用性。随着用户对i n t e r n e t 的依赖越来越大,用户需要随时访问i n t e r n e t 上的共享资料。因此,除需要可靠的稳定的网络和原服务器外,也需要可靠的稳定的缓 存服务器。在某些情况下,系统的可用性比其扩展性具有更重要的意义。单一的缓存服 务器具有单一失效点,采用集群缓存服务器具有高可用特性,满足了这一需求。 1 5 2 国内外研究现状 集群缓存服务器以其低价、可扩展性好及高可用等诸多优点,成为人们研究的热 点。以下介绍几种缓存服务器。 w h i z z b e ep r o x ys e r v e r 9 是一种基于集群技术的可扩展的代理服务器。它具有如下 特征:1 ) 采用e c c a c h e ( e x t e n s i b l ec o o p e r a t i v ec a c h ee n g i n e ) 技术。其思想是:在 w h i z z b e e 集群的每个节点都贡献出一段内存作为缓存,当集中这些分散的内存片,形 成一个巨大的虚拟文件缓存。当通过i o 读取文件缓存在一个服务器节点的内存中,另 个服务器节点需要该内存时,它采用缓存转发操作而不是磁盘i o 操作提供给需要的 服务器节点。2 ) 采用有效的包路由技术。它采用w i t c h ( w h i z i pt r a f f i cc o n t r o lh o s o 技术减少了集群内的路由延迟。3 ) 可用性好。所有的系统服务被特殊的h e a r t b e a t 协议 监控。当系统或应用程序失效,其备份立即接管并继续运行,因此w h i z z b e e 代理服务 器无单一失效点。4 ) 动态内容缓存。当代理服务器静态命中率很高时,w e b 服务器的 高负载则主要来自动态内容的访问。由于一些动态的内容并不是每时每刻都改变,因此 它们也能被缓存一段时间,从而降低了服务器的负载。w h i z z b e e 代理服务器采用 e c - c a c h e 技术缓存动态内容,粒度为1 秒。 b o r d e r m a n a g e r p r o x y c a c h e c l u s t e r i n g l l o 是另一个提供i s p 服务的公司产品。作为一 个i s p , 需要提供客户快的响应时间和稳定的i n t e r a c t 服务。n o v e l lb o r d e r m a n a g e rp r o x y c a c h e c l u s t e r i n g 采用连接级的容错技术,实现了高可用。 w e b c a c h e c l u s t e r 是b e r n 大学研制的一个具有冗余的w e b 代理服务器集群。 6 华中科技大学硕士学位论文 2 缓存管理算法 缓存,从概念上讲泛指临时存储某些东西的地方。在有限的时间间隔内将上一次的 访问结果l 临时存储到缓存中,下一次访问就可以直接从缓存中得到,而不必到最初的地 方去存取,这样既减少了时延,又减轻了系统负载。缓存技术目前已经应用到计算机的 多个领域,从c p u 中的指令和数据c a c h e ,到内存中的磁盘c a c h e ,再到应用层的文件 c a c h e ,都起着至关重要的作用。本章着重阐述w e b 缓存的管理。 随着i n t e r a c t 的迅猛发展,被访问对象的不断增加,w e b 请求已成为因特网的主要 负载之一。研究表明,大量的用户频繁访问一些热点网站,造成一些热点网站的服务器 负载很重,而其他冷点网站却无人问津。为此,在负载很重的服务器与用户之间加上缓 存显得十分重要。它有如下好处:1 ) 提高服务质量( q o s q u a l i t yo f s e r v i c e ) 。缓存与 用户的距离相对于原服务器而言更近些。因此请求的内容通过更少的路由器到达用户。 减少了包的丢失率和加快了整体服务,减少了用户等待时间。2 ) 网络拥塞的减少。缓 存拥有3 5 的命中率,就意味着请求内容的3 5 成功的被缓存,因此减少了3 5 的请 求造成的网络负载。 缓存管理的核心是缓存置换算法当一个请求到来时,如何选择和替换缓存中的 页面,从而更有效的服务客户的请求。 因此,一种有效的缓存置换算法是衡量c a c h es e r v e r 性能好坏的关键。 本章先描述缓存通用模型和w e b 请求的特性,然后阐述传统的缓存管理算法及相 应的不足,进而提出了我们自己的缓存管理算法,并给予了一些定义和证明。最后,我 们将简单的阐述全局缓存的概念。 2 1w e b 缓存通用模型 本节通过描绘缓存服务器的通用模型,更好的缓存服务器的原理、结构和缓存置换 算法的核心地位a 缓存服务器通常由缓存管理器、置换策略、元数据管理和缓存等构成。 一。 华中科技大学硕士学位论文 := = ;= = = 。;= j = ;= = = 。;= = = = = = = = = = = = = 如图2 1 所示。 l i 。l 远程服 i 客户i 7 l 务器 图2 1w e b 缓存通用模型 缓存管理器是中央控制器,它负责协调所有的操作。元数据保存缓存对象的索引 信息用于快速访问该对象。元数据还保存其它信息,如:最后访问时间,访问频率,这 些信息用于缓存置换决策。与缓存的大小相比,元数据大小可以忽略不记。置换策略是 缓存系统的心脏,它通过元数据信息来决定是否缓存一个新的对象,如果缓存空间有限, 它决定哪些对象应该替换出来为新的对象留出空间。缓存是对象存放的地方。 一个缓存系统位于客户与远程服务器之间,传递信息。下面阐述一下图2 1 中标志 的步骤。 1 一个客户发送一个w e b 页p 的请求给缓存管理器; 2 缓存管理器在元数据中查找对象p ,看是否它在缓存中还是不在。如果在,到第3 步;否则,到第4 步: 3 缓存管理器将对象p 从缓存中取出放入内存,到第1 0 步; 4 缓存管理器从远程服务器中请求对象p ; 5 远程服务器发送对象p 回来: 6 缓存管理器与缓存策略进行协商; 7 缓存策略从元数据中收集关于缓存对象的必要信息; 8 缓存策略作出决定是否允许对象p 缓存。如果允许且缓存空间不够,缓存策略替换 出些对象用于缓存新的对象: 9 如果不允许对象p 缓存,则到第1 0 步。否则,缓存管理器将对象p 缓存: 华中科技大学硕士学位论文 一= = = = = = ;= = ;= = = = = _ ;= = = = = = = = = = = ;= = 一 1 0 缓存管理器更新元数据用于与缓存状态同步; 1 1 缓存管理器将对象p 发送给客户。 2 2w e b 请求的特性 我们需要研究w e b 请求的特性,从而寻找出更适合其特性的缓存管理算法。 1 ) w v o v 的内容请求与计算机内存系统的访问有很大的相似之处【川:即w e b 请求 的局部访问原理。w e b 请求同样具有时间局部性和空间局部性的概念。 所谓时间局部性,指该用户在一段时间内访问某网页,则在下一段时间内极可能访 问该网页,这就是时间局部性原理。在1 9 9 6 年,a l m e i d a e ta 1 分析w e b 日志阐述了时 间局部性【1 2 1 。在1 9 9 7 年,c a o 和i r a n i 在d e c 代理t r a c e s 中观察到时间局部性特征t b l 。 在1 9 9 8 年,r i z z oe la 1 从意大利p i s a 大学收集的代理日志中观察到这一特性【1 4 】。 所谓空间局部性,指该用户在某一时间段内访问网页的某个对象或链接,则在下一 时间段内访问该网页的其它对象或链接的概率很高,这就是空间局部性原理1 1 2 】【1 5 】f 1 6 1 。 例如,w e b 内容的访问通常包括h t m l 页和许多图片等。对于一个可缓存的h t m l 页, 这些图片的变化很慢1 7 】【1 8 l 【1 9 1 。因此,如果个h t m l 页被客户请求,则相应的图片文 件被访问的概率很大。 2 ) w w w 的内容请求与用户对视频服务器的电影的请求有很大的相似之处:即热点 效应。根据i n t e m e t 上的统计表明,超过8 0 的请求经常访问的是2 0 的网站内容嘲。 研究表明,w e b 请求服务符合z i p f - l i k e 定律【2 0 】( 用户对电影服务器的请求符合z i p f 规律) 。 因此,如果有足够的缓存来保存这2 0 的网站内容,缓存命中率将达到8 0 以上。 3 ) w e b 请求对象大小不等,可以为几十k 字节,也可以为几百兆字节。对于操作 系统或数据库的缓存,由于缓存的对象大小一致,因此可以计算出最优的置换算法 著名的o t t l i n e 算法【2 ”。而在w e b 缓存中,对象是可变) k d , n ,确定最优算法被确定为 n p 难问题【i ”。而这对于实现好的缓存管理算法是关键。 4 ) 一个用户在相当长的一段时间内对某个网站的热衷可能会在另一段时间内被其 它新发现的更迷人的网站所代替。也就是说,用户对某个网站的热衷是有限的。 9 华中科技大学硕士学位论文 5 ) 多个用户在相当长的一段时间内对某个网站的热衷可能会在另一段时间内被其 它新发现的更流行的网站所代替【2 2 】。也就是说,某个网站的流行时间是有限的。例如, 某实验室拥有新的任务,临时组织所有人搜索某一领域的国内外研究状况,他们也许花 了好几天搞定,以后便继续进行各自的研究。这样也许某一领域方面的网站在这些天成 为热点网站。但这些天过后,就没什么人访问了。 根据1 ) 可知,用户最近访问的页需要保存在缓存中。而且可以根据1 ) 的空间局 部性原理,采用预取策略,将下一可能访问访问的页或链接也保存在缓存中。根据2 ) 可知,热点网页需要缓存。因此缓存置换算法不应置换出访问频繁的网页。根据3 ) 可 知,缓存管理算法需要考虑到对象的大小,应该置换出大的对象,用以提供更多的空间 缓存其它的对象,提高缓存命中率。特性4 ) 似乎与特性1 ) 相违背,其实不是。特性 1 ) 是在一段时间内,该时间相对特性4 ) 的时间短。特性4 ) 告送我们某个网页不能永 远的被该用户频繁的访问,这是一种趋势。因此,如果在一段时间内没有被用户访问, 即可替换出缓存。特性5 ) 是热点网站特性的特例,称为假热点特性。由于该网站在一 段时间内被一些用户频繁访问,使得缓存服务器误以为该网页符合特性2 ) ,因此将其 保存在缓存服务器中相当长时间而没有被替换。我们需要采用预测算法将其尽早发现并 替换出缓存中。 w e b 请求具有的上述特点决定了需要探索符合实际情况的有效的缓存管理算法。 当然,缓存管理算法也不能完全按照上述5 个特性来实现,因为还要考虑到缓存服 务器从远程真实服务器获取网页或对象的代价。如果某对象所在的真实服务器离缓存服 务器很远或者某段网络的原因造成获取该对象的开销很大,就必须将该对象缓存起来, 避免下次耗费同样的代价。即使获取相同大小的对象消耗的时间也可能相差很大。这中 可变代价的形势导致了缓存管理算法的调整。c - r e e d y d u a l 算法j 是用于解决对象大小 一致、但代价不一样的页面置换问题。 因此,国内外研究了许许多多的缓存管理算法,有基于l r u 算法的,有基于键值 的( 通过将对象的访问频率大小等叠加求得) ,有基于代价的,有基于预测的等等。下 面我们将分别加以介绍。 一一 1 0 华中科技大学硕士学位论文 := = = = = = = = ;= ;= = = = = = = = = = = = 2 ;= = = = = 2 2 3 传统的缓存置换算法 2 3 1 基于键值的缓存置换算法 大多数缓存置换算法均可被认为是基于键值的策略。其思想是根据一些键值来排序 文档。当主键值相等时,第二键值被使用。这些策略首先替换出最小键值的对象,然后 替换次小的键值,直到缓存空间足够容纳新的对象。由于它们遵循排序替换的原则,因 此比较容易实现。 些缓存算法概括如下,表2 1 总结了他们使用的键值。 表2 1 基于键值的策略比较 算法主键次键第三键 l r u最后访问时间 l f u访问频率 l f u - a g i n g访问频率 对象年龄 s i z e对象大小最后访问时间 l o g ( s i z e )l o g ( s i z e )最后访问时间 h y p e r - g访问频率 最后访问时间对象大小 p r最后访问时间对象大小 l l f下载时间 h y b r i d函数值 g d - s i z e函数值 g d s f 函数值 l r u 算 垂一最经典的算法,经常按最后访问时间排序组成l r u 链表,增加和移去 链表中的对象需要o ( 】) 常数时间。它替换出最近最少访问的对象,因此比较适合虚拟 内存系统。但是,它一般针对访问的对象大小是恒定的,不符合w e b 请求的特性【1 3 】【2 4 1 。 一 1 l 华中科技大学硕士学位论文 l f u l f u 置换访问次数最少的对象。这种策略保存更流行的w e b 对象,替换出 最少使用的对象。l f u 策略忍受c a c h ep o l l u t i o n :如果一个流行的对象变得不再流行,它 将仍然保留在缓存中很长一段时间,阻止了其它新的流行的对象替换它。传统的l f u 策略并没有提供任何机制解决这个问题。 l f u a g i n gp 0 1 i c y 一一种l f u 策略的变种。它同时考虑了对象的访 问频率和对象驻留在内存中的年龄。该年龄策略解决了c a c h e p o l l u t i o n 问题。但没有考 虑到缓存对象的大小。 s i z e 2 4 1 置换出最大的对象。通过替换出拥有最大大小的对象,该策略提高了缓存 命中率,但牺牲了字节命中率。该算法的一个缺点是一些对象在缓存中,却没有被访问。 它也具有缓存污染问题【1 3 1 。 l r u t h r e s h o l d 2 5 】与l r u 算法一样,除了它没有考虑缓存对象大小大于一个阀值。 l o g ( s i z e ) 2 5 1 替换出l o g ( s i z e ) n 删g 。如果对象具有相同的大小,它替换出最 近最少使用的对象。 l r u m i n 2 6 】:它首先定义一个对象大小s ,这个大小不适合缓存在c a c h e 中。当有对 象大于s ,则替换出该对象。如果没有,则按照l r u 算法替换出对象大小为s 2 的对 象,s 4 的对象,直到缓存空间能够满足新的对象。它是l r u 的改进,考虑到对象的大 小,但没有考虑到流行度等。 h y p e r - g 2 4 1 是l f u 算法的提高,但它还考虑了最后访问时间和对象大小。 p i t k o w r e c h e r 2 4 】移去最近最少使用的对象。如果所有的对象在同一天被访问,移去 最大的对象。 l o w e s t - l a t e n c y - f i r s t 2 7 1 目的是最小化平均延迟。它记录对象最近下载时间,移去下 载时间最小的对象。 h y b r i d 【2 7 l 为每个对象定义了一个函数,拥有最小函数值的首先被替换。对于一个位 于服务器s 的对象p 依赖以下参数:c s ,连接到服务器的时间;b s ,到服务器的带宽: n p ,p 在缓存中被访问的次数;z p ,对象p 的大小。该函数定义为:( ( c s + w b b s ) 州p ) w n ) z p ,其中,w b ,w n 均为常数。 一。 1 2 华中科技大学硕士学位论文 = = = = = = ;= = = = = = = = = = = = = = = = = = = = = = = = = ;= ;= = 一 g d s f 2 s 1 通过提供一个频率计数来提高g d _ s i z e 算法。其计算公式为: k ( d ) = l + f ( d ) c ( d ) s ( d ) ,其中:f ( d ) 为文档对象d 的访问计数。如果对象d 在缓存中命 中,则:f ( d ) = f ( d ) + 1 。c ( d ) 为将该对象放入到缓存中的代价,当c ( d ) = 1 时,g d s f 取得 最好的缓存命中率,这就是g d s f ( 1 ) 算法。当c ( d ) = s ( d ) 时,g d s f 能取德最好的字节 命中率,这就是l f u d a 算法【2 9 】。s ( d ) 为对象d 的大小。 2 3 2 基于预测的缓存置换算法 由于w e b 请求具有一定的可预测性,因此研究基于预测的缓存置换算法成为热点。 该算法的原理是将即将访问的对象保留在缓存中,而将未来不访问的对象或很长时间才 会访问的对象替换出缓存中,从而提高缓存的命中率。如果该算法预测相对准确,则命 中率会很高,而且有利于根据该算法做相应的预取工作,达到更好的系统性能。如果该 算法预测不准确,则会适得其返。常用的基于预测的缓存置换算法有以下几种。 基于马尔可夫模型的算法。该算法仅仅基于时间的预测,因此预测的准确性不高。 在 3 0 】 3 1 中研究表明,预测的准确性仅为大约3 0 左右。 基于路径的预测模型。1 9 9 6 年,k r o e g e r 和l o n g 3 2 】通过追踪文件打开事件来研究文 件系统日志。其缓存命中率比l r u 平均高1 5 。1 9 9 8 年,s c h e c h t e re ta 1 1 3 3 j 通过构造路 径文件来预测用户的下一请求。它是根据用户先前的请求序列来预测下一个请求。结果 表明:在最好情况下,其预测准确性为5 3 7 6 ;在最坏情况下,其预测准确性为 4 0 4 5 。 n g r a m 预测算法。它是一种基于路径的预测算法,由s ue ta 1 在2 0 0 0 年提出的【1 6 】。 他们通过考虑历史访问记录中最长的匹配来预测用户的下i r l 个请求。如果没有k 长度 的模式被匹配,则依次匹配k - 1 ,k - 2 ,l 长度的模式。当m = l 时,其准确性为1 4 , 。 2 3 3 传统算法的缺陷 施 一 一 一 排 一 竺 僦 一 酡 一 乳 一 中 一 ;呈 一 孵 一 。 蟀 一 。 貅 一 腑 一 嬲 鞠 一 龇 一 麟 一 上 一 腊 一 华中科技大学硕士学位论文 发展,要么只考虑提高对象命中率,导致字节命中率很低( 如g d s f ) ;要么只考虑提 高字节命中率,导致对象命中率很低( 如l f u d a ) ,并没有考虑到在对象命中率与字节 命中率之间求得一种平衡。然而,随着w e b 对象越来越大和本地缓存空间的有限性, 字节命中率变得越来越重要,有时重要性还超过对象命中率,因为外部的网络带宽是有 限的资源,它通常是稀少的、昂贵的。 对于基于预测的缓存置换算法也没有考虑到如何提高字节命中率,它只是盲目的根 据历史日志信息猜测出下一个请求即将访问的对象。对于基于路径的预测算法,它要求 缓存服务器启动时根据历史日志信息提炼出有用信息保存在内存中,显然占据了缓存服 务器的许多内存,造成了性能下降,有时反而使得系统整体性能下降。而且,缓存服务 器还必须每隔一段时间就要重新根据日志信息修改内存的有用信息,否则其预测的准确 性也会慢慢降低,这就是所谓的数据挖掘算法,势必导致系统负载增加,系统性能下降。 为此,我们将基于预测的算法与基于键值的算法结合起来,并力求在对象命中率和 字节命中率之间找到一个平衡,同时提高字节命中率和对象命中率,提高整体性能。 2 , 4 新的缓存管理算法 对于无限缓存,对象命中率无比重要,字节命中率一无是处。对于有限的缓存,且 所要缓存的对象相差万里,字节命中率与对象命中率同等重要。然而,有些算法以为追 求对象命中率为目标而忽略字节命中率。 根据以上分析,我们对g d s f 和l f u d a 算法进行改进,力求在对象命中率找到一 个平衡,从而使缓存服务器的性能得到提高。为此,我们提出以下几种算法。 2 , 4 1 算法1 :g d f _ l o g s 算法 由于g d s f 具有较高的对象命中率,而l f u d a 具有较高的字节命中率,因此,本 算法考虑将其两者结合,得到公式2 1 ,如下所示。 一一 1 4 华中科技大学硕士学位论文 磁= ( l + f i * c i lfc 1 0 s ? 聚s & s o ) ,c 蝴, “ i( i s c ,如果对象i 的大小超过一常量 k ( i ) l + f ( i ) + c 0 ) l o g s ( i ),计算键值 e 1 s e k ( i ) l + f ( i ) + c ( i ) s ( i ) e l s e ,如果对象i 不在缓存中 w h i

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论