基于CAR動(dòng)態(tài)調(diào)整的改進(jìn)LRFU算法
——CLRFU

王小林，還璋武

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山 243032)

?

基于CAR動(dòng)態(tài)調(diào)整的改進(jìn)LRFU算法
——CLRFU

王小林，還璋武

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山 243032)

[摘要]目前，已有LRFU(Least Recently Frequently Used)方法結(jié)合了訪問時(shí)間和訪問次數(shù)來優(yōu)化緩存，但卻無法適用于操作系統(tǒng)、存儲(chǔ)系統(tǒng)、web應(yīng)用等復(fù)雜場景。為了解決LRFU算法中無法動(dòng)態(tài)調(diào)整λ以及現(xiàn)有自適應(yīng)調(diào)整算法無法兼顧多種訪問模式的問題，本文提出了一種基于CAR(Clock with Adaptive Replacement)動(dòng)態(tài)調(diào)整策略的改進(jìn)LRFU算法——CLRFU，并將該算法與局部性定量分析模型相結(jié)合，能夠在不同訪問模式下動(dòng)態(tài)調(diào)整λ。實(shí)驗(yàn)結(jié)果表明，CLRFU算法在線性、概率和強(qiáng)局部訪問模式下都具有較好的適應(yīng)性，提高了緩存整體命中率。

[關(guān)鍵詞]LRFU；CAR；動(dòng)態(tài)調(diào)整；CLRFU

緩存作為一項(xiàng)提高計(jì)算機(jī)性能的重要技術(shù)，能夠較好地避免數(shù)據(jù)庫和磁盤文件被頻繁訪問。而緩存性能的好壞直接由緩存替換算法所決定，因此優(yōu)良的緩存替換算法顯得尤為重要。緩存中的頁面置換技術(shù)在操作系統(tǒng)、存儲(chǔ)系統(tǒng)、web應(yīng)用、web service等多個(gè)平臺(tái)使用，需要去適應(yīng)不同的復(fù)雜的應(yīng)用環(huán)境。傳統(tǒng)的單級(jí)緩存算法已無法適用于越來越復(fù)雜的應(yīng)用環(huán)境，所以研究熱點(diǎn)已轉(zhuǎn)向能夠自適應(yīng)的單級(jí)緩存替換算法和提升多級(jí)緩存的整體性能。

關(guān)于單級(jí)緩存的自適應(yīng)替換算法的研究多集中于基于探測的策略、基于特殊應(yīng)用的策略、基于時(shí)間和頻率平衡的策略。然而，最普遍的訪問特征仍然是局部性和頻率性的體現(xiàn)，因而基于時(shí)間和頻率平衡策略的算法具有更好的適用性?，F(xiàn)有基于訪問時(shí)間和訪問次數(shù)的替換算法如MQ算法、ARC[1]算法(IBM緩存算法)、CAR[2-3]算法、LIRS[4]算法(Mysql緩存算法)、LRFU自適應(yīng)算法等都有效提升了緩存整體效率。傳統(tǒng)的LRFU[5]算法兼顧訪問時(shí)間和訪問次數(shù)，卻對局部性特征和頻率性特征缺少量化分析，每個(gè)對象權(quán)重函數(shù)CRF(Combined Recency and Frequency)中的λ是固定的，參數(shù)的調(diào)整很多時(shí)候是基于經(jīng)驗(yàn)，無法以合適的CRF來平衡兩種不同的訪問模式，甚至很多時(shí)候性能比LRU和LFU還要差，從而不能很好地應(yīng)用到實(shí)際環(huán)境?；贚RFU算法改良的自適應(yīng)算法p-LRFU[6]在強(qiáng)局部訪問模式下減少λ值以傾向于LFU策略導(dǎo)致緩存效率低下，自適應(yīng)算法LALRFU[7]無法探測到大于緩存容量的循環(huán)訪問流和概率訪問模式，在線性和概率訪問模式下命中率不好。

本文提出的CLRFU算法中將借助CAR中動(dòng)態(tài)調(diào)整思想給每個(gè)對象添加標(biāo)志位flag用來區(qū)分訪問過一次和多于一次的對象，對象每訪問一次flag加1，由于CAR算法保存了近期置換出的頁面，通過這些歷史信息結(jié)合LALRFU算法所提出的局部性定量分析模型，CLRFU算法根據(jù)不同訪問模式下α表現(xiàn)出的規(guī)律動(dòng)態(tài)調(diào)整λ的大小來適應(yīng)不同的訪問模式，若α趨向于0(連續(xù)3次)說明該訪問模式趨于線性訪問模式，此時(shí)將λ調(diào)整為-λ，使策略傾向于MRU，若α趨向于某一區(qū)間(連續(xù)3次，該區(qū)間跨度少于5%)，此時(shí)訪問模式趨向于概率模式，將λ置為0，使策略傾向于LFU，此時(shí)算法可以使用flag這條屬性淘汰flag中最小的數(shù)據(jù)對象。實(shí)驗(yàn)表明CLRFU算法在不同訪問模式下及混合訪問模式下都較好地提高了命中率。

1相關(guān)算法

1.1LRU算法

最近最少使用算法LRU(Least Recently Used)：LRU算法是使用較多的一種算法，LRU算法是根據(jù)對象的Recency信息進(jìn)行緩存管理。LRU算法適合具有強(qiáng)局部性的訪問模式，對于弱局部性訪問模式很多時(shí)候卻無能為力，容易被內(nèi)存掃描影響，它也不能區(qū)分不同概率的頁面。

1.2自適應(yīng)調(diào)整算法：ARC和CAR

2003年，IBM的Nimrod Megiddo等人提出了自適應(yīng)緩存替換算法ARC(Adaptive Replacement Cache)，該算法緩存區(qū)包含兩個(gè)隊(duì)列(當(dāng)前只訪問過一次的頁面t1和訪問超過一次的頁面t2)，非緩存區(qū)包含兩個(gè)隊(duì)列(t1置換出的歷史頁面b1和t2置換出的歷史頁面b2)。

當(dāng)訪問對象在b1中時(shí)，這個(gè)跡象表明t1表小了，自適應(yīng)調(diào)整鏈表t1的大小，

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

(1)

當(dāng)訪問對象在b2中時(shí)，這個(gè)跡象表明t2表小了，自適應(yīng)調(diào)整鏈表t2的大小，

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

(2)

當(dāng)緩存溢出時(shí)，t1≥max(1,P)時(shí)，刪除t1中LRU端的對象，否則刪除t2中LRU端的對象。這一算法與LIRS算法采用相似的思想，只是ARC引入了預(yù)測機(jī)制，通過預(yù)測數(shù)據(jù)出現(xiàn)的可能性提高緩存命中率，算法的運(yùn)行維護(hù)開銷比較大。該算法實(shí)現(xiàn)完全基于LRU算法，從而暴露出LRU幾個(gè)嚴(yán)重缺陷，在線性訪問模式中新讀取的數(shù)據(jù)可能會(huì)輕易地不經(jīng)過b1隊(duì)列而直接被移出緩存，也沒有捕捉到“頻率”特性。

不久，IBM研究中心的Dharmendra Modha提出了一種改良ARC的緩存算法CAR。CAR將ARC與CLOCK[8]結(jié)合，t1和t2用CLOCK算法實(shí)現(xiàn)，b1和b2用LRU實(shí)現(xiàn)。能同時(shí)捕捉“近期”和“頻率”兩個(gè)特性，有效地解決了LRU算法不能捕捉“頻率”的缺陷。

1.3LRFU算法及其自適應(yīng)算法

Lee等人提出平衡訪問時(shí)間和次數(shù)的算法LRFU(Least Recently Frequently Used)：緩存區(qū)每個(gè)對象都保存了一個(gè)屬性代表CRF權(quán)重大小，用以表示該塊被繼續(xù)訪問的可能性。LRFU對象中的CRF值只有在被訪問的時(shí)候才會(huì)改變，而有替換請求時(shí)不會(huì)改變。該算法通過計(jì)算權(quán)值函數(shù)兼顧訪問時(shí)間(Recency)和訪問次數(shù)(Frequency)，原則是最近一次訪問所占的權(quán)值最大，越往后權(quán)值越小。緩存區(qū)滿的情況下優(yōu)先淘汰CRF值最小的對象。

LRFU算法通過權(quán)值函數(shù)計(jì)算出CRF值，通過CRF值確定要置換出的頁面。CRF值的計(jì)算公式為：

(3)

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

(4)

C(x)即對象x在第tbase時(shí)間點(diǎn)的CRF值，{t0,t1,…,tk}是對象x訪問的時(shí)間點(diǎn)。

2008年，李占勝等人提出了一種結(jié)合ARC改進(jìn)的LRFU算法p-LRFU，當(dāng)訪問流不斷在緩存中命中時(shí)，通過不斷減小λ值使其傾向于LFU策略，但在強(qiáng)局部訪問模式下顯然這樣的策略表現(xiàn)非常差。

2014年，韓永提出的基于局部性定量分析模型的自適應(yīng)算法LA-LRFU在強(qiáng)局部性訪問模式下表現(xiàn)不錯(cuò)。局部性定量分析模型對應(yīng)的訪問模式具有以下數(shù)學(xué)特征：如圖1所示，Ai為新子集的概率為β，Ai為先前出現(xiàn)過的子集概率為α，顯然α+β=1，在Ai為先前出現(xiàn)的訪問子集的條件下，Ai為距離訪問時(shí)間為kd的訪問子集的概率為qk-1p(p+q=1)，Ai有可能會(huì)生成Ai-d的概率為αp，Ai有可能會(huì)生成Ai-2d的概率為αpq，α=B/D(D：將多次關(guān)聯(lián)訪問作為一次有效訪問，則d次訪問統(tǒng)計(jì)為D次有效訪問，B：d次訪問中既不再緩存區(qū)又不再歷史隊(duì)列中的數(shù)據(jù)塊個(gè)數(shù))。

λ調(diào)整公式如下：

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

(5)

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

圖1　局部性定量分析模型中訪問子集的生成概率

該模型認(rèn)為λ值與αp值和概率衰減系數(shù)(q+αp)值的乘積為正相關(guān)，但缺少對α進(jìn)行量化分析，在概率訪問模式下α和p值相對固定，策略無法很好地捕捉到“頻率”特性，在線性訪問模式下效果也不好。

2CLRFU算法

仿真程序?qū)崿F(xiàn)時(shí)，記錄該對象上次訪問的時(shí)間lastintime，權(quán)重信息CRF值和標(biāo)志位flag值。程序?qū)⒊跏蓟彺骊?duì)列T和His。T的大小和His大小相等，T存放緩沖區(qū)的數(shù)據(jù)，t1和t2分別對應(yīng)flag為1和大于1的對象序列，His存放最近從T中淘汰出的數(shù)據(jù)，b1和b2分別對應(yīng)flag為1和大于1的對象序列。

CLRFU算法流程如圖2所示，當(dāng)訪問對象X在T命中時(shí)，更新緩存T中的X的lastintime，CRF和flag屬性，在緩存中缺失時(shí)，如果在歷史隊(duì)列中命中，需要更新X屬性并移動(dòng)到T中，否則將X直接插入T中。調(diào)整λ的時(shí)機(jī)和LALRFU一樣。

圖2　CLRFU流程圖

緩存整理子模塊流程如圖3所示，當(dāng)λ[-1,0)，除去T中CRF值最大的對象，當(dāng)λ=0，CLRFU借助CAR中緩存對象數(shù)據(jù)結(jié)構(gòu)中Flag標(biāo)志位，除去Flag中最小的，如果有多個(gè)去除CRF值最小的對象到His，當(dāng)λ∈(0,1]，CLRFU借助CAR動(dòng)態(tài)調(diào)整思想移除t1或者t2中對象，若t1≥max(1,P)，除去t1中CRF最小的對象到His，否則除去t2中CRF最小的對象到His。如果His隊(duì)列溢出，則要對其進(jìn)行緩存剔除，除去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實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的CLRFU算法的可行性及適用性，使用Java語言與Myeclipse開發(fā)環(huán)境開發(fā)仿真程序。我們將CLRFU和LRFU、p-LRFU以及LALRFU算法進(jìn)行性能比較。LALRFU和p-LRFU算法根據(jù)文獻(xiàn)中的描述設(shè)置參數(shù)，CLRFU算法中λ初始化為0.001，而LRFU中λ用1e-03和3e-03來做實(shí)驗(yàn)。

下面是數(shù)據(jù)訪問模式簡要分類：

(1)線性訪問模式。當(dāng)中有可能包含主要三種模式：連續(xù)訪問模式、隨機(jī)訪問模式和循環(huán)訪問模式。連續(xù)訪問模式下數(shù)據(jù)訪問是一個(gè)接一個(gè)。隨機(jī)訪問模式下數(shù)據(jù)訪問下數(shù)據(jù)訪問有可能被訪問一次及多次。循環(huán)訪問模式下數(shù)據(jù)訪問數(shù)據(jù)訪問存在一定間隔。

(2)強(qiáng)局部(聚簇)訪問模式。該模式下一段時(shí)間內(nèi)集中訪問一些數(shù)據(jù)。

(3)全局概率性訪問模式。各數(shù)據(jù)之間被訪問的概率是相對獨(dú)立的，每個(gè)數(shù)據(jù)對象都有一個(gè)被訪問的可能性，彼此之間沒有聯(lián)系。

上述三種訪問模式是所有實(shí)際工作負(fù)載的基礎(chǔ)，不同的替換算法適應(yīng)的不同數(shù)據(jù)訪問模式不盡相同。我們采用了三個(gè)模擬Trace進(jìn)行實(shí)驗(yàn)。三個(gè)模擬Trace對應(yīng)三種訪問模式：線性訪問模式、強(qiáng)局部訪問模式和概率訪問模式。

圖4至圖6顯示了在線性訪問、強(qiáng)局部性訪問和概率訪問這三種模式下各個(gè)緩存替換策略的命中率。

圖4　線性訪問模式下LRFU及其自適應(yīng)算法的命中率比較

圖5　強(qiáng)局部性訪問模式下LRFU及其自適應(yīng)算法的命中率比較

圖6　概率訪問模式下LRFU及其自適應(yīng)算法的命中率比較

圖4顯示了線性訪問模式下各緩存策略命中率。線性訪問模式參雜了循環(huán)訪問模式和隨機(jī)訪問模式，當(dāng)訪問流處于循環(huán)訪問模式時(shí)，若α趨向于0(連續(xù)3次)，此時(shí)可以將λ置為-λ，使策略趨向于MRU策略應(yīng)對可能存在的循環(huán)訪問模式，CLRFU命中率較其他策略提升明顯。當(dāng)Cache容量從7000到8000時(shí)，各個(gè)算法命中率提升了很多，說明此時(shí)Cache容量大于循環(huán)訪問間隔，各個(gè)策略命中率趨于相同。

在圖4中，當(dāng)訪問流中60%段集中訪問10%的數(shù)據(jù)時(shí)，此時(shí)訪問流體現(xiàn)較強(qiáng)的局部性，CLRFU表現(xiàn)良好，而p-LRFU在強(qiáng)局部性訪問模式下沒有體現(xiàn)很好的性能，因?yàn)楫?dāng)訪問流在某一段時(shí)間內(nèi)體現(xiàn)較強(qiáng)的局部性特征并連續(xù)在Cache命中時(shí)，該算法卻規(guī)定減少λ值以傾向于LFU策略，該算法造成的負(fù)面影響在Cache容量較大時(shí)尤為突出。

在圖5中，數(shù)據(jù)集遵循zipf定律，即20%數(shù)據(jù)占用80%的訪問流。CLRFU在應(yīng)對概率模式時(shí)，若α屬于某一區(qū)間(連續(xù)3次，該區(qū)間范圍少于5%)，此時(shí)將λ置為0，使CLRFU趨向LFU來提高緩存命中率。由于緩存中增加了標(biāo)志位，在概率訪問模式中，由于對α的分析有一定時(shí)間過程，有可能一開始臟數(shù)據(jù)沖掉將要訪問的數(shù)據(jù)，導(dǎo)致命中率不是很好，一段時(shí)間后當(dāng)替換策略傾向LFU時(shí)命中率轉(zhuǎn)好。

針對三種訪問模式，CLRFU雖然在概率訪問模式下命中率不是很好。但在其它訪問模式下都表現(xiàn)出了很好的命中率。

綜上可知，一個(gè)具體的訪問過程通常由多種訪問模式構(gòu)成，CLRFU算法可以實(shí)時(shí)發(fā)現(xiàn)訪問模式的轉(zhuǎn)換，并根據(jù)對應(yīng)的訪問模式動(dòng)態(tài)調(diào)整λ的值，對多種訪問模式都具有適用性。表1顯示了當(dāng)Cache塊為5000時(shí)，ILRFU、LALRFU、p-LRFU及LRFU(LRFU1：λ=3e-03，LRFU2：λ=1e-03)在memory buddies trace下的平均命中率。

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

4結(jié)語

本文結(jié)合了CAR動(dòng)態(tài)調(diào)整思想，并在文獻(xiàn)[7]提出的局部性定量分析模型的基礎(chǔ)上，分析不同訪問模式所帶來的α值的變化規(guī)律來動(dòng)態(tài)調(diào)整λ的大小，這種改進(jìn)算法使得緩存命中率普遍提高的同時(shí)并沒有帶來實(shí)現(xiàn)CAR緩存替換策略所帶來的額外開銷。針對多種訪問模式，CLRFU均可顯著提高緩存命中率。

[參考文獻(xiàn)]

[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]李占勝,畢會(huì)娟,李艷平.一種對LRFU置換策略的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2008(17):153-157.

[7]韓永,姚念民,蔡紹濱.基于局部性定量分析模型的自適應(yīng)替換算法LALRFU[J].計(jì)算機(jī)學(xué)報(bào),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

[中圖分類號(hào)]TP

[文獻(xiàn)標(biāo)識(shí)碼]A

[文章編號(hào)]2095-7602(2016)04-0031-07

[作者簡介]王小林(1964- )，男，碩士生導(dǎo)師，教授，從事關(guān)鍵字分析研究。

[基金項(xiàng)目]國家自然科學(xué)基金“不可靠無線傳感器網(wǎng)絡(luò)中自適應(yīng)稀疏壓縮采樣關(guān)鍵技術(shù)研究”(61402009)；安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目“基于無線網(wǎng)絡(luò)的行為弱監(jiān)控研究與應(yīng)用”(KJ2013Z023)；安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目“基于關(guān)鍵字的大規(guī)模地理數(shù)據(jù)查詢方法研究”(KJ2015A310)。

[收稿日期]2015-12-30