Web智能代理的预取技术和缓存技术

天津大学学报　第34卷　第5期2001年9月

Web智能代理的预取技术和缓存技术

赵　政,张　钢,杨　洁,王　松,舒炎泰

(天津大学电子信息工程学院,天津300072)

󰀁

　　　　　　　　摘　要:针对同一个工作组中成员可能对Web有相似的兴趣点和访问习惯问题,研究了主要

包括缓存和预取两个部分的智能代理技术;研究了代理缓存三种替换算法:LRU和LRU的两种变种.仿真试验表明,LRU算法的命中率极差,将LRU的两种变种相结合则是一种较好的方案.通过引入预测算法和门限算法,代理服务器可以预测最近将要访问到的页面,并在客户实际请求提出之前有选择地下载.因为单个客户访问某个页面的历史次数往往不够多,将预测算法放在代理服务器上比放在客户端的预测概率更准确.通过在代理服务器上实现缓存和预取技术,可减少用户访问Web的响应时间,还可减少实际访问Web服务器的总次数.并提出了一个为发展中国家用户缩减Web访问代价的有效方法.关键词:万维网;智能代理;预取;缓存;门限

中图分类号:TP393.4　　　文献标识码:A　　　文章编号:0493-2137(2001)05-0563-05

1　工作组成员访问兴趣分布分析

　　为了证实同一个工作组成员可能有相同的兴趣进而访问相似的页面,该课题通过对三个工作小组长达3个月的Web访问日志文件的分析,统计出全部访问的URL和相应访问频度.定义:特定页面的访问次数　　Qn=全部页面的访问次数

达到某个Qn的页面数　　Pn=

所访问过的页面总数

　　Xn=∑Pn

Q>q

n

n

　　用图1可确定成员兴趣的相似程度.在图中,观察到三个不同工作组在qn=5%时的Xn值是介于10%～20%,表明这三个工作组成员的Web访问有着足够的相似度.

2　缓存替换算法的改进

　　如果Web页面在第1次被访问时存放于Cache中,则该页面下次被该成员或其他同组成员访问时会获得很高的效率.由于采用了预取技术,某一Web页面在首次被访问时可能已经被预取到Cache中,从而减少Web服务器的负载和用户访问的延迟,提高了代理Cache的性能.提高代理服务器Cache的命中率很困难,首先,Cache命中需要被一个用户请求多次或被不同用户多次使用;其次,由于大多数浏览器具有内部缓存,因此用户在一次会话中很少对同一个页面向代理服务器提出多次请求.这些因素都减少了代理服务器Cache的命中率.

　　对于具有无限大磁盘空间的代理Cache,缓存页面不会因为空间缺乏而被替换,由此得到了真实代理

　　Xn和Qn的关系如图1所示.

图1　工作组成员Web访问兴趣分布Fig.1　Distributionofgroupinterests

Cache的命中率上界.在对积累的3个月的真实Web访问记录进行仿真后,得到了30%～50%的命中率.

󰀁收稿日期:2000-01-15;修回日期:2001-04-03.　　　基金项目:国家自然科学基金资助项目(69672031).　　　作者简介:赵　政(1948-),男,硕士,教授.

・564・

实际代理服务器只具有有限的磁盘空间,缓存页面将会因为磁盘空间不足而被替换.作者比较了传统LRU和两种LRU变种等三种Cache替换算法.传统LRU算法对于WebCache有先天不足,因为不仅需要考虑时间因素,还需要考虑文件大小,文件类型以及其他的网络性能参数.因为Web文件通常是大小不同的,当WebCache的大小有限时,应决定选择Cache替换策略,是否因一个大文件而替换掉许多的小文件(理论上,减少Cache中的文件总数导致命中率下降),保存较少的大文件还是保存较多的小文件.

　　比较仿真结果表明,传统LRU算法的命中率极差,而LRU-MIN和LRU-THOLD算法[1]的结果基本相同.所以选择LRU-MIN和LRU-THOLD算法的

结合作为该研究缓存的替换算法.2.1　Cache替换策略

　　假定新请求文件的大小是s,而且不在WebCache之中.

　　传统的LRU算法是,当WebCache的磁盘自由空间小于s时,重复替换那些驻留时间最久而又未使用的文件直到磁盘自由空间至少为s(LRU算法有可能会为一个较大的文件而替换掉许多小文件).

　　LRU-MIN算法是LRU的一种变体,它力图使被替换的文件个数最少,设L代表文件表,T表示一个尺寸的整数.1)设T为s;2)设L为尺寸不小于T的文件列表(L可以为空);3)从L中替换掉最久未使用的文件直到L为空或Cache磁盘自由空间至少为T;4)如果Cache自由空间小于s时,设T=T/2返回2).　　LRU-THOLD算法基本与LRU算法相同,只是当文件大小超过域值时不被缓存,即使此时WebCache还有足够的磁盘自由空间,进而避免替换掉大量小尺寸文件.

2.2　仿真结果及其分析　　比较LRU、LRU-MIN和LRU-THOLD的结果(见表1),藉以确定命中率的大小和磁盘尺寸的要求.

表1　三种WebCache替换算法的比较

Tab.1　Comparisonofthreecachereplacementpolicies

算法LRULRU-MLRU-T

命中率/%最小23.827.429.5

最大26.440.832.9

Cache/Mbit最小22.923.014.8

最大61.462.826.2

生存期/h最小1.32.87.2

最大15.047.3151.6

天津大学学报　　2001年　第34卷　第5期　

LRU-THOLD算法需要计算域值,因此LRU-MIN是其中最好的策略.这种策略不需要参数并且在大数情况下性能良好.另一方面,LRU-THOLD算法需要较少的磁盘空间,并且命中率随Cache空间减小,下降较为缓慢(相对于LRU-MIN),该算法较好.另外,表1中缓存文件的生存期在不同的算法中差别很大,LRU-THOLD算法中生存期几乎比LRU的长10倍.这是由于文件替换的次数太频繁,LRU算法中文件生存期最短.

　　为此采用了一种适应性的策略,先使用LRU-MIN算法,当Cache大小接近可用磁盘空间时改用LRU-THOLD算法,LRU-THOLD使用的域值逐渐减小直至Cache减小到较低水平.

3　预测算法

　　预测算法是收集所有用户的访问历史记录并预测用户将要访问的页面.代理服务器需要记载所有用户的HTTP请求并调整预取行为.在本方案中,代理服务器要使用两类计数器:页面访问计数器和链接计数器.每一个页面A有一个相应的页面计数器CA,另外,如果页面B与A有直接的超链相连,使用计数器C(A,B)表示这个链接计数.每次页面A被访问时CA加1;类似的,当用户通过A访问B页面时,C(A,B)加1.工作组的CA和C(A,B)的累积值可由各个用户的相应计数器得到.

　　使用条件概率p(B󰀁A)表示“用户在访问页面A后将要访问页面B的概率”.因此个人访问概率可以如下确定:当页面A正被用户阅读时,对于链接到s上的页面Bi的访问概率p(Bi/A)=C(Bi,A)/CA.　　如前所述,使用代理服务器的工作组有着相似的访问兴趣,因此工作组访问概率的确定在代理服务器预测算法中起着重要作用.设工作组中有k个用户,则页面Bi的工作组访问概率可定义为

k

k

j

(A,B)

i

　　P(Bi󰀁A)=

jA

∑C

j=1

/∑CjA

j=1

式中:C表示第j个成员的CA.

　　可以使用三种方法确定最终算法使用的访问概率:第一种是使用个人访问概率pu,这个概率根据个人兴趣来影响预测的准确性,然而当该用户的Web访问历史资料非常少时,pu不能反映用户的真实访问兴趣;第二种选择是使用工作组访问概率pg,当工作组成员有相似的访问兴趣时,工作组的访问概率可以在一定程度上反映个人的兴趣,成员间的兴趣越相似,使

　　由表1可见,当磁盘空间无限制时,代理缓存以30%～50%为上界,与文献[3]所述基本相同.在表1的各项参数中,LRU算法的表现最差.由于　天津大学学报　　赵　政等:Web智能代理的预取技术和缓存技术

・565・

󰀂T󰀂

sb-( 1+ 2)s

用pg的效果越好;第三种是将前两种方法的优点结合起来,通过引入权重󰀁,访问概率可以表示为　　p=󰀁pu+(1-󰀁)pg兴趣或工作组兴趣.

(1)

其中,0<󰀁<1.要以通过调节󰀁的大小来强调个人

(4)

4　门限算法模型

　　本文的门限算法是在文献[3]的方法的基础上,作了一些重要的改进.文献[3]的方法仅适用于单个用户使用的Web预取,预取引擎置于用户本地机器的

浏览器上.而本文的模型是将预取置于代理服务器上,利用集中的访问历史数据得到更好的预测效果.另外,通过调整参数󰀁,可以把文献[3]的算法作为本文算法的一种极限情况,即󰀁=1时的特例.　　为在系统资源使用和用户访问延迟之间作出权衡,预取策略是先预测将要被访问的页面,然后只选择其中的一部分下载.这项工作由预测模块完成,可以实时地确定各个Web服务器的预取门限来决定应下载的文件.　　使用“代价”来衡量系统的性能,其中包含延迟代价(󰀂T＄/单位等待时间)和系统资源代价(󰀂B＄/单位处理时间).延迟代价表示等待时间对于用户的重要程度.系统资源代价包括终端节点处理数据包的代价和数据传输代价.在本节中,探讨研究了不同系统模型下减少文件预取平均代价的优化问题.

4.1　代价函数C

　　对于某个给定系数,设 为不用预取时用户请求的到达率.假定预取不应影响用户的访问行为,即虽然用户可以由预取功能较快地获得所需页面,但其访问请求仍以 的速率以相同模式到达.设正常请求的到达率和预取请求的到达率分别为 1和 2,则通过预取文件满足的用户请求率为 - 1,由于预取页面被使用的概率为p,则前式也可写作p 2,即　　　　 1+p 2=

或　　　 1+ 2= +(1-p) 2间为x单位的请求响应时间为

xs=(3)1-!b(1-!)

式中:!为系统负载;s为文件平均大小;b为系统容量.　　　　t=

在如图2所示的系统中,!=s( 1+ 2)/b.这样,正常请求的代价(包括系统资源代价和延迟代价)为

B󰀂s+󰀂T󰀂t=󰀂B󰀂s+　　c1=󰀂图2　预取系统模型Fig.2　Prefetchsystemmodel

　　由上述公式可见,当预取文件增多时,正常请求的代价增加.这是因为预取增加了系统负载,因而增

加了文件获取延迟.　　预取请求的平均代价为　　　　c2=󰀂B󰀂s最终的平均代价函数为

1󰀂c1+ 2󰀂c2s={[ +(1-p) 2]󰀂B+

( -p 2)󰀂T

　　　　}(6)

b-[ +(1-p) 2]s

将式(1)代入式(6),可得成本代价函数为

sC={[ +[1-󰀁󰀂pu-(1-󰀁)pg] 2]󰀂B+

[ -(󰀁󰀂pu+(1-󰀁)󰀂pg) 2]󰀂T

b-[ +[1-󰀁󰀂pu-(1-󰀁)pg] 2]s　　C=

(7)

4.2　预取率 2的优化

　　假定p和 的值已知,为使系统的平均请求成本

最小要确定 2的值.对式(7)求C对 2的二阶导数得2s2d2C[󰀂T( s-b(󰀁pu+(1-󰀁)pg))(1-　　2= d 2

󰀁pu-(1-󰀁)pg)/(b-s( + 2(1-󰀁pu-(1-󰀁)pg)))3]

系统稳定的前提是 1+ 2因此,当 s即式(7)在为0时取得最大值.此时 2取 2为

d 2

󰀁1 2=b- s-s(1-󰀁pu-(1-󰀁)pg)　　(9)

󰀂T(b(󰀁pu+(1-󰀁)pg)- s)　)󰀂B(1-󰀁pu-(1-󰀁)pg)2> 2时,代价函数随 2的增大而减小.特别地,即当

2≤0时,对于给定的p, 和r(r=󰀂T/󰀂B),当 2在当 [0, /p]范围内增大时,代价函数减小,也就是说此时󰀁

󰀁

(5)

(8)

(2)

　　在等时间片分时共享处理机系统中,平均处理时

・566・

预取具有访问概率为p的文件越多,代价就越低.此时将预取全部文件[4].

4.3　预取门限H的计算

　　计算预取门限H,预取模块将预取所有访问概率

󰀁

超过门限的文件.在式(9)中得到, 2≤0,当且仅当

天津大学学报　　2001年　第34卷　第5期　

表2　响应时间和网络性能参数fn的关系Tab.2　Relationshipofresponse-timeand

networkperformancefactorfn

响应时间/ms

f

n

<1000.8

100～300300～500500～1000>1000

0.9

1

1.1

1.2

(1-!)r2(10)

(1-!)b+r

其中,!= s/b,则可得预取门限为　　(󰀁pu+(1-󰀁)pg)≥1-(1-!)r(11)2(1-!)b+r

󰀁

　　式(10)表明,若访问概率p不小于门限H, 2≤　　H=1-0.依前述分析,此时预取全部文件将降低系统代价.门限H和系统负载!在不同r值下的关系见图3.

5　智能代理的实现

　　代理服务器在客户程序和远端Web服务器之间传递数据.为实现全双工连接,代理服务器必须等待两端的数据到来而不能在一端无限阻塞时挂起.为多用户提供服务的代理服务器若使用循环的实现方法会使性能不佳,因为循环实现需要用户串行接受服务而响应时间过长.预取行为加重了这种情况.并行实现方法避免了单个用户独占资源,减少了用户响应时间,而且并行实现可以将控制部分与数据传输部分分开.据此,作者采用了并行的面向连接的实现方法.

　　这里使用多线程来实现并行计算.代理服务器有两个常驻线程:一个接受和处理控制台命令,另一个接受用户请求.当用户请求到来时,代理产生两个新线程用于Web服务器和用户程序数据的双向传输.

　　预取模块包含三个主要部分:预取文件管理模块、预取线程与正常请求处理线程交互管理模块以及预取算法.本课题设计了一个全局链表来管理全部线

图3　门限H和系统负载!在不同r值下的关系Fig.3　PrefetchthresholdHasafunctionofutilization

fordifferentvalueofr

程,链表结构称为“控制节点”.每个线程由一个控制节点来记录线程状态和属性以及线程同步和互斥的信号量.其作用大致相当于UNIX中的I-NODE.5.1　预测访问概率的计算

　　为计算式(1)中的访问概率,需要记录每个用户的全部访问历史计数器,从而得到用户访问概率和工作组访问概率.参数󰀁可采用一种适应性的方法来确定,󰀁应随特定用户对某个负面的访问增多而增大.可用下式确定󰀁,其中Cu为某用户某页面的访问次数,Cg为工作组对该页面的访问次数.

Cu

　　　　　　Cu<10,Cg>100Cg　　󰀁=

2Cuarctan　　Cu>10∀10

　　当系统负载!增加时,门限H也相应增加,即较少的文件将被预取.当r值较小时,这种变化不是单调的,其原因为,当系统负载很小时,预取并不能节省很多时间;当系统负载增加时,传输文件耗时增加而预取

会节省更多的时间,即预取门限降低;当负载继续增加时,预取文件将会导致用户正常请求响应时间增加,此时门限应该升高.

　　在确定预取门限时,还应考虑一些其他的网络性能参数,如Web服务器的负载,端到端路由个数,路由器间的带宽和每个路由的实时流量等.利用一些已有测量软件,可获得一些准确数据用于门限H的计算.　　这里,使用Web服务器响应时间作为网络性能的综合指标,为此引入网络性能参数fn,新的门限HR为　　HR=fn󰀂H

(12)

　　响应时间和fn的关系如表2所示.表2由数千次实际测量得到,依表中数据可得到较好的实际效果.

2Cgarctan　　C<10,Cg<100∀10

　　当Cu<10且Cg>100时,工作组访问概率起主导作用.如果Cu<10且Cg<100,可认为此时预测的准确度不会好,这种情况将随着代理的使用而消失.5.2　HR的修正

　　在式(12)中,可得到用于预取门限的HR,实现中　天津大学学报　　赵　政等:Web智能代理的预取技术和缓存技术

・567・

还需要考虑代理计算机的性能、并行线程个数、内存以及其他参数.为增加代理服务器的整体性能,可将线程分为不同的优先级:所有正常请求线程具有最高优先级,而预取线程依访问概率大小取得优先级.　　图4是主动代理服务器的逻辑图.

作为给定整数.运行中,并发线程总数通常小于150,用户对响应时间基本满意.

6　结　语

　　Web流量持续以指数级增长,缓存技术对缓解网络拥塞可以起到一定作用.但最近的研究表明,缓存命中率不高于50%.原因很简单,用户总是请求最新的信息.进一步提高命中率的一种有效方法是采用预取功能.在发展中国家,网络带宽相对较窄,本文提出的主动代理技术可以有效地减少用户的访问等待时间,缓解网络拥塞状况.

　　感谢加拿大渥太华大学信息技术与工程学院教授OliverW.W.Yang在研究期间提出了许多有益的建议.

[4]

参考文献:

[1]　MarcAbrams,CharlesRStandridge.Cachingproxies:

limitationsandpotentialas[Z].http://ei.cs.vt.edu/

图4　主动代理服务器逻辑图Fig.4　Logicmodelofactiveproxyserver

succeed/www4/www4.html.

[2]　GlassmanS.Acachingrelayfortheworld-wideweb

[A].FirstInternationalWorldWideWebConference[C].Toronto,1994.69-76.

[3]　JiangZhimei.Anadaptivenetworkprefetchscheme[A].

IEEEInternationalConferenceonCommunications[C].

Part1,1997.8-12.

[4]　GwertzmanJ.Autonomousreplicationinwide-areanet-works[R].TechnicalReport,HarvardUniversity,1995.17-95.

　　当代理计算机忙于处理用户的正常请求时,预取线程应该减少,因此实际实现中将HR修正为H=HR+0.1×HR×U,其中U由系统当前负载决定,可用当前线程总数除以某个给定整数而近似得到.实现当中,代理计算机采用IntelPentiumII350,128MRAM和6.3GHD,为20个用户服务.在这里取500

󰀁

PREFETCHANDCACHETECHNIQUEINWEBINTELLIGENTPROXY

ZHAOZheng,ZHANGGang,YANGJie,WANGSong,SHUYan-tai

(SchoolofElectronicInformationEngineering,TianjinUniversity,Tianjin300072,China)

Abstract:InaWebtheusersinthesameworkgroupmayhavesimilarinterestsandhabits.ThispaperstudiestheintelligentproxytechniquesforpeoplewhohaveaccesstotheWeb.Theintelligentproxyhastwoparts:cacheandprefetch.Threereplacementpoliciesforproxycachehavebeenstudied:LRUandtwovariationsofLRU.Thesimu-lationshowsthatbasicLRUgivesthepooresthitrate,andtherefore,amixtureoftheothertwopoliciesisclosenastheproposedscheme.TheintroductionofthepredictionalgorithmandthresholdalgorithmshowsthattheproxycanpredictwhichWebfileswillbeneededinthenearfuture,andsomeofthemshouldbedownloadedbeforetheyarereallyrequestedbytheusergroup.Amoreaccurateprobabilitycanbeobtainedbyrunningitontheproxyserv-erratherthanontheclientsite,whenthenumberofthevisitofafilebysingleclientsisnotnumerousenough.Per-formingthetechniquesofprefetchandcacheontheproxyservercanreducenotonlythelatencyofusersbutalsothetotalnumberofaccessrequeststotheWebserver.Thus,thispaperprovidesawaytoreducethecostofaccesstotheWeb.

keywords:Web;intelligentproxy;prefetch;cache;threshold