多用户mapreduce集群的作业调度

多用户mapreduce集群的作业调度一、简介HadoopMapReduce和它的开源实现最初优化大型批作业如web索引结构。然而,另一个用例近期显现:在多个用户之间共享一个MapReduce集群,它运行的长批处理作业、短交互式查询共享一个公共数据集。使统计复用,相比于为每组构建私有集群成本更低。分享一个集群也会导致数据整合(主机托管不同的数据集)。这避免了昂贵的跨私有集群复制的数据,并允许一个组织在不相交的查询数据集高效地运行。我们的工作最初是出于MapReduce工作负载在Facebook,主要的网络目的地运行Hadoop数据仓库。事件日志从Facebook的网站被导入到Hadoop集群每小时,在那里他们被用于各种各样的应用程序,包括分析使用模式来改进网站设计、检测垃圾邮件,数据挖掘和广告优化。仓库600台机器上运行,存储500TB的压缩数据,这是每天2TB速度增长。除了“生产”工作,必须定期运行,有很多实验工作,从几个小时机器学习几天计算到1-2分钟即席查询提交通过SQL接口Hadoop称为蜂房[3]。当Facebook开始建造数据仓库,它发现提供数据整合共享集群大有益处。例如,一位工程师在垃圾邮件检测时可以在任意数据源寻找规律,比如朋友列表和广告点击,来识别垃圾邮件发送者。然而,当足够的组织开始使用Hadoop,工作响应时间开始遭受Hadoop的FIFO调度程序影响。这对生产工作来说不可接受而且使交互式查询成为可能,大大减少了系统的效率。一些组织在Facebook考虑建造私有集群为自己的工作负载,但为许多应用程序调整太昂贵。为了解决这个问题,我们设计和实现了一个Hadoop公平调度器。我们的调度器给每个用户拥有一个私人的Hadoop集群的假象,让用户在几秒内开始工作和运行交互式查询,同时利用底层共享集群效率。在开发过程中,我们发现了几个在MapReduce设置调度挑战我们的地址。我们发现,现有的调度算法可以在MapReduce表现很差,有辱人格的吞吐量和响应时间的因素2-10,由于设置的两个方面:数据本地化(附近的需要运行计算数据)和map和reduce任务之间相互依存。我们开发了两个简单的、健壮的算法来克服这些问题:延迟调度和copy-compute分裂。提高我们的技术提供2-10x的吞吐量和响应时间在一个多用户的工作量,但也可以在单用户增加吞吐量,FIFO工作负载的2倍。虽然我们现在我们的结果在MapReduce设置,他们推广到任何基于数据流的集群计算系统,像dryad[20]。我们地址的位置和相互依存关系问题是大规模的方式来表述数据并行处理的计算。有两个方面,区分调度在MapReduce从传统的集群调度[12]。第一个方面是需要数据本地化,即。,将任务节点包含输入数据。本地网络对分带宽性能是至关重要的,因为在一个大集群远低于总带宽的磁盘机[16]。传统的集群调度程序,给每个用户一组固定的机器,如扭矩[12],显著降低性能,因为在Hadoop文件分布在所有节点在GFS[19]。电网调度程序像秃鹫[22]支持位置约束,但只有在地理网站,不是机器,因为他们像MapReduce运行cpu密集型应用程序,而不是数据密集型工作负载。即使有粒状公平调度器,我们发现位置在两种情况:并发工作和小的工作。我们通过一种称为延迟调度的技术解决这一问题,可以双吞吐量。MapReduce导致问题的第二个方面是map和reduce任务之间的依赖:减少任务不能完成,直到所有地图任务在完成他们的工作。这种相互依存,没有出现在传统的集群调度模型,可导致未充分利用和饥饿:长期工作,获得减少槽在许多机器不会释放他们,直到其映射阶段完成,饥饿的其他工作,而未充分使用预留槽。我们提出一个简单的称为copycompute分割的技术为解决这一问题,主要在2-10x增加吞吐量和响应时间。减少/地图的依赖还创建了其他动力学没有出现在其他设置:例如,即使行为端正的工作,公平分享MapReduce,它需要更长的时间比FIFO完成一批工作;这不是真正的环境中,比如包调度,公平共享保护工作。另一个问题是,不能删除映射阶段产生的中间结果,直到工作结束,消耗磁盘空间。我们在第七节探索这些问题。虽然我们激励我们的工作与Facebook的案例研究,我们解决的问题绝不是限制到一个数据仓库的工作量。我们接触的另一个主要网络公司使用Hadoop确认关于研究集群的最大抱怨用户有漫长的排队延迟。我们的工作也是相关的几个学术Hadoop集群已经宣布。这样一个集群已经使用我们的公平调度器2000节点上。一般来说,有效的调度是更重要的比其他设置,因为在集群数据密集型计算资源共享(集群)是非常昂贵的,因为数据是很难(所以数据整合提供了重要的价值)。本文的其余部分组织如下。第二节提供了背景HadoopHadoop与先前的调度和问题解决方案,包括Torquebased调度器。第三节介绍我们的公平调度器。第四节描述数据局部性问题和延迟调度技术来解决这些问题。第五节描述问题引起的减少/地图相互依存和copy-compute分裂可以减轻他们的技术。我们评估算法在第六节。第七节讨论调度权衡在MapReduce和通用课程集群作业调度的编程系统。我们调查相关工作节8和9节结束。二、背景Hadoop的MapReduce实现类似于Google[16]。Hadoop分布式文件系统上运行,HDFS,商店三副本的每一块像GFS[19]。用户提交作业组成的地图功能,减少功能。Hadoop每个工作分解成多个任务。首先,地图任务处理每个块的输入(通常为64MB),产生中间结果,键值对。这些是保存到磁盘。接下来,减少中间结果的获取任务列表与每个键和关联运行它通过用户的减少功能,产生输出。每个减速器负责不同的密钥空间的一部分。图1演示了一个MapReduce计算。在Hadoop作业调度是由一个主节点执行,其分配从节点的工作。任务被分配去回应收到奴隶每隔几秒从从节点收到的心跳(状态信息)。每个从节点都有固定数量的map插槽和reduce槽。通常,Hadoop任务是单线程的,因此每个核心有一个插槽。虽然有时未充分使用的资源(例如，当没有reduce运行),它使管理内存和CPU的从节点容易。例如,reduce往往比map使用更多的内存,所以限制reduce数量非常有用。Hadoop正朝着更动态负载管理从节点,如考虑到任务的内存需求[5]。在本文中,我们专注于从节点以上调度问题。我们确定的问题和我们的技术开发独立于从节点负载管理机制。过去的Hadoop调度方案Hadoop的内置在FIFO调度运行工作秩序,有5个优先级级别。当任务槽变得自由,通过工作的优先级和调度程序扫描提交任务的时间找到一个所需的类型1。地图,一个地方调度器使用优化在谷歌的MapReduce[16]:在选择一份工作,调度程序选择地图任务的工作数据最接近从节点(奴隶同一节点如果可能,否则在同一机架上,或远程机架上的最后)。最后,Hadoop使用备份任务减轻缓慢节点在[16],但备份调度正交我们研究的问题。FIFO调度机制的缺点是短工作在大工作面前响应时间过长。这个问题在Hadoop首先解决方案是HOD，,规定私人MapReduce集群在大量物理集群上使用[12]Torque。HOD让用户共享一个公共文件系统(运行在所有节点),而拥有私人MapReduce集群节点分配。然而,HOD有两个问题:PoorLocalityPoorUtilization三、公平调度器公平调度器针对插槽级粒度的Hadoop提出，有两个目的：隔离性：给每个用户（工作）一个拥有私有集群的假象统计多路复用：重新分配某些用户（工作）的闲置容量给其他用户（工作）FAIR使用两级层次。在顶层,FAIR分配任务槽在“池”,和第二层次,每个池分配其插槽在多个工作池中。图2显示了一个示例的层次结构。在我们的设计和实现我们使用两个水平层次,FAIR可以很容易地推广到更多的水平。FAIR使用的一个版本max-min与最低保证分配FAIR[8]在池槽。每个池我给出一个最低份额mi(槽数),可以是零。调度器可以确保每个池将收到的最低份额,只要它有足够的需求,这是最低的股票池不超过系统容量。池时没有使用完整的最低份额,其他池允许使用它的插槽。在实践中,我们创建一个每个用户池和特殊池生产工作。这给用户(池)性能至少一样好,他们将在一个私人的Hadoop集群大小相等的最低份额,但往往由于统计复用高。公平使用相同的调度算法来分配槽在同一池工作中,虽然其他调度学科,如FIFO和多级排队,可以使用。Slot分配算法图3显示了一个例子,我们分配100槽四池与下列最低股价mi和要求di:(m1=50,d1=46),(m1=10,d1=18),(d1m1=25日=28),(m4=15,d4=16)。我们假设每个池是一桶,这代表了池的大小的需求。每一桶也有一个标志代表最小份额。如果池的最小份额大于其需求,桶没有标记。减少分配把水倒进水桶,水的总量是系统中槽的数量。公平经营三个阶段。在第一阶段,它让每个无名桶,即每个桶,它满足需求的最低份额大于其需求。在第二阶段,它填补了所有剩余桶标志。这一步,隔离属性执行每个桶已收到的最低份额,或其需求满足。在第三阶段,公平实现统计复用,剩下的水均匀投入空桶,从最低的桶水和继续,直到所有的桶都装满水或耗尽。最后的股票池,池是46的14池2,25池3和15池4,这是尽可能公平,同时满足最低担保。Slot再分配如上所述,在任何时候、公平目标分配整个集群池中有工作能力。一个关键的问题是如何重新分配槽当需求变化。考虑一个系统100插槽和两个池使用50插槽。当第三个池变得活跃,认为公平需要重新分配槽,这样每个池大约33个插槽。有三种方法可以免费时段为新工作:(1)杀死其他池的任务工作,(2)等待任务完成,或(3)抢占任务(以及以后的简历)。杀死一个任务允许公平立即重新分配槽,但浪费执行的工作任务。相比之下,等待任务完成延迟槽重新分配。任务抢占可以立即重新分配,避免浪费工作,但实现起来也很复杂,因为Hadoop任务运行任意用户代码。公平使用的组合方法(1)和(2)。新工作开始时,公平分配槽开始其他工作任务完成。由于MapReduce任务通常短(15-30为减少地图和几分钟),一份工作将实现其公平份额(如计算公平)相当快。例如,如果任务一分钟长,然后每一分钟,我们可以重新分配集群中的每一个槽。此外,如果新工作只需要10%的插槽,这样可以使他们平均在6秒。这使得发射延迟在我们共享集群与延迟私有集群。然而,在可以的情况下任务会长时间运行,由于缺陷或由于不可平行计算。确保每一个工作都有其份额在这些情况下,公平使用了两个超时,一个用于保证的最低份额(Tmin),和另一个保证公平份额(Tf空气),TminTf空气的地方。如果一个新开始的工作得不到最低份额Tmin到期之前,公平杀死其他池的任务,重分配给这个工作。然后,如果工作没有实现其公平份额的Tf空气,公平的杀死更多的任务。在选择任务杀死,我们选择最近发射的任务在已安排的工作中，以减少浪费计算,和我们从不把工作低于其公平份额。Hadoop工作容忍失败的任务,因此死亡的任务是作为如果它从未开始。而杀戮任务降低吞吐量,它让我们满足我们的目标是让每个用户私有集群的错觉。用户隔离超过损失的吞吐量。Fairsharing的障碍部署一个初始版本的公平之后,我们发现两个方面产生负面影响的MapReduce的性能(特别是吞吐量)公平。因为这些方面并没有出现在我们详细讨论它们的tradiotionalHPC调度:•数据局部性:MapReduce实现效率的节点上运行的任务,包含他们的输入数据,但是我们发现严格实施公平的分享可以打破地区。这个问题也发生在其他调度规程,严格实现包括FIFOHadoop的默认调度器。•减少/地图相互依存:因为减少任务必须等待他们的工作完成才能完成的地图,他们可能占领槽很长一段时间,饥饿的其它工作。这也导致未充分利用的插槽,如果等待减少几乎没有数据复制。四、