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