43. Web Crawler

Business context. Feeds a search index (or an LLM training corpus). The outcomes are index freshness and coverage for important pages within a compute and bandwidth budget, while being a good citizen: politeness, robots.txt, not taking down small sites.

Requirements. Crawl billions of pages; recrawl important pages often (news: minutes; long tail: months); respect robots.txt and per-host rate limits; dedupe content; handle traps. 5B pages per month → ~2,000 pages/s, ~100 KB each → ~200 MB/s (1.6 Gbps) of fetching.

Design.

Seed URLs ─▶ URL Frontier
   ├─ Prioritizer: score = importance (PageRank-ish, traffic) × change rate × staleness
   └─ Politeness: per-host queues; each host is mapped to one worker; min delay between fetches per host
─▶ Fetchers (async I/O, DNS cache, robots.txt cache) ─▶ raw content to object storage
─▶ Parser/extractor: links, text, metadata; content fingerprint (SimHash) for near-duplicates
─▶ URL filter: normalization, "seen?" check (Bloom filter + persistent URL DB), trap detection
─▶ new URLs back into the frontier; documents ─▶ indexing pipeline

Deep dives.

• The frontier is the heart. Two levels of queues: front queues by priority, back queues by host (the Mercator design). This gives both prioritization and politeness.
• Dedupe: exact (hash of content) and near-duplicate (SimHash/MinHash). Mirror sites and URL-parameter variants are common.
• Traps: infinite calendars, session IDs in URLs. Limit depth per host and URL length, and detect repeating path patterns.
• Recrawl scheduling: estimate each page's change rate from its history (Poisson model) and spend the crawl budget where expected freshness gain is highest.
• Scale-out: partition the frontier by host hash so each host is owned by exactly one partition, which makes politeness a local decision.

Strategic lens. Crawl budget is a cost and quality trade-off. Measure freshness-weighted coverage of pages users actually search for, not raw pages crawled. And state the legal and ethical constraints (robots.txt, terms of service, copyright).

🏗️ Flow: the life of one URL in the frontier.

 discovered: https://Example.com/a/../b?utm_source=x#top
   → normalize: https://example.com/b      (lowercase host, resolve dots, strip fragment/tracking params)
   → seen? Bloom filter (maybe) → URL DB check (definitive) → new
   → priority score → front queue (priority 3)
   → back queue for host example.com (one host ↔ one queue ↔ one fetcher thread at a time)
   → politeness: last fetch 2.1 s ago, crawl-delay 2 s → OK
   → robots.txt (cached 24 h) allows /b → fetch (timeout 10 s, max 10 MB, follow ≤ 5 redirects)
   → content hash / SimHash → near-duplicate of known page? → store reference only
   → parse links (+ render JS in a separate, expensive queue if needed) → back to start
   → schedule recrawl: next = now + f(estimated change rate, importance)

🌍 How it's built in production.

• Mercator (1999): the two-tier frontier design (priority front queues, per-host back queues) that's still the textbook answer.
• Google Caffeine (2010): moved from batch index rebuilds to incremental indexing, so pages become searchable soon after crawling. Freshness became an architectural property.
• Googlebot renders JavaScript in a separate, later rendering stage, because rendering costs far more than fetching HTML. Rendering is a prioritized, separately budgeted resource.
• Common Crawl: a public monthly crawl of billions of pages, widely used for research and LLM pre-training. It's a reference for crawler output formats (WARC).

⚠️ Corner cases.

• robots.txt failure semantics (RFC 9309): if robots.txt returns 4xx, crawlers may treat it as "no restrictions"; on 5xx or unreachable, they should assume full disallow for a period. Getting this backwards either hammers a struggling site or crawls content that was meant to be blocked.
• Soft 404s: a 200 status with "page not found" content. Detect them by content similarity to known error pages.
• Canonicalization: rel=canonical, www vs bare domain, http vs https, and trailing slashes. Index the canonical version to avoid duplicate pages in the index.
• Spider traps: calendars generating infinite dates, faceted search combinations, and session IDs. Cap URLs per host and path depth, and detect repeating patterns.
• DNS as the bottleneck: billions of lookups. Run a local caching resolver per fetcher pool, and respect TTLs.
• Politeness vs priority: a news site's important new pages wait behind its own per-host delay. Negotiate a higher crawl rate (sitemaps, server feedback), and use adaptive delays based on response times.