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

2020-05-13 14:15郑羽罗汉云
电脑知识与技术 2020年8期
关键词:利润大数据

郑羽 罗汉云

摘要:随着计算机网络和传感器网络的迅速发展,数据呈指数级增长,特别是在因特网上。为了有效地处理大规模数据,需要具有良好的可伸缩性、灵活性和容错性的并行分布式集群。目前,许多企业基于自己的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.

【通联编辑:王力】

猜你喜欢
利润大数据
The top 5 highest paid footballers in the world
利润1万多元/亩,养到就是赚到,今年你成功养虾了吗?
观念新 利润丰