基于匹配规则的MapReduce任务调度模型

基于开源云计算平台Hadoop的MapReduce是当前流行的分布式计算框架之一,然而其先进先出(FIFO)调度算法存在资源利用效率低下的问题。提出了一种基于资源匹配规则的MapReduce任务调度模型并进行了算法实现。该调度模型通过获取任务的资源需求与计算节点的剩余资源,依据资源的匹配性进行任务分配,提高了系统的资源使用效率。首先对MapReduce的调度过程进行建模,提出了资源及匹配度的量化定义和相应的计算公式;然后给出了资源测量的具体方法及算法实现;最后利用TeraSort、GrepCount和WordCount任务与FIFO调度算法进行实验对比,实验结果显示,最好的情况下,提出的调度模型任务完成时间减少了22.19%,而最差情况下的吞吐量也提高了25.39%。     

一种Hadoop YARN的资源调度机制

YARN is a resource management system widely used in Hadoop. It supports MapReduce, Spark, Storm and other computing frameworks, and has become the core component of big data ecology. However, in Hadoop YARN’s existing resource scheduler, a resource guarantee mechanism based on resource reservation, will produce resource fragmentations, leading to a waste of resources. In order to improve the resource utilization and throughput of the cluster, this paper proposes a resource allocation mechanism based on reservation and backfill. In this mechanism, based on the priority of the job, it decides whether to make a reservation to the resource and introduce a backfill strategy to backfill the resource without affecting the execution of the reservation job. Experiments show that the resource scheduling mechanism based on reserved backfill can effectively improve the resource utilization and throughput of Hadoop YARN cluster.     

Adapting scientific computing problems to clouds using MapReduce

Cloud computing, with its promise of virtually infinite resources, seems to suit well in solving resource greedy scientific computing problems. To study this, we established a scientific computing cloud (SciCloud) project and environment on our internal clusters. The main goal of the project is to study the scope of establishing private clouds at the universities. With these clouds, students and researchers can efficiently use the already existing resources of university computer networks, in solving computationally intensive scientific, mathematical, and academic problems. However, to be able to run the scientific computing applications on the cloud infrastructure, the applications must be reduced to frameworks that can successfully exploit the cloud resources, like the MapReduce framework. This paper summarizes the challenges associated with reducing iterative algorithms to the MapReduce model. Algorithms used by scientific computing are divided into different classes by how they can be adapted to the MapReduce model; examples from each such class are reduced to the MapReduce model and their performance is measured and analyzed. The study mainly focuses on the Hadoop MapReduce framework but also compares it to an alternative MapReduce framework called Twister, which is specifically designed for iterative algorithms. The analysis shows that Hadoop MapReduce has significant trouble with iterative problems while it suits well for embarrassingly parallel problems, and that Twister can handle iterative problems much more efficiently. This work shows how to adapt algorithms from each class into the MapReduce model, what affects the efficiency and scalability of algorithms in each class and allows us to judge which framework is more efficient for each of them, by mapping the advantages and disadvantages of the two frameworks. This study is of significant importance for scientific computing as it often uses complex iterative methods to solve critical problems and adapting such methods to cloud computing frameworks is not a trivial task.     

MapReduce:新型的分布式并行计算编程模型

MapReduce是Google提出的分布式并行计算编程模型,用于大规模数据的并行处理。Ma-pReduce模型受函数式编程语言的启发,将大规模数据处理作业拆分成若干个可独立运行的Map任务,分配到不同的机器上去执行,生成某种格式的中间文件,再由若干个Reduce任务合并这些中间文件获得最后的输出文件。用户在使用MapReduce模型进行大规模数据处理时,可以将主要精力放在如何编写Map和Reduce函数上,其它并行计算中的复杂问题诸如分布式文件系统、工作调度、容错、机器间通信等都交给MapReduce系统处理,在很大程度上降低了整个编程难度。MapReduce日益成为云计算平台的主流编程模型。Apache Hadoop项目提供开源的MapReduce系统还有待进一步完善。     

异构Hadoop集群下的负载自适应反馈调度策略

随着基于Hadoop平台的大数据技术的不断发展和实践的深入,Hadoop YARN资源调度策略在异构集群中的不适用性越发明显。一方面,节点资源无法动态分配,导致优势节点的计算资源浪费、系统性能没有充分发挥;另一方面,现有的静态资源分配策略未考虑作业在不同执行阶段的差异,易产生大量资源碎片。基于以上问题,提出了一种负载自适应调度策略。监控集群执行节点和提交作业的性能信息,利用实时监控数据建模、量化节点的综合计算能力,结合节点和作业的性能信息在调度器上启动基于相似度评估的动态资源调度方案。优化后的系统能够有效识别集群节点的执行能力差异,并根据作业任务的实时需求进行细粒度的动态资源调度,在完善YARN现有调度语义的同时,可作为子级资源调度方案架构在上层调度器下。在Hadoop 2.0上实现并测试该策略,实验结果表明,作业的自适应资源调度策略显著提高了资源利用率,集群并发度提高了2到3倍,时间性能提升了近10%。     

异构云环境下基于分簇的云资源感知任务调度方案

针对提高异构云平台中资源调度的效率,提出了一种基于任务和资源分簇的异构云计算平台任务调度方案。利用K-means算法,根据任务的CPU和I/O处理时间对任务分簇,根据资源的计算能力对资源分簇;然后,将任务簇对应到合适的资源簇,并利用最早截止时间优先（EDF）算法对任务簇中的独立任务进行调度,利用提出的改进型最小关键路径（MCP）算法对依赖性任务进行调度。实验结果表明,在资源异构的云计算环境中,该方案执行任务时间短、能耗低。     

Context‐aware scheduling in MapReduce: a compact review

It is a fact that the attention of research community in computer science, business executives, and decision makers is drastically drawn by big data. As the volume of data becomes bigger, it needs performance‐oriented data‐intensive processing frameworks such as MapReduce, which can scale computation on large commodity clusters. Hadoop MapReduce processes data in Hadoop Distributed File System as jobs scheduled according to YARN fair scheduler and capacity scheduler. However, with advancement and dynamic changes in hardware and operating environments, the performance of clusters is greatly affected. Various efforts in literature have been made to address the issues of heterogeneity (i.e., clusters consisting of virtual machines and machines with different hardware), network communication, data locality, better resource utilization, and run‐time scheduling. In this paper, we present a survey to discuss various research efforts made so far to improve Hadoop MapReduce scheduling. We classify scheduling algorithms and techniques proposed in the literature so far based on their addressing areas and present a taxonomy. Furthermore, we also discuss various aspects of open issues and challenges in the scheduling of MapReduce to improve its performance. Copyright © 2015 John Wiley & Sons, Ltd.     

基于Kriging代理模型的动态云任务调度方法

任务调度在云计算环境中发挥着重要作用。提出一种基于Kriging代理模型的动态云任务调度方法。通过对云任务在不同资源组合下的性能表现进行Kriging代理模型建模并优化,从而得到对应于该云任务的最优资源分配方案;利用云平台的API,可动态对该云任务实施资源调度。基于OpenStack开源云平台,对两个工程计算应用进行了任务调度性能测试,结果表明该方法可有效动态调整云任务中的资源配给,按需按优对平台中的云任务进行资源调度。     

基于YARN资源调度器的MapReduce作业数调节方法

YARN是Hadoop的一个分布式的资源管理系统,用来提高分布式集群的内存、I/O、网络、磁盘等资源的利用率.然而,YARN的配置参数众多,要对其人工调优并获得最佳的性能费时费力.本文在现有的YARN资源调度器的基础上,结合了一种闭环反馈控制方法,可在集群运行状态下动态地对MapReduce （MR）作业数进行优化,省去了人工调整参数的过程.实验表明,在YARN的容量调度器和公平调度器的基础上使用该方法,相比于默认配置,MR作业完成时间分别减少53%和14%左右.     

SHadoop: Improving MapReduce performance by optimizing job execution mechanism in Hadoop clusters

As a widely-used parallel computing framework for big data processing today, the Hadoop MapReduce framework puts more emphasis on high-throughput of data than on low-latency of job execution. However, today more and more big data applications developed with MapReduce require quick response time. As a result, improving the performance of MapReduce jobs, especially for short jobs, is of great significance in practice and has attracted more and more attentions from both academia and industry. A lot of efforts have been made to improve the performance of Hadoop from job scheduling or job parameter optimization level. In this paper, we explore an approach to improve the performance of the Hadoop MapReduce framework by optimizing the job and task execution mechanism. First of all, by analyzing the job and task execution mechanism in MapReduce framework we reveal two critical limitations to job execution performance. Then we propose two major optimizations to the MapReduce job and task execution mechanisms: first, we optimize the setup and cleanup tasks of a MapReduce job to reduce the time cost during the initialization and termination stages of the job; second, instead of adopting the loose heartbeat-based communication mechanism to transmit all messages between the JobTracker and TaskTrackers, we introduce an instant messaging communication mechanism for accelerating performance-sensitive task scheduling and execution. Finally, we implement SHadoop, an optimized and fully compatible version of Hadoop that aims at shortening the execution time cost of MapReduce jobs, especially for short jobs. Experimental results show that compared to the standard Hadoop, SHadoop can achieve stable performance improvement by around 25% on average for comprehensive benchmarks without losing scalability and speedup. Our optimization work has passed a production-level test in Intel and has been integrated into the Intel Distributed Hadoop (IDH). To the best of our knowledge, this work is the first effort that explores on optimizing the execution mechanism inside map/reduce tasks of a job. The advantage is that it can complement job scheduling optimizations to further improve the job execution performance.     

基于MapReduce的并行同态加密算法

根据云计算分布式的特点,并结合同态加密和Hadoop环境下MapReduce并行框架,提出了一种基于MapReduce计算框架的并行同态加密方案。实现了具体的并行同态加密算法,并对该方案的安全性和正确性进行了理论分析。同时,在16个核的计算集群中进行实验,数据加密的加速比可以达到13。实验结果表明,基于MapReduce的同态加密方案可以有效地减少数据的加密时间,有利于面向实时的应用。     

基于任务进度感知的异构Hadoop云平台任务调度方案

针对异构Hadoop云计算平台的任务调度问题,对Hadoop 推测执行调度和LATE调度方案进行研究,提出一种基于任务进度感知的自适应任务调度方案。首先,根据当前计算节点上的任务进度情况,估计任务近似完成时间(ATE),以此确定掉队者(Straggler)任务。然后,以平均节点任务进度的25%为阈值,将节点分为慢节点和快节点。当Straggler后备任务达到一定阈值时,将其优先分配到快节点中执行。实验结果表明,提出的方案能够为异构Hadoop平台合理分配任务,有效降低了任务完成时间和响应延迟,同时提高了平台吞吐量。     

Preemptive cloud resource allocation modeling of processing jobs

Cloud computing allows execution and deployment of different types of applications such as interactive databases or web-based services which require distinctive types of resources. These applications lease cloud resources for a considerably long period and usually occupy various resources to maintain a high quality of service (QoS) factor. On the other hand, general big data batch processing workloads are less QoS-sensitive and require massively parallel cloud resources for short period. Despite the elasticity feature of cloud computing, fine-scale characteristics of cloud-based applications may cause temporal low resource utilization in the cloud computing systems, while process-intensive highly utilized workload suffers from performance issues. Therefore, ability of utilization efficient scheduling of heterogeneous workload is one challenging issue for cloud owners. In this paper, addressing the heterogeneity issue impact on low utilization of cloud computing system, conjunct resource allocation scheme of cloud applications and processing jobs is presented to enhance the cloud utilization. The main idea behind this paper is to apply processing jobs and cloud applications jointly in a preemptive way. However, utilization efficient resource allocation requires exact modeling of workloads. So, first, a novel methodology to model the processing jobs and other cloud applications is proposed. Such jobs are modeled as a collection of parallel and sequential tasks in a Markovian process. This enables us to analyze and calculate the efficient resources required to serve the tasks. The next step makes use of the proposed model to develop a preemptive scheduling algorithm for the processing jobs in order to improve resource utilization and its associated costs in the cloud computing system. Accordingly, a preemption-based resource allocation architecture is proposed to effectively and efficiently utilize the idle reserved resources for the processing jobs in the cloud paradigms. Then, performance metrics such as service time for the processing jobs are investigated. The accuracy of the proposed analytical model and scheduling analysis is verified through simulations and experimental results. The simulation and experimental results also shed light on the achievable QoS level for the preemptively allocated processing jobs.     

不同MapReduce运行系统的性能测试与分析

随着云计算技术的发展,许多MapReduce运行系统被开发出来,如Hadoop、Phoenix和Twister等.直观上,Hadoop具有很强的可扩展性、稳定性,适合处理大规模离线应用;Phoenix具有运行速度快等优点,适合处理数据密集型任务;Twister是轻量级的迭代系统,非常适合迭代式的应用.不同的应用在不同的MapReduce运行系统中有着不同的性能.通过测试不同应用在这些运行系统上的性能,给出了实验比较和性能分析,从而为大数据处理时选择合适的并行编程模型提供依据.     

混合存储模式下MapReduce作业调度

在异构Hadoop集群场景中, 为了缓和由于纠删码和副本存储模式混合使用, 以及服务器节点本身实时算力差异造成的MapReduce作业处理效率低下的问题, 本文实现了一种根据数据存储情况和节点实时负载来在多并发场景下动态调节MapReduce作业任务分配情况的调度策略. 该策略通过修改当前Hadoop框架中的数据存储选址策略并对节点任务并发量进行动态控制, 在多作业并发时实现更加均衡的作业间资源分配. 实验结果表明, 相较于Hadoop默认的两种作业调度策略, 本文提出的调度模式能够将作业完成时间缩短约17%, 并有效避免部分作业面临的饥饿现象.     

云计算中Hadoop技术研究与应用综述

Hadoop作为当今云计算与大数据时代背景下最热门的技术之一,其相关生态圈与Spark技术的结合一同影响着学术发展和商业模式。首先介绍了Hadoop的起源和优势,阐明相关技术原理,如MapReduce,HDFS,YARN,Spark等;然后着重分析了当前Hadoop学术研究成果,从MapReduce算法的改进与创新、HDFS技术的优化与创新、二次开发与其它技术相结合、应用领域创新与实践4个方面进行总结,并简述了国内外应用现状。而Hadoop与Spark结合是未来的趋势,最后展望了Hadoop未来研究的发展方向和亟需解决的问题。     

A cloudification methodology for multidimensional analysis: Implementation and application to a railway power simulator

Many scientific areas make extensive use of computer simulations to study complex real-world processes. These computations are typically very resource-intensive and present scalability issues as experiments get larger even in dedicated clusters, since these are limited by their own hardware resources. Cloud computing raises as an option to move forward into the ideal unlimited scalability by providing virtually infinite resources, yet applications must be adapted to this new paradigm. This process of converting and/or migrating an application and its data in order to make use of cloud computing is sometimes known as cloudifying the application. We propose a generalist cloudification method based in the MapReduce paradigm to migrate scientific simulations into the cloud to provide greater scalability. We analysed its viability by applying it to a real-world railway power consumption simulatior and running the resulting implementation on Hadoop YARN over Amazon EC2. Our tests show that the cloudified application is highly scalable and there is still a large margin to improve the theoretical model and its implementations, and also to extend it to a wider range of simulations. We also propose and evaluate a multidimensional analysis tool based on the cloudified application. It generates, executes and evaluates several experiments in parallel, for the same simulation kernel. The results we obtained indicate that out methodology is suitable for resource intensive simulations and multidimensional analysis, as it improves infrastructure’s utilization, efficiency and scalability when running many complex experiments.     

Hadoop云平台MapReduce模型优化研究

针对Hadoop平台MapReduce分布式计算模型运行机制中的顺序制约而产生的计算资源浪费问题,从提高平台中每个执行节点的细粒度并行数据处理角度出发,结合Java共享内存多线程编程技术,对该模型进行了优化,提出一种MapReduce+OpenMP粗细粒度相结合的分布式并行计算模型。并在由四个节点组成的Hadoop集群环境下对不同规模大小的出租车GPS轨迹数据分析处理,验证该模型的性能和效率,实验结果证明MapReduce+OpenMP分布式并行计算模型确实能够提高针对大数据集的计算效率,是对Hadoop平台大数据分析处理模型有效的完善和优化。     

Performance evaluation of job schedulers on Hadoop YARN

To solve the limitation of Hadoop on scalability, resource sharing, and application support, the open‐source community proposes the next generation of Hadoop's compute platform called Yet Another Resource Negotiator (YARN) by separating resource management functions from the programming model. This separation enables various application types to run on YARN in parallel. To achieve fair resource sharing and high resource utilization, YARN provides the capacity scheduler and the fair scheduler. However, the performance impacts of the two schedulers are not clear when mixed applications run on a YARN cluster. Therefore, in this paper, we study four scheduling‐policy combinations (SPCs for short) derived from the two schedulers and then evaluate the four SPCs in extensive scenarios, which consider not only four application types, but also three different queue structures for organizing applications. The experimental results enable YARN managers to comprehend the influences of different SPCs and different queue structures on mixed applications. The results also help them to select a proper SPC and an appropriate queue structure to achieve better application execution performance. Copyright © 2016 John Wiley & Sons, Ltd.     

一种多用户MapReduce集群的作业调度算法的设计与实现

随着更多的企业开始使用数据密集型集群计算系统如Hadoop和Dryad实现了更多的应用,多用户间共享MapRe-duce集群这种既减少了建立独立集群的代价,同时又使得多用户间可以共享更多的大数据集资源的需求日益增多。在公平调度算法的基础上,结合槽分配延迟和优先级的技术,本文提出了一种改进算法,可以实现更好的数据本地性,改善整个系统的计算性能如吞吐率、响应时间等;同时为了满足差别化的商业服务,通过对用户设置相应的优先级保证紧急任务的完成。