Design a Web Crawler: Mapping the Internet Systematically

Googlebot: Crawling 130 Trillion Pages

Google's index contains over 130 trillion web pages, and Googlebot must continuously re-crawl them to keep search results fresh. The crawler discovers new pages, detects changes on existing pages, and removes dead links - all while being polite enough not to overwhelm any single website. This distributed crawling system is one of the most complex pipeline architectures ever built.

Scale Requirements

Crawl Scale:

  Target: 10 billion pages in 30 days
  Pages/second: 10B / (30 * 86,400) = ~3,858/sec
  Round up: 4,000 pages/second

  Average page size: 500 KB (HTML + metadata)
  Bandwidth: 4,000 * 500 KB = 2 GB/sec = 16 Gbps
  Storage: 10B * 500 KB = 5 PB

  DNS lookups: 4,000/sec (must be cached!)
  HTTP connections: 4,000 concurrent (connection pooling)
  robots.txt checks: cached per domain (refresh daily)

Crawler Architecture

Web Crawler Pipeline:

  [Seed URLs]
       |
  [URL Frontier]  (priority queue + politeness scheduler)
       |
  Dequeue batch of URLs to crawl
       |
  [DNS Resolver]  (local cache: 90%+ hit rate)
       |
  [robots.txt Checker]  (cached per domain)
       |
  [HTTP Fetcher]  (connection pooling, timeouts)
       |
  [HTML Parser]  -> Extract page content
       |           -> Extract all outbound links
       |
  [Content Dedup]  (Simhash: is this page near-duplicate?)
       |            Already seen? -> SKIP
       |
  [Content Store]  -> Save to object storage
       |
  [Link Extractor] -> Normalize URLs
       |              (remove tracking params, canonicalize)
       |
  [URL Dedup]  (Bloom filter: have we seen this URL?)
       |        Already seen? -> SKIP
       |
  [URL Frontier]  <- Add new URLs with priority score
                     Loop continues...

Politeness and the URL Frontier

URL Frontier Design:

  Challenge: crawl 4,000 pages/sec WITHOUT
  hammering any single domain

  Solution: Two-level queue

  Level 1: Priority Queue (what to crawl next)
  +-----------+
  | Priority 1| -> CNN.com, NYTimes.com (news, changes often)
  | Priority 2| -> Wikipedia pages (important, stable)
  | Priority 3| -> Random blogs (lower priority)
  +-----------+

  Level 2: Per-Domain Queues (politeness)
  +-------------+
  | cnn.com     | -> [url1, url2, url3]  min 2s between requests
  | wiki.org    | -> [url4, url5]        min 5s between requests
  | blog.dev    | -> [url6]              min 10s between requests
  +-------------+

  Scheduler picks from highest-priority domain
  whose last-crawl was > delay threshold ago

  Result: high throughput globally,
  polite to each individual domain

Deduplication at Scale

Two Layers of Deduplication:

  1. URL Dedup (Bloom Filter):
     10 billion URLs * 10 bits each = ~12 GB in memory
     False positive rate: 1% (acceptable - we skip a few URLs)
     False negative rate: 0% (never miss a new URL)
     O(1) lookup, O(1) insert

  2. Content Dedup (Simhash):
     Same article on 50 news sites = 50 near-identical pages
     Simhash: 64-bit fingerprint of page content
     If Hamming distance < 3 bits: pages are near-duplicate
     Only index the original, skip duplicates

     O(1) per page, saves 30%+ of processing

Interview Tip

When designing a web crawler, emphasize three things: (1) the URL frontier with priority scheduling AND per-domain politeness queues, (2) Bloom filters for URL deduplication (12 GB for 10B URLs), (3) Simhash for content deduplication. Mention robots.txt compliance, DNS caching (90%+ hit rate), and HTTP connection pooling. The interviewer wants to see that you understand the politeness constraint - a crawler that ignores it will get IP-banned.

<

/blockquote>

Key Takeaway

Web crawlers are distributed systems built around a URL frontier (priority queue), polite per-domain rate limiting, and aggressive deduplication via Bloom filters and content hashing. DNS caching and HTTP connection pooling are critical for throughput. robots.txt compliance is both legal and ethical.