一種基于時鐘自適應(yīng)的改進(jìn)緩存替換算法*

魏文國，趙慧民，莊林凱，許鴻俊

(廣東技術(shù)師范學(xué)院電子與信息學(xué)院,廣東 廣州 510665)

1 研究背景分析

緩存算法是存儲系統(tǒng)、數(shù)據(jù)庫、Web服務(wù)器等計算機(jī)領(lǐng)域的核心技術(shù)之一[1-5]，幾種經(jīng)典的緩存頁面替代算法LRU、CLOCK、ARC和CAR各有優(yōu)缺點[6]，其中LRU是代替最近最少使用的頁面的算法[7-8]，Oracle數(shù)據(jù)庫使用該算法管理緩存。LRU 實現(xiàn)極其簡單，具有常數(shù)的時間和空間復(fù)雜度，能捕捉很多工作負(fù)載的“最近期”特性。但是LRU 有4個很明顯的缺點：

1)用進(jìn)程鎖去保證數(shù)據(jù)正確和統(tǒng)一，這是在高性能、高吞吐量環(huán)境下所不能接受的，如虛擬緩存管理、數(shù)據(jù)庫和文件系統(tǒng)。

2)在每次命中緩存時，它必須移動到最多最近使用(MRU)的位置。在異步計算環(huán)境下，多個線程都試圖將頁面移動到 MRU位置是不可接受的。

3)LRU 捕捉工作負(fù)載的“最近期”特性，但是沒有捕捉“頻率”特性。

4)LRU 容易被內(nèi)存掃描影響，即一系列一次使用的頁面導(dǎo)致系統(tǒng)的低性能。

CLOCK緩存算法是LRU的一種單位元量近似實現(xiàn)[9-10]，它在每個頁面包含“單位引用次數(shù)”，當(dāng)頁面第一次被插入緩存時，引用次數(shù)將設(shè)為0。頁面在緩存里以一個鐘的形式循環(huán)存放，當(dāng)緩存命中時，頁面的引用次數(shù)設(shè)為1。鐘的指針用來替代緩存，當(dāng)緩存容量滿了的時候，指針會從起始位置開始掃描整個緩存，當(dāng)指針指向引用次數(shù)為1的頁面時，會將引用次數(shù)設(shè)為0，如果指向引用次數(shù)為0的頁面，則將此頁面替換出緩存。CLOCK解決了LRU的缺點1和缺點2，它完全去除了進(jìn)程鎖，這樣使得緩存算法能更快地進(jìn)行緩存的插入和清理，大大提高了緩存工作的效率。 CLOCK算法第一次提出page reference bit，每次緩存命中后只需將頁面引用次數(shù)設(shè)為1，不用像LRU一樣每次緩存命中都將頁面轉(zhuǎn)移到MRU位置。但是缺點3和4導(dǎo)致CLOCK算法的實際命中率比LRU并沒有明顯的提高。這是因為兩種算法都只捕捉“近期使用”的特性，而不能捕捉“頻率”特性，導(dǎo)致了此類算法及其變體的命中率并沒有實質(zhì)性的提高。

2003年，IBM研究中心的Nimrod Megiddo等人[11]提出了ARC算法如圖1所示，該算法創(chuàng)造性地運(yùn)用四條LRU鏈：T1，T2，B1和B2分別捕捉近期和頻率特性。T1、T2存放緩存中的數(shù)據(jù)，B1、B2的數(shù)據(jù)并不放在緩存中。T1管理近期使用頁面，T2管理多次使用的頁面，B1、B2則分別接收從T1、T2淘汰的頁面并進(jìn)行后續(xù)管理。ARC算法將多次命中的頁面從T1轉(zhuǎn)移到有關(guān)頻率的T2中，使得緩存能同時管理“近期”和“頻率”兩個重要的特性。ARC解決了缺點3和缺點4，將高頻使用的頁面與最近使用頁面分開管理，從而捕捉到高頻使用的頁面并進(jìn)行區(qū)分管理。同時也避免了在一次一系列瀏覽后，緩存頁面被全部破壞的問題。這兩點使得ARC緩存算法相對于LRU，CLOCK等類似的緩存算法在命中率方面有很明顯的提高，ARC思想的提出對當(dāng)代緩存算法有十分重要的意義，后面涌現(xiàn)出眾多類似的改良算法都基于此算法。ARC算法雖然解決了缺點3和缺點4，但是該算法的實現(xiàn)完全基于LRU算法，從而暴露出LRU幾個嚴(yán)重的缺陷，其中上面所闡述的缺點1和2就是很關(guān)鍵的兩點，LRU自身的缺點導(dǎo)致了ARC在緩存替代效率上還有提高的空間。

圖1 ARC緩存管理算法數(shù)據(jù)結(jié)構(gòu)示意圖

IBM研究中心的Dharmendra Modha[12-13]不久又提出了一種改良ARC的緩存算法CAR：Clock with Adaptive Replacement。CAR緩存算法是當(dāng)前較經(jīng)典的幾個緩存算法之一，運(yùn)用廣泛。CAR將ARC與CLOCK結(jié)合，同時解決了LRU的4個缺點，T1，T2用CLOCK算法實現(xiàn)，B1，B2用LRU實現(xiàn)。能同時捕捉“近期”和“頻率”兩個特性，并完全解決了LRU算法的缺陷。

雖然CAR對緩存算法進(jìn)行了較充分的改良，但是它并不能很完善地捕捉緩存使用的“頻率”特性。我們在文獻(xiàn)[14]中提出了對緩存頁面的“頻率”特性進(jìn)行更加精細(xì)化管理的緩存管理算法GCAR，該算法在集群協(xié)作緩存環(huán)境下被驗證能取得更好的緩存命中率，本文在此基礎(chǔ)上進(jìn)行改進(jìn)，改變GCAR算法的部分流程，并在3種典型的概率分布(例如隨機(jī)分布、泊松分布和正態(tài)分布)的讀請求進(jìn)入緩存的情況下進(jìn)行對比測試，都能取得更好的緩存命中率，證明該ICAR緩存管理算法的適用性更好。本文還研究基于時鐘自適應(yīng)的改進(jìn)緩存替換算法ICAR的思想與流程；在3種典型的概率分布(例如隨機(jī)分布、泊松分布和正態(tài)分布)的讀請求進(jìn)入緩存的情況下進(jìn)行對比測試LRU、CAR和ICAR的緩存命中率；最后給出結(jié)論和闡述將來的工作。

2 基于時鐘自適應(yīng)的改進(jìn)緩存替換算法ICAR

通過對CAR算法以及經(jīng)典緩存算法的研究，我們發(fā)現(xiàn)：CAR用于捕捉頻率特性的CLOCK T2并不能很完善地捕捉“頻率”特性。雖然多次使用的數(shù)據(jù)會從T1傳遞到T2并進(jìn)行分開管理，但是CLOCK T2里的引用次數(shù)只是0或1。這樣導(dǎo)致即使該數(shù)據(jù)塊經(jīng)過了多次訪問，但是它的引用次數(shù)依然只是1。當(dāng)緩存進(jìn)行替代操作的時候，多次訪問的數(shù)據(jù)塊與少量訪問的數(shù)據(jù)塊在T2中引用次數(shù)都為1，導(dǎo)致兩者被清理出緩存的幾率相同。所以，CAR算法只能粗線條地對T2數(shù)據(jù)進(jìn)行管理，并不能很精確地捕捉數(shù)據(jù)“頻率”特性。

針對CAR不能精確捕捉數(shù)據(jù)塊“頻率”特性的缺陷，我們試圖改變CLOCK的數(shù)據(jù)結(jié)構(gòu)，使CLOCK的引用次數(shù)不局限于0和1，當(dāng)每次緩存命中的時候我們將引用次數(shù)進(jìn)行“加1”處理。這樣可以使CLOCK T2能對“頻率”特性進(jìn)行更精確地管理。通過對CLOCK算法的改變，并對CAR算法的適應(yīng)性調(diào)整，我們提出ICAR緩存算法，其流程如圖2所示。與ARC和CAR算法類似，同樣T1和T2采用CLOCK類型的緩存數(shù)據(jù)結(jié)構(gòu)，他們包含了緩存里的所有數(shù)據(jù)。B1和B2只是簡單的LRU列表的實現(xiàn)，包含那些近期從緩存淘汰出的數(shù)據(jù)。

CLOCK T1捕捉“近期”的頁面，并且T1是按照緩存頁面使用由新到舊排序頭進(jìn)尾出的循環(huán)鏈表；CLOCK T2則捕捉“長期”的頁面(即被頻繁訪問的頁面)，即T2是頭進(jìn)尾出的循環(huán)鏈表。從T1淘汰的數(shù)據(jù)進(jìn)入B1，即B1是按照頁面使用由新到舊排序頭進(jìn)尾出的循環(huán)鏈表。從T2淘汰的數(shù)據(jù)進(jìn)入B2，即B2也是頭進(jìn)尾出的循環(huán)鏈表，B1、B2的數(shù)據(jù)不存放在緩存中。算法限制|T1|+|T2|的大小不超過緩存容量c，將B1的大小限制與T2大小一致，B2與T1大小一致。其中T1和T2的大小此消彼長，并且由自適應(yīng)變量p調(diào)節(jié)：當(dāng)B1內(nèi)的數(shù)據(jù)命中時，T1的大小將增加1；反之，當(dāng)B2內(nèi)的數(shù)據(jù)命中時，T1的大小將減小1。

當(dāng)緩存未命中時，新的數(shù)據(jù)將被插入至T1，同時引用次數(shù)將被設(shè)為0。當(dāng)緩存命中任何在T1或T2的數(shù)據(jù)時，引用次數(shù)都將+1。

“整理緩存”子模塊的流程如圖3所示，緩存清理時，CLOCK T1的指針從尾部移動到頭部。當(dāng)CLOCK T1指針指向的頁面引用次數(shù)為0時，頁面將清理到B1的MRU(最近使用)位置，當(dāng)引用次數(shù)為不為0時，頁面將插入至CLOCK T2的頭部并使指針指向下一個頁面；當(dāng)CLOCK T2指針指向的頁面引用次數(shù)為0或1時，頁面將清理到B2的MRU位置，當(dāng)引用次數(shù)大于1時，將頁面引用次數(shù)-1并移動至CLOCK T2的頭部并使指針指向下一個頁面。

圖2 緩存替換算法ICAR流程圖

圖3 ICAR子模塊“整理緩存”流程圖

3 仿真實驗與測試結(jié)果

實驗環(huán)境與條件：不失一般性假設(shè)，緩存容量為1 024個頁面；主要測試讀請求到達(dá)的時間服從隨機(jī)分布、泊松分布和正態(tài)分布等三種代表性的情況；若讀請求太大，超過緩存容量的一定比例之后，命中緩存的幾率很低，研究的意義不大，所以假設(shè)每次讀請求的大小在[1,20]之間隨機(jī)產(chǎn)生。使用Java語言開發(fā)仿真程序，模擬三種緩存管理算法：LRU、CAR和ICAR在讀請求按照上述概率分布到達(dá)時的緩存命中率。

第一組實驗在讀請求以隨機(jī)分布到達(dá)時對比測試LRU、CAR和ICAR三種緩存管理算法的緩存命中率如圖4所示。請求大小在[1,20]中隨機(jī)產(chǎn)生，即讀請求的平均大小為10。緩存容量為1 024，表示緩存大約能夠容納(1 024 /100)約100個請求。當(dāng)概率模型為隨機(jī)分布時，讀請求進(jìn)入緩存的概率沒有明顯的高低之分，沒有固定的高頻頁面，難以捕捉頻率的特性，所以三種緩存算法的命中率都近似相同，當(dāng)不同讀請求的個數(shù)較少(例如圖4最右邊的只有128個不同讀請求的測試案例)，能夠在一定程度反映讀請求的“頻率”特性時，ICAR的緩存命中率較其他兩種略高。

圖4 讀請求按照隨機(jī)分布到達(dá)的緩存命中率對比

第二組實驗在讀請求以正態(tài)分布到達(dá)時對比測試LRU、CAR和ICAR三種緩存管理算法的緩存命中率如圖5所示。高頻率的讀請求會更長時間停留在緩存中，結(jié)果表明：當(dāng)命中率較低時(低于30%)，頁面“頻率”的特性難以捕捉，ICAR的命中率與CAR命中率近似，但比LRU命中率高；當(dāng)命中率適中時(高于30%且低于80%)，頁面“頻率”特性體現(xiàn)得較為明顯，ICAR較CAR命中率有比較明顯的增加，平均增幅約為12.5%；當(dāng)命中率較高時(高于80%)，CAR與ICAR兩者緩存命中率相對于LRU都有非常明顯的提高，但I(xiàn)CAR與CAR命中率幾乎相同，因為“高頻率”頁面長期駐留緩存，不能體現(xiàn)差異。

圖5 讀請求按照正態(tài)分布到達(dá)的緩存命中率對比

第三組實驗在讀請求以泊松分布到達(dá)時對比測試LRU、CAR和ICAR三種緩存管理算法的緩存命中率。測試結(jié)果與正態(tài)分布有相似的規(guī)律。

4 總結(jié)與展望

本文比較和分析了4種經(jīng)典的緩存管理算法LRU、CLOCK、ARC和CAR，提出基于時鐘自適應(yīng)的改進(jìn)緩存替換算法ICAR，仿真實驗驗證該算法在大多數(shù)情況下能取得更高的緩存命中率。文獻(xiàn)[14]中提出的GCAR緩存管理算法對集群協(xié)作緩存能取得較好的緩存命中率，本文的改進(jìn)在于ICAR的適用性更好。進(jìn)一步的研究可在緩存命中率相當(dāng)高(高于80%)或者比較低(低于30%)的情況下改進(jìn)和優(yōu)化ICAR算法。

參考文獻(xiàn)：

[1] CHRIS G,ALI R, BUTT Y, et al. Program-counter-based pattern classification in buffer caching[C]∥ 6th Symposium on Operating Systems Design and Implementation,2004:321-349.

[2] ALI R. The performance impact of kernel prefetching on buffer cache replacement algorithms[C]∥ Proceedings of the 2005 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems,2005:157-168.

[3] JEONG J.Simple penalty-sensitive cache replacement policies[J]. Journal of Instruction-Level Parallelism,2008,10:1-24.

[4] 王欣，周南，邱小彬.JCS數(shù)據(jù)緩存技術(shù)在動態(tài)Web系統(tǒng)中的應(yīng)用[J].中山大學(xué)學(xué)報:自然科學(xué)版, 2009(S1)：356-357.

[5] 陳華竣，鄭智，倪德明.一種面向分層訪問的目錄結(jié)構(gòu)在RDBMS中的存儲方法[J].中山大學(xué)學(xué)報:自然科學(xué)版， 2005(S1)：138-141.

[6] BANSAL S, MCKENNEY P E , MODHA D S. Apparatus and system for dynamically allocating main memory among a plurality of applications: US Patent,7 487 320[P].2009-02-03.

[7] LEE D, CHOI J, KIM J, et al. On the existence of a spectrum of policies that subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU)policies[C]∥Proceeding of 1999 ACM Sigmetrics Conference, 1999: 134 - 143

[8] LI Zhansheng.CRFP: A novel adaptive replacement policy combined the LRU and LFU policies[C]∥ IEEE 8th International Conference on Computer and Information Technology,2008:72-79.

[9] BANSAL S. Method and system of clock with adaptive cache replacement and temporal filtering:US Patent App,10/955 201[P]. 2006.

[10] JIANG S,CHEN F,ZHANG X. CLOCK-Pro: an effective improvement of the CLOCK replacement[C]∥ Proc of USENIX ′05,2005:121-130.

[11] MEGIDDO N,MODHA D. ARC: a self-tuning, low overhead replacement cache[C]∥ Proceedings of the 2nd USENIX Symposium on File and Storage Technologies,2003:115-130.

[12] BANSAL S,MODHA D.CAR: clock with adaptive replacement[C]∥ Proceedings of the 3nd USENIX Symposium on File and Storage Technologies, 2004:203-215

[13] SHAMSHEER S M.A throughput analysis on page replacement algorithms in cache memory management[J]. International Journal of Engineering Research and Applications,2012,2(2):126-130.

[14] 魏文國，陳潮填，閆俊虎.集群協(xié)作緩存機(jī)制研究[J].計算機(jī)科學(xué)，2008 (1)：282-284.