System Design · Design Question

Design a Search Engine

Mini-Google: crawl, invert, rank, and serve queries — the four-stage pipeline interviewers expect.

In simple words: The pipeline is crawl, index, rank, and serve. The index finds candidates quickly; a richer ranking step chooses the best few.

Concrete example: Search "python tutorial" → the inverted index finds pages with both terms → BM25 and PageRank rank them → top 10 URLs with snippets return in under 100 ms.

1. Requirements

Functional

Index a large web corpus (or document set).
Answer keyword queries with ranked top-K results in tens–hundreds of ms.
Freshness: new/updated pages appear within a target lag.
Scale storage and query fan-out across shards.

Non-functional

Serve queries in tens to hundreds of milliseconds despite shard fan-out.
Scale corpus storage and query replicas independently.

Back-of-envelope

10B documents × 100KB average ≈ 1PB raw corpus. If the inverted index is ~20% of source size, budget ~200TB before replication; peak may be 100k queries/s.

Phases: Crawl → Index → Rank → Serve Do not design ads/Knowledge Graph unless asked

2. API

GET /search?q=distributed%20systems&page=1 → { "results": [ { "url", "title", "snippet", "score" } ], "tookMs": 42 }

3. Pipeline overview

[Crawler] → documents store | [Indexer] → inverted index shards + forward index (title, url) | [Link graph jobs] → PageRank / signals | Query → [Frontend] → [Root aggregator] → leaf index shards → merge → snippets

4. Crawling (brief)

Same building blocks as the web crawler design: frontier, politeness, dedupe, content store. Output is a corpus of documents with canonical URLs and fetch metadata.

5. Indexing

An inverted index maps each word to the list of documents containing it. Query "python tutorial" → intersect postings for python and tutorial → score surviving docs.

Tokenize, normalize (case, Unicode), remove stop words (careful), stem optional.
Build inverted index: term → postings (docId, positions, tf).
Forward index: docId → url, title, length for snippets.
Sharding: by docId ranges or term; replication for HA.

Indexing modes: batch: rebuild segments offline, swap incremental: update postings for changed docs (harder deletes → tombstones)

6. Ranking

Signal	Role
BM25 / TF-IDF	Text relevance
PageRank / authority	Global quality
Freshness	News queries
User/context	Locale, history (careful privacy)

Two-phase: cheap retrieval of candidates from postings intersection, then heavier re-ranker on top hundreds.

7. Query serving

1) Parse query (AND/OR phrases) 2) Fan-out to index leaves holding terms/docs 3) Each leaf returns local top-K 4) Root merges, fetches snippets from forward index 5) Cache hot queries at edge with short TTL

8. Data model

docs(doc_id, url, title, storage_ptr, length, pagerank) postings stored in segment files per shard (Lucene-like) crawled_pages blob store

9. Scaling

More leaf shards as corpus grows; replicate leaves for QPS.
Tiered indexes: fresh realtime tier + deep web tier.
Separate crawl bandwidth from query clusters.

10. Challenges to name

Spam / SEO manipulation → quality classifiers.
JavaScript-heavy pages → rendering farm (costly).
Multilingual tokenization.
Tail latency from slow shards → hedged requests / timeouts.

11. Failure modes and edge cases

Slow leaf shard → deadline, hedged request, or partial result with an explicit marker.
Deleted document remains in an old segment → tombstone filters it until compaction.
Empty/stop-word-only query → return guidance or trending results, not a full-corpus scan.
Crawler/indexer lag → expose freshness metrics; query serving remains independent.

Interview talking points

Lead with: Use the four-stage story: crawl, index, rank, serve.
Four stages: crawl, index, rank, serve.
Inverted index is the core retrieval structure.
Retrieve candidates then re-rank with richer signals.
Root aggregator fans out to leaf shards and merges top-K.
Realtime + batch index tiers for freshness.
PageRank/authority complements text scores.
Cache hot queries carefully; watch spam and tail latency.