Loading…

Understanding the problem

Search autocomplete is the list under a search box that guesses the search you are making. Type “wea” and it offers “weather”, “weather tomorrow” and “weather in london”, most likely first.

Three things make it hard. Every keystroke is a request, so serving must be one cheap lookup. The suggestions must reflect this week’s searches and, when something big happens, the last few minutes. And a list everyone sees has to keep out anything offensive, and anything that reveals what one person searched.

The practice brief states the requirements up front; in an interview, you would confirm them in the first few minutes. The core is the read path: what one keystroke costs, and how its answer stays current and safe.

Functional requirements

CoreAs someone types, show up to 10 suggestions for what they have typed so far, most likely first, in their language (about 20 languages).
CoreSuggestions come from what people search for; what is popular now outweighs what was popular last year.
CoreSigned-in users see up to 3 of their own recent matching searches first.
CoreA small typo in what has been typed still gets useful suggestions.
CoreWhen something big happens, it appears in suggestions within about 5 minutes; normal changes in popularity may take about an hour.
CoreOffensive or unsafe suggestions never appear, and a suggestion removed by the legal or safety team disappears everywhere within about 5 minutes, including copies on devices and at the edge. (A user’s own recent searches, shown only to them, are their history and outside this.)
Below the lineVoice search.
Below the lineCorrecting the spelling of whole queries.
Below the lineAds in suggestions.
Below the lineSuggesting documents, products or people instead of queries.That is search over content, with its own index. Here every suggestion is a query.
Below the lineRich suggestions: an answer, an image or a link in the list.It decorates the same ten entries, and doesn’t change how they are found.

Non-functional requirements

LatencySuggestions appear within about 150 ms p99 of the user pausing, on a typical connection; the suggestion service itself has about 20 ms of that.
AvailabilitySuggestions are available 99.99% of the time; if they fail, typing and searching still work.
AvailabilityUpdating the suggestions never shows users an empty or broken list.
SecurityNothing is ever suggested that could reveal what one particular person searched for.
SecurityA person’s own suggestions are never shown to anyone else.
AvailabilityEach region serves its own users, and keeps serving them if another region is down.
Below the line

Scale

From the briefNumbers here are given in the practice brief.

ScaleAbout a billion searches a day, about 25,000 a second at peak.
ScaleA search is about 18 characters typed.
ScaleAbout 50 million different queries are popular enough to be worth suggesting, across about 20 languages.
ScaleEach logged search is about 200 bytes.
ScaleThree regions; each user is served by the nearest one, and what is popular can differ between regions.

Out of scope

Out of scopeThe search results page.
Out of scopeTraining ranking models.
Out of scopeModerating anything other than suggestions.
Out of scopeManaging search history (a history page, retention settings, deleting it); showing matching recent searches in the suggestions stays in scope.

Check yourself

Correcting whole queries is out of scope, but a small typo in what has been typed is in scope. Why is one cheap and the other not?
Show answerHide answer
A typo in the prefix costs one extra lookup in a table the build prepares. Correcting a whole query needs its own models.

The numbers that shape the design

Illustrative exampleNumbers here are illustrative: round figures to reason with, not measurements.

Work out only the numbers this design depends on, with round figures and one line of working each. The problem here is requests, not data.

Back of the envelope for the Web search brief

Quantity	Value	Working
Searches at peak	About 25,000 a second	From the brief: a billion a day, about 12,000 a second on average.
Requests if every keystroke asked	About 450,000 a second	25,000 searches × about 18 characters typed per search.
Text of the queries worth suggesting	About 1.5 GB	50 million queries × about 30 bytes of text each.
What the servers hold	About 30 GB	About 300 million (language, prefix) entries × about 100 bytes.
Search log	About 200 GB a day	A billion searches × 200 bytes: about 5.6 TB for four weeks.

What the numbers tell you

Requests are the big number, so a keystroke must be one cheap lookup, near the user where possible.
The data the servers answer from is tens of gigabytes, so every server can hold all of it in memory.
The log is big but batch: cheap storage read by a job, off the typing path.

Architecture diagramWhere the load lands

Diagram as text

Components: Searches at peak (User); App (Client); Suggestion servers (Service); Suggestion table (Cache); Search log (Object store). Connections: Searches at peak → App (~25,000 searches/s); App → Suggestion servers (up to ~450,000 requests/s); Suggestion servers → Suggestion table (~30 GB in memory); App → Search log (~200 GB a day).

Try it: The numbers that shape the designGuided practice · Search autocomplete, Web search · Mid-level

Check yourself

Which number decides the serving design, and which is smaller than it looks?
Show answerHide answer
The request rate decides it. The served data sounds huge, but capped prefixes of popular queries come to tens of gigabytes, small enough for memory.

Core entities

Keep the model small. The row that matters most is one submitted search, because everything the ranking knows comes from it. Record submitted searches only, not each keystroke, so half-typed words don’t look like searches, and record who made each one, so the build can count people rather than hits.

Typed and stored text go through the same locale-aware normalisation: Unicode normalisation, the language’s own case rules, width and spaces. Case rules depend on the language (ICU (opens in a new tab)): full Unicode case folding maps “ß” to “ss”, so German “STRASSE” and “straße ” match, and Turkish text uses the Turkic mappings for dotted and dotless i (Unicode (opens in a new tab)). Compatibility normalisation folds halfwidth and fullwidth forms but shouldn’t be applied blindly (Unicode (opens in a new tab)), and accents fold only where the language treats them as the same letter.

The entities and their key fields

Entity	Key fields	Why it exists
SearchEvent	`language`, normalised query, user or device id, region, time, typed or picked	One per submitted search: what the build counts.
QueryText	`query_id`, `language`, the text as shown	Each query’s text, stored once.
Suggestion entry	(`language`, normalised prefix) → ten (`query_id`, weight) pairs	What the servers hold; the build writes a new version each hour.
Misspelling alias	(`language`, misspelled prefix) → the right prefix’s list	The typo fallback, read only when too few suggestions match.
Removal entry	Normalised query, `language`, variants, reason, who and when	Applied to every answer, and read by every build.

Where each part lives

Part	Store	Why
Submitted searches	Kafka, copied hourly to object storage	A billion appends a day, read in bulk by the build.
Suggestion table	Each server’s memory	Read on every request, so it has to answer in microseconds.
Removal list	A small durable store, pushed to every server	Audited, and it has to reach every server within seconds.

Architecture diagramWhat is recorded, and what is served

Read:Learn: Data model design Learn: Storage choice justification

Try it: Searches and languagesGuided practice · Search autocomplete, Web search · Mid-level

Keep reading+1 min

Small typos, in one extra lookup

When fewer than three suggestions match what has been typed, the server makes one more lookup, in a misspelling table the build derives from popular queries (“weaht” to “weath”). It keeps an alias only where one right prefix clearly wins, so a typo costs one extra lookup at most, not a fuzzy search on every keystroke. Correcting whole queries is a different system, and out of scope here.

Accents, per language

Folding accents everywhere merges different words: in Spanish or Vietnamese an accent can change the word. Keep accent-insensitive aliases per language, only where the language treats the accented and plain letters as the same, and test normalisation rules per language like any other code.

High-level design

Build the design one flow at a time, following the brief: a keystroke, a submitted search, and a search many people made this week. The deep dives then harden it.

A keystroke becomes suggestions

Each server holds, in memory, the ten best completions for every (language, prefix) of the queries worth suggesting, built ahead of time by the hourly job. A trie whose nodes carry their best list works the same way, and so does a prefix table in a sharded key-value store. Nothing is searched, sorted or counted while the user types, so “s” costs the same as “weathe”.

The trap is the obvious query: WHERE query LIKE 'wea%' ORDER BY hits DESC LIMIT 10. The index finds the matching rows, but for “s” that is millions of rows to sort on every keystroke. Walking every query under a trie node costs the same, in memory.

The app calls GET /v1/suggest?q=wea&lang=en on its nearest region’s host.
The CDN answers if it has this prefix; otherwise any suggestion server does.
The server makes one lookup of (en, “wea”) in its table and returns the ten entries with their texts.
The app shows them if they still match the box.

Architecture diagramA keystroke is one lookup

Any server answers from the table in its own memory, with nothing searched or sorted.

Diagram as text

Components: App (Client); Load balancer (Load balancer); Suggestion server (Service); In-memory table (Cache). Connections: App → Load balancer (q=wea, lang=en); Load balancer → Suggestion server (any server); Suggestion server → In-memory table (one lookup: (en, “wea”)).

Read:Learn: Read-heavy Learn: Indexes and search fundamentals

Try it: From a search to a suggestionGuided practice · Search autocomplete, Web search · Mid-level

Check yourself

Why does the prefix “s” cost the same as “weathe”?
Show answerHide answer
Both are one lookup of a list built ahead of time; the sorting happened in the build.

A submitted search is recorded

The search service appends a SearchEvent to Kafka and waits only until the replicated log has accepted it: with acks=all, an acknowledged record isn’t lost while at least one in-sync replica stays alive (Kafka docs (opens in a new tab)). The suggestion path writes nothing, so a slow log can’t slow typing. An hourly job copies the events to object storage for the build.

The user submits a search, and the app calls POST /v1/searches.
The search service appends a SearchEvent and returns 202 once the log has it.
A copy job batches the events into object storage every hour.

Architecture diagramRecording a search doesn’t slow typing

This week’s searches reach the suggestions

Illustrative exampleNumbers here are illustrative: round figures to reason with, not measurements.

Every hour a Spark job reads the recent events, ranks each language’s queries, and for every prefix of the popular ones writes out the ten best as a new version in object storage. The servers load it into memory; going live safely is the second deep dive.

Keep entries only for prefixes of the queries popular enough to suggest, and only up to about 20 characters, so the long tail of rare queries is never expanded into billions of prefixes. That is about 300 million entries of ten ids and weights, some 30 GB.

The build reads the recent weeks of events and counts people per query per day.
It leaves out removed queries, and writes the ten best for every prefix of the popular ones.
It publishes the new version, and the servers load it.

Architecture diagramThis week’s searches reach the suggestions

Call	Request	Response	Caching
`GET /v1/suggest`, on the region’s host	`q` (the prefix), `lang`	`200` with the normalised `prefix`, up to ten `suggestions` and the `version`	Public for a minute, no cookies; keyed on region, language and prefix
`GET /v1/me/recent-searches`	None: the signed-in user	`200` with recent searches; `401` if signed out	Private: no shared cache stores it
`POST /v1/searches`	`q`, `lang`, the picked suggestion if any	`202`	Not cached

Design search autocomplete

The answer in two minutes

Also asked as

What interviewers look for

The decisions that matter

Understanding the problem

Functional requirements

Non-functional requirements

Scale

Out of scope

The numbers that shape the design

Core entities

Small typos, in one extra lookup

Accents, per language

The API

High-level design

A keystroke becomes suggestions

A submitted search is recorded

This week’s searches reach the suggestions

Sign in with Google to read the rest

Practise this

A trie, a table or a key-value store

The answer in two minutes

Also asked as

What interviewers look for

The decisions that matter

01Understanding the problem

Functional requirements

Non-functional requirements

Scale

Out of scope

02The numbers that shape the design

03Core entities

Small typos, in one extra lookup

Accents, per language

04The API

05High-level design

A keystroke becomes suggestions

A submitted search is recorded

This week’s searches reach the suggestions

Sign in with Google to read the rest

12Practise this

A trie, a table or a key-value store

Understanding the problem

The numbers that shape the design

Core entities

The API

High-level design

Practise this