System Design Problems
Design Typesense Autocomplete
Typesense provides typo-tolerant, instant search with sub-millisecond latency. Unlike standard autocomplete that requires exact prefix matches, Typesense uses trie-based indexing with edit distance (Levenshtein distance) to find results even when users make typos.
- Typo Tolerance β Find results with up to 2-3 character errors
- Sub-millisecond Latency β In-memory trie traversal
- Relevance Ranking β Results ranked by popularity and freshness
The key insight: instead of matching exact prefixes, traverse the trie allowing character substitutions, insertions, and deletions (edit distance).
Requirements
Functional Requirements
- Search as you type (every keystroke triggers search)
- Typo tolerance (up to 2 edits: substitutions, insertions, deletions)
- Results ranked by relevance (popularity, freshness, exact match)
- Support for multiple fields (title, description, tags)
- Faceted search (filter by category, price range)
- Real-time index updates (new documents indexed within 100ms)
Non-Functional Requirements
- Latency: Results in < 50ms (p99)
- Throughput: 100K search QPS
- Freshness: New documents indexed within 100ms
- Accuracy: Typo-tolerant results must include correct answers
- Scale: 100M documents, 1 billion search terms
Back-of-the-Envelope Estimation
Trie with Edit Distance
Trie Traversal with Edit Budget
Multi-Field Search
Search across multiple fields with field-level boosting:
High-Level Architecture
Index Structure
The trie stores document IDs at leaf nodes. Each trie node contains:
TrieNode {
children: Map<Char, TrieNode>
doc_ids: Set<DocId> // Documents with this prefix
frequency: int // For ranking
is_end_of_word: bool
}
Sharding Strategy
Partition the index across shards by document hash:
Practice Exercises
-
Algorithm: Implement a bounded trie search that finds all words within edit distance D of a given prefix. What is the time complexity?
-
Scale: If the index has 100M documents with 10 fields each, estimate the trie memory and the query time for a typo-tolerant search.
-
Ranking: Design a ranking function that combines typo tolerance, field boosting, popularity, and freshness. How do you weight these signals?
-
Optimization: How would you implement search-as-you-type that debounces keystrokes and caches recent query results?
What to Learn Next
-> Design Search Autocomplete Standard prefix-based autocomplete with popularity ranking.
-> Design Search Engine Inverted indices and full-text search infrastructure.
-> Database Indexing B-tree, LSM-tree, and trie index structures.
-> Caching Strategies Caching search results and trie hot paths.
-> Databases In-memory vs disk-based storage trade-offs.
-> Design Recommendation System ML-based ranking and personalization.