Papers
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 (PVLDB), vol. 8, no. 12, 2015
The problem: unbounded, out-of-order data, and the false choice between batch and streaming
The paper starts from the observation that global, unbounded, unordered datasets (web logs, mobile app usage, sensor networks) have become common, and that the consumers of this data demand ordering by event time, windows defined by the characteristics of the data itself, and ever faster answers. The authors argue that no one can optimize correctness, latency, and cost all at once, and that practitioners end up with disparate implementations to reconcile these tensions. The motivating example is a video provider that must bill advertisers for the ad time watched, compute aggregate statistics, and run offline experiments over history, all with minimal delay, but with correctness paramount because money is at stake. Batch systems (MapReduce and variants, FlumeJava, Spark) suffer from the latency of collecting all the input before processing. Many streaming systems fall short in expressiveness or correctness, for example lacking exactly-once semantics or having windows limited to tuple counts or processing time. The central thesis is that the mistake is trying to turn unbounded data into finite packages that will eventually be complete: one must assume that it will never be known whether or when all the data has been seen, that new data keeps arriving, and that old data may be retracted. For this reason the paper prefers the terms unbounded/bounded over streaming/batch, reserving the latter for execution engines.
Event time versus processing time, and the watermark
The model rests on two time domains. Event time is the moment the event actually occurred, and for a given event it essentially never changes. Processing time is the moment the event is observed within the pipeline, according to the system clock, and it advances continuously. Communication delays, scheduling, and serialization cause a dynamic skew between the two domains, and the article illustrates this with a graph that plots the real watermark against the ideal one, where the ideal would have a slope of one and zero skew. The watermark, in the style of MillWheel's, is a lower bound on the event times already processed by the pipeline. In most real datasets it is defined heuristically, because the system does not know, for example, when a phone that lost its connection will resume sending views. That is why the authors insist that notions of completeness are in general incompatible with correctness, and that the watermark serves as a useful estimate of progress and for monitoring system health, not as a guarantee that all the data has arrived. Moving an element's timestamp backward past the watermark makes it late relative to the watermark.
Windows: fixed, sliding, and sessions, and the two steps that generalize them
Windowing slices a dataset into finite chunks to process as a group, and is necessary for unbounded data in operations such as aggregation and outer joins. The paper describes three common patterns. Fixed windows (also called tumbling) have a static size, such as hourly windows, and generally apply to all the data in the period. Sliding windows have a size and a slide period, such as one-hour windows that start every minute; fixed windows are the special case in which size and period coincide. Sessions capture a period of activity over a subset of the data, generally per key, delimited by an inactivity timeout; they are unaligned windows, and support for them is cited as the main contribution of the windowing model. To generalize everything, the model treats all strategies as unaligned and splits windowing into two operations: AssignWindows, which assigns each element to zero or more windows, and MergeWindows, which merges windows at grouping time, allowing data-driven windows, such as sessions that merge when intermediate events arrive. For this, elements become tuples (key, value, event time, window), and grouping becomes GroupByKeyAndWindow.
Triggers and accumulation modes: when to emit and how to refine
Windows say where, in event time, data is grouped; what was missing was saying when, in processing time, results are emitted. The paper shows that the watermark alone is insufficient for two reasons: sometimes it is too fast, leaving late data behind, and sometimes it is too slow, because as a global metric a single slow datum can hold back the whole pipeline and raise latency. Hence triggers, which stimulate the production of a window's result in response to internal or external signals and can emit multiple panes per window. There are triggers based on completeness estimates (including percentile watermarks), on processing time and on data arrival (count, bytes), as well as logical composition (and, or, sequences, loops) and user-defined triggers. Refinement modes relate successive panes. In discarding mode, the contents are discarded after firing and subsequent results are independent. In accumulating mode, the contents remain in persistent state and each result refines the previous one, as in Lambda systems that overwrite values. In accumulating and retracting mode, a retraction of the previous value is emitted first and then the new one, which is necessary when several groupings in series would cause partial results to end up under different keys further downstream.
The four questions and the critique of the Lambda architecture
The conceptual contribution is a single model that breaks down a pipeline's implementation into four dimensions: what is being computed, where in event time, when in processing time results materialize, and how earlier results relate to later refinements. This separates the logical notion of processing data from the physical implementation, so that choosing between batch, micro-batch or streaming becomes a choice about correctness, latency and cost. The paper's examples, all summing integers per key, show the same set of ten values with different outputs varying only window, trigger and mode: a global sum of 51 in classic batch, periodic global sums that are accumulating or discarding, windows by element count, two-minute fixed windows on batch, micro-batch and streaming engines, and sessions with retractions. On the Lambda architecture, the authors acknowledge that it meets many of the requirements, but fails on simplicity because it requires building and maintaining two systems. They also note that Lambda does not solve completeness: it only delivers the streaming system's best low-latency estimate, with a promise of eventual consistency when the batch runs, and that this batch is only correct if the input is complete when it executes.
Implementation, design principles, and experiences that motivated the model
The model was implemented internally in FlumeJava, using MillWheel as the execution engine in streaming mode, and there is an external reimplementation for Google Cloud Dataflow, with an open-source SDK. Much of the windowing and triggers code is shared between the batch and streaming implementations. The design principles listed are: never rely on any notion of completeness, be flexible for known and future use cases, not only make sense but add value on every execution engine, encourage clarity of implementation, and support robust analysis of data in the context in which it occurred. Real-world experiences shaped the design. A large log-join pipeline ran in streaming on MillWheel, but had a separate batch implementation in FlumeJava for backfills, which motivated the unification. A customer that used weakly consistent streaming with a nightly MapReduce to produce the truth lost users' trust and migrated to strong consistency. Sessions were the central motivation for windowing. Billing pipelines motivated triggers, accumulation and retraction; computing statistics motivated watermark triggers; abuse detection motivated percentile watermarks; recommendations motivated processing-time triggers; and anomaly detection motivated data-driven and composite triggers.
See the ideas at work
Practice the designs that use this paper in the System Design school.