Design a web search engine

Someone types three words, and within a few hundred milliseconds sees the ten best pages out of billions, with a sensible snippet for each. The crawler that fetches pages is Design D09 and the suggestions while typing are D10; this design is the part in between: building the index, answering queries across thousands of machines, and ranking well.

1. The prompt

"Design web search: given a query, return the most relevant pages from a crawl of the web, fast, with fresh results when news breaks."

What makes it hard:

• The index is far too big for one machine, so every query becomes a fan-out to thousands of them, and the slowest one sets the response time.
• Relevance is the product. Fast but wrong results are worthless, and "right" can only be measured, not proved.
• The web changes constantly, but rebuilding an index of billions of pages takes hours.

2. Frame the problem

3. What it must do

1. A user can search with a text query and get the ten most relevant pages, with a title and snippet each, and more pages on request.
2. The system can index new and changed pages from the crawler, with freshness depending on the kind of page.
3. The system can remove a page from results quickly (legal requests, malware, the page is gone).

Not now: crawling (D09), suggestions while typing (D10), ads, image and video search, per-user ranking.

4. How well it must do it

5. Numbers that change the design

Skip estimating snippet storage: documents live in a separate store and are fetched only for the final ten results.

6. The nouns

• Document: a page's URL, title, text, language and quality signals.
• Term and posting list: for each word, the documents containing it, with counts and positions.
• Index shard and its replicas.
• Query and result page.
• Blocklist entry: a URL that must not be shown.

documents   doc_id, url, title, text_key (blob), lang, quality, indexed_at        (document store, sharded by doc_id)
postings    term → [(doc_id, term_freq, positions)]  sorted by doc_id, compressed  (inside each index shard)
doc_stats   doc_id → length, static_score                                       (per shard, for ranking)
blocklist   url_hash, reason, added_at                                          (small, replicated to every front end)

7. The contract

GET /v1/search?q=hiking+boots&lang=en&page_token=…
    → {results: [{url, title, snippet}], next_page_token, corrected_query?}

internal  Shard.Search(query_terms, k, deadline)  → [(doc_id, score)]   (gRPC, one call per shard)
          Docs.Snippets(doc_ids, query_terms)     → [{url, title, snippet}]
          Indexer consumes crawled pages from a queue; RealtimeIndexer consumes a stream of news pages

Data flow: crawled page → parse and clean → tokenise (lower-case, split, stem) → write postings into index segments → publish segments to shards → serve.

8. First working version

One machine: an indexer, an inverted index, a document store, and a query service.

8.1 Indexing a page

The page's text is split into terms; each term's posting list gains this document. Lists are kept sorted by document ID so they compress well and can be intersected quickly.

8.2 Answering a query

Look up each query term's posting list, intersect them (or union, scoring partial matches lower), score candidates with a text-relevance formula such as BM25 (rare terms count more; a term repeated in a short document counts more), keep the top 10, then fetch titles and snippets.

9. Make it hold up

9.1 Splitting the index latency · availability

This is Module 12's scatter-gather, at web scale: a root server sends the query to one replica of every shard, each returns its top results, and the root merges them.

9.2 Fast posting lists latency

• Compression: store gaps between sorted document IDs, not the IDs, with variable-length encoding; small gaps take a byte or less, so more of the index fits in memory.
• Skip pointers let an intersection jump over long runs of a common word's list.
• Early termination: order each list so high-impact documents come first, or use bounds on the best possible score (WAND-style), and stop once the top 10 can't change.

9.3 Ranking in stages relevance

9.4 Fresh results without rebuilding everything freshness

• The main index is rebuilt in batches (new segments daily, full rebuilds less often), like an LSM tree's large files (Module 12).
• A small real-time index takes news and frequently changing pages from a stream within minutes.
• Every query searches both and merges, preferring the newer copy of a document.
• New segments are built offline, checked (size, sample queries), then rolled to shard replicas one at a time.

9.5 Taming the fan-out's tail p99 under 300 ms

9.6 Removing a page fast removals within minutes

Rebuilding the index for one URL is far too slow. Keep a small blocklist replicated to every front end and filter results at serve time; the next index build drops the page permanently. The result cache is invalidated for affected queries, or simply filtered on the way out.

9.7 The whole design after the deep dives

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Document partitioning (every query touches many shards) for independence and easy growth.
• Partial results under a deadline instead of always-complete answers.
• A ranking cascade: cheap first, expensive only for the top candidates.
• Two indexes (batch and real-time) instead of one that's always up to date.
• A serve-time blocklist for fast removals.

What we'd watch: p99 latency · share of queries with partial results · cache hit rate · real-time index lag · relevance metrics from clicks and ratings · per-shard load.

At 10×: more replicas for queries, more shards and tiers for pages, more caching.

Common mistakes:

• "Use Elasticsearch" with no idea how it scales.
• Term partitioning without discussing multi-word queries.
• Waiting for every shard.
• Ranking by text match alone.
• Rebuilding the index to remove one page.
• No way to measure relevance.

13. Try it, check yourself, read more

Inverted index playground. Eight tiny "web pages". Type a query and see each term's posting list, the candidate pages, and their BM25 scores. Notice how a rare word counts more than a common one, and how a short page that repeats your word ranks above a long one. The page called "Boots" is keyword stuffing: it scores near the top on text match alone, which is why real ranking adds quality signals (9.3).

BM25 with k1 = 1.2 and b = 0.75; words are lower-cased and a few common endings are stripped. Real engines add positions (phrases), quality scores and learned re-ranking on top.