Windows are retention rules in time

When are sliding windows cheap, and why do session windows need a maximum length?

CaseConstructed case · Ana at Ridelo

A 24-hour sliding window pins the CPU

The product team asks for a dashboard tile: "orders per restaurant in the last 24 hours, refreshed every minute". Ana writes it as a sliding window. In the test it works. In production, the memory of the window operator is huge, and the CPU is pinned at 100%. Then Tomás restarts a source that had been stopped for an hour. Within seconds the job emits millions of results at once, downstream latency jumps, and the on-call phone rings. A week later the fraud team asks for a pattern ("an order, then any number of cancellations, then a refund within 30 minutes"), and its state grows faster than any aggregation in the job. Finally, a single quiet partition in the source makes all windows stop closing. Four symptoms, one idea: time-based retention.

How it ends →

An endless stream needs a bounded rule for what to remember. Windows express that rule in time. A window groups records into finite pieces so that an aggregate can be computed and emitted.

Tumbling windows: the cheap case

A tumbling window cuts time into disjoint buckets of equal size (for example 10 minutes: 12:00–12:10, 12:10–12:20, …). Each record belongs to exactly one bucket. State is proportional to keys × open windows.

Sliding windows and the S/s blowup

A sliding window of size S and slide s moves forward every s units, so windows overlap. Each record falls into S/s windows.

Pane decomposition fixes this.

Cut time into small panes of length s (here, 1 minute).
Compute a partial aggregate per pane. Each record is folded into exactly one pane, so per-record work returns to O(1).
At emit time, combine the S/s panes that make up the window (here, 1,440 partial counts).

State becomes keys × S/s pane accumulators (small ones, like an 8-byte counter), not a copy of each record in 1,440 windows.

# 1-minute panes; window = last 1440 panes
pane_counts[(restaurant, minute_of(event_time))] += 1       # O(1) per record
def emit(restaurant, now_minute):                           # once per minute
    return sum(pane_counts[(restaurant, m)] for m in range(now_minute - 1439, now_minute + 1))

This works only for associative aggregates, because partial results must be combinable. Exact distinct counts and medians are not decomposable: you cannot get the exact number of distinct users in 24 hours from 1,440 per-minute distinct counts, since the same user may appear in many panes. This is where sketches enter. HyperLogLog (approximate distinct count) and KLL (approximate quantiles, such as the median) are mergeable, which is exactly what pane decomposition requires. The same structural demand made them useful in distributed aggregation, appearing again.

Invertible aggregates admit an even cheaper form: keep a single running value, add the pane that enters the window and subtract the pane that leaves. But floating-point sums are not safely invertible. Addition of floating-point numbers is not associative under rounding, so subtracting a value does not exactly cancel what was added.

Small example (in 64-bit floating point): start with 1e16, add 1, then subtract 1e16. The exact answer is 1. The computer gives 0, because 1e16 + 1 is not representable and rounds back to 1e16. A running window sum that adds and subtracts such values can drift without any error being reported.

Session windows: boundaries defined by absence

A session window groups the records of one key that are close together in time. A session ends when there has been no data for a gap period (for example 30 minutes of no activity). That makes session windows categorically different:

The boundary is defined by the absence of data, so windows are created per record and must merge when a later record bridges two existing sessions. Merging requires the per-window accumulator to be mergeable, which limits what you can store.
There is no a priori bound on a session's length. A key that never goes quiet never closes, and its state grows without limit. A bot sending an event every 10 seconds forever is one session forever.
The only real defence is a maximum session duration. That is a declared retention rule replacing an undeclared one.

Global window with a custom trigger

The global window puts all records of a key into one window that never ends, and a custom trigger decides when to emit. This is "write your own retention rule", and therefore the place where unbounded state is most often introduced.