Shed+: Optimal Dynamic Speculation to Meet Application Deadlines in Cloud

• Published in: IEEE eTransactions on network and service management 2020-09, Vol.17 (3), p.1515-1526
• Main Authors: Alamro, Sultan, Xu, Maotong, Lan, Tian, Subramaniam, Suresh
• Format: Article
• Language: English
• Subjects: Cloning; Cloud; Cloud computing; Computational modeling; Deadlines; Dynamic scheduling; Electronic mail; mapreduce; Optimization; scheduling; speculation; stragglers; Task analysis
• ISSN: 1932-4537; 1932-4537
• DOI: 10.1109/TNSM.2020.2986477

With the growing deadline-sensitivity of cloud applications, adherence to specific deadlines is becoming increasingly crucial, particularly in shared clusters. A few slow tasks called stragglers can potentially adversely affect job execution times. Equally, inadequate slotting of data analytics applications could result in inappropriate resource deployment, ultimately damaging system performance. Against this backdrop, one effective way of tackling stragglers is by making extra attempts (or clones) 1 for every single straggler after the submission of a job. This paper proposes Shed \pmb {+} , which is an optimization framework utilizing dynamic speculation that aims to maximize the jobs' PoCD (Probability of Completion before Deadline) by making full use of available resources. Notably, our work encompasses a new online scheduler that dynamically recomputes and reallocates resources during the course of a job's execution. According to our findings, Shed \pmb {+} successfully leverages cloud resources and maximizes the percentage of jobs meeting their deadlines. In our experiments, we have seen this percentage for heavy load going up to 98% for Shed \pmb {+} as opposed to nearly 68%, 40%, 35% and 37% for Shed, Dolly, Hopper and Hadoop with speculation enabled, respectively. 1 Cloning or extra attempts means task duplication.