Algorithms to Mitigate Partition Skew in MapReduce Applications

Algorithms for mitigating imbalance of the MapReduce computa-tions are considered in this paper. MapReduce is a new paradigm of processing big datasets in parallel. A MapReduce job consists of two phases of mapping and reducing. In the latter phase computation completion times may become imbalanced due to unequal distribution of the data. We propose four algorithms for balancing computational effort in the reducing phase. The static algorithm improves the load distribution by constructing a few times more load partitions than the number of reducing computers. The multi-dynamic algorithm performs many load balancing operations during the reducing phase, whereas the single-dynamic algorithm uses simulation to balance the load in a single step in the reducing phase. The mixed algorithm works both before and during the reducing phase. The performance of the algorithms is evaluated and compared by simulation. We conclude that the distribution of keys in the input data and the complexity of sorting by the reducers determine which algorithm is best to use