Matching-Based Assignement Strategies for Improving Data Locality of Map Tasks in MapReduce

MapReduce is a well-know framework for distributing data-processingcomputations onto parallel clusters. In MapReduce, a large computationis broken into small tasks that run in parallel on multiple machines,and scales easily to very large clusters of inexpensive commoditycomputers. Before the Map phase, the original dataset is split intodata chunks that are replicated (a constant number of times, usually3) and distributed randomly onto computing nodes. During the Mapphase, local tasks (i.e., tasks whose data chunks are stored locally)are assigned in priority when processors request tasks. In thispaper, we provide the first complete theoretical analysis of datalocality in the Map phase of MapReduce, and more generally, forbag-of-tasks applications that behave like MapReduce. We prove that iftasks are homogeneous (in terms of processing time), as soon as thereplication factor is larger than 2, FindAssignment, a matching basedalgorithm, achieves a quasi-perfect makespan (i.e., optimal up to anadditive constant of one step) using a sophisticated matchingalgorithm. Above result is proved with high probability when thenumber of tasks becomes arbitrarily large, and we therefore complementtheoretical results with simulations that corroborate them even forsmall number of tasks. We also show that the matching-based approachleads to an improvement of data locality during the Map phase andtherefore decreases the amount of communications needed to achieveperfect makespan, compared to the classical MapReduce greedy approach