Lesson 6.6 · 25 min
Web crawler
Crawl a synthetic web with 50 fetchers and watch plain BFS send 189 requests a second to one site, fix it with per-site queues, defuse a calendar trap, and catch near-duplicate pages with SimHash.
The idea in plain words
A web crawler is a robot reader: it downloads a page, notes every link on it, then downloads those pages too, over and over. The hard part is doing it billions of times politely, without repeating itself or getting lost in endless pages.
The problem it solves
To build a search index you need copies of billions of pages, fetched continuously, without overloading any website, downloading the same thing twice, or getting stuck in endless links.
How it works
- Start from a list of seed URLs in a to-do list (the frontier).
- Take a URL, check robots.txt, download the page.
- Extract its links, skip ones already seen, and add the rest to the frontier.
- Keep one queue per website so each site gets only a polite trickle of requests.
- Spread websites across many crawler machines.
Example
Crawling 1 billion pages a month is about 400 pages per second overall, but each site gets at most one request every few seconds. So the crawler works on thousands of sites at once rather than hammering a few.
Key terms
- URL frontier
- The to-do list of links waiting to be downloaded.
- Politeness
- Limiting how often you hit one website so you don’t overload it.
- robots.txt
- A file where a site says which pages crawlers may visit.
- Bloom filter
- A compact structure that says “definitely not seen” or “probably seen”.
- Crawler trap
- A site that generates endless URLs, such as a calendar with infinite “next month” links.
In this lesson you'll learn
- How to size a crawler: pages per second, bandwidth, storage and the seen-URL set.
- How a frontier of per-site queues keeps crawling fast and polite, and how priority and trap limits steer it.
- How URL and content dedup work at scale, and how to defend a crawler design.
Sections
- Requirements and numbers
- Data
- Architecture
- Deep dive: the frontier
- Deep dive: dedup and traps
- Design review
Cheat sheet
| Frontier | priority → per-host queues |
|---|---|
| Politeness | 1 connection per host + delay |
| Seen URLs | Bloom filter, ~10 bits/URL |
| Same content | hash + SimHash |
| Traps | depth, length, per-host caps |
The interactive simulations and the scored design review load with JavaScript.