Storage-aware task scheduling for performance optimization of big data workflows

Many large-scale applications in various domains are generating big data, which are increasingly processed and analyzed by MapReduce-based workflows deployed in Hadoop systems. In addition to computing time, the makespan of such data-intensive workflows is also largely affected by communication cost. Particularly, there are two levels of data movement during the execution of distributed workflows in Hadoop: i) from map tasks to reduce tasks within each individual MapReduce module and ii) between each pair of adjacent modules in the workflow. Traditionally, these two aspects of network traffic have been treated separately as data locality at the task and module or job level, respectively. However, the interactions between these two levels of data movement may create complicated dynamics and their compound effects remain largely unexplored. In this paper, we formulate a task scheduling problem that considers data movement at both levels to minimize the end-to-end delay of a MapReduce-based workflow. We show this problem to be NP-complete, and design a storage-aware big data workflow scheduling algorithm, referred to as SA-BWS, to optimize workflow performance in Hadoop environments. The performance superiority of SA-BWS is illustrated by extensive simulations in comparison with the default workflow engine in Hadoop and existing scheduling methods.