Time-window aggregation

The problem: which minute does a click belong to?

Snip's chart shows clicks per minute for each link. A click happened at 14:02:58 on a phone in a train tunnel. The phone sends it at 14:09:40, when it gets signal. The CDN's edge logs (06.07 CDNs in depth) arrive in batches every few minutes. A consumer was restarted and replays two minutes of events.

So the click must be counted in the 14:02 bucket, not 14:09, and the 14:02 bucket can't be called final at 14:03, because clicks for it may still be on their way. Windowing is the art of answering "how many per minute?" when data is late and out of order.

Event time versus processing time

• Processing time: when the system sees the event. Easy, always moving forward, and wrong for analytics: a backlog or a replay shifts clicks into the wrong minute.
• Event time: when the event actually happened, carried in the event. Right for analytics, but events arrive in any order.

Snip counts by event time. The redirect stamps each click with the server's time when it served the 302, so phones' clocks don't matter, but delays in the pipeline still do.

Three shapes of window

Apache Flink's documentation puts it precisely: tumbling windows have a fixed size and don't overlap; sliding windows overlap when the slide is smaller than the window; session windows close when no elements arrive for a period.

Watermarks: when is a window done?

A watermark is the stream's own estimate of event-time progress. In Flink's definition, a watermark at time t declares that event time has reached t: there should be no more events with timestamps at or before t. When the watermark passes the end of a window, the window can be emitted.

The watermark is a judgement call. Snip sets it to "the latest event time seen, minus 5 seconds", because measured delays through the pipeline are almost always under 5 seconds:

• Too eager (watermark close to the newest event): results appear fast, but more events arrive after their window was emitted.
• Too cautious (watermark minutes behind): fewer late events, but every chart is minutes behind.

Google's Dataflow paper frames this as a three-way trade-off you can't avoid with unbounded, out-of-order data: correctness, latency and cost.

Late events

Some events still arrive after the watermark. Choose what happens to them:

1. Update the window. Keep each window's state for an allowed lateness after it closes, and emit a corrected count if a late event arrives. Downstream must accept updates, which per-minute rows in a database do naturally.
2. Drop, but count the drops. Past the allowed lateness, discard the event from the live windows, increment a "too late" metric, and let the nightly batch over raw events fix the numbers (11.06 Raw events vs derived data).

type Click = { code: string; at: number }; // event time, ms

export class MinuteCounts {
  counts = new Map<number, number>(); // window start -> clicks
  dropped = 0;
  private maxSeen = 0;
  constructor(readonly allowedLatenessMs = 120_000) {}

  get watermark() {
    return this.maxSeen - 5_000; // assume events are at most 5 s out of order
  }

  add(c: Click) {
    this.maxSeen = Math.max(this.maxSeen, c.at);
    const window = Math.floor(c.at / 60_000) * 60_000;
    if (window + 60_000 + this.allowedLatenessMs <= this.watermark) {
      this.dropped++; // too late even for an update: count it elsewhere
      return;
    }
    this.counts.set(window, (this.counts.get(window) ?? 0) + 1); // a late event updates an already-emitted window
  }

  /** Windows whose end is behind the watermark are complete enough to show. */
  closed() {
    return [...this.counts].filter(([w]) => w + 60_000 <= this.watermark);
  }
}

Tested with ten minutes of clicks, one a second, shuffled by up to a few seconds, plus one click from a phone that arrived about nine and a half minutes late: nine windows closed with about 60 clicks each, the jittered clicks were counted in their correct minutes, and the very late click was dropped and counted as dropped (600 of 601 counted), leaving the nightly batch to account for it.

Recap

Interview questions