6. Web Crawler Intermediate → Advanced

A. Realistic Interview Prompt

This problem looks like a simple graph-traversal exercise (BFS/DFS over links) until scale and etiquette enter the picture. The two ideas that separate a toy crawler from a real one are: politeness (a crawler that hits one server too fast is indistinguishable from a denial-of-service attack, and will get the crawler's IP blocked) and the URL frontier's prioritization problem (deciding what to crawl next isn't a plain queue — it has to balance fairness across domains, priority, and revisit frequency simultaneously).

B. Difficulty

Intermediate to state ("BFS from seed URLs, download, extract links, repeat") escalating to Advanced the moment politeness, duplicate detection at billions-of-pages scale, and freshness/recrawl scheduling enter — three genuinely distinct sub-problems layered on top of what looks like a simple traversal.

C. What This Problem Tests

• Recognition that "crawl the web" is not one queue — it's a prioritized, per-host-fair scheduling problem (the URL Frontier) with real production precedent (Google's Mercator architecture)
• Understanding of politeness as a hard constraint, not a nice-to-have — treating every host as if it can absorb unlimited concurrent requests is the single most common mistake on this problem
• Judgment on deduplication at two distinct levels — identical URLs (easy) and near-duplicate content reachable via different URLs (harder, needs content fingerprinting)
• Awareness that crawling is a continuous, never-finished process (freshness/recrawl), not a one-time batch job that terminates
• Comfort reasoning about a system with almost no external-facing API at all — this is an internal, autonomous pipeline, a different shape of problem than the previous five

D. Requirements

Functional

1. Given a set of seed URLs, fetch each page, extract outbound links, and add new, previously-unseen URLs to the crawl queue
2. Store downloaded page content (and metadata) for downstream consumption (e.g. indexing — out of scope itself)
3. Respect each site's robots.txt exclusion rules and avoid overloading any single host
4. Periodically recrawl previously-seen pages to keep content fresh

Non-Functional

• Massive scale — this document uses 1 billion pages crawled per month as the standard illustrative target, the same order of magnitude used across most published treatments of this problem
• Politeness — no single host should ever receive a disproportionate concurrent request rate; this is treated as a correctness requirement, not a performance nicety
• Extensibility — new content types (HTML today, PDFs/images/JS-rendered pages later) should be pluggable without a redesign
• Robustness — a single malformed page, redirect loop, or intentionally hostile "crawler trap" must not stall or crash the crawler fleet

Out of scope: the search-indexing/ranking pipeline that consumes crawled content, JavaScript-heavy rendering (assume mostly static HTML, with headless rendering named as a known extension, not designed in depth).

E. Clarifying Questions

F. Assumptions

• Confirmed: seed-based link-following crawl, content storage, robots.txt compliance, periodic recrawl.
• Assumption: primarily static HTML content; headless-rendering for JS-heavy pages is named as an extension (S) rather than designed in depth — the standard simplification most sources make.
• Assumption: near-duplicate content detection is in scope (E's clarifying question 3) — the more interesting, more commonly-tested version of this problem.
• Assumption: adaptive, priority-based recrawl (not a fixed blanket schedule) — reflects how real crawlers (Googlebot) actually behave and gives more to discuss in R.
• Assumption: politeness is enforced per-host via both robots.txt directives and a self-imposed rate limit, even where robots.txt is silent — treated as a floor, not a ceiling, on politeness.

G. Capacity Estimation

H. Core Entities

I. API Design

Internal / operator-facing only — this system has almost no external API:
  POST /v1/seeds              { urls: [...] }         -> enqueue new seed URLs
  GET  /v1/crawl-stats                                -> pages/sec, queue depth, error rate
  POST /v1/hosts/{host}/pause                          -> operator override for a misbehaving/blocking host

Internal worker contract (not externally exposed):
  Frontier.dequeue() -> URL                (respecting per-host politeness, M/N)
  Fetcher.fetch(URL) -> { html, headers, status }
  Parser.extractLinks(html) -> [URL]

Why so little external API surface: unlike every previous problem, a web crawler has no end-user-facing request path at all — it's an autonomous internal pipeline whose only "customers" are the seed-injection interface and whatever downstream system (a search indexer) consumes its output. Naming this explicitly is itself a useful observation — it signals the design should focus entirely on the internal pipeline's throughput and correctness, not on external API ergonomics.

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies the functional requirement in isolation: a single worker, one global FIFO queue of URLs, fetch-parse-enqueue in a loop.

V1 — one queue, one worker. Correct in shape, but has no concept of politeness or fleet parallelism at all.

Why this breaks immediately, not eventually: two failures happen simultaneously the moment this needs to run at real scale. First, a single global FIFO has no per-host awareness — nothing stops the worker from fetching 50 URLs from the same host back-to-back, which is exactly the impolite behavior that gets a crawler IP-banned. Second, one worker fetching one page at a time can never approach 385 pages/sec (G) — network fetch latency alone (hundreds of ms per request) caps a single worker at a few requests/sec. This V1 fails on both scale and etiquette before any refinement is even considered.

K. Data Model & Store Choice

Frontier queue state: a distributed queue/priority-queue system (e.g. Kafka partitioned by host-hash, or a Redis-backed priority structure) — must support per-host partitioning (M) and priority ordering, and losing an in-flight URL on a crash is recoverable (it simply gets rediscovered via a re-crawl or another inbound link), so strict durability isn't required here, the same "ephemeral, recoverable state" reasoning applied to Rate Limiter's counters and Uber's location index.

Crawled content: a blob store (S3-class) for raw page bytes, referenced by a metadata row in a wide-column store keyed by URL, storing content_hash, fetch time, and status — the same "small structured metadata pointing at large blob storage" split used for media in the News Feed and Chat System problems.

Seen-URL and content-fingerprint sets (P): Bloom filters — a probabilistic set membership structure, chosen specifically because billions of URLs make an exact set too large to hold cheaply, and false positives (occasionally skipping a URL that was actually new) are an acceptable trade against the massive space savings, unlike the false negatives a naive set could never produce anyway.

L. End-to-End Flow — One Crawl Cycle

M. Deep Dive 1 — The URL Frontier

Requirement this addresses: directly fixes V1's flaw of treating the crawl queue as one undifferentiated FIFO (J) — this is the central data structure of the entire system, modeled closely on Google's own published Mercator crawler architecture.

Front queues express priority; back queues express per-host fairness. A URL passes through both.

Why two layers, not one: a single priority queue alone would let a host with thousands of high-priority URLs monopolize the crawler (the fairness problem); a single per-host-queue layer alone would have no way to express "crawl this page sooner because it's more important" (the priority problem). The two-layer front-queue/back-queue split — front queues bucket URLs by priority, a selector round-robins fairly across back queues, and each back queue maps to exactly one host — solves both simultaneously: a worker pulling from the back queues can never accidentally starve or flood any single host, regardless of how the front queues prioritized the URLs feeding into them.

Why the host-to-back-queue mapping matters: ensuring exactly one back queue per active host (not per URL) is what makes per-host politeness (N) enforceable at all — if one host's URLs could land in multiple back queues, two different workers could pull from the same host concurrently with no coordination.

N. Deep Dive 2 — Politeness

Requirement this addresses: the politeness NFR (D) — treated as a hard correctness constraint, not a tunable performance knob.

Why this is non-negotiable, not just good manners: a crawler that fetches too aggressively from one host looks identical, from that host's perspective, to a denial-of-service attack — the practical consequence is IP-blocking or legal exposure, either of which ends the crawl for that host (and potentially others sharing the same IP range) permanently. This makes politeness a functional requirement with real failure consequences, not a "nice to have."

• robots.txt compliance — fetched and cached per host, respecting Disallow rules and any explicit Crawl-delay directive; a legitimate crawler simply does not fetch a disallowed path, full stop.
• Self-imposed rate limiting per host — even where robots.txt is silent (many sites don't specify a crawl-delay at all), the crawler enforces its own conservative minimum delay between requests to the same host (G's illustrative "a few seconds" figure) — a floor, not just a ceiling respected only when explicitly told to.
• Enforcement point: the per-host back queue from M is exactly where this check belongs — a worker dequeuing from host X's back queue checks "has enough time passed since the last request to host X" before fetching, and re-queues (with a delay) if not.

O. Deep Dive 3 — Distributed Crawling at Scale

Requirement this addresses: the throughput NFR (D, G) — a single worker (V1) can never approach 385 pages/sec; this requires a real distributed fetcher fleet.

Why parallelism has to come from host diversity, not per-host request rate: politeness (N) caps how fast any one host can be hit, so the entire 385 pages/sec target must be assembled from many different hosts being crawled concurrently, not from crawling any single host faster — directly explaining why the frontier's per-host queue structure (M) isn't just a fairness nicety, it's the mechanism that makes horizontal scaling possible at all.

Many workers pull from many different hosts' back queues concurrently — parallelism via host diversity, not per-host speed.

Why a shared DNS cache matters at this scale: a DNS lookup is a real, non-trivial latency cost per new host encountered; with hundreds of millions of distinct hosts (G), a shared cache across the whole fetcher fleet avoids redundant lookups for hosts multiple workers happen to crawl — a small, concrete optimization with an outsized effect given the sheer host cardinality involved.

P. Deep Dive 4 — Duplicate Detection

Requirement this addresses: avoiding wasted crawl/storage capacity on content already seen — a distinct problem at two different levels.

Why exact hashing (e.g. a plain SHA-256 of page bytes) isn't sufficient on its own: two pages that are substantively identical (the same article with a different ad banner, or a tracking query parameter appended to an otherwise-identical URL) will still produce completely different exact hashes — a fingerprinting scheme like SimHash is deliberately designed so that near-identical inputs produce near-identical fingerprints, making "close enough" content detectable via a cheap similarity comparison rather than requiring exact equality.

Q. Deep Dive 5 — Storage at Scale

Requirement this addresses: the ~500TB/month storage volume from G — this needs to be durable, cheap-per-byte, and organized for whatever downstream consumer (a search indexer) reads it.

Why a blob store, not a database, for the raw content: page HTML is large, write-once, and read infrequently after initial processing — exactly the access pattern object storage is built for and priced for, versus a database optimized for small, frequently-updated rows. The metadata table (URL, content hash, fetch timestamp, storage pointer) stays small and queryable in a proper database, while the bulk bytes live in cheap blob storage — the same pattern used for media in News Feed (R) and Chat System, just applied to crawled HTML instead of user-uploaded photos/video.

Compression: HTML compresses extremely well (large amounts of repetitive markup/whitespace) — storing compressed content routinely cuts the effective storage bill by more than half, a cheap, high-leverage optimization at this volume.

R. Deep Dive 6 — Freshness & Recrawl Scheduling

Requirement this addresses: the recrawl functional requirement (D) — crawling is a continuous process, not a one-time batch job that terminates once the frontier empties.

Why a fixed blanket recrawl interval is the wrong default: a news homepage changes multiple times a day; a static reference page might not change for years — recrawling both on the same fixed schedule wastes enormous capacity on the reference page while under-serving freshness on the news page. An adaptive, priority-based recrawl schedule — estimating each page's historical change frequency (did the content hash (P) change since the last fetch?) and using that to set the next recrawl priority — directly mirrors how real crawlers like Googlebot actually operate, and is a meaningfully stronger answer than a fixed interval.

Why this reuses the Frontier (M) rather than needing a separate scheduling system: a recrawl is simply a URL being re-enqueued into the same front-queue/back-queue structure that handles first-time crawls, just with a priority informed by observed change frequency instead of link-discovery order — one mechanism serving both the initial crawl and the ongoing refresh cycle.

S. Deep Dive 7 — Crawler Traps & Extensibility

Requirement this addresses: the robustness NFR (D) and the extensibility NFR — a crawler operating autonomously across the open, occasionally-hostile web needs defenses that a request/response API serving trusted internal traffic never needed.

• Crawler traps — pages that dynamically generate an effectively infinite number of distinct URLs (e.g. a calendar page with a "next month" link that never terminates), which can trap a naive crawler in an infinite loop on one host forever. Mitigations: a maximum crawl depth per host, a cap on total URLs crawled per host per time window, and heuristics flagging suspiciously repetitive URL patterns (e.g. an ever-growing query string) for manual review or exclusion.
• Redirect loops — two or more URLs redirecting to each other indefinitely; mitigated with a hard cap on redirect-chain length before abandoning the fetch.
• Extensibility for new content types — the parser stage (L) is deliberately a pluggable interface (extractLinks(content) -> [URL]) rather than HTML-specific logic baked into the fetch loop, so adding a PDF parser or a headless-browser renderer for JS-heavy pages (E's clarifying question 5) is a new implementation of the same interface, not a rearchitecture of the pipeline.

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

• V1 — single worker, single global queue (J): no politeness, no real parallelism.
• V2 — per-host back queues + priority front queues: introduces fairness and prioritization simultaneously (M).
• V3 — enforced per-host rate limiting + robots.txt compliance: makes the crawler actually polite, not just theoretically capable of being (N).
• V4 — distributed fetcher fleet + shared DNS cache: hits the real throughput target via host-diversity parallelism (O).
• V5 — Bloom-filter URL dedup + content fingerprinting: avoids wasted crawl/storage capacity on already-seen content (P).
• V6 — blob store + compressed metadata-indexed storage: sustains the ~500TB/month volume durably and cheaply (Q).
• V7 — adaptive, change-frequency-driven recrawl: turns the crawler into a continuous, self-tuning process instead of a one-shot batch job (R).
• V8 — trap detection + pluggable content parsers: hardens the crawler against the open web's hostile/unusual edge cases (S).

What stays stable throughout: the Frontier's dequeue/enqueue contract from L — every version underneath changes without the fetch-parse-store loop's shape needing to change.

V. Consistency Model

Almost the entire system is best-effort and eventually consistent by nature — losing a queued URL on a crash just means it's rediscovered later via another inbound link or the next recrawl cycle (R); a duplicate slipping through the Bloom filter's false-positive/negative edge cases causes, at worst, one wasted or skipped fetch, not a correctness failure anyone downstream would notice. There is no analogous "one atomic step" requirement here the way Rate Limiter or Uber had — this system's entire design philosophy is that individual failures are cheap and recoverable, so no component needs strong coordination guarantees.

W. Failure Scenarios

• A fetcher worker crashes mid-fetch: the URL simply isn't dequeued successfully and remains available in its back queue (or times out and is retried) — no special recovery logic needed, matching V's eventually-consistent philosophy.
• A host starts returning errors or blocking the crawler's IP: back off that host's queue (exponential backoff, or an operator-triggered pause via the API in I) rather than continuing to hammer a host that's actively rejecting requests.
• A crawler trap is entered: per-host depth/URL-count caps (S) bound the damage to that one host rather than consuming fleet-wide capacity indefinitely.
• The dedup Bloom filter produces a false positive (treats a genuinely new URL as already seen): a bounded, accepted loss — that one URL is missed, but the overall crawl continues unaffected, and it may still be discovered again via another link.
• DNS resolution fails for a host: that host's URLs are requeued with backoff rather than blocking the worker or the shared DNS cache for other hosts.

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• A single undifferentiated FIFO queue with no per-host structure. Works in a small demo; is both impolite and unable to scale the instant real hosts and real volume are involved — the most common mistake specifically on this problem.
• Ignoring politeness entirely, or treating it as a "nice to have." Leads directly to IP-blocking in the real world — a design that "works" until the very first host it actually overwhelms.
• Exact-hash-only duplicate detection presented as sufficient. Misses the extremely common case of near-identical content reachable via cosmetically different URLs.
• Modeling the crawl as a one-time batch job that terminates. Misses that a real crawler is a continuous process requiring ongoing freshness/recrawl scheduling, not a job with a defined "done" state.
• No defense against crawler traps or redirect loops. A single hostile or misconfigured host can consume unbounded crawler capacity indefinitely without an explicit cap.

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: "BFS from seed URLs with one queue" with no mention of politeness, scale, or duplicate content at all.
• Mid-level: proposes a distributed fetcher fleet and basic robots.txt compliance, but treats the frontier as one undifferentiated queue.
• Senior: proactively designs the front-queue/back-queue frontier structure for fairness+priority; names both levels of duplicate detection (URL and content) without being prompted; treats politeness as a hard constraint with real consequences.
• Staff+: discusses adaptive recrawl scheduling and crawler-trap defenses unprompted; reasons about the DNS-caching and host-diversity-driven parallelism angle; recognizes and names the near-total absence of external API surface as a defining trait of this problem's shape.

AC. Interview Simulation

AD. Online Solution Comparison

AE. Interview Cheat Sheet