一種基于混合索引的HDFS 小文件存儲策略

熊安萍，黃 容，鄒 洋

(重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065)

0 引言

在互聯(lián)網(wǎng)飛速發(fā)展、數(shù)據(jù)量暴增的時代，各種分布式文件系統(tǒng)［1］應(yīng)運(yùn)而生，如GlusterFS，Lustre，GoogleFS，HDFS等。分布式文件系統(tǒng)(hadoop distributed file system，HDFS)［2-3］作為Hadoop的分布式文件系統(tǒng)，憑借其高可靠性、高擴(kuò)展性、高效性、高吞吐率等優(yōu)勢在互聯(lián)網(wǎng)領(lǐng)域得到了廣泛研究和應(yīng)用。但其也存在一些不足之處，如:元數(shù)據(jù)服務(wù)器節(jié)點(diǎn)單點(diǎn)故障、負(fù)載均衡能力不足、小文件存儲及處理問題等。

當(dāng)前HDFS中，小文件存儲和讀取效率普遍不高，過多小文件元數(shù)據(jù)占用元數(shù)據(jù)服務(wù)器節(jié)點(diǎn)Nam-eNode的內(nèi)存開銷;小文件合并方案中小文件到大文件的映射記錄量太大，導(dǎo)致從合并文件中訪問小文件的效率不高及訪問小文件時NameNode負(fù)載過大;小文件塊內(nèi)索引訪問效率不高。針對以上問題，本文提出一種更有利于小文件存儲和讀取的優(yōu)化存儲策略。該存儲策略應(yīng)用分類器分類標(biāo)記小文件，同一標(biāo)簽的小文件合并為一個大文件，既充分利用Hadoop平臺大文件存儲處理優(yōu)勢，也減少了元數(shù)據(jù)數(shù)目;設(shè)計(jì)了混合索引機(jī)制，即對服務(wù)端的小文件標(biāo)簽及小文件與塊的映射建立H－B+樹索引，以及對塊內(nèi)小文件建立不同的塊內(nèi)索引，以提高小文件的訪問效率，一定程度節(jié)省索引文件存儲空間;實(shí)現(xiàn)中采用緩存結(jié)構(gòu)，以提高客戶端訪問請求的響應(yīng)速度及減小元數(shù)據(jù)服務(wù)器的負(fù)載。

1 相關(guān)工作

HDFS作為Google公司GoogleFS的開源實(shí)現(xiàn)［2］，是以流式數(shù)據(jù)訪問模式存儲超大文件的文件系統(tǒng)，可運(yùn)行在普通硬件集群上。

1.1 HDFS中小文件處理缺陷

1)元數(shù)據(jù)服務(wù)器NameNode內(nèi)存開銷大。NameNode將文件系統(tǒng)元數(shù)據(jù)放置于內(nèi)存，一般而言，每一個文件、文件夾或Block需要占據(jù)150 Byte左右的內(nèi)存空間，如果有100萬個文件，則至少需要300 MByte內(nèi)存。如果面對海量小文件，當(dāng)前的硬件無法滿足內(nèi)存需求。

2)小文件存儲和讀取效率不佳。HDFS利于大吞吐量數(shù)據(jù)處理，以一定延時為代價(jià)［4］。HDFS集群存儲10 000 MByte大文件的速度比存儲10 000 MByte小文件的速度要快得多。

1.2 相關(guān)研究

對于HDFS小文件問題，目前已經(jīng)有多種解決方案，其核心都是將小文件合并為大文件，通過減少文件個數(shù)以減少元數(shù)據(jù)大小，同時為小文件建立索引以提高訪問效率［5］。

文獻(xiàn)［6-9］是HDFS自身提供的解決方案。Hadoop Archive［6］將多個小文件打包成一個HAR文件存儲，通過減少文件個數(shù)，緩解了NameNode內(nèi)存的壓力。Sequence File［7］由二進(jìn)制對組成，其中key為小文件名，value為小文件內(nèi)容。CombineFileInput-Format［8］將多個小文件合并成一個單獨(dú)的split，并且考慮數(shù)據(jù)的存儲位置，解決了大量小文件造成Maptask過多而降低整體性能的問題。MapFile［9］是一種有索引的按key排序的SequenceFile，讀取性能有所提高。

文獻(xiàn)［10-13］針對特定應(yīng)用場景的解決方案。劉旭輝等［10］結(jié)合WebGIS數(shù)據(jù)的相關(guān)特征，將相鄰地理位置的小文件合并，并為這些文件構(gòu)建全局的hash索引，有效提高了小文件的訪問效率。鄭慶華等［11］針對BlueSky的PPT文件，將屬于同一課件的小文件合并，從而減輕NameNode的壓力，提出了一種兩級預(yù)取機(jī)制以提高小文件的讀取效率。趙躍龍等［12］提出的優(yōu)化的小文件存儲策略，把邏輯上連續(xù)的數(shù)據(jù)在物理空間上連續(xù)存放以提高預(yù)讀數(shù)據(jù)的命中率，減少磁盤尋道時間，通過使用cache充當(dāng)元數(shù)據(jù)服務(wù)器的角色和簡化文件信息節(jié)點(diǎn)的方式提高I/O性能。CHANDRASEKAR S等［13］合并小文件時由客戶指定要合并的小文件名及文件間的關(guān)系，建立索引機(jī)制，采用預(yù)取機(jī)制，以減少元數(shù)據(jù)讀取時間，提高I/O性能。

2 基于混合索引的小文件存儲策略

本文基于混合索引的小文件存儲策略(small files storage based on hybrid index，SFSHI)，針對小文件的存儲策略，設(shè)計(jì)混合索引機(jī)制，實(shí)現(xiàn)中采用三級緩存結(jié)構(gòu)。

2.1 小文件存儲架構(gòu)

本文小文件存儲策略架構(gòu)如圖1所示。在Client客戶端的本地存儲中，應(yīng)用一個分類器來對小文件進(jìn)行分類標(biāo)記，分類規(guī)則可由用戶定義，根據(jù)實(shí)際系統(tǒng)需求，分類規(guī)則可以按業(yè)務(wù)或按客戶群體等來分別定義，分類后同一類型小文件具有相同標(biāo)簽。同一標(biāo)簽中的小文件進(jìn)一步按照大小分類，小文件大小為1-1023 KByte，為K級文件，1-64 MByte為M級文件，同一標(biāo)簽的同級文件合并為一個大文件，合并時滿一個塊提交一次，同時保證小文件不跨2個數(shù)據(jù)塊，并根據(jù)文件大小建立合適的塊內(nèi)索引，同數(shù)據(jù)塊一起存儲到DataNode中。在NameNode中存儲小文件標(biāo)簽索引和小文件與塊的映射索引。

2.2 混合索引策略設(shè)計(jì)

結(jié)合散列索引快速定位的特點(diǎn)和樹型結(jié)構(gòu)的搜索路徑短、可動態(tài)增長的特點(diǎn)，散列與樹結(jié)構(gòu)的混合索引策略被廣泛研究及應(yīng)用。本文在小文件分類標(biāo)記的場景下，改進(jìn)混合索引策略，結(jié)合三級緩存結(jié)構(gòu)，提高小文件的訪問及處理效率。

本文小文件存儲架構(gòu)中設(shè)計(jì)的混合索引策略如圖2所示。NameNode服務(wù)端建立基于小文件標(biāo)簽的散列索引和桶內(nèi)小文件與塊的映射(簡稱小文件映射)的B+樹索引，DataNode數(shù)據(jù)端根據(jù)所存儲小文件的大小，有區(qū)別的建立合適的塊內(nèi)索引，以實(shí)現(xiàn)小文件高效快速的訪問。

圖1 小文件存儲架構(gòu)圖Fig.1 Small files storage architecture

圖2 混合索引策略Fig.2 Hybrid index strategy

本文混合索引策略中，由于小文件標(biāo)簽和小文件映射動態(tài)增長，對上層的小文件標(biāo)簽建立基于小文件標(biāo)簽的可擴(kuò)展散列索引?？蓴U(kuò)展散列可節(jié)省空間，當(dāng)索引項(xiàng)增長時，動態(tài)分配桶，雖然需要維護(hù)桶地址表，這一額外開銷影響非常小，我們可以忽略。傳統(tǒng)的散列索引結(jié)構(gòu)為了提高數(shù)據(jù)映射的隨機(jī)性，相鄰數(shù)據(jù)項(xiàng)在索引項(xiàng)的位置是離散的，這不利于小文件映射記錄的局部性訪問。本文提出基于文件標(biāo)簽的散列索引，除了保持散列索引的處理速度、存儲空間的優(yōu)勢，還能有效提高緩存命中率。該索引結(jié)構(gòu)的主要思路是根據(jù)小文件所屬標(biāo)簽，使用文件標(biāo)簽代替數(shù)據(jù)項(xiàng)作為索引單元，保證同一標(biāo)簽的文件映射記錄被映射到同一個桶中，訪問文件映射記錄時，其緩存命中率有所提高，從而使小文件達(dá)到更高的訪問效率。

下層的小文件映射采用B+樹結(jié)構(gòu)，由于小文件映射記錄海量且要適應(yīng)多個客戶端并發(fā)請求，NameNode內(nèi)存不能承擔(dān)載如此大的負(fù)載，所以小文件映射只能存儲在磁盤上，需按文件塊讀取到內(nèi)存。要有效查詢小文件映射，必須減少磁盤訪問次數(shù)，而B+樹索引具有搜索路徑短的特點(diǎn)，適合作為小文件映射的索引結(jié)構(gòu)。B+樹索引的搜索路徑小于［log［n/2］(K)］(n為結(jié)點(diǎn)的階，K為索引項(xiàng)的總數(shù)量)。例如，結(jié)點(diǎn)的大小一般為磁盤塊大小(4 KByte)，如果搜索碼大小為32 Byte，n=4×210/32=100，如果索引項(xiàng)有1 000 000個，一次查詢訪問磁盤次數(shù)為log［100/2］(1 000 000)=4次。再加上緩存的作用，訪問磁盤的次數(shù)更少。

DataNode的塊內(nèi)索引，根據(jù)數(shù)據(jù)塊所存儲小文件的大小，有區(qū)別地建立合適的索引，既能節(jié)省索引文件的存儲空間，又能充分利用高速緩存的作用，有效提高小文件塊內(nèi)索引的查詢效率。因?yàn)镠DFS有一次寫入多次讀取的特點(diǎn)，數(shù)據(jù)塊一旦建立修改操作較少，則塊內(nèi)索引的變化和增加較少，因此都采用順序索引。小文件大小為1-1 023 KByte，為K級文件，1-64 MByte為M級文件，K級文件最壞情況下索引項(xiàng)有220個，M級文件最壞情況下索引項(xiàng)有26個，索引項(xiàng)數(shù)量達(dá)到214倍的差別，有區(qū)別地建立索引是有必要的。M級文件的塊內(nèi)索引的索引項(xiàng)較少，選擇線性索引結(jié)構(gòu)，實(shí)現(xiàn)簡單，沒有節(jié)點(diǎn)和數(shù)據(jù)項(xiàng)的指針，節(jié)省存儲空間，塊內(nèi)索引項(xiàng)大小為12 Byte，則M級文件的塊內(nèi)索引文件大小64×12=768 Byte，文件非常小，可以直接加載到數(shù)據(jù)端緩存，能保證緩存命中率。K級文件的索引項(xiàng)較多，采用CST樹(cache sensitive T-tree)結(jié)構(gòu)。CST樹對所有節(jié)點(diǎn)進(jìn)行分組，分組大小根據(jù)緩存容量而定，組內(nèi)的多個節(jié)點(diǎn)采用數(shù)組結(jié)構(gòu)連續(xù)存儲。通過只保存節(jié)點(diǎn)的最大關(guān)鍵字，以及減少節(jié)點(diǎn)組內(nèi)節(jié)點(diǎn)間的指針，以減少節(jié)點(diǎn)組的存儲容量，并且節(jié)點(diǎn)組大小不大于緩存的容量，則每次從內(nèi)存可以讀入一個完整的節(jié)點(diǎn)組到緩存，這樣有效提高節(jié)點(diǎn)組內(nèi)關(guān)鍵字的緩存命中率，只有查詢節(jié)點(diǎn)組外的關(guān)鍵字時才會發(fā)生命中失敗。文獻(xiàn)［14］實(shí)驗(yàn)結(jié)果表明，CST樹在查詢速度和cache命中率方面比CSB樹和B+樹的性能都好，雖然CST樹在修改時效率不高，但對于相對比較靜態(tài)的塊內(nèi)索引，CST是最合適的選擇。

2.3 三級緩存結(jié)構(gòu)

三級緩存結(jié)構(gòu)分別為:NameNode服務(wù)端緩存、DataNode數(shù)據(jù)端緩存、客戶端緩存。

服務(wù)端緩存小文件標(biāo)簽的散列索引，客戶端訪問小文件時，NameNode通過散列函數(shù)計(jì)算出所在標(biāo)簽桶，首先在服務(wù)端緩存查詢標(biāo)簽桶的存儲地址。再由標(biāo)簽桶中小文件映射索引查找出該小文件所在的小文件映射索引塊，將該索引塊返回給客戶端，并加入到客戶端緩存，客戶端進(jìn)行訪問小文件時，首先在客戶端緩存中查找小文件映射，從而減少與NameNode的交互次數(shù)。數(shù)據(jù)端緩存則緩存小文件的塊內(nèi)索引，以有效提高小文件塊內(nèi)的訪問效率。

3 SFSHI策略實(shí)現(xiàn)

本文小文件存儲策略中，Client客戶端完成小文件標(biāo)記與合并、與DataNode之間的數(shù)據(jù)傳輸。NameNode服務(wù)器負(fù)責(zé)處理客戶端請求、標(biāo)簽索引管理、小文件映射索引管理。DataNode負(fù)責(zé)完成數(shù)據(jù)存儲和讀取操作、小文件塊內(nèi)索引管理、本身所存儲數(shù)據(jù)塊的管理。

3.1 小文件存儲流程

本文的小文件存儲流程如圖3所示。

圖3 存儲流程圖Fig.3 Storage process

當(dāng)客戶端中某標(biāo)簽小文件的數(shù)據(jù)塊已滿，調(diào)用存儲小文件的方法writeSF，DataNode服務(wù)器添加接收小文件并更新元數(shù)據(jù)的方法receiveSF。方法描述為

3.2 小文件讀取流程

本文的小文件讀取流程如圖4所示。

圖4 讀取流程圖Fig.4 Access process

客戶端添加小文件讀取方法readSF，獲取小文件的所在blockId及DataNode列表。DataNode上添加方法querySF，讀取小文件塊內(nèi)索引及小文件內(nèi)容并返回。方法描述為

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

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

實(shí)驗(yàn)環(huán)境搭建了12個節(jié)點(diǎn)的Hadoop集群，每個節(jié)點(diǎn)的配置為:6核Intel Xeon CPU 2.4 GHz，8 GByte內(nèi)存，10 TByte硬盤。網(wǎng)絡(luò)環(huán)境是千兆光纖。其中一臺機(jī)器作NameNode，一臺作SecondNameNode，12臺機(jī)器全部作DataNode。每臺節(jié)點(diǎn)安裝的操作系統(tǒng)為Cent OS5.4，Hadoop版本為cdh3u6，JDK的版本為1.6.0_35。

4.2 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)是大量小文件，小文件格式有圖片、文本文件、二進(jìn)制文件。數(shù)據(jù)來源為某電信公司營業(yè)終端服務(wù)與集約化管理平臺各客戶端產(chǎn)生的操作日志文件及用戶數(shù)據(jù)，其中，操作日志文件大小為1-300 KByte，用戶數(shù)據(jù)文件大小為1-4 MByte，該平臺每天產(chǎn)生約210 000個小文件，文件總量約40 GByte。這些數(shù)據(jù)海量，且都是大小集中在1 KByte-4 MByte的小文件。測試用到的文件集合共435 462個文件，總量為89.4 GByte，小文件大小分布如圖5所示。

圖5 小文件大小分布Fig.5 Distribution of small file size

4.3 實(shí)驗(yàn)對比

在集群上部署Ganglia集群監(jiān)控系統(tǒng)，它可以提供準(zhǔn)確而有效的實(shí)驗(yàn)結(jié)果來對實(shí)驗(yàn)進(jìn)行評價(jià)。實(shí)驗(yàn)對比的主要指標(biāo)是:NameNode的內(nèi)存開銷，讀取小文件的時間開銷。

從存儲435 462小文件的集群中，讀取6組不同數(shù)量的小文件，每組進(jìn)行10次實(shí)驗(yàn)，對實(shí)驗(yàn)結(jié)果取平均值。對HDFS原小文件存儲策略和基于混合索引的小文件存儲策略2種測試環(huán)境下讀取文件的耗時和內(nèi)存開銷進(jìn)行統(tǒng)計(jì)。

小文件讀取時間開銷對比如圖6所示。圖6結(jié)果表明，基于混合索引的小文件存儲策略讀取小文件的速度比HDFS原方案讀取速度快得多。

圖6 小文件讀取時間開銷對比Fig.6 Time cost comparison when accessing small files

小文件讀取時，NameNode的內(nèi)存開銷對比如圖7所示，結(jié)果表明，基于混合索引的小文件存儲策略中NameNode的內(nèi)存占用率大大減少。SFSHI策略中NameNode內(nèi)存只存儲合并后大文件標(biāo)簽元數(shù)據(jù)，并且將大文件標(biāo)簽索引加載到NameNode緩存，小文件映射索引存儲在NameNode磁盤上;同時，如果所訪問的小文件映射在客戶端緩存命中，則可以減少與NameNode的交互，所以SFSHI策略能顯著降低NameNode的內(nèi)存開銷。

圖7 內(nèi)存開銷對比Fig.7 Memory overhead comparison

綜上所述，基于混合索引的小文件存儲策略SFSHI對同一標(biāo)簽的小文件作為一個大文件存儲管理，同時采用的服務(wù)端緩存和客戶端緩存，減少了NameNode的內(nèi)存開銷;針對本文小文件存儲策略，合理地采用三級緩存和混合索引策略，在一定程度上減少了索引文件存儲空間，同時有效提高了小文件的讀取效率。

5 結(jié)語

本文分析了HDFS中小文件處理機(jī)制，針對小文件過多時占用NameNode內(nèi)存開銷、從合并文件中訪問小文件的效率不高等問題，給出了一個基于混合索引的小文件存儲策略，該存儲策略核心在于應(yīng)用分類器分類標(biāo)記小文件，同一標(biāo)簽的小文件作為一個大文件存儲管理，減少了元數(shù)據(jù)數(shù)目;針對本文中小文件存儲策略，設(shè)計(jì)了混合索引機(jī)制，提高了小文件訪問效率，實(shí)現(xiàn)中采用緩存結(jié)構(gòu)，同時也解決了NameNode內(nèi)存負(fù)載問題。實(shí)驗(yàn)及結(jié)果表明，本文小文件存儲策略能有效提高海量小文件的訪問效率，并大大減小NameNode的內(nèi)存負(fù)載。

［1］郝杰，逯彥博，劉鑫吉，等.分布式存儲中的再生碼綜述［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2013，25(1):30-38.

HAO Jie，LU Yanbo，LIU Xinji，et al.Survey for regenerating codes for distributed storage［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2013，25(1):30-38.

［2］TOM White.Hadoop:The Definitive Guide［M］.2nd ed.O’Reilly Media，Inc，2011.

［3］ARMBRUST M，F(xiàn)OX A，GRIFFITH R，et al.Above the Clouds:A Berkeley View of Cloud Computing［D］.Berkeley:UCB/EECS-2009-28，EECS Department，University of California，Berkeley，2009.

［4］王鈴惠，李小勇，張軼彬.海量小文件存儲文件系統(tǒng)研究綜述［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29(8):106-109.

WANG Linghui，LI Xiaoyong，ZHANG Yibin.Mass Small-File Storage File System Research Overview［J］.Computer Applications and Software，2012，29(8):106-109.

［5］TOM White.The Small Files Problem［EB/OL］.(2009-02-02)［2013-12-10］.http://www.cloudera.com/blog/2009/02/02/the-small-files-problem/.

［6］HADOOP.Hadoop Archives［EB/OL］.(2013-04-01)［2013-12-10］.http://hadoop.apache.org/docs/r-1.2.1/hadoop_archives.html.

［7］HADOOP.Sequence File Wiki［EB/OL］.(2009-09-05)［2013-12-10］.http://wiki.apache.org/had-oop/SequenceFile.

［8］CARPE Diem.Combine File Input Format［EB/OL］.(2009-10-05)［2013-12-10］.http://ww-w.idryman.org/blog/2013/09/22/process-small-files-on-hadoop-using-combinefileinputformat-1/.

［9］HADOOP.Map files［EB/OL］.(2013-04-15)［2013-12-10］.http://hadoop.apache.org/docs/cu-rrent/api/org/apache/hadoop/io/MapFile.html.

［10］LIU Xuhui，HAN Jizhong，ZHONG Yunqin，et al.Implementing WebGIS on Hadoop:A Case Study of Improving Small File I/O Performance on HDFS［C］//2009 IEEE International Conference on Cluster Computing and Work-shops.New Orleans:IEEE Press，2009:1-8.

［11］DONG Bo，QIU Jie，ZHENG Qinghua，et al.A Novel Approach to Improving the Efficiency of Storing and Accessing Small Files on Hadoop:a Case Study by Power-Point Files［C］//2010 IEEE International Conference on Services Computing(SCC).Miami，F(xiàn)L:IEEE Press，2010:65-72.

［12］趙躍龍，謝曉玲，蔡詠才，等.一種性能優(yōu)化的小文件存儲訪問策略的研究［J］.計(jì)算機(jī)研究與發(fā)展，2012，49(7):1579-1586.

ZHAO Yuelong，XIE Xiaoling，CAI Yongcai，et al.A Strategy of Small File Storage Access with Performance Optimization［J］.Journal of Computer Research and Development，2012，49(7):1579-1586.

［13］CHANDRASEKAR S，DAKSHINAMURTHY R，SESHAKUMAR P G，et al.A novel indexing scheme for efficient handling of small files in Hadoop Distributed File System［C］//2013 IEEE International Conference on Computer Communication and Informatics(ICCCI).Coimbatore:IEEE Press，2013:1-8.

［14］LEE I，LEE S，SHIM J.Making T-Trees Cache Conscious on Commodity Microprocessors［J］.J Inf Sci Eng，2011，27(1):143-161.