Search Engine (Google)

0Problem RestatementProblem

Design a web search engine like Google that can crawl billions of web pages, index content, and return relevant search results in milliseconds. Core challenges include distributed crawling at scale, building inverted indexes for fast lookups, ranking results by relevance, and handling billions of queries per day with low latency.

1RequirementsRequirements

1.1 Functional

• Crawl and index web pages from the internet.
• Accept user search queries and return relevant results.
• Rank results by relevance (quality, freshness, user intent).
• Support autocomplete/query suggestions.
• Handle different query types (informational, navigational, transactional).
• Display search results with title, snippet, and URL.
• Support advanced search (filters, date range, site-specific).
• Respect robots.txt and website politeness.

1.2 Non-Functional

• Scale: Index 100 billion+ web pages.
• Latency: Return search results in < 200ms (P99).
• Throughput: Handle 100K+ queries/second.
• Freshness: Re-crawl updated content regularly.
• Relevance: High-quality results ranked by multiple signals.
• Availability: 99.99% uptime.
• Storage: Petabytes of indexed data.

1.3 Scale Estimates

• Crawl rate: 10K pages/second → 100B pages ÷ 10K/s = 10^7 s ≈ 116 days for one full pass. So the crawler can't refresh everything often: news and popular pages are recrawled hourly to daily, the long tail every few months (see the Web Crawler case study for scheduling). Raising freshness across the board means more crawl capacity, e.g. 100K pages/s ≈ 12 days per pass.
• Daily queries: 8 billion queries/day (~100K queries/sec avg).
• Index size: 100B pages × 100 KB = 10 PB (raw HTML), 1-2 PB (compressed index).
• Storage: Original pages + inverted index + metadata = ~15 PB.

2High-Level ArchitectureArchitecture

2.1 Overview

• Crawling Pipeline: Crawlers → Content Parser → Indexer → Inverted Index.
• Query Pipeline: User Query → Query Processor → Searcher → Ranker → Results.
• Key components: Distributed crawlers, inverted index, PageRank, query processing, caching.

2.2 Architecture Diagram

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart TB
    %% Crawling Pipeline
    Web["Web Pages"] -->|"C1. HTTP GET"| Crawler["Crawler Service<br/>(10K workers)"]
    Crawler -->|"C2. Raw HTML"| Parser["Content Parser"]
    Parser -->|"C3. Extract Text/Links"| Indexer["Indexing Service"]
    Indexer -->|"C4. Build Inverted Index"| InvertedIdx[(Inverted Index<br/>Sharded DB)]
    Parser -->|"C5. Extract Links"| URLQueue["URL Frontier<br/>(Priority Queue)"]
    URLQueue -->|"C6. New URLs"| Crawler
    
    %% PageRank Computation
    InvertedIdx -->|"P1. Web Graph"| PageRank["PageRank Service<br/>(Offline Batch)"]
    PageRank -->|"P2. Page Scores"| InvertedIdx
    
    %% Query Pipeline
    User["User"] -->|"1. Search Query"| FE["Frontend / API Gateway"]
    FE -->|"2. Process Query"| QP["Query Processor"]
    QP -->|"3. Check Cache"| Cache["Query Cache<br/>(Redis)"]
    
    Cache -->|"4a. Cache Hit"| FE
    Cache -->|"4b. Cache Miss"| Searcher["Searcher Service"]
    
    Searcher -->|"5. Lookup Terms"| InvertedIdx
    InvertedIdx -->|"6. Matching Doc IDs"| Ranker["Ranking Service"]
    Ranker -->|"7. Score & Rank"| Results["Top K Results"]
    Results -->|"8. Update Cache"| Cache
    Results -->|"9. Return Results"| FE
    FE -->|"10. Display Results"| User
    
    %% Autocomplete
    FE -->|"A1. Partial Query"| Autocomplete["Autocomplete Service"]
    Autocomplete -->|"A2. Suggestions"| FE
    
    %% Analytics
    User -->|"L1. Click Logs"| Analytics["Analytics Service"]
    Analytics -->|"L2. CTR Signals"| Ranker
    
    %% Styling
    classDef crawl fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef query fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef storage fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    classDef ml fill:#f3e5f5,stroke:#7b1fa2,stroke-width:2px;
    
    class Crawler,Parser,Indexer crawl;
    class User,FE,QP,Searcher,Autocomplete query;
    class InvertedIdx,URLQueue,Cache storage;
    class PageRank,Ranker,Analytics ml;

3Components (what & why)

Crawler Service

• Responsibilities:
• Fetch web pages from URLs in frontier queue.
• Respect robots.txt and politeness policies.
• Detect duplicate content.
• Scaling: 10K+ crawler workers distributed globally.
• Optimization: Asynchronous I/O, connection pooling.

Content Parser

• Responsibilities:
• Extract text, links, metadata (title, description) from HTML.
• Identify spam/low-quality content.
• Normalize text (lowercase, stemming; stop words are usually kept so phrase queries like "to be or not to be" still work).
• Tools: BeautifulSoup, lxml, or custom parsers.

URL Frontier

• Purpose: Priority queue of URLs to crawl.
• Prioritization: PageRank, freshness, crawl history.
• Deduplication: Bloom filter + canonical URL store.

Indexing Service

• Responsibilities:
• Build inverted index: term → list of documents containing term.
• Store term frequency (TF), document frequency (DF).
• Compress index for storage efficiency.
• Output: Distributed inverted index, partitioned by document (see Sharding Strategy).

Inverted Index

• Structure: {term: [(doc_id, position, TF), ...]}
• Example: {"search": [(doc1, [5, 12, 45], TF=3), (doc2, [2], TF=1), ...]}
• Storage: Sharded across multiple nodes by document ID (each shard indexes its own subset of pages).
• Compression: Delta encoding, variable-byte encoding.

PageRank Service

• Purpose: Compute importance score for each page based on link graph.
• Algorithm: Iterative computation of PageRank (offline batch job).
• Frequency: Run weekly/monthly.
• Storage: Store PageRank scores in index metadata.

Query Processor

• Responsibilities:
• Tokenize and normalize query.
• Expand query (synonyms, spell correction).
• Identify query intent (informational, navigational, transactional).
• Optimization: Query rewriting, stemming.

Searcher Service

• Responsibilities:
• Lookup query terms in inverted index.
• Retrieve matching document IDs.
• Merge results from shards.
• Optimization: Parallel shard queries, early termination.

Ranking Service

• Responsibilities:
• Score documents by relevance using multiple signals:
• TF-IDF: Term frequency × inverse document frequency.
• PageRank: Page authority.
• Freshness: Recency of content.
• Click-through rate: User engagement signals.
• Query-document match: Exact match, phrase match.
• Combine signals using ML model (e.g., gradient boosting, neural nets).
• Output: Top K results sorted by score.

Query Cache

• Purpose: Cache popular query results to reduce load.
• Implementation: Redis with LRU eviction.
• TTL: 5-60 minutes (balance freshness vs cache hit rate).

Autocomplete Service

• Purpose: Suggest query completions as user types.
• Data: Trie or prefix tree of popular queries.
• Ranking: By query frequency, personalization.

Analytics Service

• Metrics: Query volume, latency, click-through rate, result quality.
• Feedback Loop: User clicks improve ranking model.

4Data ModelData model

Document

Document(
  doc_id,
  url,
  title,
  content,  -- compressed
  last_crawled,
  pagerank_score
)

Inverted Index (Per Term)

term -> [
  (doc_id_1, positions: [5, 12, 45], TF: 3),
  (doc_id_2, positions: [2], TF: 1),
  ...
]

Link Graph

Link(source_url, target_url, anchor_text)

Query Log

QueryLog(
  query_id,
  query_text,
  user_id,
  timestamp,
  results_shown,
  clicked_doc_id
)

5Key FlowsFlows

5.1 Crawling Flow

1. Crawler fetches URL from frontier queue.
2. Sends HTTP GET request to web server.
3. Receives HTML content.
4. Parser extracts text, links, and metadata.
5. Links added to URL frontier (after deduplication).
6. Content sent to Indexer.

5.2 Indexing Flow

1. Indexer receives parsed content.
2. Tokenizes text into terms.
3. For each term, updates inverted index with (doc_id, positions, TF).
4. Computes document metadata (title, description, PageRank placeholder).
5. Stores in distributed index shards.

5.3 Search Query Flow

1. User enters query: "machine learning tutorial".
2. Query Processor tokenizes: ["machine", "learning", "tutorial"].
3. Checks Query Cache:

• Cache hit: Return cached results.
• Cache miss: Proceed to Searcher.

1. Each shard (a subset of documents) returns its top-scoring matches.
2. Searcher merges results (intersection or union based on query).
3. Ranker scores documents using TF-IDF, PageRank, freshness, CTR.
4. Top 10 results returned to user.
5. Results cached in Query Cache.

5.4 PageRank Computation Flow (Offline)

1. Build web graph from crawled links.
2. Initialize all pages with PageRank = 1/N.
3. Iterate:

• For each page, distribute its PageRank to outgoing links.
• Update PageRank for all pages.

1. Store final PageRank scores in index.

5.5 Autocomplete Flow

1. User types "mach".
2. Frontend sends prefix to Autocomplete Service.
3. Service queries trie for queries starting with "mach".
4. Returns top 10 suggestions: ["machine learning", "machining tools", "machine gun", ...].
5. User selects suggestion or continues typing.

6Deep Dive A: Inverted Index & Indexing (~10 mins)Deep dive

Problem

With 100 billion pages, linear search is infeasible. We need fast lookups for query terms.

Solution: Inverted Index

Structure

• Inverted Index: Maps each term to a list of documents containing that term.
• Example:

"search" -> [doc1, doc5, doc12, ...]
"engine" -> [doc1, doc3, doc8, ...]

Detailed Structure

{
  "search": [
    {"doc_id": "doc1", "positions": [5, 12, 45], "TF": 3},
    {"doc_id": "doc5", "positions": [2], "TF": 1},
    ...
  ],
  "engine": [
    {"doc_id": "doc1", "positions": [6], "TF": 1},
    ...
  ]
}

Building the Index

1. Tokenization: Split document into terms (words).

• Input: "Google is a search engine."
• Output: ["google", "is", "a", "search", "engine"]

• Output: ["google", "search", "engine"]

1. Index Update: For each term, add (doc_id, position, TF) to inverted index.

Sharding Strategy

• Problem: Index too large for single machine.
• Two options:
• Partition by term (e.g. hash of the term): each shard holds the *complete* posting list for its terms. A query goes only to the shards owning its terms — but a multi-word query must ship whole posting lists between machines to intersect them, and a very common term makes one shard hot.
• Partition by document (hash of doc ID): each shard is a complete mini search engine over its subset of pages, holding posting lists for *all* terms. Every query goes to every shard; each returns its local top K, and an aggregator merges them.
• Choice: Partition by document. That is what large web search engines do: shards compute and rank locally, only small top-K lists cross the network, a slow or dead shard only drops a small slice of results, and adding documents means adding shards. Replicate each shard to handle query volume.

Compression Techniques

• Delta Encoding: Store differences between doc IDs instead of absolute values.
• Instead of [100, 105, 108], store [100, +5, +3].
• Variable-Byte Encoding: Use fewer bytes for small numbers.
• Compression Ratio: 5-10× reduction.

Indexing Architecture

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart TD
    Parser["Content Parser"] -->|"doc text"| Tokenizer["Tokenizer"]
    Tokenizer -->|"terms"| Normalizer["Normalizer<br/>(lowercase, stop words)"]
    Normalizer -->|"clean terms"| Stemmer["Stemmer"]
    
    Stemmer -->|"docs 0..N/3"| Shard1["Inverted Index<br/>Shard 1 (doc subset 1)"]
    Stemmer -->|"docs N/3..2N/3"| Shard2["Inverted Index<br/>Shard 2 (doc subset 2)"]
    Stemmer -->|"docs 2N/3..N"| Shard3["Inverted Index<br/>Shard 3 (doc subset 3)"]
    
    Shard1 --> Compression["Compression<br/>(Delta, VarByte)"]
    Shard2 --> Compression
    Shard3 --> Compression
    
    Compression --> Storage["Distributed Storage<br/>(HDFS/GFS)"]
    
    classDef process fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef storage fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    
    class Tokenizer,Normalizer,Stemmer,Compression process;
    class Shard1,Shard2,Shard3,Storage storage;

7Deep Dive B: Ranking Algorithm (~10 mins)Deep dive

Problem

Given 1 million documents matching a query, determine the top 10 most relevant.

Ranking Signals

1. TF-IDF (Term Frequency × Inverse Document Frequency)

• TF: How often term appears in document.
• IDF: Rarity of term across all documents.
• Formula:

TF-IDF(term, doc) = TF(term, doc) × log(N / DF(term))

• TF(term, doc): Frequency of term in document.
• N: Total number of documents.
• DF(term): Number of documents containing term.
• Example: "the" has low IDF (common), "quantum" has high IDF (rare).

2. PageRank

• Idea: Pages linked by many high-quality pages are more important.
• Algorithm: Iterative computation on link graph.
• Formula:

PR(A) = (1-d)/N + d × Σ(PR(Ti) / C(Ti))

• d: Damping factor (0.85).
• Ti: Pages linking to page A.
• C(Ti): Number of outbound links from Ti.
• Computation: Offline batch job (MapReduce).

3. Query-Document Match

• Exact Match: All query terms in document (higher score).
• Phrase Match: Query terms appear consecutively.
• Title Match: Terms in title weighted higher.
• Proximity: Terms close together score higher.

4. Freshness

• Recent Content: Boost newer pages for time-sensitive queries (news, events).
• Formula: Decay score based on age.

5. Click-Through Rate (CTR)

• User Feedback: If users frequently click a result, it's likely relevant.
• Learning: ML model learns from query logs.

6. Domain Authority

• Site-level quality signals: Sites with a track record of trustworthy, well-linked content get a boost. This is learned from links and user behavior, not from the domain suffix — a .edu or .gov address alone doesn't rank higher.

Ranking Pipeline

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
    Query["User Query"] --> Searcher["Searcher"]
    Searcher -->|"matching doc IDs"| Ranker["Ranking Service"]
    
    Ranker --> TFIDF["TF-IDF Score"]
    Ranker --> PR["PageRank Score"]
    Ranker --> Fresh["Freshness Score"]
    Ranker --> CTR["CTR Score"]
    Ranker --> Match["Query Match Score"]
    
    TFIDF --> ML["ML Model<br/>(Gradient Boosting)"]
    PR --> ML
    Fresh --> ML
    CTR --> ML
    Match --> ML
    
    ML --> FinalScore["Final Score"]
    FinalScore --> TopK["Top 10 Results"]
    
    classDef signal fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef ml fill:#f3e5f5,stroke:#7b1fa2,stroke-width:2px;
    
    class TFIDF,PR,Fresh,CTR,Match signal;
    class ML,FinalScore ml;

ML-Based Ranking (Learning to Rank)

• Training Data: Query + document pairs with relevance labels (manual or from clicks).
• Features: TF-IDF, PageRank, freshness, CTR, domain authority, etc.
• Model: Gradient boosting (XGBoost), neural networks (RankNet).
• Training: Offline on historical data.
• Serving: Real-time inference during query.

8Deep Dive C: Distributed Search & Low Latency (~8 mins)Deep dive

Problem

Query must scan billions of documents and return results in < 200ms.

Solution: Distributed Parallel Search

Index Sharding

• Shard by Document (chosen, see Deep Dive A): Each shard holds a subset of documents with posting lists for all terms, so every shard can answer any query for its documents.
• Replicas: Each shard is replicated; the aggregator picks one replica per shard, which spreads query load and hides slow machines.
• Tiers: Keep a small, high-quality tier (popular pages) and a large long-tail tier; query the small tier first and only fan out to the big one when results are thin.

Query Execution

1. Query Distribution: Query sent to all index shards in parallel.
2. Shard Processing: Each shard intersects the query terms' posting lists over its own documents and scores its local top K.
3. Result Merging: Aggregator merges results from all shards.
4. Top-K Selection: Ranker scores and selects top K documents.

Early Termination

• Optimization: Stop searching once top K results found.
• Strategy: Within each shard, posting lists are sorted by a static quality score (e.g. PageRank), so a shard can stop scanning once further documents can't beat its current top K (min-heap of size K).

Index Caching

• Cache Hot Terms: Frequently queried terms cached in memory.
• Cache Doc Metadata: Title, snippet, URL cached for fast retrieval.

Latency Breakdown

Total: ~180ms (budget: < 200ms)
├─ Query parsing: 10ms
├─ Cache lookup: 1ms (miss)
├─ Shard queries (parallel): 80ms
│  ├─ Shard 1: 75ms
│  ├─ Shard 2: 78ms
│  └─ Shard N: 80ms
├─ Result merging: 30ms
├─ Ranking: 50ms
└─ Response formatting: 10ms

Distributed Search Architecture

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart TD
    Query["User Query"] --> Aggregator["Query Aggregator"]
    
    Aggregator -->|"broadcast"| Shard1["Index Shard 1"]
    Aggregator -->|"broadcast"| Shard2["Index Shard 2"]
    Aggregator -->|"broadcast"| ShardN["Index Shard N"]
    
    Shard1 -->|"doc IDs + scores"| Merger["Result Merger"]
    Shard2 -->|"doc IDs + scores"| Merger
    ShardN -->|"doc IDs + scores"| Merger
    
    Merger -->|"merged results"| Ranker["Ranker"]
    Ranker -->|"top K"| Results["Top 10 Results"]
    
    classDef query fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef shard fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    
    class Query,Aggregator,Merger,Ranker query;
    class Shard1,Shard2,ShardN shard;

9Scaling & Performance (~5 mins)Scale

Horizontal Scaling

• Crawlers: 10K+ workers distributed globally.
• Index Shards: 1000+ shards for inverted index.
• Searcher Replicas: 100+ replicas for query processing.

Caching Strategy

• L1 (Query Cache): Redis, 80%+ hit rate, 5-60 min TTL.
• L2 (Document Cache): Memcached, frequently accessed docs.
• L3 (Index Cache): In-memory cache of hot index terms.

Performance Metrics

• Indexing Throughput: 10K pages/sec.
• Query Latency: P99 < 200ms.
• Query Throughput: 100K queries/sec.
• Index Size: 1-2 PB (compressed).

Bottlenecks & Mitigations

• Index Lookups: Shard more aggressively, cache hot terms.
• Ranking Computation: Pre-compute partial scores, use approximate algorithms.
• Network I/O: Use efficient serialization (Protobuf), compress payloads.

10Failure Modes & Recovery

Crawler Failure

• Impact: Pages not updated.
• Mitigation: Retry queue, distributed crawlers with redundancy.

Index Shard Failure

• Impact: Incomplete search results.
• Mitigation: Replicate shards (3× replication), route to healthy replicas.

Ranker Failure

• Impact: Results not properly scored.
• Mitigation: Fallback to simpler ranking (TF-IDF only), deploy redundant rankers.

Cache Failure

• Impact: Higher latency, increased load on index.
• Mitigation: Multiple cache layers, fallback to index on cache miss.

11Trade-offs & AlternativesTrade-offs

Centralized vs Distributed Index

• Centralized: Simpler, but doesn't scale.
• Distributed: Scalable, but complex.
• Choice: Distributed (required for billions of pages).

Real-Time vs Batch Indexing

• Real-Time: Immediate index updates, low latency.
• Batch: Process in batches (hourly/daily), simpler.
• Choice: Hybrid (batch for bulk, incremental for updates).

Exact vs Approximate Ranking

• Exact: Best quality, slower.
• Approximate: Faster, slight quality trade-off.
• Choice: Approximate with early termination for speed.

12Security & Privacy

Spam Detection

• Techniques: Detect keyword stuffing, cloaking, link farms.
• ML Models: Classify spam vs legitimate content.

Data Privacy

• Anonymize Logs: Remove PII from query logs.
• GDPR Compliance: Allow users to delete search history.

DoS Protection

• Rate Limiting: Limit queries per user/IP.
• CAPTCHA: Detect bots.

13Interview Time Allocation (45 min)

• 5 min: Requirements & scope (functional, non-functional, scale).
• 10 min: HLD & architecture diagram (crawling + query pipeline).
• 5 min: Data model & key flows (crawl, index, search).
• 10 min: Deep dive on inverted index & indexing.
• 10 min: Deep dive on ranking algorithm (TF-IDF, PageRank, ML).
• 5 min: Distributed search, scaling, failure handling.

14SummaryWrap-up

• Core Challenges: Crawling at scale, building inverted index, ranking by relevance, low-latency distributed search.
• Key Components:
• Crawler: Distributed workers with politeness, deduplication.
• Inverted Index: Sharded, compressed, term → doc_ids mapping.
• Ranking: TF-IDF + PageRank + ML model for relevance.
• Query Pipeline: Cache → parallel shard queries → merge → rank.
• Scaling Strategy: Horizontal scaling of crawlers/searchers, sharded index, multi-layer caching.
• Performance: 100K queries/sec, < 200ms latency, 100B pages indexed.

This design powers a search engine serving billions of queries daily with high relevance and low latency.