基于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等多個平臺使用，需要去適應不同的復雜的應用環境。傳統的單級緩存算法已無法適用于越來越復雜的應用環境，所以研究熱點已轉向能夠自適應的單級緩存替換算法和提升多級緩存的整體性能。

關于單級緩存的自適應替換算法的研究多集中于基于探測的策略、基于特殊應用的策略、基于時間和頻率平衡的策略。然而，最普遍的訪問特征仍然是局部性和頻率性的體現，因而基于時間和頻率平衡策略的算法具有更好的適用性?，F有基于訪問時間和訪問次數的替換算法如MQ算法、ARC[1]算法(IBM緩存算法)、CAR[2-3]算法、LIRS[4]算法(Mysql緩存算法)、LRFU自適應算法等都有效提升了緩存整體效率。傳統的LRFU[5]算法兼顧訪問時間和訪問次數，卻對局部性特征和頻率性特征缺少量化分析，每個對象權重函數CRF(Combined Recency and Frequency)中的λ是固定的，參數的調整很多時候是基于經驗，無法以合適的CRF來平衡兩種不同的訪問模式，甚至很多時候性能比LRU和LFU還要差，從而不能很好地應用到實際環境?；贚RFU算法改良的自適應算法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