Stream processing

Windows, watermarks and late events: computing over data as it arrives.

System design conceptQueues, streams and batch1 Nov 2026

01The intuition

The problem it solves

A city has 2,000 traffic sensors, each reporting a car count every second. The traffic office wants a map showing, for every road, the number of cars in the last five minutes, updated every ten seconds. Two thousand sensors times 60 reports a minute is 120,000 numbers a minute, forever. You cannot store them all in a database and run SELECT SUM over the last five minutes every ten seconds across the whole city; the query would scan millions of rows each time and fall behind.

A clerk at a toll gate has the same job and solves it without a database. She keeps a running tally on a sheet, adds each car as it passes, and every ten seconds writes the total on the board. She never re-reads the whole sheet. Stream processing is that clerk, multiplied: compute as data arrives, keep only what the current answer needs, and emit results on a schedule.

Build it one piece at a time

Step 1: a running sum per key. Events flow in from a queue. For each event (road 7, time 10:00:03, cars 4) the processor adds 4 to the counter for road 7. State is one number per road, 2,000 numbers in all.

Step 2: windows. "The last five minutes" means old events must stop counting. Split time into windows. A tumbling window of 5 minutes gives one count per road per 10:00–10:05, 10:05–10:10, and so on. A sliding window of 5 minutes every 10 seconds keeps the last 30 ten-second buckets per road and sums them; a new bucket enters, the oldest leaves.

Event arrives	Buckets for road 7 (ten-second)	Five-minute total emitted
10:00:03, +4	[…, 10:00:00: 4]	sum of last 30 buckets
10:00:12, +6	[…, 10:00:00: 4, 10:00:10: 6]	updated sum
10:05:01, +2	oldest bucket 10:00:00 dropped	sum without the 4

Step 3: event time and late data. A sensor loses its network for a minute and sends its reports late. They carry their own timestamps (event time), which differ from when they arrive (processing time). The processor must place them in the right bucket, not the current one. But how long should it wait before declaring a window finished?

Step 4: watermarks. The processor tracks a watermark: "I believe I have seen all events up to time t". It advances a little behind the newest event seen, say 30 seconds behind. When the watermark passes the end of a window, that window's result is emitted. An event later than the watermark is either dropped or triggers a corrected result, and the design must say which.

Step 5: partition and checkpoint. Split the roads across 20 machines by road ID so each machine holds state for 100 roads. Every minute, each machine saves its state and its queue offset to durable storage. If it crashes, a replacement loads the checkpoint and replays the queue from that offset. Events between the checkpoint and the crash are counted again, so the counting must be idempotent or the checkpoint must include the exact offset.

Why it works, with the numbers

State stays bounded by keys times buckets, not by events seen. For 2,000 roads and 30 buckets of 8 bytes:

state = 2,000 × 30 × 8 bytes = 480 KB, while the raw events are 120,000 a minute, 173 million a day

Each event costs one addition, so one machine handles hundreds of thousands of events a second. The guarantee is that each window's result reflects every event with a timestamp in that window that arrived before the watermark passed, and with checkpoints plus replay, no event is lost by a crash. The failure modes are late events after the watermark (undercount or late correction), skew where one key gets most events and its machine lags, and checkpoints that are too far apart, making recovery slow.

The trade-off you must say out loud

Latency against completeness: a watermark close behind real time gives fast results that miss late events; a watermark far behind gives accurate results late. Say the lateness you allow and what happens beyond it. Say that the exact totals are recomputed from the full log in a nightly batch if the business needs them. The follow-up is "what if the processor restarts", and the answer is checkpoints plus replay from the queue.

Where it shows up in the 100 Google problems

Live traffic map: the example above, with phones as sensors and road segments as keys.
Trending topics: sliding windows over hashtag counts with a sketch as the state.
Ad click aggregation: per-minute windows with watermarks, and a batch job for the exact daily bill.
Metrics and monitoring: alerts are windowed aggregates evaluated as the points arrive.
Fraud and DDoS protection: requests per source over the last minute, computed in the stream, drive blocking decisions.