System Design · Design Question
Design a Search Engine
Mini-Google: crawl, invert, rank, and serve queries — the four-stage pipeline interviewers expect.
1. Requirements
- 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.
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
- 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.
Quick revision
- 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.