Design a web crawler

01Define a finite crawl objective

Design a crawler for a public engineering-article search corpus. It accepts seed URLs, downloads eligible HTML, extracts article text and links, and revisits important pages on a schedule. Fetching U17 discovers U18 and U19; both must eventually enter the durable work queue if eligible.

The web is changing and can generate unlimited addresses, so “crawl everything” is not a useful completion condition. Choose a target corpus, site budgets and freshness classes, such as daily revisits for important articles and monthly revisits for low-priority pages. Authenticated content, bypassing restrictions and unrestricted media downloads are outside this exercise.

An origin is a scheme, hostname and port. Enforce configured per-origin concurrency and spacing, and honor robots.txt rules for the crawler’s identified user agent. Robots rules express crawl policy, not permission to access private networks or bypass authentication. A site pause or throttling response can reduce throughput regardless of spare machines.

The promise is recoverable processing, not exactly-once HTTP retrieval. A network timeout may leave the crawler unsure whether a server received the request, so retrying can fetch the same page twice. The design must make repeated scheduling and output processing safe instead of claiming the network eliminates duplication.

Clarify the target corpus and deadline, which pages need revisiting, and what each site permits. If site budgets cannot support the requested completion rate, renegotiate the deadline instead of treating more fetch workers as a solution.

02Functional requirements

Agree on these supported actions before selecting components.

1. Discover eligible URLs. Accept seeds, resolve discovered links in each page’s context and durably schedule eligible new URLs without duplicate initial work.

2. Fetch and extract. Retrieve supported public HTML, retain verified response bodies, extract article text and publish durable link/document manifests.

3. Revisit and control sites. Schedule revisits by priority, apply robots and operator pause rules, and record skipped, failed and retryable outcomes.

4. Resume interrupted stages. Recover pending fetch, parse and discovery work after a worker crash without skipping links whose scheduling never committed.

03Non-functional requirements

Use these as illustrative interview assumptions to agree with the interviewer. Numerical targets require measurement; they are not claims about an existing product or a proven implementation.

1. Finite throughput objective. Target fifteen billion eligible initial pages in 28 days: approximately 6,200 successful new pages/s and 620 MB/s at the assumed 100 KB/page. Retries and revisits require additional capacity; the initial-crawl arithmetic does not pay for them.

2. Politeness before speed. For the worked example allow at most one start per two seconds and one active fetch per origin, or a stricter site/operator limit. At least 12,400 continuously eligible origins are needed for the initial start rate even before retries and revisits.

3. Revisit freshness. Use daily revisits for important articles and monthly revisits for low-priority pages when site policy permits. Track overdue eligible work separately from policy-blocked pages, and revise the service objective when permissions or capacity prevent it.

4. Recoverable work and bytes. Accepted frontier entries and committed stage outputs must survive worker restart or one storage-node failure within the region. Repeated HTTP retrieval is allowed; lost committed discovery work is not.

5. Destination and input safety. Only fetch allowed public HTTP(S) destinations, including after DNS resolution and redirects. Enforce response/decompression/time/parser limits and do not access authenticated or internal resources.

6. Bounded pipeline. Keep ready batches, sockets and parser work bounded. Slow intake when downstream stages fill; useful coverage and revisit age matter more than an unbounded raw request rate.

04Make one worker restartable before adding more

Start with one scheduler/worker, a SQL frontier and durable body storage. The frontier is the collection of URLs waiting to be fetched or revisited. Each row records the canonical URL, state, due time and current attempt. A transaction selects a due URL and marks it leased to the worker for a bounded time.

For U17, the fetch-and-parse path is:

1. Check origin eligibility and destination safety.
2. Download within byte/time limits and store body P84.
3. Save a FETCHED record referring to P84.
4. Parse that body and write manifest M3 containing extracted text and resolved links U18 and U19.

A manifest is durable output that a later process can finish consuming after a crash.

A discovery step inserts U18 and U19 into the frontier under unique URL keys. It records its manifest progress after those insertions complete. Only then is that discovery work finished. The stages distinguish “bytes obtained” from “all discovered work durably scheduled.”

If the process crashes after storing P84 but before recording it, a retry may download again and leave an unused object to clean up. If it crashes after recording FETCHED, processing can continue from P84 without another network request. One visited=true flag cannot express these different recovery actions.

05Check site permission before worker count

Assume fifteen billion eligible pages over 28 days, averaging 100 KB each and one second of network service time. These are planning assumptions, not permission to fetch any particular site at that rate.

At one allowed start every two seconds per origin, sustaining 6,200 starts/s needs at least 12,400 continuously eligible independent origins. One thousand such origins allow only about 500 starts/s. Adding workers cannot remove this constraint.

At 200 bytes per frontier record, one billion pending URLs require 200 GB before indexes and replicas. Keep durable state on storage and only bounded ready batches in memory. Slow-request tails increase connection occupancy beyond the one-second average, so measure timeouts and outstanding sockets as well as successful pages/s.

06Store URLs, fetches and bodies as different identities

Canonicalization converts only safe equivalents, such as removing a fragment that is not sent in an HTTP request. Do not drop every query parameter: two article URLs may legitimately differ by a query value. Preserve the full canonical URL, since a hash cannot reconstruct the address to fetch.

Use a unique exact canonical-URL key for discovery. In the baseline, inserting that row also creates its pending frontier work because the frontier is an index over the same table. If separate queue storage is introduced, save an enqueue intention in the URL transaction and relay it afterward; otherwise a crash between “known” and “queued” can strand the address forever.

Keep successful fetch history separate from revisit scheduling. “Already known” means do not create duplicate discovery work, not “never fetch this URL again.” A changed article must become due under its freshness policy.

07Coordinate requests at the origin boundary

All workers fetching the same origin share one scheduler decision. Before a start, check the current site policy, reserve an active slot and advance nextAllowedStart atomically. One worker’s local sleep does not coordinate another worker’s request to the same site.

Choose one outbound dispatcher per origin partition. It owns the active connections and enforces the configured concurrency and spacing. Parallelism comes from many independent origins. If a dispatcher fails, stop and confirm that its old outbound requests have ended before transferring that origin’s work. The simple interview design accepts delayed crawling during uncertain handoff rather than claiming that a new database token can close an old machine’s socket.

Fetch and cache robots.txt through a standards-compliant implementation. Recheck policy when its cache is no longer valid, and conservatively pause ordinary fetches if policy cannot be established. Handle HTTP throttling and transient failures with delayed retries, not an immediate tight loop. A disallowed URL is a recorded skipped outcome, not a network error to retry aggressively.

Origin names can share the same physical server. Add conservative host/operator budgets where needed and expose a manual pause. The product’s four-week target must be revised if its eligible sites cannot support the required polite rate.

08Treat every destination and response as untrusted

An attacker can place a link that makes the crawler contact an internal service the attacker cannot reach directly. This is server-side request forgery. Reject non-HTTP(S) schemes and private/internal destinations, including unsafe IPv4 and IPv6 results. Validate the address actually used by the connection, not only a preliminary DNS lookup that the HTTP client later resolves differently.

Pin an approved resolved address through connection establishment while preserving the correct HTTP host and TLS hostname. Revalidate every redirect target and new resolution. A public starting URL does not make its redirect to an internal address safe. Cached Domain Name System results may reduce lookup work, but they still need an allowed lifetime and safety validation.

Limit URL length, redirects, response bytes, decompressed size, fetch duration and parser CPU/memory. A compressed response can expand far beyond its transferred size. Sandbox parsing and verify the content type before selecting an HTML handler; a filename extension is not sufficient.

Crawl traps include endless calendars, sort/filter combinations and session URLs. Bound per-site discovery and repeated path patterns, and quarantine explosive origins for inspection. These are coverage decisions as well as resource safeguards: stopping a trap allows useful sites to remain fresh.

09Separate network waiting from parsing work

Partition the frontier by origin so each scheduler owns the timing of its assigned sites. Use asynchronous HTTP workers with bounded global and per-origin connections. They can wait on many unrelated servers without allocating an unbounded thread or process to each request.

As traffic grows, fetchers persist body references and enqueue parsing work through durable stage records. Separate parser workers consume those records, extract documents and links, and publish manifests. This isolates CPU-heavy or malformed HTML from network scheduling and lets a parser fix reprocess retained bytes without downloading again.

Object storage absorbs the large sequential body volume. A search index downstream consumes extracted documents under its own indexing-freshness contract; a fetched page is not automatically searchable. Make each stage slow its input when it cannot keep up; this is backpressure. If parsing or object storage is full, slow new downloads instead of filling local disks or losing bodies already acknowledged as fetched.

Ready queues can be small in-memory batches derived from durable due-time indexes. Losing a batch then delays work rather than deleting it. Replicate and back up frontier/manifest state, and test restoring both pending URLs and partially consumed discovery output. A hash-based placement scheme distributes ownership; it does not supply durability by itself.

For the selected one-node-loss boundary, retain frontier and manifest decisions through durable majority commits across three replicas in independent regional failure domains, with body storage whose acknowledged writes survive one storage-node loss. Budget retries and revisits above the approximately 6,200/s initial-crawl rate; reduce intake or renegotiate the deadline when site budgets or downstream capacity cannot support the combined work.

10Distinguish repeated addresses from repeated bytes

The exact URL store prevents two pages discovering U18 from scheduling duplicate initial work. A body digest answers a different question: did two fetches return identical bytes? Reusing an identical object can save storage and some parsing, but URL provenance and site policy remain separate.

Identical HTML can contain the relative link ./2 on two different sites:

Those bytes resolve to different destination URLs. Cached syntax-level parsing can be reused where valid, but link resolution must still use each response’s effective URL and any valid HTML base element.

A Bloom filter is a compact membership accelerator. Its negative result means an entry was not inserted into that complete filter; a positive result means possibly present. False positives are possible, so a positive cannot be the sole reason to discard a newly discovered URL when coverage matters. Consult the exact store and let its uniqueness constraint decide insertion. A stale or incomplete filter cannot replace that final check either.

Use sufficiently strong digests with integrity or collision verification for body reuse. Digest equality is a useful lookup candidate, not a reason to erase all URL-specific records. Keep the canonical address, fetch time, redirects and source page even when bytes are shared.

11Recover the stage that actually committed

A lease gives one worker the current right to update a URL attempt for a bounded period. Completion includes its attempt token. If worker A pauses and worker B receives a new attempt, A’s late completion is rejected by a conditional database update. That protects state; the separate outbound-dispatch policy protects network politeness.

For discovery, suppose M3 contains U18 and U19:

1. The consumer inserts U18, then crashes.
2. It repeats the manifest after recovery.
3. U18’s unique key returns its existing record.
4. U19 is inserted next.

Advance the manifest cursor only after durable insertion or confirmed membership. Marking U17 visited before saving or consuming its links could permanently lose U19.

If a body object exists but no stage references it, cleanup must first make the associated attempt ineligible to publish before deleting it. A check-then-delete race could otherwise remove bytes just as a worker records FETCHED. Cleanup must keep bodies and manifests still referenced by retained processing stages.

Classify outcomes: transient network errors retry with delay; permanent unsupported content stops; policy disallow skips; repeated parser failures enter an inspectable failed state. Conditional requests may receive 304 Not Modified and reuse the prior valid body; they must not replace it with an empty document.

12Check the design against the requirements

Use the agreed lists to check the finished design. The tests below still need to establish the targets; a proposed mechanism is not a measured result. FR refers to the numbered functional requirements above; NFR refers to the numbered non-functional requirements.

13Rapid revision

Remember: Save the extracted links before recording discovery progress; a downloaded parent is not proof that its children were scheduled.

Track useful new documents per fetched byte, frontier age, revisit freshness, duplicate ratio, parser backlog, per-origin request starts and skipped reasons. A high fetch rate can hide a calendar trap or thousands of duplicate mirrors. Measure the slowest freshness class and site behavior, not only fleet averages.

Close by tracing U17 to stored P84, manifest M3 and durably scheduled U18/U19. Explain what happens if the worker fails after each stage. Then state the main scaling boundary: many independent eligible origins provide parallelism, while one site’s permitted rate remains fixed. The interview design favors recoverability and respectful bounded coverage over an impossible claim to fetch an infinite web exactly once.

Recall the key ideas

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