Tag Archives: Modeling

Modeling and Optimization of Straggling Mappers

ABSTRACT
MapReduce framework is widely used to parallelize batch jobs since it exploits a high degree of multi-tasking to process them. However, it has been observed that when the number of mappers increases, the map phase can take much longer than expected. This paper analytically shows that stochastic behavior of mapper nodes has a negative effect on the completion time of a MapReduce job, and continuously increasing the number of mappers without accurate scheduling can degrade the overall performance. We analytically capture the effects of stragglers (delayed mappers) on the performance. Based on an observed delayed exponential distribution (DED) of the response time of mappers, we then model the map phase by means of hardware, system, and application parameters. Mean sojourn time (MST), the time needed to sync the completed map tasks at one reducer, is mathematically formulated. Following that, we optimize MST by finding the task inter-arrival time to each mapper node. The optimal mapping problem leads to an equilibrium property investigated for different types of inter-arrival and service time distributions in a heterogeneous datacenter (i.e., a datacenter with different types of nodes). Our experimental results show the performance and important parameters of the different types of schedulers targeting MapReduce applications. We also show that, in the case of mixed deterministic and stochastic schedulers, there is an optimal scheduler that can always achieve the lowest MST.

[Tech Report] [Master Thesis] [IEEE Trans]

Last version > MapReduce_Performance_Optimization

Performance Modeling and Optimization of MapReduce

Abstract:
MapReduce framework is widely used to parallelize batch jobs of great companies. MapReduce splits the job for each mapper in the map phase and then intermediate tasks are synced in reducers to be processed in the next stage. It exploits a high degree of multi-tasking to process the jobs as soon as possible. However map and reduce phases are done by many parallel nodes, it has been realized that when the number of mappers increase map phase takes longer than usual. This problem known as stragglers issue has been observed in CDF of completion times of mapper nodes.
This paper shows that stochastic behavior of mapper nodes has a negative effect on the completion time of MapReduce framework, i.e. increasing the number of mapper nodes blindly not only manages resources effectively but also can degrade the performance. To the best of our knowledge this is the first time in this paper MapReduce framework is modeled as fork-join queues from HDFS storage to one reducer. We capture the stragglers problem and based on observed delayed exponential CDF of response time of mappers we model task inter-arrival and service rate of each mapper node. Mean sojourn time (MST) which is the time needed to sync the completed map tasks at one reducer is formulated. Then we minimize MST by finding the input mapping of jobs to each mapper node. Equilibrium of means as a property of MST minimization problem can be generalized to some other inter-arrival and service time distributions. In the case of mixed deterministic and stochastic modeling optimal solution can always show the lowest MST. This approach not only can capture the optimal mapping of mapper nodes but also can address the optimal number of mapper nodes to get the lowest response time by MapReduce framework.

Performance Modeling and Optimization of MapReduce