《武汉工程大学学报》 2018年06期
685-690
出版日期：2018-12-28
ISSN:1674-2869
CN:42-1779/TQ
贪婪双尺寸频率算法的优化与改进
随着互联网的发展，Web服务器的压力越来越大，用户对网页的响应速度要求也越来越高。为了减轻Web服务器在高并发访问情况下的压力，缩短用户访问Web网站的时间延迟，可以在Web服务器和用户之间增设Web代理服务器。Web代理服务器将一些经常被访问到的Web对象缓存在代理服务器中，当用户由客户端向Web服务器发出请求时，请求将被发送到代理服务器，由代理服务器来进行处理。如果代理服务器中已经存有用户请求的Web对象，则经过代理服务器对缓存对象的一致性和有效性进行判断后，直接将有效的缓存对象返回给用户，或者去源Web服务器上取回最新的Web对象，存储在代理服务器中后，再将对象返回给用户。当代理服务器缓存空间不足时，缓存机制会根据缓存替换算法会将某些缓存对象移出缓存空间来存储新的Web对象［1］。因此，缓存替换算法的好坏是决定代理服务器性能的重要因素之一。最著名和最基本的缓存替换算法有最近最少使用替换（Least Recently Used，LRU）算法［2］，该算法优先替换掉那些离上一次被访问时间的时间间隔最长的对象。先进先出（First In First Out，FIFO）算法［3］，优先替换掉最先进入缓存区的对象。基于对象大小（Size）替换算法［4］，将缓存中最大的对象替换出去。还有最不经常使用替换算法，该算法将自进入内存后使用次数最少的对象替换出去。然而，它们有一个主要的不足之处，即它们仅依赖于一种流量特性，例如访问频率、驻留时间或最近访问时间。算法考虑的因素单一，所以造成了以上4种算法的性能有限。考虑到以上基本算法的不足，研究者们提出了综合考虑多因素的缓存替换算法。最小使用价值算法［5］包括Cao 和 Irani ［6］在1997年提出贪婪双尺寸算法，Cherkasova［7］在1998年提出的贪婪双尺寸频率（Greedy Dual Size Frequency，GDSF）算法，Lee等［8］在2001年提出的最近最少经常使用算法，以及文献［9］提出的基于保存价值的Hybrid算法。此类算法通常从文件对象的大小、访问频率、访问延迟等多个影响缓存性能的方面进行考虑，通过一个价值函数来计算每个对象的保存价值，当需要发生替换缓存时，优先将保存价值最小的对象替换出去。在最近几年缓存替换算法也取得了一些新的研究成果。Sajeev和Sebastian［10］在2011年提出了一种新的网络缓存对象分类方案，该方案使用多项逻辑回归技术对缓存对象进行分类。2012年，Ali和Shamsuddin［11］提出了基于机器学习技术的智能Web代理缓存方法，以Web代理日志文件作为训练数据，用支持向量机预测稍后可能重新访问的Web对象，与传统Web代理缓存技术LRU和GDSF结合，形成名为SVM-LRU和SVM-GDSF的智能缓存方法。2015年，Negr?o 和 Roque［12］提出了一种用于Web缓存的自适应语义感知替换算法，它为缓存替换过程添加了空间维度，根据从一个对象导航到另一个对象所需的链接数量来测量对象之间的距离，发生替换时，将远离最近访问的页面的对象作为移除的候选者。2017年，Benhamida和Bouallouche-Medjkoune［13］提出了使用相对频率来替换传统的访问频率，相对频率是使用文档访问次数及其在缓存中的生命周期计算的。文档的访问频率是缓存替换算法的重要考虑因素，本文引入了平均周期访问频率、最近周期访问频率、周期相对频率3个特性，将周期相对频率作为对象流行度的重要影响因子，综合了对象大小、网络带宽因素，提出了贪婪双尺寸周期相对频率（Greedy Dual Size Frequency Periodic Relative Frequency，GDSF-PRF）算法，在用户访问网页的习惯符合Zipf［14］定律的情况下，经过与LRU、FIFO、GDSF算法的实验对比，验证了GDSF-PRF在访问命中率和字节命中率上有更好的表现。1 相关工作1.1 缓存替换算法的性能指标缓存替换算法通常使用的性能评价指标有3个：请求命中率、字节命中率和访问延迟［15］。在发生数据请求时，如果缓存中已经保存了该数据，并且该缓存数据有效，可以直接将该缓存数据返回给用户，则称此次数据请求为一次命中；否则要向原始数据所在的服务器请求数据，此时称为一次缺失，即未命中。1）请求命中率请求命中率是代理缓存服务器缓存命中的次数占用户发出的请求总次数的百分比，用[Rh]表示。用[Nr]表示请求总次数，用[Nh]表示缓存命中次数，则[Rh]可表示为：[Rh=NhNr] （1）2）字节命中率字节命中率是代理缓存服务器本身向用户发出的字节数与用户总的请求数之比，用[Rbh]表示。用[Bh]表示缓存命中字节数，[Br]表示代理接收到的用户总请求字节数，则[Rbh]可表示为： [Rbh=BhBr] （2）3）平均访问延迟平均访问延迟是指从客户端请求数据到收到数据所需的平均时间，用[tal]表示。平均时间越短，缓存性能越好。用[Nr]表示请求总次数，用[t]表示[Nr]次请求总的访问延迟时间，则[tal]可表示为：[tal=tNr] （3）1.2 GDSF算法GDSF算法，即贪婪双尺寸频率缓存替换算法［16］。该算法的基本思想是使用某个目标保存价值函数来计算出缓存中所有缓存对象的保存价值H，当缓存剩余空间不足以保存新的对象时，根据这个H值将缓存对象由高到低进行排序，优先将缓存中保存价值H最低的对象替换出去。其目标函数为：[H(i)=L+Fr(i)×V(i)S(i)] （4）[H(i)]表示第i个缓存对象的缓存价值，[V(i)]表示将Web对象i引入到缓存中的所需要付出的代价，如带宽、网络延迟等。L为膨胀因子，初值为0，每当有Web对象替换出去时，L都会被重新赋值为那个被替换出去的对象的[H(i)]。[F(i)]为Web对象i的访问次数。该算法综合考虑了对象大小和访问频率因素，但是没有考虑目标的将来流行度因素，会造成较小对象且较短时间内访问频率大的缓存对象常驻在缓存空间中。1.3 已有的GDSF改进算法从文件大小角度来看，在GDSF算法中，文件大小越小，文件的H值越大，文件被替换出去的可能性就越小，这就导致小文件被存储的概率增大，大文件被替换出去的概率增大，导致了较低的字节命中率。因此，为了提高请求的命中率，降低文件大小对文件保留价值的影响程度，部分改进方案中，将[S(i)]调整为[log2[S(i)]]，即[H(i)=L+Fr(i)×V(i)log2[S(i)]] （5）从时间角度来看，文件再次被访问的可能性随时间的延长而降低。因此在计算对象保留价值时，还应考虑对象的时间价值。GDSF算法虽然考虑了文件的访问频率但是没有考虑时间因素。因此，有研究者引入了平均访问频度的概念，提出了GDSF-T（Greedy-Dual-Size-Frequency-Time）算法［17］。定义 在时间距离t内，Web访问对象i的平均访问频度为：[G(i,t)=Fr(i)t=Fr(i)tsys-tstore_timetsys＞tstore_time1,tsys=tstore_time] （6）其中，[Fr(i)]表示Web对象i在时间t内，被访问的次数。[tsys]表示缓存替换发生时的系统时间，[tstore_time]表示对象i进入缓存时的时间。改进后的算法GDSF-T的如下：[H(i)=L+V(i)log2[S(i)]×G(i,t)] （7）2 GDSF-PRF算法设计2.1 频率因素的改进GDSF算法中考虑了文件的访问频率因素，但是单纯的考虑文件的访问频率不能很好的反映文件的最近访问热度和将来可能热度，可能造成曾今某一个时段被高频率访问而近期未被访问的文件长时间驻留缓存的情况发生。因此，已经有研究者尝试对频率因素的考量进行改进，如1.3节中提到的GDSF-T算法，该算法引入了平均访问频度的概念来代替GDSF算法原有的单纯的访问频度因素，在文件访问频率的基础上增加了对文件的缓存驻留时间的考量，使得文件的平均访问频度随驻留时间的增长而降低，考虑的因素更全面，但是需要记录下每个文件初次进入缓存的时间，造成了额外的空间消耗，并且没有考虑到文件的最近访问时间。使用平均访问频度可以大致的描述文件在过去的访问热度，不能很好的预测文件将来可能的热度。因此，本文引入了平均周期访问频率、最近周期访问频率、周期相对频率3个特性。根据文件的平均周期访问频率和最近周期访问频率，得到周期相对频率，分析出文件访问频率的周期走势。对文件的访问频率进行周期性的计数，本文的访问周期使用次数周期N来代替时间周期，以此来避免对文件访问时间的存储，减小空间消耗。平均周期访问频率描述的是从文件进入缓存至今，在被访问过的周期里，平均每个周期被访问的频率。用[F(i)]表示文件i进入缓存后被访问的次数，[Nc(i)]表示文件i被访问过的周期数，则文件i的平均周期访问频率[Fa(i)]表示为：[Fa(i)=F(i)Nc(i)] （8）最近周期访问频率描述的是文件在最近的一个周期里被访问的频率。[Nnow]表示当前周期从周期开始时刻起至今的访问次数，[Fn(i)]表示文件i在当前周期里被访问的次数，则文件i的最近周期访问频率[Fc(i)]表示为：[Fc(i)=Fn(i)Nnow] （9）周期相对频率根据文件的平均周期访问频率和最近周期访问频率得到，周期相对频率描述的是文件的周期走势。如果文件i的最近周期频率[Fc(i)]小于文件i的平均访问周期频率[Fa(i)]，则可以说明文件i被访问的频率呈下降趋势，在未来被访问的相对频率小，发生缓存替换时文件i将有更大的可能性被替换出缓存空间。如果文件i的最近周期频率[Fc(i)]大于文件i的平均访问周期频率[Fa(i)]，则可以说明文件i被访问的频率呈上升趋势，在未来被访问的相对频率大，发生缓存替换时文件i将有更小的可能性被替换出缓存空间。k为参数，可根据业务调整k的值来调整相对频率对保留价值的的影响力度。周期相对频率[Fpr(i)]的表达式如下：[Fpr(i)=[Fc(i)-Fa(i)]k] （10）2.2 GDSF-PRF算法描述GDSF-PRF算法将GDSF算法公式（5）中的频率[Fr(i)]替换成周期相对频率[Fpr(i)]，即公式（10），目标函数如下：[H(i)=L+V(i)lnS(i)×Fpr(i)] （11）L为膨胀因子，初值为0，当缓存中有Web对象被替换出去时，L都会被重新赋值为那个被替换出去的对象的[H(i)]。[V(i)]为缓存空间从Web服务器获取Web对象i需要付出的代价，本文选择数据包的传送个数作为代价，TCP分段大小为536 bytes，因此[V(i)]的计算公式如下：[V(i)=2+S(i)536] （12）式（12）中[S(i)]为Web对象的字节大小。根据公式（11），可得如下GDSF-PRF算法的伪代码：Begin输入：要访问的文件dif 数据d not in cachewhile 缓存空闲大小