一種基于頻繁項挖掘的大量小文件動態(tài)合并算法

周 斌，畢傳美

(中南民族大學 計算機科學學院，武漢430074)

一種基于頻繁項挖掘的大量小文件動態(tài)合并算法

周 斌，畢傳美

(中南民族大學 計算機科學學院，武漢430074)

分析了當前社交網(wǎng)絡(luò)中大量小文件數(shù)據(jù)特點，將訪問日志與數(shù)據(jù)挖掘相結(jié)合，提出了一種基于頻繁項挖掘的大量小文件動態(tài)合并算法.此算法實現(xiàn)小文件動態(tài)合并，解決了合并文件的一致性問題，從而預(yù)測用戶下一步的訪問，為預(yù)取小文件做引導(dǎo)，提高預(yù)取的命中率.針對預(yù)取和緩存的文件過多的特點，設(shè)計了一種新的含循環(huán)單鏈表的緩存置換算法優(yōu)化緩存內(nèi)容.通過實驗證明，該算法大量小文件動態(tài)合并性能優(yōu)于已有的算法.

大量小文件；頻繁項挖掘；動態(tài)合并

1 相關(guān)的工作

社交網(wǎng)絡(luò)的發(fā)展產(chǎn)生了大量小文件，這些小文件數(shù)據(jù)體量巨大[1]，并且單個文件容量小[2]，且其數(shù)據(jù)呈重尾分布的特點，這決定了少量的數(shù)據(jù)會被大量的用戶訪問.大量小文件在元數(shù)據(jù)管理、訪問性能等方面面臨巨大的挑戰(zhàn)，也因此成為當前業(yè)界關(guān)注和研究的熱點問題.

Liu Changtong等設(shè)置專門的小文件處理模塊，上傳文件之前先判斷是不是小文件，以key-value形式存儲小文件索引信息[3].該方案減少了NameNode內(nèi)存消耗，key-value形式的索引提高了訪問的效率，但是沒有考慮文件的相關(guān)性.Hao Xingjun等處理的是物聯(lián)網(wǎng)中的大量小文件，提出了文件存儲系統(tǒng)SensorFS、分布式內(nèi)存文件系統(tǒng)DMFS、并行化的合并文件方案[4].該方案改進了HDFS的I/O性能.但是方案中沒有考慮合并文件的一致性，即一個小文件可能合并到多個文件中.

由于傳統(tǒng)的靜態(tài)合并方案不適合用戶的動態(tài)訪問過程，因此本文提出基于訪問日志的動態(tài)合并，將訪問過程中的“熱”的數(shù)據(jù)合并到一起.

2 基于頻繁項挖掘的動態(tài)合并算法

本文借鑒頻繁項挖掘中購物籃分析的思想[4,5]，綜合考慮合并文件的一致性，提出基于頻繁項挖掘[6]的動態(tài)合并算法，獲取小文件的關(guān)聯(lián)性，將關(guān)聯(lián)性高的小文件動態(tài)合并，從而提高文件預(yù)取的效率.

Web文件訪問日志示例如表1所示.本文對Web中的日志文件進行整理，將訪問日志中的IP地址進行記錄的劃分，根據(jù)指定的時間間隔T，來分隔每個記錄集，將一個時間段T內(nèi)訪問的文件放到一條記錄中，得到的數(shù)據(jù)如表2所示(其中T1,T2,T3,T4,T5表示時間間隔).本文是用1min為一個T.Fabricio B等[7]調(diào)查文件的相關(guān)性與訪問的持續(xù)時間的關(guān)系，通過調(diào)查發(fā)現(xiàn)90%的用戶訪問社交網(wǎng)絡(luò)的會話時間在1min內(nèi)，因此取1min為時間段，該時間段內(nèi)的文件相關(guān)性最大.

表1 文件訪問日志示例

表2 文件訪問日志整理得到的數(shù)據(jù)舉例

在此基礎(chǔ)上，本文實現(xiàn)了一種基于頻繁項挖掘算法，算法如下：

(1)統(tǒng)計T時間段內(nèi)，單個用戶訪問的文件個數(shù)，找到最大值，設(shè)為k，同時將需要合并的文件個數(shù)定為k；

(2)掃描Web日志整理后得到的數(shù)據(jù)庫如表2，對數(shù)據(jù)庫中每一個記錄做如下操作：將記錄中所有的大小為k的子集求出來(Mapper)；

(3)統(tǒng)計輸出所有小文件子集的個數(shù)，如果某個小文件子集的個數(shù)超過了某一閾值s，并且該子集項在大于k的子集中沒有出現(xiàn)過，將所有子集輸出(Reducer).

算法中求取小文件子集采用數(shù)組，數(shù)組下標從1開始，每項用0或者1代表.數(shù)字“0”表示代表的數(shù)沒有被選上，輸出的子集中不會有這一項.數(shù)字“1”表示代表的數(shù)被選上，輸出的子集中會有這一項.

對于n項元素，求大小為k的所有子集，分為以下幾個步驟：

1)將前k項元素初始化為1，后面n-k項初始化為0，某一項對應(yīng)的位置為1，表示該項屬于該小文件子集.初始化可以得到小文件第一個子集；

2) 從數(shù)組第一位開始掃描找到數(shù)組排列中第一個“10”，這里“10”是指某連續(xù)兩位，前項為1，后項為0.如果有，則需要交換位置，將“10” 修改為“01”，此時數(shù)組中子集的對應(yīng)位置會改變.同時把該“01”左邊所有的“1”都移到數(shù)組的第一個位置依次排列；

3)判斷是否結(jié)束，判斷的條件為k個“1”全部移到最右端，這是最后一個子集的組合.

由于是大量小文件，子集的求取需要并行化的設(shè)計.并行化算法主要是通過Mapper和Reducer實現(xiàn)[8].對于每個Mapper，算法的實現(xiàn)主要是對每一行的文件數(shù)據(jù)進行分片，以逗號分隔元素，調(diào)用求取子集的算法，獲取所有大小為k的小文件子集，并且輸出；對于每一個Reducer，算法的主要功能是負責匯總和判斷，將小于支持度閾值s的、并且在大于k的子集項中沒有出現(xiàn)過的子集匯總，最后將結(jié)果輸出.

基于子集檢測的頻繁項挖掘算法中有兩點保證了合并文件的一致性：一是k的初始值選擇由大到小；二是加入了檢測模塊.

針對表2的合并，k的初始值為4，假設(shè)支持度閾值為2.首先檢測有沒有符合k為4，支持度閾值為2的子集.然后檢測k為3，支持度閾值為2是否符合，循環(huán)下去.經(jīng)上述處理后會得到處理結(jié)果2，3，5，表明{2,3,5}這個頻繁項集滿足算法設(shè)計的結(jié)果.那么合并小文件時將2，3，5這3個小文件放到一個容器中，然后再按照小文件的合并流程合并小文件.經(jīng)上述論證，基于子集檢測的頻繁項挖掘算法可以實現(xiàn)小文件的動態(tài)合并，并且可以保證合并文件的一致性.

3 置換算法的實現(xiàn)

隨著用戶訪問和預(yù)取文件的增多，放入到緩存中的文件會占用大量的緩存空間.為此就需要有緩存置換算法清理緩存中的內(nèi)容.本文將數(shù)據(jù)塊容器(Container)中最近時間內(nèi)很少訪問或者不訪問的文件清理出緩存.

數(shù)據(jù)換出緩存是以T=1min為單位的.如圖1所示，采用循環(huán)單鏈表將一段時間T內(nèi)訪問過的Container鏈接起來.可以看到單鏈的設(shè)計是在每一個Container中添加一個指針，指向T內(nèi)訪問的其余的Container，循環(huán)的設(shè)計是將最后一個Container指向第一個Container.本文將這種緩存中使用循環(huán)單鏈表的方法稱為含循環(huán)單鏈表的緩存置換法.

由圖1可知，如果需要置換緩存中的數(shù)據(jù)，就選擇循環(huán)單鏈表中的一個環(huán)，將時間T內(nèi)訪問的所有Container項清理出去.因此，需要有隊列Q來保存循環(huán)單鏈表的先后訪問順序.隊列中的節(jié)點保存環(huán)所在的任一個Container的地址.如果環(huán)中的Container剛被訪問，則將該節(jié)點保存到隊列頭部.隨著訪問的改變，隊列中的數(shù)據(jù)不斷發(fā)生變化，沒有被訪問的就處于尾部.置換數(shù)據(jù)選擇隊列尾部的節(jié)點，將指針所指的循環(huán)單鏈表中的項逐個刪掉，最后從隊列中徹底清除.

圖1 含循環(huán)單鏈表的緩存替換Fig.1 Cache replacement method with single cycle list

對于緩存而言，緩存清理算法的設(shè)計至關(guān)重要，算法的流程主要分以下幾步：

1)取出隊列尾部的待刪除節(jié)點；

2)逐個刪除該節(jié)點所對應(yīng)的容器中的文件；

3)刪除列隊的尾節(jié)點.

經(jīng)過上述處理，系統(tǒng)可將緩存中最近不再訪問的數(shù)據(jù)刪除，為即將訪問的熱點數(shù)據(jù)和預(yù)取數(shù)據(jù)預(yù)留空間.

4 測試結(jié)果與分析

實驗分為兩個部分進行測試和分析.第一部分是NameNode內(nèi)存消耗的測試，具體來說是將改進后HDFS消耗NameNode內(nèi)存和原始HDFS消耗NameNode內(nèi)存進行測試，并且對測試的結(jié)果進行分析；第二部分測試是訪問文件的ATPMB的測試，將改進后的HDFS與原始HDFS和HAR進行對比，包括順序讀取文件的ATPMB和隨機讀取文件的ATPMB.測試結(jié)束后對測試的結(jié)果進行分析.

4.1 測試環(huán)境

本實驗采用Hadoop1.2.1進行仿真，在VMware10上配置3個結(jié)點的Hadoop集群，每個結(jié)點的內(nèi)存為1GB，3個結(jié)點中，一個設(shè)置為NameNode，另外兩個設(shè)置為DataNode節(jié)點.小文件集總大小為1.03GB，共有817個小文件，都在4MB以內(nèi).小文件類型和小文件大小的比例如圖2和圖3所示.文件的類型有文本文件、圖像文件、音頻文件、視頻文件.圖像文件占總文件的53%.小于1MB的文件占總文件的51%.每個實驗做4次，選取平均值作為結(jié)果.

4.2 測試與分析

本文實驗對比指標：1)NameNode的內(nèi)存開銷；2)訪問文件的評價標準是讀取1MB的文件需要的時間，單位為秒(s)；3)上傳小文件的時間消耗.

讀取1MB文件的耗時可用ATPMB表示為：

(1)

實驗分別上傳200、400、600、800個小文件到改進HDFS、原始HDFS以及HAR上，文件隨機選取達到指定數(shù)，并統(tǒng)計每次的內(nèi)存消耗.

從圖4中可以看出，改進的HDFS能降低NameNode的內(nèi)存開銷，平均使用內(nèi)存空間分別為原始HDFS的35.37%和HAR的85.24%.改進的HDFS比原始的HDFS和HAR有優(yōu)勢.這因為原始HDFS沒有合并方案，每個文件占有NameNode內(nèi)存，嚴重浪費內(nèi)存.改進的HDFS將小文件合并后再存儲到HDFS中，節(jié)省內(nèi)存的原因有兩點：一是合并減少了在NameNode中存儲的元數(shù)據(jù)量；二是把生成的小文件BlockIndex文件放在DataNode中，節(jié)省了大量的NameNode內(nèi)存空間.從圖4中還可以看出，HAR存儲文件占用的內(nèi)存比原始HDFS少，這是因為HAR將文件合并，但是效果沒有本文改進的方案好.圖4中，隨著文件數(shù)量的增多，主節(jié)點的內(nèi)存消耗呈上升趨勢，但不是直線上升.主要是因為在HDFS的運行過程中，需要周期性將元數(shù)據(jù)文件fsimage和操作日志edits合并.

圖2 小文件的類型比例Fig.2 Proportion of small file type

圖3 小文件的大小比例Fig.3 Proportion of small file size

圖4 內(nèi)存消耗對比Fig.4 Memory consumption comparison

讀取測試分為兩部分：順序讀取小文件和隨機讀取小文件.順序讀取小文件是本文測試的重點，這也是本文的實驗?zāi)康?在社交網(wǎng)絡(luò)中，單個用戶的文件具有很強的相關(guān)性.并且數(shù)據(jù)呈重尾分布的特點，使得一些用戶的少量數(shù)據(jù)被大量訪問，那么延遲會增大.本實驗中，改進的HDFS初次寫入文件用靜態(tài)的小文件合并處理方法，隨著用戶的訪問，會產(chǎn)生訪問日志，再對這些訪問日志以1min為單位進行處理，將容器中的相關(guān)數(shù)據(jù)提前預(yù)取出來，減少訪問的延遲.實驗配置5個block的文件緩沖區(qū)大小.實驗中取200、400、600、800個小文件分別對原始HDFS、HAR、改進HDFS三種方案進行測試.由公式(1)計算每次的ATPMB，見表3.

由表3可計算得出ATPMB的平均值，原始HDFS為6.78，HAR為7.89，改進HDFS(順序)為5.98.即訪問1MB的數(shù)據(jù)，HAR方案耗時最多，改進的HDFS耗時最少.從表3可以看出，當順序讀取小文件時，改進的HDFS與原始HDFS、HAR相比，消耗的時間明顯減少.性能好的原因主要有兩個：一是提前將接下來有可能訪問的文件預(yù)取到Cache中，極大地減少了Client端與NameNode和DataNode的交互次數(shù)，節(jié)約了大量的時間；二是全局索引的設(shè)計，本文采用直接定位的方式，避免了在大量文件中的查找，也節(jié)省了時間.兩方面的結(jié)合使得改進HDFS在順序讀取文件上，與原始HDFS和HAR相比節(jié)省了大量的時間.表3中可以看出，HAR的ATPMB值最高，這是因為讀取過程中需要額外訪問兩級索引，消耗了時間.

隨機讀取小文件的ATPMB均值為7.85，比順序讀取小文件的時間消耗多，這也是改進HDFS的不足之處.這是因為每次都要與HDFS進行交互，并且改進的HDFS中的預(yù)取與緩存的優(yōu)化方案在隨機讀取文件中，沒有顯示出作用，反而成為負擔.改進HDFS隨機訪問文件比原始HDFS隨機訪問文件消耗的時間相對多，有微弱的差距，但在可接受的范圍內(nèi).

表3 讀取文件測試的ATPMB對比表

5 結(jié)語

本文主要針對社交網(wǎng)絡(luò)中大量小文件，包括文本、圖像、音頻、視頻四種類型的文件，在HDFS中的存儲做了深入的研究.其關(guān)鍵技術(shù)包括兩點：第一是提出一種新的動態(tài)合并算法；第二在動態(tài)合并的基礎(chǔ)上，實現(xiàn)一種置換算法優(yōu)化緩存內(nèi)容.經(jīng)過實驗測試，本算法動態(tài)文件的合并性能優(yōu)于已有算法.

[1] Katal A, Wazid M, Goudar R H. Big data: issues, challenges, tools and good practices[C]//IEEE.Sixth International Conference on Contemporary Computing. Noida: IEEE Press,2013:404-409.

[2] Demchenko Y, DeLaat C, Membrey P. Defining architecture components of the Big Data Ecosystem[C]//IEEE. International Conference on Collaboration Technologies and Systems (CTS). Minnesota: IEEE Press, 2014:104-112.

[3] Liu C. An improved HDFS for small file[C]//IEEE. International Conference on Advanced Communication Technology (ICACT). Pyeongchang: IEEE Press,2016:474-477.

[4] He L, Qi J X. Enterprise human resources information mining based on improved Apriori algorithm[J]. Journal of Networks, 2013,8(5):1138-1145.

[5] Zhou L J, Wang X. Research of the FP-growth algorithm based on cloud environments[J].Journal of Software, 2014,9(3):676-683.

[6] Jyoti L D, Kiran B D. A novel methodology of frequent itemset mining on Hadoop[J].International Journal of Emerging Technology and Advanced Engineering, 2014, 4(7):851-859.

[7] Fabricio B, Tiago R, Cha M, et al. Characterizing user behavior in on-line social networks[C]//ACM. ACM Sigcomm Conference on Internet Measurement Conference. New York: ACM,2009:49-62.

[8] Saabith A L S, Sundararajan E, Bakar A A. Parallel implementation of Apriori algorithms on the Hadoop-mapreduce platform—an evaluation of literature[J]. Journal of Theoretical and Applied Information Technology, 2016,85(3): 321-351.

A Dynamic Merging Algorithm for Mass Small Files Based on Frequent Item Mining

Zhou Bin, Bi Chuanmei

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

The characteristics of mass small files of current social network were analyzed, and the access logs and data mining were combined in this paper. A dynamically merging algorithm for mass small files based on frequent item mining was proposed. This algorithm implements dynamic merge for small files which solves the consistency problem for merging files. It also guides for prefetching small files to improve the hit rate for prefetching. A novel cache replacement algorithm containing cycle singly linked list was put forward to optimize cache content according to the characteristics of prefetching and too many cache files. The experiment results show that the mass small files dynamically merging performances are superior to the former algorithms.

mass small files; frequent item mining; dynamic merging

2016-09-06

周 斌(1971-)，男，副教授，博士，研究方向：大數(shù)據(jù)存儲與處理，E-mail：binzhou@mail.scuec.edu.cn

湖北省自然科學基金資助項目(2016CFB650)

TP311

A

1672-4321(2016)04-0111-05