Hybrid, Job-Aware, and Preemptive Datacenter Scheduling

Scheduling in datacenters is an important, yet challenging problem. Datacenters are composed of a large number, typically tens of thousands, of commodity computers running a variety of data-parallel jobs. The role of the scheduler is to assign cluster resources to jobs, which is not trivial due to the large scale of the cluster, as well as the high scheduling load (tens of thousands of scheduling decisions per second).

Additionally to scalability, modern datacenters face increasingly heterogeneous workloads composed of long batch jobs, e.g., data analytics, and latency-sensitive short jobs, e.g., operations of user-facing services. In such workloads, and especially if the cluster is highly utilized, it is challenging to avoid short running jobs getting stuck behind long running jobs, i.e. head-of-line blocking.

Schedulers have evolved from being centralized (one single scheduler for the entire cluster) to distributed (many schedulers that take scheduling decisions in parallel). Although distributed schedulers can handle the large-scale nature of datacenters, they trade scheduling latency for accuracy.

The complexity of scheduling in datacenters is exacerbated by the data-parallel nature of the jobs. That is, a job is composed of multiple tasks and the job completes only when all of its tasks complete. A scheduler that takes into account this fact, i.e. job-aware, could use this information to provide better scheduling decisions.

Furthermore, to improve the quality of their scheduling decisions, most of datacenter schedulers use job runtime estimates. Obtaining accurate runtime estimates is, however, far from trivial, and erroneous estimates may lead to sub-optimal scheduling decisions.

Considering these challenges, in this dissertation we argue the following: (i) that a hybrid centralized/distributed design can get the best of both worlds by scheduling long jobs in a centralized way and short jobs in a distributed way; (ii) such a hybrid scheduler can avoid head-of-line blocking and provide job-awareness by dynamically partitioning the cluster for short and long jobs and by executing a job to completion once it started; (iii) a scheduler can dispense with runtime estimates by sharing the resources of a node with preemption, and load balancing jobs among the nodes.

Job-aware Scheduling in Eagle: Divide and Stick to Your Probes

Pamela Isabel Delgado Borda, Diego Didona, Florin Dinu, Willy Zwaenepoel

We present Eagle, a new hybrid data center scheduler for data-parallel programs. Eagle dynamically divides the nodes of the data center in partitions for the execution of long and short jobs, thereby avoiding head-of-line blocking. Furthermore, it provides job awareness and avoids stragglers by a new technique, called Sticky Batch Probing (SBP). The dynamic partitioning of the data center nodes is accomplished by a technique called Succinct State Sharing (SSS), in which the distributed schedulers are informed of the locations where long jobs are executing. SSS is particularly easy to implement with a hybrid scheduler, in which the centralized scheduler places long jobs. With SBP, when a distributed scheduler places a probe for a job on a node, the probe stays there until all tasks of the job have been completed. When finishing the execution of a task corresponding to probe P, rather than executing a task corresponding to the next probe P' in its queue, the node may choose to execute another task corresponding to P. We use SBP in combination with a distributed approximation of Shortest Remaining Processing Time (SRPT) with starvation prevention. We have implemented Eagle as a Spark plugin, and we have measured job completion times for a subset of the Google trace on a 100-node cluster for a variety of cluster loads. We provide simulation results for larger clusters, different traces, and for comparison with other scheduling disciplines. We show that Eagle outperforms other state-of-the-art scheduling solutions at most percentiles, and is more robust against mis-estimation of task duration.

ACM2016

Kairos: Preemptive Data Center Scheduling Without Runtime Estimates

Pamela Isabel Delgado Borda, Diego Didona, Florin Dinu, Willy Zwaenepoel

The vast majority of data center schedulers use task runtime estimates to improve the quality of their scheduling decisions. Knowledge about runtimes allows the schedulers, among other things, to achieve better load balance and to avoid head-of-line blocking. Obtaining accurate runtime estimates is, however, far from trivial, and erroneous estimates lead to sub-optimal scheduling decisions. Techniques to mitigate the effect of inaccurate estimates have shown some success, but the fundamental problem remains. This paper presents Kairos, a novel data center scheduler that assumes no prior information on task runtimes. Kairos introduces a distributed approximation of the Least Attained Service (LAS) scheduling policy. Kairos consists of a centralized scheduler and per-node schedulers. The per-node schedulers implement LAS for tasks on their node, using preemption as necessary to avoid head-of-line blocking. The centralized scheduler distributes tasks among nodes in a manner that balances the load and imposes on each node a workload in which LAS provides favorable performance. We have implemented Kairos in YARN. We compare its performance against the YARN FIFO scheduler and Big-C, an open-source state-of-the-art YARN-based scheduler that also uses preemption. Compared to YARN FIFO, Kairos reduces the median job completion time by 73% and the 99th percentile by 30%. Compared to Big-C, the improvements are 37% for the median and 57% for the 99th percentile. We evaluate Kairos at scale by implementing it in the Eagle simulator and comparing its performance against Eagle. Kairos improves the 99th percentile of short job completion times by up to 55% for the Google trace and 85% for the Yahoo trace.

2018

Efficient Workload Colocation in Modern Data Centers

Calin Iorgulescu

Despite the high costs of acquisition and maintenance of modern data centers, machine resource utilization is often low. Servers running online interactive services are over-provisioned to support peak load (which only occurs for a fraction of the time), due to business continuity and fault-tolerance plans that dictate these services tolerate major unforeseen events (e.g., the failure of another data center). Underutilized computing resources correlate with reduced data center efficiency and capital losses incurred by operators. Colocating different types of workloads is a promising solution to increase resource utilization. The challenges are protecting interactive services from resource interference and handling limited resource availability: if a best-effort workload directly competes for resources with an interactive service, the latter can fail to meet its service-level objectives (SLOs), impacting user experience and resulting in lost revenue. In this dissertation we focus on how to mitigate CPU interference and limited memory availability when colocating interactive services with batch workloads such as data-parallel applications. Existing work on mitigating CPU interference assumes that progress and performance metrics are available in real-time, and that hardware support for low-level isolation mechanisms is prevalent, neither of which are always true in commercial environments. Furthermore, previous work on improving resource allocation in clusters does not attempt to over-commit memory due to concerns of unpredictable performance degradation and sporadic failures. We first focus on the colocation of open-source in-memory interactive services, and conduct a thorough investigation on how they are impacted by batch jobs. We find that existing isolation techniques do not prevent performance degradation, and explain in detail why they are insufficient. Second, we study the behavior of a large commercial-scale service (i.e., a component of a web search platform), finding that it is highly bursty. We show that, by keeping a headroom of idle cores available at all times, the serviceâs response tail-latency is maintained within its SLO even under heavy load. Third, we address the impact of limited memory availability on data-parallel applications by identifying an intrinsic property of their tasks: memory elasticity â the ability to handle memory pressure by writing intermediate data to external storage, incurring only moderate performance penalties when memory-constrained. We further show that memory elasticity is prevalent across various data-parallel application frameworks. We implement a scheduler that leverages memory elasticity and achieves reduced job completion times and increased memory utilization. We conclude that these techniques make it possible to colocate even highly-bursty latency-sensitive services with batch jobs, significantly increasing resource utilization.

EPFL2019

Efficient Workload Colocation in Modern Data Centers

Calin Iorgulescu

EPFL2019