Chapter 24: Design a Search Engine

Curriculum: Distributed Systems from First Principles Chapter: 24 of 24 — The Final Chapter Part: 10 — Synthesis Design Problems Framework: Chapter 19's six-step process, applied in full Chapters exercised: Every chapter. This is the synthesis of the entire curriculum. Estimated reading time: 90–100 minutes

Opening: The Last Data Structure

You have now seen three fundamental storage data structures. The B-Tree (Chapter 2) is a balanced tree of fixed-size pages that keeps keys sorted and enables both exact lookups and range scans in O(log N) time — the workhorse of relational databases. The LSM tree (Chapter 10) separates writes (fast, sequential) from reads (merged across levels) using compaction to amortize reorganisation cost — the workhorse of write-heavy distributed databases. Each data structure enables the queries it was built for: B-Trees for "give me all records where price BETWEEN 10 AND 50," LSM trees for "write 100,000 records per second and read them back by key."

Neither handles the query that powers every modern product: "find all documents containing the words distributed systems design." This is full-text search — and it requires a completely different data structure: the inverted index.

The inverted index is named for what it inverts. A forward index maps document → list of words it contains. An inverted index maps word → list of documents containing it. This inversion is the key insight: given a query word, you can instantly find every document containing it by looking it up in the index, without scanning every document. At Google's scale — hundreds of billions of web pages — this is the only approach that works.

Search is everywhere: Google indexes the web, Elasticsearch powers log analytics (Chapter 18's ELK stack), Lucene powers Solr and Elasticsearch both, PostgreSQL's tsvector/tsquery implements full-text search inside a relational database, your SaaS product's search bar is backed by one of these engines. Understanding search from first principles means understanding how the inverted index is built, stored, compressed, queried, ranked, distributed, and kept fresh — and that requires almost everything in this curriculum.

Step 1: Requirements Clarification

The Problem

Design a search engine for an e-commerce platform: 500 million product listings, each with a title, description, category, price, and seller. Users search with natural language queries ("red running shoes size 10") and expect relevant results in under 200ms. New products are indexed within 60 seconds of being listed. The system must handle 10,000 queries per second at peak.

This is the scope: not Google's web crawler (which is a separate system), but the core search engine that takes an index of documents and a user query and returns ranked results. It is the heart of any search system.

Functional Requirements

1. Index a document: Receive a product listing, analyse its text, add it to the inverted index so future queries can find it.
2. Search: Given a query string, return the top-N most relevant documents ranked by relevance score.
3. Filter: Combine full-text search with structured filters: "red running shoes" AND price < 100 AND category = "footwear".
4. Autocomplete: As the user types "run", suggest "running shoes", "running socks", "runners", etc.
5. Near-real-time indexing: A newly listed product appears in search results within 60 seconds.
6. Update and delete: When a product's price changes or it is delisted, the index reflects the change within 60 seconds.

Non-Functional Requirements

• Scale: 500M documents, growing at 1M/day. 10,000 queries/second peak.
• Query latency: P99 < 200ms. (Users abandon search results after 500ms.)
• Index freshness: New documents searchable within 60 seconds.
• Relevance: Results must be meaningfully ranked — the most relevant results appear first.
• Availability: 99.99%. Search downtime directly costs revenue.

Step 2: Estimate Scale

Document count: 500M products
Average document size (title + description + metadata): ~2 KB raw text

Inverted index size:
  Unique terms across all documents: ~5M (after normalisation)
  Average document length: ~200 terms (after tokenisation)
  Total term occurrences: 500M docs × 200 terms = 100 billion term occurrences
  Posting list storage (compressed): ~5 bytes per entry (see compression section)
  Total: 100B × 5 bytes = 500 GB compressed index

Query load:
  10,000 queries/second peak
  Average query: 3 terms
  Each term lookup: one posting list fetch
  Total posting list fetches: 10,000 × 3 = 30,000/second

Index growth:
  1M new products/day × 200 terms = 200M new posting list entries/day
  At 5 bytes each: 1 GB of new index data per day

Query latency budget (200ms total):
  Network (client → search service): 5ms
  Query parsing + analysis: 2ms
  Posting list fetches (from index): 10–50ms (target: < 30ms, must be in memory/SSD)
  Ranking + scoring top-K results: 20–50ms
  Result serialisation + response: 5ms
  Total target: ~80ms → comfortable headroom under 200ms

Critical insight: 500 GB of compressed index must be queryable in < 30ms. A single SSD's random read latency is ~100μs (Chapter 1). Fetching 3 posting lists × ~100μs = ~300μs if everything is on one SSD. The bottleneck is not I/O latency per fetch — it's the cost of merging posting lists and ranking thousands of candidate documents. At 10,000 queries/second, one machine handling all queries would need to process 10,000 × (posting list merge + ranking) per second — too much for one CPU. Horizontal sharding of the index is needed.

Step 3: The Inverted Index — Physical Reality

Before distributed anything, understand what an inverted index physically is.

Building the Index from Documents

Given these three documents:

Doc 1: "fast distributed database systems"
Doc 2: "distributed consensus in database design"
Doc 3: "fast query execution in database"

Step 1: Tokenisation. Split text into tokens (words):

Doc 1: ["fast", "distributed", "database", "systems"]
Doc 2: ["distributed", "consensus", "in", "database", "design"]
Doc 3: ["fast", "query", "execution", "in", "database"]

Step 2: Normalisation. Lowercase, remove punctuation, remove stop words ("in", "a", "the" — too common to be useful, bloat the index):

Doc 1: ["fast", "distributed", "database", "systems"]
Doc 2: ["distributed", "consensus", "database", "design"]
Doc 3: ["fast", "query", "execution", "database"]

Step 3: Stemming or Lemmatisation. Reduce words to their root form so "running," "runs," "ran" all map to "run." The Porter Stemmer algorithm (1980, still widely used): "systems" → "system", "execution" → "execut", "distributed" → "distribut". Lemmatisation (more linguistically correct but slower): uses a dictionary to map "ran" → "run," "better" → "good." For a product search engine, stemming is sufficient.

Doc 1: ["fast", "distribut", "databas", "system"]
Doc 2: ["distribut", "consensus", "databas", "design"]
Doc 3: ["fast", "queri", "execut", "databas"]

Step 4: Build the inverted index. For each term, record which documents contain it (the posting list):

INVERTED INDEX (forward: term → posting list):

"databas"    → [1, 2, 3]           (all three docs contain "database")
"distribut"  → [1, 2]              (docs 1 and 2)
"fast"       → [1, 3]              (docs 1 and 3)
"system"     → [1]                 (only doc 1)
"consensus"  → [2]
"design"     → [2]
"queri"      → [3]
"execut"     → [3]

Each posting list is a sorted list of document IDs (sorted for efficient merging). This is the core data structure. Query "distributed database": look up "distribut" → [1, 2]. Look up "databas" → [1, 2, 3]. Intersect (AND): [1, 2]. Documents 1 and 2 contain both terms.

Posting List Compression — Why It Matters

A real inverted index has billions of entries. The word "the" in English text appears in virtually every document — a posting list of 500M document IDs at 4 bytes each = 2 GB for one term. Compression is essential.

Delta encoding: Instead of storing absolute document IDs, store the gap between consecutive IDs:

Raw posting list: [142, 149, 155, 163, 170]
Delta-encoded:    [142, 7, 6, 8, 7]

Gaps are much smaller than absolute IDs — they can be encoded in fewer bits.

Variable-length encoding (VByte): Encode small numbers in fewer bytes. Numbers 0–127: 1 byte. Numbers 128–16383: 2 bytes. Delta-encoded gaps are typically small (adjacent documents about the same topic are often indexed near each other), so most gaps encode in 1–2 bytes instead of 4.

Result: Typical compression ratio of 5:1 to 10:1. A 500M-document index that would be 2 TB uncompressed becomes 200–400 GB compressed — potentially fitting on a single high-memory server's NVMe SSD.

Real systems go further: Lucene (Elasticsearch's index library) uses a combination of delta encoding, FOR (Frame of Reference) encoding, and SIMD-accelerated intersection algorithms that process posting list intersections at >1 billion document IDs per second on modern hardware.

The Full Posting List Entry — Beyond Document IDs

A bare posting list (just document IDs) lets you answer "which documents contain this term?" but not "how many times does this term appear in this document?" or "where exactly in the document does it appear?" For ranking and phrase search, you need richer information.

Posting list entry (full):
  doc_id:       4 bytes (document identifier)
  term_freq:    2 bytes (how many times this term appears in this document)
  positions:    variable (byte offsets where the term appears — for phrase search)
  field_mask:   1 byte  (which fields contain the term: title=1, description=2, both=3)

Example: term "running", doc_id 8821
  doc_id=8821, term_freq=3, positions=[5, 47, 103], field_mask=3 (title+description)
  → The word "running" appears 3 times in document 8821,
    at positions 5, 47, and 103 in the text,
    in both the title and description fields.

Positions enable phrase search: Query "running shoes" (exact phrase, not just both words anywhere). Intersect posting lists for "running" and "shoes," then check: is there a document where "shoes" appears at position = (position of "running") + 1? This requires position data in the posting list. Position data increases the index size significantly — many search engines store positions only for a subset of important fields.

Step 4: Relevance Ranking — What Makes a Result Good?

Finding documents that contain the query terms is the easy part. Ranking them by relevance is what separates useful search engines from useless ones. If a user searches "running shoes," a document that mentions "running shoes" once in passing is less relevant than a product listing titled "Nike Running Shoes" that contains "running" and "shoes" throughout.

TF-IDF — The Foundation

TF (Term Frequency): How often does the query term appear in this document? A document that mentions "running" 10 times is probably more about running than one that mentions it once.

TF(term, doc) = count of term in doc / total terms in doc
  (normalised by document length to avoid bias toward longer documents)

IDF (Inverse Document Frequency): How rare is this term across all documents? "Running" appears in millions of documents — not very discriminating. "Plantar fasciitis" appears in far fewer — a document containing it is strongly relevant to that query.

IDF(term) = log(total_documents / documents_containing_term)

"running":         log(500M / 50M)  = log(10)  ≈ 2.3  (common term, low IDF)
"plantar fasciitis": log(500M / 5K) = log(100K) ≈ 11.5 (rare term, high IDF)

TF-IDF score:

TF-IDF(term, doc) = TF(term, doc) × IDF(term)

For query "running shoes", document 8821:
  score = TF-IDF("running", 8821) + TF-IDF("shoes", 8821)
        = (3/150 × 2.3) + (2/150 × 1.8)
        = 0.046 + 0.024 = 0.070

The document with the highest sum of TF-IDF scores for all query terms is returned first.

BM25 — The Industry Standard

TF-IDF has a problem: TF grows unboundedly — a document that says "running" 1,000 times is not 1,000× more relevant than one that says it once. BM25 (Best Match 25, developed in the 1990s at City University London) adds saturation and length normalisation:

BM25(term, doc) = IDF(term) × 
                  [TF × (k1 + 1)] / [TF + k1 × (1 - b + b × doc_len/avg_doc_len)]

Parameters:
  k1 = 1.5  (term frequency saturation: diminishing returns after TF exceeds k1)
  b  = 0.75 (length normalisation: penalise long documents that mention a term many times
              only because they are long)
  avg_doc_len: average document length across the corpus (precomputed, stored globally)

Effect of k1: TF=1 contributes 0.8 to the numerator. TF=10 contributes 0.94. TF=100 contributes 0.99.
  → BM25 saturates. Mentioning "running" 100 times is barely better than mentioning it 10 times.
  → Prevents spam documents from gaming the ranking by keyword stuffing.

BM25 is the default ranking function in Elasticsearch, Apache Solr, and Lucene. It requires storing two global statistics per term: document_frequency (number of documents containing the term, for IDF) and globally: avg_doc_len. These are computed during index construction and stored in the index metadata.

Field Weighting

Not all text fields are equal. A product title mentioning "running shoes" is stronger evidence of relevance than the description mentioning it. Field-weighted BM25:

score(query, doc) = 
  α × BM25_title(query, doc) +
  β × BM25_description(query, doc) +
  γ × BM25_category(query, doc)

Where α > β > γ (title weight > description weight > category weight)
Typical: α=3.0, β=1.0, γ=0.5

Field weights are tuned experimentally using click-through data (do users click on the results we rank first?) and A/B tests.

Beyond Text: Signals for E-Commerce Ranking

BM25 is purely textual relevance. E-commerce search also needs:

Final score = BM25_text_score 
            × price_boost        (discounted items get a boost)
            × recency_boost      (new products get a temporary boost)
            × popularity_signal  (products with more purchases rank higher)
            × in_stock_filter    (out-of-stock items buried or removed)
            + seller_quality     (highly rated sellers get a small boost)

popularity_signal = log(1 + purchase_count_30d)  (log to prevent monopoly by top sellers)

This is learning-to-rank: instead of manually tuning weights, train a machine learning model on historical click data to learn the optimal combination. Given a (query, document) pair and the user's historical interaction (did they click? did they purchase?), the model learns the combination of features (BM25 score, price, popularity, recency, seller rating) that best predicts user satisfaction. Gradient Boosted Decision Trees (GBDT) are the standard model for learning-to-rank — fast inference (<1ms per document), interpretable, and well-calibrated.

Step 5: Query Processing Pipeline

A search query goes through multiple transformations before hitting the inverted index.

Query Analysis

Critical invariant: The query analysis pipeline must be identical to the document analysis pipeline. If documents are stemmed with the Porter Stemmer, queries must be stemmed the same way. If "running" → "run" at index time, queries must also apply the same stemmer so "running" → "run" matches indexed "run." Mismatched pipelines silently produce zero results.

Boolean Query Execution

Given query terms ["red", "run", "shoe"], fetch their posting lists:

"red"  → [42, 88, 142, 303, 8821, ...]   (10M documents)
"run"  → [33, 88, 303, 8821, 9041, ...]  (8M documents)
"shoe" → [88, 8821, 9041, 12003, ...]    (3M documents)

AND query (all terms must appear): Intersect the three posting lists. The efficient algorithm:

SORTED MERGE INTERSECTION:
  Start with the smallest posting list (lowest cardinality): "shoe" → 3M docs
  
  For each doc_id in "shoe" posting list:
    Binary search "red" posting list for doc_id → O(log 10M) per check
    Binary search "run" posting list for doc_id → O(log 8M) per check
    If found in both: add to candidate set
  
  Result: documents in all three posting lists.
  Complexity: O(|smallest| × log(|others|))
  
  With SIMD acceleration (Lucene's approach):
    Process 256 doc_ids simultaneously using AVX-512 instructions.
    Intersection of 3 million vs 8 million doc list: ~10ms on modern hardware.

OR query (any term may appear): Merge all posting lists, include union. Less selective — returns more results, requires more aggressive ranking to surface the best ones.

Phrase query "running shoes": AND intersection of "run" and "shoe" posting lists, then filter: only keep documents where the position of "shoe" = position of "run" + 1 (adjacent in original text). Requires position data in the posting list.

Top-K Retrieval — Not All Candidates Need Full Ranking

After intersection, you may have 100,000 candidate documents for "red running shoes." You need the top 10. Ranking all 100,000 with full BM25 + learning-to-rank is expensive. Optimisations:

Early termination: Sort the candidate posting lists by their precomputed "impact" scores (TF-IDF max possible score for this term). Process candidates in decreasing impact order. Once you have K documents with scores higher than the maximum possible score of any remaining candidate, stop. Lucene's WAND (Weak AND) and BMW (Block-Max WAND) algorithms implement this — they can rank top-10 from 10 million candidates in <5ms by skipping low-impact candidates entirely.

Two-phase ranking: Phase 1: fast BM25 on top-1,000 candidates (<5ms). Phase 2: expensive learning-to-rank model on top-100 from phase 1 (<10ms). Return top-10 from phase 2. This two-phase approach is standard in production — the expensive model runs on a small shortlist, not on all candidates.

Step 6: The Index on Disk — Segments

The inverted index is not a single monolithic data structure. It is composed of segments — immutable, self-contained index files. This is Lucene's architecture, which is almost identical to LSM tree segment files (Chapter 10 — not a coincidence; both optimise for write throughput by making segments immutable).

SEGMENT STRUCTURE:
  segment_1/
    terms.idx         (term dictionary: term → byte offset in postings.dat)
    terms.dat         (FST — Finite State Transducer — for term lookup)
    postings.dat      (posting lists: doc IDs, term frequencies, positions)
    doc_values.dat    (stored field values: price, category, seller — for filtering/sorting)
    norms.dat         (pre-computed document length norms for BM25)
    bloom_filter      (fast "term not in this segment" check — Chapter 10's bloom filter)
    del.bits          (bitset of deleted/updated documents — soft deletes)

FST (Finite State Transducer) for the term dictionary: A term dictionary maps a term string to the byte offset of its posting list in the postings file. With 5 million unique terms, a hash map would use hundreds of MB. An FST (a deterministic acyclic finite state automaton) encodes the term dictionary as a compressed directed acyclic graph — the entire 5M-term dictionary fits in ~50 MB, is binary-searchable in O(term_length) time, and supports prefix lookups (essential for autocomplete). Lucene invented its own FST implementation specifically for this.

Segment merging (identical to LSM compaction — Chapter 10): New documents are written to a small new segment. As segments accumulate, a background merging process combines small segments into larger ones, removing deleted documents in the process. Without merging, a query must search N segments independently and merge the results — O(N) overhead. The merge policy targets keeping N small (typically 10–20 active segments). This is Chapter 10's LSM compaction, applied to inverted indexes. The insight was the same: sequential writes (new segments) are fast, and the read cost (searching multiple segments) is paid down by periodic merging.

Soft deletes: When a document is deleted (product removed from the platform) or updated (price changed), the old document is not immediately removed from the segment (segments are immutable). Instead, the document's ID is added to the segment's del.bits bitset. During queries, results matching deleted documents are filtered out. During segment merging, deleted documents are garbage-collected. This is the inverted index equivalent of LSM tombstones (Chapter 10).

Step 7: Distributed Search — Sharding the Index

500M documents, 500 GB of compressed index. One machine with fast NVMe SSD can hold this, but:

• Query throughput: 10,000 queries/second × (30ms posting list merge + 20ms ranking) = more CPU than one machine can handle
• Availability: one machine = single point of failure (Chapter 4's reliability analysis)

The solution: shard the index across multiple machines.

Index Sharding

Unlike a database (Chapter 7), an inverted index is not sharded by a natural key. It is sharded by document: the corpus of 500M documents is divided into N shards, each holding 500M/N documents and their associated index structures.

SHARDING BY DOCUMENT:
  Shard 1: doc_id 1 to 50M      (all product listings, IDs 1-50M)
  Shard 2: doc_id 50M to 100M
  ...
  Shard 10: doc_id 450M to 500M

  Each shard: ~50M documents, ~50 GB compressed index
  Fits on one machine with NVMe SSD.
  Each shard can answer queries independently for its document set.

Why by document (not by term)? If you shard by term ("all documents for terms A–M go to shard 1, N–Z to shard 2"), then a multi-term query must hit every shard (terms from different shards). The result is the same scatter-gather overhead. Document sharding is simpler, better understood, and allows each shard to compute local BM25 statistics accurately.

Scatter-Gather Query Execution (Chapter 7)

The global vs local statistics problem: BM25 uses IDF, which requires knowing how many documents (globally) contain a term. If a shard only knows about its own 50M documents, its IDF computation is wrong. Two approaches:

• Global statistics (correct but costly): During index construction, compute global IDF (from the full 500M corpus) and store it in every shard. Each shard uses the same global IDF, so BM25 scores are globally comparable. This requires a periodic global statistics recomputation job (run nightly or after large index updates).

• Local statistics + score normalisation (fast but approximate): Each shard computes BM25 using only its local document count. Scores from different shards are not directly comparable (shard 1 has different term frequencies than shard 2). The coordinator normalises scores before merging. Practical for large systems — the approximation is good enough that it rarely changes the top-10 ranking.

Elasticsearch defaults to local statistics per shard (approximation) for speed. You can configure global statistics mode if ranking accuracy is critical.

Replication for Availability and Throughput

Each shard is replicated (Chapter 4 — replication for fault tolerance and read scaling):

Writes are acknowledged when a majority (2 of 3) confirm (Chapter 12's quorum); shards 3–10 follow the same layout. Reads go to one replica of each shard, so 3 replicas give 3× the query throughput of a single replica: at 10,000 queries/second with 10 shards × 3 replicas, each replica handles 10,000 / (10 × 3) = 333 queries/second → comfortable.

Replication also enables zero-downtime index upgrades: take one replica offline, update its index software, reindex the shard, bring it back online. Repeat for other replicas. The shard remains available throughout (other replicas serve queries).

Step 8: Near-Real-Time Indexing

A product is listed at T=0. It must be searchable at T=60s. This is the "near-real-time" (NRT) indexing requirement.

The Indexing Pipeline

Latency breakdown:
  Kafka produce + consume: ~500ms (at-most-once latency from Chapter 15)
  Text analysis: ~10ms
  Buffer write: <1ms
  Flush to disk: ~50ms
  Total: ~561ms per document → well within 60-second requirement.

Why the 1-second flush instead of immediate? Writing each document to a new segment immediately would create millions of tiny segment files. Merging overhead would dominate. The 1-second buffer amortizes the flush cost: at 1M documents/day ≈ 11.6 documents/second, a 1-second buffer accumulates ~12 documents per flush. The new segment contains 12 documents instead of 1. Background segment merging keeps the total segment count manageable.

The refresh interval: Elasticsearch calls the 1-second flush a "refresh." The refresh interval is configurable: 1 second for NRT, 30 seconds for bulk indexing (where you want to buffer more documents per segment). During bulk reindexing of the full 500M product corpus (e.g., after a ranking algorithm change), set refresh interval to 30 seconds or longer to maximise throughput.

Document Updates

When a product's price changes from $99 to $79:

OPTION 1: In-place update
  Find the document in its segment.
  Update the price field.
  Problem: segments are immutable. Can't update.

OPTION 2: Delete + re-insert
  Add doc_id to the segment's del.bits (soft delete the old version).
  Write a new document with updated price to the in-memory buffer.
  After flush: the new version appears in the new segment; old version is soft-deleted.
  After merge: old version is physically removed.
  
  This is how Lucene (and therefore Elasticsearch) handles updates.
  The cost: temporarily two versions of the document exist (old soft-deleted + new).
  For high-update documents (popular products with frequent price changes),
  the del.bits ratio can grow high until the next merge — slightly inflating index size.

Step 9: Filtering — Structured Queries Combined with Full-Text

Most search queries have both a text component and structured filters: "running shoes" AND price < 100 AND in_stock = true AND category = "footwear".

Naive approach: compute BM25 scores for all 100,000 candidates, then filter by price and stock. Wasteful — many candidates are filtered out.

Pre-filtering (using doc_values): The doc_values column in each segment stores structured field values (price, category, in_stock) in a column-oriented format, sorted by doc_id. A range query price < 100 produces a bitset: bit N is set if doc N has price < 100. This bitset is AND-ed with the posting list intersection result, eliminating non-matching candidates before BM25 scoring.

Bitset operations (AND, OR, NOT) are extremely fast with SIMD — 256 documents checked per CPU instruction. Filtering 500M documents with 3 bitsets: ~2ms.

Faceted search: The sidebar on an e-commerce page showing "Brand: Nike (12,043), Adidas (8,921), New Balance (6,733)..." For each candidate document matching the text query, count documents per facet value. This is an aggregation over the query result set. Elasticsearch's aggregation framework does this in parallel per shard (local counts) then merges at the coordinator. Precomputed facet counts for popular queries are cached (Chapter 9's cache-aside) with a 5-minute TTL.

Step 10: Autocomplete — The Trie

As the user types "run", the search bar suggests "running shoes", "running socks", "runners high". This is autocomplete — suggest completions for a partial query.

The inverted index is not designed for prefix queries. It finds documents containing a term — it cannot efficiently find all terms starting with "run".

The Trie Data Structure

A trie (prefix tree) is optimised for prefix lookups. Each node in the trie represents one character. The path from root to a node spells a prefix. Each leaf (or marked internal node) represents a complete term.

Trie for ["red", "run", "running", "runner"].

Prefix lookup: "What terms start with 'run'?" Walk the trie: root → r → u → n. Found the node for "run". Collect all leaves below: "run", "runner", "running". O(prefix_length + result_count).

Autocomplete with popularity ranking: Instead of suggesting all terms starting with "run", suggest the most popular ones. Store, at each trie node, the top-K (K=5) most popular completions from that subtree. Lookup becomes O(prefix_length) — no traversal needed, the node already knows the top-5 completions.

Node "run":
  completions: [
    ("running shoes", popularity=10M queries/month),
    ("runners",       popularity=2M),
    ("running socks", popularity=1.5M),
    ("run",           popularity=1M),
    ("runner",        popularity=800K)
  ]

User types "run" → instantly return these 5 suggestions from the trie node.

Trie storage: 5M unique search terms × 100 bytes per node ≈ 500 MB. Fits in memory on one machine. The trie is read-heavy (every keystroke = one trie lookup) and write-rarely (updated nightly with new popularity counts from query logs). Store in Redis or a dedicated in-memory structure. Rebuild nightly from the query log analytics.

Typo tolerance: Users mistype. "runnign shoes" → should suggest "running shoes". The trie alone doesn't handle this. Two approaches:

• Edit distance (BK-Tree): Index all terms in a BK-Tree, a metric space data structure that enables O(log N) search for terms within Levenshtein edit distance K. K=1 catches single-character transpositions and missing letters.
• N-gram autocomplete: Index character n-grams (substrings of length N) separately. "running" → {"run", "unn", "nni", "nin", "ing"}. A query "runnign" → {run, unn, nni, nig, ign} — most n-grams overlap with the correct term's n-grams. Return terms with the highest n-gram overlap.

Elasticsearch's completion suggester uses a weighted FST (similar to the term dictionary FST). Elasticsearch's search_as_you_type field type builds n-gram index for typo-tolerant autocomplete.

Step 11: Index Construction at Scale — Bulk Indexing

Building the initial index for 500M products (or reindexing the entire corpus after a ranking change) is a bulk indexing problem — it is fundamentally different from the NRT single-document indexing pipeline.

MapReduce-style bulk indexing (Chapter 15's batch processing paradigm):

Total bulk index build time: ~2.5 hours for 500M documents.
Compare: NRT indexing at 11.6 docs/second = 500M / 11.6 = 497 days.
Bulk indexing is 200× faster for full corpus construction.

After bulk indexing: swap the new index into production. The "hot swap" is Elasticsearch's index alias feature: the search service queries the alias "products" which points to the old index. After bulk construction completes: atomically update the alias to point to the new index. Zero downtime, instantaneous switch.

Step 12: The Separate Document Store

The inverted index answers "which documents match this query and what are their scores?" It does not efficiently store and retrieve the full document content (title, description, all metadata). Storing full document content in the index would make segments huge.

The forward store (document store): A separate key-value store (often the same node, different data structure) maps doc_id → {title, description, price, image_url, seller, ...}. When the search coordinator has the top-10 (doc_id, score) pairs, it fetches the full document content from the document store in parallel.

Inverted index: doc_id 8821 → score 0.847
Document store: doc_id 8821 → {
  "title": "Nike Air Zoom Running Shoes",
  "description": "Lightweight cushioned running shoes...",
  "price": 89.99,
  "image_url": "s3://products/8821/main.jpg",
  "seller": "Nike Official Store",
  "rating": 4.7,
  "review_count": 12841
}

In Elasticsearch, this is the _source field — the original JSON document stored alongside the index. In a high-performance e-commerce search engine, the document store is often a separate Redis cluster (for low-latency retrieval of top-10 product cards) or the product database's read replica.

Step 13: The Complete Architecture

Off the query path — indexing, autocomplete and monitoring:

Step 14: Failure Modes

One shard's primary fails: The replica is promoted to primary (Chapter 12's Raft election or Elasticsearch's shard allocation). During promotion (~30 seconds): queries to that shard fail. The coordinator retries on the surviving replica. If a replica exists and is current: queries succeed (result set is complete). If no healthy replica: queries return incomplete results (top-10 from 9 shards instead of 10 — 10% of the document space is missing). Acceptable for most queries (the missing 10% rarely contains the best-ranked results for common queries).

Coordinator failure: Stateless — any coordinator node can handle any query. The load balancer (Chapter 16) routes to a healthy coordinator. No state lost.

Kafka consumer lag (indexing pipeline delay): Indexing workers fall behind. New products take longer to appear in search results. Monitor kafka_consumer_lag per shard (Chapter 18's critical metric for any Kafka consumer). Alert if lag exceeds 60,000 events (60 seconds of documents at 1,000 docs/second peak). Scale indexing workers horizontally by adding more Kafka consumer instances.

Split-brain during network partition (Chapter 6): Two replicas of shard 1 each believe they are the primary. Both accept writes independently. When the partition heals: one replica has documents the other doesn't. Resolution: Elasticsearch uses a majority-quorum leader election (Chapter 12's Raft election). The replica that did not have quorum is fenced and resyncs from the elected primary. No permanent divergence — the fenced replica replays missed index operations from the Kafka topic (the index operation log is the Kafka topic — a durable replay source, Chapter 15).

Step 15: The Whole Curriculum, One Final Time

This is the last chapter. Every system in the curriculum connects to search:

Chapter 1 (Latency): The 200ms query latency budget is allocated across network, posting list merge, ranking, and serialisation. Every millisecond matters. SIMD-accelerated posting list intersection and early-termination algorithms exist because the latency constraint is real.

Chapter 2 (B-Tree, WAL): The term dictionary is an FST — a more sophisticated sorted structure than a B-Tree, but the insight (sorted access for range queries, specifically prefix queries for autocomplete) is the same. WAL is why the inverted index survives crashes: the Kafka topic is the WAL for the indexing pipeline.

Chapter 3 (Indexes): The inverted index is an index — specifically, an index optimised for the access pattern "given a value (a term), find all rows (documents) containing it." B-Tree secondary indexes serve "given a value, find rows with that exact value." The inverted index serves "given a term, find all documents mentioning it, ranked by relevance." Different access pattern, different data structure.

Chapter 4–5 (Replication): Each index shard has 3 replicas. Writes replicate synchronously to achieve durability. Reads are served from any replica. Replica promotion handles primary failures. Replication lag means freshly indexed documents may briefly be present on the primary but not yet on replicas — an acceptable form of read-your-writes inconsistency for search.

Chapter 6 (Consistency): Search is eventually consistent by design. A product listed 45 seconds ago may not yet be searchable. This is acceptable — no one expects search results to reflect inventory changes in milliseconds. The 60-second freshness SLO is a deliberately relaxed consistency guarantee.

Chapter 7–8 (Sharding, Consistent Hashing): The index is sharded by document ID. New documents are assigned to shards using a hash function (Chapter 8). When shards are added, documents are rebalanced by reindexing (bulk indexing pipeline — Chapters 7's rebalancing cost is acceptable because reindexing is a background operation). Consistent hashing is not used for index sharding (documents don't move between shards during normal operation), but is used for routing search queries to shard replicas (Chapter 8's load balancing within a shard replica set).

Chapter 9 (Caching): The search result cache (Redis, 5-minute TTL) serves ~40% of queries without touching the index. The trie for autocomplete is an in-memory cache of popular term completions, rebuilt nightly. The document store cache holds top-ranked product details. Cache stampede is prevented by request coalescing for unpopular queries (singleflight pattern).

Chapter 10 (LSM Trees): Segment-based index architecture is directly analogous to LSM trees. New documents → small segments → background merging → fewer larger segments. Segment merging is compaction. Soft deletes are tombstones. Bloom filters per segment eliminate unnecessary segment scans. The intellectual ancestry is shared: Lucene's segment design and LevelDB's LSM tree were developed contemporaneously and informed each other.

Chapter 11–12 (Consensus, Raft): Shard leader election uses Raft (Elasticsearch uses a Raft-like protocol in its cluster coordination). The leader election determines which replica is primary and therefore which replica processes index writes. The correctness guarantee: only one primary per shard at any time.

Chapter 13 (Distributed Transactions): Indexing a product update (delete old version + insert new version) is a distributed transaction if the old version is in shard 1 and the new document goes to shard 2 (due to a new doc_id). In practice: same doc_id = same shard. Updates stay within one shard. No distributed transactions needed for index updates — the shard boundary is aligned to document identity.

Chapter 14–15 (Message Queues, Kafka): The indexing pipeline uses Kafka as the source of truth. Kafka topic = WAL for the index. Consumer lag = indexing freshness metric. Partitioning Kafka by doc_id ensures a document's updates are processed in order (no version inversion — a price update arriving after a deletion would resurrect a deleted product). Exactly-once semantics (Chapter 15) prevent duplicate index entries from retry-stormed indexing workers.

Chapter 16 (Load Balancing): The query service and search coordinator are stateless — any instance handles any query. L7 load balancing routes queries round-robin across coordinators. Within a shard, queries are load-balanced across replicas using least-connections (the shard with the fastest recent response time gets the next query).

Chapter 17 (Rate Limiting): Search queries are expensive. A single poorly-crafted query (very common terms with millions of candidate documents) can consume a coordinator for 500ms. Rate limiting per merchant API key (if this is a B2B search API) prevents one customer's expensive queries from degrading all others. Per-IP rate limiting on the public-facing search API protects against scrapers.

Chapter 18 (Observability): Kafka consumer lag per shard is the indexing freshness metric. Query latency histograms per shard identify slow shards (compaction backlog, hardware degradation). Cache hit rate trending downward indicates search result diversity increasing (fewer repeated queries). The dead man's switch: if a shard stops emitting metrics, page immediately.

Chapter 19 (Design Framework): Requirements (NRT indexing, 200ms latency, 10K QPS) → estimation (500 GB index, 10 shards) → data model (inverted index, doc values, document store) → read path (scatter-gather query, BM25 ranking, top-K) → write path (Kafka → index workers → segments) → failure modes (shard failure, coordinator failure, partition). The framework held.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

An e-commerce search system has 10 shards, each with replication factor 3. During a network partition, Shard 5's primary (Node 15) loses connectivity to its two replicas (Nodes 16 and 17) but remains connected to the search coordinator. Node 15 continues accepting index writes (new product listings). After 10 minutes, 1,200 new documents are indexed only on Node 15.

(a) During the partition: when the coordinator fans out a search query to all 10 shards, what happens to the Shard 5 query? Node 15 responds (it's still connected to the coordinator). Are the results complete? Are the 1,200 documents in the results?

(b) A cluster management system detects the partition after 30 seconds and demotes Node 15 (it cannot reach quorum — only 1 of 3 nodes). Nodes 16 and 17 elect a new primary. What happens to queries during the 30-second partition before demotion? What happens to the 1,200 documents indexed on Node 15?

(c) When the partition heals and Node 15 reconnects: it has 1,200 documents that Nodes 16 and 17 don't have. How does the system reconcile? (Hint: the Kafka topic is the source of truth — the indexing pipeline wrote all 1,200 documents to Kafka before writing to Node 15. What does Node 15 do?) After reconciliation, how long until the 1,200 documents are searchable again?

(d) Connect to Chapter 6's CAP theorem: which consistency model does this search system provide under normal operation? Under partition? If you chose to keep Node 15 as primary during the partition (accepting writes without quorum), which CAP property are you prioritising? What is the risk?

Problem 2 — Design from Scratch

Design a personalised search system: the same query "running shoes" returns different results for different users based on their purchase history, browsing behaviour, and location.

(a) The base search returns a global ranked list. Personalisation re-ranks the top-100 results for a specific user. Design the personalisation layer: what user signals are used (purchase history, category affinity, price sensitivity, brand preference, location), how are they stored (what database — apply Chapter 19's storage decision tree), and how is personalisation applied (as a re-ranking model on top of global BM25, or by modifying the BM25 query itself with boosting)?

(b) User privacy: storing detailed browsing and purchase history per user raises GDPR concerns. Design a privacy-preserving personalisation approach using a user embedding vector (a dense 64-dimensional float vector that encodes the user's preferences without storing raw behaviour). How is the embedding computed (offline, nightly, from anonymised click logs)? How is it used during query time (add it to the query feature vector for the learning-to-rank model)? What is the trade-off compared to storing full behavioural history?

(c) The personalisation model runs in <10ms (fast inference). But the global scatter-gather already uses most of the 200ms latency budget (150ms for 10 shards). Where in the pipeline does personalisation fit? Can it run in parallel with the scatter-gather phase? Design the latency-optimal pipeline: what runs first, what runs in parallel, and where the 200ms budget is allocated across all steps.

Problem 3 — Synthesis

Connect the search engine to Chapter 10's LSM trees and Chapter 15's Kafka.

(a) Segment merging in a search index is directly analogous to compaction in an LSM tree. For each LSM concept below, identify the exact corresponding search index concept and explain the analogy:

• Memtable → ?
• SSTable → ?
• Compaction → ?
• Tombstone → ?
• Bloom filter → ?
• Leveled compaction strategy → ?

(b) The indexing pipeline uses Kafka partitioned by doc_id. This ensures updates to the same document are processed in order — a price update arriving after a deletion doesn't resurrect a deleted product. But what happens during a Kafka partition rebalance (Chapter 15's cooperative rebalancing)? For 30 seconds during rebalancing, no consumer is processing the partition. 500 documents are updated during this window. When the new consumer takes over: it reads from the last committed offset and processes all 500 updates. Are any documents permanently missed? Are any documents temporarily stale in the index during the 30-second window? Connect to Chapter 15's at-least-once delivery guarantee.

(c) A ranking algorithm change requires reindexing all 500M products (the BM25 field weights changed). Design the zero-downtime reindex:

• Phase 1: bulk index construction (2.5 hours) into a new index "products_v2"
• Phase 2: NRT indexing catchup (newly listed products during the 2.5-hour bulk index must be added to products_v2)
• Phase 3: atomic alias switch from "products_v1" to "products_v2"
• Phase 4: decommission products_v1

What Kafka consumer offset strategy handles Phase 2? (Hint: record the Kafka offset at the start of bulk indexing; replay from that offset into products_v2 after bulk construction completes.) How long does Phase 2 take given the offset gap accumulated during 2.5 hours of bulk indexing?

Problem 4 — Go Deeper

Analyse BM25 ranking under adversarial conditions (SEO spam).

A seller lists a product with the title: "running shoes running shoes running shoes Nike Adidas New Balance running shoes running shoes" — the term "running shoes" repeated 10 times in the title.

(a) Compute the BM25 TF component for this document vs. a legitimate document with title "Nike Air Zoom Running Shoes" (term "running" appears once). Use k1=1.5, b=0.75, avg_doc_len=20 terms, spam_doc_len=50 terms, legit_doc_len=8 terms.

BM25_TF(term, doc) = TF × (k1+1) / (TF + k1 × (1 - b + b × doc_len/avg_doc_len))

Spam doc (TF=10, doc_len=50):
  = 10 × 2.5 / (10 + 1.5 × (0.25 + 0.75 × 50/20))
  = 25 / (10 + 1.5 × (0.25 + 1.875))
  = 25 / (10 + 1.5 × 2.125)
  = 25 / (10 + 3.1875)
  = 25 / 13.19 ≈ 1.90

Legit doc (TF=1, doc_len=8):
  = 1 × 2.5 / (1 + 1.5 × (0.25 + 0.75 × 8/20))
  = 2.5 / (1 + 1.5 × (0.25 + 0.3))
  = 2.5 / (1 + 1.5 × 0.55)
  = 2.5 / (1 + 0.825)
  = 2.5 / 1.825 ≈ 1.37

The spam document scores higher on text relevance alone (1.90 vs 1.37). How does the overall ranking system prevent the spam document from outranking the legitimate Nike product? Which signals in the full ranking formula (beyond BM25) would correctly down-rank the spam document? (Hint: popularity signal, seller quality score, user behaviour signals — do users click on keyword-stuffed titles?)

(b) Design a spam detection mechanism at index time (before the document enters the index): what signals in the document itself indicate keyword stuffing (term repetition ratio, title-to-description similarity, term frequency deviation from the corpus mean)? Should detected spam be rejected, down-weighted, or indexed normally but flagged for human review?

Problem 5 — Connect All 24 Chapters

This is the final problem of the curriculum. For each component in the search engine architecture, identify which specific chapter's concept it applies and explain the connection in one precise sentence.

The components:

(a) Kafka partitioned by doc_id for the indexing pipeline — which chapter, which specific concept, and what property of Kafka does it provide that makes it the correct tool here?

(b) Bloom filters per segment for miss avoidance — which chapter? What is the false positive rate, and what is the consequence of a false positive in the search context (unnecessary disk read) vs. the consequence of a false negative (impossible — explain why)?

(c) BM25's IDF requiring the total document count and per-term document frequency — these are statistics maintained globally across all shards. Which chapter's "global vs local statistics" problem does this recall? (Hint: Chapter 7's cross-shard aggregation) How does a sharded search engine handle computing the global IDF across 10 shards?

(d) Shard leader election after primary failure — which chapter, which exact algorithm? What is the invariant that the algorithm preserves (only one primary per shard), and why does violating it (split-brain: two primaries) cause data corruption in the index?

(e) The search result cache (Redis, 5-minute TTL) — which chapter's caching strategy? Why is 5 minutes an appropriate TTL for search results (connect to the 60-second NRT indexing SLO — what is the worst case staleness)? What failure mode from Chapter 9 does the cache prevent, and at what traffic pattern does this failure mode occur?

(f) The trie for autocomplete, rebuilt nightly from query logs — which chapter's concept does "rebuild nightly from batch processing" recall? Why is the trie not updated in real-time as new queries arrive (what write throughput problem would that create, and connect it to Chapter 10's "write-heavy workload" discussion)?

(g) Scatter-gather query execution across 10 shards — which chapter's exact term and concept? What is the coordinator's latency budget constraint that makes this pattern viable (Chapter 1's within-datacenter RTT for fan-out to 10 shards simultaneously is X ms — what is X, and how does it fit in the 200ms budget)?

(h) Segment merging running as a background process with I/O rate limiting — which chapter's incident (the Cassandra node join causing compaction backlog) demonstrated why I/O rate limiting on background maintenance processes is critical? What is the metric from Chapter 18 that tells you the merge process is falling behind?

Closing: The Curriculum Is Complete

You have now built, from first principles, the following systems:

1. A B-Tree database with WAL durability
2. An indexed relational database with query optimisation
3. A replicated primary-replica database with failover
4. A distributed database with configurable consistency
5. A sharded database with consistent hashing
6. A write-optimised storage engine (LSM tree)
7. A consensus system (Raft)
8. A distributed transaction coordinator (2PC + Saga)
9. A message queue with exactly-once delivery (Kafka)
10. A tiered caching system (Redis + CDN)
11. A rate limiting service
12. An observability platform (metrics, traces, logs)
13. A real-time messaging system (WhatsApp-scale)
14. A distributed key-value store (DynamoDB-scale)
15. A global CDN (Cloudflare-scale)
16. A payment processing system (Stripe-scale)
17. A search engine (Elasticsearch-scale)

Every one of these systems was built using the same method: start from physical reality (what the hardware actually does, what the latency numbers actually are), reason about the failure modes, choose the data structure and algorithm that best fits the access pattern and constraints, compose components from prior chapters, and state the trade-offs explicitly.

This is the method. Not "use Kafka because Kafka is good." Not "use Redis because everyone uses Redis." But: "the access pattern is high-frequency small writes with low read latency requirements → in-memory LRU with persistence → Redis is the right tool, and here is why."

The 40 LPA goal, the FAANG interview, the product you build — they all require the same thing: the ability to reason from constraints to architecture, to know what each tool costs and what it buys, to build systems that survive the failures that will definitely happen. That ability is what the curriculum built.

The system is in your hands now.

Chapter 24 complete. The curriculum is complete. The single most important thing to do next: pick any system you've used in the past week (Google Search, Swiggy, Zepto, Razorpay, Slack) and trace it through the framework. What are the requirements? What is the scale? What data structures power it? What are its failure modes? If you can answer these questions for any system you encounter, the curriculum worked.

The 24 chapters are not meant to be memorised. They are meant to be understood deeply enough that you could reconstruct any chapter's key insights from first principles, in an interview room, with a whiteboard and 45 minutes. If you worked the practice problems honestly — especially the synthesis problems that connect multiple chapters — you can.