Cache替換算法LRU和2Q的深度分析

張恒瑞，王紅

（遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，葫蘆島 125105）

Cache替換算法LRU和2Q的深度分析

張恒瑞，王紅

（遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，葫蘆島 125105）

Cache替換算法是內(nèi)存和CPU交互時(shí)速度保證的關(guān)鍵，傳統(tǒng)的LRU算法在處理偶然性數(shù)據(jù)訪問時(shí)造成緩存污染嚴(yán)重，但其實(shí)現(xiàn)簡(jiǎn)單，命中率和效率尚可，故成為現(xiàn)今大多情況下使用的算法；2Q算法通過設(shè)置兩個(gè)隊(duì)列，A1隊(duì)列通過暫存數(shù)據(jù)減弱偶發(fā)性數(shù)據(jù)的影響，實(shí)現(xiàn)同樣簡(jiǎn)單且有不錯(cuò)的性能。通過編制的詞法分析器分析程序代碼得來的數(shù)據(jù)進(jìn)行算法性能的比較。

Cache替換算法；LRU；2Q；命中率；性能

0 引言

Cache作為一種媒介大大提升了CPU和內(nèi)存的訪問速度，為了增加Cache的訪問命中率，替換策略的選取大為重要，如今的替換策略大都以程序的局部性原理作為理論基礎(chǔ)，分別從時(shí)間局部性和空間局部性作為著眼點(diǎn)，闡釋不一樣的替換算法。LRU作為經(jīng)典的替換策略，實(shí)現(xiàn)簡(jiǎn)單，但對(duì)于特定的數(shù)據(jù)有很大的缺陷，2Q算法從某種程度上緩解了緩存污染，但是將一個(gè)隊(duì)列變成兩個(gè)隊(duì)列勢(shì)必會(huì)影響性能，如何平衡這兩者的關(guān)系成為重點(diǎn)。

1 問題抽象

將對(duì)Cache的操作簡(jiǎn)化為get和set操作，get（key）表示通過其緩存地址key得到內(nèi)容value，未命中count++，增加鍵值對(duì)（key，value）表示入緩存，緩存滿時(shí)按策略刪除，set（key，value），若key存在則修改對(duì)應(yīng)緩存中value值，若不存在則增加鍵值對(duì)（key，value）表示入緩存，count，緩存滿時(shí)按策略刪除，可以通過其count值判斷其命中情況，運(yùn)行時(shí)間來比較其效率。

2 LRU

2.1 LRU原理

LRU，最近最少使用算法，從時(shí)間局部性著手，如果數(shù)據(jù)在最近被訪問，將來也很有可能訪問，基本的思想是建立一個(gè)鏈表，當(dāng)訪問命中時(shí)，將節(jié)點(diǎn)插入鏈表頭部，當(dāng)鏈表達(dá)到長(zhǎng)度限制時(shí)刪除鏈表尾節(jié)點(diǎn)。

上述過程在查找訪問過程和刪除尾節(jié)點(diǎn)處復(fù)雜度達(dá)到了O（n）[1]，鏈表的好處在于插入刪除的復(fù)雜度為O（1）,而在訪問節(jié)點(diǎn)處復(fù)雜度高達(dá)O（n），訪問檢索處的復(fù)雜度可以通過紅黑樹或hash表予以優(yōu)化，而普通的單鏈表在刪除某節(jié)點(diǎn)時(shí)需要知道上一個(gè)節(jié)點(diǎn)，當(dāng)檢索到當(dāng)前節(jié)點(diǎn)后，還需從頭訪問到上一個(gè)節(jié)點(diǎn)才能刪除該節(jié)點(diǎn)，同時(shí)最后一個(gè)節(jié)點(diǎn)的刪除也需要從頭訪問，時(shí)間復(fù)雜度為O（n），故采用雙向鏈表[2]，插入和刪除的復(fù)雜度都為O（1）。

2.2 具體實(shí)現(xiàn)

因?yàn)殛P(guān)于Cache替換中內(nèi)存也占有很大地位，而hash占有較大的空間復(fù)雜度，所以運(yùn)用紅黑樹作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，C++的標(biāo)準(zhǔn)庫Map實(shí)現(xiàn)了紅黑樹，list實(shí)現(xiàn)了雙向鏈表，總的時(shí)間復(fù)雜度為O（logn），去除Map的定位功能，對(duì)鏈表的插入刪除僅需O（1），以下的代碼為了精簡(jiǎn)，使用了map和list的stl庫。

2.3 分析

LRU算法實(shí)現(xiàn)簡(jiǎn)單，效率也不錯(cuò)，但面對(duì)偶發(fā)性的訪問數(shù)據(jù)無力，造成緩存污染嚴(yán)重。假設(shè)緩存容量為100，操作序列為1-101循環(huán)訪問，若采用LRU算法，當(dāng)訪問101時(shí)會(huì)將1刪除，之后每次訪問都會(huì)將下次訪問數(shù)據(jù)從緩存刪除，命中率大大降低。

32 Q算法

3.1 基本原理

2Q算法緩解了LRU對(duì)弱空間局限性的無力，在2Q算法里，有兩個(gè)隊(duì)列A1和A2[3]，A1為FIFO隊(duì)列，A2為L(zhǎng)RU隊(duì)列，若數(shù)據(jù)在A1和A2中都沒命中，將數(shù)據(jù)插入A1隊(duì)列尾部，若A1滿，A1頭部出隊(duì)，當(dāng)數(shù)據(jù)在A1命中時(shí)，將其刪除，并將數(shù)據(jù)插入A2尾部，A2滿時(shí)將A2頭部出隊(duì)。

3.2 具體實(shí)現(xiàn)

程序中對(duì)A1和A2隊(duì)列采用list雙向鏈表，并采用map進(jìn)行訪問檢索，保證插入刪除時(shí)的復(fù)雜度為O（1）,對(duì)key先在A2進(jìn)行map訪問檢查，若未命中檢查A1，若命中執(zhí)行l(wèi)ist刪除操作，并將數(shù)據(jù)插入A2，代表數(shù)據(jù)入Cache，為hot數(shù)據(jù)，避免LRU中一次訪問就入Cache造成偶發(fā)性數(shù)據(jù)污染緩存，若在A1未命中，將數(shù)據(jù)以FIFO的形式入A1。

3.3 分析

以上為簡(jiǎn)化的2Q操作，在簡(jiǎn)化操作中，A1和A2所占比例是問題的關(guān)鍵，A1比例大時(shí)，緩存容量變少，命中率降低，而A1比例小時(shí)，找出數(shù)據(jù)人緩存的時(shí)間變長(zhǎng)，如何平衡好A1和A2所占比例是問題的關(guān)鍵[4]。如圖1所示，比較下LRU和2Q在緩存為3000，200000次隨機(jī)數(shù)測(cè)試下的運(yùn)行效率和命中率可以發(fā)現(xiàn)2Q的運(yùn)行效率明顯較好。

仔細(xì)看后，發(fā)現(xiàn)兩種算法的未命中次數(shù)都顯得很高，原因在于測(cè)試選用的是隨機(jī)數(shù)進(jìn)行的，在隨機(jī)數(shù)模式下，程序的局部性原理便不再起作用，替換算法之間的差距也變小了，如何進(jìn)行有效果且具有一定的規(guī)模的數(shù)據(jù)測(cè)試呢。下面決定采用編寫的簡(jiǎn)易詞法分析器對(duì)大量程序分析后得到的數(shù)據(jù)結(jié)果作為替換算法的測(cè)試數(shù)據(jù)。運(yùn)用詞法分析器對(duì)超過7000行的代碼進(jìn)行分析得到50000余條數(shù)據(jù)，作為替換算法的輸入文件進(jìn)行運(yùn)算，在數(shù)據(jù)范圍在1000以內(nèi)，緩存容量為300得到如圖2結(jié)果。

圖1 LRU和2Q比較結(jié)果

圖2 三種算法比較結(jié)果

結(jié)果中可看出最簡(jiǎn)單的FIFO算法命中次數(shù)最差，在實(shí)際的情況下多次訪問主存會(huì)造成時(shí)間效率差，相對(duì)的LRU和2Q算法命中次數(shù)較好，雖然運(yùn)行時(shí)間稍長(zhǎng)于FIFO，在較少的訪問主存下會(huì)使總的時(shí)間效率大大提升，在大多實(shí)際情況下，LRU算法運(yùn)行效率尚可，在大量偶發(fā)性數(shù)據(jù)下，可以采用2Q算法予以改進(jìn)。

[1]海子.LRU Cache.[2014-5-23].http://www.cnblogs.com/dolphin0520/p/3741519.html.

[2]黃賢明.基于LRU改進(jìn)算法的實(shí)時(shí)數(shù)據(jù)庫緩存機(jī)制[J].工業(yè)控制計(jì)算機(jī)，2015（12）：63-64.

[3]flychao88.緩存淘汰算法-LRU算法.[2013-11-20].http://flychao88.iteye.com/blog/1977653.

[4]Linux Memory.Cache替換算法之：2Q.[2015-5-20].http://www.jianshu.com/p/4f3ca27300c2.

Depth Analysis of LRU and 2Q on Cache Replacement Algorithm

ZHANG Heng-rui，WANG Hong

（School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105）

Cache replacement algorithm is the key to ensure the speed of memory and CPU interaction,the traditional LRU algorithm in dealing with accidental data access caused by cache pollution,but its implementation is simple and the hit rate and efficiency can be used now,in most cases the algorithm,the 2Q algorithm by setting two queue,queue A1 reduces the influence of sporadic data through the temporary storage of data,to achieve the same performance is simple and has good,through the use of lexical analyzer analysis program code to compare the performance of the data algorithm.

Cache Replacement Algorithm;LRU;2Q；Hit Rate;Performance

1007-1423（2017）04-0017-03

10.3969/j.issn.1007-1423.2017.04.014

王紅（1979-），女，遼寧莊河人，講師,碩士研究生，研究方向?yàn)橛?jì)算機(jī)系統(tǒng)結(jié)構(gòu)、計(jì)算機(jī)控制及應(yīng)用

2016-12-07

2017-01-20

張恒瑞（1996-），男，本科生