Design Search Engine

We are not building Google. Assume a serious challenger: 20 billion pages in the serving index, 3 billion queries a day, and a crawler that refetches the average page every three weeks. Every row below follows from those choices.

Notice the internal call carries a deadline, not just a timeout. The leaf uses it to cut scoring short and return a partial top-k, which the aggregator can still use. A timeout would throw that work away.

Draw two planes and keep them apart. The build plane on the left runs continuously but is allowed to be slow: fetchers pull pages from a prioritised frontier, the parser strips markup, collapses near-duplicates and records every outgoing link, and the index builder turns batches of documents into sorted, compressed index segments. The query plane on the right only reads those segments, and it must answer in a few hundred milliseconds no matter what the build plane is doing.

A query lands on the front end, which normalises it and checks the result cache. On a miss, query understanding rewrites it: spelling fixes, synonym expansion, language detection and a guess at intent, such as "this looks like a navigational query for one site". The rewritten query goes to a root aggregator, which sends it to a set of mid-level aggregators, each of which owns a rack of leaf shards. Leaves score their documents and send back a few hundred candidates. Aggregators merge upwards, the re-ranker reorders the best few hundred with heavier models, and snippet servers fetch the text around each match from the document store.

Freshness comes from a second, much smaller index. The real-time indexer takes pages fetched in the last few hours and keeps them in a memory segment that leaves search alongside the big batch segment. When the next full build ships, those documents fold into it and the real-time segment is trimmed.

For every term, a leaf stores the IDs of documents containing it, sorted ascending. Sorting matters twice. It lets you store gaps between IDs instead of the IDs themselves, and gaps for common terms are tiny numbers that compress to a byte or less with schemes like PForDelta or Elias-Fano. It also lets you intersect two lists by walking them together, skipping ahead with a small skip index every 128 entries.

Next to each doc ID you keep the term frequency, and in a separate stream the positions, which are read only for phrase queries and for proximity scoring. Splitting the streams means a simple keyword query never pays to decompress positions it will not use.

Document IDs are assigned so that better documents get smaller IDs. A leaf walking a list in order therefore meets strong candidates first, which makes early termination far more effective.

A two-word query over common terms can match tens of millions of documents in one shard. Scoring all of them would take seconds. Leaves use Block-Max WAND: every block of a posting list stores the highest score any document in it could reach. The leaf keeps a heap of its current top 200 and a threshold equal to the 200th score. If the upper bounds for a block of documents cannot beat the threshold, the whole block is skipped without being decoded. On real query logs this skips well over 90% of postings with exactly the same top-k as a full scan.

The first-pass score is cheap on purpose: BM25 over title, body and anchor text, plus a static quality score per document that combines link authority, spam likelihood and page speed. Static scores are computed offline in the build plane, once per index build.

If each leaf has a 1% chance of a slow response, a query that waits on 150 leaves is slow more than three quarters of the time. Three things fix this. First, a tree: the root talks to about 12 mid aggregators, each of which talks to 12 or 13 leaves in its own rack, so merges happen close to the data. Second, hedged requests: a mid aggregator that has not heard from a leaf by that leaf's p95 latency sends the same request to another replica and takes whichever answers first. That costs a few percent of extra load and removes most of the tail. Third, deadlines: when the budget runs out, the aggregator returns with what it has and marks the response as partial. Missing one shard out of 150 drops less than 1% of candidates, and users cannot tell.

Each stage is roughly ten times more expensive per document than the one before it, and sees roughly ten times fewer documents. That is the whole trick. The cross-encoder reads the query and each candidate together, which is the most accurate signal we have, but at 300 documents per query and 52,000 queries per second that is still about 15 million inferences a second, so it runs on a dedicated GPU pool with request batching.

The batch build runs as a large MapReduce-style job: mappers emit (term, doc_id, tf, positions), the shuffle groups by shard and term, and reducers write immutable segments. A build is pushed to one replica set at a time, checked against a fixed set of probe queries whose results must stay within tolerance, and only then promoted. Every leaf can hold two versions, so rolling back is a pointer swap, not a reload.