Firmament: Fast, Centralized Cluster Scheduling at Scale
Symposium on Operating Systems Design and Implementation
12th USENIX Symposium on Operating Systems Design and Implementation
MetadataShow full item record
Gog, I., Schwarzkopf, M., Gleave, A., Watson, R., & Hand, S. (2016). Firmament: Fast, Centralized Cluster Scheduling at Scale. Symposium on Operating Systems Design and Implementation, 99-115. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/gog
Centralized datacenter schedulers can make high-quality placement decisions when scheduling tasks in a cluster. Today, however, high-quality placements come at the cost of high latency at scale, which degrades response time for interactive tasks and reduces cluster utilization. This paper describes Firmament, a centralized scheduler that scales to over ten thousand machines at sub- second placement latency even though it continuously reschedules all tasks via a min-cost max-flow (MCMF) optimization. Firmament achieves low latency by using multiple MCMF algorithms, by solving the problem incrementally, and via problem-specific optimizations. Experiments with a Google workload trace from a 12,500-machine cluster show that Firmament improves placement latency by 20 x over Quincy , a prior centralized scheduler using the same MCMF optimiza- tion. Moreover, even though Firmament is centralized, it matches the placement latency of distributed schedulers for workloads of short tasks. Finally, Firmament exceeds the placement quality of four widely-used central- ized and distributed schedulers on a real-world cluster, and hence improves batch task response time by 6 x.
This work was supported by a Google European Doc- toral Fellowship, by NSF award CNS-1413920, and by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory (AFRL), under contract FA8750-11-C-0249.
This record's URL: https://www.repository.cam.ac.uk/handle/1810/264317