Design a Search Engine

Problem Statement & Requirements

Think of a search engine like a vast library with a brilliant librarian. The crawler is the librarian who reads every book and creates an index card for each. The index is the card catalog. The ranking algorithm is the librarian's judgment about which books best answer your question. And autocomplete is the librarian anticipating your question before you finish asking.

Functional Requirements

• Web crawling — Discover and download billions of web pages
• Indexing — Build searchable index from crawled content
• Query processing — Parse, expand, and execute search queries
• Ranking — Order results by relevance using signals like PageRank, BM25, user behavior
• Autocomplete — Suggest queries as the user types
• Spell correction — Handle typos and misspellings

Non-Functional Requirements

• Query latency — <200ms for web search, <50ms for autocomplete
• Freshness — Breaking news indexed within minutes, general content within hours
• Scale — Billions of documents, 100K+ QPS
• Relevance — Top-3 results contain the answer >80% of the time

Back-of-Envelope Estimation

System API Design

# Web search
GET /api/v1/search?q=distributed+consensus+algorithms
    &page=1&count=10&lang=en&safe=true

# Response
{
  "results": [
    {
      "url": "https://example.com/raft-consensus",
      "title": "Understanding Raft Consensus",
      "snippet": "Raft is a consensus algorithm designed...",
      "score": 0.87
    }
  ],
  "total_results": 1250000,
  "query_time_ms": 45,
  "spell_suggestion": null
}

# Autocomplete
GET /api/v1/suggest?q=distrib&limit=5
# ["distributed systems", "distributed consensus", ...]

# Index management (internal)
POST /api/v1/index/documents
{ "urls": ["https://example.com/page1"], "priority": "high" }

Data Model

-- Forward index (document store)
CREATE TABLE documents (
    doc_id      BIGINT PRIMARY KEY,
    url         TEXT,
    title       TEXT,
    content     TEXT,
    pagerank    FLOAT,
    crawled_at  TIMESTAMP,
    language    VARCHAR(5)
);

-- Inverted index (term -> document list)
-- Stored as: term -> [(doc_id, tf, positions), ...]
-- Compressed with variable-byte or PForDelta encoding

-- URL frontier (crawl queue)
CREATE TABLE url_frontier (
    url_hash    BIGINT PRIMARY KEY,
    url         TEXT,
    priority    FLOAT,
    last_crawl  TIMESTAMP,
    next_crawl  TIMESTAMP,
    domain      VARCHAR
);

-- Query logs (for autocomplete and ranking improvement)
CREATE TABLE query_logs (
    query       TEXT,
    count       BIGINT,
    clicked_urls TEXT[],
    timestamp   TIMESTAMP
);

High-Level Architecture

Deep Dive: Core Components

Inverted Index

from collections import defaultdict

class InvertedIndex:
    def __init__(self):
        # term -> [(doc_id, term_freq, [positions])]
        self.index = defaultdict(list)
        self.doc_lengths = {}

    def add_document(self, doc_id, text):
        tokens = self._tokenize(text)
        self.doc_lengths[doc_id] = len(tokens)
        term_positions = defaultdict(list)

        for pos, token in enumerate(tokens):
            term_positions[token].append(pos)

        for term, positions in term_positions.items():
            self.index[term].append(
                (doc_id, len(positions), positions)
            )

    def search(self, query, k=10):
        tokens = self._tokenize(query)
        scores = defaultdict(float)
        for token in tokens:
            for doc_id, tf, _ in self.index.get(token, []):
                scores[doc_id] += self._bm25(
                    tf, self.doc_lengths[doc_id], token
                )
        return sorted(scores.items(),
                      key=lambda x: -x[1])[:k]

BM25 Scoring

PageRank

Computes page authority from the link graph. Pages linked by many high-authority pages get higher scores. Computed offline via iterative MapReduce over the entire web graph. Combined with BM25 at query time.

Learning to Rank (LTR)

Modern search engines use ML models to combine 100+ ranking signals:

• Query-document features: BM25, title match, URL match
• Document features: PageRank, freshness, spam score, content quality
• User features: Click-through rate, dwell time, bounce rate
• Context: Location, device, time of day, search history

Autocomplete

Built on a trie data structure populated from query logs. Each node stores the top-K completions by frequency. Updated hourly from aggregated query logs. Served from memory with <10ms latency.

Scaling & Optimization

Index Sharding

Two strategies: document-based sharding (each shard holds all terms for a subset of documents) or term-based sharding (each shard holds posting lists for a subset of terms). Document-based is simpler and more common — query is broadcast to all shards, results are merged.

Query Optimization

• Early termination: Stop scoring once enough high-quality results are found
• Tiered index: Check high-quality documents first; only search lower tiers if needed
• Result caching: Cache top results for popular queries (40-60% cache hit rate)
• Skip lists: Efficiently intersect posting lists for multi-term queries

Practice Problems

Quick Reference