Streaming data

The Dataflow model#

Akidau et al. (2015), The Dataflow Model, VLDB, is the reference formalisation and reframes the batch/stream distinction as unnecessary. Four questions define any computation:

1. What results are computed — the aggregation.
2. Where in event time — the windowing function.
3. When in processing time results are emitted — triggers.
4. How refinements relate — accumulation mode: discarding, accumulating, or accumulating-and-retracting.

Batch is the special case where the trigger fires once, at the end. This decomposition is why the developer example can express both event-time and arrival-time windowing with the same aggregation.

Windowing functions#

A windowing function maps each element to a set of windows:

$$ \text{AssignWindows} : (k, v, t) \;\mapsto\; {\,w_1, \dots, w_m\,} $$

• Tumbling — fixed, non-overlapping, of width $T$. Each element lands in one window; storage is $O(1)$ per key.
• Sliding — width $T$, period $P < T$. Each element lands in $\lceil T/P \rceil$ windows; storage grows proportionally.
• Session — dynamic, defined by a gap $g$. Windows merge when a new element bridges them, so session windows are data-dependent and require merge support in the runner.

Sliding windows are the usual cause of unexpected state growth. A 24-hour window sliding every minute puts every element into 1,440 windows.

Watermarks#

A watermark is a monotonically non-decreasing function $W(t_p)$ from processing time to event time, asserting that no element with event time below $W(t_p)$ will be observed after processing time $t_p$.

Two regimes:

• A perfect watermark requires complete knowledge of the source and is available only for bounded or strictly ordered inputs.
• A heuristic watermark estimates the bound from observed lateness, source partition progress, or a fixed allowance. It can be wrong in both directions, producing late data when too aggressive and latency when too conservative.

The fundamental trade-off is unavoidable: completeness, latency and cost — pick two. Triggers decouple the three by allowing early speculative emissions before the watermark, an on-time emission at the watermark, and late refinements after it.

Kafka Streams takes a different route with a grace period per window and no global watermark, since partition-local ordering plus a bounded grace covers most cases at lower coordination cost.

Accumulation and correctness#

When a window emits more than once, downstream consumers must know how to combine emissions:

• Discarding — each emission covers only elements since the last. Downstream must sum. Suits an idempotent additive sink.
• Accumulating — each emission is the current total. Downstream must overwrite. Requires an upsert-capable sink, which is the idempotency property from ETL for machine learning.
• Accumulating and retracting — emits a retraction of the previous value alongside the new one. Necessary when the downstream aggregation is not invertible, for example when feeding a top-k that must remove the stale entry.

Choosing accumulating mode with an append-only sink is a common and quiet corruption: every refinement adds a row and the totals inflate.

Exactly-once, restated#

As in the batch case, exactly-once delivery is unachievable; exactly-once effect is achievable through idempotent writes or transactional sinks with a two-phase commit. Flink implements the latter via distributed snapshots (Carbone et al., 2015, Lightweight Asynchronous Snapshots for Distributed Dataflows), an adaptation of the Chandy-Lamport algorithm: barriers flow with the data, and operator state is checkpointed consistently without halting the stream.

Recovery restores the last complete checkpoint and replays from the recorded source offsets. Correctness therefore requires a replayable source — a log with retention, not a queue that discards on acknowledgement. This is the architectural reason Kafka's log-with-offsets model displaced traditional message queues for this workload.

Stream-table duality#

A stream of changes and a table of current state are two views of the same information (Kreps, 2013). A table is the fold of a stream; a stream is the changelog of a table:

$$ \text{table}{t} \;=\; \text{fold}\big(\oplus,\; \text{table}{0},\; \text{stream}_{[0,t]}\big) $$

This duality is what makes change data capture — reading a database's write-ahead log as a stream — and materialised views over streams the same mechanism. It is also the cleanest justification for event sourcing as a storage design: the log is the truth, and every table is a derived, recomputable projection.

Consequences for machine learning#

1. Label maturity. A label defined over a window is not final until the watermark passes. Training on fully matured labels while serving on immature ones is a form of leakage that offline evaluation cannot detect.
2. Feature freshness against correctness. The freshest feature is computed before late data arrives and is therefore wrong; the correct feature is stale. Quantify the trade for your specific lateness distribution rather than assuming one end.
3. Backfill asymmetry. Reprocessing history from a log has no lateness, since everything is already there. A model trained on backfilled features sees a cleaner world than production, and will overperform offline. Simulate the watermark during backfill.
4. Concept drift. Streams shift under you. Continuous evaluation on a delayed-label holdout is the only reliable detector. See monitoring and model drift.

Reading#

• Akidau et al., The Dataflow Model, VLDB 2015 — research.google/pubs/pub43864/
• Akidau, Chernyak and Lax, Streaming Systems, O'Reilly 2018 — the book-length version, and the best treatment available.
• Carbone et al., Lightweight Asynchronous Snapshots for Distributed Dataflows, 2015 — arxiv.org/abs/1506.08603
• Kreps, Narkhede and Rao, Kafka: a Distributed Messaging System for Log Processing, NetDB 2011.
• Kleppmann, Designing Data-Intensive Applications, O'Reilly 2017 — chapter 11.

What to learn next#

• Building a data pipeline — assembling everything in this section into one runnable thing.
• Feature stores — the point-in-time rule, seen from the feature side.
• What is time series data? — modelling data that arrives in order.