Design Typeahead Search

You type "pi" into a search box and, before you type the next letter, a list drops down: "pizza near me", "pie crust recipe", "pilates". Each keystroke is a request, the answer must arrive before the next keystroke, and the list must reflect what millions of people actually search for.

Interviewers like this question because the obvious answer (a trie on a server) is half right. The real work is precomputing answers offline and spending a 100 ms budget across the client, the network and an edge cache. The steps follow A Framework for Any Design. If tries are new, read Tries first.

#Clarify the problem

• Functional: for a typed prefix, return the 5 most popular past queries that start with it; popularity reflects recent searches; bad suggestions can be removed.
• Non-functional: under 100 ms from keystroke to list for most users; very high availability (the search box must never break, so an empty list is the fallback); popularity at most a day old, trending within an hour as a stretch.
• Out of scope: personalisation, spelling correction, languages other than English, searching the documents themselves (see Search Systems).

#Estimate the scale

• Searches: 50 million × 6 = 300 million a day.
• Suggestion requests: a 20-character query typed one key at a time would send 20 requests. Fewer go out: people often pick a suggestion after a few letters, the client skips keystrokes that come in quick bursts (debouncing), and its cache answers repeats. Assume 6 requests per search. 300 million × 6 = 1.8 billion a day, and 1.8 × 10⁹ ÷ 86,400 s ≈ 21,000 a second on average. Assume a 3x peak: about 62,500 a second.
• Query log: 300 million searches × 100 bytes ≈ 30 GB a day of raw input for the offline build.

#Define the API

GET /v1/suggest?q=pi&limit=5
  200 OK
  Cache-Control: public, max-age=3600
  { "q": "pi", "version": "2026-11-14",
    "suggestions": ["pizza near me", "pie crust recipe", "pilates",
                    "pineapple upside down cake", "piano lessons"] }
 
  q is empty            200 with an empty list
  q longer than 50      400 Bad Request
  service overloaded    503; the client shows no list and the user keeps typing

The decision worth arguing is making the response public and cacheable. No cookie, no user id, a normalised prefix: then every user typing "pi" in the same hour hits one cached response at the edge. The cost is that the API cannot personalise, which is why personal suggestions (your own recent searches) are merged on the client instead. The max-age of one hour fits the build: data that changes daily can be an hour stale at the edge.

#Model the data

-- serving: read-only, rebuilt each build, held in memory on every server
prefix_top5
  prefix       VARCHAR(20)   PRIMARY KEY   -- "pi"
  suggestions  [ (query, score) x 5 ]       -- about 150 bytes a row with the key
  version      DATE
 
-- offline: written by the log pipeline, read only by the build
query_counts
  query        VARCHAR(100)
  day          DATE
  count        BIGINT
  PRIMARY KEY (query, day)
 
blocklist      -- queries and patterns never to suggest; small, edited by people

The serving access pattern is a single-key lookup on a table that never changes between builds. That suits an in-memory hash map loaded from a file, on every server. No database sits on the hot path. If the table outgrew memory (many languages, longer prefixes), the next step is a key-value store partitioned by prefix. The offline counts are large, append-only and scanned in bulk by a batch job, so they belong in files in blob storage or a data warehouse, not a serving database.

#High-level design

The hot path only looks up a precomputed answer. Counting, ranking and filtering happen offline, and their only output is a file.

#Deep dives

#A trie, or a precomputed top five per prefix

A trie stores queries letter by letter, so all queries starting with "pi" sit under one node. Finding that node takes one step per character. The trap is what comes next: the subtree under "p" may hold a million queries, and searching it on every keystroke to find the best five is far too slow. The fix is to do that search once, at build time, and store each node's top five on the node.

The 30 GB bound fits in memory, so every suggest server holds the whole map and there is no sharding at all. If it stops fitting, shard by a hash of the prefix, never by first letter: far more queries start with "s" than with "x", so letter ranges give lopsided shards.

#Updating popularity offline

Counting on the hot path would mean a write per search and a re-sort of up to 20 prefix lists per query. Do it in batch: the build reads the day's log, adds it to the history, filters, ranks, and writes a complete new table.

Recent searches should count for more. Weight each day's count by 0.8 for every day of age. A query searched 1,000 times exactly a week ago scores 1,000 × 0.8⁷ ≈ 210; one searched 300 times today scores 300 and ranks higher. The build also drops queries searched fewer than a few times (they are mostly typos and private details such as names or addresses) and anything on the blocklist.

#The latency budget and where caching happens

100 ms is the whole budget from keystroke to list, so spend it on purpose. Distance sets the floor: light in fibre travels about 200 km per millisecond, so a server 6,000 km away costs at least 2 × 6,000 ÷ 200 = 60 ms per round trip before any work. A rough plan for a user near an edge location:

An edge hit lands at about 55 to 70 ms, a miss to a nearby region at about 85 to 100 ms, and a miss to a far region blows the budget. So caching does most of the work, at three levels:

• In the client. Keep every response for the session. Backspacing and retyping cost nothing. Replies can arrive out of order, so drop any whose prefix no longer matches the box. One subtle shortcut: if the list for "pi" had fewer than five entries, it is complete, and the client can filter it for "piz" without asking.
• At the edge. Short prefixes are few and hot: there are only 26 + 26² + 26³ = 18,278 letter prefixes of up to three characters, and they cover a large share of keystrokes. Assume the edge answers 60% of requests: the 62,500 a second at peak become 25,000 a second at the servers. See CDNs.
• On the server. The whole table is already in memory, so there is nothing else to cache.

Run suggest servers in several regions so misses stay near. A new region needs a file copy, not replication.

#Bottlenecks and failures

At 10x (625,000 requests a second at peak), the edge still takes 60%, leaving 250,000 a second for the suggest servers. They share nothing, so add servers; if one handles 10,000 a second (an assumption that depends on the HTTP stack, since the lookup itself is tiny), that is 25 servers plus spares. The build is the slower wall: ten times the log is 300 GB a day, so it must run as a distributed batch job split by query. Many languages would multiply the table; give each language its own table and shard by prefix hash when one no longer fits in memory.

#What a strong answer sounds like

#Follow-up questions

#How would you personalise suggestions?

Keep the shared, cached list. The client stores the user's recent searches and puts matching ones first, so the shared path stays cacheable.

#How do you show trends within an hour?

Add a stream job that counts queries over the last hour and compares them with their usual rate. It publishes a small list of spiking queries every few minutes; servers merge them into results at serve time, and the edge TTL drops to a few minutes for short prefixes.

#How do you handle typos?

Fuzzy matching per keystroke is expensive. Mine common misspellings from the logs (people who typed X, then searched Y) and add them as extra prefixes pointing to Y's list.

#What about other languages?

A table per language, chosen by the request locale, which joins the cache key. Normalisation differs by language (accents, scripts without spaces), so it lives in one library shared by the build and the client.

#Why not use a search engine's prefix queries?

You can, for a small catalogue. At 62,500 requests a second, ranking at query time costs far more than a map lookup, and the answers change only daily.