Design a Web Crawler

A web crawler downloads pages, extracts links and follows them, at a scale of billions of pages. It is the data collection engine behind search engines, price trackers, archives and machine learning datasets. The interview value is that the idea is simple and the difficulties are all about scale and good behaviour: not hammering one site, not crawling the same page twice, not being trapped, and recovering from failure without starting over.

The chapter follows the usual shape: understand the problem, set up the interface, build the high-level design, then go deep on the questions interviewers use to separate levels.

1. Understanding the problem

We start from a set of seed URLs, fetch each page, extract the links, and repeat. The output is a collection of pages and the data derived from them, which a downstream system, such as a search index, consumes.

Functional requirements

Core:

1. Starting from seed URLs, discover and fetch pages by following links.
2. Store the fetched content for downstream processing.
3. Avoid fetching the same page repeatedly, and keep content reasonably fresh by recrawling.

Confirm in or out: which content types (HTML only, or images and PDFs), handling of JavaScript-rendered pages, language filtering, and whether it serves a general search engine or a focused crawl of selected sites. A sensible opening: "I will design a general-purpose crawler for HTML pages, with deduplication and recrawling, and treat JavaScript rendering as an extension."

Non-functional requirements

• Scalability. Billions of pages, in a bounded time.
• Politeness. The crawler must not overload any website, and it must respect the site's crawling rules.
• Robustness. The web is full of broken pages, slow servers, traps and malformed data. The crawler must survive all of it.
• Extensibility. Adding new content types or processing steps should be easy.
• Fault tolerance. A machine failure must not lose the crawl state or force a restart.

Estimation

Assume a goal of 10 billion pages in four weeks, with an average page of 100 KB.

What the numbers say. 4,100 fetches per second is a lot for one machine, because each fetch spends most of its time waiting on the network, but it is easily spread across a few hundred machines. A petabyte means distributed object storage. The URL set is large but small enough to live in memory across several machines, which makes a fast deduplication check practical.

2. The set up

Core entities

• URL: the address, with its host, priority and time last fetched.
• Page: fetched content, a content hash, headers and extracted links.
• Host: a website, with its crawl delay and robots rules.

Interface

The crawler is a back-end system without a user-facing API. Its interfaces are the seed list and crawl policy configuration, and the output: pages and metadata written to storage and signalled to downstream consumers, typically through a queue.

3. High-level design

The crawl is a loop with several stages, each of which scales independently:

1. The URL frontier holds the URLs waiting to be fetched, ordered by priority and politeness.
2. Fetchers take a URL, resolve the host through a DNS cache, check the robots.txt cache, and download the page.
3. A parser extracts text, metadata and links, and validates the content.
4. De-duplication checks whether each extracted URL has been seen and whether the content duplicates another page.
5. New, unseen URLs go back into the frontier. The content goes to the content store.

Each stage can be a pool of stateless workers connected by queues. If fetching is the bottleneck, add fetchers. If parsing is, add parsers. State lives in three places only: the frontier, the seen-URL set and the content store.

Seeds and scope

Choose seeds that reach the web well: a list of popular sites and directories. For a focused crawl, restrict the frontier to chosen domains. The seed choice and the priority function are what define the crawl's character.

4. Potential deep dives

Deep dive 1: How do you stay polite and still be fast?

The challenge. You need thousands of fetches per second overall, and you must not send more than a gentle trickle to any single website.

Weak: fetch URLs in the order they were discovered, from a single FIFO queue. Links on one page often point to the same host, so a burst of URLs from one site arrives together, and many fetchers hit that site at once. It looks like an attack, gets you blocked, and can take small sites down.

Solid: one queue per host, with a delay between requests. Maintain a back queue per host. A worker takes from a host's queue only if enough time has passed since the last request to that host, honouring the site's declared crawl delay, or a sensible default of one request every few seconds. Many hosts are being crawled in parallel, so the total throughput is high while each site sees a light load. Always check and cache robots.txt, which states what the site allows, and respect it.

Excellent: a two-tier frontier that handles priority and politeness together. The frontier has front queues that order URLs by importance and back queues that enforce per-host delay.

• A prioritiser scores each URL, using signals such as the importance of its host, how often the page changes, depth from the seed and past quality, and places it in a front queue by priority.
• A router maps each URL's host to exactly one back queue, so a host is only ever handled by one queue at a time. A scheduler releases the next URL from a back queue only when that host's delay has elapsed, then hands it to a free fetcher.
• Take URLs from the front queues with a bias toward high priority, which gives important pages sooner without starving the rest.

Add adaptive politeness: slow down if a site responds slowly or with errors, since that suggests it is under strain. Identify the crawler clearly in the request headers and provide a contact point, which is part of being a good citizen.

Deep dive 2: How do you avoid crawling the same thing twice?

The challenge. The web links to itself heavily. Without deduplication the crawler loops and wastes most of its effort.

Weak: check a database table of seen URLs for every link. Hundreds of thousands of link checks per second against a disk-backed table is too slow, and the table becomes the bottleneck.

Solid: an in-memory set of seen URLs, partitioned across machines. Normalise each URL first: lowercase the host, remove default ports and fragments, resolve relative paths, sort query parameters, and strip tracking parameters. Then check membership in a sharded in-memory set, partitioned by a hash of the URL or host. Only unseen URLs enter the frontier.

Excellent: a Bloom filter in front of a persistent store, plus content-level dedup. A Bloom filter is a compact probabilistic set that answers "definitely not seen" or "probably seen". It never gives a false negative, so a URL it calls new is genuinely new, and it gives a small, tunable rate of false positives. At 10 billion URLs and a 1 percent false-positive rate it needs about 12 GB, far smaller than storing the URLs themselves. The cost is that about 1 percent of genuinely new URLs are wrongly skipped, which is usually acceptable for a web-scale crawl, and the filter is checked first so that most lookups never reach the slow store. For exactness where it matters, back it with a persistent set that confirms the "probably seen" answers.

URL deduplication is not enough, because different URLs often serve the same content, such as mirrors, tracking variants and session identifiers. Add content deduplication: compute a hash of the normalised page content and skip pages whose hash is already known. For near-duplicates, such as the same article with a different sidebar, use similarity fingerprints such as SimHash, which give similar documents similar fingerprints, so you can detect them by comparing fingerprints cheaply.

Deep dive 3: How do you handle traps and bad content?

The challenge. Some sites, deliberately or by accident, generate unlimited distinct URLs: calendars with endless future dates, session identifiers in URLs, or infinite redirect loops. A crawler can spend its life in one.

Weak: follow every link. The crawler gets stuck, fills storage with worthless pages and neglects the rest of the web.

Solid: set limits. Cap URL length and path depth, cap the number of pages per host and per time period, follow only a limited number of redirects, and use timeouts and maximum page sizes on every fetch.

Excellent: combine limits with detection and a quality signal. Detect repetitive patterns, such as many URLs differing only in a parameter, and downgrade or stop crawling that pattern. Use a per-host budget that scales with the host's quality, so a low-value site cannot absorb unlimited effort. Validate content: skip non-text types you do not handle, reject pages that fail to parse, and discard obvious spam. Log traps so that the rules improve over time. Every external input is hostile, so parse defensively and run parsers with resource limits.

Deep dive 4: Freshness and recrawling

The challenge. Pages change. A news homepage changes every few minutes, while an old article never does.

Weak: recrawl everything on a fixed schedule. Wasteful for static pages and too slow for dynamic ones.

Solid: recrawl based on observed change rate. Track how often each page changed between visits, and recrawl frequently changing pages more often. Use HTTP conditional requests (If-Modified-Since or entity tags) so that an unchanged page costs a tiny response instead of a full download.

Excellent: priority tied to importance and change, with a budget. Combine change frequency with the page's importance, so the crawl budget goes where staleness is most costly. Reserve capacity for new discovery as well as recrawl, since both compete for the same fetchers. Use sitemaps and feeds, which sites publish to say what has changed, as cheap hints.

Deep dive 5: Fault tolerance and distribution

The challenge. A crawl runs for weeks across hundreds of machines. Machines will fail.

Weak: keep crawl state in the memory of each worker. A crash loses the queue contents and everything in progress.

Solid: keep durable state outside the workers. Store the frontier and the seen set in durable, replicated storage, and make fetchers stateless. A fetcher that dies simply stops taking URLs, and any URL it held is returned to the queue after a timeout.

Excellent: partitioned frontier, checkpoints and idempotent steps. Partition the URL space by host across crawler nodes, using consistent hashing so that a node failure or addition moves only a share of hosts, and all of one host's URLs stay on one node, which keeps politeness local and simple. Persist the frontier and filter state with periodic checkpoints. Make every stage idempotent: fetching a page twice, or storing it twice under the same key, is harmless, so retries are safe. Monitor throughput, error rate, queue depth and fetch latency per stage and per host, and alert on stalls.

Deep dive 6: DNS and the network

DNS lookups can dominate fetch time at this scale, and a general resolver may rate limit you. Run a DNS cache local to the crawler, and resolve in parallel. Many fetches should be asynchronous, since each spends most of its time waiting. Reuse connections to the same host where polite, and spread fetchers across regions close to the sites they crawl to reduce latency.

Deep dive 7: Dynamic content

Many pages build their content with JavaScript after loading. A plain HTTP fetch sees only an empty shell. Options are to run a headless browser to render such pages, which is orders of magnitude more expensive per page, or to render only for sites and pages where it is known to matter. Say that you would start with plain fetching and add rendering selectively.

5. What is expected at each level

Mid-level. You describe the loop of fetch, parse and extract links, and the need for a queue of URLs and a seen set. You mention robots.txt and the need to avoid overloading sites.

Senior. You design the frontier with per-host politeness and priority, size the system from the estimates, use a Bloom filter or sharded set for deduplication, handle traps with limits, and discuss distribution by host and failure recovery.

Staff. You discuss freshness economics, crawl budget allocation, spam and trap detection, content deduplication, legal and ethical aspects of crawling, how downstream consumers interact with the crawler, and operational concerns such as monitoring and safe rollouts. You can reason about when rendering JavaScript is worth the cost.

6. Interview questions and model answers

Q: How do you make sure you do not overload a site? One back queue per host with a minimum delay between requests, honouring robots.txt and crawl delay, and adapting to slow responses. A host is always handled by one queue, so the delay is easy to enforce.

Q: How do you check whether a URL has been seen? Normalise the URL, then check a sharded in-memory Bloom filter, confirming "probably seen" answers against a persistent set if exactness is needed. At 10 billion URLs and 1 percent error the filter is about 12 GB.

Q: How do you detect duplicate pages under different URLs? Hash the normalised content for exact duplicates, and use a similarity fingerprint such as SimHash for near-duplicates.

Q: How do you avoid spider traps? Limits on URL length, depth and pages per host, a redirect cap, pattern detection for endless parameter variations, and a quality-based budget per host.

Q: What happens when a crawler machine dies? Fetchers are stateless, and the frontier and seen set are durable. URLs it held are returned to the queue after a timeout. Idempotent stages mean a repeated fetch or store is harmless.

Q: How do you keep pages fresh? Recrawl based on observed change rate and importance, using conditional requests so unchanged pages are cheap, and treat sitemaps as hints.

7. Common mistakes

• A single global queue that hits one host with a burst of requests.
• Ignoring robots.txt and crawl delay.
• Checking seen URLs against a disk database for every link.
• Not normalising URLs before deduplication.
• No limits against spider traps and endless URL spaces.
• Keeping the only copy of the frontier in a worker's memory.
• Treating every page as equally important and equally fresh.