Web Crawler
IntermediateOverview
A web crawler systematically discovers and downloads pages from the web, starting from a set of seed URLs and following links outward, so their content can be indexed by a search engine. The design must be polite to hosts, avoid re-fetching the same page, and scale to billions of URLs.
Functional Requirements
- Fetch pages starting from seed URLs and recursively discover new URLs by parsing links out of downloaded HTML.
- Store the raw content of each fetched page for downstream processing such as indexing.
- Deduplicate URLs and content so each unique page is fetched and stored once.
- Respect
robots.txtrules and per-host politeness (a bounded crawl rate per domain). - Support periodic recrawling so previously seen pages are refreshed when their content changes.
Non-Functional Requirements
- Scalability: crawl on the order of a billion pages per month across many worker machines.
- Politeness and robustness: never overload a single host, and survive malformed pages, redirects, and crawler traps.
- Extensibility: allow new content types and parsers to be added without redesigning the pipeline.
Capacity Estimation
Assume a target of 1 billion pages per month and an average downloaded page size of 500 KB (stored compressed at roughly 100 KB).
- QPS: 1,000,000,000 pages / (30 days x 86,400 s) ~ ~385 fetches/sec average. Allowing a 2x peak gives ~800 fetches/sec.
- Bandwidth: 385 pages/sec x 500 KB ~ ~190 MB/s ~ 1.5 Gbps of sustained download bandwidth (roughly double at peak).
- Storage: 1e9 pages x 100 KB compressed = ~100 TB/month of page content, plus URL and metadata records. Over a year of retained crawls this approaches ~1.2 PB.
High-Level Architecture
The architecture revolves around a URL Frontier (a priority queue of URLs to visit) and a cluster of Fetcher/Parser workers. A Deduplication service ensures we don't crawl the same page twice, and a Politeness Enforcer guarantees we don't accidentally DDoS a single website by hitting it too fast.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| Frontier entry | url, host, priority, next_fetch_at | Durable message queue with per-host sub-queues |
| Seen-URL set | url_hash | Bloom filter in front of a key-value store |
| Page | url, content_hash, fetched_at, status, raw_body | Object/blob storage for bodies, wide-column store for metadata |
| Host profile | host, crawl_delay, robots_rules | Key-value store (Redis) |
Detailed Design
The URL Frontier & Politeness
The heart of the crawler is the URL Frontier. It is not a single FIFO queue; it is partitioned into per-host sub-queues. Each sub-queue is governed by that host's crawl delay (as specified in robots.txt). Worker threads pull from a router that ensures no two workers ever fetch from the same host concurrently. This guarantees "politeness".
Deduplication (URLs and Content)
Deduplication runs before a URL ever enters the frontier.
- URL Deduplication: Each candidate URL is normalized (lowercased host, sorted query params, fragment stripped) and hashed, then tested against a Bloom Filter. A Bloom filter answers "have we seen this?" in constant time using a fraction of the memory a full set would need. If the filter says "maybe", we check the DB to be sure.
- Content Deduplication: Two different URLs might serve the exact same content. To avoid storing duplicates, we hash the HTML body (e.g., MD5) and check a "seen_content" DB before saving it.
Crawler Traps & Robustness
The web is messy. A "crawler trap" is a dynamically generated infinite loop of URLs (e.g., /page1 -> /page2 -> /page1). The crawler defeats traps by keeping a depth counter on each URL. If a link is 10 hops deep from the seed, we discard it. We also enforce strict timeouts (e.g., 10 seconds max) on all HTTP requests to prevent workers from hanging on dead servers.
Bottlenecks & Solutions
DNS Resolution is a hidden massive bottleneck. If you fetch 1,000 pages a second, doing 1,000 synchronous DNS lookups will stall the entire fleet. The solution is to build a custom, asynchronous DNS Resolver cache that updates on a cron schedule, completely bypassing the OS's slow blocking DNS resolution.