Section 8: Fifty Million Down to Ten Thousand - Deep Dive: Retrieval & the Serving Index
Executive Summary: Retrieval gets 15 ms of the 80 ms budget, and it decides which ads are even possible for this request. The index (200 GB) is split by hash(ad_id) into 16 shards of ~12.5 GB, each held in RAM, and every request queries all 16. On each shard, a conjunction index matches Maya's attributes against every ad set's targeting expression (25K hits), cheap filters drop ineligible ads, and an exact int8 dot product keeps the top 625. Freshness comes from three layers: an immutable snapshot, a delta layer for edits (≤ 60 s), and a kill list for takedowns (≤ 10 s).
The interviewer taps the retrieval box from Section 6. "Fifty million ads, fifteen milliseconds. Walk me through one leaf."
You: "How the index is cut up first, since that decides what one leaf can do alone. Then the query loop, then freshness."
Cutting the Index: By Document, Not by Term
A full index copy is 200 GB: 50M ads × ~2 KB, doubled by posting lists. We hash ad_id into 16 shards of ~12.5 GB, small enough for one leaf server's RAM, and send every request to all 16. At 1.2M QPS that is 19.2M shard-queries/s. At ~4,000 per leaf, that needs 4,800 leaf servers at peak, **5,800** with N+1.
| Option | What it costs | Verdict |
|---|---|---|
| Document-partitioned, 16 in-RAM shards | Every request fans out to all 16; Section 7's hedging and partial results absorb stragglers | Chosen |
| Term-partitioned by targeting attribute | A conjunction's terms live on different shards, so posting lists cross the network to be intersected; terms like geo=US become hot shards |
Rejected |
| General search engine (Elasticsearch-style) | GC pauses and general-purpose overhead; p99 too slow at 19.2M shard-queries/s | Rejected |
Interviewer: "Sixteen calls per request feels wasteful."
You: "Each call is small and returns 625 tiny rows, and each shard answers on its own with no cross-shard joins. The flip trigger is geography: if most ads become geo-local, I'd partition by region so a Texas request skips shards full of Japanese bakeries."
Quick check before moving on:
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson