Design: Ad Serving System¶

Difficulty: Senior → Staff | Time: 60 minutes

1. Problem Statement¶

Design the system that decides which ad to show when a page or app requests one. A publisher's page loads, hits an ad slot, and fires an ad request. Within a hard latency budget, the system must: find every advertiser campaign eligible to fill that slot (targeting match), run an auction among them, confirm the winner still has budget remaining, and return a single winning ad — all before the page finishes rendering.

The defining constraint is not "rank well." It's that three things must all be true inside single-digit milliseconds: the auction must consider many eligible bidders, the winner's budget must be checked and reserved, and a response must go out — because the ad slot is rendering right now, on a page the user is actively loading. Miss the window and the slot renders blank or falls back to a lower-value house ad; publisher revenue and user experience both degrade in real time.

Contrast this with a recommendation system: recommendations optimize relevance — which items best match a user's taste — typically inside a 100–200ms budget, and getting a suggestion 2% less relevant costs nothing measurable. Ad serving optimizes an auction under a hard budget constraint with real money changing hands on every decision, inside a latency budget 10–20x tighter. A recommendation service that's briefly stale serves a slightly worse list. An ad system that's briefly wrong either overspends an advertiser's money (a billing incident) or underspends it (a broken promise to a paying customer) — and it has roughly 5-10ms to get the decision right, not 100-200ms.

2. Clarifying Questions¶

3. Functional Requirements¶

• Accept an ad request (slot metadata, user/context signals) and return a winning ad within the latency budget
• Filter campaigns to those eligible: targeting match, budget remaining, active date range, frequency cap not exceeded
• Run an auction among eligible campaigns and select a winner (plus clearing price)
• Record impressions and clicks, and deduct spend against the correct campaign's budget
• Support advertisers creating/pausing/updating campaigns, bids, and budgets without a deploy
• Never serve a campaign whose budget is exhausted

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Ad requests:
  500K requests/second peak, 100K/s average
  Each request evaluates against targeting-filtered eligible set

Eligible advertisers per request (after targeting filter):
  200K active campaigns total, but geo/device/segment targeting
  typically narrows this to 50-500 eligible bidders per request
  Auction only ranks the narrowed set, not all 200K

Campaigns:
  200K active campaigns, ~20K updating budget/targeting per hour (self-serve UI)

Budget-check operations:
  1 check-and-reserve per ad request (for the eventual winner) = 500K ops/sec peak
  Plus periodic reconciliation writes from the tracking pipeline (impressions/clicks)
  ~500K impression events/sec + ~5K click events/sec (1% CTR) feeding back into spend

Memory for in-memory eligibility/auction data:
  200K campaigns x ~2KB (targeting rules + bid + budget state) = 400MB
  Fits entirely in RAM per auction-service replica — no DB call in the hot path

Latency budget allocation (10ms total):
  Network in/out: ~2ms
  Eligibility filter (in-memory index scan): ~1-2ms
  Auction (rank + pick winner among ~500 candidates): ~1-2ms
  Budget reserve (in-memory, local shard): ~1ms
  Buffer: ~2-3ms

6. API Design¶

# Ad request — called synchronously while the page/app is loading
POST /v1/ad-request
Request:
{
  "slot_id": "homepage-banner-300x250",
  "user_context": { "geo": "US-CA", "device": "mobile", "segments": ["sports", "auto-intent"] },
  "auction_type": "second_price"
}
Response (< 10ms):
{
  "ad_id": "camp_9182_creative_4",
  "clearing_price_cents": 42,
  "impression_token": "opaque-signed-token",   # required on the tracking callback
  "creative_url": "https://cdn.example/ads/..."
}
Status: 200 (won), 204 (no fill — no eligible bidder cleared reserve price)

# Tracking callbacks — fired by the client/SDK rendering the ad, async, not on the critical path
POST /v1/track/impression
{ "impression_token": "opaque-signed-token", "ts": "..." }

POST /v1/track/click
{ "impression_token": "opaque-signed-token", "ts": "..." }

# Control plane (advertiser self-serve, internal-authenticated)
PUT /internal/campaigns/{campaign_id}
{ "daily_budget_cents": 100000, "bid_cents": 50, "targeting": {...}, "status": "active" }
GET /internal/campaigns/{campaign_id}/spend   # near-real-time spend dashboard

7. Data Model¶

-- Durable campaign config + budget ledger. Not the hot path for reads.
CREATE TABLE campaigns (
    campaign_id     BIGINT PRIMARY KEY,
    advertiser_id   BIGINT NOT NULL,
    bid_cents       INT NOT NULL,
    daily_budget_cents    BIGINT NOT NULL,
    lifetime_budget_cents BIGINT,
    status          VARCHAR(16) NOT NULL,   -- active | paused | exhausted
    start_at        TIMESTAMPTZ NOT NULL,
    end_at          TIMESTAMPTZ,
    updated_at      TIMESTAMPTZ NOT NULL
);

-- Durable ledger: source of truth for spend, reconciled from tracking events
CREATE TABLE budget_ledger (
    campaign_id     BIGINT NOT NULL,
    day             DATE NOT NULL,
    spend_cents     BIGINT NOT NULL DEFAULT 0,
    last_reconciled_at TIMESTAMPTZ NOT NULL,
    PRIMARY KEY (campaign_id, day)
);

-- Targeting rules, indexed for fast eligibility filtering
CREATE TABLE targeting_rules (
    campaign_id     BIGINT NOT NULL,
    dimension       VARCHAR(32) NOT NULL,   -- geo | device | segment | keyword
    value           VARCHAR(128) NOT NULL,
    INDEX idx_dim_value (dimension, value)  -- inverted index: value -> campaigns
);

-- Billing-grade event log (append-only, high volume)
CREATE TABLE ad_events (
    impression_token VARCHAR(64) PRIMARY KEY,
    campaign_id     BIGINT NOT NULL,
    event_type      VARCHAR(16) NOT NULL,   -- impression | click
    clearing_price_cents INT NOT NULL,
    ts              TIMESTAMPTZ NOT NULL,
    INDEX idx_campaign_ts (campaign_id, ts)
);

Hot state (not SQL — see Version 2):

budget:{campaign_id}:{day}   → { remaining_cents, reserved_cents }  in-memory, sharded
targeting_index              → inverted index, value -> [campaign_id], cached locally per auction node

8. Version 1 — simplest thing that works¶

One service. Per request: filter eligible campaigns from Postgres, rank by bid, synchronously read-check-write the winner's budget row in the same database, return the winner.

graph LR
    Client -->|ad request| Svc[Ad Service]
    Svc -->|SELECT eligible campaigns| PG[(Postgres)]
    Svc -->|SELECT ... FOR UPDATE budget row| PG
    Svc -->|UPDATE spend| PG
    Svc -->|winning ad| Client

def handle_ad_request(context) -> dict | None:
    eligible = db.query(
        "SELECT * FROM campaigns c JOIN targeting_rules t ON c.campaign_id = t.campaign_id "
        "WHERE t.dimension = %s AND t.value = %s AND c.status = 'active'",
        "geo", context.geo,
    )
    ranked = sorted(eligible, key=lambda c: c.bid_cents, reverse=True)

    for candidate in ranked:
        with db.transaction():
            row = db.query_one(
                "SELECT remaining_cents FROM budget_ledger WHERE campaign_id=%s AND day=%s FOR UPDATE",
                candidate.campaign_id, today(),
            )
            if row.remaining_cents >= candidate.bid_cents:
                db.execute(
                    "UPDATE budget_ledger SET remaining_cents = remaining_cents - %s WHERE campaign_id=%s AND day=%s",
                    candidate.bid_cents, candidate.campaign_id, today(),
                )
                return {"ad_id": candidate.campaign_id, "clearing_price_cents": candidate.bid_cents}
    return None  # no fill

This is correct — every decrement is transactional, budget can never go negative. Ship it, measure it, then find the bottleneck.

9. Identify the bottleneck¶

10. Version 2 — in-memory auction, in-memory budget, async reconciliation¶

Move everything off the synchronous DB path. Each auction-service node caches campaign/targeting data locally (pushed from a control plane, invalidated fast on update). Budget lives in a sharded, in-memory store keyed by campaign_id, mutated with a fast in-process or single-hop operation — no relational transaction per request.

graph LR
    Client -->|ad request| Auc[Auction Service\nlocal campaign+targeting cache]
    Auc -->|reserve, in-memory| Bud[(Budget Shard\nin-memory remaining/reserved)]
    Auc -->|winning ad| Client
    Bud -.->|async batch| Ledger[(Durable Budget Ledger)]
    CP[Control Plane] -->|push campaign/targeting updates| Auc

# budget shard: one process per shard, campaign_id hashed to a shard
class BudgetShard:
    def __init__(self):
        self.remaining = {}  # campaign_id -> cents, loaded from ledger at boot

    def try_reserve(self, campaign_id: int, cents: int) -> bool:
        if self.remaining.get(campaign_id, 0) >= cents:
            self.remaining[campaign_id] -= cents
            return True
        return False

def handle_ad_request(context) -> dict | None:
    eligible = local_targeting_index.lookup(context)      # in-memory inverted index, no network call
    for candidate in sorted(eligible, key=lambda c: c.bid_cents, reverse=True):
        shard = budget_shard_for(candidate.campaign_id)     # local or one fast RPC hop
        if shard.try_reserve(candidate.campaign_id, candidate.bid_cents):
            emit_async(reservation_event(candidate, context))  # off critical path
            return {"ad_id": candidate.campaign_id, "clearing_price_cents": candidate.bid_cents}
    return None

The auction now touches zero synchronous databases. Eligibility is a local index lookup; budget is a local map mutation. Reservation events stream asynchronously to a durable ledger that periodically true-ups each shard's in-memory number.

11. Identify the next bottleneck¶

12. Version 3 — production architecture¶

graph TD
    Client -->|ad request| GW[Ad Request Gateway]
    GW --> Auc[Auction Service\nsharded, local campaign cache]
    Auc -->|targeting/bid data, fast invalidation| CP[Control Plane\ncampaign config]
    Auc -->|reserve + pace check| PS[Pacing + Budget Service\nin-memory counters, WAL]
    PS -->|async batch commit| Ledger[(Durable Budget Ledger\nPostgres/Spanner-like)]
    PS -->|pacing model: spend-so-far vs expected| PaceCalc[Pacing Calculator]
    Client -->|impression/click, async| Track[Tracking Ingest\nKafka]
    Track --> Reconcile[Reconciliation Worker]
    Reconcile -->|true-up spend| Ledger
    Reconcile -->|correct in-memory drift| PS
    Track --> Billing[Billing Pipeline]
    CP -->|invalidate on update| Auc

Key production decisions:

• Auction stays 100% in-memory. Campaign config, targeting index, and bid data are cached on every auction-service replica, pushed from the control plane on change with a fast invalidation (sub-second) rather than pulled per request.
• Budget/pacing service is the rate limiter's token bucket, but billing-grade. Same shape as rate-limiter.md's in-memory-slice-with-reconciliation pattern — each shard holds a working balance, writes a local write-ahead log of every reservation before acknowledging, and asynchronously batches those reservations into the durable ledger. The WAL is what the rate limiter didn't need: losing a reservation record there was a mild inconvenience; here it's the difference between "reconcile in 30 seconds" and "lose track of real money."
• Pacing runs as a probability multiplier, not a gate. At any point in the day, the pacing calculator computes expected_spend_by_now from the campaign's daily budget and a delivery curve, and throttles win eligibility (e.g., admit this campaign to the auction with probability min(1, target_pace / actual_pace)) rather than an on/off switch — this is what prevents a $1,000/day budget from vanishing in the first traffic spike.
• Tracking pipeline is fully async, fed by Kafka. It never blocks the ad-request path; it feeds the reconciliation worker, which is the actual source of truth for billed spend and the mechanism that corrects any drift in the in-memory budget shards.

13. Failure analysis¶

14. Consistency considerations¶

The core tension: "must never overspend" argues for a synchronous, strongly-consistent check before every ad is served. "must respond in single-digit milliseconds" argues for zero synchronous cross-service calls in the hot path. Both cannot be fully true at 500K requests/second — pick which one bends, and by how much.

The resolution used throughout this design is a conservative in-memory reservation with async true-up:

• Each budget shard holds a working balance that is pessimistic by construction — it only ever reserves budget it currently believes is available, and it writes that reservation to a local WAL before acknowledging the auction.
• The durable ledger is the eventual source of truth, updated asynchronously from the WAL and from the tracking pipeline (which confirms the reservation actually turned into a billable impression).
• Worst case is a brief, bounded overspend — not unbounded, not silent, and not permanent. It's bounded by the reconciliation interval (seconds, not hours) and by keeping each shard's authority scoped to campaigns it owns, so a single shard's drift can't compound across the whole system. This is a deliberate trade: "never overspend, ever, with zero exception" is not achievable at this latency budget without a synchronous cross-shard check that itself would blow past 10ms; "never overspend by more than a few seconds' worth of traffic, and always reconcile" is achievable and is what advertisers actually get in production ad systems.
• Contrast with the rate limiter's stance: a rate limiter can shrug off a similar-shaped overshoot forever, because the cost is "a few extra API calls." Here the same overshoot is real money, so the reconciliation loop that corrects it — not just tolerates it — is a first-class part of the design, not an afterthought.

15. Observability¶

Metrics:
  auction_decision_latency_p50/p99/p999   (SLO: p99 < 10ms)
  auction_no_fill_rate{reason}
  budget_reservation_rejects (shard says "no budget" - track separately from no eligible bidder)
  budget_shard_wal_replay_time_on_restart
  pacing_actual_vs_target_ratio{campaign_id top-K}
  tracking_pipeline_consumer_lag_seconds
  reconciliation_drift_cents{campaign_id top-K}   (in-memory remaining vs ledger truth)

Alerts:
  auction_decision_latency_p99 > 10ms
  reconciliation_drift_cents > threshold for any campaign
  tracking_pipeline_consumer_lag_seconds > 60s
  budget_shard_crash_without_clean_wal_replay
  no_fill_rate > baseline + N%  (revenue signal, not just an error signal)

Traces:
  span per auction covering eligibility filter, ranking, budget reserve — attribute campaign_count_considered

16. Cost analysis¶

Auction service fleet (stateless, in-memory cache, sized for 500K rps): ~$15,000/mo
Budget/pacing service (sharded, WAL-backed, memory-optimized instances): ~$6,000/mo
Durable ledger (Postgres cluster, billing-grade durability):            ~$3,000/mo
Tracking ingest (Kafka cluster, ~500K events/sec):                      ~$8,000/mo
Control plane + campaign config store:                                 ~$500/mo
Total:                                                                  ~$32,500/mo

Cost lever: eligibility narrowing (targeting filter before ranking) keeps the
auction's per-request candidate set at ~500 instead of 200K — this is what
makes the auction-service fleet size linear in traffic, not in campaign count.

17. Alternative architectures¶

18. Staff Engineer Extensions¶

19. Interview follow-ups¶

1. "Why can't you just add a cache in front of the Postgres budget check, like the rate limiter's Redis?" — A cache read-through still round-trips over the network; at 500K rps and a 10ms budget, even a fast Redis call (~1ms) eats a meaningful fraction of your latency, and you still need the write path to be atomic. The actual fix is eliminating the network hop from the hot path entirely — budget state has to live in the same process (or a co-located shard) as the auction, not just be cached in front of a database.
2. "How do you handle a campaign that wins an auction but the ad never actually renders (page closed, network drop)?" — This is why budget is reserved at auction time and only confirmed at the impression-tracking callback. A reservation with no matching impression event within a short window (seconds) is released back to the campaign's available budget by the reconciliation worker — otherwise budget silently leaks away on impressions that were never actually served.
3. "What's different about pacing for a campaign with a $10/day budget vs. a $1M/day budget?" — The small campaign gets vastly fewer auction opportunities, so the pacing throttle has to work at low sample counts without either starving it entirely early in the day or blowing the whole budget on the first few auctions it wins — probabilistic throttles need a floor/ceiling adjustment for low-volume campaigns, not just the same smoothed curve used for high-volume ones.
4. "How would you detect and stop click fraud before it drains a campaign's budget?" — Click events feeding the reconciliation worker should pass through fraud-scoring (velocity per IP/device, known bot signatures) before counting as billable spend; flagged clicks get excluded from the ledger write and ideally refunded if already reserved — this has to happen in the async tracking pipeline, not the synchronous auction path, since fraud scoring is too slow and too uncertain to gate a 10ms decision.

Self-Assessment¶

• [ ] I can state the three things that must all happen within single-digit milliseconds and why that's tighter than a rate limiter or recommendation system
• [ ] I can explain why the rate limiter's "approximately correct is fine" answer breaks down for budget, and what has to change instead
• [ ] I can describe pacing as a probability throttle, not a hard cutoff, with a concrete scenario showing why
• [ ] I can walk through the in-memory-reservation-with-async-true-up trade-off and state precisely what the worst case looks like
• [ ] I can explain why global budget tracking across regions is harder than ride-hailing's per-city sharding, and name at least one concrete mitigation