Design a Search Engine

A search engine is one of the most complex distributed systems ever built. Google processes over 8.5 billion searches per day, indexing hundreds of billions of web pages across a petabyte-scale inverted index. In an interview, you won’t design the full Google — but you need to demonstrate mastery of the core components: crawling, indexing, query processing, and ranking.

Understanding the Problem

Functional Requirements

1. Web search by keywords — User types a query, gets ranked results
2. Autocomplete suggestions — As-you-type query suggestions
3. Paginated results — 10 results per page, with next/previous
4. Spell correction — “Did you mean: running shoes”
5. Snippet generation — Show relevant text excerpt from each result
6. Freshness — New content indexed within hours, not days

Non-Functional Requirements

Scale Estimation

• 100 billion indexed pages, average 50KB each = 5 PB raw content
• Inverted index is ~10% of raw content = 500 TB index data
• 100K QPS at peak, each fanning out to all ~10,000 index shards (one replica each) = ~1B internal leaf RPCs/sec
• Crawl rate: ~1 billion pages/day to maintain freshness

Core Entities and APIs

Data Model

-- Document metadata (stored separately from index)
CREATE TABLE documents (
    doc_id      BIGINT PRIMARY KEY,
    url         TEXT UNIQUE,
    title       VARCHAR(500),
    content_hash CHAR(64),     -- SHA-256 for dedup
    page_rank   FLOAT DEFAULT 0.0,
    crawled_at  TIMESTAMP,
    indexed_at  TIMESTAMP
);

-- The inverted index is NOT in SQL — it's a custom
-- data structure optimized for term lookups.
-- Conceptually:
--   term → [(doc_id, term_frequency, [positions]), ...]

API Design

# Search
GET /api/v1/search?q=distributed+systems&page=1&size=10
response:
  total_results: 142000000
  results:
    - title: "Designing Data-Intensive Applications"
      url: "https://example.com/ddia"
      snippet: "A guide to the big ideas behind reliable, scalable..."
      score: 0.94
    - ...
  suggestions:
    spell_correction: null
    related_searches: ["distributed systems book", "system design"]

# Autocomplete
GET /api/v1/suggest?prefix=distrib
response:
  suggestions:
    - "distributed systems"
    - "distributed computing"
    - "distributed database"
    - "distributed lock"

# Index (internal API, not public)
POST /internal/v1/index
  body: { url, title, content, crawled_at }

High-Level Design

A search engine has two distinct pipelines that share the inverted index.

Indexing Pipeline (Offline/Batch)

1. Web Crawler — Fetches pages from the internet using BFS. A URL frontier manages priority (important sites first) and politeness (don’t DDoS anyone).
2. Document Processor — Parses HTML, extracts text, detects language, deduplicates via SimHash/MinHash.
3. Indexer — Tokenizes text, applies stemming, builds inverted index entries, computes term frequencies.
4. Index Storage — Writes sharded inverted index to disk. Computes PageRank from the link graph.

Query Pipeline (Online/Real-Time)

1. Query Parser — Tokenizes the query, applies spell check, removes stop words, stems terms.
2. Index Lookup — Scatters the query to all index shards, gathers posting lists.
3. Scorer/Ranker — Computes relevance score per document using BM25 + PageRank + freshness + ML signals.
4. Result Builder — Fetches document metadata (title, URL), generates snippets, formats the response.

Deep Dive: Inverted Index

The inverted index is the heart of any search engine. It maps every term to the list of documents containing that term.

Structure

Term Dictionary:
  "distributed" → PostingList
  "system"      → PostingList
  "design"      → PostingList
  ...

PostingList for "distributed":
  [
    { doc_id: 1042, tf: 5, positions: [3, 15, 42, 89, 123] },
    { doc_id: 2891, tf: 2, positions: [7, 56] },
    { doc_id: 5420, tf: 8, positions: [1, 12, 28, 33, 67, 91, 104, 118] },
    ...
  ]

Each posting list entry contains:

• doc_id — Which document contains this term
• tf (term frequency) — How many times the term appears
• positions — Where in the document the term appears (enables phrase queries like “distributed systems”)

Building the Index

def build_inverted_index(documents):
    """
    Build an in-memory inverted index from a batch of documents.
    In production, this writes to a sorted on-disk format (SSTable-like).
    """
    index = defaultdict(list)  # term → list of PostingEntry
    
    for doc in documents:
        tokens = tokenize(doc.content)       # split on whitespace/punctuation
        tokens = [t.lower() for t in tokens] # lowercase
        tokens = remove_stop_words(tokens)   # remove "the", "is", "a"
        tokens = [stem(t) for t in tokens]   # "running" → "run"
        
        # Count term frequencies and record positions
        term_positions = defaultdict(list)
        for pos, token in enumerate(tokens):
            term_positions[token].append(pos)
        
        for term, positions in term_positions.items():
            index[term].append(PostingEntry(
                doc_id=doc.id,
                tf=len(positions),
                positions=positions
            ))
    
    # Sort posting lists by doc_id for efficient intersection
    for term in index:
        index[term].sort(key=lambda e: e.doc_id)
    
    return index

Sharding the Index

There are two fundamental strategies for distributing the index across machines:

Document-Partitioned:

• Each shard holds a complete index for a subset of documents
• Every query is broadcast to all shards (scatter-gather)
• Each shard returns its local top-K, coordinator merges
• Simpler to rebalance, easier to add capacity

Term-Partitioned:

• Each shard owns a subset of terms (e.g., A-M, N-Z)
• A single-term query hits exactly one shard
• Multi-term queries hit multiple shards, then intersect
• Better for single-term lookups, harder to manage

For most interviews, go with document-partitioned sharding. It’s what Elasticsearch, Solr, and most modern search systems use. The scatter-gather overhead is acceptable because each shard responds in parallel.

# Scatter-gather pseudocode
async def search(query, num_shards=10_000, top_k=10):
    # Parse and prepare
    terms = parse_query(query)
    
    # Scatter: send to all shards in parallel (one replica of each;
    # in production this goes through a tree of aggregators)
    futures = []
    for shard_id in range(num_shards):
        futures.append(
            shard_clients[shard_id].search(terms, top_k=top_k)
        )
    
    # Gather: collect local top-K from each shard
    shard_results = await asyncio.gather(*futures)
    
    # Merge: global top-K from all shard results
    heap = []
    for results in shard_results:
        for doc_id, score in results:
            heapq.heappush(heap, (score, doc_id))
            if len(heap) > top_k:
                heapq.heappop(heap)
    
    return sorted(heap, reverse=True)

Deep Dive: Query Processing Pipeline

A raw user query goes through several transformations before it hits the index.

Step 1: Tokenization

Split the raw query into individual terms, normalize case, handle special characters.

def tokenize(query):
    # "New York restaurants -fast-food" →
    # ["new", "york", "restaurants", "-fast-food"]
    tokens = re.split(r'\s+', query.lower().strip())
    return tokens

Step 2: Spell Correction

Check each term against a dictionary. For unknown terms, find the closest known term using edit distance or a pre-built n-gram index.

def spell_check(term, dictionary, max_edit_distance=2):
    if term in dictionary:
        return term
    
    # Generate candidates within edit distance
    candidates = []
    for dict_term in dictionary.get_candidates(term[:3]):  # prefix filter
        dist = levenshtein_distance(term, dict_term)
        if dist <= max_edit_distance:
            candidates.append((dict_term, dist, dictionary.frequency(dict_term)))
    
    if not candidates:
        return term  # Unknown term, keep as-is
    
    # Rank by (edit_distance ASC, frequency DESC)
    candidates.sort(key=lambda c: (c[1], -c[2]))
    return candidates[0][0]

# "runing" → edit distance 1 from "running" → correct

Step 3: Stemming

Reduce words to their root form so that “running”, “runs”, “ran” all match documents containing any of these forms.

# Porter Stemmer examples:
# "running"   → "run"
# "computers" → "comput"
# "arguing"   → "argu"
# "agreed"    → "agre"

Step 4: Query Expansion

Add synonyms and related terms to improve recall:

def expand_query(terms):
    expanded = list(terms)
    for term in terms:
        synonyms = synonym_dict.get(term, [])
        # Add top 2 synonyms with reduced weight
        for syn in synonyms[:2]:
            expanded.append((syn, boost=0.5))
    return expanded

# "shoes" → ["shoes", ("footwear", 0.5), ("sneakers", 0.5)]

Step 5: Index Lookup (Scatter-Gather)

The parsed query is broadcast to all index shards. Each shard performs a local search:

1. Look up each query term in the shard’s inverted index
2. Intersect posting lists (for AND queries) or merge them (for OR queries)
3. Score each matching document locally
4. Return the top-K results to the coordinator

Step 6: Scoring with BM25

BM25 (Best Matching 25) is the industry-standard relevance scoring function. It’s an improvement over TF-IDF that handles document length normalization:

import math

def bm25_score(query_terms, doc, index, corpus_stats):
    """
    BM25 scoring for a single document against query terms.
    
    k1 = 1.2  (term frequency saturation)
    b  = 0.75 (document length normalization)
    """
    k1 = 1.2
    b = 0.75
    score = 0.0
    
    N = corpus_stats.total_docs
    avgdl = corpus_stats.avg_doc_length
    dl = doc.length  # number of terms in this document
    
    for term in query_terms:
        # df = number of documents containing this term
        df = index.doc_frequency(term)
        
        # IDF component: rare terms are more important
        idf = math.log((N - df + 0.5) / (df + 0.5) + 1)
        
        # TF component with saturation and length normalization
        tf = doc.term_frequency(term)
        tf_norm = (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * dl / avgdl))
        
        score += idf * tf_norm
    
    return score

BM25 captures two crucial intuitions:

• IDF: A term appearing in 90% of documents (“the”) is nearly worthless. A term appearing in 0.01% of documents (“kubernetes”) is highly discriminative.
• Saturating TF: Mentioning “database” 50 times in a document doesn’t make it 50x more relevant than mentioning it once. The score saturates around tf=5-10.

Step 7: Combining Signals

BM25 alone isn’t sufficient. Modern search engines combine multiple signals:

def final_score(doc, query, bm25):
    return (
        0.40 * bm25                           +  # Text relevance
        0.25 * doc.page_rank                   +  # Link authority
        0.15 * freshness_score(doc.crawled_at) +  # Newer is better
        0.10 * click_through_rate(doc, query)  +  # User engagement
        0.10 * domain_authority(doc.url)           # Trust signal
    )

PageRank measures a page’s authority based on the link graph. A page linked to by many important pages gets a high PageRank. It’s computed offline during the indexing pipeline.

Deep Dive: Autocomplete

Autocomplete must return suggestions within 50-100ms of each keystroke. The data structure of choice is a Trie (prefix tree) combined with pre-computed top-K results per prefix.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.top_suggestions = []  # Pre-computed top 10 for this prefix
        self.is_end = False

class AutocompleteTrie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, phrase, score):
        node = self.root
        for char in phrase:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            # Update top-K suggestions at each prefix node
            self._update_top_k(node, phrase, score)
        node.is_end = True
    
    def suggest(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return node.top_suggestions  # O(1) lookup!
    
    def _update_top_k(self, node, phrase, score, k=10):
        node.top_suggestions.append((phrase, score))
        node.top_suggestions.sort(key=lambda x: -x[1])
        node.top_suggestions = node.top_suggestions[:k]

The key optimization: pre-compute the top-K suggestions at every trie node. When a user types “dist”, we traverse to the “d”→“i”→“s”→“t” node and return its pre-computed list immediately — no DFS traversal needed at query time.

The trie is rebuilt periodically (e.g., hourly) from query logs, weighted by query frequency.

Deep Dive: Freshness vs. Completeness

A tension exists between two goals:

• Freshness: Index breaking news within minutes
• Completeness: Have a comprehensive index of the entire web

The solution is tiered indexing:

Tier 1 (Hot): 
  - Top 10M most important URLs
  - Re-crawled every 1-4 hours
  - Served from fastest SSD-backed shards
  - Breaking news, popular sites

Tier 2 (Warm):
  - Next 1B URLs
  - Re-crawled every 1-7 days
  - Served from standard storage

Tier 3 (Cold):
  - Long-tail: 100B+ URLs
  - Re-crawled every 30-90 days
  - Served from high-density storage
  - Only queried if tiers 1+2 don't satisfy

For breaking news, a separate real-time indexing pipeline processes new content from RSS feeds, social media, and news APIs. It pushes updates to Tier 1 within minutes.

Deep Dive: Index Serving at Scale

With 500 TB of index data and 100K QPS, you need careful capacity planning. The model: 10,000 shards × R replicas, and every query fans out to every shard once, hitting one replica of each.

Index Size:     500 TB
Shard Size:     ~50 GB per shard (fits in RAM on 64GB machines)
Num Shards:     500 TB / 50 GB = 10,000

Query Fan-out:  Each query hits all 10,000 shards (one replica each)
                = 10,000 leaf RPCs per query
                Root → ~100 aggregators → ~100 shards each,
                so no single machine sends 10,000 RPCs

At 100K QPS:    100K * 10,000 = 1B leaf RPCs/sec
Per shard:      100K queries/sec (every query touches every shard)
Per replica:    ~10K queries/sec (in-RAM shard with early termination)
Replicas:       100K / 10K = 10 per shard
                (3 would be enough for availability; throughput sets R)
Total Machines: 10,000 * 10 = 100,000 index servers

Because document partitioning sends every query to every shard, throughput, not storage, sets the replica count. Anything that keeps queries away from the full fan-out pays off directly: the result cache below, and the tiered index from the previous section, which answers most queries from the much smaller hot and warm tiers.

Query result caching. Query popularity is heavily skewed: a small set of head queries (“weather”, “news”, celebrity names) makes up a large share of traffic. Cache the final result page in a distributed cache keyed by the normalised query plus page number, with a TTL of minutes (shorter for news-sensitive queries, invalidated when the hot tier is refreshed). Every hit saves 10,000 leaf RPCs; a 40% hit rate cuts 1B leaf RPCs/sec to 600M and per-replica load from ~10K to ~6K QPS.

Bloom filters optimize this further: each shard maintains a Bloom filter of its terms. The query coordinator checks the Bloom filter first and skips shards guaranteed not to have any of the query terms. Common terms appear in every shard, so this mainly trims fan-out for rare-term queries; the worst case is still all 10,000 shards.

Key Trade-offs

• Sharding: document-partitioned vs. term-partitioned. We shard by document, so each shard is self-contained and easy to rebalance. The cost is that every query scatters to every shard: internal RPC volume grows with shard count, and p99 latency is set by the slowest shard in the fan-out. Term partitioning wins when most queries are one or two terms and you would rather touch a handful of shards, at the price of shipping large posting lists across the network to intersect them.
• Freshness: tiered batch index plus a real-time pipeline vs. one incrementally updated index. Tiers let us spend crawl and SSD budget on the top 10M URLs while the long tail sits on dense storage. The cost is two indexing paths to run and merge, and long-tail pages that can be 30–90 days stale. A single near-real-time index (Elasticsearch-style refresh) is simpler and fine for site or enterprise search, where the corpus is millions of documents rather than 100 billion.
• Ranking: BM25 + PageRank + ML signals vs. BM25 alone. Blending signals is what makes the first page good, but it adds an offline PageRank job over the whole link graph, click and authority data to maintain, and ML re-ranking that has to fit inside the 200ms budget (so only the top candidates get re-ranked). Plain BM25 is the right call for a product or documentation search box with no link graph.
• Index serving: RAM-resident shards vs. disk-resident shards. Keeping ~50 GB shards in memory gives fast posting-list lookups at 100K QPS, but it means ~100,000 index servers once you add the 10 replicas per shard that throughput demands. Serving the warm and cold tiers from disk with a RAM page cache cuts hardware cost substantially, at the price of slower long-tail queries.
• Autocomplete: precomputed top-K trie vs. computing suggestions at query time. Storing the top 10 suggestions at every trie node makes each keystroke a single lookup, but multiplies memory use and means suggestions lag trending queries until the hourly rebuild. If trending terms matter, layer a small streaming “trending queries” source on top rather than abandoning precomputation.

Key Takeaways

The search engine design tests your understanding of data structures at scale (inverted index, tries), distributed query processing (scatter-gather), and relevance engineering (BM25, PageRank). In the interview, start with the two-pipeline architecture, then let the interviewer guide which deep dive they want.