Layer 3 · Go deeper · 9 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.
1 billion fetches a day, 50 billion URLs. How often is each page revisited?
How do you check a new page against 8 billion fingerprints in milliseconds?
Build-up · 5 steps
Work PageRank by hand on four pages
Damping d = 0.85. Each link carries its page’s rank divided by its outlinks, and the random surfer’s jumps give every page a floor.
Step 1 of 5
Four pages, five links
A links to B and C, so each of those links carries half of A’s rank. B, C and D have one outlink each and pass on all of theirs. Nothing links to D.
4 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 4
Interviewer
“Your web index covers hundreds of billions of pages and must be split across machines. How do you partition it?”
Bazaar’s 4 shards split products by hash(_id), a document partition. At web scale, splitting by term looks tempting.
Your move. Pick an approach:
Deep dive 2 of 4
Interviewer
“Your batch pipeline takes 2–3 days to index a new page. How do you make results fresher?”
Each day several billion documents, plus the existing repository, go through about 100 MapReduces.
Your move. Pick an approach:
Deep dive 3 of 4
Interviewer
“One press release runs on 500 news sites, each copy with its own ads and timestamps. How does the crawler spot the copies?”
Your move. Pick an approach:
Deep dive 4 of 4
Interviewer
“Every query fans out to 1,000 leaf shards, and each leaf is slow 1% of the time. How do you keep latency down?”
Your move. Pick an approach:
Build-up · 6 steps
Serve one query across 1,000 shards
One query’s path, after Google’s 2003 cluster paper and The Tail at Scale. A cache hit stops at step 3; a miss fans out to every leaf.
Step 1 of 6
Pick a cluster and front end
DNS picks a nearby cluster and a load balancer picks a front-end server, the Google Web Server in 2003, which coordinates the whole query.