一种基于对象属性的Web缓存替换的方式分析

0引言
　　随着在线视频与社交媒体技术的演进，基于HTTP的流量成为互联网流量的重要组成部分。尤其在当前流量中大量重复数据的传输不仅占用带宽资源，而且也进一步影响用户访问延时。为了降低访问时延，提升用户体验，Web缓存技术与Web预取技术是当前网络交互性能改进的主要手段。对于缓存技术来说，主要分为两个层次：服务端缓存与客户端缓存。其中，服务端缓存技术主要是将用户频繁访问的数据放置于更靠近边缘用户位置，从而缩短传输路径，如内容分发技术；而客户端缓存则主要在用户端建立本地缓存以直接响应用户的多次请求，如浏览器中的网页缓存等。但无论缓存的性质和种类，缓存替换策略均是影响缓存效率的重要因素。如何更有效地对这些数据进行存储与替换即已成为当前互联网的研究热点。
　　1相关工作
　　Web的缓存管理，可分为缓存更新策略与缓存定位算法两个重要部分。缓存更新策略主要可分成三类：
　　（1）基于访问时间，以LRU（Least Recently Used）或其相似类为主；
　　（2）基于访问频率，以LFU（Least Frequently Used）或其衍生类算法为主；
　　（3）基于其他属性，以对象空间大小，对象价值度等其他度量指标，构造对象评价函数，以GDSF\[1-2\]为主。
　　研究中进一步发现，单纯对缓存对象本身属性进行评价计算并不足以有效提升Web数据的管理效率。文献\[3\]针对无线网络中的缓存提出一种协作式缓存替换机制，其中将对象一致性，最近命中间隔时间以及对象大小三个因素作为替换的权值因子。文献\[4\]针对移动数据库系统提出一种基于Markov图的缓存替换策略，对目标未来的位置进行预测，从而将高频数据进行预取，提升缓存效率。然而这些方法都没有考虑对象内在语义属性，本文考虑到网络数据在应用层中的表示方式，将数据本身的信息进行融合分析作为替换的权值因子，同时结合对象的重引用间隔（Reuse Interval），对缓存对象的价值度进行计算，由此而提升了缓存的性能。
　　2算法描述
　　为了研究Web请求的分布特征，在连续三天的校园网关的网络日志中提取了427 936个用户请求，其中包括167 981个不同的URL。如图1所示，该数据集符合典型的zipfα分布，并且0.6<α<0.8。对象的访问频度越大，表示其热门程度越高。提升缓存性能的关键在于尽量延长热门对象在缓存中的存活时间。图1数据集中的URL分布
　　Fig.1Distribution of data set第3期李乔，等：一种基于对象属性的Web缓存替换策略智能计算机与应用第4卷 图2展示了在数据集中最热的8个URL的访问序列，y轴表示这8个URL，x轴表示在考察期三天内每个URL出现的次序。由图2可知，热门的URL在某段时间内都具有被访问次数较多的特性，其中一部分URL逐渐变热的，如url-2和url-5；一部分URL的被访问行为则较为平滑，如url-8。而对于接近url-1的这类URL，由于其被访问行为表现了一定的周期性，但周期间隔较长，在LRU的缓存策略下，将发生多次替换，从而降低缓存性能。对于接近url-7的这类URL，虽然具有一定的周期性，但其周期间隔不断增长，在LFU策略下，该类URL的权值始终保持上升，然而其热度却呈现下降趋势，从而导致缓存污染。图2热门URL的访问序列
　Fig.2Access Sequence of hot URLs
　　
　　
　　基于以上分析可得，热门URL的访问行为主要可分为以下3类情形：
　　（1） 访问行为较为均匀，具有周期性，例如url-8,url-4;
　　（2） 访问行为逐渐变快，如url-5;
　　（3） 突发性增长，如url-3,url-6。
　　由于LRU算法的本地局部性，采用该算法的缺陷在于无法描述对象的访问频度；而LFU算法虽然将频度作为对象的权值，但由于缓存污染以及权值的单调性却降低了缓存的性能。基于此，本文首先考虑将访问间隔变化作为缓存对象的基础权值。
　　为了更直观地描述本文提出的算法，首先进行以下定义。
　　定义1访问间隔：缓存内对象的重引用距离，即本次命中该对象与上次命中该对象之间相差的缓存访问次数。
　　访问间隔是一种区别于绝对频度的缓存对象价值度的表示方法，但其与频度一致的地方则在于都是仅仅考虑对象的命中属性，而没有对整个缓存对象的上下文环境乃至缓存对象本体内在属性进行综合性衡量。在Web缓存中，由于Web是根据网络数据的命名规则对其进行查询与分发（如URL，P2P中的文件hash值），因此对这些外在的属性进行细致化描述，并将其作为对象价值的参考能够进一步提升整体缓存效率。
　　由于互联网数据主要通过URL进行定位，而URL的命名通常具备一定的语义，例如体育类相关的网页URL往往包含sport，音乐类包含music等。如图3所示，对于cba的解析首先通过CDN提供的DNS服务器对域名进行解析，而后根据sports重定向到存放sports相关的服务器上，最后通过URI定位到存储cba的服务器。一般而言，对于用户兴趣划分的一级目录命名较为一致，而对于二级，三级（如cba,nba等）目录的命名则未必相同，这就表示对URL只进行一层分析即可，所消耗的代价也极低。而且CDN运营商本身也已经根据不同的一级目录将数据分别放置于不同的服务器上，由此来实现分发效率的提升。图3URL解析过程
　　Fig.3The procedure of URL parsing在此，将URL中包含的部分语义信息作为缓存对象的价值计算参数，对URL中的域名与一级目录进行分析，并对缓存对象的热度进行计算。同时，时间敏感性是网络数据访问的典型特征，大多热门资源的热度伴随时间呈现出整体下降趋势。文中将缓存空间标记为S={obj1,obj2,...,objn},S=n，则新到达一个objn+1后，缓存管理机制将原空间S中价值最低的objmin替换为objn+1。
　　Web中的缓存是典型的网络分布式缓存系统，同时该缓存系统作为实时在线系统，对缓存对象价值度的计算时间的要求也较高。基于此，考虑将对象访问历史、应用层数据信息、用户的分散度作为综合热度的影响因素，尽可能提升未来一段时间内缓存效率。本文所用符号参数如表1所示。对象obji的被访问历史可以描述为Hobj={ad_value,reqset}，其中ad_value是对象的平均访问间隔值，间隔越小说明被访问得越频繁；reqset={},i∈N，N为访问该对象的用户数。为了对缓存内容热门度进行多维衡量，可将obj_dnval，obj_idxval，actn作为对象热 度的评价参数。一般而言，域名的热度表示该网站在整个域内的热门程度以及影响力，而以往单纯采用url的价值度并未考虑到网站热度对用户未来访问的影响，例如A网站内a页面被访问10次，而B网站中b页面也被访问10次，而A的总访问次数为100，B的总访问次数为10，那么a在未来被访问的概率应当大于b，这是由于A的知名度更高，随之A中的页面被访问的概率也更高。类似地，对象标签价值度对衡量缓存内容的热度也具有参考价值，例如标签为q的对象被访问100次，标签为p的被访问10次，则对于被访问10次的标签为q的对象a，其价值度也应大于访问数为10标签为p的对象b。文中则采用公式（1）计算对象的域名价值度与标签价值度。具体公式为：
　　obj_dnval=obj_dn∑ni=1obj_dn,
　　obj_idxval=obj_idx∑ni=1obj_idx（1）
　　表1参数描述
　　Tab.1Parameter Description参数描述obji第i个对象reqseti访问第i个对象的用户集合，是1个二元组集合reqsetval第i个对象的行为属性值，与reqset有关wvali第i个对象的综合权值，即综合热门度actn第n个用户的活跃度Hobj对象的被访问历史，是1个2元组集合obj_url对象的urlobj_dn对象的域名访问密度obj_idx对象url中的标签访问密度，一般为第1级索引ufreqik第k个用户访问对象i域名的频度dh_table域名哈希表，存放域名被访问次数obj_dnval对象域名的热度obj_idxval对象标签的热度
　　本文在缓存对象的替换过程中，考虑访问者属性进一步细致化对替换与否进行决策。reqsetval在本质上是一种概率值计算，由表1可知reqset是一个由用户活跃度和访问频度二元组构成的序列，而研究设定的目标则在于通过分析该序列得到该对象在未来出现的概率，并且对象价值度与概率值正直接相关。reqsetval的计算如式（2）所示，该式表示当用户活跃度较低时，即使总访问频度价值也不一定能够超过用户活跃度高的访问对象的价值，且显然可得reqsetval<1。对象总价值度wval的计算则如公式（3）所示，式中将用户行为与对象属性作为访问间隔的权值参数，将对象热度进行了更细粒度的计算。式（3）中的α、β是对应的调节参数，可以针对不同的网络需求进行设定。
　　reqsetvali=∑Nk=1actk·ufreqkN·∑Nk=1ufreqk,(actk<1)（2）
　　wvali=(α·obj_dnvali+obj_idxvali2+
　　β·reqsetvali)·ad_valuei（3）
　　通过以上分析，给出热度计算算法。如算法1所示，首先通过查询域名与标签的哈希表，得到对象属性的权值，其次通过查询用户行为表得到用户活跃度，最后通过公式（3）得到最终的对象热度wval。假设域名总数为M，标签总数为K，用户数为N，则该算法所需的空间为O(M+K+N*M)。而时间复杂度的计算则由于查询的过程主要通过hash函数进行，查询时间为O(C),其中的C为常数。通过设置每个用户的总访问次数，可以使公式（1）的计算时间为常数级，而公式（3）的时间复杂度上限为O(N*M)，即该对象被所有用户都访问过。因此，算法的时间复杂度上限即为O(N*M)。在实际部署中，百万级域名与千万级用户数的网络规模下，整个存储空间大约为10GB数量级。
　　多维度融合热度计算的算法如下：
　　Input:对象obj，域名哈希表dh_tab，标签哈希表ix_tab，用户活跃表ac_tab；
　　Output:对象热度obj_hvalue
　　 1.解析obj所对应的域名，标签，访问者id；
　　 2.对和进行hash计算得到dnhash与idxhash；
　　 dnhash 在dh_tab中 then
　　 4.得到obj_dn；
　
　　 6.在dh_tab中插入dnhash；
　　 if
　　 dnidx 在ix_tab中then
　　 9.得到obj_idx；
　　
　　11.在ix_tab中插入idxhash；
　　 if
　　13.更新dh_tab和ix_tab中对应的值；
　　14.根据公式（1）计算分别得到其域名与标签热度obj_dnval,obj_idxval；
　　15.通过用户id在ac_tab中查询对应活跃度；
　　16.根据公式（2）得到obj的行为属性值reqsetvali；
　　17.根据公式（3）得到obj的wvali。
　　3实验
　　文中采用校园网关采集的数据作为实验数据，其中用户的请求共计427 636条，对象大小在1MB~100MB之间随机均匀分布。在实验中，使用几种已有的内容管理策略与本文的BCV（Based on Content Value）算法进行比较。比较后的分析结果如下。
　　（1）基于邻居交换的缓存策略CCB\[5\]。该策略采用协作式替换方法，在替换时查询邻居节点的缓存列表，优先替换邻居已存储的资源。
　　（2）基于Aging的缓存策略ABC\[6\]。该策略目标是为了减少网络延迟以及资源发布者的负载，通过在传输路径中动态修改资源年龄的协作式缓存机制将热度最高的资源放置于网络最边缘。
　　（3）基于协作式中心化决策缓存策略APDR\[7\]。该策略通过建立内容上一跳路由表，进而产生每个内容的多播树，只有对该数据的第一个请求到达时会转发至上游节点，并等待该响应的数据到达后转发给剩余请求的端口。同时，在缓存替换策略中采用定期更新与LFU结合的策略以防止数据污染。
　　如图4所示，随着缓存空间的增大，每种缓存策略的字节命中率都不断提升，但由图4可以看出随着缓存增大，本文提出的BCV算法优势较为明显，这是由于提出的算法考虑了内容对象的空间大小以及融合热度，而APDR虽然命中率也较高，但其关注的因素在于汇聚用户的请求，并未将路由器种类纳入研究范围。
　　图4缓存命中率对比
　　Fig.4Comparison of hit ratio4结束语
　　本文主要对当前Web缓存系统中的替换策略进行改进，提出基于内容价值度的缓存替换算法，该算法考虑到Web对象中隐含的语义属性，并将其作为对象的价值度参数实行了统一计算，进一步提升了缓存效率。实验表明，文中设计的算法比其他策略高出7%-10%的命中率。
　　参考文献：
　　\. Computer Communications, 2001, 24(2): 174-183.
　　［2］CHERKASOVA L, CIARDO G. Role of aging, frequency and size in Web caching replacement strategies\[C\]//Proceedings of the 9th International Conference on High-Performance Computing and Networking, Amsterdam, The Netherlands, 2001:114-123.
　　［3］JOY P T, JACOB K P. A key based cache replacement policy for cooperative caching in mobile ad hoc networks\[C\]// Proceedings of IEEE 3rd International Conference on Advance Computing Conference, 2013: 383-387.
　　［4］CHAVAN H, SANE S, KEKRE H B. A Markov-graph cache replacement policy for mobile environment\[C\]// Proceedings of International Conference on Communication, Information & Computing Technology, 2012:1-6.
　　［5］DONG L J, ZHANG Y, RAYCHAUDHURI D. Enhance content broadcast efficiency in routers with integrated caching\[C\]// Proceedings of 16th IEEE ISCC, Kerkyra, Corfu, Greece, 2011:320-322.
　　［6］MING Z, XU M, WANG D. Age-based cooperative caching in information centric networks\[C\]//Proceedings of IEEE INFOCOM Workshop on Emerging Design Choices in Name-Oriented Networking. Orlando, FL, USA, 2012:268-273.
　　［7］刘外喜, 余顺争, 蔡君，等. ICN 中的一种协作缓存机制\[J\]. 软件学报, 2013, 24(8): 1947-1962.王庆斌.航材需求预测的研究\[J\]. SCIENCE & TECHNOLOGY INFORMATION科技信息，2013年（1）.
　　\[2\]刘卫红,崔振霞.基于BP神经网络的药品采购资金管理研究 \[J\]. 中国乡镇企业会计 ,2012,20(1): 70-71.