# MAPSKEW: Metaheuristic Approaches for Partitioning Skew in MapReduce
## 1 Introduction  
In the past decade, due to the massive growth of data through various application domains, such as social media, mobile computing, and the Internet of Things (IoT), MapReduce [1] has emerged as a highly successful framework for distributed and parallel computing on cloud systems. MapReduce allows the user to build complex computations on the data without having to worry about synchronization, fault tolerance, reliability or availability. Due to its simplicity, MapReduce has been widely used in various applications domains, such as search engine, database operations, machine learning, scientific computations, etc. In particular, a MapReduce job runs in two main phases: Map and Reduce. In the Map phase, a master node splits the input dataset into independent smaller sub-tasks, and distributes them to worker nodes. Then, a worker node processes its sub-tasks in a parallel way and passes the intermediate result back to the master node. In the reduce phase, the master node distributes the intermediate data to the workers according to a partition function. Finally, the workers collect the intermediate data and combine them to form the final output for the original problem. This process allows MapReduce to process large data sets on distributed clusters. The most popular open source implementation of MapReduce is Apache Hadoop. It was developed primarily by Yahoo and provides a distributed, scalable and portable file system, called HDFS, across clusters of computers. Both industry and academia, have adopted Apache Hadoop regularly to process and store large volumes of data [2]. Although it is broadly used for large scale data processing, one of the major obstacles hindering effective processing on MapReduce is data skew. Data skew refers to unbalanced computational load, caused by the imbalance in the amount of data per tasks or by the imbalance in the amount of effort spent by workers to process the datasets. By default, Hadoop uses a hash function to determine the data partition corresponding to the reduce tasks. It works well when the data are uniformly distributed. However, in many real-world applications, the data partitioning method based on hash function results in a non-uniform distribution of the output data, and further leads to skewing of the input data in the reduce tasks. As a consequence, some worker nodes may be overloaded while others may be idle, affecting the performance in Hadoop MapReduce. This phenomenon is called Partitioning Skew. Partitioning skew may occur naturally in many MapReduce applications. Bron-Kerbosch Clique [3], for example, is an algorithm for finding maximal Cliques in a undirected graph. It can exhibit skew when a large Clique is being investigated. Another example is the Inverted Index, a data structure used for Web search that takes a list of documents as input and generates an inverted index for these documents. This structure can exhibit skew if a certain content appear in many more documents than others. A simple WordCount application can also produce this similar skew phenomena if a word appear many times within a text. Hence, guaranteeing a fair load balancing in the reduce phase of Hadoop MapReduce framework, considering data skew, is a valuable issue to be addressed. In recent years, many studies have focused on the partitioning skew problem in MapReduce. Most of them [4; 5; 6; 7; 8] acts at the intermediate data distribution and try to rebalance the key distribution among reduce tasks. However, in order to obtain the statistics related to the generated intermediate data, these solutions either wait for all the mappers to finish [4; 5; 8] or add a sampling phase prior to the actual job start [6; 7]. Thus, they lead to network overhead and I/O excessive costs. Skewtune [9], a run-time skew mitigation technique, reallocates data that require more computational power to machines with more resources. Although this strategy improves performance of large data, it imposes high overhead, mainly on small amounts of data [9].