Case study

Design a Web Search Engine

Index billions of web pages and return ranked search results in under 200ms.

inverted indexPageRankcrawler

Requirements

Functional: keyword search; ranked results; snippets; spelling correction; autocomplete
Freshness: new pages indexed within 24 hours (news within minutes)
Non-functional: query p99 < 200ms; 50K QPS peak
Scale: 50B pages indexed; 5B queries/day

Back-of-envelope Estimation

Metric	Calculation	Result
Query QPS	5B / 86,400	~58K/sec avg; ~150K peak
Index size	50B × 50 KB inverted index portion	~500 TB compressed index
Postings lists	Avg 10 tokens/page × 50B	500B posting entries
Crawl rate	50B pages / 30 days refresh cycle	~20K pages/sec continuous

API Design

Endpoint	Description
GET /v1/search?q=&page=	{ results[{ url, title, snippet, score }], total }
GET /v1/suggest?q=	Autocomplete (see typeahead system)
Internal: /index/doc	Crawler pushes parsed document to index pipeline

Data Model

Component	Structure
Inverted index	term → posting list [(doc_id, tf, positions)]
Forward index	doc_id → { url, title, body, pagerank, freshness }
Doc ID mapping	url_hash → doc_id compact integer
Index shards	Shard by term hash — each shard holds subset of vocabulary

High-level Design

Search pipeline

Crawler ──► Index Builder ──► Sharded Inverted Index (distributed)
                                              │
Query ──► Query Parser ──► Scatter to index shards (parallel)
              │                    │
              └──► Merge & Rank (PageRank + BM25 + freshness)
              │
              └──► Snippet generator ──► Results

Deep Dive: Query Execution

Parse query → terms; spell-correct; expand synonyms
Scatter term lookups to shards owning those terms (MapReduce style)
Intersect posting lists for AND queries; union for OR
Score top 10K candidates with BM25 + PageRank boost
Fetch forward index for top 100; generate snippets; return top 10

Deep Dive: Index Sharding & Tiered Serving

Shard inverted index by term — common terms ('the') may have dedicated replicas. Hot tier in SSD RAM cache; cold tier on disk. Query coordinator caches popular query results 60 sec.

PageRank

Precomputed offline batch job monthly; stored in forward index as scalar boost. Real-time news uses freshness decay: score × e^(-age/half_life).

Failure Modes & Monitoring

SLO	Target
Query p99	< 200ms
Index freshness (news)	< 5 min
Zero-result rate	< 5% (track query reformulation)

Degrade: skip spell-check and secondary ranking under load
Monitor: shard latency skew, slow terms, crawl-index lag, ranking quality A/B metrics

System Design