MillWheel: Fault-Tolerant Stream Processing at Internet Scale
đź“ś Abstract
MillWheel is a framework for building low-latency data-processing applications that is widely used at Google. Users specify a directed computation graph and application code for individual nodes, and the system manages persistent state and the continuous flow of records, all within the envelope of the framework’s fault-tolerance guarantees. This paper describes MillWheel’s programming model as well as its implementation. The case study of a continuous anomaly detector in use at Google serves to motivate how many of MillWheel’s features are used. MillWheel’s programming model provides a notion of logical time, making it simple to write time-based aggregations. MillWheel was designed from the outset with fault tolerance and scalability in mind. In practice, we find that MillWheel’s unique combination of scalability, fault tolerance, and a versatile programming model lends itself to a wide variety of problems at Google.
✨ Summary
MillWheel presents a general-purpose programming model and execution framework for low-latency stream processing at Google scale. Applications are expressed as directed graphs of user-defined computations that process (key, value, timestamp) records. Computations execute serially for each key but can run in parallel across keys, allowing the framework to handle partitioning, load balancing, persistent state, timers, and record delivery without requiring application authors to implement distributed-systems recovery logic.
The central design contribution is the integration of persistent per-key state, logical event time, low watermarks, and timers with fault-tolerant execution. Low watermarks provide a monotonic estimate that all work up to a particular timestamp has been observed, enabling correct handling of out-of-order data and event-time windowing. Timers can be triggered by wall-clock time or low-watermark progress. Exactly-once processing is implemented through record identifiers, deduplication, atomic state updates, and checkpointed productions. State, timers, and pending outputs are kept within a consistency envelope, while sequencer tokens prevent stale or “zombie” workers from modifying state after ownership changes.
The implementation uses replicated storage such as Bigtable or Spanner, key-interval sharding, dynamic load balancing, fine-grained checkpointing, and a centralized, shardable authority for globally consistent low-watermark tracking. The system supports both strong productions, which checkpoint outputs before delivery, and weaker optimizations for applications whose computations are already idempotent. Reported experiments demonstrated millisecond-scale record-delivery latency, approximately constant median latency as deployments grew from 20 to 2,000 CPUs, modest additional watermark lag per pipeline stage, and a twofold reduction in normalized CPU load from framework-level caching. The paper also identifies limitations: highly skewed keys, non-checkpointable operations, and workloads whose progress is blocked by severe input delay.
The paper had a documented influence on subsequent stream-processing abstractions. The later Google Dataflow model explicitly describes itself as being based partly on MillWheel, extending its ideas around event time, watermarks, windowing, triggers, and the trade-offs among correctness, latency, and cost. (vldb.org) Apache Beam subsequently adopted the Dataflow model as the basis of a portable programming layer for batch and streaming pipelines across multiple execution engines, including Google Cloud Dataflow, Apache Flink, and Apache Spark. (beam.apache.org) Later surveys identify MillWheel and the Dataflow model as influential in popularizing watermarks, out-of-order processing, and trigger-based stream computation, while subsequent systems research continues to cite MillWheel for its state-management and strong-production approach. (link.springer.com)