论文部分内容阅读
在以搜索引擎与社交网络为代表的互联网应用为我们带来大规模数据资源的今天，MapReduce系统作为一个同时具有高效性、便捷性、容错性等特点的分布式计算系统，越来越广泛地被应用在日志分析、数据仓库、数据挖掘、科学计算等各个领域。基于作业组的MapReduce应用是一类非常重要并且广泛出现的MapReduce系统应用，它包含多个或者多轮作业，这些作业串行或者并行执行，彼此之间具有一定的依赖关系，构成了一个有向图结构。典型的基于作业组的MapReduce应用主要包括迭代作业和有向无环图关联作业两类。常见的PageRank算法就是前者的典型代表;而在Pig、 Hive等基于MapReduce系统的数据库元语言及数据仓库中，绝大多数数据库处理脚本都可以解析成有向无环图关联的作业组形式进行调度与执行。 作业组执行时间的长短取决于系统的利用率以及最长执行路径（即关键路径）的执行效率，因此单个作业的执行效率和整个作业组的调度策略都会影响一个作业组总的执行时间。现有的MapReduce系统处理基于作业组的应用时存在诸多问题:在存在数据倾斜或者异构环境的情况下，现有系统对于实现Reduce负载均衡存在较大问题，使得单个作业影响整个系统的执行时间与并行度，同时使得调度程序无法准确预测作业的执行时间;在全局作业调度的时候，现有系统无法利用作业组中作业之间的依赖关系图进行调度，因此有可能导致系统利用率相对较低。 本文从作业内负载均衡和作业间并行调度两个方面，提出了LIBRA和PISCES两套优化系统，并且将其在Hadoop1.0.0开源系统中进行了实现。 LIBRA系统旨在解决MapReduce中单个作业的动态采样及均匀划分问题。它在部分Map任务执行过程中动态采样，并且将样本传输至Master节点，再由Master节点根据收集的信息对Map任务输出的中间数据分布进行估测，计算区间划分，以此决定每一个Reduce任务所计算的键值区间，使其负载尽可能均匀。 PISCES是一个基于作业间依赖关系的调度系统。它实现了动态添加维护作业组依赖关系的编程接口，并根据当前依赖关系下发合适的作业进行执行，旨在从全局的角度提高整个作业组的执行效率。另外PISCES系统还通过将上游任务的Reduce阶段与下游任务的Map阶段并行化，使得合理调度的基础上进一步提高系统并行度，缩减整个作业组的执行时间。 我们通过一系列常见的MapReduce应用，包括排序应用、倒排索引、PageRank、包含Join和Group等操作的Pig脚本等，对LIBRA系统和PISCES系统相关指标进行了实验测试。实验证明，LIBRA系统对于存在数据倾斜的环境下，可以将单个MapReduce作业的执行时间缩短最高4倍;在不存在数据倾斜的异构环境中，也可以将单个作业总的执行时间缩短最高2倍。PISCES系统通过多级作业的并行化和作业调度，在处理作业组形式的应用时提高最高38％的系统并行度，并提高了最高42％的作业组执行总效率。