Design a Web Crawler

This is the first lesson of System Design Case Studies, Part 2. Every lesson uses the same eight steps: requirements, numbers, API, data model, architecture, deep dives, failures and trade-offs, and a 60-second interview summary. The first series of cases is in Design Problems. The general ideas (sharding, queues, caches) are in the System Design series.

A crawler is used by search engines (to build an index), by price trackers, by archive projects, and by AI data teams. We design the general one: it starts from some seed URLs and collects pages from the public web.

Words used in this lesson

• Crawler (or spider, bot) is a program that downloads web pages by following links.
• Seed URLs are the starting list of addresses. The crawler finds all other pages from them.
• URL frontier is the to-do list of URLs the crawler has found but not yet downloaded. It decides what to fetch next.
• Politeness means not overloading a website. A crawler that sends 1,000 requests per second to a small site looks like an attack.
• robots.txt is a text file at the root of a site (/robots.txt) where the site owner says which paths bots may not fetch. Good crawlers obey it.
• Hash is a fixed-size fingerprint of some data. Same data gives the same hash. SHA-256 is a common hash function with a 256-bit result.
• Bloom filter is a compact structure that answers "have I seen this item?" with either "definitely not" or "probably yes". It never forgets an item, but sometimes says "yes" for an item it never saw (a false positive).
• DNS is the system that turns a name such as news.test into a server address.
• Crawl trap is a set of pages that gives the crawler endless new URLs (for example a calendar with a "next day" link that never stops).
• Freshness is how up to date your stored copy of a page is compared with the live page.
• Conditional GET is a download request that says "send the page only if it changed since this date or tag". If not changed, the server answers 304 Not Modified with no body.

1. Requirements

Functional (what it does)

• Start from seed URLs, download pages, extract links, and add the new links to the to-do list.
• Store the page content so another system (for example an indexer, see How Search Works) can use it.
• Obey robots.txt and per-site speed limits.
• Come back to pages later to refresh them.

Non-functional (how well)

• Scalable: assume the target is 1 billion pages per month (an assumption for this lesson).
• Polite: never hurt a site. This is the rule that shapes the design most.
• Robust: bad HTML, huge files, servers that hang, redirect loops, traps. Nothing should stop the whole crawler.
• Extensible: new content types (images, PDFs) and new processing steps should be easy to add.
• Not duplicated: the same page must not be stored a thousand times.

Out of scope here: building the search index, ranking, and running JavaScript in a browser to render pages (crawling JavaScript-heavy pages needs a headless browser, which is 10 to 100 times more expensive per page; I only mention it).

2. Back-of-envelope numbers

Every number below is an assumption unless the text says otherwise. See Back-of-the-Envelope Estimation for the method.

Target                : 1,000,000,000 pages / monthSeconds in a month    : 30 * 86,400 = 2,592,000  (about 2.5 million)Average rate          : 1e9 / 2.59e6 = ~386 pages/s   -> call it 400/sPeak (assume 2x)      : ~800 pages/sPage size (assume)    : 100 KB of HTML on averageDownload bandwidth    : 400 * 100 KB = 40 MB/s = 320 Mbit/s averageRaw storage / month   : 1e9 * 100 KB = 100 TBAfter compression     : assume 3:1 -> ~33 TB / monthKeep 12 months        : ~400 TB  (object storage, not a database)Concurrency (assume 500 ms per fetch including DNS and download):  400 pages/s * 0.5 s = 200 fetches in flight at once on average.  One machine can hold thousands of idle connections, so CPU and bandwidth, not connection count, set the fleet size.Links found (assume 50 per page, 10% of them new):  1e9 * 50 = 50 billion link sightings / month  5 billion new URLs / month, so after a year ~60 billion URLs known.

For comparison, the system-design-primer solution uses 1 billion links, 4 billion crawls a month (each link about once a week), 500 KB per page: 4e9 x 500 KB = 2 PB of content per month and 4e9 / 2.5e6 = 1,600 writes per second. My numbers are smaller on purpose. The method is the same.

The politeness number matters most. Suppose the rule is one request per second per site. One site can then give you at most 86,400 pages per day. To reach 400 pages per second in total you must be crawling at least 400 different sites at the same time. This is why the frontier is organised by host (the website name), not as one big queue.

How big is the "seen" set? Say we know 10 billion URLs.

3. API

A crawler is mostly a back-end pipeline, so it has a small control API and one interface to the outside web.

# Control plane (for operators)POST /v1/seeds        { "urls": ["https://example.com/"], "priority": 5 }GET  /v1/stats        -> { "fetched": 1203311, "queued": 98211221, "errors": 8123 }POST /v1/hosts/example.com   { "crawlDelaySeconds": 5, "blocked": false }   # override per site# Data plane (what the crawler sends to sites)GET /robots.txtGET /page   with headers:  User-Agent: ExampleBot/1.0 (+https://example.com/bot-info)   <- say who you are and give a contact page  If-None-Match: "abc123"          <- conditional GET on a refresh  If-Modified-Since: Tue, 01 Oct 2026 00:00:00 GMT# Output (to the next system): a message on a queue per stored page{ "url": "...", "fetchedAt": "...", "status": 200, "contentHash": "…", "storageKey": "pages/ab/cd/…" }

4. Data model

Normalising a URL means writing it in one standard form before you compare it: lower-case the host, drop #fragment, remove tracking parameters such as utm_source, sort the query parameters. Without this, a.com/x?utm=1 and a.com/x count as two pages.

5. High-level architecture

 seed URLs     |     v+-----------+   pop URL when the host is   +------------------+     +-------------+|           |   allowed to be hit again    |  Fetcher workers |---->| DNS cache / ||  URL      |----------------------------->|  (many, async)   |     | resolver    || FRONTIER  |                              +--------+---------+     +-------------+|           |                                       | HTML bytes| front: priority queues                            v| back : one FIFO queue per host      +-------------+-------------+|        + next-allowed-time          |  Parser / link extractor  |+-----^-----+                         +------+-------------+------+      |     ^                                |             |      |     | new URLs                       | content     | links      |     |                                v             v      |     |                      +---------------+  +----------------------+      |     +----------------------|  Dedup: hash  |  | URL filter           |      |                            |  set of page  |  |  - normalise         |      |                            |  content      |  |  - robots.txt check  |      |                            +-------+-------+  |  - trap rules        |      |                                    |          |  - Bloom filter: seen?|      |                                    v          +----------+-----------+      |                            +---------------+             |      |                            | Object storage|             |      |                            | (pages)       |             |      |                            +-------+-------+             |      |                                    | message             |      |                                    v                     |      |                              to indexer (queue)          |      +----------------------------------------------------------+

The flow in words: a worker pops a URL from the frontier, resolves the host name, downloads the page, and passes it to the parser. The parser finds links. Each link goes through the URL filter (normalise, robots.txt, trap rules, "seen before?"). New links return to the frontier. The page content is hashed, checked for duplicates, compressed and saved.

6. Deep dives

6.1 The URL frontier: priority and politeness

The frontier answers one question: "which URL should I fetch next?" A single queue is not enough because two things compete:

• Priority: some pages matter more (popular sites, pages that change often, new seeds).
• Politeness: do not hit one host more often than its limit.

A well-known design for this is from the Mercator crawler paper (I did not re-read it; this is from general knowledge). It uses two layers:

1. Front queues order URLs by priority. A URL goes into one of, say, 5 queues. A picker takes more from the high-priority queues.
2. Back queues hold one FIFO queue per host. A small min-heap holds (host, next allowed time). A worker takes the host whose time has come, pops one URL from that host's queue, and sets the next allowed time to now + delay.

front queues (priority)          back queues (one per host)          heap of (next allowed time, host)  P1 [u u u]  \                   news.test  [u u u u]                 t=10.2  shop.test  P2 [u u]     >--- router --->   shop.test  [u u]                     t=10.9  news.test  P3 [u u u u]/  (puts each       trap.test  [u]                       t=11.4  trap.test                  URL in its                                           (pop the smallest time)                  host queue)

The delay for each host comes from robots.txt (Crawl-delay is not part of the standard and some big crawlers ignore it, not re-read), from the server's speed (if the server answers slowly, back off), and from a default (assume 1 second). A good rule: wait a multiple of the last response time, so slow servers get fewer requests.

The frontier is too big for memory (billions of URLs). Keep the heap and the first few URLs per host in memory. Keep the rest on disk in a log or a key-value store, and load more as queues run low.

I ran this in the simulation. Four workers, 1 second of politeness plus 0.2 seconds fetch time, three sites. The smallest gap between two hits to the same host was 1.20 s on every host. The workers did not wait for each other: while one host was resting, they fetched from another.

// excerpt from crawler.ts: choose the host that can be fetched earliestlet best: string | null = null, bestT = Infinity;for (const [h, q] of queues)  if (q.length) {    const t = Math.max(nextOk.get(h)!, free[w]);   // host is allowed AND a worker is free    if (t < bestT) { bestT = t; best = h; }  }const url = queues.get(best)!.shift()!;nextOk.set(best, now + FETCH_TIME + POLITE_DELAY);  // the host rests before its next URL

(This loop scans all hosts, which is fine for a demo. A real system uses a min-heap, so a pick costs O(log n).)

6.2 robots.txt

Before the first fetch from a host, download https://host/robots.txt, parse it, and keep the rules in a cache (a common choice is about a day; the standard allows caching for up to 24 hours, not re-read). The rules look like this:

User-agent: *Disallow: /private/Allow: /private/public-report.htmlSitemap: https://example.com/sitemap.xml

Things that go wrong:

• The file is missing (404): treat it as "everything allowed".
• The server errors (5xx) or times out: be careful. The safe choice is to treat the site as "do not crawl for now" and retry later, not "everything allowed".
• The file is huge: cap the size you parse.
• Rules are advice, not security. A site that wants to hide pages must use a login. robots.txt also does not remove a page from a search index by itself.

In the simulation news.test disallows /private/. The crawler found http://news.test/private/secret as a link and the run reports robotsBlocked: 1: it was dropped before any fetch.

6.3 Duplicates, part 1: have I seen this URL?

For every link we find we must ask: is this URL already known? That is 50 billion questions a month in our numbers (about 19,000 per second). Options:

A Bloom filter is a bit array of m bits, all zero at the start, with k hash functions. To add an item: compute k positions and set those bits to 1. To check an item: compute the k positions. If any bit is 0 the item was never added. If all are 1 the item was probably added (other items may have set those bits).

The size comes from two standard formulas: m = -n * ln(p) / (ln 2)^2 bits and k = (m / n) * ln 2, where n is the number of items and p the false-positive rate. This is what I ran:

// bloom.ts (full file is about 25 lines; core shown)export class Bloom {  bits: Uint8Array; m: number; k: number;  constructor(m: number, k: number) { this.m = m; this.k = k; this.bits = new Uint8Array(Math.ceil(m / 8)); }  // Double hashing: position_i = h1 + i*h2 (mod m). Both numbers come from one SHA-256.  private idx(s: string): number[] {    const d = createHash("sha256").update(s).digest();    const h1 = d.readUInt32LE(0), h2 = (d.readUInt32LE(4) | 1) >>> 0;   // odd, kept unsigned    return Array.from({ length: this.k }, (_, i) => (h1 + i * h2) % this.m);  }  add(s: string) { for (const i of this.idx(s)) this.bits[i >> 3] |= 1 << (i & 7); }  has(s: string): boolean { return this.idx(s).every((i) => this.bits[i >> 3] & (1 << (i & 7))); }}

Test: 100,000 URLs added, target error 1%.

{ m: 958506, k: 7, bytes: 119814 }false negatives: 0false positive rate: 0.0099 target 0.011e+9 URLs -> 1.20 GB, k = 71e+10 URLs -> 11.98 GB, k = 71e+11 URLs -> 119.81 GB, k = 7

About 120 KB for 100,000 URLs, which is 9.6 bits per URL. The measured error was 0.99%, matching the 1% target. No false negatives, as the theory promises.

What a false positive costs here: we skip a URL we have never seen, so that one page is not crawled. For a crawl of billions of pages, losing 1% of newly found URLs is acceptable, and they are likely found again from other pages. This is a good trade for a crawler. It would be a bad trade for, say, a payment check.

Limits of a Bloom filter: you cannot remove an item, so it only grows, and when it holds more items than planned, the error rate rises. Plan for growth: when it is about 70% of its planned size, start a second, larger filter (this is called a scalable Bloom filter). Because it cannot store "when was this fetched", it is only the first check. The exact state (last fetch time, ETag) lives in url_state.

In the simulation the Bloom filter caught 80 repeated links (bloomSkipped: 80), including ?utm=x copies that normalisation reduced to a known URL.

6.4 Duplicates, part 2: have I seen this content?

Different URLs can give the same page: a print version, http and https, a session id in the link, a mirror. Crawling and storing all of them wastes space and fills the index with copies.

• Exact duplicates: hash the page body (SHA-256) and look up the hash in a set. If it is there, drop the page and do not follow its links.
• Near duplicates (a page with a different ad or date): use a similarity fingerprint such as SimHash, or compare word sets with the Jaccard index (the size of the shared words divided by the size of all words). The system-design-primer suggests Jaccard and cosine similarity for this. I only implemented the exact hash.

In the simulation, every story page /story/i also links to /print/i, which has the same body. Result: dupContent: 30 — all 30 print copies were detected and their links were not followed.

6.5 Fetch workers and DNS

A fetch worker does the slow part. It should be asynchronous: one process holds hundreds of open connections, because most of the time it just waits for the network. Rules for a safe worker:

• Timeouts: connect timeout (about 5 s) and total timeout (about 30 s). A server that sends one byte per minute must not hold a slot forever.
• Size cap: stop after, say, 5 MB. Check the Content-Type and skip things you do not want (video, binary).
• Redirect cap: follow at most about 5 redirects, and re-check robots.txt and the host's politeness for each new host.
• Compression: ask for gzip. It saves bandwidth.
• Identify yourself with a User-Agent and a contact page.
• Retry with back-off: a failed URL goes back with a longer wait (Timeouts, Retries & Backoff). After N failures mark it dead and try again only in a slow, later cycle.
• Avoid fetching from internal addresses (a link to http://169.254.169.254/ or http://localhost/). A crawler that follows a link into your own network is an SSRF problem.

DNS is a hidden bottleneck. Every new host needs a lookup, and a standard system resolver call can be slow and blocking. At 400 pages per second, even if only 10% of fetches are on a new host, that is 40 lookups per second. Use a DNS cache inside the crawler (cache the answer for the TTL, or longer), resolve asynchronously, and run your own caching resolver near the workers. Since all URLs for one host go to the same worker (see the next part), each worker keeps its own small cache.

6.6 Sharding the crawl by host

With many machines, give each machine a set of hosts. worker = hash(host) mod N, or better, consistent hashing, so that adding a machine moves few hosts (Sharding). Reasons to shard by host and not by URL:

• Politeness is per host, so one machine must own the timer for that host. Otherwise ten machines each wait one second and together send ten requests per second.
• The robots.txt cache and the DNS answer for the host live on that machine.
• A link found on one machine and owned by another is sent to the owner over a queue.

The cost: a hot host (a huge site with a billion pages) lands on one machine. Since its speed is limited by politeness anyway, one machine is enough for it. Big sites are slow to crawl because of politeness, not because of hardware. Some crawlers allow a higher rate for sites that ask for it.

6.7 Crawl traps

A trap makes the crawler spend its budget on useless pages. Examples: a calendar with endless "next month" links, a search page that makes a new URL for each query, a session id added to every link, a link such as /a/b/a/b/a/b/... that grows each time.

Defences, from cheap to smart:

1. Cap the URL length (for example 2,000 characters) and the number of path segments.
2. Cap pages per host, with a bigger cap for hosts with high value.
3. Cap link depth (the number of hops from a seed).
4. Detect repeating patterns in the path (the same segment appearing many times).
5. Content check: if many new pages from a host have the same hash or almost no new text, lower that host's priority.
6. Human override: a way to block a host or a path pattern by hand.

In the simulation trap.test gives a new "next day" page forever. I set a cap of 80 pages per host. The trap used its 80 fetches and was then cut off (hostCapped: 1), while the real sites were fully crawled.

6.8 Freshness and recrawling

A page changes at its own speed: a news front page every few minutes, an "about" page every few years. If you recrawl everything every week, you waste work on pages that never change and miss changes on pages that change often.

• Record how often a page changed at each visit. If it changed, shorten the interval (for example halve it). If it did not change, lengthen it (double it). Keep the interval between, say, 1 hour and 90 days.
• Use conditional GET: send If-None-Match with the saved ETag. A 304 costs a few hundred bytes instead of 100 KB.
• Use sitemaps (Sitemap: in robots.txt) which can list lastmod dates.
• Give higher priority to pages that other systems care about (popular pages, pages users search for).
• Separate the recrawl schedule from discovery of new URLs, so a flood of new links does not starve the refresh work, and the other way round.

6.9 Storage

• Raw pages: compressed blobs in object storage, keyed by content hash. Many crawl archives pack pages into big files (the WARC format is the common choice, from general knowledge) because millions of tiny objects are expensive. Pack many pages per file and keep an index of url -> file, offset.
• URL state: a key-value or wide-column store (HBase, Cassandra, DynamoDB), partitioned by host so one host's URLs sit together.
• Frontier: on-disk queues with a small in-memory head. A message log (for example Kafka, see Apache Kafka Fundamentals) is a good fit for the "new URL found" stream between machines.
• Output to indexers: a queue message per stored page, so the crawler and the indexer run at their own speeds (Message Queues).

7. Failure modes and trade-offs

Trade-offs worth saying out loud

• Breadth-first vs depth-first: breadth-first (take links in the order found) reaches many sites and good pages early. Depth-first can sink into one site.
• Bloom filter vs exact set: Bloom is 6 to 7 times smaller than 8-byte hashes (12 GB vs 80 GB in our numbers), at the cost of missing about 1% of new URLs.
• Fast vs polite: more speed on one host needs permission. Politeness is the limit; add more hosts, not more speed per host.
• Fresh vs wide: each refresh uses budget that could find a new page. Pick the mix from the product goal.
• Rendering JavaScript: much more content, much more cost. Do it only for hosts that need it.

8. How to say it in an interview (60 seconds)

"I would start by asking the scale and the goal. Say 1 billion pages a month, which is about 400 pages a second and about 100 TB of HTML a month before compression. The core is a URL frontier with two layers: priority queues in front and one queue per host behind, with a next-allowed-time for each host, so we stay polite and still keep all workers busy. We need at least as many active hosts as pages per second. Workers are asynchronous, use timeouts and size caps, check a cached robots.txt, and use a DNS cache. For 'have I seen this URL' I use a Bloom filter, about 12 GB for 10 billion URLs at 1% error, and a key-value store for exact state. For content I hash the body to drop exact duplicates. I defend against traps with caps on URL length, depth and pages per host. I shard by host so politeness is owned by one machine. Pages go to object storage, and a queue tells the indexer. For freshness I adapt the revisit interval to how often a page changes and use conditional GET."

Run it yourself

The two programs are short. bloom.ts has the filter, and crawler.ts imports it. Run node crawler.ts with Node 22 (the TypeScript is plain enough for Node's built-in type stripping; I avoided parameter properties because strip-only mode rejects them). The full output I got:

{  fetched: 162,  robotsBlocked: 1,  bloomSkipped: 80,  dupContent: 30,  hostCapped: 1}unique pages kept: 132 | virtual time: 96.0 snews.test  fetches  61 | smallest gap between hits 1.20 sshop.test  fetches  21 | smallest gap between hits 1.20 strap.test  fetches  80 | smallest gap between hits 1.20 s

Check the numbers: news.test is 1 home page + 30 stories + 30 print copies = 61 fetches; 30 of them were exact duplicates. shop.test is 1 + 20 items = 21. trap.test stopped at the cap of 80. Kept pages: 31 + 21 + 80 = 132, and 132 + 30 duplicates = 162 fetches. The 96 seconds is virtual time, not real time.

Interview questions

Key takeaways

• A crawler is a loop. The design lives in the frontier, the seen check and trap defence.
• Politeness is per host. You need at least (pages per second x delay) active hosts, and you shard by host so one machine owns each timer.
• A Bloom filter gives a cheap "seen this URL?" check: about 12 GB for 10 billion URLs at 1% error, with no false negatives. Test for both kinds of error.
• Use a content hash to drop exact duplicate pages and a similarity fingerprint for near copies.
• Caps (URL length, depth, pages per host) stop traps. Adapt revisit time to how often a page changes, and use conditional GET.
• Keep numbers honest: label assumptions, and show the arithmetic.

What's next

Lesson 1: Design a Key-Value Store (Like Redis or Dynamo). The crawler needed a huge "url_state" table and a fast frontier. Next we build the store underneath such systems: one node first, then many nodes that stay available when some fail.