Sparrow: Distributed, Low Latency Scheduling

Abstract

📜 Abstract

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.

Description

✨ Summary

Sparrow addresses the scheduling of highly parallel jobs composed of short, sub-second tasks, where centralized schedulers can become throughput and availability bottlenecks. It proposes a stateless, decentralized architecture in which multiple schedulers independently assign work to workers using randomized probes.

The system combines two principal techniques:

Batch sampling: Instead of selecting worker machines independently for each task, a scheduler samples a larger pool for the entire job and assigns tasks to the least-loaded machines in that pool. This shares placement information across tasks and avoids the exponential degradation of per-task sampling as job parallelism increases.
Late binding: Workers place reservations rather than immediately accepting tasks. When a reservation reaches the front of a worker’s queue, the worker requests the task from the scheduler. The scheduler assigns tasks to the first workers that become ready, reducing errors caused by stale queue-length information and concurrent scheduling races.

Sparrow also supports per-job and per-task placement constraints, strict priorities, weighted fair sharing, and scheduler failover. Its design deliberately omits or approximates features such as bin packing, gang scheduling, preemption, and complex inter-job constraints in order to preserve low latency and high throughput.

In evaluation on a 110-machine Amazon EC2 cluster, Sparrow scheduled TPC-H workloads with median query response times within 12% of an idealized scheduler, achieved median queueing delays below 9 ms, and recovered from scheduler failures in under 120 ms. The experiments also found that Sparrow substantially outperformed random placement and per-task sampling, maintained approximate cluster-wide fair shares, and limited the impact of overloaded low-priority users. Performance degraded under extreme task-duration heterogeneity, particularly on machines with fewer cores, and worker failures remained outside the implemented fault-tolerance model. (people.csail.mit.edu)

The paper’s implementation was released publicly, and the accompanying project described Sparrow as a high-throughput, low-latency, fault-tolerant distributed cluster scheduler; the project also included an integration path for Spark. (github.com) The Sparrow project was subsequently presented by Berkeley’s AMPLab as an architecture for ultra-high-throughput, low-latency task scheduling for interactive cluster services. (amplab.cs.berkeley.edu)

Later research has cited or evaluated Sparrow as a representative decentralized scheduling architecture. For example, work on eventually consistent federated scheduling compares its design against Sparrow and other decentralized schedulers, while a later survey identifies Sparrow’s late-binding approach as a technique used in bandwidth-aware distributed analytics scheduling. (arxiv.org) These references indicate continued influence on research into decentralized cluster scheduling and low-latency task placement. The sources reviewed did not establish a specific large-scale commercial production deployment of Sparrow itself.