Loading...
A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.
The trap in this question is that the algorithm is three lines: download the seed pages, extract their links, add new links to the list, repeat. The interview is about the gap between that loop and a system that fetches hundreds of pages per second, politely, for weeks, without dying or looping forever.
Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):
Build incrementally while you talk. Trace one URL end to end through your diagram — from the frontier, through fetch and dedupe, back into the frontier. Argue the tradeoff, not "industry standard."
Read this before you go in. These are the decisions, and why they matter.
The web is a directed graph: pages are nodes, links are edges. DFS goes arbitrarily deep down one site — usually a bad default. BFS with a FIFO queue is the standard start, but naive BFS fails twice at scale. First, most links on a page point back to the same host; parallel workers draining one queue will flood that host — your crawler becomes a DoS attack. Second, the web is not uniform quality: apple.com's homepage and a forum post mentioning Apple should not crawl at the same priority. Nuance worth naming: DFS within a host you are already connected to amortizes handshake overhead, and path-ascending crawling (given foo.com/a/b/page.html, also try /a/b/, /a/, /) finds resources with no inbound links. Equally defensible if you can say why.
The frontier is the queue of URLs still to download, and it is the hard part of this question. Two problems, two layers of queues.
Politeness (back queues). Rule: at most one connection per host, with a delay between requests. Mechanism: a hostname-to-queue mapping table routes every URL for one host into one dedicated FIFO queue, and each worker drains exactly one queue, sequentially. Those two invariants together are the guarantee. One global queue with a worker pool has no politeness story.
Priority (front queues). A prioritizer scores each URL (PageRank, traffic, update frequency) and drops it into one of several priority queues. A selector picks front queues randomly with a bias toward high priority — strict ordering starves the low-priority queues forever.
Where it lives. The frontier holds hundreds of millions of URLs. Pure memory is not durable or big enough; pure disk is too slow. Hybrid: bulk on disk, in-memory enqueue/dequeue buffers flushed periodically.
Candidates conflate these constantly. URL-seen runs on every extracted link before it enters the frontier: has this URL been visited or queued already? It prevents re-adds and infinite loops. Content-seen runs on every downloaded document: roughly 30% of the web is duplicate content under different URLs. Compare a 64-bit checksum (MD5/SHA) of the page, never the text itself. The storage math is the same for both: 15B entries × 8-byte checksum = 120 GB per set — it fits on one big server, but plan an LRU cache backed by a persistent store.
A Bloom filter is the tempting optimization for URL-seen: memory-efficient set membership, false positives possible, false negatives impossible. Say the consequence, not the definition: a false positive means the URL is wrongly marked seen, never enqueued, and that page is silently never crawled. You tune the bit-vector size to bound that loss. Naming the consequence is the senior signal.
The sleeper bottleneck is DNS: resolution is synchronous, takes 10–200 ms, and blocks sibling threads. Run your own DNS cache, refreshed by cron, instead of hitting a resolver per request. A courteous crawler fetches and obeys robots.txt — and caches the per-host rules with periodic refresh, never refetching per request. Add short timeouts (give up on slow hosts and move on) and locality (crawl servers near the hosts they crawl).
A full crawl takes weeks; servers will die mid-run. Consistent hashing distributes the URL space by hostname across crawl servers and absorbs adding or replacing a machine. Each server checkpoints its state — frontier queues, both seen-sets — to remote storage periodically; a replacement loads the last snapshot. Partitioning follows the same key: since URLs route by hostname, keep that host's to-visit URLs, URL checksums, and document checksums co-located on the same server, so dedupe checks never leave the box.
A trap is a URL family that generates infinite crawling: example.com/foo/bar/foo/bar/foo/bar/…, calendar pages, symlink cycles. A max-URL-length cap is a partial defense. The honest answer: there is no fully automatic detector. Trap sites reveal themselves as anomalous page-count outliers; a human verifies and adds a custom filter. Claiming a complete automatic solution is overreach, and interviewers probe it. Freshness is the same honesty: you cannot recrawl everything, so recrawl based on each page's update history, and recrawl important pages more often.
One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.
Rough numbers are fine; the method is what gets graded — and the numbers should drive decisions ("120 GB means the seen-set is not a naive per-worker hash map").
How the graph works: the Scheduler seeds and re-seeds the frontier. The Queue (URL frontier) is the hub — priority front queues feeding per-host back queues. Workers each own one back queue, resolve hosts through the DNS cache, fetch pages from the web, and hand raw HTML to the parsing service. Content dedupe gates storage; the URL filter and URL-seen gate the loop edge back into the frontier. Storage and dedupe checks stay off the fetch hot path.
Scheduler (seed URLs, recrawl)
→ Queue (URL frontier: priority front queues → per-host back queues; mark distributed)
→ Worker (HTML downloader fleet; one worker per back queue; mark distributed)
↔ DNS (local resolver cache)
↔ Third-party API (the web servers being crawled; robots.txt honored)
→ Service (content parser + link extractor)
→ Redis (content-seen checksums, hot) ↔ Cassandra (checksum sets, persistent)
→ Blob Store (raw HTML, 30 PB)
→ Service (URL filter)
→ Redis (URL-seen checksums / Bloom filter) ↔ Cassandra
→ Queue (new URLs loop back into the frontier)
Components:
Most links point home: that Wikipedia page links mostly to other wikipedia.org pages. They all route to the same back queue and drain sequentially with delays — the design is what protects the host, not worker goodwill.
A rack dies in week 3 of a 4-week crawl: its checkpoints (frontier queues, both seen-sets) are on remote storage. Consistent hashing shifts its hostnames to the fleet until a replacement restores from the last snapshot. You lose minutes, not three weeks.
A trap URL enters the frontier: /foo/bar/foo/bar/… grows past the max URL length and is dropped. The subtler traps show up as a host with an anomalously huge page count; a human confirms and blacklists it in the URL filter.
Frontier(url, host, priority, enqueued_at) — disk-backed queue files
UrlSeen(url_checksum) — 8-byte checksums, ~120 GB
DocSeen(doc_checksum) — 8-byte checksums, ~120 GB
Documents(url_checksum, blob_key, doc_checksum, fetched_at, status)
RobotsCache(host, rules, fetched_at)
HostQueueMap(host, back_queue_id)
Grokking's numbers instead of Xu's: 15B pages in 4 weeks ≈ 6,200 pages/sec, ~1.5 PB raw ≈ 2.14 PB provisioned at a 70% ceiling. The Mercator worker-loop framing where each worker thread runs the whole pipeline (fetch → document input stream → dedupe → extract → filter → enqueue) instead of separate services. Kafka as the frontier substrate. A Bloom filter versus an exact checksum set for URL-seen. DynamoDB or MongoDB for the checksum sets. What matters is that you can argue the tradeoff.