Efficient shuffle for flash burst computing
Abstract/Contents
- Abstract
- Shuffle is the operation of exchanging arbitrary data among a group of servers, and it is a fundamental communication primitive in distributed computing. In particular, shuffle has been shown to be a fundamental bottleneck to the scalability of flash bursts, a radically new paradigm in datacenter computing. Flash bursts use a large number of servers but for very short time intervals (as little as one millisecond), which makes it possible to run large-scale data-intensive computation within a few milliseconds. Flash bursts present three significant challenges to the design of a shuffle algorithm. First, it cannot use a centralized scheduler. Second, it needs to be efficient even under interference from competing workloads. Finally, it must be applicable to large clusters that don't provide full bisection bandwidth. This thesis presents a clean-slate shuffle algorithm that achieves optimal performance cross a wide range of workloads even under the demanding conditions of flash bursts. This algorithm schedules messages as ensembles to match sender and receiver bandwidths decentrally; it overcommits receiver downlinks to maintain high network utilization; it uses pro rata sliding windows to enforce a weighted max-min fair sharing policy; finally, it uses a lightweight global scheduling scheme to manage the bottleneck links in the network core without knowledge of the underlying network topology.
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 | Li, Yilong, (Computer scientist) | |
|---|---|---|
| Degree supervisor | Ousterhout, John K | |
| Thesis advisor | Ousterhout, John K | |
| Thesis advisor | Winstein, Keith | |
| Thesis advisor | Zaharia, Matei | |
| Degree committee member | Winstein, Keith | |
| Degree committee member | Zaharia, Matei | |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Yilong Li. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/bc126zv2584 |
Access conditions
- Copyright
- © 2022 by Yilong Li
- 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...