What to fetch next, and how fast? The frontier decides.
A prioritiser ranks URLs by importance and change rate. Per-host queues keep a thousand fetchers off any one small site.
C has three links in, A just one. They nearly tie.
Each link passes its page’s rank, split across its outlinks. A’s one link comes from the top page. Who beats how many.
Shard the index by term or document?
Bad: By term
“chai recipe” asks two shards, but postings cross the network; hot terms overload their owner.
Good: By document
Shards never talk; each scores alone. Google pays the fan-out.
The old pipeline re-ran about 100 MapReduces over the whole repository. A document took 2–3 days.
Caffeine, 2010
Percolator made it incremental: transactions, plus observers that each fire the next step. Median document over 100× faster.
One query, a thousand shards, one merged top 10.
Cache first. On a miss, the root asks one replica of every leaf, merges each local top k, and doc servers add snippets.
74 ms
p99.9 with hedging, down from 1,800 ms
Reading 1,000 Bigtable keys across 100 servers, if a replica hasn’t answered in 10 ms, ask another. Only 2% more requests.
You can’t design Google in 45 minutes. Scope it.
- Pick one: crawler, indexing pipeline or query serving
- Draw the other two as boxes, then go deep
- Cite only what Google publishes, never ranking weights
Remember
Crawl politely from a prioritised frontier. Index by document into random shards, updated incrementally; links give PageRank. Fan each query out to every shard, merge each top k, and hedge against the tail.