{"title":"Design an Autocomplete System","description":"","content":"\n> **QUESTION**\n>\n> An autocomplete system predicts and suggests query completions in real time as the user types. Behind a seemingly simple UX sits a ranking problem over hundreds of millions of candidate queries, with a sub-50ms latency ceiling, millions of keystrokes per second, and freshness demands that force parts of the index to rebuild every minute.\n\n\n---\n\n# 1. Problem Formulation\n\nAutocomplete shows up in many products, from general web search to e-commerce search bars to code editors. Each has different scale, quality, and personalization needs, so the first job is to pin down the scope.\n\n### Clarifying Questions\n\n\n> **DISCUSSION**\n>\n> **Candidate:** \"What surface are we building for? A general web search bar like Google, an e-commerce product search, or something narrower like a maps address field?\"\n>\n> **Interviewer:** \"General web search autocomplete. Think Google or Bing in the main search box.\"\n>\n> **Candidate:** \"What is the query volume, roughly, and the peak QPS we should plan for?\"\n>\n> **Interviewer:** \"About 5 billion searches per day. Keep in mind autocomplete fires on keystrokes, not submissions, so the typeahead service itself sees close to 100,000 QPS at peak.\"\n>\n> **Candidate:** \"What is the latency budget for a single suggestion request?\"\n>\n> **Interviewer:** \"End-to-end under 100ms at the 99th percentile, including network. Server-side budget should be under 50ms so the client still feels instant on a fast connection.\"\n>\n> **Candidate:** \"How many suggestions do we return per keystroke?\"\n>\n> **Interviewer:** \"Typically the top 5 to 10, rendered below the search box.\"\n>\n> **Candidate:** \"What personalization signals are available, and how much should we lean on them?\"\n>\n> **Interviewer:** \"Coarse location, language, device, and the user's last few queries in the current session. Heavier per-user personalization is out of scope. Global quality dominates.\"\n>\n> **Candidate:** \"How fresh do trending queries need to be? A breaking news query may be nonexistent in the training data.\"\n>\n> **Interviewer:** \"Trending queries should show up within 5 minutes of going viral. Long-tail queries can be picked up in a daily rebuild.\"\n>\n> **Candidate:** \"Do we need to handle typos in the prefix, like the user typing 'restuarant'?\"\n>\n> **Interviewer:** \"Yes. Fuzzy matching is expected. You should not fail silently when the user is off by one or two characters.\"\n>\n> **Candidate:** \"What signals do we have for training? Click logs, session logs, human labels?\"\n>\n> **Interviewer:** \"Billions of suggestion impression and click events per day, session logs with downstream search outcomes, plus a small set of human-rated (prefix, suggestion) pairs for evaluation.\"\n\n\n### Requirements\n\n#### **Functional Requirements:**\n\n- Return a ranked list of 5 to 10 completions for any prefix of 1 to 60 characters, including empty-state (zero-prefix) suggestions\n- Handle typos and minor misspellings in the prefix\n- Respect a safe-search setting so adult or unsafe queries can be filtered\n- Incorporate coarse personalization using location, language, device, and session history\n- Boost trending queries so viral topics appear within minutes\n\n#### **Non-Functional Requirements:**\n\n- Server-side p99 latency under 50ms, end-to-end p99 under 100ms\n- Sustain 100,000 QPS at peak with at least 3x headroom for traffic spikes\n- Index around 500 million unique queries covering 95% of daily search volume\n- Trending queries visible within 5 minutes, long-tail queries refreshed within 24 hours\n- Suggestion MRR@10 at least 0.55, suggestion CTR at least 15% on the first rendered result set\n\n### ML Problem Framing\n\nThis is a learning-to-rank problem over a prefix-matched candidate pool. No single model can score 500 million completions per keystroke at 100,000 QPS under 50ms, so the work is split into stages. Each stage narrows the candidate pool and spends its budget on what it can actually do in the time it has.\n\n1. **Candidate generation:** A prefix index returns the top 1,000 popular completions for the typed prefix in under 5ms. This stage is retrieval-heavy and optimizes recall: the right answer has to be in the 1,000 or it cannot be ranked.\n2. **Ranking:** A gradient-boosted ranker scores the 1,000 candidates in about 15ms using 150 features covering popularity, trend velocity, personalization, and session state. This stage optimizes precision and ordering.\n3. **Post-processing:** Dedup near-identical queries, enforce safety filters, apply a trending boost, and truncate to the top 10. A few milliseconds, CPU only.\n\n\n```mermaid\nflowchart LR\n A[\"500M
Queries\"]:::primary --> B[\"Prefix Match
~1,000\"]:::teal\n B --> C[\"Ranker
Top 200\"]:::orange\n C --> D[\"Post-process
Top 10\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe recall objective at the top of the funnel and the precision objective at the bottom need different model shapes. Candidate generation leans on a hand-engineered prefix data structure plus raw popularity counts. Ranking leans on a learned model that can weigh dozens of signals per candidate. Trying to collapse both stages into one model is the most common design mistake: it either takes too long or it drops too many good candidates.\n\n### Metrics\n\n#### **Offline Metrics:**\n\n- **MRR@10.** Mean reciprocal rank of the clicked suggestion. Captures whether the right answer is near the top.\n- **NDCG@10.** Graded ranking quality using click weight or session success as relevance.\n- **Typed-chars-saved.** How many keystrokes the user would have saved by accepting a suggestion. This is the metric that best reflects the product goal.\n- **Prefix coverage.** Percentage of real prefixes for which the system returns at least one reasonable suggestion.\n\n#### **Online Metrics:**\n\n- **Suggestion CTR.** Fraction of impressed keystrokes where the user clicks a suggestion.\n- **Seconds saved per session.** Wall-clock time saved on search input, estimated from keystrokes avoided.\n- **Search success rate.** Percentage of searches that lead to a click on a result, stratified by whether the user used autocomplete.\n- **Abandonment rate.** Percentage of sessions where the user starts typing and leaves without searching. Guardrail metric. A bad typeahead can drive abandonment up even when CTR looks fine.\n\n---\n\n# 2. System Architecture\n\nThe full system splits into an offline pipeline that builds indexes and trains models, and an online pipeline that serves suggestions on every keystroke.\n\n\n```mermaid\nflowchart LR\n subgraph Offline\n L[Query &
Click Logs]:::primary --> A[Aggregator
Spark]:::orange\n A --> IX[Index
Builder]:::orange\n A --> TR[Training
Pipeline]:::orange\n IX --> AR[Index
Artifacts]:::teal\n TR --> MR[Ranker
Artifact]:::teal\n end\n\n subgraph Online\n K[Keystroke]:::primary --> G[Gateway]:::primary\n G --> PF[Prefix
Service]:::orange\n G --> FS[Feature
Store]:::teal\n PF --> RK[Ranker
Service]:::orange\n FS --> RK\n RK --> PP[Post-
process]:::green\n PP --> R[Suggestions]:::green\n end\n\n AR --> PF\n MR --> RK\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nOn the offline side, raw query and click logs land in a data lake. An aggregator rolls them into per-query statistics (popularity, CTR, success rate) over multiple time windows. Those aggregates feed two consumers: an index builder that produces the shardable prefix index, and a training pipeline that produces the ranker artifact. Both artifacts are versioned and pushed to the online stack.\n\nOn the online side, every keystroke hits a gateway. The gateway fans out in parallel to a prefix service (which performs candidate generation against the sharded index) and to a feature store (which fetches user and session features). The ranker service scores the returned candidates using the fetched features, post-processing enforces diversity and safety, and the response goes back to the client.\n\n### Scale Numbers\n\nBefore picking a concrete design, the numbers have to line up with the budgets.\n\n\n| Dimension | Estimate | Notes |\n|---|---|---|\n| Searches per day | 5B | One search = many keystrokes |\n| Keystrokes per search | ~8 | Plus debouncing on the client cuts actual requests |\n| Typeahead QPS at peak | 100K | Post-debounce, per-region |\n| Unique queries in the head | 500M | Covers ~95% of volume (power law) |\n| Raw prefix pairs | 5B+ | Each query generates many prefix-completion pairs |\n| Prefix index size | 60 to 100 GB | Shardable; hot shards replicated |\n| Ranker model size | 50 to 200 MB | GBDT artifact, fits in RAM |\n| Training data window | 30 days | Balances stability and freshness |\n| Daily training examples | 10B | After negative sampling, ~150B before |\n\n\nTwo implications fall out. First, the prefix index is big but not huge at the scale of web infra. A two-digit number of shards, each 5 to 10 GB, fits on commodity hosts with room for replicas. Second, the ranker is small enough to load in-process alongside the prefix service if cross-service RPCs become the bottleneck, which is a common late-stage optimization.\n\n### Data Flow\n\nThe data flow has three loops running at different frequencies, which is where most of the complexity lives.\n\n\n```mermaid\nflowchart LR\n LOG[Logs
Kafka]:::primary --> STR[Stream
Aggregator]:::orange\n LOG --> BAT[Batch
Aggregator]:::orange\n\n STR --> DIX[Delta
Index]:::teal\n BAT --> BIX[Base
Index]:::teal\n BAT --> TD[Training
Data]:::teal\n\n TD --> MT[Model
Training]:::orange\n MT --> MA[Ranker
Artifact]:::green\n\n DIX --> SRV[Serving]:::green\n BIX --> SRV\n MA --> SRV\n\n SRV --> LOG\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe fast loop runs every minute. A streaming aggregator in Flink or Spark Structured Streaming consumes Kafka logs and updates a small delta index of trending queries and per-query trend velocities. The medium loop runs hourly and refreshes popularity counters on the base index without a full rebuild. The slow loop runs daily and does the heavy work: full base index rebuild, ranker retraining on 30 days of data, artifact promotion through canary and into production.\n\nNote the feedback arrow from serving back to logs. Every suggestion shown is logged alongside what the user did next. This closes the loop, but it also introduces exposure bias that has to be corrected for during training. More on that later.\n\n---\n\n# 3. Data\n\n### Data Sources\n\nThe system pulls from four data sources, each with a distinct signal.\n\n- **Raw query logs:** Every submitted search, with user id, location, language, device, and timestamp. Used to compute long-term popularity.\n- **Suggestion impression and click logs:** Every typeahead request and the outcome: which suggestions were shown, which was clicked, which query was eventually submitted. This is the supervision signal for the ranker.\n- **Session logs:** Full session paths. Did the user click a result after the search? Did they refine the query? Did they abandon the session? These outcomes answer whether a suggestion led to a successful search, not just a click.\n- **External signals:** News trending APIs, social trend feeds, and maintained blocklists and allowlists for safety filtering and canonical-form mapping.\n\n### Query Representation and Normalization\n\nBefore anything gets indexed, queries go through a normalization pipeline. Skipping this step creates brutal long-tail issues where \"NYC pizza\", \"nyc pizza\", and \"nyc pizza \" live as three different queries.\n\nThe normalization pipeline does the following in order:\n\n1. Unicode normalization to NFC.\n2. Lowercase folding (with locale-aware rules for languages like Turkish).\n3. Whitespace collapse and trim.\n4. Canonical punctuation mapping (curly quotes to straight, smart dashes to plain).\n5. Optional accent folding for languages where users type unaccented forms.\n6. Stopword preservation. Do not strip stopwords in autocomplete. \"to be or not to be\" is a real query.\n\nThe same normalizer runs at index-build time and at query time, which guarantees the prefix string hashes match.\n\nFor fuzzy matching the system also stores a secondary representation: character n-grams (typically 2-grams and 3-grams) that support edit-distance lookups. This doubles some storage but is how typo tolerance becomes fast enough to hit the latency budget.\n\n### Feature Engineering\n\nFeatures for the ranker split into four groups: query features (properties of the candidate completion itself), temporal features (how the candidate's popularity is evolving), context features (about the user and session), and cross features (how well the candidate matches the context).\n\n\n| Feature | Type | Source | Freshness | Description |\n|---|---|---|---|---|\n| query_popularity_7d | Float | Batch | Hourly | Log of search count over 7 days |\n| query_popularity_30d | Float | Batch | Daily | Log of search count over 30 days, stabilizer |\n| query_popularity_1h | Float | Streaming | 1 min | Short-window count, trending signal |\n| trend_velocity | Float | Streaming | 1 min | Rate of change in hourly popularity |\n| query_ctr_historic | Float | Batch | Daily | Historical CTR when shown as suggestion |\n| query_success_rate | Float | Batch | Daily | Session success rate after query submitted |\n| prefix_match_length | Int | Online | Per-req | Chars matched between prefix and candidate |\n| prefix_match_quality | Float | Online | Per-req | Weighted match score, penalizes fuzzy matches |\n| query_length_chars | Int | Static | Static | Penalizes very long completions on mobile |\n| user_recent_queries | Vec | Online | Per-req | Last 10 queries this session |\n| user_location_region | Cat | Online | Per-req | Coarse region (country, metro) |\n| user_language | Cat | Online | Per-req | UI language setting |\n| query_lang_match | Bool | Derived | Per-req | Candidate language matches user language |\n| device_type | Cat | Online | Per-req | Mobile or desktop |\n| hour_of_day | Cat | Online | Per-req | Captures intra-day query patterns |\n| is_safe | Bool | Batch | Daily | Passes safety classifier |\n| near_dup_cluster_id | Int | Batch | Daily | Dedup cluster for canonicalization |\n\n\nTwo things worth calling out. The popularity features exist at multiple time horizons (1h, 7d, 30d) on purpose. The ranker needs both the stable signal (30d) and the recency signal (1h), and letting it learn how to combine them is far more robust than picking one manually. And several features (prefix_match_length, user_recent_queries) are computed per request. That work has to fit in the latency budget, so they are kept deliberately cheap: integer arithmetic, not embeddings.\n\n---\n\n# 4. Model\n\n### Baseline Approach\n\nThe simplest system that works: a trie of the top 500 million queries, each node weighted by raw popularity. On prefix \"mach\" the trie descends to the \"mach\" node, gathers all descendants, picks the top 10 by popularity, and returns them. No ranker, no personalization, no features beyond popularity.\n\n\n```mermaid\nflowchart TD\n ROOT[root]:::primary\n ROOT --> M[m]:::teal\n M --> MA[a]:::teal\n MA --> MAR[r]:::orange\n MA --> MAC[c]:::orange\n MAC --> MACH[h]:::green\n MACH --> Q1[machine
learning
pop: 9.2]:::green\n MACH --> Q2[macbook
pro
pop: 8.7]:::green\n MACH --> Q3[machine
gun kelly
pop: 7.4]:::green\n MAR --> Q4[march
madness
pop: 8.1]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe baseline is surprisingly strong because query popularity follows a power law: the top 10% of queries cover more than 90% of volume. If \"machine learning\" is the most popular \"mach\" completion by an order of magnitude, a naive popularity sort will land on it regardless of what the user wants. For head prefixes this gets the system to roughly 70% of the quality ceiling.\n\nThe baseline breaks in four places that matter. There is no personalization, so a user in Tokyo and a user in Mumbai get identical \"mach\" suggestions. There is no freshness, so a query that went viral yesterday is invisible until tomorrow's rebuild.\n\nThere is no typo tolerance, so \"machne\" falls off a cliff. And there is no signal about intent beyond raw popularity, so the ranker cannot learn that short queries perform better on mobile, or that session context radically changes what the user is about to type.\n\n### Advanced Approach\n\nThe production architecture keeps the prefix index as the candidate generator and adds a learned ranker plus a few targeted enhancements.\n\n\n```mermaid\nflowchart LR\n P[Prefix:
mach]:::primary --> SH[Shard
Router]:::orange\n SH --> S1[Shard 1
Radix Trie]:::teal\n SH --> S2[Shard 2
Radix Trie]:::teal\n SH --> S3[Shard N
Radix Trie]:::teal\n\n S1 --> MG[Merge
Top 1000]:::orange\n S2 --> MG\n S3 --> MG\n\n MG --> FT[Feature
Builder]:::teal\n FE[User +
Session
Features]:::teal --> FT\n FT --> GBDT[LightGBM
LambdaRank]:::orange\n GBDT --> TOP[Top 200]:::green\n TOP --> PP[Dedup +
Safety +
Trend]:::orange\n PP --> OUT[Top 10]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe prefix service uses a sharded radix trie, with shards keyed by a hash of the first two characters of the prefix. Each shard lives in memory on a dedicated host, replicated for availability, and rebuilt daily from aggregated logs. On a lookup, the shard router picks the correct shard, the radix trie descends to the prefix node, and returns the top 1,000 candidates by a static popularity score. That static score is not the final ranking, just a recall-preserving prefilter.\n\nThe ranker is a gradient-boosted decision tree model (LightGBM) with LambdaRank loss. GBDTs earn their place here for three reasons. They handle the mix of numerical popularity features, categorical features like device type, and sparse session features without much preprocessing. They score 1,000 candidates in around 15ms on CPU, which fits the budget. And they are easy to iterate on: adding a new feature is a pipeline change, not a model redesign.\n\nNeural alternatives exist. Small transformer models can generate completions directly from character inputs, bypassing the prefix index entirely, and are an active area of research in production search teams.\n\nIn practice they currently supplement the main path rather than replace it because generative models are slower, have weaker coverage on long-tail queries that rarely appear in training, and produce hallucinated completions the ranker cannot easily rescue. The typical pattern is to run them as a side branch whose outputs are merged into the candidate pool, not as the core retrieval engine.\n\n### Training\n\nTraining data is built from three weeks of logged suggestion impressions and clicks. For every impression, the system records the prefix, the full list of suggestions shown, the position of each, the user and session features as they were at serve time, and the click outcome.\n\nLabels come from the click pattern within each impression. A clicked suggestion is a positive. An unclicked suggestion that appeared above the clicked one is a negative with high confidence (the user saw it and passed). Unclicked suggestions below the clicked one are low-confidence negatives because the user may never have looked at them. Suggestions that were not shown at all are unknowns and get excluded, which is the exposure-bias problem that the evaluation section revisits.\n\nThe loss is LambdaRank, which is pairwise: for each prefix group, the model learns to score the clicked suggestion higher than each unclicked suggestion. LambdaRank weights pair gradients by the change in NDCG that would result from swapping the pair, which focuses learning on the top of the ranking where users actually look.\n\n\n```python\n# Assemble training examples: one row per (impression, suggestion) pair\nimport lightgbm as lgb\nimport pandas as pd\n\ndef build_training_frame(impressions):\n rows = []\n for imp in impressions:\n for pos, suggestion in enumerate(imp.shown):\n label = 1 if suggestion.query_id == imp.clicked_id else 0\n confidence = 1.0 if (label == 1 or pos < imp.clicked_pos) else 0.3\n rows.append({\n \"group_id\": imp.impression_id,\n \"label\": label,\n \"weight\": confidence,\n **suggestion.features,\n **imp.context_features,\n })\n return pd.DataFrame(rows)\n\ndf = build_training_frame(load_impressions(days=30))\ngroup_sizes = df.groupby(\"group_id\").size().values\n\n# LambdaRank over impression groups\nranker = lgb.LGBMRanker(\n objective=\"lambdarank\",\n metric=\"ndcg\",\n n_estimators=800,\n num_leaves=127,\n learning_rate=0.05,\n label_gain=[0, 1],\n)\nranker.fit(\n df.drop(columns=[\"group_id\", \"label\", \"weight\"]),\n df[\"label\"],\n group=group_sizes,\n sample_weight=df[\"weight\"],\n)\n```\n\n\nThree things in this snippet are worth pausing on. The `group_id` tells LambdaRank which rows belong to the same impression and therefore form a ranking problem; without it the model would treat every row as independent and collapse to pointwise regression.\n\nThe `weight` column downweights low-confidence negatives so the model does not over-penalize suggestions the user never actually looked at. And the pipeline retrains from scratch daily rather than incrementally, which trades a few hours of compute for a far simpler operational story.\n\nTwo parallel training loops run at faster cadences. Popularity counters update hourly from the batch aggregator, which keeps the candidate-generation ordering fresh without a full index rebuild. Trend-velocity counters update every 60 seconds from the streaming aggregator, feeding directly into the post-processing trending boost.\n\n---\n\n# 5. Serving\n\n### Inference Pipeline\n\nEvery keystroke that survives client-side debouncing turns into one request that traces the pipeline below.\n\n\n```mermaid\nflowchart LR\n U[User
Keystroke]:::primary --> DB[Client
Debounce
~80ms]:::teal\n DB --> GW[Gateway]:::orange\n GW --> PF[Prefix
Service
5ms]:::teal\n GW --> FS[Feature
Fetch
8ms]:::teal\n PF --> RK[Ranker
15ms]:::orange\n FS --> RK\n RK --> PP[Post-
process
5ms]:::orange\n PP --> CH[Response
Cache]:::green\n CH --> CL[Client]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe client debounces keystrokes by roughly 80ms to avoid a request per character, then fires to the gateway. The gateway issues two parallel RPCs: one to the prefix service for candidate generation, one to the feature store for user and session features. When both return, the ranker scores the candidates. Post-processing deduplicates, filters, and applies the trending boost. A short-TTL response cache absorbs repeat prefixes inside the same user's session.\n\n### Batch versus Real-Time\n\nAlmost every piece of data in the system is precomputed. The ranker is built once a day, the base index once a day, popularity counters every hour, trend counters every minute. What happens at request time is cheap: pointer chasing in a trie, a dozen key lookups in Redis, a GBDT scoring pass, and a few CPU instructions for post-processing.\n\n\n| Component | Mode | Update Cadence | Storage |\n|---|---|---|---|\n| Base prefix index | Batch | Daily rebuild | In-memory radix trie, sharded |\n| Delta prefix index | Streaming | Every 60 seconds | In-memory, small |\n| Popularity counters | Batch | Hourly | Merged into index in place |\n| Trend velocity counters | Streaming | Every 60 seconds | Redis with TTL |\n| Ranker artifact | Batch | Daily | Loaded in ranker service memory |\n| User and session features | Streaming | Per-event | Redis, keyed by user id |\n| Response cache | On-demand | Per-session | Redis with short TTL |\n\n\nThe split matters because shifting any of these to real-time blows the latency budget. Computing popularity on the fly from the raw log stream would add 50ms and terabytes of work per query. Retraining the ranker per request is absurd. The only things done on the hot path are the things that genuinely depend on the current prefix and the current user.\n\n### Latency Budget\n\nThe budget below targets an end-to-end p99 of 100ms with roughly 45ms spent server-side. The numbers are realistic for a production autocomplete service on commodity hardware.\n\n\n| Component | Budget | Notes |\n|---|---|---|\n| Client debounce | ~80ms | Happens before the request is sent, not counted server-side |\n| Network in | 3ms | TLS-terminated at the edge, warm connection |\n| Gateway routing | 2ms | Select region, attach session context |\n| Prefix service lookup | 5ms | In-memory radix trie, single shard in common case |\n| Feature store fetch | 8ms | Parallel Redis batch get, overlapped with prefix lookup |\n| Ranker inference | 15ms | LightGBM over 1,000 candidates, CPU |\n| Post-processing | 5ms | Dedup, safety filter, trend boost |\n| Serialization | 2ms | Protocol buffers |\n| Network out | 5ms | Back through the edge |\n| **Server p99 total** | **~45ms** | Under the 50ms server budget |\n| **End-to-end p99** | **~80-95ms** | Includes network on both sides |\n\n\nTwo design decisions fall out of this table. Feature fetch overlaps with prefix lookup, which is why those two budgets are not additive. If they ran serially the budget would already be blown. And ranker inference gets by far the biggest slice, because scoring 1,000 candidates is real work and the GBDT has to fit that slice exactly. Halving the candidate pool to 500 would buy latency at the cost of recall, which is a real tradeoff the team might make during a load spike.\n\n---\n\n# 6. Deep Dives\n\n### 6.1 Prefix Index Structures: Trie, FST, and N-gram Hash\n\nThe prefix index is the single most performance-sensitive piece of the system, and three families of data structures compete for the job.\n\nA **radix trie** (compressed trie) stores each query as a path from root to leaf, with edges labeled by character substrings. Lookup time is proportional to prefix length, typically microseconds, and updates are straightforward. Memory footprint is moderate because common prefixes are shared, but the pointer overhead per node adds up at the scale of hundreds of millions of queries.\n\nA **finite state transducer (FST)**, typically built as a minimal DAFSA with value annotations, is a more compact representation where common suffixes are also shared. Lucene's suggester library uses this pattern, and production teams at large search companies often land here because the compression factor over a plain trie can be 3 to 5x at this scale. The tradeoff is that FSTs are expensive to update incrementally, which is why they are usually rebuilt in full each day.\n\nAn **n-gram hash index** stores every substring n-gram (typically 2-grams and 3-grams) of every query in a hash map, with query ids as values. Lookups for an exact prefix are fast, but the real reason to use it is fuzzy matching: it naturally supports edit-distance retrieval by looking up the n-grams of the (possibly misspelled) prefix and taking intersections.\n\n\n```mermaid\nflowchart TD\n ROOT[root]:::primary\n ROOT --> M[m]:::teal\n M --> MA[a]:::teal\n MA --> MAR[r]:::orange\n MAR --> MARS[s → mars]:::green\n MAR --> MARC[ch → march]:::green\n MAR --> MARV[vel → marvel]:::green\n MA --> MACH[ch → machine...]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram shows a radix trie for a tiny slice of the corpus. Edges are compressed: the \"ch\" edge after \"mar\" jumps multiple characters at once because there is no branching between them. Production tries at web scale look structurally identical, just with hundreds of millions of leaves.\n\n\n| Structure | Memory | Exact Lookup | Update Cost | Fuzzy Support | When to Use |\n|---|---|---|---|---|---|\n| Radix trie | Moderate | <1ms | Cheap | Needs separate index | Up to ~100M queries per shard, daily rebuild |\n| FST / DAFSA | Small | <1ms | Full rebuild | Needs separate index | Very large corpora where memory matters |\n| N-gram hash | Large | 1-3ms | Cheap | Native | Fuzzy-first workloads, small-to-medium corpora |\n\n\nIn practice most systems combine at least two. A radix trie or FST handles the exact-prefix path, which is the common case, and a small n-gram index handles the fuzzy path when the exact match set is empty or too small. The radix trie is simpler to start with and scales by sharding, which is why the advanced approach in the previous section used it.\n\n### 6.2 Freshness and Trending Queries\n\nThe day after a breaking news event, the base index is up to date. The hour it happens, the base index has never heard of the query. The typeahead has to surface it anyway, and it has to do it in minutes.\n\nThe solution is a dual-layer index. The base layer is the rebuilt-daily radix trie described earlier. The delta layer is a much smaller index, typically a few megabytes, that holds only queries whose short-window volume is rising meaningfully. A streaming job updates the delta layer every 60 seconds from the Kafka log stream.\n\n\n```mermaid\nflowchart LR\n Q[Prefix
earth]:::primary --> BI[Base Index
Daily]:::teal\n Q --> DI[Delta Index
60s]:::orange\n BI --> BM[~1000
base candidates]:::teal\n DI --> DM[~50 trending
candidates]:::orange\n BM --> MG[Merge +
Decay]:::green\n DM --> MG\n MG --> OUT[Unified
candidate pool]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nAt query time the prefix service looks up both layers in parallel and merges the candidate sets before the ranker sees them. The merge uses a time-decayed score of the form:\n\n\n```plaintext\nscore(q) = log(pop_30d + 1)\n + alpha * velocity_1h * exp(-age_hours / tau)\n```\n\n\nThe long-term popularity term is the stable backbone. The velocity term is the first derivative of short-window popularity, and the decay factor `exp(-age / tau)` with tau around 6 hours means a query that spiked an hour ago gets a large boost, a query that spiked three days ago gets only the baseline. Alpha is tuned empirically.\n\nThe streaming aggregator also does a small but critical job: it filters out queries whose short-window spike looks like bot traffic or a logging glitch. A query that appears 10 million times in one minute from a handful of IPs is almost certainly not a real trend. The trending boost has to survive this filter or it will occasionally promote nonsense to the top of typeahead, which is a public embarrassment at web scale.\n\nOne subtlety is that the ranker should not learn to ignore the trending boost entirely. The simplest way to handle it is to pass `velocity_1h` and `age_hours` as explicit features to the GBDT, so the ranker learns when to trust them. The post-processing trending boost then becomes a smaller adjustment on top of an already-ranked list, not the primary freshness signal.\n\n### 6.3 Spell Correction for Misspelled Prefixes\n\nA user who types \"restuarant\" should still see \"restaurant NYC\" in their suggestions. Failing silently here is one of the most visible product flaws in autocomplete: the user feels the system is broken.\n\nThree approaches solve this with different cost profiles.\n\n#### **Edit-distance over the trie (SymSpell)**\n\nPrecompute every query in the index with a set of deletion variants up to edit distance 2. \"restaurant\" becomes \"restaurant\", \"restaurnt\" (delete 1), \"restaurnat\" wait, SymSpell keeps only deletions and handles insertions by comparing against the user's deletion variants at lookup. Lookup is very fast, typically under 2ms, and the approach is language-agnostic.\n\n#### **Noisy-channel model**\n\nModel typos probabilistically as a channel: P(typed | intended) times P(intended). The probabilities come from typo logs: common typos like \"teh\" for \"the\" get high probability. This handles context-dependent typos better than pure edit distance but needs more infrastructure.\n\n#### **Neural seq2seq**\n\nTrain a small transformer (or a lightweight character-level LSTM) to map misspelled prefixes directly to canonical prefixes. Highest quality, especially for multi-character typos and transpositions, but the added 10 to 30ms of inference is hard to afford on every keystroke.\n\n\n| Approach | Latency | Quality | Training Cost | Best For |\n|---|---|---|---|---|\n| SymSpell | <2ms | Good for edit distance 1-2 | Low | Primary path at scale |\n| Noisy channel | 3-5ms | Better on common typos | Medium | Mature systems with typo logs |\n| Neural seq2seq | 10-30ms | Best on hard cases | High | Targeted backup path |\n\n\nThe practical design runs SymSpell inline as part of candidate generation. When the exact-prefix match returns fewer than some threshold of candidates (say, 20), the prefix service also issues an edit-distance lookup for the prefix and merges the results. The ranker sees a `prefix_match_quality` feature that indicates how much fuzziness was required, and it learns to trust high-popularity exact matches over high-popularity fuzzy matches.\n\n\n```mermaid\nflowchart LR\n P[Prefix:
restuarant]:::primary --> EX[Exact
Match]:::teal\n P --> FZ[SymSpell
ed <= 2]:::orange\n EX --> N1{< 20
results?}:::teal\n N1 -- Yes --> MG[Merge
Candidates]:::orange\n N1 -- No --> PASS[Use Exact]:::green\n FZ --> MG\n MG --> RK[Ranker]:::green\n PASS --> RK\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe conditional dispatch keeps the fuzzy path cheap when it is not needed. For head prefixes like \"mach\" the exact match already returns 1,000 candidates and the fuzzy lookup is skipped entirely. For long-tail or typo-heavy prefixes the fuzzy path runs, and the ranker sorts out which matches are worth showing.\n\nThe neural seq2seq model, if the system runs one at all, sits behind a quality gate: only invoke it when the prefix is long (say, 6 or more characters), the exact match set is near-empty, and the request is not on the hottest latency path (desktop, not mobile). That keeps its cost contained while still capturing the hardest typo cases where rule-based methods fail.\n\n### 6.4 Personalization Under a 50ms Budget\n\nFull per-user ranking, where the ranker is re-run with user-specific features for every query, is straightforward to describe and impossible to afford. At 100,000 QPS, every personalized rerank consumes the whole latency budget on its own. The production pattern is to precompute global rankings and adjust them with a cheap per-user side-layer.\n\nThe architecture uses a small **user tower** (a two-layer MLP or a shallow transformer) that produces a 32-dimensional user embedding from recent queries, location, language, and device. The user embedding is computed lazily, cached in Redis keyed by user id with a 30-minute TTL, and fetched in the feature-store call. Most requests hit the cache.\n\nAt ranker time, the user embedding joins the per-candidate features as 32 additional numbers. The GBDT learns how to combine these with global popularity and other signals. Crucially, the ranker is trained on the same features it will see at serve time, so it learns when personalization helps and when to ignore it.\n\nThe design principle is **boost, do not replace**. Personalization adjusts global scores by a bounded factor, typically plus or minus 20 to 30 percent. If a global top suggestion is massively popular, the boost cannot demote it out of the top 10 based on weak personalization signals. Without this guardrail, a user who once searched for \"chicago weather\" could see that query promoted over \"chicago\" for the next month, which is a worse experience than no personalization at all.\n\nTwo failure modes matter enough to call out. The first is cold start: a brand new user has no history. The user tower is trained to output a neutral embedding for missing features, and the ranker treats cold-start candidates like any other global ranking, which is the correct behavior. The second is feedback loop: if personalization always promotes what the user clicked yesterday, the user never discovers anything new. A small exploration budget (say, 10% of impressions) samples from non-personalized top candidates to counter this, which also generates training data that is less exposure-biased toward previously-seen queries.\n\n---\n\n# 7. Evaluation and Iteration\n\n### Offline Evaluation\n\nOffline evaluation uses held-out session logs: take real sessions, replay them through the candidate system, and compare the produced ranking against what the user actually clicked.\n\nThe primary metric is MRR on the click, computed per impression and averaged. NDCG@10 tracks graded quality when session-success outcomes are available as relevance grades (a clicked-and-successful query scores higher than a clicked-but-abandoned one). Typed-chars-saved is a product-aligned counterfactual: for each session, how many keystrokes would have been saved if the user had accepted the highest-ranked suggestion matching their eventual query.\n\n\n```python\ndef typed_chars_saved(session, ranker):\n final_query = session.submitted_query\n for i, prefix in enumerate(session.keystroke_prefixes):\n top = ranker.top_k(prefix, context=session.context, k=10)\n if final_query in top:\n return len(final_query) - len(prefix)\n return 0\n```\n\n\nThe evaluation set is stratified by prefix length (1-2, 3-5, 6+ characters), language, and popularity bucket (head, torso, tail). Quality degrades sharply on tail queries, so tracking them separately is the only way to notice when a model change helps head queries and silently wrecks tail queries.\n\nOne pattern that matters at scale: evaluation must be counterfactual-aware. The training data and the held-out log both come from sessions where the old ranker chose what to show. A naive evaluation rewards the new ranker for reproducing the old ranker's choices, which is not what the system should optimize for. Inverse propensity scoring weights each observed click by 1 over the probability the old system would have shown that suggestion, which removes the bias at the cost of higher variance.\n\n### Online Evaluation\n\nOnline evaluation is an A/B test with a staged rollout: 1% of traffic for 24 hours, then 10%, then 50%, then full. Primary metric is search success rate per session, because that is the product outcome. Suggestion CTR is the secondary metric. Seconds-saved is a north-star check that the product is actually helping users.\n\nGuardrail metrics catch regressions that do not show up in primary metrics. Abandonment rate, zero-result rate on the eventual search, safety violation rate, and per-region latency p99 all have fixed thresholds, and the rollout halts if any threshold is breached.\n\nInterleaving is a useful complement to split tests. Instead of sending user A to the treatment and user B to the control, interleaving mixes results from both rankers in the same response list for the same user. This produces tighter statistical power on preference comparisons at the cost of dev complexity, and it is how a large-scale system can meaningfully A/B test small ranker changes at low sample size.\n\n### Monitoring\n\nProduction monitoring tracks four things, each at the cadence it needs.\n\n**Health metrics** (per second): request rate, error rate, latency percentiles at p50, p95, p99, and p999. Break down p99 by prefix length because mobile typeahead queries dominated by short prefixes can mask a regression on longer prefixes.\n\n**Quality metrics** (per hour): suggestion CTR, suggestion-accept rate, per-position CTR distribution. The per-position distribution is a sanity check: healthy systems have a steep power-law CTR by position. If positions 3 through 10 start seeing elevated CTR, the ranker has probably lost its ordering signal.\n\n**Counter drift** (per hour): audit the streaming popularity counters for volume spikes from bot traffic, logging bugs, or malformed keys. A query that appears one million times in ten minutes but has no click-through is almost certainly not a real trend.\n\n**Feedback loop and exposure bias** (continuous): a small slice of traffic, typically 2 to 5 percent, serves a randomized control where the ranker's top choice is replaced by a random choice from the candidate pool. The CTR on those random slots gives an unbiased estimate of how good the candidate pool is independent of the ranker, and it also generates training data where the exposure probability is known.\n\n\n```mermaid\nflowchart LR\n SRV[Serving]:::primary --> LOGS[Impression +
Click Logs]:::teal\n LOGS --> MON[Monitoring
Dashboards]:::orange\n LOGS --> TR[Training
Pipeline]:::orange\n TR --> IPS[Inverse
Propensity
Weights]:::teal\n IPS --> MD[Next Model
Version]:::green\n MD --> SRV\n EX[Exploration
2-5% slot]:::orange --> LOGS\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe exploration slot closes the loop. Without it, the training data from any given week is entirely a product of last week's model, and the system drifts toward self-reinforcing rankings that look fine on offline metrics but slowly degrade real search quality. The 2 to 5 percent hit to CTR from random exploration is the cost of keeping the system honest, and it pays back in long-term model quality every time the team wants to ship a bigger change.","pageType":"ml-system-design"}

Design an Autocomplete System

Ashish Pratap Singh

Get Premium