Active Users in the Last N Minutes

Sliding window of distinct users

Design a counter that answers how many distinct users were active in the last N minutes, with an exact version for one fixed window and a bucketed version for any window.

Overview

Every dashboard has a number like 'users active in the last 5 minutes'. Events arrive all the time: a page view, a click, a heartbeat, each with a user id and a time. The system must answer, at any moment, how many distinct users sent at least one event inside the window. Counting events is easy; counting distinct users in a window that keeps sliding is the real problem.

Interviewers use it to see whether you pick the data structure from the question. If the window is one fixed size, you only need each user's last active time, kept in time order, and the count is almost free. If callers may ask for any window up to an hour, you need the history split into time buckets. If there are hundreds of millions of users, you stop storing ids and estimate with a HyperLogLog sketch. A strong answer asks which case applies before writing code.

Scoping the problem

Ask these questions before you write code; each answer changes the data structure.

One fixed window, or any window up to a maximum? — Fixed: one ordered map is enough. Any: time buckets — Start with fixed 5 minutes; then any window up to an hour
Distinct users or events? — Distinct needs a set or an ordered map; events need only counters — Distinct users
Exact, or is about 1% error fine? — Exact stores every active id; approximate uses a fixed-size sketch — Exact for now; approximate at scale
Do events arrive in time order? — The ordered-map design needs it; buckets tolerate late events — In order from one server's clock
Do you also need the ids, or only the count? — A sketch gives only a count — Count, sometimes ids
One process, or many servers? — Many servers need a merge step that does not double count — One process first

One fixed window: last-seen in time order

Keep one entry per user: their last active time. Keep the entries ordered by that time, oldest first. On each event, set the user's time and move them to the back. To count, drop entries from the front while they are older than the window, then return the size. Each user is dropped at most once per activity, so the eviction is O(1) amortized, and memory holds only users who are still active.

Python's OrderedDict does exactly this: move_to_end sends a key to the back and popitem(last=False) removes the front.

The trace is the demo in the code. The window is 300 seconds; a user counts while their last event is less than 300 seconds old.

1 — record ann at 0, bob at 60 — ann 0, bob 60
2 — record ann at 200 — bob 60, ann 200 — ann moved to the back
3 — record cid at 250 — bob 60, ann 200, cid 250
4 — count at 300 — unchanged: bob is 240 s old — 3
5 — count at 360 — ann 200, cid 250 — bob dropped: 300 s old; 2
6 — count at 501 — cid 250 — ann dropped; 1

Any window: time buckets

When callers ask for 1, 5 or 60 minutes, one last-seen time per user is not enough: a user seen 3 minutes ago and 40 minutes ago must count in both windows. Split time into buckets of b seconds, keep a set of users per bucket, and answer a query by taking the union of the buckets in the window. The union matters: summing the bucket sizes counts a user once per bucket.

Bucket key ts - ts % b — Every server puts an event in the same bucket, whatever time it started
Window in whole buckets — The window starts at a bucket boundary, so it can miss up to b seconds at its old edge; say so
Drop buckets older than max_window on each query — Memory stays bounded without a background thread
Late events — Accepted if their bucket is still inside max_window

A query costs the total size of the sets in the window, not O(1). That is the price of answering any window.

What you will be able to do

Ask the scoping questions that decide between an ordered map, buckets and a sketch.
Build the fixed-window counter with an ordered map and explain why its count is O(1) amortized.
Build the bucketed counter, union its sets, and state its edge error of up to one bucket.
Explain when to switch to HyperLogLog and what you give up.
Merge counts from many servers without counting a user twice.

Functional requirements

record(user, ts) notes that a user was active at time ts
count(now) returns the number of distinct users with an event in the window ending at now
The fixed-window counter answers one window size; the bucketed counter answers any whole number of buckets up to max_window
users(now, window) returns the ids themselves, for the bucketed counter
Refuse what the design cannot answer correctly: timestamps that go backwards in the fixed-window counter, windows that are not whole buckets

Non-functional requirements

Fixed window: record O(1), count O(1) amortized, memory O(users active in the window)
Buckets: record O(1), count O(total ids in the window buckets), memory bounded by max_window
Thread safe: each counter guards its state with one lock
Time is injected, so tests are exact and repeatable

Interview questions

Why not keep a list of every event and scan it?
How do you pick the bucket size?
There are 200 million users. What changes?
Ten servers each see some of the traffic. How do you get one number?
Is one lock per counter enough? What about the clock?