Design a Web Crawler

Requirements

A web crawler starts from a set of seed URLs, downloads each page, extracts the links it contains, and repeats the process for the newly discovered links. Its output feeds a search engine: a reverse (inverted) index of words to pages, plus a stored title and snippet for each page.

Functional

• Crawl a list of seed URLs and every link discovered from them.
• Store page content and hand it to downstream indexing (inverted index, titles and snippets).
• Re-crawl pages periodically so the index stays fresh; popular or fast-changing sites more often.
• Respect robots.txt and per-site crawl limits.
• Out of scope: ranking (PageRank), personalization, search analytics, JavaScript rendering (mention it as an extension).

Non-functional

• Scalable: billions of pages per month across thousands of workers.
• Polite: never overload a single host; one site should see a trickle of requests, not a flood.
• Robust: survive malformed HTML, slow servers, infinite URL spaces (crawler traps) and link cycles.
• Efficient: do not fetch or store the same URL or the same content twice.
• Fault tolerant: a worker crash must not lose the frontier or duplicate large amounts of work.
• Extensible: adding a new content type (PDF, images) should be a plug-in, not a rewrite.

Capacity Estimates

Following the system-design-primer's assumptions: 1 billion distinct links, each refreshed about once a week, so roughly 4 billion fetches per month, with an average stored page of 500 KB.

Two conclusions: storage is the dominant cost (compress pages and keep only the latest few versions), and throughput is limited less by CPU than by network latency, so each worker must keep hundreds of fetches in flight concurrently.

API Design

A crawler has no public user API; its interfaces are internal. A small control plane and a worker contract are enough.

POST /internal/v1/seeds
  Body: { "urls": ["https://example.com", ...], "priority": 0.9 }
  202:  accepted into the frontier

GET  /internal/v1/frontier/lease?workerId=w-17&max=100
  200:  { "leaseId": "...", "urls": [ { "url": "...", "host": "...", "notBefore": "..." } ] }

POST /internal/v1/frontier/complete
  Body: { "leaseId": "...", "results": [ { "url": "...", "status": 200,
          "contentHash": "...", "simhash": "...", "outLinks": 42 } ] }

GET  /internal/v1/hosts/{host}/policy
  200:  { "crawlDelayMs": 1000, "disallow": ["/private/"], "fetchedAt": "..." }

Leases with timeouts make work assignment fault tolerant: if a worker dies, its leased URLs return to the frontier when the lease expires.

Data Model

-- conceptual schema for the crawled-links table
crawled_links (
  url_hash        BINARY(16) PRIMARY KEY,
  url             TEXT,
  host            VARCHAR(255),
  last_crawled_at TIMESTAMP,
  next_crawl_at   TIMESTAMP,
  content_hash    BINARY(16),   -- exact duplicate detection
  simhash         BIGINT,       -- near-duplicate detection
  http_status     SMALLINT,
  change_count    INT           -- used to estimate refresh rate
)

High-Level Design

flowchart LR
  Seeds[Seed URLs] --> F[URL Frontier]
  F --> W[Fetcher Workers]
  W --> DNS[DNS Cache]
  W --> RB[Robots Cache]
  W --> Web((Internet))
  W --> PS[(Page Store)]
  W --> P[Parser and Link Extractor]
  P --> CD{Content Seen?}
  CD -->|new| Q[[Indexing Queues]]
  Q --> RI[Reverse Index Service]
  Q --> DS[Document Service]
  P --> N[URL Normalizer and Filter]
  N --> US{URL Seen?}
  US -->|new| F
  W --> CL[(Crawled Links DB)]
  CL --> SCH[Recrawl Scheduler]
  SCH --> F

Crawl loop:

1. A fetcher leases a batch of URLs from the frontier. The frontier only releases URLs whose host is allowed to be hit now.
2. The fetcher resolves DNS (from its cache), checks the host's robots.txt rules, and downloads the page with timeouts and a size cap.
3. The raw page goes to the page store; the parser extracts text and links.
4. A content fingerprint is compared with what has been seen. Duplicate content is not re-indexed.
5. New content is published to the Reverse Index and Document queues, which build the inverted index and the static title/snippet, as in the primer's design.
6. Extracted links are normalized, filtered (blocked domains, traps, file types), checked against the URL-seen set, and new ones enter the frontier.
7. The crawled-links record is updated with the timestamp and signature; the recrawl scheduler later re-enqueues it.

The search side (query API, inverted index, a cache for skewed popular queries) consumes this output and scales independently.

Deep Dives

The URL frontier: priority plus politeness

A single FIFO queue fails in two ways: important pages wait behind junk, and consecutive URLs from the same host hammer that host. A Mercator-style frontier solves both with two layers:

• Front queues (priority): a prioritizer assigns each URL a score (site popularity, PageRank estimate, change rate, depth) and places it into one of N priority queues. A selector pulls from higher queues more often.
• Back queues (politeness): each back queue holds URLs for exactly one host. A heap keyed by "earliest time this host may be contacted again" decides which back queue a worker serves next. After each fetch, the host's next-allowed time is pushed forward by its crawl delay (from robots.txt, or a multiple of the last response time).

The primer suggests a simpler version: keep links_to_crawl as a Redis sorted set ranked by priority and pop the max. That is a fine starting point; layer per-host queues on top once politeness comes up.

Partition the frontier by host (consistent hashing on the hostname) so a single node owns all URLs for a host. Politeness then becomes a local decision with no cross-node coordination.

Deduplication: URLs and content

URL-level. Before enqueueing, normalize the URL: lowercase scheme and host, remove default ports and fragments, sort query parameters, strip known tracking parameters (utm_*, session IDs), and resolve relative paths. Then check a URL-seen set. At a billion URLs, a sharded Bloom filter (~1.2 GB at 1% false positives) answers "definitely new" cheaply; a false positive only means skipping a URL we have not seen, which is acceptable. For batch cleanup the primer shows the MapReduce approach: emit (url, 1), sum in the reducer, keep unique entries.

Content-level. Many URLs serve the same document (mirrors, http vs https, print views). Store an exact hash (MD5/SHA-1 of normalized text) to catch identical copies, and a SimHash or MinHash signature to catch near-duplicates such as the same article with a different ad block. Pages whose SimHash differs by only a few bits are treated as duplicates. Jaccard similarity over shingles and cosine similarity are the textbook comparisons. When a near-duplicate is found, lower the URL's priority instead of re-indexing it; this also breaks cycles in the link graph.

Politeness, robots.txt and crawler traps

• Fetch robots.txt once per host, cache it (for example 24 hours), and obey Disallow and Crawl-delay. The format is standardized in RFC 9309.
• Identify the crawler with a clear User-Agent and a contact URL.
• Back off on 429 and 503, honour Retry-After, and slow down a host whose latency rises.
• Traps: calendars with infinite "next month" links, session IDs in every URL, and auto-generated path loops. Defend with a maximum URL length, maximum path depth, a per-host page budget, and pattern detection for repeating path segments.

Freshness and recrawl scheduling

Each crawled_links row has a last_crawled_at and a next_crawl_at. The default refresh interval is about a week (as in the primer), but a fixed interval wastes effort on static pages and misses changes on news sites. Instead:

• Track whether the content hash changed on each visit and estimate each page's change rate.
• Schedule the next crawl proportional to the estimated change interval, clamped between, say, 1 hour and 30 days.
• Boost popular hosts and pages that rank highly in search results.
• Use conditional requests (If-Modified-Since, ETag) so unchanged pages return 304 Not Modified and cost almost no bandwidth.
• Honour sitemaps and their lastmod hints.

Fetcher performance

• DNS is a hidden bottleneck. Standard resolvers are slow and often synchronous; run a local caching resolver per worker pool and prefetch DNS for hosts about to be served.
• Asynchronous I/O: use non-blocking HTTP clients so each worker keeps hundreds of connections open; reuse connections per host (keep-alive pooling).
• Hard limits: connect and read timeouts, a maximum body size (for example 10 MB), and content-type filtering before downloading the body.

Scaling & Reliability

• Horizontal scale: fetchers, parsers and indexers are stateless consumers. Add workers to raise throughput; partition hosts across frontier nodes by consistent hashing so rebalancing moves only a fraction of hosts.
• Durable frontier: back the frontier with a replicated log (Kafka) or a replicated store; in-memory queues are periodically checkpointed. Leases with expiry guarantee at-least-once processing; dedupe makes repeats harmless.
• Decoupling with queues: the primer places queues between the crawler and the Reverse Index and Document services. A slow indexer causes back pressure on the queue, not failed fetches.
• Storage: compress pages (HTML compresses 5-10×), keep only recent versions, and shard the crawled-links table and page store by URL hash. The reverse index and document stores need heavy sharding and federation too.
• Monitoring: pages/s, error rate per host, frontier size, duplicate ratio, and the age distribution of the index (freshness).

Trade-offs

Interview Tips

• Restate the crawl loop in one sentence first: lease URL, fetch, store, parse, dedupe, enqueue new links.
• Do the bandwidth math: ~1,600 pages/s at 500 KB is several Gbps, which justifies a distributed, I/O-bound fleet.
• Bring up politeness unprompted and explain why it leads to per-host queues and host-partitioned frontiers.
• Separate URL dedupe (normalization + Bloom filter) from content dedupe (hash + SimHash).
• Mention traps and cycles; the primer's "reduce priority when a similar signature exists" is a neat, simple answer.
• Discuss freshness as an adaptive scheduling problem, not a cron job.
• Close with failure handling: leases, durable queues, and idempotent processing.

References

• System Design Primer: Design a web crawler
• System Design Primer: Message queues and back pressure
• RFC 9309: Robots Exclusion Protocol
• Bloom filter (Wikipedia)
• Karan Pratap Singh: System Design
• Awesome Scalability