System Design · Hard
Design a web crawler & search engine
Crawl the web, build an inverted index, and serve ranked search results at scale.
Requirements
What the system must do, and how well it must do it.
Functional
Crawl billions of pages: fetch, parse, extract links, respect robots.txt.
Build an inverted index: term → (doc_id, positions, tf-idf).
Rank results: BM25 + PageRank + freshness + personalization.
Serve queries with autocomplete, spelling correction, and snippets.
Recrawl: prioritize by change frequency and importance.
Non-functional
Crawl 10B pages, 100 TB raw HTML.
Index update latency: new page searchable within 1 hour.
Query p99 latency under 100 ms.
99.9% availability for search API.
Estimation
Back of the envelope numbers that drive the design.
10B pages × 10 KB = 100 TB HTML. Compressed: 20 TB.
Inverted index: 100B unique terms × avg 100 postings = 10T postings.
Index size: ~5 PB (compressed, with positions).
Crawl rate: 1M pages/sec = 86B pages/day (with politeness).
Architecture
Design decisions
Crawler architecture
The URL frontier is a priority queue (by PageRank, freshness, politeness). Fetchers pull URLs, respect robots.txt and crawl-delay, fetch with conditional GET (ETag/Last-Modified), and parse HTML. The extractor emits (1) outlinks → frontier, (2) page content → indexer. The fetcher is distributed: each host is assigned to one fetcher (politeness), using consistent hashing.
Inverted index
The indexer tokenizes (language-specific), stems, and builds postings: term → list of (doc_id, positions, tf). The index is sharded by term (hash partitioning). Each shard is an LSM tree (like RocksDB) for write throughput. Merges compact postings and compute tf-idf. Positions enable phrase queries and proximity ranking.
Ranking
Query → rewrite (synonyms, spelling correction) → retrieve candidate docs from inverted index (top-K by BM25) → rerank with ML model (Learning to Rank: LambdaMART or neural). Features: BM25, PageRank, freshness, click-through rate, geo, personalization. The reranker runs on a GPU/TPU cluster. Top 10 returned with snippets (extracted from stored page content).
Recrawl and freshness
Pages have a recrawl priority: high PageRank + high change frequency = recrawl often. A change detector (checksum or content hash) avoids re-indexing unchanged pages. The frontier scheduler allocates crawl budget per host. Freshness SLA: news sites within minutes, static sites within days.
Questions and answers
Follow-ups an interviewer is likely to ask. Try answering before you open each one.
How do you handle duplicate content?
Simhash or MinHash near-deduplication at index time. Cluster near-duplicates; index only the canonical. At query time, collapse duplicates in results.
What about JavaScript-rendered pages?
Headless browser (Puppeteer/Playwright) for a subset of high-value sites. Render, wait for network idle, then extract. Expensive: run on a separate fleet with lower priority.
How do you scale the query path?
Inverted index shards are replicated (read replicas). Query fan-out: broadcast to all shards, each returns top-K local, coordinator merges. Cache hot queries (top 1M) in Redis. Autocomplete from a separate prefix trie.