基于頻繁序列挖掘的文件系統(tǒng)緩存算法設(shè)計

摘 要：傳統(tǒng)緩存算法存在命中率低、交換率高等問題，且現(xiàn)有緩存算法在分布式大數(shù)據(jù)存儲系統(tǒng)中并不適用，為此提出了一種基于頻繁序列挖掘的自適應(yīng)緩存策略。該方法使用數(shù)據(jù)挖掘算法挖掘歷史訪問窗口內(nèi)的頻繁序列，將頻繁序列模糊合并后構(gòu)建匹配模式集合以供查詢。當(dāng)新的訪問來臨時，將固定訪問長度內(nèi)的子序列與匹配模式集合進行匹配，然后根據(jù)匹配結(jié)果預(yù)取數(shù)據(jù)，同時結(jié)合修改后的S4LRU（4-segmented least recently used）數(shù)據(jù)結(jié)構(gòu)進行緩存數(shù)據(jù)換出。在公開的大數(shù)據(jù)處理trace集上進行了仿真實驗，實驗結(jié)果表明，在不同的緩存大小下，提出算法與現(xiàn)有典型緩存算法相比，平均命中率提高了0.327倍，平均交換率降低了0.33倍，同時具有低開銷和高時效的特點。此結(jié)果表明，該方法較傳統(tǒng)替換算法而言是一個更為有效的緩存策略。

關(guān)鍵詞：緩存算法； 頻繁序列挖掘； 分布文件系統(tǒng)優(yōu)化

中圖分類號：TP3115 文獻標志碼：A

文章編號：1001-3695（2022）03-032-0831-05

doi：10.19734/j.issn.1001-3695.2021.08.0337

基金項目：國家重點研發(fā)計劃資助項目（2018YFB1004401）；北京市自然科學(xué)基金—海淀原始創(chuàng)新聯(lián)合基金資助項目（L192027）；陜西省重點產(chǎn)業(yè)鏈項目（2021ZDLGY03-02，2021ZDLGY03-08）

作者簡介：杜科星（1995-），男，陜西銅川人，碩士研究生，主要研究方向為分布式文件系統(tǒng)優(yōu)化；張小芳（1971-），女，陜西西安人，副教授，碩導(dǎo)，博士，主要研究方向為分布式文件系統(tǒng)、分布式數(shù)據(jù)庫；張曉（1978-），男（通信作者），河南南陽人，副教授，碩導(dǎo)，博導(dǎo)，博士，主要研究方向為云存儲系統(tǒng)管理與評估、性能建模技術(shù)（zhangxiao@nwpu.edu.cn）；趙曉南（1979-），女（滿族），遼寧撫順人，副教授，碩導(dǎo)，博士，主要研究方向為分布式存儲資源分配與伸縮管理、云存儲系統(tǒng)評估與建模.

File system caching algorithm based on frequent sequence mining

Du Kexing^a， Zhang Xiaofang^b， Zhang Xiao^b?， Zhao Xiaonan^b

（a.College of Software， b.College of Computer， Northwestern Polytechnical University， Xi’an 710072， China）

Abstract：Traditional cache algorithms have problems such as low hit rate and high exchange rate. And the existing caching algorithm is not applicable in the distributed big data storage system. This paper proposed an adaptive caching strategy based on frequent sequence mining. This method used a data mining algorithm to mine the frequent sequences in the historical access window， and merged the frequent sequences to construct a set of matching patterns for query. When a new access coming， matched the subsequence within the fixed access length with the matching pattern set， and then prefetched the data according to the matching result， and combined with the modified S4LRU （4-segmented least recently used） data structure for cache data exchange out. This paper conducted simulation experiments on the public big data processing trace set. The experimental results show that， under different cache sizes， compared with the existing typical cache algorithms， the proposed algorithm increases the average hit rate by 0.327 times and the average exchange rate reduces by 0.33 times， at the same time has the characteristics of low overhead and high time efficiency. This result shows that the proposed method is a more effective caching strategy than the traditional replacement algorithm.

Key words：caching algorithm; frequent sequence mining; distributed file system optimization

0 引言

隨著企業(yè)應(yīng)用數(shù)據(jù)規(guī)模的不斷增長，對海量數(shù)據(jù)進行高性能計算是當(dāng)前大數(shù)據(jù)方向的一個熱點研究領(lǐng)域。Hadoop分布式文件系統(tǒng)（Hadoop distributed file system，HDFS）是高性能計算中數(shù)據(jù)存儲和管理的基石^[1]，具有高可靠、高吞吐等優(yōu)點，拓展性較好，為大規(guī)模數(shù)據(jù)的計算和存儲帶來了許多優(yōu)勢。諸如科學(xué)數(shù)據(jù)處理、商業(yè)分析和社交圖譜分析等數(shù)據(jù)密集型作業(yè)需要在Hadoop、Spark等并行計算框架中進行處理，其后端存儲的數(shù)據(jù)訪問性能直接影響著對上層的服務(wù)質(zhì)量。在計算機的體系結(jié)構(gòu)中，內(nèi)存的讀取速度通常比磁盤高一個數(shù)量級以上，因此，對輸入數(shù)據(jù)進行有效的緩存能顯著提升作業(yè)的執(zhí)行效率、改善用戶體驗。

HDFS允許用戶根據(jù)存儲路徑指定HDFS中的文件或目錄并將其緩存在內(nèi)存中。然而，當(dāng)緩存已滿時，將不向其他緩存請求提供服務(wù)，直到用戶手動取消緩存某些文件^[2]，無法自適應(yīng)地緩存。文獻[3，4]在HDFS等底層存儲系統(tǒng)之上構(gòu)建的分布式內(nèi)存文件系統(tǒng)，它們采用了一些基本策略如LRU（least recently used）、LFU（least frequently used）等。而這些策略起源于操作系統(tǒng)的頁面替換算法，主動性不足，在大數(shù)據(jù)訪問下通常性能不佳、命中率低且交換率高，會降低內(nèi)存的壽命。Big SQL^[5]使用HDFS緩存來緩沖分區(qū)表，并提出了SLRU-K（selective LRU-K）和EXD（exponential-decay）兩種算法來執(zhí)行緩存的換入換出過程，該算法在文件訪問的新近度（recency）和頻率之間進行權(quán)衡，但與ARC（adaptive replacement cache）^[6]、LIRS（low inter-reference recency set）^[7]、MQ（multi-queue）^[8]等傳統(tǒng)替換算法一樣，仍無法學(xué)習(xí)文件訪問模式。

近年來，研究人員正在嘗試研究基于學(xué)習(xí)的緩存方法，絕大多數(shù)研究面向Web緩存、內(nèi)容分發(fā)網(wǎng)絡(luò)（content delivery network，CDN）等。在Web應(yīng)用處理中，WebProfiler^[9]使用深度學(xué)習(xí)中的門控循環(huán)單元（GRU）來處理Web交互數(shù)據(jù)的時間序列，文獻[10]提出了一種基于動態(tài)決策樹和不同階數(shù)馬爾可夫預(yù)測器的Web訪問預(yù)測方法。這些工作通過預(yù)測和預(yù)取Web用戶瀏覽的網(wǎng)頁和文件，有效減少了Web訪問的加載時間，但是這些方法僅針對Web環(huán)境，不能很好地應(yīng)用到分布式文件系統(tǒng)當(dāng)中。在內(nèi)容分發(fā)網(wǎng)絡(luò)中，文獻[11]結(jié)合用戶行為與緩存大小、帶寬等網(wǎng)絡(luò)屬性，通過極限學(xué)習(xí)機神經(jīng)網(wǎng)絡(luò)來預(yù)測內(nèi)容的未來流行度，用于蜂窩網(wǎng)絡(luò)基站的內(nèi)容緩存。但是該方法需要收集內(nèi)容的外部信息，如YouTube中某個視頻的點擊數(shù)量、標題字數(shù)等，而這些信息在分布式文件系統(tǒng)中很難得到，因此不能很好地應(yīng)用。DeepCache^[12]將LSTM（long short-term memory）編/解碼器用于內(nèi)容緩存框架中，并證明了其命中次數(shù)較LRU-K算法顯著增加。但是該方法會導(dǎo)致過多的緩存淘汰和添加，從而增加系統(tǒng)負擔(dān)，降低內(nèi)存壽命。LeCaR^[13]使用LRU和LFU之間的遺憾最小化算法進行緩存替換，在塊級的生產(chǎn)存儲 I/O 的FIU trace上進行了仿真，當(dāng)緩存大小設(shè)置為負載大小的0.1%時，其性能比ARC高出18倍以上，但其本質(zhì)仍是逐出算法，不能超過Belady算法的上限。

基于學(xué)習(xí)的方法依賴大量的訓(xùn)練數(shù)據(jù)集，且存在訓(xùn)練時間過長和預(yù)測時間長等問題，無法很好地應(yīng)用到文件系統(tǒng)當(dāng)中。目前，已有將數(shù)據(jù)挖掘技術(shù)應(yīng)用于文件系統(tǒng)元數(shù)據(jù)預(yù)取的研究，常用于挖掘文件訪問之間的關(guān)系，其算法執(zhí)行開銷一般較低。但是在數(shù)據(jù)預(yù)取方面，常見的關(guān)聯(lián)規(guī)則挖掘算法又會產(chǎn)生時效性等問題。ProMP^[14]基于進程生命周期或元數(shù)據(jù)I/O流等源信息，通過周期性地提取源窗口，結(jié)合元數(shù)據(jù)訪問頻率來挖掘進程與文件之間的相關(guān)性。文獻[15]通過語法分析和模式匹配來探索數(shù)據(jù)關(guān)聯(lián)性，并通過向元數(shù)據(jù)服務(wù)器動態(tài)反饋關(guān)聯(lián)文件的訪問信息來調(diào)整關(guān)聯(lián)度，與C-Miner^[16]策略相比降低元數(shù)據(jù)訪問延時最多20.2%。這些工作僅將挖掘結(jié)果用于元數(shù)據(jù)預(yù)取，對于上層客戶端數(shù)據(jù)讀取性能提升有限。ARMFS^[17]通過關(guān)聯(lián)規(guī)則挖掘HDFS日志，合并存儲強關(guān)聯(lián)的小文件，并當(dāng)訪問觸發(fā)文件時預(yù)取其關(guān)聯(lián)文件，對磁盤上臨近位置的讀取在一定程度上加速了預(yù)取效率。MITHRIL^[18]同樣基于零星關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘思想，通過分析塊訪問請求的時間戳，預(yù)取中頻訪問塊來改善命中率。但是，在大數(shù)據(jù)訪問模式下，關(guān)聯(lián)規(guī)則挖掘算法會生成過量的候選項目集^[19]，挖掘和匹配的過程耗時較長，無法很好地滿足生產(chǎn)環(huán)境的時效性需求。

本文提出了一個面向分布式計算框架的自適應(yīng)緩存策略CP-FSM。首先，基于SPADE（sequential pattern discovery using equivalence classes）頻繁序列挖掘（frequent sequence mining，F(xiàn)SM）算法獲取歷史文件訪問中的頻繁序列，并進行頻繁序列的模糊合并以優(yōu)化匹配的準確性和時效性；其次，將模式表示為文件的集合，基于滑動窗口的思想進行模式匹配與緩存文件換入，并結(jié)合S4LRU的改動算法進行緩存淘汰；最后，在Facebook公開trace上驗證了算法的有效性和時效性。

1 自適應(yīng)緩存算法設(shè)計

CP-FSM算法部署在NameNode節(jié)點，整體流程如圖1所示，CP-FSM在更新模式集合時，將歷史序列用于挖掘訪問模式，經(jīng)過頻繁序列挖掘、模糊合并之后形成新的模式集合，在后續(xù)訪問中使用匹配窗口的子序列去匹配，然后NameNode將匹配到的數(shù)據(jù)通知離客戶端最近的DataNode進行緩存，算法還設(shè)置了匹配間隔（即一段空閑時間，記為interval），防止換入換出過于頻繁導(dǎo)致的內(nèi)存抖動。

1.1 挖掘頻繁序列

CP-FSM算法在兩種情況下更新匹配模式集合：第一種情況是按指定時長定時更新;第二種是一定長度訪問內(nèi)緩存命中率下降到指定的閾值時更新。當(dāng)需要更新時，算法選擇出指定長度的歷史數(shù)據(jù)，然后使用頻繁序列挖掘算法挖掘新的模式。

CP-FSM算法使用SPADE頻繁序列挖掘算法，算法的基本思想是對歷史序列進行多次掃描，以確定每個文件的支持度（出現(xiàn)次數(shù)），掃描結(jié)束時，大于等于給定最小支持度的文件會被算法判定為頻繁文件，這些文件會產(chǎn)生一個由其本身組成的一元頻繁序列。后續(xù)的遍歷基于前一次遍歷生成的頻繁序列集（種子集），生成新的候選頻繁集，并且序列長度加一。文件的遍歷過程會計算出候選序列的支持度，并基于此確定頻繁序列，將其作為下次遍歷的種子集。當(dāng)沒有候選序列生成時，算法終止。將包含k個文件的序列稱為k-sequence，目的是用頻繁的（k-1）-sequence生成頻繁的k-sequence，候選序列的生成包括以下兩個步驟：

a）連接階段。如果序列S₁刪除第一個文件訪問與序列S₂刪除最后一個文件訪問后的序列相同，則可以將S₁與S₂進行連接，即用S₂的最后一個文件訪問來拓展序列S₁。此時分為兩種情況，當(dāng)S₂的最后一個文件訪問（字母）是它的最后一個元素（小括號）時，則將其作為S₁的最后一個元素，反之則將其作為S₁最后一個元素的最后一個文件訪問。

b）剪枝階段。如果一個候選序列的某個子序列不是頻繁序列，應(yīng)將其從候選序列中刪除。顯然頻繁序列的子序列也應(yīng)該是頻繁的，非頻繁序列的超序列也應(yīng)該是非頻繁的。

下面用一個例子來說明從長度為3的頻繁序列中，經(jīng)過連接和剪枝生成長度為4的候選序列的過程。如表1所示，頻繁序列{（a，b）（c）}與{（b）（c，d）}生成候選序列{（a，b）（c，d）}，{（a，b）（c）}和{（b）（c）（e）}生成候選序列{（a，b）（c）（e）}。顯然{（a，b）（d）}不能和任何序列連接，因為不存在形如{（b）（d，x）}的序列。序列{（a，b）（c）（e）}被剪枝是因為其長度為3的子序列{（a）（c）（e）}沒有在頻繁3-sequence中。

上述算法得出的頻繁訪問序列其數(shù)量仍然較大，也就是過量候選集問題^[19]，匹配過程耗時較長，因此需要進行進一步處理。CP-FSM算法將挖掘出的模式表示為文件的集合，通過頻繁序列的模糊合并，減少冗余模式數(shù)，形成最終的模式集合。頻繁序列中存在兩種需要合并的情況：

a）頻繁序列的子序列也一定是頻繁的，即會被算法一并輸出，應(yīng)該將這些子序列合并到其超序列中。

b）模式本身也是頻繁的，除了此次訪問外，在未來一段時間內(nèi)也有可能訪問該完整序列，這種情況下可以直接預(yù)取整個序列，因為這時序列之間沒有了順序關(guān)系，所以可以將其合并到包含這段序列所有元素的更大序列中。

第一種情況是第二種情況的特殊情況，因此頻繁序列的合并操作可以概括為：如果較短序列的元素是較長序列元素的子集，將較短序列合并到較長序列中。

1.2 換入策略

如圖2所示，CP-FSM算法基于滑動窗口的思想，每經(jīng)過一個匹配間隔（interval），開始積累新窗口的訪問，等訪問數(shù)等于匹配窗口大小（window_size）時，對窗口內(nèi)的子序列進行模式匹配。為進一步提升算法執(zhí)行效率，算法將模式集合列表進行反轉(zhuǎn)，從最長的模式開始匹配，若匹配成功，則將該模式從拷貝的臨時模式列表中刪除，防止下一個子序列產(chǎn)生冗余匹配。匹配成功后將集合內(nèi)的文件全部放入待緩存列表中，而不只是將集合內(nèi)的其他文件放入待緩存列表，因為模式本身也是頻繁的。

設(shè)置匹配間隔的目的是減少短期內(nèi)大量換入換出導(dǎo)致的內(nèi)存抖動。匹配到的文件可能大于緩存能容納的數(shù)量，因此不一定全部換入內(nèi)存，而且換入時要結(jié)合S4LRU的維護方式，這些將在1.3節(jié)進行討論。

1.3 換出策略

在LFU等基于引用計數(shù)的算法中，如果短期內(nèi)多次訪問了某一文件，那么因其過高的訪問計數(shù)可能很久都不會換出，但是這些訪問只是短期內(nèi)有效的。

CP-FSM算法的換出策略是基于S4LRU算法設(shè)計的。算法中維護四個分段（segment），每個分段占總緩存大小的四分之一，具體如圖3所示。通過分段將多次被訪問的文件盡可能合理地保存在內(nèi)存中，盡管其保存了訪問計數(shù)大于1的文件，但不會出現(xiàn)上述短期爆發(fā)式訪問帶來的難以換出問題。因為該算法每個分段仍然按照LRU的方式進行維護，只是將多次訪問的文件暫時放在更高級的分段中，如果后續(xù)該文件不再被訪問，則將很快被換出內(nèi)存。

將S4LRU與基于頻繁序列挖掘的換入策略相結(jié)合，在進行文件預(yù)取時，如果待預(yù)取文件在緩存中，則將本次預(yù)取操作視為一次緩存命中，維護對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以避免該文件在具有較低新近度且緩存空間不足時，被換入的預(yù)取文件置換出去，同時將此文件從待預(yù)取列表中刪除。如果待預(yù)取文件沒有在緩存中，首先需要為其確保足夠的緩存空間，如果待預(yù)取文件數(shù)目大于緩存能容納的數(shù)目，則隨機刪除待預(yù)取列表中多余的文件。

假設(shè)內(nèi)存緩存大小為1 GB，平均文件大小為32 MB，那么每個segment能容納8個緩存文件，現(xiàn)待預(yù)取文件換入前維護列表的當(dāng)前狀態(tài)，如圖4所示，其中編號僅為區(qū)分文件，沒有明確意義。如果需要換入14個待預(yù)取文件，則需要將待預(yù)取文件從fourth segment的LRU位置依次覆蓋，直至將所有的待預(yù)取文件換入緩存。

2 替換算法介紹

常見的替換算法有LRU（最近最少使用）、LFU（最近最不經(jīng)常使用）等。LRU算法維護一個緩存隊列，隊列中的文件按照所有文件最后被訪問的相對次序排序，當(dāng)緩存空間已滿時，將隊尾即最后一次被訪問時間距離現(xiàn)在最久的文件刪除，將新的區(qū)段放入隊列首部。LFU則是按每個文件被訪問的次數(shù)排序，維護方法類似LRU。這兩種算法都有其局限性，例如偶發(fā)性的、周期性的大量訪問（包含冷文件）會淘汰掉大量的熱點文件，導(dǎo)致 LRU 命中率急劇下降。而LFU的問題是早期的熱點文件會一直占據(jù)緩存，最近加入的文件總是傾向于被剔除。本文的對比方法是這兩種基礎(chǔ)算法的改進。

CP-FSM算法將與LIRS、ARC、S4LRU等替換算法進行比較。S4LRU原理在1.3節(jié)有所介紹，篇幅原因，這里主要介紹LIRS替換算法。LIRS針對LRU做了一些優(yōu)化，LIRS算法用兩個參數(shù)來表示記錄文件訪問歷史信息，IRR（inter-reference recency）表示最近連續(xù)訪問同一個文件之間訪問其他不同文件的非重復(fù)個數(shù)，第一次被訪問時IRR的值為無窮大，R（recency）為文件最近一次訪問到當(dāng)前時間內(nèi)有多少非重復(fù)文件曾經(jīng)被訪問過。IRR是由R值計算而來，在圖5中文件1第二次訪問時的R=2，第一次訪問的R=5，IRR=上一時刻的R-當(dāng)前時刻的R=3。

IRR可以衡量文件當(dāng)前訪問的頻度，IRR越高說明在某個時間段中，該文件的熱度較低。LIRS假設(shè)如果當(dāng)前文件的IRR比較大，那么該文件的下一個IRR也會比較大，在進行淘汰時會優(yōu)先選擇IRR較大的文件。

LIRS將文件分為LIR（低IRR值，熱文件）和HIR（高IRR值，冷文件，接下來有可能成為熱文件）兩種。LIRS設(shè)計了棧和隊列動態(tài)地維護IRR和R值，讓冷文件有機會成為熱文件，將變冷的熱文件剔除出緩存，避免了LRU的弊端，具體棧和隊列的維護過程較為復(fù)雜，這里不做詳細說明。

3 仿真實驗與分析

3.1 實驗準備

3.1.1 trace集準備

本文是針對分布式文件系統(tǒng)進行優(yōu)化，因此應(yīng)該選擇分布式文件系統(tǒng)的數(shù)據(jù)集，本文所用Hadoop trace來自Facebook包含3 000個節(jié)點的真實生產(chǎn)環(huán)境。完整trace從2010年10月到2010年11月共1.5個月，大約包含100萬個job^[20]。以前工作中有文章對其進行了負載分析，如統(tǒng)一的數(shù)據(jù)訪問、規(guī)律的晝夜模式和大型作業(yè)的普遍性^[21]，其開發(fā)了SWIM工具^[22]，該工具可以使用統(tǒng)一的合成數(shù)據(jù)預(yù)填充HDFS，縮放到集群中的節(jié)點數(shù)，并使用合成的MapReduce作業(yè)重播工作負載。使用SWIM工具在實驗集群上模擬來自Facebook應(yīng)用的真實負載，負載運行完畢后，即可通過日志獲取文件的訪問時序trace（為方便后續(xù)描述，這里記為fb-trace）。

SWIM項目開源了其中的一部分，共24 442個job。此外，trace中還包含job遞交絕對時間、遞交間隔、shuffle和reduce數(shù)據(jù)大小等。首先進行五次隨機挑選2 000個job，具體隨機挑選的分布結(jié)果與原分布如表2所示。從表2中可以看出，隨機挑選結(jié)果與原trace具有相同的概率分布，即嚴格服從重尾分布。因此fb-trace的緩存仿真結(jié)果足以證明算法的通用性。

實驗按照原Hadoop trace中的遞交間隔隨機地遞交所選出的2 000個job，因trace經(jīng)過脫敏處理，沒有給出具體每個job訪問的文件數(shù)目及每個文件的大小，為方便后續(xù)仿真實驗的進行，使訪問的平均文件大小為32 MB。負載運行完畢后統(tǒng)計結(jié)果顯示，執(zhí)行完所有job共耗時約34 h，訪問文件數(shù)為67 711，過濾臨時文件后，有14 970個來自數(shù)據(jù)文件的訪問。

3.1.2 仿真平臺

獲取到文件訪問trace之后，需要基于trace進行緩存仿真以計算本文算法的命中率、時間開銷等。為了使實驗更具有說服力，需要在一個公開的平臺進行緩存過程的仿真實驗。

PyMimircache^[22]是一個開源緩存仿真平臺，用于在Python的開發(fā)環(huán)境下進行有效、便捷的緩存分析與結(jié)果可視化。該工具允許自定義緩存策略，即可用于測試本文所設(shè)計緩存算法與傳統(tǒng)緩存策略的性能對比，該工具內(nèi)置ARC、S4LRU、CLOCK和LFU-fast等眾多緩存策略，支持緩存的命中率、請求率、流行對象分布、重用距離分布以及熱圖等數(shù)據(jù)可視化形式。PyMimircache具有性能良好、可拓展性強和便于使用等優(yōu)點，已應(yīng)用于許多緩存策略與工作負載的數(shù)據(jù)可視化與分析當(dāng)中。在PyMimircache平臺上進行所提算法的緩存仿真實驗，其結(jié)果具有一定的準確性與說服力。

3.2 實驗步驟

將fb-trace按順序平均分成兩部分，使用MG-FSM^[23]工具離線挖掘前7 485個訪問（歷史訪問）的頻繁序列，并進行模糊合并，形成最終的模式集合，并以文本文件格式儲存，各算法的對比將在后7 485個訪問上進行。

PyMimircache平臺默認只輸出命中率，本文在原有的代碼基礎(chǔ)上添加了統(tǒng)計交換率部分，后續(xù)訪問以文本文件格式儲存，其他替換算法只需填寫后續(xù)訪問文件的路徑，然后調(diào)用對應(yīng)算法就可以輸出命中率等結(jié)果。CP-FSM算法的換出部分基于S4LRU，因此本文修改了PyMimircache平臺默認的S4LRU算法，加入了1.3節(jié)的處理邏輯。CP-FSM算法的換入部分會按序遍歷新的訪問，以滑動窗口的方式匹配模式集合，然后調(diào)用修改后的S4LRU類，將預(yù)測的文件交給S4LRU進行相關(guān)數(shù)據(jù)結(jié)構(gòu)的維護，最后輸出緩存命中率、交換率等結(jié)果。

3.3 參數(shù)選擇

CP-FSM算法主要有匹配子序列長度（sub_len）、匹配窗口大小（window_size）和匹配間隔（interval）三個可調(diào)參數(shù)。

interval的作用是減緩匹配頻率，防止大量換入換出導(dǎo)致的內(nèi)存抖動，window_size和sub_len決定匹配到的文件數(shù)量。使用3.1.1節(jié)所獲取的fb-trace進行算法的參數(shù)選擇相關(guān)實驗，利用控制變量法控制參數(shù)變化，分別仿真在不同緩存大小下的文件訪問過程。因為模式集合的平均長度是4.63，所以window_size設(shè)置為4較為合理，同時固定interval為30，測試不同sub_len下命中率和交換率的表現(xiàn)。結(jié)果如圖6、7所示。

從圖6可以看出，sub_len越小，緩存命中率越高，這是因為sub_len越小，匹配到的模式越多，同時交換率越高，圖7的結(jié)果也證明了這一推論。sub_len的選擇確定之后，改變window_size與interval，但是保持window_size與window_size+interval的比率為0.25，結(jié)果如圖8、9所示。

從圖8可以看出，window_size越小，緩存命中率越高，相應(yīng)的交換率也越高，這是因為window_size越大，窗口內(nèi)的文件屬于同一模式的概率越高，相應(yīng)匹配到的文件也就越少，圖9的結(jié)果也證明了這一推論。確定window_size的選擇之后，需要做interval的相關(guān)實驗，控制window_size為1，sub_len為1，調(diào)整interval，結(jié)果如圖10、11所示。

綜合圖10、11可以看出，interval越小，命中率越高，但是交換率也更高，因此需要考慮命中率和交換率的平衡。

3.4 命中率和交換率對比

根據(jù)3.2節(jié)的結(jié)論，在命中率和交換率的驗證實驗中，提出算法的參數(shù)設(shè)置如下，實驗結(jié)果如圖12、13所示。

從fb-trace的仿真結(jié)果可以看出，命中率方面，傳統(tǒng)緩存替換算法普遍較好，且差距不大，算法平均命中率為32.84%～36.13%，CP-FSM算法的平均結(jié)果為46.54%，平均提升命中率32.7%。CP-FSM算法在緩存越小的情況下命中率提升越高，緩存大小為1 GB時可以超過替換算法的理論最高命中率（OPT）。緩存越大，能夠容納的熱點數(shù)據(jù)也越多，其他算法經(jīng)過維護相關(guān)數(shù)據(jù)結(jié)構(gòu)也能將熱點數(shù)據(jù)留在緩存，因此差距逐漸縮小。交換率方面，其他算法平均交換率為64.92%～61.63%，CP-FSM算法的平均結(jié)果為42.07%，平均降低了33%。因為其他算法在緩存放滿之后，都是換入一個文件的同時換出一個文件，所以交換率和命中率相加接近100%，而預(yù)取算法提前知道未來哪些文件大概率會被訪問，交換率大幅小于1減去命中率。就緩存替換算法而言，本文也曾試過將基于CP-FSM算法與ARC、LIRS等緩存替換算法相結(jié)合，但是結(jié)果并不理想，因其維護的數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜，換入時大量的緩存更新會過多地干預(yù)其維護的數(shù)據(jù)結(jié)構(gòu)，會造成算法的失效。

3.5 時效性

時效性是緩存算法性能評價中另一個需要考察的特征，該特征在大數(shù)據(jù)訪問中尤為重要。例如相關(guān)工作中提到的，基于機器學(xué)習(xí)的一些算法預(yù)測準確率高，但是算法運行時間長，可能會造成過期的預(yù)取，此類算法不能成為一個有效的算法。提出的CP-FSM算法相對于復(fù)雜的機器學(xué)習(xí)模型來說更簡單，而且使用頻繁序列挖掘算法，在 fb-trace中挖掘出54 722個頻繁序列，通過將模式表示為文件的集合，并進行模糊合并，將頻繁序列數(shù)目減少到2 452個，縮小到原來的4.48%，降低了匹配時間。

通過修改PyMimircache仿真程序，在其中加入相應(yīng)的代碼來計算緩存仿真過程中算法的平均執(zhí)行時間，其中包括獲取預(yù)取窗口訪問子序列、模式匹配以及換入換出時更新S4LRU相關(guān)數(shù)據(jù)結(jié)構(gòu)等一系列的開銷。需要注意的是，緩存文件換出僅僅抹除相應(yīng)的元數(shù)據(jù)，這部分開銷計入計算時間而不計入I/O時間。

如圖14所示，預(yù)取階段時間包括算法的計算時間和預(yù)取文件從磁盤讀到內(nèi)存的I/O時間。為了使預(yù)取有效，計算時間應(yīng)盡量短。fb-trace的統(tǒng)計結(jié)果顯示，當(dāng)預(yù)取窗口大小為1、預(yù)取間隔為6時緩存算法的平均執(zhí)行時間為0.58 ms，在算法執(zhí)行過程中，平均預(yù)取長度為3.1，平均預(yù)取大小為99.2 MB，開啟Linux direct I/O，將這部分數(shù)據(jù)繞過磁盤緩存（因為數(shù)據(jù)應(yīng)從內(nèi)存緩存讀，所以預(yù)取應(yīng)立即讀到內(nèi)存而不是磁盤緩存）直接讀到內(nèi)存的平均開銷為364.76 ms，即I/O時間。計算時間僅占預(yù)取階段總時間的0.16%。此外，頻繁序列挖掘的平均開銷為8.7 s，模糊合并的平均開銷為67 s，但是算法利用大量的文件訪問歷史進行挖掘，fb-trace是利用前7 485個文件訪問所挖掘出的模式來在后半段的trace仿真中使用，即在18 h的時間間隔后才會進行頻繁序列挖掘，充分說明算法的時效性良好。

4 結(jié)束語

針對現(xiàn)有分布式文件系統(tǒng)缺乏自適應(yīng)緩存機制，傳統(tǒng)緩存算法命中率低、交換率高，基于學(xué)習(xí)的方法耗時長、開銷大等問題，設(shè)計并實現(xiàn)了一種基于頻繁序列挖掘的文件系統(tǒng)緩存算法CP-FSM。本文通過更換模式表示法進行模糊合并、基于模式全集的預(yù)取等方法優(yōu)化算法的命中率和時間開銷。在公開trace集上的實驗表明，與傳統(tǒng)緩存算法相比，CP-FSM能明顯提高緩存命中率、同時降低交換率，在緩存較小的情況下效果更好。由于頻繁序列挖掘中的支持度不能設(shè)置過小，如果設(shè)置較小會造成頻繁序列過多，來不及匹配的情況。而例如將支持度選為5，就會漏掉出現(xiàn)次數(shù)為2～4的熱點文件。所以下一步的研究將著眼于利用出現(xiàn)次數(shù)大于等于2的文件。

參考文獻：

[1]Shvachko K， Kuang H， Radia S， et al. The Hadoop distributed file system[C]//Proc of the 26th Symposium on Mass Storage Systems and Technologies.2010：1-10.

[2]Apache Software Foundation. HDFS centralized cache management[EB/OL].（2016）.https：//hadoop.apache.org/docs/stable/hadoop-project-dist/hadoop-hdfs/CentralizedCacheManagement.html.

[3]Alluxio Open Foundation. Alluxio an open source memory speed virtual distributed storage[EB/OL].（2016）.http：//www.alluxio.org/.

[4]Zhu Bohong， Chen Youmin， Wang Qing， et al. Octopus+： an RDMA-enabled distributed persistent memory file system[J].ACM Transactions on Storage，2017，17（3）：article No.19.

[5]Floratou A， Megiddo N， Potti N， et al. Adaptive caching in big SQL using the HDFS cache[C]//Proc of the 7th ACM Symposium on Cloud Computing.New York：ACM Press，2016：321-333.

[6]Megiddo N， Modha D S. ARC： a self-tuning， low overhead replacement cache[EB/OL].（2003-11-07）.https：//www.usenix.org/legacy/events/fast03/tech/megiddo.html.

[7]Jiang Song， Zhang Xiaodong. LIRS： an efficient low inter-reference recency set replacement policy to improve buffer cache performance[J].ACM SIGMETRICS Performance Evaluation Review，2002，30（1）：31-42.

[8]Zhou Yuanyuan， Philbin J， Li Kai. The multi-queue replacement algorithm for second level buffer caches[C]//Proc of General Track：USENIX Annual Technical Conference.2001：91-104.

[9]Joo M， Lee W. WebProfiler： user interaction prediction framework for web applications[J].IEEE Access，2019，7：154946-154958.

[10]Gellert A. Web access mining through dynamic decision trees with Markovian features[J].Journal of Web Engineering，2017，16（5-6）：524-536.

[11]Tanzil S M S， Hoiles W， Krishnamurthy V. Adaptive scheme for ca-ching YouTube content in a cellular network： machine learning approach[J].IEEE Access，2017，5：5870-5881.

[12]Narayanan A， Verma S， Ramadan E， et al. DeepCache： a deep learning based framework for content caching[C]//Proc of Workshop on Network Meets AI amp; ML.2018：48-53.

[13]Vietri G， Rodriguez L V， Martinez W A， et al. Driving cache replacement with ML-based LeCaR[C]//Proc of the 10th USENIX Conference on Hot Topics in Storage and File Systems.2018.

[14]Wu Guojin， Deng Yuhui， Qin Xiao. Using provenance to boost the metadata prefetching in distributed storage systems[C]//Proc of the 34th International Conference on Computer Design.Piscataway，NJ：IEEE Press，2016：80-87.

[15]陳友旭.分布式文件系統(tǒng)中元數(shù)據(jù)管理優(yōu)化[D].合肥：中國科學(xué)技術(shù)大學(xué)，2019：9-12.（Chen Youxu. Optimization of metadata ma-nagement in distributed file system[D].Hefei：University of Science and Technology of China，2019：9-12.）

[16]Li Zhenmin， Chen Zhifeng， Srinivasan S M， et al. C-miner：mining block correlations in storage systems[C]//Proc of the 3rd USENIX Conference on File and Storage Technologies.2004：173-186.

[17]錢能武，郭衛(wèi)斌，范貴生.基于關(guān)聯(lián)規(guī)則挖掘的分布式小文件存儲方法[J].華東理工大學(xué)學(xué)報：自然科學(xué)版，2016，42（5）：708-714.（Qian Nengwu， Guo Weibin， Fan Guisheng. Distributed small file storage method based on association rule mining[J].Journal of East China University of Science and Technology：Natural Science，2016，42（5）： 708-714.）

[18]Yang Juncheng， Karimi R， Smundsson T， et al. MITHRIL： mining sporadic associations for cache prefetching[C]//Proc of Symposium on Cloud Computing.2017：66-79.

[19]于躍.基于Hadoop平臺的并行化分布式關(guān)聯(lián)規(guī)則挖掘算法研究[D].長春：吉林大學(xué)，2017：1-6.（Yu Yue. Research on parallel distributed association rule mining algorithm based on Hadoop platform[D].Changchun：Jilin University，2017：1-6.）

[20]Chen Yanpei， Ganapathi A， Griffith R， et al. The case for evaluating mapreduce performance using workload suites[C]//Proc of the 19th Annual International Symposium on Modelling， Analysis， and Simulation of Computer and Telecommunication Systems.Piscataway，NJ：IEEE Press，2011：390-399.

[21]Chen Yanpei， Alspaugh S， Katz R. Interactive analytical processing in big data systems： a cross-industry study of mapreduce workloads[EB/OL].（2012-08-21）.https：//arxiv.org/abs/1208.4174.

[22]Chen Yanpei， Sara A， Archana G， et al. SWIM： statistical workload injector for MapReduce[EB/OL].（2016）[2021-09-07].https：//github.com/SWIMProjectUCB/SWIM/wiki.

[23]Iris M， Klaus B， Rainer G， et al. MG-FSM： large-scale frequent sequence mining[EB/OL].（2015）[2021-09-07].https：//www.mpi-inf.mpg.de/departments/databases-and-information-systems/software/mg-fsm.

[24]Yang Juncheng， Reza K， Trausti S， et al. PyMimircache：a Python3 cache analysis platform[EB/OL].（2017）[2021-09-07].https：//github.com/1a1a11a/PyMimircache.