王婷，任洪敏（上海海事大学信息工程学院，上海 201306）

Web端性能优化的研究与实现

王婷，任洪敏
（上海海事大学信息工程学院，上海 201306）

为了提高Web端缓存的性能，在传统的缓存替换算法GDS基础上提出新的缓存替换算法GDS-TFH。改进的算法除了考虑被访问对象的大小，还考虑被缓存的对象访问次数之间的时间间隔和被访问对象访问的次数或被访问的频率。分析在有限的缓存空间内改进的算法GDS-TFH在请求命中率和字节命中率方面有比较好的提升。

GDS-TFH；缓存替换；代理服务器

0　引言

网页加载的时间长短在很大程度上影响着浏览网页者的浏览体验和各个网站的竞争力。在可以获得同样信息的网站之间，浏览等待的时间越短，用户体验越好，网站竞争力越大。根据网站Softpedia网站上公布的消息，Google检索到的网页加载速度平均为2.45秒。根据调查机构KissMitrics研究的结果显示：网页加载的速度会影响用户的消费，如果电子商务每天收入为10万美元，那么1秒的延迟就会让该网站每年损失250万美元。影响网页加载速度的原因有很多。其中，在服务器方面，可以设置一个代理服务器，代理浏览用户获取网络信息。代理服务器是一个缓存网络数据的软件，当用户发送Requests到服务器时，代理下载和缓存需要的网页信息，当其他用户也发出同样的Requests时，直接从代理服务器的缓存中获取需要的网页信息。若是缓存目录使用量超过95%时，使用缓存替换算法，收回一部分当前可能不需要的缓存信息，备份新缓存的信息，因此代理服务器的缓存替换算法的优劣会影响代理服务器的性能。所以对缓存替换算法的优化可以提高代理服务器的性能。

1　对现有缓存替换策略的调研

1.1被使用过的缓存替换策略部分简介

已经出现的缓存替换策略有很多，例如Least Recently Used（LRU）、Least Frequently Used（LFU）、SIZE、LRU Threshold、Log（Size）+LRU、Lowest Latency First、Hybrid、Lowest Relative Value（LRV）等。可以把这些缓存替换算法依据不同的标准分成4类：基于访问对象被访问的次数（Least Frequently Used（LFU）-最不经常使用）、基于被访问对象访问之间的时间间隔（Least Recently Used（LRU）-最近最少使用）、基于被访问对象的大小（SIZE缓存置换算法）、基于被访问对象保存的价值（Hybrid缓存置换算法）。

1.2评判缓存替换策略的标准

通过衡量对象的大小区分请求命中率和字节命中率。目前为止，还没有一种算法可以两者兼顾，使缓存替换最优。通过Arlitt M的实验可知，基于被访问对象的大小的缓存替换算法能够使请求命中率值更高，基于访问对象被访问的次数的缓存替换算法能够使字节命中率值更高。判断缓存替换算法性能的标准一般有2种：

（1）请求命中率

请求命中率由用户通过浏览器发出的Requests被命中的次数与用户通过浏览器发出的所有Requests之比而得。当用户通过浏览器访问网页时，若是此次请求的网页在缓存中命中缓存，用σi=1表示，若是没有在此次请求的网页在缓存中命中缓存，用σi=0表示。请求的Requests之和用N表示。请求命中率（RHR）的公式是：

（2）字节命中率

字节命中率由用户通过浏览器发出的Requests被命中的所有文档的大小与用户通过浏览器发出的Requests的所有的文档大小之比而得。当用户通过浏览器访问网页时，若是此次请求的网页在缓存中命中缓存，用σi=1表示，若是没有在此次请求的网页在缓存中命中缓存，用σi=0表示。请求的Requests之和用N表示。用size（i）表示对象i的文档大小。字节命中率（BHR）的公式是：

已知判断缓存替换算法的性能有两种标准，研究明白两者之间的关系，有利于理解Web端缓存替换算法之间的优劣。使用公式（2）除以公式（3），得到的是所有请求对象的平均大小与所有命中对象的平均大小之比，即可形象化地理解请求命中率（RHR）和字节命中率（BHR）之间的关系。即：

因为：

在Web缓存系统中，一般RHR比BHR大，故（6）的值大于1，即所有请求对象的平均大小比所有命中对象的平均大小大，说明小文件更容易被命中。

2　GDS缓存替换算法的研究与改进

2.1艾宾浩斯遗忘曲线

艾宾浩斯遗忘曲线描述了人类大脑对新事物遗忘的规律。用户对某件事务感兴趣的程度可以引用艾宾浩斯遗忘曲线的规律，表示用户对某对象感兴趣的程度。

图1

曲线的表达式可以近似的表示为：

ΔT为表示对象i相邻被访问次数之间的时间间隔，单位为ms。

2.2GDS算法

GDS（Greedy Dual Size）算法的基本思想是通过目标函数计算所有的对象i的函数值，将函数值由大到小排列，当有限的缓存空间的存储量达到95%时，将函数值最小的对象清除。现有的GDS缓存替换算法是Cao 和Irani在研究分析了13种不同的缓存替换算法，得

在公式（8）中，L为膨胀因子，初始值为0，当有对象在缓存中被替换时，被替换对象的目标函数值赋值给新进入缓存对象的L。Size（i）为对象i的大小。Value （i）为对象i被引入到缓存需要的代价。

GDSF（Greedy Dual Size Frequency）算法因为需要考虑对象访问的频率，所以实现起来稍微复杂一些。当出现被访问次数多的对象被替换时，GDSF算法就会显现出比GDS算法更好的健全性。GDSF算法的目标函数中引入新的变量Fr（i），表示对象i访问的频率。GDSF算法的目标函数为：到了计算目标函数的计算方法：

但是，当对象访问频率大且对象i的大小比较小的时候，近期却不被用户访问，当然可能以后也不被访问到，这时就会造成部分缓存空间被长期占用，使RHR和BHR的效率降低。

2.3GDS算法的改进算法GDS-TFH

从访问的时间间隔来看，访问间隔的时间越短，对象被访问的概率越大。从访问的频率来看，访问的频率（次数）越大，对象被访问的概率也越大。可以通过对时间间隔加权，再对不同分组中的时间间隔使用余弦相似性的方法提高算法的优越性，当余弦值越大，两组的时间间隔越相似，用户对对象访问具有规律性，表明用户对此对象越感兴趣。另外，当用户对某些数据记忆越深刻，表示用户对此请求越感兴趣，则对象请求的目标函数也越大。

由此，引入了用户感兴趣的程度 （User-Interest-Level（UIL））这一概念，定义：用户对Web对象的感兴趣程度是分组之后的时间间隔之间具有余弦相似性，1和相似性累加和结果的乘方，其中指数为艾宾浩斯遗忘曲线函数。在此基础上提出了GDS算法的改进算法GDS-TFH（Greedy Dual Size-Time Frequency probability）。设计用户感兴趣的模型。

用空间向量表示：

其中：

ΔT表示对象i相邻被访问次数之间的时间间隔，单位为ms。ΔTi中的下标i表示第i个时间间隔。Fr（i）表示对象被访问的次数，且Fr（i）≥4。I在1到Fr（i）-3之间。对时间间隔依据艾宾浩斯遗忘曲线进行加权，即：

其中ai，ai+1，ai+2位常数，分别对应艾宾浩斯遗忘曲线中H（ΔTi），H（ΔTi+1）），H（ΔTi+2）的值。再求分组之后的时间间隔之间的余弦相似性。即，对wdFr（i）-3和wdi求余弦相似性，即：

函数的取值范围在0和1之间，相似度越高越接近1。综上，UIL公式如下：

用户感兴趣程度考虑了被访问缓存对象的时间间隔和被访问缓存对象出现的频率（次数）和艾宾浩斯遗忘曲线函数，用户感兴趣程度UIL（ΔT，Fr（i），H（ΔT））的计算值越大，则用户访问对象具有时间规律，表示用户对此缓存的对象越感兴趣，目标函数越大，对象缓存的价值越大，反之就越小。故，改进后的GDS-TFH算法具体函数为公式（14）：

简要概括GDS-TFH算法的使用过程：

①：L为膨胀因子，初始值为0，UIL（ΔT，Fr（i），H （ΔT））为1。

②：代理服务器处理用户发出的请求，当有限的缓存剩余量大于5%时，需要被缓存的对象直接进入缓存；当有限的缓存剩余量小于5%时，需要被缓存的对象计算对象i的目标函数，使用公式（14），将结果与缓存中的所有对象的函数值做比较，替换出价值最小的对象空间并且将函数值最小的H赋值给对象i的L。

3　实验环境的搭建和结果分析

3.1实验环境的搭建

实验环境搭建在CentOS6系统上，使用Squid代理服务器，实现缓存替换策略的改进。缓存替换策略对应的算法存放在目录/src/repl下面，通过在Squid代理服务器的Squid.conf文件中修改配置信息以及决定采用哪种缓存替换算法，通过自己编写shell脚本分析access.log日志文件，获取请求命中率和字节命中率。在Squid中修改GDSF算法的源代码，在其配置文件中设置使用的算法，可以得到3.2章节中描述的GDS-TFH算法。Squid工作流程如下：

图1　Squid代理服务器的工作流程

第1步，客户端向代理进程发送请求；第2步，代理进程将请求和数据缓存中的数据做对比；第3步，若是数据缓存中有请求的信息，执行第3.1.1步，若是数据缓存中没有请求的信息，执行第3.2.1步；

当执行了第3.1.1步后，执行第3.1.2步，代理进程将从数据缓存中获取的内容发送给客户端；当执行了第3.2.1步后，执行第3.2.2步，代理进程发送请求给远端服务器获取缓存；当执行了第3.2.2步后，执行第3.2.3步，远端服务器将获得的缓存信息发送给代理进程；当执行了第3.2.3步后，执行第3.2.4步，代理进程判断从远端服务器下载的缓存是否需要存进缓存中，然后将获取的缓存信息发送给客户端。

3.2实验结果分析

本次实验的分析数据来源于Squid代理服务器的日志Access.log文件中，日志文件里面包含了10个域。通过采集文件里面的请求完成的时间、HTTP请求命中的结果、被访问文件的大小，获得详细的请求命中率和字节命中率。另外，实验将对比LRU、GDSF、GDS-TFH算法在请求命中率和字节命中率方面的命中结果。结果如表1所示：

表1　命中率和缓存大小之间的关系

从关系表中可以看出，使用不同的缓存替换算法，请求命中率和字节命中率不一样。在同等环境下，GDS-TFH算法优于GDSF算法优于LRU算法，另外，GDSF算法和GDS-TFH算法的字节命中率明显优于LRU算法。用户可以根据需求，在某些条件下，选择效率较高的算法。

4　结语

影响Web端性能的因素有很多，因此，在不同的需求环境下，可以使用其他的方法来提高Web端的性能。本文通过请求命中率和字节命中率评价缓存替换算法的性能优劣，比LRU算法、GDSF算法多考虑了时间间隔对缓存的影响和对象被访问的频率的结合，提高了命中率，改善了Web端的性能。但是由于改进的算法考虑的因素多，当访问量很大的时候，增加了计算的复杂度，因此还需要继续研究和优化。

［1］Softpedia.The Average Web Page Loads in 2.45 Seconds Google Reveals［EB/OL］.http∶//news.softpedia.com/news/The-Average-Web-Page-Loads-in-2-45-Seconds-Google-Reveals-265446.shtml.

［2］Aguilera M K，Strom R E，Sturman D C，et al.Matching Events in a Content-based Subscription System［C］.Proceedings of the 18th ACM Symposium on the Principles of Distributed Computing，Atlanta，GA，1999-05.

［3］Ashayer G，Leung H K Y，Jacobsen H A.Predicate Matching and Subscription Matching in Publish/Subscribe Systems［C］.Proceedingsof the 22nd International Conference on Distributed Computing Systems Workshops，2002.

［4］Arlitt M，Friedrich R，Jin T.Performance Evaluation of Web Proxy Cache Replacement Policies［J］.Performance Evaluation Journal，2000∶149-164.

［5］周扬发，武斌，国海涛.一种改进的Web代理服务器GDS缓存替换算法.虚拟运营与云计算——第十八届全国青年通信学术年会论文集（下册）［C］，2013.

［6］石磊，叶海琴，卫琳，连卫民.Web缓存命中率与字节命中率关系［J］.计算机工程，2007，33（13）∶84-86.

［7］Ludmila，Cherkasova.Improving WWW Proxies Preformance With Greedy-Dual-Size-Frequency Caching Policy.HPL–98–69（R.1），November，1998.

［8］张旺俊.Web缓存替换策略与预取技术的研究［D］.中国科学技术大学，2011.DOI∶10.7666/d.d141607.

［9］周扬发.Web代理服务器的缓存技术研究［D］.北京邮电大学，2014.

［10］杨春贵，吴产乐，彭鸿雁.一种有效的Web代理缓存替换算法［J］.计算机工程，2007，33（3）∶43-44，47.

GDS-TFH；Cache Replacement；Proxy Server

Research and Implement of Web Front-End Performance Optimization

WANG Ting，REN Hong-ming
（College of Information Engineering，Shanghai Maritime University，Shanghai201306）

To improve the performance of Web front-end cache，studies the traditional cache replacement algorithm GDS and based on it，presents a new cache replacement algorithm named GDS-TFH.The modified algorithm not only considers the size of object，but also the time interval between the object's visit times and the visit times or frequency.Analyzes the improved algorithm GDS-TFH in the limited cache room request hit rate and byte hit rate has a good upgrade.

1007-1423（2016）20-0024-05

10.3969/j.issn.1007-1423.2016.20.005

王婷（1991-），女，江苏淮安人，硕士，研究方向为软件开发方法与软件项目管理

2016-05-04

2016-07-05