Eager: Collaborative Research: DiRecMR: Reconciling the Dichotomy of MapReduce for Efficient Speculation and Resilience

MapReduce系统在处理大量数据方面具有很强的能力，已经成为政府、学术和工业组织的研究目标。然而，它们的任务管理和故障处理策略不承认存在于其固有的两个阶段（映射和减少）之间的隐性二分法。这将导致许多关键问题，例如资源利用不足、任务执行时间延长、短视猜测和失败放大。该项目采用了理论分析、仿真和建模以及系统设计和实现方法的变革性组合，以调和MapReduce的二分法。这个项目的技术对所有部署MapReduce系统和支持大数据应用的组织都有潜在的影响，这些应用包括商业分析、社交网络和科学计算研究。本项目没有通过对系统行为的实证分析来精确定位资源管理和任务调度异常，而是从不同的角度来看待MapReduce的效率和弹性，提出了Hadoop MapReduce容器转换的马尔可夫链，以及map和reduce任务排队的fork-join模型。这些公式有助于对MapReduce的二分法进行理论分析，并有助于阐明其对大规模工作负载的渐近行为的影响。本项目旨在将仿真与真实系统开发融合在一起，解决二分法导致的短视猜测，解放任务猜测的范围，确保任务弹性而不放大失败。开发这些技术是为了增强YARN和Spark等MapReduce平台。除了在MapReduce系统上的目标，这个项目的研究解决了分布式分析环境中的一个普遍问题。

MapReduce systems have great capabilities in processing large amounts of data and have become a research target for governmental, academic and industrial organizations. However, their task management and fault handling policies do not recognize a tacit dichotomy that exists between its inherent two phases (map and reduce). This results in a number of critical issues, such as resource underutilization, prolonged task execution, myopic speculation, and failure amplifications. This project adopts a transformative combination of theoretical analysis, simulation and modeling, and systems design and implementation approaches in order to reconcile the dichotomy of MapReduce. The techniques from this project are potentially impactful to all organizations that deploy MapReduce systems and support Big Data applications from business analytics, social networks, and scientific computing research.Instead of empirical analysis of system behaviors to pinpoint resource management and task scheduling abnormalities, this project takes a different perspective on MapReduce efficiency and resilience, and formulates a Markov chain for the transition of Hadoop MapReduce containers, and a fork-join model for the queueing of map and reduce tasks. These formulations facilitate a theoretical analysis of the dichotomy of MapReduce and help shed light on its impact to asymptotic behaviors of large-scale workloads. This project aims to blend simulation and real system development together, and addresses the myopic speculation caused by dichotomy, liberates the scope of task speculation, and ensures task resilience without failure amplifications. These techniques are developed to enhance MapReduce platforms such as YARN and Spark. Besides the target on MapReduce systems, the research from this project addresses a general issue in distributed analytics environments.