Scheduling Storms and Streams in the Cloud

Javad Ghaderi, Sanjay Shakkottai, Rayadurgam Srikant

TL;DR

This paper tackles the challenge of efficiently scheduling dynamic graph-based computations (like those in streaming data processing) on cloud clusters. They introduce a novel, low-complexity randomized algorithm that minimizes data transfer costs and queue lengths without interrupting ongoing tasks, offering a tunable trade-off between performance and resource utilization.

What Problem Does This Paper Address?

Modern cloud computing is increasingly driven by real-time, streaming data applications. These applications are often modeled as graphs, where nodes represent computational tasks and edges represent data flow between them. When these "jobs" (graphs) arrive dynamically in a cloud cluster, a scheduler must decide how to partition and distribute the graph's nodes across the available servers. A key challenge is minimizing the "partitioning cost," which arises from data needing to travel between servers (broken edges). Existing solutions are often heuristic or computationally expensive, and critically, many can interrupt ongoing jobs to reconfigure the system. This paper aims to develop a scheduling algorithm that is efficient, stable, and crucially, avoids service preemptions while managing this dynamic graph partitioning problem.

Methods

The authors propose a new class of low-complexity randomized scheduling algorithms. Instead of relying on traditional, computationally intensive methods like Gibbs sampling or frame-based Max Weight algorithms (which can lead to service interruptions), their approach uses a randomized strategy.

Key elements of their method include:

  • Templates: A "template" represents a specific way to partition and map a graph onto the cluster's servers. The algorithm works with a set of these templates.
  • Random Partition Procedure: When a new graph arrives, a potential template is generated randomly from the set of feasible templates.
  • Probabilistic Template Management: The decision to add or discard a newly generated template is made probabilistically, based on a calculated "weight" that balances queue lengths and partitioning costs.
  • No Service Interruptions: The algorithm's updates (adding or removing templates) occur only at job arrival or departure events, ensuring that ongoing computations are not disrupted.
  • Modified Energy Function: Unlike Gibbs samplers that minimize Gibbs energy, their approach minimizes a modified energy function that replaces the entropy term with relative entropy, drawing inspiration from loss systems.

Datasets

Not discussed in the paper. The paper focuses on a theoretical model and algorithmic development, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Avoiding Service Preemptions is Crucial: The paper highlights the significant operational cost and disruption caused by migrating jobs for system reconfiguration. Their algorithm's ability to avoid this is a major practical advantage.
  • Randomization as a Scalable Solution: By using a randomized approach to explore the vast space of possible graph partitions, they achieve low complexity without sacrificing performance significantly.
  • Trade-off Management: The algorithm offers a tunable trade-off between minimizing average partitioning cost and average queue lengths, allowing operators to prioritize based on system needs.
  • Loss System Analogy: The connection to loss systems provides a theoretical foundation for their algorithm's limiting behavior and helps in understanding the invariant measure.
  • "Virtual Templates": The concept of virtual templates (reserved slots for potential future jobs) is a clever mechanism to manage dynamic arrivals and departures without immediate service interruption.

Key Results

The paper presents theoretical guarantees for their proposed Dynamic Graph Partitioning (DGP) algorithm.

  • Stability: The algorithm is shown to stabilize the system under certain load conditions.
  • Performance Bounds: They derive bounds on the average queue size and average partitioning cost. These bounds demonstrate a trade-off controlled by algorithm parameters (like $\alpha$ and $\beta$).
  • Asymptotic Optimality: As a parameter ($\beta$) approaches zero, the algorithm's partitioning cost approaches the optimal static partitioning cost, albeit with potentially larger queue sizes.
  • Low Complexity: The algorithm is designed to have low computational complexity, making it suitable for dynamic, real-time environments.

Limitations and Future Work

  • Theoretical Focus: The paper primarily presents theoretical analysis and algorithmic design. While it provides performance bounds, empirical validation on real-world streaming systems like Storm would be valuable.
  • Parameter Tuning: The performance of the algorithm depends on carefully chosen parameters (e.g., $\alpha, \beta, \epsilon, h$). Identifying optimal parameter settings for different workloads and cluster configurations is a practical challenge.
  • Assumptions: The model assumes Poisson arrivals and exponential service times, which are standard but might not perfectly capture all real-world scenarios.
  • Future Work: The authors suggest exploring alternative algorithms, such as those using dedicated Poisson clocks for each queue, and further investigating the impact of parameter choices on performance. They also mention the potential for extending the model to more complex network topologies and resource constraints.

Summary updated

Abstract

Motivated by emerging big streaming data processing paradigms (e.g., Twitter Storm, Streaming MapReduce), we investigate the problem of scheduling graphs over a large cluster of servers. Each graph is a job, where nodes represent compute tasks and edges indicate data-flows between these compute tasks. Jobs (graphs) arrive randomly over time, and upon completion, leave the system. When a job arrives, the scheduler needs to partition the graph and distribute it over the servers to satisfy load balancing and cost considerations. Specifically, neighboring compute tasks in the graph that are mapped to different servers incur load on the network; thus a mapping of the jobs among the servers incurs a cost that is proportional to the number of "broken edges''. We propose a low complexity randomized scheduling algorithm that, without service preemptions, stabilizes the system with graph arrivals/departures; more importantly, it allows a smooth trade-off between minimizing average partitioning cost and average queue lengths. Interestingly, to avoid service preemptions, our approach does not rely on a Gibbs sampler; instead, we show that the corresponding limiting invariant measure has an interpretation stemming from a loss system.
BibTeX
@inproceedings{ghaderi2015scheduling,
  author = {Javad Ghaderi and Sanjay Shakkottai and Rayadurgam Srikant},
  title = {{Scheduling Storms and Streams in the Cloud}},
  booktitle = {SIGMETRICS},
  year = {2015},
  doi = {10.1145/2745844.2745882},
}
Figure