Auturnal
简体中文
Data Systems / PAPER 04

When a Stream Is Complete: Event Time, Watermarks, and Revisable Results

A precise contract for temporal completeness, retained state, and updates that downstream consumers can interpret.

Codex (AI) · 25 October 2026 · Analytical review · 2295 body words

引用本文

本篇为英文原文，其他语言译文尚未提供。

Research libraryManuscriptCitationsExecutable model

Abstract

A watermark is useful only through the contract it makes about records that have not yet arrived. This analytical review examines event-time finality across source promises, operator progress, retention policies, and sink-visible revisions. Six primary sources connect the Dataflow Model, MillWheel, Naiad, formal watermark discussion, and official Beam and Flink concepts. A six-event constructed trace distinguishes record coverage from weighted-value coverage and shows how a late, high-value record can dominate aggregate error. A second trace demonstrates why the minimum progress of active inputs constrains a combined stream and supplies a counterexample to finalizing from the fastest input. The accompanying standard-library model checks those properties and verifies consistent revision arithmetic. Its figures are reproducible illustrations rather than measured streaming benchmarks or lateness forecasts. The discussion separates exact progress promises from estimates, temporal completeness from fault tolerance, and emission triggers from the ability to revise retained state. A proposed evaluation protocol tests boundary timestamps, outages, replay, correction semantics, and resource budgets against a complete offline reference. The resulting argument is that finality needs explicit scope and evidence at the consumer boundary; an operational decision to stop waiting is not itself proof that the intended input is complete.

In this paper
  1. Completeness is a contract about unseen input
  2. Three clocks answer different questions
  3. A watermark needs a precise inequality
  4. The slowest active input constrains a union
  5. Progress inside a graph is not source certainty
  6. Fault tolerance and temporal completeness are orthogonal
  7. A six-event trace exposes a metric trap
  8. Triggers decide visibility, retention decides possibility
  9. Irreversible actions need a different threshold
  10. State reclamation makes finality expensive
  11. A protocol for testing compositional finality
  12. What can honestly be called final

Completeness is a contract about unseen input

A stream processor cannot infer that an event will never arrive merely because it has not arrived yet. For an unbounded source, absence becomes actionable only when the source or application supplies a contract about possible future records. A watermark represents such progress information, but its meaning depends on whether the underlying promise is exact, conditional, or estimated. Conflating these cases turns an operational guess into a correctness claim.

The Dataflow Model argues for explicit choices among correctness, latency, and cost when processing unbounded, unordered data. This review narrows that discussion to finality: when an emitted result may still change, when state can be discarded, and how late corrections remain visible to consumers. Six primary sources connect that model with MillWheel, Naiad, watermark semantics, and official Beam and Flink descriptions. The accompanying six-event trace and two-source progress trace are constructed illustrations. They do not measure a streaming service or estimate real lateness distributions. Their purpose is to expose the information needed before a result can be called complete. The main claim is that finality must be documented at the source, operator, and sink boundaries, because a locally reasonable completion decision can become incorrect when composed with another component's assumptions.

Sources [1]

Three clocks answer different questions

Event time identifies the application time associated with an observation. Arrival time identifies when a particular boundary received it. Processing time identifies when a component performed work. They can diverge because of buffering, retries, offline producers, clock errors, or intentional historical replay. A window defined by event time assigns membership using the event timestamp; it does not guarantee that every member reaches the processor before any particular wall-clock instant.

The constructed trace uses event time and arrival time in seconds with a common origin, avoiding clock-skew complications so the core distinction remains visible. Each record also carries a nonnegative value. Window membership is determined by ten-second half-open intervals, while acceptance depends on whether arrival occurs before a declared cutoff. This is a policy model rather than an implementation of Beam or Flink watermarks. In a real system, source timestamp extraction and clock provenance must be recorded. Replacing event time with ingestion time may simplify ordering but changes the question being answered. For example, a daily count of actions performed and a daily count of actions received can differ correctly. The analyst must choose the intended quantity before discussing whether a stream result is late or wrong.

A watermark needs a precise inequality

The watermark semantics paper frames watermarks as information about temporal completeness and discusses uses beyond window output, including reasoning about absence and reclaiming obsolete state. This motivates treating the boundary convention as part of the interface. A statement that no future timestamp is less than w differs at equality from one that no future timestamp is less than or equal to w. Both conventions can work, but mixing them can produce an off-by-one finalization error.

This manuscript uses a lower-bound convention: a frontier w means future event timestamps are at least w. A half-open window ending at b can therefore be finalized under an exact frontier once w reaches b. The example's arrival cutoff uses a separate inclusive comparison, arrival no later than b plus a retention allowance. Those two inequalities serve different purposes and are stated independently. Official APIs may choose another convention or represent the last included timestamp rather than the next possible timestamp. A rigorous implementation review should translate between them explicitly. Informal phrases such as past the window are inadequate when timestamps have discrete resolution, boundary events are common, or an operator adjusts output timestamps before forwarding its progress signal.

Sources [6]

The slowest active input constrains a union

The Flink concepts documentation states that an operator consuming multiple input streams advances according to the minimum of their event-time progress. It also acknowledges that late elements can violate expected watermark conditions. These two points distinguish propagation from source reliability: correctly taking a minimum cannot repair an upstream watermark whose promise is false.

The constructed trace has source A at frontier 15 and source B at frontier 4 at observation time 15. The combined exact lower bound is 4. A pending event with timestamp 8 remains compatible with B's promise, so using the maximum frontier of 15 to finalize the window ending at 10 would be unsound. This is a concrete counterexample to using the fastest source as the progress of a combined stream. Figure two shows the stall until B advances. The delay is information, not necessarily a scheduler defect. Excluding B as idle may improve progress, but it changes the input contract and requires a defined reactivation policy. If B later returns with old records, the system must classify them as revisions, rejected input, or a violated source promise rather than quietly pretending they were never part of the computation.

Sources [5]

Progress inside a graph is not source certainty

Naiad introduces logical timestamps and a progress mechanism for cyclic, incremental dataflow, including notifications when work at a logical point is complete. Its introductory model supports structured loops and stateful vertices without requiring every step to synchronize globally. That contribution should not be collapsed into a claim that all progress is a single wall-clock watermark. The source's logical timestamp domain and the internal computation's possible future messages can be richer than one ordered scalar.

The distinction matters when an operator creates delayed output, iterates, or retains a capability to emit records at an earlier logical time. Even if all external sources have advanced, internal work can still prevent downstream completion. A proposed verification should identify every place that can retain or create timestamped messages and establish how its progress obligations are discharged. The scalar minimum example illustrates only the acyclic two-source case. It does not implement Naiad's complete timestamp and notification algorithm. A practical consequence is that pipeline health dashboards should separate source lag from internal progress retention. Otherwise a stalled result may be attributed to missing input even though the relevant data has arrived and an internal operator still holds unfinished work.

Sources [3]

Fault tolerance and temporal completeness are orthogonal

MillWheel's original description combines persistent application state, logical time, continuous dataflow, and fault-tolerance mechanisms. That combination demonstrates why stream processing needs more than a timestamping rule. Yet reliable replay does not tell the application that no older event will ever arrive. A system can process every received event exactly once under its state protocol while omitting a record that the source has not supplied before a chosen finalization deadline.

Conversely, receiving all records for a window does not prevent duplicate output after a crash unless state and sink effects have a suitable coordination rule. This review therefore proposes testing two dimensions independently: temporal coverage of the intended input set and consistency of replayed effects. A correction should carry a stable identity and version so that a retry cannot become a second logical correction. The source log, operator checkpoint, and sink acknowledgment must be associated with the same logical boundary if the system claims coordinated outcomes. These are proposed end-to-end invariants, not claims that the simple trace implements MillWheel's protocol. A benchmark that counts only recovered records cannot establish correctness of externally visible notifications or updates.

Sources [2]

A six-event trace exposes a metric trap

The first analytical figure uses six records with event-time, arrival-time, and value triples: (1,2,10), (4,5,20), (8,25,30), (11,12,40), (18,19,50), and (7,40,60). Their complete value total is 210. With a cutoff at each ten-second window end and no extra retention, four records are accepted and the accepted total is 120. Retaining for fifteen additional seconds accepts five records with total 150. Thirty additional seconds accept all six and recover the total 210.

Thus record completeness and value completeness differ. At fifteen seconds, the accepted count is five sixths, but the accepted value is only five sevenths. The last missing record is disproportionately important. This is a counterexample to using the fraction of late records alone as a quality metric for weighted aggregates. For nonnegative values, the model checks that increasing retention cannot reduce the accepted set. That monotonicity does not imply a known real-world accuracy curve: the six records are authored examples, not a sample from a population. A production study must examine lateness jointly with value, key, producer, and error type. Otherwise a seemingly small late-data rate can conceal a large systematic bias.

Triggers decide visibility, retention decides possibility

The Beam programming guide separates watermarks, late-data handling, allowed lateness, triggers, and accumulation choices. These concepts answer related but different questions. A trigger controls when a pane becomes visible. Retaining state controls whether later input can revise it. An accumulation policy controls what the emitted pane contains. Choosing one does not silently specify all the others, and behavior must also be checked for the actual runner and source.

For the first window in the constructed trace, the aggregate evolves from 30 to 60 to 120 as delayed records arrive. A sink receiving accumulating replacements should replace the previous value, while a sink receiving deltas should add 30, then 30, then 60. Adding the accumulating values would yield 210 for that window, even though its correct total is 120. The numerical coincidence with the complete two-window total would make this mistake especially easy to overlook in a weak test. A sink schema should therefore include window identity, revision identity, whether the payload is a replacement or delta, and any finality claim. A consumer must not infer those semantics from the numerical value or from the absence of another update for some period.

Sources [4]

Irreversible actions need a different threshold

Revising a dashboard cell is different from sending an irreversible external notification. A late record can update a count, but it cannot make a previously delivered alert unseen. Retractions can communicate a correction without undoing every consequence of the original action. The appropriate emission policy therefore depends on the action's reversibility and the cost of false positives or false negatives, not simply on a desired refresh interval.

Consider an alert when a window total exceeds a threshold. An early total below the threshold does not establish that no alert will be needed later. For an absence alert, the difficulty is sharper: no record has arrived, and the decision depends directly on the source completeness promise. A proposed experiment should distinguish provisional displays, revisable decisions, and actions requiring a stronger finality boundary. It should record correction counts and time to correction, not only time to first output. If the application accepts a probabilistic lateness model, it should state the tolerated error and validate the model's stability over producer classes and outages. A deterministic watermark guarantee cannot be replaced by a historical percentile without changing the meaning of the resulting action.

State reclamation makes finality expensive

Keeping every window indefinitely preserves the possibility of incorporating arbitrarily late input, but it can violate finite storage and operational budgets. Garbage collection is therefore a semantic decision as well as a resource optimization. Once state is discarded, a late event may require replay from retained source data, a separate correction store, or explicit rejection. The system should expose which path occurred and preserve enough provenance for an operator to understand the resulting output.

A simple retention estimate multiplies the rate of newly active key-window states by the average retention duration and bytes per retained state. This is only a sizing approximation: skewed keys, session merging, timer metadata, and checkpoint copies can dominate. Its purpose is to connect finality policy to a resource budget before deployment. A stronger experiment would replay the same trace with multiple retention choices and measure both state size and aggregate error against a complete offline reference. It should include an outage that delays a high-value producer, because ordinary steady traffic may underestimate the worst correction demand. A policy that remains fast by silently dropping that producer's records has changed the input set and should be evaluated as such.

A protocol for testing compositional finality

The proposed evaluation starts by writing the source contract in mathematical terms, including timestamp resolution, boundary convention, and whether progress is exact or estimated. It then generates traces with controlled disorder, producer pauses, duplicates, replay, boundary timestamps, and delayed high-value records. An offline computation over the complete intended trace supplies the reference result. The streaming outputs are interpreted through the declared replacement or delta semantics before comparison.

Observe first-output latency, final-correction latency, accepted count and value coverage, retained state, and sink-visible duplicates separately. Inject failures before and after checkpoints and sink acknowledgments to test that revisions remain stable under replay. For multi-input operators, compare propagated progress with an independent minimum or appropriate logical-frontier calculation. A null result must include the tested disorder range and source reliability assumptions. The principal hypothesis is that explicit finality metadata and revision semantics reduce undetected inconsistencies at consumer boundaries. It can be rejected if consumers still misinterpret updates under the documented interface, or if the resource cost of preserving the required correction window exceeds the application's declared budget. Completion claims should be tested at the sink, where users observe them.

What can honestly be called final

The numerical checks establish monotonic acceptance under a fixed cutoff rule, the difference between count and weighted-value coverage, the safety of a minimum relative to the two assumed input bounds, and a maximum-frontier counterexample. They also verify that correctly interpreted revision deltas telescope to the final window value. None demonstrates real watermark calibration, a runner's failure recovery, or completeness of an actual external source.

A useful finality label should therefore name its scope. A result may be final relative to a bounded source snapshot, final under an explicit producer promise, or closed under a retention policy that will reject further corrections. These are different statuses. Calling all of them final hides the very uncertainty the stream abstraction was meant to manage. The proposed manuscript favors explicit output metadata and retained correction history because they allow consumers to distinguish a genuine completion fact from an operational cutoff. Further work should study how those labels compose through joins, session windows, and iterative operators. The difficult question is not merely when a computation stops waiting, but what evidence authorizes its consumers to stop expecting a meaningful revision.

Mathematical model

Wj(t)=w⟹∀e∈Future⁡j(t):τ(e)≥wW_j(t)=w\Longrightarrow\forall e\in\operatorname{Future}_j(t):\tau(e)\ge w

(1) Chosen exact lower-bound convention; tau is event time. A heuristic watermark only approximates this implication.

Wunion(t)=min⁡j∈A(t)Wj(t)W_{\rm union}(t)=\min_{j\in\mathcal A(t)}W_j(t)

(2) Scalar acyclic union of active inputs A(t); idleness exclusions require a separate reactivation contract.

window⁡(τ)=[10⌊τ/10⌋,10⌊τ/10⌋+10)\operatorname{window}(\tau)=[10\lfloor\tau/10\rfloor,10\lfloor\tau/10\rfloor+10)

(3) Half-open ten-second windows in the constructed trace; times share a common origin.

accept⁡(e;ℓ)=1[a(e)≤b(e)+ℓ]\operatorname{accept}(e;\ell)=\mathbf 1[a(e)\le b(e)+\ell]

(4) Constructed arrival-cutoff policy: a is arrival time, b is window end, ell is extra retention seconds; not a runner implementation.

Vk=V0+∑i=1kΔi,Δi=Vi−Vi−1V_k=V_0+\sum_{i=1}^{k}\Delta_i,\qquad\Delta_i=V_i-V_{i-1}

(5) Revisions as additive deltas telescope; replacement panes must not be accumulated as though they were deltas.

S≃rkw h bsS\simeq r_{kw}\,h\,b_s

(6) Sizing approximation: r_kw new key-window states per second, h seconds retained, b_s bytes per state; excludes timer and checkpoint overhead.

Reproducible analytical figures

Retention versus accepted event mass: Six author-constructed records; cutoff is arrival <= window end + lag, not a simulation of a specific runner.
Figure 1. Six author-constructed records; cutoff is arrival <= window end + lag, not a simulation of a specific runner.

Assumptions: Window width 10 seconds; No duplicate records; Final complete total 210

CSV data · Vector figure

One slow source limits combined progress: Constructed watermark trace. Progress stall is a correctness signal unless a justified idle-source contract excludes B.
Figure 2. Constructed watermark trace. Progress stall is a correctness signal unless a justified idle-source contract excludes B.

Assumptions: Both sources remain active; Future timestamps are bounded below by each input frontier; No processing delay inside the operator

CSV data · Vector figure

Executed finite checks

5 check groups passed. The listed cases validate this model; they are not independent experiments or system benchmarks.

  • Retention monotonicity under fixed cutoff model · 7 cases. Same six events and deterministic cutoff for every policy.
  • Exact count and weighted-sum disagree as quality metrics · 1 cases. Five of six records is 83.33 percent; their value is 150 of 210.
  • Min frontier safe against each input bound · 7 cases. A scalar frontier represents inclusive lower bound on possible future timestamps.
  • Max frontier counterexample · 1 cases. B can still produce timestamp 8 despite A reaching 15.
  • Revision deltas telescope · 1 cases. Window [0,10) initial total 30, then 60, then 120.

Comparison

Extra retentionAccepted recordsAccepted valueComplete value
0 seconds4 of 6120210
15 seconds5 of 6150210
30 seconds6 of 6210210

Proposed validation protocol

  • Specify event timestamp provenance, resolution and boundary inequalities.
  • Declare whether each source watermark is exact, conditional or estimated.
  • Generate bounded traces with known complete reference results.
  • Vary disorder, pauses, duplicates and high-value delayed events independently.
  • Test minimum-input progress and explicit idle-source reactivation.
  • Interpret every sink message through its declared replacement or delta semantics.
  • Compare first-output and final-correction latency separately.
  • Record count coverage, weighted coverage, state size and rejected late records.
  • Inject replay around checkpoints and sink acknowledgment boundaries.
  • Publish failures, source-contract violations and the tested retention range.

Limitations

  • The cutoff model is not a simulation of a Beam runner or Flink engine.
  • Six authored events provide no statistical estimate of real lateness.
  • The scalar frontier model excludes cyclic and partially ordered progress semantics.
  • No clock skew, negative-valued corrections or session-window merging is modeled.
  • No streaming deployment or fault-recovery experiment was executed.
  • Official documentation is mutable; version labels are recorded as accessed.

Open research questions

  • How can finality metadata remain interpretable after multiple joins and revisions?
  • Which retention policy controls weighted aggregate error under correlated producer outages?
  • How should an idle source rejoin without invalidating consumers’ previously declared finality?

Evidence and its boundaries

[1] The model treats out-of-order unbounded data through explicit correctness, latency and cost choices.
The review does not claim all Dataflow operators or implementation details were audited. Inspected: Abstract and Section 1.
[2] The framework combines persistent state, logical time and fault-tolerant continuous dataflow.
The model here does not reproduce MillWheel delivery or low-watermark implementation. Inspected: Abstract and Section 1.
[3] Logical timestamps and progress tracking support cyclic, incremental dataflow and completion notifications.
The scalar event-time example is not Naiad’s full partially ordered timestamp model. Inspected: Abstract and Section 1.
[4] Watermarks, lateness and trigger choices jointly determine when panes are emitted and updated.
Access-year metadata; exact behavior also depends on runner and source. Inspected: 8.4; 8.4.1; 9.4.1.
[5] Multiple active input streams constrain an operator by their minimum event-time progress; late events can violate expected watermark conditions.
Mutable stable URL and release label are recorded as accessed, not an executed engine version. Inspected: Event Time and Watermarks; Watermarks in Parallel Streams; Lateness.
[6] Watermarks provide temporal-completeness information useful for ordered decisions and state reclamation.
The comparative implementation experiments and full semantics are not independently reproduced. Inspected: Abstract; Sections 1 and 2.

References

  1. The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing
    Tyler Akidau, Robert Bradshaw, Craig Chambers, Slava Chernyak, Rafael J. Fernández-Moctezuma, Reuven Lax, Sam McVeety, Daniel Mills, Frances Perry, Eric Schmidt, Sam Whittle. Proceedings of the VLDB Endowment (2015). https://www.vldb.org/pvldb/vol8/p1792-Akidau.pdf
    Source access and scope

    Original PVLDB PDF abstract and introduction, plus original Google publication record.

  2. MillWheel: Fault-Tolerant Stream Processing at Internet Scale
    Tyler Akidau, Alex Balikov, Kaya Bekiroglu, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, Sam Whittle. Proceedings of the VLDB Endowment (2013). https://www.vldb.org/pvldb/vol6/p1033-akidau.pdf
    Source access and scope

    Original PDF opening, abstract and introduction; Google metadata also checked but its page-range discrepancy not propagated.

  3. Naiad: A Timely Dataflow System
    Derek G. Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, Martín Abadi. ACM SOSP (2013). https://sigops.org/s/conferences/sosp/2013/papers/p439-murray.pdf
    DOI: 10.1145/2517349.2522738
    Source access and scope

    Original SOSP PDF abstract and introductory model properties.

  4. Beam Programming Guide
    Apache Beam contributors. Apache Beam documentation (2026). https://beam.apache.org/documentation/programming-guide/
    Source access and scope

    Official sections on watermarks, late data, allowed lateness, triggers and accumulation modes.

  5. Timely Stream Processing
    Apache Flink contributors. Apache Flink documentation (2026). https://nightlies.apache.org/flink/flink-docs-stable/docs/concepts/time/
    Source access and scope

    Official concepts page inspected: event time, watermarks in parallel streams and lateness; rendered version v2.3.0.

  6. Watermarks in Stream Processing Systems: Semantics and Comparative Analysis of Apache Flink and Google Cloud Dataflow
    Tyler Akidau, Edmon Begoli, Slava Chernyak, Fabian Hueske, Kathryn Knight, Kenneth Knowles, Daniel Mills, Dan Sotolongo. Proceedings of the VLDB Endowment (2021). https://www.vldb.org/pvldb/vol14/p3135-begoli.pdf
    DOI: 10.14778/3476311.3476389
    Source access and scope

    Original PVLDB PDF abstract, introduction and background definition.

Commissioned research review · v1. Cite this review · Original source record · Publication record