Design a web crawler

Do the numbers before the boxes

An interviewer gives a scale, not a load. If we draw before we do the math, we cannot say why any box has its size.

Our target: refresh a 5 billion page index every month.

Common Crawl's October 2025 crawl fetched 2.61 billion pages in 15 days: 2,610,000,000 / (15 x 86,400) = 2,014 pages a second.

We crawl at 2,000 pages a second, all month: 2,000 x 2,592,000 seconds = 5.18 billion pages a month.

There is no peak factor. A crawler runs at the rate we set, around the clock, so the drawn month is the real month.

We measure load in pages a second: the pages the scheduler releases for fetching.

The first month runs at a quarter of that: 500 pages a second, 1.3 billion a month.

Common Crawl's December 2025 crawl reached 46 million hosts. That is the pool of sites our fetches spread across.

Check in: Close the page and derive 2,000 pages a second from a 5 billion page index refreshed every month. Then say why there is no peak factor.

The frontier: priority and politeness

A crawler that fetches as fast as it can gets blocked. A crawler that fetches in link order wastes its month on unimportant pages.

Hosts are not in the simulation, so we work this by hand.

The frontier is the set of URLs we know and have not fetched yet, plus the scheduler that picks from it.

Front queues sort URLs by priority: say 10 levels, from link-based rank and freshness.

Back queues hold one host each. A heap of hosts is keyed by the next time each host may be fetched.

That time is the last fetch plus the largest of 1 second, the host's crawl-delay, and 10 times its last response time.

With responses near 1 second, the gap is about 10 seconds, so each host gives about 0.1 page a second.

This is politeness. Being blocked costs more than being slow.

So 2,000 pages a second need about 2,000 x 10 = 20,000 hosts in rotation, and 3,200 need 32,000. Common Crawl's 46 million leave plenty.

The scheduler pops hosts that are due, takes the first URL of each, leases it for 5 minutes, and puts it on a ready queue.

We partition the scheduler by a hash of the host, so one host's politeness lives in one place and needs no coordination.

robots.txt is fetched before any page of a host, as one of its polite requests. RFC 9309 says to cache it for at most 24 hours.

A 5xx answer for robots.txt means assume everything is disallowed, and retry later. A 4xx means there are no rules.

Crawl-delay is not in RFC 9309. We honour it as policy when it asks for more than 1 second.

Step through the figure to follow URLs through the frontier.

The trade-off:

Politeness caps each host at about 1 page every 10 seconds. Speed comes only from fetching many hosts at once.

The frontier: front queues, back queues, a heap of hosts

1. Front queues sort URLs by priority. Back queues hold one host each, so each host is fetched on its own schedule.
2. The scheduler pops a host whose wait is over and leases its first URL. The host's next time is at least 1 second later.
3. A host is fetched about once every 10 seconds, so 2,000 pages a second need about 20,000 hosts in rotation. Common Crawl's 46 million hosts leave plenty.

Check in: Why cannot 2,000 pages a second come from a few big sites? Give the number of hosts in rotation, with its working.

Fetchers, and Little's law

In the first month we crawl 500 pages a second. Each fetch mostly waits on someone else's server.

Units: sizes here are binary, so a KiB is 1,024 bytes and a GiB is 2^30 bytes. AWS bills a GiB as one "GB".

Bytes: Common Crawl's October 2025 pages average 468 TiB / 2.61 billion = about 193 KiB. Gzip shrinks HTML about 4 to 1, so about 50 KiB crosses the wire.

A fetch takes about 1,005 ms: about 1 second waiting on DNS, the connection and the server, plus 5 ms of parsing. Both are our estimates.

Each fetcher task keeps 100 fetches open with async I/O. At full use it fetches 100 / 1.005 = 99.5 pages a second, and parsing uses half a vCPU.

Little's law: fetches open = pages a second x seconds a fetch. 500 x 1.005 = 503 open, which is 5.0 tasks running full.

With auto-scaling at a 70% target, 500 / (99.5 x 0.7) = 7.2, so 8 tasks run, at 63%. At most 30 tasks give 2,985 pages a second.

Fetchers in private subnets reach the web through a NAT gateway.

It charges $0.045 per GB processed: 500 x 50 KiB x 2,592,000 seconds = 61,798 GiB, about $2,781 a month.

The fetchers sit behind a queue, so nothing waits on them. A crawl is measured in pages a second and dollars per million pages.

The trade-off:

A fetcher task spends almost all its time waiting. Throughput comes from fetches held open, not from processors.

Check in: At 2,000 pages a second, how many fetches are open, and how many tasks run at the 70% target? Give each task's pages a second.

The first month: a database write per link

Every page brings back links, and every link must be checked against the URLs we know.

Links: about 25 a page after we normalise them, our estimate. That is 500 x 25 = 12,500 links a second.

The URL table in DynamoDB is the frontier's store: one item per known URL, about 300 bytes.

A dedup worker checks each link with a conditional put: insert the URL only if it is absent.

Each costs one write capacity unit (WCU), new URL or not. A failed condition still pays for its write.

Writes: 12,500 links + 500 "fetched" marks = 13,000 a second. At 70% use, 13,000 / 0.7 = 18,571, so we buy 18,600 WCU.

The scheduler also reads 500 due URLs a second, at half a read capacity unit (RCU) each. That is 250, so we buy 400 RCU.

Stage 1 runs this design at 500 pages a second. Its tiles and buttons say requests a second; here one request is one page fetched.

The latency tile shows 2ms. It shows the scheduler's read, the slowest path a request takes inside our system.

A fetch's 1 second is not on it, because the fetchers sit behind a queue.

"First to saturate" reads "Nothing at this load", and its note names the URL table, at 70%.

A part saturates when it gets more requests than it can serve. A card turns red at 90% of its limit; only past 100% does the result name it.

The cost tile shows $21k/mo, 45% of it the URL table. The one warning is the NAT gateway's processing charge.

Each page costs the URL table 26 writes, so its wall is 18,600 / 26 = 715 pages a second. That is only 1.4 times the first month's load.

Press 750. The URL table saturates. Press 2,000, the next twist's load, and it saturates far past its limit.

The trade-off:

Every link costs a database write, even a link to a page we already know: 25 writes a page. The fetch itself is cheap.

Stage 1: The first month: 500 pages a second, a database write per link

• Load: 500 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $21k/mo

• NAT gateway: 61,798 GB/month through NAT costs ~$2781/month in processing charges, on top of any data-transfer charge.

Check in: Why does the URL table need 13,000 write units for 500 pages a second?

Common Crawl's pace on the same design

The interviewer asks: Crawl at Common Crawl's pace: 2,000 pages a second. What breaks?

2,000 pages bring 50,000 links a second. Each is a conditional put, so the URL table gets 52,000 writes a second, against 18,600 WCU.

The fetchers keep up: 2,010 fetches open, and at the 70% target, 29 tasks fetching 69.0 pages a second each.

Even the most write units a table gets by default, 40,000, stop this design at 40,000 / 26 = 1,538 pages a second.

And 52,000 WCU would cost 52,000 x $0.468 = $24,336 a month, after a quota request. The cost grows with links, not pages.

Press 500 on Stage 2. At the first month's rate, nothing saturates.

Press 2,000. The URL table saturates. Read the stage's warnings: its writes are at 280% and its reads at 250%.

The latency tile now starts with "≥", a lower limit, because the URL table is on the scheduler's path.

The cost tile shows $55k/mo. Most of the rise is the page store and the NAT gateway, which the cost twist takes apart.

The trade-off:

More write units move the wall only a little, at a high price. The check itself must stop being a database write.

Stage 2: The same design at 2,000 pages a second

• Load: 2,000 req/sec
• First to saturate: URL table
• Estimated cost: $55k/mo

• Latency past saturation is a lower bound, not an estimate. URL table is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• NAT gateway: 247,192 GB/month through NAT costs ~$11124/month in processing charges, on top of any data-transfer charge.
• Page store (S3): Standard storage holds 241.4 TB.
• URL table: Read capacity 250% used (provisioned): 1000 of 400 RCU/s at 54000 RPS.
• URL table: Write capacity 280% used (provisioned): 52000 of 18600 WCU/s at 54000 RPS.

Check in: Could you just buy 40,000 write units? Give the pages a second it carries.

A Bloom filter, and how many URLs it must hold

Most links point to URLs we already know. A database write is a costly way to learn that.

A Bloom filter answers "seen before?" from memory. It can wrongly say yes, a false positive, but it never says no for a URL it holds.

Bits per URL = -ln(p) / (ln 2)^2. At a 1% false-positive rate that is 9.59 bits, with 7 hash functions.

How many URLs? We find 10,000 new URLs a second: 864 million a day, 25.9 billion a month.

The URL table holds about 10 billion: the 5.2 billion pages in the index, plus about 5 billion unfetched. An unfetched URL expires after 6 days.

A Bloom filter cannot forget, so we rebuild it every week from an export of the URL table.

A generation starts with the table's 10 billion and takes 7 x 864 million = 6.05 billion more, so we size it for 16 billion.

16 billion x 9.59 bits = 153 gigabits, or 17.9 GiB. A set of 8-byte fingerprints would be 128 GB, and whole URLs about 1.6 TB.

Valkey 8.1 caps one filter object at 128 MB. So a generation is 256 filters of about 70 MiB, picked by URL hash.

They live on 3 shards of cache.r7g.xlarge, each with a replica. After the default 25% reserve, 3 x 26.32 x 0.75 = 59.2 GiB.

During the weekly swap both generations are held: 35.7 GiB, 60%. The weekly exports cost about $1,200 a month, and are not drawn.

The guarantee is not the filter. The conditional put in the URL table stops a URL being queued twice; the filter only saves writes.

The filter can miss a URL the table holds, after a crash or a rebuild. Then the put just fails, for 1 write unit.

Step through the figure to see an insert, a check and a false positive.

The trade-off:

The filter loses 1% of new URLs on purpose, and needs a weekly rebuild. The URL table stays the truth.

A Bloom filter, and its size

1. Adding a URL sets 7 bits, one per hash function.
2. If any of the 7 bits is clear, this filter never added the URL. The conditional put in the URL table, not the filter, is the guarantee.
3. Bits set by other URLs can make a new URL look seen. At 9.59 bits a URL, that happens 1% of the time.
4. A generation for 16 billion URLs is 17.9 GiB, in 256 filters under the 128 MB cap. It is rebuilt every week; during the swap, two generations use 35.7 GiB of 59.2.

Check in: Why is each filter generation sized for 16 billion URLs? And what stops a URL being queued twice?

The filter in front of the URL table

Stage 3 puts the filter between the dedup workers and the URL table.

The drawing shows the filter as a cache. Its "hit rate", 80%, is the share of links already seen, our estimate.

The other 20% are new: 50,000 x 0.2 = 10,000 new URLs a second, each a conditional put. Adds to the filter are not drawn.

The 1% false positives skip about 100 new URLs a second, until the next cycle.

The URL table now gets 10,000 puts + 2,000 marks = 12,000 writes, and 2,000 reads. We buy 24,000 WCU and 2,100 RCU: 50%.

The scheduler finds due URLs through an index on host and due time. The stages do not draw it.

It takes 10,000 inserts, 2 writes for each of 2,000 leases and 2,000 marks, and 2,000 lease writes: about 20,000 more WCU a second.

Provisioned at 28,600 WCU, that index costs about $13,385 a month on every stage.

Stage 3 runs at 2,000 pages a second. Nothing saturates, and the note on "First to saturate" names the Fetchers, at 69%.

Read the stage's warnings: the NAT gateway's processing charge, and the page store's large storage.

The cost tile shows $59k/mo. The filters cost $1,510 a month, and URL table writes fell from 52,000 to 12,000 a second.

The next walls are the fetchers at 2,985 pages a second, then the URL table at 4,000.

The trade-off:

The filters cost $1,510 a month and save 40,000 writes a second. The undrawn index is now the larger database cost.

Stage 3: A Bloom filter in front of the URL table

• Load: 2,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $59k/mo

• NAT gateway: 247,192 GB/month through NAT costs ~$11124/month in processing charges, on top of any data-transfer charge.
• Page store (S3): Standard storage holds 241.4 TB.

Check in: What does the 1% false-positive rate cost, and what does it never cause?

Count the units: WARC files and no NAT

The interviewer asks: Finance asks why the crawler costs about $58,900 a month.

Stage 3's two biggest lines are per-unit prices.

Each page is one PUT to S3, at $0.005 per 1,000: 5.18 billion PUTs, $25,920 a month, 44% of the bill.

The NAT gateway sees 2,000 x 50 KiB = 97.7 MiB a second: 247,192 GiB a month at $0.045, $11,124, 19% of the bill.

We write pages into WARC files, the standard web-archive format. A file of 2,000 pages is 2,000 x 50 KiB = 97.7 MiB.

So the page store gets 1 PUT per 2,000 pages: 1 a second, about $13 a month.

Each task fetches 2,000 / 29 = 69.0 pages a second, so it fills a file in 2,000 / 69.0 = 29.0 seconds.

The URL item keeps the file and offset, so one page can be read back alone.

Fetchers move to public subnets behind an internet gateway, which charges nothing per GB. Data in from the internet is free.

Two costs stay. Each task's public IPv4 address costs $0.005 an hour: about $104 a month for 29 tasks.

Our requests also send bytes out, about 1 to 2 KiB a page, our estimate: 4,944 to 9,888 GiB a month.

After the first 100 GB free, at $0.09 per GB, that is about $440 to $880 a month. The stage draws neither cost.

Step through the figure to compare a PUT per page with a file per 2,000 pages.

Press 2,000 on Stage 4. Nothing saturates, and the note on "First to saturate" names the Fetchers, at 69%.

The cost tile shows $22k/mo, 63% less. On the canvas, $58,852.28 / 5,184 = $11.35 per million pages before, and $21,789.18 / 5,184 = $4.20 now.

Add the undrawn scheduler index, $13,385 a month, to both. The real months are about $72,237 and $35,174. The request bytes add under 3% to either.

So the real cost per million pages falls from about $13.93 to $6.79, 51% less. That is the number to say in an interview.

The next cut is that index: keep due URLs in sorted files per scheduler partition, with a heap of hosts in memory. That saves about $13,400 a month.

Stay provisioned: at a flat 12,000 writes a second, on-demand would cost $19,440 a month, against $11,232.

Press 3,200, the next crawl schedule. The Fetchers saturate: 30 tasks give 30 x 99.5 = 2,985 pages a second, against 3,200.

Read the stage's warnings. The ready queue's backlog grows by about 3,200 - 2,985 = 215 a second.

The trade-off:

A file is not stored until it fills or its 30-second timer fires. So pages are marked fetched only after their file is written.

A PUT per page, or a file per 2,000 pages

1. A PUT per page is 5.18 billion PUTs a month. At $0.005 per 1,000, that is $25,920.
2. A file of 2,000 pages is 97.7 MiB, so the store gets 1 PUT a second. The URL item keeps the file and offset.
3. Pages are marked fetched only after their file is stored. A crash brings them back when their leases end: duplicates, never losses.

Stage 4: WARC files and an internet gateway

• Load: 2,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $22k/mo

• Page store (S3): Standard storage holds 241.4 TB.

Check in: Which two lines of the bill fell, and what is the real cost per million pages now?

One URL through every state

The interviewer asks: A fetcher crashes halfway through a file. What is lost, and what is fetched twice?

A crawler runs for months on many tasks, so something always crashes. A URL's status in the table says what a crash leaves behind.

Crashes are not in the simulation, so we work this by hand.

Discovered: a page links to the URL. The dedup worker checks the Bloom filter.

If the filter says absent, the worker does a conditional put of the URL item, and only then adds the URL to the filter. Status: queued.

Never add to the filter first. A crash after the add, before the put, would hide that URL until the next rebuild.

A crash after the put, before the add: next time the filter says absent, the put fails, and 1 write unit is wasted. Nothing is lost.

A crash before the put: the URL is not stored. It comes back the next time any page links to it.

Leased: the scheduler puts it on the ready queue, with a lease that ends in 5 minutes.

Two clocks guard a fetch. The ready queue hides a message for 60 seconds, which covers only the fetch: the fetcher deletes it once the fetch is done.

So about 2,000 x 1.005 = 2,010 messages are in flight, far under the queue's cap of about 120,000. The lease covers the file.

Fetched: the page goes into the task's file. A 30-second flush timer stores a part-full file, so no page waits near its lease.

Only after the file is stored does the task mark its pages fetched, with the file, offset, content hash and next due time.

If a fetcher dies, a fetch in progress reappears after 60 seconds. Pages fetched but not stored come back when their leases end.

So a crash gives duplicates, never losses.

A failed fetch goes back to queued with a later time: after 1, 2, then 4 minutes. After 5 failures, the URL is dead until the next cycle.

Recrawl: the due time follows how often the page changes. If it changed c times in its last n fetches, revisit after about interval x n / c.

We keep that between 1 day and 60 days. A conditional GET turns an unchanged page into a 304, with no body.

The trade-off:

Duplicates cost fetches and storage, and false positives cost new URLs. Neither loses a page we already hold.

Check in: A fetcher dies with half a file in memory. Say what happens to those pages, and why the URL table never says fetched for them.

The data model and the URL

The interviewer asks: Walk me through the data model. When are two URLs the same URL?

None of these parts breaks under load, so no stage is about them. An interviewer asks about each one, so we answer each in a line or two.

Normalise every URL before any check: lowercase the host, drop the fragment and the default port, sort query parameters, and strip utm_ parameters.

URL table, keyed by a hash of the URL: the URL, host, status, priority, last fetched, next due, content hash, simhash, file and offset, failures.

Each item is about 300 bytes. An unfetched one expires after 6 days, which keeps the table near 10 billion items, 2,800 GiB.

A host table, not drawn, keeps robots.txt and its fetch time, crawl-delay, last fetch, response time and failure state.

The page store keeps WARC files of 2,000 pages. The URL item points to its file and offset.

Control API: POST /seeds, POST /hosts/{host}/block, GET /urls/{hash} and GET /stats.

Exact duplicate pages: a SHA-256 of the normalised body sits on the URL item, so an unchanged page is not stored again.

Near duplicates: a 64-bit simhash, where pages count as near if 3 bits or fewer differ. Manku and colleagues used it on 8 billion pages.

Finding near duplicates is a batch job per crawl, not a step on the fetch path.

The link graph: 25 links x 2,000 pages = 50,000 edges a second, 130 billion a month.

At about 10 bytes an edge compressed, that is 1.3 TB a month, in batched columnar files in S3. It is not drawn.

The trade-off:

Each choice has a price. Normalising too hard merges pages that differ, and too loosely crawls one page under many names.

Check in: Two links differ only in a utm_source parameter and a #section. Is that one URL to the crawler? And what if two different URLs serve the same page?

Say this in 45 minutes

The interviewer asks: What fails in this crawler, and what does the web see?

A design that works on a good day is half an answer. The interviewer asks what fails, and how the crawler treats the sites it visits.

DNS: the VPC resolver allows 1,024 packets a second per network interface. A task's 69.0 pages a second send 138 queries; a caching resolver such as Unbound adds room.

Crawl traps: at most 16 links deep, 2,048 characters a URL, 100,000 pages a host, and no path repeating a segment 3 times.

Fetch rules: at most 5 redirects, 5 seconds to connect and 30 in all, bodies cut at 2 MiB, and HTML only.

Priority: PageRank computed weekly on the link graph, or OPIC, which passes each page's importance to its links during the crawl.

At least 20,000 back queues, spread over scheduler partitions by host. A dead partition's hosts move to a standby through a 30-second lock.

JavaScript pages: a headless browser costs about 1 second of CPU a page. Rendering 5% of pages, 100 a second, needs about 100 vCPU.

Ethics: a User-Agent with a contact URL, back off on 429 and 503, keep an opt-out list, and never crawl behind logins.

A Bloom shard fails: until its replica takes over, its third of the checks go to the URL table. That is 13,333 extra writes a second against 12,000 spare.

Retention: 241.40 TiB of files a month. Keep 2 cycles in S3 Standard, about $11,370 a month, and older ones in Glacier, about $989 a cycle.

Geo fetchers take hosts near their Region. Vendor-neutral: Kafka queues, Cassandra with a lightweight transaction as the conditional put, and MinIO for files.

Watch pages a second, fetch p99, hosts in rotation, frontier age and dollars per million pages. Alert when pages a second stay under 90% for 10 minutes.

Say it out loud: "A PUT per page and a gigabyte through NAT were 63% of the drawn bill. With the scheduler index, the real cost is $6.79 a million."

Minutes 0 to 5: requirements. Pages a month, freshness and politeness. Ask the size.

Minutes 5 to 10: the numbers. 2,000 pages a second, flat. 50 KiB and 25 links a page, and 20,000 hosts in rotation.

Minutes 10 to 17: the frontier. Priority, a back queue per host, robots.txt, and the URL's states.

Minutes 17 to 24: fetchers. Little's law, DNS and politeness, then the first design.

Minutes 24 to 31: dedup. A write per link breaks at 715 pages a second, 1.4 times the first month. Then the Bloom filter and its rebuild.

Minutes 31 to 37: the bill. WARC files and no NAT: $4.20 per million on the canvas, $6.79 with the index.

Minutes 37 to 45: content dedup, recrawl, traps, crashes, JavaScript and ethics.

The trade-off:

Each answer has a price. Trap rules skip some real pages, and politeness makes the crawl wait on slow hosts.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.