System Design HLD-19.09
Design a web crawler
Design a web crawler: a URL frontier with priorities and per-host politeness, robots.txt, DNS caching, Bloom filter and content-hash dedupe.
The problem
A search engine, an archive or a training-data pipeline needs copies of web pages. A crawler gets them: start from some seed URLs, download each page, find the links in it, and repeat with the new links, forever. In ten lines of code it works on a laptop. At a billion pages a month it becomes a design problem with an unusual twist: the system you are calling is not yours.
That twist shapes everything. Web servers belong to other people, so the crawler must be polite: never hammer one site, obey its robots.txt. The web is full of duplicates, mirrors and infinite link mazes, so the crawler must remember billions of URLs it has seen and recognise pages it already has. And it must decide what to fetch next out of billions of candidates.
Requirements
Functional
- Start from seed URLs; fetch pages, extract links, and crawl new links.
- Store fetched HTML with metadata (URL, fetch time, status, content hash) for downstream indexing.
- Obey
robots.txtand per-site crawl delays. - Re-crawl pages periodically, more often for pages that change often.
Non-functional
- Scale: 1 billion pages a month.
- Politeness: at most one request at a time to each host, with a delay between requests.
- Robustness: survive malformed HTML, slow servers, spider traps and crawler machine failures.
- Extensibility: new content types or processing steps without redesigning the pipeline.
Out of scope
- Rendering JavaScript-heavy pages, indexing and ranking ( Inverted indexes and full-text search ), and images and video.
Estimates
- Fetch rate: 1 billion pages a month is 1e9 / (30 x 86,400), about 390 pages per second on average. Plan for about 800 per second to catch up after outages.
- Bandwidth: at about 100 KB per page, 390 pages per second is 39 MB/s, a little over 300 Mbit/s.
- Storage: 1 billion x 100 KB = 100 TB of raw HTML a month, before compression, which suits object storage.
- Seen URLs: the crawler will discover far more URLs than it fetches, say 10 billion. A Bloom filterA compact bit array that answers 'definitely not seen' or 'probably seen', with a tunable false-positive rate and no false negatives. for 10 billion URLs with a 1 percent false-positive rate needs about 9.6 bits per URL, so 96 billion bits, about 12 GB, with 7 hash functions. Storing the URLs themselves would take hundreds of GB.
- Concurrency: if a fetch takes 1 second on average (slow servers, timeouts), 800 fetches per second needs about 800 in flight at once, which is a job for asynchronous I/O on a modest number of machines ( Processes, threads and concurrency ).
API
A crawler has no public API, but its components talk through narrow interfaces:
frontier.add(url, priority) # from link extraction
frontier.next(worker_id) -> url # respects per-host politeness
fetcher.fetch(url) -> (status, headers, body)
store.put(url, fetch_time, body) # returns a content id
Data model
- URL frontier: priority queues of URLs to crawl, plus one FIFO queue per host. Too large for memory, so mostly on disk with in-memory heads.
- URL seen set: a Bloom filter over normalized URLs, with an exact store of crawled URLs (
url_hash -> last_fetch, next_due, content_hash) for re-crawl scheduling. - Content store: compressed pages in object storage, keyed by content hash, with an index from URL to the latest content id.
- Host table:
host -> robots rules, crawl delay, next allowed fetch time, cached IP address.
High-level design
- Fetch path The frontier gives a fetcher a URL only if its host's politeness delay has passed. The fetcher resolves the host from a local DNS cache, checks the host's cached robots.txt rules, and downloads the page with a timeout and a size limit.
- Process path The parser computes a hash of the page content. If the same content was stored before (a mirror or a duplicate URL), it records the alias and skips storage; otherwise it stores the compressed page in object storage.
- Discover path Links are extracted, made absolute and normalized (lowercase host, no fragments, sorted query parameters), then filtered for traps. URLs the Bloom filter has not seen are added to the frontier with a priority.
Deep dives
Deep dive 1: The URL frontier, priority and politeness
The frontier answers two questions: what should be crawled next (priority), and is it allowed to be crawled now (politeness). A common design splits it in two:
- Front queues by priority. A prioritizer scores each URL, using signals such as the site's importance, how often the page has changed, and how long since it was last fetched, and puts it in one of several priority queues.
- Back queues, one per host. A selector moves URLs from front queues into per-host queues, and a heap ordered by each host's next allowed fetch time decides which host is served next. After fetching from a host, its next time is set to now plus its crawl delay.
Here is why per-host queues matter. Twelve URLs, eight of them on one site, two workers:
# Two fetch workers, 12 URLs, mostly from one host. Each fetch takes 1 s.
# Compare a plain FIFO with per-host queues and a 3 s politeness delay.
from collections import deque
urls = ["big.example/p%d" % i for i in range(8)] + \
["a.example/", "b.example/", "c.example/", "d.example/"]
host = lambda u: u.split("/")[0]
def fifo():
q, t, log = deque(urls), 0, []
while q:
for _ in range(2): # two workers per second
if q:
log.append((t, q.popleft()))
t += 1
return log
def polite(delay=3):
queues = {}
for u in urls:
queues.setdefault(host(u), deque()).append(u)
ready = {h: 0 for h in queues} # next time each host may be hit
t, log = 0, []
while any(queues.values()):
due = [h for h in queues if queues[h] and ready[h] <= t]
for h in due[:2]: # two workers per second
log.append((t, queues[h].popleft()))
ready[h] = t + delay
t += 1
return log
for name, log in [("FIFO", fifo()), ("per-host", polite())]:
hits = [t for t, u in log if host(u) == "big.example"]
gap = min(b - a for a, b in zip(hits, hits[1:]))
small = max(t for t, u in log if host(u) != "big.example")
print(f"{name}: min gap on big.example {gap}s, "
f"small sites done t={small}s, all done t={log[-1][0] + 1}s")Output
FIFO: min gap on big.example 0s, small sites done t=5s, all done t=6s
per-host: min gap on big.example 3s, small sites done t=2s, all done t=22s The FIFO crawler hit big.example twice in the same second, again and again: from that site's point of view, a small attack. The per-host frontier never hit it more than once every 3 seconds, and it finished the small sites sooner because they no longer waited behind the big one. It took longer overall, which is the real lesson: politeness caps the rate per host, so a crawler's throughput comes from crawling many hosts in parallel. Assign hosts to crawler machines by hashing the host name ( Consistent hashing ), so one machine owns each host's politeness state.
Deep dive 2: Not fetching twice
Duplicates come in two kinds:
- Same URL discovered from many pages. Normalize URLs first, then check a Bloom filter ( Probabilistic data structures ). A false positive means a URL that was never crawled is skipped, which at 1 percent is acceptable for a crawler; a false negative never happens, so a URL is never crawled twice by mistake. The exact table of crawled URLs exists for re-crawl scheduling, not for the hot check.
- Same content under different URLs: mirrors, session ids in URLs,
?utm_source=variants. Hash the page content and look the hash up before storing. Exact hashes catch identical pages; near-duplicate techniques (such as SimHash) catch pages that differ only in a timestamp or an ad.
Deep dive 3: DNS, robots.txt and traps
DNS can dominate fetch time: resolving a host may take tens of milliseconds, and standard resolvers are often synchronous and serialize lookups. Run a local caching resolver per crawler machine and keep resolved addresses in the host table, respecting TTLs ( DNS in depth ).
robots.txt is fetched once per host, cached for about a day, and checked before every fetch. It may also specify a crawl delay, which feeds the host's politeness interval.
Spider traps are URL spaces that never end: calendars with a "next month" link forever, session ids that make every link unique, /a/b/a/b/a/b/.... Defend with a maximum URL length and path depth, a cap on pages per host per crawl cycle, and by treating parameters that only change session state as the same URL.
Try it
Try this:
- Insert more items without adding bits. Watch the false positive rate climb. In the crawler, what does a false positive cost?
- Find the number of hash functions that gives the lowest false positive rate for your bits and items. Compare with (bits / items) x 0.69.
- Use the 12 GB estimate above: if the crawler discovered 20 billion URLs instead of 10 billion, what would you change to keep the rate at 1 percent?
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| One huge site dominates the frontier | Workers idle while waiting for politeness | Per-host queues; cap pages per host per cycle |
| Slow or hanging servers | Fetch slots tied up | Strict connect and read timeouts, size limits, async I/O |
| Spider trap | Infinite URLs from one site | Depth and length limits, per-host caps, parameter normalization |
| Crawler machine dies | Its hosts stop being crawled | Frontier persisted on disk; hosts reassigned via the hash ring |
| DNS slow | Throughput collapses | Local caching resolvers, cached IPs in the host table |
| Bloom filter full | False positive rate rises, pages skipped | Size for expected URLs; rebuild larger periodically |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Per-host back queues (chosen) | Politeness enforced by design; fairness across sites | More complex frontier; throughput needs many hosts |
| Bloom filter for seen URLs (chosen) | About 12 GB for 10 billion URLs | 1 percent of new URLs wrongly skipped |
| Exact seen-URL store | No skipped URLs | Hundreds of GB and a disk lookup per link |
| Hosts partitioned across machines by hash (chosen) | Each host's politeness state in one place | Rebalancing when machines join or leave |
Extensions
- Freshness-driven re-crawl: estimate each page's change rate and schedule re-fetches to match.
- JavaScript rendering with headless browsers for pages that build content client-side, at many times the cost per page.
- Focused crawling that only follows links likely to be on topic.
- Conditional requests (
If-Modified-Since, ETags) so unchanged pages cost a tiny response.
In the wild
Where you will see this: web search engines, web archives, price and SEO monitoring tools, and the crawlers that collect training data for language models. They differ in what they prioritize and how often they return, but all of them meet the same constraints: politeness to other people's servers, robots.txt, DNS cost, and a web full of duplicates and traps.
Check yourself
-
Why does the frontier keep one queue per host?
Show answer
B. To enforce a delay between requests to the same site while keeping other sites busy Per-host queues with next-allowed times make politeness a property of the design rather than luck.
-
The Bloom filter says a new URL was 'probably seen' but it never was. What happens?
Show answer
B. The URL is skipped this time A false positive skips a URL. Bloom filters never give false negatives, so nothing is fetched twice by mistake.
-
Two URLs serve exactly the same page. How does the crawler avoid storing it twice?
Show answer
B. Comparing content hashes before storing Different URLs can point to identical content; hashing the content catches that.
-
A site's calendar links to the next month forever. What protects the crawler?
Show answer
B. Limits on URL depth and pages per host, and parameter normalization Spider traps are infinite URL spaces; caps per host and on URL shape stop them.
Recap
- A crawler is a loop: frontier, fetch, parse, extract links, filter, back to the frontier.
- The frontier handles priority with front queues and politeness with per-host back queues.
- Throughput comes from crawling many hosts in parallel, never from hitting one host harder.
- Normalize URLs and use a Bloom filter for seen URLs; hash content to catch duplicate pages.
- Cache DNS and robots.txt, and defend against spider traps with depth and per-host limits.
Next up
- Crack the system design round learning path