System design deep dive · HLD
Design a distributed web crawler (Googlebot-scale): full high-level design.
Requirements, back-of-envelope capacity estimation for a 20-billion-page corpus, a high-level design diagram, a domain-hash-sharded deployment architecture, sequence diagrams for the polite fetch path and the robots/failure path, and an entity-relationship diagram for the frontier and page-store schema - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
A crawler design question hides most of its difficulty in one word: politeness. Before any diagram, separate what the system must do from how carefully it must behave toward the sites it crawls, and pin down the scale assumption - billions of pages - that every later number depends on.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers decide the shape of everything below: how many logical queues the frontier needs, whether an exact "seen" set fits in memory, and how much raw storage the page store needs to provision for.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Pages in corpus (target) | 20 billion pages, recrawled on a 1-60 day cycle by importance | Anchors every other row below |
| Distinct domains | ~200 million active domains, ~100 pages/domain average | 200M × 100 = 20B pages - consistent with the corpus target |
| Fetch throughput | ~1 billion fetches/month (new discovery + recrawl) | 1e9 / 2,592,000s ≈ 386 pages/sec avg, ≈2,500/sec peak |
| Raw HTML storage | 500KB avg page (HTML only, images/video excluded), latest + 1 prior version kept for diffing | 20B × 500KB × 2 ≈ 20 PB |
| Bloom filter dedup set | 20 billion URLs tracked, 1% target false-positive rate | ~9.6 bits/URL × 20B ≈ 192B bits ≈ 24 GB - fits in RAM across a handful of nodes |
| Default politeness delay | 1 request/domain/sec baseline (overridden by a site's own robots.txt) | Caps any single huge domain at ~86,400 pages/day, no matter how many workers exist |
3. High-level design (HLD)
The HLD names the major components and the (cyclic, not one-directional) data flow between them - a crawler is a loop, not a pipeline, since every fetch can produce new work for the frontier - without committing yet to shard counts or regions.
What each box owns
URL Frontier
A logically-per-domain set of priority queues: each domain gets its own queue so one huge domain's backlog can never starve a small one. Priority is a function of freshness need and page importance, not simple FIFO/BFS order. Back-pressure caps how many URLs any one domain can have outstanding at once.
Politeness manager and DNS resolver
Before any fetch, the worker asks the politeness manager for that domain's cached robots.txt rules and the elapsed time since the domain's last fetch; if crawl-delay hasn't elapsed, the URL goes back on the queue instead of being fetched early. The DNS resolver caches host-to-IP lookups per domain so repeated fetches to the same host skip a full resolution round trip.
Fetch workers (sharded by domain hash)
A large, horizontally-scaled fleet that does the actual HTTP GET. Workers are assigned to domains via a consistent hash of the hostname, so every request for a given domain always lands on the same worker/queue partition - this is what makes politeness enforceable even with hundreds of workers running concurrently.
Content parser, Bloom filter, and page store
The parser extracts outbound links and readable text from fetched HTML. Every extracted link is checked against the Bloom filter before being considered "new" - a cheap, probabilistic, shared/replicated check that avoids re-queuing URLs the crawl has already visited. Raw HTML is written to a durable blob store keyed by URL hash, which the (out-of-scope) indexing pipeline reads independently.
4. Detailed architecture diagram
The architecture diagram answers "how is politeness actually enforced at hundreds-of-workers scale?" - the single hardest constraint in this system - plus how the frontier, the Bloom filter, and the page store are physically sharded and replicated.
| Decision | Choice | Reasoning |
|---|---|---|
| Frontier ordering | Priority-based, not plain BFS | BFS treats every page equally; a priority score (importance × freshness need) means a news homepage gets recrawled hourly while a stale personal blog waits weeks, which matters far more at 20B pages than crawl order alone. |
| Queue partitioning | Per-domain queue, sharded by consistent hash of hostname | Guarantees every request to a given domain is serialized through one owner, so crawl-delay is enforced correctly no matter how many total workers exist - a global shared queue cannot make this guarantee without a distributed lock per domain. |
| Dedup storage | Bloom filter over an exact hash set | An exact set of 20B+ URLs (avg ~60 bytes/URL) would need hundreds of GB to TB of storage; the Bloom filter's ~24GB fits in memory and its false positives (occasionally skipping a genuinely new URL) are an acceptable, bounded cost versus that storage bill. |
| Huge-domain handling | Sub-partition a single domain's queue further | A domain with millions of pages (e.g. a large e-commerce catalog) would otherwise dominate its shard's queue; splitting it by URL-path prefix keeps its crawl-delay guarantee while still making forward progress across the rest of the shard. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether politeness is actually enforced in the right order, and whether failure and disallow paths are handled distinctly from the happy path.
5.1 Fetching a URL while respecting politeness
Step 5 happens entirely inside the fetch worker and touches no network call - the crawl-delay check is a local clock comparison, which is why it doesn't slow the loop down. Steps 11 and 12 are drawn as dashed, non-blocking arrows: the worker moves on to its next assigned URL immediately, and both the frontier enqueue and the Bloom filter update happen asynchronously in the background.
5.2 Robots.txt disallow and fetch-failure handling
Steps 7a and 7b branch from the same point: once robots.txt is parsed and cached, a disallowed path is discarded immediately with no network call at all, while an allowed path proceeds to the actual fetch. Step 8's timeout does not retry inline - it hands off to a separate retry scheduler with exponential backoff (step 9) so a slow or dead site never occupies a fetch worker's thread, and after the configured max attempts the URL is logged to a dead-letter stream (step 11) instead of being retried forever.
6. Entity-relationship (ER) diagram and schema
The data model has to answer three questions: how does a worker cheaply find the next URL for a domain, how is a domain's politeness state tracked, and how does a fetched page get looked up again without a full scan.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Wide-column / key-value (Bigtable, DynamoDB, Cassandra) for url_frontier and crawled_pages | Access pattern is almost entirely "next N URLs for domain D" and "get page by URL/hash" at billions-of-rows scale, with no need for cross-row transactions. | Priority-ordered range scans per partition key must be designed in up front (e.g. domain as partition key, priority_score as clustering key). |
| Relational (Postgres/MySQL) for domains | The domains table is small (~200M rows) and benefits from strong constraints, joins for operational dashboards, and simple point lookups by hostname. | Don't be tempted to also put url_frontier here - the write and scan volume at 20B rows would overwhelm a relational engine's indexing model. |
7. Deep dives interviewers actually probe
How does the Bloom filter dedup work, and why accept false positives?
A Bloom filter is a bit array of size m with k independent hash functions. Adding a URL sets k bits (hash1(url) mod m, hash2(url) mod m, ...); checking a URL tests whether all k of those bits are set. It can never produce a false negative (a truly-seen URL is always reported as seen), but it can produce a false positive - reporting a genuinely new URL as "already seen" and silently skipping it. At 20 billion URLs and a tuned 1% false-positive rate, that means roughly 1 in 100 new URLs might be wrongly dropped - an acceptable loss against the alternative of storing an exact set (hundreds of GB to low TB, versus ~24GB) that would no longer fit comfortably replicated in memory across regions.
// k hash functions over one bit array of size m; each add/check is O(k)
boolean mightContain(String url) {
for (int i = 0; i < k; i++) {
long idx = hash(url, seed[i]) % m;
if (!bits.get(idx)) return false; // definitely not seen
}
return true; // probably seen (or false positive)
}
void add(String url) {
for (int i = 0; i < k; i++) bits.set(hash(url, seed[i]) % m);
}How is politeness guaranteed with hundreds of parallel fetch workers?
The guarantee comes from partitioning, not coordination. Every domain is assigned to exactly one frontier partition and one pool of fetch workers via a consistent hash of its hostname, so no two workers in the whole fleet can ever pull a URL for the same domain at the same time - there's nothing to race. Each partition's owner tracks a single per-domain "last fetched at" timestamp and compares it against that domain's crawl-delay (from robots.txt, or the 1-second default) before releasing the next URL for that domain. Scaling out to more workers only adds parallelism across different domains, never within one.
How does crawl priority and recrawl frequency get decided?
Each URL's priority_score blends two signals: an importance signal (e.g. a PageRank-like score from inbound link count/quality, plus manual boosts for known-authoritative domains) and a freshness signal (how often this specific page has historically changed, tracked via content_hash deltas across recrawls). A news homepage with a high change rate and high importance might be scheduled hourly; a static personal "About" page with years of unchanged content might be scheduled monthly or slower. The scheduler recomputes this score each time a page is recrawled, so a page that suddenly starts changing often gets promoted automatically.
How do you avoid spider traps and infinite URL spaces?
Classic traps are calendar widgets, faceted search filters, or session IDs in the URL that generate an effectively infinite number of distinct-looking links from a handful of real pages. Defenses layer together: URL normalization (stripping session/tracking query params, sorting remaining params, lowercasing the host) collapses many "different" URLs to the same canonical form before they even reach the Bloom filter; a per-domain crawl depth limit and a cap on URLs enqueued per domain per day bound worst-case damage; and pattern heuristics (e.g. more than N query parameters, or a repeating path segment like /page/2/page/2/page/2) flag a URL as low-priority or reject it outright rather than trusting every link the parser extracts.
What is the single biggest bottleneck as this scales 10x?
Not raw fetch throughput - that scales by adding more worker pods per shard. The real pressure points are (1) DNS resolution latency, since a cold lookup per fetch would dominate wall-clock time at tens of thousands of fetches/sec, solved by an aggressive, shared, TTL-respecting DNS cache; and (2) a handful of enormous domains (a large e-commerce or UGC site with tens of millions of pages) whose single frontier partition becomes a hot spot even though every other domain's queue is fine. The fix for the second is the same idea applied recursively: sub-partition that one domain's queue by URL-path prefix so it still obeys one crawl-delay budget in aggregate, but is served by several workers instead of being serialized through one.
Post a Comment
Add