Design a web crawler

The frontier must answer two questions: which URL is most important, and which host may I hit now. The classic design (Mercator) uses two layers. Front queues are priority buckets (for example 10 levels, set from domain rank, depth and change rate). A biased selector pulls more often from high-priority buckets. Back queues are per host: each back queue holds URLs for one host only, and a min-heap keyed by next_allowed_at says which host is ready. A fetcher thread pops the heap, takes one URL from that host's queue, fetches it, and pushes the host back with next_allowed_at = now + delay. This gives one connection per host at a time and a global priority order. At scale we shard the frontier by hash(host), so a single shard owns all politeness state for a host and no cross-machine locks are needed. Each shard keeps the heads of queues in memory and spills the long tails to disk (RocksDB or Cassandra), because 10B pending URLs will not fit in RAM. Large hosts such as Wikipedia get a higher allowed rate, configured per host, but are still owned by one shard.

There are two kinds of duplicates. URL duplicates are the same address written differently: fix them with normalisation, then check a set of seen URLs. With 10B URLs, an exact hash set of 8-byte hashes is ~80 GB, while a Bloom filter at 1% false positives needs ~12 GB and can be sharded by host. A false positive means we skip a new URL, which is acceptable at 1%; a Bloom filter never says 'not seen' for a seen URL. For extra safety, important URLs can be confirmed against url_state. Content duplicates are different URLs with the same or almost the same page: mirrors, session IDs in URLs, printer-friendly versions. Exact duplicates are caught by a hash of the normalised text. Near-duplicates use SimHash: a 64-bit fingerprint where similar documents differ in few bits. To find pages within 3 bits, split the fingerprint into 4 blocks of 16 bits; by the pigeonhole principle any match within 3 bits shares at least one exact block, so we index each block and compare only candidates. Duplicates are not indexed and their outlinks are trusted less.

You cannot recrawl 10B pages every day, so the budget must follow change rate and importance. For each URL we store the last few crawl results: did the content hash change? A simple estimator is change_rate = changes ÷ observed time; next interval ≈ 1 ÷ change_rate, clamped between, say, 1 hour and 60 days, then shortened for important pages. A news homepage that changes every 10 minutes gets crawled every few minutes; a 2012 blog post gets crawled every few weeks. Conditional GETs (If-Modified-Since, ETag) make most recrawls cheap: a 304 response has no body. Sitemaps with lastmod and RSS feeds are strong hints, and protocols like IndexNow let sites push changes. In the frontier this is just a priority: a URL whose next_crawl_at has passed is re-inserted into a front queue with priority from importance × staleness. Splitting capacity into a 'discovery' budget (new URLs) and a 'refresh' budget (known URLs), for example 30/70, stops new-link floods from starving freshness.

The open web is hostile. Calendars generate infinite URLs (/calendar?month=1…∞), session IDs make each link unique, and some servers reply byte by byte to tie up crawlers. Defences: cap URL length (~2,000 chars) and path depth; cap pages per host per crawl cycle (for example 100k for unknown hosts, grown if the site proves valuable); detect repeating path segments (/a/b/a/b/a/b); strip known session and tracking params; and treat many near-duplicate pages from one host as a trap signal. On the network side: connect and total timeouts, a maximum body size, and a maximum redirect chain of ~5. Parsers run in a sandboxed process with memory limits so one malformed page cannot crash a worker. Every lease has an expiry: if a fetcher dies, its leased URLs return to the frontier after the lease times out, so work is retried, not lost. Because fetches are idempotent GETs, a retry is safe.

Pure BFS is simple but wastes budget on low-value pages and hammers hosts with many links. DFS falls into traps. A priority frontier (domain rank, depth, freshness) costs more complexity but spends bandwidth where search quality gains most. Mention BFS as the starting idea, then improve it.

A Bloom filter is ~7x smaller than an exact hash set and fits in RAM per shard, at the cost of ~1% of new URLs being skipped. An exact set in RocksDB/Cassandra is precise but costs a disk lookup for ~20k links/s. Common answer: Bloom filter first, url_state as the source of truth for scheduling.

Partitioning by URL hash spreads load evenly but spreads one host's URLs over many machines, so politeness needs a distributed lock or shared rate limiter. Partitioning by host keeps politeness local and DNS/robots caches warm, at the cost of skew (big sites). Choose host partitioning and handle skew with consistent hashing and virtual nodes.

Plain HTTP fetch costs ~10-50 ms of CPU per page. Rendering JavaScript in headless Chrome costs 1-5 s of CPU and lots of memory. Render only for hosts where the plain HTML is clearly empty, in a separate queue, so the main pipeline stays cheap.

At 2,000 fetches/s, uncached DNS lookups add tens of ms each and can overload public resolvers. Run a local caching resolver per worker pool, keep the IP in host_state, and resolve ahead of time when a host enters the ready heap.

Parsers produce ~20k-100k links/s. Sending each one over RPC is wasteful. Batch links per destination shard (for example every 100 ms), dedup within the batch, and use the Bloom filter on the parser side to drop most links before they cross the network.

Writing one S3 object per page means billions of PUTs (cost and request-rate limits). Append pages to WARC files and roll a file at ~1 GB; keep an index of (url_hash → file, offset) for random reads.

Leased URLs carry a lease expiry (for example 5 min). The frontier re-queues them after expiry. Pages already in S3 but not acked may be fetched again; this is harmless because downstream dedup by url_hash + content hash makes processing idempotent.

Its in-memory queues are lost, but url_state in Cassandra holds next_crawl_at for every URL. A replacement shard (or neighbours via consistent hashing) rebuilds queues by scanning its host range. Snapshot the Bloom filter to S3 every few minutes so it can be reloaded quickly.

Track error rate and latency per host. On 5xx or 429, back off exponentially (double crawl_delay up to hours) and honour Retry-After. This protects the site and stops our fetchers wasting connections.