Mitigating Service Variability in MapReduce Clusters via Task Cloning: A Competitive Analysis
Huanle Xu, Wing Cheong Lau, Zhibo Yang, Gustavo de Veciana, Hanxu Hou · IEEE Transactions on Parallel and Distributed Systems · 2017
Measurement traces from real-world production environment show that the execution time of tasks within a MapReduce job varies widely due to the variability in machine service capacity. This variability issue makes efficient job scheduling over large-scale MapReduce clusters extremely challenging. To tackle this problem, we adopt the task cloning approach to mitigate the effect of machine variability and design corresponding scheduling algorithms so as to minimize the overall job flowtime in different scenarios. For offline scheduling where all jobs arrive at the same time, we design an$O(1)$-competitive algorithm, which gives priorities to jobs with small effective workload. We then extend this offline algorithm to yield the so-called Smallest Remaining Effective Workload based$\beta$-fraction Sharing plus Cloning algorithm (SREW+C($\beta$)) for the online case. We also show that SREW+C($\beta$) is$(1+ 2\beta + \epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive with respect to the sum of job flowtime within a cluster. We demonstrate via trace-driven simulations that SREW+C($\beta$) can significantly reduce the overall job flowtime by cutting down the elapsed time of small jobs substantially. In particular, SREW+C($\beta$) reduces the total job flowtime by 14, 10 and 11 percent respectively when comparing to Mantri, Dolly and Grass.