Design a Web Crawler and Search Index
Crawling billions of pages politely, deduplicating near-identical content, and building an inverted index that answers a query in under 200 ms.
Covers: Crawl frontier, politeness, deduplication, inverted index, sharding strategies, ranking, index freshness
This case study covers two systems that happen to be adjacent: a massively parallel, politeness-constrained crawler, and a distributed inverted index. They test completely different skills, which is exactly why interviewers like it.
- Crawl: 10 B pages, refreshed monthly ≈ 4,000 pages/s sustained.
- Storage: 10 B × 100 KB compressed ≈ 1 PB of raw content.
- Index: inverted index roughly 10–20% of corpus size ≈ 100–200 TB.
- Query: p99 under 200 ms across the full corpus.
- Politeness: never overwhelm a host - typically at most one request per host per second, and always respect
robots.txt.
30-second answer
The core structure is a URL frontier: a set of per-host queues with a scheduler that guarantees at most one in-flight request per host, so politeness is enforced by the data structure rather than by hoping workers behave. Deduplicate at three levels - exact URL after canonicalisation, exact content by hash, and near-duplicate content by SimHash, since a huge fraction of the web is boilerplate variations of the same page. Store the frontier durably and partition it by host hash so each worker owns a disjoint set of hosts and no cross-worker coordination is needed.
Crawler architecture
The frontier is the heart of the system. Everything else is fetching, parsing and storage.
Flow
- URL frontierScheduler
- SchedulerFetchers
- FetchersDedup
- DedupParser
- ParserContent store
- ParserURL frontier(new links)
Three levels of deduplication
| Level | Catches | Mechanism | Cost |
|---|---|---|---|
| URL | The same page requested twice | Canonicalise (strip session IDs, sort params, normalise case), then a Bloom filter | ~1.2 GB for 10 B URLs at 1% FP |
| Exact content | Mirrors and identical copies | SHA-256 of normalised content | 32 B per page |
| Near duplicate | Printer versions, minor edits, boilerplate | SimHash with Hamming distance ≤ 3 | 8 B per page plus an index |
Say these points
- Per-host queues make politeness structurally impossible to violate.
- Partition the frontier by hash(host) so workers need no coordination.
- Deduplicate at URL, exact-content and near-duplicate levels.
- Bloom filters handle billions of seen URLs in a few gigabytes.
- Adaptive recrawl frequency from observed change rate.
Avoid these mistakes
- Politeness enforced in worker code rather than in the frontier structure.
- No near-duplicate detection, so the index fills with boilerplate.
- Ignoring crawler traps and burning the budget on infinite calendars.
- Uniform recrawl intervals across the entire corpus.
- An in-memory frontier that is lost on restart.
Expect these follow-ups
- How do you handle JavaScript-rendered pages?
- How would you prioritise which pages to crawl first with a limited budget?
- How do you distribute the frontier across 1,000 machines?
30-second answer
An inverted index maps each term to a posting list of the documents containing it, with positions and frequencies. A query intersects the posting lists of its terms and ranks the results. Shard by **document** rather than by term: each shard holds a complete index over a subset of documents, so every query fans out to all shards, each returns its top-k, and a coordinator merges them. Term sharding looks appealing because a query only touches a few shards, but it creates catastrophic hotspots on common terms and makes multi-term intersection require cross-shard traffic.
| Document sharding | Term sharding | |
|---|---|---|
| Each shard holds | All terms for a subset of documents | All documents for a subset of terms |
| Query fan-out | All shards | Only shards holding the query terms |
| Load balance | Even | Terrible - common terms are enormous |
| Multi-term intersection | Local to each shard | Requires shipping posting lists between shards |
| Adding documents | Add to one shard | Touches many shards |
| Used in practice | Yes, almost universally | Rarely |
# Inverted index: term -> posting list, sorted by doc id for fast intersection.
index = {
"machine": [(doc_1, tf=3, pos=[12, 45, 89]), (doc_7, tf=1, pos=[3]), ...],
"learning": [(doc_1, tf=5, pos=[13, 46, 90, 120, 200]), (doc_9, ...), ...],
}
def search(query_terms, k=10):
lists = [index[t] for t in query_terms if t in index]
if not lists:
return []
# Intersect from the shortest list - it bounds the result size.
lists.sort(key=len)
candidates = intersect_sorted(lists) # skip pointers make this sublinear
scored = [(d, bm25(d, query_terms) + 0.3 * pagerank(d)) for d in candidates]
return heapq.nlargest(k, scored, key=lambda x: x[1])
# Coordinator: fan out to every shard, each returns its local top-k, merge.
# Latency = slowest shard, not the sum - so tail latency per shard is what
# actually determines query latency.Two-stage retrieval
1 · Candidate retrieval (cheap, high recall)
Intersect posting lists and score with BM25 - a fast lexical relevance function using term frequency and inverse document frequency. Return a few thousand candidates per shard.2 · Reranking (expensive, high precision)
Rerank the top few hundred with an expensive model that considers semantic similarity, click history, freshness and authority. Too costly to run over the full corpus, entirely affordable over a few hundred documents - which is exactly why stage one exists.
Index freshness
- Inverted indexes are built in batches; you cannot cheaply insert into a compressed posting list.
- Standard pattern: a large immutable base index plus a small in-memory incremental index for recent documents, queried together and merged.
- Periodically merge the incremental index into the base - the same idea as LSM compaction.
- Deletions use a tombstone bitmap filtered at query time rather than rewriting posting lists.
Say these points
- Shard by document, not by term - term sharding creates unfixable hotspots.
- Query fans out to all shards; each returns local top-k and a coordinator merges.
- Two-stage retrieval: cheap BM25 recall, then expensive reranking.
- Skip pointers, tiered indexes and compression are what deliver sub-200 ms.
- Base index plus incremental index, merged periodically, handles freshness.
Avoid these mistakes
- Term sharding, and the hotspot on common words.
- Reranking the full candidate set with an expensive model.
- Rewriting posting lists on delete instead of using tombstones.
- Ignoring that fan-out latency equals the slowest shard, so per-shard tail latency dominates.
Expect these follow-ups
- How do you support phrase queries like "machine learning" exactly?
- How would you add typo tolerance without exploding the index?
- How do you A/B test a new ranking function on live traffic?
Showing 2 of 2 questions for design-a-web-crawler-and-search.
Check your understanding
4 questions · no sign-up, nothing stored
Hands-on challenge
Build it - this is what you talk about in a deep-dive round.
Build a small crawler and search index
Crawl 100,000 pages from a permitted seed set and build a searchable inverted index. Scale down, but keep every architectural decision.
Requirements
- Implement a per-host frontier that structurally enforces politeness and respects robots.txt.
- Implement all three deduplication levels and report how many pages each caught.
- Build an inverted index with positions, and implement BM25 scoring.
- Shard the index across at least three processes with a fan-out coordinator.
- Measure p50 and p99 query latency and identify the dominant cost.
Stretch goals
- Add skip pointers and measure the intersection speedup.
- Add an incremental index for newly crawled pages and merge it periodically.