Loading…
Loading…
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.
Q: How does the crawler stay polite to websites? A: It obeys robots.txt rules and crawl-delay directives, limits concurrent connections per host, and spaces out requests to the same domain. The frontier is usually organized as per-host queues, with a scheduler that picks the next host only when its politeness delay has passed. Identify the crawler with a clear user agent, and back off when a host returns errors or slows down.
Q: How do you avoid crawling the same URL repeatedly? A: Normalize URLs (lower-case the host, remove default ports and fragments, sort or strip tracking parameters), then check a "seen" set. At billions of URLs, a Bloom filter or a sharded key-value store keeps that check cheap. A Bloom filter's rare false positives mean a few pages are skipped, which is usually acceptable.
Q: How do you detect duplicate or near-duplicate content served at different URLs? A: Compute a content fingerprint. An exact hash catches identical pages, and SimHash or MinHash catches near-duplicates, such as the same article with different ads. Skip or down-rank pages whose fingerprint is already known. This saves storage and indexing work, and avoids crawler traps built from endlessly varying URLs.
Q: What are crawler traps, and how do you defend against them? A: Traps are infinite URL spaces: calendars with endless "next month" links, session IDs in URLs, or auto-generated pages. Defences include limits on URL length and path depth, per-host page budgets, detecting repeating path patterns, and deprioritizing hosts whose pages are mostly near-duplicates.
Q: How do you decide how often to re-crawl a page?
A: Estimate each page's change rate from past crawls (how often its fingerprint changed) and its importance (link-based rank, traffic), then schedule re-crawls proportionally. News homepages might be revisited every few minutes, and static archives every few months. Conditional requests (If-Modified-Since, ETags) make revisits of unchanged pages cheap.
Q: How is the crawl distributed across many machines? A: Partition the URL space by host hash, so each worker owns a set of hosts. That keeps politeness enforcement local, with no cross-machine coordination per request. Discovered URLs for other hosts are sent to their owning worker through a queue. Rebalancing uses consistent hashing as workers join or leave.