基于协同过滤的Web缓存替换算法研究＊

吴俊龙，杨 清

（湖南科技大学计算机科学与工程学院，湖南 湘潭411201）

1 引言

随着信息技术的迅猛发展，互联网已深入渗透社会生活的各个方面，网络接入用户数与信息数据量的急剧增加导致各种网络问题日益明显，线路拥塞和服务器超载加剧了访问延迟，严重影响了用户网络访问体验。为解决这些问题，研究人员提出了各种解决方案，最具代表性的是Web缓存技术，该技术利用了Web访问模式的时间局部性，可有效提升用户网络访问体验。其基本原理是：代理服务器预先存储一些网络文件以备用户访问，若存储空间不足，则按照某种标准将过期的网络文件进行替换，以保持文件的新鲜度，并保证缓存空间的可用性。当有新的用户请求到达时，代理服务器将已存储的请求文件反馈给用户，从而减少用户感知的访问延时［1，2］。

缓存替换算法是Web缓存技术的核心，可分为以下四种类型［3］：基于时间特性的替换算法、基于频率特性的替换算法、基于文件大小的替换算法和基于成本/价值模型的替换算法。前三种类型的替换算法分别考虑了用户访问的时间特性、频率特性与Web文件的大小特性，实现起来较为简单，但性能较差，而基于成本/价值模型的替换算法通过综合考虑各种影响因素为Web 对象计算缓存价值，在性能与系统开销之间取得了不错的均衡，是今后主要研究方向之一。

本文在成本/价值模型的基础上，研究了Web对象之间和用户之间的关联性，并将协同过滤思想应用于贪婪双尺寸频率缓存替换算法GDSF（Greedy Dual Size Frequency）［4］，提出一种基于协同过滤的Web 缓存替换算法GDSF－CF（Greedy Dual Size Frequency Collaborative Filtering）。该算法运用协同过滤算法的思想考察用户－文件以及文件－文件之间的关系，计算缓存空间中每个文件的预测访问频率并形成关于缓存价值的目标函数，然后通过计算得到文件的缓存价值，最后将对最小缓存价值的文件进行替换。

2 研究现状

作为Web缓存替换策略的核心技术之一，缓存替换算法已有大量研究成果，Geetha K［5］提出了SEMA－LRU （SEMAntic and Least Recently Used）替换算法，SEMA－LRU 在LRU（Least Recently Used）的基础上，依据网页内容的语义关联和最近访问次数来判断是否将网页替换出去。Lee D 和Kim K J［6］使用了延迟缓存替换策略保证用户稳定访问体验，当请求数量出现异常高时，代理服务器不会将网页缓存，而只记录数据的元信息，当请求数量恢复至正常值后，再使用这些数据元信息为用户请求数据，通过缓解服务器的负载为大多数用户提供稳定的服务质量。张旺俊［7］运用成本/价值模型，在贪婪双尺寸频率缓存替换算法GDSF 的基础上提出了一种改进的GDSF－AI（Greedy Dual Size Frequency Access Interest）替换算法，该算法综合考虑Web 对象的访问特性、Web对象所属的内容类型以及用户兴趣，为缓存空间中的每个Web对象计算缓存价值，然后将价值最小的Web 对象从缓存空间中替换出去。

同样作为访问加速技术的一种，协同过滤技术CF（Collaborative Filtering）［8］通过分析用户的兴趣与爱好，在用户群中为指定用户找出具有相似兴趣用户，综合这些相似用户对某一信息的评价，形成系统对该指定用户对此信息的喜好程度预测。这种技术能够根据相似用户的评分来预测当前用户的兴趣。协同过滤的核心技术是协同过滤算法，一般而言可将协同过滤算法分成两种类型：基于内存的协同过滤（Memory－based CF）和基于模型的协同过滤（Model－based CF）。基于内存的协同过滤算法运用十分广泛，这种类型的算法可以基于用户，也可以基于对象，或者是用户对象两者混合形式。基于用户的协同过滤（User－based CF）根据相似用户的评分预测当前用户的评分；而基于对象的协同过滤（Item－based CF）根据相似对象的评分预测当前用户的评分。基于模型的协同过滤算法首先对用户评分数据信息进行分析，然后在此基础上进行学习并建立一个预测模型，最后利用这个模型来进行关于用户评分值的预测。此种类型的预取算法通过利用统计方法和机器学习这两种途径建立模型，包括聚类模型、贝叶斯模型关系模型、线性回归模型等。本文选用了基于内存的协同过滤算法，通过此种类型的协同过滤技术来为贪婪缓存替换算法进行改进。

3 GD系列算法

GD（Greedy Dual）算法是一种基于代价的贪婪算法，在一个代理服务器的存储空间中，有多个Web对象i，GD 替换算法根据每个Web对象缓存所需的代价为其赋值一个数值H，当存储空间不足需要进行Web对象替换时，H值最小的Web对象会被最先替换出去，然后根据最小H值来调整剩余页面的H值。但是，该类算法存在“缓存污染”问题，即存储空间会驻留大量长时间没有被访问的大尺寸Web对象。

GDS（Greedy Dual Size）是一种改进的贪婪缓存替换算法，该类算法针对GD 算法的“缓存污染”问题进行了改进，GDS算法使用一个优先级序列，并且为将来的H值设置了偏差。H值的目标函数如下所示：

其中，Value（i）为Web对象i的缓存价值；Size（i）为i的尺寸大小；L为替换变量参数，每次有Web对象被替换出去时，L都会被重新赋值为价值最小的、被替换出去的Web对象的价值H（i）。

GDS简单明了，但是没有考虑Web对象的内容类型、访问频率、访问时间间隔以及流行度，可能会出现以下情况：在存储空间内存在一组Web对象，根据目标函数的计算每个Web对象具有相同的H值，但是各个对象的访问频率不一致，具有较高访问频率的Web对象反而可能会被替换出存储空间，不符合Web 对象访问特性的局部性规律。针对该类问题，通过为目标函数引入Web对象的访问频率，提出了GDSF 算法。该算法充分考虑了Web对象的尺寸大小、缓存代价以及访问频率。其目标函数如下所示：

其中，Fr（i）为Web对象i的访问频率。

GDSF算法通过在目标函数的计算中加入Web对象的访问频率，可有效提高缓存替换效率，但对Web对象的内容类型、流行度以及修改频率这几个因素缺乏关注，GDSF算法还有进一步改进的空间。

4 GDSF－CF算法

4.1 算法描述

GDSF－CF替换算法将协同过滤中的项目作为Web对象处理，并将用户对项目的评分值归一化为用户对文件的访问频率，通过相似度的计算来预测文件的用户访问频率，并最终建立目标函数计算文件的缓存价值，如以下三个步骤：

（1）运用协同过滤算法生成用户对于Web对象的预测访问次数；

（2）考虑齐普夫定律参数与访问时间间隔因素建立Re（i）参数；

（3）结合上述各项参数建立关于Web对象缓存价值的目标函数。

下面就GDSF－CF算法的原理做出具体描述：

（1）形成相似Web对象集合。

①计算Web 对象之间的相似性。访问过Web对象i与Web对象j的用户可形成用户Ui，j，Ui，j＝Ui∩Uj，c为Ui，j中的任意一个用户。计算i，j之间的相似度可以使用皮尔孙算法，如公式（1）所示：

其中，sim（i，j）为i、j之间的相似度，Vc，i与Vc，j分别是用户c访问i与j的统计次数，和分别为每个用户访问i与j的平均统计次数。由于缓存空间中的Web对象具有相对稳定性，即新进入的Web对象不会被立即替换出缓存空间，因此可在系统处于离线时计算对象之间的相似度，然后将所得数值存放于数据列表中。

②形成每个Web对象的相似集合。对缓存空间中任意Web对象k，在整个对象集合上进行搜索，选取并集合与k相似度最高的前H个Web对象，作为k的相似对象集SIk。

③计算预测访问次数Va，k。设用户a与用户b分别访问过不同的Web对象，这些Web对象的并集为Ia，b，Ia，b＝Ia∪Ib，有Web对象k和n，k∈Ia，b，n∈SIk，目标用户a未访问过k，可通过SIk预测用户a访问k的次数Va，k，如公式（4）所示：

通过公式（4）可计算出缓存空间内任意用户对于缓存空间中任意Web对象i的预测访问次数，其值可用V（i）来表示。

（2）计算Re（i）频率参数。

本文考虑到缓存空间中的Web对象有可能被用户再次访问，为此设置了一个相关参数Re（i），Re（i）与用户访问频率因素相关，Web对象的流行度、访问频率和用户访问请求之间的时间间隔均对用户再次访问的概率有较大影响。结合齐普夫（Zipf）定律［8］以及本文提出的用户预测访问次数参数V（i）来对用户访问频率因素Re（i）进行计算，如公式（5）所示：

其中，V（i）是用户访问i的预测次数，δT（i）是用户请求i的时间间隔，β是齐普夫定律中的参数。

（3）计算节省数据包的价值。

将Web对象i引入缓存空间也需考虑付出的代价值，通常在缓存策略中考虑以下三种类型的代价值：常数、延迟时间和数据包个数。为了准确衡量因使用缓存替换算法而节省下来的数据包传送个数，本文选择数据包的传送个数作为代价，其代价值为Value（i）。因TCP分段大小为536bytes，Value（i）的计算如公式（6）所示：

（4）形成计算缓存价值的目标函数。

根据以上关于各种因素的计算，在贪婪双尺寸频率替换算法GDSF 的基础上，本文提出了一种结合协同过滤技术的缓存替换算法GDSF－CF。在缓存替换过程中，该算法利用目标函数公式计算Web对象的缓存价值并对最小缓存价值的对象进行替换。其目标函数如公式（7）所示：

其中，参数L是一个膨胀因子，Value（i）为获取Web对象i所需的代价，Size（i）为Web对象i的尺寸大小。

4.2 算法流程

为方便介绍GDSF－CF算法替换流程，首先设置如下参数：

L：为初始阈值，当有最小缓存价值H（i）min的Web对象从缓存空间中替换出去时，L会被重新赋值，其值为H（i）min；

fr（i）：用户访问Web对象i的次数，初始值为1；

Value（i）：引入Web 对象i至缓存空间所需付出的代价；

Ctotal：缓存空间的总大小；

Cused：已使用的缓存空间大小；

Size（i）：Web对象i的尺寸大小。

GDSF－CF具体流程如下所示：

（1）初始参数，令L＝0，Cused＝0。

（2）如果缓存空间中已有用户请求的Web对象i，则令fr（i）增加1，即fr（i）＝fr（i）＋1，Cused的值不发生改变。

（3）如果缓存空间中不存在用户请求的Web对象i，则表示用户请求没有被命中，此时用户请求将会转交至远程Web服务器，通过与Web服务器的直接连接获取Web对象i，然后将此Web对象i保存至缓存空间中，待下次使用。

此时令fr（i）＝1，即Web对象i访问次数为1，根据替换算法的目标函数公式（8）计算Web对象i的缓存价值H（i），由于缓存空间发生改变，有：

依据剩余空间大小，接下来会有两种状况：

①Cused≤Ctotal，表明剩余缓存空间充裕，则可以将Web对象i直接放入缓存空间中，无需进行缓存替换。

②Cused＞Ctotal，剩余缓存空间不足，Web对象i无法放入缓存空间，需要进行缓存替换以释放空间。可在缓存空间中选取n个缓存价值H（i）的Web 对 象，形 成Web 对 象 组i1，i2，…，in，这 组Web对象满足以下两个条件：

按照用户请求的Web对象i所处位置，分为以下两种情况：

a Web对象i位于这一组Web对象中，表明i的缓存价值很小，没必要进行缓存，也无需替换缓存空间中的任何对象，恢复Cused值至原值即可。

b Web对象i不处于这一组Web对象中，表明i的缓存价值超过了这组对象，则令L取值为这一组Web对象中最大的缓存价值H（i），其值为H（i）max，Cused的取值也发生变化，计算公式如下：

然后计算出L与Cused的数值，从缓存空间中替换出这n个对象i1，i2，…，in，最后将Web对象i保存至缓存空间中，完成缓存过程。

GDSF－CF算法的伪代码如下所示：

算法1 GDSF－CF算法

5 仿真实验

5.1 实验环境

仿真实验使用了SimpleScalar模拟器［9］作为仿真平台，输入数据采用来自锐捷缓存加速器RGPowerCache W5中的访问日志，共473 134条请求记录，日志总容量为199 MB，整个实验在一台DELL服务器上进行，该服务器配置为至强E7520 1.866GHz处理器，16GB DDR3内存，运行Red Hat Linux 9.0系统。

5.2 测试数据和实验分析

首先，按照不同的文件扩展名，将各类型的Web加以区分，确定各种类型的Web文件在所有用户请求记录中所占的比例。Web文件类型可分为文本、图像、音频、视频、程序和其他六种类型，经处理后得到的结果如表1所示。

Table 1 Types of Web objects表1 Web对象类型

随后，将用户的服务器访问日志发送至日志处理程序，经过处理后输出为SimpleScalar模拟器可以处理的格式，然后输入至SimpleScalar的Simcache模拟器进行仿真实验。本文采用了SIZE、LRU 与GDSF 这三种经典缓存替换算法与GDSF－CF算法进行性能对比。

表2为仿真实验所得到的各种算法命中率HR比较结果。

表3为为仿真实验所得到的各种算法字节命中率BHR 比较结果。

本文采用了以下两种指标衡量替换算法的性能：请求命中率HR（Hit Rate）和字节命中率BHR（Byte Hit Rate）

图1表示的是输入的日志文件在缓存相对大小分别 为1%、2%、3%、5%、10%、20%的条件下，GDSF－CF算法命中率与其他算法命中率的比较。当缓存相对大小处于0%～5%时，GDSF－CF 的命中率从0.377上升至0.472，命中率随着缓存相对大小的增加而持续提高，最高可达到0.512，但是命中率不会一直持续增加，而是逐渐趋于平稳。相对于GDSF算法的命中率，GDSF－CF 的命中率提升了12%。

Table 2 Results of hit rate表2 算法命中率HR

Table 3 Results of byte hit rate表3 算法字节命中率BHR

Figure 1 Comparison of hit rate图1 算法命中率比较

图2 表示的是在缓存相对大小分别为1%、2%、3%、5%、10%、20%的条件下，GDSF－CF算法字节命中率与其他算法字节命中率的比较。当缓存相对大小处于5%～10%时，GDSF－CF 的字节命中率从0.381 上升至0.420，最大可以达到0.423。与命中率的增幅情况相类似，字节命中率不会一直持续增加，而是逐渐趋于平稳。相对于GDSF算法，GDSF－CF的字节命中率提升了9%。

Figure 2 Comparison of byte hit rate图2 算法字节命中率比较

6 结束语

Web缓存技术是提升用户访问体验、优化带宽使用率的快速捷径。缓存替换算法是Web缓存研究中的核心问题之一，由于替换算法的性能对环境因素的设置相当敏感，不同设置环境下导致替换效果具有差异性。本文综合考虑各项因素对Web对象的影响，针对GDSF 算法在预测方面的不足，提出了基于协同过滤的缓存替换算法GDSF－CF。实验结果表明，GDSF－CF 算法较GDSF 算法具有更好的命中率和字节命中率。

［1］ World Internet Usage and Population Statistics［R］.NY：Internet World Stats，2009.

［2］ Deshpande S.Systems and methods for implementing a cache model：U S Patent Application 10/737，543［P］.2003－12－16.

［3］ Song Bing.Research on web prefetch and web cache model［D］.Zhengzhou：Zhengzhou University，2006.（in Chinese）

［4］ Cherkasova L.Improving www proxies performance with greedy－dual－size－frequency caching policy［R］.H P Laboratories Report No HPL－98－69R1.Palo Alto：Hewlett－Packard Laboratory，1998.

［5］ Geetha K.SEMALRU：An implementation of modified web cache replacement algorithm［C］∥Proc of Nature ＆Biologically Inspired Computing，2009：1406－1410.

［6］ Lee D，Kim K J.A study on improving web cache server performance using delayed caching［C］∥Proc of 2010International Conference on Information Science and Applications（ICISA），2010：1－5.

［7］ Zhang Wang－jun.Research of web cache replacement policy and pre－fetching［D］.Hefei：University of Science and Technology of China，2011.（in Chinese）

［8］ Fan Bo，Cheng Jiu－jun.Multiple similarity between users in collaborative filtering recommendation algorithm ［J］.Computer Science，2012，39（1）：23－26.（in Chinese）

［9］ Ma Hai－feng，Yao Nian－min，Fan Hong－bo.Cache performance simulation and analysis under SimpleScalar platform［C］∥Proc of International Conference on New Trends in Information and Service Science，2009：607－612.

附中文参考文献：

［3］ 宋冰.Web 预取与缓存一体化模型研究［D］.郑州：郑州大学，2006.

［7］ 张旺俊.Web 缓存替换策略与预取技术的研究［D］.合肥：中国科学技术大学，2011.

［8］ 范波，程久军.用户间多相似度协同过滤推荐算法［J］.计算机科学，2012，39（1）：23－26.