web缓存替换策略和预取技术的研究论文.pdf

abstract ii 摘摘 要 要 随着 internet 网络技术的飞速发展，互联网上信息量、接入用户数量的急剧 膨胀，internet 已经成为人们日常生活的一部分。但是，由于网络带宽是有限的， 用户的访问延迟往往比较大，网络的服务质量就不高。这时，就有了 web 缓存 技术和 web 预取技术，这两种技术都能很好地改善网络带宽性能、解决网络堵 塞和用户访问延时时间过长等问题。 本文描述了 web 缓存和预取的基本概念和关键技术、 缓存系统和预取系统的 分类、架构以及工作机制。主要创新点就是结合用户的感兴趣程度和 web 对象 的访问特性对缓存替换算法做了改进，然后再通过分析用户访问日志，并以此为 依据建立预测模型，将 web 缓存与预取技术相结合，共同提高网络性能。 本文的主要工作以及贡献如下： (1) 现有的 web 缓存替换策略及其相关替换算法没有充分利用 web 对象的访问 特性和用户的感兴趣程度，往往缓存的命中率不到 40%。为了能最好的减少 用户访问延迟和网络带宽消耗，本文基于 gdsf 缓存替换策略，并结合 web 对象的访问特性、web 对象所属的内容类型以及用户兴趣这几个因素，提出 了一种新的 web 缓存替换策略 gdsf-ai， 并运用一个 iptv 系统的日志驱动 的方法对其进行了性能比较和验证。实验结果表明本算法所能获得的命中率 可以达到 52%，字节命中率可以达到 41.5%。 (2) 目前对于 web 预取和缓存替换方面的研究大多是对预取技术和缓存替换策 略各自缺陷的研究，缺乏预取和替换策略相互结合的策略的研究。本文首先 提出了一种基于用户兴趣的 interest-top 预测算法，并结合上面提出的 gdsf-ai 缓存替换算法，提出一种 web 缓存与预取想结合的策略 p-gdsf-ai。运用一个 iptv 系统的日志驱动的方法对其进行了性能比较和 验证。实验结果表明本算法所能获得的命中率最大可以达到 56.5%，字节命 中率可以达到 45.6%，比不用预期技术有至少 4%的提升，进一步提升网络 性能。 需要注意的是，本文对上面提出的两种策略的仿真实验是在一个上海文广互 动电视有限公司（sitv）的下载式播放机顶盒系统中进行的，使用缓存命中率 和字节命中率作为评价标准，与传统的 lru、size 和 gdsf 等算法相比，实验 结果表明上面两种策略在 iptv 的缓存系统中，充分考虑 web 对象的访问特性、 内容的类型以及用户的兴趣等因素，能够更好地提高系统性能。 关键词关键词：web 缓存、缓存替换、web 预取、预测算法 abstract iii abstract with the rapid development of network technology and the exponential growth rate of web information and users, internet has become part of our everyday life. however, because the network bandwidth is limited, the user perceived access latency and the quality of service of the network have become an urgent problem. thus, web caching and prefetching have been recognized as the effective schemes to alleviate the server bottleneck , reduce the network traffic, and minimize customers access latencies. in this thesis, the basic concepts, key technologies, classification , structure and mechanism of web cache and web prefetching systems are described. then, a new web cache replacement algorithm, based on users interest and access characteristics, is proposed and a prediction model, through analyzing users access logs, is build, which allowed us to integrate web cache and web prefitching to improve network performance. the main research and contributions can be described as follows: (1) most of web cache replacement policies do not take full advantage of users interest and the access characteristics, and the hit rate is less than 40%. then based on the gdsf algorithm and joined users interest, content types and the access characteristics of the target of web, a new replacement algorithm named gdsf-ai (greedy-dual-size-frequency-access-interest) is proposed. through simulation experiments in a iptv system and compared with traditional algorithms, this strategy has better network performance, where hit rate can reach 52% and byte hit rate can reach 41.5%. (2) at present, web caching and prefetching technology research only emphasized on the improvements of replacement policy and prefetching algorithm, lack of the research is the combination of replacement policy and prefetching algorithm. in the thesis, according to the users interest and the access characteristics, we propose the interest-top prediction algorithm. then, combined with the web cache replacement algorithm gdsf-ai and web prefetching, a new strategy named p-gdsf-ai is proposed. through simulation experiments in a iptv system and compared with traditional algorithms, this strategy has better network performance, where hit rate can reach 56.5% and byte hit rate can reach 45.6%. we should pay attention to that our simulation experiments is based on the “download-play” set top box system in sitv. using the cache hit rate and byte hit rate abstract iv as the evaluation of standards, the algorithm gdsf-ai and the strategy p-gdsf-ai presented above are compared with other traditional algorithms lru, size and gdsf. then, the results show that joined users interest, content types and the access characteristics, the algorithm gdsf-ai and the strategy p-gdsf-ai can improve the iptv cache system performance effectively. keywords: web cache, replacement algorithm, web prefetching, prediction algorithm 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：_ 签字日期：_ 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版， 允许论文被查阅和借阅， 可以将学位论文编入 中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 公开 保密（_年） 作者签名：_ 导师签名：_ 签字日期：_ 签字日期：_ 第 1 章 绪论 1 第 1 章 绪论 第 1 章 绪论 1.1 引言 随着 internet 网络技术的飞速发展，互联网上信息量、接入用户数量的急剧 膨胀，internet 已经成为人们日常生活的一部分。但是，由于网络带宽和网络负 载的限制，用户的访问延迟往往比较大，网络的服务质量就不高。这时，就有了 web 缓存技术和 web 预取技术，这两种技术都能很好地改善网络带宽性能、解 决网络堵塞和用户访问延时时间过长等问题。本文研究的课题就是有效地利用 web 缓存和预取技术，并把这两者相互结合起来，更好地提高用户体验，优化网 络服务质量。 1.2 研究背景和意义 由于 internet 网络应用的飞快增长、接入 internet 的用户数量剧烈增加以及 web 服务和网络上所固有的延迟， 使得网络负载和网络资源拥堵日益严重， 用户 的服务质量还是得不到很好的保证。 引起 web 服务浏览、访问延迟的因素主要有以下 2 个： (1) 由于物理条件的限制造成的延迟，包括由于计算机硬件限制而不同的数据处 理能力、传输媒介的物理特性、网络带宽、网络拓扑结构等； (2) 由于网络协议上存在的缺陷造成的传输时间的延迟，从而引起一些不必要的 网络带宽消耗。 针对这两个因素，本文可以从以下两方面进行改进：一方面是从物理性能角 度加以改进，例如加大网络上的带宽、使用服务器的集群技术构架分布式系统、 升级服务器硬件设施以提高数据处理能力、 在网络中常发生堵塞的节点上增加镜 像服务器等等；另一方面，从网络性能角度加以改进，例如完善网络协议、使用 web 缓存技术、使用 web 预取技术等等。 可以通过对 web 用户访问行为的跟踪，对 web 对象的访问特性进行深入研 究，将 web 对象的访问特征归纳为以下几点： (1) web 对象访问频率服从 zipf-like 定律16：web 页面的访问规律不是均匀的， 总是会有某一些被访问次数比较多的页面，也就是热点页面，网络上 web 请求中大约有 80%是对这些访问频率排名在前 20%内的热点页面发起的34。 (2) web 对象的大小服从重尾分布： web 对象大小的这种重尾分布是表现出用户 第 1 章 绪论 2 访问比较多的是较小的对象，而对较大的对象访问相应较少。 (3) web 对象访问具有时间局部性：这个时间局部性表示了用户以前访问过的 web 对象在将来会被再次被访问的概率较高， 也就是 web 对象如果距离用户 上一次访问的时间间隔越短，它越有可能会在不久的将来被用户再一次访 问。 (4) web 对象访问具有空间局部性： 这个空间局部性表示了与当前被访问的 web 对象在物理位置接近的对象在不久的将来被访问的概率较大。 从这些 web 对象的访问特性中，可以看出通过使用缓存来提高网络服务质 量，减少网络带宽消耗和用户访问延迟是可行的。然而大量的研究实验表明32， 无论采用哪种缓存策略，缓存命中率 hr 大概都只有 40%到 50%之间。这里，引 入了 web 预取技术来更进一步改善 web 性能，提高缓存的命中率。web 预取的 基本思想就是， 按照一定的预测算法将用户在不久的将来即将可能要访问到的页 面，在用户的请求还没发起之前，就提前预取到用户的缓存当中，这样，用户对 已经预取过的页面中的某一个页面发起请求时， 由于这个相应的页面在本地的缓 存已经存在，因此能在请求的第一时间直接获取到，从而大大减少了用户请求后 的等待时间。 1995 年，pcao 首先提出了 web 缓存与预取相结合的思想33，并且给出这 种结合所要遵循的四条法则: (1) 最优预取，也就是总是预取用户即将要访问的 web 对象； (2) 最优替换，也就是总是替换那些长时间没有被访问的 web 对象； (3) 无副作用，也就是预取的 web 对象是不会对系统的总体性能产生副作用的； (4) 第一机会，也就是要尽可能在第一时间完成 web 预取和替换过程。 其中前两条法则说明了 web 预取和替换的对象是哪些，后两条法则说明了 web 预取和替换的要求以及时刻。 这四条法则中只是一条是指导性的， 而且并未 规定 web 预取和缓存的具体策略。 如何将 web 缓存技术和预取技术相结合起来， 建立一个有效的 web 缓存与预取结合模型，是目前提高 web 网络性能的一个关 键研究点。 1.3 研究现状 1.3.1 web 缓存的研究现状 设计一个 web 缓存，需要考虑以下几方面问题： (1) 缓存系统的结构 第 1 章 绪论 3 这个部分主要研究的是 web 缓存系统的部署和系统架构。 主要包括层级 web 缓存系统架构、分布式缓存架构和混合式缓存架构这 3 种架构： 层级 web 缓存系统架构：在这种层级 web 缓存系统架构下，web 缓存被划 分为父缓存和子缓存，并以一棵树的形状进行构建，子缓存可以查询父缓存，但 反过来不可以。这种架构的一个缺点是父缓存可能会负载过重。 原始服务 器 web客户 端 d e f g b c a a：根缓存 b、c：父亲缓存 d、e：孩子缓存 d、e、f、g：兄弟缓存 层级缓存 图图 1-1 层级 web 缓存系统架构 分布式缓存系统架构：这种架构通常使用缓存阵列路由协议 carp（cache array routing protocol）3536，将 url 地址空间分割成几个不同的缓存空间， 每个缓存空间储存那些指定给它的 url 的 web 对象，这样，就可以根据用户请 求的 web 对象的 url 来决定将相应的请求转发给哪一个缓存空间。 这种架构的 优点是，大部分网络流量都是在网络底层中产生的，网络堵塞发生的概率较小， 空间利用率比较高。 混合式缓存系统架构：在混合架构缓存中，缓存与在层级架构中的同一层之 间的缓存是通过层级架构缓存协作的， 与在层级架构中的高层之间的缓存的通过 分布式缓存进行协作的。icp3738协议就是混合缓存的一个典型代表。 (2) 缓存替换策略 由于 web 缓存的存储容量大小总是有限的， 当存储空间都被占满时， 新来的 对象就没有足够的空间来继续保存， 这是就需要一种有效的替换策略把当前缓存 空间中价值最小的对象替换出去。 缓存替换的处理流程如图 1-2 所示。 目前，缓存的替换策略可分为 4 类：基于访问次数的替换策略、基于访问时 间间隔的替换策略、基于网页大小的替换策略、基于成本/价值模型的替换策略。 第 1 章 绪论 4 而比较有代表性的有 lfu（least frequently used） 、lru（least recently used） 、 gdsf（greedy dual size frequency） 、gdsize（greedy dual size）等。 图图 1-2 缓存替换处理流程图 缓存替换策略的性能很大程度上依赖于 web 对象的访问特性， 怎样让替换算 法具有自适应能力，如何根据不同的 web 对象的访问特性来自适应调整缓存的 替换行为，已经成为缓存研究的热点。 (3) 缓存一致性 缓存的一致性主要可以分为 2 类：弱一致性机制和强一致性机制12。一致性 的处理流程如图 1-3 所示。 a) 弱一致性机制: 弱一致性机制是用户发起请求时可能响应陈旧的网页的缓存一致性机制。常 见的有以下 4 种： ? ttl（time-to-live）机制：这是最常用也是最简单的一致性机制，它对缓 存中的每个对象都设定出一个生存周期 ttl，将它作为缓存中的对象是否仍 然有效的判断时间； 开始 需要存储新的 web 副 本， 但缓存剩余空间不足 替换排好序的列表中对 应的缓存副本 按某个标准对缓存中副 本进行排序 缓存中剩余空 间是否足够 保存新的 web 副本 结束 第 1 章 绪论 5 图图 1-3 缓存一致性处理流程图 ? 自适应 ttl（adaptive time-to-live）机制：这个机制利用 web 对象的生命 周期特点， 即如果一个 web 对象在过去很长一段时间内都没有被修改， 那么 它将来会被修改的概率就很小。 这样， 缓存中的对象的 ttl 值就可以指定为 这个对象当前“生命点”的一个百分比，其中“生命点”表示系统当前时间 减去缓存中对象的最后修改时间； ? 用户查询机制： 这种机制是由代理缓存系统定期地发起到 web 服务器的请求 来确认缓存中的当前对象是否仍有效； ? 稍带无效（piggyback invalidation）机制：这种机制主要有 3 种方法，一是稍 带缓存有效 pcv（piggyback cache validation） ，代理缓存通过发送一个捎带 可能过期的缓存列表的请求到 web 服务器， 返回的响应是无效的或过期的缓 存对象列表，代理服务器根据这个列表更新缓存；二是稍带服务器无效 psi （piggyback server invalidation） ，服务器给代理缓存一个自从上次访问后修 改过的对象列表，代理缓存更新这个列表中的对象，并且扩展其他不在列表 中的对象的生命周期；三是将 pcv 与 psi 相互结合。 b) 强一致性机制： 强一致性机制是指对用户发起请求总是响应新鲜的网页的缓存一致性机制， 常见的有以下 2 种： 开始 用户请求的网页在 代理缓存中已存在 缓存中副本是 否新鲜 从 web 服务器获取网 页， 同时更新缓存中副本 响应给用户 结束 第 1 章 绪论 6 ? 无效（invalidation）机制：这个机制要求 web 服务器记录缓存副本保存的路 径信息， 当 web 对象被修改时， 对相关路径上的代理服务器缓存中的相关对 象通知无效化。当用户对这个被通知无效的对象发起请求时，代理服务器就 会将直接把这请求转发到 web 服务器上，重新获取对象。 ? 每次查询 （polling-every-time） 机制： 代理服务器对用户发起的每一个请求， 都先认定它的缓存副本是无效的， 同时再发起一个请求到 web 服务器上， 验 证这个缓存副本是否仍然有效。 1.3.2 web 预取的研究现状 web 预取的基本思想是：按照一定的预测算法将用户在不久的将来即将可能 要访问到的页面，在用户的请求还没发起之前，就提前预取到用户的缓存当中， 这样，用户对已经预取过的页面中的某一个页面发起请求时，由于这个相应的页 面在本地的缓存已经存在，因此能在请求的第一时间直接获取到，从而大大减少 了用户请求后的等待时间。按照 web 预取的方式预取可分为以下 3 类23： (1) dns 预取 由于客户端主机与web服务器建立好一个连接以前， 必须先得把请求的url 中的相关主机信息转变为 ip 地址，这样，就会产生用户请求的延迟。dns 预取 就是为了避免这些用户请求延迟的产生， 使客户端主机在用户发起请求之前就先 将名称转变为 ip 地址。 (2) 连接预取(connection prefetching) 由于客户端主机需要和 web 服务器或代理之间建立一个 tcp 连接，通过这 个打开的 tcp 连接来发起请求，所以 web 传输的延迟就来源于这两个主机之间 的连接的建立时间、 在服务器端的排队等待时间和发生丢包时恢复数据所附加的 延迟时间等等。连接预取方式就是为了对用户隐藏这些相关连接延迟，在用户发 起请求之前，客户端主机就提前和 web 服务器建立好 tcp 连接。 (3) http 预取 预取大多是集中在从 web 服务器上预取 http 响应， 而影响接收 http 响应 的延迟的因素有多方面的，包括服务器上生成 http 响应消息所需要的时间、服 务器与客户端之间的带宽以及传输延迟等等。http 预取就是通过提前对 web 服务器发起 http 请求并将相应的响应保存在高速缓存当中。 web 预取技术的核心是用户行为的预测算法。当前用的最多的预取算法主要 有 4 种：基于用户访问模式的预取算法、基于链接的预取算法、基于 web 对象 流行度得预取算法、基于用户兴趣的预取算法。第 4 章中会有具体的介绍。利用 用户的访问日志，利用数据挖掘技术来预测用户将来的行为，从而更加准确地加 第 1 章 绪论 7 以预取。 1.4 课题研究内容 本课题研究的目的主要是研究并且实现一种 web 缓存系统中基于用户兴趣 和 web 对象访问特性的替换算法，从而在缓存空间大小一定的前提下，尽可能 地提高 web 缓存系统的命中率和字节命中率， 使 web 缓存系统的服务质量提高。 并且在此基础上，再研究分析了 web 预取技术，提出一种 web 预取与缓存相结 合的算法。 本文的主要研究以及贡献如下： (1) 现有的 web 缓存替换策略及其相关替换算法没有充分利用 web 对象的访问 特性和用户的感兴趣程度，往往缓存的命中率不到 40%。为了能最好的减少 用户访问延迟和网络带宽消耗，本文基于 gdsf 缓存替换策略，并结合 web 对象的访问特性、web 对象所属的内容类型以及用户兴趣这几个因素，提出 了一种新的 web 缓存替换策略 gdsf-ai， 并运用一个 iptv 系统的日志驱动 的方法对其进行了性能比较和验证。实验结果表明本算法所能获得的命中率 可以达到 52%，字节命中率可以达到 41.5%。 (2) 目前对于 web 预取和缓存替换方面的研究大多是对预取技术和缓存替换策 略各自缺陷的研究，缺乏预取和替换策略相互结合的策略的研究。本文首先 提出了一种基于用户兴趣的 interest-top 预测算法，并结合上面提出的 gdsf-ai 缓存替换算法，提出一种 web 缓存与预取想结合的策略 p-gdsf-ai。运用一个 iptv 系统的日志驱动的方法对其进行了性能比较和 验证。实验结果表明本算法所能获得的命中率最大可以达到 56.5%，字节命 中率可以达到 45.6%，比不用预期技术有至少 4%的提升，进一步提升网络 性能。 1.5 文章的组织结构 本文共分 5 章： 第 1 章“绪论” ，介绍了研究背景和意义、分析 web 缓存与预取的研究现状， 并介绍了论文的研究内容和章节安排。 第 2 章“相关技术研究” ，介绍了 web 缓存和预取技术的基本概念以及各自 的关键技术，包括缓存方面的 web 访问特性，工作机制，评价标准以及预取方 面的分类、建模等。 第 1 章 绪论 8 第 3 章“一种基于用户兴趣以及 web 对象访问特性的替换算法” ，首先分析 了 web 缓存替换策略中的一些问题，以及替换算法的分类，其次着重研究了那 些影响缓存替换的因素，并且基于现有的 gdsf 缓存替换策略，结合 web 对象 的访问特性、web 对象所属的内容类型以及用户兴趣，实现了一种改进的 web 缓存替换策略 gdsf-ai，并运用日志驱动的方法对其进行了性能比较和验证。 第 4 章“web 预取与缓存替换相结合” ，首先分析了目前 web 预取算法的分 类，其次，研究了 web 日子挖掘以及数据预处理的流程，在此基础上提出一种 基于用户兴趣的 interest-top 预测算法，并结合上面提出的 gdsf-ai 缓存替换算 法，完成一种 web 缓存与预取想结合的策略 p-gdsf-ai。运用日志驱动的方法 对其进行了性能比较和验证。 第 5 章“总结与展望” ，对论文工作进行总结并对今后的研究和工作展望。 第 2 章 关键技术研究 9 第 2 章 关键技术研究 第 2 章 关键技术研究 2.1 引言 web 缓存和预取技术是提高 www 性能的最主要方法，两者都属于延迟容 忍技术1。延迟容忍技术的基本思想是，当处理器正在处理一个具有较高延迟的 事件的同时，还可以并行地处理别的任务事件，这样并行的计算时间就可以将延 迟时间隐藏。随着 web 流量和访问用户数目的大量增加，出现了一下网络堵塞、 访问延迟高、服务器负载过重等等问题，使得网络对用户的服务质量变差。web 缓存与预取技术正是解决这些问题的有效技术。 本章中主要介绍 web 缓存与预取的一些关键技术，包括 web 缓存的系统部 署、web 对象的访问特性、缓存的工作流程和工作机制以及 web 预取的基本理 论、分类和建模等等。 2.2 web 缓存关键技术 web 缓存的思想是“取一次，用多次” ，利用了 web 页面的访问时间局部性。 web 缓存服务器将用户访问频率高的内容保存到离用户较近的缓存中， 当用户再 次访问时就可快速获取，这样大量减少重复数据的传输，节省了网络带宽、减轻 了服务器负载、减少了网络延迟。 本章总结了关于 web 缓存与预取的相关技术。首先介绍了 web 对象的访问 特性与 web 缓存的工作机制，其次介绍了 web 预取的相关理论、分类。 2.2.1 web 缓存系统的部署 web 缓存系统根据所处位置的不同，可分为客户端缓存、代理服务器缓存和 服务器端缓存。 (1) 客户端缓存 位于用户浏览器上的，浏览器会把一段时间内用户所有浏览访问过的页面保 存在本地硬盘上， 下一次有相同的访问请求时就可以不用等待延迟而直接在本地 获取到。 (2) 代理服务器缓存 位于用户客户端和 web 服务器之间，按照它靠近客户端或者是靠近 web 服 务器端，又可分为前向代理和反向代理这两种。其中，靠近客户端是前向代理， 第 2 章 关键技术研究 10 它的分布如图 2-1 所示： 图图 2-1 前向代理缓存服务器 而靠近 web 服务器端的是反向代理，它的分布如图 2-2 所示： 图图 2-2 反向代理缓存服务器 (3) 服务器端缓存 服务器端缓存通常都是牺牲 web 服务器的一部分内存用来当作缓存空间， 当 用户对 web 服务器发起请求时，服务器就把对象保存在缓存空间中，当下一次 有相同的访问请求来时，就可以直接从缓存中将对象返回给用户。 2.2.2 web 访问特性 web 对象的访问特性对 web 缓存系统具有重大的影响。它决定了 web 对象 的流行度，反映了用户的访问习惯和浏览深度，对 web 缓存的一致性和替换策 略的高效性有积极的作用。 大量研究141516发现 web 对象访问具有以下几个特征： (1) web 对象访问具有时间局部性 时间局部性， 是指用户以前访问过的 web 对象在将来会被再次被访问的概率 较高，即距离用户上一次访问的时间间隔越短的 web 对象，越有可能会被再次 被访问到。 (2) web 对象访问具有空间局部性 路由器 客户端 客户端 互联网缓存 web 服务器 web 服务器 web 服务器 路由器 客户端 客户端 互联网 缓存 web 服务器 web 服务器 web 服务器 第 2 章 关键技术研究 11 空间局部性， 是指与当前被访问的 web 对象在物理位置接近的对象在不久的 将来被访问的概率较大。 (3) web 对象访问频率服从 zipf-like 定律16 研究1415表明，internet 中的许多现象都满足 zipf 定律（这是一个统称，包 括 zipf 第一定律和 zipf 第二定律） 。 a) zipf 第一定律 zipf 第一定律适用于中高频词16， 这个定律是美国语言学家 zipf 发现的， 他 在 1932 年研究单词的出现频率时，发现每个单词出现频率 p 和它的符号访问排 名 j 之间存在下面的幂函数关系： j c p j = （2-1） 其中，c 为常数，更为一般的表达式为： j c p j = （2-2） 其中，是一个接近 1 的参数。 （2-1）称为 zipf 基本定律。 （2-2）称为 zipf-like 定律。 b) zipf 第二定律 zipf 第二定律适用于低频词，它的关系函数表示为： 1 2 (1) n i in n = + （2-3） 其中，i1表示频次为1的词的总数，in表示频次为n的词的总数。 不仅web对象的访问满足zipf分布，而且用户对一个网站的web页面请求 次数、 一个网页的链接数量以及视频点播vod的访问模式等等都存在这种现象。 在实际中，可以利用zipf-like定律对高频对象建立web对象访问频率模型。对 于低频对象，可以通过zipf第二定律来建立模型。高频对象和低频对象的分界， 需要根据具体的业务和用户访问特征以及web流量来确定。 (4) web对象大小服从重尾分布 web服务器上的文档大小，表现出重尾（heavy tailed，ht） 16的分布特性， 表达公式如下： (),02p xxxx t2时，用户需要等待一点时间才能访问对象a； b) t3=t2时，对象a的访问时间为0； c) t3 total，此时就意味着缓存中必须进 行对象替换，这时，首先要在缓存中选择k个具有最小代价值h(i)的对象组 i1，i2，ik，它们满足如下2个条件： 1 ( ) k j j usedsize itotal = （3-6） ( )( )( ) 12k hh.hiii （3-7） 第 3 章 web 缓存替换策略的研究 28 然后，就会有下面2种情况发生： （i） 如果请求的对象i不在这k个对象i1，i2，ik中，那么l的值就位 这k个对象中价值h最大的那个的价值，used值也发生了改变，按下 面的2个公式 1 max( )( ) k jk j lh ih i = = （3-8） 1 ( ) k j j usedusedsize i = = （3-9） 计算得到l和used的值； 同时替换掉这k个对象i1，i2，ik，把新对象i存放到缓存中。 （ii） 如果请求的对象i在这k个对象i1，i2，ik中，那么就容易多了， 这种情况表明新对象i的价值不足以被缓存，不需要替换任何对象，只 要把used值恢复到原来大小，即used=used-size(i)。 gdsf策略实现起来稍微复杂些，但由于考虑了web对象的访问次数，所有 能够更好得将价值小的对象从缓存中替换出去，目前使用也比较广泛。但是，正 如前面分析的影响缓存替换的因素中，还有web对象内容类型、流行度，修改 频率这几个因素没有考虑，算法还有进一步改进的空间。 gdsf策略的具体流程如下图3-2所示。 尽管gds策略和gdsf策略这两者的缓存命中率hr都相对比较不错，但 是字节命中率bhr就不是很理想， 而且两者都没有充分利用web对象的访问模 式特性14 15 16。虽然gdsf中使用了web对象的访问频率，这在一定程度上反 映出了web对象的流行度， 但是这并不足以表示web对象访问特性中的局部性， 例如web请求之间的时间间隔也可以反映出一定的局部性信息。 3.5.3 gdsf-ai 策略设计分析 本节基于gdsf缓存替换策略，结合web对象的访问特性、web对象所属 的内容类型以及用户兴趣，实现了一种改进的web缓存替换策略，实现较好的 缓存命中率和字节命中率。 由上一节影响缓存替换的因素的分析，可以知道，一个有效的缓存替换策略 必须还要考虑这几方面的因素：获取web对象所需的代价、web对象所属的内 容类型、web对象被再次访问的概率以及用户对web文档的感兴趣程度等等。 第 3 章 web 缓存替换策略的研究 29 图图 3-2 gdsf-策略的具体流程图 usedtotal 用户请求队列 fr(i)=fr(i)+1 ( ) ( )( )* ( ) value i h ilfr i size i =+ 初始化 l=0; used=0; 激活队列中的下一个用户请求 fr(i)=1 ( ) ( )( )* ( ) value i h ilfr i size i =+ used=used + size(i) 保存 i 选择 k 个具有最小代价 值 h(i)的对象 i1,i2,ik 并且这 k 个对象满足 1 ( ) k j j usedsize itotal = ( )( )( ) 12k hh.hiii 对象 i 是否 在缓存中 对象 i 属于 i1,i2,ik used=used-size(i) 1 max( )( ) k jk j lh ih i = = 剔除 i1,i2,ik 1 ( ) k j j usedusedsize i= 保存 i 第 3 章 web 缓存替换策略的研究 30 (1) 获取web对象的代价 获取web对象的代价value通常有3个不同的标准： a) 代价为常数 假设每个web对象获取的代价都是相同的，可以设置value=1； b) 代价为延迟时间 获取web对象的代价是和这个对象的延迟时间成正比的， 延迟时间越大， 代 价也就越高，而对象延迟的时间又是和当时具体的网络状况有关，所有这种标准 不是很合适； c) 代价为由于引入缓存而节省的传输的包的个数 本章我们使用的就是对获取web对象的代价value用因缓存而节省传输的包 个数作为代价，即设置为 value=2+size/536 （3-10） 其中536byte表示tcp的分段大小。 (2) web对象所属的内容类型 按照上一节的讨论，web对象所属的内容类型本文就取text、image、 video、audio、application和other这六种。根据实际的应用，对不同 的对象的内容类型进行划分，并且按照系统的侧重点不同对web对象的价值进 行加权。这里，我们可以按扩展名来对不同的内容类型，进行区分，并对web 对象所属的内容类型的权重比例通过可以按照所有请求中的内容类型的比例数 来确定。 (3) web对象被再次访问的概率 影响着web对象被再次访问的概率的因素主要有web对象的流行度、web 对象被访问的次数和对象访问请求之间的时间间隔这几个。因此，我们可以结合 web对象访问特性中的zipf定律、对象的访问次数和访问请求之间的时间间隔 来计算web对象被再次访问的概率： 1 ( ) ( )() ( ) fr i p i t i = （3-11） 其中p(i)就是web对象被再次访问的概率6，fr(i)是web对象的访问次数，t 是请求的时间间隔, 是zipf定律中的参数。 (4) 用户对web文档的感兴趣程度 本文中我们将用户兴趣模型用向量空间表示为7： 1122 ,., nn qk wqk wqkwq= ? (3-15) 参数k表示用户兴趣的术语，参数wd为其权重，它是由局部权重lw和全局 权重qw这两部分组成，且有 wd = lw * gw (3-16) （ii） 局部权重lw的计算 局部权重表示的是用户兴趣术语k在web页面中不同位置上不同的重要程 度。web页面有一个特点，即是半结构化，就可以利用web页面中的各种标 签（tag）来判断术语k在页面中的位置，例如正文标签text、标题标签title， h1,h2,h3,h4,h5、超链接标签url以及页面描述，根据不同位置上重要性的 不同来计算权重。定义术语k在 i d页面中的正文上出现的次数为 , .i t txt d，在标 题上出现的次数为 , .i t th d，在超链接上出现的次数为 , .i t url d，在页面描述上出现 的次数为 , .i t desc d，那么局部权重lw的计算为： ,1, .2, .3, .4, . * d ti t txti t thi t urli t desc lwdddd=+ (3-17) 这里 1 、 2 、 3 、 4 表示术语在页面不同位置上的重要程度。 （iii） 全局权重gw的计算 定义web缓存中所有web对象的总数为m，其中含有术语k的web对象数 目为n，那么全局权重qw的计算为： 2 log/1 t gwm n=+ (3-18) 第 3 章 web 缓存替换策略的研究 32 c) 用户兴趣程度的函数表示： 给定用户兴趣向量q，web对象i，对于这两者之间的相似程度，可使用余 弦计算公式计算，即： 1 22 11 (*) ( , ) ()*() n kk k nn kk kk wdwq sim q i wdwq = = = (3-19) 函数的取值范围是0到1，相似度越高越接近1，没有相似之处时为0。 进一步考虑web对象i的访问频率fr(i)，得到用户感兴趣度函数： ( ) 1) ( , ,( )( , )* fr i score d i fr isim d ie = (3-20) 这个函数的值越大，表示用户对对象i感兴趣的程度越高。 根据以上几个因素的分析，在原先gdsf策略的基础上，本文提出gdsf-ai （greedy-dual-size-frequency-access-interest）替换策略，其本质就是把缓存中 价值h(i)值最小的web对象替换出去，它的目标函数可以描述为： ( )*( ) ( )*()*( ,( ) log( ) type p ivalue i h ilvscore i q fr i size i =+ (3-21) 其中， type v是web对象所属的内容类型在所有请求中所占的比例数，value(i) 是获取web对象所需的代价，p(i)是web对象被再次访问的概率，参数l是一 个膨胀因子，其作用和gdsf中的l的作用一样，( ,( )score i q f i是用户对该 web对象的感兴趣程度。 3.5.4 gdsf-ai 策略流程 gdsf-ai策略在原有的gdsf策略基础上，充分考虑了获取web对象所需 的代价、web对象所属的内容类型、web对象被再次访问的概率以及用户对web 文档的感兴趣程度这几个因素，使用目标函数（3-21）来计算出缓存中所有web 对象的价值h（i） ，其次，根据这个h（i）值来对对象进行由高到低的排序工作， 当缓存剩余空间不足以保存新的对象时就将缓存中具有最小h（i）值的对象替 换出去，同时，缓存中所有对象都要按照被替换的对象的h（i）值来根据目标 函数重新计算。 gdsf-ai策略的具体流程如下图3-3所示： 第 3 章 web 缓存替换策略的研究 33 图图 3-3 gdsf-ai 策略的具体流程图 gdsf-ai的伪代码如图3-4所示： usedtotal 用户请求队列 fr(i)=fr(i)+1 ( )*( ) ( )*()*( ,( ) log( ) type p ivalue i h il vscore i q fr i size i =+ 初始化 ; ; q; type v l=0; used=0; 激活队列中的下一个用户请求 fr(i)=1 ( )*( ) ( )*()*( ,( ) log( ) type p ivalue i h il vscore i q fr i size i =+ used=used + size(i) 保存 i 选择 k 个具有最小代价 值 h(i)的对象 i1,i2,ik 并且这 k 个对象满足 1 ( ) k j j usedsize itotal = ( )( )( ) 12k hh.hiii 对象 i 是否 在缓存中 对象 i 属 于 i1,i2,ik used=used-size(i) 1 max( )( ) k jk j lh ih i = = 剔除 i1,i2,ik 1 ( ) k j j usedusedsize i= 保存 i 第 3 章 web 缓存替换策略的研究 34 图图 3-4 gdsf-ai 策略伪代码 algorithm gdsf-ai: initialize ; ; q; type v； l 0.0；used 0.0； for each request for object i do if i is in cache then do a) fr(i)=fr(i)+1 b) h(i) ( )*( ) *()*( ,( ) log( ) type p ivalue i lvscore i q fr i size i + else do a) f