Job scheduling for a MapReduce cluster has been an active research topic in recent years. However, measurement traces from real-world production environment show that the duration of tasks within a job vary widely. The overall elapsed time of a job, i.e. the so-called flowtime, is often dictated by one or few slowly-running tasks within a job, generally referred as the "stragglers". The cause of stragglers include tasks running on partially intermittently failing machines or the existence of some localized resource bottleneck(s) within a MapReduce cluster. To tackle this online job scheduling challenge, we adopt the task cloning approach and design the corresponding scheduling algorithms which aim at minimizing the weighted sum of job flowtimes in a MapReduce cluster based on the Shortest Remaining Processing Time scheduler (SRPT). To be more specific, we first design a 2-competitive offline algorithm when the variance of task-duration is negligible. We then extend this offline algorithm to yield the so-called SRPTMS+C algorithm for the online case and show that SRPTMS+C is @math @math in reducing the weighted sum of job flowtimes within a cluster. Both of the algorithms explicitly consider the precedence constraints between the two phases within the MapReduce framework. We also demonstrate via trace-driven simulations that SRPTMS+C can significantly reduce the weighted unweighted sum of job flowtimes by cutting down the elapsed time of small jobs substantially. In particular, SRPTMS+C beats the Microsoft Mantri scheme by nearly 25 according to this metric.
Finally, the SRPT scheduler has been studied extensively in traditional parallel scheduling literature. In particular, SRPT has proven to be @math @math for total flowtime on @math identical machines under the single task case @cite_10 . In this paper, we extend the SRPT scheduler to yield an online scheduler which can mitigate stragglers as well.
@cite_10
2951082421
Due to its optimality on a single machine for the problem of minimizing average flow time, Shortest-Remaining-Processing-Time ( ) appears to be the most natural algorithm to consider for the problem of minimizing average flow time on multiple identical machines. It is known that @math achieves the best possible competitive ratio on multiple machines up to a constant factor. Using resource augmentation, @math is known to achieve total flow time at most that of the optimal solution when given machines of speed @math . Further, it is known that @math 's competitive ratio improves as the speed increases; @math is @math -speed @math -competitive when @math . However, a gap has persisted in our understanding of @math . Before this work, the performance of @math was not known when @math is given @math -speed when @math . We complement this by showing that @math is @math -speed @math -competitive for the objective of minimizing the @math -norms of flow time on @math identical machines. Both of our results rely on new potential functions that capture the structure of . Our results, combined with previous work, show that @math is the best possible online algorithm in essentially every aspect when migration is permissible.