一種自適應分類重用距離來捕捉熱數據的緩存算法

艾 亮，鄧玉輝,2

1(暨南大學 信息學院計算機科學系，廣州 510632)2(中國科學院計算技術研究所 計算機體系結構國家重點實驗室，北京100190)

1 引 言

緩存技術不僅僅局限于高速緩存，自現代計算機系統提出存儲器層次結構以后，CPU寄存器集合，高速緩存，主存，SSD和HDD存儲設備，甚至分布式文件系統等遠程二級存儲設備，都可以理解為是作為下一層的更大更慢的存儲設備的緩存而存在，因此凡是存儲設備自身都存在著緩存問題.而緩存替換算法作為緩存技術研究的核心部分，它的研究與計算機存儲系統、操作系統[3]、文件系統[4]、數據庫[5]、web服務器[6]、甚至包括各種其它應用技術如冷熱數據識別[7]和數據壓縮[8]等問題的研究有著直接相關的聯系.

傳統的緩存替換算法的設計原理主要是利用了高速緩存的局部性原理(即是程序具有訪問局部區域里的數據和代碼的趨勢)和數據訪問的頻率.局部性原理不僅僅是高速緩存通過保存最近被引用的指令和數據的方式來提高對主存訪問速度的有效手段,而且在其它存儲設備如web瀏覽器和SSD設備中也扮演者重要的角色.而另一個重要的指標頻率則更具有統計意味的成份，它不僅僅能客觀評價一個數據的真實熱度，而且也能彌補僅僅參考時間局部性而引起的緩存污染問題.

然而僅僅利用數據所反映的新進度或頻率這兩個特性來設計的算法，如LRU、LFU 、2Q[9]和MQ[10]算法等,雖然具有簡單易實現、應用廣泛等特點，但是首先僅僅考慮新進度或頻率這兩個指標無法全面反映數據訪問的模式特征；其次數據訪問的模式是動態的，因此算法不具備有針對捕捉到的數據特征變化而做出自適應調節的能力；最后上述所提出的針對這兩個特性的算法改進方法已經趨向于成熟(LRU算法在80年代初開始已經被廣泛使用)，因此很難有比較大的突破.

因此現在比較優秀的緩存替換算法如LIRS[11]、ARC[12]和CAR[14]算法等，如LIRS算法會通過利用數據的重用距離特征來預測數據未來的訪問順序；ARC算法則具備有自適應性，算法能根據數據訪問模式的變化對算法做自身的調整等.然而盡管這些優秀的算法存在諸多的優點，但是也會存在有例如不能捕捉大于緩存的熱數據和緩存污染等問題，關于這部分細節將在2.2中進行著重敘述.

針對這些問題，本文提出了一種自適應分類重用距離來捕捉熱數據的緩存算法(ACRD).算法基于新進度、頻率和重用距離三個數據特征來進行捕捉熱數據，其中新進度和頻率作為數據分類為潛在熱數據和熱數據的指標，而重用距離大小作為數據緩存時間分配的依據.因此緩存中存在四種類型不同的數據，即不同重用距離的潛在熱數據和不同重用距離的熱數據，算法將長重用距離潛在熱數據以元數據的方式保存，并且通過設置上限值的方式壓縮短重用距離潛在熱數據區域的大小(這其中的必要性，在實驗4.2中可以看出)，以此來加大熱數據存儲空間和提高緩存命中率的目的.同時由于數據集的訪問特征是復雜并且多變的，算法采用自適應的方式通過利用緩存替換的元數據歷史信息來進行上述這種動態地熱數據識別和緩存時間分配的過程.因此算法不僅有效吸收了LIRS和ARC等算法的優點，并能夠比較好地解決上面提出的問題.

2 背景知識

2.1 重用距離

緩存算法設計和改進的根本是基于數據集訪問模式的特征，為了提高命中率和深度挖掘出數據的訪問特征，一方面算法要獲得更多的可利用信息，另一方面在時間和空間開銷限制信息獲取的條件下，算法必須提高這些有限信息的利用深度，挖掘出更加能表征出TRACE信息特征的指標.傳統的數據訪問信息參考指標主要是新進度和頻率，在本文中，算法除了利用這2個指標之外，還主要利用重用距離這一重要指標作為算法分類數據類型捕捉熱點數據和分配熱點數據緩存駐留時間的重要依據.

圖1 一個重用距離的例子Fig.1 Example of reuse distance

重用距離(Reuse distance,簡稱RD)是指對同一內存數據的相鄰兩次訪問之間所間隔的不重復數據的個數.當前訪問到下次訪問的重用距離成為前向重用距離，當前訪問到上次訪問之間的重用距離稱為后向重用距離.通常重用距離指代的是前向距離，并且此時數據第1次訪問的重用距離為無窮大.如圖1所示，由上述定義可知，A，B和C的重用距離分別是3，0和1.

重用距離在LRU-K[13]算法中用來衡量訪問數據的未來訪問時間；在LIRS算法中，算法通過比較數據之間的重用距離來決定各數據在緩存中的位置，從而決定替換順序.

2.2 LRU、LIRS和ARC算法

LRU算法是目前應用最廣泛的算法，在現有系統中，基本上采用的都是LRU算法或者類LRU算法，并且后續的大多數算法如LRU-K,2Q,MQ等緩存算法也都是基于此做出的改進.然而LRU算法也存在這比較明顯的缺點：

1) 所有數據的時間分配都是均等制，盡管對于再次訪問的數據,LRU算法會將其置于隊列前端，但是這個數據的駐留時間和普通新數據是一樣的，因此很容易帶來緩存污染的問題，即當發生一次掃描應用時，LRU緩存中大量的熱數據會被沖刷掉.

2) LRU算法無法捕捉大于緩存的數據，由于LRU算法只有一個緩存隊列，因此緩存中的數據在緩存中最大的駐留時間即是緩存大小，當一個再次訪問的數據的重用距離大于緩存時，LRU是無法感知到這個數據是否已經被訪問過的，這也是為什么LRU在大于緩存的循環TRACE中的命中率為0的原因.這個限制其實存在于很多的算法之中，從而導致算法都無法識別出重用距離比較大的數據的訪問特征.

3) LRU算法無法準確識別出TRACE中數據反映的特性，這與它僅僅考慮數據最近的會再次被訪問的概率高這一個設計原則有關，這也導致LRU算法無法捕獲訪問頻率高的熱數據，也無法區分出不同訪問概率的頁面.

LIRS和ARC算法皆是目前比較優秀的算法之一.LIRS算法的基本原理是保留數據中重用距離小的數據，替換掉重用距離大的數據，因為重用距離小的數據在未來更有可能被訪問.LIRS算法不具備LRU算法中的1和2的缺點，因為LIRS的HIRS棧可以充當二級緩存，并且LIRS算法的HIRS棧只占緩存大小的1%，這說明LIRS的HIRS堆棧僅僅是作為一個算法輸入輸出流動棧，數據塊的二次命中主要是通過元數據命中的方式，因此數據具備有捕捉各種RD長度數據塊的能力.然而缺點也很明顯，假如一個非熱塊在很短的時間內被訪問了2次，那么該數據塊只會經歷了99%的數據之后，才會被替換掉.因此LIRS算法不具備抵抗重用距離小的但是短時連續訪問幾次的數據塊的污染.

ARC算法也是基于新進度和頻率這兩個指標設計的算法，但是算法之所有超越一般此類算法的性能，是因為算法的設計上具備有自適應性.算法保存了最近從緩存中替換出去的歷史信息，并通過歷史信息的命中情況判斷出當前負載的特性，然后設計了一個自適應的調整參數p，這個參數與負載情況有直接聯系，因此借助該參數算法可以了解緩存當前的訪問情況，并對緩存大小做出及時相應的調整.但是缺點是算法無法解決上面LRU中的捕捉重用距離大的熱數據問題，對于弱局部性訪問模式，物理緩存經常存滿最近讀取一次的數據，此時在ARC算法中，新讀取的數據可能會輕易地將最近讀取一次的數據不經保護就直接移出緩存.

3 ACRD算法

3.1 算法的基本思想

算法從解決兩個問題入手設計，即如何分類不同的數據特征和如何分配不同類型的數據在緩存中的貯存時間，因此算法分成兩個維度來設計.第一個維度算法是依照新進度和頻率這兩個指標將訪問數據按照熱度分為兩類，其中最近訪問一次的數據被視為是潛在的熱數據，最近訪問次數大于或等于2次的數據代表是熱數據.另外熱數據的熱度是有時間性的，并且潛在熱數據和熱數據保存時間也是不同的，因此第二個維度算法依照重用距離這一指標將數據分成長重用距離數據和短重用距離數據.根據這一數據類型分類，雖然訪問兩次的數據就成為熱數據，但是該數據的緩存駐留時間卻由它的重用距離長短以及接下來是否繼續被訪問來決定，這樣就減少了熱數據可能污染緩存的危險.

接下來如何分配不同的重用距離和不同的熱度數據的緩存大小成了目前的關鍵問題.算法借鑒了ARC算法的自適應手段，并在之上做出改進，使得算法能夠動態地識別不同類型的數據特征和處理這些數據緩存時間分配問題.關于這一部分的細節將在3.3節中進行詳細描述.

3.2 算法框架

算法的設計框架如圖2所示.整個緩存分成R,S和L三個區域，有實際緩存(Real Cache)和幽靈緩存(Ghost Cache)兩種類型的緩存，實際緩存存儲真實數據和元數據，幽靈緩存

圖2 ACRD算法結構圖Fig.2 ACRD algorithm structure diagram

則僅僅存儲元數據.第一個區域R存儲最近訪問一次的數據，然后按照重用距離大小分為短重用距離棧R1和長重距離棧R2，其中R1為實際緩存，R2為幽靈緩存.第二個區域S和第三區域L都是存儲最近訪問次數大于或等于2次的數據，但是S存儲的是短重用距離熱數據，L存儲的是長重用距離熱數據.同時S和L各自都劃分成兩個棧，如S分為S1和S2棧，其中S1存儲短重用距離熱數據區域為實際緩存棧，S2存儲從S1驅逐的變冷數據的區域為幽靈緩存棧.同理，L具有和S一樣的劃分特征.注意實際緩存的數據結構為LRU棧結構，而幽靈緩存則是先進先出的隊列結構.

現假設整個緩存的大小為C，則算法的必須遵守以下規則：

1) |R1|≤0.2C;

2) |R1|+|R2|≤|C|,|S1|+|S2|≤C,|L1|+|L2|≤C;

3) |R1|+|S1|+|L1|≤C

4) |R|+|S|+|L|≤3C;

注意這個||符號指緩存中的數據個數，事實上對于幽靈緩存中的元數據大小相對于數據大小而言幾乎忽略不計，因此雖然 4)中有小于3C的規定，但是其實真正的緩存大小仍然和C相差無幾.另外(1)中的0.2C為算法設置的短重用距離上限，具體見實驗4.3說明.

3.3 算法描述

這里介紹算法流程.初始時，實際緩存和幽靈緩存都為空.對于負載中的每一個讀請求或者寫請求，有且僅有以下三種情況發生：A.實際緩存命中；B.幽靈緩存命中；C.實際緩存和幽靈緩存都沒有命中.

3.3.1 實際緩存命中

當發生實際緩存命中時，說明數據此時至少在最近被訪問2次，因此數據應該被存入到熱數據棧S1或者L1中，具體地，當命中R1時，該數據將會從R1棧遷移到S1棧的MRU位置；當命中S1或者L1時，由于數據本身已經存在于熱數據棧中，因此只需將數據移動至各自棧的MRU位置即可.

3.3.2 幽靈緩存命中

幽靈緩存存在的目的是為了幫助算法識別出當前數據訪問趨勢的變化情況，從而使算法對當前各種類型的實際緩存的大小做出及時的調整.因此當幽靈緩存發生命中時，需要執行3個步驟：

1) 根據當前的數據訪問變化趨勢，調整各個類型實際緩存大小的匹配值；

2) 當實際緩存滿時，算法根據這個匹配值決定淘汰哪個實際緩存的頁面；

3) 命中的幽靈頁面的數據插入到實際緩存中.

針對步驟1，算法設計了2個可調參數p和q,其中p代表R1棧根據當前負載情況得出的緩存大小匹配值，q代表S1棧根據當前負載情況得出的緩存大小匹配值，假設緩存大小為C，則L1棧的緩存大小匹配值為C-p-q,其中p的上限值為0.2C，q的上限值為C.

當發生R2命中時，視為R1的當前緩存大小不夠，算法增加p的大小；當發生S2和L2命中時，視為其各自對應的S1和L1的當前緩存太小，算法減少p的大小；其中當發生S2命中時，算法還會視為當前數據訪問類型的趨勢可能為短重用距離數據，因此算法會增加q的大小，同理當發生L2的命中時，算法減少q的大小.具體的p和q的調整公式如下：

如果發生R2命中時，那么：

如果發生S2命中時，那么：

如果發生L2命中時，那么：

針對步驟2，算法設計一個子函數BLANCE(x,p,q).當上述參數p和q調整好之后，如果實際緩存已滿時，算法會調用該函數來做出驅逐哪一類型的實際緩存頁面的決定.而函數BLANCE的處理辦法是算法按順序依次比較參數p和q與其對應的棧R1和S1的大小，然后驅逐出實際緩存大小大于其對應匹配參數值的緩存頁面.最后，針對步驟3，當R2命中時，該數據將插入到L1棧的MRU端；當S2命中時，該數據將插入到S1棧的MRU端；當L2命中時，該數據將插入到L1棧的MRU端.同時，命中的幽靈緩存頁面都會進行刪除.

3.3.3 實際緩存和幽靈緩存均未命中

如果R1棧未滿，數據直接插入到R1棧的MRU端即可；如果R1棧已滿，算法會將R1棧的LRU端數據遷移至R2棧的ENTRY端，然后再將數據插入到R1棧中，這個過程會持續到出現以下面2種情況時截止；其中第1種情況是R或S或L滿時，第2種情況是|R1|+|S1|+|L1|=C時.對于第1種情況，算法會先刪除一個R或S或L中滿的那個里面的幽靈緩存隊列中的EXIT端頁面，然后調用函數BLANCE驅逐出一個實際緩存頁面，最后將數據插入到R1中；對于第2種情況，算法直接調用函數BLANCE驅逐出一個實際緩存頁面，然后將數據插入到R1中.之所以第1種情況需要刪除幽靈緩存頁面，是因為函數BLANCE驅逐的頁面需要存放到對應的幽靈緩存中，而如果此時的幽靈緩存為空，那么算法別無選擇，函數BLANCE驅逐的頁面將會直接被丟棄.

4 實驗評估和分析

4.1 實驗環境

為了評估本文提出的ACRD算法的性能，本文在實驗中實現了LRU,LIRS,ARC,ACRD等4種算法.對于實現的LIRS算法參數，為了使算法性能達到最優，實驗設置緩存中存儲HIR貯存塊的區域大小為緩存的1%，并且對HIR非貯存塊(元數據)的數量不設限制.每種算法均以Trace文件作為輸入，并在執行過程中記錄總的訪問次數和命中次數，并將最終產生的命中率作為衡量算法性能的重要指標.在這項評估中，我們沒有計算元數據在緩存中所占用的空間，因為元數據僅起到標志和存儲數據地址的作用，它的大小與真實數據相比幾乎忽略不計.實驗對待幽靈緩存的大小，是視作每個元數據大小為512B來計數的，所以雖然幽靈緩存的大小占了2C，但是其實非常小.

4.2 數據集分析

我們使用MSR Cambridge traces[15,16]來測試兩種方案的更新性能. MSR Cambridge traces是由微軟劍橋研究院在2007年通過13臺服務器179個磁盤收集的一個塊水平上的I/O traces，該traces由I/O請求組成，每一個請求包括時間戳，服務器名，磁盤號，讀/寫類型，邏輯塊開始地址，操作數據大小，響應時間.整個traces包括36個數據集，類型包括用戶主目錄、 項目目錄、 Web/SQL等. 由于實驗設備和實驗時間的限制，我們只選取了該traces中部分數據集進行實驗，為了測試合理性，我們從不同類型的服務器上選取了其中6個數據集進行分析測試.

表1 數據集特征Table 1 Properties of data sets

由于本文算法僅僅通過是通過數據的訪問的新進度，訪問頻率和重用距離這三種數據訪問模式的特征來決策數據的緩存分配情況，因此我們并不區分數據訪問請求中的讀請求和寫請求.表1顯示了各個負載數據集的相關測試信息，其中No.of Requests代表塊請求的個數.為了方便直觀地理解這些Trace的內部特征，本文統計了各個Trace數據集中獨立的塊個數，然后計算出各個trace數據集中數據訪問的重復率.其中No.of Blocks即代表獨立的塊個數，Repeat Rate代表該trace數據集訪問的重復率.需要說明的是從Trace的請求信息來看，Trace的每個請求其實都由幾個扇區組成的，而一個扇區的大小為512字節，因此操作數據的大小總是512的倍數.例如，如果數據請求的邏輯塊開始地址為1001，操作數據大小為1024，則這個訪問請求其實是對兩個扇區的請求，實際請求的塊的邏輯地址分別是1001和1002.所以我們這里統計的請求次數是建立每一個塊的訪問請求的上.

從表1所顯示的重復率來看，除了prn0和web0數據集的重復率小于40%外，其余的Trace數據集的重復率基本都大于或等于70%，這一方面，充分說明了緩存算法研究的必要性，另一方面也可以從某個側面簡單地看出緩存算法命中率所能達到的極限.

4.3 實驗結果分析

為了更好地評估算法的性能，我們從算法的命中率，算法各緩存棧的命中率貢獻比，算法對算法唯一可調參數的敏感性和算法的開銷進行實驗與分析.

4.3.1 數據集命中率測試分析

圖3給出的是本文提出的算法比較LRU,LIRS,ARC三種緩存算法在不同的TRACE數據集下的命中率結果.實驗選取了6種不同的類型TRACE數據集，并針對數據集的特點和規模，設計緩存大小范圍從1M到64M的7種不同的規格來進行測試.

實驗的測試結果，從橫向上看，隨著緩存大小的增加，每個算法的命中率都有相應不同幅度的提升.從縱向上看，首先不存在某個算法在任何TRACE數據集和緩存大小設置的條件下都達到最優，即便是LRU算法平均命中率是最低的，但是從web_0的TRACE數據集的測試來看，在該數據集下LRU算法是優于LIRS算法的.其次就平均命中率而言，LRU算法本身由于存在之前提及的諸多缺陷，算法的平均命中率是最低的；而LIRS和ARC算法的平均命中率不相伯仲，但是其在該指標下的性能的確遠高于LRU算法；最后本文提出的算法，其設計借鑒和吸收了其它算法的優點，因此實驗結果也達到了預期標準，算法的平均命中率是這四種算法里面最高的.此外從實驗結果中可以看出，本文提出的算法更具有穩定

性，這可能與算法引入了自適應性有關.

4.3.2 不同緩存棧性能測試

本文提出的算法有三個緩存棧即R1,S1和L1棧，其中R1棧存放的是潛在的熱數據，而S1和L1棧分別存放的是短重

(a) hm_0數據集下的不同緩存棧命中率分析

(b) prn_0數據集下的不同緩存棧命中率分析圖4 ACRD算法不同緩存棧命中率分析Fig.4 Hit ratio analysis of different cache stacks of ARCD algorithm

用距離和長重用距離熱數據.為了驗證不同緩存棧的性能，實驗選取了2個TRACE數據集來測試不同緩存棧的命中率貢獻比，如圖4所示.

從圖中可以看出，R1棧作為過濾棧，其命中率貢獻比一般不超過10%.因此算法的命中率主要取決于熱數據棧即S1和L1棧，其中L1棧的命中率貢獻比在hm_0的TRACE數據集中平均是18%，最高達23%，在prn_0的TRACE數據集中平均是22%，最高達36%.這里的L1棧命中率貢獻比是算法自適應的結果，表明當前TRACE數據集中長重用距離數據的比例，所以在其它長重用距離數據占比更高的數據集中，其L1棧命中率貢獻比可能會達到更高.這也充分說明通過分類重用距離來捕捉熱點數據這一想法的必要性.

4.3.3 敏感性和開銷分析

R1棧大小的上限值是本文算法的唯一可調參數.從4.3.2中可知，R1作為過濾棧，其命中率貢獻比很小，但是如果因此將R1棧的大小設置的太小，這會導致S1棧作為主要的命中率貢獻棧的作用降低.雖然后續L1棧的命中率會提高，但是由于R2棧是一個幽靈緩存棧，因此程序的時間開銷會增大.

圖5顯示的是R1過濾棧的上限值從緩存大小的1%到30%的敏感性分析.如圖顯示，過濾棧的大小對命中率不敏感.但是從實踐的測試結果來看，10%-20%的緩存大小可能會體現出算法的最佳性能.為了穩妥起見，在本文的算法設計中，這個上限值設置為20%.

另外對于算法的開銷，首先每個算法的實際緩存大小是一個固定值.其次對于維護歷史塊的幽靈緩存的開銷，算法的幽靈緩存大小是ARC算法的2倍，但是平均不會超過LIRS算法.此外由于歷史塊僅存儲數據塊地址信息和塊號，其大小相比數據塊大小幾乎可以忽略不計.因此綜合來看，算法的開銷是合理的.

5 結 論

本文提出了一種自適應分類重用距離捕捉熱數據的緩存算法.算法設計的主要目的主要是為了解決熱數據的緩存駐留時間問題，例如相同訪問頻率次數的不同重用距離的熱數據，它們的緩存駐留時間不可能僅僅取決于頻率，而應該更可能與數據本身存在的重用距離特征有關.而本文提出的通過分類重用距離來捕捉熱數據的方法，則可以解決很好地解決這種不同重用距離的熱數據塊的互相污染問題.實驗結果表明，這樣的設計可以提高算法的命中率，并且本文引入了自適應的方法來動態處理這種數據分類和緩存駐留時間分配問題，因此算法的命中率具有更好的穩定性.

圖5 算法對過濾棧大小的敏感性測試Fig.5 Sensitivity of the filter stack size from 1 to 30%of cache size