基于MapReduce的海量数据动态装箱算法研究
2015-08-06陶昕计春雷
陶昕 计春雷
摘 要：针对传统装箱算法在处理海量数据时所存在的的运行效率与空间利用率低的问题，在深入研究已有装箱算法的基础上，在分布式系统中定义一种可变大小的箱子，结合动态和静态算法的优势，提出基于MapReduce的动态装箱算法。实验结果表明，针对海量动态数据，运用基于MapReduce的动态装箱算法，结果接近最优解，同时具有很高的处理效率。
关键词：装箱算法；海量数据；分布式系统； MapReduce
DOIDOI：10.11907/rjdk.151567
中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2015）007-0066-05
0 引言
随着云计算和物联网技术的快速发展，数据量呈爆炸性增长。据WinterCorp统计显示，互联网产生的数据量每两年增长3倍[1]。在互联网技术极速发展的背景下，大数据应运而生，人们生活正在逐渐被巨大的数据量所包围。企业经营信息、电子商务商品物流信息、社交网络交互信息、位置信息等数据量远远超越现有企业IT架构和基础设施的承载能力，实时性要求也大大超越现有的计算能力。大数据正在逐渐影响人们的生活方式。同时，大数据的产生给传统的数据管理带来了巨大的挑战。针对海量数据的处理将成为大数据时代必须面对的问题。
Hadoop是一个开源的、具有高可靠性和良好可伸缩性的分布式计算框架，可以对海量数据进行分布式处理，其分布式计算模型MapReduce可以将数据集分割成若干小数据单元，这些小数据单元可以被放置在任何一个节点上进行处理[2]。Hadoop分布式文件系统（HDFS）专门为存储和管理海量数据而设计，其默认存储单元值为64M，但实际应用中所产生的数据大多小于64M，直接处理这些数据将造成内存浪费，降低整个系统性能。
MapReduce是Hadoop分布式框架中的并行计算模型，可以对海量数据进行并行处理。它最早由Google提出并实现，运行在Google的分布式文件系统GPS（Google File System）上。MapReduce将海量数据处理分散到各个分节点共同完成，然后整合所有分节点的中间结果得到最终结果[3]。随着数据量的不断增长，传统算法效率较低，同时造成很大的资源浪费。随着云计算技术的发展，面向云计算平台对传统算法进行改进，可以提高海量数据处理效率。
装箱问题是最经典的组合优化问题之一，将若干大小不同的物件，通过某种填装策略，将所有物件放置到尽可能少的箱子内[4]。该模型在现实生活中广泛应用于各领域，例如资源调度分配、内存动态分配、物流货物装载等。装箱问题的思想也可运用在海量数据处理上，例如在数据存储与传输过程中，将数据进行装箱存储或传输，可很好地提高数据处理效率。随着数据量的指数级增长，传统装箱策略处理的结果已不能满足实际需求，处理效率与空间利用率较低。据此，本文在深入研究已有装箱算法的基础之上，结合动态和静态两种算法的优势，基于MapReduce并行计算模型对海量数据装箱算法进行研究。
1 相关研究
装箱问题算法已经被证明是一个NP难解问题，所以针对装箱问题的研究通常运用近似算法[5，6]。所谓近似算法即该算法可以求得与精确解接近的结果，但不一定得到最优解。装箱算法具有很好的实际应用价值，诸多学着对装箱算法进行了广泛研究。Johnson等[7]证明了装箱问题是个NP难解问题，此后的研究专注于相关近似算法研究。针对一维装箱问题本文给出如下描述：
任意给定一个含有N个数据项目的序列：S1，0≤Si≤1，0≤Si≤1…0≤Si≤1，使得0≤Si≤1。项目不可被切割，这些数据需要存储在内存容量为1的内存“箱”中，目标是尽可能用最少的箱子存储这些数据[8]。假设K为箱容量，则一维装箱问题可以表示为：
∑Si≤Ki（1）
其中，0≤i≤n。目前，针对装箱问题的研究主要集中在物流货物存储和系统中的任务资源分配方面。针对货物存放，将尽可能多的货物存放在尽可能少的不同大小箱子中，并且存放在尽可能小的空间内。在处理海量数据时，将数据进行装箱处理，可以使数据传输次数减少，从而有效提高系统处理效率，降低系统功耗。一维装箱问题的近似算法按照其特征可以分为动态算法和静态算法两种[9， 10]。其中，动态算法主要有首次适应算法（FF First Fit Algorithm）、下次适应算法（NF Next Fit Algorithm）和最佳适应算法（BF Best Fit Algorithm）。而静态算法主要有降序首次适应算法（FFD First Fit Decreasing Algorithm）和降序最佳适应算法（BFD Best Fit Decreasing Algorithm）。动态是指按照数据的先后顺序进行输入装箱，不知道后面数据的具体情况，即数据到达便直接进行装箱，不考虑后续数据情况[11]；反之，静态是指需要被装箱的数据个数和大小全部是已知的，从而按照一定的策略进行最优装箱。装箱算法的静态算法效率要优于动态算法，能在较短时间内提供最优解决策略。动态算法更为实际，在局部范围内可以取得最优解。常见近似算法及运算过程如下：（1）首次适应算法：从空闲存储区的开头开始检索，将最先能够容纳数据的区域分给该数据，这种算法的优点是可以大大减少查找所消耗的时间[12， 13]。（2）下次适应算法：在分配数据时需要记住前一次分配数据的位置，然后实施分配时从该位置后开始查找一个合适的空闲存储区[14]。（3）最佳适应算法：该算法过程与首次适应算法相似，区别在于数据不是存储在最先能够容纳它的存储区，而是存储在最适合该数据的存储区，如果没有合适的存储区，则存储在下一块空闲存储区。这种算法的优点是既可以满足存储空间需求，又尽可能少地占用空闲存储区。这样使得空闲存储区被分配数据后，剩下的空间尽可能小，使得内存利用率最大化[15]。（4）降序首次适应算法：首先按照数据容量对数据进行降序排序，然后按照首次适应算法对数据进行装箱存储处理。（5）降序最佳适应算法：首先按照数据容量对数据进行降序排序，然后按照最佳适应算法对数据进行装箱存储处理。举例对上述5种装箱算法过程进行描述。假设箱容量为10，项目列表中项目大小分别为：8，4，2，3，7，3，6，5。分别运用上述算法将项目列表中的项目装入箱中，结果如图1所示。
图1 不同装箱算法过程
如图1所示，装箱算法静态算法的运算结果要优于动态算法，但在实际应用中经常要面对动态环境，故动态环境下运用静态算法来处理数据值得深入研究，可以高效地对海量数据进行最优处理，并明显提高内存利用率。
动态规划算法DP（Dynamic Programming Algorithm）是一种多阶段最优化决策解决问题的过程[16-17]，其基本思想与MapReduce并行计算模型相似，即将原问题分解为相似的子问题，在求解过程中通过子问题的解求出原问题的解。主要优势在于可以避免重复计算，可以在获得问题最优解的同时有效降低时间复杂度。针对动态规划算法本文给出如下描述：
任意给定一个含有M数据项目的序列：S1，S2，S3…Sm，使得0≤i≤1。数据元素i开始，到元素j为止所有元素构成的子段有多个，选择所有子段中子段和最大的子段。则动态规划算法可以表示为：
Sj=max1≤i≤j∑jk=iak（2）
其中，1≤j≤m。如果S[j-1]>0，那么S[j]=S[j-1]+a[j]；如果S[j-1]≤0，那么S[j]=a[j]。举例对动态规划算法过程进行描述。假设箱容量为10，项目列表中项目大小分别为：8，4，2，3，7，3，2，5。运用动态规划算法将项目列表中的项目进行装箱，结果如图2所示。
图2 动态规划算法装箱过程示意图
由图2可知，运用动态规划算法显然可以使得在尽可能短的时间内获得最优局部最优解。在MapReduce计算模式下，用户设定一个Map函数，将原数据分解成一批键值对
Map：
Reduce：
数据集通过Map函数被分解成一批键值对
图3 MapReduce处理大数据集的过程
本文主要针对海量数据装箱问题运用基于MapReduce的FFD算法和DP算法进行研究。
2 算法描述
2.1 基于MapReduce的FFD装箱算法设计
在动态环境中，设置一个缓冲区，将所有输入数据项目逐一输入到这个缓冲区，当缓冲区装满数据项目时，将其提交给MapReduce的主节点进行Map和Reduce操作处理，同时缓冲区开始接收数据，准备再次向MapReduce主节点进行传输。如此设计的优点在于使装箱算法在动态环境下具备静态算法的优点，故本算法设计可以对海量并发数据进行高效装箱处理，提高系统利用率。基于MapReduce的FFD装箱算法的步骤如下：
（1）输入。缓冲区接收需要处理的数据集，根据已收集的数据输入箱容量和数量。当缓冲区接收满数据，将数据提交至MapReduce主节点。（2）Map。将被提交的数据集传输到各映射节点，每个映射节点都独立对数据集进行处理。将特定箱容量的数据项目列表提取出来，并使用快速排序对列表进行升序排序。将箱容量作为key，然后将排序好的项目列表作为value。（3）合并列表。将Map处理后产生的键值对在本地按照键值进行合并，并对其进行升序排序。将产生的结果输入到Reduce处理阶段。（4）Reduce。Reduce节点将上阶段完成排序的映射项目列表作为输入。Reduce在此处运用降序首次适应算法，将输入数据进行装箱。由于特定大小的箱中数据项目已排序，所以此阶段得到的结果是已提交数据的最佳装箱方案。经过MapReduce对算法进行优化，产生的结果包括箱容量和装箱后箱子最优分配列表。算法伪代码如图4所示。
2.2 基于MapReduce的DP装箱算法设计
该算法与FFD装箱算法的算法步骤相同，唯一的区别在于Reduce阶段使用了动态规划算法。算法伪代码如图5所示。
2.3 算法分析
由于两种算法中设置的箱子大小为可变，可以理解为箱子大小总是与物体刚好合适。这样在装箱过程中，可以获得良好的利用空间。即使箱子大小上限会因系统的设置对空间利用造成一定影响，但在处理海量数据的过程中依然可以很好地利用存储空间。这种设计思想来源于，在装箱过程中往往预先设定了箱子大小，然后考虑物品如何进行装箱。如果存在一种箱子，其大小可变，总是可以与将要处理的物品大小相同，那么当物品输入开始进行处理时，便可以直接进行装箱处理，且具有较高的空间利用率。其时间复杂度分析如下：基于MapReduce的FFD装箱算法在Map阶段使用了快速排序，因此其复杂度为O（nlogn），其中n为每个key对应的项目数。在Reduce阶段，将非递减项目列表分配到特定的箱子中，本文使用降序首次适应算法，所以Reduce阶段的复杂度为O（n）。假设一共有m个箱子，则两个阶段整体复杂度为：
F（n）=m（O（nlogn）+O（n））（5）
在并行计算模式下，假设在Hadoop框架中设置了N个节点，算法中设置了x个Mapper和y个Reducer，则算法复杂度为：
F（n）=O（mnlognNx）+O（mnNy）（6）
可化简为：
F（n）=O（nlogn）（mNx）+O（n）（mNy）（7）
可以看出，算法运行时间与节点数量成反比，并且与Mapper和Reducer的个数成线性关系。由于算法主要计算在Map阶段，所以通过增加节点和Mapper的个数可以在短时间内获得更好的结果。计算基于MapReduce的DP装箱算法的复杂度，其在Map阶段使用了快速排序，复杂度为O（nlogn），n为每个key对应的项目数。在Reduce阶段，将非递减项目列表分配到特定的箱子中使用了动态规划算法，其复杂度为O（n2）。假设一共有m个箱子，则整体复杂度为：
F（n）=m（O（nlogn）+O（n2））（8）
同样，在并行计算模式下，假设在Hadoop框架中设置了N个节点，算法中设置了x个Mapper和y个Reducer，则算法复杂度为：
F（n）=O（mnlognNx）+O（mn2Ny）（9）
可化简为：
F（n）=O（nlogn）（mNx）+O（n2）（mNy）（10）
可以看出，两种算法运行时间均与节点数量成反比，与Mapper和Reducer的个数成线性关系。由于动态规划算法中主要的计算在Reduce阶段完成，所以通过增加节点和Reducer的个数可以在短时间内获得更好的结果。
本文通过实验设置不同的节点个数，并且设置不同的Mapper和Reducer个数，将两种算法进行对比。实验结果表明，两种算法运行时间均与节点数量成反比，与Mapper和Reducer的个数成线性关系。
3 实验结果
本文所作算法研究的实验环境建立在虚拟机集群上，所提算法在Hadoop集群上运行测试。Hadoop集群有10台机器构成，其中1台作为主节点，其余的作为分节点，电脑配置均为奔腾双核、4G内存，操作系统为Linux，Hadoop版本为hadoop-0.20.2，Java版本为JDK1.6.0_37。
实验模拟动态环境，随机选取若干10K到10MB的图像数据作为输入，箱容量设置为接收数据的数量为100个。分别设定1，4，8个节点，每个节点先设置为默认的2Mapper-2Reducer，然后分别运用两种算法进行实验。然后设定2个节点，分别设置每个节点，部署2Mapper-4Reducer和4mapper-2Reducer，对本文提出的两种算法进行实验。
本文运用传统FFD算法和DP算法对上述数据进行实验，与本文所提的基于MapReduce的FFD算法和DP算法对系统内存利用率进行比较。
由表1可知，两种算法在对海量数据进行装箱处理时，随着设置节点的增加，运行时间缩短，并且随着数据量的增加，时间缩短越来越明显。在面对海量数据的情况下，本文所提两种算法均可以通过增加节点来缩短运行时间，提高数据处理效率。
通过上文对两种算法复杂度的分析，由表2和表3可知，在节点不变的情况下，增加Reducer数量时，基于MapReduce的DP装箱算法处理海量数据运行时间将大大缩短，相比FFD算法更高效。同样，在增加Mapper数量时，基于MapReduce的FFD装箱算法处理海量数据运行时间大大缩短，相比DP算法更高效。
由图6可以看出，本文所提基于MapReduce的FFD算法和DP算法在对海量数据进行处理时，相比传统FFD算法和DP算法可以获得较高的系统内存利用率。
综上，本文所述两种算法可以高效地对海量数据进行处理，具有很好的系统内存利用率。同时，减少处理时间，有效地降低了时间成本，并且通过算法复杂度分析和实验验证了两种算法运行效率与节点数量设置，以及节点上Mapper和Reducer的数量设置均有关联。根据实际情况，通过调整节点数量和Mapper-Reducer数量可以使该算法处理海量数据得到最优结果。
4 结语
本文针对已有装箱算法在处理海量数据时所存在的时空效率较低的问题，在深入调研已有算法的基础之上，结合在线、离线两种算法的优势，提出了基于MapReduce的并行装箱算法，并在Hadoop集群上进行了实测验证，结果良好。本文所提可变大小的箱子，对于装箱算法的研究有很好的启发，具有研究空间。本文研究尚处在初级阶段，所提算法只能应用于一维装箱场景中，而且成果只达到局部最优，二维或多维以及近似全局最优是未来研究的重点。
参考文献：
[1] 王珊， 王会举， 覃雄派等.架构大数据： 挑战、现状与展望[J].计算机学报， 2011，34（10）：1741-1751.
[2] CHUCK LAM. Hadoop实战[M].韩冀中译.北京： 人民邮电出版社， 2011.
[3] 刘鹏.实战Hadoop（第二版）[M].北京： 电子工业出版社， 2011.
[4] 陈建新， 杨宇航， 龚玲等.两种在线装箱算法[J].计算机工程， 2006，32（13）： 4-6.
[5] 邵飞牛.一维装箱问题启发式算法的设计与分析[D].沈阳： 东北大学信息科学与工程学院， 2013.
[6] ROLICH T. Testing of several overlapping optimization methods for bin-packing problem[C]. Information & Communication Technology Electronics & Microelectronics （MIPRO）， Opatija， 2013. Croatia： Hrvatska， 2013： 975-980.
[7] COFFMAN E G， GAREY J M R， JOHNSON D S. Approximation algorithms for bin packing：a survey[M]. Approximation Algorithms for NP-Hard Problems， Boston： PSW publish， 1997.
[8] ANIKA， GARG D. Parallelizing generalized one-dimensional bin packing problem using MapReduce[C]. 2014 IEEE International Conference on Advance Computing Conference （IACC）， Gurgaon， 2014. India： ITM University India， 2014： 628-635.
[9] LEAH EPSTEIN，LENE M，FAVRHOLDT， et al.Comparing online algorithms for bin packing problems[J]. Journal of Scheduling，2012.
[10] LI LUO，YANG YOU. Surgical scheduling based on offline bin-packing[C]. Service Systems and Service Management （ICSSSM）， Shanghai，China： Economics & Management School， Tongji University， 2012： 491-494.
[11] LEAH EPSTEIN， ROB VAN STEE.Optimal online algorithms for multidimensional packing problem[J].SIAM Journal on Computing，2005.
[12] 马玉玲.遗传算法在物流业装箱环节中的应用研究[D].济南：山东大学，2008.
[13] 杨双全.虚拟化动态资源调度的算法设计与系统实现[D].杭州： 浙江大学，2012.
[14] 田爱雪.基于海量数据存储的性能测试与优化研究[D].长春：长春理工大学，2014.
[15] 邰建华.Hadoop平台下的海量数据存储技术研究[D].大庆： 东北石油大学， 2012.
[16] 张莹.动态规划算法综述[J].科技视界，2014，28（10）：126.
[17] 吴海洋，程国建，赵坤鹏，等.基于动态规划的整车物流装载方案优化研究[J].电脑知识与技术，2014，33（10）：8046-8050.
（责任编辑：陈福时）