Build the crawler up, one problem at a time

Part of the free System Design course on LogicWiz, in the chapter: Design a web crawler. The interactive whiteboard exercises and simulations run in the app.

Week 19: Build the crawler up, one problem at a time

"The crawler ran on one machine for a week. On day 8 the disk filled and the process died. Nobody could say which pages it had already visited."

Meera, on the version-one postmortem

Version one: a loop on one machine

Start with the simplest design, as you would on the board. One machine runs the loop: take a URL, fetch it, save it, extract links, add the new ones. A set in memory remembers what was seen.

What breaks first is time. One fetch takes about 0.5 seconds, almost all of it waiting for the network. Done one at a time, that is 2 pages a second. A billion pages then take 1 billion / 2 = 500 million seconds, about 16 years. We need 400 a second.

The CPU sits idle while it waits, so fetch many pages at once. The estimate said about 200 fetches must be in flight. A machine that uses non-blocking network calls can keep about 50 downloads open. So run ten fetchers, workers that only download pages. Ten x 50 = 500 slots, 2.5 times the need, which leaves room for slow sites. A fetcher keeps no state: it asks for work, does it and reports back.

A frontier that is polite

Put those ten fetchers on one plain queue and you get the shop outage from the opening quote. A site with 10,000 pages puts 10,000 URLs in a row, and the fetchers send them all at once.

The fix is to make the frontier many queues, not one: a queue per host. Each host has a "next allowed" time. After a fetch, move it forward by the delay: 1 second by default, or the Crawl-delay value in robots.txt, the pause the site asks for (a non-standard line that some crawlers honour, and ours does). A fetcher only receives URLs from hosts whose time has come. We also put priority queues in front, so important pages (many links point to them, or they change often) are picked first. Lesson 3 builds this in detail.

Two small helpers sit beside the fetchers:

  • robots.txt rules. Fetch the file once per host, keep it for about a day, and check each path against it before fetching.
  • A DNS cache. DNS turns a host name into an IP address, and a lookup can take tens of milliseconds before every fetch. Pages of one host are fetched close together, so keep the answer for its TTL (the time it may be reused). This also protects the resolver from 400 lookups a second.

Both fit in one small in-memory cache, replicated so that losing one copy does not stall the crawl.

The parse stage, and where pages live

Fetching waits on the network. Parsing, which reads the HTML, uses the CPU. They scale differently, so split them. The fetcher saves the page to object storage, cheap storage for large files, because 33 TB does not belong in a database. Then it puts a "page saved" message on a parse queue.

Meera asked, "Why not parse right after the fetch, in one step?" Kabir gave a case. A bad parser release failed for ten minutes. With one step, the fetchers either stalled or threw away pages they had already paid for. With a queue, the saved pages simply waited, and parsers caught up after the fix.

A parser does three things:

  1. Hash the page text into a fingerprint. If the same fingerprint is already stored, the page is a duplicate (a mirror, or two URLs for one page). Stop.
  2. Extract the links and make each one canonical: lowercase host, no #fragment, sorted query. Hash it to 8 bytes.
  3. Ask the seen-set which hashes are new. New ones go to the frontier.

The seen-set takes 20,000 checks a second. We keep the 8-byte hashes, about 40 GB, in a key-value store with several copies, with a small cache of recent URLs in front. The parser sends 50 links in one call, so the store sees about 400 calls a second. Lesson 3 compares this with a Bloom filter.

Splitting the work by host, with leases

Assume 1 billion URLs wait in the frontier at about 100 bytes each: 100 GB of queues. One machine can hold that on disk, but it is a single point of failure. So partition by host: a hash of the host name picks the frontier shard. All URLs of one host land on one shard. That shard alone enforces the delay, so no two machines ever need to agree on how fast to hit a host.

Fetchers ask a shard for a batch of URLs, and every batch comes with a lease: the right to work on those URLs, which expires after about 2 minutes. The fetcher acknowledges each URL when done. If a fetcher dies, nobody acknowledges. The lease runs out and the frontier puts the URLs back in their host queues. Fetching a page twice wastes one request and breaks nothing, so no repair is needed. That is how a dead worker loses no work.

One URL, start to finish

flowchart LR
  C["Controller"] --> FR["Frontier shards"]
  FR -->|"lease"| FE["Fetchers"]
  FE --> W["The web"]
  FE --> PS["Page store"]
  FE --> PQ["Parse queue"]
  PQ --> PA["Parsers"]
  PA --> FP["Fingerprints"]
  PA --> SC["Seen cache"]
  SC --> US["URL store"]
  PA -->|"new URLs"| FR

A new URL starts as a link on a parsed page. The parser normalises and hashes it, the cache and URL store say it is new, and it joins the queue of its host on the right shard. Later a fetcher leases it, checks the DNS and robots cache, downloads the page and saves it. A message goes on the parse queue. A parser reads the page, finds no matching fingerprint, extracts its links, and the loop closes.

Now draw it. Every box should answer one of the numbers above.

📌 Summary: Start with the loop, then fix what breaks: many fetchers, a queue per host with a delay, a parse stage behind a queue, shards by host, and leases for dead workers.

What Meera learns next

The boxes are drawn. Next: the three hard parts in depth (the frontier, the seen-set and traps), what breaks, and how a Mid and a Senior answer sound.

Check your understanding

  1. A one-machine crawler fetches one page at a time, 0.5 seconds each. What is the first fix, and why?
  2. All URLs go into one shared FIFO queue, and ten fetchers take from the front. A shop with 10,000 pages is added. What happens?
  3. A bad parser release fails for ten minutes. Fetchers and parsers are separated by a queue. What happens to the pages fetched in that time?
  4. A fetcher holds a lease on 50 URLs and its machine dies. What does the system do?