TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design a Web Crawler

    SD Mock · Design a Web Crawler

    Overview

    Design a web-scale crawler like Googlebot on a live architecture board — drag components, wire them up, and defend your design to an expert interviewer who watches every move.

    Your Instructions

    Design a web crawler

    A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.

    The trap in this question is that the algorithm is three lines: download the seed pages, extract their links, add new links to the list, repeat. The interview is about the gap between that loop and a system that fetches hundreds of pages per second, politely, for weeks, without dying or looping forever.

    Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):

    • Notepad. Shared notes. Requirements, capacity math, schema, and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    Build incrementally while you talk. Trace one URL end to end through your diagram — from the frontier, through fetch and dedupe, back into the frontier. Argue the tradeoff, not "industry standard."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    Traversal: BFS, DFS, and why naive BFS fails

    The web is a directed graph: pages are nodes, links are edges. DFS goes arbitrarily deep down one site — usually a bad default. BFS with a FIFO queue is the standard start, but naive BFS fails twice at scale. First, most links on a page point back to the same host; parallel workers draining one queue will flood that host — your crawler becomes a DoS attack. Second, the web is not uniform quality: apple.com's homepage and a forum post mentioning Apple should not crawl at the same priority. Nuance worth naming: DFS within a host you are already connected to amortizes handshake overhead, and path-ascending crawling (given foo.com/a/b/page.html, also try /a/b/, /a/, /) finds resources with no inbound links. Equally defensible if you can say why.

    The URL frontier: priority in front, politeness in back

    The frontier is the queue of URLs still to download, and it is the hard part of this question. Two problems, two layers of queues.

    Politeness (back queues). Rule: at most one connection per host, with a delay between requests. Mechanism: a hostname-to-queue mapping table routes every URL for one host into one dedicated FIFO queue, and each worker drains exactly one queue, sequentially. Those two invariants together are the guarantee. One global queue with a worker pool has no politeness story.

    Priority (front queues). A prioritizer scores each URL (PageRank, traffic, update frequency) and drops it into one of several priority queues. A selector picks front queues randomly with a bias toward high priority — strict ordering starves the low-priority queues forever.

    Where it lives. The frontier holds hundreds of millions of URLs. Pure memory is not durable or big enough; pure disk is too slow. Hybrid: bulk on disk, in-memory enqueue/dequeue buffers flushed periodically.

    Two dedupes, not one

    Candidates conflate these constantly. URL-seen runs on every extracted link before it enters the frontier: has this URL been visited or queued already? It prevents re-adds and infinite loops. Content-seen runs on every downloaded document: roughly 30% of the web is duplicate content under different URLs. Compare a 64-bit checksum (MD5/SHA) of the page, never the text itself. The storage math is the same for both: 15B entries × 8-byte checksum = 120 GB per set — it fits on one big server, but plan an LRU cache backed by a persistent store.

    A Bloom filter is the tempting optimization for URL-seen: memory-efficient set membership, false positives possible, false negatives impossible. Say the consequence, not the definition: a false positive means the URL is wrongly marked seen, never enqueued, and that page is silently never crawled. You tune the bit-vector size to bound that loss. Naming the consequence is the senior signal.

    The downloader: DNS, robots.txt, timeouts

    The sleeper bottleneck is DNS: resolution is synchronous, takes 10–200 ms, and blocks sibling threads. Run your own DNS cache, refreshed by cron, instead of hitting a resolver per request. A courteous crawler fetches and obeys robots.txt — and caches the per-host rules with periodic refresh, never refetching per request. Add short timeouts (give up on slow hosts and move on) and locality (crawl servers near the hosts they crawl).

    Surviving a weeks-long crawl

    A full crawl takes weeks; servers will die mid-run. Consistent hashing distributes the URL space by hostname across crawl servers and absorbs adding or replacing a machine. Each server checkpoints its state — frontier queues, both seen-sets — to remote storage periodically; a replacement loads the last snapshot. Partitioning follows the same key: since URLs route by hostname, keep that host's to-visit URLs, URL checksums, and document checksums co-located on the same server, so dedupe checks never leave the box.

    Spider traps and freshness

    A trap is a URL family that generates infinite crawling: example.com/foo/bar/foo/bar/foo/bar/…, calendar pages, symlink cycles. A max-URL-length cap is a partial defense. The honest answer: there is no fully automatic detector. Trap sites reveal themselves as anomalous page-count outliers; a human verifies and adds a custom filter. Claiming a complete automatic solution is overreach, and interviewers probe it. Freshness is the same honesty: you cannot recrawl everything, so recrawl based on each page's update history, and recrawl important pages more often.

    Reference solution

    One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.

    Requirements (lock these or take the defaults)

    • Purpose: search-engine indexing
    • 1 billion pages per month, HTML only, HTTP only (extensible to more types later)
    • Store raw HTML for 5 years; freshness matters (new and edited pages)
    • Ignore duplicate content; respect robots.txt
    • Non-functional: scalability, politeness, robustness (bad HTML and dead servers are the norm), extensibility
    • Out of scope: JavaScript rendering, non-HTML media (name them as wrap-up topics)

    Capacity

    • 1B pages ÷ 30 days ÷ 86,400 sec ≈ 400 pages/sec average; peak 2× ≈ 800 pages/sec
    • 1B pages × 500 KB average page = 500 TB/month
    • 500 TB × 12 × 5 years = 30 PB of stored HTML
    • Dedupe sets: 15B URLs × 8-byte checksum = 120 GB per set (URL-seen and content-seen each) — one big box, but cache + persistent backing is the sane plan

    Rough numbers are fine; the method is what gets graded — and the numbers should drive decisions ("120 GB means the seen-set is not a naive per-worker hash map").

    Components to put on the board

    How the graph works: the Scheduler seeds and re-seeds the frontier. The Queue (URL frontier) is the hub — priority front queues feeding per-host back queues. Workers each own one back queue, resolve hosts through the DNS cache, fetch pages from the web, and hand raw HTML to the parsing service. Content dedupe gates storage; the URL filter and URL-seen gate the loop edge back into the frontier. Storage and dedupe checks stay off the fetch hot path.

    Scheduler (seed URLs, recrawl)
        → Queue (URL frontier: priority front queues → per-host back queues; mark distributed)
        → Worker (HTML downloader fleet; one worker per back queue; mark distributed)
            ↔ DNS (local resolver cache)
            ↔ Third-party API (the web servers being crawled; robots.txt honored)
            → Service (content parser + link extractor)
                → Redis (content-seen checksums, hot) ↔ Cassandra (checksum sets, persistent)
                → Blob Store (raw HTML, 30 PB)
                → Service (URL filter)
                    → Redis (URL-seen checksums / Bloom filter) ↔ Cassandra
                    → Queue (new URLs loop back into the frontier)
    

    Components:

    • Scheduler. Injects seed URLs (partition by locality or topic) and drives recrawl for freshness — important pages more often, guided by update history. Without it the crawl neither starts nor stays fresh.
    • Queue (URL frontier). The to-download set and the centerpiece. Front queues rank by usefulness; back queues hold exactly one host each so politeness is structural, not best-effort. Disk-backed with memory buffers. Without the two-layer split you either hammer hosts or crawl junk first.
    • Worker (HTML downloader). The fetch fleet. Each worker drains one back queue sequentially with an enforced delay — that is the one-connection-per-host guarantee. Caches robots.txt rules per host; short timeouts on slow servers. Marked distributed: hundreds of stateless-ish fetchers behind consistent hashing.
    • DNS. The local resolver cache, refreshed by cron. Synchronous 10–200 ms lookups per request would block threads and cap the whole fleet; this box exists purely to kill that bottleneck.
    • Third-party API. The web itself — the external servers being crawled. On the board so the fetch edge (and robots.txt) is visible and traceable.
    • Service (content parser + link extractor). Validates and parses pages — malformed HTML is the norm — then pulls links and converts relative paths to absolute URLs. Separate from workers so parsing never slows fetching.
    • Service (URL filter). Drops unwanted extensions, error links, and blacklisted domains before dedupe. Cheap gate that keeps garbage out of the frontier.
    • Redis. The hot layer for both seen-sets. Link popularity is heavily skewed, so an LRU cache of popular checksums gets a high hit rate; the Bloom filter variant for URL-seen lives here too. Without it every extracted link is a database round-trip.
    • Cassandra. Persistent backing for both 120 GB checksum sets plus crawl metadata, partitioned by hostname so each crawl server's dedupe checks stay local. Replicated so one node loss is not a lost seen-set.
    • Blob Store. The 30 PB HTML archive. Write-mostly, disk-tier, hot pages cached. The crawl's actual product.

    Walk one URL: the frontier hands out en.wikipedia.org/wiki/Apple

    1. The Scheduler seeded wikipedia.org; the prioritizer ranked it high, and the URL sits in the back queue dedicated to that host. The one worker that owns that queue pulls it.
    2. The worker resolves the IP through the local DNS cache — no live lookup.
    3. The worker checks the cached robots.txt rules for the host, fetches the page from the web server, and enforces the inter-request delay before the queue's next URL.
    4. The parser service validates and parses the raw HTML.
    5. Content-seen: compute a 64-bit checksum, check Redis, fall back to Cassandra. Duplicate (~30% of the web is) → discard and move on. New → write the HTML to the Blob Store.
    6. The link extractor pulls every link and absolutizes relative paths.
    7. The URL filter drops blacklisted domains and unwanted extensions.
    8. URL-seen check per surviving link; new URLs go back into the frontier's front queues. The loop closes.

    Most links point home: that Wikipedia page links mostly to other wikipedia.org pages. They all route to the same back queue and drain sequentially with delays — the design is what protects the host, not worker goodwill.

    A rack dies in week 3 of a 4-week crawl: its checkpoints (frontier queues, both seen-sets) are on remote storage. Consistent hashing shifts its hostnames to the fleet until a replacement restores from the last snapshot. You lose minutes, not three weeks.

    A trap URL enters the frontier: /foo/bar/foo/bar/… grows past the max URL length and is dropped. The subtler traps show up as a host with an anomalously huge page count; a human confirms and blacklists it in the URL filter.

    Schema

    Frontier(url, host, priority, enqueued_at)            — disk-backed queue files
    UrlSeen(url_checksum)                                 — 8-byte checksums, ~120 GB
    DocSeen(doc_checksum)                                 — 8-byte checksums, ~120 GB
    Documents(url_checksum, blob_key, doc_checksum, fetched_at, status)
    RobotsCache(host, rules, fetched_at)
    HostQueueMap(host, back_queue_id)
    
    • Partition key everywhere is the hostname, via consistent hashing — a host's to-visit URLs, URL checksums, and document checksums live on the same server, so dedupe never crosses the network
    • Store checksums, never full URL or page text, in the seen-sets
    • Raw HTML in the Blob Store; Documents rows hold only the blob key
    • Replicate the seen-sets and checkpoint everything to remote storage

    Scaling and wrap-up

    • The worker fleet scales horizontally behind consistent hashing; the frontier and seen-sets shard by hostname along with it
    • Blob Store absorbs the bytes; Redis absorbs the dedupe reads; the DNS cache absorbs the lookups
    • First metrics: crawl rate (pages/sec), per-host error and timeout rates, frontier depth per queue
    • If time: server-side rendering for JavaScript-generated links, anti-spam filtering, storage replication and sharding, crawl analytics driving recrawl schedules

    Equally defensible variants

    Grokking's numbers instead of Xu's: 15B pages in 4 weeks ≈ 6,200 pages/sec, ~1.5 PB raw ≈ 2.14 PB provisioned at a 70% ceiling. The Mercator worker-loop framing where each worker thread runs the whole pipeline (fetch → document input stream → dedupe → extract → filter → enqueue) instead of separate services. Kafka as the frontier substrate. A Bloom filter versus an exact checksum set for URL-seen. DynamoDB or MongoDB for the checksum sets. What matters is that you can argue the tradeoff.

    More in System Design Interview Prep: AI Coach Edition

    • SD Mock · Design Twitter Search
    • SD Coach · Rate Limiting
    • SD Mock · Design an API Rate Limiter
    • SD Coach · Event-Driven Systems and Notifications
    • SD Mock · Design a Notification System
    • SD Coach · Async Jobs, Schedulers and Crawlers
    • SD Coach · Distributed Storage
    • SD Mock · Design a Key-Value Store
    • SD Coach · File Sync: Dropbox and Google Drive
    • SD Mock · Design Dropbox
    • SD Coach · Transactional Systems
    • SD Mock · Design Ticketmaster
    View the full course (43 sessions) →