A Survey on the Evolution of Stream Processing Systems

Marios Fragkoulis; Paris Carbone; Vasiliki Kalavri; Asterios Katsifodimos

Source-linked AI summary

A Survey on the Evolution of Stream Processing Systems

Marios Fragkoulis, Paris Carbone, Vasiliki Kalavri, Asterios Katsifodimos

arXiv:2008.00842v2Aug 3, 2020cs.DCcs.CLcs.DBcs.PF

TL;DR

Stream processing still lacks clear, field-specific definitions for availability and faces unresolved trade-offs in ordering architectures. The survey synthesizes the field’s evolution, finding shifts toward persistent state, passive replication, exactly-once state semantics, elasticity, and backpressure, while identifying open problems around availability and out-of-order processing.

Problem
Stream processing lacks a suitable definition and metric for high availability, while the choice between out-of-order and in-order architectures remains open.
Method
The paper surveys stream processing research across ordering, state, fault tolerance, availability, load management, elasticity, and reconfiguration.
Results
Modern streaming systems have shifted toward scalable persistent state, passive replication, exactly-once state processing, elasticity, and backpressure coupled with persistent inputs.
Takeaways & Limitations
Transactional stream processing has expanded streaming beyond data analytics, while availability contracts could improve production deployment but affect resource use, performance, recovery, and consistency.
Takeaways & Limitations
High availability has no established definition in the literature, and out-of-order processing remains difficult because revision processing can require substantial state.

Abstract

from arXiv · show

Stream processing has been an active research field for more than 20 years, but it is now witnessing its prime time due to recent successful efforts by the research community and numerous worldwide open-source communities. This survey provides a comprehensive overview of fundamental aspects of stream processing systems and their evolution in the functional areas of out-of-order data management, state management, fault tolerance, high availability, load management, elasticity, and reconfiguration. We review noteworthy past research findings, outline the similarities and differences between early ('00-'10) and modern ('11-'22) streaming systems, and discuss recent trends and open problems.

1 Introduction

Stream processing has evolved from early database-oriented prototypes into modern distributed engines used across diverse industries and cloud deployments. This survey traces that evolution, compares early and modern systems, and establishes common terminology across generations.

1 Introduction: Stream processing now supports diverse applications, including dynamic car-trip pricing, credit-card fraud detection, real-time harvesting analytics, event-driven architectures, and continuous ETL.Cloud vendors widely offer managed stream-processing pipelines, extending use beyond classic windows, aggregates, and joins.
1 Introduction: Early systems extended database execution with streaming concepts, whereas later systems shifted toward distributed, data-parallel processing on commodity shared-nothing clusters.Early prototypes differed in querying semantics despite broadly agreeing on the data model; modern systems exposed hard-coded dataflow primitives.
1 Introduction: The survey focuses on evolution over time, explaining why some early designs persisted, others disappeared, and related ideas were reinvented in modern systems.It also reconciles terminology used by different generations of streaming systems.
1.1 Contributions: The survey examines streaming-system evolution across out-of-order management, state, fault tolerance, high availability, load management, elasticity, and reconfiguration.It categorizes early and modern processors by assumptions and mechanisms and compares their approaches across these functional areas.
1.2 Related surveys and research collections: The survey excludes theoretical foundations of streaming data management and algorithms, directing readers to a separate collection covering those topics.Its scope instead centers on system design, evolution, and operational functionality.

2 Preliminaries

Stream processing handles continuously arriving, potentially unbounded data under limited memory, uncertain order, and continuously updated results. Early relational systems and modern dataflow systems differ in their models and architectures, while modern engines add explicit state and fault tolerance.

2 Preliminaries: A data stream is produced incrementally over time and may be high-volume, real-time, and unbounded, requiring on-the-fly processing with limited memory.Streaming systems cannot store the entire stream accessibly or control its arrival rate and order.
2 Preliminaries: Continuous queries ingest events and produce results continuously, often requiring compact sketches or synopses to retain and update historical information efficiently.These requirements distinguish streaming queries from processing a complete static dataset.
2 Preliminaries: Streaming systems must produce correct results for delayed or out-of-order data, estimate progress, reason about completeness, and support long-running execution.Low latency and high throughput are necessary but not sufficient requirements.
2 Preliminaries: First-generation systems modeled streams relationally as changing relations, while second-generation dataflow systems generally impose timestamps without requiring strict input schemas or relational semantics.STREAM and TelegraphCQ used timestamped tuple models, whereas Flink and Dataflow use declared time domains or logical timestamps.
2 Preliminaries: Modern distributed dataflow systems use task and data parallelism, explicit state management, fault tolerance, and disjoint stream partitions on shared-nothing clusters.Queries are independently submitted jobs with dedicated resources, replayable inputs, and persisted state.

3 Managing Event Order and Timeliness

Stream order is part of stream semantics, yet tuples commonly arrive out of order, making disorder management fundamental to semantically correct processing. The survey organizes this topic around disorder, progress, architectures, consequences, and management mechanisms.

3 Managing Event Order and Timeliness: Streaming systems may need to process tuples in a particular order for semantically correct results, although tuples generally arrive out of order.Out-of-order arrival occurs when tuples with later event-time timestamps arrive first.
3 Managing Event Order and Timeliness: The survey uses disorder and out-of-order to denote disturbed tuple order and treats reasoning about order as fundamental to streaming-system operation.The section distinguishes causes, progress, architectures, consequences, and management mechanisms.

3.1 Causes of Disorder

Disorder arises from external stochastic factors and from stream operations that alter tuple order. Network behavior is a common external source, while joins, windowing, and prioritization can reorder data inside the system.

3.1 Causes of Disorder: Disorder may result either from stochastic factors external to the streaming system or from operations performed inside it.The survey treats both sources as causes requiring explicit analysis.
3.1 Causes of Disorder: Network reliability, bandwidth, and load can delay routed tuples differently, producing a different arrival order in the streaming system.Merging inputs from multiple sources can also create a disordered collection even when each individual source preserves order.
3.1 Causes of Disorder: Join processing, attribute-based windowing, and data prioritization can reorder tuples during stream processing.Parallel joins repartition data by join attribute and emit results by match order; windowing or prioritization on another attribute disrupts the ordering attribute.

3.2 Disorder and Processing Progress

Streaming systems track processing progress to determine how far they have advanced through a stream and to manage disorder. Progress can be quantified using an ordering attribute and the smallest value among unprocessed tuples.

Disorder management and progress tracking are intertwined because systems need progress information to manage out-of-order data.
Progress measures how far processing has advanced, using an attribute A that orders the stream.The stream progresses when the smallest A value among unprocessed tuples increases over time.

3.3 System Architectures for Managing Disorder

Streaming systems use two main architectures to manage disorder: in-order processing fixes stream order, while out-of-order processing accepts tuples without waiting when they meet a lateness bound.

The two architectures differ in whether disorder is handled by fixing stream order or by propagating progress information to admit late tuples.
In-order systems buffer and reorder tuples up to a lateness bound before forwarding them for processing.They track progress by monitoring how far stream processing has advanced, then clear the corresponding buffers.
Out-of-order systems process tuples in arrival order without delay when they do not exceed a lateness bound.Operators or a global authority propagate progress information that typically reflects the oldest unprocessed tuple.

3.4 Effects of Disorder

Disorder can impede progress or produce incorrect results when streaming computations require ordered or complete input. Managing lateness therefore requires balancing correctness against waiting and state accumulation.

Disorder can impede progress or lead to wrong results when it is ignored in unbounded data processing.
Ordered joins and aggregates may require reordering out-of-order tuples, which adds processing overhead, memory overhead, and latency.
Ignoring late data can produce incorrect results, but waiting indefinitely can block output and accumulate large computation state.

3.5 Mechanisms for Managing Disorder

Streaming systems manage disorder with mechanisms that track or bound lateness, communicate progress, and revise results when late tuples arrive. These mechanisms range from slack and heartbeats to low-watermarks, pointstamps, punctuations, and triggers.

3.5 Mechanisms for Managing Disorder: Triggers update computation results when tuples arrive after the lateness bound, while slack only quantifies that bound and heartbeats, low-watermarks, and pointstamps track progress.
3.5.1.1 Slack: Slack provides a fixed grace period for late tuples by waiting for out-of-order data according to a configured metric.The metric may be the number of intervening tuples or elapsed time.
3.5.1.2 Heartbeats: Heartbeats carry timestamps indicating that subsequent tuples will have larger timestamps and can be generated by sources or inferred from system parameters.An input manager buffers and orders tuples, then dispatches tuples up to the heartbeat timestamp.
3.5.1.3 The low-watermark: Low-watermarks track processing progress through the lowest value of an attribute and admit out-of-order data whose value is not smaller.They can also support removing state once older work is no longer pending.
3.5.1.4 Punctuations: Punctuations are metadata annotations embedded in streams that communicate progress information, including low-watermarks, event-time skew, and slack.They can also communicate that tuples with attribute values below a threshold will cease to appear.
3.5.2 Tracking progress of out-of-order data in cyclic queries: Pointstamps and frontiers track progress across dataflow locations and can support arbitrary iterative and nested computations.Frontier notifications identify when unprocessed events can be delivered, while removed pointstamps correspond to no remaining unprocessed events.
3.5.2 Tracking progress of out-of-order data in cyclic queries: Cyclic queries require special progress handling because binary operators may block until matching progress information arrives on both input channels.

3.6 1st generation vs. 2nd generation

Early stream systems buffered and reordered tuples, while later out-of-order processing tracked progress without requiring tuple ordering. This shift improved throughput, latency, and scalability for window operations.

Out-of-order processing improved throughput, latency, and scalability for window operations by tracking processing progress without ordering tuples.
Early approaches buffered and reordered arriving tuples using measures of data frequency and lateness.
Revision processing was subsequently proposed to reconcile out-of-order tuples.

3.7 Open Problems

The survey identifies unresolved challenges in managing disorder across architectures, time domains, and source progress. These include architecture trade-offs, unsupported multiple time domains, and unaligned watermarks.

Choosing between in-order and out-of-order architectures remains open because each incurs distinct resource, correctness, or complexity costs.Out-of-order designs face implementation, maintenance, and revision-state challenges, whereas in-order designs are resource-hungry and can lose late events.
Streaming systems cannot yet support multiple time domains for applications receiving streams with different event-time notions.
Disparate source latencies can produce unaligned watermarks, making processing-progress tracking challenging.

4 State Management

State management spans state programmability, responsibility, architecture, persistence, and reconfiguration. The field has progressed from specialized internal state toward user-defined state managed through system mechanisms for persistence, scalability, and fault tolerance.

State management covers declaration, scaling, partitioning, persistence, and guarantees maintained during system changes.
4.2 Programmability & Responsibility: State programmability means allowing users to define state, such as a counter held in a stateful map function.
4.2.1 Discussion: Early systems used designer-defined summaries for relational operators, but limited user-defined state restricted expressiveness and hindered reconfiguration.
4.2 Programmability & Responsibility: Modern stateful APIs let users define custom state while giving systems access for persistence, scalability, and fault tolerance.
4.3 State Management Architecture: Stateful runtimes use in-memory, out-of-core, or external architectures with different capacity, modularity, latency, and storage trade-offs.
4.4 Persistence Granularity: Persistence ranges from epoch-level snapshots to batch-level micro-batching and record-level state-transition storage.

4.6 Managing Consistency and Persistence

Stream processors manage consistency by persisting state at event or epoch granularity, using transactional commits and snapshotting to recover from failures and support reconfiguration. These designs trade commit and runtime overhead against recovery speed, deterministic execution, and reconfiguration flexibility.

Managing Consistency and Persistence: Consistent stream processing remains challenging because distributed unbounded computation lacks a formal problem specification and must accommodate failures and operational changes.Reconfiguration includes software updates and scaling to additional compute nodes without loss of accuracy or computation.
State Persistence at Event Granularity: Per-event persistence atomically commits each action, guaranteeing deterministic executions and exactly-once processing for applications consuming the output.Millwheel commits input events, state transitions, and generated output as a full compute action using BigTable.
State Persistence at Epoch Granularity: Epoch-level persistence atomically commits the task graph after each mini-batch, enabling rollback to a previously committed epoch after failure or reconfiguration.Epochs are marked in the logged input, and exactly-once processing applies to each atomically committed epoch.
Strict Two-Phase Epoch Commits: Strict two-phase epoch commits separate epoch processing from state persistence but can reduce task utilization because synchronous tasks wait for one another.Drizzle improves utilization by chaining multiple epochs into a single atomic commit.
Asynchronous Two-Phase Epoch Commits: Unaligned snapshots favor runtime performance but require redo during recovery, whereas aligned snapshots increase commit time while reducing recovery and reconfiguration costs.Aligned snapshots capture complete epochs, support snapshot-isolated queries, and provide the basis for live reconfiguration during alignment.
State Persistence at Epoch Granularity: Modern stream processors execute long-running graphs with user-defined state that is system-managed, fault-tolerant, reconfigurable, and governed by transactional guarantees.This evolution extends earlier systems that internally materialized operator summaries and other in-memory structures.

5 Fault Tolerance & High Availability

Fault tolerance is essential because streaming systems maintain state over unbounded, often vanished input and operate across failure-prone distributed infrastructure. The survey compares recovery strategies, distinguishes state from output exactly-once semantics, and identifies unresolved challenges in defining, measuring, and configuring high availability.

5.4 Open Problems: High availability lacks a stream-processing-specific definition and suitable metric, motivating progress-based measurement and configurable availability contracts.The proposed direction relates availability to processing progress, while configuration may affect utilization, overhead, recovery time, and consistency.
5.1.1 The output commit problem: Exactly-once state semantics can still produce duplicate outputs after recovery, whereas output exactly-once requires reproducing failure-free externally visible results.The distinction arises because published output cannot generally be restored like internal state.
5.1 Fault-tolerance: Passive replication with stored state is the dominant fault-tolerance pattern, typically restoring a checkpoint and replaying post-checkpoint input.Storing in-flight tuples is less preferred than in the past.
5.1.1 The output commit problem: Output-commit solutions are grouped into transaction-based, progress-based, and lineage-based techniques, while special and external sinks provide practical but non-specification-compliant alternatives.The categories identify repeated tuples using identity, order, or input-output dependencies.
5.2 High availability: Passive replication requires longer recovery than active replication but incurs 90% less overhead because its checkpoint size is reduced.A checkpoint mechanism preserves output tuples until downstream acknowledgments before trimming them and checkpointing.
5.2 High availability: Hybrid replication saves 66% recovery time versus passive replication and produces 80% less message overhead than active replication.The approach normally runs passively and switches to a pre-deployed active copy during transient failure.
5.4 Open Problems: Open problems include better output-commit solutions, definitions and measurements of availability, and availability configuration for different application requirements.Existing output-commit approaches face computational cost, strong assumptions, limited applicability, and freshness constraints.

6 Load management, elasticity, & reconfiguration

Stream processing systems manage variable workloads through load shedding, flow control, elasticity, and reconfiguration. Modern approaches increasingly preserve correctness while adapting resources and runtime behavior, but general self-management remains open.

6.1 Load shedding: Load shedding sustains performance by dropping excess tuples, trading result accuracy for latency when applications tolerate approximation.Systems monitor overload and selectively drop tuples according to a QoS specification.
6.3 Elasticity: Elasticity adjusts resource allocation to variable load while preserving result correctness and can also avoid idle resources when demand decreases.Dynamic scaling applies in centralized and distributed settings.
6.1 Load shedding: Load shedding decisions must detect overload accurately and choose where, which, and how many tuples to drop, because poor choices degrade results or waste computation.Early dropping avoids wasted work but may affect result quality; strategies include operator-restricted, window-aware, and semantic approaches.
6.2 Load-aware scheduling and flow control: Back-pressure and flow control buffer, schedule, regulate, or throttle excess load without sacrificing accuracy during transient bursts.Credit-based flow control signals available receiver buffer space to senders and is implemented in Apache Flink.
6.3.1 Elasticity policies: Scaling policies separate symptom detection from cause identification and scaling-action selection, making automatic scaling challenging despite commercial and research implementations.Users otherwise face a trade-off between provisioning for peak demand and risking degraded performance.
6.5 Open Problems: Reconfiguration extends elasticity beyond resource allocation to code updates, plan switching, scheduling, placement, and skew mitigation, but these scenarios remain largely studied in isolation.Future systems need to account for interactions among optimizations to provide general self-management.

7 Conclusion

Modern stream processors have shifted from centralized, approximate relational extensions toward distributed systems emphasizing correctness, scalable persistent state, and transactional guarantees. The survey concludes that emerging applications will require further advances in reconfiguration, transactions, iteration, hardware use, and state management.

Conclusion: Modern streaming systems primarily emphasize correct results, general-purpose languages, distributed execution, and data, pipeline, and task parallelism.The survey contrasts these characteristics with early systems’ approximate results and centralized execution.
Conclusion: State management underwent major changes toward scalable, partitioned, persistent state with transactional guarantees comparable to modern database systems.These advances extend streaming beyond analytics and open research directions for managing unbounded state.
Conclusion: Stream state and compute are gradually decoupling, enabling storage interoperability, optimization opportunities, and semantics for shared and external state.The survey connects this direction to continuous applications and live scalable data services.
Conclusion: Future streaming systems are expected to address cloud services, machine learning, graph analytics, next-generation hardware, transactions, iteration, reconfiguration, shared state, and versioning.Workload-aware backends are identified as one direction for advancing state management.