Design Google Ads

Four tiers: candidate selection (find eligible ads for query), auction + ranking (score and pick winners), serving (render ad + track impression), billing pipeline (click validation + charge). Budget and fraud systems run as side-car services.

The ad server is stateless and horizontally scaled. Candidate selection uses a sharded inverted index (keyword to campaign mapping) replicated across data centers. Quality scores are pre-computed and cached in a distributed KV store. Budget state is sharded by campaign ID across budget servers. Click events flow through Kafka to both real-time fraud filters (Flink) and batch billing (Spark daily).

(a) Second-price auction (Vickrey). The winner pays the second-highest bid + $0.01, not their own bid. This is truthful: the optimal strategy is to bid your true value. No incentive to game down.

-- Auction logic (simplified)
quality_score = predicted_CTR * relevance * landing_page_quality
ad_rank = bid * quality_score

-- Sort candidates by ad_rank descending
-- Winner = highest ad_rank
-- Winner pays: (second_ad_rank / winner_quality_score) + 0.01
-- This ensures winner never pays more than their bid

Quality score = predicted CTR (ML model on historical click data) x relevance (query-to-keyword semantic match) x landing page quality (load speed, mobile-friendly, content relevance). This means a $2 bid with 10x quality beats a $10 bid with 1x quality. Google's entire ad incentive structure flows from this formula.

Why quality score matters economically. Without quality score, the platform maximizes short-term revenue (highest bidder wins) but destroys long-term revenue (users stop clicking ads because they're irrelevant, CTR drops industry-wide, advertisers see lower ROI and reduce spend). Quality score aligns all three parties: users get relevant ads, advertisers get clicks from interested users, platform maximizes total click volume and thus total revenue.

-- Example: two advertisers bidding on "running shoes"
Advertiser A: bid=$5.00, pCTR=0.08, relevance=0.9, landing=0.85
  quality = 0.08 * 0.9 * 0.85 = 0.0612
  ad_rank = 5.00 * 0.0612 = 0.306

Advertiser B: bid=$2.00, pCTR=0.15, relevance=0.95, landing=0.90
  quality = 0.15 * 0.95 * 0.90 = 0.1283
  ad_rank = 2.00 * 0.1283 = 0.257

Winner: Advertiser A (rank 0.306 > 0.257)
A pays: (0.257 / 0.0612) + 0.01 = $4.21 (not their $5 bid)

(b) Real-time bidding (RTB) for display ads. For display/programmatic ads, the ad server sends bid requests to multiple demand-side platforms (DSPs) simultaneously. Each DSP has < 100 ms to evaluate the impression, check campaign targeting, and return a bid. The ad exchange runs a second-price auction across all DSP responses. This is parallelized: fan-out to 10+ DSPs, take first responses within the deadline, discard slow ones.

-- RTB timeline (100 ms budget)
T+0ms   : page-view triggers bid request
T+5ms   : ad exchange fans out to 12 DSPs in parallel
T+10-80ms: DSPs evaluate targeting, check budgets, return bids
T+85ms  : exchange collects responses (timeout at 80ms, late = no bid)
T+90ms  : second-price auction across all received bids
T+95ms  : winning creative URL returned to page
T+100ms : ad rendered in user's browser

Key engineering challenge: the fan-out must be non-blocking. Each DSP connection uses a persistent HTTP/2 stream. Slow DSPs are dropped after 80 ms — they lose the auction by default. This creates a strong incentive for DSPs to optimize latency.

Header bidding. Publishers sometimes run a client-side pre-auction (header bidding) before calling the ad exchange. Multiple demand sources bid in parallel in the browser, and the highest bid is passed to the exchange as a floor price. This gives publishers more control over yield but adds latency (50-200 ms client-side).

(c) Budget pacing. Advertiser sets $1000/day budget. Without pacing, high-traffic morning hours consume the entire budget by 10 AM — missing afternoon conversions entirely.

-- Probabilistic throttling
expected_remaining_queries = estimate_queries(now, end_of_day)
remaining_budget = daily_budget - spent_so_far
target_cpc = remaining_budget / expected_remaining_queries

-- For each auction:
participation_probability = target_cpc / actual_cpc
if random() < participation_probability:
    enter_auction()
else:
    skip()  -- save budget for later

The pacer recalculates every few minutes. If spend is ahead of schedule, participation probability drops. If behind, it rises. Goal: spend exactly $1000 by midnight, spread evenly across the day.

Budget accounting at scale. With 10M auctions/sec, you cannot check a central budget counter atomically per auction. Instead, each ad server maintains a local budget shard. Central budget service allocates "spend allowances" to each server (e.g., $10 per 5-minute window). Server spends from its local allowance without coordination. When allowance exhausted, request more from central. Slight overspend possible (~2-5%) but no distributed lock needed.

(d) Click fraud detection. ~15-20% of raw clicks are invalid: bots, click farms, competitor sabotage, accidental double-clicks. Detection pipeline:

1. Real-time filters: IP frequency cap (same IP, same ad, 10+ clicks/hour = fraud). User-agent anomalies. Click-to-conversion time < 1 second = bot.
2. Batch ML model: runs hourly on click logs. Features: click timing distribution, mouse movement patterns, geo-IP mismatch, session depth (bot clicks but never browses).
3. Conversion validation: clicks that never convert at a rate > 3 standard deviations from baseline flagged for review. Refund issued to advertiser.
4. IP frequency capping: same IP clicking the same ad more than N times per hour is capped. Clicks beyond the cap are logged but not billed. Threshold varies by vertical (e-commerce: 3/hr, B2B: 5/hr).

Fraud refund pipeline. Clicks initially billed optimistically. Batch ML runs hourly and flags invalid clicks. At end-of-day, flagged clicks are reversed from advertiser's bill. Advertiser sees "invalid click adjustment" line item in their invoice. Google reports ~10% of clicks as invalid and auto-refunded.

sequenceDiagram
    participant U as User
    participant AS as Ad Server
    participant CS as Candidate Selector
    participant AE as Auction Engine
    participant BP as Budget Pacer
    participant CT as Click Tracker
    participant B as Billing

    U->>AS: search query "cheap flights"
    AS->>CS: find eligible campaigns
    CS-->>AS: 800 candidates
    AS->>BP: filter budget-exhausted
    BP-->>AS: 600 candidates (200 paused)
    AS->>AE: run auction (600 ads)
    AE-->>AS: winner + CPC = $1.23
    AS-->>U: render ad + click URL
    U->>CT: clicks ad (302 redirect)
    CT-->>U: redirect to landing page
    CT->>B: click event (validated)
    B->>B: charge $1.23 to campaign
          

Candidate selection pipeline. The keyword index is an inverted index mapping keywords to campaign IDs. For a query "cheap flights to NYC," the system:

1. Tokenize + expand: "cheap flights to nyc" + synonyms ("affordable," "budget") + broad match ("flights nyc," "airfare new york")
2. Index lookup: union of all matching campaign IDs from the inverted index (~5000 candidates)
3. Targeting filter: remove campaigns that don't match user's geo, device, time-of-day, audience segment (~1000 remain)
4. Budget filter: remove campaigns with exhausted daily budget or paused by advertiser (~800 remain)
5. Score + rank: compute Ad Rank for remaining candidates; take top K for auction slots

This pipeline must complete in < 50 ms (leaving 50 ms for rendering). The inverted index is sharded by keyword hash and replicated across data centers for low-latency reads.

• Second-price vs first-price auction. Second-price is truthful (bid your value) but revenue may be lower per auction. First-price generates more revenue short-term but creates a bidding arms race. Google Search uses generalized second-price (GSP). Many display exchanges moved to first-price with bid shading.
• Pre-computed candidate sets vs real-time index lookup. Pre-computing "which campaigns match which keywords" is faster but stale. Real-time inverted index lookup is fresher but adds latency. Hybrid: pre-built index refreshed every few minutes; real-time filter for budget/targeting changes.
• Exact budget enforcement vs probabilistic pacing. Exact = check budget atomically per auction (expensive distributed lock). Probabilistic = slight overspend possible (up to 5%) but no locks, massively parallel. Probabilistic wins at 10M auctions/sec.
• Real-time fraud detection vs batch. Real-time catches obvious bots instantly but has limited feature access. Batch ML (hourly) catches sophisticated patterns but bills first, refunds later. Best: both layers — real-time for obvious, batch for subtle.
• Quality score freshness. Recomputing pCTR in real-time per auction is expensive. Caching quality scores with hourly refresh is practical. New ads get an exploration bonus (higher initial score) to collect click data.
• Search ads vs display ads infrastructure. Search ads: auction triggered by user query, keyword matching, text creatives. Display ads: auction triggered by page-view, audience targeting, rich media creatives, RTB with external DSPs. Same auction engine, different candidate selection and creative rendering pipelines.
• Generalized second-price (GSP) vs VCG. Google uses GSP for multiple ad slots: each position pays the bid of the advertiser one position below. VCG (Vickrey-Clarke-Groves) is theoretically optimal but computationally expensive and harder to explain to advertisers. GSP is "close enough" and much simpler.

1. Lead with the auction model. "Second-price, Ad Rank = bid x quality score." This shows you understand the economic incentive structure, not just the tech.
2. Quality score is the key insight. Without it, ads devolve into a pure spending war. Quality score aligns platform revenue with user experience — interviewers love this.
3. Budget pacing is non-obvious. Most candidates forget it. "Probabilistic throttling to spread daily budget evenly" — this is a production detail that separates senior from junior.
4. Click fraud is a billing integrity problem. Frame it as: "we cannot charge advertisers for bot clicks." Two layers: real-time filtering + batch ML + refunds.
5. Distinguish search ads from display RTB. Search = server-side auction among own campaigns. Display = fan-out to external DSPs in real-time. Same auction principles, different latency profiles.
6. Mention the data pipeline. "Clicks flow through Kafka to a Flink streaming job for real-time fraud filtering, then to a batch pipeline for billing reconciliation." This shows you think about the full lifecycle, not just the auction.
7. Know the numbers. Google processes ~8.5 billion searches/day, each triggering an auction. Average CPC across all verticals is ~$1-2. Legal keywords ("lawyer," "insurance") can exceed $50/click. These numbers ground your design in reality.