Design search autocomplete

Question 1

Who is asking, and how often?

Accepted Answer

The search box fires on nearly every keystroke. That single fact — one request per character, not per search — is what sets the scale of everything behind it.

Question 2

What do the keystrokes hit?

Accepted Answer

A gateway is where these are terminated close to the user, and where you can drop a request that a newer keystroke has already superseded.

Question 3

A prefix of two letters matches ten million queries. How do you get the top ten in under 100ms?

Accepted Answer

Not with `LIKE 'ca%'` — that scans. The answer is a prefix structure held in memory, a trie whose nodes already carry their own top ten, so the lookup is a walk down a handful of characters and a read. This is the whole question, and it is a data structure, not a database.

Question 4

How does the system learn what people are searching for?

Accepted Answer

Every search is logged to a stream and counted offline. Doing this on the serving path would put a write behind every keystroke — the logging is asynchronous precisely so the reads stay untouched.

Question 5

Who turns a day of query logs into the thing you serve from?

Accepted Answer

An offline job aggregates the counts and builds the index, then ships it to the serving nodes as a snapshot. Splitting the build from the serve is why a read can be a pointer chase with no locks in it.

Question 6

Where do the aggregated query counts live between builds?

Accepted Answer

The index is derived data and can be thrown away. The counts it is built from cannot — they are the input to every future build.

Question 7

How many suggestion requests a second do you serve?

Accepted Answer

5B searches a day at four keystrokes each is 20B requests, and 20,000,000,000 / 86,400 is about 231,000 a second. It is four times bigger than the search traffic itself, which is the thing most people miss.

Question 8

How out of date are your suggestions, and why is that acceptable?

Accepted Answer

Building the index offline and serving a read-only snapshot is what buys the latency. It costs you freshness — a term that started trending an hour ago is missing — and naming that trade, rather than pretending the index is live, is the answer.

Blueprint — system design