王小林，還璋武

(安徽工業(yè)大學計算機科學與技術學院，安徽馬鞍山 243032)

?

基于CAR動態(tài)調(diào)整的改進LRFU算法
——CLRFU

王小林，還璋武

(安徽工業(yè)大學計算機科學與技術學院，安徽馬鞍山 243032)

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

[關鍵詞]LRFU；CAR；動態(tài)調(diào)整；CLRFU

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

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

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

1相關算法

1.1LRU算法

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

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

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

當訪問對象在b1中時，這個跡象表明t1表小了，自適應調(diào)整鏈表t1的大小，

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

(1)

當訪問對象在b2中時，這個跡象表明t2表小了，自適應調(diào)整鏈表t2的大小，

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

(2)

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

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

1.3LRFU算法及其自適應算法

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

LRFU算法通過權值函數(shù)計算出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策略，但在強局部訪問模式下顯然這樣的策略表現(xiàn)非常差。

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

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

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

(5)

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

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

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

2CLRFU算法

仿真程序實現(xiàn)時，記錄該對象上次訪問的時間lastintime，權重信息CRF值和標志位flag值。程序將初始化緩存隊列T和His。T的大小和His大小相等，T存放緩沖區(qū)的數(shù)據(jù)，t1和t2分別對應flag為1和大于1的對象序列，His存放最近從T中淘汰出的數(shù)據(jù)，b1和b2分別對應flag為1和大于1的對象序列。

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

圖2　CLRFU流程圖

緩存整理子模塊流程如圖3所示，當λ[-1,0)，除去T中CRF值最大的對象，當λ=0，CLRFU借助CAR中緩存對象數(shù)據(jù)結構中Flag標志位，除去Flag中最小的，如果有多個去除CRF值最小的對象到His，當λ∈(0,1]，CLRFU借助CAR動態(tài)調(diào)整思想移除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開發(fā)環(huán)境開發(fā)仿真程序。我們將CLRFU和LRFU、p-LRFU以及LALRFU算法進行性能比較。LALRFU和p-LRFU算法根據(jù)文獻中的描述設置參數(shù)，CLRFU算法中λ初始化為0.001，而LRFU中λ用1e-03和3e-03來做實驗。

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

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

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

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

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

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

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

圖5　強局部性訪問模式下LRFU及其自適應算法的命中率比較

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

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

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

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

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

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

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

4結語

本文結合了CAR動態(tài)調(diào)整思想，并在文獻[7]提出的局部性定量分析模型的基礎上，分析不同訪問模式所帶來的α值的變化規(guī)律來動態(tài)調(diào)整λ的大小，這種改進算法使得緩存命中率普遍提高的同時并沒有帶來實現(xiàn)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- )，男，碩士生導師，教授，從事關鍵字分析研究。

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

[收稿日期]2015-12-30