一种基于混合索引的HDFS 小文件存储策略

熊安萍，黄 容，邹 洋

(重庆邮电大学计算机科学与技术学院，重庆400065)

0 引言

在互联网飞速发展、数据量暴增的时代，各种分布式文件系统［1］应运而生，如GlusterFS，Lustre，GoogleFS，HDFS等。分布式文件系统(hadoop distributed file system，HDFS)［2-3］作为Hadoop的分布式文件系统，凭借其高可靠性、高扩展性、高效性、高吞吐率等优势在互联网领域得到了广泛研究和应用。但其也存在一些不足之处，如:元数据服务器节点单点故障、负载均衡能力不足、小文件存储及处理问题等。

当前HDFS中，小文件存储和读取效率普遍不高，过多小文件元数据占用元数据服务器节点Nam-eNode的内存开销;小文件合并方案中小文件到大文件的映射记录量太大，导致从合并文件中访问小文件的效率不高及访问小文件时NameNode负载过大;小文件块内索引访问效率不高。针对以上问题，本文提出一种更有利于小文件存储和读取的优化存储策略。该存储策略应用分类器分类标记小文件，同一标签的小文件合并为一个大文件，既充分利用Hadoop平台大文件存储处理优势，也减少了元数据数目;设计了混合索引机制，即对服务端的小文件标签及小文件与块的映射建立H－B+树索引，以及对块内小文件建立不同的块内索引，以提高小文件的访问效率，一定程度节省索引文件存储空间;实现中采用缓存结构，以提高客户端访问请求的响应速度及减小元数据服务器的负载。

1 相关工作

HDFS作为Google公司GoogleFS的开源实现［2］，是以流式数据访问模式存储超大文件的文件系统，可运行在普通硬件集群上。

1.1 HDFS中小文件处理缺陷

1)元数据服务器NameNode内存开销大。NameNode将文件系统元数据放置于内存，一般而言，每一个文件、文件夹或Block需要占据150 Byte左右的内存空间，如果有100万个文件，则至少需要300 MByte内存。如果面对海量小文件，当前的硬件无法满足内存需求。

2)小文件存储和读取效率不佳。HDFS利于大吞吐量数据处理，以一定延时为代价［4］。HDFS集群存储10 000 MByte大文件的速度比存储10 000 MByte小文件的速度要快得多。

1.2 相关研究

对于HDFS小文件问题，目前已经有多种解决方案，其核心都是将小文件合并为大文件，通过减少文件个数以减少元数据大小，同时为小文件建立索引以提高访问效率［5］。

文献［6-9］是HDFS自身提供的解决方案。Hadoop Archive［6］将多个小文件打包成一个HAR文件存储，通过减少文件个数，缓解了NameNode内存的压力。Sequence File［7］由二进制对组成，其中key为小文件名，value为小文件内容。CombineFileInput-Format［8］将多个小文件合并成一个单独的split，并且考虑数据的存储位置，解决了大量小文件造成Maptask过多而降低整体性能的问题。MapFile［9］是一种有索引的按key排序的SequenceFile，读取性能有所提高。

文献［10-13］针对特定应用场景的解决方案。刘旭辉等［10］结合WebGIS数据的相关特征，将相邻地理位置的小文件合并，并为这些文件构建全局的hash索引，有效提高了小文件的访问效率。郑庆华等［11］针对BlueSky的PPT文件，将属于同一课件的小文件合并，从而减轻NameNode的压力，提出了一种两级预取机制以提高小文件的读取效率。赵跃龙等［12］提出的优化的小文件存储策略，把逻辑上连续的数据在物理空间上连续存放以提高预读数据的命中率，减少磁盘寻道时间，通过使用cache充当元数据服务器的角色和简化文件信息节点的方式提高I/O性能。CHANDRASEKAR S等［13］合并小文件时由客户指定要合并的小文件名及文件间的关系，建立索引机制，采用预取机制，以减少元数据读取时间，提高I/O性能。

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

本文基于混合索引的小文件存储策略(small files storage based on hybrid index，SFSHI)，针对小文件的存储策略，设计混合索引机制，实现中采用三级缓存结构。

2.1 小文件存储架构

本文小文件存储策略架构如图1所示。在Client客户端的本地存储中，应用一个分类器来对小文件进行分类标记，分类规则可由用户定义，根据实际系统需求，分类规则可以按业务或按客户群体等来分别定义，分类后同一类型小文件具有相同标签。同一标签中的小文件进一步按照大小分类，小文件大小为1-1023 KByte，为K级文件，1-64 MByte为M级文件，同一标签的同级文件合并为一个大文件，合并时满一个块提交一次，同时保证小文件不跨2个数据块，并根据文件大小建立合适的块内索引，同数据块一起存储到DataNode中。在NameNode中存储小文件标签索引和小文件与块的映射索引。

2.2 混合索引策略设计

结合散列索引快速定位的特点和树型结构的搜索路径短、可动态增长的特点，散列与树结构的混合索引策略被广泛研究及应用。本文在小文件分类标记的场景下，改进混合索引策略，结合三级缓存结构，提高小文件的访问及处理效率。

本文小文件存储架构中设计的混合索引策略如图2所示。NameNode服务端建立基于小文件标签的散列索引和桶内小文件与块的映射(简称小文件映射)的B+树索引，DataNode数据端根据所存储小文件的大小，有区别的建立合适的块内索引，以实现小文件高效快速的访问。

图1 小文件存储架构图Fig.1 Small files storage architecture

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

本文混合索引策略中，由于小文件标签和小文件映射动态增长，对上层的小文件标签建立基于小文件标签的可扩展散列索引。可扩展散列可节省空间，当索引项增长时，动态分配桶，虽然需要维护桶地址表，这一额外开销影响非常小，我们可以忽略。传统的散列索引结构为了提高数据映射的随机性，相邻数据项在索引项的位置是离散的，这不利于小文件映射记录的局部性访问。本文提出基于文件标签的散列索引，除了保持散列索引的处理速度、存储空间的优势，还能有效提高缓存命中率。该索引结构的主要思路是根据小文件所属标签，使用文件标签代替数据项作为索引单元，保证同一标签的文件映射记录被映射到同一个桶中，访问文件映射记录时，其缓存命中率有所提高，从而使小文件达到更高的访问效率。

下层的小文件映射采用B+树结构，由于小文件映射记录海量且要适应多个客户端并发请求，NameNode内存不能承担载如此大的负载，所以小文件映射只能存储在磁盘上，需按文件块读取到内存。要有效查询小文件映射，必须减少磁盘访问次数，而B+树索引具有搜索路径短的特点，适合作为小文件映射的索引结构。B+树索引的搜索路径小于［log［n/2］(K)］(n为结点的阶，K为索引项的总数量)。例如，结点的大小一般为磁盘块大小(4 KByte)，如果搜索码大小为32 Byte，n=4×210/32=100，如果索引项有1 000 000个，一次查询访问磁盘次数为log［100/2］(1 000 000)=4次。再加上缓存的作用，访问磁盘的次数更少。

DataNode的块内索引，根据数据块所存储小文件的大小，有区别地建立合适的索引，既能节省索引文件的存储空间，又能充分利用高速缓存的作用，有效提高小文件块内索引的查询效率。因为HDFS有一次写入多次读取的特点，数据块一旦建立修改操作较少，则块内索引的变化和增加较少，因此都采用顺序索引。小文件大小为1-1 023 KByte，为K级文件，1-64 MByte为M级文件，K级文件最坏情况下索引项有220个，M级文件最坏情况下索引项有26个，索引项数量达到214倍的差别，有区别地建立索引是有必要的。M级文件的块内索引的索引项较少，选择线性索引结构，实现简单，没有节点和数据项的指针，节省存储空间，块内索引项大小为12 Byte，则M级文件的块内索引文件大小64×12=768 Byte，文件非常小，可以直接加载到数据端缓存，能保证缓存命中率。K级文件的索引项较多，采用CST树(cache sensitive T-tree)结构。CST树对所有节点进行分组，分组大小根据缓存容量而定，组内的多个节点采用数组结构连续存储。通过只保存节点的最大关键字，以及减少节点组内节点间的指针，以减少节点组的存储容量，并且节点组大小不大于缓存的容量，则每次从内存可以读入一个完整的节点组到缓存，这样有效提高节点组内关键字的缓存命中率，只有查询节点组外的关键字时才会发生命中失败。文献［14］实验结果表明，CST树在查询速度和cache命中率方面比CSB树和B+树的性能都好，虽然CST树在修改时效率不高，但对于相对比较静态的块内索引，CST是最合适的选择。

2.3 三级缓存结构

三级缓存结构分别为:NameNode服务端缓存、DataNode数据端缓存、客户端缓存。

服务端缓存小文件标签的散列索引，客户端访问小文件时，NameNode通过散列函数计算出所在标签桶，首先在服务端缓存查询标签桶的存储地址。再由标签桶中小文件映射索引查找出该小文件所在的小文件映射索引块，将该索引块返回给客户端，并加入到客户端缓存，客户端进行访问小文件时，首先在客户端缓存中查找小文件映射，从而减少与NameNode的交互次数。数据端缓存则缓存小文件的块内索引，以有效提高小文件块内的访问效率。

3 SFSHI策略实现

本文小文件存储策略中，Client客户端完成小文件标记与合并、与DataNode之间的数据传输。NameNode服务器负责处理客户端请求、标签索引管理、小文件映射索引管理。DataNode负责完成数据存储和读取操作、小文件块内索引管理、本身所存储数据块的管理。

3.1 小文件存储流程

本文的小文件存储流程如图3所示。

图3 存储流程图Fig.3 Storage process

当客户端中某标签小文件的数据块已满，调用存储小文件的方法writeSF，DataNode服务器添加接收小文件并更新元数据的方法receiveSF。方法描述为

3.2 小文件读取流程

本文的小文件读取流程如图4所示。

图4 读取流程图Fig.4 Access process

客户端添加小文件读取方法readSF，获取小文件的所在blockId及DataNode列表。DataNode上添加方法querySF，读取小文件块内索引及小文件内容并返回。方法描述为

4 实验与结果分析

4.1 实验环境

实验环境搭建了12个节点的Hadoop集群，每个节点的配置为:6核Intel Xeon CPU 2.4 GHz，8 GByte内存，10 TByte硬盘。网络环境是千兆光纤。其中一台机器作NameNode，一台作SecondNameNode，12台机器全部作DataNode。每台节点安装的操作系统为Cent OS5.4，Hadoop版本为cdh3u6，JDK的版本为1.6.0_35。

4.2 数据集

实验数据是大量小文件，小文件格式有图片、文本文件、二进制文件。数据来源为某电信公司营业终端服务与集约化管理平台各客户端产生的操作日志文件及用户数据，其中，操作日志文件大小为1-300 KByte，用户数据文件大小为1-4 MByte，该平台每天产生约210 000个小文件，文件总量约40 GByte。这些数据海量，且都是大小集中在1 KByte-4 MByte的小文件。测试用到的文件集合共435 462个文件，总量为89.4 GByte，小文件大小分布如图5所示。

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

4.3 实验对比

在集群上部署Ganglia集群监控系统，它可以提供准确而有效的实验结果来对实验进行评价。实验对比的主要指标是:NameNode的内存开销，读取小文件的时间开销。

从存储435 462小文件的集群中，读取6组不同数量的小文件，每组进行10次实验，对实验结果取平均值。对HDFS原小文件存储策略和基于混合索引的小文件存储策略2种测试环境下读取文件的耗时和内存开销进行统计。

小文件读取时间开销对比如图6所示。图6结果表明，基于混合索引的小文件存储策略读取小文件的速度比HDFS原方案读取速度快得多。

图6 小文件读取时间开销对比Fig.6 Time cost comparison when accessing small files

小文件读取时，NameNode的内存开销对比如图7所示，结果表明，基于混合索引的小文件存储策略中NameNode的内存占用率大大减少。SFSHI策略中NameNode内存只存储合并后大文件标签元数据，并且将大文件标签索引加载到NameNode缓存，小文件映射索引存储在NameNode磁盘上;同时，如果所访问的小文件映射在客户端缓存命中，则可以减少与NameNode的交互，所以SFSHI策略能显著降低NameNode的内存开销。

图7 内存开销对比Fig.7 Memory overhead comparison

综上所述，基于混合索引的小文件存储策略SFSHI对同一标签的小文件作为一个大文件存储管理，同时采用的服务端缓存和客户端缓存，减少了NameNode的内存开销;针对本文小文件存储策略，合理地采用三级缓存和混合索引策略，在一定程度上减少了索引文件存储空间，同时有效提高了小文件的读取效率。

5 结语

本文分析了HDFS中小文件处理机制，针对小文件过多时占用NameNode内存开销、从合并文件中访问小文件的效率不高等问题，给出了一个基于混合索引的小文件存储策略，该存储策略核心在于应用分类器分类标记小文件，同一标签的小文件作为一个大文件存储管理，减少了元数据数目;针对本文中小文件存储策略，设计了混合索引机制，提高了小文件访问效率，实现中采用缓存结构，同时也解决了NameNode内存负载问题。实验及结果表明，本文小文件存储策略能有效提高海量小文件的访问效率，并大大减小NameNode的内存负载。

［1］郝杰，逯彦博，刘鑫吉，等.分布式存储中的再生码综述［J］.重庆邮电大学学报:自然科学版，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，FOX 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］王铃惠，李小勇，张轶彬.海量小文件存储文件系统研究综述［J］.计算机应用与软件，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，FL:IEEE Press，2010:65-72.

［12］赵跃龙，谢晓玲，蔡咏才，等.一种性能优化的小文件存储访问策略的研究［J］.计算机研究与发展，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.