The big idea

What is a search engine?

Type a few words and get the ten best pages from billions, ranked by relevance, in a few hundred milliseconds. Two hard problems hide inside: finding the matching documents fast, and ordering them so the most useful is first.

Flip the data around with an inverted index (term → documents) so matching is a list lookup, not a scan. Then rank the matches by relevance and authority, shard the index for scale, and cache the popular queries.

How to read this: We add one piece at a time, problem then fix, and the diagram grows. (Getting the documents is the web-crawler design — here we make them searchable.) Hit Begin.

Step 1 · The skeleton

Query in, matches out

Given a query, you must return documents containing those words. Scanning every page for every query is hopeless at web scale — you’d need to read the entire internet on each search.

Design decision: Return docs containing the query words, from billions of pages, in ~100ms. How do you store the data?

The call: An inverted index: for each term, the list of docs. — Term → docs turns a query into looking up each word’s postings list and intersecting them — a handful of list ops instead of scanning the web. The single most important idea here.

Stand up a Query Service backed by an Inverted Index: instead of “which words are in this doc?”, store “which docs contain this word?”. A query becomes looking up each term’s document list and intersecting them.

Invert the data: A forward index (doc → words) answers the wrong question. Inverting it (word → docs) turns search from a full scan into a handful of precomputed list lookups — the single most important idea here.

Step 2 · Match the right forms

Parse the query

A user types “Running Shoes” but the index stored “run” and “shoe”. Case, punctuation, stop words and word forms all cause misses unless the query is processed the same way the documents were.

Design decision: A user types "Running Shoes" but the index stored "run" and "shoe". How do you make them match?

The call: Run the query through the same analysis used at index time. — Tokenize, lowercase, strip stop words and stem the query exactly as the documents were, so "Running" and "run" resolve to the same postings list. Symmetry of analysis is the fix.

A Query Parser tokenizes, lowercases, strips stop words and stems terms — applying the exact pipeline used at index time. Now “Running” and “run” resolve to the same postings list, so matching actually works.

Symmetry of analysis: Whatever transformation you apply to documents when indexing, you must apply identically to queries. Mismatched analysis is the most common cause of “why didn’t this match?”.

Step 3 · Build the index

From pages to postings

The inverted index doesn’t appear by magic — it has to be built from the crawler’s billions of pages, and rebuilt as new pages arrive. Doing that inline with queries would be impossible.

Design decision: The inverted index must be built from billions of crawled pages and kept current. Where does that happen?

The call: An offline Indexer pipeline builds postings continuously, apart from serving. — The indexer reads crawled docs, runs the same analysis, and writes postings in the background. Separating write-heavy indexing from read-heavy querying lets each scale independently.

An offline Indexer pipeline reads crawled documents, runs the same analysis, and writes each term’s postings (doc ids, positions, frequencies) into the index. It runs continuously in the background, separate from serving queries.

Build offline, serve online: Separating the write-heavy indexing from the read-heavy querying lets each scale independently — the same build-then-serve split behind typeahead and feeds.

Step 4 · Which ten first?

Ranking

A common query matches millions of documents. Returning them in index order is useless — the user only looks at the first few, so the order is the entire value of the product.

Design decision: A common query matches millions of docs. Returning them in index order is useless. How do you order them?

The call: Combine text relevance (BM25) with authority (PageRank) + signals. — BM25 asks "does this match the words well?", PageRank asks "is this page trustworthy?". Combining them (plus freshness, quality) is why search beats a keyword grep. The Doc Store then supplies titles/snippets for the winners.

A Ranker scores candidates by textual relevance (TF-IDF/BM25 — how well the terms fit the doc) and authority (PageRank — how important the page is), plus signals like freshness. The Doc Store then supplies titles and snippets for the winners.

Relevance × authority: BM25 asks “does this page match the words well?”; PageRank asks “is this page trustworthy?”. Combining them is why a search engine beats a plain keyword grep.

Step 5 · Too big for one box

Shard & scatter-gather

The index for the whole web is far too large for a single machine’s memory or disk, and one server can’t evaluate a query against billions of documents in time.

Design decision: The whole-web index is far too big for one machine. How do you search billions of docs in time?

The call: Shard by document; scatter to all shards, gather their top candidates. — Each shard searches its slice in parallel; the retriever fans out (scatter), each returns its local top results, and they’re merged (gather). You wait for the slowest shard, not the sum — latency stays bounded as the corpus grows.

Shard the index by document across many machines. A Retriever sends the query to every shard in parallel (scatter), each returns its local top candidates, and the retriever gathers and merges them for ranking. Latency stays bounded as the corpus grows.

Scatter-gather: Document-sharding means each shard searches a slice in parallel; you wait for the slowest shard, not the sum. Adding shards adds capacity without slowing any single query — the workhorse pattern of large-scale retrieval.

Step 6 · The same searches

Cache hot queries

A huge share of searches are the same popular queries repeated endlessly. Re-running the full parse → scatter-gather → rank pipeline for each identical query wastes enormous compute.

Design decision: A huge share of searches are the same popular queries repeated endlessly. How do you save that compute?

The call: Cache the result pages for popular (head) queries. — Search traffic follows a steep power law, so a modest result cache answers a large fraction of queries in ~1ms, sparing the index and ranking fleet for the rare, novel long-tail queries.

Cache the result pages for popular queries. Search traffic follows a steep power law, so a modest Result Cache answers a large fraction of queries in a millisecond, sparing the index and ranking fleet for the long tail.

Skew is your friend: When a small set of inputs drives most traffic, caching is pure win. Cache whole results for head queries; spend your retrieval budget on the rare, novel ones.

Step 7 · Stay current

Freshness & the sharp edges

News breaks and pages change constantly, but rebuilding a web-scale index takes time. Users also expect spelling correction, synonyms, and protection from spam pages gaming the ranking.

Run a small, fast fresh index for recent content merged with the big base index at query time. Layer query understanding (spell-correct, synonyms) before retrieval, and add spam/quality signals to ranking so manipulated pages don’t win.

Two indexes, one result: A real-time index for the last few hours plus a periodically rebuilt main index gives both freshness and scale. Ranking is an endless arms race against spam — quality signals are part of the design, not an afterthought.

You did it

You just designed a search engine.

• A — n
• Q — u
• A — n
• R — a
• D — o
• A —
• A —