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

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

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

?

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

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

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

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

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

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

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

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

1 相關(guān)研究

1.1 小文件解決方案

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

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

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

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

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

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

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

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

2 ARMFS架構(gòu)

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

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

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

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

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

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

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

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

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

表1 審計(jì)日志示例Table 1 Examples of audit logs

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

算法1 審計(jì)日志預(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) }

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

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

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

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

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

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

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

算法2 審計(jì)日志挖掘算法

輸入: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);∥得到頻繁項(xiàng)集和強(qiáng)關(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);

∥按頻繁集的項(xiàng)集個(gè)數(shù)進(jìn)行排序

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

(13) pre_table=Rk;

(14) return fre_table,merge_table,pre_table;

(15) }

應(yīng)用以上算法對(duì)表2中審計(jì)事務(wù)集進(jìn)行挖掘,其中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ù)取機(jī)制表Table 5 pre_table

3.3 小文件合并算法

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

在小文件合并算法中,將merge_table作為輸入?yún)?shù),通過遍歷 merge_table中的每一條記錄,將記錄中的小文件打包在一起進(jìn)行合并存儲(chǔ)。如果一條記錄合并后空間沒有達(dá)到64 M,則繼續(xù)向該塊中添加下一條merge_table記錄中小文件,其中merge_table一條記錄中的小文件作為一個(gè)整體,如果添加進(jìn)去沒有超過64 M,并且該添加記錄中小文件都不進(jìn)行合并存儲(chǔ),而是進(jìn)行下一次合并存儲(chǔ)操作,以此保證每條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并行編程實(shí)現(xiàn)小文件合并算法[12]。Map算法是將單個(gè)小文件輸入,每個(gè)合并小文件屬于merge_table的一條記錄中,對(duì)應(yīng)一條記錄中的小文件用merge_key進(jìn)行標(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記錄的小文件合并在一起,最后存儲(chǔ)至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)訪問到該文件時(shí),系統(tǒng)會(huì)預(yù)取與其相關(guān)聯(lián)的文件到緩存當(dāng)中。本文指fre_table中強(qiáng)關(guān)聯(lián)規(guī)則左邊的文件。如f1=>{f3,f4},則f1就是觸發(fā)文件。

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

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

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

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

輸入:fre_table,pre_able

輸出:pre_files

(1) prefetch(){

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

(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存在緩存污染等弊端。因此,本文提出了一個(gè)基于關(guān)聯(lián)規(guī)則的全新緩存替換算法(Association Rules Prefetching,ARP)。

ARP針對(duì)被訪問的TriggerFile,添加一個(gè)參數(shù)rencentTime用于記錄最近訪問時(shí)間。每次訪問了TriggerFile就需要將其關(guān)聯(lián)的RelatedFiles調(diào)入緩存中,如果緩存已滿則需要置換緩存中的“無用數(shù)據(jù)”。算法分為兩步:首先查找當(dāng)前時(shí)間和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) //時(shí)間差

(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ù)值實(shí)驗(yàn)

5.1 實(shí)驗(yàn)軟硬件環(huán)境

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

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

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

5.2 支持度大小的選取

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

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

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

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

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

通過實(shí)驗(yàn)數(shù)據(jù)計(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ù)量不斷上升時(shí),相對(duì)于HAR進(jìn)一步優(yōu)化了內(nèi)存使用,說明ARMFS針對(duì)海量的小文件具有更強(qiáng)的適應(yīng)性。

5.4 文件下載速度對(duì)比測試

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

圖3 HDFS和ARMFS下載時(shí)間對(duì)比Fig.3 Download time of HDFS and ARMFS

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

5.5 緩存置換算法對(duì)比測試

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

圖4 LRU、LFU和ARMFS下載時(shí)間對(duì)比Fig.4 Download time of LRU,LFU and ARMFS

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

6 結(jié)束語

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

[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實(shí)戰(zhàn)[M].北京:機(jī)械工業(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].計(jì)算機(jī)工程學(xué)報(bào),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-)，男，安徽蕪湖人，碩士生，研究方向?yàn)榉植际轿募鎯?chǔ)。 E-mail:1173618916@qq.com

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

TP316.4

A