A web crawler looks like a loop you could write in an afternoon: take a URL, download it, pull out the links, add them to the list, repeat. At a billion pages a month that loop has to be polite to millions of servers that never agreed to be crawled, notice that it has seen a URL before among billions, recognise the same page under ten different addresses, and avoid sites that generate infinite links. The interviewer is checking whether you see those four problems behind the loop.
Build the crawler that feeds a general web search engine. Start from a list of seed URLs, follow links, and hand fetched pages to the indexing pipeline.
In scope
- HTML pages only (no images, video, or JavaScript rendering)
- Respecting robots.txt and crawl rate limits
- Deduplication and recrawling for freshness
A search crawler fetches an assumed 1B pages a month, about 400 a second, ~100 TB of raw HTML at ~320 Mbit/s, while sending at most one request a second to any host; a Bloom filter keeps 10 billion seen URLs in about 12 GB. The loop runs frontier, fetchers (DNS and robots.txt caches), S3 and parser, content dedupe, URL filter and back to the frontier, with new pages published to Kafka for the indexer. The deep dives cover priority queues plus one queue per host with a heap of due times, politeness under RFC 9309, URL normalisation, the Bloom filter, SimHash near-duplicates and spider traps; failures cover leased URLs, recrawling by change rate with conditional GETs, and robots.txt errors.
Phase 1: Requirements (3 minutes)#
"Is this for search indexing, so breadth and freshness matter? HTML only? Do we render JavaScript? How fresh must popular pages be?"
"Search indexing. HTML only, no rendering. News-like pages should be recrawled within hours, most pages within weeks."
Functional requirements#
- Start from seed URLs, extract links, and crawl newly discovered URLs
- Store the raw HTML and its metadata (URL, fetch time, status, content hash)
- Publish each new or changed page to the indexing pipeline
- Obey robots.txt rules and crawl delays
- Recrawl pages based on how often they change
Non-functional requirements#
- Polite: never overload a site; at most one request a second per host unless robots.txt asks for less
- Scalable: 1B pages a month, growing; add machines to go faster
- Robust: survive malformed HTML, slow or hostile servers, and spider traps
- Efficient: don't fetch the same URL twice in a cycle, and don't store the same content twice
Phase 2: Estimation (3 minutes)#
- Pages: 1B a month ÷ ~2.6M seconds ≈ ~400 pages/s average; plan for ~800/s peaks
- Assume an average HTML page of ~100 KB: 1B × 100 KB = ~100 TB a month raw, roughly 25 TB if compression shrinks HTML about 4x
- Bandwidth: 400 × 100 KB = ~40 MB/s, about 320 Mbit/s sustained
- Concurrency: if a fetch takes about a second end to end (DNS, connect, slow servers), you need ~400–800 fetches in flight, spread across many hosts because of politeness
- Seen set: assume the crawler has seen 10B distinct URLs. Storing them exactly at ~100 bytes each is ~1 TB; a Bloom filter at a 1% false-positive rate needs about 9.6 bits per URL, ~12 GB, which fits in memory
"Bandwidth and storage are ordinary. What makes this hard is scheduling: hundreds of fetches in flight, but never more than one per second against any single host."
Phase 3: API (2 minutes)#
The crawler is a backend pipeline; its interfaces are a control API and an output stream.
POST /v1/crawls
{ "seeds": ["https://example.org/"], "scope": "web", "max_pages": 1000000000,
"recrawl": { "default": "14d", "news_like": "2h" } }
→ 202 { "crawl_id": "c-2026-10" }// published to Kafka topic "pages" for the indexer
{ "url": "https://example.org/a", "fetched_at": "2026-10-25T09:30:00Z", "status": 200,
"content_hash": "sha256:9f2c...", "simhash": "0x8a1f03c4d2e7b6a9", "blob": "s3://crawl/2026/10/25/9f2c..." }Phase 4: High-level design (4 minutes)#
%% title: The crawl loop
flowchart TD
SEED@{ icon: "sd:file", label: "Seed URLs" } --> FR["URL frontier<br/>priority queues + one queue per host"]:::core
FR -->|"next URL whose host is due"| FE["Fetchers<br/>async HTTP, timeouts"]:::hot
FE <-->|"GET"| WEB@{ icon: "sd:globe", label: "The web" }
FE -.-> DNS@{ icon: "sd:dns", label: "DNS cache" }
FE -.-> RB@{ icon: "sd:cache", label: "robots.txt cache" }
FE -->|"raw HTML"| S3@{ icon: "tech:s3", label: "S3 · raw pages" }
FE --> PA["Parser<br/>links + text"]:::service
PA --> DD["Content dedupe<br/>hash + SimHash"]:::service
DD -->|"new or changed page"| K@{ icon: "tech:kafka", label: "Kafka · pages" }
K --> IDX@{ icon: "sd:search", label: "Indexer" }
PA -->|"extracted links"| UF["Normalise, filter,<br/>seen? (Bloom filter)"]:::service
UF -->|"only new URLs"| FR
class SEED,S3 store
class WEB external
class DNS,RB cache
class K queue
class IDX service- URL frontier: decides what to fetch next and when. It is the heart of the design (deep dive 1).
- Fetchers: asynchronous HTTP clients holding hundreds of connections each, with strict timeouts and a size cap per page. They use a local DNS cache (DNS lookups are slow and repetitive) and a robots.txt cache per host.
- Parser: extracts links and text; tolerant of broken HTML.
- Content dedupe: a hash of the normalised content catches exact copies; a SimHash fingerprint catches near-duplicates (deep dive 2).
- URL filter: normalises each link, drops unwanted ones (wrong scheme, blocked extensions, too long), and checks the Bloom filter so only unseen URLs reach the frontier.
- Kafka: decouples crawling from indexing, so a slow indexer never stalls the fetchers.
Phase 5: Deep dives (5 minutes)#
Deep dive 1: The frontier, or how to be fast and polite at once#
"You have a million URLs from the same big site in the queue. A plain FIFO would send all your fetchers there. What do you do?"
- Front queues by priority: new URLs are scored (page importance, how often it changes, how long since the last fetch) and placed into a handful of priority queues.
- Back queues by host: a router moves URLs from the front queues into one back queue per host. Each back queue only ever holds one host's URLs.
- A heap of "next allowed time": each host has a time before which it must not be hit again (now + 1 s, or the robots.txt Crawl-delay). Fetchers pop the host whose time is earliest and due, fetch one URL, and push the host back with its new time.
- Partition by host: with many crawler machines, assign hosts to machines by hashing the host name (consistent hashing), so one host's queue, timer and robots.txt live on exactly one machine.
This is the design described for the Mercator crawler in the late 1990s, and it is still the standard answer: priority decides what to fetch, per-host queues decide when.
- Fetch and cache robots.txt per host before crawling it; RFC 9309 says not to rely on a cached copy for more than 24 hours unless the file is unreachable
- Honour
Disallowrules and any crawl delay; default to one request a second per host - Identify yourself with a clear User-Agent and a contact URL
- Back off when a host answers slowly or with 429 or 503
Deep dive 2: Duplicates and traps#
"How do you know you've already seen a URL? And what about the same page at two addresses?"
- Same URL, different spelling: normalise before anything else. Lowercase the scheme and host, drop default ports (
:80,:443) and#fragments, resolve../, and strip known tracking parameters, soHTTP://Example.org:80/a/../b#topbecomeshttp://example.org/b. - Same URL, already seen: check the Bloom filter. It never says "no" for a URL it has seen; it says "maybe" for about 1% of new URLs, which means 1% of new URLs are skipped this cycle. For a crawler, that's an acceptable price for fitting 10B URLs in about 12 GB.
- Different URL, same content: mirrors, print versions and session IDs in URLs. An exact hash of the normalised text catches identical copies. SimHash produces a 64-bit fingerprint where similar documents differ in only a few bits, so pages within a small Hamming distance (say 3 bits) are treated as near-duplicates and not re-indexed.
A calendar with a "next month" link forever, a site that appends a new session ID to every link, or a server that generates infinite unique paths. None of these break any rule; they just never end.
Defences
- A maximum URL length and a maximum path depth
- A page budget per host per crawl cycle
- Detecting repeating path segments (
/a/b/a/b/a/b/) - Lowering the priority of hosts whose new pages are mostly near-duplicates
Frontier and dedupe
Q1/2 Why does the frontier keep one back queue per host?
Answer & explanation
Answer: B
Per-host queues plus a heap of "next allowed time" let hundreds of fetches run in parallel while any one host sees at most one request per interval.
Q2/2 The Bloom filter answers "maybe seen" for a URL that was never crawled. What is the effect?
Answer & explanation
Answer: C
False positives skip a few new URLs; there are no false negatives, so nothing seen is ever refetched by mistake. Fitting 10B URLs in about 12 GB is worth it.
Phase 6: Trade-offs and failure modes (2 minutes)#
A fetcher crashes mid-batch
Fetchers lease URLs from the frontier with a timeout. URLs that aren't acknowledged as done return to their host queue when the lease expires. A URL that keeps crashing the parser goes to a dead-letter queue after a few attempts.
robots.txt can't be fetched
RFC 9309 treats the two cases differently: if robots.txt returns a 4xx (for example 404), the crawler may crawl the site; if it is unreachable (5xx or a network error), assume everything is disallowed for now and retry later.
Freshness versus coverage
Every recrawl of an old page is a new page not crawled. Recrawl by observed change rate: pages that changed last time come back sooner. Use conditional requests (If-Modified-Since, ETag) so an unchanged page costs a 304 with no body.
Slow and hostile servers
Connection and read timeouts, a maximum page size, and a cap on redirects. A server that drips one byte a second must not tie up a fetcher slot.
The indexer falls behind
Kafka absorbs the gap. If lag keeps growing, slow the crawl rather than dropping pages.
Phase 7: Go deeper in the course#
- Crawling for a search engine, robots.txt and politeness in context: Side quest: Google Search
- What happens to pages after the crawl: Week 7 · Day 2: Indexing Pipeline
- Partitioning hosts across crawler machines: Week 1 · Day 1: Partitioning Deep-Dive
- Bloom filters and the vocabulary: Week 0 · Part 6: Terminology and Theory
- Queues, leases and redelivery: Week 3 · Day 1: Queue vs Stream
- Poison pages and dead letters: Week 3 · Day 4: Dead Letters and Poison Pills
- Slowing producers when consumers lag: Week 3 · Day 3: Backpressure and Flow Control
- Timeouts against slow servers: Week 2 · Day 1: Timeout Hell
Final check#
Final check · Web crawler
Q1/3 1B pages a month at about 100 KB each. Roughly what sustained download bandwidth is that?
Answer & explanation
Answer: B
About 400 pages/s × 100 KB = 40 MB/s, which is about 320 Mbit/s. Bandwidth is ordinary; scheduling under politeness is the hard part.
Q2/3 Which pair of URLs should normalisation turn into the same string?
Answer & explanation
Answer: A
Case of scheme and host, default ports,
../segments and fragments don't change the resource. Query parameters likepage=2and different hosts or paths do.Q3/3 A site's robots.txt returns 503 for an hour. What should the crawler do?
Answer & explanation
Answer: C
RFC 9309: unreachable (5xx) means assume complete disallow; a 4xx such as 404 means the crawler may proceed.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.