Chapter 51: Design Google Search
1. Requirements
Functional Requirements
| Requirement |
Details |
Priority |
| Web Crawling |
Discover and crawl billions of web pages continuously |
P0 |
| Indexing |
Build and maintain inverted index for fast term lookup |
P0 |
| Ranking |
Rank results by relevance (PageRank, ML signals, user intent) |
P0 |
| Query Serving |
Return top 10 results for user queries in <200ms |
P0 |
| Snippet Generation |
Generate contextual snippets highlighting query terms |
P0 |
| Spell Correction |
Suggest corrections for misspelled queries |
P1 |
| Autocomplete |
Suggest queries as user types |
P1 |
| Personalization |
Tailor results based on user history, location |
P1 |
Non-Functional Requirements
| Requirement |
Target |
Interview Callout |
| Latency |
p99 < 200ms |
Critical for user experience; 100ms increase = 20% traffic drop |
| Availability |
99.99% |
Every minute of downtime = millions in lost revenue |
| Scale |
8.5B searches/day, 100B+ indexed pages |
Must scale horizontally; single points of failure unacceptable |
| Freshness |
News within minutes, most content within days |
Balance crawl frequency with politeness; avoid bans |
| Relevance |
Top 3 results satisfy 75%+ queries |
Core business metric; poor relevance = user churn |
| Storage |
Hundreds of petabytes |
Discuss compression, sharding, replication strategies |
Out of Scope
| Image/video search |
Ads bidding/auction system |
Knowledge graph |
| Voice search |
Search analytics dashboard |
Spam detection details |
2. Capacity Estimation
Traffic
| Metric |
Calculation |
Result |
| Daily Searches |
Given |
8.5 billion |
| QPS (avg) |
8.5B / 86,400 seconds |
~100,000 QPS |
| QPS (peak) |
2x average |
~200,000 QPS |
| Query Size |
Avg 50 bytes (5 words x 10 bytes) |
50 bytes |
| Daily Query Bandwidth |
8.5B x 50 bytes |
425 GB/day |
Crawling
| Metric |
Calculation |
Result |
| Total Web Pages |
Estimated indexed web |
100 billion pages |
| Avg Page Size |
HTML + assets |
500 KB |
| Re-crawl Frequency |
Complete refresh cycle |
Every 30 days |
| Pages per Second |
100B / (30 days x 86,400 sec) |
~40,000 pages/sec |
| Crawl Bandwidth |
40,000 x 500 KB |
20 GB/sec = 160 Gbps |
| Monthly Crawl Data |
100B x 500 KB |
50 PB/month |
Storage
| Component |
Size per Page |
Total (100B pages) |
Notes |
| Raw HTML |
500 KB (compressed 100 KB) |
10 PB |
Gzip compression 5:1 |
| Inverted Index |
~200 KB |
20 PB |
Term lists, positions, metadata |
| Forward Index |
~50 KB |
5 PB |
Document metadata, title, URL |
| PageRank Scores |
8 bytes |
800 GB |
Float per document |
| Link Graph |
~1 KB |
100 TB |
Avg 50 outlinks x 20 bytes/link |
| Total |
~850 KB |
~35 PB |
With replication (3x): ~105 PB |
Serving Infrastructure
| Component |
Capacity per Server |
Servers Needed |
Interview Callout |
| Index Servers |
1,000 QPS, 10 TB storage |
10,000+ servers |
Index sharded across servers; each handles subset of terms |
| Cache Servers |
10,000 QPS (hot queries) |
1,000+ servers |
Cache hit rate 40-60%; Zipf distribution (few queries dominate) |
| Ranking Servers |
500 RPS (ML inference) |
5,000+ servers |
GPU/TPU acceleration for deep learning models |
| Crawlers |
100 pages/sec |
400+ servers |
Distributed crawling; politeness per domain |
3. High-Level Design
graph TB
subgraph "Crawling & Indexing (Offline)"
Seed[Seed URLs]
Crawler[Web Crawler
40K pages/sec]
URLQueue[(URL Frontier
Priority Queue)]
DNS[DNS Resolver]
Downloader[HTML Downloader]
ContentStore[(Content Store
Raw HTML)]
Seed --> URLQueue
URLQueue --> Crawler
Crawler --> DNS
DNS --> Downloader
Downloader --> ContentStore
Downloader -.New URLs.-> URLQueue
ContentStore --> Indexer[Indexer
MapReduce]
Indexer --> InvIndex[(Inverted Index
20 PB sharded)]
Indexer --> FwdIndex[(Forward Index
Metadata)]
ContentStore --> LinkGraph[Link Graph Builder]
LinkGraph --> PageRank[PageRank Calculator]
PageRank --> RankStore[(PageRank Scores)]
end
subgraph "Query Serving (Online)"
User[User] --> LB[Load Balancer]
LB --> QueryServer[Query Server]
QueryServer --> Spellcheck[Spell Checker]
QueryServer --> Rewriter[Query Rewriter]
QueryServer --> QueryCache[(Query Cache
40-60% hit rate)]
QueryCache -.miss.-> Scatter[Scatter/Gather]
Scatter --> IndexServer1[Index Server 1]
Scatter --> IndexServer2[Index Server 2]
Scatter --> IndexServerN[Index Server N]
InvIndex -.shard 1.-> IndexServer1
InvIndex -.shard 2.-> IndexServer2
InvIndex -.shard N.-> IndexServerN
IndexServer1 --> Ranker[Ranking Service]
IndexServer2 --> Ranker
IndexServerN --> Ranker
RankStore --> Ranker
FwdIndex --> Ranker
Ranker --> Snippets[Snippet Generator]
Snippets --> Merger[Result Merger]
Merger --> QueryServer
QueryServer --> User
end
subgraph "Supporting Services"
Ads[Ads Service] -.ads.-> Merger
Analytics[Analytics] -.logs.-> QueryServer
Personalization[Personalization] -.user data.-> Ranker
end
style Crawler fill:#e1f5ff
style Indexer fill:#e1f5ff
style QueryServer fill:#ffe1f5
style Ranker fill:#ffe1f5
style InvIndex fill:#fff4e1
style QueryCache fill:#e8ffe1
Architecture Components
| Component |
Responsibility |
Technology |
| Web Crawler |
Discover URLs, download pages, respect robots.txt |
Custom distributed crawler, bloom filters |
| Content Store |
Store raw HTML for re-indexing |
Distributed filesystem (GFS/Colossus) |
| Indexer |
Build inverted index from crawled content |
MapReduce pipeline |
| Inverted Index |
Map terms to document lists (posting lists) |
Bigtable, sharded by term or document |
| PageRank |
Calculate authority scores from link graph |
Iterative MapReduce |
| Query Server |
Parse query, coordinate retrieval, merge results |
C++/Go service |
| Index Servers |
Serve index shards, return candidate documents |
In-memory index, SSDs |
| Ranking Service |
Score/rank candidates using ML models |
TensorFlow Serving, TPUs |
| Query Cache |
Cache popular query results |
Memcached, Redis |
Data Flow
| Phase |
Steps |
Latency |
| Crawling (offline) |
Seed URLs → Crawler → Download → Store → Extract Links → Queue |
Hours to days |
| Indexing (offline) |
Content Store → Tokenize → Build Index → Shard → Replicate |
Hours |
| Query (online) |
User → Query Server → Cache (miss) → Index Servers → Rank → Merge → User |
<200ms |
4. Web Crawler
Crawler Architecture
flowchart TB
Seed[Seed URLs] --> Frontier[URL Frontier Priority Queue]
Frontier --> Politeness[Politeness Checker]
Politeness --> Fetcher[Web Fetcher]
Fetcher --> Parser[HTML Parser]
Parser --> ContentStore[(Content Store)]
Parser --> URLExtract[URL Extractor]
URLExtract --> Dedup[Dedup: Bloom Filter]
Dedup --> Frontier
Fetcher --> RobotsCache[(Robots.txt Cache)]
Crawler Components
| Component |
Purpose |
Implementation Details |
| Seed URLs |
Starting points for crawl |
High-authority sites (Wikipedia, news sites, popular domains) |
| URL Frontier |
Queue of URLs to crawl |
Priority queue (PageRank, freshness); separate queues per domain |
| Bloom Filter |
Fast URL deduplication |
100B URLs, 1% FP rate: ~120 GB memory; backed by persistent DB |
| Robots.txt Cache |
Store crawl permissions |
Cache per domain; TTL 24 hours; respect Disallow rules |
| Rate Limiter |
Politeness per domain |
Token bucket per domain; max 1-10 req/sec; avoid bans |
| DNS Resolver |
Resolve domain to IP |
Local cache with TTL; batch DNS lookups; async resolution |
| HTTP Downloader |
Fetch page content |
Connection pooling; timeout 10s; follow redirects (max 5 hops) |
| Content Processor |
Extract text, links, metadata |
Parse HTML; extract text, title, meta tags; handle JS-rendered pages |
| Duplicate Detector |
Avoid re-indexing identical content |
Content hash (MD5/SHA-256); near-duplicate (SimHash) |
URL Frontier Design
| Queue Type |
Priority |
Refresh Frequency |
| News Sites |
P0 |
Every 15-30 minutes |
| High PageRank |
P1 |
Daily |
| Medium PageRank |
P2 |
Weekly |
| Low PageRank |
P3 |
Monthly |
| New Discoveries |
P4 |
First crawl, then re-prioritize |
Politeness & Rate Limiting
| Technique |
Purpose |
Interview Callout |
| Robots.txt |
Respect site crawl rules |
Fetch /robots.txt first; cache 24h; honor Disallow, Crawl-delay |
| Rate Limiting |
Avoid overloading servers |
Max 1-10 req/sec per domain; adaptive based on response times |
| Delay Between Requests |
Politeness |
1-10 seconds between requests to same domain |
| User-Agent |
Identify crawler |
Clear user-agent string (Googlebot); contact info for webmasters |
| IP Rotation |
Distribute load |
Multiple crawler IPs; avoid single IP overwhelming a server |
Distributed Crawling
| Challenge |
Solution |
| URL deduplication across crawlers |
Consistent hashing: assign URL to crawler by hash(domain); each crawler owns subset of domains |
| Load balancing |
Shard by domain hash; rebalance when adding/removing crawlers |
| Failure handling |
Crawler health checks; redistribute domains from failed crawlers; retry failed URLs |
| Coordination |
Zookeeper for crawler registration, URL frontier sharding |
5. Indexing
Indexing Pipeline
graph TB
ContentStore[(Content Store
Raw HTML)] --> MapReduce[MapReduce Indexing Pipeline]
subgraph "Map Phase"
MapReduce --> Mapper1[Mapper 1]
MapReduce --> Mapper2[Mapper 2]
MapReduce --> MapperN[Mapper N]
Mapper1 --> Tokenize1[Tokenize
Stem, Stop Words]
Mapper2 --> Tokenize2[Tokenize]
MapperN --> TokenizeN[Tokenize]
Tokenize1 --> Emit1[Emit: term → docID, position]
Tokenize2 --> Emit2[Emit: term → docID, position]
TokenizeN --> EmitN[Emit: term → docID, position]
end
subgraph "Shuffle Phase"
Emit1 --> Shuffle[Shuffle & Sort by Term]
Emit2 --> Shuffle
EmitN --> Shuffle
end
subgraph "Reduce Phase"
Shuffle --> Reducer1[Reducer 1
Terms A-F]
Shuffle --> Reducer2[Reducer 2
Terms G-M]
Shuffle --> ReducerN[Reducer N
Terms N-Z]
Reducer1 --> PostingList1[Build Posting List
docIDs, positions, TF]
Reducer2 --> PostingList2[Build Posting List]
ReducerN --> PostingListN[Build Posting List]
end
PostingList1 --> InvIndex[(Inverted Index
Shard 1)]
PostingList2 --> InvIndex2[(Inverted Index
Shard 2)]
PostingListN --> InvIndexN[(Inverted Index
Shard N)]
Mapper1 --> FwdIdx[Forward Index Builder]
FwdIdx --> FwdIndex[(Forward Index
Metadata)]
style MapReduce fill:#e1f5ff
style InvIndex fill:#fff4e1
style FwdIndex fill:#ffe1f5
Inverted Index Structure
| Term |
Document Frequency (DF) |
Posting List (docID: positions, TF) |
| search |
50,000,000 |
doc1:[5,12,45] TF=3, doc5:[2] TF=1, doc8:[1,7,9,22] TF=4, ... |
| engine |
30,000,000 |
doc1:[6,13] TF=2, doc3:[10] TF=1, doc5:[3] TF=1, ... |
| google |
100,000,000 |
doc1:[1] TF=1, doc2:[1,5] TF=2, doc5:[1] TF=1, ... |
Forward Index Structure
| Document ID |
URL |
Title |
Length |
PageRank |
| doc1 |
google.com |
Google Search Engine |
500 words |
0.98 |
| doc2 |
wikipedia.org/wiki/Google |
Google - Wikipedia |
3,000 words |
0.95 |
| doc3 |
techcrunch.com/google-search |
How Google Search Works |
1,200 words |
0.75 |
Index Sharding Strategies
| Strategy |
Pros |
Cons |
Google's Choice |
| Document Sharding |
Each shard has full index for subset of docs; easy to update single doc |
All shards queried for every term; higher latency |
✗ |
| Term Sharding |
Each shard handles subset of terms; only relevant shards queried |
Load imbalance (common terms create hotspots) |
✓ (with hybrid) |
| Hybrid |
Term sharding + document replication for common terms |
Complex to implement and maintain |
✓ |
Index Compression
| Technique |
Compression Ratio |
Description |
| Delta Encoding |
4-5x |
Store differences between consecutive docIDs: [5, 10, 15] → [5, +5, +5] |
| Variable Byte Encoding |
2-3x |
Use fewer bytes for small numbers; 1-4 bytes per integer |
| Bit-Packing |
5-8x |
Pack multiple small integers into single word; SIMD-friendly |
| Combined |
10-15x |
Delta + variable byte or bit-packing; used by Google |
Index Building (MapReduce)
| Phase |
Input |
Output |
Parallelism |
| Map |
Document (HTML) |
term → (docID, position, TF) |
1,000s of mappers |
| Shuffle |
term → (docID, position, TF) |
Grouped by term, sorted by docID |
Network-intensive |
| Reduce |
term → [(docID, pos, TF), ...] |
term → compressed posting list |
100s of reducers |
| Merge |
Index shards |
Merged index with replicas |
Parallel writes to storage |
6. Ranking
Ranking Signals (200+ in production)
| Category |
Signals |
Weight |
Interview Callout |
| Relevance |
TF-IDF, BM25, term proximity, exact match, phrase match |
High |
Core signal; how well doc matches query terms |
| Authority |
PageRank, domain authority, inbound link count, link quality |
High |
PageRank revolutionary; link-based authority |
| Freshness |
Crawl date, content update date, QDF (query deserves freshness) |
Medium-High |
Critical for news, events; less for evergreen content |
| User Engagement |
Click-through rate (CTR), dwell time, bounce rate, pogo-sticking |
Medium |
Implicit feedback; learn from user behavior |
| Content Quality |
Spelling/grammar, reading level, ads ratio, spam score |
Medium |
Filter low-quality content; Panda update |
| Personalization |
Search history, location, language, device type |
Low-Medium |
Tailor results; balance with diversity |
| Document Features |
URL depth, title length, use of HTTPS, mobile-friendly |
Low |
Many small signals; cumulative impact |
PageRank Algorithm
| Concept |
Formula |
Details |
| Basic PageRank |
PR(A) = (1-d) + d × Σ(PR(Ti) / C(Ti)) |
Sum over all pages Ti linking to A; C(Ti) = outlink count; d = damping factor (0.85) |
| Damping Factor |
d = 0.85 |
Probability user follows link (85%) vs random jump (15%); prevents rank sink |
| Initialization |
PR(A) = 1 / N |
Equal distribution across N pages; iteratively update until convergence |
| Convergence |
|PR_new - PR_old| < ε |
Typically 50-100 iterations; ε = 0.0001; MapReduce implementation |
TF-IDF Scoring
| Component |
Formula |
Interpretation |
| Term Frequency (TF) |
TF(t, d) = (count of t in d) / (total terms in d) |
How often term appears in document (normalized) |
| Inverse Document Frequency (IDF) |
IDF(t) = log(N / DF(t)) |
Rarity of term; N = total docs, DF = docs containing t |
| TF-IDF Score |
TF-IDF(t, d) = TF(t, d) × IDF(t) |
High if term frequent in doc but rare across corpus |
| Document Score |
Score(q, d) = Σ TF-IDF(t, d) for t in q |
Sum over all query terms; cosine similarity variant |
BM25 (Better than TF-IDF)
| Parameter |
Value |
Purpose |
| k1 |
1.2 - 2.0 |
Controls term frequency saturation; prevents over-weighting repeated terms |
| b |
0.75 |
Document length normalization; longer docs penalized less than TF-IDF |
| Formula |
BM25(t,d) = IDF(t) × [TF(t,d) × (k1+1)] / [TF(t,d) + k1 × (1-b + b × |d|/avgdl)] |
Saturating TF, length normalization; state-of-art for lexical matching |
Machine Learning Ranking
| Approach |
Model Type |
Training Data |
Features |
| Learning to Rank (LTR) |
Gradient Boosted Trees (GBDT) |
Query + (doc, relevance label) pairs |
200+ signals (TF-IDF, PageRank, CTR, freshness, etc.) |
| Pointwise |
Regression/Classification |
Predict relevance score per doc |
Simple but ignores relative ranking |
| Pairwise |
RankNet, LambdaMART |
Predict pairwise order (doc A > doc B) |
More training data (all pairs); better ranking |
| Listwise |
ListNet, SoftRank |
Optimize entire result list |
Directly optimizes ranking metrics (NDCG); complex |
| Deep Learning |
Transformer (BERT) |
Query-document semantic matching |
Used for re-ranking top candidates; computationally expensive |
Ranking Pipeline
| Stage |
Candidates |
Method |
Latency |
| Retrieval |
100M → 10K |
Index lookup (inverted index); fast matching |
10-20ms |
| L1 Ranking |
10K → 1K |
Simple signals (TF-IDF, PageRank); lightweight |
20-30ms |
| L2 Ranking |
1K → 100 |
ML model (GBDT) with 200+ features |
50-100ms |
| Re-ranking |
100 → 10 |
Deep learning (BERT); semantic understanding |
50-100ms |
| Final |
10 |
Diversity, personalization, ad insertion |
10-20ms |
7. Query Processing
Query Processing Pipeline
| Stage |
Input |
Process |
Output |
| Tokenization |
"google search engine" |
Split by whitespace, lowercase |
["google", "search", "engine"] |
| Spell Check |
["gogle", "serch"] |
Edit distance, query logs, dictionary |
Did you mean: "google search"? |
| Normalization |
["searching", "searched"] |
Stemming (Porter stemmer): remove suffixes |
["search"] |
| Stop Words |
["the", "a", "is", "google"] |
Remove common words (optional; context-dependent) |
["google"] |
| Synonym Expansion |
["laptop"] |
Query logs, WordNet, embeddings |
["laptop", "notebook", "computer"] |
| Query Rewriting |
["ny weather"] |
Expand abbreviations, add context |
["new york weather forecast"] |
| Intent Detection |
["apple"] |
Classifier: company vs fruit; use context |
Show Apple Inc. results (higher prior) |
Spell Correction
| Technique |
Method |
Example |
| Edit Distance |
Levenshtein distance ≤ 2; find closest dictionary word |
"gogle" → "google" (1 edit) |
| Query Logs |
If misspelling common in logs, suggest popular correction |
"gogle" → "google" (100M searches) |
| Context-Aware |
Use surrounding terms; "gogle serch" both misspelled |
Higher confidence: "google search" |
| Phonetic |
Soundex, Metaphone; match by pronunciation |
"night" ↔ "knight" |
Query Rewriting
| Rewrite Type |
Example |
Technique |
| Abbreviation Expansion |
"nyc" → "new york city" |
Dictionary of common abbreviations |
| Synonym Expansion |
"cheap flights" → "cheap flights OR inexpensive flights OR budget flights" |
Query logs, WordNet, word embeddings |
| Query Relaxation |
If "red leather jacket XL" has 0 results → try "red leather jacket" |
Progressively drop terms if too few results |
| Query Refinement |
"apple" + user history (tech interest) → "apple iphone" |
Personalization based on search history |
Personalization
| Signal |
Use Case |
Privacy Consideration |
| Search History |
User searched "python" + "programming" → prioritize programming over snake |
Store anonymized; allow opt-out |
| Location |
"pizza" in NYC → show NYC pizzerias |
Coarse location (city-level); IP geolocation |
| Language |
Browser language setting; prefer results in user's language |
Low privacy risk |
| Device Type |
Mobile → prioritize mobile-friendly pages |
Low privacy risk |
| Time of Day |
"breakfast" at 7am → breakfast places; at 7pm → breakfast recipes |
No privacy concern |
8. Serving
Serving Architecture
| Component |
Responsibility |
Latency Budget |
Scale |
| Load Balancer |
Distribute queries across query servers |
1-2ms |
10-20 per datacenter |
| Query Server |
Parse query, coordinate retrieval, merge results |
10-20ms |
1,000s globally |
| Query Cache |
Cache popular query results |
1-5ms |
100s of servers, TBs of RAM |
| Index Servers |
Serve index shards, return candidate docs |
50-100ms |
10,000s of servers |
| Ranking Service |
Score and rank candidate documents |
50-100ms |
1,000s of servers (GPU/TPU) |
| Snippet Generator |
Generate result snippets with query terms |
10-20ms |
100s of servers |
Scatter-Gather Pattern
| Phase |
Action |
Details |
| 1. Scatter |
Query server sends query to all relevant index shards in parallel |
100-1000 index servers queried simultaneously |
| 2. Retrieve |
Each index server returns top K candidates from its shard |
K = 100-1000 per shard; fast index lookup |
| 3. Gather |
Query server collects results from all shards |
Wait for all (or timeout after 100ms) |
| 4. Merge |
Merge and sort candidates by initial score |
Top 1000 candidates sent to ranker |
| 5. Rank |
Ranking service scores candidates with ML model |
Multi-stage ranking; top 100 to re-ranker |
| 6. Finalize |
Generate snippets, add ads, apply personalization |
Return top 10 results to user |
Query Cache Strategy
| Metric |
Value |
Details |
| Hit Rate |
40-60% |
Zipf distribution: small fraction of queries dominate traffic |
| Cache Size |
TBs |
Store top 10 results per query; avg 10KB per cached query |
| TTL |
Minutes to hours |
Short TTL for news queries; longer for evergreen content |
| Invalidation |
On index update |
Invalidate affected queries when index changes (rare for stable results) |
| Personalization |
Cache key = query + user segment |
Segment users by location, language; avoid per-user caching |
Snippet Generation
| Step |
Process |
Example |
| 1. Extract Context |
Find sentences containing query terms |
Query: "search engine" → "Google is a search engine used by millions..." |
| 2. Highlight Terms |
Bold query terms in snippet |
"Google is a search engine used by millions..." |
| 3. Truncate |
Limit to ~150-160 characters |
"Google is a search engine used by millions of people to find information..." |
| 4. Add Ellipsis |
Indicate truncation |
"... search engine used by millions of people ..." |
Latency Optimization
| Technique |
Impact |
Interview Callout |
| Tail Latency Tolerance |
Return after N% of shards respond (e.g., 95%); timeout stragglers |
Critical for p99 latency; 5% slower shards shouldn't block all queries |
| Hedged Requests |
Send duplicate request after 50ms if no response |
Reduces tail latency; small cost increase |
| Result Caching |
40-60% hit rate; 1-5ms vs 100-200ms |
Huge latency win for popular queries |
| Early Termination |
Stop scanning index after K results with high scores |
WAND algorithm; avoid scanning entire posting list |
| Index in Memory |
Hot index tier in RAM; 10x faster than SSD |
Expensive but critical for latency; store frequent terms in RAM |
9. Freshness
Freshness Strategy
| Content Type |
Re-crawl Frequency |
Indexing Latency |
Priority |
| Breaking News |
Every 5-15 minutes |
1-5 minutes |
P0 |
| News Sites |
Every 30-60 minutes |
5-15 minutes |
P1 |
| Social Media |
Real-time (API push) |
Seconds |
P0 |
| High PageRank Sites |
Daily |
Hours |
P1 |
| Medium Authority |
Weekly |
1-2 days |
P2 |
| Low Authority |
Monthly |
Weeks |
P3 |
| Static Content |
Quarterly |
As needed |
P4 |
Continuous Crawling
| Challenge |
Solution |
Interview Callout |
| Detecting content changes |
HTTP ETag, Last-Modified headers; content hash comparison |
Avoid re-downloading unchanged pages; save bandwidth |
| Prioritizing re-crawls |
PageRank + change frequency + query demand (QDF) |
Allocate crawl budget to high-value pages |
| Incremental indexing |
Update index for changed docs; avoid full rebuild |
MapReduce with incremental updates; merge new with old index |
| Freshness vs coverage |
Balance: re-crawl popular pages frequently; crawl new pages slowly |
Finite crawl budget; optimize for user impact |
Incremental Indexing
| Step |
Process |
Latency |
| 1. Crawl Update |
Re-crawl page; detect changes via content hash |
Real-time |
| 2. Delta Index |
Build small index for changed docs only |
Minutes |
| 3. Merge |
Merge delta index with main index (background) |
Minutes to hours |
| 4. Serve |
Query both main + delta index; merge results |
Real-time |
| 5. Compaction |
Periodically compact: merge delta into main, remove old docs |
Hours (offline) |
Query Deserves Freshness (QDF)
| Signal |
Indicator |
Action |
| Query Spike |
Sudden increase in query volume (e.g., "earthquake") |
Boost fresh results; prioritize news sources |
| Temporal Terms |
Query contains "today", "2026", "latest", "breaking" |
Apply freshness boost to ranking |
| News Keywords |
Query matches known news events (election, sports, weather) |
Prioritize recently crawled pages |
| User Intent |
Classifier: navigational vs informational vs transactional |
Freshness less critical for navigational (e.g., "facebook login") |
10. Scalability & Reliability
Horizontal Scaling
| Component |
Scaling Strategy |
Bottleneck |
| Query Servers |
Stateless; add more servers behind load balancer |
None; linear scaling |
| Index Servers |
Shard index by term or document; add shards as index grows |
Hot shards (popular terms); mitigate with replication |
| Cache Servers |
Consistent hashing; add nodes to cache cluster |
Cache invalidation overhead |
| Crawlers |
Partition URLs by domain hash; add crawlers |
URL frontier coordination; use distributed queue |
| Ranking Servers |
Replicate model across servers; load balance |
Model size (GBs); use model parallelism for large models |
Geographic Distribution
| Region |
Datacenters |
Latency Benefit |
Challenges |
| North America |
10+ (US East, West, Central) |
20-50ms to users |
Index replication; consistency |
| Europe |
5+ (UK, Germany, France) |
30-60ms to users |
GDPR compliance; data residency |
| Asia-Pacific |
5+ (Japan, Singapore, Australia) |
40-80ms to users |
Cross-region consistency |
| Strategy |
Serve queries from nearest datacenter; replicate index globally; eventual consistency acceptable (minutes lag) |
Fault Tolerance
| Failure Type |
Detection |
Mitigation |
| Index Server Failure |
Health checks (heartbeat every 10s) |
3x replication; query replica shards; auto-restart failed servers |
| Query Server Failure |
Load balancer health checks |
Remove from pool; route traffic to healthy servers |
| Datacenter Failure |
Cross-region monitoring |
Redirect traffic to nearest healthy datacenter (DNS/Anycast) |
| Slow Shard (Straggler) |
Timeout after 100ms |
Return results from available shards; hedged requests |
| Crawler Failure |
Monitor crawl rate, error rate |
Redistribute URLs to healthy crawlers; retry failed URLs |
Graceful Degradation
| Scenario |
Degradation Strategy |
Impact |
| High Query Load |
Increase cache TTL; reduce candidate set size; skip re-ranking |
Slightly stale results; lower quality but still functional |
| Index Server Overload |
Query fewer shards (e.g., 80% instead of 100%) |
Incomplete results; still show top results from available shards |
| Ranking Service Overload |
Use simple scoring (TF-IDF); skip ML ranking |
Lower relevance; still usable results |
| Datacenter Partition |
Serve from local index only; skip cross-region shards |
Reduced coverage; prioritize availability over completeness |
Monitoring & Alerting
| Metric |
Threshold |
Alert Action |
| Query Latency (p99) |
> 300ms |
Page on-call; investigate slow shards; check network |
| Error Rate |
> 0.1% |
Page on-call; check logs for exceptions; rollback if recent deploy |
| Cache Hit Rate |
< 30% |
Investigate cache evictions; check for query distribution changes |
| Index Freshness |
> 4 hours lag |
Check crawler health; verify indexing pipeline |
| Crawl Rate |
< 30K pages/sec |
Check crawler failures; verify URL frontier has URLs |
| Datacenter Traffic |
Imbalanced (>70% to one DC) |
Check DNS/load balancing; verify other DCs healthy |
Interview Callouts
| Topic |
Key Points |
| Availability |
99.99% = 52 min downtime/year; achieve via replication (3x), multi-region, graceful degradation |
| Latency |
p99 < 200ms critical; techniques: caching (40-60% hit), tail tolerance (timeout stragglers), hedged requests |
| Scalability |
Stateless services scale linearly; shard data (index, cache); avoid single points of failure |
| Consistency |
Eventual consistency acceptable; index can lag minutes; prioritize availability over consistency |
| Cost |
100K QPS × 100ms avg = 10K cores; compression (10x), caching (40-60%), efficient data structures critical |
Interview Summary
Key Discussion Points
| Topic |
What to Emphasize |
| Crawling |
Politeness (robots.txt, rate limiting), deduplication (bloom filter), distributed crawling, freshness prioritization |
| Indexing |
Inverted index structure, sharding strategies (term vs document), compression (10-15x), MapReduce pipeline |
| Ranking |
PageRank (link graph), TF-IDF/BM25 (lexical), 200+ signals, ML ranking (GBDT, BERT), multi-stage ranking |
| Serving |
Scatter-gather, query cache (40-60% hit), tail latency tolerance, hedged requests, 10K+ index servers |
| Scalability |
Horizontal scaling, geographic distribution, graceful degradation, 99.99% availability, p99 < 200ms |
Common Mistakes to Avoid
| Proposing single monolithic index (must shard) |
Ignoring tail latency (stragglers kill p99) |
| Forgetting politeness in crawler (will get banned) |
Over-engineering consistency (eventual is fine) |
| Not discussing ML ranking (critical for relevance) |
Ignoring caching (40-60% queries cacheable) |