Web crawler
A web crawler is a BFS over a graph with billions of nodes, where every edge costs a network round trip to someone else’s server. Following links is the easy part. The design is the URL frontier: per-host queues with a next-allowed time, so you stay polite to each site while keeping thousands of fetches in flight. Around it sit dedupe (normalized URLs in a Bloom filter or fingerprint set, near-duplicate content via SimHash), trap defences, and partitioning by host so politeness never needs cross-machine coordination. Throughput is set by Little’s law (rate × fetch time = connections in flight); storage is about 100 TB a month at 1B pages.
The problem
Section titled “The problem”Search engines, archives (Common Crawl, the Internet Archive), price monitors, and LLM training pipelines all need a copy of a large part of the web, kept reasonably fresh. A crawler starts from seed URLs, downloads each page, extracts its links, and repeats.
Its goals conflict:
| Goal | What it means | Pulls toward |
|---|---|---|
| Coverage and throughput | Fetch as many useful pages per second as hardware allows | Many concurrent fetches, aggressive scheduling |
| Politeness | Never overload a site; obey robots.txt | At most one connection per host, delays between hits |
| Freshness | Re-fetch pages that changed, soon after they change | Recrawl budget spent on volatile pages |
| Efficiency | Don’t download duplicates or infinite junk | Dedupe, trap detection, priority |
Politeness is what makes this different from a graph traversal exercise. A naive crawler with 1,000 threads and one queue will send 500 of them to Wikipedia at once.
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Crawl from seeds, follow links, store raw HTML and metadata, extract links, recrawl changed pages. | HTML only, or PDFs, images, JS-rendered pages? Whole web or a set of domains? |
| Scale | 1B pages per month (≈400 fetches/s average, ≈800 peak). Seen set of ≈10B URLs. | Pages per month or per day? How long is history kept? |
| Politeness | One connection per host at a time, delay between requests, robots.txt obeyed. | Any sites with agreed higher rates? |
| Freshness | Important pages recrawled within hours, the long tail within weeks. | What’s the freshness target and for which pages? |
| Consistency | Each URL fetched at most once per crawl cycle; small loss acceptable. | Is missing a page acceptable (Bloom false positive)? |
| Out of scope | Indexing and ranking, JS rendering at scale, the search UI. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. Notice that compute is small: two machines’ worth of connections handles 1B pages a month. Storage and the seen set are what force the design.
What to say out loud: “400 pages a second average. By Little’s law, with 1-second fetches that’s only 400 connections in flight, so fetch capacity is easy. The constraints are politeness per host, ≈100 TB a month of storage, and keeping a 10-billion-URL seen set fast enough to check 60 links per page.”
API and data model
Section titled “API and data model”A crawler has no user-facing API. Its contracts are internal: what goes into the frontier, and what comes out of a fetch.
frontier.add(url, priority, not_before) -- idempotent: seen URLs are droppedfrontier.next() -> (url, host) | wait -- only from a host whose timer has expiredfrontier.done(host, fetch_ms, status) -- sets that host's next-allowed time
CrawlRecord { url_fp: u64, url, host, status, fetched_at, etag, last_modified, content_hash, simhash: u64, next_visit_at, change_interval }HostRecord { host, ip, ip_expires_at, robots_rules, robots_fetched_at, next_allowed_at, backoff_level, urls_this_cycle }Page blob key = content_hash -> compressed HTML (blob store, deduped by hash)Two decisions hide in that sketch:
- State is per host, not per URL. DNS, robots.txt, the politeness timer and the trap budget all belong to the host. That is why the whole system partitions by host.
- URLs are identified by a fingerprint of their normalized form. A 64-bit hash of the canonical URL is the key in every table. Normalize first, or
HTTP://Example.com:80/a/../bandhttp://example.com/bcount as two pages.
High-level design
Section titled “High-level design”Step through each flow. The frontier is the heart: everything feeds it, and it decides what is fetched next.
| Component | Role | Why it’s there |
|---|---|---|
| Scheduler | Injects seeds and URLs due for recrawl. | Freshness is a schedule, separate from discovery. |
| URL frontier | Priority (front) queues feeding per-host (back) queues with next-allowed times. | Decides what to fetch and when each host may be hit. |
| Fetchers (×N) | Async HTTP clients, hundreds to thousands of connections each. | Fetching is I/O-bound; concurrency per machine, not threads per fetch. |
| DNS and robots caches | Host → IP; host → parsed robots.txt rules. | Both are per-host and slow to fetch; caching removes them from the hot path. |
| Parser | Extracts links and text, normalizes URLs, computes fingerprints. | CPU-bound; scales separately from fetchers. |
| URL seen set | Bloom filter in memory, exact fingerprints on disk. | 60 links per page means ≈25k membership checks a second. |
| Content store | Compressed pages keyed by hash, plus a SimHash index. | 100 TB a month; exact and near-duplicate detection. |
Deep dive: the frontier and politeness
Section titled “Deep dive: the frontier and politeness”The frontier answers two questions: which URL matters most? and which host may I hit now? Mercator (Compaq Systems Research Center, 1999) split them into two layers, and most crawlers since follow the same shape:
- Front queues (priority). F queues, one per priority level. A prioritizer assigns each new URL a level (PageRank-ish importance, change rate, depth). A biased selector pulls from higher levels more often.
- Back queues (politeness). B queues, each holding URLs of exactly one host. When a back queue empties, the frontier pulls URLs from the front queues until it finds a host that has no back queue yet, and gives the empty queue to that host. URLs for hosts that already have a queue are appended to it. Mercator used about 3 back queues per fetcher thread, so there is always some host ready.
- A heap of next-allowed times. One entry per back queue, keyed by the earliest time that host may be hit again. A fetcher pops the top, waits if the time is in the future, fetches, then reinserts the host with
now + delay. - Adaptive delay. Mercator set the delay to 10× the duration of the last fetch from that host. A slow server, which is probably a loaded one, automatically gets hit less often.
Run the two frontiers below. Watch the red bars (fetches that overlap or ignore a host’s delay) and the finish time.
What the simulator shows:
| Frontier | Impolite fetches | Finish time | Why |
|---|---|---|---|
| One FIFO queue | Many | Fast, scales with W | Links cluster by host in discovery order, so workers pile onto one site |
| Per-host queues + delay, skewed mix | None | Bounded by the busiest host | That host’s URLs go one at a time; extra workers sit idle |
| Per-host queues + delay, many hosts | None | Close to FIFO | Politeness is free when the frontier has enough distinct hosts |
The lesson for scale: a polite crawler’s throughput is number of active hosts ÷ per-host delay, not number of machines. Keep the frontier broad.
robots.txt (RFC 9309, 2022) is fetched once per host and cached, no longer than 24 hours. Status codes matter: 4xx means “no rules, crawl anything”; 5xx or unreachable means assume complete disallow. Parsers must handle at least 500 KiB. Crawl-delay is not in the standard; some crawlers honour it, Google ignores it.
DNS was a measured bottleneck in Mercator: standard resolvers were synchronous and slow, so they built a multi-threaded resolver with a cache. Today: a local caching resolver per fetcher machine, plus the IP in the host record.
Deep dive: dedupe and traps
Section titled “Deep dive: dedupe and traps”Large crawls have found roughly 30% of web pages to be duplicates or near-duplicates of others (Fetterly et al., 2003), and most links on a page point to URLs you already know. Dedupe happens at three levels.
1. Normalize the URL. Make one canonical spelling before anything else.
normalize(raw, base): u <- resolve raw against base -- relative links, ../ and ./ lowercase u.scheme and u.host drop default port (:80 for http, :443 for https) drop fragment (#...) -- never sent to the server percent-encoding: uppercase hex, decode unreserved chars (%7E -> ~) empty path -> "/" -- policy, not RFC: may change meaning on some sites remove known tracking params (utm_*, fbclid), session ids optionally sort query params return u2. The URL seen set. Is this normalized URL new? At 10B URLs you have three options:
| Structure | Memory at 10B URLs | Error | Notes |
|---|---|---|---|
| Full URL strings in a hash set | ≈800 GB | none | Too big for RAM |
| 64-bit fingerprints, sorted on disk + RAM cache | 80 GB | ≈0 (2⁶⁴ space) | Mercator’s approach; batch lookups to amortize disk |
| Bloom filter, 10 bits/URL | 12.5 GB | ≈0.8% false “seen” | Fits in RAM; pair it with the disk set for “maybe” answers |
A Bloom filter is a bit array with k hash functions. Insert sets k bits; lookup checks them. All set = “maybe seen”; any zero = “definitely new”. The hash map and memory efficiency pages cover the trade-off between exact and probabilistic sets. Try it:
In a crawler, a false positive means a new page is silently never fetched. That’s often acceptable for the long tail, and you can bound it: the rate is about 0.6185^(bits per element) at the best k, so 10 bits gives 0.8% and 14.4 bits gives 0.1%. A Bloom filter can’t delete, so rebuild it each crawl cycle.
3. Content dedupe. Different URLs, same page: mirrors, ?print=1, www. vs bare domain. An exact hash (SHA-256 of the body) catches identical bytes. Near-duplicates (same article, different ad or timestamp) need SimHash: Google’s crawler used 64-bit SimHash fingerprints and treated pages within 3 bits of Hamming distance as duplicates, across 8B pages (Manku et al., WWW 2007).
simhash(text): v <- array of 64 zeros for each feature f in shingles(text): -- e.g. word 3-grams, weighted by count h <- hash64(f) for bit i in 0..63: v[i] += weight(f) if bit i of h is 1 else -weight(f) return 64-bit number with bit i = 1 where v[i] > 0
near_duplicate(a, b) = popcount(a XOR b) <= 3Finding all fingerprints within 3 bits of a new one, without comparing to all 8B, uses the paper’s trick, a pigeonhole argument: split the 64 bits into 4 blocks of 16. If at most 3 bits differ, at least one block matches exactly. Keep one table per block, sorted by that block first, and compare only fingerprints that agree on some block. The paper refines this with more permuted tables.
Traps generate unbounded unique URLs, so dedupe can’t catch them: calendars with a “next month” link forever, session ids in the path, /a/b/a/b/a/b/... from relative links, soft 404s that return 200 for any path. Defences are budgets, not cleverness:
- Max depth from a seed and max URL length (a few hundred to ~2,000 chars).
- Max URLs per host per cycle, raised for hosts that prove valuable (many unique, linked-to pages).
- Detect repeating path segments and near-duplicate content across a host’s URLs.
- Fetch a random nonsense path once per host; if it returns 200, the host serves soft 404s, so compare against that body.
Deep dive: distribution, partitioning and recrawl
Section titled “Deep dive: distribution, partitioning and recrawl”Partition by host. Hash the host (or registered domain) to pick the crawler node that owns it. Each node runs its own frontier, fetchers, DNS cache and robots cache for its hosts. Politeness then needs no cross-node coordination: only one node ever talks to news.org.
on_link(raw, page_url): url <- normalize(raw, page_url) if trap_rules_reject(url): return owner <- consistent_hash(registered_domain(url.host)) if owner == me: if seen_set.maybe_contains(fp(url)) and seen_store.contains(fp(url)): return seen_set.add(fp(url)); frontier.add(url, priority(url)) else: outbox[owner].append(url) -- flushed in batches every ~1 sMost links are same-host, so cross-node traffic is a minority, and batching makes it cheap. Use consistent hashing so adding a node moves only about 1/N of hosts. Partition by registered domain (blog.example.com and www.example.com → example.com) if you want politeness per organization, since subdomains often share servers.
Recrawl by change rate. Each URL keeps a change_interval. On recrawl:
after_fetch(record, status, new_hash): changed <- status != 304 and new_hash != record.content_hash if changed: record.change_interval <- max(MIN, record.change_interval / 2) else: record.change_interval <- min(MAX, record.change_interval * 2) record.next_visit_at <- now + record.change_interval / importance(record)Cho and Garcia-Molina showed that the naive “visit fast-changing pages most” can be worse than uniform: a page that changes every minute is stale again before anyone reads your copy. Weight by importance and cap how often the hottest pages are fetched. Use conditional GETs (If-None-Match / If-Modified-Since → 304) and sitemaps (lastmod) to avoid downloading unchanged bodies.
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| A fetcher node dies | Its in-flight URLs vanish | Frontier is persisted (disk-backed queues, or a log); lease URLs and re-queue on timeout |
| Crawler trap | One host’s URL count explodes | Depth, length and per-host budgets; repeating-path detection |
| Target site overloaded | 429/503, rising latency | Per-host exponential backoff, honour Retry-After, adaptive delay |
| robots.txt 5xx | Host’s rules unknown | Treat as full disallow; retry later; use cached copy if recent |
| DNS slow or failing | Fetchers stall on lookups | Local caching resolver, async resolution, negative caching |
| Seen set grows past RAM | Bloom FP rate climbs | Size for the cycle up front; rebuild per cycle; exact disk set behind it |
| Hot host dominates a partition | One node’s frontier is all one host | Per-host budget; politeness caps that host anyway, so give the node more hosts |
| Duplicate content flood | Storage grows, index quality drops | Exact hash + SimHash; don’t follow links from duplicates |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
| Frontier next() / done() | O(log B) heap op over B back queues | O(URLs queued), mostly on disk |
| URL seen check | O(k) Bloom probes, O(1) expected disk lookup on “maybe” | ≈1.25 B/URL at 10 bits (12.5 GB for 10B) |
| Normalize one URL | O(length) | O(length) |
| SimHash one page | O(features × 64) | 8 B per page (8 GB for 1B) |
| Near-dup lookup | O(tables × log N) sorted-table probes | tables × 8 B per page |
| Store a page | 1 blob write | ≈100 KB raw, ≈20 KB compressed |
| Throughput | ≈400 fetches/s for 1B/month | ≈40 MB/s download, ≈100 TB/month raw |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Broad or focused, page volume, content types, freshness target, politeness rules, JS rendering.
- Estimate (5 min). Fetches per second, connections in flight (Little’s law), storage per month, seen-set size.
- Single-node pipeline (10 min). Seed → frontier → fetch → parse → normalize → seen? → frontier. Name BFS, then say why plain BFS is impolite.
- The frontier (10 min). Front queues for priority, per-host back queues, heap of next-allowed times, delay proportional to fetch time. robots.txt and DNS caching.
- Scale and harden (10 min). Partition by host with consistent hashing, Bloom + disk seen set, SimHash, trap budgets, crash recovery of the frontier.
- Stretch (5 min). Recrawl policy, JS rendering, prioritizing by importance.
Follow-ups to expect: “How do you avoid hitting one site too hard across 100 machines?” Partition by host so only one node owns it. “A Bloom filter says ‘seen’ for a new URL. What happens?” The page is skipped; size the filter for an acceptable rate, and rebuild each cycle. “How do you detect the same article at two URLs?” SimHash, Hamming distance ≤ 3. “A machine crashes mid-crawl.” The frontier is durable and fetches are leased, so its URLs return to the queue.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Heydon and Najork: Mercator, a scalable, extensible web crawler (1999): front and back queues, the URL-seen test on disk, the DNS bottleneck.
- Manku, Jain and Das Sarma: Detecting near-duplicates for web crawling (WWW 2007): 64-bit SimHash and the permuted-tables lookup at Google scale.
- RFC 9309: Robots Exclusion Protocol: status-code handling, caching, parse limits.
- Google Search Central: How Google interprets robots.txt: a large crawler’s real-world policy, including what it ignores.
Concept pages to drill: Crawling · BFS · Hash map · Heap · Memory efficiency · Concurrency · Rolling hash