Accuracy Improvement for Backup Tasks in Hadoop Speculative Algorithm
Worachate Apichanukul, Jun I. Kawahara, Shoji Kasahara · 2016
Hadoop suffers from the issue of stragglers in which some tasks with unusual long execution time delay the whole job. Hadoop relieves the straggler problem by launching backup tasks, that are cloned from original tasks and executed on server nodes different from those executing original tasks. A speculative algorithm is responsible for classifying straggler tasks and launching backup tasks. Although launching backup tasks can solve the problem, it requires additional resources to run. Existing algorithms wrongly classify and start many wasteful backup tasks, which reduces resource utilization. This paper proposes an algorithm called Accuracy Improvement for Backup Task (AIBT) in Hadoop speculative algorithm. In the AIBT algorithm, a task is divided into phases, and the execution time of the task is estimated from progress rates of the phases. Moreover, AIBT uses execution time information both from other finished tasks and its own to improve the accuracy of the estimated values by changing the weight dynamically. We implement the AIBT algorithm in Hadoop and evaluate its performance for four job types: Wordcount, KMean clustering, PageRank, and Inverted Index. Numerical results show that AIBT significantly reduces the number of unnecessary and wrong backup tasks compared with the existing algorithms.