Design a Web Crawler

A search engine can only find pages it has seen. A web crawler is the program that sees them: it starts from a few known URLs, downloads each page, pulls out the links, and adds the new ones to its to-do list. Run that loop a billion times a month and you have the raw material for a search index.

Interviewers like it because the loop is easy and everything around it is not: be polite to other people's servers, avoid fetching a page twice, survive sites that generate endless URLs, and keep hundreds of downloads in flight. The steps follow A Framework for Any Design.

#Clarify the problem

• Functional: start from seed URLs; fetch HTML pages; extract links and add new ones; store each page's content; recrawl pages, important ones more often.
• Non-functional: polite (one request at a time per site, with a gap, robots rules obeyed); about 1 billion pages a month; each URL scheduled once per cycle (a rare lease retry may fetch it twice); survives slow and hostile sites; a crashed machine loses no frontier state.
• Out of scope: indexing and ranking, JavaScript rendering, images and video, pages that need a login.

#Estimate the scale

A month is 30 × 86,400 = 2,592,000 seconds, call it 2.6 million. The crawler sets its own pace, so there is no traffic peak to plan for, only a target rate plus headroom for retries and slow periods.

• Fetch rate: 10⁹ pages ÷ 2.6 × 10⁶ s ≈ 385 a second. Call it 400, and plan for 800 so a bad day can be caught up.
• Bandwidth: assume an average HTML page of 100 KB. 400 × 100 KB = 40 MB/s, about 320 Mbit/s. One data center link handles it.
• Connections in flight: assume a fetch takes about 1 second end to end, because many sites are slow. By Little's law (in-flight = rate × time), 400 a second × 1 s = 400 downloads open at any moment, 800 with headroom.
• The politeness ceiling: at most one request a second per site, so a site with 1 million pages takes 10⁶ ÷ 86,400 ≈ 11.6 days. Large sites, not bandwidth, limit how fresh you can be.

#Define the API

frontier.add(urls: [ { url, priority, discovered_from } ])
  -> accepted count; URLs already seen are dropped silently
 
frontier.lease(fetcher_id) -> { url, host, lease_id, lease_until }
  -> or "nothing ready, retry in N ms" when every host is cooling down
 
frontier.complete(lease_id, result)
  result: fetched(status, content_hash) | not_modified | failed(reason, retry_after?)
  -> an expired lease is handed out again, so a dead fetcher loses no URL
 
event PageFetched { url, fetched_at, status, content_hash, blob_key }
  -> published to a stream that the indexer consumes

The decision worth arguing is lease, not pop. If a fetcher popped a URL and crashed, the URL would be lost for good, since it is already marked seen and will never be added again. A leased URL goes back out after lease_until. The cost: a slow (not dead) fetcher may download a page another fetcher also downloads. That wastes a fetch but breaks nothing.

#Model the data

-- one row per known URL, partitioned by host hash
urls:   url_hash      BIGINT PRIMARY KEY  -- 8-byte hash of the normalised URL
        url           TEXT                -- up to ~2 KB
        host          TEXT
        priority      SMALLINT
        next_fetch_at TIMESTAMP
        last_status   SMALLINT
        content_hash  BIGINT NULL         -- fingerprint of the last body
 
-- one row per host
hosts:  host            TEXT PRIMARY KEY
        robots_rules    TEXT              -- parsed robots.txt, refreshed daily
        crawl_delay_ms  INT               -- 1,000 unless the site asks for more
        next_allowed_at TIMESTAMP
        ip_cache        TEXT, ip_expires TIMESTAMP
 
-- page bodies: object storage, key = url_hash + fetch date, gzip-compressed

The URL table gets lookups and inserts by hash and a scan for "what is due", with no joins: a wide-column or key-value store (such as Cassandra) partitioned by host fits, so the machine that schedules a host also owns its URLs. Page bodies are large, written once and read in bulk: that is blob storage.

Normalise URLs before hashing, or one page looks like many: lowercase the scheme and host, drop the default port and the #fragment, sort and prune query parameters. HTTP://Example.com:80/a?b=2&a=1#top and http://example.com/a?a=1&b=2 are one page.

#High-level design

The crawl is a breadth-first search over the web graph: the frontier is the queue and the seen-URL set is the visited set. Here the queue is ordered by priority and politeness, and the visited set spans machines.

Follow one URL through the loop.

#Deep dives

#The URL frontier: politeness and priority

A plain first-in, first-out queue fails twice. Pages link mostly within their own site, so the queue fills with runs from one host and the fetchers hit it all at once. And it treats a news home page like a ten-year-old forum thread.

Split the frontier into two layers. The front layer is a handful of priority queues: high for pages that change often or rank well, low for the long tail. The back layer is one queue per host, and each host is in at most one fetcher's hands at a time. A min-heap holds each host keyed by the time it may next be fetched. When a host's queue runs dry, it is refilled from the front layer, picking high priority more often than low.

host, ready_at = heap.peek()if ready_at > now: wait until ready_atheap.pop(); url = queue[host].pop()lease url to fetcheron complete: heap.push(host, now + delay[host])

To scale out, split the frontier by host with consistent hashing over, say, 10 machines. Each host lives on exactly one machine, so politeness needs no coordination. Queues live on disk with a small in-memory head.

For priority, score each page by how often it changed on past fetches and how many known pages link to it.

#Deduplicating URLs

Each page adds about 50 links to check, so at 400 pages a second the seen set answers 20,000 lookups a second, nearly all "already seen".

Two details make it correct. The check is insert-if-absent, one atomic step on the shard, so two parsers finding the same link cannot both add it. And a URL counts as seen only once the frontier has stored it, so a crash never leaves a URL marked seen but never queued.

A Bloom filter is a big bit array plus k hash functions. Adding a URL sets k bits; checking it looks at the same k bits. If any is 0, the URL is certainly new. If all are 1, it is probably seen, because other URLs may have set those bits. For a 1% false-positive rate you need about 9.6 bits per item and 7 hash functions: 10¹⁰ × 9.6 bits ≈ 12 GB.

The catch to say out loud: a false positive is sticky. The same new URL hits the same bits every time it is discovered, so it is skipped every time, for as long as that filter lives. If you use a Bloom filter, rebuild it each crawl cycle with fresh hash seeds so the unlucky URLs change. At this scale I would pick the hash set. At 100 billion URLs (800 GB against 120 GB) the trade flips.

#Deduplicating content

Different URLs often serve the same page: mirrors, ?ref= variants, printer-friendly copies. Store a 64-bit fingerprint of each body (8 bytes × 1 billion pages = 8 GB) and skip parsing when it is already known. That catches exact copies only. Pages that differ by a timestamp or an ad need a similarity hash, where similar pages get fingerprints that differ in a few bits. Mention it; design it only if asked.

#DNS and fetch throughput

A fetch is mostly waiting. With non-blocking I/O, ten fetcher machines holding 80 open connections each cover the 800 we planned for. The CPU goes to parsing, which is why parsers are a separate fleet.

DNS is the classic hidden bottleneck: many standard resolver calls block a thread, and an uncached lookup can take 10 to 200 ms. Run a caching resolver next to the fetchers, keep each host's IP until its DNS time to live runs out, and resolve a host just before its turn in the heap. If one lookup serves 20 fetches on average, 400 fetches a second need only 400 ÷ 20 = 20 lookups a second.

#Robots rules and traps

Before the first fetch from a host, download its /robots.txt and cache the parsed rules for about a day. Obey Disallow paths and any longer delay the file asks for. If the file returns a server error, treat the site as off limits for now; a 404 means no rules.

Some sites generate URLs without end: a calendar with a "next month" link forever, session IDs in every link, filters that combine into millions of pages. Defend in layers: cap URL length (say 2,000 characters) and path depth, cap pages per host per cycle, strip session parameters, and flag hosts where most fetched pages have a fingerprint you have already seen.

#Bottlenecks and failures

At 10x (10 billion pages a month, about 4,000 fetches a second), fetchers and parsers scale by adding machines, and bandwidth becomes 400 MB/s, about 3.2 Gbit/s. The seen set heads toward 100 billion URLs, where a Bloom filter starts to earn its loss rate. The real limit is politeness: large sites cannot be fetched faster, so their freshness comes from smarter priority and conditional requests (If-Modified-Since), where a 304 Not Modified costs almost nothing.

#What a strong answer sounds like

Everyone draws the loop. The difference is whether politeness and deduplication shape the design.

#Follow-up questions

#How do you decide when to recrawl a page?

Track how often its fingerprint changed over past fetches and schedule around that interval, shorter for important pages. Conditional requests make an unchanged page cost a 304, not a download.

#How would you crawl pages that need JavaScript to render?

Send only the pages that need it to a separate pool of headless browsers. Rendering costs far more CPU than parsing HTML, so keep it as a per-site exception.

#A site asks you to stop crawling it. What changes?

Add the host to a blocklist the frontier checks before leasing, and purge its queue. Each host lives on one frontier machine, so this takes effect at the next lease.

#How would you crawl from several regions?

Give each host to the region nearest its servers, so fetches are short and each host still has one owner. Only new URLs cross regions, to the seen set.

#How do you know the crawler is healthy?

Watch fetches per second, the duplicate-content share, error rates per host, and the age of the oldest due URL in the high-priority queue, which tells you whether important pages are going stale.

#What to practise next

Next, Design Video Streaming moves huge files instead of small pages. For the queue ideas here, see Message Queues and Streams.