Scheduling in Hadoop clusters: Novel algorithms, state space collapse and delay minimization in heavy traffic

Friday, December 04, 2015
UTA 7.532
Abstract: A fundamental problem to all data-parallel applications is data locality. There are multiple levels of data locality, as a data block can be accessed in local memory or disk, within a rack or a data center, or across data centers. Scheduling with data locality is an affinity scheduling problem with an explosive number of task types and unknown task arrival rates. As a result, existing algorithms do not apply and the recently proposed JSQ-MaxWeight (Wang et. al. 2014) algorithm for two-level locality is delay-optimal only for a special heavy traffic scenario.
We found that for two-level locality, a simple priority algorithm is delay-optimal for all heavy traffic scenarios. With multi-level locality, we propose a novel algorithm. The key insight is that instead of focusing on scheduling alone, what if we co-design routing and scheduling? The insight is potentially applicable to affinity scheduling in general.
For both algorithms, we provide rigorous proofs for heavy-traffic optimality that use an ideal load decomposition and an interesting state space collapse. We implemented our algorithm in Hadoop clusters, and showed that it accelerates the data-processing phase of jobs by 11 times with hot-spots and 2.4 times without hot-spots.


Assistant Professor
University of Illinois at Urbana-Champaign

Yi Lu is an assistant professor in the ECE department at UIUC. She is a recipient of the Terman Engineering Scholastic Award, Stanford Graduate Fellowship, the Sigmetrics Best paper award in 2008, the Performance Best paper award in 2011, the NSF Career award in 2012 and the Center of Advanced Study fellowship in 2014. Her work focuses on developing scalable architectures and algorithms for large networking systems such as modern web services with dynamic content, cloud computing and social networks. Her work spans fundamental analysis and algorithm implementation, and emphasizes design of low-complexity easy-to-implement algorithms.

Lu received a BS, MS and PhD in electrical engineering from Stanford University. Her research interests include distributed systems and networking, network algorithms and inference on graphical models. She is the recipient of a 2012 NSF CAREER Award and a Center of Advanced Study Fellow.