For years, big data architectures were constrained by the dualism of the Lambda Architecture (Nathan Marz): pairing an accurate but slow batch layer (Hadoop/MapReduce) with a low-latency but inaccurate streaming layer (Storm). In 2015, Tyler Akidau et al. at Google published “The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing”. Grounding what became Apache Beam and Apache Flink, the Dataflow model dismantled the artificial boundary between batch and streaming, providing an exact mathematical framework for reasoning about stateful computations over unbounded streams using Event Time, Watermarks, and Distributed State Snapshots.
1. The Four Fundamental Questions of Stream Processing
Akidau formalized stream processing by decoupling pipeline logic across four independent axes:
- What is being computed? (Transformations: sum, average, histogram).
- Where in event time is it being computed? (Windowing: tumbling, sliding, session).
- When in processing time are results materialized? (Watermarks and Triggers).
- How do those results relate to previously materialized results? (Accumulation: discarding, accumulating, accumulating & retracting).
2. The Dual-Time Horizon: Event Time vs. Processing Time
A fatal flaw of early stream processors was evaluating streaming data based on Processing Time—the local wall-clock time of the computing server when the event arrived at the pipeline. Because mobile devices experience offline buffering, flaky wireless networks, and distributed queuing delays, the difference between physical real-world event generation and pipeline arrival is non-deterministic:
$$text{Time Skew: } Delta(e) = t_{text{processing}}(e) – t_{text{event}}(e)$$
In distributed streams, $Delta(e)$ follows a heavy-tailed, unpredictable probability distribution. Evaluating financial fraud or analytics against processing time yields fundamentally incorrect results: network spikes distort hourly aggregates. Event Time—the immutable timestamp embedded in the record when the event occurred in the physical universe—is the only time domain that guarantees computational correctness.
3. Watermarks: The Assertion of Completeness
If streams arrive out of order, how can an operator ever know that all events for a given time window $[t_0, t_1)$ have arrived, so that it can safely emit a final aggregate? The answer is the Watermark.
A Watermark $W(t) in mathbb{R}$ is a monotonically advancing timestamp emitted into the data stream that establishes a temporal boundary:
$$forall e text{ arriving after } W(t), quad t_{text{event}}(e) > W(t)$$
When an operator processing a 10-minute window $[12:00, 12:10)$ receives a watermark $W ge 12:10$, it knows that no further events belonging to that window will ever arrive. It can now compute the final aggregate, trigger downstream state emission, and garbage-collect window state.
Heuristic Watermarks & Late Data
In real-world networks, unbounded delays make perfect watermarks impossible without waiting indefinitely. Systems employ Heuristic Watermarks based on statistical network delay models:
$$W(t) = max_{e in text{Observed}} { t_{text{event}}(e) } – delta_{text{lag}}$$
If an event arrives with $t_{text{event}}(e) le W(t)$, it is classified as Late Data. Advanced streaming runtimes do not drop late data; instead, configurable Triggers emit refined updates or Retractions to correct previously emitted window values.
4. Windowing Topologies
Windowing partitions unbounded streams into finite temporal slices for aggregation:
- Tumbling (Fixed) Windows: Disjoint, non-overlapping contiguous slices $[t, t + Delta)$.
- Sliding (Hopping) Windows: Overlapping slices of fixed duration $Delta_{text{size}}$ advancing by slide interval $Delta_{text{slide}} < Delta_{text{size}}$.
- Session Windows: Dynamic, data-driven windows defined by periods of user inactivity (e.g. 30 minutes of silence). Replicas merge adjacent windows dynamically as late events bridge temporal gaps.
5. Fault Tolerance: Chandy-Lamport Distributed State Snapshots
Modern stream processing engines maintain gigabytes of state in local RocksDB instances. To achieve Exactly-Once Processing (EOP) across machine crashes without expensive distributed locks, Apache Flink implements an asynchronous variant of the Chandy-Lamport Algorithm (1985):
- A centralized coordinator injects special Checkpoint Barrier markers $S_k$ into the source data streams.
- Barriers flow strictly inline with data records without stalling pipeline execution.
- When an operator receives barrier $S_k$ from all input channels (barrier alignment), it takes a non-blocking asynchronous snapshot of its local state and flushes it to durable storage (GCS/S3).
- Upon failure, the entire cluster rolls back to checkpoint $S_k$ and replays offsets from the upstream commit log, guaranteeing deterministic, exactly-once state semantics.
