BOLAS+: Scalable Lightweight Locality-Aware Scheduling for Hadoop
Shengli Gao, Ruini Xue · 2016
Locality-aware task scheduling for MapReduce can reduce job execution time by avoiding data transferring. However, many existing scheduling algorithms suffer from either heavy storage overhead, reduced task parallelism, significant response time, or poor scalability. To address these issues, this paper presents BOLAS+, a scalable lightweight locality-aware scheduling algorithm for Hadoop. BOLAS+ takes such global information as block distribution and node performance divergence into consideration for optimal scheduling. BOLAS+ associates each node and each block replica with a value, node importance, and replica priority, respectively. As the only factors for scheduling decision-making, these two values are updated dynamically upon a scheduling request, and are designed in a way that they can be calculated very efficiently. Only simple comparisons within these values of local blocks are involved during scheduling, which guarantees the scalability of BOLAS+. Experimental results show that BOLAS+ can completely eliminate off-switch scheduling, and ensure more than 95% node-local scheduling with a very low complexity O(n/m), which in turn can reduce the total job execution time by up to 15.1%.