錢能武, 郭衛(wèi)斌, 范貴生

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

?

基于關(guān)聯(lián)規(guī)則挖掘的分布式小文件存儲方法

錢能武, 郭衛(wèi)斌, 范貴生

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

Hadoop分布式文件系統(tǒng)(HDFS)設(shè)計之初是針對大文件的處理,但無法高效地針對小文件進行存儲，因此提出了一種基于關(guān)聯(lián)規(guī)則挖掘的高效的小文件存儲方法——ARMFS。ARMFS通過對Hadoop系統(tǒng)的審計日志進行關(guān)聯(lián)規(guī)則挖掘,獲得小文件間的關(guān)聯(lián)性,通過文件合并算法將小文件合并存儲至HDFS;在請求HDFS文件時,根據(jù)關(guān)聯(lián)規(guī)則挖掘得到的高頻訪問表和預(yù)取機制表提出預(yù)取算法來進一步提高文件訪問效率。實驗結(jié)果表明,ARMFS方法明顯提高了NameNode的內(nèi)存使用效率,對于小文件的下載速度和訪問效率的改善十分有效。

HDFS; 關(guān)聯(lián)規(guī)則挖掘; 小文件關(guān)聯(lián)性; 預(yù)取

Hadoop分布式文件系統(tǒng)(HDFS)是一種Master/Slave主從式結(jié)構(gòu),一個HDFS系統(tǒng)由一個NameNode節(jié)點和若干個DataNode節(jié)點組成。其中文件的元數(shù)據(jù)(MeteData)信息存放在系統(tǒng)NameNode節(jié)點的內(nèi)存中,這樣就導(dǎo)致了文件的存儲規(guī)模受到內(nèi)存大小的限制。例如,對于每1個文件HDFS存儲的MeteData信息大約150 Byte,此時若有約107份大小為1 M的小文件存儲至HDFS中,則將產(chǎn)生約1.4 G的元數(shù)據(jù)[1]。大量的小文件對于內(nèi)存的消耗極大,同時大量的元數(shù)據(jù)對于數(shù)據(jù)的讀取也會產(chǎn)生影響,從而影響整個系統(tǒng)的效率。

現(xiàn)實環(huán)境中,人們存取小文件的概率極大,如Office文檔、音樂文件、PDF文件等,其中絕大數(shù)的文件均小于5 MB。Dong等[2]通過實驗證明了小文件在小于4.35 MB這個閾值時將明顯降低HDFS的文件存儲效率,所以,有效地解決HDFS中小文件存儲問題具有非常重要的實際意義。

針對Hadoop系統(tǒng)中小文件存儲問題,本文提出了一種基于關(guān)聯(lián)規(guī)則挖掘的高效的小文件存儲方法——ARMFS(Association Rule Mining File System)。通過對Hadoop系統(tǒng)的審計日志進行關(guān)聯(lián)規(guī)則挖掘,獲得小文件間的關(guān)聯(lián)性;通過小文件的關(guān)聯(lián)性,文件合并算法將小文件合并壓縮存儲至HDFS;在關(guān)聯(lián)規(guī)則挖掘的過程中,得到高頻訪問表和預(yù)取機制表,在訪問HDFS文件時,基于高頻訪問表和預(yù)取機制表提出預(yù)取算法將文件預(yù)取至緩存中,從而有效地提高文件的訪問效率。

1 相關(guān)研究

1.1 小文件解決方案

目前,解決Hadoop小文件存儲的方法主要有3類:HAR小文件歸檔技術(shù)、Sequence file序列化二進制文件技術(shù)和自定義的CombineFile文件合并技術(shù)[3]。

HAR小文件歸檔技術(shù)是一個將小文件放入HDFS塊中的文件存檔工具,它能夠?qū)⒍鄠€小文件打包成一個HAR文件,減少NameNode內(nèi)存使用。HAR文件一旦創(chuàng)建便不可改變,且存檔文件不支持壓縮,有很大的局限性。

Sequence file由一系列的二進制key/value組成,如果key為小文件名,value為文件內(nèi)容,則可以將大批小文件合并成一個大文件。因為無大文件到小文件的索引,所以每次訪問需要遍歷整個Sequence大文件,訪問效率低下。

CombineFile可以自定義文件輸入格式,將多個文件合并成一個塊，但是它本身是一個抽象類,使用該方法需要自己進行實現(xiàn)。

1.2 關(guān)聯(lián)規(guī)則挖掘

實際應(yīng)用中,如果某一用戶訪問一個包含多個小文件(如圖片、文本、音頻等)的網(wǎng)頁,則屬于該網(wǎng)頁的所有小文件都將被訪問。這些屬于同一網(wǎng)頁的小文件具有較強的關(guān)聯(lián)性,如果將該類強關(guān)聯(lián)性的小文件合并在一起進行存儲,既能提高存儲效率也能提高訪問效率。

關(guān)聯(lián)規(guī)則挖掘正是查找數(shù)據(jù)間“親密度”的一種數(shù)據(jù)挖掘算法。通過對審計日志的挖掘,挖掘出具有較強關(guān)聯(lián)性的小文件,再將具有較強關(guān)聯(lián)性的小文件進行合并存儲。關(guān)聯(lián)規(guī)則算法是一種十分經(jīng)典的數(shù)據(jù)挖掘算法,其中Apriori算法是一種最具影響力的挖掘關(guān)聯(lián)規(guī)則的算法[4]。挖掘過程分為兩步:一是查找頻繁項集,二是產(chǎn)生強關(guān)聯(lián)規(guī)則。

目前,對于Apriori算法的研究已經(jīng)十分深入,無論是算法本身的優(yōu)化,還是并行化實現(xiàn)[5-7]。本文提出的方法是在Hadoop分布式平臺下,基于Mao等[8]提出的一種高效的并行Apriori算法——AprioriPMP。

2 ARMFS架構(gòu)

ARMFS包含3個模塊:審計日志挖掘模塊、小文件合并模塊和小文件預(yù)取模塊,如圖1所示。

圖1 ARMFS架構(gòu)Fig.1 Architecture of ARMFS

(1) 審計日志挖掘模塊。首先是針對 Hadoop審計日志進行預(yù)處理后生成審計事務(wù)集,通過審計事務(wù)集挖掘小文件間的關(guān)聯(lián)性,得到合并集合表、高頻訪問表和預(yù)取機制表。

(2) 小文件合并模塊。通過得到的合并集合表,將具有強關(guān)聯(lián)性的小文件進行合并存儲至HDFS。

(3) 小文件預(yù)取模塊。在初始讀取文件時,通過高頻訪問表將高頻訪問文件放入緩存。文件讀取過程中,使用預(yù)取機制表中的信息,將可能會訪問的文件信息放入緩存中。

3 審計日志的關(guān)聯(lián)規(guī)則挖掘

3.1 審計日志的預(yù)處理

很多情況下各個小文件間是有關(guān)聯(lián)性的,例如,一個網(wǎng)頁頁面包含圖片A和圖片B兩個圖片文件,則在訪問該網(wǎng)頁時,圖片A、B都將被訪問到。如果圖片A、B存儲在HDFS中,則很難發(fā)現(xiàn)A和B之間的關(guān)聯(lián)性,但是可以通過對文件歷史訪問記錄來得到文件間的關(guān)聯(lián)性。而尋找其中的關(guān)聯(lián)性需使用Apriori算法。

Hadoop中對于訪問文件的請求均記錄在NameNode的審計日志中,Hadoop的默認審計日志是處于關(guān)閉狀態(tài)的,可以通過log4j.properties修改audit=INFO即可打開審計日志功能,這樣就可以實現(xiàn)記錄文件系統(tǒng)所有文件訪問請求的功能[9]。審計日志示例如表1所示。

表1 審計日志示例Table 1 Examples of audit logs

參考關(guān)聯(lián)規(guī)則挖掘在Web日志中的應(yīng)用,將得到的訪問日志進行預(yù)處理,根據(jù)不同的用戶即IP的訪問記錄分別生成一條對應(yīng)的訪問事務(wù),同時設(shè)置一個時間間隔閾值timeout[10]。Catledge等[11]通過實驗驗證了timeout設(shè)置為25.5 min時會得到較好的性能效果,一般將timeout設(shè)置為30 min。同一個IP訪問超過timeout的話則重新生成一條記錄。其算法描述如算法1所示。

算法1 審計日志預(yù)處理

輸入:logs

輸出:T{T1,T2,T3,…}

(1) Preprocess(logs){ //預(yù)處理

(2) for log in logs{

(3) if(log.ip is new){ ∥新用戶判定

(4) newTi;

(5)Ti.add(log.file);

(6) }

(7) else if(prelog.time-log.time

(8)Ti.add(log.file);

(9) else{ //超過timeout的生成新事務(wù)

(10) newTi;

(11)Ti.add(log.file);

(12) }

(13) }

(14)T={T1,T2,T3，…};

(15) returnT;

(16) }

針對表1中的示例,可得到審計事務(wù)集,如表2所示。

表2 審計事務(wù)集Table 2 Audit transaction set

3.2 基于關(guān)聯(lián)規(guī)則的審計日志挖掘算法

對預(yù)處理后得到的審計事務(wù)集進行關(guān)聯(lián)規(guī)則挖掘,本文使用了AprioriPMR并行關(guān)聯(lián)規(guī)則算法,運行在Hadoop平臺上,只需掃描2次數(shù)據(jù)庫即可得到頻繁項集。通過對關(guān)聯(lián)規(guī)則挖掘的結(jié)果進行處理得到自己想要的結(jié)果,結(jié)果分為3個部分:合并集合表、高頻訪問表和預(yù)取機制表。

合并集合表(Merge file table,merge_table)是用于記錄合并在一起存儲的文件名的記錄表,其中每一條記錄對應(yīng)一個合并文件集。對挖掘出的頻繁項集進行篩選,其篩選過程如下:首先取頻繁k-項集(k>K/2,K表示最大頻繁k-項集的項集數(shù)),先按項集k的大小進行排序;其次是在排序過程中刪除重復(fù),即前面已經(jīng)出現(xiàn)過的項集再次出現(xiàn)時則刪除該項集。篩選后的頻繁項集作為合并項集放入到合并集合表中。同時因為頻繁k-項集的k>K/2,所以得到的合并項集文件個數(shù)適中,不會出現(xiàn)文件數(shù)較少而進行合并的情況。例如:頻繁2-項集,只有2個文件合并,從而影響合并效率。

高頻訪問表(Frequent access table,fre_table)是用于記錄審計日志中被訪問次數(shù)最多的文件。其主要是針對得到的頻繁1-項集按支持度進行排序,取出前N項作為高頻訪問表。

預(yù)取機制表(Prefetch table,pre_table)是記錄強關(guān)聯(lián)規(guī)則的表。從大于置信度的強關(guān)聯(lián)規(guī)則中,選擇由單個項集作為前提條件的,如f1=>{f3,f4}形式,而非{f1,f2}=>{f3,f4},認為某個用戶訪問了f1后必然會訪問f3和f4。對于篩選后的強關(guān)聯(lián)規(guī)則由置信度大小進行排序,最終將這些規(guī)則放入預(yù)取機制表中。基于關(guān)聯(lián)規(guī)則的審計日志挖掘算法描述如算法2所示。

算法2 審計日志挖掘算法

輸入:T{T1,T2,T3,…},mini_sup,mini_conf，N

輸出:merge_table,fre_table,pre_table

(1) Logs_Mining(){

(2) AprioriPMP(T,mini_sup,mini_conf);

(3) get(Lk,Rk);∥得到頻繁項集和強關(guān)聯(lián)規(guī)則

(4)L1=Sort(L1,sup_num);

(5) fre_table=get(L1,N);

(6)K=max(Lk.itemNum)

(7) forLinLk{

(8) if(L.itemNum>K/2)

(9) merge_table.add(L);

(10) }

(11) SortByItemsNum(merge_table);

∥按頻繁集的項集個數(shù)進行排序

(12) Distinct(merge_table); ∥去重操作

(13) pre_table=Rk;

(14) return fre_table,merge_table,pre_table;

(15) }

應(yīng)用以上算法對表2中審計事務(wù)集進行挖掘,其中mini_su設(shè)置為2,mini_conf設(shè)置為60%,可得到merge_table、fre_table和pre_table,如表3～5所示。

表3 合并集合表Table 3 merge_table

表4 高頻訪問表Table 4 fre_table

表5 預(yù)取機制表Table 5 pre_table

3.3 小文件合并算法

通過審計日志的挖掘得到合并集合表用于小文件的合并存儲。通過對審計日志的關(guān)聯(lián)規(guī)則的挖掘得到了合并項集表,可以知道合并項集中的文件具有很強的“親密度”,就可以將合并項集表中的對應(yīng)小文件進行合并存儲。

在小文件合并算法中,將merge_table作為輸入?yún)?shù),通過遍歷 merge_table中的每一條記錄,將記錄中的小文件打包在一起進行合并存儲。如果一條記錄合并后空間沒有達到64 M,則繼續(xù)向該塊中添加下一條merge_table記錄中小文件,其中merge_table一條記錄中的小文件作為一個整體,如果添加進去沒有超過64 M,并且該添加記錄中小文件都不進行合并存儲,而是進行下一次合并存儲操作,以此保證每條merge_table記錄中小文件的整體性。其算法描述見算法3。

算法3 小文件合并算法

輸入:files,merge_table

輸出:HDFS blocks

(1) merge_Files (){

(2) while(merge_table){∥遍歷merge_table

(3) if(file in merge_table)

(4) if(mergeFiles.Size<64 M)

(5) mergeFiles.add(file);

(6) blocks=merge(mergeFiles);

(7) store blocks in HDFS;

(8) }

(9) }

可以發(fā)現(xiàn)該合并算法可以并行化操作,通過MapReduce并行編程實現(xiàn)小文件合并算法[12]。Map算法是將單個小文件輸入,每個合并小文件屬于merge_table的一條記錄中,對應(yīng)一條記錄中的小文件用merge_key進行標(biāo)記。則Map的輸出是< merge_key,file_context >。小文件合并的Map算法描述見算法4。

算法4 小文件合并Map算法

輸入:files,merge_table

輸出:

(1) merge_Map(){

(2) while(merge_table){

(3) for file in merge_table{

(4) write(merge_key,file_context)

(5) }

(6) }

(7) }

Reduce操作就是將Map任務(wù)的輸出結(jié)果作為輸入,通過合并相同的merge_key,即將屬于同一條merge_table記錄的小文件合并在一起,最后存儲至HDFS。小文件合并的Reduce算法描述見算法5。

算法5 小文件合并Reduce算法

輸入:

輸出:HDFS mergeFile

(1) merge_Reduce (){

(2) for key1 in merge_keyList{

(3) mergeFiles.add(file_context);

(4) for in

file_context>List{

(5) if(key1 == key2 )

(6) if(mergeFiles<64 M)

(7) mergeFiles.add(file_context);

(8) mergeFile(mergeFiles);

(9) store mergeFile in HDFS;

(10) }

(11) }

(12) }

4 小文件的預(yù)取與緩存

4.1 小文件預(yù)取算法

定義1 觸發(fā)文件(TriggerFile):當(dāng)訪問到該文件時,系統(tǒng)會預(yù)取與其相關(guān)聯(lián)的文件到緩存當(dāng)中。本文指fre_table中強關(guān)聯(lián)規(guī)則左邊的文件。如f1=>{f3,f4},則f1就是觸發(fā)文件。

定義2 關(guān)聯(lián)文件(RelatedFiles):和觸發(fā)文件相關(guān)聯(lián)的文件,當(dāng)觸發(fā)文件被訪問,其將會被預(yù)取到緩存中的文件。本文指fre_table中強關(guān)聯(lián)規(guī)則右邊的文件。如f1=>{f3,f4},則{f3,f4}就是關(guān)聯(lián)文件。

TriggerFile和RelatedFiles是成對出現(xiàn)的,如f1=>{f3,f4}這個強關(guān)聯(lián)規(guī)則,f1是{f3,f4}的觸發(fā)文件,而{f3,f4}是f1的關(guān)聯(lián)文件。

本文提出的小文件預(yù)取算法包括兩個步驟:第1步是在文件讀取開始階段,將fre_table中高頻訪問文件放入緩存中;第2步是在文件的讀取進行階段,當(dāng)TriggerFile被訪問了,則通過緩存置換算法ARP與TriggerFile相對應(yīng)的RelatedFiles置換到緩存中。其算法描述見算法6。

算法6 小文件預(yù)取算法

輸入:fre_table,pre_able

輸出:pre_files

(1) prefetch(){

(2) if(first_vist) ∥是否是首次進行讀取操作

(3) cache.set(fre_table);

(4) else{

(5) if(TriggerFile){ //觸發(fā)文件預(yù)取操作

(6) cache.ARP (RelatedFiles);

(7) }

(8) }

(9) }

4.2 緩存置換算法

緩存資源是有一定限度的,并不能無限地將要預(yù)取的文件放入緩存中,這就需要一種緩存置換策略,將利用率較低的文件置換出緩存。

常見的置換算法主要有兩種:最近最少使用(LRU)和最近頻繁使用(LFU)算法[13-14]。LRU存在局部性限制,LFU存在緩存污染等弊端。因此,本文提出了一個基于關(guān)聯(lián)規(guī)則的全新緩存替換算法(Association Rules Prefetching,ARP)。

ARP針對被訪問的TriggerFile,添加一個參數(shù)rencentTime用于記錄最近訪問時間。每次訪問了TriggerFile就需要將其關(guān)聯(lián)的RelatedFiles調(diào)入緩存中,如果緩存已滿則需要置換緩存中的“無用數(shù)據(jù)”。算法分為兩步:首先查找當(dāng)前時間和rencentTime的差值,超過閾值T的置換出緩存;其次是比較TriggerFile在pre_table中的置信度大小,置信度小的話說明訪問的可能性低,將其置換出內(nèi)存。如果沒有找到可以置換的文件則不做預(yù)取操作。算法描述見算法7。

算法7 緩存置換算法

輸入:TriggerFile,RelatedFiles,pre_table

輸出:cache file

(1) ARP(TriggerFile,RelatedFiles,pre_table){

(2) if(cache.available | | TriggerFile.exit){

(3) RelatedFiles.recenttime=now;

(4) cache.put(RelatedFiles);

(5) else{

(6) for(trigFile in cache){

(7) if(now-recentTime>T) //時間差

(8) exchange(trigFile.RelatedFiles);

(9) cache.add(RelatedFiles);

(10) if(trigFile.conf< TriggerFile.conf)

//置信度比較

(11) exchange(trigFile.RelatedFiles);

(12) cache.add(RelatedFiles);

(13) }

(14)}

5 數(shù)值實驗

5.1 實驗軟硬件環(huán)境

實驗使用兩臺Win Server 08服務(wù)器,共搭建了4個節(jié)點,1個Master節(jié)點和3個Slave節(jié)點。Master節(jié)點位于其中1臺服務(wù)器上,其CPU為Intel(R) Xeon E5620,內(nèi)存16 GB,主頻2.40 GHz;3個Slave節(jié)點位于另外1臺服務(wù)器,其CPU為Intel(R) Xeon E5620,內(nèi)存16 GB,主頻2.40 GHz。

使用在虛擬機中搭建的Ubuntu系統(tǒng)作為節(jié)點。實驗使用的虛擬機是VMware Workstation 9.0,操作系統(tǒng)是Ubuntu desktop 12.10,Hadoop的版本是Hadoop 1.0.4,JDK 版本為1.6,OpenSSH版本6.0。

實驗選取了5種不同格式的小文件,平均大小約為1 MB,通過預(yù)處理得到2 000、4 000、6 000、8 000、10 000份測試文件,分別將測試數(shù)據(jù)上傳至HDFS。對于ARMFS算法,通過隨機模擬訪問生成約106條的審計日志記錄,分別針對2 000、4 000、6 000、8 000、10 000份測試文件進行數(shù)據(jù)測試實驗。

5.2 支持度大小的選取

選擇支持度大小時,盡量以能得到好的合并項集為目標(biāo),這樣就能更好地實現(xiàn)小文件間的合并。如果得到的合并項集中大多數(shù)合并集的個數(shù)為60個左右,即合并文件的大小為60 MB左右,就很接近一個數(shù)據(jù)塊的大小(64 MB),合并效果及合并效率將更高。

實驗中發(fā)現(xiàn),支持度的大小與文件的平均訪問次數(shù)有很大的關(guān)系,如:106條記錄對于2 000個文件,平均訪問次數(shù)是500次,而對于10 000個文件則是100次,支持度定位在平均訪問次數(shù)的10%較為合理。接下來的實驗中,支持度的大小都是按照此規(guī)則制定,而置信度大小都取為60%。

5.3 內(nèi)存使用對比測試

分別對2 000、4 000、6 000、8 000、10 000份小文件隨機產(chǎn)生了約100萬條審計日志,在HDFS、HAR和ARMFS環(huán)境下進行實驗。HAR和ARMFS需要進行小文件合并存儲的操作,實驗中記錄在3種環(huán)境下文件對于NameNode主內(nèi)存的消耗情況,其結(jié)果如圖2所示。

圖2 HDFS、HAR和ARMFS內(nèi)存使用對比Fig.2 Memory use of HDFS,HAR and ARMFS

通過實驗數(shù)據(jù)計算,HDFS、HAR和ARMFS的平均文件占內(nèi)存大小為0.016、0.002 1、0.001 5 MB。從圖2也可以看出，HDFS內(nèi)存消耗較大,HAR技術(shù)能有效改善內(nèi)存使用率,而ARMFS在數(shù)據(jù)量不斷上升時,相對于HAR進一步優(yōu)化了內(nèi)存使用,說明ARMFS針對海量的小文件具有更強的適應(yīng)性。

5.4 文件下載速度對比測試

對小文件合并存儲后,分別對2 000、4 000、6 000、8 000、10 000份小文件進行訪問下載實驗,根據(jù)審計日志的內(nèi)容獲取2 000、4 000、6 000、8 000、10 000份小文件到本地中。文件下載時間如圖3所示。

圖3 HDFS和ARMFS下載時間對比Fig.3 Download time of HDFS and ARMFS

通過實驗數(shù)據(jù)計算,HDFS和ARMFS的平均下載時間為0.038 s和0.016 s。從圖3中也可以直觀地看出,ARMFS相對于HDFS在下載效率上有很大的提升,速度提升了約57.9%,說明ARMFS能很好地預(yù)取文件,提升文件的下載效率。

5.5 緩存置換算法對比測試

ARMFS方法提出了一個全新的緩存置換算法ARP,將其與傳統(tǒng)的LRU和LFU算法進行對比測試。同樣在實驗中根據(jù)審計日志的內(nèi)容去獲取2 000、4 000、6 000、8 000、10 000份小文件到本地中,實驗結(jié)果如圖4所示。

圖4 LRU、LFU和ARMFS下載時間對比Fig.4 Download time of LRU,LFU and ARMFS

通過實驗數(shù)據(jù)計算,LRU、LFU和ARMFS的平均文件下載速度為0.025 、0.023 、0.016 s。從圖4可以看出,使用LRU和LFU基本沒有差別,但ARMFS相對于LRU和LFU具有一定的效率提升,說明緩存置換算法ARP在緩存置換中有一定優(yōu)勢,能提高緩存命中率。

6 結(jié)束語

本文提出了一種基于關(guān)聯(lián)規(guī)則的分布式小文件存儲方法ARMFS,有效地解決了HDFS中存在的小文件存儲問題。該方法使用關(guān)聯(lián)規(guī)則挖掘算法挖掘小文件的審計日志,從而發(fā)現(xiàn)小文件間的關(guān)聯(lián)性,在小文件合并過程中關(guān)聯(lián)性強的小文件進行合并存儲在一起。同時,ARMFS也提出了新的緩存置換算法ARP。實驗表明,ARMFS能夠顯著減少NameNode的內(nèi)存消耗,有效地提高了小文件的下載速度和訪問效率。該方法也存在不足之處,如在緩存置換算法中,未考慮文件訪問次數(shù)和文件大小等因素，接下來,將對此進行改進,進一步提高文件的訪問效率。

[1] KONSTANTIN S,HAIRAING K,SANYJY R,etal.The Hadoop distributed file system[C]//Proceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies(MSST).USA:IEEE,2010:1-10.

[2] DONG Bo,QIU Jie,ZHENG Qinghua,etal.A novel approach to improving the efficiency of storing and accessing samll fileson Hadoop:A case study by PowerPoint files[C]//IEEE International Conference on Services Computing.Miami:IEEE,2010:65-72.

[3] LIU Xuhui,HAN Jizhong,ZHONG Yunqin,etal.Implementing WebGIS on Hadoop:A case study of improving small file I/O performance on HDFS[C]//∥IEEE International Conference on Cluster Computing and WorkShops.Piscataway:IEEE,2009:1-8.

[4] TAN P N,MICHAEL S,VIPIN K.數(shù)據(jù)挖掘?qū)д揫M].北京:人民郵電出版社,2013:201-240.

[5] AOUAD L M,LE-KHAC N A,KECHADI T M.Performance study of distributed apriori-like frequent itemsets mining[J].Knowledge and Information Systems,2010,23(1):55-72.

[6] TAO Limin,HUANG Linpeng.Cherry:Analgorithm for mining frequent closed itemsets without subset checking[J].Journal of Software,2008,19(2):379-388.

[7] SHANKAR S,PURUSOTHAMAN T.Utility sentient frequent mining and association rule mining:A literature survey and comparative study[J].International Journal of Soft Computing Applications,2009,4:81-95.

[8] MAO Weijun,GUO Weibin.An improved association rules mining algorithm based on power set and Hadoop[C]// 2013 International Conference on Information Science and Cloud Computing Companion(ISCC-C).Guangzhou:IEEE,2013:236-241.

[9] 陸嘉恒.Hadoop實戰(zhàn)[M].北京:機械工業(yè)出版社,2014:196-197.

[10] ZHU T S.Web usage mining for Internet recommendation[D].Canada:University of Alberta Edmonton,2001.

[11] CATLEDGE L D,PITKOW J E.Characterizing browsing stratagies in the word-wide Web[J].Computer Networks and ISDN Systems,1995,27(6):1065-1073.

[12] 黃宜華,苗凱翔.深入理解大數(shù)據(jù)[M].北京:中國電影出版社,2014:91-122.

[13] TANTER E,FIGUEROA I,TABAREAU N.Execution levels for aspect-oriented programming:Design,semantics,implementations and applications[J].Science of Computer Programming,2014,80(2):311-342.

[14] 鮑東星,李曉明.一種基于LRU的高速緩存方案研究[J].計算機工程學(xué)報,2007,33(9):272-274.

Approach of Distributed Small File Storage Based on Association Rule Mining

QIAN Neng-wu, GUO Wei-bin, FAN Gui-sheng

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Hadoop distributed file system (HDFS) is previously designed for large file processing,but it is not effective for small file storage.This paper proposes an efficient method of distributed small file storage by means of association rule mining and named ARMFS.By analyzing the audit logs to obtain the association of small files,these small files are merged and compressed to HDFS via file merge algorithm.When requesting HDFS file,the prefetching algorithm is further proposed to improve the access efficiency according to the high frequency access table and prefetching table that is based on association rules.The experiment results show that the ARMFS method can significantly improve the memory efficiency on NameNode and the access efficiency of the small file on HDFS.

HDFS; association rule mining; the association of small files; prefetching

1006-3080(2016)05-0708-07

10.14135/j.cnki.1006-3080.2016.05.019

2015-11-18

國家自然科學(xué)基金(61300041,61272198)

錢能武(1990-)，男，安徽蕪湖人，碩士生，研究方向為分布式文件存儲。 E-mail:1173618916@qq.com

郭衛(wèi)斌，E-mail:gweibin@ecust.edu.cn

TP316.4

A