← all topics Web crawler board · say it in this order 1 Problem2 Entities + API 3 High-level design4 Deep dives 5 Final + levelsreset

Design a web crawler: seed URLs in, text out

10B pages · under 5 days · 1 request/s per domain · 3,750 pages/s per machine, 8 machines · board rules, one idea per line
SAY THIS SENTENCE FIRST

"A crawler is a data pipeline, not a user-facing service: seed URLs in, text out. I split it into stages joined by queues so any stage can fail and retry alone, I stay polite to every site (obey robots.txt, one request per second per domain), and I let the bandwidth math size the fleet for 10B pages in 5 days."

STEP 1 OF 5

Understanding the problem

5 min
  • Ask what the crawl is for. A search engine indexes and ranks pages; an LLM lab wants raw text. This design extracts text from the web to train an LLM.
  • Say out loud that no crawler reaches every page. The goal is the vast majority.
  • Ask whether seed URLs are given (almost always yes). If not, start from popular search engines, news sites, social media and web directories.

Functional Requirements

  1. Crawl the web starting from given seed URLs.
  2. Extract the text from each page and store it for later processing.

Below the line (out of scope):

  • Processing the text (the training itself).
  • Non-text content: images and video.
  • Pages rendered by JavaScript, and pages behind a login.
  • Security against malicious actors.
  • Cost.
  • Legal and privacy compliance.

Non-Functional Requirements

Do the scale math first, because it shows where the simple design breaks
  • Average 2 MB transferred per page (HTML plus inline resources), a worst case for bandwidth planning. HTML alone is ~30 KB.
  • 10B × 2 MB = 20 PB transferred: a bandwidth number, not a storage one.
    • Stored raw HTML: 10B × ~30 KB = 300 TB. Extracted text at 5 to 10 KB a page: 50 to 100 TB.
  • Politeness caps one domain at 86,400 × 5 = 432,000 pages in the 5 days.
    • A domain with 1M URLs needs 11.6 days at 1 request/s, which is why the goal is the vast majority of pages.
  1. Fault tolerant: after a failure the crawl resumes without losing progress.
  2. Polite: obey robots.txt and never overload a site.
    • 1 request/s per domain by default.
  3. Efficient: the crawl finishes in under 5 days.
  4. Scalable: 10B pages.
    • Ask about scale first. It shapes the database and the architecture.
DONE WHEN: the interviewer has heard "text for LLM training, from seed URLs", "10B pages in under 5 days" and "polite: robots.txt and 1 request/s per domain". Those three numbers drive every deep dive.
STEP 2 OF 5

Entities + system interface

5 min

Defining the Core Entities

  • URL record (Metadata DB): url, links to the raw HTML and the extracted text in S3, content hash, depth, status, attempts, next_attempt_at.
    • ~300 B a row × 10B = ~3 TB of URL rows.
    • Status: discovered, pending, fetched, duplicate, blocked, skipped or dead.
  • Domain record (Metadata DB): parsed robots.txt rules, crawl delay, lastCrawlTime.
  • Queue message: a URL reference.
  • The URL and Domain records live in a Metadata DB that the fault-tolerance dive introduces; the high-level design in step 3 does not need it yet.

API or System Interface

Input:  seed URLs
Output: extracted text, stored for later processing
// no user-facing API: a system interface and a data flow

1. Take a URL from the frontier; resolve its IP through DNS
2. Fetch the HTML
3. Extract the text
4. Store the text
5. Extract the links; add them to the frontier
6. Repeat until the frontier is empty
  • This question has no API: the interface is seed URLs in and extracted text out.
  • The data flow is six steps: take a URL and resolve DNS, fetch, extract text, store it, add the links to the frontier, repeat.
  • Write the data flow on the board before any boxes, because the high-level design follows it step by step.
DONE WHEN: the six data-flow steps are on the board and you have said "no API, seed URLs in and text out" inside 5 minutes.
STEP 3 OF 5

High-level design

10 min, end to end, no dives yet

1) Crawl from seed URLs

High-level design: seed URLs in, text out SeedURLs fill the FrontierQueue. The FrontierQueue delivers a URL to the one Crawler, which resolves the IP via DNS, fetches the HTML from the Webpage, stores the text in S3TextData and pushes the new links back to the FrontierQueue, until the queue is empty. 1) Crawl from seed URLs Data flow: take a URL from the frontier, resolve its IP, fetch the HTML, extract the text, store it, add the new links, repeat until the frontier is empty. system boundary SeedURLs given as input FrontierQueue Kafka, Redis or SQS(decided later) url url url Crawler DNS, fetch, extracttext and links S3TextData extracted text DNS domain nameto IP Webpage externalweb server 1. SeedURLsfill theFrontierQueue 2. FrontierQueuedelivers a URLto the Crawler 3. Crawlerresolves the IPvia DNS 4. Crawler fetchesthe HTML fromthe Webpage 5. Crawler storesthe text inS3TextData 6. Crawler pushes the new links to the FrontierQueue then repeat until the FrontierQueue is empty the not-so-happy paths: the one Crawler does DNS, fetch, text extraction and link extraction: a failure anywhere loses that page's progress.fetching fails most often: sites are down, slow, or serve huge pages.
  • Seed URLs go into the Frontier Queue, the list of URLs to crawl.
    • Kafka, Redis or SQS; the fault-tolerance dive picks one.
  • The Crawler takes a URL from the Frontier Queue and resolves its IP through DNS.
    • DNS caching comes up in the scale dive.
  • The Crawler fetches the HTML from the Webpage, an external server outside the system boundary.
  • The Crawler extracts the page's links and pushes them back onto the Frontier Queue.
  • The loop repeats until the Frontier Queue is empty.

2) Extract and store text

High-level design: extract and store text The FrontierQueue delivers a URL to the one Crawler, which fetches the HTML from the Webpage, extracts the text from it and stores the text in S3TextData for later processing. 2) Extract and store text The Crawler already holds the fetched HTML: it pulls the text out and writes it to blob storage for later processing. system boundary FrontierQueue URLs to crawl url url url Crawler fetch, extract textand links S3TextData extracted textGCS or Azure Blob are fine too Webpage externalweb server 1. FrontierQueuedelivers a URLto the Crawler 2. Crawler fetchesthe HTML fromthe Webpage 3. Crawler extractsthe text and storesit in S3TextData the not-so-happy path: one Crawler does DNS, fetch, text extraction and link extraction, so one failure loses all of it.
  • The Crawler extracts the text from the fetched HTML.
  • The text goes to S3 Text Data, blob storage that is cheap, durable and scales.
    • GCS or Azure Blob are fine too.
  • One Crawler does DNS, fetch, text and links, so one failure loses all of it.
    • The fault-tolerance dive handles it.
DONE WHEN: both requirements have a path (Frontier Queue, Crawler, DNS, Webpage, S3 Text Data) and you have said out loud that the single Crawler does too much.
STEP 4 OF 5

Potential deep dives

~20 min, interviewer steers
TRIGGER: "what happens when a crawler crashes" / "how do you not lose progress"

1) Fault tolerance: how does one failure not lose progress?

PIPELINED STAGES · URL FETCHER + PARSER WORKER · QUEUES CARRY URL IDS · SQS
Fault tolerance: pipelined stages joined by queues The FrontierQueue delivers a url id to a URLFetcher, which fetches the page, writes the raw HTML to S3, sends the url id to the ParsingQueue, marks the URL record fetched and only then deletes the message. A ParserWorker takes the url id from the ParsingQueue, writes the text to S3, records new URLs in MetadataDB and sends their ids back to the FrontierQueue. A failed fetch extends the visibility timeout; a message that never processes goes to the DLQ. 2) Fault tolerance: pipelined stages joined by queues Each stage retries alone and scales alone. Queue messages carry the url id, never the HTML. SQS: per-message visibility timeout, built-in DLQ, managed scaling. FrontierQueue SQS, 14-day retention urlId urlId Webpage external web server URLFetcher fetch, storeraw HTML S3 raw HTML and text,keyed by url id ParsingQueue SQS urlId urlId urlId ParserWorker extract textand links DLQ backstop urlId MetadataDB (URL table) urlId, url, htmlLink, textLink, contentHash,depth, status, attempts, next_attempt_at 1. FrontierQueuedelivers aurl id hidden for the60 s visibility timeout 2. URLFetcherfetches the page 3. URLFetcherwrites raw HTMLto S3 4. URLFetcher sendsthe url id message = url id,never the HTML 5. URLFetcher setsthe URL recordfetched the commit 6. URLFetcherdeletes themessage, last 7. ParsingQueuedelivers theurl id 8. ParserWorker writesthe text to S3 (reads the HTML first) 9. ParserWorker saves the textlink and inserts new URL rows 10. ParserWorker sends the new url ids to the FrontierQueue a. fetch fails: URLFetcherextends the visibility timeout after attempts + 1 on the URL record;base x 2^n with jitter, then SQSredelivers it b. FrontierQueuemoves it tothe DLQ backstop only,maxReceiveCount 50 the not-so-happy paths: a URLFetcher dies mid-fetch: it never deleted the message, so SQS shows it again after the 60 s visibility timeout and another URLFetcher redoes it. The visibility timeout sits above the 30 s fetch timeout, so a slow fetch is not run twice.a crash between steps 3 and 5: the URL is still not fetched, so the fetch repeats into the same url-id keys. The status write in step 5 is the commit.5 real fetch failures (the attempts column, not the receive count): the URLFetcher sets the row dead and deletes the message.a message that fails to process at all: after 50 receives the FrontierQueue moves it to the DLQ.a URL waits longer than 4 days: frontier retention is 14 days, so it outlives the 5-day crawl.a ParserWorker dies: the same, on the ParsingQueue. Changing text extraction later re-runs only the parse stage, not the fetches.
Bad Solution: the one Crawler from the high-level design
  • The one Crawler does DNS, fetch, text extraction and link extraction, so a failure anywhere loses all of it.
    • Fetching fails most: sites are down, slow, or serve huge pages.
Good Solution: pipelined stages joined by Kafka topics
  • Split the Crawler into a fetch stage and a parse stage, joined by Kafka topics, so each stage retries alone and scales alone.
    • Still wrong: Kafka has no per-message delay, so retry backoff is a service you build yourself.
Great Solution: pipelined stages joined by SQS, carrying url ids
  • Split the Crawler into pipelined stages joined by queues (SQS): the URL Fetcher and the Parser Worker.
    • URL Fetcher: fetch the page, store the raw HTML in S3, send the url id to the Parsing Queue.
    • Parser Worker: read the HTML, write the text to S3, push new URLs to the Frontier Queue.
    • Text and URL extraction share one stage. Both are simple.
  • Each stage retries alone and scales alone.
  • A Metadata DB (DynamoDB, or PostgreSQL/MySQL) holds a URL table with the links to the blobs in S3.
  • Queue messages carry the url id (the URL record's id), never the HTML.
    • Queues are bad at large payloads.
  • Changing text extraction (say, adding image alt text) re-runs only the Parser Workers, not the fetches.

Retrying failed fetches: how do you back off, and when do you stop?

ATTEMPTS COLUMN · VISIBILITY TIMEOUT = BASE × 2^N + JITTER · DEAD AFTER 5 REAL FAILURES · 14-DAY RETENTION · DLQ AT 50 AS A BACKSTOP

Sites go down, time out, or return errors. The retry has to survive the URL Fetcher that tried.

Bad Solution: an in-memory timer in the URL Fetcher
  • Retry the fetch after a short in-memory timer.
    • The retry is lost if the URL Fetcher dies.
    • A few seconds is rarely enough for a site that is down.
Good Solution: a Kafka retry topic with hand-built backoff
  • Write failed URLs to a retry topic with the next attempt time in the message, and run a retry service that re-enqueues each URL when it is due.
    • It works, but you build the backoff yourself: Kafka has no per-message delay.
    • Offsets commit per partition, so out-of-order fetches either stall a partition behind one slow URL or, committed ahead, lose URLs on a crash.
Great Solution: SQS visibility timeout plus an attempts column
  • On a failed fetch, add 1 to attempts on the URL record and hide the message for base × 2attempts plus jitter.
    • ChangeMessageVisibility does the hiding: SQS holds the delay, so there is no retry service.
    • Visibility timeout: default 30 s, max 12 hours, and the 12 hours run from the receive.
  • After 5 real fetch failures, set the row dead and delete the message.
    • Count failures in attempts, not in ApproximateReceiveCount: a politeness deferral is also a receive.
  • Set the Frontier Queue's retention to 14 days, because the 4-day default is shorter than the 5-day crawl.
  • A dead-letter queue with maxReceiveCount 50 catches only messages that fail to process at all.

A URL Fetcher dies mid-fetch: why is the URL not lost?

STORE, THEN COMMIT, THEN DELETE · VISIBILITY 60 S OVER A 30 S FETCH TIMEOUT · IDEMPOTENT WRITES KEYED BY URL ID
  • SQS only hides a received message, so a URL Fetcher that crashes before the delete leaves it to reappear for another URL Fetcher.
    • Parser Workers work the same way.
  • Write order: HTML to S3, url id to the Parsing Queue, URL record set fetched (the commit), then delete the message.
    • Marking it first lets a crash before the send leave a fetched page nothing parses.
  • Set the visibility timeout above the fetch timeout plus the writes: 60 s over a 30 s fetch timeout.
    • Otherwise a slow fetch reappears and is fetched twice.
  • Key every write by url id and make it idempotent, so a repeated fetch is harmless.
    • A crash between the send and the delete repeats the fetch; SQS standard is at-least-once anyway.
  • SQS wins over Kafka here because of per-message visibility, the built-in dead-letter queue and managed scaling.
TRIGGER: "how do you not take down a small site" / "what about robots.txt"

2) Politeness: how do you obey robots.txt and never overload a site?

ROBOTS.TXT IN THE DOMAIN TABLE, CACHED 24 H · 1 REQUEST PER CRAWL DELAY · CAP PER IP · SAME-HOST REDIRECTS ONLY
Politeness, first step: robots.txt and a per-domain lock in Redis The FrontierQueue delivers a url id to a URLFetcher, which reads the domain's robots.txt rules and crawl delay from MetadataDB, takes a per-domain lock in Redis, and only if it won fetches the page and updates lastCrawlTime. A disallowed path deletes the message; a lock already taken extends the message's visibility timeout so it retries after the window opens. 3) Politeness, first step: robots.txt and a per-domain lock in Redis robots.txt gives User-agent, Disallow paths and Crawl-delay seconds (not in the standard, Googlebot ignores it, we honor it).One request per domain per crawl delay (default 1 s) across all URLFetchers; throughput comes from millions of domains at once. FrontierQueue SQS urlId urlId URLFetcher many, in parallel MetadataDB (Domain table) domain, robots.txt rules (Disallow),crawlDelay, lastCrawlTime Webpage externalweb server Redis per-domain lock domain:{d}TTL = crawl delay (default 1,000 ms) 1. FrontierQueuedelivers aurl id 2. URLFetcher reads the domain'srobots.txt rules and crawl delay new domain or rules over 24 h old:GET /robots.txt, parse it, store it 3. URLFetcher takes the domain lock SET domain:{d} <fetcherId> NX PX <crawlDelayMs>;never DEL it, the TTL is the spacing 4. URLFetcherfetches the page only if 3 won 5. URLFetcher updateslastCrawlTime A. path disallowed:URLFetcher deletesthe message row blocked B. lock taken: URLFetcher extendsthe visibility timeout(ChangeMessageVisibility) by the key's PTTL plus jitter, so the retrylands after the window opens the not-so-happy paths: two URLFetchers read the same stale lastCrawlTime: only one wins SET NX; the other takes path B.Redis is unreachable: defer (fail closed), never fetch unguarded. TTLs run on the Redis clock, so fetcher clock skew does not matter.robots.txt returns 4xx: everything is allowed. 5xx, 429 or a network failure: the domain is pushed back and its URLs wait. Only a parsed Disallow blocks a URL.thousands of domains share one hosting IP: cap concurrent requests per resolved IP as well.an in-flight message cannot take DelaySeconds (new messages only): defer it with ChangeMessageVisibility, up to 12 hours from the receive.deferral churn: every deferral is a receive. A domain with n waiting URLs costs about n(n+1)/2 receives and fills the ~120,000 in-flight cap. This is why the Domain Scheduler replaces the lock: URLs wait in the database, domains wait in Redis.
Bad Solution: fetch every URL the frontier hands out
  • The Crawler fetches whatever URL comes off the Frontier Queue, with no robots.txt check.
    • It fetches Disallow paths, and nothing spaces its requests to one site.
Good Solution: parse each domain's robots.txt once and keep the rules
  • Fetch a domain's robots.txt the first time the domain comes up, parse it, and store the rules in the Domain table.
    • Still wrong: the rules go stale over a 5-day crawl, and a URL may wait days before its fetch.
    • It says nothing about a robots.txt that errors, or about thousands of domains on one shared-hosting IP.
Great Solution: cached rules with fail-safe errors, a per-IP cap and same-host redirects
  • Store each domain's parsed robots.txt rules in the Domain table and cache them for up to 24 hours (RFC 9309).
    • A 5-day crawl refetches each robots.txt about 5 times.
    • Re-check the cached rules at fetch time; a URL may have waited days.
  • robots.txt lists a User-agent, the Disallow paths and a Crawl-delay in seconds.
    • Crawl-delay is not in the official standard and Googlebot ignores it. We honor it, and default to 1 s.
  • A 4xx robots.txt allows everything; a 5xx, 429 or network failure means push the domain back and wait.
    • Its URLs keep waiting. Only a parsed Disallow marks a URL blocked.
    • Follow up to 5 redirects for robots.txt itself, one hop per claim.
  • Cap concurrent requests per resolved IP, because thousands of domains can share one shared-hosting IP.
    • The DNS cache already has the IP.
  • Follow a page's redirect only within the same host, as the domain's next request; a cross-host target is enqueued as a new URL.
    • Inline, it would hit another domain without its crawl delay or robots.txt check.

Crawl delay: how do two URL Fetchers not hit one domain inside its delay?

ONE CLOCK PER DOMAIN IN REDIS · DOMAIN SCHEDULER: SCHEDULE DOMAINS, NOT URLS · NEXT TIME = NOW + CRAWL DELAY + JITTER
Bad Solution: each URL Fetcher remembers its own last request per domain
  • A URL Fetcher waits out the crawl delay only for its own requests.
    • Any URL Fetcher can pick up any domain's URL, so several hit one site at once.
Good Solution: a shared per-domain lock in Redis, deferring early URLs
  • Take SET domain:{d} <fetcherId> NX PX <crawlDelayMs> before the fetch. The winner fetches.
    • The key is a spacing token, never deleted: deleting it early allows a second request inside the delay.
    • Redis TTLs run on the server's clock, so crawler clock skew does not matter. Redis unreachable: defer, never fetch unguarded.
  • The loser defers the message with ChangeMessageVisibility by the key's remaining TTL (PTTL) plus jitter.
    • Without jitter, every URL Fetcher waiting on one domain retries at the same instant and all but one fail again.
  • The cost: a domain with n queued URLs is received about n(n+1)/2 times to fetch n pages.
    • Each round one URL fetches and the rest re-hide. 10,000 URLs: ~50M receives.
    • Deferred messages stay in flight; big domains hit the ~120,000 in-flight cap, and past it ReceiveMessage returns OverLimit for the whole fleet.
Great Solution: the Domain Scheduler
  • Schedule domains, not URLs: the Domain Scheduler keeps each domain in a Redis sorted set scored by the earliest time it may be hit.
    • URLs wait as pending rows in the Metadata DB; domains wait in the sorted set ready, one member per domain with waiting URLs, scored in Redis server time.
    • It is the front-queue/back-queue design of Mercator (Heydon and Najork's crawler), with Redis as the heap.
  • A URL Fetcher claims a due domain, not a URL, and sends one request per claim.
  • After the fetch the Domain Scheduler rescores the domain to now + crawl delay + jitter.
  • Each URL is received from SQS once and no URL Fetcher holds a message, so there is no re-receive churn and no ~120,000 in-flight cap to hit.
  • The score replaces a per-domain lock: no domain gets two requests in one crawl delay.

The Domain Scheduler: how do URLs wait in the database and domains wait in Redis?

CONDITIONAL INSERT · REDIS FIRST, ROW SECOND, DELETE LAST · CLAIM WITH A LEASE AND A FENCE · RESCORE ONLY WITH THE CLAIM TOKEN
The Domain Scheduler: URLs wait in the database, domains wait in Redis A ParserWorker sends a new url id to the FrontierQueue, which delivers it to the DomainScheduler. The DomainScheduler checks robots.txt rules in the Domain table, adds the domain to the Redis ready set and flips the URL row to pending. A URLFetcher claims a due domain in Redis, reads that domain's lowest-depth pending URL, fetches the page, writes the HTML to S3, sends the url id to the ParsingQueue, sets the row fetched and reports back; the DomainScheduler then writes lastCrawlTime and reschedules the domain. The Domain Scheduler: URLs wait in the database, domains wait in Redis One receive per URL, no URLFetcher holds an SQS message, and the ready score spaces each domain's requests by its crawl delay, so no lock and no deferrals. ParserWorker after the conditionalinsert (row: discovered) FrontierQueue SQS, intake urlId urlId Webpage external web server DomainScheduler reads theFrontierQueue Redis ready: sorted set,one member perdomain with work,score = earliesttime the domainmay be hitpending:{domain}:URL counter URLFetcher claims domains,not URLs MetadataDB (Domain table) robots.txt rules, crawlDelay,lastCrawlTime MetadataDB (URL table) status, attempts, next_attempt_atindexed by (domain, status, depth) S3 raw HTML ParsingQueue urlId urlId 1. ParserWorkersends the url id 2. FrontierQueuedelivers it to theDomainScheduler 3. DomainScheduler checksrobots.txt rules Disallow: row blockeddepth or trap cap: skipped 4. DomainScheduleradds the domain one Lua script:INCR pending:{domain}ZADD ready NX <now> <domain> 5. DomainScheduler flipsthe row to pending discovered -> pending;then DeleteMessage:Redis first, row second,delete last 6. URLFetcherclaims a duedomain score due now;new score =now + lease;tokenclaim:{domain}lease = max(60 s,crawlDelay +fetch timeout) 7. URLFetcher reads the domain'slowest-depth due pending URL 8. URLFetcher fetches the page one request per claim; rules missing orover 24 h: it is the robots.txt fetch.Fence: no send if the claim is olderthan lease - max(crawlDelay, fetchtimeout). ~10 MB check reads the GET'sContent-Length (no HEAD) 9. URLFetcherwrites the HTMLto S3 10. URLFetchersends the url id 11. URLFetcher sets the row fetched,only if still pending (the commit) 12. URLFetcher reports thefetch to the DomainScheduler 13. DomainSchedulerwriteslastCrawlTime only ever later 14. DomainSchedulerreschedulesthe domain only if claim:{domain}is still thisfetcher's; DECRBY therows that leftpending; ZADD ready XXnow + crawl delay +jitter, even at 0 the not-so-happy paths: URL statuses: discovered (conditional insert, not yet accepted), pending (the DomainScheduler accepted it), fetched (HTML in S3, url id on the ParsingQueue), duplicate (content hash seen), blocked (a parsed robots.txt Disallow), skipped (depth, trap caps, size over ~10 MB), dead (5 real failures).a send after the insert is lost: a sweeper re-enqueues discovered rows older than an hour.a URLFetcher crashes: the domain's score is now + lease, so it comes due when the lease ends and another URLFetcher claims it; the URL is still pending. A crash before step 11 refetches into the same url-id keys; the status write is the commit.a paused URLFetcher: the fence (claim age timed from when the claim call was sent) stops a late send; a zombie's writes hit the fetched-only-if-pending update and url-id keys, and its expired claim token stops it rescheduling the domain. One gap stays: a pause between the fence check and the send itself cannot be fenced.a crash before the row turns pending redelivers the message and INCRs twice: a URLFetcher that finds no pending row at all resets the counter from a DB count.a fetch fails: attempts + 1 and next_attempt_at = now + base x 2^n with jitter; after 5 real failures the row goes dead and the counter drops. A claim that finds only not-yet-due rows rescores the domain to its earliest next_attempt_at.a whole domain fails (timeouts, 5xx, robots.txt unreadable): its score is pushed back exponentially and its URLs wait; rules refresh every 24 h.a redirect: same host, it is the domain's next request (target row straight to pending, with an INCR); a cross-host target is enqueued as a new URL; a robots.txt redirect is followed one hop per claim.a domain leaves ready only inside a claim, once it is due, at a count of 0. A reconcile sweep every few minutes re-adds any domain with pending rows but no ready member, so a race can delay a URL, never strand it.Redis is lost: rebuild ready and the counters from the URL table (count pending per domain), score = max(now, lastCrawlTime + crawlDelay). After a rebuild or a failover, hold new claims for one max crawl delay plus 30 s, since a fetch in flight at the loss has not written lastCrawlTime yet.sizing: millions of domains x ~100 B = hundreds of MB; 30,000 claims/s fits one Redis, or shard ready by domain hash.
  • A Parser Worker's conditional insert writes the URL row discovered, then sends the url id to the Frontier Queue.
    • The Frontier Queue (SQS) stays as the durable intake, read by the Domain Scheduler instead of the URL Fetchers.
    • A sweeper re-enqueues discovered rows older than an hour, so a crash between the insert and the send loses nothing.
  • The Domain Scheduler checks robots rules, INCRs the domain's pending-URL counter, ZADDs the domain NX, flips the row to pending, then deletes the message.
    • A row no longer discovered is a duplicate delivery: delete the message and stop.
    • A parsed Disallow marks the row blocked; the depth limit or a trap cap marks it skipped.
    • One Lua script: INCR pending:{domain} and ZADD ready NX <now> <domain>. NX never pulls a domain's time earlier, and a domain leaves ready only inside a due claim, so re-adding it at now is safe.
    • Redis first, row second, delete last: a crash re-runs the step and over-counts, which is harmless.
  • A URL Fetcher claims a due domain: its score moves to now + lease and it gets a claim token.
    • Lua: ZRANGEBYSCORE ready -inf <now> LIMIT 0 k; ZREM a member whose counter is 0; move each other to now + lease (ZADD ready XX) and set claim:{domain} = the fetcher's id, same expiry.
    • Lease = max(60 s, crawlDelay + fetch timeout). No other URL Fetcher sees the domain until it ends.
    • Fence: no send once the claim is older than lease minus max(crawlDelay, fetch timeout), 30 s with a 30 s fetch timeout, timed from the claim call. A request that is sent starts at least one crawl delay before the lease ends and finishes before it.
  • One request per claim: the domain's lowest-depth due pending row, or its robots.txt.
    • A cached Disallow marks the row blocked with no request made.
    • Rules missing or older than 24 h: the request is the robots.txt fetch. A 5xx, 429 or network failure pushes the domain back; its URLs stay pending.
    • Read Content-Length from the GET's response and abort past ~10 MB (skipped); a HEAD would be a second request.
    • Only not-yet-due rows: rescore to their earliest next_attempt_at. No row at all: reset the over-counted counter from a DB count.
  • Store before commit: HTML to S3 keyed by url id, url id to the Parsing Queue, then the row set fetched only if still pending.
    • A crash before the status write leaves the row pending; the refetch overwrites the same keys.
    • A same-host redirect target's conditional insert goes straight to pending in this domain (with an INCR).
  • Fetch failure: attempts + 1 and next_attempt_at = now + base × 2n with jitter; the row stays pending.
    • After 5 real failures the row is dead and the counter drops.
    • A whole domain failing (timeouts, 5xx) pushes the domain's score back exponentially instead.
  • After each fetch the Domain Scheduler writes lastCrawlTime and rescores the domain, only if the claim token is still this fetcher's.
    • Lua: check claim:{domain}, DECRBY pending:{domain} by the rows that left pending, then ZADD ready XX <now + crawlDelay + jitter>, even at 0. The next claim removes a domain at 0.
  • URL Fetcher crash or pause: the domain comes due again when the lease ends, and the URL is still pending.
    • A fetcher paused past its fence sends nothing. A late zombie's claim token has expired, so it cannot rescore the domain.
    • One gap stays open: a pause between the fence check and the socket write. A remote site cannot check a fencing token.
  • A reconcile sweep every few minutes re-adds any domain with pending rows but no ready member (ZADD NX), so a race can delay a URL, never strand it.
  • Redis loss: rebuild ready and the counters from the Metadata DB, each score max(now, lastCrawlTime + crawlDelay), never plain now.
    • After a rebuild or a failover (an async replica may drop the newest claims), hold new claims for one max crawl delay plus 30 s: a fetch in flight at the loss has not written lastCrawlTime yet.
    • A replica plus AOF makes a rebuild rare. Millions of domains × ~100 B = hundreds of MB; 30,000 claims/s fits one Redis (or shard ready by domain hash).
TRIGGER: "can you really do 10B pages in 5 days" / "how many machines"

3) Scale: how do you crawl 10B pages in under 5 days?

200 GBPS / 8 / 2 MB = 12,500 PAGES/S · 30% USABLE = 3,750 · 8 MACHINES = 3.9 DAYS
Scale: 10B pages in under 5 days, without refetching or reparsing A url id from the FrontierQueue reaches one of 8 URLFetchers through the DomainScheduler. The URLFetcher resolves the IP through its DNS cache, fetches the page, writes the raw HTML to S3 and sends the url id to the ParsingQueue. Auto-scaled ParserWorkers check the content hash in MetadataDB, write the text to S3, check each new URL with a conditional insert and send the new url ids back to the FrontierQueue. 4) Scale: 10B pages in under 5 days, without refetching or reparsing 200 Gbps / 8 bits per byte / 2 MB per page = 12,500 pages/s per machine; 30% usable = 3,750 pages/s.10B / 3,750 = 2,666,667 s = 30.9 days on one machine. 8 machines: 3.9 days, under 5. Fleet: 30,000 pages/s. FrontierQueue SQS urlId urlId urlId URLFetcher x 8 200 Gbps each, I/O boundDNS cache by record TTL ParsingQueue SQS urlId urlId urlId ParserWorker auto-scaled onParsingQueue depth(Lambda, ECS on Fargate) S3 raw HTML and text DNS several resolversand providers Webpage external web server MetadataDB (URL table) url, contentHash (UNIQUE),depth, status 1. url id, via theDomainScheduler 2. URLFetcherresolves the IP cache first,DNS on a miss 3. URLFetcherfetches theWebpage 4. URLFetcher writesraw HTML to S3 5. URLFetchersends the url id 6. ParsingQueuedelivers it 7. ParserWorkerchecks thecontent hash seen: skip parsing 8. ParserWorker writesthe text to S3 9. ParserWorkerchecks eachnew URL normalize, thenconditional insert;known URL or trapcap: skip 10. ParserWorker sends the new url ids, depth + 1, to the FrontierQueue not drawn: the FrontierQueue feeds the DomainScheduler,and each URLFetcher claims a due domain from it the not-so-happy paths: one slow site does not stall a machine: 3,750 pages/s at 1 to 2 s per fetch is 3,750 to 7,500 open fetches per machine.DNS is a real bottleneck: Mercator measured 87% of each thread's time on DNS before a custom resolver, 25% after. Cache by the record's TTL and cache NXDOMAIN too, or every link to a dead domain costs a lookup. Spread lookups over several resolvers and providers.one URL, many spellings: normalize first (lowercase scheme and host, drop the default port and #fragment, sort query parameters, strip utm_* and gclid).two parsers find the same URL: a conditional insert of a discovered row (INSERT ... ON CONFLICT DO NOTHING, or attribute_not_exists(url_hash)); only the winner enqueues. A sweeper re-enqueues discovered rows older than an hour if that send was lost.two URLs serve the same page: the contentHash key is UNIQUE (DynamoDB: a ContentHash table with attribute_not_exists(hash)); the loser is a duplicate. A Bloom filter is the faster alternative (10B at 1% = ~12 GB), but a false positive skips a unique page for good. A content hash catches byte-identical pages only; near-duplicates need SimHash or MinHash, usually offline.crawler traps: depth 15 to 20 stops deep traps; a URL length cap (~2,000 characters), a repeated-path-segment check and a per-domain URL budget stop wide ones.
  • Do scaling last, once you know every stage.
Bad Solution: one fetch machine
  • Run the crawl on one machine: even at full line rate, 12,500 pages/s, 10B pages take 9.3 days.
    • About twice the 5-day target.
Good Solution: size the fleet at full line rate
  • Size the fleet at full line rate, 12,500 pages/s per 200 Gbps machine, so 2 machines finish in 4.6 days.
    • Still wrong: latency, DNS, politeness and retries leave about 30% of line rate usable, so 2 machines really take about 15 days.
Great Solution: size from usable bandwidth, and scale Parser Workers apart
200 Gbps / 8 bits per byte        = 25 GB/s per instance
25 GB/s / 2 MB per page           = 12,500 pages/s at full line rate
12,500 × 30% usable              = 3,750 pages/s   // latency, DNS, politeness, retries
10B / 3,750                       = 2,666,667 s = 30.9 days on one machine
30.9 days / 8 machines            = 3.9 days, under 5
8 × 3,750                         = 30,000 pages/s for the fleet
  • URL Fetchers are I/O bound: one 200 Gbps instance at 30% usable fetches 3,750 pages/s.
    • A network-optimized instance, c6in.32xlarge or c7gn.16xlarge class.
  • 10B pages take 30.9 days on one machine, so 8 machines finish in 3.9 days.
  • Parser Workers auto-scale on the depth of the Parsing Queue (Lambda, or ECS on Fargate).
  • 30,000 pages/s at 1 to 2 s per fetch is 30,000 to 60,000 open fetches, 3,750 to 7,500 per machine (Little's law).
    • At 1 request/s per domain, 30,000 pages/s needs 30,000+ domains every second: throughput comes from crawling millions of domains at once.

DNS: how do you keep lookups from becoming the bottleneck?

CACHE FOR THE RECORD'S TTL, NXDOMAIN TOO · SEVERAL RESOLVERS AND PROVIDERS
  • DNS is a real bottleneck at thousands of lookups per second over millions of domains.
    • Mercator measured 87% of each thread's time in DNS with the stock resolver, and 25% after a custom multi-threaded resolver.
  • Cache lookups in the URL Fetchers for the record's TTL, with a floor of a few minutes.
  • Cache NXDOMAIN failures too, or every link to a dead domain costs a lookup.
  • Spread lookups across several resolvers and DNS providers, round-robin.
  • Raise a provider's limits with money.

URL dedup: how do you avoid fetching one URL twice?

NORMALIZE · CONDITIONAL INSERT DECIDES · STATUS CHECK ON RECEIVE
  • Normalize the URL first: lowercase scheme and host, drop the default port and the fragment, sort the query parameters, strip tracking parameters.
    • Also resolve relative links and .. and normalize percent-encoding. Tracking parameters: utm_*, gclid.
    • Keep the path's case, http vs https and www: they can differ, and the content hash catches the ones that do not.
  • The insert decides: a Parser Worker enqueues a URL only if its conditional insert won.
    • Postgres: INSERT ... ON CONFLICT DO NOTHING. DynamoDB: a put with attribute_not_exists(url_hash), keyed by a hash of the normalized URL.
    • Check-then-enqueue would let two Parser Workers both enqueue a new URL.
    • The row starts discovered; a sweeper re-enqueues discovered rows older than an hour.
  • A duplicate delivery hits a row that is no longer discovered and is dropped without a fetch.
    • SQS standard can deliver a message twice.
  • At ~50 outlinks a page, Parser Workers check 30,000 × 50 = 1.5M URLs/s against the URL table.
    • Each is a write-sized conditional insert, so a parser-local cache or Bloom filter in front pays off.

Duplicate content: how do you skip a page you already have?

HASH THE CONTENT · UNIQUE KEY, THE INSERT DECIDES · NEAR-DUPLICATES OFFLINE
  • Different URLs can serve identical content: http and https, www, mirror sites.
Bad Solution: rely on URL dedup alone
  • Parse every page whose URL is new.
    • URL dedup cannot see identical content, because the URLs differ.
Good Solution: a Bloom filter of content hashes
  • Hash the fetched content and check RedisBloom (BF.ADD / BF.EXISTS) before parsing.
    • Fast, no false negatives, but a false positive skips a unique page for good, and entries cannot be deleted.
    • 10B entries at 1% false positives is ~9.6 bits each = ~12 GB, one key on one shard.
Great Solution: a content hash with a unique key
  • Hash the fetched content and parse only if the hash's conditional insert won.
  • The key must be unique, or two Parser Workers with the same hash both see "absent" and both parse.
  • Postgres: a UNIQUE index, with ON CONFLICT DO NOTHING on the insert.
  • DynamoDB: a separate ContentHash table keyed by hash with an attribute_not_exists(hash) conditional put.
    • A GSI can neither enforce uniqueness nor read consistently.
  • A content hash catches only byte-identical pages; near-duplicates need SimHash or MinHash, usually offline.
    • Pages that differ by an ad or a timestamp: SimHash on shingles (Hamming distance) or MinHash with LSH, run on the text.

Crawler traps: how do you stop a site that never ends?

DEPTH ON THE URL RECORD · STOP PAST 15 TO 20 · LENGTH CAP, REPEATED SEGMENTS, PER-DOMAIN BUDGET
  • A crawler trap is a site built to keep a crawler busy forever.
  • Store a depth on the URL record (link hops from a seed: seed 0, its links 1) and stop past 15 to 20.
    • A URL keeps the depth of its first discovery; dedup drops later, shorter paths.
  • Depth stops deep traps (calendars, /a/a/a/...) but not wide ones, where session ids or sort orders mint unlimited URLs at one depth.
  • Add a URL length cap (~2,000 characters), a repeated-path-segment check and a per-domain URL budget.
    • Politeness caps a trap's fetches at 432,000 per domain in 5 days; the budget caps its Frontier Queue and URL table growth.

Other dives, one line each:

  • JavaScript pages: a headless browser such as Puppeteer.
  • Monitoring: Datadog or New Relic.
  • Large files: read Content-Length from the GET's headers and abort past ~10 MB.
  • Continual recrawls: a URL Scheduler owns recrawl timing and Parser Workers write URLs to the DB.
  • Priority crawling: several SQS queues by priority.
DONE WHEN: you have split the Crawler into URL Fetcher and Parser Worker behind SQS, said "a URL Fetcher claims a due domain from the Redis ready set, one request per claim, rescored to now + crawl delay", and walked "200 Gbps / 8 / 2 MB = 12,500, 30% = 3,750, 8 machines = 3.9 days".
FLASHCARDS · THE FIVE HARDEST PROBESshow all (interview mode)
A URL Fetcher dies mid-fetch. Why is the URL not lost?
  • Nothing is deleted until the work is stored: the SQS message reappears after its visibility timeout, and under the Domain Scheduler the row is still pending when the lease ends.
  • Write order: HTML to S3, url id to the Parsing Queue, URL record set fetched, then any message delete.
  • Visibility timeout (60 s) above the fetch timeout (30 s), and every write keyed by url id, so the repeat is harmless.
A fetch fails. How do you retry with backoff, and when do you stop?
  • attempts + 1 on the URL record; next try at now + base × 2n with jitter.
  • After 5 real failures the row is dead. Receives do not count, since a politeness deferral is also a receive.
  • Frontier retention 14 days, over the 4-day default. A dead-letter queue at maxReceiveCount 50 is only a backstop.
Two URL Fetchers pick up URLs from the same domain at the same moment. What keeps you polite?
  • Fetchers claim domains, not URLs. A domain sits once in the Redis ready set, and a claim moves its score to now + lease with a claim token.
  • After the fetch the Domain Scheduler rescores the domain to now + crawl delay + jitter, only if the claim token is still this fetcher's.
Walk the math: how many machines to crawl 10B pages in 5 days?
  • 200 Gbps / 8 = 25 GB/s; / 2 MB = 12,500 pages/s; 30% usable = 3,750 pages/s.
  • 10B / 3,750 = 2.67M s = 30.9 days on one machine.
  • 8 machines = 3.9 days, under 5.
  • Parser Workers scale separately on Parsing Queue depth.
A domain has 10,000 URLs in the frontier. What does deferring with ChangeMessageVisibility cost, and what replaces it?
  • Each round one URL fetches and the rest re-hide, so ~n(n+1)/2 = 50M receives.
  • Every deferred message counts toward the ~120,000 in-flight cap, and each deferral is a receive.
  • The Domain Scheduler replaces it: URLs wait in the Metadata DB, a Redis sorted set holds each domain's next allowed time, and a URL Fetcher claims a due domain, so each URL is received once.
STEP 5 OF 5

Final design + what is expected at each level

wrap

Final Design

Web Crawler: final design SeedURLs fill the FrontierQueue, which delivers url ids to the DomainScheduler. The DomainScheduler checks robots rules and flips rows to pending in MetadataDB and adds each domain to the Redis ready set. URLFetchers claim a due domain, read its pending URL, resolve DNS, fetch the page, write HTML to S3, send the url id to the ParsingQueue, commit the row and report back so the DomainScheduler reschedules the domain. ParserWorkers check the content hash, write text to S3, insert new URLs and send the winners back to the FrontierQueue. Web Crawler: final design. Stages joined by SQS, a Domain Scheduler for politeness, 8 URLFetchers crawl 10B pages in 3.9 daysEvery URL ends fetched, skipped, dead after 5 real failures or still pending at day 5, and no domain gets two requests in one crawl delay. SeedURLs given as input FrontierQueue SQS, 14-dayretention urlId urlId DLQ backstop Redis ready: sorted set, one memberper domain with waiting URLs,score = next allowedcrawl timepending:{domain}: URL counter DomainScheduler reads theFrontierQueue URLFetcher x 8 claim domains,not URLsDNS cache byrecord TTL DNS severalresolvers andproviders Webpage externalweb server S3 raw HTML andtext, keyed byurl id MetadataDB URL table: url, htmlLink, textLink,contentHash (UNIQUE), depth,status, attempts, next_attempt_atDomain table: robots.txt rules,crawlDelay, lastCrawlTime ParsingQueue SQS urlId urlId ParserWorker auto-scaled onParsingQueue depth 1. SeedURLs fillthe FrontierQueue 2. FrontierQueuedelivers theurl id 3. DomainSchedulerchecks robots rules Disallow: blocked;depth or trapcap: skipped 4. DomainScheduleradds the domain INCR pending:{domain};ZADD ready NX 5. DomainSchedulerflips the row topending, then deletesthe message 6. URLFetcherclaims a due domain score = now + lease;claim token 7. URLFetcherreads thedomain's lowest-depth duepending URL 8. URLFetcherresolves the IP cache first; NXDOMAINcached too 9. URLFetcherfetches the page one request per claim;fence check first 10. URLFetcherwrites the HTMLto S3 11. URLFetchersends the url idto the ParsingQueue 12. URLFetcher setsthe row fetched ifstill pending (commit) 13. URLFetcherreports the fetchto theDomainScheduler 14. DomainSchedulerreschedulesthe domain and writeslastCrawlTime 15. ParsingQueuedelivers it 16. ParserWorker checksthe content hash conditional put on the UNIQUE key;seen: duplicate 17. ParserWorkerwrites the textto S3 18. ParserWorker inserts each new URL normalized; conditional insert,depth + 1, trap caps 19. ParserWorker sends the url ids whose insert won to the FrontierQueue FrontierQueuemoves a messagethat fails toprocess at allto the DLQ maxReceiveCount 50 the not-so-happy paths: a URLFetcher crashes: the domain's score is now + lease, so it comes due when the lease ends and another URLFetcher claims it; the URL is still pending. A crash before step 12 refetches into the same url-id keys; the status write is the commit.a URLFetcher pauses: no send once the claim is older than lease - max(crawlDelay, fetch timeout); lease = max(60 s, crawlDelay + fetch timeout). A pause between that check and the send itself cannot be fenced.a fetch fails: attempts + 1, next_attempt_at = now + base x 2^n with jitter; dead after 5 real failures.a whole domain fails (timeouts, 5xx, 429, robots.txt unreadable): its score is pushed back and its URLs wait. robots.txt 4xx: all allowed; rules cached up to 24 h.a send after the insert is lost: a sweeper re-enqueues discovered rows older than an hour.a race strands a domain outside ready: a reconcile sweep re-adds every domain with pending rows.Redis is lost: rebuild ready and the counters from the URL table, score = max(now, lastCrawlTime + crawlDelay); after a rebuild or a failover, hold claims for one max crawl delay plus 30 s.shared hosting: cap concurrent requests per resolved IP. A ParserWorker dies: the ParsingQueue redelivers after its visibility timeout.
  • Seed URLs → Frontier Queue (SQS) → Domain Scheduler → URL Fetchers → S3 and Parsing Queue → Parser Workers → S3 text and new URLs.
    • Write order: HTML to S3, url id to the Parsing Queue, URL record set fetched, then any message delete.
    • 8 URL Fetcher machines at 3,750 pages/s each, caching DNS for the record's TTL across several providers.
  • The Domain Scheduler keeps one Redis score per domain, the next time it may be hit; URL Fetchers claim a due domain and send one request per claim.
    • robots.txt rules and crawl delay in the Domain table, cached up to 24 h. Requests also capped per IP.
  • A failed fetch bumps attempts and backs off with jitter; dead after 5 real failures; a dead-letter queue is a backstop only.
    • Frontier retention 14 days.
  • Auto-scaled Parser Workers skip seen content hashes, write text to S3, and enqueue normalized URLs at depth + 1 only if the insert won.
  • Every URL ends fetched, skipped, dead after 5 real failures or still pending at day 5, and no domain gets two requests in one crawl delay.
    • That is the invariant to close on. Skipped by rule covers blocked, skipped and duplicate.

What is Expected at Each Level

  • Mid (E4):
    • Understands the data flow and builds a simple working system, like the high-level design.
    • Knows the basics of politeness and robots.txt.
    • Has some idea of scaling.
    • Not expected to go deep on queues or rate limiting.
  • Senior (E5):
    • Requirements, entities and API: states the purpose (text for LLM training), the two functional requirements and the targets with their numbers, sizes bandwidth apart from storage (20 PB transferred, 300 TB stored), and writes the six-step data flow with the URL and Domain records and a queue message that holds the url id.
    • The high-level design, then detail on politeness and robots.txt.
    • Detail on scaling to finish within 5 days.
    • One answer per deep dive:
      • Fault tolerance: splits the Crawler into a fetch stage and a parse stage joined by queues, so each retries and scales alone, retries failed fetches with growing backoff that survives the URL Fetcher, and recovers a mid-fetch crash by storing before deleting.
      • Politeness: keeps each domain's parsed robots.txt rules in the Domain table, and holds the crawl delay across every URL Fetcher with one shared key per domain in Redis (SET NX PX, never deleted).
      • Scale: walks the bandwidth math to 8 machines in 3.9 days, auto-scales Parser Workers on queue depth, caches DNS, checks the URL table before enqueueing a link, skips content it has already seen (a Bloom filter is acceptable), and stops past a depth of 15 to 20.
  • Staff+:
    • Deep on 3 or more areas, with insight the interviewer did not have.
    • Covering every deep dive above, some at less than full depth, is "a good spot".
    • Requirements, entities and API: names every URL status (discovered, pending, fetched, duplicate, blocked, skipped, dead), which is what lets the closing invariant be stated.
    • Fault tolerance: counts real failures in attempts rather than SQS receives, so a politeness deferral never kills a URL, and raises the Frontier Queue's retention to 14 days.
    • Politeness: replaces the per-domain lock with the Domain Scheduler, and refreshes robots.txt every 24 h with errors that fail safe.
    • Scale: makes URL and content dedup a conditional insert on a unique key, normalizes URLs first, and caps wide traps with a length cap, a repeated-segment check and a per-domain budget.
DONE WHEN: you can point at the final diagram and say, in one breath, stages joined by SQS, url ids in the queues, the Domain Scheduler's ready score per domain, dead after 5 real failures, 8 machines for 3.9 days, and the invariant.