Knowledge Guide
Home › Hands-On Builds › SD Design Labs

Design a Web Crawler

Design a Web Crawler (large-scale, polite, deduplicated)

The interview version sounds trivial: "BFS the web — pull a URL off a queue, fetch it, extract links, push the new ones, keep a visited set so I don't loop." That's a correct graph traversal and a completely broken crawler, and it breaks in three ways the instant it meets the real web. (1) The visited set won't fit in RAM. A search-scale crawl tracks on the order of 15 billion URLs; even at a stingy 8-byte hash per URL that's 120 GB of raw keys (we compute this below), and a real hash table's pointer/load-factor overhead pushes it past 300 GB — your process OOMs long before the crawl finishes. (2) No politeness means you DoS a host and get banned. A plain FIFO queue happily lets 6,200 fetchers hammer whichever host happens to sit at the front — a big site like Wikipedia can have millions of pages clustered there, so you fire hundreds of requests per second at one server, blow past the ~1 req/s a crawler is expected to use, trip its rate limiter, and earn a permanent IP ban (you've now both attacked them and lost the ability to crawl them). (3) You re-fetch the same content forever. A calendar page linking ?date=2026-07-12 → ?date=2026-07-13 → … is an infinite space of distinct URLs; session-id URLs (?sid=random) make one page look like a million new ones. The naive crawler follows them until the heat death of the universe, starving every other site. This lab derives the design — frontier, fetcher pool, dedup, store — that survives all three.

1. The Trap — watch the naive BFS break

Here is the "obvious" crawler, and exactly where each line detonates at scale:

// NAIVE — a textbook graph BFS pointed at the web
Queue<String> frontier = new LinkedList<>(seeds);
Set<String> visited = new HashSet<>();          // (1) in-memory: dies at ~10^8 URLs
while (!frontier.isEmpty()) {
    String url = frontier.poll();                 // (2) plain FIFO: no per-host fairness
    if (visited.contains(url)) continue;
    visited.add(url);
    String html = httpGet(url);                   // (2) hammers whatever host is at the head
    for (String link : extractLinks(html)) {
        if (!visited.contains(link))              // (3) URL-dedup only: same content, new URL = re-crawl
            frontier.add(link);
    }
}

None of these are bugs you patch with a bigger machine. They're the reason a crawler is a distributed systems problem, not a data-structures problem. Feel the pain first; the rest of the lab removes it piece by piece.

2. Scope it like a senior (ask before you design)

Before drawing a box, pin these down — each one changes the architecture:

3. Reason to the design (derive it, don't recite it)

Attempt 1 — the naive BFS above. Dies on memory, politeness, and content identity (§1). Keep the shape (a work queue + a seen-check + a fetch/parse loop) and fix each failure.

Attempt 2 — make the queue polite: split the frontier. The queue can't be one FIFO, because FIFO order couples "what's important to crawl next" with "which host am I allowed to hit right now." Split it into two stages. Front queues hold URLs by priority (important/fresh pages first). A router pulls from the front and drops each URL into a back queue keyed by host — one queue per host. A fixed pool of workers each owns some back queues, and each host queue has its own next-allowed-fetch timestamp (from our default rate or the site's Crawl-delay). A worker only pulls from a host queue whose timer has elapsed. Now politeness is structural: because all of a host's URLs funnel through one back queue with one timer, it is physically impossible to exceed that host's rate no matter how many workers exist. This is the crux of the frontier design — it's a priority queue and a per-host rate limiter fused together.

Attempt 3 — make the seen-set fit: don't store URLs, approximate them. An exact in-RAM set of 15 B URLs is 120 GB+ (below) — doesn't fit. Two ways out: (a) put the exact set on disk / shard it across many nodes (correct, but every link check is now a disk or network round-trip — and we extract tens of links per page at 6,200 pages/s, so that's hundreds of thousands of lookups/s); or (b) accept a Bloom filter — a probabilistic set that says "definitely-new" or "probably-seen" in ~27 GB (below), fits in RAM, at the cost of a small false-positive rate. A false positive means we think we've seen a URL we haven't → we skip a genuinely new page → tiny coverage loss, which we already scoped as acceptable. A Bloom filter cannot produce a false negative, so it never re-crawls something it has truly seen. This is the second crux: the seen-set's memory budget is what forces the probabilistic structure.

Attempt 4 — catch duplicate content, not just duplicate URLs. The URL seen-set does nothing for "same page, different URL" (mirrors, session ids, trap parameters). So after parsing, compute a content fingerprint (hash of normalized text; a similarity hash like SimHash for near-duplicates) and skip storing/re-expanding content we've already indexed. URL dedup saves fetch bandwidth on links we've queued; content dedup saves storage and stops trap-fed re-indexing.

Attempt 5 — distribute it, and shard by host, not by URL. One machine can't hold the frontier (billions of URLs, disk-backed) or the seen-set. Shard both. The key insight: shard by host-hash, not URL-hash. Because politeness is per-host, co-locating all of a host's URLs on one shard lets that shard enforce the host's rate limit locally with zero cross-node coordination. Shard by URL-hash and a single host's URLs scatter across every node → you'd need global coordination to rate-limit that host, which is exactly the coordination host-sharding avoids. That gives us the full design: seeds → sharded frontier → fetcher pool (with DNS + robots.txt caches) → parser → content-fingerprint dedup + store, and URL dedup (sharded Bloom filter) re-injecting unseen links into the frontier.

4. Build it — the HLD design worksheet

This is the artifact you'd produce on the whiteboard. Work it top-down; every number is traced, not asserted — recompute them before an interview.

Functional requirements

Non-functional requirements (these are the hard part)

Back-of-envelope estimation (BOTE)

Component / API sketch (internal — a crawler has no public write API)

Frontier.add(url, priority)        // dedup-checked before it ever lands here
Frontier.nextForWorker(workerId)   // returns a URL whose host timer has elapsed, else blocks
Frontier.setHostDelay(host, secs)  // from robots.txt Crawl-delay
SeenSet.checkAndAdd(url) -> bool    // Bloom: false = definitely new (enqueue); true = probably seen (drop)
Content.storeIfNew(fingerprint, body) -> bool   // content-hash dedup
Robots.allowed(host, path) -> bool  // cached per host, TTL

Data model & partitioning

High-level diagram

The crawl is a loop, not a pipeline: seeds prime the frontier (priority front-queues + per-host politeness back-queues, disk-backed, host-sharded); the fetcher pool (with DNS + robots.txt caches) pulls only URLs whose host timer has elapsed and does the HTTP GET; the parser canonicalizes and extracts links; content goes to the store after a content-fingerprint dedup check; extracted URLs hit the Bloom-filter seen-set, and only the unseen ones are re-injected into the frontier — closing the loop.

Web-crawler HLD: seed URLs feed a disk-backed URL frontier sharded by host-hash with priority front-queues and per-host politeness back-queues; a fetcher pool with a DNS and robots.txt cache pulls rate-limited URLs and does HTTP GETs against the open web; a parser canonicalizes and extracts links; content is written to an S3/HDFS store with content-fingerprint dedup; extracted URLs are checked against a ~27 GB Bloom-filter seen-set sharded by host-hash, and unseen URLs are re-injected into the frontier to continue the crawl loop.
Web-crawler HLD: seed URLs feed a disk-backed URL frontier sharded by host-hash with priority front-queues and per-host politeness back-queues; a fetcher pool with a DNS and robots.txt cache pulls rate-limited URLs and does HTTP GETs against the open web; a parser canonicalizes and extracts links; content is written to an S3/HDFS store with content-fingerprint dedup; extracted URLs are checked against a ~27 GB Bloom-filter seen-set sharded by host-hash, and unseen URLs are re-injected into the frontier to continue the crawl loop.

Rubric — what a strong answer hits

5. Break it — three traced failures

1. Politeness violation → self-DoS → host ban. Ship the plain FIFO frontier. Suppose a large host (say a wiki) has ~10% of the URLs sitting near the queue head. With 6,200 fetchers pulling in order, ~10% × 6,200 = ~620 requests/second aimed at one server. Most sites expect a crawler at ≤1 req/s; 620× over that trips their WAF/rate limiter, which returns 429/503 and then null-routes your crawler's IP block — within minutes. You've DoS'd them and lost the ability to ever crawl them. Fix: the per-host back-queue + timer (§3, Attempt 2) makes 620 req/s to one host physically impossible — that host drains at 1 req/s regardless of fleet size, and the extra workers move on to other hosts.

2. Seen-set doesn't fit RAM → the Bloom-filter false-positive trade-off, traced. Insist on an exact in-memory set: 15 B URLs × 8 B = 120 GB raw, ~300 GB with hash-table overhead — a 128 GB box OOMs, and even a 256 GB box dies as the crawl grows. Push the exact set to disk instead and every one of the hundreds-of-thousands-of-links/s checks becomes a disk seek → the frontier starves. The Bloom filter fits the whole thing in 27 GB, but you now eat a p=0.1% false-positive rate: 0.1% × (new URLs seen) genuinely-new pages get misjudged "already seen" and silently skipped → ~0.1% permanent coverage loss. That is the trade: 27 GB in RAM buys you a 0.1% blind spot. Acceptable for web search; if not, spend more bits (p=0.01% → ~19 bits/URL → ~36 GB) or front the Bloom with an exact disk check only on the rare "probably seen" hits.

3. Crawl trap / infinite URL space. A calendar links /cal?d=2026-07-12 → /cal?d=2026-07-13 → … forever; each URL is genuinely new to the seen-set, so the frontier fills with one host's synthetic URLs and every other site starves. Worse, session-id URLs (?sid=abc123) make one page appear as unbounded distinct URLs → the URL seen-set can't help (they really are different strings). Two defenses stack: (a) bound the space — max crawl depth per host + a per-host URL budget + heuristics that flag high-fan-out parameters; (b) content-fingerprint dedup (§3, Attempt 4) catches the session-id case the URL set can't: the pages are byte-identical, so after the first fetch the fingerprint says "already stored," and we stop re-expanding that trap even though every URL looks new.

6. Optimise — with trade-offs

Each row: what the choice buys, what it costs, and when to pick it over the named alternative.

DecisionOption AOption BPick when
Frontier orderingPlain BFS FIFO queuePriority front-queues + per-host politeness back-queuesAlways B for a real crawler — FIFO couples importance with host-fairness and self-DoSes (Break It #1). FIFO is fine only for a toy single-host crawl where politeness is moot.
URL dedup structureExact hash set (on disk / sharded)Bloom filter (in RAM)Bloom when the seen-set exceeds RAM and a ~0.1% coverage loss is acceptable (search). Exact set when you cannot tolerate any missed URL (e.g. crawling your own site for an audit) and can afford the disk/shard round-trip per check.
Duplicate detectionURL-only dedupURL dedup + content fingerprint (SimHash for near-dups)Add content dedup whenever mirrors/session-ids/traps exist (i.e. the real web) — URL dedup alone re-stores identical content under new URLs. URL-only suffices only in a closed, canonical-URL corpus.
Distributed partitioningShard by URL-hashShard by host-hashHost-hash almost always: it co-locates a host's URLs so politeness is enforced locally with no coordination. URL-hash spreads load more evenly but scatters a host across all shards → needs global rate-limit coordination. See Consistent Hashing for adding shards without a full reshuffle.
Re-crawl schedulingUniform (re-crawl everything on a fixed cycle)Adaptive by estimated change rate + conditional GET (If-Modified-Since/ETag → 304)Adaptive when freshness matters and change rates vary wildly (they do: news vs archived docs). Uniform only if content changes at a roughly uniform rate, which is rarely true.

7. Defend under drilling

Q1 — "With a distributed fleet, how do you stop two workers from hammering the same host?"
The frontier is sharded by hash(host), so every URL of a given host lives on exactly one shard and drains through exactly one per-host back-queue with one next-allowed-fetch timer. Politeness is therefore enforced locally, with zero cross-node coordination — it's structurally impossible for two workers to exceed the host's rate, because only the owner of that host's queue ever dispatches its URLs, and only when the timer has elapsed. robots.txt/Crawl-delay is cached per host and feeds that timer.

Q2 — "Your Bloom filter has false positives. Isn't dropping real URLs a bug?"
It's a deliberate, bounded trade. A false positive means we skip a genuinely-new URL → ~0.1% coverage loss at p=0.1%. Crucially a Bloom filter has no false negatives, so we never re-crawl something truly seen (which would waste far more budget). If 0.1% is too high, I spend more bits (p=0.01% → ~36 GB) or use the Bloom as a cheap front filter and do an exact disk lookup only on the rare "probably seen" hit — trading a little latency for exactness. See the Bloom sizing/FPR deep dive.

Q3 — "How do you keep the index fresh / schedule re-crawls?"
Not uniformly. Estimate each page's change rate from observed history (a news homepage changes in minutes; an archived PDF in years) and set its re-crawl priority in the frontier accordingly — high-churn pages ride the front queues, stable pages sink. On re-fetch, send a conditional GET (If-Modified-Since/ETag); a 304 Not Modified costs almost no bandwidth and confirms freshness without re-downloading. That decouples "how often we check" from "how much we transfer." Full treatment: Web Crawler Freshness.

Q4 — "How do you avoid crawling duplicate / mirror content?"
Two layers. Canonicalization before dedup: honor rel=canonical, strip tracking/session params, normalize scheme/case/trailing-slash — so many "different" URLs collapse to one before they hit the seen-set. Content fingerprinting after fetch: hash the normalized content (and a SimHash for near-duplicates) so mirror sites and session-id traps serving identical bytes are detected as duplicates and neither re-stored nor re-expanded, even when their URLs are genuinely distinct. URL dedup can't catch those; content dedup is precisely what does.

Q5 — "A single giant host (millions of pages) — doesn't its shard become a bottleneck?"
Politeness already caps that host at ~1 req/s, so a giant site is inherently spread over time, not parallelized — its shard isn't CPU/IO-hot, it's just long-lived. We assign the host a crawl budget/priority so it can't monopolize the cycle, and if one host is truly enormous we sub-partition it by path-prefix into several logical "hosts," each with its own polite queue, so the work parallelizes without ever exceeding the site's tolerated rate.

Q6 — the 100× escalation: "Now crawl 1.5 trillion pages per cycle."
Re-run the BOTE at 100×. Fetch rate → ~620,000 pages/s; bandwidth → ~500 Gbps (now a multi-datacenter, many-NIC problem); storage → ~150 PB/cycle. The seen-set is the sharp edge: Bloom at 1.5×10¹² × 14.4 bits = ~2.7 TB — no longer one box, so shard the Bloom across tens of nodes by host-hash (same key as the frontier, so a worker's host set maps to one Bloom shard → still a local check). New bottleneck that didn't bite at 1×: DNS — 620K fetches/s means DNS resolution itself needs a dedicated caching-resolver fleet or you melt your upstream resolver. The frontier goes multi-datacenter, partitioned by host so a host is still owned by one region for politeness. The design doesn't change shape — host-sharding is what lets it scale linearly — but DNS, cross-DC frontier, and Bloom sharding move from footnotes to first-class components.

8. You can now defend

Re-authored/Deepened for this guide. Model-answer reading: Designing a Web Crawler — Frontier, Dedup & Politeness, Traced; Designing a Web Crawler; Web Crawler Freshness (System Design Problems). Building blocks cross-referenced: Bloom Filters (sizing & FPR) and Consistent Hashing.

🤖 Don't fully get this? Learn it with Claude

Stuck on Design a Web Crawler? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Design a Web Crawler** (Hands-On Builds) and want to truly understand it. Explain Design a Web Crawler from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Design a Web Crawler** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Design a Web Crawler** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Design a Web Crawler** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design Instagram / News FeedDesign WhatsApp / Chat →