CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 5 of 8 · 2 min read

Windows

A window groups events by time so that they can be counted or averaged.

Think of counting passers-by with a clicker. You can count in separate blocks of one minute. You can count the last five minutes, updated every minute. Or you can count each burst of people until there is a long quiet gap.

DDIA lists four kinds of window.

Tumbling window

A tumbling window has a fixed length and no overlap. Each event belongs to exactly one window.

Example: with one-minute tumbling windows, events from 10:03:00 to 10:03:59 form one window, and events from 10:04:00 to 10:04:59 the next. Each timestamp is rounded down to the minute.

Hopping window

A hopping window has a fixed length but overlaps with the next. It moves forward by a "hop" smaller than its length.

Example: a 5-minute window with a hop of 1 minute covers 10:03 to 10:07, then 10:04 to 10:08. An event can be in up to 5 windows.

Sliding window

A sliding window contains all events that happened within some interval of each other. It has no fixed boundaries.

Example: a 5-minute sliding window covers events at 10:03:39 and 10:08:12 together, since they are less than 5 minutes apart.

Session window

A session window has no fixed length. It groups events of one user that are close in time, and ends when the user has been inactive for a set time.

Example: events for a user at 10:00, 10:10 and 10:25, with a 30-minute inactivity limit, form one session. A next event at 11:30 starts a new session.

The book says a hopping window can be built from tumbling windows, by aggregating several adjacent ones. A sliding window can be built by keeping a buffer of events sorted by time and removing old ones as they expire. Sessionization is a common need for website analytics.

A worked example. Events (page views) at these times: 10:00:10, 10:00:50, 10:01:20, 10:02:05, 10:04:30.

Window type Windows and counts
Tumbling, 1 minute 10:00: 2 events. 10:01: 1. 10:02: 1. 10:04: 1
Hopping, 2 minutes, hop 1 minute 10:00 to 10:02: 3. 10:01 to 10:03: 2. 10:02 to 10:04: 1. 10:03 to 10:05: 1
Session, gap limit 2 minutes Session 1: 10:00:10 to 10:02:05 (4 events). Session 2: 10:04:30 (1 event)

Check yourself:

  • How many hopping windows (5 minutes, hop 1 minute) contain a given event?
  • What decides the end of a session window?