How to Design a Web Crawler
Learn how to design a web crawler: frontier queues, politeness policy, deduplication with Bloom filters, and host-based sharding at scale.
Expected Interview Answer
A web crawler is designed as a distributed pipeline of a URL frontier, fetchers, parsers, and a dedup/storage layer, where politeness rules, priority scheduling, and a seen-URL filter keep it from overwhelming sites or wasting cycles on pages already visited.
The frontier is a priority queue of URLs to fetch, partitioned by host so that a politeness policy can enforce a delay between requests to the same domain. Fetcher workers pull URLs, respect robots.txt, download pages, and hand raw content to parsers that extract links and text; a Bloom filter or distributed hash set marks URLs as seen so the same page is never re-queued twice. Extracted links are normalized, filtered for relevance and freshness, then pushed back into the frontier, while content is stored for indexing. At scale this whole pipeline is sharded across many machines using consistent hashing by host, with a coordination layer tracking crawl state and handling failures gracefully.
- Politeness-aware scheduling avoids overloading or getting blocked by target sites
- Deduplication via Bloom filters keeps the crawl efficient at billions of URLs
- Host-based sharding lets the crawl scale horizontally across many machines
- Priority queues let fresh or high-value pages get recrawled sooner
AI Mentor Explanation
A web crawler is like a scouting network sent to track every domestic match across the country instead of one scout trying to watch every ground at once. Each scout (fetcher) is assigned a region (host) and must wait a respectful gap between visiting the same ground twice so as not to disrupt play, mirroring the politeness delay. A shared master ledger crosses off grounds already scouted so no scout wastes a trip revisiting one, just like the seen-URL filter. New leads discovered at one ground, like a promising player mentioned by a coach, get added to the master to-do list for the next round of scouting, the way a crawler queues freshly extracted links.
Step-by-Step Explanation
Step 1
Seed and prioritize the frontier
Start with seed URLs in a priority queue, ranked by estimated page value and freshness needs, partitioned by host for politeness.
Step 2
Fetch with politeness limits
Workers pull URLs, check robots.txt, and enforce a per-host delay so no single site is hammered with concurrent requests.
Step 3
Parse and deduplicate
Extract links and content from fetched pages; check each URL against a Bloom filter or distributed hash set before adding it back to the frontier.
Step 4
Store and recrawl on schedule
Persist page content and metadata for indexing, then requeue URLs for recrawl based on observed change frequency.
What Interviewer Expects
- Describes the frontier as a priority queue partitioned by host
- Explains politeness policy and robots.txt handling explicitly
- Names a deduplication mechanism like a Bloom filter for seen URLs
- Addresses horizontal scaling via host-based sharding and failure recovery
Common Mistakes
- Ignoring politeness and robots.txt, risking IP bans from crawled sites
- Using an in-memory set for deduplication that cannot scale to billions of URLs
- Not partitioning work by host, causing uneven load and possible site abuse
- Forgetting to plan for recrawl frequency and content freshness
Best Answer (HR Friendly)
“A web crawler is a system that automatically visits web pages, follows the links it finds, and stores the content for later use like search indexing. The tricky part is doing this politely and at scale, so it does not hammer any one website and does not waste effort revisiting pages it has already seen.”
Code Example
import time
class Crawler:
def __init__(self):
self.frontier = PriorityQueue() # (priority, url)
self.seen = BloomFilter(capacity=10_000_000)
self.last_fetch_by_host = {}
self.min_delay_seconds = 2
def enqueue(self, url, priority=1):
if url not in self.seen:
self.seen.add(url)
self.frontier.push((priority, url))
def crawl_one(self):
priority, url = self.frontier.pop()
host = extract_host(url)
last = self.last_fetch_by_host.get(host, 0)
wait = self.min_delay_seconds - (time.time() - last)
if wait > 0:
time.sleep(wait)
if not robots_allows(url):
return
page = fetch(url)
self.last_fetch_by_host[host] = time.time()
store(url, page.content)
for link in extract_links(page):
self.enqueue(normalize(link))Follow-up Questions
- How would you design the deduplication layer to work across billions of URLs and many machines?
- How do you decide crawl priority and recrawl frequency for a given page?
- How would you shard the frontier across crawler machines while respecting per-host politeness?
- How do you avoid crawler traps like infinite calendar pages or session-ID loops?
MCQ Practice
1. What data structure is commonly used to efficiently track billions of already-seen URLs with low memory overhead?
Bloom filters provide space-efficient probabilistic membership testing, ideal for deduplicating huge URL sets.
2. Why does a web crawler partition its frontier by host?
Grouping URLs by host lets the crawler apply a rate limit per domain, preventing it from overwhelming any one server.
3. What is a “crawler trap”?
Crawler traps are page structures that dynamically generate unlimited distinct URLs, which can trap a naive crawler in an infinite loop.
Flash Cards
What is the crawl frontier? — A priority queue of URLs to fetch next, typically partitioned by host for politeness and scheduling.
Why enforce politeness delays? — To avoid overwhelming a target site with concurrent requests and risking IP bans or service degradation.
How is URL deduplication done at scale? — Using a Bloom filter or distributed hash set to check if a URL has already been seen before re-queuing it.
What is a crawler trap? — A page structure that generates endless unique URLs, wasting crawl resources if not detected and limited.