Web crawler

Visit a billion web pages a month by following links, without hammering any one website and without fetching the same page twice. The hard parts are the URL frontier (what to fetch next, and when), the seen-set that does not fit in memory, and crawler traps.

Design a web crawler that fetches 1 billion web pages a month, finds new pages by following links, is polite to the sites it visits, avoids duplicates, and keeps pages reasonably fresh.

Requirements

Functional

Start from a list of seed URLs (the first addresses to visit), fetch each page, extract its links, and visit the new ones. Repeat until told to stop.
Store every fetched page (compressed HTML and the time it was fetched) for a later step, such as a search index, to read.
Be polite: obey robots.txt (the file where a site says what a crawler may visit; it is a convention that polite crawlers follow by choice) and never send more than about one request per second to one host.
Never fetch the same URL twice in one crawl, and do not store the same content twice when two URLs show the same page.
Re-crawl pages over time: a page that changes often is visited more often than one that rarely changes.

Non-functional

Scale: 1 billion pages a month, each refreshed about once a month on average. That is about 400 pages a second, planned with 2 times headroom for a peak of about 800.
Politeness: at most about 1 request per second per host, or the Crawl-delay a site asks for. A site must never see our crawler as an attack.
Throughput: the crawl must keep about 200 fetches in flight at once (400 pages a second times about 0.5 s each). One slow site must not hold up the rest.
Fault tolerance: a worker that dies mid-fetch loses no work. Its URLs go back to the queue and are fetched again, which is safe.
Freshness: pages that change hourly are re-visited within hours. Pages that rarely change are visited at most every 30 days.
Extensible: a new stage (for example a virus check or a language detector) can be added after the fetch without changing the fetchers.

Out of scope

Ranking, indexing and search over the pages (they read from the page store).
Pages that need JavaScript to show their content (mention a separate, slower pool of headless browsers, do not design it).
Images, video and other large files, and logging in to private pages.

Estimate

Pages: 1B pages a month / (30 days x 86,400 s ≈ 2.6M s) ≈ 385, so about 400 pages a second on average. Plan for 2x headroom: about 800 at peak.
Bandwidth: 400 pages x 100 KB average HTML = 40 MB a second ≈ 320 Mbit a second coming in. One good network link per few fetchers, nothing exotic.
Storage: 1B pages x 100 KB = 100 TB raw. Compressed about 3 to 1 gives about 33 TB for one full copy of the web. Three copies for safety is about 100 TB.
Links: 50 links per page x 400 pages a second = 20,000 URLs a second to check against the seen-set. Most are already known, so the check must be very cheap.
Seen-set: about 5B distinct URLs known (1B fetched, 4B found but waiting or skipped). Full strings at 100 B = 500 GB. An 8-byte hash of each = 40 GB. A Bloom filter at 10 bits per URL = 5B x 10 bits = 50 Gbit ≈ 6 GB.
Fetch slots: Little's law says slots in use = rate x time per fetch = 400 x 0.5 s = 200 fetches in flight. With 10 fetchers at 50 slots each we have 500 slots, 2.5 times the need.
Politeness: at 1 request per second per host, reaching 400 pages a second needs at least 400 different hosts active at once. One host alone gives at most 86,400 pages a day.
Frontier: if 1B URLs wait at about 100 B each, that is about 100 GB of queues. It lives on disk, with only the front of each queue in memory.

API

POST /v1/crawls {seeds[], allowed_domains[]?, max_pages?, max_depth?} -> 201 {crawl_id}
POST /v1/crawls/{crawl_id}/seeds {urls[]} -> 202 (adds more starting points to a running crawl)
GET /v1/crawls/{crawl_id} -> 200 {state, pages_fetched, frontier_size, error_rate}
GET /v1/pages?url= -> 200 {url, fetched_at, status, content_hash, storage_key} (the stored copy, for the next stage)
PUT /v1/hosts/{host}/policy {crawl_delay_ms?, blocked?} -> 204 (an operator override for one host)
POST /internal/frontier/lease {worker_id, max_urls} -> 200 {lease_id, urls[], expires_in_s} (a fetcher asks for work)
POST /internal/frontier/ack {lease_id, results[]} -> 204 (a fetcher reports each URL as done, failed or moved)

Data model

urls(url_hash PK, url, host, state new|queued|fetched|failed, priority, depth, last_fetch_at, next_fetch_at, change_interval_s, etag, content_hash): key-value access by url_hash, sharded by host.
hosts(host PK, robots_rules, robots_fetched_at, crawl_delay_ms, next_allowed_at, ip, ip_fetched_at): one row per site; drives politeness and the DNS cache.
frontier queues (per host): FIFO of url_hash entries with a priority class, plus a lease record {lease_id, worker_id, expires_at} per batch handed out.
content_fingerprints(content_hash PK, first_url_hash, first_seen_at): one row per distinct page body; a hit means the content is a duplicate.
page store (object storage): key = url_hash + fetch time, value = compressed HTML. The next stage reads from it.

A request, step by step

Start: the operator posts seed URLs to the controller. The controller normalises them, records them in the URL store as new, and adds them to the frontier. The frontier is split into shards by a hash of the host name, so all URLs of one host live on one shard.
Lease: a fetcher asks the frontier for work. The shard looks at its hosts whose next-allowed time has passed, picks by priority, and hands out a batch of URLs from different hosts with a lease (a right to work on them that expires, say after 2 minutes). Each host is now busy until its URLs are acknowledged and its delay has passed.
Fetch: for each URL the fetcher gets the host's IP and robots.txt rules from the cache (looking them up once if missing). If the rules allow the path, it sends a GET with a timeout and a size cap. It uses a conditional GET (If-None-Match or If-Modified-Since) for pages it has seen before.
Save: the fetcher writes the compressed page to the page store, publishes "page saved" to the parse queue, and acknowledges the lease with the result. A 304 Not Modified only updates the next-crawl time. A failure is retried later with a longer wait.
Parse: a parser reads the page. It hashes the text into a content fingerprint and looks it up. If the fingerprint is known, the page is a duplicate and its links are skipped. Otherwise it extracts the links.
Normalise and check: each link is made canonical (lowercase host, no fragment, sorted query, tracking parameters removed), then hashed. The parser checks the seen-URL cache first, and the URL store on a miss. The checks are batched: about 50 links in one call.
Enqueue: URLs not seen before are written to the URL store as queued and added to the frontier with a priority, a depth (the hops from a seed) and the host's queue. URLs past the depth limit or the host's page budget are dropped here. The loop closes.
Failure: if a fetcher dies, nobody acknowledges its lease. When the lease expires, the frontier puts the URLs back at the front of their host queues. Fetching a page twice is harmless, so no state needs repair.

Deep dives

The URL frontier: priority and politeness

The frontier decides what is fetched next. It has two jobs that pull in opposite directions: fetch important pages first, and never hit one host too fast.

Weak: one FIFO queue. The crawler takes the next URL from a single line. A site with 10,000 pages puts 10,000 entries in a row, so the crawler sends 10,000 requests to one host back to back. That is an attack from the site's side. It also fetches boring pages ahead of important ones.

Good: one queue per host, with a delay. URLs are sorted into a queue per host. Each host has a next-allowed time. After a fetch, the time moves forward by the delay (1 second by default, or the Crawl-delay in robots.txt, a non-standard line that some crawlers honour). A min-heap of hosts ordered by next-allowed time tells us which host may be fetched now. With 400 pages a second and 1 request per second per host, at least 400 hosts must be active at once.

Great: priority queues in front, host queues behind. Front queues rank URLs by priority: how often the page is linked, how fast it changes, how shallow it is. A chooser picks a front queue (high priority more often) and moves the URL into its host queue. The host queues enforce politeness. Shard the whole structure by host hash, so each shard owns its hosts and needs no coordination to keep the delay. A fetcher leases a batch with an expiry.

Trade-off: per-host queues limit speed on one big site. At 1 request per second, one host gives 86,400 pages a day. A site with 50 million pages would take about 1.6 years (50M / 86,400), so large hosts need a page budget per cycle, or a higher rate agreed with the site. The frontier is also the largest piece of state (about 100 GB), so it lives on disk with only the queue heads in memory.

Not fetching twice: URLs and content

Two kinds of duplicate exist. The same URL can be found many times (20,000 link checks a second). Different URLs can also show the same content.

Weak: look up every full URL in a database table. The strings take about 500 GB for 5 billion URLs, and 20,000 lookups a second against long strings is slow. The same page also hides behind many spellings: HTTP and HTTPS, a trailing slash, a #fragment, a tracking parameter, a different query order.

Good: normalise, hash, and keep a Bloom filter. First make the URL canonical: lowercase the scheme and host, drop the default port and the fragment, resolve ../ segments, sort the query, remove tracking parameters. Then hash it to 8 bytes. A Bloom filter is a compact bit array that answers "have I seen this?" with "definitely not" or "probably yes". At 10 bits per URL, 5 billion URLs need about 6 GB and the false-positive rate is about 1%.

A false positive means a new URL is wrongly treated as seen, and it is never crawled until the filter is rebuilt. A Bloom filter never gives a false negative, so nothing is fetched twice. It also cannot delete an entry, grow after it is built, or list its contents.

Great: an exact sharded store, with a small cache in front. Keep the 8-byte hashes (about 40 GB) in a key-value store sharded by host, with the crawl state beside each hash. A cache of recent and popular URLs absorbs the many repeat links to popular pages. The parser checks 50 links in one batched call, so the store sees about 400 calls a second, not 20,000. With 8-byte hashes, expect about one colliding pair in the whole set, which skips one page in 5 billion. Use 16-byte hashes (80 GB) if that is too many.

Trade-off: the Bloom filter is cheaper (6 GB against 40 GB plus a store) but loses about 1% of new URLs and cannot hold per-URL state. The exact store costs more and lets you keep schedules and change history in the same row.

Content duplicates: hash the page text (tags and scripts removed) into a fingerprint, and keep fingerprints in their own store. A hit means a mirror or a repeat. Skip its links and store it once. For near-duplicates, a similarity hash such as SimHash gives close pages close fingerprints, at more compute cost and some risk of merging pages that differ in a way that matters.

Crawler traps and freshness

Both problems are about spending a fixed fetch budget on pages worth fetching.

Traps. A trap is a set of URLs that never ends. A calendar page links to "next month", and that page links to the month after, for ever. A session id in the URL makes every visit look like a new page. Two folders that link to each other build paths such as /a/b/a/b/a/b.

Weak: hope the seen-set catches it. Each calendar month is a different URL, so the seen-set sees every one as new. The crawler spends its whole budget on one site.

Good: depth and size limits. Track depth (hops from a seed) and stop at a limit such as 15. Cap the URL length (say 2,000 characters). Keep a page budget per host per cycle.

Great: layered limits, learned from the data. Add normalisation that strips session ids. Detect repeating path segments. Watch the duplicate rate and the new-link rate per host. If the last 100 pages of one host were near-duplicates, or the host keeps producing new URLs with no new content, lower its budget and alert someone. Pages with many outside links get a deeper allowance, so a real deep forum is not cut off.

Freshness. Keeping a page up to date costs fetches. If 1 million news pages were refreshed every hour, that is 1,000,000 / 3,600 ≈ 280 fetches a second: 70% of the whole 400 a second budget.

Weak: refresh everything at the same interval. Good: a rule by page type. Great: learn each page's change rate. Each visit compares the content hash with the last one. If the page changed, halve its re-crawl interval (down to 1 hour). If not, double it (up to 30 days). Send a conditional GET with the stored ETag, so an unchanged page returns a 304 with no body.

Trade-off: the adaptive rule saves most of the budget, but a page that changes rarely and then suddenly matters (a recall notice) may be stale for weeks. Let seeds, feeds and sitemaps (a site's own list of its pages) trigger a visit sooner.

Distributing the crawl and surviving a dead worker

One machine cannot hold 200 fetches in flight, 100 GB of queues and 40 GB of hashes, so the work is split. The question is how.

Weak: any worker takes any URL from a shared list. Two workers can fetch the same host at the same moment, so politeness is lost. Every worker needs the full seen-set and robots rules.

Good: partition by host. A hash of the host name picks the shard. All URLs of one host go to one shard, so that shard alone enforces the delay, holds the host's robots rules and IP, and owns its slice of the seen-set. Use consistent hashing (a scheme that moves only a small share of hosts when a shard is added or removed) so growth does not reshuffle everything.

Great: partition by host, and lease the work. Shards hand batches to stateless fetchers with a lease. The fetcher acknowledges each URL when done. If the lease expires with no acknowledgement, the URLs return to their host queue with a retry count. After 3 failures a URL moves to a failed state with a longer wait (1 hour, then 1 day).

This is safe because every step can be repeated. Fetching a page twice wastes one request. Saving it twice overwrites the same key. Re-adding a link is blocked by the seen-set.

A dead frontier shard is handled by keeping its queues in a replicated log, so a standby loads them and takes over. The new owner waits one full delay per host before the first fetch, because it does not know when the old owner last sent a request.

Trade-off: a short lease finds dead workers fast but may hand a slow page to a second worker. A long lease wastes time when a worker dies. Two minutes with a heartbeat (a small "still working" signal) is a reasonable middle.

What breaks

A fetcher dies mid-fetch: the lease expires with no acknowledgement and the frontier puts the URLs back. You notice a jump in expired leases and a dip in pages per second. Fetching twice is harmless, so there is nothing to repair.
A trap swallows the budget: one host produces millions of new URLs with the same content. You notice the host's duplicate rate and frontier share rising. The page budget and depth limit cap the damage, and an alert tells an operator to block or lower that host.
A site slows down or answers 429 or 5xx: the crawler backs off for that host (double the delay each time, honour Retry-After) and moves on. Without per-host queues, slow sites would fill all 500 fetch slots.
Slow servers and DNS: with 500 slots, if every fetch hung for 30 seconds, throughput would fall to 500 / 30 ≈ 17 a second. So set timeouts (a few seconds for DNS and connect, 30 seconds in total) and a size cap of a few MB. Alert on p99 fetch time.
The page store or the parse queue is slow: parsing falls behind and the queue grows. Fetching can continue for a while because the queue buffers, then slow down fetchers when its depth passes a limit. The oldest-message age is the alert.
The URL store loses a shard: replicas take over. If a whole hash range were lost, the crawler would forget which URLs it had seen and refetch some pages. That wastes budget but breaks nothing, which is why the store is replicated and the steps are repeatable.

What each level is expected to cover

Mid level: A Mid candidate should draw the crawl loop and size it: about 400 pages a second, 40 MB a second of bandwidth, tens of terabytes of storage. They should put a frontier with a queue per host and a delay in front of stateless fetchers, add a seen-set, and say it will not fit in memory as full strings. They should mention robots.txt and a trap, and say a dead worker's URLs go back to the queue.

Senior: A Senior candidate also compares a Bloom filter with a sharded exact store, with the memory and false-positive numbers. They design the frontier with priority queues in front of host queues, partition by host, and use leases. They handle traps with layered limits, set re-crawl intervals from observed change, use conditional requests, and explain how politeness limits one huge host. They say how they would know the crawl is healthy.

Common mistakes

Drawing a loop of fetch, parse and add, and calling it done: no frontier, no politeness, no seen-set, no numbers.
One global queue, so a big site gets thousands of requests in a row. Politeness needs a queue per host and a delay.
Keeping every full URL in a memory set without doing the arithmetic. 5 billion URLs at 100 bytes is 500 GB.
Using a Bloom filter without saying that false positives mean some new pages are never crawled, or that you cannot remove an entry.
Ignoring crawler traps, so one infinite calendar uses the whole budget.
Skipping robots.txt, DNS caching and timeouts, then finding that one slow host holds every worker.
Re-crawling every page at the same interval, which wastes most of the budget on pages that never change.
Treating a worker crash as a data-loss problem. With leases and repeatable steps it is only a retry.

Follow-up questions

How would you crawl the same billion pages in a week instead of a month? (About 1,650 pages a second, 165 MB a second of bandwidth, at least 1,650 active hosts: the same design with more fetchers, but huge hosts become the limit.)
How do you handle pages that need JavaScript to show their content?
How do you find new pages on a news site quickly, without waiting for the next full visit? (Feeds, sitemaps, and a short interval for the site's hub pages.)
A site owner emails to say you are hitting them too hard. What do you change, and how fast?
How would you crawl from several data centres, and which one fetches a given site?
How do you decide which pages are important enough to fetch first?