Design search typeahead

Type "how to" into a search box and ten suggestions appear before your next keystroke. Every keystroke is a request, so a search engine serves far more suggestion lookups than searches, and each must answer in a few milliseconds. The trick is to do almost no work at query time: precompute the answer for every popular prefix in advance, and serve it from memory. It follows the interview framework phase by phase.

1. The prompt

"Design the autocomplete for a search box: as the user types, show the top 10 most popular queries that start with what they've typed."

The read path must be almost free, so the design moves the work offline: a pipeline that counts queries and precomputes answers, and a serving fleet that only looks them up. The interesting parts are the data structure, freshness for trending queries, and taking load off the servers altogether with the client and the CDN.

2. Frame the problem

3. What it must do

1. For a prefix, the system returns up to 10 suggestions, ranked by popularity.
2. Popularity reflects recent searches: trending queries appear within minutes.
3. Operators can block offensive or unsafe suggestions immediately.

Not now:

• Spelling correction: a different model.
• Deep personalisation: mentioned in follow-ups.
• Tokenisation for every language.

4. How well it must do it

5. Numbers that change the design

6. The nouns

• Query log event.
• Query count: time-decayed popularity.
• Prefix entry: a prefix and its top 10.
• Table version: one build of all prefix entries.
• Block list.

query log      text, time, locale                      (stream → data lake)
query counts   (locale, query) → decayed score         (batch job output)
prefix table   (locale, prefix) → [(query, score) × 10]   versioned, loaded whole into memory
block list     terms and exact queries, applied at build and at serve time

7. The contract

GET /v1/suggest?q=how%20to%20m&locale=en-IN&limit=10
→ 200 {"suggestions": ["how to make pancakes", "how to meditate", …]}
   Cache-Control: public, max-age=300

Anonymous and cacheable: personal suggestions (the user's own history) are mixed in on the device, so the shared response stays cacheable.

Data flow: (1) searches are logged → (2) a batch job counts and builds the prefix table → (3) servers load the new version → (4) a stream job adds trending queries → (5) the client debounces and caches; the CDN answers popular prefixes; misses hit a server's memory.

8. First working version

A queries table with counts, updated from the search logs, and a suggestion service that queries it.

8.1 Suggesting

For each keystroke, the service runs a prefix query sorted by count.

8.2 Counting

A nightly job aggregates the day's search log into the counts table.

8.3 Blocking

A blocked flag on the queries row hides it from the query.

9. Make it hold up

9.1 Finding the top suggestions for a prefix very fast

9.2 Building the tables, and swapping safely fresh · available

1. Search events stream into a log (Kafka) and land in the data lake.
2. A batch job (hourly or daily) counts queries over a window, with more weight for recent searches (exponential decay), drops rare queries, and filters out blocked terms.
3. It builds the prefix → top-10 table for every prefix of every kept query.
4. The new table is loaded into the serving fleet as a whole new version, and servers switch to it atomically. Serving never sees a half-built table; a bad build is rolled back by switching back.

9.3 Serving it fast, and mostly not serving it at all very fast · scale

• Suggestion servers hold the table in memory, partitioned if needed by the first characters of the prefix (with care: "s" is far busier than "x", so balance partitions by traffic, not letters) and replicated for throughput.
• Client side: wait ~100 ms after the last keystroke before sending (debounce), cancel requests that are out of date, and cache answers in the browser, since users often type and delete.
• CDN: short prefixes are requested by everyone and change slowly, so they cache very well at the edge for a few minutes.

9.4 Trending queries fresh

A daily rebuild misses a story breaking right now. Add a stream job that counts queries over the last few minutes (Module 23) and detects sudden rises; a small "trending" table is merged into results at query time, or into the top lists of affected prefixes. Keep CDN lifetimes short (a few minutes) so trends reach users.

9.5 Personalisation and safety safe

Blend global suggestions with the user's own recent searches, kept on their device or in a small per-user store, so the shared response stays cacheable. Filter suggestions through a block list and safety classifiers at build time, plus an emergency block list applied at serving time for anything that slipped through. An emergency block also purges affected prefixes from the CDN.

9.6 The whole design after the deep dives

Building, swapping and serving suggestions in the final design.

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Precompute everything offline (trivial lookups, freshness limited by build frequency).
• A trending stream to close the gap.
• Atomic versioned swaps.
• Heavy client and CDN caching (fewer requests, minutes of staleness).
• Personalisation on the device to keep responses shareable.

What we'd watch:

• Suggest latency p99.
• CDN hit rate.
• Table age.
• Acceptance rate.
• Trending lag.
• Block-list hits.

At 10×:

• More replicas.
• Per-locale tables.
• More edge caching.

Common mistakes:

• Querying the database per keystroke.
• Searching the trie subtree at query time.
• No client debouncing.
• Ignoring the CDN.
• Rebuilding in place.
• No answer for trending queries or offensive suggestions.

13. Try it, check yourself, read more

A real trie built from about 40 sample queries with counts. Each node stores its top 5. Type a prefix: the lookup walks one node per character and returns the stored list.