Before Google can rank a page, it has to find it. That's the job of a web crawler (a spider or bot). “Design a web crawler” is a frequently reported question at Google and Amazon, and it's where BFS, hashing and a clever structure called a Bloom filter meet real-world manners: don't knock on the same door too often.
Step 1 · Requirements
- Functional: given seed URLs, download pages, extract links, and keep going; store page content for a search indexer; revisit pages to keep them fresh.
- Non-functional: polite (never overload a website, obey robots.txt); scalable to billions of pages; robust to broken HTML, slow servers and traps; avoid duplicates.
- Clarify: HTML only, or images and PDFs too? (Say HTML first.) How fresh must pages be?
Step 2 · Estimates
- Pages: 1 billion pages a month ≈ 1B ÷ (30 × 100,000 s) ≈ 400 pages per second, ~800 at peak.
- Storage: ~100 KB of HTML per page → 100 TB a month; compressed and kept for a few years, petabytes. Object storage, not a database.
- Seen set: tens of billions of URLs. A hash set would be terabytes; a Bloom filter with ~1% false positives needs about 10 bits per URL.
Step 3 · Interfaces
A crawler is mostly internal. The key contracts are what it reads and writes:
input: seed URLs (popular sites, sitemaps) + site rules from https://<host>/robots.txt
output: { url, fetchedAt, httpStatus, contentHash, html → object storage } → indexer queue
robots.txt example:
User-agent: *
Disallow: /admin
Crawl-delay: 2Step 4 · Design
🎮 Crawl a tiny web, one page at a time
URL frontier (queue)
- site.in/
Seen URLs (1)
site.in/
The frontier is a queue, so the crawl is breadth-first (BFS): nearby pages first. The seen-set stops loops (site.in/ links back to itself), robots.txt keeps out /admin, and the content check catches the ?ref=home copy.
The URL frontier: priority and politeness
- Priority: front queues rank URLs by importance (well-linked pages, homepages, pages that change often).
- Politeness: back queues hold one queue per host; a worker takes from a host only after its delay (e.g. 1–2 seconds, or the robots.txt Crawl-delay) has passed.
- Freshness: pages that change often (news) are re-queued sooner than ones that rarely change.
Have I seen this URL? A Bloom filter
A Bloom filter is a bit array plus a few hash functions. To add a URL, set the bits at its hash positions. To check one, look at those bits: any zero means definitely new; all ones means probably seen.
def fnv1a(text: str) -> int:
h = 2166136261
for b in text.encode():
h ^= b
h = (h * 16777619) & 0xFFFFFFFF
return h
class BloomFilter:
"""'Have I seen this URL?' in a few bits per URL. Never a false 'no'; rarely a false 'yes'."""
def __init__(self, size_bits: int = 10_000, hashes: int = 3):
self.size = size_bits
self.k = hashes
self.bits = bytearray(size_bits) # one byte per bit, for readability
def _positions(self, url: str):
return [fnv1a(f"{i}:{url}") % self.size for i in range(self.k)]
def add(self, url: str):
for p in self._positions(url):
self.bits[p] = 1
def might_contain(self, url: str) -> bool:
return all(self.bits[p] for p in self._positions(url))
seen = BloomFilter()
for url in ["https://example.com/", "https://example.com/about", "https://example.com/blog"]:
seen.add(url)
print(seen.might_contain("https://example.com/about")) # True -> skip, already crawled
print(seen.might_contain("https://example.com/contact")) # False -> definitely new, crawl it| Problem | Fix |
|---|---|
| Same page, many URLs (?ref=, #top, capital letters) | Normalise URLs before checking the seen set |
| Same content on different sites | Content checksum (exact) or SimHash (near-duplicates) |
| Spider traps (endless calendars, session IDs) | Max depth, max URL length, max pages per site |
| Slow or dead servers | Timeouts, retries with backoff, skip hosts that keep failing |
| DNS lookups are slow | Cache DNS answers per host |
Step 5 · Scale and reliability
- Distribute by host: hash the host name to choose a crawler machine, so each site's politeness queue lives on exactly one machine (that's consistent hashing again).
- Async fetching: most time is spent waiting on the network, so each machine keeps thousands of downloads in flight with non-blocking I/O.
- Checkpoint the frontier: persist it to disk or a durable queue so a crash doesn't restart a month-long crawl.
- Geography: run crawlers in several regions so each fetches nearby sites faster.
- Hand-off: after storing a page, put its ID on a queue for the indexer (search) or other consumers.
🧠 PATH memory card
Remember the web crawler design for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
A census volunteer walks a city with a list of addresses. They knock politely (and skip houses with a 'No visitors' sign), write down any new streets they discover, and tick off every house visited so they never knock twice. Nearby streets first, then further out.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Frontier, Fetch, Parse, Filter, and back to the Frontier”
- Address list→URL frontier: priority + one queue per host
- Knock politely→robots.txt rules and a delay per host
- Nearby first→Queue = BFS order
- Note new streets→Parse HTML, extract and normalise links
- Tick visited→Bloom filter for seen URLs; checksums for duplicate content
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Frontier: [site.in/]. Fetch it → links /courses, /about, /admin → none seen → frontier [/courses, /about, /admin]. Fetch /courses → its link back to site.in/ is already ticked, skip. /admin → robots.txt Disallow, skip without fetching. Later /courses/ai?ref=home → normalised or caught by the content checksum as a duplicate. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 8 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Follow-up questions interviewers ask
- “JavaScript-heavy pages?” Some pages need a headless browser to render. It's much more expensive, so do it only for important pages.
- “How do you recrawl?” Track how often each page changes; schedule frequent changers more often. Sitemaps with last-modified dates help.
- “Ethics?” Identify your bot in the User-Agent, obey robots.txt, rate-limit, and honour removal requests.
Where to go next
Crawlers move text. Video is a thousand times heavier. Next, the system that streams it smoothly even on a weak mobile network: design YouTube or Netflix.
Key takeaways
- ✓The loop: frontier → fetch → parse → filter → frontier, starting from seed URLs.
- ✓The frontier handles priority and politeness: one queue per host, delays, robots.txt.
- ✓A FIFO frontier gives breadth-first crawling.
- ✓Bloom filters track billions of seen URLs cheaply; checksums or SimHash catch duplicate content.
- ✓Distribute by host hash, fetch asynchronously, checkpoint the frontier, and guard against traps.
Frequently asked questions
How does a web crawler work?
A crawler starts from a list of seed URLs. It repeatedly takes a URL from a queue called the URL frontier, checks the site's robots.txt rules, downloads the page, stores it, extracts the links, and adds links it hasn't seen before back to the frontier. Repeating this loop across thousands of machines lets search engines discover and refresh billions of pages.
What is a URL frontier?
The URL frontier is the crawler's to-do list. It is more than a simple queue: it ranks URLs by priority (important or frequently changing pages first) and enforces politeness by keeping one queue per website and waiting between requests to the same host, so the crawler never overloads a single server.
What is robots.txt?
robots.txt is a plain text file at the root of a website (example.com/robots.txt) that tells crawlers which paths they may or may not fetch, and sometimes how long to wait between requests. Well-behaved crawlers download and cache it for each site and follow its rules.
Why does a web crawler use a Bloom filter?
A crawler must check whether it has already seen each of billions of URLs. Storing them all in a hash set would take a lot of memory. A Bloom filter answers 'have I seen this?' using a few bits per URL. It never wrongly says 'no', but occasionally wrongly says 'yes', which just means a page is skipped, an acceptable trade-off for a crawler.
How does a crawler detect duplicate pages?
Many URLs show the same content (tracking parameters, mirrors, printer versions). The crawler normalises URLs (lowercase host, remove fragments and tracking parameters) and computes a fingerprint of each page's content. Exact duplicates share a checksum; near-duplicates can be found with techniques like SimHash, which gives similar pages similar fingerprints.
🧠 Quick check: web crawler
1. The URL frontier is a FIFO queue. What order does the crawl follow?
2. Your crawler sends 500 requests per second to one small website. What's wrong?
3. A Bloom filter says a URL “might be seen”, but it actually wasn't. What happens?
4. A calendar page links to “next month” forever. What is this?
Checking your access…