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

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

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

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

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

1相關(guān)算法

1.1LRU算法

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

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

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

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

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

(1)

當(dāng)訪問(wèn)對(duì)象在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端的對(duì)象，否則刪除t2中LRU端的對(duì)象。這一算法與LIRS算法采用相似的思想，只是ARC引入了預(yù)測(cè)機(jī)制，通過(guò)預(yù)測(cè)數(shù)據(jù)出現(xiàn)的可能性提高緩存命中率，算法的運(yùn)行維護(hù)開銷比較大。該算法實(shí)現(xiàn)完全基于LRU算法，從而暴露出LRU幾個(gè)嚴(yán)重缺陷，在線性訪問(wèn)模式中新讀取的數(shù)據(jù)可能會(huì)輕易地不經(jīng)過(guò)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等人提出平衡訪問(wèn)時(shí)間和次數(shù)的算法LRFU(Least Recently Frequently Used)：緩存區(qū)每個(gè)對(duì)象都保存了一個(gè)屬性代表CRF權(quán)重大小，用以表示該塊被繼續(xù)訪問(wèn)的可能性。LRFU對(duì)象中的CRF值只有在被訪問(wèn)的時(shí)候才會(huì)改變，而有替換請(qǐng)求時(shí)不會(huì)改變。該算法通過(guò)計(jì)算權(quán)值函數(shù)兼顧訪問(wèn)時(shí)間(Recency)和訪問(wèn)次數(shù)(Frequency)，原則是最近一次訪問(wèn)所占的權(quán)值最大，越往后權(quán)值越小。緩存區(qū)滿的情況下優(yōu)先淘汰CRF值最小的對(duì)象。

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

(3)

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

(4)

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

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

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

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

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

(5)

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

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

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

2CLRFU算法

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

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

圖3　CLRFU子模塊整理緩存流程圖

CLRFU算法：

輸入:訪問(wèn)對(duì)象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語(yǔ)言與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來(lái)做實(shí)驗(yàn)。

下面是數(shù)據(jù)訪問(wèn)模式簡(jiǎn)要分類：

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

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

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

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

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

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

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

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

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

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

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

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

綜上可知，一個(gè)具體的訪問(wèn)過(guò)程通常由多種訪問(wèn)模式構(gòu)成，CLRFU算法可以實(shí)時(shí)發(fā)現(xiàn)訪問(wèn)模式的轉(zhuǎn)換，并根據(jù)對(duì)應(yīng)的訪問(wèn)模式動(dòng)態(tài)調(diào)整λ的值，對(duì)多種訪問(wèn)模式都具有適用性。表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é)語(yǔ)

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

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

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

[收稿日期]2015-12-30