Design a Web Crawler: URL Frontier, Politeness, Dedup and Recrawl

Listen

Clarify the goal first. We start from seed URLs, fetch HTML, store the raw page for an indexer, extract links and keep going, and we revisit pages that change. Non-functional needs matter more here. Be polite: obey robots dot txt and never hit one host with many parallel requests. Survive malformed pages and infinite link traps. Scale horizontally and resume after a crash. Out of scope: rendering JavaScript, images and video, and the search index itself.

Ask scale

A billion pages a month is about four hundred pages a second, eight hundred at peak. At a hundred kilobytes a page that is forty megabytes a second of download, around three hundred megabits, and a hundred terabytes a month raw, about three hundred terabytes a year compressed. We will know of ten billion URLs, so remembering which ones we have seen takes eighty gigabytes of hashes, or about twelve as a Bloom filter. None of this is CPU heavy; waiting on slow sites is the real constraint.

1B pages/month / 2.5M s = 400 pages/s
peak x2 = 800 pages/s

avg HTML page 100 KB
  400 x 100 KB = 40 MB/s = 320 Mbps
  1B x 100 KB = 100 TB/month raw
  compressed 4x = 300 TB/year

seen URLs: 10B x 8-byte hash = 80 GB
  Bloom filter at 1% error = 12 GB

Define API

A crawler has no end users, so the API is about control. Operators add seeds, read stats and override the rate for a specific host, for example after a site owner complains. Internally the key interface is the frontier: a worker leases a URL and later acknowledges it with the result. Leases matter, because if a worker dies the URL goes back to the queue. Every fetched page emits an event that the indexer consumes.

POST /v1/seeds  { urls: [...], priority }
GET  /v1/stats  pages/s, errors, queue
PUT  /v1/hosts/{host}/limit { rps: 0.5 }

frontier.lease(worker) -> url, lease_id
frontier.ack(lease_id, result)

event page.fetched {
  url, status, content_hash, blob_key }

Data model

Two tables and a blob store. The URL table is keyed by a hash of the normalized URL and holds depth, priority, when we last fetched it, when to fetch it next, and the ETag and content hash from last time. The host table holds parsed robots rules and the earliest time we may hit that host again. Raw pages go to object storage, packed into segment files. Ten billion rows with only key lookups is a great fit for a wide-column store like Cassandra; we never need joins.

urls (key = hash(normalized url))
  url, host, depth, priority
  last_fetch, next_fetch, status
  etag, last_modified, content_hash
hosts (key = host)
  robots_rules, crawl_delay, next_ok_at
pages: segment files in object store
  url_hash + time -> segment, offset

NoSQL: point reads by key, 10B rows

High-level design

Here is the loop. A fetcher leases a URL from the frontier, resolves the host through a local DNS cache, and downloads the page. The raw HTML is appended to object storage. A parser pulls out links and text. Each link is normalized and checked against the seen set; most are already known, and only genuinely new URLs go back into the frontier. Then the worker leases the next URL. Everything is a queue, so every stage scales on its own.

Deep dive: frontier

The frontier is the heart of the design, and it has two layers. Front queues sort URLs by priority, based on things like how many pages link to them and how often they change. Back queues hold one queue per host. A heap orders hosts by the earliest time we are allowed to contact them again. A worker pops a host whose time has come, takes one URL, and pushes the host back with its next allowed time. Important pages go first, and no host ever sees a burst.

front: priority queues P1..P5
  priority from link popularity,
  site quality, change rate

back: one FIFO queue per host
  a heap orders hosts by next_ok_at
  worker pops the host whose time
  has come, takes one URL
  next_ok_at = now + crawl delay

result: important first, polite always

Deep dive: politeness

Politeness is a requirement, not a nicety. Fetch each host's robots dot txt, cache it for about a day, and skip disallowed paths. Keep one connection per host with a gap of a second or two, or whatever crawl delay the site asks for. If a site returns 429 or 503, double the gap and slow down. And send an honest user agent string with a contact page, so site owners can reach you instead of blocking you.

Deep dive: URL dedup

One page can be reached by dozens of URL spellings, so normalize first: lowercase the host, drop fragments and tracking parameters, sort query parameters and resolve relative paths. Then ask a Bloom filter. If it says no, the URL is definitely new. If it says maybe, confirm against the URL table. A Bloom filter never misses a URL it has seen; its only error is occasionally claiming to know a new one, and at one percent we accept skipping a few pages.

normalize first:
  lowercase host, drop #fragment
  drop tracking params (utm_*)
  sort query params, resolve ../

Bloom filter in memory (12 GB)
  "no" is certain -> new URL
  "maybe" -> check urls table

1% false positive: some pages skipped

Deep dive: content dedup

Even with perfect URL dedup, the same content lives at many addresses: mirrors, print views, session-id URLs. Hash the body to catch exact copies, and store only a pointer. For near copies, where only a date or an ad changed, compute a SimHash of the text. Similar pages produce fingerprints that differ in just a few bits, so a page within three bits of a known one is treated as a duplicate. This can save a large fraction of storage and indexing work.

Some sites, by accident or on purpose, generate infinite URLs: a calendar with a next link forever, a session id baked into every link, endless sort and page parameters. Defend with simple limits. Cap the depth from the seed, cap the URL length, give each host a page budget per day, and skip paths with repeating segments. A trap then costs you a few thousand pages instead of your whole crawl.

exact copy: hash the body (SHA-256)
  match -> store a pointer only

near copy (new date, new ad):
  SimHash of the text, 64 bits
  differ in 3 bits or fewer
    -> treat as a duplicate

mirrors and print views: near
  copies are a big share of pages

Deep dive: recrawl

Pages change at wildly different rates. A news front page changes hourly, an old blog post almost never. Track each URL's history: if it changed on recent visits, halve its revisit gap; if not, double it, within sensible bounds. When you do revisit, send a conditional GET with the stored ETag or last-modified date. An unchanged page answers 304 Not Modified, a tiny response that saves bandwidth for you and the site.

track change rate per URL
  changed last 3 visits -> halve gap
  unchanged -> double gap
  bounds: 1 hour to 60 days

news front page: hourly
old blog post: monthly

conditional GET: ETag, Last-Modified
  304 = tiny response, no reparse

Deep dive: distribution

To scale out, partition everything by host. Hash the host name to pick an owner partition, using consistent hashing so adding machines moves few hosts. Because one worker owns each host's queue, politeness needs no global lock. Links to other hosts are forwarded to their owners. With async I/O one machine keeps hundreds of fetches open, so a handful of machines covers eight hundred pages a second. Keep a local DNS cache; public resolvers are slow and rate limited.

partition = hash(host) mod N
  (consistent hashing on rebalance)
  one owner per host -> politeness
  needs no global lock

new link for another host:
  forward to its owner partition

async I/O: 500+ open fetches/box
800 pages/s / 100 per box = 8 boxes
local DNS cache: resolvers are slow

Deep dive: storage

Storing a billion pages as a billion tiny objects is slow and expensive, since object stores charge per request and listing them is painful. Instead, append compressed pages to large segment files of around a gigabyte, with a small side index from URL hash to file and offset. When a segment closes, publish an event and the indexer reads it as one sequential stream. Older fetches move to a cheaper cold storage tier.

1B tiny objects/month: slow to list,
  costly per request

instead: append pages to segment files
  about 1 GB each, gzip per record
  side index: url_hash -> file, offset

segment closed -> event to indexer
old fetches: lifecycle to cold tier

Trade-offs

Failure handling leans on leases and idempotent writes. If a worker crashes, its lease expires and the URL returns to the queue. Frontier queues are persisted as a log, so a restarted node replays them. Fetching a page twice after a retry is harmless, because storage writes are keyed by URL and time. Dead sites get retried with backoff and then marked. And give the parser strict time and size limits, because some HTML is truly hostile.

Monitor pages per second, the mix of status codes, frontier size per priority, the duplicate rate and bytes per second. A rising share of 429s is your early warning that you are being impolite. At ten times the volume the design holds: add partitions and fetchers, and storage becomes the main cost. Crawling JavaScript-heavy sites needs a separate tier of headless browsers, which is many times more expensive per page, so send only the URLs that need it.

Interview summary

To summarize in the interview. Four to eight hundred pages a second and about three hundred terabytes a year. A loop of lease, fetch, store, parse, dedup and enqueue. A two-layer frontier with priority queues in front and per-host queues behind. Robots rules, crawl delay and backoff. URL normalization with a Bloom filter, SimHash for near duplicates, limits against traps, adaptive recrawl with conditional requests, and partitioning by host.