System Design: Search Systems
Master full-text search concepts, inverted indices, Lucene & Elasticsearch cluster architecture, BM25 ranking, autocomplete Trie design, and fuzzy spell correction.
1. Full-Text Search Concepts & The Text Analysis Pipeline
Relational databases fail at full-text search because WHERE text LIKE '%query%' forces a full table scan ($O(N)$) that ignores word variations, tenses, and relevance rankings. Modern search engines run raw text through a multi-stage Text Analysis Pipeline.
Text Analysis & Tokenization Pipeline (Character Filters, Tokenizer & Stemming)
System DesignTransforming unstructured human prose into normalized indexable lexical tokens
1. Character Filters
Pre-processes raw text before tokenization.
- Strips HTML tags (<p>, <script>)
- Normalizes Unicode characters & accents (é -> e)
- Regex pattern replacement
2. Tokenizer
Splits continuous text streams into distinct tokens.
- Standard Tokenizer: Splits on whitespace and punctuation
- N-gram Tokenizer: Generates sub-word substrings for autocomplete
- Whitespace Tokenizer: Preserves internal punctuation
3. Token Filters
Transforms, normalizes, and filters tokens.
- Lowercase Filter: Ensures case-insensitive matching
- Stop Word Filter: Drops common non-informative words (the, is, at)
- Stemmer / Lemmatizer: Reduces words to root base (foxes -> fox, running -> run)
2. The Inverted Index Data Structure & Posting Lists
The Inverted Index is the core data structure powering all modern search engines. Instead of mapping Document $\rightarrow$ Words, it inverts the relationship to map Word $\rightarrow$ List of Documents (the Posting List).
Inverted Index Mapping & Sorted Posting List Architecture
System DesignInverting forward document records into fast dictionary lookups and doc ID posting lists
Posting Lists & Compression
Storing millions of document IDs compactly in memory.
- Posting Entry: Contains Document ID, Term Frequency (TF), and Byte Positions
- Delta Encoding: Stores differences between sorted IDs ([100, 104, 109] -> [100, 4, 5])
- Roaring Bitmaps: Highly compressed bitsets allowing sub-millisecond set intersections (AND/OR queries)
Immutable Lucene Segments
High-throughput search without lock contention.
- Write Once: Lucene index segments are write-once and immutable (zero lock contention during searches)
- Segment Merging: Background worker threads merge smaller segments into large consolidated segments
- Deletions: Deleted docs are flagged in a bitset and purged during segment merging
3. Distributed Search Engines (Elasticsearch, Solr & Lucene Clusters)
Distributed search engines shard large indices across a cluster of nodes. When executing a query, a Coordinating Node executes a two-phase Scatter-Gather operation across all shard replicas.
Elasticsearch Distributed Scatter-Gather Query Execution Flow
System DesignParallel shard query execution, local BM25 scoring, coordinating node merge, and document fetch
Elasticsearch Node Roles in System Design
Separating compute responsibilities for extreme stability.
- Master Eligible Nodes: Manages cluster metadata, index creation, and shard rebalancing
- Data Nodes: Stores Lucene index segments on SSDs and executes search/aggregation queries
- Coordinating Nodes: Acts as a smart load balancer, scattering requests and merging results
- Ingest Nodes: Applies transformation pipelines (grok, GeoIP, PII stripping) before indexing
4. Ranking, Relevance Scoring (TF-IDF vs BM25) & Hybrid Search
Search relevance determines which documents appear at the top. While classical search uses Okapi BM25 lexical scoring, modern systems combine BM25 with Dense Vector Embeddings using Reciprocal Rank Fusion (RRF).
Hybrid Search Architecture (BM25 Keyword + Dense Vector Embeddings)
System DesignBlending exact keyword precision with semantic embeddings via Reciprocal Rank Fusion (RRF)
Okapi BM25 vs TF-IDF
The modern standard for lexical relevance ranking.
- Term Frequency Saturation: Repeating a word 100 times does not make a document 100x more relevant
- Document Length Normalization: Penalizes long, spammy documents so short matching titles rank higher
- Formula: Uses k1 (term saturation factor ~1.2) and b (length penalty ~0.75)
Hybrid Vector Search (ANN & HNSW)
Understanding semantic meaning and synonyms.
- Vector Embeddings: Converts sentences into high-dimensional float arrays (e.g. 1536 dims)
- HNSW Graphs: Hierarchical Navigable Small World graphs for fast Approximate Nearest Neighbor (ANN) search
- Reciprocal Rank Fusion: Merges keyword & vector rank positions into a single robust relevance score
Inverted Index Engine with Okapi BM25 Ranking Algorithm in Node.js
An inverted index implementation that ranks search results using the Okapi BM25 relevance scoring algorithm.
Press Run to execute the code and see output here.
5. Autocomplete and Typeahead System Design
Typeahead suggestions must return in under 30ms as users type each character. This is achieved using memory-resident Trie (Prefix Trees) storing pre-computed Top-K suggestions at every node.
Ranked Trie (Prefix Tree) Data Structure with Precomputed Top-K Suggestions
System DesignEach node caches top 5 popular queries for constant O(L) sub-millisecond retrieval
End-to-End Autocomplete System Architecture & Caching Pipeline
System DesignClient debouncing, Edge Redis cache, In-memory Trie serving, and offline Spark log aggregation
Scaling Real-Time Autocomplete to Millions of QPS
Techniques used by Google & Amazon typeahead systems.
- Client Debouncing: Wait 150-250ms after user stops typing before firing HTTP request
- Precomputed Top-K: Avoid traversing child subtrees at query time by caching Top 5 queries directly on each Trie node
- Finite State Transducers (FST): Ultra-compressed memory-resident Trie used in Lucene
- Offline Pipeline: Spark/Flink jobs aggregate query click logs nightly to recompute Trie weights without slowing production
High-Performance Autocomplete Trie with Precomputed Top-K Rankings in Node.js
A trie-based autocomplete engine that precomputes top-K ranked suggestions at each node for fast lookups.
Press Run to execute the code and see output here.
6. Fuzzy Search, Edit Distance & Spell Correction (SymSpell)
Users frequently make typographical errors. Search systems match misspelled queries using Levenshtein Distance (Edit Distance) and ultra-fast lookup algorithms like SymSpell.
Fuzzy Spell Correction & SymSpell Symmetric Deletion Lookup Pipeline
System DesignResolving typographical mistakes in O(1) time using pre-computed deletion hash tables
Levenshtein & Damerau Distance
Quantifying string differences by minimum edit operations.
- Insertion: "aple" -> "apple" (Cost: 1)
- Deletion: "appple" -> "apple" (Cost: 1)
- Substitution: "appla" -> "apple" (Cost: 1)
- Transposition (Damerau): "appel" -> "apple" (Cost: 1)
Phonetic Matching (Soundex & Metaphone)
Matching words that sound identical.
- Soundex: Encodes words based on English phonetic pronunciation (e.g. "Smith" & "Smyth" -> S530)
- Double Metaphone: Generates primary and alternate phonetic keys for foreign language names
Knowledge Check
1. What is the primary function of an Inverted Index in search engines?
2. How does Okapi BM25 improve upon classical TF-IDF scoring?
3. Why do Autocomplete systems store precomputed Top-K lists at each Trie node?
4. What happens during the "Scatter-Gather" phase in Elasticsearch clusters?
5. What algorithm enables fast O(1) fuzzy spell correction in search systems?