Designing a Typeahead/Autocomplete System

What you'll learn

• 1. Problem Definition

  Build a service that, given any prefix typed by a user, returns the top 10 most relevant query suggestions in under 200 milliseconds. The system must handle internet-scale traffic and keep suggestions fresh without impacting availability.

• 2. Requirements Gathering

• Functional Requirements

  1. For any prefix of length >= 1, return top 10 ranked completions 2. Ranking is primarily by search frequency, weighted toward recency 3. Support English (lowercase a-z, optionally digits and spaces) 4. Personalization: blend user-speci…

• Non-Functional Requirements

  | Dimension | Target | |-----------|--------| | Daily queries | 5 billion | | Peak QPS | ~60,000 | | Unique indexed terms | 100 million | | P99 latency | Component Responsibilities: - API Gateway: Rate limiting, authentication, request r…

• Design Evolution & Trade-offs

  How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview.

• Stage 1 — MVP: One box, one database

  The simplest thing that could possibly work for typeahead. On every keystroke the API server issues a LIKE 'prefix%' query against a terms(name, frequency) table, sorts by frequency, and returns the top 10. - A single API server (monolit…

• Stage 2 — Scale-out: Multiple pods behind a load balancer

  - API layer becomes stateless: N pods behind an L7 load balancer. - User debounce (50ms) and in-flight cancellation move to the browser to cut request volume by roughly 3-4x. - The database gets a small read replica so the write-path (lo…

• Stage 3 — Bottleneck: Prefix-lookup latency at read fan-out

  Typeahead is a read-heavy, latency-critical system. The first hard problem is not writes — writes are batched offline — it is answering "top 10 completions for prefix X" in single-digit milliseconds at 60K QPS, where X is arbitrary and 2…

• Stage 4 — Second bottleneck: Hot-prefix read amplification and freshness

  Even with an in-memory trie, two related problems remain: 1. Read amplification on hot prefixes. The top ~1000 short prefixes drive 60-80% of all queries. Every one of those hits the trie server holding that shard. A single "s" or "the"…

• Stage 5 — Mature architecture

  The full picture, combining everything: browser optimizations, CDN, load balancer, sharded stateless API, hot-prefix cache, trending buffer, sharded in-memory tries with pre-computed top-K, offline rebuild pipeline, snapshot store, and Z…

• Cost vs Complexity — When to Pick What

  | Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Prefix index | Postgres B-tree + LIKE | Elasticsearch edgengram OR single-node trie | Sharded in-memory compressed…

• Migration Path (MVP → Enterprise)

  The order matters — each step is designed to be independently shippable and reversible. 1. Move debounce, cancellation, and pre-fetch to the client. Zero backend risk, immediate 3-4x drop in QPS. Ship this before anything else. 2. Add a…

• 5. Core Data Structure: The Trie

• 5.1 Standard Trie

  A trie is a tree where each edge represents a character and each path from root to a node represents a prefix. Paths to "end" nodes represent complete stored terms. Problem: With 100M terms averaging 15 characters, a naive trie could hav…

• 5.2 Compressed Trie (Patricia Trie)

  Solution: Merge any chain of single-child nodes into one node storing multiple characters: Benefits: - Drastically fewer nodes (roughly one node per branching point + one per term) - Reduces pointer overhead - Better cache locality

• 5.3 Node Structure (Detailed)

  The topResults field is the critical optimization -- explained next.

• 6. Pre-Computed Top-10 at Every Node

• The Naive Approach (Too Slow)

  When a user types "ca", find the node for "ca", then do a DFS/BFS of its entire subtree to find the 10 most frequent completions. For a popular prefix like "s", the subtree could contain millions of terms. The time complexity to find all…

• The Optimized Approach

  Pre-compute and cache the top 10 results at every single node during trie construction. At query time, reaching a node gives you the answer immediately. Lookup complexity: O(prefixlength) to walk down the trie, then O(1) to return result…

• 7. Frequency Calculation: Exponential Moving Average

• Why Not Raw Counts?

  If you simply count all-time occurrences, a term that was searched heavily years ago but is now irrelevant will forever dominate. We need temporal decay.

• EMA Formula

  In standard signal processing notation: Where: - St = smoothed frequency at time t - Yt = observed count in the current time window - S{t-1} = previous smoothed frequency - alpha (e.g., 0.2) = smoothing factor Applied to our system: Key…

• Example

  The term naturally rises during the event and decays afterward.

• 8. Trie Construction: Bottom-Up with Back-Propagation

• Step-by-Step Process

  1. Insert all terms into the compressed trie structure (no top-10 yet) 2. Assign frequencies to leaf/end nodes based on EMA calculations 3. Bottom-up aggregation: - Start at leaf nodes: their top-10 is just themselves (if they are comple…

• Back-Propagation Illustration

• 9. Update Strategy: Offline Batch Pipeline

• Why Not Real-Time Updates?

  At 60,000 QPS: - Locking a trie node for writes blocks reads (latency spikes) - Propagating a frequency change up the trie touches many nodes - Concurrent writers create race conditions on top-10 lists - Memory allocation for new nodes u…

• The Batch Pipeline

  Frequency: Hourly rebuilds (configurable based on freshness needs)

• Master-Slave Swap in Detail

  Zero-downtime deployment. Users never see stale or missing results.

• 10. Serialization for Persistent Storage

• Level-Order Format

  Serialize the trie breadth-first. Each entry is: Character + ChildCount. This format is compact and allows sequential reconstruction without recursion.

• Why Level-Order?

  - Sequential disk reads (no random seeks) - Can stream-load the trie level by level - Easy to split across files for parallel loading

• 11. Partitioning (Sharding) Strategies

  With 25 GB of trie data, a single server can hold it all in memory, but for throughput at 60K+ QPS, we need multiple servers handling requests in parallel.

• Option 1: Range-Based Partitioning

  Problem: Wildly unbalanced. "S" alone might have more terms than "X", "Y", "Z" combined.

• Option 2: Max-Capacity Partitioning (Recommended)

  Fill each server until it hits a capacity threshold, then spill to the next: Routing: A lookup table maps prefix ranges to servers. The client (or a router service) checks the first few characters to determine which shard to query. Advan…

• Option 3: Hash-Based Partitioning

  Problem: Every query must go to a specific shard determined by the exact prefix. Since users type incrementally ("c" -> "ca" -> "car"), each keystroke likely hits a DIFFERENT shard. Alternatively, querying all shards and merging defeats…

• Comparison Table

  | Strategy | Balance | Routing Complexity | Single-Shard Query? | |----------|---------|-------------------|---------------------| | Range-based | Poor | Simple | Yes | | Max-capacity | Good | Moderate (lookup table) | Yes | | Hash-based…

• 12. Replication and Load Balancing

• Architecture

  - Primary handles writes (trie swaps) - Secondaries handle reads (majority of traffic) - Load balancer distributes across healthy replicas - If primary fails, a secondary is promoted

• Replication During Trie Swap

  1. New trie deployed to primary 2. Primary validates and begins serving 3. Secondaries pull the new serialized trie and load it 4. Brief inconsistency window (seconds) -- acceptable since suggestions are "best effort"

• 13. Caching Layer

• Why Cache?

  Query distribution follows the 80-20 rule -- 20% of prefixes generate 80% of traffic. The top 1000 prefixes (1-2 characters) account for a disproportionate share of all requests. Caching these eliminates most trie lookups.

• Cache Design

  - Cache the top few hundred short prefixes (1-3 chars) - TTL = 1 hour (aligned with trie rebuild frequency) - On trie swap, invalidate all cache entries (or let them expire naturally)

• Redis Cache Key-Value Structure

  The Redis cache stores popular prefixes as simple key-value pairs: This flat structure allows O(1) lookups for the most frequently requested prefixes, bypassing the trie entirely.

• Cache Hit Rate Estimation

  - Prefixes of length 1: 26 entries, cover ~15% of traffic - Prefixes of length 1-2: ~700 entries, cover ~40% of traffic - Prefixes of length 1-3: ~18,000 entries, cover ~60% of traffic Caching 20K entries with 10 suggestions each is triv…

• 14. Client-Side Optimizations

• 14.1 Debounce (50ms)

• 14.2 Cancel In-Progress Requests

  Why? If "c" response arrives after user has typed "car", showing suggestions for "c" would be wrong and jarring.

• 14.3 Pre-Fetch Top-Level Results

  On page load (before user interacts with search box): - Fetch results for the 10 most common single-character prefixes - Store in browser memory - When user types first character, respond instantly from local cache

• 14.4 Local History Cache

  - Store the user's last N searches in localStorage - When displaying suggestions, prepend 2-3 personal history matches - No network round-trip needed for these

• 14.5 Early TCP Connection

  Establish TCP + TLS handshake to the suggestion service when the page loads. Saves ~100ms on the first actual request.

• 15. Personalization

• Approach

  Maintain a small per-user store of recent searches (last 100-500 terms). At query time, blend: Context factors include: - Location: Boost locally relevant suggestions (e.g., "pizza" surfaces local chains) - Language: Prefer terms matchin…

• Architecture for Personalization

  - Personalization layer fetches global top-10 AND user's matching history - Merges using weighted scoring - User store is small (few KB per user) -- fits in Redis or even client-side

• Privacy Considerations

  - User history is per-account, encrypted at rest - Option to disable personalization - History auto-expires after N days

• 16. Fault Tolerance and Recovery

• Master-Slave Configuration

  Each trie server shard operates in a master-slave configuration: - Master handles trie swaps and serves reads - Slave(s) replicate the master's state and handle overflow read traffic - If the master dies, a slave is promoted to master (c…

• Recovery from Failure

  When a trie server restarts after a crash: 1. Load the last serialized trie snapshot from the NoSQL database 2. Rebuild the in-memory trie from the snapshot 3. Begin serving requests (data may be slightly stale -- up to 1 hour old) 4. On…

• Zookeeper's Coordination Role

  - Maintains a registry of all healthy trie server instances - Detects failed servers via heartbeat timeouts - Triggers slave-to-master promotion when a master fails - Coordinates trie deployment across the cluster (ensuring all shards up…

• 17. Handling Edge Cases

• Trending/Breaking Queries

  - Between hourly rebuilds, a breaking news term won't appear - Solution: maintain a small real-time trending buffer (last 15 min, top 100 terms) - Merge trending buffer results with trie results at query time - Buffer is small enough to…

• Offensive/Sensitive Content

  - Maintain a blocklist of terms that should never appear in suggestions - Filter applied as a post-processing step on results - Blocklist checked during trie build (exclude terms) AND at query time (in case of cache)

• Multi-Language Support

  - Separate tries per language - Route based on user locale or detected input script - Same architecture applies; just partition by language first

• 18. Complete System Diagram

• 19. Summary of Key Design Decisions

  | Decision | Choice | Rationale | |----------|--------|-----------| | Data structure | Compressed Trie | O(prefixlen) lookup, space-efficient | | Query optimization | Pre-computed top-10 per node | O(1) result retrieval after node lookup…