Module 12 · Lesson 04
Design a web crawler
A polite, deduplicating pipeline that has to decide what to fetch, how often, and when to stop.
What you will be able to do
- Design a URL frontier with per-host politeness
- Deduplicate URLs and near-duplicate content
- Explain robots.txt and crawl-delay handling
- Size the fetch fleet from target throughput
Requirements and estimates
- Functional: fetch pages from a seed set, extract links, store content and metadata, recrawl for freshness.
- Non-functional: 1B pages/month, no more than one request per second per host, resume after failure.
- Scale: 1B pages ÷ 2.6M seconds ≈ 400 pages/s sustained.
400 pages/s at ~100 KB average = ~40 MB/s ingress = ~3.5 TB/day of raw HTML, before dedup seeds: 1B pages over ~50M hosts = 20 pages/host polite rate 1/s/host => fetching is host-bound, not page-bound fleet: 400 concurrent fetches at ~1 s each
That last line is the useful estimate: with a one-request-per-second-per-host rule, throughput is a function of how many hosts are in flight. Four hundred concurrent connections at one second each gives the target rate.
Pipeline
Frontier
Priority queue of URLs, partitioned by host. Each host has a next-allowed-fetch timestamp.
Fetcher
Pulls only hosts whose time has come, respects robots.txt and timeouts, follows redirects with a cap.
Parser and extractor
Extracts links, normalises them, discards unsupported schemes and file types.
Deduplicator
Checks URL fingerprints, then content hashes, before enqueueing or storing.
Storage
Raw HTML in object storage, metadata in a wide-column table keyed by URL hash, links in an adjacency store.
Normalisation and duplicates
- Lowercase scheme and host, strip default ports, sort query parameters, drop fragments.
- Remove tracking parameters only against a known list; guessing changes meaning.
- Resolve relative links against the base URL before hashing.
- Near-duplicate content: hash normalised text, or use a shingle-based similarity sketch for paraphrased pages.
Crawler traps
Calendars, infinite pagination and session-id URLs generate unbounded URLs. Cap path depth, cap URLs per host, and detect patterns where every page links to many similar URLs.
Politeness and freshness
Robots.txt is parsed per host and cached with a TTL; crawl-delay overrides your default. Per-host state includes last fetch time, error counts and backoff — a host returning 500s should be retried later, not hammered. Freshness is a scheduling policy: news sites recrawl hourly, static docs monthly, driven by change frequency observed over time.
What separates a good answer
"The frontier is host-partitioned with a per-host next-fetch time, so throughput is set by hosts in flight, not workers. URL normalisation and a content hash prevent duplicate work, and robots plus backoff handle politeness."
Worth remembering
- Normalise URLs before deduplication or the same page is fetched many times.
- Politeness is per host: a single global rate limit either overloads a small site or starves a big one.
- Separate the frontier from page storage; they have different write rates and retention.
- A crawler needs a stop condition — depth, budget, or freshness — or it never finishes.
Checkpoint
Answer all 3 questions to finish the lesson.
1. Why is the frontier partitioned by host?
Each host has its own rate limit and backoff state. Partitioning makes those independent and keeps throughput predictable.
2. What is the purpose of URL normalisation before deduplication?
Case, ports, parameter order and fragments create many spellings of one page. Normalising before hashing prevents duplicate fetches.
3. With one request per second per host and 400 concurrent fetches, what is the expected page rate?
Each in-flight fetch targets a distinct host, so 400 concurrent fetches at one second each yields about 400 pages per second.