算法hosts文件在哪

I清华大学综合论文训练题目:物联网分布式计算模型研究系别:信息学院自动化系专业:自动化姓名:邹睿指导教师:董炜助理研究员2013年6月6日IIIII中文摘要随着互联网技术的不断发展,信息呈现爆炸式增长,很多应用都需要对大数据进行处理,例如智能电网是作为一个典型的物联网应用,每时每刻都有大量的数据需要处理,而智能电网中各个数据汇聚节点都有一定的计算能力,但节点间由于带宽的限制所产生的时延较大,如何利用所有的计算资源在大时延的环境下对分散的数据完成分布式计算就是我们所要解决的问题.
我们基于MapReduce模型提出了一种适用于MapReduce的改进的Min-Min算法,并在MapReduce的开源实现Hadoop中,根据其架构特点,对它的调度算法进行改进,并给出了两种性能优于Hadoop自带调度器的调度算法.
最后在Hadoop集群中对设计的调度算法进行实验验证.
关键词:时延;MapReduce;Hadoop;任务调度IVABSTRACTWiththedevelopmentofInternettechnology,theamountofinformationgrowsfast.
Manyapplicationsneedtodealwithbigdata.
Takesmartgridforexample,asatypicalapplicationofInternetofthings,alargeamountofdataneedstobeprocessedconstantly.
Eachdatacollectingnodehasitsowncomputingabilityandthenetworkdelayalsoexistsbecauseofthelimitofbandwidth.
Howtomakeuseofdistributedcomputingresourcesunderdelayconditionistheproblemthispaperaimstosolve.
AmodifiedMin-MinalgorithmadaptingtoMapReducemodelisproposed.
TwotaskschedulingalgorithmsaredevelopedtoimprovetheperformanceofHadoop.
FinallytheproposedschedulingalgorithmsareimplementedandtestedinHadoopcluster.
Keywords:timedelay;MapReduce;Hadoop;TaskschedulingV目录第1章引言.
11.
1.
研究背景.
11.
2.
研究现状.
21.
3.
本论文所做的工作.
31.
4.
论文的组织结构.
3第2章MapReduce模型介绍.
52.
1.
MapRedece的基本原理.
52.
2.
MapReduce处理任务的具体步骤.
52.
3.
MapReduce的优点.
62.
4.
Hadoop平台72.
4.
1Hadoop概述.
72.
4.
2.
Hadoop基本构架.
72.
4.
3.
Hadoop计算模型假设.
112.
4.
4.
Hadoop任务选择策略.
112.
5.
本章小结.
12第3章异构环境下基于网络时延的MapReduce任务调度模型设计及仿真实验133.
1.
数学建模.
133.
2.
基于MapReduce的调度算法设计.
143.
2.
1.
改进Min-Min算法.
153.
2.
2.
改进Min-Min算法仿真.
163.
3.
基于Hadoop的调度算法改进173.
3.
1Hadoop任务调度流程.
173.
3.
2.
增加和修改参数.
183.
3.
3.
Hadoop调度算法改进.
193.
3.
4.
设计算法的仿真实验.
203.
4.
本章小结.
22第4章验证实验.
234.
1.
实验环境介绍.
23VI4.
1.
1.
Hadoop集群安装.
234.
1.
2.
Estinet仿真软件.
234.
2.
用于实验的MapReduce作业.
244.
3.
时延对MapReduce作业总完成时间影响实验.
264.
4.
Hadoop自带任务调度器实验274.
5.
设计的任务调度算法实验.
284.
6.
本章小结.
29第5章总结和展望.
305.
1总结.
305.
2展望.
30图片索引.
32表格索引.
33参考文献.
34致谢词.
35声明.
35附录A外文资料书面翻译361第1章引言1.
1.
研究背景1999年,物联网(TheInternetofthings)的概念被提出.
它是在现有的互联网技术、网络无线射频识别系统、无线数据通信技术的基础之上,构建的一个将所有"物"连接到一起的网络,并用于进行资源和信息共享.
随着物联网技术的开发,物联网更是成为了未来能够改变人类生活的十大技术之首.
在物联网中,数据以流(stream)的形式实时、高速、源源不断地产生,因此物联网数据具有海量性;物联网往往是由大量子节点组成,并且每个子节点都收集数据,物联网数据传输复杂性成为必然;只有刚收集到的数据才能展现各子节点感触到物的状态,因此物联网的数据具有时效性.
由于物联网的数据具有以上特点,同时由于物联网各子节点会源源不断的采集新的数据,大量的数据需要及时处理,同时因物联网数据海量性不可能长期保存,所以系统的反应速度或者响应时间就是系统可靠性和实用性的关键.
智能电网作为物联网一个典型案例,大量的数据采集节点和计算节点分布在各地电网中,图1.
1为2008年南方电网图,由1393节点、2371支路、244发电机、620负荷组成,由于数据量过大和节点地理位置分布较远,时延对传输和计算的影响较大,同时,电网的决策支持系统对数据的实时性要求较高,在时延较大的情况下,如何利用大量分布式计算节点较快的完成分散的大规模数据的计算就成了一个问题,这也就是本论文研究的内容.
图1.
1南方电网2008年节点图2这是典型的分布式计算问题,有两个问题需要解决,第一个问题是如何将大量计算转换成并行计算,从而将一个任务分为很多个子任务,并在大量子节点中同时运行各个子任务;第二个问题是用何种调度算法去对资源和任务进行统一管理,使得总任务完成时间尽量的短,且各计算子节点负载尽量均衡.
1.
2.
研究现状在现有的分布式计算模型中,网格计算和云计算模型是现在运用较多的两种分布式计算模型.
云计算模型中的MapReduce将在第二章予以介绍,下面先对网格计算进行介绍:网格计算是由网络中各子节点资源组成的一个统一的虚拟整体,利用这个整体的资源对网格中所有子节点用户提供服务[1],是一种在大规模分布式资源中实现资源协调共享和解决问题的过程.
图1.
2网格计算流程图图1展示了网格计算的工作原理,网格的计算节点可以是服务器、集群,也可以是嵌入式设备以及工作站.
在GIS(GridInformationServer)中注册各计算节点,GIS中存储有各计算节点的资源信息.
每个计算节点上都有一个本地资源管理来管理本地资源,并通过通信与网格中间件中的资源管理器进行资源整合,共同调度资源,本地任务管理器则监督子任务在本地的执行情况.
用户向网格计算中间件的任务控制管理提交任务.
然后任务控制管理组件将任务交给任务调度器,通过一定的方法,任务调度器将任务划分成许多能够无关联的子任务,同时将所有子任务的信息交给资源索引,通过资源定位,各子任务都获得适合各自任务的资源信息,并通过任务管理把所有子任务移交给相应的计算3节点的任务执行器.
各子任务完成后,将任务结果传递给用户.
网格计算将所有计算资源构建成统一的整体,用户提交的任务可以方便地使用大量的资源来完成,而无需考虑所需资源的具体位置.
它的任务多来自于单一子节点,然后通过大量节点来处理,输入的数据并不是分布式,使得它有一定的自治性.
我们课题的大背景是基于电网,难免要对整体的数据进行处理,网格计算更多的考虑是单个任务如何高效的完成,而我们需要的是一个能缩短总体时间的分布式计算模型.
对于网格计算的任务调度算法,目前,已有很多科研组织对网格计算这种分布式计算模型的调度进行了研究.
下面对一些较为经典的进行简单介绍:AppleS[2]:即为ApplicationLevelScheduling,AppleS的主要目标是将资源以最有效形式对任务进行调度,它设计了一个自适应算法来进行任务调度,在这个算法中,Max-Min,Workqueue,Sufferage,Min-Min等调度策略都可使用,对不同特性的任务选择最合适的的调度算法.
Nimrod[3]:此系统为在满足任务条件的同时提供经济计算模式,该系统根据任务在各节点预测的任务执行资源使用量和任务完成时间来进行一定的资源调度.

Condom[4][5][6]为了能够充分利用网格中的空闲资源来为用户服务,它的调度过程主要分为两个部分:匹配和声明,首先通过信息收集收集所有任务和子节点的信息,然后对每个任务进行资源配置,让每个任务选择适合处理该任务的节点资源,然后通知任务管理器和适合的节点资源,两者之间进行通信确认,确认完毕后开始进行数据传输处理.
Condom的优势在于能用于高吞吐率计算.
1.
3.
本论文所做的工作本文考虑时延对任务总时间的影响,基于MapReduce的分布式计算模型,通过参考网格计算的任务调度算法,设计了一种适用于MapReduce模型的调度算法,并在MapReduce的开源实现Hadoop上,提出了三种调度算法对其Hadoop任务调度进行改进,并在hadoop集群上予以验证.
1.
4.
论文的组织结构第二章介绍了MapReduce模型和MapReduce的开源实现Hadoop,并对Hadoop的架构和调度机制进行了详细说明;第三章改进了Min-Min算法,使其适用于大4时延网络环境下的MapReduce任务调度,并通过仿真对Min-Min算法的调度性能进行分析;接着基于Hadoop,对其调度算法进行分析,基于新增加的参数设计了三种Hadoop调度算法,然后对三种算法进行仿真;第四章通过在Hadoop集群进行实验,验证了由于带宽的限制而产生的时延对MapReduce调度的影响,并修改Hadoop调度算法进行验证性实验;第五章为总结和未来展望.
5第2章MapReduce模型介绍2.
1.
MapRedece的基本原理MapReduce是由Google公司提出的一个编程模型[7],它被设计用于大规模的数据处理,在Google公司内部,每天都有成千上万的MapReduce作业被执行.
但Google只提出了这一模型,并没有对MapReduce进行开源.
Hadoop项目于2006年初开始,一直致力于MapReduce的开源实现,并且不断完善MapReduce的功能.
经过7年的发展,Hadoop已经成为了云计算领域的首选技术.
从MapReduce自身的命名特点可以看出,MapReduce将要执行的问题拆解成Map和Reduce两个阶段,用户只需编写map和reduce两个函数,即可完成简单的分布式程序设计.
MapReduce将输入按照用户需求切割成大小相同的数据片段,且各个数据片段中的数据并不相关,然后将每个数据片段作为一个Map任务的输入,将所有Map任务分配个集群中的计算节点进行分布式计算,然后将Map任务的结果聚合起来,排序后用Reduce任务对中间结果进行迭代.
2.
2.
MapReduce处理任务的具体步骤图2.
1MapReduce流程图图2.
1展示了我们的MapReduce接受作业后的全部流程.
当有作业提交时:61.
程序首先调用MapReduce库中自带的函数或者自定义的split切割函数将输入的文件按照用户定义的大小切割成很多个split,split如果用户不进行配置,默认为64MB.
2.
一个split作为一个Map任务的输入,将所有的split分别调度给所有的MapWorker,Map函数先将split分割成pair,一般key值都是该数据的首字符相对于首字符的偏移量,然后对所有pair进行Map操作,产生新的pair.
3.
对每个Map的输出进行Combin操作,即简单的合并操作,将具有相同的key值的数据合并,以减小中间数据的大小.
4.
对所有的map输出进行排序,将具有相同key值的pair聚合在一起,并一起传递给一个Reduceworker进行Reduce操作,值得注意的是,这个阶段将有很多不同的key值的数据给一个Reduce进行处理,所以先对输出进行排序就是十分必要的.
5.
Reduce任务执行完后,每个Reduce任务都有一个输出存在本地的分区文件上.
直到所有子任务完成,一个MapReduce作业才全部完成.
2.
3.
MapReduce的优点MapReduce模型能够解决的问题都有一个共同特点:作业可以被划分成多个子任务,而且每个子任务之间都相对独立不会有牵连,通过并行处理完所有子任务后,再通过迭代就能完成作业.
在实际运用中,有大量的问题都能通过MapReduce解决,google在其论文[7]中提出"贝叶斯分类,分布排序,文档聚类,K-means聚类,web连接图反转,web访问日志分析,TopK问题,反向索引构建"等都是MapReduce的典型运用.
其他相关工作[12]表明,MapReduce可以成功地用于图问题,如发现图形组件,质心聚类、枚举矩形和三角形列举.
MapReduce也进行过科学问题[13].
它在简单问题中表现良好,像组极方法产生随机变量和整数排序.
然而,MapReduce也被表示有很大问题在更复杂的算法[14],如共轭梯度,快速傅里叶变换和块三对角线性系统求解.
此外,这些问题大多是通过迭代的方法来解决,这表明MapReduce可能不适合迭代性质的算法.
MapReduce不仅能解决很多实际问题,同时它也提供了以下几点优良特性:(1)改变了传统的计算模式,移动计算是MapReduce的基本理念,MapReduce的任务调度优先考虑本地的计算节点,即master优先将子任务分配给它数据块所7在的节点位置处理,使得计算尽量本地化,移动计算要比移动数据的更加的经济.
(2)MapReduce设计了很好的容错机制,在MapReduce模型中,它认为机器出现故障或者网络中断是很正常的,所以MapReduce设计了完善了故障处理机制.
它一方面对所有的子任务以及计算节点进行监控,另外一方面优先处理失效的任务.
(3)MapReduce系统具有良好地扩展性.
在google内部的MapReduce中,每个典型的MapReduce任务都执行在成百上千台计算机上.
在MapReduce的开源实现中Hadoop中,3000多个节点的Hadoop集群已经得以实现[11],在这个集群上运行了80000多个Map任务和20000个Reduce任务.
2.
4.
Hadoop平台Google共享了MapReduce的技术要点,但是并没有进行开源.
Hadoop作为MapReduce的开源实现,可以通过搭建Hadoop集群来运行MapReduce作业.
2.
4.
1Hadoop概述2006年年初,Hadoop作为Lucene的子项目Nutch中的一部分被ApacheSoftwareFoundation基金会引进,它受到了google两篇论文的启发(一篇是2003年发表的关于google分布式系统(GFS)的论文,另一篇是2004年发表的关于google分布式计算框架MapReduce的论文),于2006年2月,ApacheHadoop项目正式启动,支持MapReduce和HDFS的独立发展.
经过七年的发展,hadoop在所有开源云计算系统中稳居第一.
很多高校和企业都在大规模使用hadoop.
[10]2.
4.
2.
Hadoop基本构架Hadoop由两部分组成,它们分别是分布式文件管理系统HDFS和分布式计算框架MapReduce.
HDFS主要用于大规模数据的分布式存储,而MapReduce则对存储在HDFS中的大规模数据进行分布式计算.
HDFS构架:HDFS作为一个高容错的分布式文件系统,能提供高吞吐量的数据访问,适应于大规模数据的存储.
8图2.
2HDFS架构图HDFS的构架如图2.
2所示,它继承了MapReduce的master/slave架构,HDFS中的NameNode对应于master,DateNode对应于slave.
Client代表用户,SecondaryNameNode作为NameNode的一个辅助节点.
整个Hadoop集群只有一个NameNode,它负责管理HDFS的目录树,含有所有存储任务的存储地址.
此外,NameNode还需监控各个子节点DataNode的健康状况,如果发现DataNode没有响应,则需重新备份存储在DataNode上面的数据.
DataNode是Hadoop上的计算节点以及数据存储节点,它以固定大小的block存储文件,定期将数据信息汇报给NameNode.
当用户提交一个大文件到HDFS上时,该文件会被切割成若干个block,按照一定的规则,分别存储到不同的DataNode上.
HadoopMapReduce构架:HadoopMapReduce也采用了Master/Slave构架,其构架图如图2.
3.
它由Client,TaskTracker,JobTracker、Task组成.
下面对这几个组件进行介绍:9图2.
3HadoopMapReduce架构图在HadoopMapReduce架构中,Client将用户编写的MapReduce程序提交给JobTracker.
在Hadoop中,作业(Job)表示MapReduce程序.
每个作业被分为若干个Map/Reduce任务(Task).
JobTracker在NameNode节点上,主要用于负责资源监控并通过调用TaskScheduler对作业和任务进行调度.
所有TaskTracker的健康状况和作业的完成情况都被JobTracker所监控.
一旦发现有任务失败或者TaskTracker出现故障后,JobTracker会将其转移到其他节点上重新执行任务;同时,JobTracker会跟踪所有任务的执行进度以及各DataNode资源使用量,并将这些信息告诉TaskScheduler,当节点资源出现空闲时,TaskScheduler会选择合适的任务使用这些资源.
TaskTracker部署在DataNode上,它会主动的通过周期性的heartbeat(心跳机制)将本节点上所有slot的使用情况和任务的完成进度汇报给JobTracker,同时接受JobTracker的心跳应答,该应答由两部分构成,一部分为给TaskTracker的命令,另外一部分为下次汇报心跳的时间间隔.
在DataNode上,资源被TaskTracker等量划分为若干个slot.
一个slot可以执行一个任务,当slot无任务时,TaskTracker在heartbeat中向JobTracker反馈信息,Hadoop调度器的就会给空闲的slot分配Task.
Task即为MapTask和ReduceTask,这两种任务均由TaskTracker启动.
Map10Task的输入数据大小为split,与HDFS的存储大小可以不同,可由用户定义.
Split与block的关系如图2.
4.
split个数即为Map的个数,所以split不能太大也不能太小,太大容易影响任务完成时间,太小容易使得JobTracker的任务量过大,数据读写次数过多.
MapTask和ReduceTask执行流程分别如图2.
5、图2.
6.
图2.
4split和block的关系图2.
5MapTask执行流程图2.
6ReduceTask执行流程112.
4.
3.
Hadoop计算模型假设Hadoop项目主要目的是在实现MapReduce以及其分布式存储文件系统HDFS,所以在设计之初,隐含了一些假设,这些假设都是根据负载均衡和同构集群建立的,而这些假设也影响了Hadoop推测执行设计算法.
假设主要有以下四点:1.
每个节点具有相同的计算能力2.
任务进度随时间线性增加3.
对失败的任务重新启动的代价忽略不计4.
同一作业所有Map任务计算量相同,所有Reduce任务计算量相同2.
4.
4.
Hadoop任务选择策略在Hadoop中,任务调度是一个可以拔除的模块,用户可以根据自己的MapReduce函数特点和Hadoop集群特点设计调度器.
目前的Hadoop版本自带了三种作业调度器:即FIFO、CapacityScheduler和FairScheduler.
这三种调度器是不同的作业调度器,但是他们调用了相同的任务调度函数,并把任务调度函数存放在JobInProgress类中的obtainNewMapTask和obtainNewReduceTask函数中.
Hadoop的任务调度将数据本地性当成最重要的考虑因素,尽量把最多的任务在本地进行计算,从而减少任务数据传输过程的网络传输开销.
对于目前的Hadoop而言,任务调度策略都采用了两层网络拓扑结构,如图2.
7所示,所有的任务对每个datanode而言都划分为三种:rack-local(同机架)任务,node-local(同节点)任务以及off-swith(跨机架)任务.
如果H1是计算节点,任务Y的数据在H1上,则Y是node-local任务.
如果H1是计算节点,任务Y的数据在H2上,则Y是rack-local任务.
如果H1是计算节点,任务Y的数据在H3上,则Y是off-swich任务.
12图2.
7Hadoop任务调度两层拓扑结构当某个DataNode空闲时,调度器会调用任务调度器,任务调度器会优先调度运行失败的任务,如果这种任务列表为空,则优先将node-local任务即数据在本地的任务分配给该DataNode,如果本地任务为空,则选择rack-local任务,若同机架任务也为空,则选择off-swith任务,当不在本地的任务也为空时,则检测是否有正在执行拖后腿的任务,并为该任务启动一个备份任务.
当有任一节点将该拖后腿的任务执行完后,终止所有该任务的备份任务.
2.
5.
本章小结本章介绍了MapReduce的基本原理和执行MapReduce作业的基本步骤,MapReduce能很好的将一个能够进行并行的任务分解的作业分解成很多个子任务,以此为基础对作业进行分布式任务调度,使单个作业可以利用集群中所有空闲资源进行处理,从而快速的完成作业,为大规模数据处理提供了可行的方法.
本章还介绍了MapReduce的开源实现,通过介绍Hadoop的基本构架,分析了Hadoop自带的信息传输机制以及本身的任务调度器,为第三章利用Hadoop集群运行MapReduce作业和对传递的节点信息修改和调度算法可行性验证和改进提供基础.

13第3章异构环境下基于网络时延的MapReduce任务调度模型设计及仿真实验第二章中介绍了MapReduce的基本思想,同时MapReduce具有良好将串行计算转换为并行计算能力,MapReduce更多的研究在于如何将各种算法运用在MapReduce模型中,并研究他们的效率和伸缩度.
但是MapReduce设计中对任务调度并没有过多的设计,主要是针对大量的作业调度进行了优化,防止出现由于某个作业占据大量的资源使得某些作业得不到应得资源的情况.
这章将对在较大时延下的单个MapReduce作业进行任务调度研究.
3.
1.
数学建模已知条件:计算节点间时延、计算节点处理速度、任务规模目标:任务求解总体时间最短数学建模如下:1.
表示所有的计算节点2.
矩阵表示各计算节点间的网络时延(s)3.
表示所有的计算节点的计算能力(已每秒处理的数据数表示)(MB/s)4.
表示任务数据在所有节点上分布的情况(MB)5.
表示分配后的数据量在各个计算节点上的分布情况6.
b表示经过处理后的数据规模7.
表示各个计算节点上存储的中间节点规模情况8.
R表示分配后的数据量在各个计算节点上的分布情况9.
假设每个计算节点上都只部署单一slot,即每个计算节点上不能并行处理多个任务10.
假设需要调用的Mapworker数为m,Reduceworker数为r11.
选取节点i为Map节点则记,否则1412.
选取节点i为Reduce节点则记,否则13.
不考虑调度算法的运行时间则依据以上条件,可将问题建模如下:3.
2.
基于MapReduce的调度算法设计在实际网络情况下,节点间延迟和各节点的负载情况随时间变化,网络情况下的任务调度问题已被证明是NP完全问题,很难通过调度获得最优解,因此大多数任务调度算法都被设计为启发式算法为主,很多这类算法都能近似与最优解.

静态调度算法在任务调度前就决策完成,静态任务调度算法的开销较低,而且静态调度算法有足够的时间利用所有信息,更能趋进于最优解,能够产生有效地调度策略,但在网络的情况下,很多参数现在都无法定量去预测,只能根据实测值去收集参数.
所以并不具备较强的可用性.
较为典型的静态调度算法有遗传算法,蚁群算法和模拟退火算法.
动态任务调度算法分为两类,一类是在线模式启发式算法[8],一类是批模式启发式算法[8].
在线模式启发式算法可以对所有已知的空闲slot会立刻做出决策,15分发任务,具有较强的实时性,但在线启发式算法多是根据某一特定的规则指派任务,只考虑到单一节点的信息,而没有考虑到其他节点的信息,最后的调度性能会受到很大的影响.
批模式启发式处理算法则是将任务信息收集到一个队列中,将一定时间内的任务进行统一处理再调度.
所以批模式启发式处理算法具有一定的实时性同时也具备静态算法的高效性[15].
较为典型的在线模式启发式算法有MCT(最小完成时间算法),MET(最小执行时间算法),OLB(OpportunisticLoadBalancing)等.
较为典型的批模式启发式算法有快速贪心(FastGreedy)算法,Min-Min算法、Max-Min算法,Sufferage(损失度)算法等.
针对MapReduce中每个Map任务具有相同的输入数据大小的情况,所有Map任务所需的计算量都一样,任务完成时间差异具体在数据传输上,所以本地的任务必然在任务完成时间上更小,所以计算本地化能够大幅度的减少总的作业完成时间,同时计算优先本地化也能使得大规模数据网络传输中带宽的限制不再是问题.
Min-Min算法即为根据任务完成时间来选择任务的一种算法,TracyD等人的论文结果表明[10],单一考虑作业完成时间而不考虑负载等问题情况下,Min-Min能得到优于其他算法的调度性能.
但是Min-Min在任务大小不一样的情况下,Min-Min算法容易造成大量小任务优先在计算能力强的节点上执行,使得计算本地化较低,容易造成大量的数据传输,对于时延较大的系统,这点往往让人很难以接受.
但是Min-Min算法对于具有相同计算量的数据任务,有着较好的本地化能力,下一小节将针对MapReduce特点及各节点时延较大的特点改进Min-Min算法,以适用于课题.
3.
2.
1.
改进Min-Min算法Min-Min算法根据命名含义可知,即为找最小值中的最小值,该算法先预测每个任务在所有计算节点上的最小完成时间,这个时间包括:任务计算时间,传输时间和存储时间等.
然后再计算所有任务的最小完成时间中的最小值,将这个具有Min-Min值的任务从任务列表中删除,并分配给对应的计算节点.
记第i个子节点任务在第j台主机上的预测最小完成时间MCT(i,j),若存在m个数据存储节点和n个计算节点,则MCT矩阵是一个m*n的矩阵.
MCT主要由以下几个参数决定:1.
数据节点i上的任务数量n(i);162.
数据节点i上的任务在主机j上的预测执行时间ETC(i,j);3.
计算节点j的最早可用时间TaskStart(j)(即上个任务完成时间);4.
通过网络把任务节点i上一个任务所需的数据传输到计算节点j上的传输时间Trans(i,j);MCT(i,j)的计算公式为:MCT(i,j)=ETC(i,j)+TaskStart(j)+Trans(i,j).
该算法具体调度步骤:1.
当任务列表非空时,重复执行如下操作直至任务列表为空;2.
对于任务列表中所有待处理的任务,根据以上公式计算出所有任务到所有节点的任务完成时间,同时对所有任务找出它最小的预测完成时间,并将预测完成时间和计算节点记录下来,将最小预测完成时间存入数组MT中;3.
查找出MT数组中最小MCT的任务分配给产生这个最小MCT的计算节点;4.
从需要调度的任务列表中删除这个最小MCT的任务,并更新MCT矩阵.
并重复以上操作.
3.
2.
2.
改进Min-Min算法仿真利用Matlab进行如下两个仿真:(1)Min-Min算法对所有任务计算量相同作业的计算本地化仿真生成100个节点,每个节点随机生成2~14MB/s的数据处理速度,两两节点间的一个任务数据的传输时间Trans为均值1S方差为2的正态分布绝对值随机数,每个节点随机生成4~100的任务数n(i).
在MapReduce中每个任务数据默认大小为64MB.
为了将计算本地化程度是否由于任务的计算量相同而大量改进,将每个节点上任务生成[n(i)/2]个2~126之间的数值,再用128减去每个数值,得到另外一半任务大小,获得一个大小不相等,各节点总任务数据和原来大小一样的一个任务集.
将两个任务数据大小相同,分布状态相同,但任务划分不同的作业根据Min-Min算法进行调度仿真.
通过十次仿真结果,实验平均值结果如表3.
1.
表3.
1Min-Min算法本地化实验结果总任务数本地任务数本地任务比作业总时间(s)相同的任务大小542140780.
7535497不同的任务大小54212730.
0504578仿真实验可知,Min-Min算法十分适用于任务输入数据大小相同的调度策略中,17具有较好的计算本地化能力.
(2)改进的Min-Min算法与快速贪心算法的作业总时间仿真生成100个节点,每个节点随机生成2~14MB/s的数据处理速度,两两节点间的一个任务数据的传输时间Trans为均值1S方差为2的正态分布绝对值随机数,每个节点随机生成4~100的任务数n(i),每个任务的数据大小默认为64MB快速贪心算法具体步骤:对所有Map任务进行随机排序,按照任务顺序进行选择,预测当前任务在所有节点执行完这个任务的时间,选出其中的最小值节点,将任务进行分配.
然后刷新所有节点的可以接受任务的最早时间,重新对下一个任务进行选择,直至所有Map任务都被调度出去.
通过十次仿真结果,实验平均值如表3.
2表3.
2改进Min-Min算法仿真结果总任务数本地任务数本地任务比作业总时间改进的Min-Min算法510738200.
748479快速贪心算法51072980.
058608仿真实验表明,在时延较大的MapReduce模型中,改进的Min-Min算法较之快速贪心算法有着较好的效率.
3.
3.
基于Hadoop的调度算法改进在Hadoop集群的信息管理中,任务调度机制是由计算节点向主节点申请任务,3.
2节中的Min-Min算法等批模式启发式算法无法在Hadoop中运用.
Hadoop的任务调度并没有考虑节点间时延情况,调度器调度主要依赖各节点数据信息和各节点的任务信息进行简单的调度.
由于Hadoop源代码中已经实现将运行作业的架构完整实现,要修改Hadoop任务调度算法,只能是基于Hadoop框架进行改进.
3.
3.
1Hadoop任务调度流程Hadoop任务调度流程如图5.
1所示,在Hadoop架构中,JobTracker不会主动向TaskTracker分配任务,而是由TaskTracker每隔3s向JobTracker发送一次心跳(Heartbeat),Heartbeat中包含了当前节点的运行信息,JobTracker再给应答心跳18中给出任务.
图3.
1Hadoop任务调度流程图每个Heartbeat中的TaskTrackerStatus包含有以下信息:StringtrackerName;//TaskTracker名称Stringhost;//TaskTracker的主机名inthttpPort;//对外的HTTP端口号ListtaskReports;//当前TaskTracker上所有任务的运行状态privateTaskTrackerHealthStatushealthStatus;//TaskTracker健康状态privateResourceStatusreaStatus;//TaskTracker的内存,CPU情况taskReport存储了任务信息,其中包括每个任务的完成情况,开始时间和完成时间.
resStatus中保存了TaskTracker资源情况.
3.
3.
2.
增加和修改参数为了提高任务调度效率,增加以下两个参数:两两节点时延参数和各计算节点完成一个Map任务所需的时间参数.
由于在小规模集群下实验,通过参数配置TaskTracker的心跳时间间隔,将其调成300ms.
各节点完成一个Map任务所需时间可以由TaskReport中的任务开始时间和完成时间相减得到,这两个参数都存在taskReport中,CountTime=finishTime-startTime.
同时为了保证数据的实时性,需要先找到该TaskTracker上完成时间最晚的一个本地任务,计算它的任务完成时间,作为该TaskTracker上的计算能力,用于调度.
将时延参数加入HeartBeat的方法:在Java中exec("ping"+ip)即可获得每个节点到所有节点中的时延,并把它按照顺序存入一个文本中.
当MapReduce运行时,同时在所有子节点上运行这个Java程序,并以3S为时间间隔反复调用以上函数.
当TaskTracker要发送HeartBeat时,初始化HeartBeat时读入文本中时延,并19把它存在一个TimeDelay数组中(各节点到本节点的时延为0).
JobInProgress类主要用于监控作业运行状态,并为调度器提供底层的调度接口.
在JobInProgress中加入二位数组TimeDelay存储延时,再加入所有子节点的计算能力Count数组.
当JobTracker通过心跳机制接收到HeartBeat时,将参数写入到JobInProgress中.
3.
3.
3.
Hadoop调度算法改进Hadoop采用的是当计算节点空闲后向主节点申请任务的机制,该机制更适合在线启发式算法的调度,而不适用Min-Min算法等批模式启发式算法调度.
通过上一节增加的时延参数和各节点计算能力参数,重新编写Hadoop的Map任务调度函数.
Hadoop的调度函数在JobInProgress类的obtainNewMapTask中.
在Hadoop中,任务本地化既可以缩短任务时间又可以减少网络传输开销,所以计算本地化依然是算法的核心思想.
对于基于Hadoop构架MapReduce调度算法,根据上一节添加的两个参数分别给出了两种算法:第一种是较为常见的快速贪心算法,它根据各个任务到当前需要任务分配的计算节点的延时大小,选择延时最小的任务进行执行.
该算法具有较好的作业完成速度,但是快速贪心算法容易造成大量计算的非本地化,使得网络开销较大.

第二种算法为:当有计算节点需要任务分配时,优先考虑本地数据任务,当本地数据任务处理完后,通过各节点计算能力和剩余任务量,优先考虑各节点完成剩余任务所需时间最多的节点任务进行分配.
该算法没有用到时延条件,而是以尽可能的计算本地化为标准,所以该算法的计算本地化较好,但与此同时,任务执行时间与Hadoop原算法不会有太大的改进.
前两种算法都存在一定的缺陷,基于两种算法不足,本文提出第三种算法进行改进.
算法三步骤如下:(1)当有计算节点需要任务分配时,先遍历本地任务列表,如果不为空,则选取一个任务执行,任务分配结束(2)当本地任务为空时,将其他所有剩余任务数不为0的节点(假设有n个),按照各节点剩余任务所需处理时间进行排序,选择剩余任务所需时间最长的Z(Z等于n乘以m向上取整)个节点(m为一个百分比,可设置).
(3)选取这Z个节点到计算节点最小的延时节点,若该延时小于给定值t,则选择这个最小的延时节点上的任务.
反之,则遍历n个节点到计算节点的延时,选20择其中的最小延时节点任务分配给该计算节点.
(4)当所有节点剩余未执行的任务数为0时,遍历所有正在执行的任务,找出其中预计时间最慢的任务,并与当前节点执行该任务预计结束时间进行比较,若能更快执行完该任务,且该任务备份数小于3,则在这个节点启动该任务的一个备份,当任意节点完成该任务时,停止其他节点上该任务.
图3.
2算法三流程图根据网络情况调整t参数,m可由实验调整,m越大本地性越小,数据越快.
3.
3.
4.
设计算法的仿真实验先对三种算法进行Matlab仿真实验:现生成100个节点,每个节点随机生成2~14MB/s的数据处理速度,两两节点间的一个任务数据的传输时间Trans为均值1S,方差为2的正态分布绝对值随机数,Trans矩阵并每3s更新一次,每个节点随机生成4~100的任务数n(i),每个21任务的数据大小默认为64MB.
对相同参数和相同网络时延变化,对三种算法进行仿真,算法三取中t=0.
5S,m取30%.
结果如下表5.
1所示.
表3.
3三种算法仿真结果总任务数本地任务数本地任务比作业总时间(s)快速贪心算法539032460.
602513算法二539040960.
760628算法三539039310.
731547由仿真实验结果可知,快速贪心算法具有较快的作业完成速度,但是任务本地性较差欠佳,不过由于贪心算法也会优先考虑本地任务,所以本地任务比仍保持较高的水平;算法二本地任务比较高,但是无法掩盖其作业完成速度较差的缺陷;算法三的本地任务率较之算法二也相差不大,但是作业总时间有了显著的提高.
通过这个仿真实验可知,贪心算法和算法三都对MapReduce有较好的调度效果.
接下来,将通过实验对比选取合适的m值,从而达到更好的调度效果.
分别选取m=0%,10%,20%,30%,40%,50%,60%,80%,100%.
t=10000S对实验进行仿真,仿真结果如表5.
2所示.
表3.
4算法三参数选取实验结果m值(%)总任务数本地任务数本地任务比作业总时间(s)1488337060.
75959510488336820.
75454520488336530.
74852830488336180.
74151740488335110.
71951150488333730.
69150260488331430.
64450380488330050.
615500100488329880.
612498当m=1%时,该算法即为算法二,当m=100%时,该算法即为贪心算法.
由实验可知当m取20%~30%时,算法对本地任务比和作业总时间都有良好的效果.
223.
4.
本章小结本章通过对MapReduce进行建模,通过对各种任务调度算法进行分析,选择了较为适合的Min-Min算法,并对其进行改进以适应MapReduce架构.
通过实验得出Min-Min算法的计算本地性和效率都十分理想.
本章基于Hadoop的基础上,对Hadoop的调度参数进行增加和修改,并基于增加的参数对Hadoop任务调度提出三种算法,快速贪心算法和算法三通过实验都获得了较为优良的性能,下一章将进行硬件实验验证算法.
23第4章验证实验4.
1.
实验环境介绍本次实验环境由实验室搭建的Hadoop集群和Estinet网络仿真环境共同组成.
4.
1.
1.
Hadoop集群安装硬件环境:虚拟机操作系统:LinuxHadoop集群中Hadoop代码版本号:Hadoop-1.
0.
1Hadoop集群由5台分布在不同服务器上的虚拟机(一个namenode节点,四个datanode节点)构成,每台虚拟机的CPU和内存参数将在具体实验中设置.
Hadoop集群安装步骤如下:1.
在各节点中建立统一用户名:hadoop2.
将Hadoop-1.
0.
1代码解压缩到各个节点中.
3.
修改所有配置文件,将各主节点和计算节点进行申明,并创建HDFS存储输出和任务执行目录.
4.
修改所有节点中的Hosts文件中所有节点对应的IP地址,使得各节点能正常通信.
5.
修改SSH,使得Hadoop集群运作中无需密码即可访问各节点.
6.
在namenode中start-all.
sh启动所有datanode节点和TaskTracker,利用hadoopdfsadmin–report命令检查各datanode节点存储数据情况,检验是否成功安装.
4.
1.
2.
Estinet仿真软件Estinet7.
0是一款由台湾思锐科技有限公司开发的通信网络仿真软件,它可以在实际的主机中运行应用程序并在仿真的网络环境上的虚拟主机和路由器上运行,它可以产生与实际网络中相近的流量模型.
Estinet软件部署在另外一台主机的一个虚拟机上,由于必须所有节点都能够改变链路情况,所以将Estinet软件所在的虚拟机部署在所有节点传输数据的必经之路上.
将五个Hadoop虚拟机通过修改IP设置成五个不同局域网,将Estinet部署的虚拟机多配置几个网卡,设置成这五个虚拟机的子网网关,并通过修改路由表,将五个Hadoop虚拟机节点间通信都经过Estinet部署的虚拟机,Estinet仿真图如24图6.
1.
然后通过Estinet可以修改任意两个节点之间的传播时延和带宽,如图6.
2所示.
图4.
1Estinet仿真图图4.
2Estinet修改网络参数图4.
2.
用于实验的MapReduce作业本次用于实验的MapReduce作业采用最能体现MapReduce思想的词频统计作业,输入文件大小为492MB,Splits大小为1M.
将文件按Splits大小分割成各个splits,并将每个splits按行分割成pair,key值是存储该行首字符的偏移量,value存储文本一行的数据.
通过Map操作,生成一大串的,Map部分实现代码如图4.
3.
25图4.
3词频统计Map部分并通过Map端排序和combine过程,对一个Map任务相同的key值进行合并,再将所有Combine输出结果排序后根据Reduce个数将结果分为若干个分片,每个Reduce读取自己所处理Key值范围读取相应的分片,并合并相同的key值,输出最后结果.
Reduce部分代码如图4.
4.
图4.
4词频统计Reduce部分26图4.
5词频统计程序运行过程4.
3.
时延对MapReduce作业总完成时间影响实验实验中参数如表6-1,由于Hadoop对作业提交的数据利用HDFS进行负载均衡,较为平均的存储在各个datanode中.
所有只有通过修改CPU和内存参数来修改节点的计算能力.
表4.
1各节点CPU、内存和存储数据表NameNodeDataNode-1DataNode-2DataNode-3DataNode-4CPU内核总数12311内存(GB)12311数据(MB)0110108126129由于延时较大时,namenode会认为datanode丢失,所以将任务大小改为1MB,以便将任务计算时间和网络时延形成很好的比较.
分别用estinet对两两节点间添加时延和带宽参数,给各链路设计一个ms级别的传播时延,该时延对实验结果几乎没有影响,然后分别给各节点间设计相同的带宽,分别为10MB/s,1MB/s,0.
1MB/s.
由于网络中传输的数据只有该MapReduce27作业,所以实验结果无需通过多次实验取平均值来获得.
实验结果如表6-2所示.
表4.
2Hadoop在不同带宽环境下的调度结果带宽(MB/S)非本地任务本地任务总时间(ms)10MB813916291201MB674056789720.
1MB32440961810由实验结果可知,每个任务的平均完成时间约为4800ms,当带宽较大导致时延较之每个任务的平均完成时间过小时,时延变化对总作业完成时间并没有太大的影响,当带宽减小,时延增大到和每个任务的平均完成时间较为相近时,任务完成时间开始急剧增大,同时由于在非本地任务时间大幅提高后,本地任务增多.
4.
4.
Hadoop自带任务调度器实验当各虚拟机CPU和内存如表6.
3所示时,在1000ms量级的时延下,实验结果如图6.
4所示:表4.
3不同节点性能的实验结果非本地任务本地任务总时间(ms)1000ms414311161810为了改变计算节点性能,修改各虚拟机CPU和内存参数如表6.
3.
表4.
4各节点CPU、内存、数据存储信息NameNodeDataNode-1DataNode-2DataNode-3DataNode-4CPU内核总数11111内存(GB)11111数据(MB)0110108126129在大时延下,即1000ms量级的时延下,实验结果如下:表4.
5不同节点性能的实验结果非本地任务本地任务总时间(ms)1000ms2344986998028两个实验结果比较可知,由于有节点计算能力突出,导致本地化程度下降,很多任务配给了计算能力较强的节点进行运算,然而,这反而导致总时间大幅增加.
然而明显第一个实验中集群的计算能力较强,却产生了截然相反的结果,可以得出结论:Hadoop自带的任务调度器在时延较大的情况下调度的效果不佳.
4.
5.
设计的任务调度算法实验第三章中已经为Hadoop调度器提出了三种改进算法,其中快速贪心算法和算法三通过仿真都得到了较好的性能,但是由于集群中Hadoop的DataNode节点数量有限,算法三的很难适应于这种小规模集群.
本小节仅在Hadoop集群上对快速贪心算法进行实验.
将快速贪心算法写入obtainNewMapTask函数中,同时对原来调度函数中,对任务全部都在调度后进行备份调度的部分保留(防止有拖后腿的任务),通过修改配置文件将split大小设置为1MB.
实验中各节点参数如表6.
2所示.
将Estinet仿真中每条链路进行带宽设计,对原调度器进行三次实验,为了保证各节点间带宽不相同,对每个节点间的带宽进行设计,带宽的量级分别为10MB/S(节点到网关间带宽在50~2MB/s之间),1MB/S(节点到网关带宽在5~0.
2之间),0.
1MB/S(节点到网关带宽分别在0.
5~0.
02之间),在相同带宽环境下,对现在所用的调度器进行如上三次实验,实验结果如表6.
5.
表4.
6快速贪心算法实验结果调度算法带宽(MB/s)非本地任务本地任务总时间(ms)自带调度器1090382622776自带调度器173399670986自带调度器0.
135437971293新调度器1093379624168新调度器180392668812新调度器0.
145427925380通过以上实验结果,当带宽较大,各节点数据传输延时较小时,快速贪心算法的作业完成总时间和Hadoop自带调度器的作业完成总时间并没有多大差别.
当带宽较小导致时延较大时,传输数据时间相对于计算时间大幅增加,快速贪心算法比之Hadoop自带的调度算法有着更快的任务完成时间和效率.
但是由数据可知,29数据传输时间仅仅减少了10%,可能的原因是由于Estinet构建的仿真图中,由于节点太少,节点间链接也过于简单,两两节点的带宽由于结构原因导致相同,同时节点过少导致了链路结构不够复杂.
4.
6.
本章小结本章在Hadoop集群中运行MapReduce作业,通过estinet给集群中两两节点加上时延,在时延较大的网络环境下,实验表明,Hadoop任务调度器调度性能欠佳.
将快速贪心算法加入Hadoop任务调度器中,计算本地化并没有下降,在时延较小时,新的调度算法并没有显示出较好的性能,当时延较大时,新的调度算法有很好的调度效果.
30第5章总结和展望5.
1总结随着互联网技术的不断发展,信息呈现爆炸式增长,很多应用都需要对大数据进行处理,这迫切的需要更加强大的计算能力,然而,在摩尔定律渐渐失效的今天,单一计算机的硬件发展开始减缓,单一计算机很难满足这种应用对计算能力的需求,利用集群来处理大规模数据的分布式计算模型就成为解决这种需求的唯一方法.
本文基于MapReduce模型上提出了一种改进的Min-Min算法,由仿真实验可知,这种算法很好的适用于Map任务计算量一样的MapReduce模型中.
接着在MapReduce的开源实现Hadoop中,对Hadoop的任务调度器算法进行研究并改进,并基于Hadoop机制,在Hadoop中添加了时延参数和节点计算能力参数,并给出了在Hadoop集群的参数获得方法,同时根据添加的参数提出了两种典型的调度算法,一种是根据时延的快速贪心算法,一种是根据节点计算能力的自适应调度算法,第一种算法有较高的效率,但是计算本地化程度不高,第二种算法计算本地化程度较高,但调度效率较差.
根据这两种算法的优缺点,对两种算法进行改进,并提出了算法三,该算法在调度效率和计算本地化上都有很好的效果.
并通过实验对仿真中环境选择出较好的算法参数值.
为了验证大时延对MapReduce的影响和Hadoop本身调度算法不足以及新算法,我们使用了Hadoop集群和estinet软件仿真相结合的实验环境,用Hadoop集群执行MapReduce作业,用estinet仿真软件对节点间带宽进行限制,从而增大网络时延.
通过大时延环境下的MapReduce实验,对比Hadoop原来的任务调度器,采用快速贪心算法的任务调度器有着较好的调度效率.
由于Estinet的修改时延本身有着较大的缺陷,无法模拟真正的大时延网络环境,同时Hadoop集群自带的HDFS存储机制使得实验中很难模拟任务数据的复杂分布式存储,而是根据负载进行一定策略的固定分配,也导致计算本地性在Hadoop集群中的效果要好于实际的MapReduce作业,以上都对实验结果有着较大影响.
5.
2展望任务调度算法所解决的问题是一个NP完全问题,Hadoop的开发者更关注于31当集群有多个MapReduce作业时如何保证各个作业间的合理调度,对MapReduce任务调度机制没有过多的设计.
本文虽然对Hadoop的调度算法进行了优化设计,但由于Hadoop本身的机制所限,调度算法都是在线启发式算法.
下一步工作是通过对Hadoop的任务调度机制进行修改,将Min-Min算法等批模式启发式算法加入到Hadoop调度器中,从而更好地优化调度性能.
32图片索引图1.
1南方电网2008年节点图1图1.
2网格计算流程图2图2.
1MapReduce流程图5图2.
2HDFS架构图8图2.
3HadoopMapReduce架构图9图2.
4split和block的关系10图2.
5MapTask执行流程10图2.
6ReduceTask执行流程10图2.
7Hadoop任务调度两层拓扑结构12图3.
1Hadoop任务调度流程图18图3.
2算法三流程图20图4.
1Estinet仿真图24图4.
2Estinet修改网络参数图24图4.
3词频统计Map部分25图4.
4词频统计Reduce部分25图4.
5词频统计程序运行过程2633表格索引表3.
1Min-Min算法本地化实验结果16表3.
2改进Min-Min算法仿真结果17表3.
3三种算法仿真结果21表3.
5算法三参数选取实验结果21表4.
1各节点CPU、内存和存储数据表26表4.
2Hadoop在不同带宽环境下的调度结果27表4.
3不同节点性能的实验结果27表4.
4各节点CPU、内存、数据存储信息27表4.
5不同节点性能的实验结果27表4.
6快速贪心算法实验结果2834参考文献[1]董征宇.
网格计算中任务调度算法研究[D].
重庆大学,2009.
[2]BermanF,WolskiR.
TheAppLeSproject:Astatusreport[C]//Proceedingsofthe8thNECResearchSymposium.
1997,16.
[3]沈华,魏斐翡.
"网格资源计费模型的研究.
"湖北工业大学学报21.
4(2006).
[4]BasneyJ,LivnyM,TannenbaumT.
Deployingahighthroughputcomputingcluster[J].
Highperformanceclustercomputing,1999,1(5):356-361.
[5]LitzkowMJ,LivnyM,MutkaMW.
Condor-ahunterofidleworkstations[C]//DistributedComputingSystems,1988.
,8thInternationalConferenceon.
IEEE,1988:104-111.
[6]TheGrid2:Blueprintforanewcomputinginfrastructure[M].
MorganKaufmann,2003.
[7]DeanJ,GhemawatS.
MapReduce:simplifieddataprocessingonlargeclusters[J].
CommunicationsoftheACM,2008,51(1):107-113.
[8]罗红,慕德俊,邓志群等.
网格计算中作业调度研究综述[J].
计算机应用研究,2005,,2(5):16-19[9]牛川川.
计算网格中任务调度算法和策略的研究[D][D].
南京:南京理工大学,2007.
[10]刘鹏.
实战Hadoop:开启通向云计算的捷径[M].
电子工业出版社,2011.
[11]吴宝贵,丁振国.
基于Map/Reduce的分布式搜索引擎研究[J].
现代图书情报技术,2007(8):52-55.
[12]Cohen,Jonathan.
"GraphtwiddlinginaMapReduceworld.
"ComputinginScience&Engineering11.
4(2009):29-41.
[13]Bunch,Chris,BrianDrawert,andMatthewNorman.
"Mapscale:acloudenvironmentforscientificcomputing.
"UniversityofCalifornia,ComputerScienceDepartment,Tech.
Rep(2009).
[14]Srirama,SatishNarayana,PelleJakovits,andEeroVainikko.
"AdaptingscientificcomputingproblemstocloudsusingMapReduce.
"FutureGenerationComputerSystems28.
1(2012):184-192.
[15]樊莎.
网格计算启发式任务调度算法的研究及在GridSim中的仿真.
MSthesis.
西北大学,2010.
[16]WhiteT.
Hadoop:Thedefinitiveguide[M].
O'ReillyMedia,Inc.
,2012.
35致谢词本论文是在我的导师董炜老师的耐心指导下完成的,董炜老师为此花费了大量的宝贵时间和精力并给予我很多指导,在此向导师表示衷心的感谢!
导师高度的责任心和严谨的治学态度让我受益终生.
此外,曹军威老师常常对我的毕设进行指导,给予了我很大的帮助.
万宇鑫博士给我的毕设提出了很多可行性建议,并指出我实验中的误区,让我能及时发现问题并顺利完成毕业设计.
还要感谢实验室的师兄师姐以及一同做毕业设计的几位同学共同营造了这个良好的毕设环境,是你们在我平时设计中和我一起探讨问题,给予了我很多启发.
没有以上老师和同学的帮助我不可能这样顺利地完成毕设,在此表示深深的谢意.
3637附录A外文资料书面翻译适用于科学云计算问题的MapReduce框架摘要:云计算,它承诺几乎无限的资源,似乎相当适合解决需要大量资源的科学计算问题.
为了研究这项内容,我们在我们内部的集群上建立了科学云计算(SciCloud)项目和环境.
项目的主要目标是研究在大学范围内建立私有云.
通过这些云,学生和研究人员能够有效地使用大学计算机网络的现有资源去解决计算密集型科学,数学和学术问题.
然而,要能够在云基础设施运行科学计算应用程序,应用程序必须降低到可以成功的利用云资源的框架,像MapReduce框架.
本文总结了在MapReduce模型中关于换算迭代算法相关的挑战.
科学计算的算法通过依赖MapReduce模型分为不同的类;在MapReduce模型上对每一个类性能进行测量和分析.
这项研究主要侧重于研究HadoopMapReduce框架并把它和一个替代MapReduce框架——Twister相比,Twister是专们为迭代算法设计的.
分析表明,HadoopMapReduce在迭代问题方面具有显著的麻烦,但它适合高度平行问题,Twister可以更有效率地处理迭代问题.
这工作展示了在不同的问题类型中,适用于MapReduce模型的算法怎样影响了效率和可伸缩性,并允许我们通过比较两个框架的优缺点来判断哪个框架是更有效的.
本研究是具有重要意义的科学计算问题,因为这经常不是一个轻松的任务去使用复杂的迭代方法来解决关键问题.
1.
Introduction介绍科学计算是一个应用计算机科学解决典型科学问题的研究领域.
它不应该被误解为只是计算机科学.
科学计算通常是相关联的大型计算机建模和仿真,并且通常需要大量的计算机资源.
云计算[1]很适合解决这些科学计算问题,其承诺提供几乎无限的资源.
在适应资源密集型的应用程序的云,应用程序必须降低到可以成功地利用云资源的框架,这正是我们正在研究的云项目的科学计算方法.
一般来说,云基础设施是基于效率不高和经常注定失败(网络故障和硬件故障导致的失败)的商业电脑.
38软件总是失败这可能会导致严重的问题.
当在一个分布式系统中面临硬件或网络故障的时候,最好的办法通常是复制重要数据和重试失败的计算.
也有分布式计算框架,提供容错机制,MapReduce框架[3]就是这样的框架.
MapReduce作为在大量计算机上执行分布式计算的并行计算框架是由谷歌首次开发.
自那时以来,它已经作为一个可执行自动可伸缩的分布式应用程序的云计算框架得以普及.
谷歌MapReduce实现是专有的,这也就导致开源同行像HadoopMapReduce[4]的开发.
Hadoop是一个基于谷歌的MapReduce和谷歌文件系统[5](GFS)的Java软件框架.
Hadoop项目正在被Apache积极研制开发并且在商业和搜索方面被广泛应用,使得它有一个庞大的用户基础和足够多的作业.
MapReduce应用程序的结构非常严格,同时在处理分布式应用程序其自动可伸缩性是很有吸引力的.
对于MapReduce模型减小算法复杂度也不是轻而易举的事情并且并没有保证由此生成的MapReduce算法是有效的.
先前的工作已经证明,MapReduce非常适合简单和通常高度平行的问题.
谷歌在他们的论文中展示,他们使用[3]MapReduce对于各种各样的问题,如大规模索引、图计算、机器学习和从一个巨大的组索引网页提取特定的数据.
其他相关工作[6]表明,MapReduce可以成功地用于图问题,如发现图形组件,质心聚类、枚举矩形和三角形列举.

MapReduce也进行过科学问题[7].
它在简单问题中表现良好,像组极方法产生随机变量和整数排序.
然而,MapReduce也被表示有很大问题在更复杂的算法,如共轭梯度,快速傅里叶变换和块三对角线性系统求解.
此外,这些问题大多是用迭代的方法来解决这些问题,表明MapReduce可能不适合算法,迭代性质.
然而,这里有超过一种类型的迭代算法.
去研究如果MapReduce模型不适合所有迭代算法或者只是其中一个特定的子集,我们设计了一组类科学算法.
算法根据他们如何难适应他们MapReduce模型和由此引起的结构来分类.
为了比较这些分类,我们从每个分类选择算法去适应MapReduce模型,研究他们的效率和可伸缩性.
这样的分类可以让我们准确判断哪些算法更容易适应MapReduce模型和对并行效率和可伸缩性的自适应算法,什么样的效应属于一个特定的分类.
接下来的文章组织如下.
第二节简要介绍了SciCloud项目.
第三节描述了在我们的云计算的基础设施上的HadoopMapReduce模型和第四节描述了不同分类迭代算法.
第五部分概述了算法实现和分析.
第六节描述了一个替代MapReduce框架称为Twister和生产分析的算法框架.
第七节提到相关工作和第8部分总结了论文,描述了在SciCloud项目中未来的研究方向.
392.
科学云计算科学云计算(SciCloud)项目的主要目标[2]是研究在大学范围内建立私有云.

这些云、学生和研究人员在解决计算密集型科学,数学和学术问题上能够有效地使用现有的大学计算机网络资源.
传统来说,这样的计算密集型问题针对性的面向批处理的模型的网格计算领域.
SciCloud试图用更多互动和面向服务的云计算模型实现去实现,这适合较大的应用程序.
它的目标是开发框架,其中包括模型和为建立适当的选择、状态和数据管理的方法,自动伸缩功能和互操作性的私有云.
一旦这样的云是可行的,可以用它们来为大学中有兴趣的团体之间的合作和在内部测试的试用、创新和社交网络提供更好的平台.
SciCloud也侧重于寻找新的分布式计算算法和试图在MapReduce算法中减少一些科学计算问题.
在市场上虽然有几个公共云,GoogleApps(包括谷歌邮件、文档、网站、日历等)、GoogleAppEngine[8](有限的提供一个可供Java、Python的弹性平台应用)和AmazonEC2[9]可能是最众所周知和广泛应用的.
AmazonEC2是一种在操作系统上允许完全控制虚拟机.
可以从许多可用的AmazonMachineImages(AMI)和几个可能的虚拟机中选择一个合适的操作系统和平台(32位和64位).
这一点不同于CPU、内存和磁盘空间.
此功能允许我们对于任何特定的任务自由选择合适的技术.
对于EC2,服务价格取决于机器的大小,它的正常运行时间,以及使用云的中多少带宽.
这里也有几个自由实现的云基础结构如:Eucalyptus[10].
Eucalyptus允许用AmazonEC2创建私有云.
因此,云计算应用程序最初可以在私有云中开发,稍后可以推广到公共云.
这是对于研究和学术有着巨大的帮助,作为实验的初始费用可以很大程度上降低了.
这个主要目标我们已经建立了SciCloud集群上8节点组成的SUNFireServerBlade系统与2-coreAMDOpteron处理器,使用Eucalyptus技术.
集群后来延长2个节点采用双四核处理器和32GB的内存,每个节点用单一的四核处理器加上4个节点,每个节点8GB的内存.
虽然一些应用程序是明显来自与这样一个私有云的设置,我们使用它在分布式计算和移动web服务域[2]上解决我们的一些研究问题.
在移动web服务领域,我们尽可能在蜂窝网络扩展我们的MobileEnnterprise[11]的负载.
一个MobileEnnterprise可以通过参与MobileHosts建立一个手机网络,后者充当对智能手机和他们的客户web服务提供者.
MobileHosts通过遵守以下web服务标准[12]启用用于企业的特定用户服务的无缝集成,同时也会用于收音机链接,通过资源约40束的智能手机中.
几个应用程序通过MobileHost被开发并展示了卫生保健系统,协同移动、社交网络和多媒体服务域[11].
我们改变一些MobileEnterprise关于SciCloud的元件和负载平衡器并证明了移动Web服务中介框架[13]和组件是水平伸缩的.
更详细的分析在[14].
除了以上在我们的研究中帮助我们,SciCloud也有几个在数据挖掘、生物信息学领域的想法支持着我们的研究.
3.
科学云计算Hadoop框架为了有一个试验基于MapReduce应用的地方,我们已经建立了一个动态可配置SciCloudHadoop框架.
我们使用Hadoop集群去解决一些科学计算问题,如CGMapReduce算法.
细节将在本节中被解决.
MapReduce是一种编程模型和分布式计算框架.
这是由谷歌率先开发出来用于处理非常大量日常生活中的每天都在增长的原始数据,如索引文件和web请求网络日志.
谷歌使用MapReduce在数百或数千个普通计算机上处理数据.
MapReduce应用程序获取键值对列表作为输入,并由两个主要函数.
Map和Reduce.
Map对输入列表中分开处理每个key-valuepair,并输出一个或多个key-valuepairs结果.
map(key,value)[(key,value)].
Reduce函数聚合Map函数的输出.
它得到一个key值和一个所有被分配给这个key值的一个列表所有值作为输入,执行用户定义的聚合并输出一个或多个key-valuepairs值.
reduce(key,[value])[(key,value)].
用户只需要生产这两种方法来定义一个MapReduce应用程序;框架负责一切,包括数据分布、通信、同步和容错.
这使得用MapReduce编写分布式应用程序更加容易,因为框架允许用户集中在算法和而它自己能够处理其他一切.
并行化在MapReduce框架是在并行集群中通过在不同的机器上执行多个Map和Reduce任务.
然而,谷歌的MapReduce实现是专有的.
ApacheHadoop[4]是一个用Java编写的开源的MapReduce实现.
除了MapReduce,Hadoop还提供Hadoop分布式文件系统[15](HDFS)可靠地在成百上千的计算机中存储数据.
HDFS是近似并基于谷歌文件系统(GFS)[5].
HadoopMapReduce框架用一种分布式样式使用HDFS既存储MapReduce应用程序的输入和输出.
一个简单的Hadoop集群包含n≥1台机器运行Hadoop软件.
集群是一个单一的主集群与不同数量的从节点.
从节点可以同时作41为MapReduce的计算节点和HDFS的数据节点.
ApacheHadoop正在被大力发展用于商业和研究.
分析了MapReduce科学计算的性能,我们建立了一个小的SciCloudHadoop集群.
集群是由一个主节点和十六个从节点组成.
只有从节点充当MapReduce任务节点,可以16平行MapReduce任务可以执行.
每个节点都是一个虚拟机与2.
2GHz处理器,500MB的RAM和10GB磁盘空间分配给HDFS,使的总大小HDFS160GB.
更多的节点可以被添加到集群动态,当需要.
我们的脚本,可以添加更多的从节点到框架和可以配置到主节点.
我们也支持自动伸缩功能,这个功能能基于观察到大量的单个实例一开始就具备更多的从节点.
细节将会在我们未来出版物上刊登.

4.
算法类我们已经设计了一组科学算法的类基于他们如何难适应MapReduce模型和需要哪些步骤.
算法分为不同的类如下:可以适应作为一个单一的MapReduce模型执行的算法.
可以适应作为一个顺序的固定数量MapReduce模型执行的算法.
在一个迭代的内容都被表示为一个单一的MapReduce模型执行的算法.
在一个迭代的内容都被表示为一个多个MapReduce模型执行的算法第一个类可以被认为代表高度并行算法,第二种则被认为是简单的并行算法.

第三和第四个代表迭代算法,一些类型的同步必须在每次迭代之间执行;例如检查结束条件或总计和广播上一次迭代的结果.
第四类算法被认为是更复杂的迭代算法,在每个迭代中只有一些操作可以完全并行化.
算法属于第4类通常很难有效地并行化,这是更难以实现适应他们MapReduce模型.
研究属于一个特定的类是如何影响效率和可伸缩性的算法,我们从每个类MapReduce选择算法和分析结果.
我们选择的算法将在下面章节介绍.
除了属于特定的类,并行效率和可伸缩性也受算法特征的影响.
例如,它取决有多少在MapReduce模型外的计算.
当它不能完成在MapReduce的reduce上,用迭代算法或聚合检查结束条件和处理最终结果,意味着经常有些部分的迭代算法必须在模型外执行并行性,从而降低了整个算法的并行效率.
同时,属于第二个类的算法会变得不那么有效,如果MapReduce模型执行的数据很大.
在不同的MapReduce模型间切换作为同步步骤,输入数据为每个不同的MapReduce的执行必须再次进42行处理,这意味着在第二和第三类当第二类步骤的数量比得上第三类迭代的次数时,可能没有实际的区别,.
此外,并行效率不仅取决于该算法对MapReduce模型的适应或继承特征的算法本身,还取决于执行环境.
在不同的MapReduce框架中执行MapReduce应用程序可以在应用程序的运行时间上产生重大影响,还取决于此应用程序中运用的算法属于哪一类.
5.
在MapReduce中减少迭代算法我们从第3节谈到的每个算法类选择了一个算法来说明不同的设计选择和问题,在HadoopMapReduce框架中出现的科学计算问题的.
这些算法是:共轭梯度(CG).
两个不同的k-medoid聚类算法:——分区在Medoids(PAM).
——聚类大型应用程序(CLARA).
整数的因子分解.
CG属于第4类,PAM属于第三类,CLARA属于第二类,和整数因子分解是第一类的例子和高度并行算法.
对于这里的每个算法,我们提供一个简短的描述、指出为什么他们属于给定的类的原因,去适应MapReduce模型的步骤和实验结果.
5.
1共轭梯度(CG)共轭梯度法(CG)是一种求解矩阵形式的线性方程组的迭代算法:Ax=b在这个线性系统中,A是一个已知的矩阵,b是一个已知的向量,x是向量的解.
CG的总体想法是起始一个不准确的解x,然后通过不断的迭代提高其解的准确性.
CG是一个相对复杂的算法,不太可能直接用整个算法构建MapReduce模型.
相反,使用CG的矩阵和向量操作在每个迭代都简化成MapReduce模型.
因为这,它直接属于第四类算法.
矩阵向量乘法.
点积.
43两个向量加法.
矢量和标量乘法.
这些操作中的一个用于CG,一个新的MapReduce工作就在运行.
导致在每一次迭代时多个MapReduce工作在运行.
这不是最有效的方式,因为Hadoop框架需要时间去安排,启动和完成,它可以被视为在MapReduce工作中每个迭代的延迟和执行多个作业构成了一个显著的开销.
此外,在Hadoop,矩阵A存储在HDFS并且被当做每一个迭代中输入的矩阵向量进行乘法操作.
在HadoopMapReduce框架中在不同的运行的MapReduce任务下,缓存输入是不可能,所以每次执行这个操作,输入必须再次从文件系统中读取.
作44为一个矩阵的值在迭代之间永远不会改变,在每一个迭代重复同样的工作.
这意味着一个重要的额外开销.
实验为了能够并行加速计算运行在不同数量的并行节点.
并行加速措施并行执行多少次是在一个节点上运行相同的MapReduce算法速度比.
如果它是大于1,这意味着至少有一些获得并行任务.
这等于加速节点的数量被认为是理想的,意味着算法有一个完美的可伸缩性.
CG算法的运行时间都显示在表1,计算速度显示在图1.
它花了220秒去解决系统在只有24个未知的事物在16个节点的集群,这在这样一个小数量的计算下,无疑是非常缓慢的求解线性系统.
不幸的是,这些解决更大的系统的测试也显示:CGMapReduce算法并不能随着数据大小的增加而改善.
例如,一个8000未知事物的线性系统,使用MapReduce算法花了近2小时解决.
这些结果表明,大部分的时间都花在MapReduceCG的后台任务,而不是实际的计算中.
5.
2分割环绕物件法分割环绕物件法[17](PAM)是一个迭代kmedoid聚类算法,在这领域具有重要的价值.
k-medoid聚类的一般的想法是,每个集群被最核心的元素所代表,medoid和在所有对象和集群之间的比较减少到对象和集群中medoids的比较.
为了聚集一组对象到k不同集群,PAM算法首先选择k随机对象作为初始medoids.
在第二步,对于每个在数据集的对象,距离每个kmedoids都被计算并且对象都被分配到与medoid最接近的集群.
因此,数据集分为k不同集群.
在下一步的,PAM算法重新计算每个medoid的位置,选择最中央对象作为新medoid.
这个将对象划分到集群,并重新计算集群medoid的位置的过程被重复,直到与之前的迭代结果没有变化,这才意味着集群变得稳定.
类似于CG,PAM制定了初步解决问题的方法,在这种情况下,聚类,在每一个迭代后,提高了解决方案的准确性.
同时,和CG一样,(PAM)不可能将整个算法用于MapReduce模型.
然而,整个迭代的内容可以概括为MapReduce模型,表明PAM算法属于第三类.
由此产生的MapReduce工作可以表示为:Map:——找到最接近的medoid和在其集群分配对象,.
——输入:(集群id、对象).
——输出:(新集群id、对象).
Reduce:45——找到哪个对象是最中央,把它指定为集群中一个新的medoid.
——输入:(集群id(所有集群对象列表)).
——输出:(集群id、新medoid).
Map函数重新计算每个对象属于哪个集群,Reduce函数为每个生成的集群找到一个新中心.
MapReduce任务重复执行直到集群中Medoid位置的不再变化.
类似于CG,因为在每个时间都有一个新的MapReduce作业执行,PAM也存在工作滞后和在每一个迭代从文件系统重读输入的问题.
5.
3聚类大型应用程序聚类大型应用程序[17](CLARA)也是一个迭代k-medoid聚类算法,但是相比PAM,它只集群数据集的随机子集的小找到整个数据集medoids候选人.
这个过程被重复多次,最好的medoids组候选人被选择作为最终结果.
不同于PAM,迭代的结果是相互独立的,并且不需要执行在一个序列上.
因此,同时在不同的任务中执行内容的和消除迭代结构的迭代算法是可能的.

无论是执行多少不同的任务,一切都可以减少到两个不同的MapReduce工作.
第一步工作是从输入数据集选择一定数量的随机子集,同时使用PAM的集群和输出结果.
第二个MapReduce工作是计算第一个任务的每个结果的质量检测,通过在整个数据集的一个并发的MapReduce任务中检查他们.
由于只有两个MapReduce工作,工作延迟保持最小并且输入数据集只读两次.
这两个MapReduce工作概述如下:第一个CLARAMapReduce任务:Map:——分配给每个对象一个随机的key值.
——输入:(key、对象).
——输出:(随机key,对象).
Reduce:——读前n的对象,这是升序排序的关键.
因为钥匙被随机指定,在排序后对象的顺序是随机的.
在n个对象上运行PAM的聚类找到k不同候选medoids.
——输入:(key,对象的列表).
——输出:(关键、kmedoids的列表).
第二个CLARAMapReduce任务:Map:46——每个对象,找到最接近的距离medoid并计算它们的距离.
对于每一个对象,有多少候选集medoids就进行多少次操作,并且为每个对象生成一个输出.
——输入:(集群、对象).
——输出:(候选集合id,最近的medoid的距离)[每个候选集都有一个输出].
Reduce:-用相同的候选集合id计算距离之和.
——输入:(候选集合id,距离的列表).
——输出:(候选集合id、总数(距离的列表)).
第二个任务的结果是一个列表的计算总数,每个代表和所有对象距离他们最近的medoids的总和,一个用于每个候选集.
对象之间最小的距离和的候选组medoids并且他们最近的medoids作为最好的聚类.
MapReduce任务被执行的数量始终是两个,这个算法属于第二类.
从实验结果(表2、3和图2、3)可以看到,CLARAMapReduce算法速度远远超过PAM,尤其是当数据集中对象的数量增加的时候.
PAM是不能够处理数据集大于100000对象而CLARA可以处理包含数百万甚至数千万对象的集群集.
还应指出的是,最小数据集时间对于CLARA和PAM已经相当大了.
这是因为MapReduce框架的后台任务开始的相对缓慢,所以每个单独的MapReduce任务开始减慢了算法.
这对47PAM的影响比对CLARA大得多,因为PAM中有太多了的MapReduce迭代、,CLARA只使用两个MapReduce任务.
5.
4.
整数的因子分解整数的因子分解是一种将整数划分成一组相乘得到原来整数的素数的方法.

例如一个数21的因子是3和7.
整数的因子分解被使用与例如打破RSA密码体制.
在这种情况下我们选择整数的因子分解的最基本的方法,试除法.
这个方法不48用于实践,因为它相对缓慢,并且存在更快方法像一般数域筛网[18].
但我们选择这个方法纯粹是为了说明它适应一个高度平行问题,相较于其他三个算法,它属于MapReduce模型的第一类.
用试除法去分解一个整数,这个整数所有可能的分解都会被检查是否均匀划分.

如果每个都通过检查,那么它是一个分解.
这可以采取MapReduce模型,通过划分多个可能的分解在不同的分组中,并同时对每个分组用单独的Map或Reduce任务检查:Map:——得到一个数字被分解作为输入,发现数量的平方根并从2到数字的平方根分为n个更小的范围,输出每一个.
——输入:(key、数字).
——输出:(id,(开始、结束、数字))(每个范围的一个输出,总共n个].
Reduce:——得到在哪里验证分解一个数字和一个范围,,作为输入,并发现如果任何数字在这个范围均匀划分数字.
——输入:(id,(开始、结束、数字)).
——输出:(id、因素).
因此,不同于先前的算法,这个算法是减少到一个单一的MapReduce任务,这意味着在序列运行多个任务没有开销,和为什么该算法属于第一个算法类.

49整数分解的运行时间在表4中给出,速度在图4显示.
从图4可以看到,当因子分解的数字很小的时候,并行使用多个worker只有很小的优势.
相对于2节点集群加速比略高于1,只有在16个节点集群才达到2.
22.
这是因为计算数量相对框架的后台任务更小.
然而,随着输入数字规模的增大,加速开始显著增长.
当有21位的输入时候,两个和四个节点执行的速度是2.
07和4.
17,表明使用多个节点有一个理想的结果发现分解的大小什么时候输入足够大.
用大量的节点增长的速度达不到节点增长数量,表明计算不够长去对于使用16个节点得到完整的收益.
计算的增长速度数据表明,这种算法具有良好的可伸缩性,算法属于第一个类可以非常适合HadoopMapReduce框架.
5.
5.
总结分析从我们的实验结果中,我们发现HadoopMapReduce在迭代算法中有几个问题.
第4类复杂的迭代算法在每一次迭代中可能需要一个或多个执行MapReduce任务.
然而,如果迭代次数过大,然后在一个序列中执行许多MapReduce任务,因为工作50延迟而导致低效率.
任务的延迟时间就是MapReduce框架的安排、开始和结束MapReduce工作,不包括花在做实际的计算上的时间.
此外,HadoopMapReduce任务的输入到存储在HDFS,HDFS的数据是按分布式方式保存得.
每次执行MapReduce任务时都要从读这个输入,即使很大一部分的输入在任务运行之间的是不会改变,因为它不可能在HadoopMapReduce框架缓存输入.
对于如CG和PAM算法,大量的输入数据保持不变,这意味从文件系统中很多次读入相同的输入数据,在每一个迭代做重复的工作和最后导致结果效率降低.
对于算法类3和4,在每个迭代中一个或多个MapReduce任务运行,工作延迟,和无法缓存MapReduce应用程序输入可以显著增加运行时间.
这意味着大量的时间都花在MapReduce框架的后台任务管理上,和更少的时间花在执行实际的计算.
当有大量的迭代时,这大大影响了迭代算法.
不管遇到的问题,所有实现算法都能够利用多个节点实现加速,如图5所知,在我们的测试中RSA有最好的加速和PAM有最坏加速.
然而,很难充分比较不同算法之间的加速数据,因为他们强烈地依赖于算法特点,输入尺寸,计算的时间和后台任务等.
对于需要更多后台任务的迭代MapReduce算法,达到一个理想的加速是更加困难的.
同时增加问题的大小,因此花在实际的计算时间,通常改善结果,也增加了花在后台任务的时间,增加输入大小意味着在每一个迭代有更多的时间花在阅读来自文件系统的输入数据上.
6.
TwisterMapReduce框架在认识了Hadoop在每个算法类的问题后,我们对与其他MapReduce框架的比较结果非常有兴趣,去判断哪个是Hadoop框架本身的问题和一般MapReduce固有的问题.
去看看什么影响了在每个算法类中MapReduce框架实现在算法效率和可伸缩性的方面的选择.
51WechoseTwister[19]作为替代MapReduce框架,因为它被宣传成迭代MapReduce框架,因此它应该在Hadoop中对于Hadoop已经显示出了麻烦的算法类3和4提供一个更好的方案.
TwisterMapReduce框架区分迭代过程中不会改变的静态数据和在每一个迭代中可能会改变的正常数据.
它还提供了长期运行Map和Reduce任务而这些任务作为Hadoop中必须的,不需要在MapReduce运行迭代之间被终止.
这两个是主要的特点,单独从Hadoop中分离Twister和提供迭代算法更好的支持.
JaliyaEkanayakeetal.
[20]相比HadoopMapReduce,Twister和的MPI在不同的数据和计算中加强应用.
他们的研究结果表明,Twister可以大大减少MapReduce应用程序迭代的开销.
我们决定测试类3和4的TwisterMapReduce框架,看看Twister是否可以更快的管理迭代算法.
我们在SciCloud建立了一个小的Twister集群.
集群是一直于Hadoop集群非常类似去为了更精确的比较.
它是由一个主节点和十五从节点.
主节点和从节点都充当MapReduce任务节点,结果就是MapReduce任务可以在16个平行节点上执行.
每个节点都是一个2.
2GHz处理器,500MBRAM的虚拟机.
Twister没有分布式文件系统,和所有输入文件仅仅是分配到本地硬盘的节点.
我们在Twister中实现的算法是CG和PAM,代表了类3和4.
表5和图6显示了这些实验的运行时间.
6和7展示了计算速度.
52比较了Twister和Hadoop(表1和2)对这些算法运行时间清楚地表明Twister对于类3和4是更高效.
Twister在相同大小的问题上可以用更少的时间去解决更大的问题并且当有16个节点的时候,这是在Hadoop上运行时的50-100倍的速度,.
算法结构的方式是适应MapReduce模型的,在Twister和Hadoop中是保持完全相同的,然而Twister更高效处理MapReduce应用程序迭代后台任务.
在Hadoop工作每次迭代滞后约19–20s,而在Twister中不管它迭代的次数都是低于3s.
Twister还存储大量的输入到内存,不需要在每一个迭代从文件系统读一遍.
在CG中,这意味着能够在集体记忆的集群和inPAMit中存储整个矩阵和意味着能够存储所有的集群对象.
然而,Twister也在分布式应用程序具有一定的局限性.
使用Twister的明显53的优势在它跨迭代在内存中保持静态输入数据的能力.
但它意味着,这种静态的数据必须在Twister机器配置融入集体记忆.
在数据密集型任务中这可能是一个相当不合理的需求.
例如,用twister处理1TB的数据将需要超过128台机器与每个8GB内存作为只是存储数据到内存中,更不用说在应用程序的其余部分中需要的内存,框架本身和他运行的操作系统.
Twister还没有一个能和Hadoop提供的容错机制相比的合适的容错机制,这在运行在一个公共云是一个非常严重的问题,Twister机器容易相对频繁出现问题.
比较Twister和Hadoop的属于第三和第四类的算法已经表明,Twister更适合这些类.
同时,由于Hadoop提供的容错,Hadoop更适合第一个类的算法以及在一般的数据密集型算法,Twister在拟合数据到内存中有问题.
结果不是太明确对于减少数据密集型算法属于第二类.
当不同的MapReduce程序的数量并不大时,Hadoop可以执行良好并且考虑到容错,它应该被认为是更合适的.
但因为在Hadoop中短时间运行的任务,每次一MapReduce周期结束都被终止,当随着MapReduce任务增加,Hadoop渐渐失去效率,Twister则代替成为更好的选择.
因此,在用第二类算法选择框架应该更取决于需要MapReduce步骤数量和任务需要的数据大小多少.
7.
相关的工作除了Hapoop和Twister,还有多种基于Mapreduce模型的分布式计算框架的实现.
YingyiBuetal提出了通过支持迭代MapReduce应用,扩展了MapReduce框架的HoLoop.
它添加了多张数据缓存机制,并使得任务调度器loop-aware.
他们声称自己和Twister不同,因为HaLoop更适合于迭代算法因为使用内存缓存和长时间运行MapReduce任务使得Twister与商品硬件相适应,而且更容易失败.
MateiZahariaetal.
提出了Spark,这是一个支持迭代应用同时保留了MapReduce的可伸缩性和容错机制的框架.
Spark关注的是不同的类似MapReduce的任务的执行时它们之间的数据的缓存.
这些执行通过弹性分布式数据集(RDDs)可以在整个计算机群的内存中显示地保存.
但是,Spark不支持简化的组操作,只能使用一个任务来收集结果,这将严重影响算法的可伸缩性.
不过对于并行的Reduce任务,每个任务都能处理不同的子群的数据,这也有利于算法的实用性.
54Google解决MapReduce问题使用的是图迭代算法----Pregel.
GrzegorzMalewiczetal.
介绍Pregel算法时认为对于图迭代算法来说这是一个可伸缩性和容错性的平台.
与其他以前的相关工作相比,Pregel不是基于MapReduce模型,而是基于BulkSynchronous并行模型.
在Pregel中,计算是由supersteps构成的,这些用户定义的方法之和每个图的当前节点有关.
每一节点都有一个状态并且能接受从在前一个super-step中的另一个的节点上发送来的消息.
尽管节点的核心方法是和在每个项目当地的执行的MapReduce的图操作是相似的.
能够保留两个super-step之间的每个节点的状态为迭代算法提供了支持.
类似的,Phoenix为共享内存系统实现了MapReduce.
它的目标是在没有并行管理程序负担的前提下支持高效执行.
由于它是在共享内存上使用的,它就能不容以发生问题.
只要数据可以放进内存,我们就鼓励继续使用迭代算法.
这个想法很有趣,但是我们不能认为共享内存模型是SciCloud项目的解决方案,因为我们对使用现有的大学资源和商业硬件来解决这个问题更感兴趣.
SaurabhSehgaletal用SAGA(用于网格应用的的简单API)实现了MapReduce模型.
这是一个支持独立分布式编程的平台,它旨在提供分布式科学用的互操作性.
他们认为MapReduce模型非常适合用来实现应用程序的互操作性而且它展现了分布式应用的三种不同层次互操作性.
首先,该应用可以在对应用不做任何修改的情况下使用不同的分布式平台;第二,应用可以在不同的编程模型之间无缝切换;第三.
多个编程模型可以同时用来解决同一个任务.
他们得出结论说,应用级互操作性的影响是迈向理解通用编程模型的重要一步8.
结论以及未来工作指导云计算及其近乎无限的资源,似乎很适合解决消耗很多资源的科学计算问题.