Design a Search Engine

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

1. Rejected. Scan every document for the query terms.

   Reading the entire web on every search is hopeless — billions of docs per query. You must precompute where each word lives, not search at query time.

2. Rejected. A forward index: for each doc, the list of its words.

   Doc → words answers "what’s in this page?", the wrong question. You’d still scan every doc’s word list to find a term. You need the inverse.

3. 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.

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

1. Rejected. Add every word form as a synonym in the index.

   Enumerating every case/tense/plural for every word explodes the index and still misses forms you didn’t list. Normalize both sides instead of expanding one.

2. 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.

3. Rejected. Do a fuzzy/substring match against raw terms.

   Substring matching can’t use the postings lists (slow) and is wrong (matches "run" inside "errand"). The principled fix is identical normalization, not fuzzy scanning.

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

1. Rejected. Build postings on the fly as each query arrives.

   Indexing a document is heavy work; doing it in the query path would make every search wait on parsing pages. Build and serve are opposite workloads — separate them.

2. 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.

3. Rejected. Re-index the whole corpus on every crawler update.

   Rebuilding billions of postings for each new page is absurdly wasteful. Indexing is incremental — append/merge new postings into segments — not a full rebuild per change.

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

1. Rejected. Sort by how many times the term appears in the doc.

   Raw term frequency rewards keyword-stuffed and long pages and ignores authority — a spam page repeating the word wins. You need match quality and trustworthiness.

2. Rejected. Sort by the page’s authority (PageRank) alone.

   Authority without textual relevance returns famous pages that barely match the query. A trusted page on the wrong topic isn’t a good result — you need relevance too.

3. 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.

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

1. Rejected. Shard the index by term (each machine owns some words).

   Term-sharding creates hotspots on common words and uneven load, and the postings for a popular term still won’t fit one box. Document-sharding spreads work evenly.

2. 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.

3. Rejected. Keep one giant index and add more replicas.

   Replicas add throughput but every replica still can’t fit or evaluate the whole-web index in time. You must partition the index across machines, then replicate each shard.

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

1. Rejected. Add more retrieval and ranking machines to keep up.

   Scaling the fleet to re-run identical popular queries burns compute on work you already did. When the same input repeats, recompute is the waste to eliminate, not to scale.

2. Rejected. Cache each shard’s postings more aggressively.

   Postings caching helps retrieval but still re-runs parse → scatter-gather → rank → merge for every repeat of a head query. You can skip the whole pipeline by caching the finished result.

3. 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.