SwadhyAI Notes

All System Design notes

System Design Case Study

Design a web crawler

Before someone types a query into Google Search, crawlers have already walked the web: fetching pages, extracting links, and deciding what to fetch next. To the search product it feels like the web is “already known.” Under the hood it is a polite automated browser at huge scale.

The hard part is not HTTP GET. It is choosing the next URL without duplicates, traps, or melting the sites you visit, while still staying fresh enough for ranking.

Basic crawl loop

1

Priority + per-host fairness.

2

Allow/Disallow + crawl-delay.

3

Fetch + parse

HTTP get, extract links, normalize.

4

URL seen? Content near-dup?

Try it: crawl frontier and politeness

The frontier queues URLs per host. Politeness delays and robots rules bound how fast each host is fetched.

  1. Frontier
  2. DNS
  3. Fetcher
  4. Parser
  5. Index queue
Highlighted hops show where the last action moved traffic. A stopped hop means backpressure, rejection, or a consistency guard blocked further progress on that path.
Fetched
0
Deferred
0
Mode
polite
Path hop
0

Frontier

per host

0 fetches, 0 deferred.

Politeness

delay

Host budgets prevent ban-worthy bursts.

Dedup

URL

Canonicalization and content fingerprints avoid recrawling duplicates.

Crawl politely first, then try aggressive mode to force host deferrals.

What actually happens

Seed URLs enter the . A fetcher pulls a URL only after rules say that host is ready: cached , , and per-host concurrency limits. Recheck those permissions at dispatch because a URL may have waited for hours and the cached policy may have changed. Treat host scheduling and URL priority as separate concerns: a valuable URL does not entitle the crawler to exceed the host’s budget. Keep redirects under the same destination validation and pacing rules instead of allowing them to bypass the frontier.

DNS resolves (ideally from cache), HTTP fetches the page, the parser extracts links and text, and new URLs are normalized. A (plus exact store for positives) answers “URL already seen?” catches near-duplicate content under different URLs. Surviving links go back into the frontier.

Raw HTML lands in object storage; parsed metadata feeds indexing or monitoring. Checkpoints keep the frontier recoverable when workers die.

How to choose crawl trade-offs

1. Coverage or freshness? Broad crawl budgets discover new sites; important and fast-changing pages get denser recrawl schedules.

2. Politeness or throughput? Never “fix” delay by hammering one host. Scale by keeping many hosts ready in parallel behind a .

3. Exact or approximate dedup? Use Bloom for URL seen-checks at billion scale; confirm high-value positives. Use SimHash/MinHash for near-duplicate content.

Simple rule of thumb

Tell the story as a loop: frontier → robots → fetch → parse → dedupe → enqueue. Everything else exists to keep that loop polite, fault-tolerant, and fresh at scale.

In simple terms: fetching pages is easy; scheduling the next fetch without overloading sites is the system design.

Case-study upgrade

Crawler Frontier Math

A web crawler is mainly a frontier and politeness system. Fetchers are workers; the frontier decides what can be fetched next.

Assumptions and formulas

  • Target: 1B pages/week. Average page size: 500 KB. Parse CPU: 50 ms/page.
  • Pending discovered URLs can be much larger than pages fetched today.
  • Per-host politeness limits request rate to avoid overloading origin sites.

Concrete math

  • 1B pages/week = 1,653 pages/sec average. At 500 KB/page, this is 826 MB/sec or 71 TB/day raw.
  • Parser workers: 1,653 pages/sec x 50 ms CPU = about 83 CPU cores average; add 3x peak and headroom.
  • Frontier: 10B pending URLs x 100 bytes hash/metadata = 1 TB raw before full URL logs.
  • Bloom filter: 10B URLs x 10 bits/item = 12.5 GB for one duplicate-check filter.
  • Politeness: 1 request/sec/host means 1,600 pages/sec requires at least 1,600 active hosts at that moment.

Design decisions forced by numbers

  • Separate priority frontier queues from per-host politeness queues.
  • Store canonical URL hashes for fast dedup and compressed URL logs for audit/debug.
  • Timeouts, backoff, and trap detection matter more than raw fetcher count.

Scaling to millions

  • At 1M pages: one scheduler and fetcher pool are enough.
  • At 100M pages: partition frontier, cache DNS, and separate parsing from fetching.
  • At billions of URLs: shard by host/domain, tier freshness, and schedule recrawls by importance.

Readable flow

Priority frontier
Host queue
Fetcher
Parser
Dedup
Storage/index

Interview follow-ups to expect

  • How is politeness enforced per host?
  • How large can the frontier become?
  • How do we avoid crawler traps and duplicate pages?

Operational readiness checklist

After the math, explain how this capacity plan is measured, protected, launched, and evolved.

Observability

  • Attach each capacity estimate to a dashboard metric: p99 latency, queue age, cache hit rate, shard skew, error rate, and freshness lag.
  • Alert on rate-of-change and saturation, not only hard failures; backlogs and hot keys usually warn before an outage.

Security and abuse

  • Budget for auth checks, rate limits, quota isolation, audit logging, privacy filters, and abuse-review side paths.
  • Separate trusted internal events from user-controlled input so retries and backfills cannot bypass policy checks.

Degraded modes

  • Define the fallback when a dependency is slow: stale cache, partial results, read-only mode, delayed async work, or admission control.
  • Protect the invariant first; reduce freshness, personalization, or analytics quality before risking duplicate or corrupt state.

Testing and rollout

  • Test average, peak, and hot-object traffic; include retry storms, cold caches, lagging workers, and regional dependency loss.
  • Use canaries, shadow reads, dual-write validation, feature flags, and explicit rollback criteria for risky path changes.

Rollout, backfill, and runbooks

  • Make migrations and backfills idempotent, resumable, rate-limited, and visible through progress and error metrics.
  • Write the runbook before launch: owner, dashboards, paging thresholds, mitigation switches, replay steps, and repair commands.

10x evolution

  • For crawler frontier math, state which number forces the next move: cache memory, shard count, write amplification, queue lag, egress, or failover reserve.
  • Add the next layer only when the metric forces it: sharding, regional reads, async replay, hot-key isolation, or stricter backpressure.

Scope you should nail down

Functional

  • Crawl billions of pages from seeds via extracted links
  • Respect standard robots.txt rules and a separate per-host pacing policy; optionally support the crawl-delay extension
  • Handle duplicate URLs and near-duplicate content
  • Prioritize important pages (PageRank, freshness)
  • Store raw HTML and parsed content for indexing

Non-functional

  • 1B pages/week ≈ 1,600 pages/sec
  • Politeness: rate limit per domain
  • Fault tolerant: checkpoint and recovery
  • Robust against bad HTML, slow hosts, traps
  • Extensible to new content types later

Search indexing

Broad coverage, freshness, link graph, extraction, downstream ranking.

Web archiving

Preserve raw snapshots for years; completeness over instant indexing.

Web mining

Target domains and entities; extraction quality over crawling everything.

Monitoring

Detect changes, spam, or policy issues with recrawl schedules and alerts.

Questions to ask early

Purpose? Search, archive, mining, monitoring, or site-specific?

Scale? Pages/month, page size, peak fetch rate, retention.

Content type? HTML now; design plugins for PDF/images later.

Freshness? New and edited pages need recrawl policy, not only discovery.

Capacity picture

1,600/s
Pages/sec
800 MB/s
Bandwidth (~70 TB/d)
~100-150 TB
Storage/week (compressed)
1,600
Concurrent fetchers

Alternate interview estimate

If the interviewer gives 1B pages/month and 500 KB/page, average throughput is roughly 400 pages/sec, peak about 800 pages/sec, storage about 500 TB/month, and five-year raw retention about 30 PB before compression and deduplication.

Frontier operations at scale

Capacity formulas and SLOs

1B pages/week ≈ 1,653 pages/sec. At 500KB/page, ingress is about 826MB/sec or 71TB/day raw. Parser CPU at 50ms/page needs about 83 cores average before 3× peak headroom. Track freshness SLOs separately from crawl volume.

Metrics and degraded modes

Watch frontier age, host starvation, robots rejection rate, DNS p99, fetch success, duplicate ratio, parser failures, and stale important pages. If indexing lags, keep fetching within budget and buffer raw results by crawl date.

Security and abuse controls

Enforce robots rules, identify the crawler user-agent, cap redirects, block internal IP ranges, limit page size and decompression ratio, and treat malicious HTML or traps as expected inputs.

Rollout and 10× growth

Replay frontier logs into a shadow scheduler, canary parser changes by host group, and at 10× shard frontier state by host hash with regional fetcher pools.

Hard part: versus throughput

If per-host delay is 1 request/sec and the target is 1,600 pages/sec, keep at least 1,600 active hosts ready. Slow hosts get backoff and must not occupy all fetchers; priority queues choose valuable URLs while host queues enforce fairness.

APIs worth sketching

typescript
addSeed(url)
// Add URL(s) to crawl frontier. Initial seeds for crawl.

getCrawlStatus()
// Returns: pages_crawled, queue_size, rate, errors

pauseCrawl()
// Gracefully pause; save frontier state.

resumeCrawl()
// Resume from checkpoint.

Seeds and traversal

Seed selection

For a site crawl, seed with the site's home page and sitemap. For broad web crawling, seed by geography, language, topic, known high-quality domains, public directories, and previously discovered high-value pages.

BFS vs DFS

DFS can fall into deep paths and traps. BFS is the usual starting point, but production crawlers add priority and politeness so one host or one low-quality branch does not dominate the frontier.

Architecture: the crawl pipeline

URLs flow through frontier, DNS, fetcher, parser, deduplicator, and back to the frontier. Each stage scales independently.

URL Frontier (Priority + Back Queues)
↓
DNS Resolver (with cache)
↓
Fetcher (HTTP)
↓
Content Parser
↓
Duplicate DetectorURL Extractor
↓
URL Frontier (loop)

Datastore | Politeness (robots.txt, crawl-delay)

(the critical piece)

Two-level queue

Front queues prioritize useful and timely URLs. Back queues group eligible work by host and expose it only when that host may be fetched again. The scheduler chooses among ready hosts, then selects useful work inside one host. Persist in-flight reservations so a worker crash can release its claim without having two replacements unknowingly exceed the host’s concurrency budget.

Front queue: priority

Priority by PageRank (precomputed or estimated), freshness (sitemap lastmod), and seed importance. Heap or multiple FIFO queues per priority. Fetchers pull from the highest non-empty priority.

When a fetcher needs work, pick a host whose crawl-delay has elapsed. Round-robin across ready hosts so one site cannot dominate.

javascript
// Structure
front_queue: { priority_0: [urls], priority_1: [urls], ... }
back_queue: { host_a: [urls], host_b: [urls], ... }
last_fetch_time: { host_a: timestamp, host_b: timestamp, ... }

// Fetcher picks URL:
host = pick_host_with_elapsed_delay(back_queue, last_fetch_time)
url = back_queue[host].pop()
url = front_queue.get_next()
back_queue[host].push(url)

Frontier storage and freshness

Hybrid storage

  • Memory buffers for active front/back queues
  • Disk or log-backed queue for hundreds of millions of waiting URLs
  • Periodic flush so worker crashes do not lose frontier state

Freshness policy

  • Recrawl important or frequently changing pages sooner
  • Use sitemap lastmod, HTTP cache headers, and historical update frequency
  • Track average freshness and stale important pages as first-class metrics

Fetcher and DNS

Distributed HTTP fetchers

Worker pool; each fetches one URL (or a small batch per host). Connection pooling, keep-alive, 10–30s timeouts, explicit User-Agent. Retry with exponential backoff (max ~3). Follow 301/302 carefully; extract links from HTML only.

DNS resolution

  • DNS cache: host → IP with TTL: a major bottleneck otherwise
  • Async DNS: resolve before fetch; overlap I/O
  • Prefetch: resolve when a URL is extracted so IP may be warm at fetch time

Scale fetchers horizontally

Partition URL space by host hash so fetcher groups can be added with limited movement. Keep fetchers stateless; persist reservations in the frontier/checkpoint layer.

Fail fast on bad hosts

Short connect/read timeouts, retry budgets, circuit breakers per host, and exponential backoff prevent slow sites from occupying threads forever.

Content processing and URL filtering

Normalize only transformations whose semantics are understood: resolve relative references, normalize host casing, and remove fragments that are not sent in ordinary HTTP requests. Preserve path case and query values unless a site-specific rule proves they are equivalent. Removing every query string can merge distinct pages, while keeping tracking parameters forever can create many duplicate URLs. Store both fetched and canonical forms to explain deduplication decisions.

plaintext
// URL normalization
https://Example.COM:443/path?q=1  → https://example.com/path?q=1
http://a.com/b/../c                → http://a.com/c
https://a.com/page#section         → https://a.com/page

URL filter

  • Drop blacklisted hosts, logout URLs, unwanted extensions, obvious traps
  • Reject non-HTML when scope is HTML-only

URL seen?

Canonicalized URL hashes, Bloom filters, and an exact store for high-value positives.

Content seen?

An exact content hash identifies byte-identical or deliberately normalized content, depending on what was hashed. It cannot by itself recognize near-duplicates whose navigation or one sentence differs. Use similarity fingerprints for that separate task and choose a threshold that avoids merging genuinely different pages. Retain enough provenance to associate identical content with multiple URLs when links, timestamps, or source identity still matter.

Duplicate detection

URL dedup:

A correctly maintained standard Bloom filter can say definitely absent or possibly present. At ten bits per inserted URL, one billion entries require about 1.25 GB before metadata, with a false-positive rate that depends on hash count and occupancy. Confirm positives in an exact store when missing a new page is unacceptable. A lost or stale filter can behave differently from the ideal model, so checkpoint it or rebuild from durable seen-URL records.

Content dedup: / MinHash

Near-duplicate pages (same article, different URL). SimHash gives a 64-bit fingerprint; MinHash estimates Jaccard similarity of shingles. LSH for fast lookup.

python
// SimHash (simplified)
shingles = tokenize(content, k=3)
hash_bits = [0] * 64
for shingle in shingles:
  h = hash(shingle)
  for i in 64:
    hash_bits[i] += 1 if (h >> i) & 1 else -1
simhash = sum(1 << i for i in 64 if hash_bits[i] > 0)
// Similar content → Hamming distance(simhash_a, simhash_b) small

and

Robots.txt cache

Fetch robots.txt for the relevant origin and select the rules for the crawler’s user-agent. Cache and refresh it under the Robots Exclusion Protocol’s rules, including distinct behavior for unavailable versus unreachable responses. Check permission again before a queued fetch. Robots rules express crawl access preferences; they do not grant authentication or make private network endpoints safe to fetch.

Apply a configurable per-host pacing policy even when robots.txt has no timing directive. Crawl-delay is a non-standard extension whose support and syntax vary; do not present it as part of RFC 9309. If the crawler supports it, combine it with conservative defaults, observed response time, retry backoff, and overload signals. Throughput grows by fetching many eligible hosts concurrently, not by ignoring a slow host’s limit.

Trap detection

Spider traps

Infinite URL spaces: calendars, session IDs, mirrors. Detect with URL patterns, max URLs per host, and max depth.

Mitigations

Max depth from seed (for example 5 hops). Max URLs per host (for example 10K). Limit numeric-only URL variants. Prefer shorter canonical URLs.

Checkpoint, recovery, and datastore

A checkpoint records queued URLs, host scheduling state, and in-flight reservations at a consistent position in the frontier log. After restart, replay changes after that point and reclaim expired work. A fetch may have completed just before its acknowledgement was lost, so the output and seen-URL state need duplicate-safe handling. Periodic snapshots alone lose enqueue progress since the last snapshot unless an additional durable log preserves it.

json
// Checkpoint contents
{
  "front_queue": [...],
  "back_queues": { "host": [...] },
  "last_fetch": { "host": timestamp },
  "crawl_count": 123456789,
  "timestamp": 1640000000
}

Store raw HTML in object storage keyed by URL hash. Store parsed title/text/links in a DB or search index. Keep the crawl loop async from indexing. Compress HTML; segment by crawl date for cold archival. Metadata (status, content-type, fetch time) drives recrawl decisions.

Extensibility, dynamic pages, and quality

Plugin pipeline

Keep downloader, parser, link extractor, and post-processors modular so PDF or image modules do not rewrite the frontier.

Dynamic rendering

Use a separate headless-rendering tier only for pages that need it: browser rendering is far more expensive than raw HTML fetch.

Spam and low-value pages

Filter thin content, infinite faceted search spaces, malware, and known spam domains so finite budget goes to useful pages.

Data layer scale

Shard metadata by URL hash or host, replicate raw storage, and keep fetchers stateless so scaling is mostly more workers and queue partitions.

Bottlenecks

DNS resolution

Slow DNS = slow crawl. Aggressive cache, async prefetch, local resolver.

Politeness vs throughput

Crawl-delay limits one host. Crawl many hosts in parallel; scale fetchers horizontally.

Frontier bottleneck

Single queue = contention. Shard by host; use distributed durable queues.

Storage I/O

Hundreds of TB/week. Compress, batch writes, object storage, hot/cold tiers.

Bloom false positives

May reject new URLs. Tune FP rate (~0.1%); confirm positives in DB.

Review the design

URL Frontier: front queue (priority) + back queue (one per host). Politeness enforces crawl-delay.

Fetcher: distributed workers, pooling, retry with backoff, User-Agent, timeouts.

DNS: cache and async prefetch because lookup latency dominates throughput.

Robustness: stateless workers, checkpointed queues, validation, short timeouts, per-host budgets.

Freshness: recrawl important and frequently changing pages sooner.

Duplicate: Bloom filter for URL dedup; SimHash/MinHash for near-duplicate content.

Filtering: drop unwanted extensions, spam, malformed pages, and traps before they waste budget.

Robots.txt: cache per origin, honor Allow/Disallow rules, and apply the separately defined pacing policy and any supported crawl-delay extension.

Extensibility: add parser/downloader modules without rewriting the frontier.

Recovery: checkpoint frontier state and resume cleanly after failure.

Compare a starting answer with a more complete design

A starting answer

Use a URL frontier, fetchers, robots.txt checks, parsers, deduplication, and a document store.

Developing the reasoning

Explain priority versus politeness queues, per-host crawl budgets, DNS caching, spider-trap detection, SimHash near-duplicate detection, and frontier checkpointing.

Deeper walkthrough

Web crawler deeper walkthrough

A crawler is mostly a scheduler. Fetching pages is easy; choosing what to fetch next without overloading sites is the real system design problem.

Requirement refinements

Clarify crawl goal: broad coverage, freshness for important pages, site-specific crawling, or search-engine scale.

State politeness requirements: robots.txt, crawl-delay, per-host concurrency, and retry backoff.

API design details

Represent frontier operations explicitly: enqueue URL, reserve next URL for host, mark fetch result, and checkpoint progress.

Store fetch metadata such as status code, content hash, canonical URL, robots decision, and discovered links.

Data model and storage

Use URL canonicalization plus Bloom filter for URL dedup, and SimHash or content hashes for document dedup.

Keep host-level crawl state separate from URL priority so politeness can be enforced independently.

Scaling strategy

Shard frontier by host hash or URL hash while preserving per-host ordering and concurrency limits.

Use DNS cache, connection reuse, and fetcher pools, but cap fetch rate per host and per IP block.

Reliability, recovery, and operations

Checkpoint frontier state so worker crashes do not lose reserved URLs forever.

Monitor frontier size, duplicate ratio, fetch success rate, robots rejection rate, parser failures, and average freshness.

Deepening reference

Web Crawler: realistic production notes

Beginner mental model: A crawler is a scheduler plus fetchers plus duplicate detection plus politeness enforcement.

Production scope: Real crawlers optimize freshness, coverage, and quality while avoiding harm to websites. The URL frontier is the core data structure.

Choose what the first version must guarantee

Start by deciding which web crawler capabilities are essential. Describe the main read and write operations before choosing infrastructure. For each operation, identify the stored records it uses and the condition that makes its result correct. A fast response is useful only if it satisfies that condition.

Next, separate work the user must wait for from work that can finish later. Estimate requests per second, storage growth, and the busiest object or customer. Use those estimates to choose one bottleneck to investigate. The calculations below are example workloads with stated assumptions; they are not measured limits of a particular product.

Core flow to walk through

1

Discover URL from seed, sitemap, or parsed page.

2

Canonicalize and dedup URL, score priority, place into host-aware frontier.

3

Fetch with robots/politeness checks, parse content, store document, enqueue links.

Production readiness

Web Crawler: ship, operate, and evolve

Now examine the same request flow during failures and deployments. Tie each operational control to the user behavior it protects.

Observability

Track web crawler p95/p99 latency, error rate, saturation, and user-visible freshness separately for read, write, and async paths.

Alert on leading indicators such as queue age, hot-key skew, cache miss storms, reconciliation mismatches, and error-budget burn.

Security and abuse

Enforce authentication, authorization, rate limits, input validation, audit trails, and privacy checks at the service boundary.

Treat abuse controls as a first-class path: throttling, quota isolation, moderation hooks, revocation, and safe handling of sensitive data.

Degraded modes

Name what still works if cache, search, ranking, stream processing, object storage, or a regional dependency is slow.

Prefer stale-but-safe reads, partial results, async retry, admission control, and feature disablement over corrupting core state.

Testing and rollout

Load test average, peak, and hot-object traffic; add failure-injection for retries, timeouts, backlog growth, and dependency outages.

Ship with canaries, shadow reads or dual writes when useful, rollback switches, schema compatibility checks, and replay validation.

Runbooks

Document dashboards, paging thresholds, owner actions, rollback steps, data repair commands, and customer-impact language.

Keep backfills and replays idempotent, resumable, rate-limited, and observable so repair work does not create a second incident.

10x evolution

Say which metric forces the next architecture change: shard count, cache footprint, write amplification, queue lag, p99 latency, or regional failover reserve.

Evolve one bottleneck at a time: partition by access pattern, isolate hot tenants, regionalize reads, add replayable async pipelines, then harden multi-region behavior.

Hard parts worth deepening

Use separate priority and per-host queues to balance importance and politeness.

Robots.txt and crawl-delay are correctness requirements, not optional features.

Detect exact duplicate URLs and near-duplicate content separately.

Checkpoint frontier state for restart without losing crawl progress.

Failure modes and recovery

Spider trap creates infinite URLs; cap depth, host budget, and URL pattern expansion.

DNS failures slow fetchers; cache DNS and retry with backoff.

One host dominates frontier; enforce per-host quotas and fairness.

Content parser crashes on malformed pages; isolate parser workers and dead-letter bad pages.

Signals to monitor

Fetch success rate measures completed downloads, while robots-policy rejection counts show intentional skips. Keep policy decisions separate from network errors so a responsible crawler is not reported as broken.

Frontier size measures queued URLs but oldest queued age is needed to understand waiting time. Duplicate ratio shows wasted discoveries, and freshness by host reveals sites whose documents are aging even when total throughput looks healthy.

ChoiceBest whenCost
Freshness priorityNews or fast-changing sites matter.Less coverage of long-tail pages.
Coverage priorityYou want broad index growth.Staler important pages.
Bloom filter dedupMassive URL scale needs compact memory.False positives can skip some URLs.

Try this scenario

Explain how your crawler avoids overwhelming a small website while still crawling a large news site quickly.

Primary sources

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Operate a canonicalized, SSRF-safe, polite URL frontier with robots policy, host fairness, dedup, recrawl scheduling, rendering budgets, and freshness SLOs.

Explain the decision

Why is URL canonicalization a correctness problem?

Read the reasoning

Equivalent URLs can create infinite duplicate work, while overly aggressive normalization can merge distinct resources; rules need versioning and evidence.

Apply it to a production scenario

A crawled hostname resolves to 169.254.169.254 after redirect. What happens?

Read one approach

Re-resolve and validate every hop, block private/link-local/metadata ranges, isolate fetchers, cap redirects, and record the security rejection.

Work through the numbers

One billion pages averaging 400 KiB recrawled every 30 days require what average payload bandwidth?

Read the worked calculation

About 154 MB/s average, before images, headers, retries, compression differences, and peak/headroom.

Reason through a failure

What must frontier scheduling preserve?

Read the recovery reasoning

No host can monopolize workers, robots/crawl-delay policy is respected, and retries remain bounded and persistent across restarts.

Sources and further study

Continue with Design Typeahead/Autocomplete.