Design Count Unique Active Users

You run analytics for a company with several apps and about 180 million monthly users. Leadership, product teams and the investor deck all want the same family of numbers: DAU, WAU, MAU, the ratio between them, and the same figures broken down by country, platform and app. Product managers also want ad hoc windows ("unique users between the launch and the outage") and a live view of today that is no more than a minute behind.

The trap is that distinct counts are not additive. If 40 million people used the app on Monday and 41 million on Tuesday, the two-day figure is somewhere between 41 and 81 million, depending on overlap. You cannot store one integer per day and add them up. Storing the full list of user ids for every day and every segment works, but the storage and the cost of unioning large sets for every chart grows quickly.

So the question is really: what is the smallest thing you can store per bucket that still lets you union buckets later? The answer most production systems reach is a probabilistic sketch, with an exact batch path for the handful of numbers that must be precise.

Take 180M monthly users, about 60M on an average day, each sending around 40 qualifying events a day. Segments are 3 apps, 4 platforms and about 200 countries, so up to 2,400 fine-grained combinations, though many are tiny.

Two details are worth calling out. Every response says whether the number is an estimate and gives its error band, so nobody pastes a sketch estimate into a board report as if it were exact. And ingest returns 202 as soon as the event is in the queue; counting happens later and never blocks the client.

Collectors accept batches, validate them and write to a Kafka topic keyed by user id. Keying by user keeps each person's events on one partition, which lets downstream jobs deduplicate and stitch identities with local state instead of a shared lookup on every event.

A stream processor (Flink, or Kafka Streams at smaller sizes) reads the topic, drops non-qualifying event types, resolves the person id, and adds that id to the HLL sketch for the right half-hour bucket and every segment the event belongs to. It keeps sketches in memory and flushes changed ones every 10 seconds to Redis for the live view and to a durable sketch store, a wide-column table keyed by (metric, segment, bucket_start).

In parallel, raw events land in the data lake. A nightly batch job rebuilds the previous day's sketches from the lake, which absorbs late events and any stream bugs, and computes exact daily sets for the top-level metrics as compressed bitmaps. The query service never counts events. It fetches the buckets a window needs, merges them, and reads one estimate off the merged sketch.

Hash each person id to 64 uniformly random-looking bits. In a set of random numbers, about half start with a 0, a quarter with 00, an eighth with 000. If the longest run of leading zeros you have seen is 20, you have probably seen something like 2²⁰, about a million, distinct values. One such observation is very noisy, so HyperLogLog splits the stream into many registers using the first few bits of the hash, keeps the longest run seen in each, and combines them with a harmonic mean, which keeps a single unlucky register from skewing the result.

With 2¹⁴ registers of 6 bits each the sketch is 12 KB and the standard error is about 0.81%, which means 95% of estimates land within about 1.6% of the truth. Doubling the registers cuts the error by a factor of only about 1.4, so p = 14 is a common sweet spot. Small segments use a sparse encoding that stores only non-zero registers, so a country with 3,000 users costs a few hundred bytes, not 12 KB. At very low counts the algorithm switches to a different estimator (linear counting) that is accurate for small sets.

Two sketches built with the same hash and register count merge by taking the larger value in each register. The result is exactly the sketch you would have got by feeding both streams into one. That single property powers the whole design:

HyperLogLog has one big weakness: it supports union but not intersection. You can estimate "used both iOS and web this week" by inclusion and exclusion, but the errors of the three terms compound, and for a small overlap the answer can be meaningless. For the handful of retention metrics that need set operations, keep a theta sketch alongside. Theta sketches keep the smallest hash values seen, which makes intersection and difference straightforward at the price of more memory.

For the top-line numbers that finance signs off on, run an exact path: map each account to a dense integer once, and store each day's active users as a Roaring bitmap. A month is the OR of thirty bitmaps, which takes milliseconds. This is affordable for a few metrics, not for 2,400 segments.

Phones batch events while offline and send them hours later. The stream job places each event by its client timestamp, clamped to between 72 hours in the past and five minutes in the future to stop broken device clocks from creating activity in 1970 or next year. Because adding to a sketch is idempotent and order-free, a late event simply updates an older bucket, and the nightly rebuild catches anything the stream missed.

Identity needs a decision. If a person browses anonymously on the web and then signs in, counting both the device id and the account id makes them two people. The identity resolver keeps a map from device to account and counts the account once known. Merges discovered later are reconciled only in the nightly job; the live number is allowed to be slightly high, and the API labels it so.

Finally, filter automated traffic before counting. A crawler cycling through fresh device ids can add hundreds of thousands of "users" in an hour. Apply rules on request rate, user agent and server-side signals in the collectors, and keep a separate sketch of filtered traffic so analysts can see what was removed.