## Design an Ad Frequency Capping System Design a **frequency capping** system for an advertising platform. The system must ensure that a user does not see the same advertisement more than a configured number of times within a given time window. Representative limits include: - at most **3 impressions** per user per ad per day - at most **10 impressions** per user per campaign per week Your design should address each of the following: - how the ad-serving system checks caps **in real time**, before an ad is shown - how impressions are **counted and stored** - how to support multiple **cap scopes**, such as user-ad, user-campaign, or household-level limits - how to handle **high QPS, low latency, and eventual consistency** across regions - what happens when counting data is **delayed, duplicated, or arrives out of order** - **data retention**, expiration of old counts, and the operational trade-offs between accuracy and latency ```hint Where to start There are two very different workloads hiding in this prompt: deciding whether an ad may be shown, and recording that it was shown. They have opposite performance profiles — one is latency-critical and on the request path, the other is high-volume and can tolerate slack. Notice the tension before committing to a single store or pipeline for both. ``` ### Clarifying Questions to Ask - What is the expected **ad-serving QPS** and the read-latency budget per cap check (e.g. p99 under a few ms)? - How many **distinct cap scopes** must be supported per ad request (user-ad, user-campaign, household), and can several caps apply to a single candidate ad simultaneously? - Are the time windows **calendar-aligned** (per UTC/local day, per ISO week) or **rolling** (last 24 hours)? Does timezone matter? - How **strict** must enforcement be — is a small, bounded overshoot acceptable, or must the cap be exact even under concurrency and across regions? - Is serving **single-region or global**, and what is the tolerance for cross-region inconsistency? - On a counter-store outage, should the system **fail open** (keep serving, risk violations) or **fail closed** (stop serving, lose revenue)? Is this configurable per campaign? ### Constraints & Assumptions - **Scale:** assume a large ad platform — high ad-serving QPS with a tight per-check latency budget (single-digit milliseconds), and a high-volume impression event stream. - **Caps:** multiple configurable limits per scope (user-ad, user-campaign, user-advertiser, household-campaign) over hourly / daily / weekly / rolling windows. - **Correctness target:** reasonable accuracy despite duplicate, delayed, or out-of-order events; a small bounded overshoot is acceptable by default unless a campaign opts into stricter enforcement. - **Availability:** the serving path must stay highly available; the system spans multiple regions. ```hint The crux to reach Once read and write are separated, the central judgment call is *how fresh the counts on the decision path need to be*. Be explicit about where you'd tolerate a stale count (and therefore a bounded violation) versus where correctness is worth extra cost — and let the per-campaign strictness requirement, concurrency, and the multi-region picture drive that decision rather than a single global stance. ``` ### What a Strong Answer Covers These are the **dimensions an interviewer evaluates** — signals to look for, not a prescribed design: - **Path separation:** whether the candidate recognizes the decision path and the impression-recording path as distinct concerns with different latency/throughput needs, rather than conflating them. - **Data model:** whether cap rules are modeled in a way that supports several scopes and window types, and whether the candidate proposes a counting key that distinguishes *scope* and *time window* (regardless of the exact encoding). - **Read path:** whether the candidate keeps the per-request eligibility check cheap and bounded when multiple caps apply to multiple candidate ads. - **Write path:** whether impressions are recorded durably and reliably feed whatever maintains the counts. - **Consistency trade-offs:** whether the candidate reasons explicitly about freshness vs. latency/cost and matches different strategies to different strictness requirements, instead of asserting one approach everywhere. - **Reliability:** whether the candidate addresses duplicate, delayed, and out-of-order events, and safe behavior under concurrent requests for the same user. - **Lifecycle:** whether short-lived counts and longer-lived raw event history are treated differently, with sensible expiration. - **Scale & failure:** whether the candidate handles partitioning, hot keys, multi-region enforcement, pipeline lag, store outages, and the observability needed to detect overshoot. ### Follow-up Questions - How does the design change at **100x scale** or when a single campaign or user becomes a **hot key** that bottlenecks one counter shard? - A campaign requires **exact** enforcement (no overshoot, ever). What do you add, and what does it cost in latency and complexity? - The aggregation pipeline **falls hours behind**. How do you detect it, how do serving decisions degrade, and how do you recover the correct counts? - An ad is **selected but never actually rendered** (user scrolls past, page abandoned). How do you avoid over-counting impressions that were reserved but not shown?