Basis Lab

Answers · Where the data lives

How does a streaming system know when a window is finished?

In shortIt cannot know. It guesses: it takes the latest event time it has seen, subtracts an allowance you choose, and treats every window ending before that point as finished.

It does not know, and nothing it can observe would tell it. It decides: it takes the largest event time it has seen so far, subtracts an allowance you picked in advance, and treats every window ending before that result as finished.

Call the largest event time seen mm and the allowance dd. The result w=m−dw = m - d is the watermark. A window is emitted when its end falls below ww, so a one-minute window ending at 10:09:00 is emitted the first moment mm reaches 10:09:00 plus dd.

w=m−dw = m - d

Take d=120d = 120 seconds and suppose the event times seen so far run up to 10:12:30. Then w=10:12:30−2:00=10:10:30w = 10{:}12{:}30 - 2{:}00 = 10{:}10{:}30. The window covering 10:00:00 to 10:10:00 ends at 10:10:00, which is 30 seconds below ww, so it closes and is reported.

Running that backwards gives the exact trigger: the window closed the instant an event with event time 10:12:00 arrived, because 10:12:00−2:00=10:10:0010{:}12{:}00 - 2{:}00 = 10{:}10{:}00. Any event stamped 10:09:55 that turns up after that instant is not counted. It raises no error, it is not retried, it simply falls outside a window that has already been computed. The published figure is a little low and the figure itself gives no sign of it.

Note which term is which. mm is data: it moves forward only when events arrive, and it stops when they stop. dd is a configuration value, and it is the single place where a person states how much lateness is tolerable.

The natural guess is that the system is waiting for the last relevant event, and that a well-built one would notice when it had arrived. Nothing distinguishes that moment. Silence from a source with nothing to send and silence from a source whose network is down are the same observation, which is to say none. A gap in sequence numbers proves that something is missing, not that nothing further is coming, and a phone that has been in a tunnel will sync in four minutes or four days with the first three days looking identical. Even the check that every source has reported in fails, because a device that has not connected for a week is a source you do not know exists. The only definite answer available is the negative one: a recent arrival with a 10:09 timestamp proves the 10:09 window is incomplete. Its absence proves nothing at all.

The allowance is the whole decision

Since dd is a judgement, set it from measurement rather than taste. Record the gap between arrival time and event time for every event, build the distribution, pick a percentile, and write the percentile down. If the ninety-ninth percentile of measured lateness is 200 seconds, then d=200d = 200 s means roughly one event in a hundred arrives too late to be counted, and the sentence "we exclude about one per cent of events, and here is what happens to them" is a defensible thing to have written.

The cost of raising dd is memory as well as delay. At 50 events per second, a 200 second allowance keeps about 50×200=10,00050 \times 200 = 10{,}000 events of open state; 400 seconds keeps 20,000 for a gain in coverage that the tail of the distribution makes very small. The cost of lowering it is invisible rather than slow, and invisible is worse: a slow pipeline is noticed, an undercounted total is not.

FIG 1The believed point is a minimum, not an average
stepstepABCbelieved pointwhat happened
1110:0009:5809:5909:53All three advancing: the per-partition points are 09:55, 09:53 and 09:54, and the minimum is 09:53. Windows ending before 09:53 are being emitted.
2210:1010:0809:5909:54A has moved ten minutes, C has not moved at all. The believed point advanced by one minute.
3410:5010:4809:5909:54Forty minutes later the point has not moved. Nothing closes, every open window is still holding state, and from outside there are no errors, two healthy partitions and a flat line on the dashboard.
4510:5510:5310:5210:47C recovers. The point jumps from 09:54 to 10:47, which is 53 minutes, and 53 one-minute windows are computed and emitted in a single burst.
4 steps
Three partitions, allowance 300 seconds. The believed point trails the slowest partition, which is the point of the design and also the source of the incident.

Completeness has to hold across every input, so the believed point is the minimum of the per-partition points. One partition that stops for forty minutes holds every window open, and one partition that is merely idle does exactly the same for a completely benign reason: no events means nothing to push its point forward. Every system therefore has an idleness setting, which excludes a partition from the minimum after a stated interval with no data. Leaving it unset is how this behaviour gets discovered at an inconvenient moment, and setting it very short declares completeness while a partition is only slow.

A second consequence surprises people: closing time depends on traffic. A busy period pushes mm forward quickly and the hourly window is out at 10:04; the same window on a quiet night waits for something to arrive and is out at 10:40. Neither run is faulty. Systems that need output on a silent source let ww also advance with wall-clock time once the source is known to be idle.

Where the argument stops

The reasoning assumes an open-ended source. If the input is a finite file with a real end-of-input marker, completeness is knowable, the marker is evidence, and the job is a batch job that may as well wait for it. The guess is forced only where arrivals have no end.

The two extremes also show what dd is doing. At d=0d = 0 the watermark is the last event time, so any event that arrives out of order is silently dropped. At a very large dd, or under a stalled source with no wall-clock fallback, nothing ever closes and memory grows without bound. The setting is not a safety margin bolted onto a correct mechanism; it is the mechanism.

Worth keeping

  • A watermark is the largest event time seen minus a chosen allowance, and windows ending below it are treated as complete.
  • Silence has two causes, nothing to send and a broken link, and they are indistinguishable at the receiver, so completeness is never observed, only assumed.
  • An event arriving after its window closed is dropped without an error, which makes an undersized allowance more dangerous than a slow pipeline.

Where this goes next

This question is one step of Counting Things as They Arrive, a course that works through its subject from the beginning. The page that teaches this part of it is Deciding a Window Is Finished, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. Why does my count come out doubled after the job restarts?Your count doubled because the restart replayed events the saved counter already held: the state and input position were not saved as one snapshot.
  2. Why can't I just average the old average with the new number to get a running average?Averaging the old average with the new number gives that single new value half the weight, when it deserves one share out of however many values came before.
  3. Should I use a sliding window or a fixed window?Use a fixed window when the question names a period that must add up, and a sliding one when it asks about the recent past as of now. Questions about episodes want neither.
  4. How do you count unique visitors without remembering every visitor?Turn each visitor identifier into a random-looking code, keep only a small summary of the rarest pattern seen, and scale it up; repeats change nothing and memory stays fixed.
  5. Why is the date off by one day after I save it and read it back?You saved a calendar date as if it were a precise moment, so showing it in another time zone can move it to the day before or after.
  6. Is UTF-8 the same thing as Unicode, or what's the difference?No: Unicode assigns a number to each character, while UTF-8 is a way of writing those numbers as bytes, using one to four bytes per character.

Read alongside