面向SSD壽命優(yōu)化的訪問(wèn)序列折疊緩存替換算法*

唐 琪，王吉磊，柴云鵬

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

2.1 L2ARC算法

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

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

2.2 LARC算法

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

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

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

2.3 SieveStore算法

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

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

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

3 訪問(wèn)序列折疊

本章詳細(xì)介紹所提訪問(wèn)序列折疊（FAS）緩存替換算法。

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

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

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

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

3.1 訪問(wèn)序列折疊思想

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

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

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

Fig.5 Principle of folded access sequence圖5 訪問(wèn)序列折疊原理

3.2 訪問(wèn)抽樣與抽樣時(shí)間窗口折疊

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

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

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

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

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

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

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

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

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

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

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

3.4 復(fù)雜度分析

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果

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

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

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

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

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

4.2 緩存算法比較實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

本節(jié)選用了metanodej和dslct兩個(gè)用戶訪問(wèn)記錄，通過(guò)調(diào)節(jié)抽樣時(shí)間窗口的長(zhǎng)度、折疊方式以及SSD緩存的比例，來(lái)進(jìn)一步分析訪問(wèn)序列折疊算法的性能。

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

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

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

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

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

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

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

5 總結(jié)

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