The hard parts, the failures and the follow-ups

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: The hard parts, the failures and the follow-ups

"The crawler was fast, polite and tidy. Then it spent a whole weekend on one calendar page that links to the year 9999."

Kabir, on the weekend the budget disappeared

The frontier: three ways to build it

The frontier decides what is fetched next. Two jobs pull against each other: important pages first, and gentle treatment of every host.

Weak: one FIFO queue (first in, first out). A site with 10,000 pages gets 10,000 requests in a row, and boring pages are fetched ahead of important ones.
Good: one queue per host, with a delay. Each host has a next-allowed time. A min-heap (a structure that always gives the smallest value first) of hosts, ordered by that time, shows which host may be fetched now. The delay is 1 second or the site's Crawl-delay.
Great: priority queues in front, host queues behind. Front queues rank URLs by how many links point to them, how fast they change, and how shallow they are. A chooser picks a front queue, favouring high priority, and moves the URL into its host queue. Shard it all by host hash, so each shard owns its hosts and needs no coordination.

Trade-off: politeness caps one big site. At 1 request per second, a host gives 86,400 pages a day, so a site with 50 million pages would take about 1.6 years. Give large hosts a page budget per cycle, or a higher rate agreed with the owner. The frontier is also the biggest state, about 100 GB (1 billion queued URLs at 100 bytes each), so it lives on disk with only the queue heads in memory.

Not fetching twice: URLs and content

First normalise each URL: lowercase the scheme and host, drop the default port and the #fragment, resolve ../ segments, sort the query and remove tracking parameters. Then hash it to 8 bytes. Now there are three ways to remember 5 billion hashes.

Weak: full strings in a database table. 5 billion x 100 bytes is 500 GB, and 20,000 lookups a second on long strings is slow.
Good: a Bloom filter. It is a bit array that answers "definitely not seen" or "probably seen". At 10 bits per URL, 5 billion x 10 bits = 50 Gbit, about 6 GB, with a false-positive rate near 1%. It never says "not seen" for a URL it has seen, so nothing is fetched twice. It cannot delete entries, grow after it is built, or store a schedule.
Great: an exact store of hashes, sharded by host. 5 billion x 8 bytes = 40 GB, with the crawl state in the same row. A cache of recent URLs absorbs repeat links to popular pages, and batching 50 links per call turns 20,000 checks into about 400 calls a second. With 8-byte hashes, expect roughly one pair of different URLs to share a hash in the whole set, which skips one page in 5 billion. If that is too much, use 16 bytes and pay 80 GB.

Meera said, "A 1% error is nothing." Kabir asked, "One percent of what?" A false positive means a new URL is judged already seen. It is skipped and never crawled until the filter is rebuilt, and nobody is told which ones. The Bloom filter is cheaper, about 6 GB against 40 GB plus a store. Choose it when memory is tight and losing 1% of new pages is acceptable. Otherwise pay for exactness.

Same content, different URLs. Mirrors and repeat pages are caught by a content fingerprint: a hash of the text with tags and scripts removed, kept in its own store. A match means a duplicate. Store it once and skip its links. To catch near-duplicates, use a similarity hash such as SimHash, which gives similar pages similar fingerprints. It costs more compute and can merge pages that differ in a way that matters.

Traps and freshness: spending a fixed budget

A crawler trap is a set of URLs that never ends. A calendar links to "next month" for ever. A session id in the URL makes every visit look like a new page. The seen-set cannot help, because each URL really is new.

Weak: hope the seen-set catches it.
Good: a depth limit (hops from a seed, say 15), a URL length cap of 2,000 characters, and a page budget per host per cycle.
Great: also strip session ids, detect repeating path pieces, and watch each host's duplicate rate. If the last 100 pages were near-duplicates, lower that host's budget and alert someone. Pages with many outside links get a deeper allowance, so a real deep forum is not cut off.

Freshness spends the same budget. The crawler can do 400 fetches a second. If 1 million news pages were refreshed hourly, that is 1,000,000 / 3,600 = 280 a second, 70% of everything. So learn each page's change rate. On each visit compare the content hash with the last one. If it changed, halve the interval (down to 1 hour). If not, double it (up to 30 days). Send the page's stored ETag, a version tag the site gave us, in a conditional request. An unchanged page then returns a 304 (not modified) with no body. The risk: a quiet page that suddenly matters stays stale. Let feeds and sitemaps, a site's own list of its pages, trigger an early visit.

What breaks, and how you notice

A fetcher dies. The lease expires and the URLs return. You see expired leases and a dip in pages a second.
Slow servers. With 500 slots, if every fetch hung for 30 seconds, throughput would be 500 / 30 = 17 a second. Set timeouts (a few seconds to connect, 30 in total) and a size cap of a few MB.
A site answers 429 (too many requests) or a 5xx error. Double that host's delay and honour Retry-After. The other hosts continue.
A frontier shard dies. A standby loads its replicated queues. It waits one full delay per host before fetching, because it does not know when the old owner last called.
The parse queue grows. Alert on the age of the oldest message, and slow the fetchers when it passes a limit.

The dashboard: frontier size, age of the oldest waiting URL, errors per host, and duplicate rate. Now harden the design.

What Mid and Senior sound like, and the follow-ups

A Mid answer draws the loop, sizes it (about 400 pages a second), puts a queue per host in front of stateless fetchers, says the seen-set cannot be full strings, and returns a dead worker's URLs to the queue. A Senior answer adds the Bloom filter against exact store numbers, priority queues, partition by host with leases, traps in layers, adaptive freshness, and the signals that show the crawl is healthy.

Expect these follow-ups. "A week instead of a month?" That is 1 billion / 604,800 s = about 1,650 pages a second and 165 MB a second, with at least 1,650 hosts active at once. The design is the same, with about four times the fetchers. Huge hosts become the limit. "JavaScript pages?" Use a separate, smaller pool of headless browsers (browsers run by a program, with no screen), only for pages that need one, because each page costs far more. "A site owner complains?" Lower that host's rate through the policy call; its shard owns the delay, so it applies at the next lease.

The same five steps for any new question

This is the last question chapter, and the method was the same each time:

Ask and scope. Functional needs, non-functional needs with numbers, and what is out of scope.
Estimate. Rates, bandwidth and storage. Find the one number that shapes the design.
API and data model. The calls, and the keys the data is looked up by.
Draw the simplest design, break it with a number, fix it. Every box answers a number.
Deep dive. Take the two or three hardest parts. Compare weak, good and great, say the trade-off, then say what fails and how you would notice.

📌 Summary: Compare weak, good and great for each hard part. Frontier: queue per host. Seen-set: Bloom filter or exact store. Traps: limits. Freshness: learn the change rate. Leases cover dead workers.

What Meera learns next

The next step is practice: the harder problems, where you run the five steps yourself and the checks tell you what you missed.

Check your understanding

A crawler uses a Bloom filter with a 1% false-positive rate for its seen-set. A new Diwali recipe page was never linked before. What can happen to it?
The team will not accept losing 1% of new pages and has 5 billion URLs. Which seen-set fits, and about how big is it?
A calendar page links to the next month for ever. Every month has a new URL. What stops the crawler wasting its budget on it?
The crawler refreshes 1 million news pages every hour and can fetch 400 pages a second in total. What does that refresh cost?
A frontier shard fails and a standby takes over its queues. Why should it wait one full delay per host before fetching?