Design a Web Crawler

Design a Web Crawler

Step 1 of 10

target1 B pages

A billion pages to fetch, and the queue of what to visit next — the frontier — is the entire design.

The Idea

Fetch a billion pages without hammering any single host and without fetching the same page twice. The frontier — the queue of what to visit next — is the whole design, and it is partitioned by host.

Real-World Example

Post delivered street by street. One walker per street, a steady pace between doors, and a list of addresses already covered so nobody walks the same road twice.

The Tradeoff

Sharding the frontier by host gives politeness for free: one queue, one worker, one delay. It also lets a slow host starve its own queue while other workers sit idle, since nobody else may take that work. A hash set catches repeat URLs in a single lookup, and a mirror still needs a fingerprint of the content to be recognised.

Your turn

Put the steps in the right order.

1. 1Fingerprint the body and skip it if those bytes have been seen before↑↓
2. 2Pop the next URL from that host's queue, respecting its crawl delay↑↓
3. 3Push newly discovered links into the frontier, dropping URLs already seen↑↓
4. 4Check the host's robots rules before fetching↑↓

Check order

Mini quiz

1 / 3

The frontier is partitioned by host so that:

• AURLs sort alphabetically
• BOne worker owns a host and can pace itself
• CDuplicates disappear
• DRobots rules can be ignored