Real-Time Bidding Platform

Ad exchange on OpenRTB

Design an ad exchange that auctions each ad slot to many outside bidders while the page loads: send bid requests, collect answers before a hard deadline, pick a winner, and bill each shown ad exactly once.

Overview

When a page or app has room for an ad, it can sell that slot in an auction that runs while the page loads. The exchange receives the ad request, sends a bid request describing the slot, the page and the device to many bidders (the buyers' systems), waits a fixed time for their bids, picks a winner, and returns the winning ad. The whole thing has to fit in a small fraction of a second, because the page is waiting.

The messages follow OpenRTB, the IAB Tech Lab's open standard. A bid request carries tmax, the time in milliseconds the exchange allows for a bid to arrive, network included. A bidder that does not want the slot answers HTTP 204 No Content. A winning bid carries URLs the exchange calls later: a win notice, a billing notice when the ad becomes billable, and a loss notice for losers.

This problem is mostly about time and money. Time: every step is on a deadline, and the design is judged by what it does when something is slow. Money: the price rule decides who pays what, and a billable impression must be counted once, never zero times and never twice.

Questions to ask first

Are we the exchange or a bidder? — The exchange; the bidder's pacing and frequency caps are covered as a follow-up
How many auctions? — 500,000 a second at peak, 200,000 on average
How many bidders per auction? — About 20, chosen from a few hundred connected bidders
How long does the publisher wait? — 120 ms from request to answer at the exchange
Which auction type? — First price by default; second price plus supported per request
When is an impression billable? — When the ad is shown, signaled by the billing notice

What you will be able to do

Lay out a time budget for one auction and defend each number.
Fan out to many bidders in parallel and cut off late answers.
Explain first-price and second-price-plus auctions, floors and clearing prices.
Count billable impressions exactly once from notices that may repeat.
Explain how a bidder paces a daily budget and enforces frequency caps under a deadline.

Key concepts

OpenRTB bid request
tmax deadline
Parallel fan-out
No-bid (204)
First price vs second price
Bid floor
Win, billing and loss notices
Budget pacing
Frequency cap
Invalid traffic filter

Functional requirements

Accept an ad request from a publisher and answer with a winning ad or no ad
Send an OpenRTB bid request to each eligible bidder in parallel, with tmax set
Accept bids that arrive before the cutoff; treat 204 and late answers as no bid
Drop bids below the floor; run a first-price or second-price-plus auction
Fill the clearing price into the win and billing notice URLs
Record every auction and every billable impression for billing and reporting
Let bidders register an endpoint, a request rate limit and filters

Non-functional requirements

Answer the publisher within 120 ms at p99 (a budget we chose), whatever the bidders do
Never bill an impression twice, even when a billing notice is fired twice
Keep auction servers stateless so any server can take any request
Stay up 99.99% of the time: an outage loses the publisher's revenue at once
Never send a bidder more requests a second than it asked for

Interview questions

Why is the deadline a hard cutoff and not a wait for all bidders?
Walk me through one auction from the ad request to the billing notice.
First price or second price: which would you build, and why?
How do you make sure an advertiser is billed exactly once?
How does a bidder pace a daily budget without a shared counter on every bid?
How do you enforce a frequency cap inside the deadline?
How does the system scale to millions of bid requests a second?