What a crawler is, and how big it gets

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: Design a web crawler

"We pointed the first crawler at one shop's website. By morning it had asked for the same calendar page 40,000 times, and the shop's server was down."

Kabir, on the first crawler he ever wrote

What a crawler is, and why SwiftKart wants one

SwiftKart's product team has an idea: "Cook with what you ordered". To suggest recipes, the app needs a copy of recipe pages from across the web. Nobody hands you that. You go and get it.

A web crawler is a program that visits a web page, saves it, reads the links inside it, and then visits those pages too. The addresses it starts from are the seed URLs. The list of addresses still waiting to be visited is the frontier. The whole thing is one loop.

flowchart LR
  F["Frontier: URLs to visit"] --> G["Fetch the page"]
  G --> S["Store the page"]
  G --> P["Parse: extract links"]
  P --> N{"New URL?"}
  N -->|"yes"| F
  N -->|"already seen"| X["Drop it"]

Meera read the loop and said, "That is a queue and a while loop. Where is the hard part?" Kabir answered, "The loop is the easy ten percent. Every page lives on someone else's server. Visit too fast and you break a small shop. Forget what you visited and you repeat yourself for ever. Follow an endless calendar and you never finish." Interviewers ask this question to see whether you notice those three problems before they tell you.

Questions to ask before drawing anything

Ask these five, and write down the answers.

  • What is it for? It feeds a search index. We fetch and store pages. Ranking and search belong to another team.
  • How big? About a billion pages, each visited about once a month on average.
  • How fresh? News pages should be revisited within hours. Pages that never change can wait a month.
  • What content? HTML pages only. Pages that need JavaScript to show their text are out of scope.
  • What are the rules? Be polite. Obey each site's robots.txt, the file where a site says which parts a crawler may visit. It is a convention, not a lock, so a polite crawler follows it by choice. Send at most about one request a second to one site.

Requirements, with numbers

The crawler must start from seeds, fetch pages, store them, extract links and visit the new ones. It must never fetch the same URL twice in one crawl, and it must revisit pages that change. Ranking, search, images, video and pages behind a login are out of scope.

Now the non-functional requirements, each with a number:

  • Scale: 1 billion pages a month.
  • Politeness: at most about 1 request per second per host. A host is one website address, such as shop.example.com.
  • Fault tolerance: a worker that dies loses no work.
  • Freshness: pages that change hourly are revisited within hours. Every other page is visited at least every 30 days.
  • Extensible: a new stage, such as a language detector, can be added after the fetch.

The estimate, step by step

Work through six numbers. Each one will earn a box on the board.

  • Pages per second. A month is 30 x 86,400 = 2.6 million seconds. 1 billion / 2.6 million is about 385. Round it to 400 pages a second, and plan for 2 times headroom, so 800 at peak.
  • Bandwidth. An average HTML page is about 100 KB (we skip images). 400 x 100 KB = 40 MB a second, about 320 Mbit a second.
  • Storage. 1 billion x 100 KB = 100 TB raw. Compressed about 3 to 1, one full copy is about 33 TB.
  • Links. A page has about 50 links. 50 x 400 = 20,000 URLs a second to check against what we have already seen.
  • Seen URLs. About 5 billion distinct URLs are known: 1 billion fetched and 4 billion found. As 100-byte strings that is 500 GB. As 8-byte hashes it is 40 GB.
  • Fetches in flight. One fetch takes about 0.5 seconds for DNS, connect and download. Little's law says the number of jobs in progress equals the arrival rate times the time each takes. So 400 x 0.5 = 200 fetches at once.

Meera's first guess was, "A billion pages is a huge amount of bandwidth, so the network is the problem." The arithmetic says otherwise. 320 Mbit a second is a few ordinary servers' worth of network. The numbers that shape this design are different: 20,000 link checks a second against a set too big to hold as strings, and politeness. At 1 request per second per host, reaching 400 pages a second needs at least 400 different hosts busy at the same time.

Write the estimate yourself before reading on.

The API and the data model

Crawling itself needs no user-facing API. The public API is small: start a crawl, watch it, read a stored page, and override one host.

POST /v1/crawls {seeds[], max_pages?, max_depth?} -> 201 {crawl_id}
GET /v1/crawls/{id} -> 200 {state, pages_fetched, frontier_size}
GET /v1/pages?url= -> 200 {url, fetched_at, content_hash, storage_key}
PUT /v1/hosts/{host}/policy {crawl_delay_ms?, blocked?} -> 204

The data is keyed by the hash of the URL, so a key-value store fits and no joins are needed.

urls(url_hash PK, url, host, state, priority, depth, next_fetch_at, content_hash)
hosts(host PK, robots_rules, crawl_delay_ms, next_allowed_at, ip)
content_fingerprints(content_hash PK, first_url_hash)
pages: object storage, compressed HTML, key = url_hash + fetch time

Hosts get their own table because politeness is decided per host, not per URL.

📌 Summary: Size it first: a billion pages a month is about 400 pages and 20,000 link checks a second. The seen-set and politeness shape the design, not bandwidth.

What Meera learns next

The numbers are on the page. Next: draw the crawler from a one-machine loop and fix what breaks at each step.

Check your understanding

  1. The crawler must visit 1 billion pages every 30 days. About how many pages per second is that on average?
  2. A teammate says a billion-page crawl needs a huge network because "the web is big". Pages average 100 KB and the crawl runs at 400 pages a second. What is the bandwidth?
  3. Each fetched page has about 50 links, and the crawler fetches 400 pages a second. A design checks every link against a table of full URL strings. What load does that table face?
  4. The limit is 1 request per second to any one host, and the target is 400 pages a second. How does the crawler reach that rate?