Data & analytics
Search autocomplete - an answer before the word is finished
Why suggestions come from a precomputed prefix index, and why freshness is traded for speed on every keystroke.
What this board gets wrong on purpose
The tension
Every suggestion comes from an index built once an hour from yesterday's and today's counts, so a query that starts trending now - breaking news, a product launch - is invisible for up to an hour plus the CDN TTL, and there is no fast trending layer to fill the gap. The top ten per prefix is fixed at build time, so short prefixes are owned forever by the same head queries and the long tail never surfaces. And the blocklist is applied at build time only: an offensive suggestion found at 10:05 stays live until the 11:00 build unless someone hot-patches every node.
Practise this as an interview
Take Search autocomplete - an answer before the word is finished as a timed system design interview on a blank board - on your own, with the requirements to check yourself against, or with a candidate you invite.
Start here
Why this design
Autocomplete is the search box finishing your sentence. It feels like a small feature and it is one of the highest-traffic endpoints a search product has, because it fires on keystrokes rather than on searches - several requests for every query anybody types. The interview question is really about one decision: what do you compute per keystroke, and what do you compute in advance? The answer on this board is "nothing" and "everything".
What you will learn
- Why 500M searches a day become ~3 billion suggestion requests, and why the client debounce is part of the capacity plan.
- How a precomputed prefix -> top-10 table turns each keystroke into one in-memory lookup.
- Why the whole index fits in memory on every serving node (~12 GB), so there is no shard to call.
- How ranking is decided offline from counted, time-decayed, filtered query logs.
- What freshness you give up, and the usual fix: a small real-time trending layer merged on top.
How to read this board
- Top: ONE KEYSTROKE. User, search box, CDN edge, the suggest service hex and its in-memory prefix index.
- Right: SHARED STORES. Query counts and the versioned index snapshots the serving nodes load.
- Bottom: OFFLINE PIPELINE. Finished searches flow into a log, get counted hourly, and a builder writes a new index.
- Press play for the walkthrough, then read pages 1 to 6, then the tables.
- The conversation to have is the red builder: everything a user sees is at most as fresh as its last run.
1 · Requirements
Functional
- As the user types, show up to 10 completions of the current prefix, best first.
- Rank by popularity, with recent searches weighted more than old ones.
- Never suggest blocked terms (abuse, slurs, legal takedowns).
- Work from the first character; accept lower case, trimmed, accent-folded input.
- Selecting a suggestion runs the full search.
Non-functional
- Server p99 under 20 ms; perceived end-to-end under ~100 ms, or suggestions arrive after the user has typed past them.
- Availability 99.95 percent, and failure is silent: no suggestions is acceptable, an error box is not.
- Freshness: a new popular query appears within about an hour.
- Suggestions are the same for everyone with the same prefix and language - which is what makes them cacheable.
Out of scope
- Personalised suggestions (your own history) - a small per-user list merged on the client.
- Spelling correction and fuzzy matching ("pyhton" -> python).
- Full search ranking; this board only feeds the box.
The rest of this board
Available on Tier Slate
This page publishes the question. The answer — 5 more written pages, an 8-step narrated walkthrough and a 4-table schema — is the board itself, and it opens in Tierslate.
- 5written pages
- 8walkthrough steps
- 4tables18 columns
5 pages behind this one
- Capacity estimation
- Storage estimation
- Availability
- How it works
- Deployment plan
More boards
Pipelines, metrics and the lag between event and answer.
- Ad serving - an auction inside a page load
- Analytics pipeline - the lag between an event and the answer
- Log aggregation - the index is bigger than the data
- Metrics and monitoring - cardinality is the thing that kills you
- Recommendation engine - retrieve a thousand, rank twenty
- Leaderboard - a sorted set and the rank nobody stores
- View counter - counting a million clicks without a million writes
- Uptime monitor and status page - checking from outside
- A/B testing platform - assignment is the easy half
- ETL and the data warehouse - yesterday, correctly
- Full-text search - the inverted index and the shard that is slow