Design a web crawler

The problem

A web crawler starts from some known URLs, downloads each page, extracts the links and follows them. Search engines use crawlers to build their index, and others use them for archiving, price tracking or monitoring.

Requirements

• Scale: about a billion pages a month.
• Polite: do not overload sites, follow robots.txt.
• Robust: bad HTML, huge files, slow servers and traps must not break it.
• Extensible: later add new content types (images, PDFs).
• Avoid fetching the same page twice.

Estimates

1 billion pages a month is about 400 pages a second on average. At roughly 500 KB each (HTML plus metadata), that is around 500 TB a month, so storage and network are the big costs.

High-level design

100%

Figure SDA-CSD-05-1 · Crawler pipeline · © forcsguy.com

1. The URL frontier hands out URLs to crawl next.
2. Fetchers download pages (resolving names with a local DNS cache, since DNS lookups can dominate time).
3. The parser validates and processes the HTML.
4. A content-seen check drops pages identical to ones already stored.
5. Links are extracted, normalised, filtered, and checked against URL-seen before going back to the frontier.

The web as a graph

100%

Figure SDA-CSD-05-2 · Crawling is graph traversal · © forcsguy.com

The URL frontier

The frontier is the brain. It decides what to fetch and when.

• Priority: important or frequently changing pages first. Priority queues ordered by a score (for example link popularity or freshness).
• Politeness: one queue per host, and each host is handled by one worker that waits between requests (for example one request per second to a given site).

100%

Figure SDA-CSD-05-3 · URL frontier: priority and politeness · © forcsguy.com

Because the frontier is huge, keep most of it on disk with an in-memory buffer at the front.

Keeping one polite worker per host

100%

Figure SDA-CSD-05-4 · Politeness queues · © forcsguy.com

Not doing the same work twice

• URL seen: before queueing a link, check it. A Bloom filter (or a hash set partitioned across servers) keeps this small and fast. Normalise URLs first (lowercase host, remove fragments, sort query parameters).
• Content seen: pages often exist under many URLs. Compare a hash of the content, or a similarity fingerprint for near duplicates, and skip repeats.

Staying out of trouble

• robots.txt: fetch and cache it per host, and obey it.
• Spider traps: endless generated URLs. Cap URL length, link depth and pages per host.
• Timeouts and size limits so one slow or giant response cannot stall a worker.
• Dynamic pages: content built by JavaScript needs a rendering step, which is much more expensive.
• Harmful content: filter spam or illegal material before storing or indexing.

More ways to make it fast and robust

• Two-stage frontier. Front queues carry priority (each queue has a score band and is picked with a bias toward the higher bands); back queues carry politeness (one host per queue). A URL passes through both, so you get "important first" and "gentle per site" together.
• Freshness. Recrawl by observed change history, and re-visit important pages more often. Recrawling everything is too costly.
• DNS is a hidden bottleneck. Lookups can take tens to hundreds of milliseconds and many resolver interfaces block a thread, so keep your own DNS cache and refresh it on a schedule.
• Locality and timeouts. Put crawl servers near the sites they fetch from, and give each fetch a short timeout so one slow host cannot stall a worker.
• Robots rules are fetched once and cached, then obeyed before each fetch.
• Resilience. Spread URLs over downloaders with consistent hashing, checkpoint the crawl state so a crash resumes instead of restarts, and validate pages before storing them.
• Extensible by modules. New content types (images, a copyright monitor) plug in after the downloader without redesigning the pipeline.
• Noise. Skip ad blocks, spam and low-value pages with a quality filter; cap URL length and per-site page counts to limit spider traps, and have a person exclude sites that still trap you.
• Beyond search. The same engine serves archiving, mining and brand or copyright monitoring.

100%

Figure SDA-CSD-05-5 · Plugging new modules into the crawler · © forcsguy.com

100%

Figure SDA-CSD-05-6 · Distributing the crawl · © forcsguy.com

Scaling and reliability

• Add many fetcher workers, partitioned by host (consistent hashing keeps assignments stable).
• Make workers stateless and checkpoint the frontier, so a crashed worker's URLs are re-queued.
• Spread crawlers across regions to be closer to the sites being fetched.
• Re-crawl by schedule: pages that change often (news) are revisited more often than static ones.

Worked numbers: why it is about many hosts, not one fast fetcher

Target: 1 billion pages a month, about 400 pages per second, at about 500 KB each.

• Bandwidth: 400 x 500 KB = 200 MB/s, about 1.6 Gbit/s sustained, before retries and robots.txt fetches. Many machines in several places, not one big link.
• Politeness sets the shape. If you allow one request per second per host, then to fetch 400 pages a second you must be talking to at least 400 different hosts at the same moment. A single site with 100,000 pages would take 100,000 seconds, nearly 28 hours, to crawl at that pace. So a crawler is a scheduler that interleaves thousands of hosts, which is exactly what the per-host queues do.
• Seen-URL memory. With 10 billion known URLs, an exact set of 8-byte hashes is 80 GB. A Bloom filter at about 10 bits per URL (1% false positives) needs 12.5 GB, and a false positive only means skipping a page you could have crawled.
• Storage: 1 billion x 500 KB = 500 TB a month raw. Compress and deduplicate, and keep only what you will index.

100%

Figure SDA-CSD-05-7 · Throughput comes from interleaving many hosts · © forcsguy.com

Staying fresh: not every page needs the same schedule

Re-crawling everything monthly wastes effort on pages that never change and misses news that changes hourly. Practical schedules:

• Keep the observed change history per page (did the content hash change since the last visit?). Visit pages that change often more frequently, and stable pages less often, within limits.
• Use hints: Last-Modified, ETag and conditional requests (If-None-Match) let the server answer "not modified" in a few bytes.
• Give importance a vote: popular pages, and pages that many others link to, are revisited sooner.
• Keep a small fast lane for news and feeds, driven by sitemaps and feed updates.

100%

Figure SDA-CSD-05-8 · Recrawl by how often a page changes · © forcsguy.com

Walking through a spider trap

A calendar page links to "next month", which links to the next month, forever. A naive crawler follows it, fetching millions of near-identical pages from one host. Defences, layered: cap URL length and path depth; cap pages per host per period; detect repeating patterns (the same path with only a number changing); skip pages whose content hash you have seen; and let an operator add a rule when a site still traps you. None is perfect, so budgets per host are the safety net.

Mistakes people make

• Ignoring robots.txt and crawl-delay. It gets you blocked, and it is rude.
• Not normalising URLs. HTTP://Example.com/a?b=1&a=2#top and http://example.com/a?a=2&b=1 are the same page. Lowercase the host, drop fragments, sort parameters, remove tracking parameters.
• One slow host stalling workers. Always use timeouts and size limits.
• Treating the frontier as a plain FIFO. It ignores priority and politeness.
• Fetching JavaScript-built pages as plain HTML. The content may be missing; rendering is a separate, costlier pipeline.
• No deduplication of content. The same article under ten URLs wastes storage and pollutes the index.

Try it yourself

Build the Bloom filter lab and measure its false-positive rate and memory against an exact set, then read the seen filtering lesson. The consistent hash ring lab shows how to assign hosts to crawler workers so assignments stay stable.

Real-world reading