Distributed Data Primitives
Design a web crawler
Every search engine, every price monitor, every archive starts with the same humble machine: download a page, read its links, repeat forever. The algorithm is one line. The engineering is everything around it — billions of pages, hosts that will ban you, and a queue that must never forget where it was.
You start from a handful of seed URLs — a few trusted, link-rich pages — and everything else is discovered. Say the target is one billion pages per month: that is roughly 400 pages per second, sustained, day and night. A single machine fetching 50 pages a second needs a week to do what a small fleet does in hours, so this is a distributed system from the first sketch.
The frontier is the queue of URLs waiting to be fetched, and it answers two questions: which page next, and how fast may we ask each host. Politeness means per-host queues — all URLs for one host sit in their own queue, and a worker keeps at most one request in flight per host with a delay between requests, so a thousand-page site gets visited steadily, never hammered. Priority runs in parallel: pages that change often or matter more (a news homepage beats a forgotten forum thread) jump ahead. One global queue would fail both jobs — it would fire fifty requests at one unlucky host in the same second.
Fetchers are stateless workers that pull a URL from its host queue, download the page, and hand the bytes on. The hidden bottleneck is DNS: every new hostname means a lookup that can cost hundreds of milliseconds and hammer public resolvers until they throttle you. So each fetcher keeps a DNS cache — hostname to IP, refreshed on expiry — and a crawl that touched ten million hosts resolves most names from memory. Robots.txt gets the same treatment: fetch it once per host, cache it, and obey it.
The parser extracts text and outgoing links, and then two filters save you from yourself. First, the document fingerprint: hash the page content and compare — many URLs serve identical content (mirrors, tracking parameters), and a seen checksum lets you skip storing and re-processing the same page. Second, the URL-seen set: before any extracted link enters the frontier, check whether it was already queued. At a billion URLs that set cannot live in a hash map — a Bloom filter holds it in a few gigabytes of RAM, with rare false positives whose only cost is skipping one page the web will offer again tomorrow.
Some sites generate infinite URL spaces on purpose or by accident: a calendar page that links to next month forever, a search page with endless filter combinations. Your crawler will happily fill its frontier with one site's garbage while the rest of the web waits. The defenses are boring and effective: a maximum crawl depth per seed, a per-host page budget, and URL length limits. Traps are not an edge case — they are the default state of the open web.
A month-long crawl will meet dead workers, full disks, and at least one deploy that goes wrong. If the frontier lives only in memory, one crash costs you every discovered-but-unfetched URL — days of work. So persist the frontier: snapshot it to disk or a replicated store, and checkpoint progress (which pages done, which in flight) often enough that recovery means resuming, not restarting. Fetchers can die freely; the queue may not.
Strip away the scale and a crawler is a queue with manners. The frontier decides what is next and how gently to ask, the fetchers are interchangeable muscle, and dedup is two cheap checks that keep the queue honest. Everything hard about this system lives in that queue — priority, politeness, persistence — and everything easy lives outside it.
Why does the frontier keep a separate queue per host instead of one big global priority queue? (Politeness: per-host queues let you enforce one in-flight request per host with a delay between requests, so no site ever gets hammered; a global queue could send fifty requests to the same host in one second, get you banned, and still starve high-priority pages behind a single noisy site.)
Draw it as a loop and the design tells on itself: seeds in, frontier pacing per host, fetchers with a DNS cache, parser, two layers of dedup, links back to the frontier. Then spend the interview on the three things that actually break crawlers — politeness, traps, and crashes — because that is where juniors draw boxes and seniors draw failure modes.
This Monday, write a fifty-line polite crawler in your favorite language: one seed page, a per-host map that enforces a one-second delay between requests, a seen-URL set, and a depth limit of three. Then point it at a site with a calendar widget and watch the depth limit save you — that little program contains every idea in this lesson except the scale.
Distributed Data Primitives