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.
On this page
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.
| Phase | Time in a 45-min interview | What you produce |
|---|---|---|
| 1. Clarify requirements | 5 min | Scope (HTML only?), politeness rules, freshness |
| 2. Estimate | 5 min | Pages/s, bandwidth, storage, URL-seen set size |
| 3. API | 3 min | The internal interfaces between the loop's stages |
| 4. Data model | 5 min | Frontier, seen set, page store, fingerprints |
| 5. High-level design | 10 min | The crawl loop, traced for one page |
| 6. Deep dives | 10–15 min | Politeness, URL dedup, content dedup, traps, recrawl |
| 7. Wrap up | 2–3 min | Bottlenecks, 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
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
| Quality | Target | Why |
|---|---|---|
| Throughput | ~400 pages/s sustained (1 B/month) | |
| Politeness | ≤ 1 request per second per host by default | Don’t knock websites over |
| Robustness | Survive bad HTML, slow servers, traps and crashes | The web is messy |
| Scalability | Add machines to crawl more | |
| Freshness | Important 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
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.
| Number | Estimate | Why it matters |
|---|---|---|
| Pages per second | 386 / s | 1 B ÷ (30 × 86,400) ≈ 400/s; peaks maybe 800/s. |
| Download bandwidth | 38.6 MB/s | ≈ 40 MB/s (about 320 Mbps) of HTML. |
| Storage per month | 100 TB | ≈ 100 TB a month raw; HTML compresses 4–5×, so about 20–25 TB stored. |
| Storage over the retention period | 6 PB | |
| Average pages per host per day | 3.33 | Most 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
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.
| Call | Request | Response | Notes |
|---|---|---|---|
(internal) frontier.add(urls[]) | normalised URLs + priority | – | Called by the link extractor |
(internal) frontier.next(workerId) | – | { url, host } when the host is allowed | Respects per-host delays |
(internal) store.put(url, html, fetchedAt) | page | contentHash | Raw pages for the indexer |
GET {host}/robots.txt | – | rules | Fetched 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
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
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
- 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.
- 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.
| Component | What it does |
|---|---|
| URL frontier | Prioritised, per-host queues of URLs to fetch |
| Politeness scheduler | Ensures ≥ 1 s (or robots crawl-delay) between requests to the same host |
| Fetchers | Many async workers; timeouts, size limits, retries |
| DNS / robots caches | Avoid repeated lookups |
| Parser + content dedup | Extract text/links; skip duplicate pages |
| Link extractor + URL seen | Normalise links; Bloom filter of known URLs |
| Page store | Raw HTML for indexing |
Trace one page:
- A fetcher asks the frontier for work. The politeness scheduler hands out
example.com/abecause example.com's delay has passed. - 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.
- It downloads with a timeout (say 30 s) and a size cap (say 10 MB), following at most a few redirects.
- The parser fingerprints the content. A duplicate is skipped; a new page goes to the page store.
- 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
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
| Option | How | Catch |
|---|---|---|
| One FIFO queue | Fetch in discovery order | Links cluster by site, so one site gets hammered |
| Random order | Shuffle the queue | Spreads 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 times | More 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-Typeheader. - 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
- 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.
| Option | Memory for 10 B URLs | Catch |
|---|---|---|
| Database lookup per link | Small RAM, big disk | Tens of thousands of random reads a second |
| Hash set of URL strings | ~1 TB | Exact, 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.
| Defence | What it stops |
|---|---|
| Max URL length (e.g. 2,000 characters) and path depth | Ever-growing paths |
| Per-host page budget per crawl cycle | Any single site eating the crawl |
Repeated-segment detection (/a/b/a/b) | Relative-link loops |
| Stripping session-id parameters during normalisation | Infinite unique URLs for one page |
| Priority demotion for deep, low-linked URLs | Traps 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
| Bottleneck | Fix |
|---|---|
| Throughput | Add fetcher machines; partition the frontier by host hash so each host lives on one machine |
| DNS bottleneck | Local caching resolvers; prefetch |
| Bloom filter size | Shard by URL hash; persist periodically |
| Storage | Compress pages; object storage; drop pages after the indexer consumes them if not needed |
When things fail
| Failure | What happens |
|---|---|
| Fetcher machine crashes | Its in-flight URLs time out and return to the frontier |
| Site is slow or down | Timeouts, exponential backoff per host, mark as unhealthy |
| Frontier node lost | Frontier is disk-backed and replicated; resume from checkpoints |
| Malformed HTML | Lenient 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
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:
- 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.
- 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.
- 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.
- 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.
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?
Links on a page mostly point to the same site. Per-host back queues and a next-allowed-time heap enforce politeness while other hosts keep fetchers busy.
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?
Politeness per host name ignores shared infrastructure. Also rate-limit per resolved IP and back off when its latency or errors rise.
3. Your URL-seen Bloom filter is tuned for a 1% false-positive rate. What does a false positive cost?
A Bloom filter can wrongly say "seen" but never wrongly say "new". The cost is a small fraction of pages that are never fetched.
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?
Normalising before the seen check avoids the fetch entirely. Content dedup would catch it too, but only after paying for the download.
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?
Any cryptographic or exact hash changes completely with one byte. SimHash is designed so similar inputs give fingerprints within a small Hamming distance.
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?
Every calendar URL is genuinely new, so dedup can't help. A per-host budget caps what any single site can consume.
7. Most of your 1 B pages rarely change. How do you keep re-crawls cheap without missing updates?
Adaptive intervals spend fetches where content changes; ETag or If-Modified-Since turns an unchanged page into a tiny 304 response.
Score 60% or more and the lesson is marked complete.