Problem RestatementProblem
Design the autocomplete box in a search bar. As the user types "how to", we show the top ~10 suggestions such as "how to tie a tie" and "how to make pancakes", updating on every keystroke. Suggestions come from what people search most, should include trending searches within minutes, and must appear in under 100 ms per keystroke.
RequirementsRequirements
1.1 Functional
- Return the top 10 suggestions for a prefix.
- Rank by popularity, with freshness (trending) and optionally personalization.
- Update suggestions as new searches happen.
- Hide offensive or blocked suggestions.
1.2 Non-Functional
- Very low latency: under 100 ms end to end, ideally about 10 ms on the server.
- Very high QPS: every keystroke is a request.
- Highly available. It's fine if suggestions are a few minutes stale.
1.3 Scale Estimates
- 500M searches/day, ~10 keystrokes each → 5B suggestion requests/day ≈ 60K/sec, peak ~200K/sec.
- Distinct queries worth suggesting: ~100M. At ~50 bytes each plus trie overhead, that's tens of GB. This can be sharded, and the most popular prefixes are small.
1.4 API Design
GET /v1/suggest?q=how%20to&limit=10&lang=en→["how to tie a tie", "how to make pancakes", ...]
High-Level ArchitectureArchitecture
2.1 Overview
- Suggestion Service: looks up the prefix in an in-memory index and returns the top 10.
- Trie index: built offline and loaded into memory on suggestion servers.
- Query log pipeline: every completed search goes to Kafka. A batch job counts queries (e.g., over the last 7 days, weighted toward recent days) and builds a new trie. A streaming job tracks trending queries.
- Caches: the browser caches recent results. The CDN or edge caches very common short prefixes ("a", "ho", "how").
2.2 Architecture Diagram
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
U["Search box"] -->|"prefix"| CDN["CDN / edge cache"]
CDN --> SS["Suggestion Service - in-memory trie"]
U -->|"completed searches"| K[("Kafka - query log")]
K --> BJ["Daily batch - count, build trie"]
K --> ST["Streaming - trending counts"]
BJ --> OS[("Trie snapshots")]
OS -->|"load"| SS
ST -->|"trending boost"| SSData Structure: Trie with Top-K
A trie (prefix tree) stores strings letter by letter: the path h → o → w represents "how". To make lookups instant:
- At each node, store the top 10 completions for that prefix, already sorted.
- A lookup walks down the prefix (length L, e.g., 6 steps) and returns the stored list. No searching the subtree.
- Memory trade-off: we store top-10 lists at every node, which is more memory but constant-time answers.
A simpler alternative: a sorted list of all queries, where a binary search finds the range with that prefix. That still needs top-K, so we precompute it for short prefixes.
Key FlowsFlows
4.1 Serving a keystroke
- The client waits ~50 ms after typing stops (debounce) to avoid sending a request for every fast keystroke.
- It checks its local cache (results for "how t" are often reused).
- The edge cache serves common prefixes. Otherwise, the suggestion server walks the trie and returns the top 10.
- The server optionally mixes in trending and personal suggestions (recent searches by this user).
4.2 Building the index
- A daily job counts all queries from the logs, with weights so recent days count more.
- It removes blocked and unsafe queries and applies minimum-count thresholds (rare queries may contain private info).
- It builds the trie with top-K lists, writes a snapshot, and servers load it (blue/green: load the new one, then switch).
Deep Dive A — Suggesting something that only started happening an hour agoDeep dive
The trie is built from a query log and shipped to the serving fleet. News breaks, everyone searches a name nobody searched yesterday, and the box has never heard of it.
Rebuild the trie every night
A batch job counts yesterday's queries, builds the structure, and pushes it to the servers at 3 AM.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
LOG[("Yesterday's query log")] --> B["Nightly build"]
B --> T["Trie shipped at 3 AM"]
T --> S["Serving fleet"]
NEWS["Story breaks at 10 AM"] --> GAP["No suggestion until 3 AM tomorrow"]Up to 24 hours of staleness on exactly the queries with the most volume. Users type the full phrase by hand, which is the one thing autocomplete exists to prevent.
Rebuild more often
Run the job hourly instead of nightly. Staleness drops from a day to an hour.
The cost scales with the frequency: each build re-counts the whole log, rebuilds a structure of tens of gigabytes, and pushes it to every server. Running it hourly means the fleet is constantly absorbing full index pushes, and an hour is still far too slow for a story that peaks in twenty minutes. Rebuilding faster is spending more to remain late.
Leave the big index alone and ship a tiny trending one
Two structures with different update rates, merged at lookup:
- The base trie keeps its slow rebuild. It holds the long tail, it is large, and almost none of it changes day to day.
- A trending index — a few thousand queries, kilobytes — is produced by a stream job that counts queries in 5-minute windows and flags the ones whose rate jumped well above their own baseline. It ships to every server every few minutes.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["Query stream"] --> WIN["5-minute counts vs baseline"]
WIN --> TR["Trending index - a few thousand queries"]
TR -->|"pushed every few minutes"| SRV["Serving node"]
BASE[("Base trie - nightly")] --> SRV
P["Prefix 'how to'"] --> SRV
SRV --> MERGE["Merge top-10 from base with trending matches, boosted"]
MERGE --> OUT["Suggestions"]Flag on the jump relative to a query's own baseline, not on raw volume — otherwise "weather" is permanently trending and nothing new can ever rank.
One detail that matters more than it sounds: break score ties alphabetically, deterministically. Otherwise two suggestions with equal scores swap places between keystrokes and the list appears to flicker while the user types.
Deep Dive B — Scale and shardingScale
- Replicate full tries across many servers if they fit in memory (~tens of GB is fine on large machines).
- If too big, shard by prefix: "a–c" on shard 1, and so on. Popular first letters (like "s") need smaller ranges. A router maps the first 1–2 characters to a shard.
- Deterministic ties: when two suggestions have equal scores, sort alphabetically so results don't flicker between keystrokes.
- Personalization: keep each user's recent searches on the client or in a small per-user store, and blend them in at the top.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Index | Trie with top-K per node | O(prefix length) lookups | Compute top-K on each request: too slow |
| Updates | Daily rebuild + streaming trending | Stable and fresh | Update the trie on every search: complex locking, costly |
| Serving | In-memory, replicated | Microsecond lookups | Database queries: too slow per keystroke |
| Client | Debounce + local cache | Cuts requests by more than half | Request on every key: wasteful |
Common Follow-up QuestionsFollow-ups
- "How do you handle typos?" Add a fuzzy-matching fallback (edit distance of 1) for when the prefix has no results, or learn common misspellings from logs.
- "Privacy?" Only suggest queries typed by many distinct users (e.g., 50+), so personal data never shows up as a suggestion.
- "Other languages?" Build a separate trie per language or market, and normalize text (lowercase, remove accents) before lookup.
Wrap-UpWrap-up
Keep an in-memory trie where each node stores its precomputed top 10 completions, so every keystroke is a short walk down the tree. Rebuild it daily from query logs with filters, blend in a streaming trending index for freshness, and cut load with client debounce and caching plus edge caching of short prefixes. Replicate the trie, or shard it by prefix when it grows too big.