缓存替换策略技术综述

肖敬伟 ,刘金鑫

国家知识产权局专利局专利审查协作天津中心   天津   300304

摘要：随着网络技术的飞速发展，互联网上信息量、接入用户数量的急剧膨胀。大量数据的传输对系统I/O和网络带宽的高需求，使得服务器和网络带宽成为系统的瓶颈。缓存技术能很好地改善网络带宽性能、解决网络堵塞和用户访问延时时间过长等问题。通过在客户端和服务器之间配置代理缓存系统来缓存部分或全部数据，为就近的客户端请求提供服务，降低服务器负载和网络资源消耗，减小延迟。其作为提高系统性能的重要手段一直是研究的热点。本文综述了常用缓存替换算法以及作为热门研究的协同缓存。

关键词：缓存替换；LRU ；LFU ；混合式；协同

一、缓存替换策略的发展状况

按照缓存策略设计是否考虑了缓存层次分为单级缓存策略和多级缓存策略。单级缓存策略中，按照缓存替换标准具有的时间特性(Recency)、频率特性(Frequency)分为基于时间特性的策略、基于频率特性的策略、混合式替换策略。多级缓存策略中，按照要求缓存之间协作，提出基于协同操作的策略。

二、缓存替换策略的分支及其发展

（1）基于时间特性的策略

LRU 算法[1]选择最长时间未被使用的那一块淘汰掉。该算法基于局部性原理:如果某一个数据块被访问了,它很有可能马上还要被访问;相反,如果它很长时间都未曾使用,在最近的未来它仍然是不大需要的。LRU 算法开销高，因为 LRU 算法每次访问数据块都必须修改有关信息,且需要做连续的修改。此外,LRU 算法只注意了不同数据块最近一次访问时间的差异,而没有注意到不同数据块使用频率的不同。

（2）基于频率特性的策略

LFU 算法[2]把最近使用次数最少的数据块淘汰掉。不同数据块的使用频率独立分布,使用频率最高的数据块,最近被使用的概率也比较大。但是由于 LFU 算法不参考最近的历史信息,即使老数据不再有用了,只要其使用计数很高,就会一直保留在缓存中,因此难以适应不断变化的访问模式。

FBR算法[3]维护一个 LRU 栈,将 LRU 栈从栈顶到栈底分为三个区域:新区域、中间区域和旧区域,三个区域大小都保持不变。每个数据块都记录引用次数,当新区域中数据块命中时,引用次数不增加;当中间区域或者旧区域数据块命中时,引用次数增加。新加入的数据块和命中的数据块都放到栈顶，发生缓存替换时,将旧区域中引用次数最小的块替换出去。FBR 算法通过三个区域的设置为新数据块增加了一个过渡区,使其不会由于引用次数少而被马上替换。实现难点在于如何确定三个区域大小。

（3）混合式策略

LRU-K算法[4]是为解决数据库中的关联访问而提出。在关联访问中,尽管存在多次访问,但并不表明数据块是频繁使用的,所以不需要重点保存。LRU-K算法能有效识别关联访问。记录每个数据块的倒数第K次访问的访问时间,当需要淘汰数据块时,寻找访问时间最老的数据块丢弃。关联访问一般限制在两三次之内,所以当K值取2、3时,关联访问都能被屏蔽。当K取1时,LRU-K算法就是LRU算法。但是在关联访问不明显或者关联访问次数不固定的应用中,LRU-K性能就打了折扣。

LRFU算法[5]采用一个权值函数，该函数对所有以前的访问进行评估，其评估原则要兼顾recency和frequency两个特性，并且最近一次访问所占权值最大，越往后其权值越小。该权值被称作CRF(C0m—bined Recency and Frequen cy)值，表示该块未来被访问的可能，是进行块替换的依据。

（4）基于协同操作的策略

基于信息素的协同缓存替换算法[6]，首先,设计合适的协作Cache大小,可采用代价算法,建立预测缓存的模型。其次，根据蚁群算法的启示,建立基于信息素的Cache替换模型。协作Cache技术在移动P2P网络中资源请求的处理流程：对于需求发送方：1）移动节点i先寻找需要的数据。2）通过查找自己的存储器,没有找到合适的数据资源。3）决定向邻居节点请求需要的资源。对于邻居节点接收方即响应方:1）移动节点j当监听到有数据到达时,通知接收模块，接收模块对数据进行处理后,根据预定的机制进行验证等工作。2）对所有任务进行调度执行。再者,根据接收到的任务的需求,确定是否可以响应该数据请求,即查询向外提供的协作Cache资源。3）如果不能完成对方需求,给予通知。

基于博弈论中VCG拍卖算法的协同缓存策略[7]，在同一区域，移动用户会被多个WSP的缓存设备覆盖，因此使不同的WSP之间的cache进行合作，协同缓存。各个WSP的缓存服务器优先为本地信道分配带宽，若有剩余，则将这些带宽以商品形式进行拍卖，需要带宽的其他缓存服务器可以进行报价购买。当卖家缺少带宽时，可以用得到的虚拟支付再去购买别人的带宽，这样就能有效、公平的分配带宽资源，减少用户的等待延时。

三、总结

基于recency和frequency平衡策略仍然是研究的热点。但目前的一些cache算法研究忽略了用户行为变化规律、数据流行度等对替代算法性能的制约作用，将用户对资源的访问视为无记忆的行为。所以我们必须综合考虑多种因素对缓存算法的影响，未来将在这些方面继续开展研究。

参考文献：

[1]  Mattson R L, Gecsei J, Slutz D R, Traiger I L. Evaluation techniques for storage

hierarchies [C]. IBM System Journals, 1970.

[2]  Aho A V, Denning P J, Ullman J D. Principles of optimal page replacement [J].

Journal of the ACM, 1971.

[3]  Robinson J T, Devarakonda M V. Data cache management using frequency-based

replacement  [C].  Proceedings  of  the  1990  ACM  SIGMETRICS  Conference  on

Measurement  and  Modeling  of  Computer  Systems  (SIGMETRICS  1990).

[4]  O.Neil E J, O.Neil P E, Weikum G. The LRU-K page replacement algorithm for

database  disk  buffering  [C].  Proceedings  of  the  ACM  SIGMOD  Conference

(SIGMOD 1993).

[5]Lee Donghee，Choi Jongmoo，Kim Jong-Hun，etal.LRFU replacement policy：A spec trum of block replacement policies．IEEE Transactions on Computers，2001.

[6]牛新征,秦科,周明天.移动P2P网络的协作缓存优化策略.计算机研究与发展，2008.

[7]Jie Dai,Bo Li,Fangming Liu,aochun Li, Jiangchuan Liu.Collaborative Caching for Video Streaming among Selfish Wireless Service Providers. Global Telecommunications Conference (GLOBECOM 2011).