（计算机软件与理论专业论文）rcd：一种精简的网络缓存内容摘要表达方法.pdf

太原理工大学硕士研究生学位论文 r6 2 0 3 1 5 r c d ：一种精简的网络缓存内容摘要表达方法 摘要 网络缓存技术是一种把访问过的网络对象( 网页、嵌入对 象、流媒体等) 暂存起来用于将来再次访问的网络技术。目前 研究的重点已进入网络缓存协作的新阶段。网络缓存协作使更 多的用户共享更大的网络缓存从而更进步提高网络缓存的命 中率、字节命中率，并可进行负载平衡，从而更多地节省网络 带宽、缩短用户等待对间。 ， 网络缓存协作的关键是网络缓存的内容表达。本文在对网 络缓存内容表达方法、研究动态综述的基础上，实现了一种精 简的缓存内容摘要( r c d ：r e d u c e dc a c h ed i g e s t ) 表达方法。 该方法以缓存摘要( c d ) 为基础，为每台设定的缓存服务器生 成含有被请求对象访问频率信息的缓存目录，并将网络对象进 一步分为最近访问的、最频繁访问的和很少访问的三组， r c d 只把前两组网络对象映射到缓存目录中。在此基础上，以在7 l 交换机上设置r c d 为目标，给出了r c d 缓存目录的数据结构以 及建立、更新和访问的算法，并分析了存储空间的大小以及组 太原理工大学 爱士研究生学位论文 间划分对r c d 性能的影响。 为了评价r c d 的性能，我们建立了一个以局域网访问 i n t e r n e t 为背景的软件模拟模型，它由两台网络缓存服务器， 两台交换设备还有若干客户机组成。使用n l a n rc a c h e 服务器 提供的访问记录模拟客户机的访问请求。 在模拟环境中，首先调整r c d 的参数，设定六组不同大小 的缓存摘要，再设定r e c e n t 组占整个缓存摘要的不同比例结 果表明，当r e c e n t 组占整个缓存摘要的3 7 ，5 时，r c d 性能最。 好。接着调整c d 的参数，同样设定六组不同大小的缓存摘要， 分别按照不同的更新比和不同的周期发布发布摘要，结果表明， 当以一个小时为时间间隔发布摘要时，c d 性能最好。 在以上参数设置下，取六组不同的访问记录，分别运行r c d 和c d 两种方案，实验表明，r c d 相对于c d 有较多的t r u eh i t ， 而有较少的f a l s em i s s ，但同时又有较多的f a l s eh i t 。 从整体的试验结果看，r c d 相对于在性能上有一定程度 的改进，而且这种性能的提高是在无需发布缓存摘要的基础上 获得的，节省了一定的网络带宽。 关键词网络缓存，代理缓存，网络缓存合作，缓存摘要 太原理工大学硕士研究生学位论文 ar e d u c e dc a c h e d i g e s t f o rt h ec o n t e n t r e p r e s e n t a t i o n o fw e b c a c h i n g a b s t r a c t w e bc a c h i n gc a l ls t o r ew e bo b j e c tt e m p o r a r i l yi no r d e rt c s a t i s f y r e p e a t e d w e b r e q u e s t f o rt h e o b j e c t n o w , t h er e s e a r c h e m p h a s i s i st h e c o o p e r a t i o no fw e bc a c h i n g t h et e c h n i q u e c a r l s h o r t e n l a t e n c yt i m e ； i m p r o v e w e bp e r f o r m a n c ea n de x t e n d e d c a p a c i t y a c c o r d i n g l y , i tr e s o l v e st h es c a r c i t yo fw e bb a n d w i d t h c o m ew i t ht h ei n t e r n e t d e v e l o p m e n t t h ek e yo fw e bc a c h i n gc o o p e r a t i o ni st h er e p r e s e n t a t i o no f c a c h i n gc o n t e n t n o w , w ep u tf o r w a r da n o t h e rm e a n st or e p r e s e n t t h ec a c h i n gc o n t e n t ：r e d u c e dc a c h ed i g e s t ( r c d ) r c dh a st h e 厅e q u e n c yi n f o r m a t i o no fr e q u e s t e do b j e c t s i tg e n e r a t e sd i g e s tf o r e a c hc a c h es e r v e ra n dd i v i d e sw e b o b j e c t si n t ot h r e eg r o u p s ：r e c e n t f r e q u e n ta n du n p o p u l a r r c du s e sr e c e n ta n df r e q u e n tg r o u pt o 太原理工大学硕士研究生学位论文 g e n e r a t ed i g e s t i no r d e r t ob u i l dr e di nl 7 s w i t c h ，w er e s e a r c ht h e d a t as t r u c t u r ea n du p d a t em e t h o do fr e d w ea l s or e s e a r c ht h e i m p a c to f m e m o r y s i z ea n d g r o u p i n gp r o p o r t i o n o nr e d i no r d e rt oe v a l u a t et h ep e r f o r m a n c eo fr c d ，w eb u i l da m o d e lo fl a nt h a tc a na c c e s si n t e m e l i th a st w oc a c h es e r v e r s ， t w os w i t c h e sa n ds o m ec l i e n t t h en l a n rc a c h et r a c ef i l e s i m u l a t e su s e r r e q u e s t s b y t h i sm o d e l ，w ef i r s ta d j u s tp a r a m e t e r so f r c da n dc d t or e dw h e nt h ep r o p o r t i o no fr e c e n tg r o u pi s 3 7 ，5 。t or c dw h e nr e l e a s e d i g e s te v e r y1 - h o u r , t h e i r p e r f o r m a n c ei s t h eb e s t a f t e rw ef i n dt h eb e s t p a r a m e t e r s ，w e c o m p a r e t h ep e r f o r m a n c eo fr c da n dc d w ef i n d ：r e dh a sm o r e t r u eh i ta n dl e s sf a l s em i s st h a nc d ，b u tr e dh a sm o r ef a l s eh i t i n s h o r t ，t h ep e r f o r m a n c e o fr e di sb e t t e rt h a nc d f u r t h e r m o r e ，r c dd o e s n tn e e dt or e l e a s ed i g e s tb e t w e e nc a c h e s t l a ts a v eb a n d w i d t ho f n e t w o r k k e yw o r d s ：w e b c a c h i r l g ，p r o x yc a c h e ，c o o p e r a t i o no fw e b c a c h i n g , c a c h ed i g e s t 太原理工大学硕士研究生学位论文 第一章绪论 1 。1 网络缓存产生的背景 i n t e m e t 是一个在全球范围内共享信息的互连网络。各种各样 的文字、图片、文件汇聚成了互联网这个信息海洋，这些数据是 以超文本的形式组织的，信息之间再用超链接相互联系起来。位 于世界各地的网络用户和提供网络内容的服务器是通过超文本传 输协议( h r r p ) 完成通讯的。网络用户如果需要网络服务器中的 某些内容，就会发出一个h t t p 请求，服务器接收到这个请求后， 找到所需的信息，把结果发给用户。 由于友好的用户接口和有效的信息共享能力，互联网的发展 非常迅速。然而，这种发展也给互联网带来了许多问题，如更长 的h t t p 请求回应时间，网络服务器的负载过重等。据调查显示， 网站的响应时间小于7 秒钟，用户放弃访问的比例是7 ，网站 的响应时间超过1 2 秒钟，用户放弃访问的比例急剧增加到7 0 “3 。这说明减少用户等待时间是网站建设者和用户的迫切要求。 这些问题都促使人们想办法提高网络性能。 1 2 网络缓存技术及其应用 能提供原始信息的服务器毕竟是有限的，如果所有的用户都 通过原始服务器获取信息，那势必造成服务器负担增加、用户等 太原理工大学硕士研究生学位论文 待时间延长的后果。网络缓存技术是一种把访问过的网络对象( 网 页、嵌入对象、流媒体等) 保存在缓存服务器上，以供将来再次 访阀的网络技术，它被认为是提高鼹络性链的最有效的方法之一。 网络缓存技术可以在网络代理服务器上完成，代理服务器从 一组用户群接收h t t p 请求从存放所需内容的原始服务器获取 用户请求的两络对象，将这些对象暂存起来再发给用户。这样一 来，如果把重复访问的网络对象保存在缓存中，当同样的访问请 求再次发生时，就可以直接从缓存服务器获取所需的网络对象， 从而达到缩短用户等待对闻、节省两络带宽的目的。 除了本地的代理网络缓存之外，还存在着分布式的缓存合作 机制，它使得在众多的缓存服务器之间可以实现网络对象共享， 这种更大范国内的缓存信息共享可以为更多数量的用户服务，进 一步地提高网络性能。在一个网络缓存合作的系统内，如果网络 请求在本地的缓存中未能命中，这个请求就会被发往与之合作的 l 缓存服务器去。因此，如果任何一个服务器傈存过被请求对象的 拷贝，那么这个请求就一定会被缓存系统所满足。 图卜l 网络缓存的概念模型 太原理工大学硬士研究生学位论文 f i g u r e1 - 1m o d e l o fw e b c a c h i n g 近期，出现了基于交换设备的网络缓存技术，这种技术不但 使得配置缓存系统的工作更为方便，而且更好地解决了访问无法 被缓存的h t t p 请求的重定向问题。 网络缓存对象的定位或缓存内容的表达是实现缓存合作的关 键，这是由几个原因造成的。首先，由于互联网的飞速发展，网 络环境中数据流量特别巨大；其次，虽然缓存服务器的储存能力 在不断扩大，但它能保存的内容终究是有限的：最后，在前两个 条件的制约下，需要在很短时间内对用户请求作出响应。目前有 以下几种方法实现：通过广播式查询实现定位，i n t e r a c tc a c h e p r o t o c o l ( i c p ) 叫是其代表；通过u r l 地址映射实现定位，c a c h e a r r a yr o u ti n gp r o t o c o l ( c a r p ) 嘲是其代表；利用缓存摘要实 现缓存内容表达，c a c h e d i g e s t ( c d ) “1 和s u m m a r yc a c h e 嘲使用 b l o o mf i l t e r 构造缓存摘要，是这种方法的代表。 1 3 各章节的安排 论文的各部分是如下安排的：第二章首先介绍网络访闯特性， 这些特性，是实现网络缓存的基础；接着介绍网络缓存技术的原 理和各种不同的网络缓存模型；最后说明网络缓存合作及其需要 解决的问题。 缓存对象的定位是网络缓存技术的关键部分，第三章详细介 绍了缓存对象定位和缓存内容表达的若干方法。这部分内容可以 帮助大家理解r c d 的提出和实现。 第四章是整篇论文的重点，在这一章首先分析目前的缓存内 太原理工大学硕士研究生学位论文 容表达方法所存在的问题，接着提出基于交换的网络缓存内容的 表示方法：r c d ，说明了实现这种方法所涉及的具体问题。 为了说明这种方案的可行性，第五章对其进行了性能评价。 在一个用软件模拟的环境中，利用n l a n r 缓存系统提供的访问 记录进行了实验，首先分别对影响r c d 和c d 性能的重要参数进 行了调整，接着在最优参数设置下，比较了r c d 和c d 韵性能差 异，并分析造成这些差异的原因。 第六章总结了全文，提出了最后的结论。 4 太原理工大学硕士研究生学位论文 第二章网络缓存和网络缓存合作 2 1 与网络缓存相关的网络访问特性 充分了解网络访问特性对于实现网络缓存系统十分重要，网 络对象有多大? 这些对象被重复使用的机会有多大? 它们的内容 多长时间更改一次? 这些问题对于设计网络缓存的决策都有重要 影响。 网络对象的大小 不同的网络对象的大小差异很大，知道普遍的网络对象的大 小对于决定合适的网络缓存存储能力和网络连接带宽非常有用。 研究表明：网络对象的平均大小为1 0 - 1 5 k 字节，百分之七十五的 被访问对象的大小要比这个平均大小小得多，而大型的网络对象 ( p d f 文件、音像文件) 则不经常被访问“1 。 如果缓存服务器专注于存储小的网络对象，则它就可以满足 更多的用户请求，提高系统的命中率；如果缓存服务器专注于大 的网络对象，则可以充分利用缓存空间，提高系统的字节命中率。 网络对象的类型 如今，最经常被访问的网络对象是图形对象，其次是h t m l 页面，页面经常包括内嵌的图片和指向其它页面的链接，它们大 约占所有网络请求的9 0 ，占所有下载字节的7 0 ”1 。对多媒体对 象的访问相对较少，但它占了相当大的字节数。1 。 太原理工大学硕士研究生学位论文 某些类型的网络对象，如动态网页等，无法被缓存。据测定， 大约有4 0 的网络对象是不能被缓存的旧。 网络对象的重复使用程度 网络对象被重复访问的频率与其频率排序之间遵循 “z i p f - l i k e ”分布州，即第i 个最常被访问的w e b 对缘被再次访 阕的概率p 是( 其中q 接近1 ) ： p = 1 f 。 由此可见大部分网络流量是由对少数被频繁请求的网络对象 的访问构成的，甚至有许多网络对象几乎不被访问，这对于网络缓 存而言是非常有益的。 网络对象的更新速度 了解网络对象的更新速度，对于确保用户不会接收到陈旧的 内容非常重要。研究表明，网络对象的更新对网络缓存内容与实 际内容的一致性有一定影响。但并不足以掩盖网络缓存积极的一 面3 。 2 2 网络缓存的原理及其模型 在目前已有的代理式网络缓存系统中，代理缓存被组织成层 次式、分布式和混合式三种结构，本节将具体介绍这三种结构， 并指出它们各自的优点和缺点。 6 太原理工大学硕士研究生学位论文 2 2 i 层次式缓存模型 图2 - i 层次式网络缓存模型 f i g u r e2 - 1h i e r a r c h i c a lw e bc a c h i n gm o d e l 在层次式网络缓存系统中，缓存被布置在网络中的不同层次 中3 。如上图所示，在这个网络中有四个层次的缓存：b o t t o m 、 i n s t i t u t i o n a l 、r e g i o n a l 和n a t i o n a l 。用户的缓存就处于b o t t o m 一级，当用户的缓存无法满足一个访问请求时，这个请求就被重 定位到了i n s t i t u t i o n a l 一级的缓存去。如果被请求的访问对象 在i n s t i t u t i o n a l 一层也没有找到，请求就被发往r e g i o n a l 一级， 如果仍然没有就继续发往n a t i o n a i 一级。如果所需的文件在任何 一级缓存都没有找到，最后一级的缓存服务器就会与保存所需内 容的原始服务器通讯。当文件被找到后，在把文件传给用户的途 太原理工大学硕士研究生学位论文 中，处于中介位置的各级缓存都会保存一份这个文件的拷贝，以 后对这同一个文件的访问请求就可以在某一级缓存中找到。 层次型缓存有良好的带宽荦j 用能力，经常被访闯钓页面可以 很快地发送给需要它的用户。不过这种模型也有以下问题： 口 每一层都会引入额外的延迟。 凸 处于高层的缓存可能成为整个系统的瓶殒，可能有更长 的查询延迟。 口 在不同层次的缓存都保存同一份文件的拷贝会浪费很多 存储空阀。 2 2 2 分布式缓存模型 | 艮绷 觥 晒审甾苗峨雪 图2 - 2 分布式网络缓存模型 f i g u r e2 - 2d i s t r i b u t e dw e bc a c h i n gm o d e l 最近，有入提出一种替代层次式网络缓存模型的方案，称为 分布式缓存模型“。同上一种模型不同的是，分布式模型不设置 太原理工大学硕士研究生学位论文 任何的中介缓存，就上面的例子而言，本模型只是依靠 i n s t i t u t i o n a l 级的缓存来处理未命中的记录。为了决定从哪 一个缓存获取所需文件，每个缓存需要保存与它相连的其它缓存 的数据信息。此时，可以层次式地管理这些缓存以便在检索文件 时效率更高。但是，这种层次式的管理，只关心在哪个缓存保存 了哪些文件，而并不储存这些文件本身的拷贝。 分布式缓存模型与层次式模型相比，内部流量要小得多，几 乎不会发生拥塞的情况。保存其它缓存的文件信息也只需要很小 一部分的额外磁盘空间，而且这种模型可以更好地实现信息共享， 具有更好的容错性。然而如果在一个比较大的范围内实现分布式 缓存模型可能会遇到很多问题，如无法忽视的连接延迟、更多的 带宽使用和管理问题。 2 2 3 混合式缓存模型 综合以上两种模型，在混合式缓存结构中，缓存服务器首先 以层次式的结构组织起来，在同一层的缓存之间，再用分布式技 术加以管理。 在这种方式下，被请求的网络对象可以用最短的时间从双亲 或兄弟缓存处取得，从而避免访问远程缓存服务器，如果需要的 话，也可以花最小的代价直接重定向到原始服务器。 2 3 网络缓存合作 网络缓存技术的实现最初是基于测竖器的，每个用户都有一 个独立的缓存区，这样可以在一定程度上满足用户的需求，但可 9 太原理工大学硕士研究生学位论文 能在不同用户的缓存区内，重复性地保存了相同的缓存内容，造 成不必要的浪费，限制了它的大规模使用。 代理缓存针对浏览器缓存的缺点作了改进，一组在物理上接 近的用户可以共用一个代理缓存服务器。通常组内用户有相似的 访问习惯，也就有更多相似的访问内容，代理缓存一次性地保存 这些内容，可以为更多的用户服务，更有效地使用缓存区。 但是，单个的缓存服务器所能保存的缓存内容是有限的，它所能 服务的客户也是有限的。如何使代理缓存技术有更大的可扩展性， 于是网络缓存合作( c o o p e r a t i v ep r o x yc a c h i n g ) 就应运而生了， 这是网络缓存技术发展的趋势。这种机制使得众多孤立的缓存服 务器联合起来；达到最大程度的资源共享。缓存之间了解彼此的 缓存内容，用户的请求如果在本地缓存无法满足，可以设法从其 它缓存服务器上取到所需内容。目前，网络缓存合作已经发展到 了内容传输网络阶段( c o n t e n td e l i v e r yn e t w o r k ) 。 2 4 网络缓存合作需要解决的问题 实现网络缓存合作，需要解决一系列的技术问题，最主要的 有以下两个方面：缓存对象的定位和代理的裁剪，下面分别就这 两个问题加以具体介绍。 2 4 1 缓存对象的定位 当某个用户的请求在本地代理缓存可以满足时，称为本地命 中( l o c a lh i t ) ，否则日q 作本地未命中( l o c a lm i s s ) ；如果本地 代理缓存从与他合作的代理缓存处取到所需内容，称为远程命中 1 0 太原理工大学硕士研究生学位论文 ( r e m o t eh i t h 如果只能从原始服务器处取到所需内容，叫作全 局未命中( g l o b a lm i s s ) 。 缓存对象的定位( l o c a t i o nm a n a g e m e n t ) 就是要在当本地 未命中发生时，判断究竟是远程命中还是全局未命中。下一章将 具体介绍具体的定位方法； 2 4 2 代理的裁剪 有时候当本地未命中发生时，远程命中和全局未命中都有可 能实现，需要由代理的裁剪( p r o x yp r u n i n g ) 决定究竟是从提供 内容的原始服务器获取内容，还是从相互合作的缓存服务器获取 内容。 在互联网上，当本地未命中发生时，需要决定究竟是从远程 缓存服务器还是从原始服务器去取所需内容，这对于缓存协作的 效率十分重要。这个问题看似简单，似乎只需比较用户与远程缓 i 存服务器或原始服务器之间的开销即可，如网络跳数、上次下 载的等就可以选择。但事实上这涉及到了许多技术细节，如标准 如何确定、距离值如何收集等。目前主要有两种方法可以实现代 理的裁剪： 缓存路由 缓存路由( c a c h er o u t i n g ) 是一种解决代理裁剪的一种方案， 代理缓存把在本地未命中的请求发往与它邻近的且指向原始服务 器的代理缓存，这样一来，即使在通往原始服务器途中的所有代 理缓存都没有被请求的对象，用户的这个请求也可以尽快地在原 始服务器上得到满足，剪除了一些不必要的代理缓存。这种方法 需要缓存服务器保存一张缓存路由表( c a c h er o u t i n gt a b l e ) ， 太原理工大学硕士研究生学位论文 通过这张表，每个缓存服务器都知道通往原始服务器的下一跳。 如果某一跳发生故障，可以选择直接从原始服务器取得请求对象。 近邻缓存 近邻缓存( v i c i n i t yc a c h i n g ) 也可以实现缓存的裁剪，它 根据从不同的代理缓存和原始服务器获取请求对象的不同代价做 出裁剪选择。最初，代理缓存服务器针对具体的网站定义一组近 邻，记录了从原始服务器获取请求对象所经过的代理缓存。在此 之后，本地未命中发生时，代理缓存只从近邻记录中的代理缓存 查找所需要的请求对象。 2 5 网络缓存所带来的进步 正如绪论中提到的，网络缓存可以减少网络流量和延迟。对 个人而言，改善了访问互联网时的体验。对企业而言，这项技术 可以明显减少自身对立联网的带宽需求；可以控制网络访问的内 容；减少了延迟，就减少了员工等待的时间进而提高生产力。对 互联网服务提供商( i s p ) 而言，随着带宽的节省，i s p 就可以为 更多的客户服务，从而获得更多业务：也可以减少i s p 之间的流 量，节约了i s p 的资金。有两个指标可以反映缓存的性能： 口 命中率( h i tr a t e ) = 可被缓存满足的请求数全部请 求数 口 字节命中率( b y t eh i tr a t e ) = 可由缓存提供的字节 数全部字节数 可见，命中率字和节命中率越高，就可以减少更多的延迟，节约 更多的带宽。 太原理工大学硕士研究生学位论文 下面具体说明网络缓存给我们带来的进步； 减少延迟 h 虹d i | 蛔m y 岫鼋甑 曲t姗 r h e m ts “ 、b _ j # 一， 。十厂 图2 - 3p 8 2 通过代理服务器获取一个网络对象的延迟组成 f i g u r e2 - 3l a t e n c yc o m p o n e n t s o ff e t c h i n ga no b j e c tt h r o u g hap r o x y 由上图可知，延迟主要由两部分组成。从原始服务器到代理 服务器之间的外部延迟和从代理服务器到用户的内部延迟。 研究表明，外部延迟占到了整个延迟的7 7 - 8 8 “”。如果在 代理服务器上设置缓存。用户的请求就可以由缓存满足，于 是外部延迟就被消除了。如果缓存能够达到4 5 的命中率， 那么在最好情况下可以减少的延迟为：4 5 x 8 8 = 4 0 。 节省带宽 另一个使用网络缓存的原因是节省带宽。节省带宽不仅对于 减少网络的整体开销意义重大，而且减少了和原始服务器的 连接从而间接减少了延迟。影响带宽节省的一个重要因素是 由用户发出的中止传输的命令，通常情况下，用户到代理的 连接要比从代理到原始服务器的连按慢得多。所以，当代理 太原理工大学硕士研究生学位论文 意识到用户要求中止传输时，大量的数据已经从原始服务器 下传到了代理服务器，这样就浪费了许多不必要的带宽。如 果在代理服务器上设置一个缓存，当代理发现缓存中的内容 没有及时被用户取走时，立刻停止从原始服务器获取内容， 则可以在一定程度上节省带宽。 网络缓存与流媒体 随着互联网的发展，记录声音、图象的流媒体越来越多的被 人们使用，如果把这些流媒体全部保存到缓存中，势必会占 用大量的缓存空间，夺取其它类型文件被缓存的机会。对于 这些大型的网络对象，网络缓存技术常常把它开头的一小部 分保存下来。当用户访问这个文件时，可以很快地播放一段 时间，与此同时，其余部分的数据就从原始服务器下传到了 代理服务器。这样，用户就不会感到太多的延迟。 1 4 太原理工大学硕士研究生学位论文 第三章缓存对象定位和缓存内容表达 随着网络缓存技术的深入应用，为了保存更多的缓存内容， 为更多的用户提供服务，自然要求设立众多的缓存服务器。一方 面，用户需要获取某个服务器上的某个缓存对象；另一方面，缓 存服务器之间也需要相互了解，避免重复保存同一个网络对象。 这就必须定位缓存对象和表达缓存内容，本章将详缅介绍这个闻 题。 3 1 通过广播查询实现定位 早期是通过广播式查询的方法定位缓存对象的，这种方法至 今仍在使用。当本地朱命中发生时这个代理服务器通过简单两又 广泛的查询，在与它合作的所有代理缓存中逐个查找，直到找到 所需要的w e b 内容为止。网络缓存协议( i c p i n t e r n e tc a c h e p r o t o c o l ) 是实现这种方法的协议之一。 i c p ( i n t e r n e tc a c h ep r o t o c 0 1 ) 是在网络缓存合作系统中 最常见的一种基于广播式查询的协议，既可用于层次式模型也可 用于分布式模型。i c p 是一神运行于u d p ( u s e rd a t a g r a m p r o t o c 0 1 ) 上的应用层协议。 在层次式缓存合作系统中，i c p 把不同层次的代理缓存区分 为叶、兄弟和父节点。如果一个请求在叶缓存不能得到满足，它 就向其兄弟和父节点发出查询命令，而如果还不能命中，则继续 太原理工大学硕士研究生学位论文 向上级节点查询，直到在指定的有效时间内命中为止。 在分布式缓存合作系统中，i c p 是按如下的方式工作的。用 户首先向负责为它服务的代理缓存发出某个访阊请求，当这个缓 存服务器在自己的缓存内没有发现被请求的对象时，它就向与它 合作的所有缓存服务器广播一个i c p 查询命令。如果至少有一个 缓存发现了这个对象，这些缓存就会对查询回复一个i c p 命中信 息。用户的代理缓存向第一个回复的缓存服务器发出h t t p 访问请 求，并在自己的缓存内保存一份这个被请求对象的拷贝，再将对 象发绘用户。如果在一定的对阀内没有任何一个缓存服务器发出 i c p 命中信息，用户的代理缓存就从原始服务器获取所需对象。 这种方法简单易行，当相互合作的缓存服务器设置得非常接 近时效率很高，只要其它缓存中保存有所需的对象就一定能够找 到。不过，当合作的代理缓存数量过多时，查询回应的延迟也可 能越长，而且由查询带来的网络流量十分可观。 l 3 2 通过u r l 地址映射实现定位 用一个哈希函数将不同的u r l 地址映射到不同的缓存服务器 上，从而每个缓存服务器都负责了不同的w e b 资源的子集，网络 缓存阵列路由协议( c a r p c a c h ea r r a yr o u t i n gp r o t o c o l ) 是 实现这种方法的协议之一。 举一个例子，在下图的模型中，如果有2 0 个网络对象并且简 单地认为它们的m d 5 哈希值依次等于1 。2 ，2 0 。那么，哈希值 等于l 的那个对象就被定位到了p r o x y l ，这是因为lm e d5 = i ； 哈希值等于9 的那个对象就被定位到了p r o x y 4 ，因为9m o d5 = 4 ， 1 6 太原理工大学硕士研究生学位论文 其它对象的定位方法以此类推。 q 愀( 3 1 1 i d 图3 - 1 基于哈希映射的缓存合作模型 f i g u r e 3 1t h eh a s h - b a s e dc o o p e r a t i o nm o d e l 代理缓存之间的合作可以通过把被请求对象的u r l 地址分配到不 同的代理缓存而完成。：所有的代理缓存服务器都相互连接形成网 状，而且都遵循同一个分配原则，不论哪一个代理缓存收到某个 请求后，都按照这个原则把这个请求的u r l 地址分配到特定的代 理缓存上，这样由查询回应带来的延迟就完全被避免了。 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 而言，代 理缓存之间的通信量大大减少。另一方面，这种方法可以充分地 1 7 太原理工大学硕士研究生学位论文 利用缓存空间，不会出现同一个内容被多次保存的情况。 c a r p 的效率取决于哈希函数的选择，而仅仅根据u r l 地址 无法判断其访闳频率，所以哈希函数不可能将弼络流量平均分配 到各个代理缓存上。此外，如果发生某个代理缓存被移走或加入 了新的代理缓存的情况，哈希函数就需要重新定义，而且已有的 缓存内容的布局需要重新分配。 3 3 基于缓存摘要的内容表达方法 如果把系统中被缓存的对象的位置信息收集起来，由一个目 录设备负责保存这些信息，同样可以实现缓存合作，缓存服务器 的内容变化都反映在目录中。s u m m a r yc a c h e 和c a c h ed i g e s t 可 以实现这种方法。 a 吐 矗啉节 图3 - 2 基于缓存摘要的缓存合作模型 f i g u r e 3 - 2 磷r e c t o r y b a s e dc o o p e r a t i v e c a c h i n g 同样是为了减少查询回应带来的延迟和网络流量，基于缓存 摘要的合作方法保存了其它缓存的内容信息，这样查询就可以在 本地完成。 然而，如果使用一个没有经过任何处理的缓存内容目录就会 太原理工大学硕士研究生学位论文 占用大量的缓存空间，还会导致在更新目录时产生可观的网络流 量。例如，如果我们把整个u r l 地址作为代表缓存内容的关键值， 缓存中最多保存l ，o o o ，0 0 0 个对象，每个u r 乙地址平均长度为5 0 个字节，那么这个缓存摘要的大小就为5 0 ，0 0 0 ，0 0 0 字节。如果系 统中有1 6 个相互合作的缓存服务器，那么每个缓存就需要花1 5 x 5 0 = 7 5 0 ，o o o ，0 0 0 字节来保存其它缓存的内容信息。因此，寻找 对缓存内容目录的压缩表示方法就十分重要。 s u m m a r yc a c h e 和c a c h ed i g e s t 是两种非常相似的方案，它 们都使用了一种称为b l o o m f i l t e r “”的方法来表示缓存内容。二 者最大的不同之处在于；s u m m a r yc a c h e 利用扩展了的i c p 来更 新目录，而c a c h ed i g e s t 用h t t p 来传输目录信息。 。 h l ( u r l l ) h 2 ( u 【1 1 】 h 3 ( u r l l ) h 4 ( u r l l 图3 - 3b i o o mf i i t e f i g u r e 3 3b l o o m f i t e r b l o o mf i l t e r 是一个位数组，有些位被置为l 有些位被 1 9 太原理工大学硕士研究生学位论文 置为0 。当需要向b l o o mf i l t e r 添加新的u r l 值时，需要用几 个相互独立的哈希函数对这个u r l 值进行计算，每个哈希值表明 了需要将b l o o mf i l t e r 中的哪一位置为1 。当查询每个对象是 否在目录中时，用同样的哈希函数计算，再检查b l o o mf i i t e r 中的相应位。如果所有的位都是1 ，说明b l o o mf i l t e r 没有保 存过这个记录，这个对象不在缓存中；如果所有的位都是1 ， 那么我们就可以预测这个对象在缓存中。 这是一种比较有效的紧凑式的目录表示方法，不过，使用这 种数据结构会带来一定的预测出错率，也就是有时通过计算认为 命中的记录事实上并不存在，而有时认为未命中的记录却存在着。 具体而言有以下四种情况： 口t r u eh i t ：预测认为命中，实际也存在； 口f a l s eh i t ：预测认为命中，实际并不存在； 口t r u em i s s ：预测认为未命中，实际也不存在； 口f a l s em i s s ：预测认为未命中，实际存在。 为了提高预测准确度，可以增加b l o o mf i l t e r 的位数，不过 同时也占用了更多的存储。因此，需要在预测准确度和b l o o m f ii t e r 位数二者之间进行权衡，以达到最好的效果。 太原理工大学硕士研究生学位论文 第四章r c d 一种精简的网络缓存内容摘要表 达方法 网络缓存内容的表示是实现缓存合作的关键，这是由几个原 因造成的。首先，由于互联网的飞速发展网络对象的数量特别 庞大；其次，虽然缓存服务器的储存能力在不断扩六，但它能保 存的内容终究是有限的：最后，需要在很短时间内定位用户所需 要的网络对象。 4 1 现有缓存摘要存在的问题 现有的缓存摘要方法是行之有效抟，但迩有许多不足之处， i 主要有以下两点： 每个缓存服务器不但要保存自己的缓存摘要，而且要保 存与其搔俸钦服务器鸽缓存摘要。为了提高摘要文件蛉 查找速度，摘要文件需要被存放在内存里，当协作缓存 服务器数量增多时，内存需求基大，可扩展性受限制。 缓存服务器之褥需要定觏枢互各氢筑缓存摘要。缓存取 务器越多，这些信息的通信量越大，系统开销也越大， 这同样也会影响到系统的可扩展性。 2 l 太原理工大学硕士研究生学位论文 4 2 一种在交换设备上实现的精简式网络缓存摘要 许多研究已经表明，两络对象被访溺钓频率与其频率排序之 间遵循“z i p f l i k e ”分布，即第i 个最常被访问的w e b 对象被再 次访问的概率尸是( 其中a 接近1 ) ： p = l f 。 图4 1 是根据n l a n r 的服务器在1 9 9 7 年1 2 月2 2 日记录的 访问目志统计出的结果【9 j ，其中纵坐标代表一个网络对象被访问 的次数，横坐标代表这个对象在日志文件中的排行，排行为1 表 示这是一个最频繁被访问的对象，且纵轴横轴上的数字都是对数 级的。 l 搿) o l o o 1 0 l 固4 一l “2 g f - l i k e 分毒 f i g u r e 4 1z i p f - l i k ed i s t r i b u t i o n 由此可见，排行越靠前的对象越会被频繁地访问，大部分的 网络流量是由对少数被频繁请求的网络对象的访问构成的。前面 讲到衡量网络缓存效率的标准之一是命中率，很少被重复访问到 嚣蓍嚣藏氅謦 太原理工大学硕士研究生学位论文 的网络对象对提高命中率无益。因此c a c h ed i g e s t 的缓存目录中 包含大量只被请求一次的网络对象是没有必要的，不仅增加了存 储和发布时的负担，也降低了预测的精度。 另一方面，p e ic a o 观察到，距离某个网络对象最后一次被 访问t 时间后，这个网络对象被再次访问的概率是1 t “。因此 最近发生的网络请求再次发生的可能性比较大。 根据以上事实，牛保宁副教授提出了r e d u c e dc a c h ed i g e s t 的构想“”，如果能够根据网络对象被访问的频率，把它们分为 r e c e n t 、f r e q u e n t 、u n p o p u l a r 三个组，分别代表最近、最频繁 和不经常被访问的网络对象，那么其中r e c e n t ，f r e q u e n t 两个组 内的w e b 请求在将来最有可能再次发生。于是r e d u c e dc a c h e d i g e s t 只取r e c e n t ，f r e q u e n t 两个组的内容生成缓存摘要，就 可以在一定程度上减少存储空间的使用，从而减少缓存之间目录 发布时的带宽占用。同时，命中率也不会发生太大变化，甚至还 有可能提高。 交换设备位于网络环境中的中心位置，用户的网络请求无一 例外地都是经过交换设备发往服务器的。r c d 充分利用了交换设 备的这种特点，在交换设备上构造缓存摘要，记录与交换设备相 连的各个缓存服务器上所保存的内容。 所以，r c d 是一种新的缓存内容表示方法。相对于c a c h e d i g e s t 而言，一方面，它较好地解决了c a c h ed i g e s t 的觖点和 局限性；另一方面，它是一种基于交换的网络缓存合作的实现方 法，充分利用了交换设备处于缓存合作中心位置的优势生成缓存 摘要。 太原理工大学硕士研究生学位论文 4 3r c d 的实现 4 3 1r c d 的数据结构 为了达到在海量的信息中快速定位缓存对象的目的，根据前 面提刭的b l o o mf i l t e r 的特点，可班较好的满足这种要求，r c d 也采用了b l o o mf i l t e r 作为实现缓存摘要的数据结构。 构造r c d 首先要设法根据网络对象的访问频率把它们分组， 最近发生的访谪置于r e c e n t 组，比较频繁访闯的置于f r e q u e n t 组，剩余的属于u n p o p u l a r 组。根据“z i p f l i k e ”分布及p e ic a o 观察的结论可知，对r e c e n t 组和f r e q u e n t 组内容的请求最有可 能频繁发生，它们是从所有请求中提取出来的，我们称之为 d i s t i l l a t i o n 组。最后，我们根据d i s t i l l a t i o n 组的内容生成 的缓存摘要。 图4 - 2 对网络请求的分类 f i g u r e 4 2g r o u p i n g o fr e q u e s t s 基于以上定位缓存对象的特点帮将啜络访问请求分组钓思 路，在实现r c d 时，其缓存摘要采用如下图所示的数据结构。 太原理工大学硕士研究生学位论文 b ! o o m 图4 - 3r c d 的数据结构 f i g u r e 4 - 3d a t as t r u c t u r e o fr e d u c e dc a c h e d i g e s t 4 3 2 缓存摘要的生成 如何从大量的请求中提取出d i s t i l l a t i o n 组呢? 这就要设法 统计出被访问对象的访问频率，由于网络对象纷繁芜杂，不可能 用常用的方法，如设置计数器来统计。我们的解决方法是，每来 一个请求都把它置于r e c e n t 组，这是最近发生的请求，之后的请 求到达时，都要与r e c e n t 组中的内容比较，一旦发现r e c e n t 组 内的请求再次出现，我们就认为这是个频繁发生的请求，把这 个请求信息置于f r e q u e n t 组。 太原理工大学硕士研究生学位论文 图4 - 4 生成r c i ) 的流程图 f i g u r e 4 - 4f l o wc h a r to fr c ds e t u p ( 注：b f r 表示r e c e n t 组，b f f 表示f r e q u e n t 组) 在交换设备上，r c d 为相互协作的每个缓存服务器设置各自的 缓存摘要。这样一来，自然简化了缓存之间的合作，用户的网络 请求到达之后，交换设备可以很快地判断有没有用户需要的内容， 并指出这些网络对象在哪一个缓存服务器上。而且当需要从原始 服务器获取在缓存服务器没有的内容时