SkewTune

TLDR

The study addresses three challenges in MapReduce skew mitigation: requiring no user input, remaining transparent, and imposing minimal overhead when no skew is present. The authors propose SkewTune, an automatic skew mitigation system that serves as a drop‑in replacement for existing MapReduce implementations. SkewTune monitors idle nodes, identifies the task with the longest expected remaining time, and proactively repartitions its unprocessed data to fully utilize the cluster while preserving input order for output reconstruction; it is implemented as a Hadoop extension and evaluated on real applications. Experiments show that SkewTune substantially reduces job runtime under skew and incurs negligible overhead when skew is absent.

Abstract

We present an automatic skew mitigation approach for user-defined MapReduce programs and present SkewTune, a system that implements this approach as a drop-in replacement for an existing MapReduce implementation. There are three key challenges: (a) require no extra input from the user yet work for all MapReduce applications, (b) be completely transparent, and (c) impose minimal overhead if there is no skew. The SkewTune approach addresses these challenges and works as follows: When a node in the cluster becomes idle, SkewTune identifies the task with the greatest expected remaining processing time. The unprocessed input data of this straggling task is then proactively repartitioned in a way that fully utilizes the nodes in the cluster and preserves the ordering of the input data so that the original output can be reconstructed by concatenation. We implement SkewTune as an extension to Hadoop and evaluate its effectiveness using several real applications. The results show that SkewTune can significantly reduce job runtime in the presence of skew and adds little to no overhead in the absence of skew.