一种高效的自适应代理缓存一致性替换算法

一种高效的自适应代理缓存一致性替换算法

0缓缓机技术研究网络技术和web服务的快速发展导致了网络过载和服务器负载过大的问题。为了解决这些问题,提出了一种新型的内容分发网络(ContentDeliveryNetwork,CDN),利用缓存服务器,也称作代理缓存,将内容从中心服务器推向网络的边缘,使得内容距离用户只有一步之遥。其中,一致性策略和替换策略的研究是提高代理缓存系统性能的两个重要研究方向。而以往的研究往往局限于将这两种策略作为两种独立的机制分开研究,从而不能完美的提升代理缓存系统的整体性能。本文考虑如何将这两种策略有机地结合起来,并拟合能反应用户访问模式的访问特性,探讨了代理缓存一致性策略和替换策略的处理流程、性能评价指标和研究现状,进而提出将这两种策略结合起来的一致性—替换算法的处理流程和主要性能评价指标。1其他替换算法一个有效的代理缓存的替换策略来源于对WWW业务访问特性的深刻认识,因此目前所提出的替换策略大部分来源于对WWW访问特性的分析,如LRU、LFU、SIZE、LRV、GreedyDual-Size等。通常被用来排序的关键值有访问频率、访问延迟、文档大小、访问流逝时间等,而使用这些关键值作为排序的关键字也可能采用不同的方法。因此目前已有的替换策略非常多,为了进行性能比较,概括描述几个有代表性的替换算法。LRU(least-recently-used)算法:最先移出最近最少使用的文档,其优点是实现简单,在内存缓存中很有效,其缺点是没有考虑文档大小和延迟时间。LFU(least-frequently-used)算法:最先移出最少使用的文档,其优点也很简单,其缺点除了LRU的缺点以外,如果没有失效机制,可能使过时的文档永远待在缓存器里。SIZE算法:首先清除大文档,其优点是移出大文档,可以保留更多的小文档,产生更高的请求命中率,其缺点是可能使小文档永远留在缓存器中,字节命中率偏低,且再次下载大文档时,占用网络资源很多。LRV(lowest-relative-value)算法:在估计文档时,基于和文档相关的值,的计算是对轨迹数据进行经验分析后得到的。其优点是字节命中率优于其它算法,其缺点是,由于是对轨迹分析得到的,参数的选取依赖于特殊的轨迹。LNC算法(最小正规化代价算法):它是根据引用率评估Web文档的代价。引用率是一个反映文档未来被访问的可能性大小的量,由文档的访问历史和现在流逝的时间组成,和文档单元价值一起形成一个公平、一致性的代价。该算法是一个高效的算法,与其它算法不同的是,它有LRU算法的简洁,对文档代价的计算既不需要保留以前的访问记录,又不需要有复杂的参数估计,同时还能迅速地体现文档访问率的变动情况。2基于上年度网络的特征特性,提出并介绍互联网为了得到用户Web访问在时间和空间分布上的特性,本文将采用对InternetTrafficArchive(ITA)在Internet上公开的轨迹文件进行分析的方法,具体过程如下。(1)访问时段及访问情况描述通过对轨迹文件的分析显示Web访问具有很强的时间局部性,时间局部性是代理所看到的Web业务普遍具有的一个性质。也就是说用户都倾向于再次访问近来访问过的内容。其主要原因一是用户对网络内容的访问在时间上呈现局部性,另外一个重要原因是用户对内容的兴趣重叠。图1是对轨迹文件中连续24小时的访问统计,以秒为单位记录下所有内容访问时间间隔,图中显示的是时间间隔在90s内的访问次数分布情况,从图中可以看出,内容被再次访问的引用率与流逝时间成指数关系,也就是说被再次访问概率随时间的增加而显著下降,流失的时间越长,再次被访问的概率就越低。用户请求到达时间服从指数分布。对于上述访问时序性可以这样来描述,设t0是最近一次访问内容后流逝的时间,tk是k次访问内容和k-1次访问内容之间的时间间隔,设第k-1次访问内容后得到的平均访问间隔时间为λk-1,那么第k次访问内容的平均访问时间间隔为:λk=atk+(1-α)λk-1。其中α是参数,α大于等于1/2即可。可以看出,λ反映了内容当前的访问率。令λf为最后一次访问后得到的平均访问间隔,由于请求的到达时间服从指数分布,故经过时间tc后被访问的概率为:内容下一次被访问的平均时间间隔为:所以可以得到它的引用率为:这个引用率Fi可以在访问时间和频率上反映用户访问特性。(2)内容访问的重尾分布近年来,许多Web访问特性的研究发现:Web对象的大小分布服从Pareto分布:参数a称为重尾度索引,它决定分布的重尾度,参数k决定重尾分布的尾起始点。重尾分布的一个例子就是Pareto分布,用于说明一个小的问题集合比其他所有问题对输出的影响更大。用在Web文档特性上则说明一个网站上的所有内容中,较小的内容占了很大的比例,同时较大的内容也是存在的,并且呈现出重尾特性。在轨迹文件中随机抽取一段连续时间里的访问轨迹,其内容访问大小分布如图2、3。图2显示的是第一次抽取情况,时间为2400s,共32009次请求,其中有31910次请求的内容小于70KB,即位于图中下方密集区内,占总数的99.7%,有28418次请求的内容小于10000B,占总数的88.7%。图3显示的是第二次抽取,时间为40s,共有418次请求,其中有369条分布在10000B以内,占总数的88.3%,而这些在10000B以内的请求内容分布大部分分布在2000B以内。可以看出,用户对内容的请求更趋向于对较小内容的访问。通过对内容访问大小分布分析可以看到,对内容的访问也符合重尾分布。从中可以得到对内容大小为x的访问概率约等于对上述分布函数的求导,即:其中aka是一个常数。从中可以得出用户对内容访问在内容大小上的引用率Fd=aka/xa+1,它在内容访问分布上反映了用户的访问特性。3新鲜标志的确定,根据分ACRA包括一致性策略和替换策略两部分,一致性策略确定新鲜标志以保证缓存副本的新鲜程度;同时,替换策略确定替换标准以便将网页换入或换出代理缓存。(1)自适应ttl机制代理缓存的强一致性可通过无效机制和每次查询机制来保证。前者在目前可用的Web服务器上不被支持;而后者增加了网络的额外负载。目前,所有的代理缓存只能保证弱一致性,用户可能得到的是旧数据。如果弱一致性是可接受的,而且网络带宽较窄,自适应TTL机制是较好的弱一致性维护技术,且对那些不经常对网页进行修改的Web服务器来说,它是实现缓存一致性的主要方法,大多数代理服务器都使用这种机制来维护一致性。如果代理缓存的替换算法能用TTL来选择要换出缓存的网页,将会改善缓存的性能。因此,选用自适应TTL机制作为本算法的一致性策略。(2)目标函数的建立代理缓存的替换策略需要解决的问题相当于寻找满足约束条件并使目标函数最大的解,即代理缓存的替换策略是基于最优化模型的。该模型定义为:假设Web服务器上有n个网页,网页i的大小为sizei(sizei≥0,i=1,2,…,n),综合价值为KeyValuei(KeyValuei≥0),代理缓存的容量为S。计算网页i的KeyValuei,尽量将KeyValuei最大的网页放在缓存中,因此目标函数可定义为式中:取0或1,1表示网页在缓存中,0表示网页不在缓存中。在最优化模型中,如何定义KeyValue(即替换标准),使其能较好地体现Web访问特性,是替换算法是否有效的关键。(3)不同待存储的网页副本会出现不同方案算法的处理过程(如图4所示)为:(1)从客户端获得请求的网页;(2)判断被请求的网页在代理服务器中是否有相应的缓存副本;(3)如果有,根据副本的TTL值来判断它是否新鲜,如果新鲜,表示缓存命中,则将副本响应给客户端;(4)如果缓存中没有被请求的网页或者是副本不新鲜,表示缓存缺失,要从Web服务器上取回新鲜的网页,则要判断缓存剩余空间是否可以容纳新的网页副本;(5)如果有足够的缓存剩余空间,则将网页副本放入缓存中或替换掉旧的副本;否则,按KeyValue进行替换。4算法的设计4.1不同类别网页的合作设置网页的TTL很重要,如果TTL足够小,代理缓存的一致性就能得到保证,但额外增加了网络负担;TTL太大,代理缓存的一致性很难得到保证。通常,用户访问模式影响代理缓存的替换决策,而网页特性(如类型)影响代理缓存的一致性决策,因此,有必要将网页特性融入到ACRA中。一般情况下,HTML/text类网页经常更新,而其它类网页(如图像、声音等)变化很小。因此,可根据网页类型的不同来设置网页的TTL,例如设HTML/text类网页的TTL小一些,而其它类网页的TTL大一些。ACRA的一致性策略是根据Web服务器的响应消息头来为每一新接收到的请求网页设置TTL的,具体有以下3种情况:(1)如果消息头有“Expires”时,就设网页i的TTL为网页的到期时间expiretime(Expires的值)减去代理缓存收到网页i的最新版本的时间(incachetime),即(2)当消息头无“Expires”,但有“Last-Modified”时,如果是HTML/text类网页,可设网页的TTL为否则,对于其它类网页就设网页的TTL为式中:accesstimei——网页i的当前访问时间,参数p1,p2取值范围为[0.1,1],一般取p1=0.5,p2=1。(3)当消息头无“Expires”和“Last-Modified”时,可由管理员根据实际的Web访问特性来设置网页的TTL()。如果是HTML/text类网页,可设网页的TTL为否则,对于其它类网页就设网页的TTL为式中:p1和p2的取值同上,userttl的取值一般为4～24小时。根据具体情况,可设时间长一些。在ACRA中采用的自适应TTL算法与传统的自适应TTL算法是有区别的,其在于:ACRA根据网页类型来设置网页的TTL;另外,当在Web服务器的响应消息头中无“Expires”和“Last-Modified”时,管理员能够根据需要来设置网页的TTL。因此,ACRA能更准确地估计网页的TTL,从而减少将旧数据响应给用户的概率。4.2不同sdi的一致性缓存替代算法的主要目的是使缓存中所存放的文件能最大程度的满足客户对服务器文件的请求。也就是说,缓存替换算法的目标就是使下面的表达式最优化限制条件为:profiti表示单个文件的价值。其中Ft,Fd在上文中已经给出定义。si是第i个缓存文件的大小,S为缓存的容量。由表达式(12),(13)定义的问题等同于一个NP难度的背包问题,然而,目前还没有十分有效的算法来解决这一类问题。如果我们假设被缓存文件的大小相对于缓存容量来说足够的小,以至于几乎可以填满整个缓存空间,则表达式(13)可以表示为:那么,简单贪婪算法即可解决这一问题。除此之外,一致性替换算法还应优先缓存不经常改变的网页,用一个typei来区别,当网页为HTML/text类网页时typei=1,当为其他类网页时typei=2。因此最终决定网页文件i是否被替换的标准为文件的综合价值KeyValuei当缓存内没有足够的空间存放新鲜的网页副本时,KeyValuei把值最小的文件替换出去,直到有足够的空间存放新鲜的网页副本。5算法的实现(1)替换算法性能我们用基于Trace-Driven模拟实验来评价该算法的性能,模拟模型如图5所示。其中:(1)选用某个Web服务器上的2008年1月1日至2008年12月31日的访问日志;(2)动态更新的Web服务器库用来模拟Web服务器提供网页;(3)访问序列库用来模拟客户不断发出访问请求;(4)为了能更好地评价该算法的性能,替换算法选用具有代表性的LRU、LFU、Size与ACRA做性能对比;(5)评价缓存替换策略和一致性策略的主要性能指标分别是命中率(HR)和陈旧率(SR),但高命中率和低陈旧率有时是相互矛盾的,只能综合考虑这两个指标或使用其它中间指标来衡量。为此,我们提出命中陈旧比(HSR):HSR能更好地衡量代理缓存的各种算法的优劣和缓存系统的整体性能,因此我们选用它比作为主要的性能评价指标。(2)动态更新数据比较通过Trace-Driven模拟实验,如果服务器动态更新数据比较频繁,我们可以得到如图6-8所示的模拟结果。在陈旧率方面,ACRA综合考虑了网页的一致性问题,所以它的陈旧率必然总是最低的(如图6)。例如,当Web服务器动态更新数据比较频繁时,ACRA的陈旧率比LRU、LFU、Size的陈旧率分别平均降低了1.25%,7.35%和31.95%。在命中率方面,ACRA的替换策略综合考虑了网页的大小、访问次数、类型等因素,但受到一致性策略对网页在缓存中的影响,其命中率是动态变化的。当网页的相对比较长时,ACRA的命中率比LFU和LRU的命中率都高;反之,当网页的相对较短时,ACRA的命中率可能会不如LFU的高,但比LRU的命中率高。在整个模拟过程