Optimal reducer placement to minimize data transfer in MapReduce-style processing
Xiao Meng, Lukasz Golab · 2017
MapReduce-style processing has become the standard for large-scale distributed platforms, with Hadoop being the most popular implementation. While Hadoop achieves parallelism by scheduling Map and Reduce tasks across the available nodes, it incurs communication overhead in the Shuffle stage which sends intermediate results from mappers to reducers. The problem we solve is as follows: given a collection of mapper outputs (intermediate key-value pairs) and a partitioning of this collection among the reducers, which node should each reducer run on to minimize data transfer? We reduce two natural formulations of this problem to optimization problems for which polynomial solutions exist. We show that our techniques can cut communication costs by 50 percent or more compared to Hadoop's default reducer placement, which leads to lower network utilization and faster MapReduce job runtimes.