system-design

Design a Search Engine (Google Search)

Difficulty: Tier 3 Asked at: Google, Amazon, Microsoft, senior loops Time budget: 45–60 min

Web search is the deepest read-side problem in this repo: take the entire crawled web and answer any query in ~100 ms, ranked by relevance. The signature structure is the inverted index (word → list of documents), the signature process is indexing (turning documents into that index), and the signature challenge is ranking at scale. Nobody expects PageRank in detail — they want the inverted-index + distributed-serving story.

Prerequisites: Search Systems, Web Crawler, Sharding, Batch vs Stream

1. Requirements

Functional:

Given a text query, return relevant web pages ranked by relevance, fast.
Full-text search over billions of documents.
Support multi-word queries, phrases; snippets.

Non-functional:

Low latency — results in ~100–300 ms.
Massive scale — billions of documents, billions of queries/day.
Relevance — the best results first (ranking quality is the product).
Fresh-ish — new/updated pages appear within a reasonable time.

Out of scope: crawling (separate), the full ranking-ML model, personalization internals, spam fighting (mention).

2. Estimation

Index side: ~100 billion documents; the inverted index is enormous (terabytes–petabytes) → sharded across thousands of machines.
Query side: ~100K+ queries/sec; each must fan out to many index shards and merge, in ~100 ms → massive parallelism + caching.
Two very different systems: offline indexing (batch, huge) and online serving (low-latency, highly parallel).

3. The core structure: the inverted index

🚨 An inverted index maps each term → a posting list of documents containing it (plus positions, frequencies for ranking).

"pizza"  → [doc3, doc17, doc42, ...]   (posting list, often sorted by doc/score)
"karachi"→ [doc17, doc88, ...]
Query "pizza karachi" → intersect the two posting lists → docs with both → rank

Building it: for each crawled doc, tokenize → for each term, append the doc to that term’s posting list. This is a giant batch (MapReduce-style) job over the whole corpus.
Querying it: look up each query term’s posting list, intersect/merge them, then rank the matching docs. 🚨 The inverted index is what turns “search billions of docs” into “look up a few posting lists.”

4. High-level design

flowchart TB
    Crawl[(Crawled pages)] --> Indexer[Indexing pipeline<br/>batch, tokenize, build]
    Indexer --> Index[(Inverted index<br/>sharded by term or doc)]

    Query[User query] --> QP[Query processor]
    QP -->|fan out| S1[Index shard 1]
    QP --> S2[Index shard 2]
    QP --> S3[Index shard N]
    S1 --> Merge[Merge + rank]
    S2 --> Merge
    S3 --> Merge
    Merge --> Cache[(Query result cache)]
    Cache --> Query

Offline: crawled pages → indexing pipeline → sharded inverted index (deployed to serving). Online: query → processor fans out to index shards → each returns its top candidates → merge and rank → return top results (heavily cached for popular queries).

5. Deep dives

5a. Sharding the index

The index is too big for one machine. Two sharding strategies:

Document partitioning (by doc): each shard holds the full inverted index for a subset of documents. A query fans out to all shards (each searches its docs), then merges. 🚨 The common choice — scales with corpus size, each shard is self-contained, fan-out parallelism gives low latency.
Term partitioning (by term): each shard holds full posting lists for a subset of terms. A query goes only to the shards holding its terms — less fan-out, but hot terms create hotspots and multi-term queries need cross-shard joins. Usually less favored.

5b. Ranking

Matching docs must be ordered by relevance. Signals: term frequency / inverse document frequency (TF-IDF), page importance (PageRank-style link analysis), freshness, location, and hundreds of ML features. 🚨 Do it in stages: cheaply retrieve a candidate set from the index, then apply expensive ranking to the top candidates only (not all billion). Reference the model; don’t rabbit-hole into PageRank math.

5c. Low latency via parallelism + caching

Fan-out parallelism: query hits all doc-shards concurrently; latency = slowest shard, not the sum.
Caching: popular queries’ results are cached (a big fraction of queries repeat) → serve instantly.
Early termination: posting lists sorted by score let a shard return top candidates without scanning everything.
Tiered index: a small hot index (popular docs) answers most queries fast; the full index backs it.

5d. Building & updating the index (freshness)

Full index builds are massive batch jobs. For freshness, layer an incremental/live index for recently-crawled pages on top of the periodically-rebuilt main index; queries search both and merge. 🚨 Same batch+streaming two-speed pattern as typeahead.

5e. Multi-word & phrase queries

Intersect posting lists for AND semantics; use positional info (stored in postings) for phrase queries (“exact phrase”). Compression of posting lists (delta + varint encoding) keeps the index size manageable.

6. Bottlenecks & scaling further

Index size → shard by document across thousands of machines; compress posting lists.
Query latency → fan-out parallelism + result caching + early termination + tiered hot index.
Ranking cost → staged retrieval (cheap candidate gen → expensive re-rank on top-K).
Freshness → incremental live index layered on the batch-built main index.
Query volume → cache popular queries; replicate serving shards.

7. Trade-off summary

Decision	Chosen	Alternative	Why
Structure	Inverted index	Scan documents	Turns billions-of-docs search into posting-list lookups
Sharding	By document (fan-out)	By term	Self-contained shards, parallel low latency, no term hotspots
Ranking	Staged (candidate → re-rank)	Rank all matches	Expensive ranking only on top candidates
Latency	Fan-out + cache + early-term	Serial search	Parallelism + repeats + sorted postings
Freshness	Batch main + incremental live	Rebuild constantly	Two-speed keeps fresh without full rebuilds

8. Follow-up questions

What is an inverted index and why is it essential?

An inverted index maps each term to a posting list of the documents that contain it (typically with extra data like term positions and frequencies), which is the inverse of a document→words mapping — hence "inverted." It's essential because it turns full-text search from an impossible scan into a lookup: instead of examining billions of documents to find those containing "pizza," you read the single posting list for "pizza" and immediately have the candidate documents; for a multi-word query you look up each term's posting list and intersect them to find documents containing all the terms. This reduces the query cost from proportional to the corpus size to roughly proportional to the number of matching documents for the query's terms, which is what makes sub-second search over billions of pages feasible. The positions stored in postings additionally enable phrase queries, and the frequencies feed ranking. Without an inverted index there's no practical way to answer arbitrary text queries at web scale.

How do you shard an index too big for one machine — and what are the trade-offs?

The common approach is document partitioning: each shard holds a complete inverted index over a *subset of the documents*. A query is broadcast to every shard in parallel; each searches its own documents and returns its best candidates, and the results are merged and ranked. Its advantages are that each shard is self- contained (it can fully answer over its docs), it scales naturally as the corpus grows (add more shards), and the fan-out is embarrassingly parallel so query latency is the slowest shard's time, not the sum — good for low latency. The alternative, term partitioning, puts complete posting lists for a *subset of terms* on each shard, so a query only contacts the shards holding its query terms (less fan-out); but it suffers from hotspots (common terms concentrate load on their shard) and multi-term queries require shipping and joining large posting lists across shards, which is expensive. So document partitioning is usually preferred for web search despite requiring every query to fan out to all shards, because the parallelism is cheap and it avoids term hotspots and cross-shard joins.

How do you rank results without scoring billions of documents per query?

With staged ranking: cheap retrieval first, expensive ranking only on a small candidate set. The inverted index (with posting lists often sorted by a static importance score) cheaply produces a bounded set of candidate documents that match the query terms — you can even early-terminate, taking the top candidates from each shard without scanning entire posting lists. Only those candidates (thousands, not billions) are then passed to the expensive ranking stage, which applies the full set of relevance signals — term frequency/IDF, link-based importance like PageRank, freshness, location, and many ML features — to order them precisely. This funnel keeps the costly computation proportional to a small candidate set per query rather than the whole corpus, which is what lets high-quality ranking coexist with a ~100 ms latency budget. Caching popular queries' final results avoids even that work for repeats.

How is the index kept fresh when a full rebuild is a massive batch job?

By layering a fast incremental index on top of the slowly-rebuilt main one — the same two-speed pattern as autocomplete. The main inverted index is produced by large periodic batch jobs over the whole crawled corpus, which is efficient but too slow to reflect brand-new pages immediately. So recently crawled or updated documents are added to a smaller, live/incremental index that updates quickly. Queries search both the main index and the live index and merge the results, so fresh content appears without waiting for the next full rebuild, while the bulk of the corpus is served from the efficient batch-built index. Periodically the live index's contents are folded into the next main rebuild. This gives near-real-time freshness for new content at low incremental cost, accepting the complexity of querying and merging two indexes.

9. What junior / mid / senior answers look like

Junior: proposes scanning documents or a naive database text search; may not know the inverted index — can’t reach web scale or latency.
Mid: builds an inverted index, shards it, fans out queries and merges, ranks by TF-IDF + importance, caches popular queries.
Senior: document-partitioned sharding with fan-out parallelism, staged retrieval-then-rerank to bound ranking cost, early termination and result caching for latency, a batch+incremental two-speed index for freshness, positional postings for phrases, and compression — cleanly separating the offline indexing system from the online low-latency serving system.