Designing a search engine

The search and analytics article explained what an inverted index is and how BM25 ranks documents. This one builds the engine around them: a crawler that must not melt the web, an index of fifty trillion postings that has to be rebuilt continuously, a query that fans out to a thousand machines and comes back in under two hundred milliseconds, and a ranking stack in which the text match is only the first of a hundred signals.

The map

Read this first when short on time. Every branch is a section below.

What it must do, and at what size

It must discover documents on the open web, keep a current copy of what they say, and answer an arbitrary query with ten good results fast enough that the page feels instant. It must not, in this design, personalize deeply per user, answer questions directly rather than linking, or index anything behind authentication.

Corpus     ~100 billion documents indexed, many more discovered and rejected
Postings   ~500 useful terms per document -> ~50 trillion postings
           compressed to ~1-2 bytes each -> 50-100 TB of index

Queries    ~100,000/s at peak
Latency    ~200 ms end to end, of which ~100 ms is retrieval and ranking
Repeats    30-50% of queries have been seen recently -> result caching matters

Fan-out    index sharded across ~1,000 leaves -> every query touches all of them
           if one leaf's p99 is 100 ms, a 1,000-way fan-out hits it
           on essentially every query

That last block is the single most important consequence of the whole architecture and worth stating plainly. When a query must consult a thousand machines and wait for all of them, the slowest one determines the response time. A per-machine 99th percentile that sounds excellent becomes the common case at the query level, because with a thousand independent draws you almost always hit at least one. Tail latency stops being a statistical curiosity and becomes the dominant design constraint.

flowchart TD
  W["the web"] --> CR["crawler and frontier"]
  CR --> PR["parse, canonicalise, dedupe"]
  PR --> IDX["index build, batch"]
  PR --> GR[["link graph"]]
  IDX --> SEG[["index segments, sharded by document"]]
  Q["query"] --> RT["root"]
  RT --> SEG
  SEG --> RT
  RT --> RK["rerank with the full model"]
  RK --> RES["ten results"]

Crawling

A crawler is a distributed breadth-first traversal of a graph that is hostile, infinite and owned by other people. Almost every rule in it is about not being a nuisance.

The frontier is a priority queue of URLs to fetch, fed by links found in crawled pages and by sitemaps. It is never plain breadth-first: a page's priority comes from its estimated importance, how long since it was last fetched, and how often it changes. The web is effectively infinite, so the frontier's job is to spend a finite budget on the pages that matter.

Politeness is the hard constraint. Requests are queued per host, not globally, with a small number of concurrent connections and a delay between them, because a crawler that hits one site with a thousand parallel requests is indistinguishable from an attack. The robots file is fetched, cached and obeyed, and a site that asks for a slower rate gets it. This is why the architecture is a queue per host rather than one global work queue — the unit of scheduling is the host, not the URL.

flowchart TD
  S["seed URLs and sitemaps"] --> F[["frontier, prioritised"]]
  F --> HQ["one queue per host, limited concurrency"]
  HQ --> FE["fetch, respecting robots and delay"]
  FE --> PA["parse, canonicalise, dedupe"]
  PA --> L["new links discovered"]
  L --> F
  PA --> RS["recrawl scheduled from the change rate"]
  RS --> F

Recrawl scheduling is a prediction problem: a news front page changes every few minutes and an archived document never changes again. Fetching both daily is simultaneously too slow and a waste, so the crawler estimates each page's change rate from its own history and schedules accordingly.

Parsing, canonicalisation and duplicates

A fetched page becomes a document through several steps, and the interesting ones are about identity rather than content.

Extraction separates the main content from navigation, footers and advertisements, because indexing boilerplate makes every page on a site look similar. Pages that build their content with scripts have to be rendered rather than merely parsed, which costs orders of magnitude more, so rendering is a decision made per page rather than universally.

Canonicalisation answers "is this the same document?". The same content is reachable at many addresses — with and without a trailing slash, with tracking parameters, on both protocols, on several hostnames — and indexing them separately splits the ranking signals across duplicates and wastes the crawl budget. URLs are normalised, redirects followed, and the page's own canonical declaration respected.

Near-duplicate detection handles the harder case: syndicated articles, product pages that differ in one field, sites that copy others wholesale. The standard technique reduces each document to a compact fingerprint built from overlapping word sequences, chosen so that similar documents produce similar fingerprints and near-duplicates can be found by looking for fingerprints within a small distance. Clusters are collapsed to a single representative — the original where it can be identified, the most authoritative otherwise.

Building the index

Index construction is a sort. Documents produce postings — one per term occurrence — and the pipeline groups them by term, orders each group by document, compresses it and writes immutable segments.

Compression is not an optimisation here, it is what makes the index possible. Fifty trillion postings stored naively would be hundreds of terabytes of document ids alone; stored as deltas between consecutive ids and packed into the minimum number of bits, the same data is a fraction of that. Because postings are read sequentially during query evaluation, decompression is cheap and the smaller index means more of it fits in memory — which is where the real speed comes from.

Tiering is the structural idea that makes serving affordable. The index is split into a small tier holding the highest-quality documents and much larger tiers holding the rest. Most queries are answered entirely from the first tier, and only queries that fail to find enough good results there descend. That turns "search a hundred billion documents" into "search a few hundred million, usually".

Freshness needs a second mechanism, because a batch build takes hours and news does not wait. A small live index holds very recent documents, is updated continuously, and is merged with the main index at query time. It is the same pattern as an LSM-tree's memtable, and it exists for the same reason: batch efficiency for the bulk, a small mutable layer for the recent.

Sharding: by document or by term

The index is far too large for one machine, and there are exactly two ways to divide it. This choice determines the shape of query serving completely.

Document partitioning gives each shard a slice of the corpus and the complete index for those documents. Every query goes to every shard, each returns its own best candidates, and a root merges them. Load is even, updates are local — a new document affects one shard — and adding capacity is adding shards.

Term partitioning gives each shard the complete posting list for a subset of terms. A two-word query touches two shards instead of a thousand, which sounds far better until the details bite: posting lists for common terms are enormous and must be shipped across the network to be intersected, the shard holding the popular terms is permanently hot, and adding a document touches every shard that holds one of its terms.

Document partitioning wins in practice, and the price it pays is the fan-out and its tail — which the next section is entirely about.

Serving a query

A query enters a root, fans out to every leaf, and comes back merged. The structure is simple; making it fast at a thousand-way fan-out is not.

sequenceDiagram
  autonumber
  participant C as Client
  participant R as Root
  participant L as Leaves
  participant M as Reranker
  C->>R: query
  R->>R: result cache hit? if so, return
  R->>L: fan out to about 1,000 shards
  L-->>R: each returns its top few, scored cheaply
  Note over R,L: hedge to a replica for leaves that are slow
  R->>M: merged candidates, a few hundred
  M-->>R: reranked with the expensive model
  R-->>C: ten results

Tail latency is the defining problem. With a thousand leaves, the probability that at least one is slow is essentially one, so the query's latency is governed by the worst machine rather than the typical one. Three mechanisms fight it. Hedged requests: after waiting a short time, send the same request to a replica and take whichever answers first — this costs a few percent of extra work and removes most of the tail. Answer with what arrived: if a handful of leaves have not responded by the deadline, return results from the rest, since missing a fraction of the corpus changes the top ten far less often than being a second late hurts. And keep leaves uniform, because a single overloaded or degraded machine damages every query rather than a thousandth of them.

Caching does the rest of the work. A large share of queries are repeats, so a result cache at the root answers them without touching the index at all, and posting lists for common terms stay in memory at the leaves. The cache is invalidated when a new index version is published — which is another reason index builds are published as discrete, versioned events rather than trickling in.

Ranking

Retrieval finds documents containing the words. Ranking decides which ten are worth showing, and it is where nearly all of the quality lives.

The structure is the funnel seen throughout this series, sized by cost. Each leaf retrieves thousands of matching documents and scores them with something cheap — a text-match score plus a precomputed quality signal — keeping only its best few. The root merges those into a few hundred candidates and reranks them with a model that can afford to be expensive because it runs once per query on a small set.

flowchart TD
  A["each leaf retrieves thousands of matches"] --> B["cheap score: text match plus a quality signal"]
  B --> C["each leaf keeps its best few"]
  C --> D["root merges a few hundred candidates"]
  D --> E["expensive model reranks them"]
  E --> F["ten results"]

The signals that model uses fall into four groups. Text match, with BM25 as the baseline and proximity, field weighting and synonym handling on top. Authority, from the link graph: a link is a citation, links from well-cited pages count for more, and the anchor text describes the target in other people's words — which is often better than the page's description of itself. Context: freshness for queries that want it, language, location. And behaviour: aggregated interaction with results for similar past queries, which is the most powerful signal available and the most easily gamed.

Combining these is a learning to rank problem — a model trained on human relevance judgements and behavioural data, evaluated with a graded metric rather than accuracy, since the order of the top few matters far more than anything below.

Vector retrieval at a billion documents

Keyword retrieval cannot match "why is my laptop hot" to a page titled "thermal throttling in notebooks". Embeddings solve that, and the engineering question is how to search a billion of them inside the same latency budget.

Exact nearest-neighbour search is out immediately: comparing a query vector against a billion stored vectors is hundreds of billions of multiplications. So vector retrieval follows the same shape as the inverted index — shard the vectors across machines, run an approximate search within each shard, and merge — which means it fits the existing fan-out tree rather than needing a separate architecture.

Inside a shard the trade is memory against recall. A graph index gives excellent recall and speed but keeps the full vectors plus the graph in memory, which at a billion vectors of several hundred dimensions is prohibitive. Quantisation compresses each vector into a short code, cutting memory by an order of magnitude at some loss of precision, and is usually combined with a clustering index so only a few clusters are searched. The common production shape is quantised candidates followed by exact rescoring of the top few hundred against full vectors fetched from disk.

Hybrid retrieval is not optional. Vectors are weak exactly where keywords are strong — product codes, error strings, rare names, quoted phrases — so both retrievers run and their ranked lists are fused, commonly by a rank-based method that needs no score calibration between two systems that score on different scales.

Spam and adversaries

Ranking position converts directly into money, so every signal in the previous section is under continuous attack. This is not a subsystem bolted on afterwards; it shapes which signals are usable at all.

The guiding principle is to prefer signals that are expensive to fake. Keyword density on a page is free to manipulate, which is why it stopped being useful decades ago. Links from established, well-cited sites are expensive to obtain, which is why link-based authority survived — until link-selling made it worth attacking too, at which point graph analysis to detect unnatural linking patterns became necessary.

The defences form layers: content classifiers that detect low-quality or machine-generated text, graph analysis that finds link schemes by their structure, behavioural checks that notice results nobody engages with, and manual action as a backstop for cases the automation cannot reach. And because it is adversarial, the details of the signals cannot be published — a constraint that makes this the one part of the system that is deliberately not documented.

What breaks first

1. Fan-out tail latency. The structural problem: a thousand-way fan-out makes every machine's tail the query's typical case. Hedging, deadlines with partial results and uniform leaves are the tools, and adding shards makes it worse rather than better.
2. Index build time. A full rebuild is hours of batch work, which bounds how quickly a ranking or schema change can reach production, and makes the live tier essential rather than a nicety.
3. Crawl capacity against freshness. Politeness limits how fast the web can be recrawled, so freshness is allocated rather than achieved — spend it on pages that change and matter.
4. Ranking model cost. The reranker runs on every query, so its size is bounded by the latency budget and by hardware cost, which is the constraint that pushes work into cheaper earlier stages.

Recap