Design: a web crawler

The prompt

A crawler's core loop fits in five lines: take a URL, fetch it, store it, extract links, add the new ones. Every interesting part of the design is about what that loop does to other people's servers, and to itself, at a billion pages.

1. Requirements

Functional: fetch pages from seeds outward; store each page and its metadata; extract and follow links; recrawl pages based on how often they change.

Non-functional:

• Polite: one request at a time per host, with a pause between requests, and obey robots.txt.
• Scalable: 1 billion pages a month, more by adding machines.
• Robust: slow servers, malformed HTML and infinite link structures can't stall it.
• Restartable: a crashed node resumes without losing its frontier.

2. Estimates

The last row is the one that shapes the design.

3. High-level design

4. Deep dives

Try it

With one big site (40% of URLs) and a 2-second pause, a single queue with no politeness fetched 594 pages in a minute, but 510 requests broke the rule, with up to 8 at once on one host. Making each thread wait for its host made it polite and cut it to 54 pages, with threads idle 91% of the time. A queue per host fetched 360, all polite: the big site got about the same number of requests either way (22 and 21); the difference is that the other threads kept working on the small sites. With 70% of URLs from one site, even per-host queues left threads idle 70% of the time: politeness caps each host, so throughput comes from crawling many hosts at once.

robots.txt. Before fetching from a host, the crawler fetches /robots.txt and obeys it. RFC 9309 sets the rules: cache it for at most 24 hours; if it returns a 4xx, the crawler may fetch anything; if the server errors (5xx) or can't be reached, assume everything is disallowed; parse at least the first 500 KiB.

const TRACKING = /^(utm_[a-z]+|fbclid|gclid)$/i;

export function normalise(href: string, base?: string): string | null {
  let u: URL;
  try {
    u = new URL(href, base); // resolves relative links against the page
  } catch {
    return null;
  }
  if (u.protocol !== "http:" && u.protocol !== "https:") return null; // mailto:, javascript:, ...
  u.hash = ""; // fragments never reach the server
  u.hostname = u.hostname.toLowerCase().replace(/\.$/, "");
  const params = [...u.searchParams].filter(([k]) => !TRACKING.test(k)).sort(([a], [b]) => a.localeCompare(b));
  u.search = new URLSearchParams(params).toString();
  if (u.pathname === "") u.pathname = "/";
  return u.toString(); // URL already lowercases the scheme and drops default ports
}

Tested: https://Shop.Example:443/a/b/page.html?utm_source=x&b=2&a=1#reviews became https://shop.example/a/b/page.html?a=1&b=2; ../c?id=7 on that page resolved to https://shop.example/a/c?id=7; HTTP://shop.example:80 became http://shop.example/; mailto: and javascript: links were dropped; a gclid parameter was removed; and a trailing dot on the host was removed.

Traps. Calendars with a "next month" link forever, session IDs in URLs, and generated pages make infinite URL spaces. Cap URL length and path depth, cap pages per host per crawl, and lower the priority of hosts whose pages are mostly near-duplicates.

Freshness. Recrawl by observed change rate: a news front page hourly, an old article monthly. Conditional requests (If-Modified-Since, If-None-Match) let unchanged pages answer 304 with no body.

5. Wrap-up

What breaks first is rarely the fetchers: it's DNS (each node needs its own caching resolver), the seen-URL set as it grows, and complaints, which is why politeness, a clear user agent and a contact page for site owners are part of the design.

Recap

Interview questions