（通信与信息系统专业论文）基于web日志数据挖掘的web缓存策略研究.pdf

武汉邮电科学研究院硕士学位论文 摘要 由于接入i n t c r n e t 的用户数量剧增以及w c b 服务和网络固有的延迟，使得网 络越来越拥挤，用户的服务质量( q o s ，q u a l i t yo f s c r v i c , e ) 得不到很好的保证。 现在的服务器普遍都使用缓冲机制。它利用w w w 访问的时间局部性，将曾经访 问过的文档保存在高速缓存中，避免向本地硬盘或者其他服务器发送请求，从而 加快服务器端的响应速度。 本文发现越来越多的缓存技术开始考虑用户的访问模式以及大量的日志中存 在的知识。随着w e b 数据挖掘技术的发展，我们可以充分的利用这一技术，将日 志中隐藏的模式挖掘出来应用到缓存策略中，提高缓存的命中率以及服务器的响 应速度。本文介绍一种应用w e b 请求预测模型的智能w e b 缓存算法；这种算法是 对w e b 和代理服务器的l r u 策略的拓展，使其对使用数据挖掘技术从w e b 日志 数据中提取出来的w e b 访问模型敏感。 我们主要研究了使用决策树的方法。新算法的试验结果显示，在点击率上它 比现有的基本l r u 缓存技术有了显著的提高。在本文中我们分析了许多现有的缓 存策略的特性。结合w e b 代理服务器业务流的特点，提出了一个基于o r c l 算法 的新的缓存替换算法o r s 2 。 关键词：w e b 缓存；日志数据库；数据挖掘；关联规则；决策树 武汉邮电科学研究院硕士学位论文 a l t h o u g ht h es p e e do fn e t w o r kh a sb e e ni m p r o v e dc o n s i d e r a b l yi nr e c e n ty e a r s ，t h e r a p i de x p a n s i o no fi n t e r n e tu s e r s ，t h ei n h e r e n tc h a r a c t e r i s t i c so fd e l a yi nt h en e t w o r k a n dt h er e q u e s t r e s p o n s ew o r k i n gm o d eo f w w ws t i l lm a k et h en e t w o r kt r a 街cv e r y s l o wa n dg i v en og u a r a n t e eo nt h eq u a l i t yo fs e r v i c e n o wt h ew e bs e r v e ru s e st h e m e c h a n i s mo f c a c h ec o m m o n l y i ts a v e st h ed o c u m e n t st h a th a v eb e e nv i s i t e di nt h e c a c h eb yt h eu s eo f t h ei d e a lc h a r a c t e ro f t h el o c a lc h a r a c t e ro f w e ba c c e s st i m e ，t h u s a v o i d i n go f t h er e q u e s tt ob es e n tt ot h el o c a lh a r dd i s ko ro t h e rw e bs e r v e r , a n d i n c r e a s i n gt h er e s p o n ds p e e do ft h es e r v e r m o r ea n dm o r ec a c h et e c h n o l o g ys t a r t s c o n s i d e r i n gt h ep a t t e r no fu s e ra n dt h ek n o w l e d g ei nt h ev a s tw e bl o g w i t i lt h e d e v e l o p m e n to ft h ew 曲d a t am i n i n g , t h em i n e dp a t t e rc a l lb eu s e df o rt h ew e bc a c h e ， a n dt h eh i tr a t eo f t h ec a c h ec a l lb ei n c r e a s e d w ei n t r o d u c ei n t e l l i g e n tw e b c a c h i n ga l g o r i t h m st h a te m p l o yp r e d i c t i v em o d e l so f w e br e q u e s t s ；t h eg e n e r a li d e ai st oe x t e n dt h el e a s tr e c e n t l yu s e d ( l r u ) p o l i c yo fw e b a n dp r o x ys e r v e r sb ym a k i n gi ts e n s i t i v et ow e ba c c e s sm o d e l se x t r a c t e df r o mw e bl o g d a t au s i n gd a t am i n i n gt e c h n i q u e s f o rt h i sw o r kw es t u d yo nd e c i s i o nt r e ei np a r t i c u l a r t h ee x p e r i m e n t a lr e s u l t so ft h en e wa l g o r i t h m ss h o ws u b s t a n t i a li m p r o v e m e n to v e r e x i s t i n gl r u - b a s e dc a c h i n gt e c h n i q u e s ，i nt e r m so fh i tr a t e i nt h i sp a p e rw ea n a l y z e f e a t u r e so fm a n ye x i s t i n gc a c h i n gs t r a t e g i e s c o n s i d e r i n gc h a r a c t e r i s t i c so fd i f f e r e n t w e bp r o x yw o r k l o a d s ，w ep r o p o s ead a t a - m i n i n gc a c h i n gs t r a t e g yc a l l e do r s 2 ，w h i c h b a s e d o n o r c l k e yw o r d s ：胁6c a c h i n g ；l o gd a t a - b a s e ；d a t am i n i n g ；a s s o c i a t i o nr u l e s ；d e c i s i o n t r e e s 武汉邮电科学研究院硕士学位论文 1 1 w w w 的现状 第一章绪论 i n t e r a c t 正以迅猛的速度发展，在世界前5 0 0 强公司中，8 0 以上的公司都有 自己的w e b 站点，一半以上的公司已经实现了i n t r a n c t ，并在公用w a n 上存放图 文并茂的数据，而且在未来的几年里，w e b 用户数量仍将飞速增长。w e b 访问需 求的不可控制的增长将需要为满足带宽需求付出巨大的努力【l 】。据统计，i n t e r a c t 上8 0 的流量是由w w w 产生的，而超过8 0 的用户重复访问着2 0 的w w w 信 息资源，缓存技术也就应运而生。缓存技术利用网络共享机制，其目的就是要减 少网络中冗余数据的重复传输，并使之最小化，将重复的数据由本地缓存服务器 直接发送给用户，从而达到提高请求响应速度、节约带宽资源的目的。 随着用户对上网速度的要求越来越高，相对于新的应用来说目前的网络容量 带宽日渐不足。一些著名的w e b 站点( 例如y a h o o ) 试图通过在全球建立镜像站 点、进行大规模的网络扩容等方法来解决带宽不足的问题，但建立足够多的靠近 所有用户的镜像站点代价不菲，而且对大部分w e b 站点来说，建立镜像站点是根 本无法做到的，同时镜像站点的管理( 比如数据同步问题) 是很困难的。任何行 之有效的解决方案必须能够存储大量来自远端w e b 站点的网页，并能很快的提供 给本地用户，而且要求管理的工作量较小；同时这种方案还必须能自动决定哪些 网页需要存储在本地缓存服务器，而哪些页面又不需要存储。明显地，有存储价 值的网页将会随时间的变化而变化，本地用户的访问模式( 习惯) 在极大程度上 决定当前需要存储的页面。简单的说，就是要将大量远端的有效w e b 页面存储在 本地缓存服务器中，以供后续用户访问。即网络高速缓存是一个可行的有效解决 武汉邮电科学研究院硕士学位论文 方案。但是现在也有很多人认为通过网络扩容就能很好的解决这个问题。事实上， 网络扩容不仅所需的花费费用昂贵，并且对于w w w 这种特定的应用，网络扩容 根本就无法很好的解决其中的某些问题，比如d n s 查询延时、服务器的访问负载、 服务器响应延时等。因此采用高速缓存技术是一项经济有效的解决方案，是大中 型企业、大学、政府机关等单位提高网络访问速度的重要手段。 1 2 为什么w e b 用户要等待 相信每个曾经浏览过w w w 的人都有这样的经历：当点击某个链接后，接下 来也许是一段漫长而痛苦的等待，然后才看见请求的主页缓慢的出现在计算机屏 幕上。网络上的延迟问题受诸多因素的影响。首先，w e b 服务器需要花费一定时 间去处理一个请求，显然在超负荷运转或磁盘速度比较慢时要花更多的时间 原来人们一直认为是由于w e b 服务器负载过重而最终导致网络的长时间延 迟，但s t e p h e nm a n l e y 等人排除了这一观点 2 1 。他们通过对w 曲服务器上的日志 记录分析发现，即使在最繁忙的时段，对于小于8 k 文件( 不需要再拆成更小的包， 从而避免了传输控制中的频繁确认) 的请求的处理时间也不到1 秒钟；大约5 0 这样的请求的处理只需不到1 毫秒的时间，因而服务器对这种小文件的处理不会 引起用户所能感受到的巨大的网络延迟。对于大于8 k 的文件，记录表明延迟时间 从5 0 毫秒到1 0 分钟，这样用户感受到了等待时间。但是延迟除了包含了网络和 用户的因素之外，还应考虑传输文件的大小不同( 1 0 m b 的文件显然比1 m b 的文 件需要更长的时间) ，因而不能仅从时间上得出结论。于是他们使用了另一个衡量 标准字节延迟( 用户收到一个字节的平均所需时间) 来分析这一现象。通过 对负载不同数量级的服务器的调查发现，这些服务器的字节延迟分布基本相同， 因而可以认为用户感受到的网络延迟不能归于服务器因素。他们在研究中还考虑 了服务器上c g i 业务的影响，发现没有一个c g i 的响应超过8 k ，前面已经说过， 2 武汉邮电科学研究院硕士学位论文 这样的请求不会造成服务器过长的处理时间。以上的一系列分析得出的结论是： 用户所感受到的不愉快的等待不是由服务器负载过重的。 其次，w e b 客户端程序( 浏览器) 如果不能快速的对取回的数据进行分析并 将结果显示在用户面前，也会增加用户的等待时间 第三，文档的传输时间还与网络的带宽有关，理想情况下因为在带宽为1 m b p s 的网上传输1 m b 的文件至少需要8 秒钟 第四，网络的延迟也取决于网络的传播延迟( p r o p a g a t i o nd e l a y ) ；最后，由网 络协议的不完善而造成的延迟也是需要考虑的( 我们可以为此提出很多f i e ) ，例如 h t t p 协议要求对于一个h t m l 文档中的每个传输对象都要单独建立一个t c p 连 接，这不可避免会引起一些不必要的开销。 由机器或网路自身能力造成的延迟可以通过购买速度更快的计算机或使用宽 带计算机网络加以解决，由协议造成的延迟也可以通过修改协议而得到改善，但 是由网络所跨越的物理距离和光速共同决定的传播延迟是客观存在的，因而没有 办法降低。 1 3 研究的意义 本论文提出的一种智能缓存技术可以在高速w e b 里获得应用，解决现有缓存 的效率低下的问题。 1 4 研究要点 本文将首先简要介绍w e b 缓存的相关基础知识。在第二章中我们将简要介绍 h t t p 协议以及w w w 缓存技术，并将简要介绍缓存替换算法的工作过程以及当 前已有的主要替换算法。 接下来在第三章中我们将重点提出一种独特的基于数据库技术的数据w e b 挖 3 武汉邮电科学研究院硕士学位论文 掘应用：它是一种智能缓存结构的拓展，能够根据用户的访问模式的改变来调整 其行为。这种使用模式或模型是依靠数据挖掘技术，从记录在日志文件中的历史 访问数据中提取出来的。 。 如果数据挖掘的目的是为了发现隐藏在数据里的规律和模型，那么w e b 挖掘 的目的则是为了发现在w e b 资源的结构和内容中的规律和模型。更精确一些讲， 这种方法是通过使l r u ( l e a s tr e c e n t l yu s e d ) 对从w e b 日志数据中提取出来的 w e b 访问模型敏感来达到对l r ij 这种被w e b 和代理服务器使用的缓存替换策略 拓展的目的。 与许多文献中介绍的l r u 缓存策略的变种相比较而言，我们的研究具有一个 特性：它能够根据使用模式的变化作出自适应的调整。而这种模式的变化对w e b 而言是很普通的。这是因为我们提出的缓存策略关于数据挖掘模型是变参的，为 了跟踪最近的过去的轨迹，这个参量能够被周期性重新计算。 我们将采用决策树( d e c i s i o nt r e e s ) 的数据挖掘技术，开发基于w e b 日志的 决策树。这个模型能够根据给定的对w e b 对象a 的请求，对下一次对a 的请求给 出参数值的预测。这种预测是基于w e b 日志中所包含的历史数据的预测。 该技术的先决条件是日志数据的数据库的设计。因为原始的日志文件无法满 足数据挖掘的先决条件。因此我们设计了一个全自动的获取过程，它能过将日志 数据转换成适用于智能缓存分析需要的数据集市。在数据集市中，为了进行数据 挖掘分析，w e b 日志信息被清理、过滤和重组；比如：引入了新的属性，丢失的 属性值得到了估算。 作为知识发现过程的最后一步，在第四章中，我们将设计一个w e b 缓存参考 模型用以评估用数据挖掘提取出来的模型。这个模型的结构仿真了一个缓存，并 且对替换策略是变参的，它支持不同替换策略的评估和对比。在考虑两个选定的 标准：点击率和权重点击率的同时，还将被请求实体的大小纳入了考虑的范围。 4 武汉邮电科学研究院硕士学位论文 1 5 本章小结 本章首先简要介绍了w w w 的现状及其存在的问题，然后对w e b 用户等待的 原因进行了分析，最后对本文要讲述的研究课题进行了简要的介绍。 5 武汉邮电科学研究院硕士学位论文 第二章w w wc a c h e 技术概述 2 1 h t t p 协议概述 2 1 1 h t t p 协议概述 h t t p ( h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) ，即超文本传输协议。w w w 服务使用的主 要协议就是h t t p 协议。h t t p 是一个属于应用层的面向对象的协议。该协议描述 了在h t t p 服务器( 即w e b 服务器) 和m t p 客户端( 即w e b 浏览器) 之间如何 进行通信。h t r p 协议于1 9 9 0 年提出，经过十几年的使用与发展，得到了不断地 完善和扩展。目前在w w w 中使用的主要是h i t p 1 0 ( r f c l 9 4 5 ) 的第六版和 h t t p 1 1 ( i 强c 2 6 1 6 ) 。 h t t p 协议是基于请求回应范式的。一个客户机与服务器建立连接后，发送 一个请求给服务器，服务器收到客户机的请求后，先分析客户机的请求，然后将 客户机请求的内容返回给客户机。 客户机请求消息一般由请求行、消息头和消息体组成，而请求行一般由请求 方法、u r l 地址、h t t p 协议版本号三部分组成。请求行标识了客户请求的对象 以及h t t p 协议的版本信息；消息头则告诉了w e b 服务器怎样解释本次请求，主 要包括用户可以接受的数据类型、压缩方法和语言等信息；消息体表示请求或应 答对象本身，有些请求的消息体可以为空。请求行和消息头之间用c r l f ( 回车加 换行) 隔开，而消息头和消息体之间用空行隔开。比如访问百度主页 w w w b a i d u c o r n i n d e x h t m ，那么其客户机的请求消息格式如下： g e t i n d e x h t mh 1 t p ，1 1 h l n r e q u e s tm e t h o d ：g e t r e q u e s t u r i ：i n d e x h t m 6 武汉邮电科学研究院硕士学位论文 r e q u e s tv e r s i o n ：h t t p 1 1 a c c e p t ：i m a g e g i t ：i m a g e x - x b i t m a p ，i m a g e j p e g , i m a g e p g p e g , a p p l i c a t i o n x - s h o c k w a v e f l a s h ，a p p l i c a t i o n v n d m s - e x c e l ， a p p l i c a t i o n v n d m s p o w e r p o i n t , a p p l i c a t i o n m s w o r d ，a p p l i c a t i o n x s i l v e r l i g h t , i a c c e p t - - l a n g u a g e ：z h - c n r k n u s e r - a g e n t ：m o z i l l a 4 0 ( c o m p a t i b l e ；m s i e6 0 ；w i n d o w sn t5 1 ；s v i ；n e t c l r2 0 5 0 7 2 7 ；i n f o p a t h 2 ) m h o s t ：w w w b a i d u 。跚驴国 c o n n e c t i o n ：k e e p - a l i v e f i n 驴l 詹 请求行中的请求方法描述了指定资源( i j i 也) 中应该执行的动作，常用的请 求方法有g e t 、p o s t 、h e a d 、d e l e t e 、o p t i o n s 、t r a c e 和p u t 等。具体 的请求方法同时也在一定程度上决定了该请求返回的w e b 对象是否可以缓存，请 求方法以及该请求返回的w e b 对象是否可以缓存的关系如表2 1 所示。 表2 1 请求方式与该请求返回的b 对象是否可以缓存的对应关系 请求方式是否可以缓存 g e t 一般可以缓存 h e a d 一般用来更新缓存的时间戳 p o s t 当回应消息的h t t p 包头中明确允许缓存时才可以缓存 d e l e t e 一 一般不被缓存 0 ”i o n s一般不被缓存 硼艮c e 一般不被缓存 p u t 一般不被缓存 服务器回应消息一般由回应行，消息头和消息体组成，而回应行一般由h t t p 协议版本号、状态码和原因叙述组成。回应行和消息头之间一般用c r l f 隔开， 而消息头和消息体之间一般用空行隔开。比如上例中访问百度主页，服务器端的 7 武汉邮电科学研究院硕士学位论文 回应消息为： h t t p 1 12 0 0o k f l n， d a t e ：w e d ，0 3s e p2 0 0 80 8 ：2 7 ：5 6g m t k f l n s e r v e r ：b w s 1 o k 6 n c o n t e n t l e n g t h ：1 7 1 5 m c o n t e n t - t y p e ：t e x t h t m l k f l n c a c h e - c o n t r o l ：p r i v a t e v i l e x p i r e s ：w e d ，0 3s e p2 0 0 80 8 ：2 7 ：5 6g m t 挑a c o n t e n t - e n c o d i n g ：g z i p f l n s e t - c o o k i e ：b a i d u u 3 = 6 0 4 d 1 0 0 9 e d e 2 6 8 3 6 f c 7 c 1 a 5 d 4 8 3 f c d 3 0 ：f g = - 1 ； e x p i r e s = w e d ，0 3 - s e p - 3 80 8 ：2 7 ：5 6g m t ；p a t h = ； d o m a i n = b a i d u c o m f l n p 3 p ：c p = , - o t id s pc o ri v ao u ri n dc o m r ：i l ， 驴幻 c o n t e n t - e n c o d e de n t i t yb o d y ( g z i p ) ：1 0 4 8b y t e s 一 1 8 7 0b y t e s 回应内容( 耵，方式) 其中，2 0 0 是服务器端回应的状态码，o k 是服务器端回应的原因叙述。状态 码及该状态码代表的含义如表2 2 所示 裹2 2 服务器端回应状态码及其含义 状态码 一7 含义 l 系统保留 2 客户端的请求被成功接受 3 为完成请求客户端需要进一步细化请求 4 客户端请求错误 5 服务端回应错误 服务器端回应码同时也在一定程度上决定了该回应是否可以缓存，可以缓存 8 武汉邮电科学研究院硕士学位论文 的状态码如表2 3 所示。 表2 3 可以缓存的状态码及含义 状态码 描述 含义 2 0 00 k 客户请求被成功处理 2 0 3n o n - a u t h o r i t a t i v ei n f o r m a t i o n 基本与2 0 0 类似，主要是用在代理服务器无法与原始 服务器进行确认时 2 0 6p a r t i a lc o n t e n t 部分请求被成功处理 3 0 0 m u l t i p l ec h o i c e s 服务器的回应消息有多个备份 3 0 1m o v e dp e r m a n e n t l y 请求的对象更换了u r l 地址 4 1 0g o n e 请求的对象已经从原始服务器上删除 c a c h e c o n t r o l 消息头是h t t p i 1 的新特性，它告诉了客户端请求和服务器端 回应能否缓存。常用的c a c h e c o n t r o l 消息头如表2 4 所示。 表2 4 常用的c a c h o - - o o r r t r o i 消息头及含义 c a c h e - c o n t r o l 消息头含义 m - c 批h e 该对象可以缓存，但在使用前需要检查对象的新鲜度 p r i v a t e 该对象只可以被客户端的浏览器缓存 p u b l i c该对象可以缓存 m a x - a g e 该对象的最大合法期，超过期限需要检查对象新鲜度 s - m a x a g e基本上与m a x = a g e 类似 m u s t - r e v a l i d a t e基本上与n o - c a c h e 类似 p r o x y - r e v a l i d a t e基本上与n o - c a c h e 类似，常用于缓存服务器 n o - s t o r e 该对象不能被缓存 m a x = s t a l e 如果对象过期，可以接受的最大过期时间 o n l y - i f - c a c h e d 可以直接将缓存中的对象发给客户端，而不需要考虑对象的合法性( 新鲜度) 9 武汉邮电科学研究院硕士学位论文 2 1 2 合法性验证 当客户请求对象被击中时，如何来判断该对象的合法性是缓存系统必须考虑 的重要问题。h t t p 协议提供了两种方法来验证对象的合法性，即e x p i r a t i o nt i m e s ( 过期时间) 和v a l i d a t i o n ( 验证) 。e x p i r a t i o n t i m e s 用于标识w e b 对象的过期时间， 只要客户请求的对象没有超过e x p i r a t i o nt i m e s ，缓存服务器就可以将该对象直接返 回给客户端；如果超过了e x p i r a t i o nt i m e s ，为了保证客户请求对象的新鲜度，在把 该对象返回给客户端前，缓存服务器需要与原始服务器建立连接来验i 正( v a l i d a t i o n ) 该对象的合法性。h t t p 协议提供了两种机制来验证对象的合法性。即 l a s t - m o d i f i e dt i m e s t a m p s ( 最近更新时间戳) 和e n t i t yt a g s ( 实体标识) 。 许多服务器端回应消息中包含了l a s t m o d i f i e d 消息头，该消息头用于指定 w e b 对象的最后修改时间。当缓存服务器无法确定对象的合法性时，可以用条件 g e t 请求方法或者h e a d 请求方法向原始服务器请求l a s t - m o d i f i e dt i m e s t a m p s 时间戳，从而来验证该对象是否被修改。如果该对象没有被修改，原始服务器就 会回应3 0 4 ( n o tm o d i f i e d ) 消息；如果该对象被修改，服务器端就会返回修改后 的对象。 e n t i t yt a g s 是一个随机字符串，是w e b 对象生成时随机产生的。e n t i t yt a g s 主要是用来标识一个己经存在的w e b 对象，该实体的值一般由e t a g 消息头给出。 如果对象被修改，e n t i t yt a g s 的值就会被修改为另外一个随机的字符串。当缓存服 务器无法确定对象的合法性时，也可以用条件g e t 请求方法或者h e a d 请求方法 向原始服务器请求该对象的e n t i t yt a g s 值，如果该对象的e n t i t yt a g s 值没有改变， 原始服务器就会回应3 0 4 ( n o tm o d i f i e d ) 消息；如果该对象被修改，服务器端就 会返回修改后的对象。 2 1 3 w w w 访问过程分析 通常，大多数人都认为网络技术不完善是w e b 性能较差的原因，相信采用高 1 0 武汉邮电科学研究院硕士学位论文 速的路由设备、a t m 主干或千兆以太网等技术就能够很大的加速w e b 访问。实际 上，m e t 通道加速在改善w e b 性能上的影响并非想象的那么大。为了发现造成 这种情况的原因，下面就对引起w e b 性能低下的根本原因进行详细的分析。 w | e b 访问是通过h t t p 协议实现的，h t f p 是在t c p i p 层之上的基于 r e q u e s t - r e s p o n s e ( 请求一回应) 的协议。在h t t p 请求发出之前，w e b 服务器的 i p 地址必须通过d n s 查询来得到。最终用户感觉到的访问性能，取决于d n s 服 务器和h t t p 服务器应答的反应时间。d n s 请求通常由本地d n s 服务器来应答， 但一般需要数秒钟的响应时间；h t t p 的响应时间实际上是多次往复的延迟。图 2 1 显示了w e bc l i e n t 端、d n s 服务器和w e b 服务器间的通讯交互过程： 图2 1 黼访问延时分析 每个h t t p 请求需要打开一个新的t c p 连接，这就会出现一个往返的延时 ( t c p 协议的三次握手) ；然后，用户发出h t t p 请求，服务器接收到请求后，对 武汉邮电科学研究院硕士学位论文 其进行分析处理并发出h t t p 回应包，用户在第二个往返延时后收到这个h t t p 应答；当这个h t t p 应答是一个h t m l 对象时( 通常网页的第一个对象是h t m l 对象) ，客户端浏览器将为其中嵌入的每个对象发出一个新的h t t p 请求。假定平 均的往返延迟时间是r t d ，对单个w e b 对象访问的响应时间为2 幸r 1 d ( 两个来回) 。 典型情况下，w 曲页面都包含多个嵌入的对象，每个对象都会增加2 * r t d 的延迟 时间，一个r t d 用于建立t c p 连接，另一个则用于h t t p 请求和应答报文的交换： 假设一个w e b 页面中包含了n 个嵌入对象，那么这个w e b 页面总的访问响应时间 为：2 r t d + 2 n 木r 1 d ，即2 叶1 ) * r t d 。往返延迟时间( r 1 d ) 取决于网络的健康 状况( 例如：网络的丢包情况) 和服务器的拥挤情况等，其差异一般很大。 如果客户端和服务器之间采用永久t c p 连接，那么页面访问的延迟将是 ( 2 斗n ) * r t d 。减少这个延迟的一个常用方法是c l i e n t 端同时打开多个连接，很多浏 览器都提供了这样的功能，但这种技术将会引起w e b 服务器端的拥挤，从而造成 服务器端反应迟钝，也就抵消了期望的增益。 平均的往返延迟r t d 取决于下面的因素： ( 1 ) w e b 服务器产生的延时。w e b 服务器延时常常在往返延迟中占很大比例。 当服务器需要同时处理多个h t r p 请求时，会产生排队延时。由于需要多次磁盘 读写( 的) 来完成客户请求的应答，即使负载较轻的w e b 服务器，也会需要几十 或上百毫秒的延时。 ( 2 ) 路由器、网关、p r o x y 和防火墙产生的延时。典型情况下，用户端到服务 器的网络链路上有多个网络设备，比如：路由器、网关、p r o x y 和防火墙等，它们 对每个网络数据包的转发都要执行存储一转发的操作；同时这些设备还会增加排 队延迟；当网络较拥挤的时候，它们甚至还会丢弃数据包，要求用户端和服务器 间采用端到端的可靠协议来恢复。 ( 3 ) 不同通讯链路上的数据传输速度。在广域网中，网络设备间数据传输速度 的减慢将明显增加往返延迟。实际上，基础带宽并不像感觉中那么重要，在一系 列测试中，用户通过4 5 m b p s 连接对一系列的著名w e b 站点进行访问，结果只有 1 2 武汉邮电科学研究院硕士学位论文 2 的w e b 对象是以超过6 4 k b p s 的速度获得的。这也明显说明：带宽并不是w w w 访问性能的最终决定因素。 ( 4 ) 光速延迟。即使w e b 服务器和d n s 服务器能迅速做出应答，没有路由器 的延迟，端到端的带宽是无限的，并且网络从不发生拥挤，在某些情况下，光信 号在全球复杂的光纤网络中传输也会带来很大的往返延迟。当前，网络带宽已逐 渐变得更便宜，但w e b 的访问速度可能变得更慢，因为从上面的分析中可以看出 带宽不是主要的问题，人们对w e b 丰富内容需求的不断增长，可能超过w e b 服务 器速度、路由器和带宽的改进。 加速w e b 访问最有效的方法是将大部分经常被请求的w e b 对象存储到最靠近 用户的地方。这样，光速延时间的影响就成为可以忽略的因素，并且引起访问延 时的路由器、防火墙或代理服务器( p r o x ys e r v e r ) 也变得很少。 高速缓存是一种广泛采用的技术，它被广泛应用于计算机系统中。当数据处 理速度比数据访问速度快时，用来消除性能瓶颈。显然，缓存服务器直接将w e b 对象递交给客户端比通过广域网访问要快很多，因此网络高速缓存是一个很自然 的高效解决方案。 2 2 w w wc a c h e 技术 c a c h e ( 缓存) 技术的基本思想是“一次取来，多次使用”。其基本目的就是 要最小化网络中大量重复传输的数据，从而提高网络的使用效率和提高对用户服 务品质的保证。 c d n ( c o n t e n td e l i v e r yn e t w o r k ) ，即内容推送网络。其目的是通过在现有的 i n t e m e t 中增加一层新的网络架构，将w e b 站点的内容发布到最接近用户的网络，边 缘 ，使用户可以就近取得所需的内容，解决i n t e r n e t 网络拥塞状况，提高用户访 问w e b 站点的响应速度，从技术上全面解决由于网络带宽小、用户访问量大、网 点分布不均等原因，从而解决了用户访问网站响应速度慢的根本原因。 武汉邮电科学研究院硕士学位论文 c a c h e 是c d n 的重要技术手段。高速缓存手段的成本较低，适用于静态内容。 在i n t e m e t 上，超过8 0 的用户经常访问的是2 0 的网站的内容，在这个规律下， 缓存服务器可以处理大部分客户的静态请求，而原始的w e b 服务器只需处理约 2 0 左右的非缓存请求和动态请求，于是大大加快了客户请求的响应时间，并降低 了原始w e b 服务器的负载。 2 2 1 w w wc a c h e 服务器的工作过程 如图2 2 所示，传统的w w w 访问过程为：客户端首先向w e b 服务器提出请 求，w e b 服务器接收客户端的请求，然后分析客户端的请求并将客户端请求的数 据回送给客户端。 客户端 图2 2 传统洲访i * - - i 过程 如果加入了缓存服务器，则整个w w w 访问过程变为：客户端的请求先提交 给w w w 缓存服务器，缓存服务器分析该请求，先查看缓存中是否有客户请求数 据，如果有就直接将该数据传送给客户端；如果没有缓存服务器就代替客户端向 原始w e b 服务器发出请求，原始w e b 服务器将数据回送给缓存服务器，缓存服务 器再将回应的数据传送给客户端，同时在自己的缓存中保留一份该数据的拷贝。 这样，如果有后续的用户请求相同的数据时，缓存服务器就可以直接将数据传送 给客户端，而不需要再向原始w e b 服务器发起请求。如果客户端请求的页面己被 缓存，实际上存在两种可能：其一，缓存的页面已经不新鲜，即缓存中保存的页 面超过了合法期或者原始w e b 服务器的网页己经被更新，这时缓存服务器就会与 1 4 武汉邮电科学研究院硕士学位论文 原服务器建立连接，去验证缓存中的页面，如果被更新，就返回新的页面；如果 没有被修改，就返回“页面未修改一的消息；其二，缓存的内容是新鲜的，即该 页面与原始w e b 服务器上的页面保持同步，此时称为缓存命中，这时缓存会立即 将己保存的页面回送给客户端。正是由于缓存服务器的这种工作原理，因此常把 缓存服务器称为代理缓存服务器。具体的工作过程如图2 3 所示： 图2 3 删* 代理缓存服务器的工作过程 2 2 2 v o y v w 缓存服务器的分类 缓存服务器根据服务模式的不同，常分为主动缓存和被动缓存。主动缓存即 根据事先设置的策略预先把要访问站点页面缓存到本地，用户获得的数据都是已 经缓存的页面，但不一定是原始w e b 服务器最新的页面，这种方式类似镜像功能， 一些政府机关为了使内外网隔离常采用这种方式，这样既能访问i n t e m e t 上的内容， 又保证了内部网的安全。一些早期的缓存服务器常采用主动缓存，随着i n t e m e t 的 高速发展，信息的实时性和新鲜度显得格外重要，所以目前的缓存服务器都是采 用被动模式。被动缓存即有客户请求，缓存服务器才代理客户向原始w e b 服务器 发出请求，并且将原始w 曲服务器返回的数据缓存，供下一个访问的客户机使用。 在这种方式下，每次客户提出的请求，如果缓存服务器不能确定请求对象的新鲜 武汉邮电科学研究院硕士学位论文 度，都要与原始服务器建立连接以验证该对象的合法性，如果原始服务器的内容 与缓存的内容不一致，就只取更新部分的数据，如果原始服务器的内容与缓存的 内容没有变化，就不再重取，直接从本地缓存服务器中将客户请求的数据发送给 客户。比如一个新闻页面，原始w e b 服务器只更新了其中的一条新闻，那么缓存 只需要取回更新的这条信息，而其他部分仍然从缓存服务器中获得，这显然减少 了已有数据的重复传输。 缓存服务器根据加速对象的不同，可分为正向代理( f o r w a r dp r o x y ) 和反向 代理( r e v e r s ep r o x y ) 两种模式。加速内部网络用户对外部网络的访问速度称之为 正向代理，正向代理缓存服务器处于网络中靠近用户的边缘网关位置，能对所有 的网络用户提供缓存服务，这是大多数用户使用的模式。其工作原理如图2 4 所示： 图2 4 正向代理缓存服务器 如果缓存服务器用于加速w e b 服务器的访问速度，一般称之为反向代理或反 向加速，处于服务提供商方( i s p ) 靠近w e b 服务器一端，用户的请求主要通过高 速缓存服务器获得，此时的缓存服务器类似于一台w e b 服务器，也是在8 0 端口接 受客户端的h t r p 请求。由于缓存服务器加操作的运行机制与w e b 服务器不一样， 因此性能要大大高于w e b 服务器，通过反向加速，可以降低w e b 服务器的负载， 从而提高w e b 服务的响应速度，增加单位时间内该从w e b 站点的访问流量。反向 代理的工作原理如图2 5 所示： 1 6 武汉邮电科学研究院硕士学位论文 h e h q 务器 图2 5 反向代理缓存服务器 根据客户端浏览器是否需要更改配置，可分为传统代理缓存和透明代理缓存。 传统代理缓存需要客户端在浏览器中设置代理缓存服务器的m 地址和监听的端口 号，从而将请求发送给指定的代理缓存服务器。这种方法的缺点是所有的用户都 需要在客户端浏览器中进行设置，指明代理服务器的i p 地址和所监听的端口号， 这不但加大了客户端的使用难度，而且也不利于对缓存服务器的管理。 透明代理缓存( t r a n s p a r e n tp r o x y ) 则不需要客户端做任何配置就可将客户端 的w w w 请求( 目的端口是8 0 ) 重新定向到缓存服务器。之所以称为透明代理缓 存，指的是缓存的存在对客户端来说是透明的，也就是说客户端根本感觉不到缓 存的存在，当然客户端也不需要知道缓存服务器在网络中的具体位置。 2 2 3 现有w e b 缓存产品 目前，基于w w w 的缓存产品比较多。无论是开放源代码产品，比如基于通 用操作系统l i n u x 、u n i x 、b s d 的s q u i d ，还是国际、国内各主要n i 厂商推出的 w e b 缓存产品，比如c a c h e f l o w 公司推出的c a c h e f l o w 系列产品、c i s c o 推出的c a c h e e n g i n e 系列产品、3 c o m 推出的w e b c a c h e 系列产品、i n t e l 推出的n e t s t r u c t u r e 系 列产品、联想推出的i c a c h e 系列产品、实达推出的s t a r - c s 系列产品、朗新推出的 n e t s h i n e 系列产品。总的来说这些缓存产品一般都是采用纯软件方式或软硬结合的 1 7 武汉邮电科学研究院硕士学位论文 方式来实现的。 纯软件的方式不需要任何额外的硬件支持，只需要将缓存系统安装到普通的 p c 机或服务器上并按照说明进行相应的配置后就可以使用，比如s q u i d 就是这种 实现方式。一般开放源代码的缓存产品都是基于这种方式实现的。纯软件方式缓 存产品的优势在于成本比较低，但是安装和配置一般比较复杂。对于s q u i d ，由于 实现模型是基于单线程的，所以不能很好的利用主机的c p u 资源，效率也不高， 实现起来也非常复杂；s q u i d 也不能做到在后台执行某些耗时任务，比如对w e b 对 象的完整性和合法性检查，这肯定会影响缓存服务器的性能；而且s q u i d 也不能直 接实现拦截代理缓存，必须借助第三方工具比如i p t a b l e s 来实现。 除了开放源代码缓存产品外，其他的商用缓存产品基本上都是采用软硬结合 的方式来实现的。这种实现方式一般是将缓存系统安装到一个特定的设备中( 比 如工控机) ，这种特定设备中安装的操作系统一般是l i n u x 或者对l i n u x 针对w e b 应用做了某些优化。像c a c h e f l o w 、3 c o m 、c i s c o 、联想、实达、朗新等公司的缓 存产品都是采用的这种实现方式。 2 24 评价缓存系统的主要性能指标 评价缓存性能的主要指标有：命中率、访问延时和吞吐量，命中率分为对象( 请 求) 命中率和字节命中率。缓存的其他评价指标包括c p u 占用率、同时能支持多 少连接、每秒钟响应请求的对象数，最大线速、以及数据吞吐量等。 对象( 请求) 命中率是指缓存服务器自身命中的用户请求与服务器收到的用 户请求总数之比，字节命中率是指缓存服务器从自身向用户发送的字节数与它向 用户发送的总字节数之比。用公式