Designing a Web Crawler's Visited-URL Filter

In one line

A crawler must skip URLs it has already fetched across billions of URLs and thousands of workers. Canonicalise URLs, partition the URL space by host across crawler workers, keep a Bloom filter of visited URLs per partition, and accept that a false positive means an unvisited URL is occasionally skipped, which is usually fine for a crawler.

0/5 · 0%

Think of it like this

Postal workers covering districts. Each worker keeps a list of houses already visited in their own district; a house seen twice isn't visited again, and occasionally a new house is wrongly skipped, which is acceptable because the next round will catch it.

Key ideas

01
Canonicalisation first: lowercase host, remove default ports and fragments, sort or strip tracking query parameters, resolve relative paths, normalise trailing slashes. Otherwise duplicates look like different URLs and the filter can't help.
02
Partitioning: assign hosts to workers by consistent hashing on the host (also enforces per-host politeness). Each worker owns a filter for its hosts; newly discovered URLs are routed (via Kafka or a frontier queue) to the owning worker.
03
Here the false-positive direction is a correctness trade-off: "maybe visited" → skip. A false positive means a genuinely new page is never crawled (until a recrawl cycle). At 10B URLs and 0.1%, ~10M pages missed, often acceptable; for critical domains, verify "maybe" against the URL store.
04
Memory: 10B URLs at 0.1% ≈ 18 GB total, split across workers (1,000 workers → ~18 MB each). Recrawl scheduling keeps a separate store of URL → last crawl time.
05
Persistence: checkpoint worker filters to object storage periodically; rebuild from the URL store if lost; rebalance filters when workers join or leave (rebuild the moved hosts' filters).

Code & diagrams

crawler.mermaiddiagram

Rendering diagram…

canonicalize.pypython

from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode

DROP = {"utm_source", "utm_medium", "utm_campaign", "gclid", "fbclid"}

def canonical(url: str) -> str:
    s = urlsplit(url.strip())
    host = (s.hostname or "").lower()
    port = s.port
    netloc = host if port in (None, 80, 443) else f"{host}:{port}"
    q = urlencode(sorted((k, v) for k, v in parse_qsl(s.query) if k not in DROP))
    path = s.path or "/"
    return urlunsplit((s.scheme.lower(), netloc, path, q, ""))   # drop fragment

print(canonical("HTTPS://Example.com:443/a?utm_source=x&b=2&a=1#top"))
# https://example.com/a?a=1&b=2

Interview problem

The problem

Crawler for 10 billion URLs with distributed workers

Design visited-URL detection for a crawler handling 10 billion URLs across thousands of workers with limited memory. Cover URL normalisation, the Bloom filter, false positives, partitioning, shared vs local filters, persistence and rebuilds. Is a false positive acceptable?

You're given

10B URLs
2,000 crawler workers
Crawl ~50K pages/sec

Explain it without notes

Why is a false positive acceptable for a crawler but not for a payment system?

Practice

Estimate filter memory per worker for 20B URLs, 0.5% FPR, 5,000 workers.

Trade-offs

↔
Local partitioned filters scale and avoid shared hot spots; routing URLs to owners adds a queue hop.

Done when you can

I can design a partitioned visited-URL filter for a large crawler.

Command Palette