Courses › System Design › Question Breakdowns

Design Typeahead

Tries with cached top-k, offline rebuilds, partitioning and client tricks.

Design typeahead (autocomplete): as a user types into a search box, suggest the most popular queries that start with what they've typed. The feature is small, but the latency budget is tight: suggestions must arrive between keystrokes, so this is a question about precomputation, keeping the read path trivial and getting fresh trends in without slowing it down.

Requirements

Functional

  • As the user types, return the top 10 suggestions that start with the current prefix
  • Suggestions are ranked by popularity (how often the full query is searched)
  • Popularity reflects recent searches and is updated periodically

Out of scope: spelling correction, personalization (we'll cover it as an extension), searching inside the suggestions.

Non-functional

  • Very low latency: suggestions visible within ~100–200ms of a keystroke, end to end
  • Highly available; slightly stale rankings are fine (an hour old is OK)
  • Scale: a large search engine's box, ~3B searches/day

[!TIP] Back-of-the-envelope 3B searches/day is ~35k searches/second. Each search sends a request for most keystrokes, say 6, so the read load is ~200k requests/second, about 600k at peak. What gets stored is small: only queries searched at least ~50 times a week are worth suggesting, perhaps 20M distinct queries. Precomputing the top 10 for every prefix of those queries gives ~150M prefixes × 10 query IDs × 4 bytes ≈ 6 GB, plus ~1 GB of query strings. That fits in RAM on every server.

The idea: answer every prefix ahead of time

A prefix lookup has to return in a couple of milliseconds, so don't search at request time. Compute the answer for every prefix in advance and serve it from a key-value table:

A trie (prefix tree) is the natural way to *build* that table. Each query is a path of characters from the root, and every query sharing a prefix shares the path:

root = service "(root)" @2,0
w = service "w" @2,1
e = service "e" @2,2
a = service "a" @1,3
b = service "b  • web" @3,3
th = service "t-h-e-r  •" @0.5,4
ve = service "v-e  •" @1.5,4
cam = service "c-a-m  •" @2.5,4
inar = service "i-n-a-r  •" @3.5,4
root -> w
w -> e
e -> a, b
a -> th, ve
b -> cam, inar

• marks a node where a complete query ends. Single-child chains (t-h-e-r) are stored as one node (a radix tree).

Deep Dives

1. Building the top-10 lists

Walk the trie post-order. Each terminal node knows its query's score; each node's top 10 is the best 10 among its own query and its children's top-10 lists. That's a merge of small sorted lists, so the whole build is linear in the size of the trie.

The trie lives only in the build job. The serving tier gets the flattened prefix table, which is simpler and faster: one hash lookup per request, no pointer chasing.

2. Scoring and refreshing

user = client "Client" @0,1
lb = service "Load Balancer" @1,1
srv = service "Suggestion Servers\n(prefix table in RAM)" @2,1
logs = queue "Search Events\n(Kafka)" @1,2
batch = service "Daily Build\n(Spark)" @2,2
trend = service "Trend Counter\n(streaming)" @3,2
store = store "Table Snapshots" @3,1
user -> lb
lb -> srv
lb --> logs : searches
logs -> batch
logs -> trend
batch -> store : new table
store --> srv : load
trend --> srv : hot queries
  • Base table, rebuilt daily: a Spark job counts queries over the last ~30 days, scoring each query as a decayed count (yesterday's searches weigh more than last month's), then builds the trie and flattens it. Servers load the new snapshot into a second buffer and flip a pointer, so a reload never pauses traffic.
  • Trending overlay, near real time: a streaming job counts queries over the last ~15 minutes and publishes those growing far faster than their usual rate (news, a match result). Servers merge this short list into the base answer at request time. Without it, a breaking story wouldn't show up until tomorrow's build.
  • Thresholds keep the table clean: a query must be searched by many distinct users before it's eligible. That stops one script from injecting a suggestion, and it keeps private strings someone typed once (names, emails) out of the table.

3. Serving and scaling

At 6–7 GB, the whole table fits in memory, so don't partition it: every suggestion server holds a full copy, and the load balancer can send any request anywhere. Scale by adding replicas: at ~50k requests/second per server, the 600k peak needs about 12, plus spares in each region.

If the table someday outgrows one machine (many languages, per-country tables), split it by market first (one table per language and country), since each request needs only one. Splitting by prefix range is the last resort: some prefixes are vastly hotter than others.

4. Caching

Prefix popularity is extremely skewed: single letters and common two-letter prefixes account for a big share of requests. Give responses a short cache lifetime (a few minutes) so the CDN and the browser absorb repeats. The trending overlay is the reason to keep that lifetime short.

5. The client matters as much as the server

  • Debounce keystrokes by a few tens of milliseconds, and drop stale responses: tag each request with a sequence number and ignore any answer older than one already shown, since responses can arrive out of order.
  • Reuse earlier answers: after a backspace, show the cached list for the shorter prefix immediately.
  • Warm up the connection when the search box gets focus, so the first keystroke doesn't pay for a TLS handshake.

6. Safety and personalization

  • Blocklist at serving time: offensive, dangerous or legally removed suggestions must disappear within minutes, not at the next daily build. Keep a blocklist that every server checks before returning a list, and drop those queries in the next build too.
  • Personalization: blend the user's own recent searches (kept on the device or in a small per-user store) above the global list, and rank by language and region. Because personalized lists can't be shared, don't let the CDN cache them.

What's expected at each level

  • Mid-level: a trie or prefix table, prefix lookup, ranking by frequency.
  • Senior: precomputed top-k per prefix, offline rebuilds with an atomic swap, full replication vs. partitioning from the size estimate, client debounce and out-of-order responses.
  • Staff: time-decayed scoring, a streaming trend overlay, abuse and privacy thresholds, fast removal, personalization without losing cacheability.