唐 琪，王吉磊，柴云鵬

中國人民大學(xué) 信息學(xué)院，北京 100872

1 引言

長期以來，硬盤因具有容量大、價格低、性能穩(wěn)定的特點而成為最主流的存儲介質(zhì)，新型的瓦記錄磁盤進一步提升了磁盤的存儲密度和性價比。隨著大數(shù)據(jù)時代的到來，對于存儲的性能也提出了越來越高的要求。利用緩存機制來加速硬盤訪問的性能也已成為一項愈加重要的技術(shù)。

有企業(yè)直接將基于閃存芯片的固態(tài)硬盤（solid state drive，SSD）作為存儲介質(zhì)。但SSD的寫操作的次數(shù)是有限制的，如果針對某些單元進行過10萬次寫操作（SLC（single-level cell）），甚至僅5 000～10 000次（MLC（multi-level cell））[1-2]，后續(xù)這些單元的寫入可能會失效，即閃存的寫入的耐久性有限。而且閃存芯片內(nèi)部固有的寫放大現(xiàn)象（即由于擦除和讀寫操作單位的不匹配引發(fā)的額外的數(shù)據(jù)搬移操作）也加劇了芯片磨損的速度，實際寫入大小很可能比用戶寫入的要大很多[3]。另一方面，并非所有數(shù)據(jù)都會被經(jīng)常訪問，甚至有些數(shù)據(jù)可能幾乎不會被訪問，SSD作為存儲介質(zhì)的高成本很難帶來相匹配的收益。

但是在緩存設(shè)備方面，SSD相對于DRAM來說，容量更大、成本更低、功耗更低，且具有非易失性，是新一代的緩存介質(zhì)。將讀能力出色的SSD作為磁盤讀緩存，是一個加速效果非常明顯的方案。將一些會被頻繁訪問的數(shù)據(jù)寫入SSD緩存，減少CPU進行磁盤I/O訪問的次數(shù)，以提高硬盤的性能[4-7]。

因此以硬盤作為存儲介質(zhì)，SSD作為其緩存的存儲模式是很多大數(shù)據(jù)存儲系統(tǒng)較為理想的選擇。但多數(shù)緩存算法需要頻繁地緩存數(shù)據(jù)更新，也會導(dǎo)致寫入耐久性有限的SSD遇到使用壽命縮短的問題。目前主流的企業(yè)級SSD產(chǎn)品，假設(shè)預(yù)期5年使用壽命，每日只能寫入1.38～10.05倍自身容量的數(shù)據(jù)[8]，這對于需要頻繁更新緩存數(shù)據(jù)保持高命中率的緩存來說，是遠遠不夠的。

現(xiàn)有的傳統(tǒng)緩存替換算法（如LRU（least recently used））多數(shù)基于時間局部性設(shè)計，這類方法傾向于選擇短期熱門數(shù)據(jù)進行緩存，因此在保證高命中率的同時往往需要頻繁的數(shù)據(jù)更新，會縮短SSD的使用壽命。也有一些改進算法能夠減小一部分SSD緩存的寫入量，主要的方法隨機地禁止一部分數(shù)據(jù)進入SSD（如L2ARC（level 2 adjustable replacement cache）[9]）,或者去掉部分時間局部性差的數(shù)據(jù)（如LARC（lazy adaptive replacement）[10]）。這些方法只是在LRU 等緩存短期熱門數(shù)據(jù)的傳統(tǒng)方法基礎(chǔ)上，減少一部分數(shù)據(jù)寫入SSD，并沒有在數(shù)據(jù)選擇方法上做出本質(zhì)上的調(diào)整，從根本上改善SSD緩存中數(shù)據(jù)的質(zhì)量，進而從根本上保持高命中率和減少寫入量。

本文提出的訪問序列折疊（folded access sequence，F(xiàn)AS）算法能夠通過很低的開銷識別出長期穩(wěn)定被訪問的數(shù)據(jù)，通過提高緩存數(shù)據(jù)的質(zhì)量來同時減小SSD寫入量和保持高命中率。具體來說，F(xiàn)AS算法通過抽樣統(tǒng)計的方法，將較長時間內(nèi)的訪問記錄在若干個連續(xù)的時間窗口內(nèi)，并通過折疊窗口的方式，統(tǒng)計對各個數(shù)據(jù)塊的訪問在多個窗口中出現(xiàn)的次數(shù)占總窗口數(shù)的比例，將高于一定比值的數(shù)據(jù)篩選出來。這些數(shù)據(jù)在一定概率篩選的前提下仍然在多數(shù)時間窗口內(nèi)出現(xiàn)，說明這些數(shù)據(jù)是比較穩(wěn)定的長期熱門數(shù)據(jù)，將其寫入FAS的白名單中。在白名單中的數(shù)據(jù)塊再次訪問時會被允許進入SSD讀緩存，反之不在白名單的數(shù)據(jù)不允許被緩存，這樣既避免了頻繁的數(shù)據(jù)更新，也能讓高質(zhì)量的長期熱門數(shù)據(jù)較穩(wěn)定地保持在SSD緩存中，從而用較少的SSD寫入就能達到較高的緩存命中率。

通過一系列基于仿真系統(tǒng)的實驗，將FAS算法與一些典型的緩存算法進行比較。FAS算法相對于傳統(tǒng)LRU算法可減少90%的寫入量，而命中率損失僅不到10%。與SieveStore[11]算法相比，在命中率相當(dāng)?shù)那闆r下寫入量可減少50%～75%。在命中率高于L2ARC[9]算法的情況下，寫入量至少可以減少50%，在局部性較好的情況下，寫入量甚至可以減少90%。實驗結(jié)果表明提出的訪問序列折疊算法可有效地提高緩存數(shù)據(jù)質(zhì)量，減少SSD的寫入量，從而延長其使用壽命。

本文的第2章將介紹現(xiàn)有的相關(guān)研究；第3章將介紹訪問序列折疊算法的原理；第4章將給出實驗結(jié)果與分析；最后在第5章進行簡要的總結(jié)。

2 相關(guān)工作

作為硬盤緩存部分的SSD的容量通常較小，需要有高效的替換算法來保證系統(tǒng)的性能。從傳統(tǒng)磁盤概念上講，緩存替換算法主要關(guān)注訪問的命中率，如LRU、FIFO（first input first output）、LFU（least frequently used）、MQ（multi queue）[12]等。這些算法更傾向于緩存一些短期內(nèi)訪問量較高的數(shù)據(jù)，當(dāng)然無法保證緩存的是長期熱門數(shù)據(jù)，因此需要頻繁地更新緩存數(shù)據(jù)。但對于寫入耐久性有限的SSD緩存來說，頻繁的數(shù)據(jù)更新會導(dǎo)致SSD壽命縮短，對于存儲系統(tǒng)的可靠性和企業(yè)運維成本來說都是一項嚴峻的挑戰(zhàn)。

現(xiàn)有的幾種針對SSD讀緩存的壽命改進的緩存算法主要包括Solaris ZFS所使用的L2ARC[9]算法、LARC[10]算法，以及SieveStore[11]算法。這些算法雖然通過過濾掉部分數(shù)據(jù)來減少寫入量，但并沒有提高緩存中的數(shù)據(jù)質(zhì)量。下面將分別進行詳細的分析。

2.1 L2ARC算法

L2ARC[9]算法是Solaris ZFS中SSD讀緩存所使用的緩存算法。所使用的算法是周期性地將內(nèi)存緩存隊列末尾的一部分數(shù)據(jù)抽樣進入SSD讀緩存，這些數(shù)據(jù)仍然屬于短期熱門數(shù)據(jù)，但是即將被內(nèi)存緩存淘汰，因此提前轉(zhuǎn)入容量更大的SSD緩存。抽樣的選擇方法可以控制和減少SSD的寫入量。但在這個過程中，只是完全隨機地去掉部分數(shù)據(jù)，并沒有提高長期熱門數(shù)據(jù)的比例。如圖1所示，三角形表示按照LRU等景點算法寫入SSD讀緩存的數(shù)據(jù)總和，其中好、中、差表示數(shù)據(jù)的長期熱度的高低。L2ARC算法由于是隨機篩選數(shù)據(jù)，因此對于好、中、差數(shù)據(jù)不做區(qū)分，都有一部分進入SSD讀緩存，寫入情況如圖1所示。L2ARC并沒有提高好數(shù)據(jù)的比例，改善緩存數(shù)據(jù)的質(zhì)量。

Fig.1 Written block selection of SSD cache under L2ARC圖1 L2ARC算法對寫入SSD緩存數(shù)據(jù)的篩選

2.2 LARC算法

LARC(lazy adaptive replacement)[10]算法主要思想是如果一個數(shù)據(jù)塊在較短的時間內(nèi)被連續(xù)多次訪問，則被允許進入SSD讀緩存；否則不允許進入。這樣可以選擇局部性最好的一部分數(shù)據(jù)進入SSD，減少SSD的寫入量。LARC主要針對的是數(shù)據(jù)的時間局部性特征，即將局部熱（短期內(nèi)具有高訪問量）的數(shù)據(jù)寫入SSD緩存，寫入情況如圖2所示。

Fig.2 Written block selection of SSD cache under LARC圖2 LARC算法對寫入SSD緩存數(shù)據(jù)的篩選

這樣的篩選機制可以在一定程度上提高高數(shù)據(jù)的比例，但連續(xù)兩次較近訪問只是好數(shù)據(jù)的一種特征，既不是充分條件，也不是必要條件，會受不同應(yīng)用的特征影響使其在命中率和寫入量減少上的表現(xiàn)差距較大，會遺漏很多長期熱門數(shù)據(jù)，也會將一些短期熱門但熱度衰變較快的數(shù)據(jù)寫入SSD緩存。

2.3 SieveStore算法

SieveStore[11]算法所采用的方式是設(shè)置數(shù)據(jù)塊訪問緩存缺失數(shù)閾值作為進入SSD緩存的門檻，即訪問某數(shù)據(jù)塊的緩存缺失數(shù)達到一定次數(shù)后運行進入SSD緩存，寫入情況如圖3所示。這樣的機制只去掉了一部分最差的數(shù)據(jù)（訪問次數(shù)最少的數(shù)據(jù)），但中等和最好的數(shù)據(jù)在這個過程中沒有區(qū)分，還是有很大的SSD寫入量，其中還是有很多較差數(shù)據(jù)。并且該方法為了記錄每個數(shù)據(jù)塊的訪問情況，元數(shù)據(jù)的開銷很大，甚至可能無法全部裝入內(nèi)存，需要放到外設(shè)中，導(dǎo)致其性能較低。

希望對緩存算法做出的改進是以一種低開銷的方式通過對緩存替換設(shè)置一定的篩選機制，提高好數(shù)據(jù)的比例，選擇那些長期具有高訪問頻率，而非短期熱門的數(shù)據(jù)寫入緩存數(shù)據(jù)，從而提高緩存中數(shù)據(jù)的平均質(zhì)量。

Fig.3 Written block selection of SSD cache under SieveStore圖3 SieveStore算法對寫入SSD緩存數(shù)據(jù)的篩選

3 訪問序列折疊

本章詳細介紹所提訪問序列折疊（FAS）緩存替換算法。

對于寫入耐久性較差的SSD緩存來說，為了在保證命中率的同時減少寫入量，最理想的情況是找出長期穩(wěn)定的熱門數(shù)據(jù)來寫入SSD緩存，這樣的數(shù)據(jù)熱度能夠保持較長時間，即訪問序列較長，寫入緩存后可以提高SSD內(nèi)的數(shù)據(jù)質(zhì)量，不需要頻繁更新緩存數(shù)據(jù)就可以使SSD緩存保持較高的命中率。但是為了找出這些長期熱門的“好”數(shù)據(jù)，需要長期跟蹤訪問記錄來實現(xiàn)，一般來說存儲和計算的開銷都比較大，很難實際應(yīng)用。

但實際上，并不需要所有數(shù)據(jù)的精確訪問記錄，本文目標只是將圖4中訪問序列很長的長期熱門的“好”數(shù)據(jù)和其他低質(zhì)量的數(shù)據(jù)區(qū)分開。因此可以采用較為模糊的方式來維護數(shù)據(jù)塊的訪問記錄，從而降低計算和存儲的開銷。

Fig.4 Access sequence distribution of data quality圖4 不同質(zhì)量的緩存數(shù)據(jù)對應(yīng)的訪問序列長度

具體來說，本文所提出的訪問序列折疊算法就是這樣一個用較低開銷找出長期熱門數(shù)據(jù)的方法。最核心的思想是通過訪問序列折疊來用較低開銷準確識別長期熱門數(shù)據(jù)（3.1節(jié)），其次通過訪問抽樣方法來進一步減小算法開銷（3.2節(jié)），并通過白名單機制來進行低頻率的緩存數(shù)據(jù)更新，延長SSD壽命（3.3節(jié)）。最后，訪問序列折疊算法的復(fù)雜度將在3.4節(jié)進行分析。

3.1 訪問序列折疊思想

長期熱門數(shù)據(jù)的主要特征是訪問序列較長，因此會導(dǎo)致兩個屬性：一是訪問總數(shù)較多；二是訪問分布持續(xù)的時間長，在很多時間段上都會有訪問。傳統(tǒng)的LFU等算法就是抓住第一個特征識別熱門數(shù)據(jù)，但是這樣可能有一些短期熱門的數(shù)據(jù)，在短期內(nèi)有較高的訪問量，與長期熱門數(shù)據(jù)會混淆。因此所提出的訪問序列折疊（FAS）算法就是利用長期熱門數(shù)據(jù)的第二個特征。

如圖5所示，F(xiàn)AS算法維護一個隊列記錄最近訪問的數(shù)據(jù)塊的ID，新來的訪問直接寫入隊列的尾部，而不需要進行高開銷的排序操作。當(dāng)整個隊列滿了之后，會將其均分為幾個時間窗口進行折疊，并統(tǒng)計其中每個數(shù)據(jù)塊在幾個時間窗口內(nèi)出現(xiàn)。例如圖5中所示的數(shù)據(jù)塊a，在4個時間窗口中的3個出現(xiàn)，說明a的訪問序列較長，覆蓋較多的時間窗口，a是長期熱門數(shù)據(jù)的可能性比較大。而數(shù)據(jù)塊d、e、f等在4個時間窗口中只出現(xiàn)1次，說明長期熱門數(shù)據(jù)的可能性比較小。

相對于LFU等算法，F(xiàn)AS算法不需要進行復(fù)雜的排序操作，而訪問序列折疊這樣的復(fù)雜操作會間隔較長時間進行一次，計算實時性要求也不高。存儲空間則主要取決于記錄訪問數(shù)據(jù)塊ID的隊列長度，但并不需要很長的記錄即可識別出長期熱門數(shù)據(jù)。但是，F(xiàn)AS算法針對長期熱門數(shù)據(jù)的第二個特征，更為準確，可以有效減小SSD緩存的數(shù)據(jù)更新頻率，并維持較高的緩存命中率。

Fig.5 Principle of folded access sequence圖5 訪問序列折疊原理

3.2 訪問抽樣與抽樣時間窗口折疊

為了進一步減小訪問序列折疊方法的開銷，數(shù)據(jù)塊進入訪問記錄隊列可以采用抽樣的方法，即所有訪問以概率p進入隊列。這種情況下，可以理解為該隊列包括若干個抽樣時間窗口，如圖6所示。這樣可以用更小的空間開銷覆蓋更長的時間段，提高長期熱門數(shù)據(jù)識別的效果。而長期熱門數(shù)據(jù)由于熱度較高，在一個時間窗口內(nèi)會多次出現(xiàn)，即使進行抽樣操作，也會有很大的概率被選中。

如圖6所示，所有的緩存缺失，都將以一定概率p進入抽樣時間窗口中。假設(shè)共有n個分布在時間軸上的時間窗口，每個時間窗口的長度相同，可以記錄Lw個訪問，每兩個連續(xù)時間窗口之間的間隔為Ls個訪問，即兩個窗口之間的Ls個訪問沒有進入抽樣時間窗口的機會，這樣可以進一步延長所有抽樣時間窗口覆蓋的時間長度。

Fig.6 Principle of folded access sequence algorithm圖6 訪問序列折疊算法原理

假設(shè)，某個訪問正處于第i個抽樣時間窗口，那么它將以概率p進入窗口i。以此類推，對后續(xù)的訪問進行相同操作直到窗口i填滿即窗口中接納進了Lw個訪問，跳過后續(xù)Ls個視為在間隙中的訪問后，開始下一個窗口的填充。

當(dāng)一組時間窗口（假設(shè)為n個）全部填滿后，對這n個窗口進行折疊，即統(tǒng)計出現(xiàn)過的數(shù)據(jù)塊在所有窗口中出現(xiàn)的次數(shù)。如果次數(shù)達到預(yù)先設(shè)置的閾值，則視為符合長期熱門數(shù)據(jù)的篩選條件，進入后續(xù)的白名單，即白名單中的數(shù)據(jù)都是被識別出來的長期熱門數(shù)據(jù)。當(dāng)后續(xù)訪問命中白名單時，該數(shù)據(jù)塊可以寫入SSD緩存。這樣既避免了頻繁的數(shù)據(jù)更新，大大減少了SSD緩存的寫入量，又保證了緩存中的數(shù)據(jù)質(zhì)量和命中率。

總的來說，雖然本文進行了抽樣，但由于長期熱的好數(shù)據(jù)擁有高訪問頻率，進入時間窗口的機會更大，在連續(xù)多個窗口中重復(fù)出現(xiàn)的概率高。折疊窗口后便可將這些多次重復(fù)出現(xiàn)的長期熱數(shù)據(jù)準確識別出來。而有些局部熱數(shù)據(jù)，盡管短期內(nèi)訪問頻率高，但由于每個時間窗口內(nèi)的元素是不重復(fù)的，排除了短期內(nèi)的多次訪問的干擾，即差數(shù)據(jù)或局部熱數(shù)據(jù)是很難在窗口折疊的過程中被篩選出來的。

3.3 低頻率數(shù)據(jù)更新

將時間窗口折疊篩選出的好數(shù)據(jù)記錄在一個長度有限的白名單中，白名單隊尾的元素將會被淘汰。當(dāng)新的訪問命中白名單時，對應(yīng)的數(shù)據(jù)將被寫入SSD緩存，替換掉相對最差的數(shù)據(jù)。而SSD可以采用多種已有算法進行數(shù)據(jù)管理（如FIFO、LRU等），在更新數(shù)據(jù)時，淘汰掉隊列尾部同等數(shù)量的數(shù)據(jù)即可。白名單的存在使得不需要產(chǎn)生額外的磁盤訪問將數(shù)據(jù)加載到SSD緩存，而是等待在下一次訪問缺失時自然加載。

爐殼采用焊接式鋼結(jié)構(gòu)框架，保證焊接的密封性。由于氫氣密度小于空氣，爐殼進氣口設(shè)置在上部，排氣口設(shè)置在下部，在排氣口處有長明火咀，工作時將排出的廢氣點燃，確保設(shè)備和工作環(huán)境安全。爐口處有水冷套，爐門采用新型結(jié)構(gòu)[2]，保證了爐口的氣密性。同時，出于安全考慮，在爐頂部設(shè)有防爆裝置。

值得注意的是，白名單的長度是有限的，滿了之后需要進行替換，用LRU算法進行管理。由于長期熱門數(shù)據(jù)也會脫離活躍期，這樣可以逐漸從白名單中脫離。

由于填滿每個抽樣時間窗口需要較長時間，且每次窗口折疊也不一定都能產(chǎn)生很多符合條件的數(shù)據(jù)，整體上SSD緩存的數(shù)據(jù)更新并不頻繁，低頻率的更新能夠明顯較少寫入壓力。與此同時，訪問序列折疊算法篩選出的數(shù)據(jù)有較大概率為長期熱的高訪問頻率數(shù)據(jù)，因此能在低頻率數(shù)據(jù)更新和低開銷的前提下，保證較高的數(shù)據(jù)平均熱度和緩存命中率。

3.4 復(fù)雜度分析

訪問序列折疊算法無論是從時間復(fù)雜度還是空間復(fù)雜度來講都滿足作為緩存算法負載低的要求。

在時間復(fù)雜度方面，對每一個訪問，額外的計算開銷只是生成一個隨機數(shù)并判斷它是否小于等于給定的概率p值，如果符合便將其放入當(dāng)前時間抽樣時間窗口的集合中。這個操作非常簡單，開銷很低，時間復(fù)雜度為O(1)，理論上不會對系統(tǒng)的讀寫速度產(chǎn)生額外影響。相對于LFU算法，訪問序列折疊方法在每次更新緩存隊列時不需要進行排序操作，因此能夠降低這方面的計算復(fù)雜度。

而算法的主要開銷是在周期性地進行時間窗口折疊時，這個階段需要統(tǒng)計n個集合中每個元素出現(xiàn)的總次數(shù)，并只留下大于等于M的數(shù)據(jù)塊，時間復(fù)雜度為O(Lw×n)。然而這個操作需要間隔很久才進行一次，即等待抽樣時間窗口填滿，并且沒有明確的時間限制需要立即完成，因此可以接受其相對較高的復(fù)雜度。

在空間復(fù)雜度方面，主要的開銷是增加n個抽樣時間窗口的集合，集合中每個元素只需要記錄訪問數(shù)據(jù)塊的編號，整體占用空間很小。此外便是白名單的空間開銷，也同樣只需要記錄數(shù)據(jù)塊的編號，開銷同樣很小。

4 實驗與結(jié)果

4.1 實驗環(huán)境設(shè)置

基于Erlang語言實現(xiàn)了一個支持內(nèi)存緩存和SSD緩存的仿真模擬系統(tǒng)，用于評估訪問序列折疊算法的性能，Erlang語言的優(yōu)勢是便于并行計算來提高實驗評價的速度。

在系統(tǒng)中實現(xiàn)了多種具有代表性的緩存算法，包括傳統(tǒng)的LRU算法，針對SSD寫入耐久性改進的算法L2ARC和SieveStore。算法對比是在同樣的環(huán)境配置下，SSD Cache的大小默認采用Trace覆蓋容量的20%，使用SSD緩存的命中率以及SSD的寫入量（單位為4 KB的數(shù)據(jù)塊的個數(shù)）兩個考察指標，來評估所提出的訪問序列折疊（FAS）算法與已有算法的差異（實驗結(jié)果見4.2節(jié)）。最后，通過調(diào)整訪問序列折疊算法的參數(shù)來進一步評估該算法，包括窗口長度、折疊比例以及SSD緩存占Trace覆蓋容量的比例等（實驗結(jié)果詳見4.3節(jié)）。

用于測試的磁盤訪問記錄如表1所示，其中as2來自UC Berkeley的Auspex文件服務(wù)器[13]；metanodej和dslct均來自在BigdataBench[14]上運行Hive,其中metanodej為運行join操作時元數(shù)據(jù)節(jié)點上的I/O訪問記錄，dslct為運行select操作時數(shù)據(jù)節(jié)點上的I/O訪問記錄；websearch收集自搜索引擎[15]。

Table 1 Real-world traces used for evaluations表1 實驗所采用的實際應(yīng)用中的trace

4.2 緩存算法比較實驗結(jié)果與分析

如圖7～圖10所示，將訪問序列折疊（FAS）算法與LRU算法、L2ARC算法和SieveStore算法進行比較?？梢园l(fā)現(xiàn)，LRU算法由于沒有對寫入量進行限制，命中率一般要好于改進型算法L2ARC和SieveStore；但從寫入量上看，改進型算法的寫入量與LRU相比卻是量級上的差距。FAS與LRU在命中率上因不同的磁盤訪問記錄而異，最多相差17%，但此時的寫入量只有LRU算法的1/10；命中率相差不足10%時，寫入量是LRU的1/100，甚至在局部性比較好的訪問記錄（如metanodej）下，命中率相差不足1%時，寫入量也減少到LRU算法的1/10，可見FAS能夠在保證一定寫入量的同時有效減少寫入量。

Fig.7 Hit rates and SSD writes under trace as2圖7 as2下各算法的命中率及寫入量

Fig.8 Hit rates and SSD writes under trace dslct圖8 dslct下各算法的命中率及寫入量

Fig.9 Hit rates and SSD writes under trace metanodej圖9 metanodej下各算法的命中率及寫入量

Fig.10 Hit rates and SSD writes under trace websearch圖10 websearch下各算法的命中率及寫入量

與改進型算法L2ARC相比，對L2ARC進行參數(shù)的調(diào)試之后發(fā)現(xiàn)，若想保持寫入量在一個較低的水平，則需要大幅犧牲緩存命中率（30%左右），圖7～圖10中的結(jié)果是其命中率與其他算法相當(dāng)時，寫入量最低的結(jié)果。由于隨機選擇寫入SSD的數(shù)據(jù)，好數(shù)據(jù)的比例在SSD中并不占優(yōu)勢地位，造成在局部性較好的訪問記錄中，寫入量下降不明顯且命中率也不理想的情況，而FAS算法在相同的環(huán)境配置下，無論是從命中率還是寫入量，性能都優(yōu)于L2ARC。寫入量基本保持在L2ARC的1/10。對于數(shù)據(jù)讀取更為隨機的websearch，訪問序列折疊算法的命中率略高于L2ARC，但寫入量仍明顯減小，僅有其1/2。

與改進型算法SieveStore相比，訪問序列折疊算法在命中率方面多數(shù)情況下比較接近，但是寫入量可以減少至少50%。這說明FAS算法選擇數(shù)據(jù)的平均質(zhì)量更高一些，長期保持熱度方面更強一些，因此可以用很少的寫入量達到接近的命中率。

4.3 FAS算法參數(shù)的影響

本節(jié)選用了metanodej和dslct兩個用戶訪問記錄，通過調(diào)節(jié)抽樣時間窗口的長度、折疊方式以及SSD緩存的比例，來進一步分析訪問序列折疊算法的性能。

如圖11、圖12所示，當(dāng)其他參數(shù)保持不變，每個抽樣窗口長度從10增加至50時，命中率有所提高，但寫入量也隨之上升。由于折疊方式（訪問達到要求時出現(xiàn)頻數(shù)占總窗口數(shù)的比例）不變，窗口長度越小，越難篩選出符合要求的數(shù)據(jù)塊，寫入量相對較小，而增加窗口長度后，越符合想要篩選出長期熱數(shù)據(jù)的想法，因此命中率有所提升。搜索范圍更廣則能夠篩選出更多符合要求的數(shù)據(jù)塊，因此寫入量也相應(yīng)有所提升。

另外如圖13所示，固定了目標數(shù)據(jù)塊出現(xiàn)頻數(shù)占統(tǒng)計窗口數(shù)的比例為2∶5后，增加統(tǒng)計的窗口數(shù)量發(fā)現(xiàn)，考察的窗口數(shù)越多會使命中率有一定下降，寫入量也隨之下降。但寫入效率（SSD命中數(shù)/SSD寫入量）隨之提高，這是由于統(tǒng)計的窗口數(shù)越多，滿足條件的數(shù)據(jù)塊越符合長期熱數(shù)據(jù)的特征，寫入效率也隨之上升。

Fig.11 Impact of time window length under trace metanodej圖11 metanodej下窗口長度的影響

Fig.12 Impact of time window length under trace dslct圖12 dslct下窗口長度的影響

Fig.13 Impact of manner of folding access sequence under trace metanodej圖13 metanodej下折疊方式的影響

圖14給出了不同SSD緩存空間比例對FAS算法性能的影響，SSD緩存空間與訪問數(shù)據(jù)空間的比例從5%變化到20%。由圖14可知，隨著SSD緩存空間的上升，命中率在上升，而由于緩存的增加，緩存缺失數(shù)目更少，雖然緩存的大小增加會導(dǎo)致SSD緩存在算法啟動階段數(shù)據(jù)寫入增加，但緩存缺失的下降也會導(dǎo)致進入抽樣時間窗口的請求變少，SSD內(nèi)數(shù)據(jù)更新減小，使得雖然在中間過程中的寫入量有所波動，但整體趨勢上SSD的寫入量會更低。

Fig.14 Impact of SSD capacity percentage under trace metanodej and SieveStore on FAS圖14 metanodej和SieveStore下SSD緩存空間比例對FAS的影響

5 總結(jié)

本文提出了一種面向SSD壽命優(yōu)化的訪問序列折疊（FAS）緩存替換算法。不同于現(xiàn)有基于時間局部性設(shè)計的緩存替換策略數(shù)據(jù)更新過于頻繁的缺點，F(xiàn)AS算法旨在以低開銷來識別長期熱門數(shù)據(jù)，從而提高緩存內(nèi)數(shù)據(jù)的整體質(zhì)量，在保證一定命中率的同時，減少SSD緩存的寫入量。實驗結(jié)果表明，本文提出的訪問序列折疊算法在命中率方面與現(xiàn)有算法相差不大，而寫入量的減少大大優(yōu)于LRU等已有傳統(tǒng)算法與L2ARC和SieveStore等面向SSD改進的算法。