Design: a web crawler

The full lesson, with a worked example: Design: a web crawler.

Requirements

Functional

• Seed and discover: start from a seed list (popular news sites, directories), fetch each page, store it, extract its links and queue the new ones.
• Recrawl: revisit known pages to pick up changes, busy pages more often than quiet ones.
• Hand off: pass each stored page to downstream users (a search indexer, a price tracker, an AI search tool).

Non-functional

• Polite: never overload a site, obey robots.txt, identify itself, back off when a site struggles. This is a hard rule, not a nice-to-have.
• Scale: about 100 crore (1 billion) pages a month, across many machines, growing by adding machines.
• Robust: survive slow servers, broken HTML, giant files, endless trap pages and machine crashes.
• Prioritised and fresh: important pages first; fast-changing pages refetched often.
• Out of scope unless asked: ranking, the search index itself, running every page's JavaScript.

Estimates

• Pages a second: 100 crore a month ÷ about 26 lakh seconds ≈ 400 pages a second, say 800 at peak.
• Links checked: about 50 links a page × 400 ≈ 20,000 seen-checks a second.
• Bandwidth: about 100 KB of HTML a page × 400 ≈ 40 MB a second ≈ 320 Mbps of steady download.
• Storage: 100 crore × 100 KB ≈ 100 TB a month raw; compression shrinks HTML about 4–5×, so about 25 TB a month.
• Fetches in flight: each fetch takes about 1 second, mostly waiting on someone else's server, so about 400 fetches are open at any moment (rate × time, Little's law).
• Sites in progress: at 1 request a second per site, at least 400 sites must be active at once; in practice tens of thousands, because many sites are slower.
• Seen set: say 1,000 crore (10 billion) known URLs. Full URLs at about 100 bytes each ≈ 1 TB. A Bloom filter at about 10 bits per URL for a 1% false-alarm rate ≈ 12 GB, which fits in memory across a few machines.
• URL metadata: 1,000 crore URLs × about 200 bytes ≈ 2 TB, spread across machines.

The key insight: speed comes from crawling thousands of sites slowly at the same time, never from crawling one site fast.

API

A crawler is mostly internal, so its "API" is a small control surface plus the HTTP behaviour it shows the web.

• POST /v1/seeds with a list of URLs and a priority → queued count. Adds starting points or urgent pages.
• GET /v1/pages/:urlHash → latest stored copy: URL, fetch time, status, fingerprint, storage key.
• GET /v1/hosts/:host → politeness state: next allowed time, crawl delay, recent errors, robots.txt rules.
• PUT /v1/hosts/:host/limits → override a site's rate (an owner complained, or a partner asked for more).
• Event out: page.fetched on a queue with the URL, storage key and fingerprint, for the indexer to consume.
• Outgoing requests: GET with a clear User-Agent naming the crawler and a contact URL; If-Modified-Since and If-None-Match on refetches (a conditional request); honour 429 and 503 with Retry-After.

Data model

• Frontier entry (per machine, in memory, checkpointed to disk): url, host, priority, depth, discoveredAt.
• Host record (keyed by registered domain): host, nextAllowedAt, crawlDelay, robotsRules, robotsFetchedAt, errorCount, avgResponseMs, pagesToday, ownerMachine.
• Page record (key-value store, keyed by hash of the normalised URL): urlHash, url, lastFetchedAt, httpStatus, contentHash, simhash, etag, lastModified, changeRate, nextFetchAt, storageKey.
• Page body (object storage): compressed HTML at storageKey, about 20–25 KB after compression, one object per fetch or the latest only.
• Seen set (in memory per machine): Bloom filter over hashes of normalised URLs.
• Fingerprint index: exact content hashes and near-duplicate fingerprints, to group copies.

High-level design

• URL frontier: the to-do list. The URL frontier sorts URLs by importance and splits them by site, so each site is visited at a polite pace.
• Fetchers: many workers, each with hundreds of open connections. They look up site addresses through a cached DNS resolver, download the page with a timeout and size cap, and save it.
• Parsers: pull out links, clean them and check them against the seen set.
• Seen URLs: a Bloom filter answering "definitely new" or "probably seen".
• Page storage: compressed pages in object storage plus a page record per URL.
• Recrawl scheduler: puts known pages back into the frontier when they are due.

One page going round the loop:

1. 1

   URL frontierFetcher

   Next URL whose site is free (next allowed time has passed)

2. 2

   FetcherWebsite

   GET, with robots.txt checked and If-Modified-Since if seen before

3. 3

   WebsiteFetcher

   200 OK with HTML, or 304 Not Modified

4. 4

   FetcherPage storage

   Compress and save, record fingerprint

5. 5

   FetcherParser

   Extract links

6. 6

   ParserSeen set

   Normalised links: which are new?

7. 7

   ParserURL frontier

   New links, scored and routed to the owning machine

Deep dives

The frontier: priority in front, politeness behind

A single first-in, first-out queue fails at once: the 50 links on a news page mostly point to the same site, so the next 50 fetches hammer one server.

• Front: priority lines. New links are scored (how many pages link to them, how popular and fresh their site is) and placed in a fast or slow line, like a priority queue.
• Back: one line per site. Each site has its own small line and a nextAllowedAt time. A free fetcher takes from any site whose time has passed (a min-heap of next allowed times makes this cheap). After a fetch, the site's clock moves forward by 1 second, or by its crawl delay, or by about 10× the last response time if the site is slow.
• robots.txt first: fetched before the first page of any site and cached for about a day. Rules like "skip /checkout" or "wait 5 seconds" are applied before a URL is handed out.
• Group by registered domain, not full hostname, so a site with thousands of subdomains can't escape the limit. Also cap requests per IP address, since many small sites share one server.

Duplicates: normalise, check, fingerprint

• URL normalisation first: lowercase the host, drop #fragments, strip tracking parameters such as utm_source, sort the remaining parameters, resolve ../. Five spellings of one page become one.
• Seen check: the Bloom filter gives no false "new" answers, only false "seen" ones. At 1% about 1 new link in 100 is skipped, which is fine: the page will usually be found again through another link.
• Exact copies: same content fingerprint, different URL. Store once, record the alias.
• Near-copies: a syndicated story on 300 sites with different headers and ads. A fuzzy fingerprint over the main text catches a near-duplicate; keep one main copy (often the original source) and crawl copy-heavy sites less often.
• Don't use a database for seen-checks: 20,000 lookups a second against billions of rows makes the database the bottleneck. Memory first; batch any exact disk checks.

Traps, junk and struggling sites

A crawler trap generates new URLs forever: calendars with "next month", search pages with endless filter combinations, a fresh session ID in every link.

• Limits: maximum depth within a site, a daily page cap per site (scaled by importance), maximum URL length, rules for repeating path patterns like /2026/11/2026/11/.
• Similarity alarm: a site producing many near-identical pages is flagged and its new links drop to low priority.
• Per-fetch caps: a timeout of about 10 seconds and a size cap of about 10 MB, so a 4 GB video link can't tie up a fetcher. Keep only content types you use, mainly HTML.
• Struggling sites: on 503, 429 or rising response times, widen the gap with exponential backoff and respect Retry-After. If robots.txt itself returns a server error, treat the site as "don't crawl" for a while.

Freshness: recrawl by change rate

• Track change per page: every refetch records whether the fingerprint changed. A page that changed on 9 of its last 10 visits is checked more often; one that never changes drifts out to monthly.
• Weight by importance: a busy, popular news homepage might be checked every few minutes; an old blog post every few weeks.
• Cheap checks: conditional requests return a 304 Not Modified of a few hundred bytes instead of about 180 KB.
• Sitemaps: many sites list their pages with last-changed dates, so the crawler can refetch without guessing.
• Budget split: every fetch spent refreshing is a fetch not spent discovering. Reserve a share for each, for example 60% refresh and 40% discovery, and tune it.

Scaling out and surviving crashes

• Partition by site: hash each registered domain to pick an owning machine, using consistent hashing so adding a machine moves only a slice of sites. The owner holds that site's line, clock and robots.txt, so politeness needs no cross-machine coordination.
• Forward links in batches: a parser on machine 1 that finds links for sites owned by machine 7 sends them in batches of a few hundred.
• Checkpoints: each machine writes its frontier to durable storage as a checkpoint every few minutes. A crash loses minutes, not days.
• Leases: a fetcher takes a URL on a lease; if it isn't marked done within a few minutes, the URL goes back in line. Fetching a page twice is harmless.
• Async fetchers: each machine runs thousands of non-blocking connections; DNS is a common hidden bottleneck, so run local caching resolvers.

Trade-offs

• Polite vs fast: per-site limits make each site slow; breadth across many sites keeps total speed high.
• Bloom filter vs exact set: about 99% less memory in exchange for skipping about 1 new link in 100. Use an exact disk-backed set for a small list of must-not-miss URLs.
• Fresh vs wide: refresh budget competes with discovery budget.
• Plain HTML vs full rendering: a headless browser sees pages built by JavaScript but costs about 10–50× a plain fetch. Render only pages that look script-built and are worth it, in a separate queue, less often.
• Breadth-first vs priority: breadth-first is simple and fair; priority scoring finds important pages sooner but needs link and popularity signals.
• Store every version vs latest only: history helps change detection and research, but multiplies storage.

Interview talking points

• Start with politeness and robustness as named requirements; they shape the whole design.
• Do the estimate out loud and land on "400 fetches in flight, thousands of sites at once".
• Draw the loop: frontier → fetchers → storage and parsers → seen set → frontier.
• Explain the two-layer frontier: priority lines in front, one line per site behind, each with a next allowed time.
• Show the Bloom filter sum: 12 GB instead of 1 TB.
• Name the trap defences: depth, per-site caps, URL length, pattern rules, timeouts and size caps.
• Recrawl by change rate and importance, with conditional requests and sitemaps.
• Partition by registered domain, checkpoint the frontier, lease URLs.

Follow-up questions

How do you stay polite with 40 machines crawling at once? Assign each site to exactly one machine by hashing its registered domain. That machine holds the site's clock, so no two machines ever hit it together, with no locking between machines.

How do you decide what to crawl first? Score URLs by inbound links from important pages, site popularity and how often the site changes, and route high scores to the fast priority line. Seeds and sitemaps from trusted sites start high.

The crawler fills up with useless pages. What went wrong? Most likely traps or duplicates. Check pages per site, look for repeating URL patterns and huge parameter counts, tighten depth and per-site caps, and confirm normalisation and near-duplicate detection are working.

How would you handle a site that asks you to slow down or stop? Honour robots.txt and any crawl delay, back off on 429 and 503 with Retry-After, and give operators a per-site override. A contact URL in the User-Agent lets owners reach you before they block you.

What changes to crawl 10× more pages? Mostly more machines: the design is already split by site. Watch the new limits: DNS lookups, outbound bandwidth (about 3 Gbps), the seen set (about 120 GB across the cluster) and the metadata store's write rate.

How do you crawl pages that are built by JavaScript? Fetch plain HTML for everything, detect pages that come back nearly empty, and send those to a separate rendering queue with headless browsers, sized for a small share of pages because each render costs many plain fetches.