Web Crawler

What the interviewer is asking

"Design a web crawler" means design the program that downloads the web for a search engine: start from a few known pages, fetch them, pull out their links, fetch those, and keep going. No user ever sees it: the hard parts are fetching a billion pages a month without hurting the sites you visit, fetching any page twice or getting lost in sites that never end. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Start from seed URLs, a list of well-known pages.
• Fetch pages and follow their links, again and again.
• Store each page for the search engine's indexer.
• Be polite: obey robots.txt and never overload a site.
• Never fetch the same page twice.

Name the rest and park it: running each page's JavaScript to see what it draws, ranking, recrawling news sites within minutes (freshness), and images or video. Politeness and duplicates are not extras: a crawler that floods small sites gets blocked, and one that refetches pages wastes most of its work.

2. Data: the frontier, the seen set and the pages

data        what it holds
frontier    URLs waiting to be fetched, seeds first
seen set    every URL ever queued, fetched or not
page file   the HTML, in object storage
page row    URL, fetch time, content hash, file key

The frontier is the to-do list. The seen set answers one question for every link the crawler finds: have we queued this URL before? Pages are big blobs read whole, so the HTML goes to object storage under a key, and a small row keeps the URL, when it was fetched, a hash of its content and the file's key. The indexer finds pages through the rows; the hash spots the same content under different URLs.

3. The API: none public

A crawler has no users clicking buttons, so it has no public API. Say so, and describe its inputs and outputs instead:

takes:  seed URLs
        limits: gap per host, page budget per site
gives:  stored pages
        + a note to the indexer per new page

Don't offer a call the search page makes to fetch pages live: a search must answer in a fraction of a second from an index built ahead of time, and live fetches would take seconds and hit sites on every search.

4. The busy path: the fetch loop

1. Take the next URL from the frontier.
2. Look up the host's IP address (DNS).
3. Download the page with an HTTP GET.
4. Save the page in the page store.
5. Pull the links out of the page and make them full URLs: a link to /about on shop.com becomes https://shop.com/about.
6. Queue the links the seen set hasn't seen.

Steps 2 and 3 are what a browser does when you open a link; the crawler runs this loop for every URL, all day.

5. The numbers

From the interviewer: 1 billion pages a month, and an average page of 100 KB. A month has about 2.6 million seconds.

• Pages a second: 1 billion ÷ 2.6 million ≈ 385, so about 400 a second. A crawler has no busy hours: it sets its own pace, so plan for the average, not 5× it.
• Storage: 1 billion × 100 KB = 100 TB a month, about 300 TB with 3 copies, and 1.2 PB of pages a year.
• Bandwidth: 400 × 100 KB = about 40 MB a second, small next to the 1 GB a second one server's network carries.
• Fetcher machines: a fetch mostly waits (on DNS, on connecting, on a slow server), say 1 second in all, so about 400 fetches are in flight at any moment. If one machine keeps 100 going and finishes about 100 pages a second, that's 400 ÷ 100 = 4 machines, plus a spare.

The surprise is how few machines it takes: the work is waiting, not computing, so each machine runs many fetches in parallel.

6. Services

• URL frontier: holds the URLs to fetch and hands each fetcher its next one.
• Fetchers: look up the host through a DNS cache (a lookup can take a round trip or more, and thousands of URLs share one host), download the page, save it and hand it to the parser.
• Parser: pulls out the links, makes them full URLs, drops the ones already in the seen set and queues the rest.
• Seen set and page store, as above.

Fetchers wait on the network while the parser keeps a CPU busy, so each grows on its own. The frontier works like a message queue with the fetchers as its workers: a URL is done only once its page is saved, so the URLs of a fetcher that crashes are handed out again, and a URL that keeps failing is retried a few times, with growing waits, then dropped.

7. Scale: split the frontier by host

One frontier machine is a single point of failure, and the frontier keeps growing, since most pages add more new links than the one URL they used up. Split it over several machines by a hash of the host name, so all of a site's URLs land on one machine. That machine alone knows when the site was last fetched, so politeness stays simple, and the site's robots.txt rules and DNS answer are kept in one place. With consistent hashing, adding a machine moves only a slice of the hosts.

Hashing the whole URL spreads URLs more evenly but sends one site's URLs to every machine, and each would fetch from it on its own clock. Splitting by the time a URL was found makes a hot spot: every new URL goes to one machine at a time. A huge site is no hot spot under host hashing either, because politeness caps how fast it's fetched anyway. The seen set can be split the same way.

8. Deep dive: BFS and crawler traps

The crawl is a breadth-first search over links. The frontier is a FIFO queue: take the URL at the front, and new links join the back. On a tiny web with seed A, each page's links in the order they appear on it:

fetch   new links   frontier after
A       C, F        C F
C       B, E        F B E
F       D           B E D
B       G           E D G
E       none        D G
D       none        G
G       none        empty

The fetch order, A, C, F, B, E, D, G, goes level by level: the seed, then pages one link away, then two. A stack instead would dive down one chain of links first (depth first).

Some sites never end. A calendar whose every month links to the next has a new URL for every month, forever, so the seen set can't stop it: no URL ever repeats. These are crawler traps. Two limits handle them: a page budget per site per crawl (say 10,000 pages, more for big, well-linked sites) and a depth limit on how far from a seed the crawler follows links. Depth first would make a trap worse: it would follow "next month" and never come back.

9. Deep dive: politeness

Never send a site more than one request every few seconds, say 2. Each frontier machine keeps one queue per host and the time each host may next be fetched. Before a host's first page, the crawler reads the host's robots.txt and skips the paths it disallows. Here are 6 URLs from 2 hosts, with one fetcher, 1 second a fetch and a 2-second gap per host; the fetcher always takes the host whose turn comes first:

second   fetch   shop.com next   news.org next
0        s1      2               0
1        n1      2               3
2        s2      4               3
3        n2      4               5
4        s3      6               5
5        wait    6               5
6        s4      8               5

At 5 s news.org has nothing left and shop.com isn't allowed until 6 s, so the fetcher waits. This is rate limiting turned around: the crawler limits itself. One big site alone is slow by design; with thousands of hosts in the frontier, some host's turn has almost always come, so the fetchers stay busy.

10. Deep dive: duplicates and the Bloom filter

The seen set must hold every URL: 1 billion at about 100 bytes is 100 GB of memory, growing with every crawl. A Bloom filter answers "seen?" in far less by keeping bits instead of URLs. To add a URL, hash functions turn it into positions in a bit array and set those bits to 1; to check a URL, look at its bits. Any 0 means definitely new; all 1s means maybe seen.

A toy filter of 12 bits with two hash functions (here FNV-1a and djb2, two classic string hashes, each taken mod 12):

URL              h1   h2   result
shop.com/sale    0    4    added
news.org/team    6    10   added
blog.net/post    11   3    added
shop.com/help    8    0    bit 8 is 0: definitely new
shop.com/deals   6    0    both 1: maybe seen

shop.com/deals was never added, but news.org/team and shop.com/sale set its two bits, so the crawler skips it: a false positive. It costs a page missed now and then, never a page fetched twice, because a URL that was added always finds its own bits set. With half of its 12 bits set, the toy says maybe for about 1 new URL in 4. A common size is about 10 bits per URL with 7 hash functions, for under 1% false positives: 1 billion × 10 bits = 1.25 billion bytes, about 1.2 GB, 80× less than the plain set. Keeping an 8-byte hash of each URL would take 8 GB: exact enough, but bigger.

Different URLs can also serve the same page: with and without www, or with tracking tags. Normalize URLs before checking them, and compare content hashes to catch the copies that remain.

What breaks first

• A fetcher dying mid-fetch: its URLs come back from the frontier after a timeout; saving pages by URL makes a second fetch harmless.
• Slow or dead sites: short timeouts keep one slow server from holding a fetch slot for minutes.
• The Bloom filter filling up: false positives climb once it holds more URLs than it was sized for; size it ahead, or start a new one for each crawl.
• Spam and junk sites: page budgets limit the damage; ranking later decides what's worth keeping.

Summary: the order to follow

1. Scope: seeds in, pages out, politely, never a page twice.
2. Data: the frontier, the seen set, pages in object storage with a small row each.
3. API: none public; seeds and limits in, pages out to the indexer.
4. Busy path: take, look up, fetch, save, extract, queue.
5. Numbers: about 400 pages a second, 100 TB a month, 4 fetcher machines.
6. Services: frontier, fetchers with a DNS cache, parser, seen set, page store.
7. Scale: the frontier split by host.
8. Deep dives: a FIFO frontier with page budgets and depth limits; a queue and a next turn per host; a Bloom filter for URLs and content hashes for pages.

The same steps work for any "design X" question.