《外文翻译云计算中倾斜度感知的任务调度课案》由会员分享，可在线阅读，更多相关《外文翻译云计算中倾斜度感知的任务调度课案（10页珍藏版）》请在金锄头文库上搜索。
1、2013Skew-Aware Task Scheduling in Clouds云计算中倾斜度感知的任务调度李东生，陈宜兴，理查德胡亥国防科技大学，计算机学院，并行与分布式处理国家实验室，中国国立大学莱佛士商学院，新加坡摘要：数据扭曲是MapReduce一样的云系统中慢任务出现的一个重要原因。在本文中，我们提出了一个斜感知任务调度（SATS）机制针对MapReduce类似系统的迭代应用。该机构利用迭代应用中在相邻迭代的数据分布的相似性，来减少数据扭曲造成的落伍的问题。它在当前迭代的任务的执行过程中收集数据的分布信息，并用这些信息来指导下一次迭代时任务的数据分割。我们在HaLoop系统落实机制，
2、在一个集群中部署。实验结果表明，该机制可以处理数据扭曲，有效地提高负载平衡。关键词：数据扭曲；任务调度；云计算；负载均衡1、 简介近年来云计算已经成为一个有前途的技术，而且MapReduce是最成功的一个大规模数据密集型云计算的实现平台1 - 3。MapReduce的使用一个简单的数据并行的编程模型，有两个基本的操作，即，Map和Reduce操作。用户可以根据应用程序的要求自定义Map功能和Reduce功能。每个map任务取一片输入数据，并产生一个用Map功能的key/value对的集合，这是初步地用Reduce功能做Reduce任务。这种编程模型很简单，但功能强大，许多大规模数据处理应用程序
3、可以由模型来表示。类MapReduce的系统可以在云计算中自动调度多个分布在机器中的Map和/或Reduce任务。作为同步步骤仅存在于Map阶段和Reduce阶段之间，任务执行在相同的阶段具有高平行度，并且因此并发性和系统的可扩展性可以被高度增强。 Hadoop4和它的变体（例如，HaLoop 5和Hadoop+ 6）是典型的类MapReduce系统。由于在类MapReduce系统中Map和Reduce阶段之间存在同步步骤，在任一阶段慢任务可能减慢整个工作的执行。这种慢任务在Map或Reduce阶段叫做落后者。当慢任务出来时，整个工作的执行时间会增加，而资源的使用会被减少。最近，有研究7-8显
4、示该数据歪斜已经成为了在Map或Reduce阶段出现慢任务的一个主要原因。在许多科学计算和数据分析应用中，输入的数据或中间数据的数据倾斜可能会导致严重的负载不平衡的问题。例如，PageRank 9用于大规模搜索工程是一种典型的执行在类MapReduce系统上的应用。该PageRank应用进行链接分析通过反复迭代其周边邻居的权重，为在网页的链接图中的每个顶点/网页分配权重（等级）。研究7，8，18表明网页链接图的度是多倾斜的，一些顶点具有较大度的入边。由于MapReducelike系统4使用随机哈希算法进行分区中间数据到Reduce节点，节点代表着计算度较大的节点的权重的任务可能需要更多的时间来
5、完成他们的任务，从而成为该系统的慢任务。而数据歪斜引起落伍问题已成为类似MapReduce的系统中一个重要研究课题。在本文中，我们针对类似MapReduce的系统提出了一个倾斜度感知任务调度（SATS）机制。该SATS机制是基于观察到许多在类似MapReduce的系统中的应用是迭代计算5，如PageRank9，机器学习应用程序，递归关系查询和社会网络分析。在迭代应用程序中，数据被迭代处理，直到计算满足收敛或停止状态，并在计算时每个迭代可以是一个或多个MapReduce工作。数据在两个相邻的迭代之间可能有相似性，并且在相邻迭代的作业中的数据分布可能是相似的。如果数据的分布在一个MapReduce
6、工作执行前能被获得，我们可以正确地划分数据到系统中的节点，以改善负载平衡。基于这样的思想，SATS机制被设计成利用相邻迭代中的数据分布的相似性，以减少数据扭曲造成的落伍问题。它收集在当前迭代的任务执行期间数据分布的信息，并使用该信息，引导下一个迭代时该数据的分布。由于数据偏移通常发生在MapReduce工作中的Reduce阶段，SATS机制重点在MapReduce工作中的Reduce阶段的落后者问题。本文的主要贡献如下所示。首先，我们设计了一个倾斜感知任务调度机制，称作SATS，以处理在MapReduce类似系统中的迭代应用因数据倾斜造成的落后者问题。其次，我们实施SATS机制，建立基于HaL
7、oop5的原型，一个开源的MapReducelike系统。最后，我们进行补偿实验来评估SATS机制，实验结果表明，这SATS可以有效地改善负载平衡。本文的其余部分安排如下。第2节讨论了相关工作。第3节示出了设计和实施SATS机制。第4节通过实验评估该机制。第5节介绍的结论和未来的工作。2、 相关工作A.MapReduce类似的系统MapReduce1是一种流行的针对数据密集型云计算系统的数据并行编程模型，由谷歌提出。Hadoop4开源实现MapReduce模型，其中包括若干个子项目，如普通Hadoop和HDFS3-4。使用MapReduce模型的云计算系统通常被称为MapReduce的类似系统
8、。MapReduce的类似系统将集群中所有节点划分进入Master（即JobTracker）和Slave（即TaskTracker），而且只有一个Master，很多个Slaves。Master处理某些全球性的工作，如作业和任务调度，Slaves进行Master分配的工作，包括Map工作和Reduce工作。当一个Map工作完成时，拥有相同key的中间key/value对根据数据分配方案将被分配到一个分区。在当前版本的Hadoop中4，分区的数量和Reduce节点的数量是相同的，并且每个Reduce节点处理来自所有被分配的Map节点的一个分区中的key/value对。在本文提出的SATS机制可以修
9、改数据分配方案，以处理数据倾斜所造成的落后者问题。HaLoop5是针对迭代应用的Hadoop修改后的版本，如科学计算和数据分析应用。 HaLoop使用三个缓存，即Reducer输入缓存，Reducer输出缓存和Mapper输入缓存以提高性能。Reducer输入缓存设计为存储Map任务的输出，提供数据供下一次迭代。Reducer输出缓存被设置为使所述固定点的计算变得更加容易。Mapper输入缓存是用于Map任务的数据本地性。通过使用循环感知任务调度和输入/输出缓存，HaLoop可以显著减少迭代应用的执行时间。提出的SATS机制在HaLoop系统中实现，并且其利用了任务在相邻迭代中的中间数据的相似
10、性以提高Reducer节点的负载均衡。B.MapReduce类似系统的调度调度是MapReducelike系统一个重要的研究课题。在Hadoop中有几个默认的作业调度机制，例如，FIFO，计算能力调度，公平调度10。由于Hadoop的调度可能会在异构环境中导致严重的负载不均衡和性能下降，LongestApproxi-mateTimetoEnd（LATE）调度11的设计通过修改推测执行策略处理了在异构集群中的落后者问题，它可以减少Hadoop一半的响应时间。Ganesh Ananthanarayanan等人12对于落后者的问题将原因划分为三类，包括具有不同的容量和可靠性的设备特性，任务间具有不同
11、带宽、拥堵和工作量的网络特性（例如，数据扭曲造成的失衡）。他们提出Mantri12，一种监视任务和使用进程和资源感知技术精选落后者的机制，包括重启慢任务，任务的网络意识安置和保护有价值任务的输出。具有实时进度报告，Mantri在其时间周期的早期检测落后者，并根据他们的原因采取适当的行动。数据倾斜是在MapReduce类似系统中执行的许多应用中的一个普遍现象7-8，13-15。YongChul Kwon等人7提出科学分析应用即提取从数据集显示出的显著计算倾斜的特征。 Jimmy Lin8观察发生在许多MapReduce工作中的落后者问题，提出它与数据集的数据偏移是相关的。SkewReduce 7
12、根据用户定义的成本函数静态优化数据的分配，但它取决于来自用户的领域知识并被限制为特定的应用程序。SkewTune 13是一个针对用户定义的MapReduce程序的自动倾斜缓解机制。当一个节点变为空闲时，SkewTune标记任务最大的预期剩余处理时间，主动地重新分配掉队的任务中未处理的输入数据。LEEN 14基于成本模型安排keys到reduce任务中，而TopCluster 15构建了所有reduce 的keys的直方图来鉴定倾斜的reduce keys。总体而言，上述的方法是对提出的SATS机制互补的，这是第一个利用在迭代应用中相邻迭代的数据相似性来处理数据倾斜，提高MapReduce类似系
13、统的负载均衡。3、SATS设计A.机制概述该SATS机制是一个运行时负载均衡的机制，以减少迭代应用程序中数据倾斜所造成的落后者的概率。在MapReduce框架的Reduce阶段，每个Reducer节点处理一些key/value对，所以数据倾斜问题是不平衡的key分配的问题，即，有些keys比其他的有更多对应的key/value对。另外，具有相同key的key/value对将在相同的Reduce节点被处理。因而SATS机制的基本单位是具有相同的key的key/value对。在迭代应用中，在两个相邻迭代间的输入数据往往存在着一定的相似性，并且中间数据也可能有类似的关于key/value对的数据分布
14、。举例来说，在PageRank应用的所有迭代中，图形数据集是相同的，只有顶点的权重变化。顶点分布的程度在数据集中是永远不会改变，并且输入数据和MapReduce作业的中间数据的数据分布是几乎是相同的。因此，中间数据关于从当前迭代的作业中提取出key/value对的分布信息可以被用来预测在下一次迭代时的数据分配。基于这样的思想，在SATS机制是设计成利用在相邻迭代的数据分布的相似性来减轻由数据倾斜造成的落后者问题同时增强了负载平衡。该SATS机制收集当前迭代中在作业执行期间由Map任务产生的中间key/value对数据的分布信息，并利用该信息来指导下一次迭代的数据分配以提高Reduce节点的负载
15、均衡。MapReduce类似系统中SATS机制的组成部分如图1所示，Map，Reduce和JobTracker是MapReduce类似系统的通用组件。图1.MapReduce类似系统中SATS机制的组成部分SATS机制由三个模块实现：收集器模块，控制器模块，平衡器模块。在MapReduce类似系统中，每个Map或Reduce任务被分配的节点中有一个的TaskTracker工作。收集器模块与Reduce任务中的TaskTracker运行，并收集在MapReduce作业的中间key/value对数据的分布信息。每个收集器模块传送上述数据分配信息聚集到平衡器模块。平衡器模块在MapReduce类似系
16、统的JobTracker子系统中工作，收集所有来自分布式收集器的数据分布信息，并计算中间key/value对的全局分布，然后确定一个数据分配方案用于下一个迭代的作业来处理数据倾斜，提高Reducer节点的负载平衡。平衡器模块采用HLF算法计算出的数据分配方案，稍后在C部分描述。平衡器模块确定数据分配方案后，它通知分布在控制器模块的TaskTracker，它会在下一个迭代的方案中执行Map任务。当下一迭代的Map任务产生中间key/value对，它们将根据分配方案分割key/value对，而不是默认的Hadoop/ HaLoop 中的HashPartitioner方案，然后将它们洗牌到Reducer节点相应地处理该数据倾斜并提高Reducer节点的负载均衡。我们在H
