Design Search Autocomplete: Tries, Top-K Caching and Fast Rebuilds

Listen

Start by fixing scope. Given a prefix, return the five most popular completions. New trending queries should appear within about an hour. The whole round trip must feel instant, so under a hundred milliseconds end to end, which leaves the server maybe twenty. Suggestions being a few minutes stale is completely fine. Spelling correction and personal history are out of scope for now; we will mention them as extensions.

Ask scale

Now the numbers. A hundred million daily users doing ten searches each is a billion searches a day. Each search fires about six suggest calls after debouncing, so six billion requests a day, sixty thousand per second on average and close to two hundred thousand at peak. The key insight is size: the top fifty million queries are only a gigabyte of text, and the full trie fits in tens of gigabytes. It fits in memory.

100M daily users x 10 searches
  = 1B searches/day
about 6 requests per search (debounced)
  = 6B requests/day
6B / 100,000 s = 60,000 rps average
peak x3 = about 180,000 rps

log writes: 1B queries/day = 10,000/s
keep top 50M queries x 20 chars = 1 GB
trie with top-5 per node: 10-30 GB

Define API

The API is tiny. One GET with the prefix, a limit and a language, returning a list of strings. Add a Cache-Control header so browsers and the CDN can reuse answers for a few minutes. Notice what is not here: we do not log anything on this path. The real search service already records every submitted query, and that is our data source. An admin endpoint lets a trust and safety team block terms.

GET /v1/suggest?q=app&limit=5&lang=en
200 { "q": "app",
      "items": ["apple", "app store",
        "apple watch", "apps", "app ideas"]}
Cache-Control: max-age=300

search events are logged by the
search service, not this API

POST /v1/admin/blocklist { "term": ... }

Data model

There are two kinds of data. The serving data is a read-only map from prefix to its top five terms with scores, held in memory. The source of truth is an analytics table of query counts per hour, in a column store or data lake, because we only ever scan and aggregate it. Neither needs a relational database or transactions. The link between them is a versioned snapshot file that an offline job builds.

serving (in memory, read-only):
  prefix -> [(term, score) x 5]
  "app" -> apple 9.1, app store 8.7 ...

source of truth (column store):
  query_counts(term, hour, count)
  partitioned by hour

snapshot file: trie_v2026_10_24_14
  built offline, loaded atomically

High-level design

First, the naive version, because interviewers like to hear why it fails. Store queries with counts in a table and run a prefix match ordered by count. An index finds the matching range, but for a short prefix like a it still sorts millions of rows, and we need almost two hundred thousand of these a second. The answer to any prefix barely changes within an hour, so compute it ahead of time and just look it up.

Here is the read path. The browser asks for the prefix. Very short prefixes like a or ap are identical for everyone, so the CDN answers most of them. On a miss, a stateless suggest service asks a trie server, which walks three characters down an in-memory tree and returns a precomputed list. That lookup takes microseconds; the network is the slow part.

The write path is completely separate. Submitted queries land in a Kafka topic. An aggregator rolls them into hourly counts and applies a time decay so last week matters less than today. A builder job turns the scored terms into a new trie, writes a versioned snapshot, and the trie servers load it and swap it in atomically. Reads never wait on writes.

SELECT term FROM queries
  WHERE term LIKE 'app%'
  ORDER BY count DESC LIMIT 5

index helps find the range, but
  "a%" still sorts millions of rows
180,000 of these a second: no

fix: precompute the answer
  for every prefix, ahead of time

Deep dive: the trie

The core data structure is a trie, a tree with one character per edge. The naive version walks to the prefix node and then searches its whole subtree for the best terms, which for the letter a means millions of nodes. The fix is to store the top five directly at every node. Now a lookup is just a walk of a few characters. You pay in memory and in rebuild work, which is fine because we rebuild offline.

A simpler variant skips the tree entirely: precompute every prefix up to about twenty characters and store prefix to top five in a key-value store like Redis. It uses more memory because shared prefixes are not shared, but it is trivial to shard and any team can run it. Cap the prefix length, because almost nobody types twenty characters before picking a suggestion. Either answer is fine if you say why.

naive: walk to "ap", then search the
  whole subtree for the best 5
  = millions of nodes for "a"

better: every node stores its top 5
  root -> a -> p  [apple, app store..]
  lookup = O(prefix length)

cost: more memory, and top lists
  must be rebuilt when scores change

precompute every prefix up to 20 chars
  "a" "ap" "app" "appl" "apple"
store in a key-value store (Redis)
  GET sugg:en:app -> list of 5

+ simple, any KV store works
+ easy to shard by key
- more keys: no shared prefixes

cap length: long prefixes are rare

Deep dive: freshness

Popularity is a decayed count: each hour's count is weighted down by its age, here with a one-day half-life, so yesterday's trend fades naturally. Rare terms below a threshold are dropped, which also protects privacy. Every hour the builder makes a fresh trie from scratch. Each server loads the new version next to the old one, flips a pointer, then frees the old one. No locks, no partial states.

Hourly is not enough when news breaks. Add a small streaming job that counts the last fifteen minutes and flags only terms spiking far above their normal level. Their prefixes get a short hot list in Redis. The suggest service merges the trie's top five with that hot list and re-ranks. This is a lambda style split: a big accurate batch layer and a tiny fast layer.

score = sum over hours of
  count(h) x 0.5 ^ (age_h / 24)
  (half-life of one day)

drop terms seen under N times
filter blocklist at build time

every hour: build v43 from scratch
servers load v43 next to v42,
flip a pointer, free v42

problem: news breaks at 14:05,
  next build is at 15:00

stream job counts last 15 minutes
  only for terms spiking vs baseline
small hot list per prefix in Redis

suggest service merges:
  trie top 5 + hot list, re-rank

Deep dive: scaling

Should you shard? First check whether it fits. A twenty gigabyte trie fits on one machine, so the easiest move is replication: every server holds the full trie and the load balancer spreads requests. If it outgrows one machine, shard by prefix range, but not by first letter, since s alone is far bigger than x. Split ranges by measured traffic and keep the map in config. Separate languages into separate tries.

trie 20 GB fits on one box
180,000 rps / 20,000 per box
  = 9 boxes, run 15 across zones
  each holds the full trie

if too big: shard by prefix range
  not by first letter: "s" is huge
  split by measured traffic
  a-ap | aq-b | ... kept in config
per language: one trie each

Deep dive: client

Half the scaling happens in the browser. Debounce, so a fast typist sends one request instead of five. Cancel the old request when a new key arrives. Cache every prefix result for the session, so backspacing costs nothing. The CDN can hold one to three character prefixes for everyone. And the user's own recent searches can come from local storage, which adds personalization without any server state.

Trade-offs

Failure modes are friendly here because reads and builds are decoupled. A trie server dies, and the load balancer routes around it. The build job fails, and servers keep the last good snapshot while an alert fires on snapshot age. A bad build is the scary one, like an empty trie or offensive terms, so validate size, sample queries and blocklist hits before publishing, and keep one-click rollback.

Monitor p ninety-nine latency, CDN hit rate, snapshot age and build duration, plus the business metric: how often people click a suggestion. At ten times the traffic you just add replicas and lean harder on the CDN. Ten times the vocabulary is what forces range sharding or pruning low-score tails. Typo tolerance belongs in a separate fuzzy service using edit distance or n-grams.

Interview summary

In the interview, say it in this order. Top five suggestions per prefix in under a hundred milliseconds. Around two hundred thousand requests a second at peak, but the data fits in memory. A cacheable GET endpoint. A trie with top five stored at every node. An hourly offline rebuild from query logs with decayed counts and an atomic swap. A streaming hot list for breaking trends. Replicate before you shard. And debounce on the client.