（计算机应用技术专业论文）web代理服务器缓存替换算法的设计与仿真.pdf

中文摘要 随着i n t e r n e t 技术和1 惭w 服务的发展，w e b 网络流量和网页访问延迟日益引 起人们的关注，对这两个问题的解决影响了i n t e r n e t 的持续发展。代理缓存技 术是解决这两个问题的最常用方法。本文着重研究w e b 代理服务器缓存替换算 法。 首先，本文介绍了w e b 缓存的分类和组织结构，分析了w e b 业务流的特性， 揭示了w e b 请求具有时间局部性的特点。然后，讨论了缓存替换算法的性能评价 指标和已有缓存替换算法，并指出了它们的优缺点。根据这些优缺点，对h y b r i d 算法进行了两次改进，在改进的基础上提出了一种综合考虑了文档的大小、访问 次数、访问延迟和最近一次访问时间的新算法。并设计了仿真工具，对已有算法 和新设计的算法进行了实现。最后通过t r a c e 驱动的仿真方法对各种算法进行了 仿真，并对它们迸行了性能评价。仿真实验结果表明。新设计的算法具有较高的 命中率和较低的延迟率，综合性能要优于其它替换算法。 关键字：缓存，代理服务器，替换算法，仿真，请求命中率，字节命中率， 延迟率 a b s t r a c t w i t ht h ei n c r e a s i n g p o p u l a r i t y o ft h ew b r l dw i d ew e b ，t h ea m o u n to f i n f o r m a t i o na v a i l a b l ea n dt h eu s eo f w b bs e r v e r sa r eg r o w i n g e x p o n e n t i a l l y m o r ea n d m o r ea t t e n t i o ni sp a i dt ot h ew e bt r a f f i ca n dp a g ea c c e s sd e l a y p r o x yc a c h ei st h e m o s tc o m l t l o nm e t h o dt os o l v et h e s et w oi s s u e s i nt h i sp a p e r , w em a l m ys n 】d yt h e c a c h er e p l a c e m e n t a l g o r i t h m sf o rw e bp r o x y s e r v e r f i r s t w ea n a l y z et h ew e bt r a f f i ca n dd e m o n s t r a t et h el o c a l i t yo fw e br e q u e s t s s e c o n d l yw e t a l ka b o u tt h e r e p l a c e m e n ta l g o r i t h m sp r o p o s e di nt h el i t e r a t u r ea n dg i v e t h e i ra d v a n t a g e sa n ds h o r t c o m i n g s t h e nw e i m p r o v eh y b r i da l g o r i t h ma n dp r o p o s ea n e wc a c h ea l g o r i t h mw h i c ht a k e si n t oa c c o u n tt h en e t w o r kl a t e n c y , t h es i z eo ft h e d o c u m e n t s ，t h e i ra c c e s sf i e q u e n c i e s , a n dt h et i m ee l a p s e ds i n c et h el a s tr e f e r e n c et o d o c u m e n t si n 也ec a c h e t h r o u g h 灯a c e d r i v e ns i m u l a t i o n sa n df o rv a r i o u ss t a n d a r d c o s tc r i t e r i a ( r e q u e s th i tr a t e ，b y t eh i tr a t ea n d l a t e n c yr a t i o ) u s i n gas i m u l a t i o nt 0 0 1 d e v e l o p e do u r s e l v e sw es h o w 也a to u rr e p l a c e m e n ta l g o r i t h mp e r f o r m sb e r e rt h a n s e v e r a lp o l i c i e sp r o p o s e di nt h el i t e r a t u r e k e y w o r d s ：c a c h e ，w e b p r o x y ，r e p l a c e m e n ta l g o r i t h m ，s i m u l a t i o n ，r e q t m s th i t r a t e ，b y t e h i t r a t e ，l a t e n c yr a t e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫壅盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：套晨熙签字日期：抛歹年月牙日 学位论文版权使用授权书 本学位论文作者完全了解基鲞盘壁有关保留、使用学位论文的规定。 特授权鑫蓬盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 杏晨酶 导师签名； 签字日期：2 0 年1 月孑日签字日期： g 日 第一章鳍论 1 1 全球互联网概述 i 1 1i n t e r n e t 与棚哪 第一章绪论 i n t e r n e t 的历史不过几十年的时间，然而其发展却是加速度的。6 0 年代美 国国防部以a r p a n f r 为主干建立起i n t e r n e t ，1 9 8 5 年，n s f 开始涉足t c p i p 协 议的研究与开发，并投入巨资建立了主干网n s f n e t ，逐渐代替a r p a n e t 成为 i n t e r n e t 新的主干网。不久，一些研究机构和厂商也将? c p i p 协议加入到一些 流行的计算机操作系统中，发展成为基于t c p i p 的i n t e r n e t 。今天，i n t e r n e t 已经成为主要的信息载体，可以传递声音、图形、图像和文本等各种信息，成为 人们之间信息交流的一种新方式。t e l n e t 、e m a i l 、f r p 、g o p h e r 、w w w 以及基于 w 啊的网上购物、远程教育、视频点播等应用都迅猛地发展起来。 w w w ( w o r l dw i d ew | e b 或w e b 。中文简称万维网) 通常是建立在i n t e r a c t 上的，是i n t e m e t 上最受欢迎，最为流行的信息检索服务程序，它的出现提供 给用户简便、快捷和友好的信息访问方式。正是由于w w w 的出现，才带来 了i n t e m e t 的迅速发展。在1 9 9 2 年，w w w 只是作为i n t c m e t 的一种应用存在， 每个月的网络流量仅为7 4 m b ，排在所有i n t e l n e t 上包传送数目的第1 8 位，而 现在已经是第一位了，这种爆炸般的发展表现为指数增长。 1 1 2 矾哪的工作机制 w w w 采用开放式的c l i e n t s e r v e r 结构作为基本框架，是由w e b 服务器( w e b s e r v e r ) 和w e b 客户机c 臀e bc l i e n t ) 组成的分布在整个i n t e r n e t 上的大型分布 式系统。 w e b 服务器是运行于计算机上的一个应用程序，该程序的目的是当其它计算 机请求时为其提供请求文档。w e b 服务器是存储信息的仓库，是信息的提供者， 规定了服务器的传输设定、信息传输格式及服务器本身的基本开放结构。w e b 服 务器软件( 可能还包括其它相关软件，如p r o x ys e r v e r 、扩展应用软件) 负责处理 客户端的请求，并将有关数据( h t m l 文档和原始数据) 通过网络返回给客户机。 w e b 客户机设计出适当的接收格式以建造适当的信息接收工具。w e b 客户机与用 户以交互方式运行，当用户需要某个文档时，客户机软件( 一般是w w w 浏览器) 第一章绪论 负责初始化用户的请求，然后提交给w 哪服务器；并对服务器返回的数据进行处 理和显示( 有时还需要相关的软件协助处理，比如f l a s h 插件) 。目前有不少常用 的w e b 服务器和w e b 浏览器软件。比较著名的w e b 服务器软件有a p a c h e ， m i c r o s o f ti i s ，n c s ah t t p d 等。浏览器主要有n c s a 的m o s a i c ，n e t s c a p e 公司 的n a v i g a t o r ，微软公司的i n t e r n e te x p l o r e r 等。 w w w 服务端有大量的原始数据( 如文本、图像、视频、音频等) 和超文本文档( 用 于组织管理原始数据) ，这些信息在存放方式、访问模式、数据格式等方面各异。 w w w 通过h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本标记语言) 文档来组织管理 各类原始数据。这种文档内可以包含各种数据类型( 经m i m e 定义) 的数据，还包 含一些数据文件的超级链接指针。这些超级链接指针分别指向存放在不同地方的 不同类型的w e b 文档。所有的w e b 文档或所有的w e b 节点都用一个唯一的地址来 标志，称为统一资源定位符( u n i f o r mr e s o u r c el o c a t e r ，简称u r l ) 。 w e b 服务器与客户机之间使用的通信协议是超文本传输协议( h y p e r t e x t t r a n s f e rp r o t o c o l ，简称h t t p ) 。h t t p 是一种请求应答式的高层网络协议， 建立在t c p i p 的基础上。对应于i s o o s i 七层协议中的应用层。h t t p 协议由 i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 组织维护和更新，已经从最初的0 9 版本发展到1 1 版本( r f c 2 0 6 8 ) ，目前最常用的是1 1 版本。在h t t p l 1 中， h t t p 的一次会话( s e s s i o n ) 是由一个h t t p 请求过程和一个响应过程( 或称 h 竹p 应答) 组成的，对应于一次t c p 连接。一个h t t p 请求是由个请求头和 一个请求体构成的。在请求头指明了请求的类型，包括g e t 、p u t 、p o s t 和h e a d 四种请求。分别表示了从服务器上传或下载的各种情况。在请求头还提供协 议版本、数据压缩方式和连接方式等信息。请求体是客户机发送给w e b 服务 器的数据。w e b 服务器的响应也是由响应头和晦应体构成的响应头提供返回 状态、协议版本、数据长度和数据压缩方式等信息，响应体是从服务器返回 给用户的网页数据。图l - l 是h t t p 的一个会话过程。 图1 1h t t p 的会话过程 用户只需在测览器中指出u r l ，相应的文档就会从w e b 服务器上传输到本地 2 第一章绪论 机器并显示出来，用户随后可以点击网页中的超文本链接转到其它w e b 节点。每 点击一个链接，浏览器就发出一个h t t p 请求。w e b 服务器接收到请求后，寻找 所请求的w e b 页面。并将所请求的w e b 页面传送给w e b 浏览器；w e b 浏览器接收 到返回的w e b 页面，并将它显示出来，原理如图1 2 所示： 图1 2w 啊的工作机制 1 2 w e b 所面临的问题及改善w e b 服务的方法 1 2 1w e b 所面临的问题 在i n t e r n e t 飞速发展的今天，w 厢以其多媒体的传输以及良好的交互性而倍 受青睐，w w w 已经成为网上生活的基本工具，它不仅仅用于浏览网上的信息，还 成为发布信息、商务活动的媒介，被人们称为第六媒体。然而恰恰是由于w w w 的 流行，使用的人数越来越多。人们开始抱怨网络测览速度太慢，用户的服务质量 ( q o s ) 得不到很好的保证。相信每个曾浏览过w 唧的用户都有这样的经历：当点 击某个链接后，接下来的是一段漫长而痛苦的等待，然后才看见请求的主页缓慢 地出现在计算机的屏幕上。有人戏说w o r l dw i d ew e b 变成了w o r l dw i d ew a i t 。 实际上网络测览的延迟问题受到许多因素的影响。第一，w e b 服务器需要花 一定的时间去处理一个请求，而在超负荷运转或者磁盘速度比较慢时需要花更多 的时间：第二，w e b 客户端程序( 浏览器) 如果不能快速地对取回的数据进行分析 并将结果显示在用户面前，也会增加用户的等待时间i 第三，文档的传输时间还 与网络的带宽有关，带宽越大速度就越快，反之就越慢。第四，由于网络协议的 不完善而造成的延迟也是需要考虑的。例如，m p 协议是无状态的。无状态就 是指协议对事务处理没有记忆能力。缺少状态就意味着如果后续处理需要前面的 信息，则它需要重传前面的信息。这样可能导致每次连接传送的数据量增大，因 此导致网络延迟增大。 1 2 2 改善h b 服务的方法 从图1 1 中可以看出，改善w 哪服务的能就是加速h t t p 会话过程的处理。 目前的研究主要是从客户机、w e b 服务器以及i n t e r n e t 网络设施这三方面进行 第一章绪论 的。方法主要有两类，虽然两类方法所需要解决的问题和所要达到的目的相同， 但是解决问题的着眼点和解决途径却截然不同。第一类方法是提高w e b 服务器的 处理能力，增加网络带宽，并控制发入网络的数据量；第二类方法是提高现有系 统的利用率。 显然。第一类方法是解决网络延迟的最根本途径。采用更高处理能力的 w e b 服务器可以减少w e b 服务器对h t t p 请求进行分析和处理的时间。尤其是 目前动态网页的大量出现，进一步增加了w e b 服务器上要进行的计算检索的 操作量。如果通过购买更高档的服务器来提高性能，则成本高，且不具有可 扩展能力。发展的趋势是采用服务器集群技术，多个服务器通过局域网连接， 协同对客户机的h t t p 请求进行处理。这种技术提供了可扩展、高可用性的w e b 服务器平台，具有很好的应用前景。增加网络带宽主要依赖对整个网络环境 的改造，通过增加网络投资提高路由器的路由性能、成倍地增加网络带宽等 方法，可以使问题得到基本的缓解，但是投资较大，实施较困难。+ 从i n t e r n e t 的发展过程中可以看出，即使服务器的性能越来越出色，网络带宽也在逐步 提高，i n t e r n e t 主干网的容量茬不多以每年6 0 的速度扩充 1 。但是网络系 统能力的提高始终跟不上网络用户的增长。出现这种被动局面的主要原因是 网络基础设施建设需要大量的投资，较长的建设周期。 研究人员通过对网络流量的分析认为，要彻底解决问题，单纯依靠增加带宽 是不够的，而应该充分提高带宽的利用率，保证服务质量，降低响应时间，达到 事半功倍的效果。通过采用某些技术手段，减少网络流量，从而降低对网络带宽 的要求，可以很好地改善聊哪服务的质量。提高网络带宽的利用率来减少网络延 迟的方法有以下几种： i 完善m p 协议 提高网络协议的效率的基本依据和出发点是：由于不完善的网络协议将消耗 掉部分带宽，从而加剧网络带宽的不足，由网络协议本身引起的问题应该通过改 进网络协议来解决。以前的w e b 服务器使用的协议是h t t p i 。0 ，它是晕巾简单的 请求应答协议，并不是为重载情况所设计，因此在解决网络延迟方面并没有采 取一定的措施。虽然h t t p i 1 协议的提出和使用就是从网路协议对网络系统的影 响方面出发的，但是仍旧存在着缺陷和不足，需要对h t t p 协议进行进一步的设 计、改进 2 。 2 使用镜像技术 所谓镜像技术就是在不同物理位置的多台服务器上复制和存储相同的内容。 这种技术的思路很简单，即通过缩短用户到服务器的距离，来加快访问速度。镜 象技术自身存在着一定的缺陷，例如，数据的多次复制将导致数据不一致问题的 第一章绪论 出现。同时，在不同地点维护多台服务器将增加成本和费用 3 。 3 集群技术 集群技术是将客户端的请求按照一定的算法分配到一台或者多台服务器上， 然后由这一台或多台服务器共同响应客户端的请求，从而达到提高网络访问速度 的目的。群集系统在一定限度上提高了w e b 系统可用性和处理能力，但是集群系 统无法解决i n t e r n e t 带宽存在的限制。 4 对传输的文档进行压 压缩技术指发送方首先对要传输的数据进行压缩，而后再进行网络传输。这 就需要在发送方安装压缩软件，并在接收方安装解压软件。目前大多数的w e b 服 务器都是用h t t p l 1 ，它允许用户对服务器上的文档压缩后再传输 4 。目前传 输的w e b 文档绝大部分是没有经过压缩处理的，如果将经过压缩的文档放在w e b 服务器上不仅可以减少网上数据的传输量，而且可以改善用户的检索延迟。虽然 客户端需要对文档进行解压缩处理，需要花费一些时间，但在实际的数据传输过 程中，带宽是主要的瓶颈，在等待数据到达的这一段时间内c p u 处于空闲状态， 因此可以利用空闲的c p u 周期来处理已到达的部分文档。 5 使用w e b 缓存技术 w e b 缓存的基本依据和出发点是：如果一个文档可能被使用两次或者两次以 上，那么可以在这个文档第一次被使用时将其保存在客户机或者本地服务器( 例 如，代理服务器) 中，这样以来，后续的访问就能够直接从客户机或本地服务器 直接获得该文档，丽不必再访问w e b 服务器。这种技术不仅可以大大缩短访问距 离，较少信息的传输时间，而且还可以减轻网络和w e b 服务器的负担。 6 使用w e b 预取技术 w e b 预取的基本依据和出发点是：在一个测览器会话中连续两个页面的下载 之间，常常有一段空闲时间称为用户思考时间，这个空闲时间的长度范围可以从 几秒钟到几分钟，预取策略就是利用这个空闲时间提前把使用者不久将要使用的 文档取回。并保存到缓存中，这样就可以减少实际访问的等待时间。 1 3 本文的研究内容 随着以h t t p 协议为基础的w 珊服务成为i n t e r n e t 上最受欢迎的服务，w e b 业务量也迅速膨胀起来，随之而来的是网络延迟的急剧增加。如何提高w e b 的响 应速度已经成为当前亟待解决的问题。而缓存技术被公认为是行之有效的解决方 案，并广泛应用到客户浏览器、w e b 代理服务器和w e b 服务器上。通过把w e b 文 档缓存在代理服务器或者距离用户较近的服务器上，当用户请求此文档时，可以 这里获得，而不必访问髓b 服务器，从而大大减少了请求响应时间和网络带宽的 蔓二兰堕丝+ 消耗。目前大多数的缓存都是采用传统的内存页面策略，例如l r u ( l e a s t r e c e n t l yu s e d ) 策略。而w e b 业务的自身特点使得这些缓存策略效果并不十分理 想。 考虑到代理服务器在w e b 访问中所处的特殊位置及其自身的特点，研究人 员把注意力重点转移到代理服务器上，希望通过代理服务器上的缓存尽可能的降 低w e b 业务量，减少网络延迟，提高用户请求的响应时间。然而如果缓存命中 失败，则会导致更长的响应时间和占用额外的处理器周期，因此设计命中率高的 算法是缓存技术的关键。本文结合了代理服务器业务流的特点。在对已有算法分 析、改进的基础上，提出了一种具有较高命中率和较低延迟率的新算法n i t s 。 本文总共分为五章，第一章为绪论，介绍了i n t e m e t 的发展状况，指出了 w e b 服务所面临的问题以及解决方案，最后介绍了作者所做的具体工作；第二章 介绍了代理服务器的工作原理及其主要功能，w e b 缓存的分类和组织结构，并对 代理服务器上的w 曲业务流特性进行了研究；第三章是本文的重点，主要介绍 了已有的缓存替换算法和性能评价指标，对h y b r i d 算法进行了改进，并结合 h y b r i d 算法提出了一种新的算法。通过们仿真实验对各种算法进行分析比较， 指出了各种算法的优缺点：第四章介绍了本文所使用的仿真工具的设计和实现 第五章是结论和展望。 6 第二章w e b 缓存及其业务流特性 第二章w e b 缓存及其业务流特性 2 1 代理服务器概述 h t t p 1 0 的规范对代理服务器( p r o x y ) 有明确的定义，它是一个兼服务器和 客户机双重功能于一身的中介程序。功能上，它属于防火墙的一种，位置上它处 于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 所示： 图2 1 代理服务器的工作方式 代理服务器通常作为网络防火墙的客户端入口。所谓防火墙，就是在一个封 闭的网络，人们出于安全的考虑，不让整个网络内的机器直接与外界沟通，通常 的做法是将它们连接到某台与i n t e r n e t 相连的主机上，然后再由那台主机负责 与i n t e r n e t 交流，这台主机就叫做防火墙。代理服务器一般用在装有防火墙的 网络机器上，可以说是防火墙网络( 内部网) 中所有主机的w e b 代理人。在一个受 到保护的网络内，代理服务器为内部网上的主机提供了一个访问i n t e r n e t 的机 会，实际上代理服务器就是内部网和i n t e r n e t 之间的一个高屡网关，它容许内 部客户向i n t e r n e t 发送请求并且接收信息，但可以禁止来授权的用户的访问。 代理服务器通过防止数据包在用户内部网和i n t e r n e t 之间直接传送有效地屏 蔽了内部网络，增强了内部网的安全性。 代理服务器除了具有防火墙的功能外，更为重要的是它的缓存功能。若某个 代理服务器上缓存了很多远端的文档，那么以此作为代理服务器的客户，就不必 7 苎三童旦堂堡查垦基些墨煎壁垡 再重新连接到w e b 服务器，花费大量的时间将文档取回来，只要让代理服务器把 它所缓存的文档发送给客户即可。从图2 ，1 中知道，客户发出的请求首先会先发 送到代理服务器上，如果该代理服务器具有缓存功能，它在每一次接收到用户的 w e b 请求后，首先从本地的缓存查找请求的文档，如果找到( 称为缓存命中) 并且 是最新的，则代理服务器立即将缓存中的文档发送给客户机作为对其请求的响 应；如粟没找到( 称为缓存失效) ，代理服务器需要向对等上一级代理服务器或 者w e b 服务器提出请求，接受到请求的文档后在发送给客户的同时，在自己的缓 存中留一份备份。具体见图2 2 所示。 图2 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 服务器( 比如，本地网络中的一些w e b 服务器) 。 由于目前大多数用户使用的w e b 浏览器具有内部缓存的功能，因此客户机发 送请求之前首先在本地缓存中查找有没有所请求的w e b 文档，如果命中则直接从 本地缓存中取得；否则，才访问代理服务器；因此同样具有缓存功能的代理服务 毫 第二章w e b 缓存及其些务逸蝗壁 器只能作为客户机的第二级( 或更高级) 的缓存。代理服务器上的缓存命中事件只 有当用户的请求无法从本地缓存中得到满足进而向代理服务器提出请求时才有 可能发生。 2 2w e b 缓存的分类和组织结构 2 2 1w e b 缓存与传统缓存的区别 高速缓存的设计思想在计算机系统中有很多应用场合，比如为了提高文件系 统的访问速度而使用的文件缓存，为了提高主存的访问速度而使用的高速缓存 等，我们称这些缓存为传统缓存。虽然在w e b 中使用的缓存思想与传统缓存相同， 但是由于w e b 的自身特点使得w e b 缓存和传统缓存之间存在着些差别。这些差 别主要表现在三个方面：第一，传统缓存所缓存的对象大小固定( 以数据块为单 位) ，而w e b 缓存所缓存的对象是以文件为单位的，因此缓存的对象的大小不一。 这是由于h t t p 协议所支持的是整个文件的传输，同时w e b 文件在长度上的变化 显著，小到几个字节，大到几百k 字节，这与文件所携带的信息类型有关( 比如， 文本、图像和视频等) 。第二，传统缓存中获取不同缓存对象的成本主要是由机 器的性能决定的，因此不同对象的成本基本相同，而w e b 缓存中获取不同缓存对 象的成本可能相差很大。这是因为w e b 缓存对象是从w e b 服务器上下载的，它的 获取受许多因素的影响( i t 如，服务器的性能、文档大小、网络带宽等) 。所以下 载不同的文档花费的时间一般也不相同。第三，传统缓存一般只有很少的程序访 问，而w e b 缓存被很多客户访问，访问的用户可能有几个。也可能有上千个。第 四，w e b 缓存需要解决一致性的问题。如果由于w e b 服务器修改了对象导致w e b 缓存中缓存的对象与w e b 服务器中的对象不一致( 缓存的一致性问题) ，那么w e b 缓存就失去了存在的意义。因此w e b 缓存必需解决缓存对象一致性的问题。 2 2 2w e b 缓存的分类 一般说来，按照w e b 缓存在w w w 服务中所处的位置可以把w e b 缓存分为：客 户端缓存( c 1l e n tc a c h i n g ) 、服务器端缓存( s e r v e rc a c h i n g ) 以及代理服务器缓 存( p r o x yc a c h i n g ) 。其中代理服务器上的缓存是本文研究的重点。 i 客户端缓存 客户端的缓存通常是捆绑在w e b 浏览器上的，客户端缓存为浏览器开辟出一 定的存储器或磁盘空间，作为测览器的高速缓存。而早期的浏览器并没有提供 w e b 缓存的功能，随着人们认识水平的提高，现在的浏览器都提供了这一功能， 9 第二章w e b 缓存及其业务流特性 如n e t s c a p e 公司的n a v i g a t o r 和m i c r o s o f t 公司的i n t e r n e te x p l o r e r 浏览器 都提供了缓存用户一定时期内访闯过的网页信息的功能。客户端w e b 缓存分为非 永久( r l o p e r s i s t e n t ) 缓存和永久( p e r s i s t e n t ) 缓存两种缓存方式。前者只在主 存中存放本次浏览器会话( s e s s i o n ) 所访问的文件( 如，m o s a i c ) ；而后者将w e b 文档保存到磁盘中，以备将来的会话使用 5 。客户端缓存的工作原理如图2 3 所示。 图2 3 客户端缀存 缓存需要使用硬盘空间来存储用户曾经访问过的文档。一般可以在浏览器中 自行设置缓存的大小。只有当本地缓存中无法满足用户的请求时，浏览器才会把 请求发送给代理服务器或者w e b 服务器。当客户所要访问的文档存在于高速缓存 中时，只需要很短的时闻就可以从w e b 缓存( 一般为本地磁盘) 中得至所请求的 w e b 文档。显然，客户端的w e b 缓存技术大大提高了浏览速度。然而这种缓存机 制实现的一致性策略和替换策略都比较简单，提供给用户的经常是一些失效了的 信息，因此它是一种不可靠的缓存机制。 2 服务器端缓存 服务器端缓存是和w e b 服务器软件捆绑在一起的，通常在w e b 服务器上实现 二级或三级c a c h e 作为缓存，它比存放网页的磁盘具有更高的访问速度。w e b 服 务器端缓存分为两类；一类是把w e b 服务器的主存划出一部分空间作为高速缓 存，称为主存w e b 缓存，如图2 4 所示；另一种是放在特定w e b 服务器前端的 w e b 缓存，称为w e b 加速器( 又叫做反向代理) ，如图2 5 所示。 l o 图2 4 主存w e b 缓存 图2 5w 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 缓存的应用既减少了对文件系统的请求数量， 又减少了从文件系统传输到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 服务器加速器 的工作原理如图2 6 所示。 图2 6 反向代理的工作原理 工作原理具体如下： ( 1 ) 客户机请求w 曲服务器的某个页面，客户端发出的请求首先被w e b 服务 器加速器得到： ( 2 ) 如果请求的页面在w e b 服务器加速器中存在，则直接把页面发送给客户： 如果请求的页面在w e b 服务器加速器中不存在，则w e b 服务器加速器向w e b 服 务器请求该页面； ( 3 ) w 曲服务器加速器把得到的w e b 页面发送给客户机，同时把该页面缓存。 服务器端缓存机制能够适当地降低访问延迟，但是对服务器的要求较高， 增加了服务器软件的复杂度。为了更好地降低延迟，一些w e b 服务器还实现 了预取功能。 3 代理服务嚣缓存 在w 册中代理服务器( p r o x y ) 位于客户机与服务器之间的通路上，充当w e b 测览器和w e b 服务器之间的媒介物，它的最基本功能是允许处于防火墙内部的用 户访问i n t e r n e t 。当用户的请求到达代理服务器时，如请求可被满足，则代理 直接把请求文档提供给用户。否则重定向请求到w e b 服务器。 在这种环境下，浏览器必需配置成直接与代理服务器通信，而不是把自己的 请求直接发送给u r l 所指向的w e b 服务器。此时浏览器所发出的请求被称作代理 h t t p 请求。代理服务器接收这些请求，并检查所请求对象是否己被缓存。如果 所请求的对象已经在缓存中，那么代理服务器直接从缓存中取得该对象，并把它 发送给客户端。如果请求的对象不在缓存中。那么代理服务器就会代替客户端向 u r l 所指向的w e b 服务器发送请求。当w e b 服务器返回请求的w e b 文档时，代理 服务器就把收到的w e b 文档发送给客户机，同时使用缓存替换算法，在缓存中备 份一个副本。代理服务器缓存的结构如图2 7 所示。 图2 7 代理服务器缓存 一般来说，子网内部( 处于防火墙内部) 的所有客户机使用同一个代理服务 器。因此，代理服务器可以缓存那些被多个客户端访问的w e b 文档。另外，代理 服务器的缓存功能，对于那些不使用防火墙的用户来说也有很大的意义。比如， 一个工作小组内的所有主机使用一个代理服务器，由于代理服务器具有缓存文件 的功能，当一个客户访问以前曾经访问过的文件时，就可以直接从本地的代理服 务器中获取。从而大大减少了上网费用和响应时间。由此可见，代理服务器上的 缓存可以被多个客户机访问，比客户端的缓存更有效 6 。 代理缓存机制具有多个客户端可以共享所有w e b 文档的特点，降低了访问 延迟和网络费用。同时，这些代理服务器提供的缓存服务还可以连接在一起，共 享资源。 通过比较三种缓存方式，代理服务器缓存机制是解决聊w 访问速度慢、 服务器负载重和网络阻塞等问题的最好办法。首先，它具有客户端缓存机制 降低访问延迟的优点。其次，因为缓存由专门的代理服务器实现和维护，缓 存机制可以占用较大的磁盘空间，有利于存放日益增多的大容量多媒体信息。 另外，缓存的一致性维护策略和替换策略可以比铰复杂，从而提高命中率( h i t r a t e ) 和减少颠簸( t h r a s h i n g ) 。最后，由所有代理服务器构成的共享缓存， 可以将最接近用户的文档返回给用户，增加了信息的本地化( 1 0 c a l i t y ) ，也 降低了访问延迟。 下面，我们从代理缓存的目标出发，先分析一下实现代理缓存时应注意 的几个问题。 第二章w e b 垤存及其业务遵! ! 丝 目标l ：减少客户机和w e b 服务器之间的网络流量，降低对网络带宽的消 耗。这要求用户和代理缓存系统间的通信协议应该简单、快速，而且客户机 和代理服务器最好是在一个高速局域嘲内，这样才能实现减少网络流量的目 标。 目标2 ：加速响应，降低用户h t t p 请求的访问延迟。这要求代理缓存系 统具有良好的缓存策略和命中率，否则会因为增加了查找文档的信息反而增 加了访问延迟。 目标3 ：提供多用户访问的信息共享，降低客户机空间浪费和维护开销。 显然，一个代理服务器连接着多台客户机，是面向多个用户服务的，在代理 服务器上实现的代理缓存也应当为多用户提供信息共享。由于用户可以共享 信息，从而减少了客户机硬盘空间的浪费。 代理缓存的概念实际上是从存储体系结构( m a ) 和分布共享存储系统( d s m ) 的 缓存概念发展来的，它同样需要解决包括替换策略、一致性以及些改进和评价 性能的技术问题。后续章节将对这些技术分别进行讨论。 2 2 3h b 缓存的组织结构 根据w e b 缓存的组织结构的不同可以把w e b 缓存分为：层次结构缓存 ( h i e r a r c h i c a lc a c h i n g ) 、共享缓存( s h a r e dc a c h i n g ) 、虚拟缓存( v i r t u a l c a c h i n g ) 和分区缓存( p a r t i t i o n e dc a c h i n g ) 等。 1 层次缓存结构 层次缓存结构( h i e r a r c h i c a lc a c h i n g ) 是将处于不同位置的缓存按照层次 结构加以组织。比如由客户端缓存、地区代理服务器缓存和国家出口代理缓存等 就构成了三层缓存的结构。当客户端缓存不能满足客户的请求时，这个请求被发 送到高一层的缓存( 地区代理服务器缓存) 如果还是不能满足客户的请求。那么 这个请求还要继续向上一层发送。如果最顶层的缓存仍旧不能满足客户的请求， 则最顶层的缓存服务器就会直接访问w e b 服务器。一旦甩户请求的焉e b 文档被找 到，则按照相反的顺序把文档通过缓存的层次结构发送给用户，并在每一层的缓 存中缓存此文档，以备将来使用。层次缓存的逻辑结构如图2 8 所示。 1 4 蔓三茎堕生塑壹墨曼型堡崮堑劐生一 图2 8 层次缓存的逻辑结构图 2 共享缓存结构 共享缓存是将多个分层次或不分层次的缓存聚集在一起，并且使不同缓存中 的信息能够为其它缓存共享。共享缓存的逻辑结构如图2 9 所示。为了实现不同 缓存间信息的共享，目前提出了几种共享方法。 图2 9 共享缓存的逻辑结构 i c p 协议支持下的缓存簇- - i c p ( i n t e r n e tc a c h ep r o t o c 0 1 ) 协议支持下的缓 存簇的工作原理是：当一个缓存失效( 命中失败) 时，这个缓存就向所有与其相邻 的缓存服务器发出请求，以便确定这些缓存能否命中。如果能够从相邻的缓存服 务器中得到请求的w e b 文档，就没有必要再访问w e b 服务器。这种共享方法的一 个弱点就是：当缓存簇中缓存服务器的数量较多时，缓存之间的数据通信量和处 理工催鲞将会显著增加。i c p 协议支持下的缓存簇的实例有h a r v e s tc a c h e 和 第二章w e b 缓壹垦基些垒煎! ! 丝 s q u i dp r o x yc a c h e 等。 c a r p 协议支持下的缓存阵列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 ) 协议 支持下的缓存阵列的工作原理是：将u r l 做哈希散列，从而将松数耦会的缓存阵 列化分成不同的u r l 空间，使得每个缓存只存储相应u r l 的文件。但是，这种方 法不适合广域缓存共享。因为，一方面受到缓存之间网络带宽的限制，另一方面 各个缓存与用户之间的距离也不尽相同。 扩展i c p 协议支持下的摘要缓存一扩展i c p 协议支持下的摘要缓存( s u m m a r y c a c h e ) 的工作原理是；每个缓存除了保存自己缓存的内容外，还要保存其它缓存 当前缓存信息的目录。一个缓存服务器为了使其它服务器知道它目前所缓存的信 息，就要定期向其它服务器发布它的缓存目录，也就是说每隔一段时间缓存都要 把自己最新的缓存目录发送给其它服务器，使它们之间能够获取当前所保存的信 息。当一个缓存命中失败时，便可以在本地查询其它服务器的目录，如果查到就 向那个服务器发送请求，否则就向w e b 服务器发送请求 7 。 3 虚拟缓存结构 把缓存从逻辑上划分为n 个虚拟缓存“i r t u a lc a c h e ) ，n 个虚拟缓存成互 相串联的形式，每个虚拟缓存使用自己的替换算法，各个虚拟缓存使用的替换算 法可能相同也可能不同。虚拟缓存的逻辑结构如图2 1 0 所示。开始时，所有w e b 文档都被缓存到l 号虚拟缓存中。对象替换时服从这样的规则：从虚拟缓存i 替 换出来的w e b 文档，被转移到下一个虚拟缓存( 虚拟缓存i + 1 ) 中，直到w e b 文 档从最后一个虚拟缓存中替换出时，w e b 文档才算被真正地移出缓存。缓存中所 有再次被访问的w e b 文档将被重新缓存到l 号虚拟缓存中。这样就使得那些在一