Infrastructure · Design 30

Design Autocomplete

Design search autocomplete (typeahead) in a 45-minute interview: a trie with top-k per node, prefix tables, the offline aggregation pipeline, trending, caching and a latency budget.

IntermediateInterview priority: High55 min
On this page
  1. How to use this page
  2. 1. Clarify the requirements
  3. 2. Back-of-the-envelope estimates
  4. 3. API
  5. 4. Data model
  6. 5. High-level design
  7. 6. Deep dives
  8. 7. Bottlenecks, failures and monitoring
  9. 8. Follow-up questions
  10. Quiz

How to use this page

This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first, then open ours and compare. Autocomplete is a lesson in moving work off the request path: the request itself must be almost free, so nearly everything is computed in advance.

PhaseTime in a 45-min interviewWhat you produce
1. Clarify requirements5 minWhat is ranked, how fresh, what is filtered
2. Estimate5 minRequests/s, trie size, the latency budget
3. API2 minOne cacheable GET
4. Data model5 minQuery log, counts, trie snapshot, blocklist
5. High-level design10 minThe online path and the offline path
6. Deep dives10–15 minData structure, top-k, freshness, caching, sharding
7. Wrap up2–3 minBottlenecks, failures, what you would monitor

As the user types in a search box, show the top 10 most popular completions for the prefix, updated as trends change (within an hour or so). Filter offensive suggestions. Skip spelling correction, personalisation and the search results themselves.

1. Clarify the requirements

Your turn: scope it

The interviewer says: "Design autocomplete for a search box." Write the questions you would ask, the functional and non-functional requirements with targets, and what you would leave out.

Compare with our answer

The questions that matter most: Ranked by what: global popularity, or personalised? How many suggestions? How quickly must a new trend appear? Do we need spelling correction? Which languages? Then agree the list below.

A strong answer mentions: top 10 completions by popularity · freshness measured in an hour, not seconds · filtering offensive suggestions · a latency target the user feels (under ~100 ms) · failing open when the service is down · personalisation and typo correction out of scope (or a follow-up).

Functional: what it must do

  • Suggest completions for a prefix: Top 10, ordered by popularity
  • Update with trends: New popular queries appear within ~1 hour
  • Filter: Remove offensive or dangerous suggestions
  • Works for every keystroke: Including very short prefixes

Out of scope

Spelling correctionPersonalised suggestionsSearch results

Non-functional: how well it must work

QualityTargetWhy
Latency< 100 ms as the user sees it (p99); < 10 ms on the serverSlower than typing feels broken
Availability99.99%But failing open (no suggestions) is acceptable
FreshnessHours, not secondsPopularity changes slowly
Scale~140 K suggestion requests/s on average, 2–3× at peak

2. Back-of-the-envelope estimates

Your turn: the numbers

Assume 200 M daily users, 10 searches each a day, and 6 suggestion requests per search after debouncing. There are 100 M distinct queries worth keeping, averaging 25 bytes. Work out requests per second and roughly how much memory a structure holding all queries and their top-10 lists needs. Then split a 100 ms budget between the network and the server.

Compare with our answer
  • Requests: 200 M × 10 × 6 = 12 B a day ÷ 86,400 ≈ 140 K/s, 300–400 K/s at peak.
  • Searches logged: 200 M × 10 = 2 B a day, the input to the offline pipeline.
  • Trie: a compressed trie has at most about 2 nodes per query; each node stores 10 query ids plus child pointers, ~75 bytes. 100 M × (25 + 2 × 75) ≈ 18 GB: fits in one server's memory.
  • Latency budget: see the table below. The server's share is under 10 ms.

A strong answer mentions: requests/s with a peak factor · a memory size that fits one machine, so replicate rather than shard at first · the logging volume · splitting the latency budget so the server's slice is tiny.

Assumptions: daily active users 200 M; searches per user per day 10; keystrokes per search (after debouncing) 6; distinct queries kept 100 M; average query length (bytes) 25.

NumberEstimateWhy it matters
Suggestion requests per second139 K / s≈ 140,000/s average: serve from memory, close to the user.
Searches logged per day2 BInput to the offline popularity pipeline.
Trie size (compressed, top-10 ids per node)17.5 GB≈ 18 GB: fits in one server’s RAM; replicate it, and shard by prefix when it outgrows a machine.
  • Debounce on the client (wait ~100 ms between keystrokes) and cache recent prefixes to cut requests.
  • The trie is rebuilt offline and loaded read-only: no locking on the read path.

The numbers say: replicate, don't shard (yet). An 18 GB read-only structure copied to dozens of stateless servers serves 140 K/s easily, since one server walking an in-memory trie handles tens of thousands of lookups a second.

Here is a typical latency budget, measured from the keystroke to the suggestions appearing:

StepTimeNotes
Debounce wait0 (not counted)The browser waits ~100 ms after a keystroke before sending; it's a deliberate pause
Network to an edge (CDN)10–40 ms round tripDepends on the user's connection; mobile is worse
Edge cache hit~1 msPopular prefixes stop here
Edge → origin on a miss10–60 msSame continent
Suggestion server1–5 msWalk the trie, return a list
Render in the browser~5 ms
Total~30–100 msLeaves almost nothing for the server to waste

3. API

Your turn: the API

What does the browser call, and how do you make the response cacheable by a CDN?

Compare with our answer

A strong answer mentions: a single GET with the prefix and locale in the URL (no cookies, no user id), so it can be cached by prefix · a Cache-Control max-age of minutes · a tiny JSON response · normalising the prefix (lowercase, trim) so How and how share a cache entry.

CallRequestResponseNotes
GET /v1/suggest?q=how%20to%20b&lang=en–{ suggestions: ["how to boil eggs", …] }Cacheable for minutes by prefix; tiny response

Keep the request anonymous and deterministic: the same q and lang always give the same answer for the next few minutes. That is what lets browsers and the CDN cache it. Personalisation, if added later, should be a separate small call merged on the client, so it doesn't destroy the cache hit rate.

4. Data model

Your turn: the stores

What is written on every search, what is computed offline, and what does a suggestion server load into memory?

Compare with our answer

A strong answer mentions: an append-only query log (sampled) · aggregated counts per query and locale with time decay · a versioned trie snapshot in object storage · a blocklist applied at build time · no database on the request path at all.

query log Event stream → data lake

  • query, ts, locale, region

Every completed search is logged (sampled) for counting.

query counts Batch / streaming aggregation (Spark / Flink)

  • query, locale → weighted_count

Counts per query over a sliding window, with recent searches weighted more.

trie snapshot Serialised file in object storage

  • node(prefix) → children, top10[(query, score)]

Built offline, versioned, loaded by every suggestion server.

blocklist Small curated list

  • pattern, reason

Removes offensive or dangerous suggestions before the trie is built.

The point of this model: the online path reads nothing but memory. The query log and counts live in a data pipeline (Kafka into a data lake, then Spark or Flink), and the only thing that crosses into the serving world is a snapshot: a single file, built and validated offline, that servers download and swap in.

Sampling means logging, say, 1 in 10 searches instead of all of them. Popular queries still show up thousands of times, so the ranking barely changes, and the pipeline is 10× cheaper. The cost: rare queries may never cross the threshold for being suggested, which is usually fine.

5. High-level design

Your turn: draw it

Sketch two halves: the online path from a keystroke to the suggestions, and the offline path from a completed search to a new snapshot on every server.

Compare with our answer

Compare with the figure. The pieces people most often forget: client-side debouncing and caching, the edge cache, and the atomic swap of a new snapshot (servers never edit the live structure).

The online and offline halves, then one keystroke traced through them

  1. Two halves. The online path is tiny and fast: browser caches, an edge cache, and stateless suggestion servers walking an in-memory trie. The offline path logs searches, aggregates popularity, filters, builds a new trie every hour, and ships it to the servers.
  2. As the user types, the browser waits a moment between keystrokes and checks its own cache. Then it asks the suggestion service, often answered by an edge cache. The service walks down the in-memory trie to the prefix node, which already stores its top ten, and returns them.
ComponentWhat it does
Client logicDebounce keystrokes; cache prefixes locally
Edge cachePopular prefixes cached for minutes
Suggest serviceStateless; walks the in-memory trie
TrieEach node stores its top-10 completions
Query log + aggregatorCounts searches with recency weighting
Trie builderFilters, builds, versions and ships snapshots
BlocklistRemoves harmful suggestions

Trace the online path:

  1. The user types how to b. The browser waits ~100 ms for more keystrokes (debouncing), then checks its own cache of recent prefixes.
  2. On a miss, it calls GET /v1/suggest?q=how%20to%20b&lang=en. The CDN answers if another user asked for this prefix in the last few minutes.
  3. On a CDN miss, a stateless suggestion server walks its in-memory trie to the node for how to b.
  4. That node already holds its top 10. The server returns them; nothing is sorted at request time.

6. Deep dives

Your turn: the hard parts

Two or three sentences each: which data structure finds completions for a prefix fast? How do you return the top 10 for "a" without looking at millions of queries? How do new trends appear? What do you do when the structure outgrows one machine?

Compare with our answer

A strong answer mentions:

  • A trie (or a prefix → list key-value table), with the comparison between them.
  • Top-k precomputed per node offline, trading memory and build time for constant-time reads.
  • Hourly rebuilds from time-decayed counts with an atomic swap, plus a small streaming overlay for breaking trends.
  • Sharding by locale and by prefix range balanced by traffic, with replicas per shard.

Data structure: a trie, or a prefix table

A trie (prefix tree) stores strings one character per level, so each node is a prefix, and finding the node for how to b takes 8 steps no matter how many queries exist. A radix tree (compressed trie) merges chains of single-child nodes into one node, cutting memory several times.

Walking a trie, and why each node stores its own top k

OptionHowGood atCatch
SQL LIKE 'how to b%' ORDER BY count LIMIT 10Index range scan, then sort by countSimple; fine for a small siteSorts every match on every keystroke; short prefixes match millions
Trie with top-k per node (chosen)In-memory tree built offlineCompact (~18 GB here); lookups in microsecondsCustom code; one machine's RAM per shard; rebuilt, not edited
Prefix table in a key-value storeKey = every prefix up to ~20 chars, value = its top 10Any KV store (Redis, Cassandra, DynamoDB); no custom treeMany more keys (often ~1 B prefixes, ~100 GB); a network hop per lookup

The prefix table is a fair alternative and some interviewers prefer it: it's just a precomputed trie flattened into keys. It costs more memory (each prefix stores its own key and list, with nothing shared) and adds a network round trip (0.2–0.5 ms to Redis), but it scales by adding KV nodes and needs no custom server. Either way, the key idea is the same: the top 10 are stored, not computed.

Top-k per node: pay at build time

For the prefix a, millions of queries match. Traversing them and sorting on every request is hopeless. So the builder computes, bottom-up, the top 10 for every node: each node's list is the best 10 from its own query (if it is one) and its children's lists. Requests become "walk to the node, return its list".

Store query ids (4–8 bytes) in each list, not strings, with the strings held once in a separate table; that keeps the lists small. Limit very deep nodes too: few people type 40 characters before picking a suggestion, so many builders stop storing lists below a certain depth.

How the builder computes every list

The build is a batch job (Spark or MapReduce) over the scored queries. For each query, emit one record per prefix: "how to boil eggs" with score 9,100 emits ("h", …), ("ho", …), up to the depth limit. Group by prefix and keep the best 10 per prefix with a small heap (a min-heap of size 10: a new candidate replaces the smallest only if it's larger). With 100 M queries averaging ~20 stored prefix levels, that's ~2 B emitted records, which a cluster processes in minutes. The output is the prefix table directly; the trie builder then serialises it as a compressed tree.

The offline pipeline: log, aggregate, filter, build and swap

  1. Offline, completed searches flow into a log. An aggregator counts them with recent searches weighted higher. Every hour a builder removes blocked phrases, builds a new trie with the top ten stored at every node, and the servers swap to the new snapshot.

The aggregator scores each query with time decay, so recent searches count more. A common form is an exponential decay with a half-life: a search from 24 hours ago counts half as much as one now (with a 24-hour half-life). Scores are recomputed hourly over the recent window and merged with the decayed long-term totals.

An hourly rebuild means a breaking event ("earthquake in …") takes up to an hour or two to appear. If the requirement is minutes, add a trending overlay: a stream processor (Flink, Kafka Streams) counts queries over the last 5–15 minutes, compares each count with its usual level, and publishes a small list of spiking queries every minute. Suggestion servers merge that small list into the trie's answer at request time. The overlay is tiny (thousands of queries), so merging costs microseconds.

Safety on the fast path

The trending overlay is exactly where abuse and tragedy show up first: coordinated bots pushing a phrase, or offensive completions about a breaking news story. Run the blocklist and a classifier on the overlay as well, require a minimum number of distinct users (not just searches) before a query can trend, and give humans a kill switch that removes a suggestion everywhere within a minute (a small "removed" list that servers check on every response).

Shipping the snapshot to every server

Copying an 18 GB file to a hundred servers (several regions, with peak headroom) every hour is about 1.8 TB of internal traffic an hour, and a bad file on every server at once is an outage. The usual approach:

  • Versioned snapshots in object storage (trie-en-v451), with a manifest pointing at the current version.
  • Validation before release: size within a few percent of the last build, a fixed set of probe queries returning sensible results, no blocked terms present.
  • Staged rollout: a few canary servers load it first; their latency and click-through are compared with the rest before the manifest moves for everyone.
  • Memory headroom for the swap: a server holds the old and new versions together for a moment, so it needs about 2× the snapshot size in RAM, or it memory-maps the file (lets the operating system page it in from disk) so loading costs little extra.
  • Deltas when the full file gets too large: ship only the changed nodes and apply them to a copy, then swap.

Caching: most requests never reach a server

Caching works at three layers, each cheaper than the next:

LayerWhat it holdsEffect
BrowserResponses for prefixes typed this sessionBackspacing and retyping cost nothing
CDN / edgePopular prefixes, max-age of a few minutesShort prefixes (a, ho, how) are a large share of traffic and almost always hit
ServerThe trie itself is in memoryA miss still costs only a few milliseconds

Two client tricks cut traffic further: debouncing (send only after ~100 ms without a keystroke) and prefetching (the response for how can include the top results for how and how t, the likely next prefixes). Together with caching, these often halve the requests that reach the origin.

Sharding when it outgrows one machine

Add languages and the trie outgrows one server. Shard first by locale (one trie per language or market, which is natural since users rarely mix), then by prefix range within a large locale.

7. Bottlenecks, failures and monitoring

Scaling bottlenecks

BottleneckFix
Request volumeEdge and browser caches; many stateless replicas
Trie memoryCompress (radix tree), shard by locale/prefix
Hot prefixes (“a”, “how”)Cached everywhere; trivially cheap with precomputed lists
Build timeDistributed aggregation; incremental builds per shard

When things fail

FailureWhat happens
Suggest service downThe search box still works, just without suggestions (fail open)
Bad trie build (e.g. offensive entries)Versioned snapshots; validate before swap; instant rollback
Aggregation pipeline delayedKeep serving the previous trie

What to monitor

Suggestion latency (p99)Requests per keystrokeCache hit ratioTrie build ageSuggestion click-through rateBlocklist hits

8. Follow-up questions

Your turn: the interviewer pushes

Answer in order. 1) Product wants personalised suggestions (your own recent searches first). What changes, and what happens to caching? 2) A celebrity dies and people search for them within minutes, but suggestions lag for an hour. Fix it. 3) Legal asks you to remove one suggestion from every server within 5 minutes. How?

Compare with our answer

A strong answer mentions:

  1. Keep the global, cacheable call unchanged; add a small per-user history call (or keep history in the browser) and merge on the client, so the global response stays cacheable. Server-side personalisation per request would kill the CDN hit rate.
  2. A streaming trending overlay counting the last few minutes, detecting spikes against a baseline, filtered for safety, merged at request time.
  3. A small removal list pushed to every server (and CDN purges for the affected prefixes), checked on every response; the next full build drops it permanently.
How would you personalise suggestions?

Blend the global top-k with the user’s own recent searches, stored per user and merged at request time.

How do you handle typos?

Fuzzy matching (edit distance) on a separate index, used when the exact prefix has few results.

How do you support many languages?

One trie per locale; normalise accents and case; route by the user’s locale.

Autocomplete on one page
  • Numbers: 140 K req/s average (300–400 K peak); 2 B searches logged a day; trie ~18 GB for 100 M queries.
  • Latency budget: ~100 ms user-visible; server gets < 10 ms; edge cache answers popular prefixes.
  • Structure: trie (radix-compressed) in memory, or a prefix → top-10 table in a KV store.
  • Top-k per node, computed bottom-up offline; store query ids, not strings.
  • Offline pipeline: sampled log → decayed counts → blocklist → build → validate → atomic snapshot swap.
  • Trending overlay: streaming counts over minutes, merged at request time, with safety filters.
  • Caching: browser + CDN (minutes) + debouncing (~100 ms) + prefetching next prefixes.
  • Sharding: locale first, then prefix ranges balanced by traffic; replicate hot shards.
  • Fail open: no suggestions is acceptable; no search box is not.
Mock interviewPractise it as a mock interview: scope, size and the big decisionsOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. Your suggestion service stores counts in Postgres and answers WHERE query LIKE 'a%' ORDER BY count DESC LIMIT 10. Why does it struggle at 140 K requests a second?

2. Why does each trie node store its own top 10 rather than computing it from its subtree?

3. A teammate proposes incrementing counts in the live trie on every search so suggestions are always current. What is the main problem?

4. Product adds "your recent searches first" by reading the user's cookie in the suggestion service. What is the biggest side effect?

5. Suggestions must reflect a breaking news event within 10 minutes, but the trie is rebuilt hourly. What is the most practical fix?

6. You split the English trie into four shards: a–f, g–m, n–s, t–z. What goes wrong?

7. The suggestion cluster goes down during a deploy. What should users see?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.