Design Search Autocomplete (Typeahead)

Autocomplete (typeahead) is the dropdown of suggestions that appears as you type into a search box. It feels trivial, but it's deceptively demanding: a suggestion must come back in tens of milliseconds because the request fires on every keystroke, the suggestions must be the most relevant for a given prefix out of billions of possible queries, and the whole thing runs at enormous QPS. The design hinges on a single idea — precompute the top-k suggestions for every prefix so that serving is a near-instant lookup rather than a search.

            (root)
              │ c
              ▼
             [c]  top: cat(90), car(70), care(40)
              │ a
              ▼
             [ca] top: cat(90), car(70), care(40)
            ╱      ╲
         t ▼        ▼ r
       [cat]       [car] top: car(70), care(40), cargo(20)
       top:cat        │ e
                      ▼
                    [care] top: care(40), career(25)

  query "car" → jump to node [car] → return its cached top-k. done.

Step 1 — Clarify Requirements

Functional: given a prefix, return the top k (say 5–10) most relevant complete suggestions; suggestions reflect what's popular and evolve over time. Non-functional: extremely low latency (<50 ms, since it fires per keystroke), very high read QPS, high availability, and scalability to a huge phrase corpus. Scope decisions to state: prefix match only (not fuzzy/typo correction, which is a bigger NLP problem — though worth mentioning), suggestions ranked by global popularity (personalization optional), and a small fixed k. We can tolerate suggestions being a little stale (rebuilt periodically) — autocomplete doesn't need to reflect the last second of activity.

Step 2 — Capacity Estimation

Suppose 5 billion searches/day. Because each search is several keystrokes and each keystroke can trigger a suggest call, raw autocomplete QPS could be ~10× the search QPS — easily hundreds of thousands of QPS, with peaks higher. That read volume, multiplied by a sub-50 ms latency target, is what forces precomputation and in-memory serving. The phrase corpus (distinct queries worth suggesting) might be tens to hundreds of millions of strings; a trie over them, with top-k lists at nodes, is large but shardable across memory on a fleet of servers.

Step 3 — API Design

GET /suggest?prefix=car&limit=5
      → {suggestions: ["car", "care", "career", "cargo", "carpet"]}

# reads only. updates happen out-of-band via the data pipeline,
# not through this endpoint.

Step 4 — The Trie

A trie (prefix tree) stores strings character by character: each path from the root spells a prefix, and shared prefixes share nodes. Looking up a prefix is just walking down the corresponding characters — O(length of the prefix), completely independent of how many phrases the trie contains. That property is why it's the canonical autocomplete structure. The naive version stores complete words at leaves and, to answer a prefix query, traverses the entire subtree under the prefix node to gather and rank candidates — which is too slow at request time. The fix is Step 5.

Step 5 — Precompute Top-k at Each Node

Instead of searching the subtree on every request, cache the answer at the node: each trie node stores the top-k completions of its prefix, already ranked. Now a query is "walk to the prefix node, return its stored list" — essentially O(prefix length) with no ranking or subtree traversal at request time. The cost is moved to build time (computing those lists) and storage (k entries per node), which is exactly the right trade for a read-dominated system: do the expensive work once, offline, and make every one of the billions of reads cheap. This is the classic move of pushing work from the read path to the write/build path.

Step 6 — Ranking

"Top" suggestions are ranked primarily by popularity — how often each complete query has been searched historically. Refinements:

• Time decay — weight recent searches more so that trending terms rise and stale ones fade (an older query that was once huge shouldn't dominate forever).
• Personalization / context — location, language, or user history can re-rank, at the cost of breaking the simple shared precomputation (now lists vary per segment).
• Business rules — filtering of offensive or disallowed suggestions happens at build time.

Step 7 — Building and Updating the Trie (the Data Pipeline)

The trie isn't built live; it's produced by an offline pipeline from query logs:

search logs ─▶ aggregate counts per query (MapReduce / stream)
            ─▶ filter (offensive, rare) + apply time-decay weights
            ─▶ build trie, compute top-k at every node
            ─▶ publish immutable snapshot ─▶ load into serving fleet

Aggregation is a textbook batch (or streaming) job. The output is an immutable snapshot; serving nodes load a new snapshot periodically (e.g. hourly/daily) and atomically swap to it. This read/write decoupling is what keeps the serving path simple, fast, and lock-free.

Step 8 — Serving and Sharding

The serving tier holds the trie in memory for speed and is horizontally scaled. Since the whole trie may not fit on one machine, shard by prefix: e.g. all prefixes starting with "a"–"m" on one shard group, "n"–"z" on another (or a finer split to balance load — common prefixes like "th" get more traffic). A lightweight aggregator/router sends each request to the shard owning that prefix. Each shard is replicated for availability and to spread read load. Because the data is read-only between snapshot swaps, replicas are trivially consistent.

Step 9 — Caching and Client-Side Tricks

Several layers cut latency and load:

• Client debouncing — wait ~100–300 ms after the last keystroke before firing a request, so "h-e-l-l-o" sends one or two calls, not five.
• Client/browser caching — cache suggestions for prefixes the user already typed (typing then backspacing should hit local cache).
• Server cache / CDN — the most popular short prefixes ("a", "th", "you") account for a huge share of traffic; cache their top-k at the edge with a modest TTL.

Step 10 — Real-time vs Batch Updates

How fresh should suggestions be? A pure batch rebuild (hourly/daily) is simple and sufficient for most terms, but misses trending spikes (breaking news). The trade-off:

A practical hybrid: a large, slowly-rebuilt base trie plus a small real-time layer that tracks trending terms via a streaming counter and merges them into results. Mention this when the interviewer pushes on "what about breaking news?"

Step 11 — Key Tradeoffs

• Precompute vs compute-on-the-fly. Storing top-k at every node makes reads O(1)-ish but costs storage and build time; computing per request saves storage but blows the latency budget. For read-dominated autocomplete, precompute wins decisively.
• Freshness vs cost. More frequent rebuilds (or streaming updates) surface trends faster but cost more compute; most terms tolerate hours of staleness.
• Personalization vs shareability. Global top-k lists are shared across all users (cheap); personalized lists multiply storage/compute and weaken caching.
• Trie size vs sharding overhead. Finer prefix shards balance load better but add routing complexity.