Web Crawler

Clarifying the requirements

Start by separating what the crawler must do from how well it must do it. The functional core is small and is exactly what the gym grades the rubric on: fetch pages starting from a set of seed URLs, parse each page to extract links, canonicalize and enqueue the new URLs, and deduplicate both URLs and page content so you never do the same work twice. The output is a stream of raw page bodies plus their extracted links, handed to a downstream indexer that is out of scope here.

The non-functional requirements are where this problem lives, and they map one-to-one onto the simulator's SLOs. You need high sustained throughput (the gym's floor is 6,000 fetches per second, surviving a surge to 12,000). You need politeness: rate-limit per host, honor robots.txt and any crawl-delay directive, and never let one popular domain become a denial-of-service victim. You need to not re-fetch or re-store duplicates, because at this scale wasted bandwidth is the dominant cost. And you need fault tolerance, because the run will crash a fetcher and stall the page store mid-crawl and still expect 97 percent of fetches to succeed.

Good clarifying questions to ask the interviewer, each of which changes the design: do we crawl HTML only, or also render JavaScript and fetch assets (renders multiply CPU cost by 10x or more)? What is the freshness policy, one-shot or continuous re-crawl (continuous needs a recrawl scheduler keyed on change rate)? Is politeness per-host, per-IP, or per-domain (hosts behind one IP must share a budget)? How fresh must dedup be, can we tolerate the rare double-fetch (yes, and that buys us enormous simplicity)? Pin these down before drawing boxes.

• Functional: crawl from seeds, extract links, canonicalize and enqueue new URLs, dedup URLs and content.
• Non-functional: sustained throughput at 6,000 to 12,000 pages/sec, per-host politeness plus robots.txt, no duplicate fetch or store, survive node and store failures.
• Explicit SLO targets from the gym: throughput at or above 6,000 rps, availability at or above 97 percent, peak saturation at or below 90 percent, provisioned footprint at or below 9 units.
• Out of scope to state aloud: ranking, indexing, query serving, and JavaScript rendering unless the interviewer asks.

Back-of-the-envelope estimation

Anchor everything on the throughput target. At 6,000 pages per second sustained, you crawl 6,000 times 86,400 equals about 518 million pages per day, and roughly 15.5 billion per month. That is the 'billions of pages' the brief promises, and it is the number that justifies every expensive decision below. The deep-crawl peak of 12,000 pages/sec doubles the instantaneous figures.

Bandwidth. Take an average HTML page at about 100 KB on the wire (real HTML varies wildly, but this is the standard interview figure and is defensible for text-only crawling). At 6,000 pages/sec that is 600 MB/sec, or about 4.8 Gbps of sustained ingest; at the 12,000 peak it is 1.2 GB/sec, near 9.6 Gbps. This is why fetching must be massively parallel and asynchronous: a single fetcher blocked on a slow server's socket is wasted capacity, so each worker juggles hundreds or thousands of in-flight connections.

Storage. 518 million pages per day at 100 KB is about 52 TB per day of raw HTML. HTML compresses well, roughly 5 to 1, so call it about 10 TB per day after compression, and a full multi-billion-page corpus lands in the petabyte range. Multi-kilobyte blobs arriving at thousands of writes per second are exactly what object storage is built for and exactly what a single relational table is not, which decides the storage tier for you.

The seen-URL set. This is the memory of the crawler and it must answer 'have I queued this already?' on every extracted link. Use a bloom filter. The optimal bloom filter needs about 9.6 bits per element for a 1 percent false-positive rate (the formula is minus the natural log of p divided by ln-2 squared). So 1 billion known URLs costs about 1.2 GB of RAM, and 10 billion costs about 12 GB. That fits in memory on a beefy host or, better, sharded across a few. An exact hash set would cost 10x to 50x more, which is the trade-off discussed later.

DNS. Every fetch needs the host's IP, and the resolver is a classic hidden bottleneck. The fan-out is enormous: at 12,000 pages/sec with tens of links extracted per page, you discover on the order of hundreds of thousands of raw URLs per second, the vast majority already seen. With a DNS cache hit ratio of 0.92, only 8 percent of fetches resolve fresh, about 480 per second at the 6,000 base load and roughly 960 per second at the 12,000 peak. Drop the hit ratio to 0.6 and the base figure jumps to 2,400 per second, and the resolver becomes your ceiling. That single ratio is the difference between the gym's starter design and its reference design.

Politeness math closes the loop. If you fetch a given host at most about once per second to be polite, one host yields roughly one page/sec, so sustaining 6,000 pages/sec means you must be actively crawling on the order of 6,000 to 12,000 distinct hosts at any instant. That requirement, more than raw CPU, is what forces the frontier's per-host structure.

High-level architecture

The whole design follows from one decision: decouple discovery from fetching. A naive crawler recurses synchronously as it parses each page, which has no backpressure, no politeness, and a stack that overflows, essentially a self-inflicted denial-of-service. Instead, fetching is driven by a queue, and parsed links flow back into that queue. The gym requires four pieces — a client (seed URLs), a queue (the URL frontier), a worker fleet (fetchers), and a blob store (pages) — and the reference design adds a cache (DNS plus the seen-URL set) in front of the store. That cache is optional to place but decisive in practice: it is what actually clears the availability target when the page store fails, as the dedup deep dive shows.

The flow is a loop. Seed URLs enter the URL frontier. Fetcher workers pull URLs from the frontier, resolve the host through the DNS cache, check the seen-URL set, download the page, parse it, write the raw body to the page store, and push newly discovered, canonicalized, never-before-seen URLs back into the frontier. The frontier is the heart: it is not a plain FIFO, it is a priority structure crossed with per-host politeness queues, which is what the rubric rewards over a single global queue.

Storage splits cleanly by access pattern, which is the answer to 'where do fetched pages and metadata live?'. Raw page bodies are large, write-once, read-rarely blobs, so they go to object storage. URL metadata (status, last-crawled time, content hash, priority) needs fast point lookups and updates, so it goes to a key-value store. DNS responses are cached so the resolver is spared. Putting multi-KB blobs and high-volume metadata into one relational table is the trap answer: it crushes the database on write volume.

Sizing the reference design that clears the SLOs: the frontier is a queue with drain capacity around 30,000 rps and a buffer of about 80,000 so it can absorb the deep-crawl link explosion without dropping. The fetcher fleet is 4 replicas at 4,000 rps each, 16,000 total, which carries the 12,000 peak at about 75 percent utilization and survives a replica crash. The DNS plus seen-URL cache runs at a 0.92 hit ratio. The page store is object storage sized around 25,000 rps. That footprint, one frontier plus four fetcher replicas plus one cache plus one page store, is 7 provisioned units, comfortably under the gym's cost ceiling of 9. The starter design fails precisely because it is undersized on every axis: frontier drain capacity 8,000, fetchers 3 by 2,000 equals 6,000, and a 0.6 DNS hit ratio.

Deep dive 1: the URL frontier (politeness plus priority)

The frontier is the component that makes a crawler a crawler, and it has two jobs that pull in opposite directions: crawl important pages first (priority), and never overwhelm any single host (politeness). The standard solution, the Mercator design, is a two-stage queue. The first stage is a set of front queues, one per priority band; a prioritizer assigns each incoming URL a band based on importance signals like PageRank, domain authority, or refresh need. The second stage is a set of back queues, and here is the key invariant: each back queue holds URLs for exactly one host, and a routing table maps each host to exactly one back queue.

That one-host-per-back-queue invariant is what makes politeness fall out for free. Because a host's URLs all live in a single back queue, and a single worker drains a given back queue at a time, requests to that host are naturally serialized. To enforce crawl-delay, a min-heap orders back queues by their next-eligible fetch time; a worker pops the earliest-eligible queue, fetches one URL, then reinserts the queue with its timestamp pushed forward by the host's crawl-delay (from robots.txt, or a default). A worker is never blocked waiting on a slow host because there are thousands of other eligible back queues to work on. This is the structure that lets you keep 6,000 to 12,000 hosts in flight at once, which the capacity math demanded.

Separating priority from politeness matters because they have different lifetimes and owners. Priority is about which URL to prefer when you have a choice; politeness is a hard constraint about pacing once a host is chosen. Conflating them into one global FIFO, the rubric's partial-credit answer, works in a toy but cannot express either 'crawl news sites more often' or 'this domain wants a 10-second delay.' In the gym, the frontier's generous buffer (around 80,000) maps directly to this: during the deep-crawl stage, each fetched page emits tens of links, so discovery briefly outruns fetching and inflow spikes toward hundreds of thousands of raw URLs per second. The buffer absorbs that transient while dedup strips the already-seen majority; without it, the frontier overflows and drops URLs and you lose coverage. To scale the frontier past one machine, partition it by host hash across shards, which preserves the one-host-per-queue invariant within each shard.

Deep dive 2: deduplication and DNS

Dedup is the other hard part, and it is three layers, not one. The rubric awards points for all three because skipping any one of them wastes bandwidth. Layer one is URL canonicalization before anything is enqueued: lowercase the scheme and host, strip default ports, remove fragments, sort or drop tracking query parameters, and resolve relative links against the base URL. Without this, the same page arrives as a dozen syntactically different URLs and defeats every downstream check.

Layer two is the seen-URL set, the bloom filter sized earlier at about 12 GB for 10 billion URLs. On every extracted link, you test membership; if present, drop it; if absent, add it and enqueue. The defining property is that a bloom filter has false positives but never false negatives, so the only failure mode is occasionally deciding you have already seen a URL you have not, skipping a genuinely new page. For a crawler that is an acceptable, tunable loss (set p to 0.1 percent if coverage matters more than memory), and it is far cheaper than the alternative. Shard the filter by URL hash so the membership check is not a single hot key throttling the whole fleet.

Layer three is content dedup. Distinct URLs routinely serve identical bytes: mirrors, print versions, session-ID-stamped URLs, trailing-slash variants. Hash each fetched body (a 64- or 128-bit hash for exact duplicates, or SimHash if you also want near-duplicate detection) and check it against the content-hash store before writing to object storage. This is the rubric's 'content hash to detect duplicate page bodies,' and it is what stops you from storing the same article ten thousand times.

DNS deserves its own attention because in the gym it is modeled as part of the same cache, and the hit ratio does double duty. First, caching resolutions keyed by host with a sensible TTL spares the resolver: at 0.92 hit, only 8 percent of fetches resolve fresh, versus the 0.6 starter where 40 percent do and the resolver becomes the bottleneck. Second, and more subtly, the simulator counts a cache hit as a served request and forwards only the miss fraction downstream to the page store. So a high hit ratio also means only about 8 percent of traffic depends on the page store at all. That is exactly why, when the run stalls the page store at second 20, the reference design only drops that 8 percent and availability stays near 98 percent, while a 0.6-hit design routes 40 percent of traffic into the dead store and falls to about 91 percent, missing the 97 percent target. The lesson generalizes: aggressive caching is not only a latency and throughput win, it shrinks your blast radius when a downstream dependency fails.

Bottlenecks under load and how to scale

Walk the chaos timeline, because each event targets a real bottleneck. The first pressure is the deep-crawl surge to 2x, around 12,000 pages/sec. The fetcher fleet is the throughput-limiting component, so you scale it horizontally by replicas. Four replicas at 4,000 rps gives 16,000 of capacity, which carries the 12,000 peak at 75 percent utilization, satisfying both the throughput SLO and the saturation ceiling of 90 percent. The starter is undersized on both stages of the pipeline: its frontier drains only 8,000 rps and its fetcher fleet tops out at 6,000, so at the 12,000 peak the frontier alone runs around 150 percent utilization, its buffer overflows, and the fetchers fall further behind — together shedding a large share of the peak load and blowing the saturation ceiling, the throughput floor, and the availability floor at once.

At second 12 a fetcher crashes. This is why you provision N-plus-one, not exactly-N. Losing one of four replicas during the 1.5x stage leaves three by 4,000 equals 12,000 of capacity against roughly 9,000 of offered load, so nothing drops and utilization sits at 75 percent. Size the fleet so that the load you actually meet during a crash still fits with headroom; that single spare replica is the difference between riding out a crash and a cascading failure.

At second 20 the page store stalls (object storage outage). Two things save you. First, decouple writes from fetching so a stalled store does not block workers: fetchers should hand off page bodies through a buffer or async writer and move on, retrying with backoff rather than holding the fetch pipeline hostage. Second, the high DNS-plus-seen hit ratio means only about 8 percent of traffic actually needs the store in this window, so availability holds near 98 percent instead of collapsing. The page store itself scales by being object storage, which is effectively elastic for sequential blob writes; the failure here is availability, not capacity.

At second 28 the DNS resolver slows. Because resolutions are cached at 0.92, the resolver is off the hot path for 92 percent of fetches, so a latency spike there raises tail latency but does not cut throughput or availability. This problem has no latency SLO, which is itself the point: the reason DNS caching exists is so that resolver slowness is a non-event. The general scaling rules: the frontier scales by raising drain capacity and buffer and partitioning by host; the seen-URL filter scales by sharding on URL hash; the fetchers scale by replica count tuned to peak-load-plus-one-failure; and you keep the busiest node under 90 percent so a surge or a crash never tips it over.

Key trade-offs to state out loud

An interviewer is listening for the trade-offs you choose deliberately. Name them and justify each against this problem's economics, where wasted bandwidth and re-work are the dominant costs and the occasional missed or repeated page is cheap.

• Bloom filter versus exact set: the filter is roughly 12 GB for 10 billion URLs but occasionally skips a real page on a false positive; an exact hash set never skips but costs 10x to 50x the memory. For a crawler, accept the rare miss.
• Politeness versus throughput: a stricter crawl-delay lowers per-host rate, which forces you to keep more distinct hosts in flight to hit the same aggregate page rate. Throughput is bought with host diversity, not just more workers.
• Freshness versus cost: re-crawling everything every cycle, the rubric's trap answer, spends almost all bandwidth re-downloading unchanged pages. Re-crawl on a schedule keyed to each page's observed change rate instead.
• Object storage plus key-value versus one relational table: blobs to object storage and metadata to a KV store scales on write volume; a single RDBMS holding multi-KB bodies at thousands of writes per second does not.
• Best-effort dedup versus strong coordination: a sharded bloom filter is eventually consistent, so two workers can briefly double-fetch a URL. That is far cheaper than the distributed locking it would take to guarantee exactly-once, so prefer it.
• N-plus-one headroom versus a lean fleet: the cost SLO caps the footprint at 9 units, so you cannot over-provision blindly. Four fetcher replicas (a 7-unit footprint) is the sweet spot, enough to carry the 12,000 peak and survive one crash without paying for a fifth.
• Priority frontier versus a global FIFO: the FIFO is simpler and earns partial credit, but it cannot express importance or per-host pacing. The two-stage priority-plus-politeness frontier is the standard answer for a reason.