Design a web crawler

01Problem and scope

A web crawler discovers and retrieves eligible resources by following links from seed URLs. Its engineering responsibilities are durable scheduling, bounded network access, per-origin politeness and recoverable processing of fetched bytes. An origin is a scheme, hostname and port; per-origin politeness limits how frequently and concurrently the crawler requests that site. For example, fetching https://example.org/articles/1 can discover two more URLs that must enter the durable frontier: the stored collection of URLs waiting to be fetched or revisited. A search corpus retains bodies for indexing and reprocessing; link validation, monitoring, mirroring and specialized-media crawls may require different retention and revisit policies.

Begin with one worker and a list of unvisited URLs. Breadth-first traversal uses a first-in-first-out queue to spread discovery; depth-first traversal follows one branch and may reuse a connection. Neither guarantees useful coverage when a site generates endless addresses.

Scope the exercise to a public engineering-article search corpus refreshed on a schedule, subject to site policy and explicit crawl budgets. The crawler must not ignore those restrictions to meet a throughput target. An unbounded, changing web has no reliable global “finished” state; define progress over eligible discovered URLs and freshness targets for prioritized resources.

A parse manifest is a durable record of a parser’s output, including the links it discovered. Keeping that output lets the crawler resume adding links to the frontier after a crash, instead of having to infer whether a downloaded page was fully processed.

Three components protect different work: the frontier remembers unfinished URLs, the egress gate controls requests to each origin, and saved parse manifests preserve discovered links. The bounded example uses U17 discovering U18 and U19 to test those boundaries. Two workers must not overload one origin, and a crash or retry must not silently lose discovery or create uncontrolled duplicate work.

02Functional requirements

1. Accept seeds and discover links: Add seed URLs, follow eligible links, prioritize important/change-prone pages, and assign revisit budgets. Path-ascending discovery may inspect /articles/ and / under the same checks.
2. Enforce crawl policy: Fetch and cache /robots.txt for the crawler's user agent under the Robots Exclusion Protocol. The filename is plural; its rules express crawl policy, not access authorization. RFC 9309.
3. Schedule fetches and revisits: Keep “already seen” distinct from “never fetch again.” Retrieve bounded responses and persist bodies and metadata.
4. Process and export content: Parse supported content and export eligible documents to the search pipeline. Completed URLs record response status, fetch time, content digest and processing generation.
5. Operate a recoverable crawl: Let operators pause a site, inspect failed URLs, change budgets and resume work.

Outcomes that control scheduling

Scope and content handlers

Assume HTTP/HTTPS HTML and 15B discovered eligible pages over four weeks. MIME type identifies the downloaded content kind; handlers remain modular for future protocols/types. Authenticated content, evading restrictions and a literally complete crawl of an infinite changing web are non-goals.

HTML link extraction is the first processor. Later image/video handlers can reuse bytes and metadata without parsing binary content as markup. A link validator might discard bodies after processing; this search corpus retains them for replay and extraction fixes.

03Non-functional requirements

1. Workload: Fetch 15 billion eligible pages over four weeks; assume 100 KB average responses and one-second normal network service time.
2. Availability: 99.9% scheduler availability. A specific site may stop indefinitely when its policy or health requires it.
3. Politeness: Configure per-origin concurrency and spacing. For the worked origin, permit one active fetch and at least two seconds between starts; too few independent origins can limit global throughput.
4. Durable scheduling: Persist accepted frontier items and lease transitions before reporting success. A worker crash may repeat a fetch, but must not permanently lose a URL or duplicate document publication.
5. Replayable extraction: Store raw content durably before marking extraction complete so parser fixes can reprocess it.
6. Recrawl freshness: Define site classes—for example, important articles within one day and low-value pages within a month. One global average can hide neglected sites.
7. Resource bounds: Limit URL length, redirects, compressed/uncompressed body size, fetch time, parser CPU and per-site discovery. A page expanding to gigabytes cannot consume an unlimited worker.
8. Destination safety: Enforce destination restrictions even when doing so slows the crawl.

Processing guarantee

Network uncertainty prevents exactly-once HTTP retrieval. The promised invariant is durable, idempotent processing of accepted work under a polite dispatch policy; retries and content publication must be designed around that boundary.

04Capacity estimates

Worked estimates

Capacity implications and limits

Hundreds of millions of frontier URLs cannot remain in one queue in RAM. Use persistent queues with separate buffered enqueue/dequeue batches. Cache Domain Name System (DNS) address lookups for their allowed time to live (TTL); repeated lookups otherwise waste part of the fetch budget.

With one fetch start every two seconds per origin, 6,200 fetches/s needs at least 12,400 continuously eligible independent origins. If the corpus concentrates on 1,000 such origins, the polite ceiling is roughly 500 starts/s and the four-week target must change. More machines cannot manufacture permission to fetch a site faster.

Assume an average page yields ten candidate links. The URL gate sees about 62,000 candidate links/s before deduplication, often far more than successful new pages. At 200 bytes per retained frontier record, a billion pending URLs is 200 GB before indexes and replication; keep only bounded ready batches in memory. At 620 MB/s, one day of raw payload is about 53.6 TB. Three replicas of the 1.5075 PB logical corpus would exceed 4.5 PB before slack; an erasure-coded cold store can reduce that multiplier with different repair costs.

Little's Law estimates 6,200 in-flight requests at one second, but a ten-second timeout tail can consume many more slots. Use independent global and per-origin limits, and measure connection occupancy rather than assuming worker count equals useful throughput.

05APIs and contracts

Request and response example

These are internal calls between discovery workers, the scheduler and processing workers. A work lease temporarily gives one worker authority to update a particular fetch attempt; its token identifies that attempt. Permission to send network traffic remains subject to the separate origin-policy checks.

enqueue(url, sourceUrl, priority, crawlGeneration)
  → {urlId:U17, state:pending|already_known|rejected}
leaseNext(workerId, capacity)
  → {urlId:U17, attempt:A9, leaseToken:L9, expiresAt, origin}
complete(L9, bodyRef:P84, digest:H4, status:200, parseManifest:M3)
  → {accepted:true, currentState:complete}

The scheduler assigns lease tokens; workers cannot invent completion authority. Every mutation supplies the token and expected attempt. A stale token returns a harmless stale-attempt result and cannot replace a newer completed fetch. Discovery events carry their parent fetch/parse generation, allowing extraction replay without losing provenance. Large extracted link sets go in a durable manifest rather than one unbounded remote procedure call (RPC) between services.

The administrative API supports per-origin pause, priority and revisit policies with audited versions. Fetch results preserve status, redirect chain, headers needed for conditional retrieval, timing and a bounded error category. A 304 response can reference the prior body when the conditional request contract is valid; it is not an empty replacement document.

Public target websites do not receive our internal lease IDs as trust signals. The HTTP fetcher identifies its crawler user agent and uses the applicable site policies. A failed completion RPC is retried with L9 and the same stored body/manifest; it does not require downloading the page again while the lease remains valid.

06Data model and access patterns

The scheduler must remember both URL progress and origin-wide limits. The first three rows show state used to accept and recover URL work; the host schedule coordinates all requests to the same origin, including requests for different URLs.

Preserve canonical URL strings, discovery source, retry count, and next-due time. A hash can accelerate membership checks but cannot reconstruct the URL to fetch. Canonicalization removes fragments and normalizes safe equivalents; dropping every query parameter can incorrectly merge distinct pages. Domain, prefix, and protocol filters enforce crawl scope before enqueueing.

Maintain exact URL membership in a partitioned store, including canonical string, URL ID, current crawl generation, due time, state and attempt. The frontier indexes due work by priority/time within origin ownership. HostSchedule stores next-start time, active requests and policy version. The raw object store keeps immutable body objects; a content-digest index links identical bytes to one processing representation where safe.

Separate fetch metadata from content identity: two addresses can serve identical bytes but have different robots rules, canonical links, timestamps or crawl provenance. Do not erase those URL records merely because body deduplication succeeds. A parser's output manifest records resolved discovered links and extraction version, so downstream publication can be replayed.

Partition scheduling by origin/host responsibility to coordinate politeness. Partition global digest checks by digest to find mirrors across unrelated hosts. This means URL scheduling and content deduplication have different keys and may live on different owners; there is no assumed cross-store transaction. Save each stage’s result, then let the next stage retry from that record without duplicating its effects.

The URL-membership insert and a durable enqueue intention must commit together at the URL authority. If membership and frontier use different stores, insert the URL plus an outbox event in one local transaction, then relay an idempotent (urlId,crawlGeneration) job. A crash after “already known” but before a separate queue send must not strand the URL forever. A repeated discovery returns the existing record and leaves its pending enqueue intention recoverable. The frontier may instead be an index over that same authoritative URL table, avoiding the extra relay in the baseline.

07Basic working design

One durable scheduler and body store

The baseline has one scheduler/worker process, a local durable frontier database and a body directory/object store. A queue chooses an eligible URL, records a lease, checks robots and per-origin time, fetches under limits, stores bytes, parses them and records a durable link manifest. It then marks the attempt complete and feeds manifest entries back to the frontier.

Fetched and parsed recovery stages

For U17, the process records A9 before opening the connection. The body becomes P84, and manifest M3 contains U18 and U19. If it crashes after storing P84 but before completion, P84 is an orphan that can later be collected; U17's durable lease remains recoverable. If it crashes after completion but before enqueuing links, the manifest cursor shows which discovery work remains. A single “visited=true” bit would lose this distinction.

Breadth-first discovery and due recrawls

Use breadth-first order initially to spread discovery, with due-time priority for recrawls. Keep per-origin spacing even on one machine: one worker can still issue rapid sequential requests faster than a site's permitted start interval. DNS caching honors TTL; redirects are revalidated. This small version is already safe to restart and inspect. Distribution is an optimization for independent work, not a substitute for recording processing states.

08Find the baseline flaws

The durable manifests in the baseline already address the crash case below. The remaining throughput problem motivates more workers, while the counterexamples show which safeguards must survive that change and which new coordination is needed across workers.

09Improve the design, step by step

1. Change 1 — persistent partitioned frontier with ready batches. Trigger: billions of pending URLs and a single queue bottleneck. Store full durable state by origin partition, while buffering small enqueue/dequeue batches in memory. This reduces random I/O and supports parallel origins. Costs include queue indexes and recovery checkpoints; a lost ready buffer delays work but cannot lose its durable record. A single embedded database is simpler for a small crawl.

2. Change 2 — asynchronous fetchers behind per-origin dispatch. Trigger: 6,200 required sockets and slow-response tails. Nonblocking fetchers start work only when both the origin’s policy and the crawler’s total connection limit permit it. Throughput increases across origins while one origin remains polite. The cost is lease/egress coordination and more sockets; a replaced dispatcher can overload a host unless the egress gate prevents it from starting more requests. More unconstrained threads are rejected because they do not solve origin scheduling.

3. Change 3 — durable body and parsing pipeline. Trigger: parsing and body writes keep network workers occupied. Fetchers write immutable objects and stage manifests; parser workers consume references asynchronously. This isolates CPU-heavy extraction and permits reprocessing. Costs are extra storage reads and queue latency; malformed or adversarial HTML can repeatedly crash or stall parsers unless parsing is isolated with resource limits and retries are bounded. Inline parsing remains appropriate when pages are tiny and throughput modest.

4. Change 4 — exact membership plus approximate acceleration. Trigger: 62,000 link candidates/s cause repetitive exact lookups. A Bloom filter can quickly identify definite negatives; possible positives still consult the exact URL store when coverage matters. Digest-based body deduplication avoids repeated extraction of mirrors. Costs include filter rebuilds, hashes and extra stores; treating Bloom positives as final can silently drop unseen pages. Choose approximate-only discovery only when the product explicitly accepts that recall loss.

10Detailed architecture

Discovery and scheduling ownership

Seeds and discovered links enter a URL gate that normalizes safe equivalents, checks scope and consults exact membership. Eligible work reaches the persistent frontier. Its scheduler chooses due origins and leases attempts, while a policy service supplies robots and site limits. Fetchers send actual network traffic through an egress gate that enforces destination safety and per-origin dispatch authority.

Eligibility is enforced at network dispatch

The final architecture shows these as separate components because a lease to process U17 is not automatically permission to open a new socket to example.org. The egress layer owns active outbound connections and validates the current dispatch ownership version, called an epoch. On failover, the old network authority must be stopped/fenced, or the new one must conservatively wait through the maximum in-flight timeout before granting conflicting work. A stale application token alone cannot revoke a socket already open on an unfenced machine.

Replayable bytes and extracted manifests

Downloaded bytes go to immutable object storage. A saved fetched-stage record tells parsers which body to process. Parsers save versioned output manifests, send discovered links through the URL gate and send extracted documents to the indexer. A digest index supports global content deduplication. Replicated frontier state and checkpoints preserve pending work; consistent hashing merely helps assign partitions with less movement.

Control changes versus body traffic

Control and data have different scaling: changing a site pause is low-volume but must reach egress enforcement promptly, while link discovery and object writes dominate volume. A paused site can retain its queued URLs without issuing more network requests.

Concrete starting stack

A practical initial stack can use a transactional SQL or embedded database for URL state and enqueue intentions, a bounded asynchronous HTTP client behind the egress gate, and object storage for immutable bodies. A durable message broker is useful when independent fetch/parse pools justify it, but it does not replace state transitions or outbox recovery. DNS safety checks must govern the address actually used by the connection: validate all resolved IPv4/IPv6 destinations and pin an approved address through connect while preserving the correct HTTP host and TLS name. Revalidate redirects and new resolutions; checking one DNS lookup but letting the connection use a second unchecked lookup allows DNS rebinding: the hostname can resolve to an approved public address during the check and an internal address during connection.

11Write path and acknowledgement

Each fetch produces durable artifacts that later stages can replay. In this example, URL U17 is fetched under lease token L9, produces body P84, and yields manifest M3 containing discovered URLs U18 and U19.

At noon, the scheduler admits the example fetch under the following checks.

1. Worker w3 leases U17 as L9 and checks host eligibility/robots rules.
2. DNS resolves the destination; the fetcher downloads its body once under byte/time limits.
3. A replayable document input stream lets processors reread the bytes: small bodies stay in RAM; large bodies spool to a temporary file.
4. Content hash H4 and object ID P84 identify the result. New content proceeds to parsing; duplicate bytes may reuse context-independent parse output, but URL-relative link resolution still runs for each fetched URL.
5. The parser resolves ./2 and ../about to absolute U18/U19; the URL gate filters, checks membership, and durably enqueues new addresses.
6. Completion records P84 and releases L9.

Future image/video MIME handlers can reuse the stream abstraction without pretending their contents are HTML.

Before the network step, the egress gate validates the current origin epoch, safe resolved destination, current robots decision and due time. It reserves the next allowed start and active slot under one authority. A redirect repeats safety/policy checks for its target; it cannot tunnel into a private address because the initial URL was public.

After body storage, the fetched-stage record refers to P84 and the durable attempt identified by lease token L9. A parser writes M3 before completing its stage. A discovery consumer inserts U18/U19 with unique canonical URL keys, records its manifest position and retries safely after a crash. If another page already discovered U18, that insertion returns the existing URL record rather than creating another frontier entry. Completion and manifest consumption are separate recoverable stages, not a distributed transaction across the object store and URL database.

The output document includes URL provenance, fetch timestamp and extraction version. Identical content can share a body object while retaining separate fetch records. That lets a later extractor fix a bug or a recrawl update metadata without fabricating a new network observation.

12Read and delivery path

Workers obtain due work from durable scheduler state and retrieve stored bodies by reference. The path below distinguishes scheduling reads, network eligibility and parser reprocessing.

1. A scheduler reads its next due origin from a durable time/priority index. If example.org is paused, its work remains pending and the scheduler moves to another origin rather than spinning on it.
2. It reads the origin's policy version and selects a due URL whose retry/revisit time has arrived. Within a short transaction, it changes pending to leased, increments attempt and returns L9 with a deadline.
3. The fetcher reads cached robots rules only within their valid policy; missing or expired rules schedule a compliant refresh rather than assuming unrestricted access. Robots error behavior follows the chosen RFC-compliant implementation.
4. DNS resolution uses TTL-aware caching, then the egress layer verifies actual destination addresses and redirect targets. The fetch reads bytes under time and expansion limits; small replayable streams stay in memory and larger ones spool.
5. Parser workers read P84 by object reference and read their extraction-generation manifest state. They can reprocess the same bytes without issuing another HTTP request.
6. Operator status reads aggregate frontier age, recent result and next-due time. They do not mutate visited state or change a worker's lease merely because a dashboard page was opened.

This read path is largely scheduling and object retrieval, not user-facing search. The search engine is a downstream consumer with its own indexing freshness contract.

Robots retrieval has explicit outcomes. A successful response is parsed for the crawler’s user agent. RFC 9309 permits access when robots is unavailable through an HTTP 4xx response, but this crawler still honors throttling and applies backoff for 429. For server/network failure, use the RFC’s unreachable handling; this design conservatively stops new fetches while policy cannot be established. Cached rules normally should not be used beyond 24 hours unless the RFC’s unreachable exception applies. Any redirect used while retrieving robots is still subject to destination-safety controls. A robots allow never authorizes access to a private network.

13Correctness deep dive

Deduplication answers two different questions: have we scheduled this URL, and have we processed these response bytes? URL identity controls discovery, while byte identity can save storage and parsing work. The table separates the authoritative records from filters that only accelerate lookups.

Bloom filters cannot prove completeness

Explicit attempt transitions

Use explicit attempt transitions rather than a boolean visited flag:

Stale fetch completion is rejected

Worker w3 stores P84 and pauses before recording fetched. Its lease expires and w8 gets L10. If w3 resumes, complete(L9,...) compares its token with L10 and rejects the stale mutation. W8 may fetch identical bytes; digest deduplication can reuse storage, but the newer attempt remains authoritative. If w3 had committed fetched before pausing, recovery continues parsing P84 without downloading again. The database transaction decides which durable state exists; wall-clock guesses about the worker do not.

recordFetched(urlId, token, bodyRef):
  update URL
    set state=FETCHED, body=bodyRef
    where id=urlId and state=LEASED and currentToken=token
  require one row changed, or return STALE_ATTEMPT

Atomic discovery and enqueue intention

Equal bytes can yield different resolved links

Body collection versus publication

Cleanup must not delete a body just as a worker saves its reference. Track each staged object under its fetch/parse attempt. The state database either commits the reference or marks the attempt RECLAIMING, blocking later publication before cleanup deletes the bytes. Garbage collection skips bodies and manifests reachable from committed stages. Merely finding no reference in one scan and deleting afterward can race a worker recording FETCHED.

14Failure and recovery

15Operations, security, and cost

Bound crawl traps

Calendar pages, sorted/filter combinations, session URLs, symbolic cycles, spam, and deliberate traps can create endless branches. Bound depth, URL length, redirects, per-site discovery, retries, and response expansion. Google documents how faceted navigation can generate excessive crawlable URL combinations. Crawler guidance.

Destination validation and parser isolation

Reject internal/private destinations and recheck DNS/redirects to prevent server-side request forgery (SSRF), where an attacker makes the crawler contact a destination the attacker could not access directly. Sandbox parsing; protect against compression bombs. Respect throttling and back off. Measure new-page yield, duplicate rate, frontier age, per-host spacing, DNS/fetch latency, error codes, checkpoint lag, and recrawl freshness.

Useful-content and freshness signals

Measure useful new documents per fetched byte, recrawl freshness by priority class, and robots/pause enforcement latency. A high fetch count can hide calendar traps and duplicate mirrors. Track the maximum observed per-origin start rate, not only fleet average. Preserve enough audit metadata to explain why a URL was skipped without logging secret credentials or unrestricted response bodies.

Parsing and retention cost

At 620 MB/s ingress, a parser that rereads every body twice consumes another 1.24 GB/s of storage-read traffic. A replayable stream abstraction avoids duplicate network downloads but does not make repeated object reads free. If content deduplication avoids context-independent parsing for 30% of bytes, it can save roughly 186 MB/s of that parse input under the illustrative workload, at the price of digest computation and lookup traffic. Validate with actual duplicate distribution.

Canonicalizer rollout and replay tests

Canary a new canonicalizer against stored URLs before changing identity rules; an overaggressive query-parameter removal can merge distinct articles permanently. Roll out a new parser generation on existing objects, compare extracted links and document quality, then enable it for new fetches. Recovery tests pause a worker after every stage, corrupt a checkpoint copy and change robots policy while URLs are waiting.

16Decision ledger and limitations

Breadth-first traversal spreads discovery; depth-first traversal may reuse connections and memory locality but risks spending too long in one branch. Priority scheduling beats either blindly when revisit freshness and site importance matter. Global content deduplication saves work across mirrors but must preserve URL-specific provenance. Hash fingerprints require collision analysis and, where completeness matters, exact verification.

The limiting resource may be site permission rather than our infrastructure. When the eligible corpus cannot sustain 6,200 polite fetches/s, revise the four-week goal or scope. Do not call that an autoscaling failure. Similarly, no scheduler can guarantee exhaustive coverage of endlessly generated calendars and faceted URLs; scope budgets make the objective finite and measurable.

17Interview closing

“I model the crawler as a durable frontier and a recoverable processing pipeline. A URL moves through leased, fetched, parsed and complete states, each with a token and durable artifacts. The scheduler partitions by origin, while egress authority enforces robots, safe destinations, spacing and active-request limits. Fetchers store bytes once, parsers produce replayable manifests, and exact URL insertion makes repeated discovery harmless. A stale worker cannot overwrite a newer attempt; a crash may repeat a fetch but cannot silently lose its links.

“I scale independent origins with bounded asynchronous I/O and persistent frontier batches. The costs are duplicate network work, petabyte body storage and coordination around polite failover. More workers do not increase one site's permitted rate. I would next measure the fraction of fetches yielding useful new pages, the number of independently eligible origins, the fetch slots occupied by slow requests, and recovery of a worker paused after body storage.”

If the interviewer changes the goal to continuously monitoring a small set of sites, prioritize revisit scheduling and conditional fetches over broad discovery. If media crawling is added, separate MIME handlers and byte budgets change capacity; the durable stages and destination-safety checks remain. If approximate coverage is acceptable, Bloom-only rejection can be a conscious recall tradeoff, not an unnoticed correctness bug.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.