面向SSD壽命優化的訪問序列折疊緩存替換算法*

唐 琪，王吉磊，柴云鵬

中國人民大學 信息學院，北京 100872

1 引言

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

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

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

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

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

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

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

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

2 相關工作

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

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

2.1 L2ARC算法

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

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

2.2 LARC算法

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

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

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

2.3 SieveStore算法

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

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

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

3 訪問序列折疊

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

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

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

Fig.4 Access sequence distribution of data quality圖4 不同質量的緩存數據對應的訪問序列長度

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

3.1 訪問序列折疊思想

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

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

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

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

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

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

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

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

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

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

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

3.3 低頻率數據更新

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

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

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

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

3.4 復雜度分析

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

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

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

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

4 實驗與結果

4.1 實驗環境設置

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

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

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

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

4.2 緩存算法比較實驗結果與分析

如圖7～圖10所示，將訪問序列折疊（FAS）算法與LRU算法、L2ARC算法和SieveStore算法進行比較。可以發現，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進行參數的調試之后發現，若想保持寫入量在一個較低的水平，則需要大幅犧牲緩存命中率（30%左右），圖7～圖10中的結果是其命中率與其他算法相當時，寫入量最低的結果。由于隨機選擇寫入SSD的數據，好數據的比例在SSD中并不占優勢地位，造成在局部性較好的訪問記錄中，寫入量下降不明顯且命中率也不理想的情況，而FAS算法在相同的環境配置下，無論是從命中率還是寫入量，性能都優于L2ARC。寫入量基本保持在L2ARC的1/10。對于數據讀取更為隨機的websearch，訪問序列折疊算法的命中率略高于L2ARC，但寫入量仍明顯減小，僅有其1/2。

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

4.3 FAS算法參數的影響

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

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

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

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緩存空間與訪問數據空間的比例從5%變化到20%。由圖14可知，隨著SSD緩存空間的上升，命中率在上升，而由于緩存的增加，緩存缺失數目更少，雖然緩存的大小增加會導致SSD緩存在算法啟動階段數據寫入增加，但緩存缺失的下降也會導致進入抽樣時間窗口的請求變少，SSD內數據更新減小，使得雖然在中間過程中的寫入量有所波動，但整體趨勢上SSD的寫入量會更低。

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

5 總結

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