Scalable and Fault-tolerant Stateful Stream Processing

Raul Castro Fernandez, Matteo Migliavacca, Evangelia Kalyvianaki, Peter R. PietzuchICCSW 2013 · DOI

TL;DR

This paper introduces a novel approach to managing state in stream processing systems (SPSs) that allows for both dynamic scaling and robust fault tolerance. By externalizing operator state and providing explicit management primitives, their system can automatically scale out bottleneck operators and recover from failures with minimal disruption, crucial for modern "big data" applications.

What Problem Does This Paper Address?

Modern applications, from social media to e-commerce, demand real-time insights from massive data streams. This necessitates stream processing systems (SPSs) that can handle enormous data volumes and adapt to fluctuating workloads, especially in cloud environments where resources are provisioned on-demand. A significant challenge arises when these stream processing queries involve "stateful operators" – operators that maintain and update information over time (e.g., counting occurrences of an item). Scaling out such operators (distributing their work across more machines) and recovering them after failures (e.g., a machine crashing) without losing or corrupting their internal state, and thus the query results, is a complex problem. Existing systems often simplify this by treating operators as stateless or by placing a heavy burden on developers to manage state manually.

Methods

The core innovation of this paper lies in externalizing operator state from the stream processing logic itself. Instead of being embedded within the operator's code, the state is managed by the SPS through a set of defined primitives. These primitives allow the SPS to:

  • Checkpoint State: Capture the current processing and buffer state of an operator.
  • Backup State: Store this checkpointed state, typically on an upstream operator, for quick recovery.
  • Restore State: Load a backed-up state onto a new operator instance, allowing it to resume processing from where the failed operator left off.
  • Partition State: Split an operator's state across multiple new, partitioned operators when scaling out.

Based on these primitives, the authors propose an integrated approach for dynamic scale-out and fault tolerance. When a bottleneck is detected (an operator slowing down the system), the SPS automatically scales it out by partitioning its state and distributing the workload. Similarly, when a VM hosting a stateful operator fails, the SPS treats this as a special case of scaling out to a single instance, restoring the operator's state from a checkpoint and replaying necessary tuples.

Datasets

The paper evaluates its approach using the Linear Road Benchmark (LRB). The LRB is a well-known benchmark for stream data management systems, simulating a real-time toll collection system. The authors use a specific implementation of the LRB query with 7 operators. They do not introduce a new benchmark but rather use an existing one to demonstrate their system's capabilities in a realistic scenario.

Key Insights and Ideas

  • Unified Approach for Scale-Out and Recovery: The most significant insight is that state management can serve as a unified mechanism for both scaling out operators and recovering from failures. This simplifies the overall system design and implementation.
  • Explicit State Management is Key: By treating operator state as an independent entity that the SPS can manipulate, the system gains fine-grained control over scaling and recovery, leading to more efficient and robust operations.
  • Automatic Adaptation: The system's ability to automatically detect bottlenecks and scale out, or to seamlessly recover from failures without manual intervention, is crucial for building truly resilient and elastic cloud-based stream processing applications.
  • Trade-offs in Checkpointing: The frequency of state checkpointing is a critical parameter. More frequent checkpoints reduce recovery time but incur higher overhead. The paper explores this trade-off, showing that their approach can achieve lower recovery times than other methods even with moderate checkpointing intervals.

Key Results

  • Effective Dynamic Scale-Out: The approach successfully scales out queries on the Amazon EC2 cloud platform to handle increasing workloads. They demonstrate scaling to a load factor of L=350 with 50 VMs on the LRB.
  • Fast Failure Recovery: Their state management approach achieves lower recovery times compared to traditional methods like source replay (SR) and upstream backup (UB). For a word frequency query, their system recovers significantly faster.
  • Manageable Latency Overhead: While state checkpointing does introduce some overhead, the paper shows that processing latency remains within acceptable limits, even for large state sizes and high input rates, confirming that the approach is practical.

Limitations and Future Work

  • Scale-In: The current approach focuses on scaling out. The authors acknowledge that supporting "scale-in" (reducing the number of VMs when the load decreases) is a natural extension for achieving truly elastic deployments.
  • Source and Sink Bottlenecks: In their LRB experiments, the source and sink components became bottlenecks at higher loads, limiting the overall throughput. This suggests that optimizing these components or their interaction with the SPS is important for achieving maximum scalability.
  • VM Model: The approach is designed for an IaaS cloud environment and assumes a VM model. Adapting it to other deployment models might require further work.

Summary updated

BibTeX
@inproceedings{fernandez2013scalable,
  author = {Raul Castro Fernandez and Matteo Migliavacca and Evangelia Kalyvianaki and Peter R. Pietzuch},
  title = {{Scalable and Fault-tolerant Stateful Stream Processing}},
  booktitle = {ICCSW},
  year = {2013},
  doi = {10.4230/oasics.iccsw.2013.11},
}
Figure