基于CAR动态调整的改进LRFU算法——CLRFU

王小林，还璋武

(安徽工业大学计算机科学与技术学院，安徽马鞍山 243032)



基于CAR动态调整的改进LRFU算法
——CLRFU

王小林，还璋武

(安徽工业大学计算机科学与技术学院，安徽马鞍山 243032)

[摘要]目前，已有LRFU(Least Recently Frequently Used)方法结合了访问时间和访问次数来优化缓存，但却无法适用于操作系统、存储系统、web应用等复杂场景。为了解决LRFU算法中无法动态调整λ以及现有自适应调整算法无法兼顾多种访问模式的问题，本文提出了一种基于CAR(Clock with Adaptive Replacement)动态调整策略的改进LRFU算法——CLRFU，并将该算法与局部性定量分析模型相结合，能够在不同访问模式下动态调整λ。实验结果表明，CLRFU算法在线性、概率和强局部访问模式下都具有较好的适应性，提高了缓存整体命中率。

[关键词]LRFU；CAR；动态调整；CLRFU

缓存作为一项提高计算机性能的重要技术，能够较好地避免数据库和磁盘文件被频繁访问。而缓存性能的好坏直接由缓存替换算法所决定，因此优良的缓存替换算法显得尤为重要。缓存中的页面置换技术在操作系统、存储系统、web应用、web service等多个平台使用，需要去适应不同的复杂的应用环境。传统的单级缓存算法已无法适用于越来越复杂的应用环境，所以研究热点已转向能够自适应的单级缓存替换算法和提升多级缓存的整体性能。

关于单级缓存的自适应替换算法的研究多集中于基于探测的策略、基于特殊应用的策略、基于时间和频率平衡的策略。然而，最普遍的访问特征仍然是局部性和频率性的体现，因而基于时间和频率平衡策略的算法具有更好的适用性。现有基于访问时间和访问次数的替换算法如MQ算法、ARC[1]算法(IBM缓存算法)、CAR[2-3]算法、LIRS[4]算法(Mysql缓存算法)、LRFU自适应算法等都有效提升了缓存整体效率。传统的LRFU[5]算法兼顾访问时间和访问次数，却对局部性特征和频率性特征缺少量化分析，每个对象权重函数CRF(Combined Recency and Frequency)中的λ是固定的，参数的调整很多时候是基于经验，无法以合适的CRF来平衡两种不同的访问模式，甚至很多时候性能比LRU和LFU还要差，从而不能很好地应用到实际环境。基于LRFU算法改良的自适应算法p-LRFU[6]在强局部访问模式下减少λ值以倾向于LFU策略导致缓存效率低下，自适应算法LALRFU[7]无法探测到大于缓存容量的循环访问流和概率访问模式，在线性和概率访问模式下命中率不好。

本文提出的CLRFU算法中将借助CAR中动态调整思想给每个对象添加标志位flag用来区分访问过一次和多于一次的对象，对象每访问一次flag加1，由于CAR算法保存了近期置换出的页面，通过这些历史信息结合LALRFU算法所提出的局部性定量分析模型，CLRFU算法根据不同访问模式下α表现出的规律动态调整λ的大小来适应不同的访问模式，若α趋向于0(连续3次)说明该访问模式趋于线性访问模式，此时将λ调整为-λ，使策略倾向于MRU，若α趋向于某一区间(连续3次，该区间跨度少于5%)，此时访问模式趋向于概率模式，将λ置为0，使策略倾向于LFU，此时算法可以使用flag这条属性淘汰flag中最小的数据对象。实验表明CLRFU算法在不同访问模式下及混合访问模式下都较好地提高了命中率。

1相关算法

1.1LRU算法

最近最少使用算法LRU(Least Recently Used)：LRU算法是使用较多的一种算法，LRU算法是根据对象的Recency信息进行缓存管理。LRU算法适合具有强局部性的访问模式，对于弱局部性访问模式很多时候却无能为力，容易被内存扫描影响，它也不能区分不同概率的页面。

1.2自适应调整算法：ARC和CAR

2003年，IBM的Nimrod Megiddo等人提出了自适应缓存替换算法ARC(Adaptive Replacement Cache)，该算法缓存区包含两个队列(当前只访问过一次的页面t1和访问超过一次的页面t2)，非缓存区包含两个队列(t1置换出的历史页面b1和t2置换出的历史页面b2)。

当访问对象在b1中时，这个迹象表明t1表小了，自适应调整链表t1的大小，

P=min(P+max(1，t2/t1)，C).

(1)

当访问对象在b2中时，这个迹象表明t2表小了，自适应调整链表t2的大小，

P=max(P-max(1，t1/t2)，0).

(2)

当缓存溢出时，t1≥max(1,P)时，删除t1中LRU端的对象，否则删除t2中LRU端的对象。这一算法与LIRS算法采用相似的思想，只是ARC引入了预测机制，通过预测数据出现的可能性提高缓存命中率，算法的运行维护开销比较大。该算法实现完全基于LRU算法，从而暴露出LRU几个严重缺陷，在线性访问模式中新读取的数据可能会轻易地不经过b1队列而直接被移出缓存，也没有捕捉到“频率”特性。

不久，IBM研究中心的Dharmendra Modha提出了一种改良ARC的缓存算法CAR。CAR将ARC与CLOCK[8]结合，t1和t2用CLOCK算法实现，b1和b2用LRU实现。能同时捕捉“近期”和“频率”两个特性，有效地解决了LRU算法不能捕捉“频率”的缺陷。

1.3LRFU算法及其自适应算法

Lee等人提出平衡访问时间和次数的算法LRFU(Least Recently Frequently Used)：缓存区每个对象都保存了一个属性代表CRF权重大小，用以表示该块被继续访问的可能性。LRFU对象中的CRF值只有在被访问的时候才会改变，而有替换请求时不会改变。该算法通过计算权值函数兼顾访问时间(Recency)和访问次数(Frequency)，原则是最近一次访问所占的权值最大，越往后权值越小。缓存区满的情况下优先淘汰CRF值最小的对象。

LRFU算法通过权值函数计算出CRF值，通过CRF值确定要置换出的页面。CRF值的计算公式为：

(3)

F(x)=(1/p)λx.

(4)

C(x)即对象x在第tbase时间点的CRF值，{t0,t1,…,tk}是对象x访问的时间点。

2008年，李占胜等人提出了一种结合ARC改进的LRFU算法p-LRFU，当访问流不断在缓存中命中时，通过不断减小λ值使其倾向于LFU策略，但在强局部访问模式下显然这样的策略表现非常差。

2014年，韩永提出的基于局部性定量分析模型的自适应算法LA-LRFU在强局部性访问模式下表现不错。局部性定量分析模型对应的访问模式具有以下数学特征：如图1所示，Ai为新子集的概率为β，Ai为先前出现过的子集概率为α，显然α+β=1，在Ai为先前出现的访问子集的条件下，Ai为距离访问时间为kd的访问子集的概率为qk-1p(p+q=1)，Ai有可能会生成Ai-d的概率为αp，Ai有可能会生成Ai-2d的概率为αpq，α=B/D(D：将多次关联访问作为一次有效访问，则d次访问统计为D次有效访问，B：d次访问中既不再缓存区又不再历史队列中的数据块个数)。

λ调整公式如下：

λ=θ(C)αp(q+αp).

(5)

其中，θ(C)=10-3+4000/C2.

图1　局部性定量分析模型中访问子集的生成概率

该模型认为λ值与αp值和概率衰减系数(q+αp)值的乘积为正相关，但缺少对α进行量化分析，在概率访问模式下α和p值相对固定，策略无法很好地捕捉到“频率”特性，在线性访问模式下效果也不好。

2CLRFU算法

仿真程序实现时，记录该对象上次访问的时间lastintime，权重信息CRF值和标志位flag值。程序将初始化缓存队列T和His。T的大小和His大小相等，T存放缓冲区的数据，t1和t2分别对应flag为1和大于1的对象序列，His存放最近从T中淘汰出的数据，b1和b2分别对应flag为1和大于1的对象序列。

CLRFU算法流程如图2所示，当访问对象X在T命中时，更新缓存T中的X的lastintime，CRF和flag属性，在缓存中缺失时，如果在历史队列中命中，需要更新X属性并移动到T中，否则将X直接插入T中。调整λ的时机和LALRFU一样。

图2　CLRFU流程图

缓存整理子模块流程如图3所示，当λ[-1,0)，除去T中CRF值最大的对象，当λ=0，CLRFU借助CAR中缓存对象数据结构中Flag标志位，除去Flag中最小的，如果有多个去除CRF值最小的对象到His，当λ∈(0,1]，CLRFU借助CAR动态调整思想移除t1或者t2中对象，若t1≥max(1,P)，除去t1中CRF最小的对象到His，否则除去t2中CRF最小的对象到His。如果His队列溢出，则要对其进行缓存剔除，除去His中CRF端的对象。

图3　CLRFU子模块整理缓存流程图

CLRFU算法：

输入:访问对象X输出:更新缓存C1:ifX∈Tthen2: update(T.X)3:elseifX∈Histhen4: move(His.X,T)5: if(X.flag==1)then6: useEq(1)tocomputeP7: else8: useEq(2)tocomputeP9: endif10: else11: insert(X,T)12: endif13:endif14:adjustα15:useEq(5)tocomputeλ16:if(T.size>C)then//整理缓存17:ifλ∈[-1,0)then18: move(T.X(max(CRF)),His)19:elseifλ==0then20: move(T.X(min(flag,CRF)),His)21:elseifλ∈(0,1]then22: if(Count(flag=1)≥max(1,P))then23: move(T.X(flag=1,min(CRF)),His)24: else

25: move(T.X(flag>1,min(CRF)),His)26: endif27: endif28: endif29: endif30: endif31:if(His.size>C)then32: delete(His,min(CRF))33:endif

3实验分析

为了验证本文提出的CLRFU算法的可行性及适用性，使用Java语言与Myeclipse开发环境开发仿真程序。我们将CLRFU和LRFU、p-LRFU以及LALRFU算法进行性能比较。LALRFU和p-LRFU算法根据文献中的描述设置参数，CLRFU算法中λ初始化为0.001，而LRFU中λ用1e-03和3e-03来做实验。

下面是数据访问模式简要分类：

(1)线性访问模式。当中有可能包含主要三种模式：连续访问模式、随机访问模式和循环访问模式。连续访问模式下数据访问是一个接一个。随机访问模式下数据访问下数据访问有可能被访问一次及多次。循环访问模式下数据访问数据访问存在一定间隔。

(2)强局部(聚簇)访问模式。该模式下一段时间内集中访问一些数据。

(3)全局概率性访问模式。各数据之间被访问的概率是相对独立的，每个数据对象都有一个被访问的可能性，彼此之间没有联系。

上述三种访问模式是所有实际工作负载的基础，不同的替换算法适应的不同数据访问模式不尽相同。我们采用了三个模拟Trace进行实验。三个模拟Trace对应三种访问模式：线性访问模式、强局部访问模式和概率访问模式。

图4至图6显示了在线性访问、强局部性访问和概率访问这三种模式下各个缓存替换策略的命中率。

图4　线性访问模式下LRFU及其自适应算法的命中率比较

图5　强局部性访问模式下LRFU及其自适应算法的命中率比较

图6　概率访问模式下LRFU及其自适应算法的命中率比较

图4显示了线性访问模式下各缓存策略命中率。线性访问模式参杂了循环访问模式和随机访问模式，当访问流处于循环访问模式时，若α趋向于0(连续3次)，此时可以将λ置为-λ，使策略趋向于MRU策略应对可能存在的循环访问模式，CLRFU命中率较其他策略提升明显。当Cache容量从7000到8000时，各个算法命中率提升了很多，说明此时Cache容量大于循环访问间隔，各个策略命中率趋于相同。

在图4中，当访问流中60%段集中访问10%的数据时，此时访问流体现较强的局部性，CLRFU表现良好，而p-LRFU在强局部性访问模式下没有体现很好的性能，因为当访问流在某一段时间内体现较强的局部性特征并连续在Cache命中时，该算法却规定减少λ值以倾向于LFU策略，该算法造成的负面影响在Cache容量较大时尤为突出。

在图5中，数据集遵循zipf定律，即20%数据占用80%的访问流。CLRFU在应对概率模式时，若α属于某一区间(连续3次，该区间范围少于5%)，此时将λ置为0，使CLRFU趋向LFU来提高缓存命中率。由于缓存中增加了标志位，在概率访问模式中，由于对α的分析有一定时间过程，有可能一开始脏数据冲掉将要访问的数据，导致命中率不是很好，一段时间后当替换策略倾向LFU时命中率转好。

针对三种访问模式，CLRFU虽然在概率访问模式下命中率不是很好。但在其它访问模式下都表现出了很好的命中率。

综上可知，一个具体的访问过程通常由多种访问模式构成，CLRFU算法可以实时发现访问模式的转换，并根据对应的访问模式动态调整λ的值，对多种访问模式都具有适用性。表1显示了当Cache块为5000时，ILRFU、LALRFU、p-LRFU及LRFU(LRFU1：λ=3e-03，LRFU2：λ=1e-03)在memory buddies trace下的平均命中率。

表1　各算法在memory buddies trace平均命中率

4结语

本文结合了CAR动态调整思想，并在文献[7]提出的局部性定量分析模型的基础上，分析不同访问模式所带来的α值的变化规律来动态调整λ的大小，这种改进算法使得缓存命中率普遍提高的同时并没有带来实现CAR缓存替换策略所带来的额外开销。针对多种访问模式，CLRFU均可显著提高缓存命中率。

[参考文献]

[1]Megiddo N,Modha D S.ARC A self-turning,low overhead replacement cache[C]//USENIX Conference on File and Storage Technologies.Berkerley,USA:ACM,2003:115-130.

[2]Bansal S,Modha D S.CAR:Clock with adaptive replacement[C]//USENIX Conference on File and Storage Technologies. Berkerley,USA:ACM,2004:187-200.

[3]Shamsheer S M.A throughput analysis on page replacement algorithms in cache memory management[J].International Journal of Engineering Research and Applications,2012(2):126-130.

[4]S Jiang,X Zhang.LIRS:An efficient low inter-reference recency set replacement policy to improve buffer cache performance[C].ACM SIGMETRICS Conf(SIGMETRICS’2002), Marina Del Rey.California,2002.

[5]Lee D,Choi J,Kim J H.LRFU:A Spectrum of policies that subsumes the least recently used policies[J].IEEE Transactions on Computers,2001(12):1352-1361.

[6]李占胜,毕会娟,李艳平.一种对LRFU置换策略的改进[J].计算机工程与应用,2008(17):153-157.

[7]韩永,姚念民,蔡绍滨.基于局部性定量分析模型的自适应替换算法LALRFU[J].计算机学报,2014(7):1538-1547.

[8]Jiang S,Chen F, Zhang X.CLOCK-Pro:an effective improvement of the CLOCK replacement[C]//PROc of USENIX 05,2005:121-130.

An Improved Algorithm of LRFU-CLRFU Based on CAR Dynamic Adjustment

WANG Xiao-lin，HUAN Zhang-wu

(Computer Science & Technology, Anhui University of Technology, Anhui Maanshan 243032, China)

Abstract:At present,existing LRFU (Least Recently Frequently Used) method is a combination of access time and the number of access to optimize cache, but it will not apply to operating systems, storage systems, web applications and other complex scenes. In order to solve the LRFU algorithm in dynamic adjustment λ and the existing adaptive algorithm can't combine multiple access mode, this paper proposes a improved LRFU algorithm-CLRFU which is based on the CAR (Clock with the Adaptive Replacement), with local quantitative analysis model, the combination of dynamic adjustment λ to different access mode. The experimental results show that the CLRFU algorithm has good adaptability in linear, probability and the strong local access mode and improve the cache hit ratio as a whole.

Key words:LRFU; CAR; dynamic adjustment; CLRFU

[中图分类号]TP

[文献标识码]A

[文章编号]2095-7602(2016)04-0031-07

[作者简介]王小林(1964- )，男，硕士生导师，教授，从事关键字分析研究。

[基金项目]国家自然科学基金“不可靠无线传感器网络中自适应稀疏压缩采样关键技术研究”(61402009)；安徽省高校自然科学研究重点项目“基于无线网络的行为弱监控研究与应用”(KJ2013Z023)；安徽省高校自然科学研究重点项目“基于关键字的大规模地理数据查询方法研究”(KJ2015A310)。

[收稿日期]2015-12-30