周 斌，毕传美

(中南民族大学 计算机科学学院，武汉430074)

一种基于频繁项挖掘的大量小文件动态合并算法

周 斌，毕传美

(中南民族大学 计算机科学学院，武汉430074)

分析了当前社交网络中大量小文件数据特点，将访问日志与数据挖掘相结合，提出了一种基于频繁项挖掘的大量小文件动态合并算法.此算法实现小文件动态合并，解决了合并文件的一致性问题，从而预测用户下一步的访问，为预取小文件做引导，提高预取的命中率.针对预取和缓存的文件过多的特点，设计了一种新的含循环单链表的缓存置换算法优化缓存内容.通过实验证明，该算法大量小文件动态合并性能优于已有的算法.

大量小文件；频繁项挖掘；动态合并

1 相关的工作

社交网络的发展产生了大量小文件，这些小文件数据体量巨大[1]，并且单个文件容量小[2]，且其数据呈重尾分布的特点，这决定了少量的数据会被大量的用户访问.大量小文件在元数据管理、访问性能等方面面临巨大的挑战，也因此成为当前业界关注和研究的热点问题.

Liu Changtong等设置专门的小文件处理模块，上传文件之前先判断是不是小文件，以key-value形式存储小文件索引信息[3].该方案减少了NameNode内存消耗，key-value形式的索引提高了访问的效率，但是没有考虑文件的相关性.Hao Xingjun等处理的是物联网中的大量小文件，提出了文件存储系统SensorFS、分布式内存文件系统DMFS、并行化的合并文件方案[4].该方案改进了HDFS的I/O性能.但是方案中没有考虑合并文件的一致性，即一个小文件可能合并到多个文件中.

由于传统的静态合并方案不适合用户的动态访问过程，因此本文提出基于访问日志的动态合并，将访问过程中的“热”的数据合并到一起.

2 基于频繁项挖掘的动态合并算法

本文借鉴频繁项挖掘中购物篮分析的思想[4,5]，综合考虑合并文件的一致性，提出基于频繁项挖掘[6]的动态合并算法，获取小文件的关联性，将关联性高的小文件动态合并，从而提高文件预取的效率.

Web文件访问日志示例如表1所示.本文对Web中的日志文件进行整理，将访问日志中的IP地址进行记录的划分，根据指定的时间间隔T，来分隔每个记录集，将一个时间段T内访问的文件放到一条记录中，得到的数据如表2所示(其中T1,T2,T3,T4,T5表示时间间隔).本文是用1min为一个T.Fabricio B等[7]调查文件的相关性与访问的持续时间的关系，通过调查发现90%的用户访问社交网络的会话时间在1min内，因此取1min为时间段，该时间段内的文件相关性最大.

表1 文件访问日志示例

表2 文件访问日志整理得到的数据举例

在此基础上，本文实现了一种基于频繁项挖掘算法，算法如下：

(1)统计T时间段内，单个用户访问的文件个数，找到最大值，设为k，同时将需要合并的文件个数定为k；

(2)扫描Web日志整理后得到的数据库如表2，对数据库中每一个记录做如下操作：将记录中所有的大小为k的子集求出来(Mapper)；

(3)统计输出所有小文件子集的个数，如果某个小文件子集的个数超过了某一阈值s，并且该子集项在大于k的子集中没有出现过，将所有子集输出(Reducer).

算法中求取小文件子集采用数组，数组下标从1开始，每项用0或者1代表.数字“0”表示代表的数没有被选上，输出的子集中不会有这一项.数字“1”表示代表的数被选上，输出的子集中会有这一项.

对于n项元素，求大小为k的所有子集，分为以下几个步骤：

1)将前k项元素初始化为1，后面n-k项初始化为0，某一项对应的位置为1，表示该项属于该小文件子集.初始化可以得到小文件第一个子集；

2) 从数组第一位开始扫描找到数组排列中第一个“10”，这里“10”是指某连续两位，前项为1，后项为0.如果有，则需要交换位置，将“10” 修改为“01”，此时数组中子集的对应位置会改变.同时把该“01”左边所有的“1”都移到数组的第一个位置依次排列；

3)判断是否结束，判断的条件为k个“1”全部移到最右端，这是最后一个子集的组合.

由于是大量小文件，子集的求取需要并行化的设计.并行化算法主要是通过Mapper和Reducer实现[8].对于每个Mapper，算法的实现主要是对每一行的文件数据进行分片，以逗号分隔元素，调用求取子集的算法，获取所有大小为k的小文件子集，并且输出；对于每一个Reducer，算法的主要功能是负责汇总和判断，将小于支持度阈值s的、并且在大于k的子集项中没有出现过的子集汇总，最后将结果输出.

基于子集检测的频繁项挖掘算法中有两点保证了合并文件的一致性：一是k的初始值选择由大到小；二是加入了检测模块.

针对表2的合并，k的初始值为4，假设支持度阈值为2.首先检测有没有符合k为4，支持度阈值为2的子集.然后检测k为3，支持度阈值为2是否符合，循环下去.经上述处理后会得到处理结果2，3，5，表明{2,3,5}这个频繁项集满足算法设计的结果.那么合并小文件时将2，3，5这3个小文件放到一个容器中，然后再按照小文件的合并流程合并小文件.经上述论证，基于子集检测的频繁项挖掘算法可以实现小文件的动态合并，并且可以保证合并文件的一致性.

3 置换算法的实现

随着用户访问和预取文件的增多，放入到缓存中的文件会占用大量的缓存空间.为此就需要有缓存置换算法清理缓存中的内容.本文将数据块容器(Container)中最近时间内很少访问或者不访问的文件清理出缓存.

数据换出缓存是以T=1min为单位的.如图1所示，采用循环单链表将一段时间T内访问过的Container链接起来.可以看到单链的设计是在每一个Container中添加一个指针，指向T内访问的其余的Container，循环的设计是将最后一个Container指向第一个Container.本文将这种缓存中使用循环单链表的方法称为含循环单链表的缓存置换法.

由图1可知，如果需要置换缓存中的数据，就选择循环单链表中的一个环，将时间T内访问的所有Container项清理出去.因此，需要有队列Q来保存循环单链表的先后访问顺序.队列中的节点保存环所在的任一个Container的地址.如果环中的Container刚被访问，则将该节点保存到队列头部.随着访问的改变，队列中的数据不断发生变化，没有被访问的就处于尾部.置换数据选择队列尾部的节点，将指针所指的循环单链表中的项逐个删掉，最后从队列中彻底清除.

图1 含循环单链表的缓存替换Fig.1 Cache replacement method with single cycle list

对于缓存而言，缓存清理算法的设计至关重要，算法的流程主要分以下几步：

1)取出队列尾部的待删除节点；

2)逐个删除该节点所对应的容器中的文件；

3)删除列队的尾节点.

经过上述处理，系统可将缓存中最近不再访问的数据删除，为即将访问的热点数据和预取数据预留空间.

4 测试结果与分析

实验分为两个部分进行测试和分析.第一部分是NameNode内存消耗的测试，具体来说是将改进后HDFS消耗NameNode内存和原始HDFS消耗NameNode内存进行测试，并且对测试的结果进行分析；第二部分测试是访问文件的ATPMB的测试，将改进后的HDFS与原始HDFS和HAR进行对比，包括顺序读取文件的ATPMB和随机读取文件的ATPMB.测试结束后对测试的结果进行分析.

4.1 测试环境

本实验采用Hadoop1.2.1进行仿真，在VMware10上配置3个结点的Hadoop集群，每个结点的内存为1GB，3个结点中，一个设置为NameNode，另外两个设置为DataNode节点.小文件集总大小为1.03GB，共有817个小文件，都在4MB以内.小文件类型和小文件大小的比例如图2和图3所示.文件的类型有文本文件、图像文件、音频文件、视频文件.图像文件占总文件的53%.小于1MB的文件占总文件的51%.每个实验做4次，选取平均值作为结果.

4.2 测试与分析

本文实验对比指标：1)NameNode的内存开销；2)访问文件的评价标准是读取1MB的文件需要的时间，单位为秒(s)；3)上传小文件的时间消耗.

读取1MB文件的耗时可用ATPMB表示为：

(1)

实验分别上传200、400、600、800个小文件到改进HDFS、原始HDFS以及HAR上，文件随机选取达到指定数，并统计每次的内存消耗.

从图4中可以看出，改进的HDFS能降低NameNode的内存开销，平均使用内存空间分别为原始HDFS的35.37%和HAR的85.24%.改进的HDFS比原始的HDFS和HAR有优势.这因为原始HDFS没有合并方案，每个文件占有NameNode内存，严重浪费内存.改进的HDFS将小文件合并后再存储到HDFS中，节省内存的原因有两点：一是合并减少了在NameNode中存储的元数据量；二是把生成的小文件BlockIndex文件放在DataNode中，节省了大量的NameNode内存空间.从图4中还可以看出，HAR存储文件占用的内存比原始HDFS少，这是因为HAR将文件合并，但是效果没有本文改进的方案好.图4中，随着文件数量的增多，主节点的内存消耗呈上升趋势，但不是直线上升.主要是因为在HDFS的运行过程中，需要周期性将元数据文件fsimage和操作日志edits合并.

图2 小文件的类型比例Fig.2 Proportion of small file type

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

图4 内存消耗对比Fig.4 Memory consumption comparison

读取测试分为两部分：顺序读取小文件和随机读取小文件.顺序读取小文件是本文测试的重点，这也是本文的实验目的.在社交网络中，单个用户的文件具有很强的相关性.并且数据呈重尾分布的特点，使得一些用户的少量数据被大量访问，那么延迟会增大.本实验中，改进的HDFS初次写入文件用静态的小文件合并处理方法，随着用户的访问，会产生访问日志，再对这些访问日志以1min为单位进行处理，将容器中的相关数据提前预取出来，减少访问的延迟.实验配置5个block的文件缓冲区大小.实验中取200、400、600、800个小文件分别对原始HDFS、HAR、改进HDFS三种方案进行测试.由公式(1)计算每次的ATPMB，见表3.

由表3可计算得出ATPMB的平均值，原始HDFS为6.78，HAR为7.89，改进HDFS(顺序)为5.98.即访问1MB的数据，HAR方案耗时最多，改进的HDFS耗时最少.从表3可以看出，当顺序读取小文件时，改进的HDFS与原始HDFS、HAR相比，消耗的时间明显减少.性能好的原因主要有两个：一是提前将接下来有可能访问的文件预取到Cache中，极大地减少了Client端与NameNode和DataNode的交互次数，节约了大量的时间；二是全局索引的设计，本文采用直接定位的方式，避免了在大量文件中的查找，也节省了时间.两方面的结合使得改进HDFS在顺序读取文件上，与原始HDFS和HAR相比节省了大量的时间.表3中可以看出，HAR的ATPMB值最高，这是因为读取过程中需要额外访问两级索引，消耗了时间.

随机读取小文件的ATPMB均值为7.85，比顺序读取小文件的时间消耗多，这也是改进HDFS的不足之处.这是因为每次都要与HDFS进行交互，并且改进的HDFS中的预取与缓存的优化方案在随机读取文件中，没有显示出作用，反而成为负担.改进HDFS随机访问文件比原始HDFS随机访问文件消耗的时间相对多，有微弱的差距，但在可接受的范围内.

表3 读取文件测试的ATPMB对比表

5 结语

本文主要针对社交网络中大量小文件，包括文本、图像、音频、视频四种类型的文件，在HDFS中的存储做了深入的研究.其关键技术包括两点：第一是提出一种新的动态合并算法；第二在动态合并的基础上，实现一种置换算法优化缓存内容.经过实验测试，本算法动态文件的合并性能优于已有算法.

[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-)，男，副教授，博士，研究方向：大数据存储与处理，E-mail：binzhou@mail.scuec.edu.cn

湖北省自然科学基金资助项目(2016CFB650)

TP311

A

1672-4321(2016)04-0111-05