Infrastructure · Design 29

Design Web crawler

Design a web crawler in a 45-minute interview: a URL frontier with per-host politeness, robots.txt and DNS caching, Bloom-filter and SimHash dedup, traps and recrawling.

AdvancedInterview priority: Medium55 min
On this page
  1. How to use this page
  2. 1. Clarify the requirements
  3. 2. Back-of-the-envelope estimates
  4. 3. API
  5. 4. Data model
  6. 5. High-level design
  7. 6. Deep dives
  8. 7. Bottlenecks, failures and monitoring
  9. 8. Follow-up questions
  10. Quiz

How to use this page

This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first, then open ours and compare. A crawler looks like a simple loop ("fetch, extract links, repeat"), and the interview is about everything that goes wrong when that loop meets the real web.

PhaseTime in a 45-min interviewWhat you produce
1. Clarify requirements5 minScope (HTML only?), politeness rules, freshness
2. Estimate5 minPages/s, bandwidth, storage, URL-seen set size
3. API3 minThe internal interfaces between the loop's stages
4. Data model5 minFrontier, seen set, page store, fingerprints
5. High-level design10 minThe crawl loop, traced for one page
6. Deep dives10–15 minPoliteness, URL dedup, content dedup, traps, recrawl
7. Wrap up2–3 minBottlenecks, failures, what you would monitor

Starting from seed URLs, download web pages, extract their links, and keep crawling. Store the HTML for an indexer. Respect robots.txt and don’t overload any website. Re-crawl pages periodically. Skip building the search index and ranking, JavaScript rendering, and images or video.

1. Clarify the requirements

Your turn: scope it

The interviewer says: "Design a web crawler." Write the questions you would ask, the functional and non-functional requirements with targets, and what you would leave out.

Compare with our answer

The questions that matter most: What is it for (a search index, an archive, price monitoring)? How many pages, how often? HTML only, or images and JavaScript-rendered pages too? Must we re-crawl changed pages? How polite must we be? Then agree the list below.

A strong answer mentions: seeds → fetch → extract → repeat · store HTML for an indexer · obey robots.txt and a per-host rate limit · skip duplicate URLs and duplicate content · re-crawl by change rate · JavaScript rendering, ranking and the index itself out of scope.

Functional: what it must do

  • Crawl from seed URLs: Follow links breadth-first
  • Store page content: HTML for the indexer
  • Respect robots.txt: And per-site crawl delays
  • Avoid duplicates: Same URL or same content
  • Re-crawl: Popular / changing pages more often

Out of scope

Building the search indexRankingJavaScript renderingImages and video

Non-functional: how well it must work

QualityTargetWhy
Throughput~400 pages/s sustained (1 B/month)
Politeness≤ 1 request per second per host by defaultDon’t knock websites over
RobustnessSurvive bad HTML, slow servers, traps and crashesThe web is messy
ScalabilityAdd machines to crawl more
FreshnessImportant pages re-crawled within days

robots.txt is a plain-text file at the root of every site (https://example.com/robots.txt) that says which paths crawlers may fetch, standardised as RFC 9309. Some sites add a non-standard Crawl-delay line; many crawlers honour it, though Google ignores it and lets site owners adjust crawl rate in its own tools.

2. Back-of-the-envelope estimates

Your turn: the numbers

Assume 1 billion pages a month, 100 KB of HTML per page, 10 million distinct hosts, and 5 years of storage. Work out pages per second, bandwidth, storage per month, and the memory needed to remember every URL you have seen.

Compare with our answer
  • Pages/s: 1 B ÷ (30 × 86,400 s) ≈ 400/s; plan for ~800/s at peak.
  • Bandwidth: 400 × 100 KB = 40 MB/s, about 320 Mbps.
  • Storage: 1 B × 100 KB = 100 TB/month raw; HTML compresses 4–5×, so ~20–25 TB stored.
  • Per host: 1 B ÷ 30 ÷ 10 M ≈ 3 pages per host per day on average, but a few huge sites have millions of pages.
  • URL-seen set: links outnumber pages, so expect ~10 B distinct URLs. As strings (~100 bytes) that's 1 TB; a Bloom filter at 1% false positives needs ~10 bits per URL, ≈ 12 GB.

A strong answer mentions: pages/s with a peak factor · bandwidth in Mbps · compressed storage · the per-host trickle (politeness is easy for most hosts, hard for big ones) · seen-set memory as the number that forces a Bloom filter.

Assumptions: pages per month 1 B; average html page size 100 KB; years of storage kept 5; distinct websites (hosts) 10 M.

NumberEstimateWhy it matters
Pages per second386 / s1 B ÷ (30 × 86,400) ≈ 400/s; peaks maybe 800/s.
Download bandwidth38.6 MB/s≈ 40 MB/s (about 320 Mbps) of HTML.
Storage per month100 TB≈ 100 TB a month raw; HTML compresses 4–5×, so about 20–25 TB stored.
Storage over the retention period6 PB
Average pages per host per day3.33Most hosts are small; a few huge sites need careful scheduling.
  • 400 pages a second spread over millions of hosts means huge parallelism, but per-host speed stays tiny.
  • Keep a URL-seen set of billions of entries: a Bloom filter makes it fit in memory.

One more number matters: concurrency. A fetch takes 0.5–2 s (DNS, TCP and TLS handshakes, a slow server), so 400 pages/s needs roughly 400–800 requests in flight at once, which a few machines with asynchronous I/O can hold. And since each host allows only about one request a second, at least 400 different hosts must be active at any moment. The frontier's real job is keeping enough distinct hosts ready.

3. API

Your turn: the interfaces

A crawler has no public API. What are the internal calls between the frontier, the fetchers and the parser?

Compare with our answer

A strong answer mentions: frontier.add(urls, priority) from the link extractor · frontier.next(worker) that only returns a URL whose host is allowed now · store.put(url, html) returning a content hash · a robots.txt fetch per host, cached.

CallRequestResponseNotes
(internal) frontier.add(urls[])normalised URLs + priority–Called by the link extractor
(internal) frontier.next(workerId)–{ url, host } when the host is allowedRespects per-host delays
(internal) store.put(url, html, fetchedAt)pagecontentHashRaw pages for the indexer
GET {host}/robots.txt–rulesFetched once per host, cached for a day

The interesting call is frontier.next(). It isn't "pop the queue"; it's "give me a URL whose host may be contacted now". That one sentence is the politeness deep dive.

4. Data model

Your turn: the stores

Which data must survive a crash, which can live in memory, and what is the biggest structure?

Compare with our answer

A strong answer mentions: a disk-backed frontier (billions of pending URLs) · a Bloom filter for "seen URL" plus a persistent table of per-URL crawl state · object storage for compressed HTML · a fingerprint store for content dedup · in-memory robots.txt and DNS caches with TTLs.

URL frontier Disk-backed priority queues (Kafka / RocksDB) with per-host queues

  • priority queues (front)
  • per-host FIFO queues (back)
  • host → next allowed time (heap)

Billions of pending URLs; must decide what to fetch next and when each host is allowed.

URL seen set Bloom filter in memory + persisted set

  • bloom(normalised URL)
  • url_hash → last_crawled, next_due

“Have we already queued this URL?” for billions of URLs; a Bloom filter answers in a few bits per URL.

content store Object storage / Bigtable

  • url_hash → html (compressed), fetched_at, content_hash

Petabytes of raw HTML for the indexer; append-heavy.

content hashes Key-value store

  • content_hash / simhash → url

Detect pages with identical or near-identical content (mirrors, copies).

robots and DNS cache In-memory cache

  • host → robots rules, crawl-delay (TTL 1 day)
  • host → IP (TTL)

Avoid re-fetching robots.txt and resolving the same hosts repeatedly.

Two terms from the table:

  • A Bloom filter is a bit array plus several hash functions. Adding a URL sets a few bits; checking a URL tests those bits. If any bit is 0, the URL is definitely new. If all are 1, it was probably seen, with a tunable false-positive rate. It never says "new" for a URL it has seen.
  • A content fingerprint is a short hash of a page's content, used to spot copies without comparing full pages.

The per-URL table (url_hash → last_crawled, next_due, etag) is what recrawling reads. It's large (billions of rows) but simple, so a wide-column or key-value store such as Bigtable, Cassandra or RocksDB on each crawler node fits.

5. High-level design

Your turn: draw it

Sketch the crawl loop. Where does politeness live? Where are DNS and robots.txt looked up? Where are duplicate URLs and duplicate pages caught?

Compare with our answer

Compare with the figure. The pieces people most often forget: DNS caching (resolution becomes the bottleneck), checking robots.txt before every fetch, and the difference between URL dedup (before queueing) and content dedup (after fetching).

The crawl loop, then one page fetched through it

  1. The architecture is a loop. The URL frontier holds what to crawl next, with a politeness scheduler per host. Fetchers download pages using DNS and robots.txt caches. A parser de-duplicates content and stores pages, and a link extractor feeds new URLs back through a seen-filter into the frontier.
  2. A fetcher asks the frontier for its next URL; the politeness scheduler only hands out a host when its delay has passed. The fetcher checks robots.txt and DNS caches, downloads the page, and the parser checks whether the content is a duplicate before storing it.
ComponentWhat it does
URL frontierPrioritised, per-host queues of URLs to fetch
Politeness schedulerEnsures ≥ 1 s (or robots crawl-delay) between requests to the same host
FetchersMany async workers; timeouts, size limits, retries
DNS / robots cachesAvoid repeated lookups
Parser + content dedupExtract text/links; skip duplicate pages
Link extractor + URL seenNormalise links; Bloom filter of known URLs
Page storeRaw HTML for indexing

Trace one page:

  1. A fetcher asks the frontier for work. The politeness scheduler hands out example.com/a because example.com's delay has passed.
  2. The fetcher checks the cached robots.txt rules for example.com (fetching them first if the cache has none), and resolves the host from the DNS cache.
  3. It downloads with a timeout (say 30 s) and a size cap (say 10 MB), following at most a few redirects.
  4. The parser fingerprints the content. A duplicate is skipped; a new page goes to the page store.
  5. The link extractor normalises the page's links, drops those already seen, and adds the rest to the frontier with a priority.

6. Deep dives

Your turn: the hard parts

Two or three sentences each: how do you crawl 400 pages a second while sending only one request a second to each site? How do you remember 10 billion URLs? How do you notice that two different URLs serve the same page? How do you avoid an infinite calendar?

Compare with our answer

A strong answer mentions:

  • Priority front queues, one back queue per host, and a heap keyed by each host's next allowed time.
  • URL normalisation before a Bloom filter, and what a false positive costs.
  • An exact hash for identical pages and SimHash with a small Hamming distance for near-duplicates.
  • Per-host budgets, URL length and depth limits, and repeated-pattern detection for traps.

Politeness: a frontier that schedules hosts

A page's links mostly point to the same site. Put them in one FIFO queue and the fetchers swarm that site.

From one FIFO queue to per-host queues and a ready heap

OptionHowCatch
One FIFO queueFetch in discovery orderLinks cluster by site, so one site gets hammered
Random orderShuffle the queueSpreads load on average, but no guarantee and no priorities
Mercator-style frontier (chosen)Front queues by priority → back queues per host → heap of next-allowed timesMore moving parts; must keep enough hosts in the heap

The design is named after Mercator, an early crawler from Compaq's research lab. Front queues hold URLs by priority (importance, freshness). A router moves URLs into back queues, one per host, and keeps about three times as many back queues as fetcher threads so a ready host is always available. A heap (a structure that always returns its smallest item first) holds each host with the time it may next be contacted. A fetcher pops the heap, waits if the time is in the future, fetches one URL from that host's queue, and pushes the host back with now + delay. A good default delay is a small multiple of how long the last fetch took, so slow sites are crawled more gently, never faster than robots.txt's Crawl-delay.

To spread this across machines, hash the host name to a crawler node. Every URL of a host lands on the same node, so politeness is enforced locally without any coordination.

DNS: the hidden bottleneck

Every fetch needs an IP address. A DNS lookup takes from a few milliseconds to hundreds when it misses all caches, and the standard resolver library in many languages is blocking. At 400 fetches a second spread over millions of hosts, DNS can become the slowest step. The fix: run a local caching resolver on each crawler node, use asynchronous lookups, respect each record's TTL, and prefetch the IP when a host's URLs reach the front of its back queue. The robots.txt cache works the same way: one fetch per host, cached for about a day.

Fetchers: surviving a hostile web

Fetchers talk to millions of servers you don't control, and some are broken or malicious. Each defence is cheap; skipping any one of them eventually stalls a fetcher:

  • Timeouts at every stage: connect (~5 s), first byte, and total download (~30 s). A server that sends one byte a minute (a "tarpit") otherwise holds a connection forever.
  • Size caps: stop reading after ~10 MB and keep only the part needed for indexing.
  • Redirect limits: follow at most ~5, and run each redirect target through normalisation and the seen check like any other link.
  • Content-type checks: skip images, video and archives early from the Content-Type header.
  • Per-host backoff: after repeated 5xx errors or timeouts, push the host's next-allowed time far into the future instead of retrying at full speed.

Pages are written in batches to object storage, typically in WARC files (the standard web archive format that bundles many request/response records into one compressed file), which keeps the number of objects manageable at a billion pages a month.

Seen URLs: normalise, then a Bloom filter

The same page can be written many ways: HTTP://Example.com:80/a/../b#top is http://example.com/b. URL normalisation converts each link to one canonical form: lowercase scheme and host, remove default ports and #fragments, resolve . and .., decode unnecessary percent-escapes, and strip known tracking parameters (utm_*, session ids). Only then check "seen?".

New links are normalised and checked against the URL-seen filter

  1. Extracted links are cleaned up into a standard form, checked against the URL-seen Bloom filter, and only new ones are added to the frontier with a priority.
OptionMemory for 10 B URLsCatch
Database lookup per linkSmall RAM, big diskTens of thousands of random reads a second
Hash set of URL strings~1 TBExact, but needs a cluster of RAM
Hash set of 8-byte URL hashes~80 GB+Exact enough, still large; shard by hash
Bloom filter (chosen)~12 GB at 1%~1% of new URLs wrongly skipped

A false positive means a page is never crawled. For a search engine that's usually acceptable, and you can lower the rate (at 0.1%, ~15 bits per URL, ~18 GB) or re-admit important URLs from sitemaps. Shard the filter by URL hash across nodes and checkpoint it to disk so a restart doesn't lose it. Note that a Bloom filter can't delete; when you want to "forget" URLs, rebuild it periodically from the persistent per-URL table.

Duplicate content: exact hashes and SimHash

Mirrors, ?sort=asc variants and syndicated articles produce the same content under different URLs; studies of web crawls have found that roughly a quarter to a third of pages are duplicates or near-duplicates.

  • Exact duplicates: hash the page body (after stripping whitespace) with a fast 64- or 128-bit hash and look it up. Cheap and exact, but a single changed timestamp or ad defeats it.
  • Near-duplicates: SimHash turns a page into a 64-bit fingerprint in which similar pages get fingerprints that differ in only a few bits. Google's crawler used SimHash to call two pages near-duplicates when their fingerprints differed in at most 3 of 64 bits (the Hamming distance, the number of differing bits). Finding all fingerprints within 3 bits fast uses several tables, each keyed on a different block of bits, since two fingerprints within 3 bits must share at least one of the blocks exactly.

A detected duplicate is not stored again, and its links are usually not followed either.

Crawler traps

A crawler trap is a site, accidental or deliberate, that generates infinite URLs: a calendar with a "next month" link forever, /a/b/a/b/a/b/… from a relative-link bug, or a session id added to every link.

DefenceWhat it stops
Max URL length (e.g. 2,000 characters) and path depthEver-growing paths
Per-host page budget per crawl cycleAny single site eating the crawl
Repeated-segment detection (/a/b/a/b)Relative-link loops
Stripping session-id parameters during normalisationInfinite unique URLs for one page
Priority demotion for deep, low-linked URLsTraps that slip through, crawled last

No single rule catches every trap; the per-host budget is the one that bounds the damage.

Recrawling: how often to come back

A news front page changes every few minutes; a 2009 forum thread never does. Re-crawling everything daily wastes most of the bandwidth.

Estimate each page's change rate from history (how often the fingerprint changed on past visits) and combine it with importance to set next_due. Shorten the interval when a page changed, lengthen it (up to a cap such as a month) when it didn't. Make each re-fetch cheap with a conditional GET: send If-None-Match with the stored ETag or If-Modified-Since; an unchanged page returns 304 Not Modified with no body. Sitemaps with lastmod dates hint which pages changed.

Prioritising the frontier

The front-queue priority blends signals: a link-based importance score (PageRank-like, computed offline from the link graph), the host's quality, how stale the page is relative to its change rate, and whether it's a new URL. A useful mental model: the frontier has a fixed budget of fetches per second, and each candidate URL is worth "importance × probability it changed since last crawl". New URLs from high-quality hosts score well; deep URLs on a host that is already over its budget score poorly.

7. Bottlenecks, failures and monitoring

Scaling bottlenecks

BottleneckFix
ThroughputAdd fetcher machines; partition the frontier by host hash so each host lives on one machine
DNS bottleneckLocal caching resolvers; prefetch
Bloom filter sizeShard by URL hash; persist periodically
StorageCompress pages; object storage; drop pages after the indexer consumes them if not needed

When things fail

FailureWhat happens
Fetcher machine crashesIts in-flight URLs time out and return to the frontier
Site is slow or downTimeouts, exponential backoff per host, mark as unhealthy
Frontier node lostFrontier is disk-backed and replicated; resume from checkpoints
Malformed HTMLLenient parsers; skip and log

What to monitor

Pages fetched per secondError rate by type (timeouts, 4xx, 5xx)Frontier size and agePer-host request rate (politeness)Duplicate rateStorage growth

8. Follow-up questions

Your turn: the interviewer pushes

Answer in order. 1) A site's robots.txt returns a 503 error for a day. What do you do? 2) You must also crawl JavaScript-heavy pages that show nothing without running scripts. What changes? 3) Crawl volume grows 10× to 4,000 pages a second. What breaks first?

Compare with our answer

A strong answer mentions:

  1. Treat a server error on robots.txt as "don't crawl" for that host (RFC 9309 says to assume complete disallow on 5xx), keep the last good copy if you have one, back off and retry later; a 404 means no rules, so crawling is allowed.
  2. A separate, much slower rendering tier of headless browsers, used only for pages that need it (detected by little text in raw HTML); render queue with its own politeness, and a far higher cost per page.
  3. DNS resolution, the URL-seen filter size and the frontier's disk I/O come first; add crawler nodes (host-hash partitioning makes this linear), scale bandwidth to ~3 Gbps, and make sure enough distinct hosts are ready to keep fetchers busy.
How would you crawl JavaScript-heavy sites?

A separate, much slower rendering tier with headless browsers, used only for pages that need it.

How do you prioritise pages?

PageRank-like importance, freshness needs, and site quality feed the frontier priority.

How do you distribute across machines?

Hash the host to a crawler node so politeness is enforced locally without coordination.

Web crawler on one page
  • Numbers: 1 B pages/month ≈ 400/s; 40 MB/s (~320 Mbps); 100 TB/month raw, ~20–25 TB compressed; ~400–800 fetches in flight.
  • Frontier (Mercator): priority front queues → per-host back queues → heap of next-allowed times. Hash host → node.
  • Politeness: ~1 request/s per host (slower for slow sites), also limit per IP; obey robots.txt, cached ~1 day.
  • DNS: local caching resolver, async lookups, prefetch.
  • URL dedup: normalise first, then a Bloom filter (~10 bits/URL at 1% → ~12 GB for 10 B URLs). False positive = a skipped page.
  • Content dedup: exact hash + SimHash (≤ 3 differing bits of 64).
  • Traps: URL length/depth limits, per-host budgets, repeated-segment detection, session-id stripping.
  • Recrawl: interval from change rate × importance; conditional GET (304); sitemaps.
  • Robustness: timeouts, size caps, disk-backed frontier, in-flight URLs time out and return.
Mock interviewPractise it as a mock interview: scope, size and the big decisionsOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A crawler fetches 400 pages a second with 1,000 async fetchers sharing one global FIFO queue of discovered URLs. What goes wrong first?

2. You hash each host name to a crawler node, and each node enforces one request a second per host. A shared-hosting server serves 20,000 sites from one IP. What is the risk?

3. Your URL-seen Bloom filter is tuned for a 1% false-positive rate. What does a false positive cost?

4. Two URLs, /article?id=5 and /article?id=5&utm_source=mail, are both queued and fetched. Which step should have caught this most cheaply?

5. A news site changes its footer timestamp on every page load, so the exact content hash differs each time even though the article is identical. What detects the copy?

6. The crawler spends a week fetching /calendar?month=… pages from one university site, millions of them. Which defence bounds the damage of any trap like this?

7. Most of your 1 B pages rarely change. How do you keep re-crawls cheap without missing updates?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.