Web Analytics

The problem

"Design a web analytics service like Google Analytics." Thousands of customers put your tracking script on every page of their sites and open a dashboard of page views and unique visitors, over any date range.

This practice problem reuses the pattern of Design an Ad Click Aggregator. What's new: events from pages you don't own, unique visitors, ranges from an hour to a year, and many customers sharing one pipeline. Nobody is billed per page view, so unlike ad clicks a few lost events are fine. Park funnels for later.

The numbers

From the interviewer: 50,000 customer sites, 5 billion page views a day in all, and busy hours at about 5× the average. Round a day to 100,000 seconds: 50,000 page views a second on average (about 58,000 with 86,400), so about 250,000 a second at busy hours, 2.5× the ad clicks' peaks. Dividing by the 1,440 minutes of a day instead gives page views a minute, a common slip.

Sending events from pages you don't own

The script runs inside your customers' pages, so it must never slow them down. Say a page view brings about 5 events (the view, scrolls, clicks, leaving): the script queues them and sends them in one beacon, every few seconds and as the visitor leaves:

POST /collect
{"site": "news", "visitor": "9f2c…",
 "events": [{"type": "view", "page": "/results"},
            {"type": "scroll"}]}
→ 204 No Content

A beacon is fire and forget: the browser sends it in the background, even while the page closes, and the collector answers 204 at once and appends the events to the stream. Load the script with async, so the page never waits for it either.

• Waiting for an answer adds a round trip to every page, and hangs them whenever your collector is slow or down.
• One request per event doesn't wait, but makes 5 requests per page view: about 1.25 million a second at busy hours instead of 250,000.

Unique visitors: a HyperLogLog per site per day

A unique visitor counts once however many pages they read, so adding 1 per page view won't do. Each visitor carries a random 16-byte id kept by the script. An exact count needs the set of ids seen: the news site, your biggest customer, has about 50 million visitors a day, so 50 million × 16 bytes ≈ 800 MB for one site's day, in an aggregator's memory.

The usual answer is a HyperLogLog: a small sketch that estimates how many distinct ids it has seen, within about 1%. It hashes each id: the first 14 bits of the hash pick one of 16,384 slots, and each slot keeps the longest run of leading zeros seen in the rest. Long runs are rare, so the slots together tell how many different hashes went by; a repeated id changes nothing. 16,384 slots of 6 bits are 12 KB, with a typical error of 1.04 ÷ √16,384 ≈ 0.8%. Google has published that Google Analytics 4 estimates its active users and sessions with HyperLogLog++, a refined version.

Any date range: hour and day rollups

Counting raw events for every dashboard would scan billions, so the aggregators keep rollups: a row per site and page for each hour, rolled up into a row per day when the day ends, and each site's day keeps its sketch. A range reads whole days from day rows and the hours at its ends from hour rows:

question                       reads
page views 9:00 to 17:00       8 hour rows (no day row yet)
page views, 1 March–30 June    122 day rows, not 2,928 hour rows
unique visitors in March       31 day sketches, merged
unique visitors this year      365 sketches, about 4.5 MB

Page views add up across rows. Unique visitors don't: a reader who came on 5 days would count 5 times. Sketches merge instead: keep the larger value of each slot, and the result is the sketch of all those days' visitors. Take a blog whose 15,000 regulars come every day, plus 5,000 new visitors a day:

the blog in March           unique visitors
each day                    20,000
31 daily counts, added      620,000
31 sketches, merged         ≈ 170,000 (really 170,000)

Many customers, one huge site

Most of the 50,000 sites get a few views a minute. Split the event stream by site_id: each site's counts and sketch stay whole on one aggregator, and a flood from one site lands only on its own partition.

On election night the news site sends 60,000 page views a second; say one aggregator counts about 20,000. Give a site that big several keys, news#0 to news#3, on partitions of its own: 60,000 ÷ 20,000 = 3 at least, so 4 keys at about 15,000 a second each. Its 4 counts add up and its 4 sketches merge. A per-site limit at the collector also caps floods such as a bot.

Round robin would scatter every site over every partition and let one flood slow everyone; a pipeline per customer would mean 50,000 pipelines, nearly all idle.

Same pattern as the Ad Click Aggregator

The pipeline carries over: a collector appends events to a stream; aggregators count in memory and write each closed hour once; raw events are copied to object storage, so a bug fix can be recounted. Event time and a watermark handle late beacons from phones that were offline, and counts saved with their offsets survive a crash.

Summary

• Scope: page views and unique visitors for 50,000 sites, over any range.
• API: the script's beacon, POST /collect, answered 204 at once.
• Numbers: about 250,000 page views a second at busy hours.
• Scale: split by site_id; a huge site on keys of its own.
• Unique visitors: a HyperLogLog per site per day, 12 KB, within about 1%.
• Date ranges: hour and day rollups; sketches merged, never added.