Validated Models of MapReduce Scaling

VaMoS项目的目标是弥合面向系统的研究与并行系统的理论工作之间的差距，以创建反映真实的系统性能及其缩放行为的模型。本文报告了该项目的第一阶段，并提出了一个扩展项目的工作计划，该计划建立在过去几年该领域的成功和发展的基础上。在VaMoS项目的第一阶段，我们在并行系统上进行了广泛的实验性工作。我们研究了作业局部性的影响，分析了来自真实的集群的痕迹，从理论和实验上研究了更精细的任务粒度的性能优势和权衡，并进行了实验，并为具有障碍的并行系统开发了模型，这是并行化机器学习工作负载时经常需要的。这项工作涉及的实施或扩展的几个软件包，我们已经公开发布。我们建议的项目扩展主要集中在并行系统的障碍。典型地，这意味着作业被划分为任务，这些任务将由一组工作者并行地服务，但是这些任务被限制为同时开始，并且可能同时完成。还可以存在中间同步点。这种类型的约束在机器学习工作负载中很常见，并且最近已经将对屏障执行模式的支持添加到一些map-reduce引擎中，以支持这些类型的工作负载。这些屏障约束具有重要的性能影响，因为它们可以迫使工作者闲置，等待一个长时间运行的任务完成。在该项目的第一阶段，我们为这些类型系统的基本配置开发了分析性能界限。为了将我们的结果与真实的系统联系起来，我们需要回答一些问题，例如并行系统如何在多屏障工作负载下扩展，它们如何处理包含屏障的作业的异构流，以及如何对多屏障工作负载进行建模。我们还需要解决某些实现问题，涉及动态操纵作业的并行度，以及调度优化所需的支持极细的任务粒度，可以在流数据的并行处理是有用的。

The goal of the VaMoS project is to bridge the gap between systems-oriented research and queueing theoretic works on parallel systems to create models which reflect the performance of real systems and their scaling behavior. This document reports on the first phase of this project, and proposes an extension to the project with a work program that builds on the successes and developments in the field over the last few years.During the first phase of the VaMoS project we performed wide-ranging, experimentally inspired work on parallel systems. We investigated the effects of job locality, analyzed traces from real clusters, investigated the performance benefits and trade-offs of finer task granularity both theoretically and experimentally, and conducted experiments and developed models for parallel systems with barriers, as are often needed when parallelizing machine learning workloads. This work involved implementation or extension of several software packages which we have publicly released.Our proposed project extension focuses mainly on parallel systems with barriers. Typically this means that jobs are divided into tasks which will be serviced in parallel by a cluster of workers, but that the tasks are constrained to start, and possibly complete, simultaneously. There may also be intermediate synchronization points. This type of constraint is common in machine learning workloads, and support for barrier execution mode has very recently been added to some map-reduce engines in order to support these types of workloads. These barrier constraints have major performance implications, because they can force workers to sit idle, waiting for a single long-running task to finish. In the first phase of the project we developed analytical performance bounds for basic configurations of these types of systems. To connect our results with real systems we need to answer a number of questions about how parallel systems scale under multi-barrier workloads, how they handle a heterogeneous stream of barrier-containing jobs, and how multi-barrier workloads can be modeled. We also need to address certain implementation problems involving dynamic manipulation of a job's degree of parallelism, and whether scheduling optimizations required to support extremely fine task granularity can be useful in parallel processing of streaming data.