Typeahead
Typeahead suggests completions while you type, so it must answer a request per keystroke in well under 100 ms. The core decision is to move all the work offline: a batch pipeline counts queries from logs and builds a prefix index (a trie or equivalent) in which every node already stores its top k completions. Serving is then a walk of O(prefix length) plus a read of k items, from memory, on a shard chosen by prefix. Freshness comes from a small streaming “trending” overlay; request volume is cut by client debouncing and edge caching of short prefixes.
The problem
Section titled “The problem”Google, Amazon, YouTube and every app with a search box do it: type wea and see weather, weather tomorrow, weather radar. Suggestions save typing, steer people toward queries that return good results, and spread load away from rare misspellings.
The goals conflict:
| Goal | What it means | Pulls toward |
|---|---|---|
| Instant | Suggestions appear while typing, ~100 ms per keystroke including the network | In-memory, precomputed answers |
| Relevant | The likely completion for this user, language and region | More signals per request (slower) |
| Fresh | A query trending in the last hour shows up | Online updates (hard to do in a precomputed index) |
| Safe | Never suggest offensive, defamatory or dangerous completions | Filtering, review, removal pipeline |
| Cheap | 5-10 requests per search, billions of searches a day | Debouncing, caching, fewer servers |
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Given a prefix, return up to 10 completions ranked by popularity. Per language/region. | Personalised (your own recent searches)? Spelling correction (“wether” → weather)? Mid-word matching? |
| Scale | 5B searches/day, ~6 suggest requests per search, 100M distinct queries worth indexing. | How many locales? How skewed are prefixes? |
| Latency | p99 under ~50 ms server-side, so the round trip stays under ~100 ms. | Mobile networks? Then edge serving matters most. |
| Freshness | Popularity refreshed daily; trending within minutes. | How quickly must a news event appear? |
| Consistency | None needed. Two users may see slightly different lists. | |
| Out of scope | The search results page, ads, the ranking of results. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. Two numbers decide the design: requests reaching the servers (after debounce and edge cache), and index memory, which decides how many shards you need.
What to say out loud: “About 700K requests a second at peak, most for short prefixes that cache well, so maybe 300K/s reach the index. The index is ~100 GB with top-k lists, which I’d shard by prefix range and replicate for throughput. Each lookup is a memory walk, so latency is network-bound.”
API and data model
Section titled “API and data model”GET /suggest?q=wea&lang=en®ion=US&k=10 (q normalised: lowercase, trimmed, collapsed spaces) -> 200 { q: "wea", suggestions: [ { text: "weather", score }, ... ] } Cache-Control: public, max-age=300 -- for anonymous requests; personalised ones are private
offline input: QueryLog { query, ts, lang, region, user_id? } -- submitted searches onlyoffline output: Snapshot per (shard, version): prefix index + query table query table id -> { text, score } index node prefix -> [ query ids of its top k ] -- the precomputed answerTwo decisions hide in that sketch:
- Log submissions, not keystrokes. A keystroke is a guess; a submitted query is what people want. Counting keystrokes would make suggestions recommend themselves.
- Store ids, not strings, in the top-k lists. A popular query appears in the list of every one of its prefixes, perhaps 20 copies. Storing a 4-byte id instead of the text makes those copies cheap.
High-level design
Section titled “High-level design”Two separate systems: an offline pipeline that builds the index, and an online path that only reads it. Step through each.
| Component | Role | Why it’s there |
|---|---|---|
| Client | Debounces keystrokes, cancels stale requests, caches recent answers. | Cuts requests 2-3× and hides network jitter. |
| Edge cache / CDN | Caches responses for popular prefixes by (q, lang, region). |
Short prefixes are few and very hot. |
| Suggest API | Routes to a shard, merges the trending overlay and personal history, applies filters. | Keeps shards simple: they only do lookups. |
| Trie shards | Hold the prefix index in memory, sharded by prefix range, replicated. | The index is too big for one box, and reads need replicas. |
| Aggregator + builder | Daily batch: count, decay, threshold, build top-k per node, write snapshots. | All expensive work happens here, off the request path. |
| Trend counter | Streaming counts over the last hour; flags spikes. | Freshness without rebuilding the big index. |
Deep dive: the prefix index
Section titled “Deep dive: the prefix index”Type a prefix below. In stored top-k mode, each node on the path shows the list it holds. Switch to scan subtree and watch the cost jump, especially for one-letter prefixes. Then press +300 on a suggestion and see how many stored lists that one change touches.
The trie concept page covers the structure itself. For serving at scale, what matters is the cost table:
| Approach | Lookup | Memory | Update one count |
|---|---|---|---|
| Trie, scan subtree on each request | O(p + subtree size + m log k) | O(total characters) | O(length) |
| Trie, top-k stored at every node | O(p + k) | O(nodes × k) | O(length × k): every ancestor’s list |
| Sorted array of queries + prefix range | O(log n) to find the range, then top-k over it | O(n) | O(n) insert |
| Finite-state transducer (Lucene / Elasticsearch completion) | O(p + k) with weights | Very compact; shares prefixes and suffixes | Rebuild |
(p = prefix length, n = queries, m = matches under the prefix.)
The sorted-array option deserves a sentence in the interview: sort all queries, and the completions of any prefix are a contiguous range [p, p + ""), found by two binary searches. Getting the top k by score out of that range needs a range-maximum structure (a segment tree or sparse table) or precomputed answers for short prefixes. It is compact and easy to shard by range; tries win on simplicity of the top-k lookup.
The update column is why the index is rebuilt rather than mutated. One search for a popular query would rewrite up to length lists of size k, under concurrent reads. Batching all counts into a daily build, then swapping an immutable snapshot, keeps serving lock-free.
Deep dive: the offline pipeline and freshness
Section titled “Deep dive: the offline pipeline and freshness”counts = QueryLog over the last 30 days map each search -> (normalise(query), lang, region), weight = decay(age_days) -- e.g. 0.9 ^ age reduce sum weights per (query, lang, region) filter score >= MIN_SCORE and distinct_users >= MIN_USERS -- drops noise and private queries filter not on the policy blocklist
for each (lang, region): split queries into shard ranges by cumulative traffic, not alphabet -- "s" is busier than "x" for each shard: build the prefix index bottom-up, keeping the best k ids at each node write snapshot (shard, version) to blob storage
serving nodes: load the new version beside the old one, health-check it, flip a pointerPoints worth saying:
- Decay, not a fixed window. Weighting by age keeps last week ahead of last year, so suggestions drift with taste without a hard cliff.
- Minimum counts are a privacy control. A query typed by one person (a name, an address) must never be suggested to others. Requiring many distinct users before a query is eligible is the standard defence.
- Trending is an overlay. A streaming job (see streaming) counts queries in 5-minute buckets and compares them with their baseline. Spiking queries go into a small table pushed to API nodes every minute, merged with the trie’s answer at request time. A bucketed sliding window count is the building block.
- Personalisation is another overlay. The user’s own recent searches come from a small per-user store and are mixed in by the API for signed-in users. The shared index stays the same for everyone, so it stays cacheable.
Deep dive: the keystroke budget
Section titled “Deep dive: the keystroke budget”Every keystroke could be a request, and every response races the next keystroke. Pick a sending strategy, then make latency slower and more jittery than the typing speed.
What it shows:
- Debounce (send after D ms of quiet) cuts requests most, at the cost of D ms after the last key. Throttle (at most one per D ms, plus the last) keeps suggestions moving while typing. 100-150 ms is a common D.
- Out-of-order responses are normal. Without a guard, the answer for
weacan arrive after the answer forweathand overwrite it. Tag each request with an increasing id and drop any response older than what’s on screen (or cancel in-flight requests).
on keystroke(text): schedule send(text) after DEBOUNCE ms, replacing any pending send -- debouncesend(text): if cache has text: show(cache[text]); return -- backspace is free my_id <- ++latest_id request(text) then on response(r): cache[text] <- r if my_id == latest_id: show(r) -- older answers are ignoredThe latency budget then looks like this for a ~100 ms target:
| Step | Typical | How to shrink it |
|---|---|---|
| Debounce wait | 0-150 ms (after the last key) | Tune D; throttle instead |
| Network round trip | 20-80 ms | Edge PoPs; HTTP/2 or HTTP/3 connection reuse |
| Edge cache hit | ~1 ms | Cache short prefixes; tie the TTL to the snapshot version |
| API + shard lookup | 2-10 ms | In-memory index, no fan-out to more than one shard |
| Rendering | a few ms | Keep the payload tiny: 10 strings |
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Shard down | Prefixes in its range get errors | Replicas per shard; the client shows nothing rather than an error (suggestions are optional) |
| Bad snapshot (bug, bad data) | Wrong or empty suggestions everywhere | Validate before swap (size, sample queries, diff against previous); keep the old version for instant rollback |
| Hot prefix (breaking news) | One shard’s replicas saturated | Edge cache with short TTL; more replicas for hot ranges; precompute 1-2 char prefixes fully |
| Offensive or manipulated suggestions | Brand and legal risk | Blocklists in build and at serving time; spike detection on trending; fast manual removal list pushed to API nodes |
| Pipeline fails for days | Stale suggestions | Keep serving the last good snapshot; trending overlay still adds fresh items |
| Request flood from clients | QPS spikes, cost | Debounce and throttle in the client, edge caching, per-client rate limits |
| Stale responses on slow networks | Suggestions flicker or go backwards | Request ids on the client; drop older answers |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
| Lookup (top-k stored) | O(p + k), microseconds in memory | — |
| Lookup (scan subtree) | O(p + subtree), unbounded for short prefixes | — |
| Index size | — | O(nodes × k) ids: ≈ up to 140 GB for 100M queries, k = 10 |
| Daily build | O(log events) to count + O(total characters × k) to build | Snapshots per version |
| Trending overlay update | O(1) per log event; push every minute | Thousands of entries |
| Requests | ≈ searches × requests per search; 2-3× fewer with debouncing | — |
| Edge cache | O(1) | Small: a few million (prefix, locale) keys cover most traffic |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Freshness, personalisation, locales, k, latency target, safety.
- Estimate (5 min). Requests per second after debounce, index memory, shard count.
- Data structure (10 min). Trie, then the problem with scanning, then top-k stored per node; mention sorted ranges or FSTs as alternatives. State O(p + k).
- Offline pipeline (10 min). Logs → counts with decay and thresholds → build → versioned snapshot → atomic swap.
- Serving at scale (10 min). Shard by prefix range balanced by traffic, replicas, edge cache for short prefixes, client debounce and stale guards.
- Extensions (5 min). Trending overlay, personal history, filtering and removals, spelling tolerance.
Follow-ups to expect: “Support typos?” Generate candidates within edit distance 1 for short prefixes at build time, or use a fuzzy automaton at query time on a smaller index. “Mid-word matching (‘radar’ → ‘weather radar’)?” Index each word suffix of a query too, pointing to the same query id. “Make it real-time?” Keep the daily snapshot and push a small, frequently rebuilt delta, rather than mutating the big index.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Facebook Engineering: The life of a typeahead query: browser-side caching, a global index and a per-user index merged per keystroke.
- Google: How Google autocomplete works in Search: predictions from real searches, trending queries, language and location, and the removal policies.
- Elasticsearch: completion suggester: a production prefix suggester whose data structure is built at index time and held in memory.
Concept pages to drill: Tries · Heaps · Binary search · Data aggregation · Streaming · Caching