system-design

Design an Ad Click Aggregator (Real-Time Analytics)

Difficulty: Tier 3 Asked at: Meta, Google, Amazon, ad-tech companies Time budget: 45–60 min

Every ad click is an event; advertisers want near-real-time counts (“how many clicks on campaign X in the last minute”) plus accurate billing. This is the canonical stream-processing question: a firehose of events, aggregated into time-windowed counts, with the tension between real-time approximate and batch-accurate results — the Lambda/Kappa architecture. It underpins view counts, likes, metrics, and dashboards throughout this repo.

Prerequisites: Batch vs Stream, Kafka, Idempotency

1. Requirements

Functional:

Ingest ad click events (ad_id, user, timestamp, context).
Aggregate counts per ad/campaign over time windows (per-minute, hourly, daily).
Serve near-real-time dashboards and accurate billing totals.
Support queries: “clicks for campaign X grouped by minute over the last hour.”

Non-functional:

Very high volume — millions of clicks/sec.
Low-latency aggregates for dashboards (seconds).
Accuracy for billing — advertisers are charged, so totals must eventually be exactly right.
Handle duplicates (retries, double-fires) and late/out-of-order events.

Out of scope: ad serving/targeting, fraud/bot detection (separate — though click fraud matters).

2. Estimation

1M clicks/sec, each ~100 bytes → 100 MB/sec ingest → hundreds of TB over time. Partition + stream.
Two consumers of the same stream: a fast path (approximate, seconds-fresh dashboards) and a slow path (batch, exact, for billing). 🚨 This dual requirement drives the architecture.

3. The core tension: real-time vs accurate

🚨 You need both fast and correct, and they conflict:

Real-time aggregation (stream processing) is fast but approximate — it may miss late events, double- count on failures, or use approximations.
Batch aggregation (reprocess the raw event log) is slow but exact — perfect for billing.

Two architectures resolve this:

Lambda architecture: run both — a speed layer (stream, approximate, fresh) and a batch layer (exact, authoritative), and serve a merged view (recent from speed layer, older from batch). Duplicated logic is the downside.
Kappa architecture: a single stream-processing path that’s replayable — reprocess the log through the same stream engine for corrections. Simpler; the modern preference.

4. High-level design

flowchart LR
    Click[Click events] --> Q[[Event log / Kafka<br/>partitioned, durable]]
    Q --> Stream[Stream processor<br/>windowed aggregation]
    Stream --> RT[(Real-time store<br/>recent counts)]
    RT --> Dash[Dashboards]
    Q --> Batch[Batch job<br/>exact recompute]
    Batch --> Billing[(Authoritative totals<br/>billing)]

Ingest all clicks into a durable, partitioned event log (Kafka) — the source of truth. A stream processor consumes it, computes windowed aggregates, and writes recent counts to a fast store for dashboards. A batch job (or replayable stream) recomputes exact totals from the raw log for billing.

🚨 Store the raw events durably first — everything downstream is a re-derivable view; the raw log lets you recompute after bugs or for exactness.

5. Deep dives

5a. Windowed aggregation & watermarks

Aggregate into time windows (tumbling per-minute, etc.). Events arrive late/out-of-order (mobile networks, retries), so a naive “count per wall-clock minute” is wrong. Use event-time windows with watermarks — wait a bounded grace period for late events before finalizing a window, then emit. 🚨 Late data is the subtle hard part of stream processing — name event-time vs processing-time and watermarks.

5b. Exactly-once / dedup for billing

Duplicates (a client retries a click beacon, a stream reprocesses) would over-bill. Defend:

Idempotent counting — each click has a unique ID; dedup on it (a set / bloom filter of seen IDs per window, or exactly-once stream processing with transactional state). (Idempotency)
The batch/replay path recomputes from the deduplicated raw log for the authoritative total. 🚨 Billing must be exact; dashboards can tolerate slight over/undercount.

5c. Scaling ingestion & aggregation

Partition the event log by ad_id/campaign so all of a campaign’s clicks aggregate on one partition/worker (local, ordered counting). Stream processors scale with partitions. Pre-aggregate at the edge (combine counts before shipping) to cut volume. This is Kafka + a stream engine (Flink/Spark Streaming).

5d. Serving queries (roll-ups)

Precompute rollups at multiple granularities (minute → hour → day) so a “last 24h by hour” query reads 24 precomputed buckets, not millions of events. Store in a fast queryable store (a time-series or OLAP store). Same precompute-rollups idea as the metrics system.

5e. Approximate algorithms (when exactness isn’t needed)

For “unique users who clicked” at massive scale, exact distinct counts are expensive → HyperLogLog (approximate cardinality, tiny memory). For “top-K ads,” count-min sketch. 🚨 Use approximations for dashboards where a small error is fine, exact recompute for billing. (Probabilistic Data Structures)

6. Bottlenecks & scaling further

Ingest volume → durable partitioned log, edge pre-aggregation.
Real-time aggregation → partitioned stream processing by campaign.
Accuracy vs speed → Lambda/Kappa: fast approximate + exact batch/replay.
Late/out-of-order → event-time windows + watermarks.
Duplicates → idempotent counting; exact recompute for billing.
Query latency → precomputed multi-granularity rollups.

7. Trade-off summary

Decision	Chosen	Alternative	Why
Architecture	Kappa (replayable stream) / Lambda	Single batch or single stream	Need both fresh and exact
Source of truth	Raw durable event log	Aggregated counts only	Re-derive/correct any view; enable exactness
Windows	Event-time + watermarks	Processing-time	Correct under late/out-of-order events
Billing counts	Exact (dedup + batch)	Approximate	Advertisers are charged; must be right
Dashboard counts	Approximate OK (HLL etc.)	Exact	Speed and memory over tiny error

8. Follow-up questions

Why do you need both a real-time and a batch path?

Because the two requirements — near-real-time dashboards and exact billing — conflict, and no single path serves both well. Real-time stream aggregation gives you counts within seconds, which advertisers want for live dashboards, but it's approximate: it may not yet include late-arriving events, can double-count under failure/retry, and often uses approximations for speed. Billing, by contrast, must be exactly right because advertisers are charged real money, which requires waiting for all events (including late ones), deduplicating precisely, and being able to recompute authoritatively. So you run a fast speed layer (stream) for fresh approximate numbers and a slow batch (or replayable stream) layer that recomputes exact totals from the raw event log for billing — the Lambda pattern — or you use a single replayable stream (Kappa) that you reprocess for corrections. Either way, you store the raw events durably as the source of truth so every aggregate is a re-derivable view, letting the fast path be approximate while the authoritative path is exact. The dual path is the direct consequence of needing both immediacy and correctness.

Events arrive late and out of order. How do you count correctly per minute?

By windowing on *event time* (when the click actually happened, carried in the event) rather than *processing time* (when it reached your system), and using watermarks to decide when a window is complete. If you counted by wall-clock arrival, a click that happened at 12:00:59 but arrived at 12:01:03 (slow mobile network, a retry) would wrongly land in the 12:01 minute. Event-time windows assign each event to the minute it occurred; but since you can't wait forever for stragglers, a watermark tracks how far event-time has progressed and lets you hold a window open for a bounded grace period to absorb late events, then finalize and emit it — with a policy for anything arriving after (drop, or emit a correction). This trades a little latency (you wait out the grace period before a window is final) for correctness under the reality that distributed event streams are always somewhat late and out of order. Event-time-plus-watermarks is the standard, and subtle, answer to "count correctly over time."

How do you prevent double-counting from inflating an advertiser's bill?

By deduplicating on a unique event identifier and reserving the exact total for a path that counts each distinct click once. Every click event carries a unique ID, and the counting logic tracks which IDs it has already seen — via a set or bloom filter of seen IDs per window for the stream path, or exactly-once stream processing with transactional state — so a retried click beacon or a reprocessed event doesn't increment the count twice. Crucially, the authoritative billing total is computed by the batch/replay path over the raw, deduplicated event log, which can be recomputed deterministically and exactly, rather than trusting the fast approximate stream. Dashboards can tolerate a slight over- or under-count from the speed layer, but billing goes through the exact, idempotent recomputation. So duplicates are handled by idempotent counting keyed on event IDs, and billing correctness is guaranteed by recomputing exact totals from the deduplicated source-of-truth log.

When would you use approximate algorithms like HyperLogLog here?

For dashboard metrics where a small, bounded error is acceptable and exactness would be prohibitively expensive — most commonly counting *distinct* things at massive scale, like the number of unique users who clicked an ad. Computing an exact distinct count requires remembering every unique ID seen, which at millions of clicks per second consumes enormous memory; HyperLogLog estimates cardinality within a couple percent using a tiny fixed amount of memory, which is perfect for a live "unique clickers" dashboard number where being off by 1% doesn't matter. Similarly, count-min sketch approximates per-key counts for "top-K ads" cheaply. You deliberately confine these approximations to the real-time/dashboard path, where speed and memory efficiency outweigh a tiny inaccuracy, and never to billing, where the exact recompute path counts precisely because money is involved. Matching approximate structures to error-tolerant queries and exact recomputation to money is the judgment the question rewards.

9. What junior / mid / senior answers look like

Junior: increments a counter per click in a database. Can’t handle the volume, duplicates, late events, or the billing-vs-dashboard tension.
Mid: durable event log + stream processor with windowed aggregation, a fast store for dashboards, dedup, precomputed rollups.
Senior: frames the real-time-vs-exact tension explicitly (Lambda/Kappa), keeps the raw log as source of truth, handles late/out-of-order data with event-time windows + watermarks, guarantees exact billing via idempotent dedup + batch recompute, and applies approximate structures (HLL/count-min) only where error is tolerable — connecting it to view counts/likes/metrics elsewhere.