Handbooks / System Design Case Studies / Chapter 8

Design a Web Crawler

13 pages · ~18 min✓ Reviewed

Builds on Design a News Feed like Instagram. Next up: Design Cloud File Storage like Dropbox.

System Design Case StudiesPage 1

Problem Statement, Scope and Requirements

1. Problem and Scope (Web Crawler)

Crawl the public web starting from seed URLs
Store pages so a search index can use them later
Example system: a Google-style Web Crawler

Ranking
Indexing
JS-heavy rendering
Login-walled pages

2. Requirements

Seed intake: accept starting URLs
Fetch HTML pages
Extract links from each page
Dedupe URLs and content
Respect robots.txt
Recrawl by change rate

Non-functional	Target
Politeness	max 1 request/sec per host
Robustness	survive bad HTML, timeouts, traps
Extensibility	plug in new content types and parsers
Freshness	changing pages recrawled sooner
Scalability	~400 pages/sec avg, ~1,200 peak

System Design Case StudiesPage 2

High-Level Architecture and Crawl Loop

1. Pipeline and Components (Web Crawler)

Seedsstart URLs
URL frontierwhat to crawl next
DNS resolverhost → IP
FetcherHTTP GET
Content storeraw body
ParserHTML → text
Link extractora, link tags
Filter / dedupback to frontier

System Design Case StudiesPage 3

URL Frontier: Priority and Queues

The frontier of the Web Crawler: ~400 pages/sec average, ~1,200 peak, 10B known URLs waiting.

1. Responsibilities

Hold every URL still to crawl
Order by priority: important pages first
Enforce politeness: max 1 request/sec per host
Survive restarts: no lost or duplicated queue
Hand fetchers the next URL on demand

2. Two-Tier Design

System Design Case StudiesPage 4

Politeness and robots.txt Handling

Web Crawler: stay at 1 request/sec per host while the fleet runs ~400 pages/sec average, ~1,200 peak.

1. The Politeness Rule

One connection per host at a time, never parallel
Delay = max(1s, 10x last fetch time), or the host's Crawl-delay if larger
Fetch took 3s → wait 30s; fetch took 200 ms → wait 1s
Host not yet allowed → park its back queue, serve another host

Pop hostearliest next_allowed_at
Robots checkcache, 24h
Fetch1 connection
Set next_allowed_atnow + delay

System Design Case StudiesPage 5

DNS Resolution and Fetcher Design

1. DNS Is the Bottleneck

Running example: the Web Crawler at 1,200 fetches/sec peak, where every new host needs a lookup.

Synchronous lookups take 10-200 ms and block a worker
Run a custom async resolver inside the fetcher
Keep a local cache of ~10M entries
Honor each record's TTL; expire entries when it runs out
A cache hit costs microseconds, not a network round trip

System Design Case StudiesPage 6

Parser and Link Extraction

1. What the Parser Does

Runs after the fetcher stores the body in the content store (Web Crawler)
Validate Content-Type is text/html; skip images, PDFs, zips
Detect the encoding before decoding the bytes
Extract text for the index
Extract links from a href, link href, and link rel=canonical

Fetchbody stored
Parse queuedecouples
Parser pooltype, charset, DOM
Normalizecanonical form
Filterrules
Dedup, frontiernew URLs only

System Design Case StudiesPage 7

URL Deduplication: Seen-URL Test

1. Why Check Every Link

In the Web Crawler, the seen-URL test sits between the link extractor and the frontier. It runs on every extracted link.

Goal: never re-enqueue any of the 10B+ URLs already known
Load: ~50 links/page x 400 pages/sec = 20,000 checks/sec
Each check must be fast (in-memory or one KV read)
A wrong "seen" answer loses a page; a wrong "new" answer only wastes a fetch

2. Exact Store and Bloom Filter

System Design Case StudiesPage 8

Content Deduplication with Fingerprints

1. Why Dedup Content

~=30%== of web pages are duplicates or near-duplicates
Sources: mirrors, tracking params, printer views
URL dedup cannot catch them: the URLs differ, the body is the same
Goal: skip parsing, indexing and storage for pages we already hold

2. Exact and Near Duplicates

Exact: store SHA-256 of the body in a KV store
A hit means skip parsing and indexing

System Design Case StudiesPage 9

Recrawl Scheduling and Freshness

1. The Goal and the Tiers

Goal: maximize fresh pages under a fixed budget of ~400 fetches/sec
Pages do not change equally: spend fetches where change is likely
Wasted fetch = page re-downloaded that did not change

Tier	Pages	Recrawl
Hot	News homepages	hourly

System Design Case StudiesPage 10

Distributed Crawler and Crawler Traps

1. Partition and Route (Web Crawler)

Partition by hash(host) on a consistent hash ring
Each node owns whole hosts, never part of one
Politeness state and robots cache stay local to the owner
No cross-node lock needed for the 1 request/sec per host rule

Parser on node Aextracts link
hash(host)owner = node C
Kafka topicpartitioned by host hash
Node C frontierback queue for host

System Design Case StudiesPage 11

Scaling, Failure Handling, Trade-offs and Interview Questions

1. Scale-out (Web Crawler)

	Today	10x growth
Peak fetch rate	1,200 pages/sec	~12,000 pages/sec
Fetcher nodes	~10 (60 connections each)	~100
Bandwidth	~1 Gbps	~10 Gbps
Storage	100 TB/month raw, ~30 TB gzip

System Design Case StudiesPage 12

Web Crawler Cheatsheet

Night-before notes for the Web Crawler design: numbers, frontier, politeness, dedup, recrawl, scale and traps.

1. Numbers

Quantity	Estimate
Volume	1B pages/month
Average rate	400/sec
Peak rate (3x)	1,200/sec
Raw storage

System Design Case StudiesPage 13

Check yourself

A crawler runs 10 workers that all pop from one shared queue. Host X has 500 URLs queued next to each other. What goes wrong, and what is the fix?

Several workers pop X's URLs at the same moment, so X gets parallel requests and the 1 request/sec rule is broken.
X may rate-limit with 429s or block the crawler.
Fix: route each URL to a back queue by hash(host), so one host lives in one queue.
Give each back queue to a single worker, and use a heap keyed by next-allowed-time to pick the next host.

The seen-URL check uses a Bloom filter: 'seen' means skip, 'not seen' means enqueue. Which mistake can it make, and which can it never make?

Quantity	Math	Result
Raw HTML	1B pages x 100 KB avg	100 TB/month
Compressed	gzip ~3x	~30 TB /month
Metadata	1B x 500 B	500 GB

Component	Job
Frontier	holds and orders URLs to crawl
Fetcher workers	download pages over async I/O
DNS cache	avoids slow repeat lookups
Parser	extracts text and links
Dedup services	URL seen and content seen
Content store	keeps raw pages
Scheduler	decides when to (re)crawl

Data	Store	Why
Page bodies	Blob store (S3 / HDFS)	large, write-once, cheap per TB
URL metadata	Key-value store	fast lookup by URL hash
Seen URLs	Bloom filter + KV	Bloom first, KV on a hit

	Front queues (F)	Back queues (B)
Keyed by	priority	host
Job	importance order	politeness
Per queue	many hosts	exactly one host

robots.txt status	Meaning	Action
`404`	no rules exist	allow all
`5xx`	server broken	disallow all, retry later
`429` / `503`	host overloaded	exponential backoff

Setting	Limit
Workers	async I/O, many sockets per node
Connect timeout	5 s
Read timeout	30 s
Max body	10 MB (truncate beyond)
Redirects	follow at most 5

Metric	Watch for
Fetch success rate	target above 90%
p99 fetch latency	tail near the 30 s read timeout means slow hosts
DNS cache hit rate	a drop means more 10-200 ms stalls
Bytes/sec	~40 MB/s average; ~120 MB/s at 3x peak

Step	Rule	Example
Scheme, host	lowercase	`HTTP://A.com` → `http://a.com`
Relative path	resolve against base URL	`../x` → `/x`
Fragment	strip `#...`	`/p#top` → `/p`
Default port	drop `:80` / `:443`	`a.com:80` → `a.com`
Query	sort params	`?b=2&a=1` → `?a=1&b=2`
Tracking	remove `utm_*`, `fbclid`	`?utm_source=x` → none

Problem	Defense
Malformed HTML	tolerant parser (html5lib or lxml style); never reject a page for bad tags
Huge page	truncate at 10 MB; parse what was kept
Wrong charset	sniff `<meta charset>` or `http-equiv`; fall back to UTF-8 with replacement

	Bloom filter	Exact hash set	Bloom + KV
Memory	~12 GB	80 GB (7x larger)	12 GB + KV on disk
Speed	fastest	KV read per check	KV only on Bloom hit
Errors	1% false positives	none	none
Cost of error	new URL dropped	none	none

	SHA-256	SimHash	MinHash
Finds	exact copies	near-dupes	near-dupes
Size	256 bits	64 bits	many hashes per page
Measure	equality	Hamming ≤ 3	estimates Jaccard on shingles
Cost	cheapest	cheap	heavier; best for set overlap

url_meta field	Use
`url_hash`	key
`last_crawled`, `next_crawl`	scheduler orders by next_crawl
`etag`	conditional GET
`content_hash`	detect real change
`change_count`	change history
`interval`	adaptive, 1h to 30d

Trap	Example	Why it loops
Infinite calendar	`/cal?month=2031-04`, next-month link forever	Every page links to a new date
Session ID in URL	`/page?sid=a8f3...`	New ID per visit, same content
Repeated segments	`/a/b/a/b/a/b`	Relative links stack on the path
Generated pages	`/page/1`, `/page/2`, ... endless	Server builds each page on demand
Spam site	Millions of auto-made pages	Built to soak up crawlers

Defense	Limit	Catches
Max URL length	2,048 chars	Growing paths and query strings
Max depth	~15 hops from seed	Endless link chains
Pages per host cap	fixed budget per host	Spam and generated pages
Repeated segments	same segment 3+ times	`/a/b/a/b` loops
Content-hash loop	same body hash seen again	Session IDs, calendars

Choice	Gain	Cost
BFS crawl	Broad coverage	Low-value pages crawled early
Priority crawl	Better quality sooner	Long tail reached later
Exact URL set	No false positives	80 GB, 7x larger than Bloom
Bloom filter	~12 GB at 1% FP	Drops ~1% of new URLs
SimHash distance high	Higher recall of near-dupes	False merges of distinct pages
SimHash distance low	Few false merges	Misses near-dupes

Check	Method	Key number
Seen URL	Bloom filter, then KV on hit	9.6 bits/URL at 1% FP (~12 GB for 10B)
Exact content	`SHA-256` of body	hit = skip parse and index
Near-dupe	`SimHash` 64-bit	Hamming distance ≤ 3

Design a Web Crawler

1. Problem and Scope (Web Crawler)

2. Requirements

1. Pipeline and Components (Web Crawler)

1. Responsibilities

2. Two-Tier Design

1. The Politeness Rule

1. DNS Is the Bottleneck

1. What the Parser Does

1. Why Check Every Link

2. Exact Store and Bloom Filter

1. Why Dedup Content

2. Exact and Near Duplicates

1. The Goal and the Tiers

1. Partition and Route (Web Crawler)

1. Scale-out (Web Crawler)

1. Numbers

3. Scale and Storage Estimates

2. The Crawl Loop

3. Storage Choices

4. Bandwidth Estimate

3. Prioritizer and Router

4. Size and Failure

2. robots.txt Rules

3. Data Model

4. Failures, Metrics, Mistake

2. Fetcher and HTTP Details

3. Capacity and Failures

4. Metrics

2. Normalize, Then Filter

3. Failure Scenarios

3. Comparison

4. Common Mistake

3. Lookup and Storage

2. Change Rate and Cheap Checks

3. Data Model

4. Metrics

2. Adding a Node

3. Crawler Traps

4. Defenses and Manual Handling

2. Failure Handling

3. Trade-offs

4. Interview Answers

2. Frontier and Politeness

3. Dedup and Recrawl

4. Distribute and Defend