Designing Typeahead Autocomplete: Sharded Tries and Precomputed Top-K

Autocomplete has the most hostile latency budget in consumer software. A user typing at 200ms per character fires a query per keystroke, and suggestions that arrive after the next keystroke are garbage — the effective deadline is ~100ms end-to-end, network included. That budget outlaws almost everything: no database query, no scoring pass over candidates, no fan-out to ten services. The design lesson autocomplete teaches better than any other system: when the read deadline is brutal, move all the work to write time.

Requirements

Suggest top 5-10 completions per prefix from a corpus of billions of historical queries; p99 under ~50ms server-side; suggestions reflect popularity and recency (a breaking-news term should surface within minutes-hours); personalize lightly; filter unsafe content.

The read path: a lookup, not a computation

The core structure is a trie over query strings — but the naive version (walk to the prefix node, DFS the subtree, collect completions, rank by frequency) does unbounded work per keystroke: prefix "a" has a subtree with hundreds of millions of descendants. DFS-at-read-time is the answer that fails the interview.

The fix: store the answer in the node. Each trie node holds its precomputed top-K completions.

node "app" -> ["apple", "apple watch", "app store", "application", ...]  (K=10)
read path: hash/walk to node -> return stored list -> done. O(prefix length).

Space math holds up: top-10 per node, with completions stored once and referenced by ID, keeps the whole structure memory-resident even at billions of queries — and memory-resident is non-negotiable at this deadline. Serving nodes hold the trie in RAM, replicated for throughput; a request touches exactly one shard (see below), so p99 is a single in-memory lookup plus network.

Two practical refinements interviewers reward: prefix hashing beats pointer-chasing (store prefix → top-K in a flat hash map; the "trie" is conceptual — cache-friendly, trivially serializable, and shardable by key), and client-side caching of results per prefix, since typing "appl" then backspacing to "app" should not re-query.

Sharding: not A-Z

The instinctive shard-by-first-letter is a skew disaster — 'a' and 's' carry orders of magnitude more traffic than 'x'. Shard by hash of the full prefix instead: hash("app") mod N. Every prefix lives on exactly one shard, load spreads uniformly, and a query still touches one shard (the client asks for the prefix it has, not a range). The trade: prefixes of one word scatter across shards, so there is no subtree locality — which costs nothing, because we never walk subtrees at read time. The precompute decision and the sharding decision reinforce each other; noticing that coupling is senior-level signal.

The write path: where the actual system lives

Suggestions come from query logs, so the pipeline is a streaming aggregation feeding periodic index builds:

search logs -> stream aggregation (count per query, sliding windows)
            -> candidate scoring: frequency × recency decay × quality/safety filters
            -> offline build: for every prefix of every candidate, compute top-K
            -> ship immutable index shards to servers (atomic pointer swap)

The top-K-per-prefix build is a classic MapReduce/Spark job: emit (prefix, query, score) for each prefix of each query (a 20-char query emits 20 pairs), group by prefix, keep K. Rebuild cadence — daily or hourly — is fine for the stable head of the distribution but fails breaking news, so real systems run a two-tier index: the big offline-built base, plus a small real-time overlay fed by the stream (last few hours' trending deltas), merged at read time. Two sorted lists of ~10 merged in-process is nanoseconds; freshness without touching the base build. Same lambda shape as ad-click counting — batch for truth, stream for now.

Scoring inside the build is where product lives: raw frequency plus time decay (score = Σ count_i × e^(-λ·age_i)), geography/language partitioning (separate indexes per locale beats per-query filtering), and the safety filter as a build-time exclusion list — filtering at read time means one config bug serves the unfiltered list.

Personalization stays out of the hot structure: fetch the user's recent-queries list (small, cached) and merge-boost client- or edge-side. Blending a per-user model into the shared index is how you turn one lookup into a scoring pass and blow the budget.

Interview probe	Answer sketch
Why not Elasticsearch prefix queries?	Search engines score at read time; the deadline demands O(1) lookup of precomputed answers
Update top-K on every search, online?	Write amplification: one query touches 20 prefix entries under contention; stream + periodic merge wins
Multi-word / mid-word matching?	Index suffixes/word-boundaries too (bigger build, same read path) — state the space trade
Typos?	Fuzzy matching breaks the precompute; practical answer: small edit-distance expansion at the edge for short prefixes only

The transferable principle, worth closing an interview with: precompute-at-write vs compute-at-read is a dial, and autocomplete sits at the extreme end — every design choice (per-node top-K, hash sharding, immutable index ships, overlay merges) is that one dial turned all the way.