Design Google search autocomplete

Start typing "distr" into a search box and a list drops down: distributed systems, distributed lock, and a few more. That list is autocomplete (also called typeahead). It looks small. But every letter you type can be a new request, and each answer has to come back before your finger reaches the next key. Nobody clicks a suggestion that shows up after they finished typing.

Watch one keystroke go through the system, and then watch how the suggestions get made.

That gives you about fifty milliseconds per answer, and far more requests than there are searches. The surprise is that this is not a search problem at all. It is a precomputation problem: work out the answers in advance, so that answering is only a lookup. Once you see that, the whole design falls out.

A few words come up all through this page:

• A prefix is the start of a word. "dis", "dist" and "distr" are all prefixes of "distributed".
• Top five (written top-k in general) means the five most searched terms that start with a prefix.
• A trie (said "try") is a tree of letters. Each step down adds one letter, so the path d, i, s, t, r leads to the node for "distr". You will build one by hand in the deep dive.
• p99 means 99 out of 100 requests are at least this fast. "50ms at p99" allows only one request in a hundred to be slower than 50ms.

Step 1: Understand the problem#

The trap here is designing a search engine. Ask enough questions to establish that you are not. Six questions do it, and the third one is the one most people forget.

What you are building, and what you cut#

Back of the envelope#

Three inputs. The first row is the one that surprises people. (New to this kind of estimate? The back of the envelope chapter walks through the method.)

Step 2: Propose the high level design#

The API#

One endpoint does the real work, and every design decision is in the headers. Two words first. A CDN is a network of cache servers spread across cities, so an answer can come from a machine near you instead of from the data centre. A TTL (time to live) is how long a cached answer may be reused before it must be fetched again. Both are covered in caching patterns.

{ "query": "distributed systems", "at": "...", "lang": "en" }

The data model#

The build side and the serve side store completely different things, which is the whole trick. The serve side is a trie held in memory. Here is a small piece of one:

root
 └ d
    └ i
       └ s ── top 5 here: distributed systems, discord, disney plus, ...
          └ t
             └ r ── top 5 here: distributed systems, distributed lock, district map

Every node stores its own short list of best answers. That list is the column called top_k below. The trie is split into shards (slices kept on different machines) by prefix range, so all prefixes starting with "d" live together. The sharding chapter compares range sharding with the other options.

The whole system on one whiteboard#

Figure 1 is the picture at the top of the page, with the two exceptions added. Walking it:

1. The client debounces, then asks. A large share of these never reach you at all, because the answer for a prefix is the same for every user, so the CDN can keep it. (The what happens when you type a URL article shows how much time a nearby cache saves.)
2. The gateway is stateless: it keeps no data of its own, so you can add more copies at any time. It sends the prefix to the shard holding that part of the trie, which walks to the node and reads the five strings sitting there. No ranking, no searching, no sorting. This is the entire busy path, and it is a memory read.
3. Separately, when someone actually searches, the client logs what they searched.
4. Those events flow into an aggregator. The log is an event stream: an append only list that several readers can each go through at their own pace. See queue vs pub/sub vs event stream.
5. The aggregator keeps a count per term over a rolling window, like "last seven days".
6. An hourly build reads the counts and constructs new trie shards from scratch.
7. Finished shards are swapped in whole. A serving node has either build 41207 or build 41208, never half of each, which makes a bad build a one line rollback.

Two boxes beside the main path are the exceptions that make it usable. A fuzzy index, for typos, consulted only when the exact prefix returns nothing. And a safety filter that can block a term between builds, without waiting an hour for the next one.

Notice what the design accepts: suggestions can be up to an hour old. That is eventual consistency, where readers may see slightly old data for a while, and it is a fine trade here because nobody is hurt by a suggestion that is an hour stale. Strong vs eventual consistency explains when it is not fine.

Step 3: Design deep dive#

Why the answer lives at the node#

This is the question the whole design turns on, so take it in three steps.

Try it. Type a prefix and watch the walk, then compare what is stored with what would otherwise have to be ranked.

Figure 2 steps through both paths on a real sized prefix. The difference between them is the difference between fifty milliseconds and five.

The general principle worth stating out loud, because it transfers to half the other questions in this course: when reads outnumber writes by orders of magnitude, move the work to the write side. Here the write side is an hourly batch job, which is the most comfortable place work can possibly live.

Rebuilding without going down#

Every hour there is a new index. Getting it onto the serving machines without a blip is the second deep dive.

The index is immutable: once built it is never changed, only replaced. That sounds heavy until you compare it to changing a live trie while a hundred thousand requests a second walk it. If the pointer flip feels familiar, it is the same idea as a blue green deployment, covered in blue green vs canary vs rolling.

The build runs on its own machines: read the term counts, filter blocked and unsafe terms, construct the shards, verify them against a set of known queries, and publish. A serving node downloads the new shard, builds it in memory alongside the current one, and flips a pointer. Memory usage doubles briefly, which is the price, and the swap is atomic, which is the point.

Two things this buys you that are worth naming. A bad build is rolled back by pointing at the previous version, which takes seconds and needs no code change. And because nothing is ever mutated, a serving node needs no locks at all on the read path, so a lookup is genuinely just a memory walk.

The fast path for trending terms is the exception, and it should be built as an exception rather than by making the whole pipeline faster. A small separate structure holds terms that spiked in the last ten minutes, the gateway merges it into the results, and it is allowed to be approximate. When a plane goes down, people search for it within seconds and an hourly build is useless, but that is a few hundred terms, not a few million.

Typos, and why they get their own path#

Someone types "restrant". No term starts with that, so the trie walk ends with nothing. The fix needs edit distance: how many single letter changes (add, remove, swap one letter) turn one word into another. "restrant" is one edit from "restaurant", one missing letter.

Prefix lookup and fuzzy matching want different structures. A trie answers "what follows this prefix" in five hops and answers "what is one edit away from this" not at all. Three ways to add it, from simplest to strongest:

Pick the deletion index if you can afford the build, and say why: eight lookups on the query side instead of fifty, paid for with offline storage. Then add the important qualifier, which is that none of this runs on the common path. Exact prefix first, always, and fuzzy only on an empty result.

Break it#

The "one letter" level is a hot partition: one shard gets most of the traffic because the data it owns is suddenly popular. The repair is worth remembering as a pattern. When the hot keys are also the small keys, copy them to every machine instead of trying to spread them. (The sharding chapter has the general version.)

Trade-offs#

Interview replay#

Checkpoint#