System Design: Search Autocomplete (Walnut Typeahead: Suggestions From Day One, Typo Matching, Per-Keystroke Load)
We design the search box suggestions of a large online store. The store is Walnut Mart, and our system is called Walnut Typeahead.
While a shopper types, it shows the searches she most likely means. It must do this from day one, before anyone has searched for a new product. It must also forgive typos such as "hi protean".
Walnut Typeahead only suggests the words. When the shopper picks one, Walnut Mart Search finds the products. That is a separate system, outside this design.
As in any system design interview, the numbers are assumptions for planning. Every number here is our own assumption, and the design is our own. All times are Central Time, in 2026.
How to read this post. It takes about 75 minutes in full, so it is built to be read in parts:
1. Requirements
1.1 What we are building
Walnut Typeahead does three jobs:
- Suggest while typing. On almost every keystroke, it shows up to 8 searches that start like the typed text. They arrive within 50 ms, before the next key.
- Forgive mistakes. Short forms and wrong letters still find the right search.
- Learn. It starts from the product catalog on day one. Then it learns what shoppers really search, and what is rising today.
The story, one week:
- Mon 30 Nov, 07:30:00. Chloe Ramirez is a high school teacher in Chicago. Before work, she plans a pickup order for the week's breakfasts. She types "hi protean" on her phone with one thumb.
- Mon, 07:30:02. After the last letter, her list shows 8 suggestions. The first three are "high protein breakfast", "high protein breakfast cereal" and "high protein breakfast sugar free".
- Mon, 07:30:02. Two searches are left out on purpose. Last month 900 shoppers typed "hight protein breakfast", a misspelling. And "high protein breakfast without sugar" means the same as "sugar free".
- Mon, 07:30:04. Chloe taps the first suggestion. Walnut Mart Search shows her the products, and she orders oatmeal cups for pickup.
- Mon, 14:00. The catalog team adds product P781, Walnut Protein Pancake Mix. It goes on sale on Tuesday at 06:00. Nobody has ever searched "protein pancake mix".
- Mon, 20:15. Marcus Lee in Minneapolis types "gift for dad who grills". Nobody has typed it before, so no suggestion matches it. His search still finds grill tool sets, and he buys one.
- Tue 1 Dec, 07:12. Ethan Walker in St. Louis types "protein pan". He sees "protein pancake mix" second, the day the product appears.
- Tue, 19:00. A cooking video with the mix spreads fast. In the next 40 minutes, searches for it go from about 40 an hour to 9,000 an hour.
- Tue, 19:42. "protein pancake mix" is now first for "protein p", for every shopper.
- Wed 2 Dec, 11:20. The maker of Little Sprout baby formula recalls it. By 11:22 no shopper sees a suggestion for it.
- Thu 3 Dec, 03:05. The night's new index fails its checks: its counts covered only half of the month. It never goes live. A rerun is live everywhere by 05:20, before the morning rush.
- Sat 5 Dec, 05:00. 63 different shoppers have now searched "gift for dad who grills". It becomes a suggestion.
The hard part: a fresh answer on every keystroke within 50 ms. At the busiest moment that is 500,000 answers a second. And the list must be clean even when the typing is not.
1.2 Words we use
Words used in only one place are explained there. Each word below is used all through the post.
Typing and suggesting
| Word | Meaning |
|---|---|
| Typed text | What is in the search box so far, such as "hi protean". |
| Suggestion | One complete search we offer, such as "high protein breakfast". We return up to 10, and the phone shows 8. |
| Query | The words of one search a shopper runs, by tapping search or a suggestion. |
| Prefix | The start of a string. "high p" is a prefix of "high protein breakfast". |
| Word prefix | The start of one word. "hi" is a word prefix of "high". |
| Edit | One wrong letter: one letter added, removed or changed. "protean" is one edit from "protein". |
| Short form | A word cut short on purpose, such as "hi" for "high". |
| Correction | A pair of a wrong word and the right one, such as "hight" and "high", learned from shoppers who fixed their own search. |
| Family | Suggestions that mean the same thing, such as "sugar free" and "without sugar" endings. We show one suggestion per family. |
Scoring
| Word | Meaning |
|---|---|
| Shopper count | How many different shoppers searched a query in the last 30 days. One shopper who searches it ten times counts once. |
| Score | One number per suggestion that sets its order. Recent days count more, and searches that led to a purchase count extra. |
| Catalog phrase | A suggestion made from product data, such as "protein pancake mix", before anyone searched it. |
| Rising query | A query searched far more often this hour than usual, such as "protein pancake mix" on Tuesday evening. |
| Takedown | Removing a suggestion everywhere at once, for example after a recall. |
Models inside Walnut Mart Search
These belong to Walnut Mart Search, not to Walnut Typeahead. They decide which products a search means.
| Word | Meaning |
|---|---|
| Small models | Small machine learning models that read a search live when it is not yet cached, such as a spell model, the product-type model and the tagger. They are not LLMs. Walnut Mart trains them on its own searches, clicks and catalog. |
| Product-type model | A small model that guesses which product types a search means, with weights, such as grills 0.40 and gift sets 0.35. |
| Tagger | A small model that finds sizes, brands and diets in a search, such as "keto" in "keto oatmeal". With the product-type model it takes about 7 ms. |
| LLM | A large language model. It is also a machine learning model, but far larger. Walnut Mart Search runs an open-weight one on its own GPUs, not an outside AI service. It runs once per new search, at night, to pick product types from a short list. |
Servers and storage
| Word | Meaning |
|---|---|
| Index | The file of all suggestions, laid out so one lookup takes microseconds. A microsecond is a millionth of a second. |
| Index version | One nightly build of the index, such as version 2026-11-30. All servers in a region switch to a new version together. |
| CDN | Content delivery network: a company with servers in many cities that keeps copies of our answers close to shoppers. |
| Region | A group of our data centers. Walnut Mart runs US East, US Central and US West. |
| p50, p99 | p50 is the time half of all requests beat. p99 is the time 99 of every 100 requests beat, so it shows the slow cases. |
IDs in this post
Every ID below is made up for the story. The start of each ID says what kind of thing it names.
| ID | What it names | Example |
|---|---|---|
| sg_118204 | A suggestion ID: one suggestion in one index version | sg_118204, "high protein breakfast" |
| fam_2291 | A family ID: suggestions that mean the same | fam_2291, the "sugar free" and "without sugar" endings |
| sh_4410 | A shopper ID: one Walnut Mart account | sh_4410, Chloe |
| P781 | A product ID: one product in the catalog | P781, Walnut Protein Pancake Mix |
| q_88213 | A search ID: one search, made by the app | q_88213, Chloe's search at 07:30:04 |
| 2026-11-30 | An index version: one nightly build, named by its day | 2026-11-30, the version Chloe's request used |
| td_0417 | A takedown ID: one removal on the takedown list | td_0417, the Little Sprout recall |
1.3 Every kind of request and change
The story follows a few shoppers. Walnut Typeahead handles more than that. Each row names the part that handles it, and the outside company that takes part.
| Kind | What it is | How big or how often | Which part handles it | Outside company or other team |
|---|---|---|---|---|
| Plain prefix | Typed text that is the exact start of a suggestion, such as "high p" | About 9 in 10 requests | The Typeahead service, with the exact lookup | The CDN answers the shortest ones |
| Typed with mistakes | Short forms or wrong letters. Chloe's "hi protean" is this kind | About 1 in 10 requests | The Typeahead service, with the word-by-word lookup | None |
| Empty box | The shopper taps the box and types nothing yet | Once per search | The app shows her recent searches, with no request | None |
| First-time search | A search no shopper typed before, such as Marcus's "gift for dad who grills" | Most of the 400 million different queries | Walnut Typeahead suggests it only after 50 shoppers; until then it is only counted | Walnut Mart Search finds its products from the first time |
| New product | A product nobody has searched yet, such as P781 | About 50,000 new products a day | The Phrase builder, each night, from the catalog | The Catalog store, another team's |
| Learning from searches | Every search and every pick is logged and counted | 600 million searches a day | The Event stream, the Count job and the Index builder | Walnut Mart Search sends each search |
| Rising query | A query searched far more this hour than usual, such as the pancake mix on Tuesday | A few hundred a day | The Trend job, every minute | None |
| Takedown | A suggestion that must disappear, after a recall or a complaint | A few a week | The takedown list in the Control store | The CDN removes its copies |
| Recent searches | The shopper's own past searches, shown first | Every typing session | Only the app, on the phone | None |
This post follows Chloe's typing in depth. The other kinds use the same parts.
1.4 Functional requirements
- Suggest while typing. Return up to 10 suggestions for any typed text of up to 60 characters. The phone shows 8.
- From day one. Suggest searches for products nobody has searched yet, from the catalog.
- Learn from shoppers. Order suggestions by how many different shoppers searched them. Recent days count more, and searches that led to a purchase count extra.
- Forgive typos. Match word by word: short forms, and one or two wrong letters per word.
- Keep lists clean. Never show a misspelling or two suggestions that mean the same. Never show a search that finds no products, or anything unsafe.
- Show rising queries within 10 minutes.
- Take suggestions down everywhere within 2 minutes.
- Show recent searches from the shopper's own phone.
- Log what happened. Record which suggestion was shown, which was picked, and whether the search led to a purchase.
Out of scope:
- the results page, which Walnut Mart Search builds;
- ads inside the suggestion list;
- product pictures inside the list;
- voice search;
- languages other than US English;
- suggestions written by a large language model.
1.5 Non-functional requirements
- Fast. A list reaches the phone within 50 ms at p99, from the moment the request leaves it. The server itself answers within 10 ms at p99.
- Big. 500,000 requests a second at the busiest moment, the 06:00 hour of Black Friday.
- Fresh. Scores are rebuilt every night. A rising query appears within 10 minutes. A takedown reaches every server within 1 minute, and every CDN copy within 2 minutes.
- Private. A query is shown to other shoppers only after 50 different shoppers searched it in 30 days. A query with a phone number, an email or an order number is never shown.
- Always on. 99.95% of requests get an answer. If Walnut Typeahead fails, the search box still works without suggestions.
- Safe changes. A bad build never goes live. Every server can switch back to the last good version within 1 minute.
1.6 The numbers
Every number below is our own assumption for planning, with its sum. The search numbers are those of Walnut Mart Search.
| Question | Our assumption, and the sum | Result | What it decides |
|---|---|---|---|
| Searches? | 600 million a day; 100,000 a second at 06:00 on Black Friday | 600 million a day | How much the logs hold |
| Keystrokes per search? | Our estimate: shoppers stop typing once they tap a suggestion | About 11 | The load without any help |
| Requests per search? | The phone waits for a pause in typing and keeps its own copies | 5, not 11 | The phone halves the load |
| Requests a second? | 600 million × 5 ÷ 86,400 s ≈ 34,700 on average; 100,000 × 5 at the peak | About 35,000 average, 500,000 peak | Size for the peak |
| Answered by the CDN? | The CDN keeps answers for typed text of 1 to 4 characters, which millions share. Our estimate: 40% of requests at the peak | 300,000 a second reach our servers | The CDN takes 40% off our servers |
| Servers? | We estimate one 16-core server answers 20,000 a second. If one region is lost, two regions carry 150,000 each: 8 busy servers. With 50% spare, 12 per region | 36 servers, 12 in each region | Small: requests decide this, not data |
| Different queries? | Our estimate: 400 million in 30 days, most typed by one shopper once | 400 million | Most must never be shown |
| Queries 50 shoppers searched? | Our estimate | 6 million | The suggestions learned from shoppers |
| Catalog phrases? | Our estimate, from the 60 million products people buy | 14 million | Suggestions from day one |
| Suggestions in the index? | 6 million + 14 million, minus overlaps and misspellings | 18 million | About 3 GB, so every server holds all of it |
| Search log? | 600 million × 500 bytes | 300 GB a day, 9 TB for 30 days | A nightly batch job, not a database |
| Time between keystrokes? | Our estimate for a fast thumb | About 250 ms | The answer must come first |
What these numbers tell us:
- The data is small: 3 GB fits in every server's memory. Requests, not data, decide the number of servers.
- Every keystroke is a request, so the phone and the CDN must remove half of them before they reach us.
- Of 400 million different queries, only 6 million may be shown. Choosing them is the real work, and it happens at night.