Back to System design
Design a Web Crawler
hardA crawler downloads a page, finds the links in it, and repeats. That part is a weekend project.
Scale1B pages, weekly refresh → ~1700 pages/s sustained
StorageCompressed HTML ~100 KB × 1B = 100 TB; index much larger
Key Concepts
1
What makes it a systems problem is being polite to the websites you visit, avoiding pages you have already
seen, and not getting stuck in traps.
2
Politeness sets your speed, not your hardware. You cannot hit one website as fast as your machines
allow. Small sites would fall over and large ones would block you. One request every second or two per
website is normal.
Politeness sets your speed, not your hardware.
3
That changes the whole design. One queue of URLs is useless, because consecutive URLs are usually from the
same site. You need a separate queue per website, drained at that site's own pace.
4
It also means speed comes from visiting many sites at once, not from hammering one. To fetch 1,000
pages a second at one request per 1.5 seconds per site, you need about 1,500 sites in progress
simultaneously.
many sites at once
5
At that rate, a billion pages takes about twelve days.
6
Remembering what you have seen is a memory problem. A billion URLs at 70 characters each is 70 GB
before any overhead, and you check this list for every link you find — tens of billions of times.
Remembering what you have seen is a memory problem.
7
A Bloom filter solves it. It answers "have I seen this?" using about 1.2 GB for a billion URLs, which fits
in memory. The trade is that it occasionally says yes when the answer is no, so roughly 1% of new pages
are skipped. For broad crawling that is fine. When you must not miss anything, use it as a fast first
check with an exact list behind it.
8
The same article appears at many addresses. Tracking parameters, session IDs, mobile versions. Exact
matching on the page content catches only identical copies.
The same article appears at many addresses.
9
The tool for near-identical pages is a fingerprint that changes only slightly when the text changes
slightly, so two pages that differ by an advert can be recognised as the same story.
10
Traps, deliberate and accidental. A calendar page that links to next month, forever. A site that puts a
new session ID in every URL, so every visit looks like new pages. Deliberately generated mazes designed to
waste crawlers' time.
Traps, deliberate and accidental.
11
The defences are limits rather than cleverness: a cap on pages per site, a cap on how deep you go, removal
of known junk parameters, and stopping when a site keeps returning pages that look the same.
12
Re-visiting should follow how often pages change. A news homepage changes hourly; a 2009 archive page
has not changed in years. Track how often each page actually changes and schedule accordingly, or you
spend your budget re-downloading things that are identical.
Re-visiting should follow how often pages change.
13
What the interviewer is probing.
What the interviewer is probing.
14
1. "Design a crawler." Probing: whether politeness comes before throughput. Stalls: "A thread pool
pulling URLs off a queue." Moves up: per-site queues with a rate limit, and that speed comes from many
sites at once.
1. "Design a crawler."
15
2. "How do you know you have seen a URL?" Probing: the memory arithmetic. Stalls: "A hash set."
Which is 70 GB and growing. Moves up: a Bloom filter at about 1.2 GB, what its false positives cost, and
an exact list behind it when completeness matters.
2. "How do you know you have seen a URL?"
16
3. "The same article is at twenty addresses." Probing: near-duplicate detection. Stalls: "Hash the
content." That only catches identical copies. Moves up: similarity fingerprints, plus cleaning the URL
first.
3. "The same article is at twenty addresses."
17
4. "The crawler has been on one site for six hours." Probing: trap awareness. Stalls: "It has a lot
of pages." Moves up: an infinite calendar or session-ID trap; caps per site and per depth, and stopping
when the content stops varying.
4. "The crawler has been on one site for six hours."
18
5. "How often do you re-crawl?" Probing: spending the budget well. Stalls: "Every week." *Moves
up:* measure how often each page really changes and schedule from that.
5. "How often do you re-crawl?"
High-level design
Seed → frontier (partitioned by domain, prioritized).
Fetcher pool → DNS cache → robots.txt cache → HTTP fetch → store HTML.
Parser → outlink extraction → normalization → dedup check → enqueue.
Parser → content extraction → indexing pipeline (separate system).
Recrawl scheduler → re-enqueue pages by change-rate model.
Optional headless fallback for JS-rendered pages.
Components
- Frontier (Kafka with domain-partitioned queues, or sharded priority queue in RocksDB).
- Fetcher pool (async HTTP).
- DNS resolver + cache.
- Robots.txt cache (TTL per domain).
- Parser (Beautiful Soup / lxml / native).
- Canonical URL builder.
- Dedup: Bloom filter + SimHash for near-dup.
- Storage: HTML compressed in object store, metadata in KV.
- Link graph store (for PageRank, recrawl decisions).
- Recrawl scheduler.
- Headless browser pool (Puppeteer/Playwright) for SPA fallback.
Crawl budget, worked
Target pages 1,000,000,000
Politeness, per host 1 request / 1.5 s
----------------------------------------------------------------
Throughput from ONE host 0.67 pages/s
To reach 1,000 pages/s
Hosts crawled concurrently 1000 / 0.67 = ~1,500 hosts Time at 1,000 pages/s
1B / 1,000 / 86,400 = 11.6 days
At 5,000 pages/s (7,500 concurrent hosts) = 2.3 days Bandwidth
Average page (HTML only, compressed) ~50 KB
1,000 pages/s x 50 KB = 50 MB/s
= 400 Mbps
5,000 pages/s = 2 Gbps Storage
Raw HTML, compressed 1B x 50 KB = 50 TB
Extracted text only 1B x 5 KB = 5 TB
URL metadata (status, ts, hash, etc.)
1B x 100 B = 100 GBThe point of this table in an interview: throughput is bounded by how many DISTINCT hosts you are polite to at once, so the frontier design -- not the fetcher -- is the scaling lever.
Dedup memory, compared
Exact set of 1 billion URLs
Average URL length ~70 bytes
Raw 1B x 70 B = 70 GB
Hash set overhead (pointers, buckets) = 2-3x that
In practice = 150-200 GB
-> a sharded store, one network hop per check. Bloom filter, 1 billion entries
1% false positive ~9.6 bits/entry = 1.2 GB
0.1% false positive ~14.4 bits/entry = 1.8 GB
0.01% false positive ~19.2 bits/entry = 2.4 GB
-> fits in memory; check costs nanoseconds, no network. What a false positive costs here
The URL is judged "seen" and never crawled. At 1% over a billion
URLs that is ~10 million pages silently skipped. Acceptable for
broad discovery; not acceptable for a site-complete crawl. Hybrid (the usual production answer)
Bloom filter in front: a negative is definitive, so most checks
are answered locally. Only a positive goes to the exact store to
confirm. Network traffic drops by the filter's hit rate.Traps and defences
Infinite calendar
/events?date=2031-04-17 -> links to the next month, forever.
Defence: cap URLs per host; normalise or strip date parameters;
stop descending when content similarity across a host is high. Session ids in URLs
/product?sid=abc123 -- every visit mints a new URL.
Defence: strip known session parameters before dedup; treat URLs
differing only in those parameters as one. Faceted navigation explosion
/search?color=red&size=l&sort=price... every combination.
Defence: parameter allow-list per host, depth cap, and respect
rel=canonical. Deliberate maze / tarpit
Generated pages designed to consume crawlers.
Defence: per-host budget in pages AND in seconds; drop hosts whose
yield (new unique content per fetch) falls below a threshold. Slow-loris responses
Server dribbles bytes to hold your connection open.
Defence: aggressive read timeouts and a cap on concurrent
connections per host.