Walkthrough: a web crawler

What you are building

"Design a web crawler" (a chapter of Alex Xu's first volume) is a graph traversal with three rules bolted on that make it a systems problem. The web is a graph of pages joined by links; a crawler starts from seed URLs, downloads each page, extracts the links and repeats. The rules are the real question: be polite (do not hurt the sites you visit), be robust (the web contains traps, garbage and malice), and stay fresh (pages change, and the crawl never finishes). The purposes differ (a search index, a web archive, a data set for model training), but the machinery is the same. Requirements to say aloud:

• Scale. Billions of pages, so every data structure is sized for billions and most live on disk or are sharded.
• Politeness. Bounded request rate per host, obeying robots.txt, an honest user-agent.
• Robustness. Malformed HTML, endless URL spaces, slow or hostile servers, DNS failures.
• Freshness and priority. Spend a fixed budget of fetches on the pages that matter most and change most.
• Extensibility. New content types (PDF, images) plug in without rewriting the loop.

Capacity estimation

The inputs are assumptions chosen to be round; the method is what to copy. Where a figure comes from a paper, it is attributed.

• Throughput: design for 600 pages a second: 600 × 86,400 = 51.8 million pages a day, or about 1.56 billion a month. (For scale, the Mercator crawler processed about 50 million URLs a day over 17 days in 2000, about 43 million of them successful downloads, and IRLbot averaged 1,789 pages a second for 41 days on one server.)
• Bandwidth: assume 100 KB of HTML a page: 600 × 100 KB = 60 MB/s, or 480 Mbps of download.
• Storage: an index of 1 billion pages × 100 KB = 100 TB of raw HTML; at an assumed 4:1 compression, 25 TB.
• URL checks: with 10 links per page (about what Mercator saw in 2000; IRLbot's 2007 crawl parsed 394.6 billion links from 6.38 billion pages, about 62 per page, which would make it 37,000 a second), 600 × 10 = 6,000 URL-seen lookups a second. Mercator's first disk-based table managed about 125 seeks a second, 750 submissions a second after caching, which with 10 links per page capped it at 75 downloads a second. We need 8 times that. On the spinning disks of 2000 a seek per lookup cannot work; today's SSDs change the arithmetic, but a URL-seen set that must grow to tens of billions of URLs still wants memory-resident or batched structures for cost and latency.
• URL-seen set: assume 5 billion known URLs. Mercator's in-memory table of URL fingerprints (it stored 5 of the 8 fingerprint bytes plus overhead) cost slightly over 5 GB per billion URLs, so about 25 GB for a near-exact set; a Bloom filter at a 1% false-positive rate needs about 9.585 bits an entry (derived below), 5 × 10⁹ × 9.585 bits = 47.9 Gbit = 6.0 GB.
• Simhash fingerprints: 1 billion pages × 8 bytes = 8 GB.
• Crawler nodes: at an assumed 30 pages a second a node (network and DNS bound), 600 ÷ 30 = 20 nodes, each moving 3 MB/s (24 Mbps).
• Concurrency: by Little's law, in-flight fetches = rate × time per fetch. At an assumed 1 second including DNS, 600 × 1 = 600 in-flight requests cluster-wide, 30 per node.

The loop

The URL frontier: priority in front, politeness behind

A plain FIFO queue gives breadth-first order, and breadth-first order is rude: relative links mean a page's links share a host, so the queue contains runs of the same host and many threads hit one server at once. The Mercator paper reports that even a frontier that allowed only one thread per host still drew a handful of complaints per crawl, because it did not stop a stream of requests to one host with no pause between them. The fix, described in the paper and in the Stanford IR book, is two layers of queues:

• Front queues (priority). F queues, numbered by priority. A prioritizer assigns each URL an integer from 1 to F from its history (whether the page has changed since the last download, its estimated quality). Selection is random but biased to high-priority queues.
• Back queues (politeness). B queues, each holding URLs from one host only, plus a table from host to queue. A min-heap has one entry per back queue, keyed by the earliest time that host may be contacted again. A fetch thread pops the root, waits until its time, fetches the head URL, and re-inserts the queue with a new time. When a back queue empties, it is refilled from a front queue.
• The gap. A common heuristic, in the Stanford text and in Mercator's production settings, is to wait about 10 times as long as the last download from that host took before contacting it again.
• Back off when told to. A 429 (Too Many Requests, RFC 6585) or a 503 may carry a Retry-After header, either a number of seconds or an HTTP date (RFC 9110). Treat it as a floor: push that host's heap entry out to at least that time, and without the header back off exponentially while the errors continue. Google's crawlers treat 5xx and 429 as a sign the server is overloaded, slow down, and speed up gradually after 2xx responses return. The header is optional, so the crawler cannot rely on it.

How many hosts must be waiting? If every download from a host takes f seconds and the gap is 10f, one host can be fetched at most once every 11f seconds (the gap counted from completion). At a target rate R with average f, the crawler needs about R × 11f distinct hosts ready at all times. At 600 pages a second and f = 0.5 s that is 600 × 5.5 = 3,300 hosts. Since threads needed = R × f = 300 (counting only download time), that is 11 queues per thread, whatever f is. Mercator reports using only three times as many back queues as threads with the 10× gap, and says that was sufficient to keep all threads busy, without giving a derivation. With equal fetch times the arithmetic says three would leave threads mostly idle; real fetch times vary a lot, and fast hosts cycle faster, which may be part of the answer. The lesson is to size the queue count from your own gap rule and measured fetch times, not from a quoted ratio.

Dry run: one thread, three hosts, and why politeness idles a crawler

Gap = 10 × the last download time, counted from when the download finishes. Host a (download 0.4 s) has two URLs, b (0.2 s) has three, c (1.0 s) has one. One fetch thread, all hosts ready at time 0.

Six fetches in 5.0 seconds, 1.2 a second. Busy time was 0.4 + 0.2 + 1.0 + 0.2 + 0.4 + 0.2 = 2.4 s, idle time 1.0 + 1.6 = 2.6 s, so the thread was 48% busy. With three hosts one thread cannot keep busy, which is the case for a frontier with thousands of hosts ready; and a slow host's long gap (c's would be 10 seconds) never blocks the others, because it only delays that host's own queue in the heap. Politeness is a scheduling problem, and the heap solves it without a sleeping thread per host.

robots.txt and DNS: two caches in front of every fetch

robots.txt. Before fetching anything from a host, a polite crawler fetches /robots.txt and obeys it. The protocol is now a standard, RFC 9309 (2022), and its rules are the details interviewers like:

• Matching. The most specific rule wins, meaning the match with the most octets; if an allow and a disallow are equivalent, allow is used; if nothing matches, the URL is allowed. User-agent matching is case-insensitive and falls back to the * group.
• Caching. A crawler may cache the file but should not use a copy older than 24 hours, unless the file is unreachable. Google's crawler says it generally caches for up to 24 hours too. Mercator kept a fixed-size LRU cache of robots rules (2¹⁸ hosts by default).
• Failure modes. If the server says the file is unavailable (a 4xx), the crawler may access any resource. If it is unreachable (a 5xx or a timeout), RFC 9309 says the crawler must assume complete disallow, and may treat the file as unavailable, or keep using a cached copy, only after a long outage, for which the RFC's example is 30 days. Google's crawler is less strict than the RFC: it stops crawling the site for the first 12 hours while it keeps retrying, then uses the last good copy for up to 30 days, and if it never had one it assumes no restrictions. Choose the RFC's rule when you have no cached copy and want the safe default; if you copy Google's, say so, because it crawls on a stale copy or an empty one.
• Size and redirects. Parse at least the first 500 kibibytes (Google ignores content past 500 KiB), and follow at least five redirects.
• Not in the standard. Crawl-delay is not part of RFC 9309, and Google's crawler does not support it. Some other crawlers support it, so you may honour it where present, but do not rely on it; derive your own per-host gap, as above. Also: robots.txt is not access control. The RFC says so explicitly, and a disallowed URL can still be listed by search engines without a snippet.

DNS. Resolving a host name can take seconds, because a lookup may need many round trips across the world. Mercator found DNS "a well-documented bottleneck"; caching helped only partly because the standard resolver calls were synchronized, allowing one outstanding lookup per process. Replacing them with a multi-threaded resolver that forwards to a local name server cut the share of each thread's time spent on DNS from 70% to 14%. The modern version: an asynchronous resolver with its own cache that respects record TTLs, and sharding by host (below) so each node needs only its own hosts' records.

URL normalization and the URL-seen set

The same page has many spellings. Two URLs must be compared after normalizing them, or you fetch the same page repeatedly. RFC 3986 section 6 defines the safe steps: lowercase the scheme and host; uppercase the hex digits of percent-encodings; decode percent-encoded unreserved characters; remove dot-segments; drop a default port; treat an empty path as /. Crawlers then add their own policy, such as discarding fragments (they are never sent to the server) and tracking parameters.

The URL-seen test asks, for each extracted link, "have I already queued or fetched this?". Mercator's duplicate URL eliminator stored 8-byte Rabin fingerprints of URLs in a hash table, keeping 5 of the 8 bytes in each entry (slightly over 5 GB for a billion URLs) and used sorted batch merges against a disk file when memory ran out, so that lookups became sequential reads instead of random seeks. IRLbot, the single-server crawler that reached 6.3 billion pages, showed that batch-merge checkers of that kind (merging a batch of new URLs into a sorted file, as Mercator's later design did) have total disk work that grows roughly quadratically with crawl size, and replaced them with DRUM, which batches keys and checks and updates them with bucket sort on disk.

A Bloom filter is the compact in-memory alternative, at the price of one-sided errors. With m bits for n items and the best number of hash functions k = ln 2 × (m/n), the false-positive rate is about 0.6185^m/n. For 1%: m/n = ln(0.01) ÷ ln(0.6185) = (−4.605) ÷ (−0.4805) ≈ 9.585 bits an item, with k = ln 2 × 9.585 ≈ 6.6, so 7 hash functions. For the 5 billion URLs that is the 6.0 GB above, against about 25 GB for a near-exact fingerprint set. The gap is mostly the price of accepting a 1% error rate instead of an almost zero one. The error direction decides where it is safe: a false positive here means a new URL is wrongly thought seen and never crawled, losing about 1% of discoveries (their links usually recur from other pages, so the loss is smaller in practice). That is acceptable for a URL set and not for the content-seen test, where a false positive would discard a genuinely new page. Bloom filters also cannot delete, so a recrawl needs a separate "last fetched" store, not the filter.

Duplicate content: exact and near

Different URLs often serve the same content (mirrors, ?sessionid=, print versions). After download, the crawler fingerprints the body and consults a content-seen set; Mercator's loop has exactly this step, and drops a document whose content was seen under a different URL. Exact hashing misses near duplicates, such as the same article with a different advertisement or timestamp. Two techniques:

• Shingling. Take every run of k consecutive tokens (k = 4 is typical), hash them, and compare the sets with the Jaccard coefficient |A∩B| ÷ |A∪B|; pages above a threshold such as 0.9 are near-duplicates. Keeping the minimum under 200 random permutations gives a 200-value sketch whose overlap estimates the Jaccard coefficient. Accurate, but a sketch per page is large; even Broder's compact variant (six Rabin fingerprints, two of which must match) takes 24 bytes a page, according to Manku et al.
• Simhash (Charikar; Manku, Jain and Das Sarma, WWW 2007). Hash each weighted feature to 64 bits; keep a 64-element vector where each feature adds its weight where its hash bit is 1 and subtracts where it is 0; the sign of each element gives one bit of the fingerprint. Similar documents get fingerprints that differ in few bits, the opposite of a cryptographic hash. The paper reports that for a repository of 8 billion pages, 64-bit fingerprints with a Hamming distance of at most 3 are reasonable, at a precision and recall near 0.75 in its experiment. The remaining problem is searching for neighbours: probing every fingerprint at distance exactly 3 means C(64, 3) = 64 × 63 × 62 ÷ 6 = 41,664 probes (the paper's count; including distances 0 to 2 it is 43,745).

The paper's trick is a pigeonhole argument. Split the 64 bits into 6 blocks. Two fingerprints that differ in at most 3 bits differ inside at most 3 blocks, so at least 3 blocks match exactly. Build one sorted copy of the fingerprints for each of the C(6, 3) = 20 ways to choose 3 blocks, with those blocks as the leading bits. A probe in each table finds the few fingerprints that agree on the chosen blocks (the paper's example expects about 8 per probe), and a Hamming-distance check settles each. That is 20 probes instead of 41,664, for 20 copies of the data: for our 1 billion fingerprints, 8 GB × 20 = 160 GB before compression, which is the price of speed.

Spider traps and crawl budgets

A spider trap is a part of a site that generates unlimited URLs: a calendar with a "next month" link forever, a session id in every URL, /a/b/a/b/a/b/... paths from a relative-link bug, filter combinations that multiply, or deliberate link farms. The IRLbot paper makes the case that breadth-first order is not neutral here: it reports that BFS eventually gets trapped in useless content, because spam sites' high branching factor lets their URLs overtake legitimate ones in the pending queue. Defences, from cheap to principled:

• Hard limits. A maximum URL length, a maximum path depth and a maximum number of query parameters, chosen as policy (the values are yours to tune) and logged when hit. Detect repeating path segments.
• Normalize first. Many traps are just un-normalized duplicates: drop known session parameters and sort the remaining ones.
• Per-host and per-domain budgets. Cap the pages fetched from a host per day. A per-domain budget needs every host of the domain on one node (see the next section). IRLbot's STAR algorithm lets a domain's budget grow with the number of in-links it receives from other domains, because spammers can create unlimited pages and hosts but must pay for each additional domain that could link to them (in the run reported, budgets were conservative: the top 10,000 ranked domains got budgets linearly interpolated between 10 and 10,000 pages, and every other domain got 10); a companion mechanism, BEAST, keeps over-budget URLs in ever-lower-frequency queues so the crawler does not keep rescanning them. In the run described, the crawler handicapped quickly branching spam and over 30 million low-ranked domains.
• Content signals. Near-duplicate pages (simhash) from one host at a high rate are a trap signature: lower that host's priority.
• Timeouts. A slow server that trickles bytes can pin a thread: cap time and size per fetch. IRLbot also lists deliberate DNS and HTTP delays as an attack.

Politeness also limits depth on huge hosts, which a budget formalizes. A site with 10 million pages fetched at one page every 2 seconds needs 20,000,000 s, 231 days. A crawler cannot "finish" such a site, which is why priority decides which of its pages come first.

Freshness: a budget, not a schedule

The crawl never ends because pages change. You have a fixed fetch budget (600 a second) and need to divide it between re-fetching known pages and discovering new ones. Tier the pages by how often they change and how much they matter, and give each tier an interval. An illustrative split of a 1-billion-page index:

• Adapt the interval. A simple policy: when a recrawl finds the page changed, halve its interval (to a floor); when unchanged, double it (to a ceiling). Pages migrate between tiers by themselves. This is a heuristic, not a result from the literature.
• Conditional requests cut bandwidth, not requests. Send If-None-Match with the stored ETag or If-Modified-Since; if the representation is unchanged the server answers 304 Not Modified with no body (RFC 9110). If an assumed 80% of recrawls return a 1 KB 304, recrawl traffic falls from 401 × 100 KB = 40.1 MB/s to 401 × (0.2 × 100 + 0.8 × 1) KB = 8.3 MB/s. It depends on servers sending validators, and a request still costs a politeness slot.
• Use hints, do not trust them. A sitemap can list up to 50,000 URLs (and 50 MB uncompressed) per file with lastmod; the protocol calls changefreq a hint, not a command, and says priority only ranks a site's own URLs against each other. Trust lastmod only for hosts where it has proved right.
• Priority signals. Link in-degree, host quality, past change rate, and depth from a seed. Feed the number to the front-queue prioritizer.

Distributed crawling: shard by host

The natural unit of ownership is the host, not the URL. Hash the host name to pick the owning node (consistent hashing, as in the sharding chapter). Everything that is per host then lives on one node: the back queue and its politeness timer, the robots rules, the DNS record, the host's budget. Mercator's distributed configuration does exactly this, partitioning the space of host names among its processes. If you sharded by URL instead, ten nodes might fetch from the same server at once and no node could enforce the gap.

A per-domain budget breaks that arrangement if the shard key is the host: the hosts a.example.com and b.example.com would hash to different nodes, and no node could see the domain's total. If you enforce domain budgets, hash the registrable domain (example.com, or example.co.uk, using the Public Suffix List) instead. All of a domain's hosts then share a node, the host queues and timers stay local, and the domain counter is one number in one place. The cost is coarser balance, since a domain with thousands of hosts is one unit; the alternative is to keep host sharding and give each node a fixed share of each domain's budget.

• Forwarding. A node that extracts a link for another node's host sends it there, in batches. At 6,000 extracted URLs a second across 20 nodes, if link targets were uniformly random 19 of 20 (95%) would leave the node. Real pages link mostly within their own host, which stays on the node, so that is an upper bound. Batch aggressively; even at 95%, 5,700 × about 100 bytes is 0.57 MB/s, well under 1 MB/s, so it is not a bottleneck.
• Resizing. Adding a node moves roughly 1 ÷ 21 of the hosts, about 4.8% of the frontier, with consistent hashing. Their pending URLs, robots cache and politeness timers move with them, and the timers may simply reset.
• Failure and checkpoints. Fetching is naturally idempotent. Mercator checkpoints its full state one to four times a day and, after a failure, loses only the work since the last checkpoint. Write the frontier to a durable log or store so a dead node's hosts can be reassigned.
• Hot hosts. A giant site is one host and one node, but the polite rate is slow enough (about 0.5 pages a second at a 2-second gap) that one node can serve it; the cost is that it takes months, as computed above.
• Where DNS and robots go. They shard with the host, so caches stay small and hit rates high, and a node never needs another node's robots rules.

Recognizing it in an unseen problem

• Signals: "crawl", "index the web", "build a search engine", "scrape product pages", "keep a mirror up to date", "link checker", or any traversal of an external graph you do not control.
• The structure to reach for: frontier with priority and per-host politeness, normalization and URL-seen, content-seen, budgets, host-sharded workers.
• The numbers an interviewer wants: pages a second from a pages-a-month target, bandwidth from page size, the URL-seen memory cost, and how many hosts must be ready to keep fetchers busy.
• The pitfalls to name unprompted: a FIFO frontier hammering one host, no URL normalization, spider traps and breadth-first order, treating robots.txt 5xx as "allow", sharding by URL instead of host, and a Bloom filter used for content-seen.
• The follow-up you will get: "how do you handle JavaScript-heavy pages?" Rendering is far more expensive than fetching; render selectively (high-priority hosts, pages whose static HTML is nearly empty) in a separate pool with its own budget.