Building a Real-Time Ad Bidder in Rust — Part 1: Designing the 50ms Hot Path

A real-time bidder has one non-negotiable property: it answers inside the exchange’s timeout, every time, or its bids stop counting. (The opening post covers the ecosystem and the architecture at a high level — this part goes deep on the request path itself.) Everything here follows from taking that constraint seriously at design time rather than discovering it in production. The theme: the hot path is designed, not optimized. The data structures, the contracts between components, and the failure behavior were all decided before the first benchmark ran, because no amount of after-the-fact tuning rescues the wrong architecture.

A latency budget is a contract, not a comment#

Why the 99th percentile, not the average#

Exchanges attach a timeout to every bid request — OpenRTB carries it in tmax. A bidder whose average latency is 10ms but whose 99th percentile is 200ms is not “mostly fine”: at tens of thousands of requests per second, 1% is hundreds of missed auctions per second, and it’s usually the valuable requests that are slow (more candidates, more data, more work). Worse, an exchange watching your timeout rate throttles the traffic it sends you. Tail latency is the metric; averages are noise. The design target for the whole system is p99 ≤ 50ms, leaving headroom under a 100ms tmax for network transit and the exchange’s own processing.

Decomposing the SLA#

Fifty milliseconds is a budget, and budgets get spent by line item. Each stage of the request path gets an explicit budget, written in configuration where it can be seen, reviewed, and alerted on:

Two things to notice. First, the arithmetic is deliberately loose: a budget that sums exactly to the SLA is a budget that’s already blown — the slack absorbs queueing delay, scheduler jitter, and the unknown-unknowns that appear under load. Second, the largest allocations go to the stages that touch the network, because in this workload network round-trips to the data tier cost more than all the compute combined. This isn’t idiosyncratic: Aerospike’s published RTB lifecycle budget allocates 5–15ms to profile lookup and 10–25ms to bid evaluation — the same shape, drawn by people who run this in production.

These per-stage budgets are advisory: exceeding one doesn’t kill the request, it increments a per-stage Prometheus counter. That turns latency drift into something a dashboard shows you before it becomes an incident — when a code change makes scoring 3x slower, the guilty stage is named in monitoring on day one, not discovered in a profiler after a bad week.

Above the advisory budgets sit two hard limits, layered:

1. The pipeline deadline (40ms), checked before each stage starts. Crossed it? The request immediately returns “no bid” rather than starting a stage it can’t afford. Checking before the stage means no stage partially executes on a doomed request — and a fast, honest no-bid is strictly better than a late bid, which the exchange discards anyway while it occupies a concurrency slot a viable request needed.
2. The HTTP timeout (50ms) — the transport-layer backstop, enforced by middleware.

The gap between 40 and 50 is deliberate: room for response encoding and the socket write, so the application deadline fires before the transport one under normal degradation.

The failure philosophy#

The budget system implies a philosophy worth stating explicitly: never miss the SLA silently — drop, degrade, or shed, but always fast and always observably. Every overload condition has a predetermined action and a named metric:

Note the third row: if the counter store can’t answer in time, the bidder bids without the frequency check rather than blocking. Bid quality may dip during degradation; the SLA never does. That ordering — deadline above feature completeness — is the single most load-bearing decision in the design. Part 4 covers the machinery that enforces it under real failure.

The pipeline: nine stages over one context#

The request path is an ordered list of stages, each implementing a small trait, each reading and mutating a shared per-request context:

trait Stage {
    fn name(&self) -> &'static str;
    fn execute<'a>(&'a self, ctx: &'a mut BidContext)
        -> impl Future<Output = Result<()>> + Send + 'a;
}

The context accumulates state as the request flows: the decoded request, then the user’s segments, then candidates, scores, winners, and finally the response. A stage that determines the request can’t produce a bid sets a “no bid” outcome with a reason code, and the runner short-circuits the rest. The runner itself (bidder-core/src/pipeline/) is barely fifty lines: loop over stages, check the deadline, time the stage, compare against its budget, stop early on a no-bid.

Why a linear pipeline rather than a DAG, parallel stages, or an actor per stage? Because the stages are genuinely sequential (you can’t retrieve candidates before you know the segments; you can’t rank before you score), and a linear structure makes the two things that matter trivial: per-stage attribution of latency, and a single comprehensible place where deadline enforcement happens. Boring structure, observable behavior. The concurrency lives across requests — thousands in flight on the async runtime — not within one.

The cost model that predicts your bottleneck#

Before writing any stage, it pays to classify it by what its cost scales with:

• Per-request I/O — O(1) per request. User enrichment does one Redis read per request, whatever else happens.
• Per-candidate I/O — O(candidates) per request. Frequency capping reads one counter per surviving candidate — ~20 of them. At 50K requests/second that’s up to a million reads per second from one stage.
• Pure compute — effectively free here. Ranking, validation, response build; microseconds against a network hop’s hundreds.

That classification told us where the budget’s big allocations belonged before any measurement existed — and it flags per-candidate I/O stages as the ones that will dominate the moment anything goes wrong with their caching. Hold that thought for Part 4.

A Rust note for readers building their own: making the Stage trait object-safe (so stages live in a Vec<Box<dyn Stage>>) and non-allocating per call takes care — async trait methods desugar into returned futures, and naive approaches either don’t compile or box a future on every stage of every request. The pattern here returns impl Future + Send + 'a and pays one boxing at pipeline construction, not per call. But measure before copying: the I/O each stage does dwarfs a heap allocation.

One structural rule applied everywhere: every internal queue is bounded, and every bound has a documented overflow policy. The impression-counter write queue holds 65,536 entries and drops with a counter on overflow; the event queue to Kafka holds 100,000 and drops by policy; the HTTP layer caps in-flight requests and sheds beyond that. Unbounded queues don’t make overload go away — they convert it into memory growth and latency, the two failure modes hardest to diagnose. Bounding forces “what happens when this is full?” to be a whiteboard question instead of an incident question.

Candidate retrieval: surviving 100,000 campaigns#

The arithmetic that kills the naive design#

The retrieval stage answers: of all active campaigns, which are eligible for this request? The naive implementation iterates campaigns and evaluates each one’s targeting rules. At small scale it works, which is exactly what makes it a trap. Checking one campaign costs on the order of 10µs; at 1,000 campaigns that’s 10ms — painful but survivable, and many prototypes stop there. At 100,000 campaigns it’s $100{,}000 \times 10\,\mu\text{s} = 1\,\text{s}$ per request, against a 1ms stage budget. A thousand times over. No compiler and no faster language closes a 1000x gap. Only a different data structure does.

Inverted indices: the search-engine idea, applied to campaigns#

The structure that closes it is the one behind every search engine: the inverted index. Instead of asking “for each campaign, does it match this request?”, precompute the reverse — “for each targeting value, which campaigns want it?” Eligibility then becomes set algebra: union the campaign sets for the user’s segments, then intersect with geo, device, and format. Try it:

A request with 5 segments touching ~500 campaigns each does a few thousand set operations — a few hundred microseconds, comfortably inside budget. The per-request cost now scales with the size of the matching sets, not the size of the catalog. If you build a bidder, this is the load-bearing data structure.

The sets themselves are Roaring Bitmaps — the standard compressed-bitmap format (used inside Lucene, Spark, and ClickHouse) that stores dense integer ranges as bitmaps and sparse ones as arrays. Campaign IDs are small dense integers, Roaring’s happy case: intersections run at memory bandwidth over compressed data. One seeding lesson learned on the way: uniformly random test data makes every bitmap medium-density and your benchmarks lie. Real targeting data is heavily skewed — a few huge segments, a long tail of tiny ones — and Roaring’s performance profile depends on that shape. Synthetic data must be Zipf-distributed to be honest.

Refreshing the catalog without stopping the world#

The catalog lives in Postgres, but Postgres is never queried during a request. A background task rebuilds the entire in-memory catalog — campaigns, creatives, all the inverted indices — every 60 seconds, then swaps it in atomically (bidder-core/src/catalog/).

The swap mechanism matters. A read-write lock has three problems at this request rate: the writer blocks every reader while swapping, the read lock becomes cross-core contention, and there’s no snapshot isolation — a request could observe half-updated state. The structure used instead is an atomic pointer swap (the arc-swap crate): readers load the current pointer in a few nanoseconds, wait-free, and hold a reference-counted snapshot for the whole request; the refresher builds the complete new catalog off to the side and publishes it with one atomic store. In-flight requests finish on the old snapshot; new requests see the new one; nobody waits. If a rebuild fails — Postgres down, bad data — the old catalog stays live and a counter fires: stale-but-serving beats fresh-but-down.

The trade, stated honestly: up to 60 seconds of staleness on campaign changes. Campaign edits are human-timescale, so that’s fine here — but know what staleness your domain tolerates and spend it deliberately.

The cache in front of the user lookup#

The other hot-path data dependency is the user’s segment list, from Redis. In front of it sits an in-process cache (the moka crate — Rust’s sibling of Java’s Caffeine, using the TinyLFU admission policy, which resists the classic LRU failure of one-time visitors evicting your regulars). Two details worth copying:

• The cached value is the decoded segment list — parse cost paid once per user per TTL, not per request.
• Lookups use a coalescing get-or-load (try_get_with): when a popular user goes cold, a hundred concurrent requests produce one Redis fetch, not a hundred. Cache stampedes are a self-inflicted thundering herd; most cache libraries prevent them, but only if you call the right entry point.

Redis key design is a performance lever, not a naming convention#

This section is the least glamorous and, per unit of effort, was the most valuable. When the bottleneck hierarchy starts with “network round-trips to the data tier”, the shape of keys and values determines how many round-trips you make and how many bytes each carries — before any client library or server tuning enters the picture.

The keyspace is a handful of versioned families:

v1:seg:{u:12345}            user → packed segment IDs
v1:fc:{u:12345}:c:204:d     frequency counter, user 12345 × campaign 204, daily
v1:fc:{u:12345}:c:204:h     same, hourly
v1:winx:<request>:<imp>     win-notice dedup marker

Four decisions in that tiny listing, each with a reason.

The braces are Redis Cluster routing, and they’re load-bearing. Cluster shards keys by hashing them into slots — but hash the whole key and a user’s segment key plus their fifty frequency-cap keys scatter across fifty shards, turning the cap stage’s single batched MGET into fifty network operations. A hash tag — the substring in braces — routes on that substring only, so everything for user 12345 co-locates on one shard and the batched read stays one round-trip:

Designed in from day one, this makes the eventual migration from one Redis to a cluster a pure topology change with zero key-schema work. Retrofitted later, it’s a full dual-write data migration. This is the highest-leverage five minutes of design in the whole data layer.

Values are raw binary, not JSON. A segment list is packed little-endian 32-bit integers: 120 segments = 480 bytes, versus ~1.2KB as a JSON array — and it decodes in a single pass of chunks_exact(4) at effectively memcpy speed, no parser (bidder-server/src/segment_repo.rs). At 100 million users, encoding choice is a multi-gigabyte, multi-millisecond-tail decision.

But identifiers stay human-readable. Binary-packing the IDs in key names would save another ~30% — and was deliberately rejected, because nobody can redis-cli GET a key they can’t type during an incident. Optimizations that tax debuggability need to clear a much higher bar. This one didn’t.

Every family has an explicit TTL and lifecycle. Segments expire after 14 days (the behavioral pipeline refreshes them); counters expire just past their window, set atomically with the first increment via a four-line Lua script so a counter and its expiry can’t get separated; dedup markers live one hour. The v1: prefix is the schema-versioning escape hatch: an incompatible encoding change becomes v2: with a dual-write window, never an in-place rewrite racing a rolling deploy.

And the arithmetic nobody enjoys but everybody needs: at target scale this keyspace does not fit one Redis instance. Segments for 100M users at ~480 bytes is roughly 48GB before overhead; counters for the active fraction add tens more, with realistic totals well past 100GB. Doing that arithmetic in a design doc — key count × (key bytes + value bytes + per-entry overhead) — is an hour of work that tells you your clustering story before your OOM does.

What to take away#

If you’re building your own bidder — or any service with a hard tail-latency SLA and a large working set:

1. Budget the SLA per stage, in config, with metrics on violation. Advisory budgets catch drift in dashboards; one hard deadline, checked between stages, protects the contract.
2. Classify stages by what their cost scales with. Per-request I/O, per-candidate I/O, pure compute — the per-candidate class is where your bottleneck will live.
3. When per-request cost scales with catalog size, invert the index. Precompute value→candidates bitmaps and do set algebra per request. The difference between 1 second and 500 microseconds is a gap no language choice closes.
4. Refresh shared state by atomic snapshot swap, never in place. Readers get consistency and wait-freedom; failed refreshes degrade to staleness instead of downtime.
5. Design your keys before your code. Co-location, value encoding, TTL lifecycle, a version prefix — plus the memory arithmetic — determine your round-trip count and clustering story more than any client-side tuning will.

The budgets in this part say what each stage was supposed to cost. Part 2 follows the money — pacing, caps, auction pricing, and the signed win notice. Part 4 shows what the stages actually cost under load, including the one that quietly ate three-quarters of the pipeline.

References & further reading#

• OpenRTB specification — IAB Tech Lab
• Callout quota system — Google Authorized Buyers
• Programmatic advertising data flow — the RTB lifecycle with per-stage latency budgets
• Roaring Bitmaps — the compressed bitmap format behind the indices
• TinyLFU: A Highly Efficient Cache Admission Policy — the policy behind the segment cache

Disclaimer: I don’t work in ad tech. This series documents a personal project built to learn high-performance systems engineering, using real-time bidding as the problem domain because its constraints (hard latency SLAs, large working sets, high request rates) are unusually honest teachers. Industry references are from public engineering material; my own numbers come from synthetic workloads on developer hardware and are reported with their caveats. Corrections from people who build these systems for a living are very welcome.