System Design Handbook · llms.txt
A web crawler is a program that downloads web pages, finds the links on them, and then downloads the pages those links point to. For example, the crawler fetches https://example.com/, finds links to /about and https://news.example.org/today, adds both to its to-do list, and later fetches each of them, finding more links as it goes. Search engines run crawlers so they have a copy of the web to search.
In this chapter the crawler feeds a small search service. A user types hello world and gets back a list of pages, each with a title, a short snippet (a sentence or two of text from the page) and a link. The crawler's job is to keep the data behind that list complete and up to date.
It's a good interview question because the web is hostile to naive code. Pages link in cycles, so a careless crawler visits the same pages forever. Many URLs serve the same content, and some sites generate endless URLs. Every site belongs to someone else, and a crawler that fetches too fast can overload it. And a billion pages refreshed weekly comes to petabytes a month.
The chapter follows the four steps from The system design interview, step by step. The search engine design covers ranking and the index in more depth. This chapter spends its depth on the crawler.
The estimates below need a few more assumptions of our own. State them out loud in an interview:
A 30-day month has 30 × 86,400 = 2,592,000 seconds, about 2.6 million.
Crawling
Storage
Searching
A sanity check. Common Crawl, a nonprofit that publishes a free copy of the web, reported that its August 2026 crawl fetched 2.14 billion pages between August 7 and August 20, with 360 TiB of uncompressed content. That's 2,140,000,000 ÷ (14 × 86,400 s) ≈ 1,770 pages a second, close to our 1,540. It's also about 185 KB a page (360 TiB ≈ 396,000,000,000,000 bytes ÷ 2.14 billion), so our 500 KB is generous by almost 3 times. That's fine for a capacity plan.
What these numbers tell us. Search and crawling are two systems with different shapes. Search is read-heavy and latency-sensitive at tens of thousands of requests a second, so it needs caching and replicas. Crawling is a steady, throughput-bound job limited by bandwidth (6.2 Gbit/s), open connections (3,100) and "have we seen this URL?" checks (77,000 a second). Page content dominates storage, so the retention policy is the biggest storage decision: 72 PB for every version over three years, or 500 TB for the latest only. The index and snippets are small by comparison.
links_to_crawl, the to-do list ranked by priority, and crawled_links, a record of every page fetched with its signature and fetch time. Every access is by URL, which suits a key-value store.A crawler needs a starting list, the seed list. We assume we're given an initial links_to_crawl ranked by overall site popularity. If not, we can seed it with popular sites that link out to a lot of other content, such as large directories and news front pages, and discover the rest by following links.
links_to_crawl is the frontier: the URLs waiting to be fetched, each with a priority score. The crawler always takes the highest-scoring URL next. A Redis sorted set fits: unique strings, each with a numeric score, kept in score order. Adding a URL (ZADD) costs O(log N), and ZPOPMAX removes and returns the highest-scoring member, also in O(log N).
links_to_crawl (sorted set, score = priority)
https://en.wikipedia.org/wiki/Main_Page 0.97
https://www.bbc.com/news 0.95
https://example.com/about 0.31
crawled_links records what we have fetched, keyed by URL, with a second index on signature:
crawled_links (key-value, key = normalized URL)
url https://example.com/about
signature 9f2c41a07be3d655 # fingerprint of the page content
crawled_at 2026-10-12T08:14:03Z
next_crawl_at 2026-10-19T08:14:03Z
change_count 3 # recrawls that found new content
Relational or NoSQL? Every access is by one URL, there are no joins, and a billion rows must be split across machines, which suits a key-value store. See SQL or NoSQL.
For each URL, the crawler:
links_to_crawl.robots.txt allows it (see politeness).crawled_links for a page with the same or a very similar signature.
links_to_crawl with a lower priority, so the crawler doesn't keep returning to it. This also stops a cycle of links between copies from trapping the crawler.crawled_links.links_to_crawl.As a Python sketch, with storage hidden behind a small class:
import hashlib
import time
from urllib.parse import urljoin, urlsplit, urlunsplit
WEEK = 7 * 86_400
def normalize(url):
"""Make equal URLs compare equal: lowercase scheme and host,
drop default ports and #fragments."""
parts = urlsplit(url)
scheme = parts.scheme.lower()
host = (parts.hostname or "").lower()
if parts.port and parts.port != {"http": 80, "https": 443}.get(scheme):
host = f"{host}:{parts.port}"
return urlunsplit((scheme, host, parts.path or "/", parts.query, ""))
def signature(text):
"""Exact-content fingerprint. Near-duplicates need more (see below)."""
words = " ".join(text.lower().split())
return hashlib.sha256(words.encode()).hexdigest()[:16]
class LinkStore:
"""links_to_crawl in a Redis sorted set, crawled_links in a key-value store."""
def __init__(self, redis, kv):
self.redis, self.kv = redis, kv
def next_url(self):
popped = self.redis.zpopmax("links_to_crawl")
return popped[0][0] if popped else None
def add_if_new(self, url, priority):
if self.kv.get(url) is None:
# nx=True: never overwrite a URL that's already queued
self.redis.zadd("links_to_crawl", {url: priority}, nx=True)
def demote(self, url, priority=0.01):
self.redis.zadd("links_to_crawl", {url: priority})
def copy_of_another(self, url, sig):
other = self.kv.find_by_signature(sig) # URL stored with this signature
return other is not None and other != url
def record(self, url, sig):
now = time.time()
self.kv.put(url, {"signature": sig, "crawled_at": now,
"next_crawl_at": now + WEEK})
def crawl(store, fetcher, robots, index_queue, doc_queue, score):
while True:
url = store.next_url()
if url is None:
time.sleep(1) # frontier empty for now
continue
if not robots.allowed(url):
continue
page = fetcher.get(url) # waits for this host's turn
if page is None: # timeout, error, not HTML
continue
sig = signature(page.text)
if store.copy_of_another(url, sig):
store.demote(url) # a copy: don't index it again
continue
index_queue.put({"url": url, "text": page.text})
doc_queue.put({"url": url, "html": page.html})
store.record(url, sig)
for href in page.links:
link = normalize(urljoin(url, href))
store.add_if_new(link, score(link))
The loop checks for repeats at two moments:
add_if_new refuses URLs already queued or crawled. This is cheap and stops most cycles: when C links back to A, A is already in crawled_links.http:// and https:// versions, or an article with and without a tracking parameter.One production detail: ZPOPMAX removes the URL before it's fetched, so a crawler that crashes mid-fetch loses it. The fix is a lease. Move the URL to an "in progress" set with a deadline, and put it back if it isn't recorded in time, like a visibility timeout in a message queue.
The reverse index service reads its queue. For each page it splits the text into lowercase words and adds the page's ID to each word's list of pages, called a posting list:
"hello" -> [17, 42, 108, ...]
"world" -> [42, 99, 108, ...]
To answer hello world, it intersects the lists (pages 42 and 108), ranks the matches and returns the best. Updating posting lists one page at a time is slow, so real indexers batch pages into new index segments and merge them in the background. See the inverted index pipeline.
The document service reads its own queue. It takes the title from the HTML <title> element, and the snippet from the meta description or the first 160 or so characters of the main text, and stores them by page ID:
documents
doc_id 42
url https://foo.com
title foo's title
snippet foo's snippet: the first sentence or two of the page.
crawled_at 2026-10-12T08:14:03Z
Because snippets are static, all the work happens at crawl time, and a search only needs a lookup by ID.
There are two kinds of duplicates, and they need different tools.
The same URL arrives many times: from every page that links to it, from seed lists merged with discovered links, and from crawler restarts. Before a batch of URLs goes into the frontier, we remove repeats.
For a small list, sort -u urls.txt on one machine is enough. With 1 billion links we use MapReduce, a way to run a job over data spread across many machines. A map step turns each record into key-value pairs. The framework groups all pairs with the same key onto one machine (the shuffle). A reduce step combines each group into an output. The batch processing chapter explains the model.
Here the key is the normalized URL. Every copy of a URL lands in the same group, and the reducer writes it out once.
from collections import defaultdict
def map_urls(lines):
"""Map: emit (normalized URL, 1) for every line."""
for line in lines:
if line.strip():
yield normalize(line.strip()), 1
def shuffle(pairs):
"""What the framework does between map and reduce."""
groups = defaultdict(list)
for key, value in pairs:
groups[key].append(value)
return groups
def reduce_urls(groups):
"""Reduce: one output per distinct URL. The count is how often
the URL was linked, a useful signal for its priority."""
for url, ones in groups.items():
yield url, sum(ones)
lines = ["https://Example.com/a#top", "https://example.com/a", "https://example.com/b"]
print(dict(reduce_urls(shuffle(map_urls(lines)))))
# {'https://example.com/a': 2, 'https://example.com/b': 1}
Watch the reducer. A tempting version emits only URLs whose count is 1. That silently drops every URL that appears more than once, which is the opposite of what we want. Emit every key once, whatever its count.
Between batch runs, the crawler still needs a fast "seen this URL?" check for 77,000 links a second. A Bloom filter is a compact bit array that answers "definitely not seen" or "probably seen". At a 1% false-positive rate it needs about 9.6 bits per URL (−ln 0.01 ÷ (ln 2)² ≈ 4.6 ÷ 0.48), so 1,000,000,000 × 9.6 bits ≈ 1.2 GB, which fits in one machine's memory. The cost: about 1 new URL in 100 is wrongly reported as seen and skipped. The cache chapter uses a Bloom filter the same way.
An exact fingerprint, like the SHA-256 hash in the loop, only catches pages that match character for character. Two copies of an article that differ by a timestamp get completely different hashes. Such copies are common: Introduction to Information Retrieval notes that by some estimates as many as 40% of web pages duplicate other pages.
To catch near-duplicates, compare pages by similarity:
import hashlib
def shingles(text, k=4):
words = text.lower().split()
return {" ".join(words[i:i + k]) for i in range(max(1, len(words) - k + 1))}
def jaccard(a, b):
return len(a & b) / len(a | b) if (a or b) else 1.0
def minhash(shingle_set, num_hashes=200):
return [min(int.from_bytes(hashlib.blake2b(f"{seed}:{s}".encode(),
digest_size=8).digest(), "big")
for s in shingle_set)
for seed in range(num_hashes)]
def estimated_similarity(sketch_a, sketch_b):
return sum(x == y for x, y in zip(sketch_a, sketch_b)) / len(sketch_a)
The sketch is 200 numbers however long the page is, so it fits in crawled_links beside the signature. Cosine similarity is an alternative: it treats each page as a vector of word counts and measures the angle between two vectors, so it weighs how often words appear and ignores their order.
Large crawlers often use SimHash, which packs a page into one 64-bit fingerprint such that similar pages differ in only a few bits. The search engine chapter explains SimHash and how Google used it. With any of these, the loop's "seen similar content?" check becomes a search for fingerprints close to the new one.
Pages change, so they must be fetched again. Each row in crawled_links has a crawled_at timestamp. A simple policy: after a default period, say one week, every page is due again, and popular or frequently updated sites sooner. A scheduler finds rows whose next_crawl_at has passed and puts those URLs back in links_to_crawl.
A better policy learns each page's rate of change. Every recrawl tells us whether the signature changed, so over several visits we can estimate the mean time between changes and set the interval from it:
DAY = 86_400
MIN_INTERVAL, MAX_INTERVAL = 1 * DAY, 30 * DAY
def next_interval(previous, changed):
"""Recrawl sooner after a change, later after no change."""
interval = previous / 2 if changed else previous * 1.5
return max(MIN_INTERVAL, min(MAX_INTERVAL, interval))
It's tempting to recrawl every page in direct proportion to how often it changes. Cho and Garcia-Molina tested this on 270 web sites over four months, in Synchronizing a database to improve freshness (SIGMOD 2000). Revisiting every page at the same rate kept the copy fresher than revisiting in proportion to change rate, because a page that changes many times a day goes stale again almost at once. With their crawl budget and real change data, the predicted share of fresh pages was 0.12 for the proportional policy, 0.57 for the uniform one and 0.62 for their optimal one. Their conclusion: "to improve freshness, we should penalize the elements that change too often." That's why next_interval has a floor. A search engine may still revisit a popular, fast-changing page often, because a stale copy of an important page affects more users.
Two web standards make recrawling cheaper:
ETag or last-modified date from the previous fetch in an If-None-Match or If-Modified-Since header. An unchanged page comes back as 304 Not Modified with no body, saving the 500 KB download. Our storage estimate counted every refresh as a new page, so it's pessimistic.<lastmod> date for each. Google says it uses <lastmod> if it's consistently accurate, and ignores <changefreq> and <priority>. Site-reported dates help, but the crawler should check them against what it sees.Every fetch costs someone else's server some work, and to a small site a crawler sending hundreds of requests a second looks like an attack. Politeness has two parts: obeying the site's rules, and limiting the rate.
The Robots Exclusion Protocol lets a site tell crawlers which paths they may fetch. It was standardized as RFC 9309 in September 2022. The rules that shape our design:
/robots.txt at the top of the host, such as https://example.com/robots.txt. The file is split into groups that start with user-agent lines. A crawler uses the group matching its name, compared case-insensitively, and otherwise the * group.allow and disallow path rules. * matches any run of characters, and $ marks the end of the path. The most specific matching rule (the one with the most characters) wins, and allow should win a tie. If nothing matches, the URL is allowed.An example:
User-agent: *
Disallow: /search
Disallow: /*?sessionid=
Allow: /search/about$
Our crawler may fetch /news/today. It may not fetch /search?q=x or /cart?sessionid=abc. It may fetch /search/about, because that Allow rule is longer than Disallow: /search.
So the design needs a robots cache: parsed rules per host, with the time they were fetched. A host's robots.txt is fetched before any other URL on it and refreshed at most every 24 hours. Many URLs share a host, so Introduction to Information Retrieval finds such a cache still "highly effective".
Many files contain Crawl-delay: 10, asking for 10 seconds between requests. RFC 9309 doesn't define it, though it lets crawlers interpret extra records, and Google doesn't support crawl-delay. Our crawler can honor it as a minimum gap, but it can't rely on sites setting it.
So the crawler needs its own per-host limit. The textbook design, from the Mercator crawler and described in Introduction to Information Retrieval, has two rules:
The frontier implements this with two layers of queues. Front queues order URLs by priority. Each back queue holds URLs from a single host, and a heap orders hosts by the earliest time each may be contacted again. In our design, links_to_crawl plays the front queues, and each crawler keeps back queues and the heap in memory. The search engine chapter walks through this frontier.
The crawler should also back off when a site pushes back. A 429 Too Many Requests or 503 Service Unavailable means "too fast", and a Retry-After header says how long to wait. Google documents the same signal from the site's side: returning 500, 503 or 429 makes Googlebot slow down across the whole hostname.
Politeness changes the capacity math. At one request per host every 10 seconds, each host supplies at most 0.1 pages a second. To reach 1,540 pages a second, the crawler must work on at least 1,540 ÷ 0.1 = 15,400 hosts at once. That's why step 4 shards the crawler by host.
A crawler trap (or spider trap) is a set of URLs that never runs out. Introduction to Information Retrieval describes pages "that mislead crawlers into getting stuck fetching an infinite number of pages", and notes that many are accidents of "faulty website development". Google's URL structure guidelines list common causes:
/calendar?date=2026-10-20 links to 2026-10-21, and so on forever./docs/section/section/section/... if the server answers every path with a page instead of a 404.Some responses never end, such as an audio stream. Common Crawl truncates every fetch at 5 MiB for this reason.
Content checks catch some traps, but a calendar's pages really do differ. Add limits:
from urllib.parse import urlsplit
def looks_like_trap(url, max_len=2000, max_depth=15, max_repeats=3):
segments = [s for s in urlsplit(url).path.split("/") if s]
return (len(url) > max_len
or len(segments) > max_depth
or any(segments.count(s) > max_repeats for s in set(segments)))
Step 3 on the input <b>Helo</b> WORLD:
| Step | Result |
|---|---|
| Remove markup | Helo WORLD |
| Break into terms | Helo, WORLD |
| Fix typos | Hello, WORLD (the index knows "hello" is common and "helo" is rare) |
| Normalize capitalization | hello, world |
| Boolean form | hello AND world |
The public API is REST: a GET with the query in the URL.
$ curl "https://search.com/api/v1/search?query=hello+world"
{
"query": "hello world",
"results": [
{"title": "foo's title", "snippet": "foo's snippet", "link": "https://foo.com"},
{"title": "bar's title", "snippet": "bar's snippet", "link": "https://bar.com"},
{"title": "baz's title", "snippet": "baz's snippet", "link": "https://baz.com"}
],
"next_page": "/api/v1/search?query=hello+world&page=2"
}
Because it's a GET with everything in the URL, browsers, CDNs and our own cache can all cache it by the normalized query.
Between the Query API and the internal services, use RPC, such as gRPC. The calls are fixed functions ("find documents for these terms", "get documents by ID") between services we own, and compact binary messages over persistent connections save time on a path that must be fast.
Don't jump straight to the final design. Say that you would (1) benchmark and load-test, (2) profile to find bottlenecks, (3) fix them one at a time while weighing alternatives and trade-offs, and (4) repeat. Design a system that scales to millions of users shows that loop on a smaller system. Here, the step-1 numbers predict the bottlenecks:
| Number from step 1 | What breaks |
|---|---|
| 116,000 searches a second at peak | One web server, API server or index server can't take it. |
| 10 TB index, 500 GB of documents | The index doesn't fit in one machine's memory, so latency depends on disk. |
| Uneven, repetitive search traffic | Popular queries redo the same work thousands of times a second. |
| 3,100 open fetches across 15,400 hosts | One crawler machine runs out of connections, and DNS lookups pile up. |
| 77,000 new links a second | The frontier database takes a lookup and a write for every link. |
| 6.2 Gbit/s inbound, 2 PB a month | Network and storage must be sized for the crawl, not only for users. |
Users reach the service through DNS, which returns a load balancer's address. The load balancer spreads requests over many identical web servers. Adding copies of a stateless server is horizontal scaling, and it answers the 116,000-a-second peak. It costs more machines to run, and every server must stay stateless; see horizontal scaling and what it costs. Run the load balancers in pairs so they aren't a single point of failure.
The web servers act as reverse proxies: they terminate TLS, compress responses and forward requests to the Query API servers, a separate application layer. Splitting the layers lets the web layer scale with connections and the API layer scale with query work.
Some searches are very popular, and others run once. Serve popular ones from a memory cache such as Redis or Memcached, keyed by the normalized query. That cuts response time, keeps load off the reverse index and document services, and absorbs uneven traffic and spikes, such as a news event that sends millions of people to one search.
Memory is much faster than storage. In the widely shared latency numbers table, reading 1 MB sequentially takes about 250 µs from memory, 1 ms from an SSD (4 times as long) and 20 ms from a spinning disk (80 times as long).
Ten million cached result pages at 5 KB each come to 50 GB, which a small Redis cluster holds easily. How much traffic that absorbs depends on how skewed queries are, so measure the hit rate. Use cache-aside with a TTL of minutes to an hour, so results catch up with recrawls, and LRU eviction so rare queries fall out. When a very popular entry expires, thousands of requests can hit the index at once; cache stampede covers the fixes.
The reverse index service and document service need heavy use of sharding and federation to handle their data size and request load.
The cost is complexity. A query fans out to many shards and waits for the slowest, so tail latency matters, and resharding as the index grows takes planning.
links_to_crawl and crawled_links stay in a key-value NoSQL store, sharded by hash of the host name. All of a host's URLs then sit on one shard, which is what per-host politeness needs: the crawler that owns a shard enforces the rate for its hosts without asking anyone. The trade-off is skew, since a huge site makes its shard heavier. Place hosts with consistent hashing and split the largest out.
The 77,000 new links a second never hit the database directly. Each crawler's Bloom filter drops URLs it has seen, and the MapReduce job removes repeats from large URL lists before they're merged into the frontier.
These tables can be eventually consistent. If one crawler briefly misses that another just recorded a URL, the worst case is fetching a page twice, a small price for fast, available writes. See the consistency spectrum.
Accept-Encoding: gzip) reduce it.1. How to store the frontier? A Redis sorted set gives one priority order and is easy to explain, but knows nothing about hosts. The Mercator front and back queues handle priority and politeness together, with more machinery. A log such as Kafka is durable and fast but has no priority order. Start with the sorted set sharded by host, with per-host back queues as the politeness layer. See the crawl frontier.
2. Exact or approximate "seen URL" checks? A database lookup is exact but costs a read per link, 77,000 a second. A Bloom filter holds a billion URLs in 1.2 GB but skips about 1% of new URLs. Use the Bloom filter as the fast first pass, and confirm "probably seen" answers in the database if losing 1% of new pages matters.
3. Exact or near-duplicate content detection? SHA-256 is cheap and never wrong about identical pages, but misses a changed timestamp. MinHash or SimHash catch near-duplicates, with a threshold that will sometimes merge pages that really differ. Use the exact hash first, then a near-duplicate check before indexing.
4. How often to recrawl? A fixed weekly cycle is simple and predictable. Adaptive intervals spend the budget on pages that change. Cho and Garcia-Molina's results warn against recrawling purely in proportion to change rate. Use adaptive intervals with a floor and a ceiling, weighted by popularity.
5. Every version or only the latest? 72 PB versus 500 TB over three years. Unless the product needs page history, keep the latest copy plus the signature history, which is tiny.
6. Static or query-dependent snippets? Static snippets are cheap to serve and cache. Snippets that highlight the search words are more useful but need page text at query time. Start static, as required, and mention the upgrade.
7. How polite is polite enough? A stricter per-host rate protects sites but slows the crawl of large ones. The ten-times-the-fetch-time rule adapts by itself. Honor robots.txt, Crawl-delay, 429, 503 and Retry-After, then use sitemaps and conditional requests to spend a large site's budget on pages that changed. The rate limiting chapter covers the algorithms a per-host limiter can use.
Daily pages: 100,000,000 × 30 = 3,000,000,000 fetches a month. Weekly pages: 900,000,000 × 30 ÷ 7 ≈ 3,860,000,000. Together, about 6,860,000,000 fetches a month.
6,860,000,000 ÷ 2,592,000 s ≈ 2,650 fetches a second, up from 1,540. At 500 KB each, that's about 1.3 GB a second, or roughly 10.6 Gbit/s. With a 2-second fetch, Little's Law puts about 5,300 fetches in flight. Check politeness before agreeing, because popular pages cluster on a few large sites. Conditional requests matter too, since most daily refetches will return 304 Not Modified.
The crawler fell into a calendar trap. Each date page links to the next and previous dates with no end, and each day's page is slightly different, so the content checks didn't stop it.
Remove the site's queued URLs. Then add a per-host page budget scaled by popularity, so a small site can't flood the frontier, and URL limits on length, depth and repeated segments. Also check the site's robots.txt, since many sites disallow their calendars.
A 5xx status makes the file "unreachable", and the crawler must assume complete disallow: fetch nothing from that host, and keep retrying robots.txt. If it lasts a long time (the RFC's example is 30 days), the crawler may treat the file as unavailable or keep using a cached copy.
A 404 makes the file "unavailable", which means no restrictions. The crawler may fetch any URL on the host, still under its own per-host rate limit.
The reducer drops every URL that appeared two or more times. Popular URLs appear many times, because many pages link to them, so the job threw away most of the URLs that matter. Emit every key once, whatever its count. Keep the count, though: it's how often the URL was linked, which can feed its crawl priority.
No. 50,000,000 requests at one a second take 50,000,000 seconds, about 579 days for one pass.
Spend the budget where it counts. Use the site's sitemaps and <lastmod> dates to find changed pages, checking them since sites aren't always accurate. Send conditional requests so unchanged pages cost a 304 with no body. Prioritize by popularity and measured change rate, and accept that the long tail is refreshed rarely. It's also worth asking the site for a higher rate or a feed of changes.
With plain ZPOPMAX, every URL the machine had popped but not recorded is lost: it left links_to_crawl and never reached crawled_links. That's around a hundred URLs per crash.
With leases, popping moves a URL into an in-progress set with a deadline, and a sweeper returns expired ones to the frontier. The machine's host range goes to another crawler, which rebuilds its per-host queues from the frontier shard. Pages already queued for indexing are safe in the durable queues. A page may be fetched twice after a crash, so indexing must be idempotent: indexing the same URL and signature twice gives the same result.
robots.txt. Short, and it settles matching, error and caching questions.crawl-delay.304 Not Modified and Retry-After, which make recrawling cheaper and politer.links_to_crawl.Previous: Design a social media news feed (like Facebook, Instagram, or Twitter) · Next: Design a web search engine