Fast and flexible scheduling across the system stack
Abstract/Contents
- Abstract
- This thesis focuses on scheduling, a fundamental operation in computer systems and networks. Scheduling occurs at multiple layers across the stack, from global load balancers to programmable network devices to the operating system in end-hosts. Despite this diversity, schedulers perform a single fundamental operation: they map work to execution resources and deal with queuing and ordering and any other trade-offs in this operation, e.g., locality vs. parallelism. The emergence of cloud computing has drastically changed the scheduling requirements in recent years as performance constraints have become increasingly tight. Applications need to serve millions of queries per second while keeping each query's latency at microsecond scale, even in the worst-case scenario. In other words, schedulers need to enable low request tail latency under high loads. We first explore how to design faster and better scheduling policies and mechanisms for the cloud. We find that this question has different answers depending on the level of the stack considered, ranging from single-host operating systems to load balancers to cloud providers' cluster managers. We present Shinjuku, a specialized single-node OS that supports an order of magnitude higher load and lower tail latency than state-of-the-art systems by enabling better scheduling. Shinjuku leverages hardware support for virtualization to enable fast interrupts that allow us to preempt as often as every 5 microseconds and disproves the conventional wisdom that interrupts are incompatible with microsecond timescales. We built on these interrupts to design scheduling policies that match the task distribution and target latency and achieve microsecond-scale tail latency for all types of workloads regardless of the variability in task duration. Then, we study the effect of scheduling in large-scale environments by deploying a system called PACT to Google's data centers and showing that core scheduling across applications combined with dynamic frequency scaling can reduce power consumption even in a highly-utilized and optimized system. Finally, we shift our focus to an emerging cloud compute paradigm, serverless computing and explore its scheduling implications. Taking a first-principles approach, we create a taxonomy of scheduling policies for serverless functions and study their unique characteristics. Based on our conclusions, we design Hermod, a load-, cost-, and locality-aware scheduler that, for real-world traces, achieves lower latency under higher load compared to schedulers not optimized for serverless functions. However, it is not enough to build better and faster schedulers; we should also make it easier for everyone to build a custom scheduler for their application. Towards this goal, we built Syrup, a framework that enables everyday application developers to specify custom scheduling policies easily and safely deploy them across different layers of the stack over existing operating systems like Linux, bringing the benefits of specialized scheduling to everyone. Syrup treats scheduling as a matching problem between units of work and executors, allowing users to declare scheduling policies as matching functions without dealing with the low-level details of actually implementing the matching. Thus, Syrup decouples policy declaration and implementation. Using Syrup, we implemented policies that previously required dataplanes in less than 20 lines of code and improved the performance of an in-memory database by 8x without needing any application modification.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Kaffes, Konstantinos |
|---|---|
| Degree supervisor | Kozyrakis, Christoforos, 1974- |
| Thesis advisor | Kozyrakis, Christoforos, 1974- |
| Thesis advisor | Mazières, David (David Folkman), 1972- |
| Thesis advisor | Rosenblum, Mendel |
| Degree committee member | Mazières, David (David Folkman), 1972- |
| Degree committee member | Rosenblum, Mendel |
| Associated with | Stanford University, Department of Electrical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Kosti Kaffes. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/dv298bh6466 |
Access conditions
- Copyright
- © 2022 by Konstantinos Kaffes
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...