Autocomplete

01 · CONTEXT

One suggestion per keystroke

Search autocomplete returns suggestions while the person types, which means a query on every keystroke. A system design interview guide on the topic states that the system must return suggestions in under one hundred milliseconds per keystroke, for hundreds of millions of users. Whoever designs the system therefore starts from a tight latency budget and a read volume far greater than the write volume. To understand what fits in that budget, it helps to separate the read path, which serves the person typing, from the update path, which decides what will be suggested.

1. Each keystroke generates a query with the typed prefix, which reaches the suggestion service through the load balancer.

2. The service computes nothing: it queries an in-memory structure that already holds the ready-made suggestions.

02 · TRIE AND TOP-K

Ready-made answers at every node

The central structure is a trie, in which each path from the root represents a prefix. The idea the guide highlights is to store at each node the best suggestions for that prefix, computed and stored ahead of time. With that, finding the prefix's node and returning the ready list costs a single lookup proportional to the length of the prefix, instead of walking the entire subtree below it. It is an example of search systems in which the expensive work is shifted from read time to build time.

1. The service sends the prefix to the trie server responsible for it.

2. The server locates the prefix's node and returns the list of suggestions it already holds, without walking the subtree.

03 · COLLECTION AND UPDATE

The pipeline that feeds the trie

Suggestions come from what people actually search for. In the design described by the guide, every search is recorded in a distributed log, and a streaming job aggregates the counts of each query in one-hour windows. Also every hour, a builder job rereads the frequency table and rebuilds the affected trie nodes. The new version goes live through a blue-green switch, in which all traffic moves at once to the new trie, with no downtime. This is a typical use of data pipelines, in which the write path is asynchronous and completely separate from the read path. The one-hour cadence is the guide's.

1. Every search served is recorded in a distributed log, outside the response path to the user.

2. An aggregator consumes the log and accumulates each query's count in the frequency table.

3. Periodically, the builder rereads the frequencies and assembles the trie with ready-made suggestions at every node.

4. The new version replaces the previous one on the trie servers all at once, without taking them offline.

04 · FRESHNESS

Queries that explode between rebuilds

A periodic rebuild leaves a gap: a query that suddenly spikes, like a breaking event, would only enter the suggestions in the next round. The guide proposes a separate component that tracks recent spikes and injects them into the suggestions without rebuilding the whole trie. The cost of this solution is a second source of results, which must be combined with the trie's at response time.

1. A detector tracks recent searches and stores the queries that are spiking in a fast store.

2. The service queries the trie and the spikes and combines the two results before responding.

05 · SCALE

Partitioning the trie and saving requests

When the trie does not fit on a single server, it has to be split. The guide suggests partitioning by the first characters of the prefix, so that each slice holds a range of prefixes. On the client, the guide recommends a debounce: only send the query when the person pauses typing for a short interval, which reduces requests to the server. Both are ways to scale horizontally the system: one divides the data across servers, the other reduces the load that reaches them.