Design a Web Crawler

• Crawl from a seed set — Start from a list of URLs, fetch each page, extract links, and continue until a budget or scope limit is reached.
• Respect robots.txt and crawl politely — Honour disallow rules and crawl-delay, and never open more than a small number of concurrent connections to one host. A polite crawler is one that does not get blocked.
• Deduplicate URLs and content — Do not fetch the same URL twice in one cycle; detect near-duplicate pages (mirrors, tracking parameters, print versions) so the corpus is not inflated.
• Prioritise — Important or frequently changing pages are fetched first and more often. Priority comes from a score (link-based importance, change rate, freshness needs).
• Store the fetched content — Raw HTML with headers and fetch metadata, versioned, so downstream indexers and analysers can process it. Storage is append-only.
• Re-crawl for freshness — Pages are revisited on a schedule that adapts to how often they change.
• Handle traps and errors — Infinite calendars, session-id URLs, redirect loops, huge files, slow hosts. The crawler bounds its work per host and per page.
• Out of scope — Indexing and ranking, JavaScript rendering (mention the headless-browser lane), and the search product. We produce a corpus.

• Throughput (1 B pages/month · ~400 pages/s) — The number is modest per second; the difficulty is that it is spread over tens of millions of hosts with per-host limits.
• Politeness (≤ 1 request per host per second by default) — The hardest constraint: it turns a throughput problem into a scheduling problem, because the frontier must always have a host ready that is not in cooldown.
• Freshness (news within hours · long tail within weeks) — Drives the re-crawl scheduler and the priority model.
• Coverage and dedupe (< 5 % duplicate content) — Duplicates waste fetch budget and storage and skew the corpus.
• Robustness (no single host can stall the crawl) — Timeouts, per-host budgets and trap detection are mandatory, not optional.
• Durability (frontier survives crashes) — The frontier is the crawler's state; losing it means restarting from seeds. It must be persisted.
• Scalability (horizontal on fetchers and frontier) — Add fetchers to add throughput, as long as the frontier can partition hosts among them.

• Fetch rate: ~400 pages/s — 1 B pages/month ÷ 2.6 M s ≈ 385/s. Plan for 2× headroom (800/s) because retries, redirects and robots fetches add requests beyond page fetches.
• Concurrent connections: ~2 000 — Average fetch takes ~2 s (DNS, connect, TLS, transfer, slow servers). 800/s × 2 s = 1 600 in flight; round to 2 000. A single fetcher machine handles thousands of idle connections, so a few dozen fetchers with headroom.
• Download bandwidth: ~1.6 Gbit/s — Average page with headers ~500 KB (HTML only; media not fetched). 400/s × 500 KB = 200 MB/s ≈ 1.6 Gbit/s. Bandwidth is not the bottleneck; politeness is.
• Storage per month: ~150 TB compressed — 1 B × 500 KB = 500 TB raw; HTML compresses ~3–4×, so ~150 TB/month, ~1.8 PB/year. Object storage with lifecycle rules; keep the latest version hot and older versions cold.
• URLs seen: ~10–20 B — Each page yields ~50 links; most point to already-known URLs. Over a year the seen-URL set reaches tens of billions. The URL-seen structure must hold ~15 B keys: as 8-byte fingerprints that is ~120 GB, feasible in a sharded key-value store or a large Bloom filter.
• Hosts in the frontier: ~50 M — The crawlable web is a few hundred million hosts; a 1 B-page crawl touches roughly 50 M of them. With a 1 req/s per-host limit, most hosts are idle at any moment: only ~400 need to be "ready" per second, so the scheduler must keep many hosts warm.
• DNS lookups: ~400/s → ~10/s with cache — One lookup per fetch without caching. Hosts repeat heavily, so a local DNS cache with a ~1 h TTL cuts external lookups by 95 %+. Run a caching resolver per fetcher cluster; public resolvers rate limit.

• Seed / URL API — Where crawls start: seed lists, sitemaps, and an API for operators to inject or reprioritise URLs. Also receives external hints such as ping services and sitemap updates.
• URL frontier (per-host queues + priority) — The heart of the crawler: the set of URLs to fetch, organised so that a fetcher can always get the next URL for a host that is not in cooldown. Two levels: priority queues that select which URLs are eligible, and per-host FIFO queues with a next-allowed-time that enforce politeness. Persisted, partitioned by host across frontier nodes.
• Host scheduler (min-heap of next-fetch times) — Maintains, per frontier partition, a heap of hosts keyed by the earliest time they may be fetched again. Hands out (host, URL) leases to fetchers so that no host has more than one in-flight request and the per-host delay is respected.
• Fetcher fleet (async HTTP · many connections) — Stateless workers that lease URLs, resolve DNS via a local cache, check robots rules, fetch with strict timeouts and size limits, and hand the response to the processing pipeline. Identify themselves with a clear user agent and contact URL.
• DNS cache (caching resolver) — A local resolver per cluster that caches lookups for hours and answers most queries without leaving the network. Without it, DNS is the first bottleneck and public resolvers will throttle the crawler.
• Robots cache (per-host rules · 24 h TTL) — Parsed robots.txt per host, refreshed daily. A host whose robots.txt fails to fetch is treated as disallowed for a while. Also stores crawl-delay and sitemap hints.
• Web servers — The hosts being crawled. They are slow, wrong, hostile, or down in every possible way, and the crawler must remain correct regardless.
• Parser / extractor (HTML parse · link extraction) — Parses HTML, extracts and normalises links (resolve relative URLs, strip fragments and known tracking parameters, lowercase host), extracts canonical tags and metadata, and computes a content fingerprint for near-duplicate detection.
• URL-seen store (sharded KV of fingerprints) — Tells whether a normalised URL is already known and when it was last fetched. Billions of 8-byte fingerprints in a sharded key-value store, fronted by a Bloom filter for fast negatives. This is what keeps the frontier from growing without bound.
• Content dedupe (SimHash index) — Near-duplicate detection by SimHash: pages whose 64-bit fingerprints differ in at most 3 bits are treated as duplicates. Indexed in bit-permuted tables so lookup is a handful of exact-match queries, not a scan.
• Content store (object storage · WARC) — Fetched pages with headers and fetch metadata, appended to compressed archive files (WARC) in object storage, with an index by URL fingerprint and fetch time. Downstream consumers read from here.
• Crawl log (Kafka · fetch events) — One event per fetch outcome (status, size, change detected, timing). Feeds the freshness model, monitoring, and downstream indexers that want to know what changed.
• Freshness scheduler (change-rate model) — Batch and streaming job that estimates each page's change rate from its fetch history and importance, and re-enqueues pages into the frontier at the right time with the right priority.
• Coordinator (ZooKeeper / etcd) — Assigns host ranges to frontier partitions and fetcher groups, tracks membership, and rebalances when nodes join or fail. Small, strongly consistent, rarely on the hot path.

1. Fetch one page — The basic loop: lease a URL from a host that is allowed right now, check robots, fetch with limits, parse, discover links, store. Everything else in the design exists to keep this loop fast and polite.
   1. Fetcher asks the scheduler for work; the scheduler picks a host whose cooldown has expired and pops its next URL from the frontier.
   2. Fetcher resolves the host through the local DNS cache.
   3. Fetcher checks the URL against the host's cached robots rules.
   4. Fetcher issues the request with conditional headers, a timeout, and a size cap.
   5. Fetcher releases the host with its next-allowed-time and hands the response to the parser.
   6. Parser extracts links, normalises them, and checks each against the URL-seen store.
   7. Parser writes the page to the content store, computes the SimHash, and enqueues new URLs into the frontier with an initial priority.
2. Keeping the crawl polite at 400 pages per second — One request per host per second means the crawler needs hundreds of hosts ready at any instant and must never let two fetchers hit the same host. The scheduler and the frontier partitioning make that a local decision.
   1. Coordinator assigns each host to exactly one frontier partition by hashing the host name.
   2. Scheduler keeps a heap of hosts by next-allowed-time and hands out at most one in-flight URL per host.
   3. A large site (Wikipedia, 100 M pages) is crawled at 1 page per second like everyone else, unless it says otherwise.
   4. Many hosts share one IP (shared hosting); the crawler also limits per IP.
   5. Host stats flow to the crawl log so operators can see which hosts are throttling, failing, or dominating.
3. Discovering a URL that is already known, or content that is — Most extracted links point to URLs the crawler already has, and a good fraction of pages are copies. Both checks must be cheap, because they run on every link and every page.
   1. Parser normalises the extracted URL to its canonical form.
   2. URL fingerprint is checked in the Bloom filter and then in the sharded URL-seen store.
   3. New URLs are inserted into URL-seen and the frontier atomically enough: URL-seen first, then frontier.
   4. Fetched content is fingerprinted with SimHash and looked up in the near-duplicate index.
   5. A duplicate is recorded with a pointer to its original; its outlinks are deprioritised and its re-crawl interval lengthened.
4. A host that never ends: crawler traps and abuse — Some sites generate infinite URLs: calendars, faceted search, session ids, symlink loops. Others are simply hostile. The crawler bounds work per host and detects patterns rather than trusting the web.
   1. A fetched page yields thousands of links to the same host with slightly varying query strings.
   2. The scheduler notices the host's fetched count and duplicate ratio climbing without new content.
   3. Fetcher hits a page that streams forever or returns a 500 MB "HTML" file.
   4. Redirect chains loop or fan out across hosts.
   5. A host returns 429 or 503 with Retry-After, or its robots.txt changes to disallow.
5. Re-crawling for freshness — The web changes at wildly different rates. A news front page changes every few minutes; a 2009 blog post never will. The freshness model spends the fetch budget where change is likely and important.
   1. Fetch events with change detection flow into the crawl log.
   2. Freshness job updates each page's estimated change rate.
   3. Freshness job computes the next fetch time from change rate, importance, and budget, and re-enqueues the URL.
   4. Sitemaps and external hints short-circuit the model.
   5. Budget is enforced per host and globally: if the frontier's due set exceeds capacity, lower-value re-crawls slip.

Ask: Why not one big priority queue of URLs? How do you combine priority with per-host politeness?

Good answers name: Two-level frontier: priority front queues feeding per-host back queues with a next-time heap (Mercator), Single global priority queue, One queue per host with round-robin fetchers, Kafka topic per priority with consumer-side host throttling.

Our pick: Partition the frontier by hash(host) across N nodes so each host lives in exactly one place. Within a node: a set of priority front queues (say 10 levels) from which a selector picks URLs biased toward higher priority; each selected URL is appended to its host's back queue (bounded, spilling to disk or RocksDB, since most hosts have few URLs and a few have millions). A min-heap keyed by next-allowed-time holds hosts with non-empty queues; the lease API pops ready hosts, hands out the head URL, and re-inserts the host on release with next time = now + max(delay, k × response time). Persistence is a RocksDB-backed queue per partition with a write-ahead log, so a node restart resumes; the coordinator reassigns partitions on failure. Capacity is added by adding partitions, which move hosts wholesale.

1. A frontier node dies. What is lost?
   In-flight leases expire and their URLs return to the queue on the replacement node, which rebuilds from the RocksDB state on the node's replicated disk or from a checkpoint plus the crawl log. A few minutes of enqueued URLs since the last checkpoint may be lost; they are re-discovered on the next crawl of their parents, so nothing is permanently lost. Duplicated fetches are prevented by URL-seen.
2. How do you avoid every fetcher hammering one frontier node?
   Fetchers are assigned to partitions by the coordinator so each partition has a fixed set of fetchers, and lease requests are batched (50 URLs across many hosts). The frontier node's work per lease is a heap pop and a queue read, tens of microseconds; one node serves tens of thousands of leases per second, far more than its share of 800/s.
3. Priority levels: what feeds them and how do you avoid starvation?
   Priority from importance (link-graph score, host reputation), freshness need, and depth. The selector uses weighted sampling across levels (level 1 chosen 40 % of the time, level 10 1 %) rather than strict priority, so low levels drain slowly instead of never. Discovery URLs and re-crawls have separate budgets so neither starves the other.
4. A host has 5 M pending URLs. Where do they live?
   Not in memory. The back queue for that host is an on-disk queue (RocksDB range keyed by host, sequence) with only the head cached. The cap on pending URLs per host (100 k) is a soft limit: beyond it, only higher-priority URLs are admitted and the rest are dropped and re-discovered later. A crawl of that host at 1/s will take 58 days anyway, so holding millions is pointless.

Ask: How do you check 20 000 extracted links per second against 15 billion known URLs cheaply?

Good answers name: Bloom filter in memory + sharded key-value store of 64-bit fingerprints with metadata, Relational table with a unique index on URL, Bloom filter only, Keep it in the frontier partition by host.

Our pick: Normalise, then fingerprint the URL with a 64-bit hash. A Bloom filter sized for 20 B entries at 1 % false positives (~24 GB) lives in memory on each parser node (or per frontier partition, since host-partitioning co-locates a host's URLs); a negative means new, and the URL is inserted into both the filter and the KV store and enqueued. Positives (99 % of links) go to a sharded key-value store (RocksDB-based or DynamoDB-class) keyed by fingerprint holding last fetch time, status, and content hash; the parser uses that to drop the link or to re-enqueue if due. The filter is rebuilt from the KV store during quiet periods as it fills, and the KV store is the source of truth. Batch lookups (MGET of 50) keep the per-page cost to one round trip.

1. A Bloom filter false positive marks a genuinely new URL as seen. Is it lost forever?
   It would be, if the filter alone decided. With the KV confirmation step a false positive costs one lookup that returns null, and the URL is then treated as new. That is the reason for the two-tier design: the filter reduces load, the store is the truth.
2. How do you handle the same page at http and https, or with and without www?
   Normalisation policy, informed by data: prefer https when both resolve, and treat www and apex as the same host only when they return the same content (learned from the dedupe index). rel=canonical and redirects are the site's own answer and override heuristics. Get this wrong and the corpus doubles.
3. URLs are 8-byte fingerprints in the store. How do you get the URL back?
   The frontier and content store keep the full URL alongside their records; URL-seen never needs to return it. If an operator wants to look up a URL, they fingerprint it first. Storing the URL in URL-seen would multiply its size by ten for no read path that needs it.
4. The parser and the URL-seen store are in different regions. What happens to latency?
   Twenty thousand lookups per second across a 50 ms link is unworkable without batching and co-location. Keep URL-seen shards in the same region as the parsers, partition both by host or fingerprint range identically, and batch. If the crawl is multi-region, partition the crawl itself by host across regions so each region owns its URL-seen slice.

Ask: Exact hashing catches mirrors byte for byte. How do you catch the 30 % of pages that are the same article with a different sidebar?

Good answers name: SimHash of shingled text with a permuted-table index for Hamming distance ≤ 3, MinHash + locality-sensitive hashing, Exact content hash (SHA-256), Compare against the previous version of the same URL only.

Our pick: Extract the main text (strip navigation, ads and scripts with a boilerplate remover), shingle it into overlapping word 4-grams, and compute a 64-bit SimHash. To find near neighbours, store each fingerprint in, say, 4 tables, each keyed by a different 16-bit block of the fingerprint (with the remaining bits permuted to the front). Two fingerprints within Hamming distance 3 must agree exactly on at least one of the 4 blocks (pigeonhole), so a lookup is 4 exact-prefix range scans over a few candidates each, then a popcount check. Each table is a sorted key-value store sharded by prefix. On a hit, mark the page a duplicate of the earliest-seen or canonical original; still store the fetched copy but exclude it from downstream and lengthen its re-crawl interval.

1. Two different news articles about the same event hash within distance 3. False positive; how bad?
   It drops a real page from the index, which is the expensive error. Mitigate with a second check on hits: compare title and length, or compute a MinHash similarity only for candidates, and require both to agree. Tune the distance threshold on a labelled sample; distance 3 on 64 bits is conservative for pages longer than a few hundred words.
2. Where does the index live and how big is it?
   15 B fingerprints × 4 tables × ~16 bytes is roughly 1 TB, sharded by table and prefix across a key-value cluster. Inserts are 4 writes per page (1 600/s), lookups 4 reads; trivial load. Keep it separate from URL-seen because keys and access patterns differ.
3. A page is a duplicate today and unique tomorrow (the original was deleted). What happens?
   The duplicate mark points to the original's fingerprint. When the original 404s on re-crawl, a small job promotes the earliest remaining member of the cluster to canonical. In practice this is rare enough that a nightly batch suffices.
4. Would you dedupe before or after storing?
   After fetching, before enqueuing outlinks, and store regardless. Storage is cheap relative to fetch; the record that a URL served duplicate content is useful; and dedupe policy may change, in which case you want the bytes. What you must not do is spend fetch budget on the duplicate's outlinks at full priority.

Ask: What exactly does "polite" mean in code, and what happens if you get it wrong?

Good answers name: Structural politeness: one in-flight per host, adaptive delay, robots enforced at lease, clear identity, Global rate limit only, Per-host limit enforced by each fetcher independently, Rotate IPs and user agents to avoid blocks.

Our pick: Identify honestly (a stable user agent naming the bot and a URL explaining it, plus reverse-DNS-verifiable IPs). Fetch robots.txt per host, cache it 24 h, honour Disallow, Allow, Crawl-delay and Sitemap for our agent, and treat a 5xx on robots.txt as "disallow for now". Serialise requests per host in the scheduler with a delay of max(crawl-delay, 1 s, 10 × the host's recent response time) so a struggling server is automatically crawled slower, plus a per-IP limit for shared hosting. Back off exponentially on 429, 503 and timeouts, honouring Retry-After; park a host after repeated failures. Respect meta robots and X-Robots-Tag on individual pages (nofollow, noindex) at parse time. Provide an opt-out and a contact address, and answer them. Large sites that want faster crawling can raise the rate in robots.txt or by arrangement.

1. Robots.txt is fetched but the site changes it an hour later to disallow everything. How long until you stop?
   Up to the 24-hour cache TTL by default. Reduce exposure by re-checking robots on every 4xx or 5xx from the host and by shortening the TTL for hosts that change it often. Google re-fetches robots roughly daily too, and site owners know that.
2. A CDN fronts 100 000 sites with one IP range. Per-IP limits would throttle all of them.
   Detect known CDN ranges (published IP lists) and disable the per-IP limit for them while keeping per-host limits; the CDN can absorb it and will tell you with 429s if not. For unknown shared IPs keep the per-IP cap.
3. How do you crawl a site that requires JavaScript to render links?
   A separate lane: pages flagged as JS-dependent (few links, known frameworks) go to a headless-browser fetcher pool that is 10 to 50× more expensive per page, with a much smaller budget and higher priority threshold. The main crawler stays HTML-only. Sitemaps often rescue such sites without rendering.
4. How do you know the crawler is behaving?
   Per-host metrics: request rate, error rate, response time trend, robots-disallow counts. Alert on any host receiving over the allowed rate (a bug), on a rising 429 rate across hosts (we are too aggressive), and on the abuse mailbox. Keep a per-host fetch log for 90 days so a complaint can be investigated with evidence.

Ask: You can only fetch 400 pages a second. Which pages do you re-fetch, and when?

Good answers name: Per-page Poisson change-rate estimate × importance, clamped, with sitemap and ping overrides, Uniform refresh interval for everything, Refresh proportional to observed change rate, Refresh by importance only.

Our pick: For each page keep a compact history (last N fetch outcomes: changed or not, and timestamps) and estimate a change rate λ with a Poisson model, using 304s and content hashes for change detection. Compute the next fetch time as now + interval where interval = clamp(k / (λ × importance^α), 1 h, 90 d), with importance from an offline link-graph score and host-level priors for new pages. Reserve a fixed share of capacity (say 40 %) for discovery so refresh cannot starve it, and vice versa. Sitemap lastmod, feeds, and publisher pings bypass the model with high priority. Track the freshness SLI as the age of the stored copy for the top-importance pages and tune k to hit the targets (news within an hour, tail within a quarter).

1. A page changes every minute (a stock ticker). How often do you fetch it?
   Not every minute; the clamp and the cap on λ mean it is fetched at the ceiling for its importance, perhaps hourly, and it is never fresh. Pages like that are handled by the downstream product differently (an API, not a crawl). Spending more here is provably wasted under a fixed budget.
2. Change detection says a page changed but it was only the date in the footer.
   Hash the main content after boilerplate removal, not the raw HTML, and treat a SimHash distance of 0 to 1 as unchanged. Otherwise every page with a clock or an ad rotation looks like it changes constantly and the model inflates its rate.
3. What about pages that disappear?
   A 404 or 410 marks the page gone; re-check a couple of times over weeks (sites have outages), then stop scheduling it and mark it in URL-seen so re-discovered links to it are ignored for a long time. A permanent redirect updates the canonical URL and transfers the history.
4. How would you evaluate whether the scheduler is good?
   Sample pages, fetch them at a high rate out of band for a while to learn their true change times, and measure how stale the production copy was on average, weighted by importance. Compare against uniform scheduling on the same sample. Also track wasted fetches (unchanged) as a share of refresh fetches; a healthy model sits well below 50 %.