Design Typeahead Suggestions

It is 10:40 pm, the last over of an India vs Australia final. Lakhs of people pick up their phones and type ind into a search app at the same moment. On Neha's phone in Kanpur the list under the box arrives only after her third letter, still offers last month's "india vs australia 2nd odi", then jumps back to suggestions for in while she is typing indi. Nothing is down. The suggestions are simply late, stale and out of order. This chapter designs a search box that answers every keystroke within about 100 ms, with tonight's queries in the list.

The product: the suggestion list that drops down under a search box. Show up to ten completions for the letters typed so far, favour what is popular right now, and never suggest anything offensive or private. About 50 million people search every day. Neha typing ind on final night is the example we follow throughout.

Neha's problem was three problems: a slow list, a stale list and a list from the wrong keystroke. Start by pinning down what the feature must do. Type ind and a list should drop down before the next key press: "india vs australia live score", "indigo flight status", "indian railway pnr status". This is typeahead, also called autocomplete: given the prefix typed so far, return the few complete queries the user most likely wants.

It looks small, but it runs on almost every keystroke of every user, which gives it several times the traffic of search itself, and each answer has to arrive before the next key.

The 100 ms target comes from typing speed. Someone typing 40 words a minute presses a key about every 300 ms; a fast typist, about every 150 ms. If suggestions take longer than the gap between keys, the list describes a prefix the user has already moved past. About 100 ms is also roughly where a response stops feeling instant.

Before drawing servers, count the requests, because every keystroke is one. Assume 50 million daily users who search 6 times a day. A query is about 20 characters, but the app skips keys during a fast burst and many people tap a suggestion early, so count about 8 suggestion requests per search.

Nine servers, not four, because a whole region can fail: the six left still have room for 40,000 a second. The big-match row is why the edge matters so much. A final multiplies traffic 5 to 10 times, but nearly everyone types the same few prefixes, which is exactly what a cache serves best.

Requests decide how many servers answer; memory decides what each one can hold. We keep only queries that enough different people typed recently, about 100 million distinct queries across all languages, in a compressed trie that stores the top 10 answers at every node. The deep dives explain both ideas; first, estimate what they cost.

Two checks before trusting that. First, 60 bytes a node assumes a compact layout: nodes packed into large arrays, with children and lists stored as 4-byte indexes. Built as one object per node with pointers, as a quick prototype would be, the same trie takes several times more and stops fitting. Second, is 100 M queries sane? Thirty days bring 300 M × 30 = 9 B searches, and a query is kept only if at least 50 different people typed it, so at most 9 B ÷ 50 = 180 M can qualify. Popular queries use up many searches each, so the real number is lower: 100 M is a generous ceiling.

This result shapes the whole design: a full copy of the index fits in one server's memory. Every suggestion server holds all of it, any server can answer any prefix, and we add servers for throughput, not for space.

Servers and memory are settled; now check that an answer can actually arrive in time. Split the 100 ms across every step a keystroke passes through, and give the biggest share to the part you control least: the mobile network.

Add it up honestly. An edge hit takes about 45 to 75 ms, comfortably inside the budget. A miss takes about 55 to 115 ms, so on a slow network it can run over. The server's own work is about 1 ms either way: almost all of the budget is network. That is why the design answers as many keystrokes as possible from the edge, and why a faster lookup would barely help.

An answer can only come from the edge if the request is cacheable, so the API is designed around that. One read endpoint carries almost all the traffic. Make it a plain GET with everything in the URL, so the browser, the CDN and any proxy on the way can cache it.

GET /v1/suggest?q=ind&lang=en-IN&limit=10

200 OK
Cache-Control: public, max-age=300
{
  "prefix": "ind",
  "suggestions": [
    { "text": "india vs australia live score" },
    { "text": "indigo flight status" },
    { "text": "indian railway pnr status" }
  ]
}

POST /v1/events
{ "type": "search", "q": "indigo flight status", "picked_rank": 2, "lang": "en-IN" }

The suggest call never needs to know who is typing, which is what keeps it cacheable.

• Normalise the prefix before using it as a cache key: lowercase it and collapse repeated spaces, so IND and ind share one entry. Keep a single trailing space, because ind (a finished word) means something different from ind.
• lang picks the right index. People searching in Hindi, Tamil or English type different things.
• limit is capped at 10. Nobody reads a longer list while typing.
• max-age=300 lets the browser and the edge reuse an answer for 5 minutes. A longer time means more cache hits but staler lists.
• POST /v1/events is sent when a search is submitted, with the rank of the suggestion the user picked, if any. It feeds the offline build, never the live path.

Personal suggestions, such as your own recent searches, deliberately do not come from this endpoint. The app keeps them on the device and merges them in, so the shared response stays identical for everyone.

The suggest call reads nothing but memory, so where does that memory come from? There are two worlds: raw logs that grow every second, and serving data rebuilt from them on a schedule. Keep them apart: the live path never reads a log.

user_hash is a one-way hash of the user id, made with a secret key so nobody can match it back by hashing known ids. The build needs to count how many different people typed a query, so it never suggests something only a handful searched for, but it never needs to know who they were.

With the data split in two, the system splits the same way. The online path answers keystrokes from caches and memory. The offline path turns logs into a fresh trie every hour and ships it to the servers as one file. Follow the online path first.

Three lessons. Many keystrokes never leave Neha's city, because short prefixes are shared by everyone and stay cached at the edge, as in the CDN chapter. A miss costs extra network hops but no disk or database work. And a failed server is replaced by copying a file, because suggestion servers hold no state of their own.

That is the offline path, the second deep dive. The contract between the two paths is the snapshot file, plus two small lists covered later: trending queries and blocked ones. As long as a valid snapshot exists, the online path keeps working, even if the build pipeline is down for a day.

The diagram starts at the phone, and the phone decides two things: how many requests reach the edge, and which answers reach the screen. Remember Neha's list jumping back to in. Four habits fix both.

• Keep one request in flight. While an answer is on its way, send nothing more; when it returns, send only the newest prefix. A fast typist skips the prefixes in between, and a slow typist still gets an answer for every key. If an answer takes longer than about 300 ms, stop waiting and send the newest prefix anyway.
• Debounce lightly, if at all. Debouncing means sending only after typing pauses for a set time. A 150 ms pause would skip most keys but add 150 ms to every answer, more than the whole budget; one request in flight saves requests without that delay.
• Drop stale answers. An abandoned request can still answer late, so number every request and show an answer only if it is newer than the list on screen.
• Reuse what you have. Filter the list for ind on the phone to show something for indi while the real answer loads, and keep recent answers in memory so backspacing touches no network at all.

The rule is "newest request wins", not "matching prefix wins". It costs one counter on the phone, and it is what stops the list jumping back to an older answer while the user types.

A server receives ind and must return 10 queries in about a millisecond. Search results come from an inverted index (the distributed search chapter), which matches whole words. Suggestions must match the start of a query, and the classic structure for that is a trie (said like "try"): a tree in which each edge adds one character. Every node stands for a prefix, and every query below it starts with that prefix, so reaching ind takes three steps however many queries are stored. Think of a library shelved by the first letters of each title: finding the shelf is quick, but the shelf for "i" is enormous.

The lesson: precompute the answer. Finding the best 10 below a prefix happens once per build, not once per keystroke, and the stored list is only 40 bytes.

def suggest(trie, prefix, k=10):
    node = trie.root
    for ch in prefix:                 # one step per character typed
        node = node.children.get(ch)
        if node is None:
            return []                 # no kept query starts with this prefix
    return [trie.text[qid] for qid in node.top[:k]]   # precomputed list

A plain trie; a compressed trie compares a whole edge label per step.

The scene filled the lists from the bottom up. Precisely: a node's top 10 is the best 10 among the query that ends at that node, if any, and its children's top 10 lists. One pass over the tree fills every node, offline, so its cost never touches a keystroke. Here is the result for six queries, keeping the top 3 to fit the page:

Four tricks keep the trie inside the 15 GB estimated earlier. Store 4-byte query ids in each list, not the text: about 16 bytes saved per entry. Compress the trie: merge chains of single-child nodes where no query ends into one edge, so there are at most 2 nodes per query instead of one per character; a prefix that ends mid-edge uses the list of the node the edge leads to, since the same queries lie below both. Keep 10 entries per node, not 50, because the list is the biggest part of each node. Drop queries few people typed, the huge long tail that is rarely useful.

The trie is only as good as the scores in its lists, and those come from real searches. Every submitted search is logged as an event, about 30 GB a day. Each hour a batch job normalises the new hour's queries (lowercase, collapsed spaces, one Unicode form, so equal queries count together) and adds them to a count per query per day. It never rereads 30 days of raw logs.

Scoring with decay. Raw counts would favour old hits forever. Instead, each day's count is multiplied by a weight that halves every 7 days, a 7-day half-life. Say a query about tonight's final is searched 1,000 times today: it scores 1,000. Last month's match, searched 10,000 times four weeks ago and not since, has been halved four times: 10,000 ÷ 16 ≈ 625. Tonight wins, as it should. Days older than 30 weigh under 5%, so the job stops there.

HALF_LIFE_DAYS = 7

def score(daily_counts, today):
    # daily_counts: {date: count} for one normalised query
    total = 0.0
    for day, count in daily_counts.items():
        age_days = (today - day).days
        total += count * 0.5 ** (age_days / HALF_LIFE_DAYS)
    return total

A small bonus for suggestions people tapped, and a small penalty for ones they skipped, also helps.

Counting different people. The privacy rule keeps a query only if at least 50 different people typed it. Daily counts of distinct users cannot simply be added up, because Neha searching on three days would count three times. So the job keeps a small mergeable sketch per query per day, such as a HyperLogLog, which estimates distinct users within a few percent; merging 30 daily sketches gives the 30-day figure. Keeping sketches only for queries searched more than a handful of times that day keeps their storage small, at the cost of missing a few slow, steady queries.

Scores in hand, the job builds a compressed trie per language, fills its lists bottom-up and writes it as one versioned file. Three steps stand between that file and Neha's screen, and each one prevents a specific failure.

• Write the file in the memory layout. If the file holds the same packed arrays the server uses, a server maps it into memory instead of parsing 200 M nodes, so a swap costs a download and seconds of work, not minutes.
• Validate before publishing. A bug that produces an empty or half-built trie would blank every search box at once. Compare each build with the last one (query count, file size, answers for a list of common prefixes) and refuse it if they differ wildly.
• Canary, then swap. One server loads the new file first and takes a little traffic; if its error rate and acceptance rate look normal, the rest follow. Each maps the new file beside the old one and switches a single pointer; requests in progress finish on the old trie. That is why the memory estimate planned for two copies.

Shipping is cheap. Each server fetches about 15 GB an hour, about 12 seconds over a 10 Gbps link, so 9 servers move about 135 GB an hour from the blob store. Rolling back is pointing at the previous file. Hundreds of servers would call for staggered downloads or shipping only the changed parts.

An hourly trie with decayed scores covers most needs. Three gaps remain: news faster than an hour, what this user personally wants, and what must never appear.

Trending queries. An hourly build is too slow when a match ends on the last ball. Add a small fast layer: a streaming job counts queries over the last 10 to 15 minutes, spots those rising far above their usual rate, and publishes a short trending list per prefix every few minutes. It passes the same safety filters, and servers merge it with the trie's answer at request time.

Personal suggestions. Your own recent searches are the best predictor of what you will type next. Keep the last 50 or so on the device, match them locally and show them above the shared list. The shared response stays the same for everyone, so the edge can still cache it.

Language and place. Build one trie per script and language, and pick it by what is being typed: many people type Hindi words in English letters, and those queries belong in the Latin-script trie. Where suggestions differ by place ("weather" should complete to the user's own city), add a coarse region such as the state to the request and the cache key. Keep regions few, because each one splits the edge cache.

The serve-time list is the safety valve: an entry pushed to every server, plus a purge of the affected prefixes from the edge caches, removes a bad suggestion within minutes. The build filter is fixed afterwards.

Typeahead has one rule above the rest: suggestions may fail, the search box may not. If anything below goes wrong, the app shows no list and the user types and searches as usual.

Hot prefixes are a gift here, not a problem. In most systems a hot key hurts. In typeahead the hottest prefixes are one or two letters long, and there are only about 700 of those with the 26 English letters, so the edge caches them almost perfectly.

Sharding, when you need it. If many more languages arrive or a trie outgrows one server, split by prefix range (for example, a to c on one group of servers), with ranges sized by measured data, since far more queries start with s than with x. Keep one- and two-letter prefixes in a small table on every server, so the shortest prefixes never depend on the shard map.

Most choices in this design trade one thing: fresher and more personal results cost cacheability and simplicity. The table shows where each choice landed.

Each pick flips under a condition: a product where freshness within seconds matters, such as live scores inside the app, justifies streaming updates; a product whose index is far larger than RAM, such as every address in the country, starts as a sharded table.

What dominates the bill: the request count. 2.4 B requests a day is about 72 B a month, and edges price or provision per request, while the data is small and nine 64 GB servers answer the misses.

A 45-minute round leaves about 40 minutes of design. Here is typeahead on that clock.

Pick the trie if they ask how a lookup stays near 1 ms with millions of queries. Pick the build pipeline if they ask how suggestions stay fresh, ranked or safe. If they ask about personal results, explain the merge on the device and why it keeps the edge cache working.

Each question changes one thing. Answer it before you open it.