Stream processing: windows, late data, exactly-once

The interviewer says: "Show each merchant how many payments they got in the last 10 minutes, updated every minute. Some events arrive late. If your job crashes, the numbers must still be right. The job may also send an SMS."

A weak answer says "use Kafka and a stream tool" and stops, or counts by the time the job reads the event. A strong answer says which time it uses, which window fits and how long it waits for late events. It says where the counts live and how a restart avoids counting twice. It also says what happens where a result leaves the job.

At SDE-2 level you should know the window kinds and late events. At SDE-3 level you should also explain saved state, the outside world, joins and replay.

Think of a scorekeeper who listens to radio commentary and writes the score in a notebook. At the end of each over he photocopies the notebook and writes on the copy the number of the last commentary line he heard. If he falls ill, a new scorekeeper takes the last copy and listens again from that line. The copy and the line number belong together.

A stream processor works like this. It is a program that reads events from a log all the time (lesson 87). It keeps state between events: a count, a sum or a list. State is the notebook. Lesson 116 built one for ad clicks. Here is the general engine.

Windows

A window is a slice of event time that gets one result. Event time is the time written in the event (lesson 116). There are three kinds.

• Tumbling: equal slices with no overlap, for example each minute. An event is in one window.
• Sliding: a size and a slide. "The last 10 minutes, updated every minute" is size 10 minutes and slide 1 minute. Windows overlap, so one event is in size / slide windows.
• Session: no fixed length. A window starts with an event and closes after a gap with no events. It fits a user's visit. A late event can join two sessions.

The watermark and late events

The job cannot see the future, so it needs a rule for when a window is complete. The watermark says "all events up to time T have probably arrived". A common rule is T = the newest event time seen minus a bound that you choose, for example 20 seconds. When the watermark passes the end of a window, the job closes the window and writes the result.

With many partitions, the watermark is the smallest one (lesson 116). A partition with no events never moves, so it holds back every window. Tools let you mark an input as idle after some time. The watermark is a guess, so an event can still arrive behind it. This is a late event. It has three choices.

1. Drop it. Fine for a live chart.
2. Update the old result. The job keeps the window for an allowed lateness and writes a corrected result when a late event comes. The reader must accept a second result for the same window, so write each result as an overwrite by key.
3. Send it to a side output. This is a separate stream of late events, fixed later by another job (the late table of lesson 116).

State and checkpoints

State lives next to the processor, in memory or on its disk, so an update needs no network trip. If the machine dies, its state dies. A checkpoint is a snapshot of the state and of the log positions (the offsets of lesson 87), taken together while the job keeps running. After a crash, the job loads the last checkpoint, moves its read position back and reads again. The events after the checkpoint are read a second time, but the crash erased their first effect on the state. So each event changes the state once. Lesson 116 did this with a database transaction; a checkpoint does it for any state.

Exactly-once and the outside world

A checkpoint gives exactly-once for the state only. The source is where the job reads, and the sink is where it writes. If the job sends an SMS and crashes before the next checkpoint, the restart reads the same events and sends the SMS again. For an exactly-once effect outside, the source must be readable again from a saved position, and the sink must be idempotent or transactional (lesson 89). There are two ways.

• Idempotent sink. Each result carries a key made from its content, such as merchant and window start. The receiver stores the key and ignores a repeat. There is no delay. If the receiver cannot store a key, keep your own table of sent keys and check it first. A crash between send and save can still repeat one message.
• Two-phase commit sink. The job writes its output inside an open transaction in the sink. When a checkpoint starts, the sink prepares the transaction. When the checkpoint completes, the sink commits it. After a crash between the two, the restart commits again, so the commit must be safe to repeat. The sink must support transactions, as a database or a log does. Readers must read only committed data. The output is visible only after a checkpoint, so it is late by up to one checkpoint interval.

Joining two streams

A stream join matches events from two logs by a key, for example an order and its payment. They do not arrive together, so the job holds each event in state for a join window and waits for its match. After the window, the event goes to a side output as unmatched. State size = events per second x seconds held x bytes per event.

Replay

If the job has a bug, the old results are wrong. The log keeps events (lesson 87), so start a fixed copy of the job from an older position and write to a new output. Switch the readers when it has caught up. Turn off outside effects such as SMS in the replay, or old alerts go out again. The log must keep data longer than the age of the bug. Catch-up time = backlog / (job speed - arrival rate).

PayEasy, a wallet app, counts payments for each merchant.

Assumptions (made up to teach with): 6,000 events per second at peak and 2,000 on average. 200,000 merchants. A state entry is 40 bytes. The watermark bound is 20 seconds. 0.5% of events are late. A restart takes 20 seconds. The job reads 30,000 events per second when it catches up.

Step 1: the sliding window. An event is in 10 / 1 = 10 windows. This answers the predict box. Updates: 6,000 x 10 = 60,000 per second. State: 200,000 x 10 x 40 bytes = 80 MB.

Ten windows, each 10 minutes long, each starting 1 minute after the one above it. One event falls in the same moment of all ten windows, so it is counted in 10 windows: the window size 10 divided by the slide 1.

Step 2: sessions. The gap is 5 minutes, so an event at minute t opens the window [t, t+5). Events at minutes 0, 2 and 3 merge into [0, 8) with 3 events. Events at 10 and 11 merge into [10, 16) with 2 events. A late event with time 6 opens [6, 11). It overlaps both sessions. If allowed lateness keeps them open, they become [0, 16) with 6 events, and two results that were already written are now wrong.

Step 3: late events. Per day: 2,000 x 86,400 = 172,800,000 events. Late: 0.5% x 172,800,000 = 864,000. Drop them for the live count. Use a side output for settlement.

Step 4: a stuck watermark. Seven of eight partitions are at 10:10:00. Partition 5 got nothing since 10:02:00. The watermark is the smallest time minus 20 seconds: 10:01:40. No later window can close, so at 10:10:00 the results are 500 seconds behind. With an idle limit of 30 seconds, the job ignores partition 5 from 10:02:30, so the stall lasts 30 seconds and not 8 minutes.

Step 5: a crash. A checkpoint is taken every 60 seconds. In the worst case the job must re-read (60 + 20) x 6,000 = 480,000 events. It reads 30,000 and receives 6,000 per second, so it gains 24,000 per second: 480,000 / 24,000 = 20 seconds. The live numbers stop for about 20 + 20 = 40 seconds: 20 to restart and 20 to catch up.

Step 6: the alert. The job sends an SMS when a merchant passes 1,000 payments in 10 minutes. Assumption: 2 crashes a day, and 30 alerts in the 60 seconds before each crash. Without protection: 2 x 30 = 60 repeated SMS a day. With an alert key (merchant and window start) checked before each send: about 0. An SMS service cannot join a transaction. A two-phase commit sink fits a database or log that a separate sender reads, and then an alert waits up to 60 seconds.

Step 7: a join. 1,000 orders per second wait up to 15 minutes (900 seconds) for a payment. State, at most: 1,000 x 900 x 200 bytes (assumption) = 180,000,000 bytes = 180 MB. If 3% never match, 30 orders per second go to the side output.

Step 8: replay. A bug in the alert rule is found 2 hours later. The log holds 7 days (assumption), so we can replay, with the SMS turned off. Events in 2 hours: 2,000 x 7,200 = 14,400,000. Catch-up: 14,400,000 / (30,000 - 2,000) = 514 seconds, about 8.6 minutes.

What companies wrote

• Netflix wrote in October 2026 (post listed on 14 Oct 2026) that its ad-event job used to look up each ad in a database. The team replaced the lookup with a streaming join in Flink, a stream processing tool. An event waits for its match for up to 60 minutes (the company's figure), and events with no match go to an hourly batch job. Link: https://netflixtechblog.com/behind-the-scenes-evolving-netflixs-ads-event-pipeline-for-live-part-ii-826ebf9ad9fb (opens in a new tab)
• Uber wrote on 23 Sep 2021 that its ad pipeline reads only committed Kafka messages and removes repeats with state kept for each key. Each result gets a unique ID, the sinks commit at checkpoints with two-phase commit, and the store ignores a repeated ID. Link: https://www.uber.com/blog/real-time-exactly-once-ad-event-processing/ (opens in a new tab)
• Zomato wrote on 22 Apr 2025 that its ad-counting job kept user IDs for 24 hours to remove repeats. The state reached 150 GB and was sometimes lost. A second job now checks the counts and fixes late events. So the limit fell to 2 hours, and the state shrank by 99% (the company's figures). Link: https://www.zomato.com/blog/eliminating-bottlenecks-in-real-time-data-streaming-a-zomato-ads-flink-journey/ (opens in a new tab)

Stream processing solves results that are seconds old and not hours old. It costs state to look after, a rule for late events, and checkpoints (80 MB of state here). I would change to a batch job (lesson 116) when nobody needs the number within minutes. I would add an idempotent key whenever a result leaves the job, as an SMS or a payment does.

"Exactly-once means each event is processed one time." After a crash, events are read again. Exactly-once means each event changes the state once. Step 6 shows that the outside world is not covered.

"The watermark means no more late events will come." It is a guess. In step 3, 864,000 events a day still arrive behind it.

"A checkpoint makes the SMS safe." A checkpoint saves state. It cannot take back an SMS. You need an idempotent key or a two-phase commit sink.

1. Name the three window kinds. What does a checkpoint hold, and why must its parts be taken together?
2. A sliding window is 30 minutes with a 5-minute slide. There are 50,000 keys, and a state entry is 40 bytes. (a) In how many windows is one event? (b) How many state entries, and how many bytes? (c) After a crash the job must re-read 3 minutes of events. Events arrive at 10,000 per second and the job reads 40,000 per second. How long does it take to catch up?
3. A job counts clicks and writes each result with an insert into a billing table. After a crash the table has some windows twice. What do you do?