Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 65 ยท Case Studies: Classic Designs

Design a Web Crawler

Design a web crawler: URL frontier, politeness and robots.txt, DNS and fetch workers, duplicate detection with hashes and Bloom filters, and spider traps, with Python.

A web crawler (spider) downloads pages by following links, starting from a list of seed URLs. Search engines use crawlers to build their index; other uses include archiving, price monitoring and training data collection. The core loop is simple: take a URL, fetch it, extract links, add new ones. The design effort goes into doing this for billions of pages without hammering any single site or crawling the same page twice.

Requirements

  • Crawl 1 billion pages per month, keeping content fresh (important pages revisited often).
  • Be polite: obey robots.txt and never overload a site.
  • Robust against broken HTML, slow servers, infinite link loops and malicious pages.
  • Extensible: later add image or PDF handling.

Estimates: 1 billion pages per month is about 400 pages per second. At an average of 100 KB per page that is 40 MB/s of download and about 100 TB of raw content per month. Fetching is network-bound, so you need many parallel workers and mostly asynchronous I/O.

Architecture

flowchart LR
    SEED["Seed URLs"] --> FR["URL frontier"]
    FR --> FW["Fetcher workers"]
    FW --> DNS["DNS cache"]
    FW --> ROB["robots.txt cache"]
    FW --> ST[("Content store")]
    ST --> PA["Parser: extract links and text"]
    PA --> DD{"Seen before?"}
    DD -- "no" --> FR
    DD -- "yes" --> X["Discard"]
    PA --> DC["Content duplicate check"]

The frontier decides what to fetch next; the duplicate checks keep the loop from running forever.

The URL frontier

The frontier is more than a queue. It must handle two things at once:

  • Priority: important pages (high link authority, news sites, recently changed) come first.
  • Politeness: only one request at a time (or one every few seconds) to any single host.

A standard design: front queues order URLs by priority, and back queues hold one host each. A worker takes a host whose "next allowed time" has passed, fetches one URL, and puts the host back with a new delay.

Python A polite frontier with per-host delay

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

While a.com waits out its two-second delay, the crawler moves on to b.com and c.com, so it stays busy without being rude. The pages of a.com are always at least two seconds apart.

Duplicate URLs and duplicate content

Billions of links point to pages already seen, so two checks are essential:

  • URL seen test: normalize the URL (lowercase host, remove fragments like #top, resolve ../, sort query parameters, drop tracking parameters) and test whether it was already crawled. A hash set is exact but huge; a Bloom filter uses a few bits per URL with a small false positive rate (you occasionally skip a new page, never refetch an old one).
  • Content seen test: different URLs often serve the same page. Store a hash (or a SimHash for near duplicates) of the content and skip pages whose hash exists.
Python URL normalization and a Bloom filter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first two inputs normalize to the same URL, so they count as one page. The Bloom filter fits 3,000 URLs in 8 KB with a handful of false positives; real crawlers size it for billions with a target rate such as 1%.

Fetching safely

  • robots.txt: fetch it once per host, cache it (for example for a day), and obey Disallow and Crawl-delay.
  • DNS: lookups can dominate latency; run a local caching resolver.
  • Timeouts and limits: cap response size (skip files over a few MB), connect and read timeouts, and a maximum redirect count.
  • Spider traps: a calendar with infinite "next month" links, or session IDs in URLs, create endless unique URLs. Defend with a maximum depth, a limit of URLs per host, and detection of repeating path patterns.
  • Freshness: re-crawl pages by how often they change (record each page's last change, then crawl hourly, daily or monthly accordingly) using If-Modified-Since to save bandwidth.
  • JavaScript pages: many sites render in the browser; a headless browser is slow, so reserve it for sites that need it.
  • Distribute: partition the frontier by host hash, so each crawler node owns a set of hosts (which also makes politeness local), and replicate the seen-URL structure or shard it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the frontier keep a separate queue per host?

    Per-host queues with a next-allowed time prevent overloading a single server.
  2. 2. What is the trade-off of a Bloom filter for the 'URL seen' check?

    A false positive skips a new page occasionally; there are no false negatives, so nothing is refetched.
  3. 3. Which is a spider trap?

    Endless generated URLs never end; use depth and per-host limits.
  4. 4. Two URLs differ only in utm_source. What step makes them one entry?

    Normalization removes tracking parameters, sorts query strings and lowercases hosts.

Summary

  • A crawler is a loop: frontier, fetch, parse, filter, back to the frontier.
  • The frontier balances priority and per-host politeness.
  • Normalize URLs, test seen URLs with a hash set or Bloom filter, and detect duplicate content by hash.
  • Respect robots.txt, cache DNS, set limits, avoid spider traps and schedule re-crawls by change rate.
  • Partition by host to distribute work and keep politeness local.

Next: Design a File Storage Service