Design a Web Crawler

Prompt

Crawl the web: start from seed URLs, fetch pages, extract links, store the content, and repeat — at the scale of billions of pages, while being polite to each site and keeping content reasonably fresh.

1. Requirements

Functional: fetch pages from seeds, extract and follow links, store content for indexing. Non-functional: scalable (billions of pages); polite (respect robots.txt, cap requests per domain); robust (avoid traps, handle failures); fresh (re-crawl changing pages); dedup (don't crawl the same URL/content twice).

2. Architecture

seeds ─▶ URL frontier ─▶ fetchers ─▶ parser ─▶ extract links
          (priority +      (HTTP)      │           │
           per-domain                   ▼           ▼
           politeness)            content store   dedup filter
              ▲                    (S3 / blob)    (Bloom filter / seen-set)
              └──────────────── new, unseen URLs ◀──┘

The URL frontier is the heart of the design — a queue of URLs to crawl that enforces two competing goals at once: priority (crawl important/fresh pages sooner) and politeness (don't hammer one server).

3. The decisions that matter

• Politeness: never blast a single domain. Maintain per-domain queues with a minimum delay between requests to the same host, and obey robots.txt (cached per domain). A common design: a front set of queues for priority, a back set keyed by domain for politeness, with a mapping between them.
• Dedup at scale: a billions-URL "have I seen this?" set won't fit in memory as a plain hash set. Use a Bloom filter (tiny, fast, false positives only — occasionally skip a new URL, never re-crawl). Also dedup content (hash the page) to catch the same page under different URLs.
• Crawler traps & cycles: infinite calendars, session-id URLs, deep dynamic links. Cap URL length and crawl depth per domain, normalize URLs (strip fragments/params), and budget pages per domain.
• Freshness / re-crawl: pages change at different rates. Re-crawl high-change pages (news) often, static pages rarely — an adaptive policy based on observed change frequency.
• Distribution: partition the frontier by domain hash so each crawler node owns a set of domains (which also makes politeness local). Cache DNS aggressively — DNS lookups are a surprising bottleneck.

Design drills