连铸智能化平台Web访问缓存替换策略

王红涛，冯连强，刘颖，陈蕊，郝乐

(中国重型机械研究院股份公司，陕西 西安 710032)

专题综述

连铸智能化平台Web访问缓存替换策略

王红涛，冯连强，刘颖，陈蕊，郝乐

(中国重型机械研究院股份公司，陕西 西安 710032)

针对目前连铸技术与信息化技术高度融合，但已有的缓存替换策略对于数据交互传输存在局限性的问题，提出一种引用度模型来对Web访问对象的空间局部性进行评价，并将其作为设计缓存替换策略的依据，提出一种基于引用度的缓存替换策略GDSR，改善了缓存替换策略的性能，为Web缓存替换策略的设计提供了一个新的方向和思路。

缓存替换策略；空间局部性；引用度模型

0 前言

互联网的不断发展使得网络访问量不断增加，但服务器及网络基础设施的性能是有限的，服务器和网络带宽的负载都长期处于饱和状态，导致网络服务质量QOS下降。Web缓存技术是提高Web访问速度的一个有效的手段。缓存替换策略是Web缓存技术的核心，它是决定Web缓存性能的最为重要的因素。依托中国机械工业集团有限公司“高品质特殊钢特超厚板连铸技术及创新平台”科技发展基金项目，针对生产现场与设计中心智能化云平台存在大量数据交互问题，进行了此方面内容的一些研究。

目前，已有的缓存替换策略大部分都利用Web对象访问特性中的时间局部性、频率分布特性和大小分布特性，而Web对象访问的空间局部性在Web缓存替换策略中利用较少。本文提出一种引用度模型来对Web访问对象的空间局部性进行评价，并将其作为设计缓存替换策略的依据，提出基于引用度的缓存替换策略GDSR，改善了缓存替换策略的性能。

1 Web缓存相关理论及技术

1.1 Web缓存原理

Web缓存的工作机制为：当连铸智能化云平台收到用户请求时，首先在Web缓存中查找该对象，当对象在缓存中存在有效副本时，缓存直接将对象发送给用户；当对象副本存在但已经失效时，从服务器更新对象，并将Web对象发送给用户；当对象副本不存在时，从原始服务器获取该对象，若缓存空间未满，则将对象放入缓存，否则根据替换策略，用该对象替换陈旧对象，最后将该对象发送给用户。

1.2 Web对象访问特性

Web对象具有的访问特性是Web缓存机制的基础，同时也是设计Web缓存替换算法的重要依据。Web对象访问具有以下特性：

(1)时间局部性。指请求过的连铸智能化云平台Web对象再次被请求的可能性较高。

(2)空间局部性。指与当前被访问对象相邻的对象在将来被访问的概率较大，但Web对象访问中空间局部性比较特殊：首先，Web对象没有实际的存储地址，因此两个对象的相邻关系由它们在访问序列中的相邻情况决定，例如，当连铸智能化云平台序列中间包数据对象在结晶器数据对象被访问不久之后被访问，那么可以认为结晶器数据对象与中间包数据对象相邻，这种相邻关系以多对多的形式普遍存在于Web对象访问序列中。其次，Web对象访问的空间局部性具有很强的单向性：如果中间包数据对象在结晶器数据对象被访问不久之后被访问，那么当结晶器数据对象被再次访问时中间包数据对象很有可能再次被访问，而中间包数据对象的访问通常并不影响结晶器数据对象被再次访问的概率，并且当结晶器数据对象不被访问时，中间包数据对象也很有可能不会被访问。

(3) 频率分布。用户对连铸智能化云平台Web对象的访问通常存在一些热点，将Web对象的访问频率按照降序进行排列，可以得到Web对象请求的分布序列，而这种分布大多服从Zipf-like定律。

(4)大小分布。当对象的大小超过某一数值之后，将概率分布服从Pareto分布。这种分布规律说明用户访问通常集中于较小的网络对象。

利用访问特性能够对已访问对象的未来访问趋势进行预测，从而评价该对象未来再次被访问的可能性大小，并以此为根据设计连铸智能化云平台Web缓存替换算法。

1.3 Web缓存替换策略

连铸智能化云平台缓存替换策略的目标是尽可能保留那些缓存价值较高的对象，删除那些缓存价值较低的对象。缓存替换策略主要分为以下几类：(1)基于访问时间间隔的替换策略主要利用了Web对象访问特性中的时间局部性；(2)基于访问频率的替换策略利用了Web对象访问特性中的频率分布特性；(3)基于对象大小的替换策略利用了Web对象访问特性中对象大小的分布特性；(4)基于目标函数的替换策略综合利用Web对象访问特性中的时间局部性、频率分布特性和对象大小分布特性，同时结合访问代价，利用目标函数计算出Web对象缓存价值，以此作为替换时的依据，每次将缓存价值最低的对象替换出缓存空间。其代表算法有GDS、GDSF、GD*等。

目前连铸智能化云平台Web对象访问的空间局部性主要被用于Web预取技术中，在Web缓存替换算法中利用较少，比较有代表性的算法为PGDSF，该算法在GDSF算法基础上进行改进，算法利用历史访问序列建立起基于Markov链模型的频繁访问树，并以此为基础得到一个预测对象集，该集合内的对象将不被替换出缓存空间。

1.4 Web缓存评价指标

连铸智能化云平台Web缓存系统的主要评价指标有：(1)命中率。从缓存中得到请求对象的数量占总请求数的比例；(2)字节命中率。从缓存中得到的对象的大小，即字节数，占总请求字节数的比例；(3)延迟率。从原始服务器得到对象与从缓存中获取对象的时间之差；(4)移除率。从缓存中移除对象的次数与处理的请求总数的比值。

2 GDSR缓存替换策略

2.1 Web对象相邻关系

相邻关系是连铸智能化云平台Web对象访问空间局部性的重要依据，对Web对象访问的相邻关系进行具体分析。

定义1 令X→Y表示两个Web访问对象X和Y在访问序列中存在相邻关系，并且Y紧跟在X之后被访问。访问序列中的相邻关系分为三种：

(1)访问逻辑相邻。它是用户访问倾向的真实体现，它表征了用户的上网浏览信息的行为习惯。假设每种访问只请求一个独立的Web对象，分别为A～F，那么当一个用户具有访问习惯模式“a-f-c-d-e-b”时，该用户的访问会产生A→F、F→C、C→D、D→E和E→B相邻关系。对一个用户来说，这种习惯可能是长时间不会改变的，并且可能有很多用户具有相同或相似的访问习惯，因此这种由用户访问习惯造成的访问逻辑相邻关系是比较稳定的，具有规律性。

(2)偶发物理相邻。指Web缓存服务器接收到的访问序列中两个对象存在相邻关系，但它们在逻辑上完全无关，只是在访问的物理顺序上出现相邻。

(3)引用相邻。由于连铸智能化云平台Web对象访问过程中内在的引用关系产生的相邻关系，Web对象的引用关系有两种：一种是Web对象(主要是页面)内引用其它资源文件产生的引用关系；另一种是用户点击超链接产生的引用关系。引用相邻一旦出现将稳定存在，只是再次出现的概率大小不同。

通过分析不难看出，访问逻辑相邻和引用相邻能够真正体现出Web对象访问的空间局部性，而偶发物理相邻不具有任何参考意义。由于引用相邻关系的存在是明确的，因此具有较高的识别效率，并且引用相邻重复出现的概率很高，对空间局部性的体现具有很大的价值。因此本文通过引用相邻关系来对Web对象访问的空间局部性进行部分抽取。

2.2 Web对象引用关系

(1)引用关系的来源。浏览器加载页面时会自动获取被引用的资源，并在页面中进行展示，或者将其作为动态代码和页面样式使用。这种引用关系在页面HTML代码相关部分不变时固定存在，即只要页面被请求，那么浏览器就会请求被引用的资源，这种引用关系就是内部引用。

(2)引用关系的获取。Web对象之间的引用关系同样可以从HTTP协议中获取，HTTP的请求头中存在一个可选字段“Referer”，当一个对象是由于引用而被请求时，该字段会出现在请求头中，其值为引用源的URL。如果一个HTTP请求报文中不存在“Referer”字段，则表示该对象的访问请求是独立的。因此，通过检查HTTP请求头中的“Referer”字段，能够很容易的获取Web对象之间的引用关系。

(3)引用关系的分析。为验证引用关系的普遍存在，本文对连铸智能化云平台中某核心网络设备1小时的流量日志进行了分析。该日志共包含1 771 417条有效访问记录，其中不重复的URL访问960 315条，总的有效流量为31 155 285 780字节。其中共出现62种不同的对象类型，各类型所占数量如图 1所示。

图1 不同对象类型数量统计图

当日志中的访问记录中HTTP请求中包含“Referer”字段，则说明该请求来自其它对象的引用，日志引用概况如表1所示。

表1 日志分析统计表

从分析结果可以看出引用关系在Web对象的访问中普遍存在，并且引用源数量和被引用对象的数量差距极大，即少数的对象造成了引用关系的大量出现。

针对对象类型分析引用和被引用情况，发现引用其它对象的类型大量集中在是“text/html”、“application/x-shockwave-flash”、“text/xml”、“text/css”及“text/plain”类型的对象，见表 2。

表 2 不同类型对象引用情况统计表

从统计结果可以看出，大部分的引用是由Web页面(text/html)类型的对象引起的，因为它包含大量内部资源(如图片，JavaScript代码等)的引用，同时还包含很多超级链接。而被引用的对象类型中图片(image)所占比例最多，此外，除了Web页面(text/html)类型以外，JavaScript代码(text/javascript)和CSS文件(text/css)被引用的次数也比较多。因为图片、JavaScript代码和CSS文件很少被用户直接访问，基本都是作为其他页面的内部资源被引用，因此被引用次数较多。并且这些类型的同一个对象经常会被多个不同的引用源引用，因为很多网站内的多个网页会使用相同的图片、JavaScript代码和CSS文件。而超级链接的目标通常是Web页面，因此Web页面(text/html)被引用次数也较多。

图 2 不同类型对象被引用情况统计图

2.3 引用度计算模型

综上所述，引用关系在连铸智能化云平台Web对象访问中普遍存在，而这种引用关系将会直接影响被引用对象再次被访问的概率。

若一个对象i被N个对象引用，则对象i由于引用关系的存在而再次被访问的概率为

(1)

其中，P(n)为第n个引用源对象被再次访问的概率，PR(n,i)为第n个引用源对象被再次访问时引用对象i的概率。当引用关系为内部引用时PR(n,i)为1，当引用关系为非内部引用时0≤PR(n,i)≤1。

本文提出使用一个引用度计算模型来量化引用关系对对象再次被访问可能性的影响。引用度是Web对象访问中引用关系的量化表示，其目的在于将引用关系中隐含的一部分Web对象访问空间局部性抽取出来，以便作为缓存替换策略的设计依据。引用度计算模型定义如下

若一个对象i存在N个引用源S1,S2,…,Sn，则对象i的引用度Ri为

(2)

式中，PR(Sn,i) 为引用源Sn被访问时引用对象i的概率;R(Sn,i)为引用源Sn引用对象i的次数。其中

PR(Sn,i)=R(Sn,i)/F(Sn)

(3)

因此进一步得到

(4)

2.4GDSR缓存替换策略工作原理

GDSF是一种基于目标函数的替换算法，该算法综合了频率、大小、访问代价三个因素，综合性能优秀。GDSF策略计算每个对象的缓存价值并对其排序，每从缓存价值最低的对象开始替换。GDSF策略缓存价值计算方法如下

(5)

式中，Fi为对象i的访问次数；Si为对象i的大小；Ci为将对象i引入缓存空间的代价；L为衰老因子。

将GDSF策略与引用度结合，将引用度加入缓存价值的计算过程，提出GDSR策略，其缓存价值计算方法如下

(6)

其中，FDi为对象i被独立访问的次数。GDSR策略使用将GDSF策略中的对象访问次数进行了分解，将引用产生的访问次数从中去除。对象的访问次数使用引用度进行计算，从而确保不被重复累计。λ是一个调节参数，用来调整引用度对整个缓存价值的影响程度；Ci为将对象i引入缓存空间的代价。

本文采用的计算对象的获取代价的标准为网络标准：网络标准：认为对象的获取代价与获取该对象需要传输的包数相关，将对象获取代价设为

(7)

其中,Si为对象i的大小。536为TCP分段大小，单位是字节。

GDSF策略设计时考虑了Web对象访问特性的频率分布、大小分布特性。GDSR策略在此基础上，通过引用度将空间局部性加入到缓存价值的判断依据中，从而提高连铸智能化云平台缓存替换策略的性能。

2.5GDSR缓存替换策略工作流程

(1) 可缓存性判断流程。Web对象的可缓存性的判断流程如图 3所示。为了降低算法实现的复杂度和运行代价，本文对判断标准进行了简化：在对HTTP状态码进行判断时，只接受可缓存状态码，不考虑消极缓存类型的状态码；由于HTTP参数的获取需要进行复杂的HTTP解析，因此不使用HTTP参数作为判断依据。

图3 可缓存性判断流程图

(2)引用信息更新流程。对象的引用信息需要作为引用度计算的依据，因此每当对象被引用访问时，需要更新其引用信息，引用信息更新流程如图 4所示。Web对象引用度计算流程如图 5所示。

图4 对象引用信息更新流程图

图5 Web对象引用度计算流程图

(3)对象替换流程。当连铸智能化云平台Web缓存空间已满时，需要执行替换操作将缓存中的一部分对象替换出去，替换的依据是从缓存中价值最小的对象开始，将价值小于待缓存对象的对象依次替换出，直到释放了足够的缓存空间。但是这种替换并不总能成功，如果当前缓存中价值最小的对象的价值高于待缓存对象的价值，则替换不能进行，此时需要将之前替换出的对象恢复，因此需要一个待删除队列来暂时存储这些对象。对象替换具体流程如图 6所示。

(4)GDSR策略工作流程。本文在以上设计的基础上完成了GDSR策略工作流程的设计，GDSR策略工作流程如图 7所示。

图6 对象替换流程图

图7 GDSR工作流程图

(未完，待续)

Web cache replacement strategy for intelligent platform of continuous casting

WANG Hong-tao, FENG Lian-qiang, LIU Ying, CHEN Rui, HAO Le

(China National Heavy Machinery Research Institude, Co., Ltd., Xi’an 710032, China)

Currently, the continuous casting technology and information technology are highly integrated. However, the existing cache replacement strategies have limitations on the data transmission. This paper proposed a reference model to evaluate the spatial locality of Web object accessing, and used the reference model as the basis of a new cache replacement policy-greedy-dual-size reference (GDSR). GDSR improved the performance of cache replacement strategy, provided a new direction and ideas for the design of Web cache replacement policies.

cache replacement strategy; spatial locality; reference model

2016-11-16；

2016-12-09

中国机械工业集团有限公司科技发展基金项目(SINOMACH12科167号)

王红涛(1986- )，男，中国重型机械研究院股份公司工程师。

TP393

A

1001-196X(2017)02-0001-06