Problem RestatementProblem
A frequency cap limits how often one person sees an ad. For example: "show this campaign to a user at most 3 times in any 24 hours" or "at most 10 times per week per line item". Showing the same ad too often annoys viewers and wastes the advertiser's money.
Design the service the ad server calls on every ad request: "for this user, which of these candidate ads are still under their caps?" It must answer in a few milliseconds, and it must count every impression (a shown ad) correctly. This was asked at Netflix many times.
RequirementsRequirements
1.1 Functional
- Configure caps at several levels: ad (creative), ad group / line item, campaign, order or advertiser, each with a count and a window (e.g., 3 per 24h rolling, 10 per 7 days).
- Check: given a user and ~50 candidate ads, return which are allowed.
- Record: count each impression once, when it's actually shown.
1.2 Non-Functional
- Latency: check in under ~5 ms at p99, since it sits inside ad serving (whose total budget is ~100 ms).
- Throughput: 100K+ ad requests/sec.
- Accuracy: small overshoot is tolerable, while big overshoot breaks advertiser trust.
- Available: if the service fails, ad serving must still work (with a safe fallback).
1.3 Scale Estimates
- 50M viewers, and the active capped entities per user are small (tens).
- Checks: 100K requests/sec × 50 candidates × ~3 cap levels = 15M counter reads/sec, but batched per user into 1–2 round trips.
- Impressions: ~20K/sec written.
1.4 API Design
POST /v1/fcap/check{ user_id, candidates: [{ ad_id, line_item_id, campaign_id }] }→{ allowed: [ad_id, ...] }- Impressions arrive as events (Kafka) from players or ad servers:
{ impression_id, user_id, ad_id, line_item_id, campaign_id, ts } - Admin: caps are stored with the campaign configuration.
High-Level ArchitectureArchitecture
2.1 Overview
- Cap config cache: caps per entity, loaded in memory in the fcap service (they change rarely).
- Counter store: Redis Cluster (or a similar in-memory KV), sharded by user_id, so all of one user's counters live on one shard and one call fetches them.
- FCap check service: stateless and close to the ad servers.
- Impression consumer: reads impression events, deduplicates and increments counters.
2.2 Architecture Diagram
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
AS["Ad Server"] -->|"check user + candidates"| FC["FCap Service - cap config in memory"]
FC -->|"1 batched read per user"| R[("Redis - counters by user")]
FC -->|"allowed ads"| AS
PL["Players / ad server"] -->|"impression events"| K[("Kafka - by user_id")]
K --> IC["Impression consumer - dedupe"]
IC -->|"increment buckets"| RCounting in Rolling Windows
"3 times in any 24 hours" is a rolling window. Storing every impression timestamp works but is heavy. Instead, use time buckets:
- For a 24h window, keep 24 hourly buckets per (user, entity). For a 7-day window, 7 daily buckets (or 28 six-hour buckets for better precision).
- Count in window = sum of the buckets inside the window. The oldest bucket is only partly inside the window. Either count all of it (a little conservative: may block slightly early) or weight it.
fc:{user_id}:{yyyymmdd} with fields li:{line_item}:{hour} → count, TTL 8 days. A check fetches the few day-hashes needed in one pipelined call to that user's shard.
Key FlowsFlows
4.1 Check
- Receive user + candidates. Look up each candidate's caps (ad, line item, campaign) from in-memory config.
- Fetch the user's relevant hashes from Redis (1–2 round trips).
- For each candidate, compute counts per cap level. The ad is allowed only if every level is under its cap.
- Return the allowed list. Ad selection then picks from these.
4.2 Record
- When the ad actually plays (not just when selected), an impression event is sent to Kafka with a unique
impression_id. - The consumer drops duplicates (a
SET NXonimp:{id}with a 2-day TTL), thenHINCRBYthe right buckets for each cap level.
Deep Dive A — The gap between checking a cap and recording the impressionDeep dive
We check the counter, serve the ad, and record the impression when it renders. Those are seconds apart, and a user opening six tabs lives entirely inside that gap.
Check the counter, serve, record later
The ad server asks "is user 42 under the 3-per-day cap for campaign 9?", gets yes, serves the ad, and the impression beacon arrives a second or two later.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
sequenceDiagram
participant U as User - opens 5 tabs
participant A as Ad server
participant R as Counter store
U->>A: 5 requests within 200 ms
A->>R: count for user 42 - campaign 9
R-->>A: 0 - under cap, five times over
A-->>U: serves the ad 5 times
Note over R: impressions land seconds later - count jumps 0 to 5The counter is only as current as the last beacon, so the cap is enforced against stale data. Under normal browsing this is invisible; under tab-opening, prefetch or a retargeting burst the advertiser pays for five impressions against a cap of three.
Accept a small overshoot, and keep the write path short
Shrink the gap instead of closing it: record the impression as early as the product allows, keep counters in memory next to the ad server, and treat the cap as a target rather than a hard limit.
For a 24-hour cap this is usually the right answer, and most ad platforms ship it. Be explicit about what it costs — the cap can be exceeded by roughly the number of requests in flight for that user, which is small in the common case and unbounded in the pathological one.
Reserve on selection, then confirm or release
When the ad server picks an ad, increment a pending counter for that user and campaign immediately. The impression beacon confirms it; a timeout releases it.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SEL["Ad selected"] --> RES["pending + 1 - counted against the cap now"]
RES --> SERVE["Ad served"]
SERVE -->|"beacon arrives"| CONF["confirmed + 1, pending - 1"]
SERVE -->|"no beacon in 30 s"| REL["pending - 1 - slot returned"]The cap is now enforced at the moment of the decision, so concurrent requests see each other. It costs one extra write per selection and a sweeper for abandoned reservations — worth it for high-value caps (a $50 CPM campaign, a legally mandated frequency limit), not worth it for house ads.
Pick per campaign, not per system. The interesting answer is that both modes exist and the cap's value decides which one runs.
Deep Dive B — Failures, regions and late eventsDeep dive
- Redis slow or down: fcap must never block ad serving. Use a strict timeout (e.g., 3 ms). On failure, either serve without caps (risk of over-frequency) or only serve uncapped or house ads. It's a business decision, and a "fail open with alerts" default is typical.
- Multi-region: users usually stay in one region, so keep a user's counters in their home region, and replicate asynchronously for failover. Small inaccuracy during failover is acceptable.
- Late impressions (offline TV apps upload later): increment the bucket for the impression's own time, not arrival time. If the window already passed, it doesn't matter.
- Cap changes: caps live in config, and counters are just counts, so raising or lowering a cap applies immediately without migrating data.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Window counting | Time buckets (hourly/daily) | Small, fast, easy to expire | Per-impression timestamps: exact, heavy |
| Sharding | By user_id | One call per request | By ad: many calls per request |
| Counting point | On confirmed impression | Matches what users saw | On selection: counts ads never shown |
| Failure mode | Timeout + fail open (configurable) | Protects revenue and latency | Fail closed: no ads when Redis is down |
Common Follow-up QuestionsFollow-ups
- "Household caps?" Key counters by household ID instead of (or as well as) user ID.
- "Why not a database?" Millions of counter reads per second in under 5 ms need an in-memory store. A DB can hold the audit trail of impressions.
- "How do you test accuracy?" Replay impression logs offline, compute exact rolling counts, and compare them with the bucketed counts.
Wrap-UpWrap-up
Keep caps in memory, keep per-user rolling-window counters as time buckets in Redis sharded by user, and answer each ad request with one batched read that checks every cap level. Count only confirmed impressions, deduplicate by impression ID and bucket by event time, accept small overshoot or use reservations for stricter caps, and use strict timeouts so frequency capping can never slow down or stop ad serving.