Layer 3 · Go deeper · 11 min
Go deeper
Size it, build it, then make the calls an interviewer will push you on.
Back of the envelope
Size it up
Tap through each step of the arithmetic.
How many “seen this URL?” checks a second?
How big is the set of every URL you’ve seen?
How many nodes, and how many open connections?
Build-up · 5 steps
Build the high-level design
One functional requirement at a time, ending with a loop that works at a few hundred pages a second.
Step 1 of 5
Crawl continuously from seeds
The whole crawler is one loop: take a URL, fetch it, store the bytes, pull out the links. With a FIFO frontier it’s a breadth-first search, fine for thousands of pages but rude, unprioritised and forgetful.
6 interview moments
You’re the candidate
The interviewer pushes on the hard parts. Pick an approach and see how it holds up.
Deep dive 1 of 6
Interviewer
“Fetch the most valuable URL next, but never hit a host you fetched two seconds ago. How do you build the frontier?”
Your move. Pick an approach:
Deep dive 2 of 6
Interviewer
“Every page brings about 50 links, so 580,000 checks a second against 100 billion URLs. How do you answer “seen it?””
Your move. Pick an approach:
Deep dive 3 of 6
Interviewer
“One wire-service story runs on fifty news sites, each with a different ad slot. How do you avoid storing it fifty times?”
Your move. Pick an approach:
Deep dive 4 of 6
Interviewer
“One machine can’t crawl 11,600 pages a second. How do you split the work across 100 nodes?”
Your move. Pick an approach:
Deep dive 5 of 6
Interviewer
“Suppose the index holds 10 billion pages and you can afford 1 billion fetches a day. Which get fetched today?”
Your move. Pick an approach:
Deep dive 6 of 6
Interviewer
“A calendar links to “next month” forever, and faceted search makes 1,024 URLs per category. How do you stop traps eating the crawl?”
Your move. Pick an approach:
Build-up · 8 steps
Follow one URL through the crawler
Each of about 100 nodes runs this stack for its slice of hosts. Only the URL exchange, the shared stores and the event log cross machines.
Step 1 of 8
Schedule
Seeds, sitemaps and feeds, plus the scheduler’s due rows from the URL database, enter the owning node’s frontier with a priority from importance, domain budget and staleness.