基于节点性能的Hadoop作业调度算法改进

由于构成数据中心的计算设备一般都存在性能上的差异,但是Hadoop调度算法没有考虑不同节点的性能差异,导致节点间出现"忙闲不均"的现象,影响作业的执行效率。针对如上问题,在系统分析Hadoop资源管理机制(Yarn)源代码的基础上,提出了节点性能评价指标,综合考虑节点的硬件配置参数和运行过程中的动态性能指标。在此基础上对Fair Scheduler调度算法进行改进,实现了基于节点性能的任务分配,整体上提高了所有节点的利用率。在Hadoop集群上的实验表明,所提出的节点性能评价指标和对Fair Scheduler调度算法的改进,有效解决了节点的负载均衡问题,整体上提高了作业执行效率。     

使用确定随机Petri网对Hadoop公平调度的建模和性能分析

由于Hadoop能在同一时间处理多个用户提交的不同作业的多个任务,这使得用传统的方法对其进行建模和性能分析变得十分困难.为了解决这个问题,基于马尔可夫排队模型M/MMDP/C/K建立了一个随机Petri网(SPN)模型和一个确定随机Petri网(DSPN)模型来分别描述Hadoop调度中的数据状态和作业公平调度.通过设置DSPN中的使动谓词和随机开关来建模Hadoop公平调度和YARN公平调度.使用嵌入的马尔可夫链模型来分析单用户情景,而在分析多用户情景时则引入分解和迭代技术来减小模型的状态空间,从而避免产生状态爆炸问题.研究侧重于Hadoop中作业调度的平均性能,仅通过求解提出的分析模型,就可以对比和分析服务质量(QoS)的一些关键指标,如平均吞吐量、平均队列长度和平均时延.采用Matlab进行仿真:当每秒到达任务数大于等于20时,YARN算法的数据积压和平均时延明显少于公平算法;当每秒到达任务数大于等于30时,YARN算法的平均吞吐量明显高于公平算法.实验结果表明,YARN公平算法能够减少平均处理和排队等待时间,在平均吞吐量、平均队列长度和平均时延上明显优于公平算法.     

IaaS环境下多租户安全资源分配算法和安全服务调度框架

针对基础设施即服务（IaaS）环境下多租户使用安全服务时由于安全资源有限和安全资源分配不均导致的效率低下问题,提出了一个租户安全资源调度框架。首先以最小最大公平算法为基础,结合Fair Scheduler的调度思想为租户设定了最小共享量和资源需求量属性;然后通过安全服务资源分配算法在保证租户最小共享量满足的前提下,尽可能公平地满足租户的资源需求;最后结合租户内任务调度和租户间资源抢占算法,实现了租户安全服务调度框架。实验结果表明,在随机资源分配条件下,安全服务资源分配算法与传统资源分配算法相比在资源利用率和作业效率上均有明显提高,安全服务调度框架可以有效解决多租户安全资源的分配和强占问题。     

Hadoop平台下计算模型中调度策略的研究

针对Hadoop平台下默认调度算法FIFO、计算能力调度算法以及公平调度算法在调度过程中遵守严格的队列顺序,导致一些任务被调度到不满足数据本地性节点上的问题,提出一个基于本地性的调度算法——延时调度。该算法在维护公平性原则的同时,当一个被调度的作业无法启动一个本地的任务时,让这个任务等待一小段时间,调度其他作业先执行。实验结果表明,此调度算法缩短了作业平均响应时间,有效增加了集群系统的吞吐量,提高了集群资源利用率。     

基于延迟调度策略的Reduce调度优化算法

在大规模的Hadoop集群中,良好的任务调度策略对提高数据本地性、减小网络传输开销、减少作业执行时间以及提高集群的作业吞吐量都有着重要的影响。本文针对Hadoop架构中Reduce任务的数据本地性较低问题,提出了一种基于延迟调度策略的Reduce任务调度优化算法,通过提高Reduce任务的数据本地性来减少作业执行时间以及提高作业吞吐量,该算法在Hadoop架构的Early Shuffle阶段,使用多级延迟调度策略来提高Reduce任务的数据本地性。最后重写原生公平调度器代码实现了该调度算法,并与原生公平调度器进行了对比实验分析,实验结果表明该算法明显减少了作业执行时间,提高了集群的作业吞吐量。     

Hadoop平台的多队列作业调度优化方法研究

对Hadoop平台的作业调度算法进行了研究, 提出了支持作业类型区分的多队列调度优化算法。优化算法支持根据节点当前的负载情况分配不同类型的作业, 以提高节点的资源利用率; 允许作业队列的资源在闲置时被其他作业队列占用; 在原作业队列需要时可以被即时回收, 即回收过程支持任务抢占; 采用共享队列列表和非共享队列列表的逻辑划分来防止乒乓效应。Hadoop平台的性能测试结果表明, 优化算法相比系统默认算法在作业调度的执行效率、执行平稳性等方面都有了显著的提升。     

Hadoop平台下的动态调度算法

目前,云计算环境具有动态、异构和海量多类型任务并发等特征,随着集群规模不断增大、用户QoS不断增多,现有调度算法越来越难以适应动态变化的环境及满足用户的需求。针对Hadoop平台下现有调度器不能根据作业运行状态和资源使用情况进行动态调整的问题,提出了Hadoop下基于作业分类的动态调度算法。该算法在使用朴素贝叶斯分类算法对队列中作业进行分类的过程中,根据各个作业的类型,预先设定类别权值,将队列中的作业分类,并引入效用函数,根据用户提交时的预期完成时间QoS和作业完成情况估算其作业完成时间,实现动态设置作业优先级。实验表明,使用提出的算法不仅能有效减少 作业的分类时间,而且能明显提高 动态性和用户QoS。     

LTE上行调度中一种补偿公平正比算法

以第三代移动通信系统的长期演进(LTE)标准为背景,针对上行调度中资源分配算法展开研究,分析公平正比(PF,Proportional Fair)调度算法的优缺点,并提出一种补偿公平正比调度算法。该算法可以判断用户当前分配的RB资源的服务质量好坏,对服务质量较差的RB资源进行重新分配。仿真分析表明,本算法可以在系统吞吐量和用户公平性之间取得较好的平衡。     

一种基于动态slot分配的公平调度算法

Hadoop框架中基于缺额的公平调度算法以统一的固定配置设置定时计算和更新作业信息,在一定程度上影响了其作业调度的公平性,同时也不能满足作业的资源需求。针对基于缺额的公平调度算法配置方式的不足,提出一种基于公平性的动态slot分配算法,通过实时计算更新缺额进行slot分配以确保真正的公平性。     

多租户集群中基于服务水平目标的调度机制

针对多租户集群中无法保证作业服务水平目标(SLO)的问题,提出了一种多租户场景下基于SLO的调度机制,其中包括优先调度算法和资源抢占算法。优先调度算法区别考虑超额使用资源的租户和未超额使用资源的租户,赋予后者的作业更高的优先级,在此前提下选择紧急度最高的作业,优先为其分配资源;资源抢占算法在资源受限的情况下,选择紧急度超过阈值的作业实施资源抢占,并根据租户的资源使用情况,在相应的运行作业范围内选择紧急度最低的作业,抢占其资源。实验结果表明,与现有保证公平的多租户调度器Capacity Scheduler相比,该调度机制可以在兼顾作业执行效率和租户间公平的前提下,显著提高作业的截止时间保证率,从而保证业务的服务水平目标。     

基于心跳超时机制的Hadoop实时容错技术

针对官方的Hadoop软件中提供的节点心跳超时容错机制对短作业并不合理,而且忽略了异构集群中各节点超期时间设置的公平性的问题,提出了公平心跳超时容错机制。首先根据每个节点的可靠性及计算性能构建节点故障误判损失模型,提出公平误判损失(FMJL)算法,使其同时满足长作业和短作业要求;接着,设计并实现了基于FMJL算法的公平超时机制。在实现了公平超时机制的Hadoop上运行大约345 s的短作业时,当出现TaskTracker节点故障时作业完成时间平均大约节省了44%,与自适应超时机制相比,作业完成时间大约节省了23%。实验结果表明,公平超时机制在保证不影响长作业完成时间的情况下缩短了短作业的容错处理时间,提高了Hadoop的实时处理效率。     

Guidelines for Selecting Hadoop Schedulers Based on System Heterogeneity

Hadoop has been developed as a solution for performing large-scale data-parallel applications in Cloud computing. A Hadoop system can be described based on three factors: cluster, workload, and user. Each factor is either heterogeneous or homogeneous, which reflects the heterogeneity level of the Hadoop system. This paper studies the effect of heterogeneity in each of these factors on the performance of Hadoop schedulers. Three schedulers which consider different levels of Hadoop heterogeneity are used for the analysis: FIFO, Fair sharing, and COSHH (Classification and Optimization based Scheduler for Heterogeneous Hadoop). Performance issues are introduced for Hadoop schedulers, and experiments are provided to evaluate these issues. The reported results suggest guidelines for selecting an appropriate scheduler for Hadoop systems. Finally, the proposed guidelines are evaluated in different Hadoop systems.     

异构Hadoop环境下的实时作业调度算法

为提升Hadoop集群在异构环境下处理硬实时作业的性能,提出一种基于历史进度自动调整作业优先级的调度算法（HAPS）。该算法实时监控作业进度信息,对作业进度率进行指数平滑预测,计算作业剩余执行时间,动态估算作业空闲时间。并据此实时更新作业队列中作业的优先级顺序,优先调度空闲时间小的作业。实验结果表明,HAPS有效地提高了异构环境下硬实时作业的执行成功率。     

Hadoop平台下基于截止时间限制的动态调度算法的研究

为了满足有截止时间限制的MapReduce作业的需求,提出一种基于截止时间限制的动态调度算法（DCDS）。该算法实时监控作业运行状况,并对作业运行时间进行动态估算,从而确定作业优先级;对于时间紧迫的作业,可通过抢占策略来保证在用户要求的截止时间内完成。实验结果表明,与Hadoop平台现有的调度算法相比,该算法不仅能满足作业截止时间的要求,也提高了系统资源的利用率和吞吐量。     

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

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

基于加速收敛蜂群算法的资源感知调度器

为了能有效处理海量数据,进行关联分析、商业预测等,Hadoop分布式云计算平台应运而生。但随着Hadoop的广泛应用,其作业调度方面的不足也显现出来,现有的多种作业调度器存在参数设置复杂、启动时间长等缺陷。借助于人工蜂群算法的自组织性强、收敛速度快的优势,设计并实现了能实时检测Hadoop内部资源使用情况的资源感知调度器。相比于原有的作业调度器,该调度器具有参数设置少、启动速度快等优势。基准测试结果表明,该调度器在异构集群上,调度资源密集型作业比原有调度器快10%~20%左右。     

Grid Resource Availability Prediction-Based Scheduling and Task Replication

The frequent and volatile unavailability of volunteer-based Grid computing resources challenges Grid schedulers to make effective job placements. The manner in which host resources become unavailable will have different effects on different jobs, depending on their runtime and their ability to be checkpointed or replicated. A multi-state availability model can help improve scheduling performance by capturing the various ways a resource may be available or unavailable to the Grid. This paper uses a multi-state model and analyzes a machine availability trace in terms of that model. Several prediction techniques then forecast resource transitions into the model’s states. We analyze the accuracy of our predictors, which outperform existing approaches. We also propose and study several classes of schedulers that utilize the predictions, and a method for combining scheduling factors. We characterize the inherent tradeoff between job makespan and the number of evictions due to failure, and demonstrate how our schedulers can navigate this tradeoff under various scenarios. Lastly, we propose job replication techniques, which our schedulers utilize to replicate those jobs that are most likely to fail. Our replication strategies outperform others, as measured by improved makespan and fewer redundant operations. In particular, we define a new metric for replication efficiency, and demonstrate that our multi-state availability predictor can provide information that allows our schedulers to be more efficient than others that blindly replicate all jobs or some static percentage of jobs.     

基于累计工作量的在线大数据分析作业调度算法

针对Hadoop和Spark等大数据分析系统中无先验知识任务的高效执行问题，设计了基于累计工作量（CRW）的任务调度器CRWScheduler。该调度器根据CRW将任务在低权重队列与高权重队列间切换；在为作业分配资源时，同时考虑到作业所在的队列和其瞬时占用资源量，无需作业先验知识即显著提升系统性能。基于Apache Hadoop YARN实现了CRWScheduler原型，在28个节点的基准测试集群上的实验表明，与YARN的公平调度机制相比，作业流时间（JFT）平均降低21%，其中95百分位的作业流时间（JFT）最多降低了35%，并且在与任务级调度程序协作时可获得进一步的性能提升。     

Minimizing the Average Completion Time for Concurrent Grid Applications

When multiple grid applications are executed on a common grid computing infrastructure, the policy of resource allocation impacts the time to complete these applications. In this paper, we formulate an analytical model that permits us to compare different allocation policies. We show that a uniform allocation policy penalizes large jobs (i.e., the work required for an application), whereas a linear allocation of resources penalizes small jobs. In particular, we study an allocation policy that aims at minimizing the average job completion time. We show that such policy can reduce the average completion time by as much as 50% of the completion time required for uniform or linear allocation policies. Using such policy is also fair to applications because it does not penalize small jobs or large jobs as other policies (such as uniform or linear) do.