Web Crawler
Fetching billions of pages politely — URL deduplication at scale, per-host rate limiting, and avoiding traps
A crawler is a breadth-first search over a graph with a billion nodes, where every edge traversal is a network request to a machine you do not control.
1. Clarify and Scope
| Question | Assumption taken here |
|---|---|
| Scale? | 1 billion pages per month |
| What is stored? | Raw HTML, for later processing |
| Recrawl? | Yes — important pages more often |
| Politeness? | Must respect robots.txt and not overload any host |
| Content types? | HTML only |
2. Put Numbers On It
1 billion pages/month
÷ 30 days ÷ 100,000 sec ≈ 400 pages/sec average
× 3 peak ≈ 1,200 pages/sec
STORAGE
average page ≈ 500 KB raw, ~100 KB compressed
1B × 100 KB = 100 TB/month
× 12 ≈ 1.2 PB/year
URL FRONTIER
~10 billion known URLs
100 bytes each = 1 TB ← too big for memory
BANDWIDTH
1,200 pages/sec × 500 KB ≈ 600 MB/sec inboundTwo findings shape the design
The URL set does not fit in memory. At 10 billion URLs you cannot keep a hash set of what you have seen — that is the central engineering problem.
400 pages/sec is not fast per machine, but politeness makes it hard. You cannot hit one site 400 times a second. The work must be spread across many hosts, which turns scheduling into the difficult part.
3. Define the Interface
No user is waiting for a reply here — this is a pipeline, not a request/response service. The step does not disappear; it becomes name what crosses each boundary.
IN — from operators, rarely
submit_seeds(urls[], priority) → ack
set_policy(domain, rules) → crawl rate, exclusions
OUT — per page fetched, the contract with everything downstream
{
url, final_url, after redirects
fetched_at, status,
content_hash, for detecting unchanged pages
html, to object storage; the record holds a pointer
links[] extracted, already normalised
}Skipping this step on a pipeline is how you build a data swamp
It is tempting to say "a crawler just downloads pages" and start drawing the fetch loop. Then months of HTML land in storage with no fetched_at, no final_url, and no content_hash — and the indexer that has to consume it cannot tell fresh from stale, or a redirect from a real page.
The output record is the interface. It is agreed with the consumer before the fetching is designed, because re-crawling a billion pages to add one field is not an option.
`links[]` comes out normalised, not raw
HTTP://Example.COM/a/../b?utm_source=x#top and https://example.com/b are the same page. Deciding where that cleanup happens is an interface question: do it once here, or force every consumer to redo it inconsistently.
Doing it at the boundary is also what makes the deduplication in section 5 possible at all — you cannot deduplicate URLs that are still spelled five different ways.
4. The Architecture
5. URL Deduplication
With 10 billion URLs, an exact set needs about a terabyte. A Bloom filter holds the same information in around 12 GB at a 1% false-positive rate.
Why a false positive is acceptable here
A false positive means the filter claims a URL was already seen when it was not, so that page is never crawled.
Missing 1% of pages is fine for a web crawler — the web is effectively infinite, and most pages are low value. A false negative would be worse, because it means recrawling and possibly looping, and Bloom filters never produce those.
This is the textbook case where the error direction is exactly the harmless one.
URLs must also be normalised before checking, or the same page is crawled many times:
http://Example.com/Page/ → https://example.com/page
https://example.com/page#top → https://example.com/page
https://example.com/page?b=2&a=1 → https://example.com/page?a=1&b=26. Politeness and Scheduling
An impolite crawler is a denial-of-service attack
Hitting one host with hundreds of concurrent requests will take it down. You will be blocked, and rightly so.
Three rules:
Respect robots.txt, including its Crawl-delay.
One connection per host at a time, with a delay between requests — typically one to several seconds.
Identify yourself in the user agent, with a contact URL, so an affected operator can reach you instead of just blocking.
The frontier is therefore not one queue but many queues, one per host, with a scheduler that only releases a URL when that host's politeness delay has elapsed.
Frontier
├─ queue: example.com next allowed at 10:00:03
├─ queue: news.site next allowed at 10:00:01
└─ queue: blog.org next allowed at 10:00:07
A worker takes from whichever host is ready now.Priority sits on top of politeness
Not all pages deserve equal attention. A news homepage changes hourly; an archived page from 2009 does not.
Assign a priority from update frequency, inbound links and page importance, and keep several priority levels within each host's queue. High-priority URLs are crawled first and recrawled sooner.
Politeness constrains when you may fetch from a host; priority decides which of its URLs you fetch.
7. Traps
The web is full of structures that will consume a naive crawler forever.
| Trap | Example | Defence |
|---|---|---|
| Infinite calendars | /calendar?month=1, 2, 3, … forever | Cap URL depth and path length |
| Session ids in URLs | Same page, endlessly new URLs | Normalise; strip known session parameters |
| Spider traps | Deliberately generated infinite link trees | Limit pages per domain |
| Very large files | A 10 GB file behind an HTML link | Cap response size, check Content-Type |
| Slow servers | Responses that never finish | Aggressive timeouts |
| Redirect loops | A → B → A | Cap redirects at around 5 |
Cap pages per domain
Without a per-domain cap, one site with generated URLs can absorb your entire crawl capacity indefinitely.
A cap of, say, 100,000 pages per domain means a trap wastes a bounded amount of work rather than an unbounded one. It also improves coverage, because the crawl keeps moving across the web instead of drilling into one site.
8. What Was Traded Away
| Decision | Gained | Cost |
|---|---|---|
| Bloom filter for URLs | 12 GB instead of 1 TB | ~1% of pages never crawled |
| Per-host queues | Politeness, never blocked | Complex scheduling; lower throughput |
| Content hashing | Duplicates detected across URLs | Near-duplicates still slip through |
| Depth and domain caps | Traps are bounded | Some legitimate deep pages are missed |
| Async parsing | Fetchers never wait | Links enter the frontier slightly late |
Follow-on Questions
Related Reading
- Probabilistic Structures — the Bloom filter doing the heavy lifting
- Queues and Async Work — the frontier as a priority queue
- Partitioning — distributing hosts across crawlers
- Number of Islands — BFS with a visited set, which this is at scale