Hadoop集群中给定候选任务集的最大利润问题

郑羽 罗汉云

摘要：随着计算机网络和传感器网络的迅速发展，数据呈指数级增长，特别是在因特网上。为了有效地处理大规模数据，需要具有良好的可伸缩性、灵活性和容错性的并行分布式集群。目前，许多企业基于自己的Hadoop集群提供云服务。因为单个Hadoop集群的资源是有限的，Hadoop集群必须将有限的资源分配给一些特殊的任务以获得最大的利益。该文研究给定候选任务集的最大利润问题。用有效的序列描述候选任务集，并提出了一种基于序列的调度策略。为了提高查找有效序列的效率，设计了一些修剪策略，并给出了相应的调度算法。最后，在某些任务运行超时的情况下，我们提出了超时处理算法。实验表明，该算法的总收益非常接近理想的最大值，在不同的实验环境下明显优于相关的调度算法。

关键词：MapReduce;任务集;调度算法;利润;大数据

中图分类号：G642 文献标识码：A

文章编号：1009-3044（2020）08-0269-05

随着计算机网络和传感器网络的迅速发展，数据呈指数级增长，特别是在因特网上。为了有效地处理大规模数据，需要具有良好的可伸缩性、灵活性和容错性的并行分布式集群。由Google提出的MapReduce[3]架構，应用分而治之的方法来处理数据密集型任务，是大数据领域一个既成事实的标准。Google使用了一个运行MapReduce和相关技术的大型集群，诸如GFS[2]和Bigtable[3]，每周处理PB级数据以上。在这种服务过程中，企业与客户之间的服务细节通常是通过服务水平协议来（SLA）[4，5]描述的。SLA分两种，根据数量定价和根据有效性定价。根据数量定价的SLA向客户收取与硬件规模和服务时间成比例的费用。根据有效性定价的SLA依据服务效能向客户收费。以垃圾邮件检测服务为例，该服务必须在一定时间内完成，因此，只有服务在规定时间内完成，才会支付款项。本文研究了如何安排客户的任务以使得Hadoop集群的总利润最大化。在研究中，主要关注的是定时MapReduce任务，它是以时间的有效性为代价的，即任务必须在给定的时间内完成。在这里将每个任务抽象为四个部分，即用户定义的Map/Reduce函数、完成时间、利润和惩罚，并试图找到一个最大化Hadoop集群总利润的调度算法。

1 相关知识

这一部分简要介绍了MapReduce，然后回顾了有关MapRe-duce任务调度的工作。

1.1 Mapreduce环境

MapReduce是一种流行的面向数据密集型任务的编程模型，在许多领域得到了广泛的应用[6-8]。Hadoop是一个由Apache基金会所开发的分布式系统基础架构。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力进行高速运算和存储。Hadoop实现了一个分布式文件系统（Hadoop Distributed File System），简称HDFS。HDFS有高容错性的特点，并且可以部署在低廉的Clow-cost）硬件上;而且它提供高吞吐量来访问应用程序的数据，适合那些有着超大数据集的应用程序。图1所画的就是MapReduce框架，在用户定义的map函数中，输入是一个键值对，输出是零或多个键值对。在组步骤中，具有相同密钥的系统组键值对会被发送到相同的还原节点。在自定义的Reduce函数中，组合键值对处理产生的结果。MapReduce任务通常需要多次Map/Reduce迭代。

1.2相关工作

在MapReduce，有一些通用的任务调度程序，如FIFO调度器、基于容量的调度器和基于公平的调度器。在具体应用中，Sandholm和Lai等人提出了一种调度算法，允许用户根据Ma-pReduce任务的重要性动态调整需要的计算资源。Zaharia等人提出了异构集群环境下的调度算法，Kwon等人提出了skew-tune算法处理MapReduce任务的过程偏度。此外，还有一些调度算法，涉及在给定时间内完成的MapReduce任务。

1.3存在的问题

在本文中，目的是最大限度地提高同类的Hadoop集群的总利润，其中所有节点的计算能力是相同的。在一个Hadoop集群中，有M个Map任务，M个Reduce任务，对于每个提交的任务j，假设以下参数：

j.N，j中的Map作业数。

j.Nr，j中的Reduce作业数;为了获得高效率，j.N初j.N，是M的整数倍。

i deadline，j所规定的时间或期限。

j.profit√在截止时间前完成所获得的利润。

在上述两种情况下，都不可能按时完成JS中的所有任务，因此S必须不是有效的序列。

基于定理1和2，可以得出结论，所提出的调度策略对于固定序列S是最优的。这意味着如果在提议的策略下存在超时任务，那么它们必须存在于任何其他调度策略中。

1.4.2调度算法

在提出的基于序列的调度策略的基础上，本文提出了一种调度算法。首先，当候选任务设置是静态的，使用的评分策略为所有任务指定优先级，将找到可接受的任务并为其设定一个有效的修剪策略，并发现一个有效的序列。其次，当候选的任务集实现了动态更新，会执行增量法判断可接受的任务集和更新有效序列是否必要。

现在，分析了如何提高查找有效序列的效率。假设候选集通过公式2的计算进行了排序，即，穷举搜索法需要（|A|+1）！遍历所有候选序列的复杂性。为了提高搜索速度，给出了以下两种方法。

2 实验

2.1 实验设置

在实验中，Hadoop集群包含一个主节点和40个从节点，每个节点包含一个英特尔酷睿i3 3.1 GHz处理器，8 GB的内存和500 GB的存储，运行的操作系统是RedHat Linux 6.1。在从节点中，每个节点配置两个Map任务槽和两个Reduce任务槽。实验中的数据是enwi：ki（https;//dumps.wikimedia.org/enwi：ki/20150204/）运行了三个经典任务的数据集，即，统计词频，倒排索引、分布式grep。数据存储在Hadoop文件系统（HDFS）中，每一块是64MB，每个数据块有三份拷贝。对于一个候选任务集j，主要考虑以下三个影响性能的参数：

1）平均任务尺寸L，即L中所有任务的平均尺寸（块数）;

2）任务数N，即L中任务的数量;

3）平均期限D，即L中所有任務的平均期限（完成时间）。

总利润的计算在公式l中。此外，定义接收率和完成率如下：

接受任务集的大小

（3）

接受率= 候选任务集的大小

完成的任务数

完成率= 接受的任务数

（4）

2.2 实验结果

在实验中使用的基线算法是DC和WC。首先评估了任务数对总利润的影响，结果如图2所示。在图2a中，理想曲线是理想的利润，随着平均任务规模的增加，所有利润值都减少，但此方法接近理想值。在图2b中，所画的三个接收率逐渐降低，但此方法具有最高的价值，这意味着此方法可以获得最多的候选任务。在图2C中，所提出的方法比另外两种方法有更高的完成率。由于此方法不仅接收到最多的候选任务，而且完成大部分任务，因此可以带来最大的利润。

同时，观察了任务数和平均截止期对总利润的影响，结果如图3所示。由于同样的原因，方法不仅接收到最多的候选任务，而且完成大部分任务，因此可以带来最大的利润。此外，对三种情况的总利润非常接近理想值。

最后，动态地将任务提交给Hadoop集群，观察总利润的变化。在图中，水平轴是经过的时间，垂直轴分别是总利润、接收率和完成率。从数据可以看出，此方法不仅接收到最多的候选任务，而且完成大部分任务，因此可以带来最大的利润。这说明所提出的方法也适用于动态提交的任务。

3 结束语

本文研究了Hadoop集群中的最大利润问题，该资源在整个候选任务集中所占的资源不足。为了使利润最大化，基于候选任务集的有效序列选择了一些高利润率的任务。此外，为了提高查找有效序列的效率，设计了一些修剪策略，并给出了相应的调度算法。实验表明，该算法的总收益非常接近理想的最大值，在不同的实验环境下明显优于相关的调度算法。

参考文献：

[1]李玉丹，郑晓薇.Hadoop下多模式并行分类算法及其应用研究[J].计算机工程，2014（12）：45-49.

[2]王静蕾.Hadoop云计算框架中的分布式数据库HBase研究[J].商丘职业技术学院学报，2014（2）：18-20.

[3lchu cheng，et al.Map-reduce for machine learning on multicore[C]//Advances in neural information processing systems，2007，25[4]：19-281.

[4]1nza I，Larranaga P，Blanco R.Filter versus wrapper gene se-lection approaches in DNA microarray domain[J].Artificial In-telligence in Medicine， 2004，31（2）：91-103.

[5]向丽辉，缪力，张大方.压缩对Hadoop性能影响研究[J].计算机工程与科学，2015（2）：207-212.

[6）杨倩茹，黄梦醒，万兵，一种引入内存平衡的Hadoop平台作业调度算法[Jl.小型微型计算机系统，2014（12）：2708-2011.

[7]孙彦超，王兴芬.基于Hadoop框架的MapReduce计算模式的优化设计[J].计算机科学，2014（11）：333-336.

[8] B.K. Tripathy; Dishant Mittal;， Hadoop based uncertain possi-bilistic kernelized c-means algorithms for image segmentationand a comparative analysis[Jl. Applied Soft Computing. 2016，46（C）：886-923.

[9]Ganesh S，Binu A.Statistical analysis to determine the perform-ance of multiple beneficiaries of educational sector using Ha-doop-Hive[C]// International conference on data science&engineering.[s.I.l：lEEE， 2014：32-37.

[10] Berli 7 nska，M Drozdowski， Scheduling divisible mapreducecomputations[J]. Parallel Distrib. Comput，2011，71（3）：450-459.

[11]李洋，吕家恪.基于Hadoop与Storm的日志实时处理系统研究[J].西南师范大学学报：自然科学版.2017（4）：119-126.

[12]梁俊荣.基于Hadoop的图书馆复合大数据存储系统研究[Jl，现代情报，2017（2）：63-67.

[13]余辉，黄永峰，胡萍.微博舆情的Hadoop存储和管理平台设计与实王见[J].电子技术应用，2017（3）：120-123.

[14] T.K.Ho The random subspace method for constructing deci-sion forests[Jl.IEEE Transaction on PatternAnalysis and Ma-chine InteUigence，1998，20（8）：832-844.

[15]张建平，李斌，刘学军，等.基于Hadoo的异常传感数据时间序列检测[J].传感技术学报，2014，27（12）：1659-1665.

【通联编辑：王力】