多MapReduce作业协同下的大数据挖掘类算法资源效率优化

由于任意的MapReduce作业都需要独立地进行任务调度、资源分配等一系列复杂的操作,这使得同一算法协同的多个MapReduce作业之间,存在着大量的冗余磁盘I/O及资源重复申请操作,导致计算过程中资源利用效率低下。大数据挖掘类算法通常被切分成多个MapReduce job协作完成。以ItemBased算法为例,对多MapReduce作业协同下的大数据挖掘算法存在的资源效率问题进行了分析,提出基于DistributedCache的ItemBased算法,利用DistributedCache将多个MapReduce job之间的I/O数据进行缓存处理,打破作业之间独立性的缺陷,减少map与reduce任务之间的等待时延。实验结果表明,DistributedCache能够提高MapReduce作业的数据读取速度,利用DistributedCache重构后的算法极大地减少了map与reduce任务之间的等待时延,资源效率提高3倍以上。     

基于MapReduce的连续概率Skyline查询

大数据对传统的Skyline研究产生了挑战,利用并行框架MapReduce计算大数据下的Skyline已成为一个研究热点。研究了不确定移动对象的Skyline查询问题,提出了一种MapReduce框架下基于事件跟踪的连续概率Skyline查询算法——MR-DTrack(domination-track algorithm based on MapReduce)。首先采用基于角度的划分方法保证负载均衡,通过预计算获取Skyline集可能变化的时刻,在Reduce阶段获取候选概率Skyline集;然后利用局部过滤点剪枝,减少计算开销;最后合并计算出全局概率Skyline集。在人工数据集和真实数据集上的实验验证了算法的有效性。     

求解多维背包问题的MapReduce蚁群优化算法

应用MapReduce编程模式实现蚁群优化算法的并行化计算,提出基于MapReduce的改进背包问题蚁群算法.通过改进概率计算时机、轮盘赌、交叉、变异等技术,降低蚁群算法的计算复杂度.在云计算环境中应用该算法分布式并行地求解大规模多维背包问题,仿真实验结果表明,该算法能改善蚁群算法搜索时间长的缺陷,增强对大规模问题的处理能力.     

基于MapReduce检测僵尸网络的贝叶斯算法的实现

利用贝叶斯算法检测僵尸网络具有较高的准确性,但僵尸网络具有流量大的特征,同时贝叶斯分类训练阶段需要对大量的网络数据集进行训练,用单一结点来检测僵尸网络将会遇到计算时间和计算资源瓶颈。为此设计了基于MapReduce检测僵尸网络的贝叶斯算法,把贝叶斯算法训练阶段的先验概率、条件概率和检测阶段的后验概率的计算并行化处理。通过大量运行在Hadoop平台上的实验表明,该方法提高了检测僵尸网络的效率。     

大数据环境下基于概率矩阵分解的个性化推荐

概率矩阵分解是近几年广泛应用的协同过滤推荐方法。针对如何利用矩阵分解技术提高推荐质量以及在大数据环境下如何突破计算时间、计算资源瓶颈等问题进行研究,提出了Improved Probabilistic Matrix Factorization(IPMF)融入邻居信息的概率矩阵分解算法,并且提出了parallel-IPMF (p-IPMF)算法来解决融入邻居信息后计算复杂度高和难以并行化等问题。 在MapReduce并行计算框架下将p-IPMF算法加以实现,并在真实数据集上进行验证。实验结果表明,所提算法能有效提高推荐质量并缩短计算时间。     

基于Spark的ItemBased推荐算法性能优化

MapReduce计算场景下,复杂的大数据挖掘类算法通常需要多个MapReduce作业协作完成,但多个作业之间严重的冗余磁盘读写及重复的资源申请操作,使得算法的性能严重降低。为提高ItemBased推荐算法的计算效率,首先对MapReduce平台下ItemBased协同过滤算法存在的性能问题进行了分析;在此基础上利用Spark迭代计算及内存计算上的优势提高算法的执行效率,并实现了基于Spark平台的ItemBased推荐算法。实验结果表明：当集群节点规模分别为10与20时,算法在Spark中的运行时间分别只有MapReduce中的25.6%及30.8%,Spark平台下的算法相比MapReduce平台,执行效率整体提高3倍以上。     

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

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

F1owS:一种MapReduce数据流公平调度方法

MapReduce Job的调度机制一直是学术研究的热点。在分析MapReduce数据流调度模型的基础上,提出一种面向MapReduce数据流的公平调度方法FlowS。该方法采用数据流池来分配资源以保证MapReduce数据流的隔离性,并且采用数据流池动态构建算法来确保资源的公平分配。实验表明,该调度方法可以有效提高Hadoop集群对MapReduce数据流的处理效率。     

故障诊断算法在MapReduce中的优化实现

针对故障诊断算法特点,给出了MapReduce框架实现故障诊断算法的基本方法。通过对故障诊断算法和MapReduce运算框架的分析,得出诊断算法MapReduce化的基本方法和思路。在算法研究的基础上,针对非迭代诊断算法,采用传统MapReduce框架实现。针对迭代诊断算法,采用添加了传送模块的迭代式MapReduce框架实现。分别以最近邻法和模糊C均值聚类算法为例,给出非迭代和迭代诊断算法MapReduce化的具体实现。实验结果表明,本文所提基本方法可以运用在故障诊断算法中,为诊断算法MapReduce化提供依据,将MapReduce运用到故障诊断算法中可以有效提升故障诊断效率。     

基于排队网络的多优先级MapReduce作业调度算法

MapReduce是一个能够对大规模数据进行分布式处理的框架,目前被各个领域广泛应用。在提供MapReduce服务的集群中,如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战。针对这一问题,提出了一个基于排队网络的多优先级作业调度算法（MPSA）。首先分析和归纳了基于MapReduce模型的算法,提出了三种常见模式,采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求;随后使用AR(1)模型进行预测,使算法可以动态地适应不同的用户访问量;利用二分查找算法,分步计算出不同优先级在map阶段和reduce阶段分配的槽位数;最后实现了在MapReduce模型中应用的实时调度算法。实验结果表明,与传统的FIFO和公平调度算法相比,本文提出的算法在用户到达率和任务规模变化的情况下,可以更加有效地满足不同优先级用户的截止时间限定。     

SLA-aware energy-efficient scheduling scheme for Hadoop YARN

Apache Hadoop becomes ubiquitous for cloud computing which provides resources as services for multi-tenant applications. YARN (a.k.a. MapReduce 2.0) is one of the key features in the second-generation Hadoop, which provides resource management and scheduling for large-scale MapReduce environments. Two enormous challenges in the YARN scheduler are the abilities to automatically tailor and control resource allocations to different jobs for achieving their Service Level Agreements (SLAs), and minimize energy consumption of the overall cloud computing system. In this work, we propose an SLA-aware energy-efficient scheduling scheme which allocates appropriate amount of resources to MapReduce applications with YARN architecture. In our task scheduling policy, We consider the data locality information to save the MapReduce network traffic. Furthermore, the slack time between the actual execution time of completed tasks and expected completion time of the application is utilized to improve the energy-efficiency of the system. An online userspace governor-based dynamic voltage and frequency scaling (DVFS) scheme is designed in the YARN per-application ApplicationMaster to dynamically change the CPU frequency for upcoming tasks given the slack time from previous completed tasks. Experimental evaluation shows that our proposed scheme outperforms the existing MapReduce scheduling policies in terms of both resource ultization and energy-efficiency.     

MapReduce delay scheduling with deadline constraint

MapReduce programming paradigm has been widely applied to solve large‐scale data‐intensive problems. Intensive studies of MapReduce scheduling have been carried out to improve MapReduce system performance. Delay scheduling is a common way to achieve high data locality and system performance. However, inappropriate delays can lead to low system throughput and potentially break the original job priority constraints. This paper proposes a deadline‐enabled delay (DLD) scheduling algorithm that optimizes job delay decisions according to real‐time resource availability and resource competition, while still meets job deadline constraints. Experimental results illustrate that the resource availability estimation method of DLD is accurate (92%). Compared with other approaches, DLD reduces job turnaround time by 22% in average while keeping a high locality rate (88%).Copyright © 2013 John Wiley & Sons, Ltd.     

基于成本的MapReduce工作流优化器

对MapReduce栈的不同层进行优化有各自的优缺点。针对MapReduce工作负载的优化问题,提出了相关概念;通过与RoT的对比,介绍了MapReduce工作基于成本的优化及所使用的相关技术,并对MapReduce基于成本的优化进行了评估;基于工作流中的数据流依赖和资源依赖关系,提出了三种工作流优化器,评估了基于成本的工作流优化,并对工作流优化器进行了终端-对-终端的评估;通过实验评估了工作流优化器的优化开销并对这三种工作流优化器的优缺点进行了对比分析。     

用于Hadoop2.x的MapReduce性能评估模型

基于MapReduce的程序被越来越多地应用于大型数据分析的应用中.Apache Hadoop是最常用的开源MapReduce模型之一.程序运行时间的缩短对于MapReduce程序以及所有数据处理应用而言至关重要,而能够准确估算MapReduce程序的执行时间是优化程序的重要环节.本文定义了一个在Hadoop2.x版本...     

基于机器学习的MapReduce资源调度算法

针对MapReduce中允许map和shuffle阶段重叠的优化模型需要自适应性的问题,提出了基于此模型的机器学习的资源调度算法,利用贝叶斯分类器依据作业对系统资源的需求和系统环境的匹配程度对作业进行调度,并不断更新分类器,使其具有自适应性,考虑了map和shuffle的重叠阶段。通过模拟实验验证,改进后的算法能够提高MapReduce系统的性能,获得更好的平均响应时间。     

一种异构环境下的基于MapReduce任务调度改进机制

针对在异构环境下采用现有MapReduce任务调度机制可能出现各计算节点间数据迁移和系统资源分配难以管理的问题, 提出一种动态的任务调度机制来改善这些问题。该机制先根据节点的计算能力按比例放置数据, 然后通过资源预测方法估计异构环境下MapReduce任务的完成时间, 并根据完成时间计算任务所需的资源。实验结果表明, 该机制提高了异构环境下任务的数据本地性比例, 且能动态地调整资源分配, 以保证任务在规定时间内完成, 是一种有效可行的任务调度机制。