Sparrow: distributed, low latency scheduling

By Kay Ousterhout, Patrick Wendell, Matei A. Zaharia, Ion Stoica. 2013

687 citations recorded by the source corpus.

Large-scale data analytics frameworks are shifting towards shorter task durations and larger degrees of parallelism to provide low latency. Scheduling highly parallel jobs that complete in hundreds of milliseconds poses a major challenge for task schedulers, which will need to schedule millions of tasks per second on appropriate machines while offering millisecond-level latency and high availability. We demonstrate that a decentralized, randomized sampling approach provides near-optimal performance while avoiding the throughput and availability limitations of a centralized design. We implement and deploy our scheduler, Sparrow, on a 110-machine cluster and demonstrate that Sparrow performs within 12% of an ideal scheduler.

Subfields: Computer Networks and Communications, Hardware and Architecture, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

In Information Systems

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “In the context of a job scheduler [62], the allocation strategy selects the server on which to run a task.”
Splitwise: Efficient Generative LLM Inference Using Phase Splitting (2023, background): “Insights from prior work on partitioned or replicated scheduling could help improve scalability [27], [61], [72] and are orthogonal to Splitwise.”
Twine: A Unified Cluster Management System for Shared Infrastructure (2020, background): “A large body of work [6, 15, 20, 31] focuses on improving batch scheduling throughput and latency.”
Decentralized task-aware scheduling for data center networks (2014, background): “While decentralization may appear at odds with the recent trend towards a centralized control plane [3], it is crucial for supporting applications with small (sub-second) tasks (e.g., search, social networking, etc) [23].”
Flexible Scheduling of Distributed Analytic Applications (2016, background): “Issues related to scheduling scalability, due to the sheer number of low-level tasks that are typically required by analytic jobs, have been addressed through a distributed design, such as in Sparrow [18] and in Condor [12].”
Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing (2014, background): “298 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’14) USENIX Association Distributed schedulers such as Omega [23] and Sparrow [22] address the scalability challenges by not relying on a centralized entity for scheduling.”
Efficient Memory Disaggregation with Infiniswap (2017, methodology): “Similar techniques had been used before for task scheduling and input selection [67, 75].”
Hopper: Decentralized Speculation-aware Cluster Scheduling at Scale (2015, methodology): “Clusters already blacklist problematic machines (e.g., faulty disks or memory errors) and avoid scheduling tasks on them.”
Large-scale cluster management at Google with Borg (2015, background): “Relaxed randomization is somewhat akin to the batch sampling of Sparrow [65] while also handling priorities, preemp-tions, heterogeneity and the costs of package installation.”
Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads (2019, background): “In contrast, in big data analytics, job execution times range from only tens of milliseconds to a few hours [11, 36, 41].”
Computation Offloading Toward Edge Computing (2019, background): “Sparrow [118] realizes a distributed and low-latency scheduling framework for large-scale data analytics, and it adopts a random sampling approach for load balancing based on the theory of “the power of two choices” [119].”
Serverless Computation with OpenLambda (2016, background): “Previous low-latency cluster schedulers (e.g., Sparrow [39]) target tasks in the 100ms range.”
The RAMCloud Storage System (2015, methodology): “2007], and Sparrow uses randomization with refinement to schedule tasks for large-scale applications [Ousterhout et al. 2013].”