基于多项式回归预取技术缓存管理的研究①

李春洁， 闫瑞峰， 王 超， 周 虹，阴丽莹

(1.佳木斯大学信息电子技术学院，黑龙江 佳木斯 154007;2.哈尔滨轴承集团计算机中心，黑龙江 哈尔滨 150036)

0 引言

Web按其所蕴涵信息的“深度”可以分为Surface Web和Deep Web.通过超链接访问的静态网页、文件等称为Surface Web;需要通过动态网页技术访问而不能直接通过超链接访问的资源称为Deep Web.Deep Web是网络新信息增长的最大来源.与Surface Web相比，Deep Web中的Web数据库不仅数量众多，而且其信息资源可以覆盖现实世界的整个领域.如此庞大的信息资源，如果按现实世界的领域对其分类，可以分为商业与经济、计算机与互联网、新闻媒体、娱乐等十几个，而这只是宏观的分类.对Deep Web中的资源进行访问需要注册或者满足某些限定的条件，通过填写表单的方式对后台在线数据库进行查询，由此得到动态页面.除此之外，Deep Web还可以访问非网页文件，如图片、PDF 和 Word 文档等[1].

随着时代的发展，网络数据库信息量以及网络用户增长迅速，用户在访问Web时常出现访问延迟的现象.目前核心的解决方法是缓存技术和预取技术[2]，或者两种技术相结合[3].现有的预取技术和相应的缓存管理及替换策略大多只适用于Surface Web，减少访问延迟多是应用于Surface Web访问的.由于Deep Web已经占据主要地位，所以缓解Deep Web访问延迟对整个网络加快访问速度有重要意义.

1 Deep Web缓存与预取

1.1 预取技术和缓存替换

用户发起两次Web请求的时间间隔称之为用户浏览时间.预取技术是指在用户浏览时间内就把用户可能要访问的页面提前从服务器取回.当用户发出Web请求时，若要访问的页面已经预取回且已经存在于本地缓存中，此时能在请求的第一时间立即获取，从而减少了用户访问请求后的等待时间.该技术充分利用了I/O系统的空闲时间，当用户访问时可以减少网络延迟.预取技术好坏主要是靠准确率和查全率两个性能指标来衡量[4－5].

若在Deep Web中实施预取技术，以达到减缓访问延迟的目的.预取回的语义缓存项存放在缓存中，当缓存达到额定数量时，需要对缓存中的语义缓存项进行替换更新[6].为了使用户得到准确的预取结果，缓存替换策略就显得尤为重要[7].

1.2 Deep Web预取模型与缓存

Deep Web数据集成系统预取体系结构包括查询管理、预取、Deep Web数据集成、缓存一致性管理、存储管理、缓存替换管理等模块，体系结构如图1所示.

其中查询管理模块的功能是用来进行查询匹配，得到不同的匹配类型.针对不同的匹配类型对该查询进行处理，将结果返回给用户，并进行缓存项访问量统计.

预取模块采用多项式回归预取技术，对缓存中各语义缓存项的访问概率进行预测，根据预取阈值、预取标志位和缓存一致性效时间来生成预取队列，得到的预取结果集和语义缓存项将在外缓存有效数据存储区和内缓存有效语义缓存区中保存.

Deep Web数据集成模块的功能是满足用户查询需要，对同一领域的多个Web数据库访问和访问结果完成集成，最后将查询结果合并去重，在本地存储.

图1 Deep Web数据集成系统预取体系结构

一致性管理主要功能是判断语义缓存项及其对应结果集是否有效，如超出有效期范围，则需要访问服务器重新获得最新数据.

2 基于Deep Web的缓存替换策略

2.1 缓存的位置

缓存的位置可以是Web浏览器，服务器或代理服务器[8].在代理服务器上实现的缓存机制称为代理缓存[9].除了可以减少用户访问延迟之外，代理缓存还具有分析用户的访问模式、提高Web服务的健壮性、减轻服务器的负载、减少网络流量等特点.因此代理服务器缓存是较理想的.

2.2 存储管理

增加预取模块的Deep Web的数据集成系统，将存储区分为内缓存区和外缓存区两部分.

语义缓存项定义为{K，P，T，Z}i，其中 K 为用户提交的查询关键字集合，P为访问概率预测值，T为该查询语句有效期，Z为查询语句是否被预取.在内缓存中存储最近N个周期的访问频率pij(j=1～N)，及其在下一周期的访问概率预测值POP.

将预取语义缓存描述项存储于内缓存中，并将该区域设定为有效语义缓存区;在外缓存中，有效语义缓存项的结果集在存储部分设定为有效数据区，存储临时语义缓存项及对应结果集的外缓存部分设定为临时数据区，实际上在临时数据区存储的是直接访问Deep Web获得的查询结果，根据缓存替换策略将内缓存未过期的语义缓存项及其对应结果集替换出来.

2.3 存储管理

增加预取模块的Deep Web的数据集成系统，其存储区由内缓存区和外缓存区两部分组成.随着用户访问Deep Web的时间和访问量的增加，有限的内缓存和外缓存存储空间会达到额定值.当产生新的语义缓存项时需依据替换策略替换出一些数据，保证访问频率高的语义缓存项及其相关数据保留在缓存中.

根据内、外缓存的特点，对内外缓存分别采取不同的缓存替换原则.内缓存替换的基本思想是在新的周期，根据预取阈值α及有效期标志T的值来进行缓存替换;外缓存替换的基本思想在用户访问Deep Web获得新的查询数据时，根据语义缓存项Pop和有效期标志T的值进行替换.

2.4 缓存替换策略

增加预取模块的Deep Web的数据集成系统，采用多项式回归预测模型策略，对保存在内缓存中的各语义缓存项预测访问概率.根据内缓存替换策略的基本思想，新周期到来时更新内缓存中的有效语义缓存存储区存储的各语义缓存项的POP值.POP小于阈值α时，如果T在有效期内，则该缓存项及其结果集移动至临时数据存储区;如果T已超出有效期，则删除该缓存项及其对应的结果集.

外缓存的临时语义缓存区，用户访问 Deep Web获得新的查询数据时，根据外缓存替换的基本思想，若临时语义缓存区已满，则替换POPmin，替换超出有效期T的语义缓存项及对应结果集.

3 结束语

目前研究的预取技术中的缓存管理及缓存替换多是针对Surface Web，而且存在一些缺陷，例如对网页的大小和获取网页的延迟等因素没有考虑，当换入缓存中的文档副本较大时，可能会替换出多个较小的文档副本，影响缓存的命中率.经过实验测试发现，Deep Web数据集成系统未加入预取技术，和在代理服务器端采用多项式回归预取技术，且根据本文提出的存储管理方案进行管理，在缓存数量为100条时，查询响应时间最高降低比率为38.23%，最低降低比率为27.32%，预取准确率为44%;缓存数量为450条时，用户的查询响应时间达到最低，查询响应时间最高降低比率为40.33%，最低降低比率为28.12%，预取准确率达到了62%.由此可见对缓存的管理符合Deep Web的特点，原理简单清晰、易于实现，明显提高用户访问的速度.

[1]刘伟，孟小峰，孟卫一.Deep Web数据集成研究综述[J].计算机学报.2007，9(30):1475 －1489.

[2]Xu Huanqing，Wang Yongcheng.A Web Pre－fetching Model Based on Analyzing User Access Pattern[J].Journal of Soft ware.2003，14(6):1142 －1147.

[3]Shi L，Han Y，Ding X，et al.An SPN Based Integrated Model for Web Prefetching and Caching[J].Journal of Computer Science and Technology.2006，21(4):482－489.

[4]Christos B.Predictive Prefetching on the Web and Its Potential Impact in the Wide Area[J].World Wide Web .2004，7(2):143－179.

[5]Shi Lei，Han Yingjie，Ding Xiaoguang，et al.An SPN －based Integrated Model for Web Prefetching and Caching[J].Journal of Computer Science and Technology.2006，21(4):482 －489.

[6]石磊，孟彩霞，韩英杰.基于预测的Web缓存替换策略[J].计算机应用.2007，27(8):1842 －1845.

[7]SHIL，DNG XG，WEIL，etal.An Adaptive PPM Prediction Model[J].Journal of Computational Information Systems.2006，2(2):633－638.

[8]尹挺然，王珍娥，周頔.基于主动网络的最佳缓存位置计算[J].科学技术与工程.2007，21(7):5688－5960.

[9]Domenech J，Gil J A，Sahuquillo J，et al.Web Prefetching Performance Metrics:A Survey[J].Performance Evaluation.2006，63(9):988－1004.