Design a web crawler that discovers and downloads web pages starting from a set of seed URLs, following links to discover new pages, while respecting site politeness constraints and avoiding infinite loops.
Assume crawling 1 billion pages/month. That's roughly 1B / (30 * 24 * 3600) ≈ 385 pages/second sustained. Assuming an average page size of 500KB, that's ~190MB/second of bandwidth, and roughly 500TB/month of storage for raw page content alone (before deduplication or compression) — these numbers are what justify a distributed, horizontally-scalable crawler rather than a single-machine one.
[Seed URLs] → [URL Frontier] → [Crawler Workers (many, distributed)]
↑ │
│ fetch page, parse HTML
│ │
new URLs found ←───── extract links
│ │
[Dedup Filter] [Content Store]
(Bloom filter / seen-URL set) │
[Downstream: indexing, analysis]
The URL Frontier is the central coordination structure — a priority queue (or set of queues) holding URLs waiting to be crawled. Each crawler worker pulls a URL from the frontier, fetches the page, extracts new links, and feeds newly-discovered URLs back into the frontier (after deduplication) — this feedback loop is what drives discovery outward from the seed set.
BFS (see BFS / Level Order for the same shortest-path-guarantee property applied here) is the natural traversal order: crawl all pages linked directly from the seeds before going two links deep, three links deep, and so on. This has a practical benefit beyond just traversal order — BFS naturally spreads early crawling across many different domains (since seed pages typically link to many different sites) rather than DFS's tendency to plunge deep into one site's link structure first, which directly supports the politeness requirement below.
A single, centralized frontier queue becomes a bottleneck at billions-of-pages scale. The standard fix: partition the frontier by domain (consistent hashing on hostname, the same technique from the Distributed Cache case), so each crawler worker (or worker group) owns a specific set of domains — this simultaneously solves the distribution problem AND makes politeness enforcement local (a worker naturally rate-limits itself against the domains it owns, without needing cross-worker coordination for that specific concern).
Internal service APIs (not public-facing): POST /frontier/enqueue { url, priority, discoveredFrom } GET /frontier/next?workerId={id} → returns next URL(s) this worker should crawl POST /content/store { url, html, fetchedAt, statusCode } GET /robots/{domain} → cached robots.txt rules for a domain, refreshed periodically
URL Frontier (priority queue per domain shard):
frontier_queue: domain (partition key), priority, url, discovered_at
Seen-URL set (deduplication — see below for why this needs to be a Bloom filter at scale, not a literal set):
seen_urls: bloom filter, sharded alongside the frontier by domain
Content store (the actual crawled pages, blob storage — same pattern as Design a Distributed File Storage System's separation of metadata from blob content):
pages: url (key), content_hash, raw_html (blob ref), fetched_at, http_status
Crawling too aggressively against a single domain is both bad citizenship and a good way to get the crawler's IP range blocked entirely. Each domain gets its own rate limit (see the Rate Limiter case for the underlying algorithms) — typically enforced as a minimum delay between consecutive requests to the same domain, tracked per-domain in the frontier partitioning described above, so one worker never issues two requests to the same domain faster than that domain's configured politeness delay allows.
A crawler trap is a site (deliberately or accidentally) generating an effectively infinite sequence of distinct URLs — a calendar page linking to 'next month' forever, or session-ID query parameters making every URL technically unique. Mitigations: capping crawl depth per domain, detecting and normalizing URL patterns that differ only in ignorable parameters (session IDs, tracking parameters), and setting a maximum page count per domain — without these, a single pathological site can consume disproportionate crawler resources indefinitely.
Each domain's robots.txt declares which paths crawlers may or may not access, and can specify a Crawl-delay. Fetching and caching robots.txt per domain (refreshed periodically, since it can change) before crawling any of that domain's pages is a hard design constraint, not an optional politeness nicety — many sites actively block crawlers that ignore it, and it's the standard, expected mechanism for a site to opt out of crawling specific paths entirely.
BFS-first crawling trades "depth into any one site early" for "breadth across many sites early" — appropriate for general web crawling, but a crawler built specifically to thoroughly index one domain might reasonably prefer DFS or a domain-focused strategy instead. A Bloom filter for URL deduplication trades perfect accuracy (a small, tunable false-positive rate — occasionally treating a genuinely new URL as already-seen) for the massive space savings needed at billions-of-URLs scale, where a literal hash set would be prohibitively large to keep in memory or even on fast storage.
The URL Frontier is the central coordination point and the most likely bottleneck without domain-based partitioning — a single unpartitioned frontier queue serializes all crawler workers against it. DNS resolution can also become a bottleneck at high request rates against many distinct domains, commonly mitigated with a local, cached DNS resolver rather than querying external DNS servers for every single request.
A crawler worker crashing mid-fetch should not lose track of the URL it was processing — the frontier should only remove a URL once it's confirmed successfully processed (fetched and its links extracted), not the moment it's handed to a worker, so a crashed worker's in-flight URLs are recoverable rather than silently dropped. An unresponsive target server needs a bounded timeout (see the general request-timeout pattern from Locking Strategies/ExecutorService & Thread Pools) so one slow/dead site doesn't tie up a worker indefinitely.