text: Distributed computing frameworks such as MapReduce are often used to process large computational jobs. They operate by partitioning each job into smaller tasks executed on different servers. The servers also need to exchange intermediate values to complete the computation. Experimental evidence suggests that this so-called Shuffle phase can be a significant part of the overall execution time for several classes of jobs. Prior work has demonstrated a natural tradeoff between computation and communication whereby running redundant copies of jobs can reduce the Shuffle traffic load, thereby leading to reduced overall execution times. For a single job, the main drawback of this approach is that it requires the original job to be split into a number of files that grows exponentially in the system parameters. When extended to multiple jobs (with specific function types), these techniques suffer from a limitation of a similar flavor, i.e., they require an exponentially large number of jobs to be executed. In practical scenarios, these requirements can significantly reduce the promised gains of the method. In this work, we show that a class of combinatorial structures called resolvable designs can be used to develop efficient coded distributed computing schemes for both the single and multiple job scenarios considered in prior work. We present both theoretical analysis and exhaustive experimental results (on Amazon EC2 clusters) that demonstrate the performance advantages of our method. For the single and multiple job cases, we obtain speed-ups of 4.69x (and 2.6x over prior work) and 4.31x over the baseline approach, respectively.
  @cite_29: The data placement strategy greatly affects the efficiency of MapReduce. The current strategy only takes the map phase into account to optimize the map time. But the ignored shuffle phase may increase the total running time significantly in many jobs. We propose a new data placement strategy, named OPTAS, which optimizes both the map and shuffle phases to reduce their total time. However, the huge search space makes it difficult to find out an optimal data placement instance (DPI) rapidly. To address this problem, an algorithm is proposed which can prune most of the search space and find out an optimal result quickly. The search space firstly is segmented in ascending order according to the potential map time. Within each segment, we propose an efficient method to construct a local optimal DPI with the minimal total time of both the map and shuffle phases. To find the global optimal DPI, we scan the local optimal DPIs in order. We have proven that the global optimal DPI can be found as the first local optimal DPI whose total time stops decreasing, thus further pruning the search space. In practice, we find that at most fourteen local optimal DPIs are scanned in tens of thousands of segments with the pruning strategy. Extensive experiments with real trace data verify not only the theoretic analysis of our pruning strategy and construction method but also the optimality of OPTAS. The best improvements obtained in our experiments can be over 40 compared with the existing strategy used by MapReduce.
  @cite_22: MapReduce clusters are usually multi-tenant (i.e., shared among multiple users and jobs) for improving cost and utilization. The performance of jobs in a multitenant MapReduce cluster is greatly impacted by the all-Map-to-all-Reduce communication, or Shuffle, which saturates the cluster's hard-to-scale network bisection bandwidth. Previous schedulers optimize Map input locality but do not consider the Shuffle, which is often the dominant source of traffic in MapReduce clusters. We propose ShuffleWatcher, a new multitenant MapReduce scheduler that shapes and reduces Shuffle traffic to improve cluster performance (throughput and job turn-around times), while operating within specified fairness constraints. ShuffleWatcher employs three key techniques. First, it curbs intra-job Map-Shuffle concurrency to shape Shuffle traffic by delaying or elongating a job's Shuffle based on the network load. Second, it exploits the reduced intra-job concurrency and the flexibility engendered by the replication of Map input data for fault tolerance to preferentially assign a job's Map tasks to localize the Map output to as few nodes as possible. Third, it exploits localized Map output and delayed Shuffle to reduce the Shuffle traffic by preferentially assigning a job's Reduce tasks to the nodes containing its Map output. ShuffleWatcher leverages opportunities that are unique to multi-tenancy, such overlapping Map with Shuffle across jobs rather than within a job, and trading-off intra-job concurrency for reduced Shuffle traffic. On a 100-node Amazon EC2 cluster running Hadoop, ShuffleWatcher improves cluster throughput by 39-46 and job turn-around times by 27-32 over three state-of-the-art schedulers.
  @cite_3: Nowadays, MapReduce has become very popular in many applications, such as high performance computing. It typically consists of map, shuffle and reduce phases. As an important one among these three phases, data shuffling usually accounts for a large portion of the entire running time of MapReduce jobs. MapReduce was originally designed in scale-out architecture with inexpensive commodity machines. However, in recent years, scale-up computing architecture for MapReduce jobs has been developed. Some studies indicate that in certain cases, a powerful scale-up machine can outperform a scale-out cluster with multiple machines. With multi-processor, multi-core design connected via NUMAlink and large shared memories, NUMA architecture provides a powerful scale-up computing capability. Compared with Ethernet connection and TCP IP network, NUMAlink has a much faster data transfer speed which can greatly expedite the data shuffling of MapReduce jobs. The impact of NUMAlink on data shuffling in NUMA scale-up architecture has not been fully investigated in previous work. In this paper, we ignore the computing power (i.e., map and reduce phases) of MapReduce, but focus on the optimization of data shuffling phase in MapReduce framework in NUMA machine. We concentrate on the various bandwidth capacities of NUMAlink(s) among different memory locations to fully utilize the network. We investigate the NUMAlink topology using SGI UV 2000 as an example and propose a topology-aware reducer placement algorithm to speed up the data shuffling phase. In addition, we extend our approach to a larger computing environment with multiple NUMA machines, and design a reducer placement scheme to expedite the inter-NUMA machine data shuffling. Experiments results show that data shuffling time can be greatly reduced in NUMA architecture with our solution.
summary: The work of @cite_22 introduced ShuffleWatcher", a MapReduce scheduler that reduces throughput and job completion time. The scheme replicates Map tasks and delays or elongates a job's communication time depending on the network load. Their technique also judiciously assigns Reduce tasks to workers based on the Map assignment. Other related work on this topic has been published in @cite_3 which considers a model of MapReduce executed on a multi-core machine and proposes a topology-aware architecture to expedite data shuffling. The authors of @cite_29 present an algorithm that finds the optimal placement and jointly optimizes Map and Shuffle time.