A Model for Data Processing on Warehouse-Scale Computers

Modern data processing workloads often have highly unpredictable end-to-end latency characteristics that are caused by heterogeneity, time-variation, and parallelized processing. The increase in unpredictability is in part attributable to job "straggling", and is symptomatic of a new class of stochastic scheduling challenges that will degrade the performance of current and future applications at scale. While the job scheduling literature for data processing frameworks is rich with ideas; there is little coordination between research groups on methodology and presentation, stunting the ability for designers to survey a collection of results and draw generalizable conclusions about good design patterns. We introduce an abstract system model for data processing on warehouse scale machines that aids in eliminating ambiguity in the job scheduling research by categorizing schedulers based on where they act on the system in the job processing data pathway. Furthermore, we demonstrate that although the scheduling problem is NP-Hard in the general case, it is still possible to derive scheduler design principles using bounds and asymptotics.