Design a web crawler

01Functional requirements

A web crawler starts from a few page URLs, fetches them and discovers links to visit next. Its main challenge is choosing safe, useful work at a rate each site can tolerate. An origin is the combination of scheme, host and port, such as https://a.example; all paths at that origin share our sample request allowance.

1. FR1: Accept bounded crawl jobs. Let an authorized operator submit starting URLs, permitted public origins and finite page, depth and byte budgets. The operator can inspect status or cancel the dispatch of new fetch work.

2. FR2: Discover and fetch pages. Fetch eligible HTTP/HTTPS HTML pages, follow permitted links relative to each final page URL and record robots denials, errors and oversized responses as outcomes.

3. FR3: Control duplicate work. Check the exact stored URL record to avoid scheduling the same work twice accidentally. Reuse verified identical response bodies, while keeping each URL’s fetch history, cache validators and base for resolving relative links.

4. FR4: Recover durable progress. Persist which fetch attempt owns the work, its accepted result and any links still needing processing. A worker crash can then be retried, while a late result from a replaced attempt cannot overwrite newer accepted work.

5. FR5: Revisit and propagate changes. Schedule known URLs again when they are due for a revisit. Use returned cache validators, such as an entity tag, to ask whether a stored response has changed. Record changed or missing pages for downstream consumers.

Out of scope

• Signing into accounts, bypassing access restrictions or executing page scripts.
• FTP or arbitrary media parsing in the baseline.
• A promise to visit every possible URL; traps and infinite address spaces remain bounded by declared scope and budgets.

Example: Call https://a.example origin A and https://b.example origin B. The starting pages are A/a and B/c. A discovered link to A/b can become new work, but it shares origin A’s request allowance with A/a.

02Nonfunctional requirements

Planning load: 100 million fetches/day averaging 200 KB; aggregate throughput requires enough independently eligible origins. These are proposed interview targets to validate under the stated conditions.

1. NFR1: Shared origin politeness. The sample policy allows at most one unfinished HTTP request and one start per two seconds per origin(scheme, host and port), unless another restriction is stricter. All workers share that allowance; replacing a worker does not free a slot while its old request may still run.

2. NFR2: Robots and scope. Every page or robots request must stay inside the job’s current scope and applicable rules. Before fetching a page, apply robots rules for this crawler’s user-agent name and the page path. A network/server failure fetching robots records an unreachable state and waits before retrying; it is not unrestricted permission. Robots does not define the sample rate limit or grant login access.

3. NFR3: Durable recovery. A worker crash must not permanently lose accepted URL work. Save the attempt, result and required follow-up work so another process can resume. Retrying may repeat network requests, but a replaced worker’s late result must not overwrite the current accepted outcome.

4. NFR4: Network safety. Connect only to approved public IP addresses obtained from name resolution. For HTTPS, still verify that the certificate matches the requested hostname. Repeat safety checks on every redirect, including robots requests: checking the first hostname does not authorize a later connection into a private network.

5. NFR5: Bounded resources. Enforce job limits on pages, link depth and total bytes. Cap a sample response at 2 MB transferred, separately cap bytes after decompression, and limit redirects and parsing time. Record or reject violations rather than keeping unlimited waiting work.

6. NFR6: Useful freshness. For an important news class, target one-hour revisits when its origin is eligible. Record overdue work caused by denial, overload or finite capacity; never break origin policy to satisfy the freshness target.

03Size useful parallelism

The target is 100 million fetches/day averaging 200 KB each. Use decimal bytes and include enough different eligible origins; extra workers cannot make one site accept requests faster.

1. Fetch rate. 100,000,000 ÷86,400 ≈1,157 fetches/second, rounded to 1,160 for planning. Test the complete fetch-and-parse pipeline, not just opening sockets.
2. Body traffic. 100 million ×200 KB =20 TB/day. Dividing by 86,400 gives about 231 MB/second before retries, robots requests and protocol overhead. Network transfer and retained bodies can dominate cost.
3. Open requests. At one-second mean fetch duration, 1,160 starts/second ×1 second ≈1,160 simultaneous requests. Slower pages need more slots for the same total rate, while each origin still keeps its own timing limit.
4. Origin diversity. One start per two seconds is 0.5 starts/second per origin. Reaching 1,160/second requires at least 1,160 ÷0.5 =2,320 continuously eligible origins under this allowance. A million queued links on one origin do not supply that diversity.
5. URL history. One billion known URLs at 100 bytes each require 100 GB raw, before indexes and copies. Keep exact records on durable indexed storage; a small approximate filter cannot replace their scheduling state.
6. Active scheduling. Ten million due/queued entries at 200 bytes each are 2 GB raw. Size this working set separately from all historical URLs.
7. Body retention. Saving every raw body for 30 days would use 20 TB ×30 =600 TB before copies and compression. Choose retention deliberately. Conditional revisits can save transferred bytes, and duplicate bodies can share storage, but each URL still needs its own status and future schedule.

04Define operator and worker contracts

An authorized operator submits a finite job. The job handler checks its scope and budgets, saves it, and returns j81, the identifier used to inspect that same job later. This is not a public proxy for arbitrary URLs.

POST /crawl-jobs
Idempotency-Key: crawl-81
Content-Type: application/json

{"seeds":["https://a.example/a","https://b.example/c"],"allowedOrigins":["https://a.example","https://b.example"],"maxPages":10000,"maxDepth":5,"maxResponseBytes":2000000}

{"jobId":"j81","state":"queued","acceptedSeeds":2}

1. Submit once. Return 202 after retaining the job and accepted starting URLs. The idempotency key crawl-81 identifies this request; matching retries return j81, while a changed payload conflicts with 409.
2. Validate the request. Return 400 for invalid scope,403 for denied operator access and 429 when admission budgets are exhausted. The two example origins limit where the job may fetch.
3. Inspect or cancel. GET /crawl-jobs/j81 returns saved completed/queued/error counts and a restart checkpoint. Authenticated cancellation stops dispatching new work; it does not claim that already sent network requests vanished. Apply the same operator access check to status and cancellation.
4. Dispatch a saved attempt. An internal worker receives {"attemptId":"f17","url":"https://a.example/a","originEpoch":8,"leaseUntil":"..."}. Here f17 names this fetch attempt,8 is its origin-owner write-permission number, and the lease deadline limits how long that attempt owns the stored work.
5. Acknowledge the same attempt. The worker returns f17’s HTTP outcome, validators, staged body reference and required parsing/discovery work. A retry uses f17 again. The store compares it with the current attempt and permission before accepting it; an old worker cannot replace a newer result.
6. Keep network ownership separate. Expiring that work lease does not cancel HTTP. The origin’s network slot stays reserved until the old request is known closed or a hard request deadline enforced by the network client/egress has passed. Do not dispatch a replacement while closure is uncertain.

05Separate URL, origin, attempt and body state

The scheduler needs more than a queue of strings. Its database stores every URL’s progress and each origin’s next allowed start. That durable inventory of work is the frontier.

• The job handler saves scope, budgets and the original submission result. Those records let the operator repeat a request without creating another job.
• The scheduler finds due origins and URLs using indexes. It checks the origin’s next start time and occupied request slot, then records the selected attempt and new timing together in one transaction, or through one equivalent origin owner.
• The attempt record names the URL, lease deadline and accepted result. When responsibility changes, a controller changes the stored write-permission number, such as 8 to 9. Result-saving code rejects a worker still carrying 8 once 9 is current. This explicit permission number is called an epoch.
• The body store keeps verified bytes separately from URL status. A content hash is a fingerprint used to find possible identical bodies; the URL record retains its own final URL, validators and fetch time.
• The result transaction saves the body reference and required parse work before claiming completion. A relay can discover that saved work after a crash and send it to parsers later. Parser results also check the expected attempt before changing current URL state.

Normalize fetch URLs cautiously. Lowercasing a hostname or removing a fragment is different from discarding a meaningful query parameter or changing a case-sensitive path.

06Build the safe fetch loop

Start with one scheduler, a durable frontier database and a worker that fetches and parses. The scheduler chooses work; the worker performs an allowed network request and extracts links.

1. Save the starting URLs. The job handler inserts A/a and B/c with due times and the job’s limits. A database uniqueness rule on normalized fetch URL prevents two simultaneous discoveries from creating duplicate scheduling records.
2. Prepare origin policy. The scheduler reads cached robots rules for the crawler’s user agent. If a policy must be fetched, schedule a guarded robots request first, using the same scope, address, timing and concurrency restrictions as other network work. A page waits for the applicable policy decision.
3. Reserve one request. The scheduler checks that the URL is due, its origin may start now and no request slot is still occupied. In one transaction it records an attempt, reserves the slot and advances the origin’s next allowed start by the sample two-second interval.
4. Fetch safely. The network client validates the actual destination address, keeps HTTPS hostname checks and streams only supported content within byte and time limits. A redirected hop is another request: recheck destination scope, address and applicable origin allowance instead of following blindly.
5. Parse and record. The worker extracts links, stores a verified body reference and commits the HTTP result plus required discovered-link work. A relative link is resolved for that page’s final URL; identical HTML under another URL can lead elsewhere.
6. Accept or reject the result. The database compares the attempt ID and current write-permission number. The same accepted f17 acknowledgment returns its retained result; a replaced attempt cannot overwrite newer work. Rejecting an obsolete result is called fencing.
7. Recover without overlapping requests. A lease can let another worker resume stored work, but keep the origin slot reserved until the earlier HTTP request is known closed or its enforced hard deadline has passed. A caller simply stopping its wait is not enough. Pause the origin when uncertain.

Robots rules and access

Robots rules direct cooperative crawling; they are not login permission. RFC 9309 distinguishes a 4xx robots response, which can permit crawling, from network/5xx failure, which requires initial complete disallow. Retain the actual status and any valid cached policy, then retry conservatively. Neither outcome overrides job scope or network safety.

Keep fetching and parsing together until measured parsing work delays network progress. Even this small design must retain work across a restart rather than trust one worker’s memory.

07Schedule fresh useful pages within a finite budget

The scheduler answers two different questions: which URL within a site is useful next, and which origin may receive a request now.

1. Choose within an origin. Its due-URL queue can prefer shallow links, important pages or scheduled revisits. A priority only changes ordering among work allowed by policy.
2. Choose an eligible origin. A global due-time queue selects origins whose next start time has arrived and whose network slot is free. One logical owner or transaction coordinates this allowance across all workers.
3. Dispatch bounded work. Record the attempt before sending it. Ten idle workers cannot each create their own two-second timer for A; they share A’s stored allowance.
4. Preserve progress. Keep known-URL history durably indexed, but schedule from the smaller due set rather than scanning a billion records for every request. Retain queue/attempt checkpoints when adding workers or changing owners.

Choose URL order within the allowance

Use depth, page and query-pattern limits for traps rather than rewriting distinct URLs into one identity. A canonical link can suggest a preferred URL, but is not proof that two resources have the same content, permissions or base for relative links. Distinct domains can also share infrastructure, so broader related-host limits may be needed.

First measure one node’s network and parsing capacity and consider a larger node. Add horizontal workers only with coordinated origin owners and enough eligible origins: the estimate needs roughly 2,320 continuously eligible sites. More workers cannot fix either a saturated parser or a single site’s already-spent allowance.

08Schedule hosts fairly and control duplicates

Scale only the stage that is falling behind; keep the same saved URL and origin rules.

1. Partition scheduling by origin. Assign each origin one logical owner and keep due queues plus timing in durable records. The owner dispatches eligible work across the worker pool; no worker may independently reset that allowance.
2. Recover the network slot safely. Replacing an expired work lease does not make another connection safe. Keep the old slot reserved until known closure or a hard deadline enforced by the network client/egress. An uncertain origin pauses, even when many workers are free.
3. Keep exact scheduling state. The seen-URL store says whether a URL is queued, fetching, finished or due again. A Bloom filter is a small approximate pre-check; a positive may be wrong, so it cannot permanently drop work or replace that exact record.
4. Reuse fetched bytes. Identical bodies can share storage and reusable parse work, but keep each URL’s own outcome and revisit history. Near-duplicate similarity is a later approximation, not the same claim as identical bytes.
5. Separate parsing when needed. If parsing consumes CPU while fetch slots sit occupied, let the fetcher stage a bounded body and commit a pending parse row with its result. A relay reads that row and sends a task to a queue. Parser workers check the expected attempt, extract links and save results before advancing the frontier.
6. Recognize repeated parse delivery. A relay may send twice after losing an acknowledgment. Both tasks identify the same attempt/result. The result transaction accepts it once and repeats recover that stored result; they do not publish a second independent URL outcome.

Cost of a separate parser

The separate parser stage adds queue operation, staged body storage and parse delay. Bound backlog and monitor age. Keep the combined worker while it meets demand, and reserve capacity for small origins so a large site cannot monopolize the crawl.

09Distinguish duplicate URLs, duplicate bodies and unsafe targets

Check scheduling duplicates before fetching; check content duplicates after bytes arrive. These are different actions.

1. A URL is discovered again. The scheduler looks up its exact URL record. If already queued or fetching, it does not enqueue another independent task. If due for a deliberate revisit, it updates that same record’s work state instead of dropping it forever as “seen.”
2. The Bloom pre-check says yes. A positive means the URL may be known; it can be a false positive. Check the exact store before dropping work when coverage matters. A negative may avoid a preliminary read, but inserting work still uses the exact store’s uniqueness rule.
3. Two bodies appear identical. After fetching, compute their hashes and verify the claimed byte identity under the chosen method. Reuse the stored body, but retain each final response URL, validator and fetch time. The same <a href="next"> under A/a and B/c can resolve to different absolute links.
4. A link targets the crawler’s own network. An untrusted page can point to localhost, a private database or a cloud metadata service. Turning the fetcher into an unintended internal proxy is called server-side request forgery. Restrict schemes, validate resolved IP addresses and connect only to an approved public address while checking the HTTPS hostname.
5. DNS or redirects change the destination. Do not blindly resolve again after checking a safe address; DNS rebinding can replace it with a private one. Recheck every hop, including robots fetches, and enforce outbound network restrictions as another layer.
6. A small response expands enormously. Cap received bytes and decompressed bytes separately, plus redirects, parser time and nesting. Do not execute page scripts in this baseline. An authorized operator’s job does not authorize an unrestricted private-network response.

A body hash cannot decide whether a URL may be fetched, which relative links it means or when it should be revisited.

10Trace discovery and revisit

Assume valid cached robots policies and one request start every two seconds per origin, with at most one request in flight. Origin A hosts page A/a; origin B hosts page B/c.

1. At t=0 the scheduler reserves A’s slot for A/a and B’s slot for B/c. Workers may start both because these are separate origin allowances.
2. A/a finishes at t=1 and its parser finds A/b and B/c. The exact URL record already identifies B/c, so only A/b becomes new queued work.
3. A’s prior connection is closed, but its next allowed start is t=2. The scheduler waits until then before starting A/b, even if ten workers are idle.
4. If A/a and B/c have verified identical bodies, save one reusable body and retain both URL records. Resolve next separately against each final URL rather than copying one absolute outlink list to both.
5. Save any entity tag or modification-time validator returned with each URL. On a revisit, send it to ask whether the saved representation changed. A 304 response can reuse the prior body while recording the new check time.
6. If a page is missing, record its status and apply the defined downstream removal policy. For transient errors, increase retry delay within a bound and vary the delay randomly so retries do not all arrive together.

A known URL can deliberately become due again. The exact seen record prevents accidental duplicate work; it is not a permanent ban on revisits.

11Guard the network and explain cost

Explain the surviving record and allowed next action for each failure:

1. A result reply is lost. The database may already have accepted f17. The worker retries acknowledgment with f17; result-saving code returns the retained outcome rather than creating a new attempt.
2. A worker returns after replacement. The stored current attempt or write-permission number has changed. Result-saving code rejects the old worker’s update. The replacement owns progress; the old reply does not become newer just because it arrived last.
3. The old HTTP request may still run. Result rejection does not stop it. Keep the origin slot reserved until confirmed closure or an enforced hard request deadline has passed. A storage lease timeout or client wait timeout alone proves neither; pause when uncertain.
4. A body is saved before its parse task is sent. The result commit includes a pending parse row, so another relay can find and send it. Parser tasks identify the same attempt and check it before publishing links.
5. A public URL redirects into a private network. The guarded client rechecks the actual connection, scope and origin budget for the new request and rejects unsafe addresses. Robots allowance does not override that boundary.
6. A parser receives hostile input. Isolate it and enforce byte, nesting and time limits. Reject oversized or decompression-bomb responses without running page scripts.

Measure eligible origins, timing-limit violations, queue age, lease retries, body bytes per useful page, duplicate ratio and revisit freshness by page class. Back off on failure or overload. Bandwidth, retained bodies and repeated processing are costs separate from frontier memory; idle workers cannot spend another origin’s allowance.