# Design a web crawler > Design a crawler for billions of pages: the URL frontier, politeness per host, robots.txt, DNS, duplicate detection, recrawl scheduling and traps. System Design roadmap · Case studies · 19 min read · https://levelcode.org/roadmaps/system-design/design-web-crawler A web crawler starts from a few URLs, downloads each page, extracts its links and repeats, until it has fetched a meaningful slice of the web. Search engines, archives, price monitors and the datasets behind language models all depend on one. The loop is ten lines of code; the hard part is running it over billions of pages without overloading websites, refetching the same content endlessly or getting stuck in infinite link mazes. This lesson designs a crawler for a search engine. ## Requirements **Functional:** - Given seed URLs, discover and download HTML pages across the public web. - Store each page's content and metadata for the indexing system downstream. - Recrawl pages so the stored copy stays reasonably fresh: news front pages within minutes, most pages within weeks. - Out of scope: rendering JavaScript-heavy pages (discussed at the end), images and video, and the search index itself. **Non-functional:** - **Politeness**: never overload a website. Respect `robots.txt` and limit requests per host. - **Scale**: billions of pages; the system must scale horizontally by adding machines. - **Robustness**: the web is hostile and broken: malformed HTML, endless redirects, slow servers, deliberate traps. - **Efficiency**: don't download the same content twice when it hasn't changed. ## Numbers ```text target: 5 billion pages, refreshed on average every 30 days fetch rate: 5e9 / (30 × 86,400 s) ≈ 2,000 pages/s steady; plan for 5,000/s average page: ~100 KB of HTML (compressed in transit to ~25 KB) download bandwidth: 5,000/s × 25 KB ≈ 125 MB/s ≈ 1 Gbit/s storage: 5e9 × 100 KB = 500 TB raw; ~100 TB compressed, per snapshot URLs known: ~10× pages fetched → tens of billions of URLs in the frontier and seen-set ``` The fetch rate itself is modest for a fleet of machines. The difficulty is the bookkeeping: tens of billions of URLs, each with a priority and a next-fetch time, organised so that no host is hit too often. ## The crawl loop ```sequence title: Crawling one URL participants: Frontier, Fetcher, DNS cache, Website, Parser, Content store Frontier -> Fetcher: Next URL for host example.com (its turn now) Fetcher -> DNS cache: Resolve example.com DNS cache --> Fetcher: 93.184.216.34 Fetcher -> Website: GET /page (If-Modified-Since) Website --> Fetcher: 200 OK, HTML Fetcher -> Content store: Store page if content is new Fetcher -> Parser: Extract links Parser -> Frontier: New URLs (normalised, not seen before) > The frontier decides when each new URL is fetched. ``` Each box is a separately scaled tier. Fetchers are I/O-bound (thousands of concurrent connections per machine); parsers are CPU-bound; the frontier is a large, carefully structured queue. Content goes to object storage, and an event per stored page tells the indexer. ## The URL frontier: priority and politeness The **frontier** holds URLs waiting to be fetched. A plain FIFO queue fails in two ways: it fetches unimportant pages before important ones, and when a popular site's links pile up in the queue, the crawler hammers that one site with hundreds of requests a second. The classic design has two layers: 1. **Front queues for priority.** Each URL gets a score: a page's importance (for example a link-based score), how often it changes, how long since it was last fetched. URLs go into one of several priority queues; selection favours higher queues without starving lower ones. 2. **Back queues for politeness.** Each back queue holds URLs for **one host**, and each host has a "next allowed fetch time". A heap ordered by that time tells fetchers which host is ready next. After fetching from a host, set its next time to `now + delay`, where the delay respects the site's `Crawl-delay` if set, and otherwise scales with how long the server took to respond (a slow server gets more breathing room). Fetchers ask the frontier for "a URL from a host whose turn it is", so politeness is enforced by construction rather than by every fetcher remembering it. At tens of billions of URLs, the frontier can't live in one process's memory. **Partition by host**: hash the hostname to pick a frontier shard, so all URLs of one host, and its politeness timer, live on one shard. New links extracted anywhere are routed to the shard that owns their host. Each shard keeps the head of each queue in memory and the rest on disk. ## robots.txt and DNS Before fetching from a host, the crawler fetches its `/robots.txt`, which says which paths crawlers may visit: ```text User-agent: * Disallow: /cart/ Disallow: /search Crawl-delay: 5 User-agent: ExampleBot Disallow: / ``` Cache it per host (for about a day) and check every URL against it before fetching. Identify your crawler honestly in the `User-Agent` header with a URL explaining what it is and how to contact you; site owners need to be able to block or complain. **DNS** is a surprisingly common bottleneck: every new host needs a lookup, standard resolvers are slow and rate-limited, and a crawler talks to millions of hosts. Run a dedicated caching resolver close to the fetchers, cache aggressively, and resolve asynchronously so a slow DNS answer doesn't block a fetcher thread. ## Not doing the same work twice The web repeats itself constantly, and the crawler must notice at three levels. **The same URL.** Links come in many spellings: `HTTP://Example.com:80/a/../b?utm_source=x#top` is the same page as `http://example.com/b`. **Normalise** before anything else: lowercase scheme and host, drop default ports and fragments, resolve `..`, sort query parameters, strip known tracking parameters. Respect `` when a page declares its canonical URL. **URLs already seen.** Before adding a URL to the frontier, check whether it's been seen. With tens of billions of URLs, an exact set costs hundreds of gigabytes; a [Bloom filter](https://levelcode.org/concepts/bloom-filters) per shard answers "definitely not seen" or "probably seen" in a fraction of the memory. A false positive means occasionally skipping a new URL, which is acceptable for a crawler. Exact records of fetched URLs (with last fetch time and content hash) live in a key-value store for recrawl scheduling. **The same content at different URLs.** Mirrors, session IDs in URLs and printer-friendly versions serve identical or near-identical pages. Store a hash of each page's normalised content: an exact match means a duplicate. Near-duplicates (the same article with a different ad block) are caught with similarity fingerprints such as SimHash, where similar documents get fingerprints that differ in only a few bits. ## Recrawling: freshness on a budget Fetching every page every day is impossible, and unnecessary: most pages rarely change. Schedule each URL's next fetch from evidence: - **Change rate**: if the last five fetches all returned the same content hash, double the interval (up to a cap); if it changed, shorten it. News front pages converge to minutes, an old documentation page to months. - **Importance**: popular pages are worth fetching more often, because stale results there are seen by more users. - **Cheap revalidation**: send `If-None-Match` with the stored ETag or `If-Modified-Since` with the last date. A `304 Not Modified` costs the site and you almost nothing. - **Sitemaps** (`sitemap.xml`, often listed in `robots.txt`) give `lastmod` dates; trust them in proportion to how accurate they've proven for that site. ## Traps and failures The web contains structures, some accidental and some deliberate, that can consume a naive crawler forever: - **Infinite spaces**: a calendar whose "next month" link goes on forever, or faceted search producing endless combinations of filters. Cap URLs per host, the depth of path segments and URL length, and deprioritise URLs with many query parameters. - **Redirect loops and chains**: follow at most 5 redirects per fetch. - **Huge or endless responses**: cap the response size (say 10 MB) and the total fetch time. - **Slow servers**: set connect and read timeouts, and treat repeated timeouts as a signal to slow down for that host. - **Spam and link farms**: thousands of generated hosts linking to each other. Per-domain budgets (not just per host) and quality scores keep them from eating the crawl. Fetchers should treat every response as untrusted input: parse HTML with a robust, memory-bounded parser, and run parsers in isolated processes so a pathological page can only crash one worker. ## Practice The search team asks for two changes: 1. Many important sites are now single-page apps whose HTML is an empty shell until JavaScript runs. The crawler must index their content. 2. A large news site complains that your crawler sent it 800 requests per second, even though politeness is enforced per host. How do you handle each? **Solution** **1. JavaScript-rendered pages.** - Rendering requires a headless browser, which is 10–100× more expensive per page than an HTTP fetch (CPU, memory, and it fetches the page's scripts, styles and API calls too). Don't render everything: fetch HTML as usual, and send a page to a **rendering queue** only when it looks like a shell (little text, a large script bundle, a known framework's root element) and the site is important enough. - Run a separate **renderer fleet** of headless browsers with strict limits: time budget per page, blocked heavy resources (images, video, fonts), and no execution of anything beyond what's needed to produce the DOM. - Politeness still applies: the scripts and API calls a rendered page makes hit the site too, so count them against the host's budget and cache common script files across pages of the same site. **2. 800 requests per second to one site.** - Politeness was enforced per **host**, and the news site uses hundreds of subdomains (`sport.news.example`, `cdn1.news.example`, regional editions) that all hit the same servers. Apply politeness at the level of the **registrable domain** and, better, of the **IP address** the hosts resolve to: hosts behind the same IPs share one rate limit. - Make the delay **adaptive**: if response times rise or the site returns 429 or 503, back off sharply for that domain, and respect `Retry-After`. - Give site owners a contact address in the `User-Agent`, honour `Crawl-delay`, and consider a self-service way for verified site owners to set a crawl rate. ## Key takeaways - A crawler is a loop of frontier, fetch, store and parse; each stage scales independently. - The frontier combines priority queues with per-host back queues and next-fetch times, so politeness is built into what fetchers are given. - Partition the frontier by host, cache robots.txt and DNS, and identify your crawler honestly. - Normalise URLs, use Bloom filters for the seen-set, and fingerprint content to skip duplicates and near-duplicates. - Schedule recrawls by observed change rate and importance, revalidate with conditional requests, and defend against traps with caps on depth, size, redirects and URLs per site. ## Quiz 1. Why does the frontier keep a separate back queue and next-fetch time per host? A. So that no host receives requests more often than its allowed delay, regardless of how many of its URLs are queued B. To store URLs in alphabetical order C. Because DNS lookups require it D. To prioritise important pages **Answer: A.** Politeness is enforced by construction: a fetcher only receives a URL whose host's turn has come. Priority is the job of the front queues. 2. Why is a Bloom filter acceptable for the 'URL already seen' check? A. It never makes mistakes B. It sorts URLs by priority C. Its only error is occasionally reporting an unseen URL as seen, which skips a page, and it uses far less memory than an exact set D. It stores page content **Answer: C.** Bloom filters have false positives but no false negatives. Rarely skipping a new URL is a fine trade for fitting tens of billions of entries in memory. 3. A page's last five fetches all returned identical content. What should the scheduler do? A. Remove it from the crawl B. Fetch it more often in case it changes C. Fetch it on the same schedule D. Increase the interval before the next fetch **Answer: D.** Recrawl frequency should follow observed change rate (weighted by importance). Unchanged pages get longer intervals, and conditional requests make each check cheap. 4. Which measure protects against a calendar page whose 'next month' link continues forever? A. Following at most five redirects B. Caps on URLs per host and path depth, and deprioritising URLs with many parameters C. Using HTTPS D. Caching robots.txt **Answer: B.** Infinite URL spaces need budgets: a cap on how many URLs one host may contribute, and limits on depth and query complexity. Redirect limits handle a different trap.