Requirements and Scale
Functional: start from a seed set of URLs, fetch pages, extract links, add new URLs to the crawl queue, store page content. Non-functional: scalable (billions of pages), polite (respect robots.txt and crawl-delay), robust (handles bad HTML, DNS failures, redirects), extensible (pluggable storage and processing pipelines).
Scale: 1B pages to crawl in 4 weeks = ~4,000 pages/sec. Average page = 100 KB → 100 TB of raw HTML. After compression: ~30 TB.
High-Level Architecture
Seed URLs → URL Frontier (priority queue of URLs to fetch) → Fetcher Workers (download HTML) → Link Extractor (parse HTML, extract links) → URL Filter (dedup, robots.txt check) → back to URL Frontier. Fetched content → Document Storage (S3) → Content Processor (indexer, classifier).
The URL Frontier is the heart of the crawler. It must: (1) Prioritize important URLs (PageRank, freshness), (2) Ensure politeness (max 1 request/sec per domain), (3) Hold billions of URLs (too large for RAM — must use disk).
graph LR SeedURLs --> Frontier["URL Frontier (Priority Queue)"] Frontier --> Fetchers["Fetcher Workers"] Fetchers --> HTMLParser["HTML Parser + Link Extractor"] HTMLParser --> URLFilter["URL Filter (Bloom Filter + robots.txt)"] URLFilter --> Frontier Fetchers --> DocStore["Document Store (S3)"]
URL Deduplication with Bloom Filters
A 1B-page crawl produces billions of extracted URLs. Many are duplicates. Storing all visited URLs in a hash set would require hundreds of GB of RAM. Instead, use a Bloom filter: a probabilistic data structure that answers "have we seen this URL?" with zero false negatives (never misses a visited URL) and small false positive rate (occasionally reports unvisited URLs as visited, causing rare missed crawls — acceptable).
A Bloom filter for 1B URLs with 1% false positive rate needs only ~1.2 GB of memory. Implementation: k hash functions, a bit array of size m. To add URL: set bits at positions h1(url), h2(url), ..., hk(url). To check: if all bits are set, URL is "seen" (probably); if any bit is 0, URL is definitely new.
Politeness and Robots.txt
Web crawlers must be polite: (1) Respect robots.txt — before crawling any domain, fetch /robots.txt and cache it. Honor Disallow directives and Crawl-delay. (2) Throttle per domain — maintain one queue per domain. Fetcher workers take from domain queues with a minimum delay between consecutive requests to the same domain (e.g., 1 request/10 sec). (3) Distribute fetches across time — don't hammer a small site all at once.
Implementation: domain-partitioned URL frontier. Each domain gets its own sub-queue. A scheduler picks the next URL from the least-recently-crawled eligible domain queue.
Content Deduplication
Many pages have identical or near-identical content (mirror sites, content scrapers). Storing duplicates wastes storage and dilutes search index quality. Exact dedup: hash the page content (MD5 or SHA-256); if hash already seen, discard. Near-dedup: SimHash — compute a fingerprint where similar documents have similar fingerprints (Hamming distance < threshold). Simhash of 64 bits; index all seen fingerprints in a hash table; for each new page, compute simhash and look up near neighbors.
Distributed Worker Coordination
Partition the URL space across worker machines. Each worker "owns" a range of URL hashes (consistent hashing). Worker fetches only URLs assigned to it. When a worker extracts a new link, it routes the link to the correct worker's frontier queue (via a message queue like Kafka). Master node monitors worker health, reassigns partitions if a worker dies. Crawl state (which URLs have been fetched) is persisted to a distributed DB (HBase or Cassandra) so that the crawl can resume after failures without re-crawling everything.