Design typeahead (autocomplete)

Typeahead is the dropdown that finishes your sentence. Type “iph” and the box offers “iphone 16”, “iphone 16 pro max” and “iphone 15” before you reach the fourth letter. It looks small, but it is one of the busiest services a search product runs — every search becomes five or six requests — and it has a hard deadline: Facebook’s engineers wrote that taking more than 100 ms makes typeahead “stutter”. Once the data structure is right, the lookup is easy. The design problem is everything around it: turning a billion daily searches into ranked completions, noticing within minutes that “ind vs aus live score” has exploded after the toss, answering 200,000 requests a second mostly from caches, blending in your language and history, and never suggesting something offensive or private.

Understand the problem

Be precise about which typeahead you are building. Query autocomplete predicts the search a person is typing from what millions of others have searched: “kurt” becomes “kurti for women”. Entity typeahead returns things — friends, a company page, a product card — and is closer to a tiny search engine; Facebook’s and LinkedIn’s are of this kind. This design is the first, for a large search engine or shopping app. Google describes its predictions the same way: common and trending real searches that match what was typed, adjusted for language, location and past searches (Google, 2020).

Functional requirements

1. Users should see up to 10 completions for what they have typed so far, refreshed at every pause in typing and ranked by popularity: “iph” → “iphone 16”, “iphone 16 pro max”, “iphone 15”.
2. The system should learn from searches. Popularity comes from real search logs, weighted towards recent days, and the index is refreshed at least every hour.
3. The system should surface trending queries within about five minutes. When the toss happens in a cricket final, “ind vs” should offer “ind vs aus live score” long before tonight’s batch run.
4. Users should get suggestions in their language and region, plus their own recent searches. “kurt” in Lucknow and in Chennai, typed in Latin script or in Devanagari, should not give identical lists.
5. The system should never suggest blocked content — offensive, dangerous, legally removed or private queries — and an urgent takedown should take effect within a minute.

Non-functional requirements

• Latency. Under 100 ms at p99 from request to drawn list. After the mobile network’s share, the server gets about 10 ms at p99, and should answer in under 2 ms at p50.
• Throughput. About 70k suggestion requests per second on average and 210k/s at the evening peak, with 2× bursts during cricket finals and sale launches (arithmetic below).
• Availability. 99.99%, and it is an enhancement: if it fails, the search box still works. Degrade to fewer or staler suggestions, never to an error.
• Freshness. Base popularity refreshed hourly; trending queries visible within 5 minutes; urgent takedowns live within 1 minute.
• Scale. 200M daily active users, 1B searches a day, about 100M distinct suggestible queries across English, Hindi and a dozen other languages.
• Consistency. Eventual; two people may see slightly different lists for a minute.

Out of scope

• The search results page behind the box — that is the search engine design.
• Spell-corrected search itself. Light typo tolerance in the box is a deep dive; “did you mean” on the results page is not.
• Ads and sponsored suggestions.
• Rich entity suggestions such as product cards with images and prices — covered briefly as a follow-up.
• A machine-learned ranker. We rank with a clear scoring formula; a learned model could re-rank the top 30 later without changing the architecture.

The set-up

Plan the approach

This system has two paths with opposite rules. The read path must answer in a few milliseconds, 200,000 times a second, for every keystroke. The write path turns logs into an index and may take minutes or an hour. The core idea is to move every expensive decision off the read path: precompute the answer for every prefix, so serving is a lookup. Say that early, build each requirement simply, then spend the time on the deep dives: the data structure, building the index, trending, serving at scale, personalisation, and safety and typos.

Core entities

• Suggestion. A normalised query (“iphone 16”), its display text, language and script, alternative input forms such as transliterations, a time-decayed score, per-region scores and flags (blocked, sensitive).
• Index snapshot. An immutable, versioned build of the prefix-to-top-k structure for one language and region bucket, with a checksum.
• Search event. One per submitted search: raw and normalised query, a hashed user or device ID, language, region, timestamp, and which suggestion was picked (and at which position), if any.
• Trending entry. A query with its short-window count, its usual baseline, a trend score and an expiry time.
• User history. A person’s last 50 searches, kept on the device and optionally synced.
• Block rule. An exact query, a normalised phrase or a term, with a scope (global or one country), a reason and an owner.

API

The suggest call. One GET per request, with everything that shapes the answer in the URL.

GET /v1/suggest?q=iph&lang=en&region=IN-MH&k=10

HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: public, max-age=60

{
  "q": "iph",
  "suggestions": [
    { "text": "iphone 16" },
    { "text": "iphone 16 pro max" },
    { "text": "iphone 15" },
    { "text": "iphone 17 launch date", "trending": true },
    { "text": "iphone 16 cover" }
  ],
  "complete": false,
  "index": "en-IN/2026-10-27T13"
}

Three choices matter. There is no user ID in the request, so the response is the same for everyone in the bucket and the browser and CDN can cache it. Language and region are query parameters, not headers, because the URL is the cache key. And the client normalises q before sending, so “IPh ” and “iph” share one cache entry. complete: true means the prefix has fewer than k completions in total, so the client can answer longer prefixes by filtering this list locally.

Personal history is a separate, private call, made once when the search box gets focus:

GET /v1/suggest/history?limit=50
Cache-Control: private, no-store

DELETE /v1/suggest/history/h_81c2      (remove one entry)

Search events are not an API the client calls; the search service emits one per submitted search onto a log topic:

{
  "q_raw": "Iphone 16 ",
  "q": "iphone 16",
  "user": "u#5d0e9a",
  "lang": "en",
  "region": "IN-MH",
  "ts": "2026-10-27T13:02:11Z",
  "picked": { "position": 1, "typed": "iph" }
}

Safety operations go through an admin API: POST /v1/blocks with a pattern, a match type (exact, phrase or term), a scope and a reason. Urgent blocks reach every server within 60 seconds.

Back-of-envelope estimates

These numbers decide whether the index fits in memory, what caching buys and how many servers you need (method).

Searches. 200M daily users × 5 searches = 1B searches a day, or 1B ÷ 86,400 s ≈ 11,600 searches/s on average and about 35k/s at a 3× evening peak.

Suggestion requests. People pick a suggestion or press Enter after about eight keystrokes, and debouncing merges bursts. Assume 6 requests per search: 1B × 6 = 6B requests a day, and 6B ÷ 86,400 s ≈ 69,000 requests/s on average. At a 3× peak that is about 210k/s; a cricket final or a sale launch can double it for an hour, to about 420k/s.

What reaches the servers. About 10% of requests are answered by the browser’s own cache (backspacing, retyping): 210k × 0.9 = 189k/s leave the device. About 40% of those are for 1–3 character prefixes, and there are only 37 + 37² + 37³ = 52,059 such prefixes per language (26 letters, 10 digits and a space), so the CDN answers about 95% of them. The origin sees 189k × (1 − 0.40 × 0.95) = 189k × 0.62 ≈ 117k requests/s at peak, and about 234k/s in a burst.

Index size. Suppose 100M distinct queries pass the popularity and privacy thresholds, at 20 bytes each on average: 100M × 20 B = 2 GB of text. With the structure chosen in the first deep dive, plus regional lists and spare slots, a server’s copy of the index is about 15 GB — small enough for every server to hold all of it.

Servers. The lookup is microseconds; parsing, merging, filtering and JSON encoding dominate. Budget 10k requests/s for a 16-core server: 117k ÷ 10k ≈ 12 servers at peak. Double it for bursts and for losing a zone: 24 servers, each with 64 GB of RAM so that two index versions (2 × 15 GB) fit side by side during a swap.

Logs for the pipeline. One event of about 300 bytes per submitted search: 1B × 300 B = 300 GB a day raw, about 60 GB compressed, or 12.5 GB raw per hour. At the peak that is 35k events/s × 300 B ≈ 10 MB/s into Kafka — easy. Keystroke requests are not needed by the index; a 1% sample is enough for latency analysis.

Trending state. At the peak, 35k searches/s × 300 s ≈ 10.4M searches land in a five-minute window. A count-min sketch with error ε = 0.0001 and failure probability δ = 0.001 has ⌈e/ε⌉ = 27,183 columns and ⌈ln 1,000⌉ = 7 rows: 190,281 counters × 4 B ≈ 0.76 MB per window, overcounting any query by at most 0.0001 × 10.4M ≈ 1,040 searches.

Shipping snapshots. 15 GB × 24 servers = 360 GB per hourly build, or about 100 MB/s averaged over the hour — unremarkable inside a data centre.

High-level design

Build the system one requirement at a time. By the end of this section it works, at modest scale, with fresh and safe suggestions.

Users should see top completions as they type

Start with the read path and an index that someone built by hand. The search box sends the current prefix; a suggest service holds a prefix index in memory, finds the precomputed top 10 for that prefix, and returns it. There is no database on this path at all.

The flow is four steps:

1. The user types “iph”. The client waits for a short pause in typing, then sends GET /v1/suggest?q=iph&lang=en&region=IN-MH.
2. The load balancer picks any suggest server; each one holds the whole index.
3. The server normalises the prefix, walks the index to the node for “iph”, reads the ten completions stored there, and returns them.
4. The client draws the dropdown. If the user has typed more letters in the meantime, it throws the stale answer away.

Why not query a database per keystroke? Because “find everything starting with s and sort it” grows with the number of matches, and the shortest prefixes have the most matches and are typed most. The first deep dive puts numbers on that.

The system should learn from searches

A hand-built index goes stale on day one. Add a write path that never touches the read path: the search service logs one event per search; the events land in hourly files; an aggregation job counts searches per normalised query, applies time decay and thresholds, and drops blocked queries; an index builder turns the survivors into an index snapshot; the suggest servers download it and swap it in.

Three rules make the numbers trustworthy:

• Normalise before counting. Lower-case, Unicode-normalise, collapse spaces and strip trailing punctuation, so “Iphone 16 ” and “iphone 16” are one query.
• Count people, not hits. Count each user at most once per query per day, so a script that searches its own brand 10,000 times counts once.
• Require a crowd. A query becomes suggestible only after enough distinct people have searched it — say 20 in the window. That keeps out noise, and it stops one person’s phone number or PNR number from ever being suggested to someone else.

The serving path never writes. Each snapshot is read-only, so many threads can read it without a single lock, and a bad build is undone by loading the previous version.

The system should surface trending queries within minutes

An hourly batch with a week-long memory cannot react to a toss at 7:00 pm. Add a fast path beside it: a stream job reads the same search events, counts queries in short windows, notices the ones growing far faster than usual, and publishes a small trending list — about 20,000 entries — to every suggest server once a minute. The server merges trending matches into the base answer at request time.

This is a classic batch versus stream split: the batch path is complete, exact and slow; the stream path is approximate, partial and fast, and only has to be right about the few hundred queries that are spiking.

Users should get local, language-aware and personal suggestions

Popularity depends on where you are and how you type. The pipeline builds one index per language and region bucket — en-IN, hi-IN, ta-IN and so on — with per-state scores alongside the national ones, so “kurt” in Lucknow can rank “kurti chikankari” higher than it does in Chennai. All of that is still the same answer for everyone in the bucket, so it stays cacheable.

Personal history is different: it is private and changes with every search. Keep it out of the cacheable response. Facebook’s typeahead fetched each user’s friends, pages and groups into the browser when the box got focus, then matched them locally (Facebook, 2010). Here the client fetches the last 50 searches on focus and merges them into each server answer.

The system should never suggest blocked content

Add a block-rules service with two consumers. The index builder applies the full rule set at build time, so a blocked query never enters a snapshot and never takes a slot in a top-10 list. The suggest servers also load a small urgent list, pushed within 60 seconds, and filter every answer — base and trending — against it, because a court order or a dangerous rumour cannot wait for the next hourly build.

The design now works end to end. The deep dives make each piece fast, small and robust.

Deep dives

How do we find the top completions for a prefix fast?

Every request asks: of all queries starting with this prefix, which ten are most popular? Short prefixes are the trap — nearly every search passes through one, and they have the most matches.

Bad: a database range scan. Keep the queries in a table and ask:

SELECT query
FROM   suggestions
WHERE  lang = 'en' AND query LIKE 'iph%'
ORDER  BY score DESC
LIMIT  10;

With a B-tree index on query, a prefix LIKE becomes a range scan. For “s” it might read 8M of the 100M rows and sort all of them by score, because the index is ordered by text, not by popularity. That is seconds per request, at 117k requests a second. A search engine’s prefix query has the same shape, which is why Elasticsearch ships a separate, in-memory completion suggester (Elasticsearch docs).

Good: a trie, walked and then collected. In a trie, each edge adds a character, so every completion of a prefix lives in the subtree under that prefix’s node. Walk to the node, then visit its whole subtree keeping the best ten in a min-heap. For “s” the subtree holds 8M queries; at about 50 ns per node, 8M × 50 ns = 0.4 s — for the prefix typed most often. Memory is poor too: if 100M queries have about 600M distinct prefixes, that is 600M nodes at roughly 48 bytes each as objects, about 29 GB.

Great: store the answer at every node. The index is rebuilt offline, so precompute. Walk the trie bottom-up: each node’s list is the best ten among its own query (if one ends there) and its children’s lists. At request time, walk to the node and read its list: a few hops and ten string lookups, a few microseconds, however many queries share the prefix.

The catch is memory. Ten 4-byte query IDs are 40 bytes per node; on 600M nodes that adds 24 GB, so the trie with lists weighs about 29 + 24 = 53 GB, plus 2 GB of query text: 55 GB. A server must hold two versions during a swap, so this does not fit a 64 GB machine. Three changes bring it down:

• Collapse chains into a radix trie. Most deep nodes have one child and add only a character. Merge each chain into one edge labelled with a substring, as in the figure. A radix trie over N strings has at most 2N − 1 nodes, so 100M queries need at most 200M nodes, not 600M. A prefix ending partway along an edge — “iph” inside “hone 1” — uses the list of the node below it.
• Store lists only where they are needed. A leaf is a single query, so its list is itself. Only internal nodes — at most 100M — need a stored list.
• Use flat arrays, not objects. Lay nodes out in arrays (first child, edge-label offset and length, list offset): about 20 bytes per node, no object headers or garbage collection, one file to memory-map.

The arithmetic: 200M nodes × 20 B = 4 GB, plus 100M lists × 40 B = 4 GB, plus 2 GB of text and 100M × 4 B = 0.4 GB of scores: about 10 GB. Regional lists and a couple of spare slots per list (both covered below) take a server copy to the 15 GB used in the estimates.

Two alternatives are worth knowing, because an interviewer may push on each.

A prefix → top-k hash map. Precompute a map from every prefix to its top ten. A lookup is one hash probe, and it maps onto a key-value store such as Redis or RocksDB that you can shard by key. The cost is memory: 600M prefixes × (about 12 B of key + 16 B of overhead + 40 B of list) ≈ 41 GB, plus 2 GB of text, about 43 GB — several times the radix trie, which shares prefixes the map stores one by one.

A weighted finite state transducer (FST). This is what Lucene and Elasticsearch use. An FST is a minimal automaton: it shares common endings as well as beginnings, and maps each string to an output such as a weight. Mike McCandless built one over the 9.8M distinct terms of a Wikipedia index in about 8 seconds; it took 69 MB, about 7 bytes per term — far less RAM than other sorted maps, for more CPU per lookup (McCandless, 2010). Queries are longer and share fewer endings, so assume about 20 bytes per query, roughly 2–3 GB for 100M — an order of magnitude, not a measurement. Elasticsearch’s completion suggester is built this way, with integer weights per input and the whole structure in heap memory.

How do we build and update the index?

Bad: update the serving trie on every search. At 35k searches a second, each search raises one query’s score and may reorder the lists of up to 20 ancestor nodes, on all 24 replicas. Reads at 117k a second now contend with writes on the same nodes, so you need locks or copy-on-write. Worse, nothing stands between a search and the suggestion list: one person, or one bot, makes a phrase suggestible at once, private queries included. LinkedIn’s Cleo does update in real time, but it indexes entities from a vetted catalogue (LinkedIn, 2012); raw query logs are neither slow nor vetted.

Good: a nightly rebuild from the last 30 days of logs. Count, rank, build, ship. It is simple and safe, but a search from 29 days ago weighs as much as one from this morning, so dead queries linger; the job rereads 30 × 300 GB = 9 TB every night; and the index can be a day stale.

Great: decayed scores updated every hour, built into immutable snapshots, swapped in atomically.

Give every query an exponentially decayed count: on each run, score ← score × 2^(−Δt / half-life) + new count. With a 7-day half-life and hourly runs, the multiplier is 0.5^(1/168) ≈ 0.9959. A search from yesterday is worth 0.91 of one today, last week’s 0.5, last month’s 0.05. Each query needs one number of state, and each run reads only the last hour of logs — about 12.5 GB raw — plus the previous score table. Keep that table larger than the index (say the top 500M candidates) so that queries just below the threshold can climb in.

The chart’s numbers come from the same formula with daily steps (0.5^(1/7) ≈ 0.906). The old model starts at its steady state, 100k ÷ (1 − 0.906) ≈ 1.06M, and the lines cross after ln(0.524) ÷ ln(0.906) ≈ 6.5 days. With plain all-time counts, a year of 100k searches a day — 36.5M — would need 36.5M ÷ (150k − 40k) ≈ 332 days to overtake. Pick the half-life per product: a news-heavy search box wants a day or two, a shopping app a week or two, and some systems blend a long-term and a short-term score.

Building and shipping each snapshot follows a fixed routine:

1. Aggregate. Normalise queries, count each user once per query per day, apply decay, keep queries searched by at least 20 distinct people, and remove anything matching a block rule.
2. Build. Sort the survivors, build the radix trie bottom-up computing each node’s list, and write the flat arrays and a checksum. Each language bucket builds in parallel; 100M strings take minutes.
3. Validate. Golden prefixes still work (“iph” includes an iPhone), size is within 10% of the last build, no blocked query is present, and the top suggestions for the 1,000 busiest prefixes are diffed against the previous version.
4. Ship. Upload to blob storage and move a version pointer. Each server downloads the file (15 GB at 500 MB/s is 30 seconds), memory-maps and warms it, runs a self-test, then swaps one pointer; in-flight requests finish on the old version. One server goes first, then 10%, then all, while you watch click-through and latency.
5. Roll back by pointing back at the previous version, which still exists untouched.

How do we capture trending queries within minutes?

The base index cannot react to a toss. A query searched 200k times a day for weeks has a decayed score of about 8,300 an hour × 1 ÷ (1 − 0.9959) ≈ 2M. “ind vs aus live score” might be searched 300k times in the hour after the toss, and after the next hourly build its score is still only about 300k — far below the evergreen queries for “ind vs”. By the time decay lets it climb, the match is over. Trending needs its own path.

Bad: rebuild the base index every minute, or count in a database. Rebuilding ships 15 GB × 24 servers = 360 GB a minute (6 GB/s) from a build that takes minutes anyway. UPDATE … SET n = n + 1 puts 35k writes a second on a database, thousands on the hottest row — lock contention exactly when you need the count.

Good: exact counts in a stream processor. Partition the search events by query in Kafka, count each query in one-minute windows in a stream processor such as Flink, compare each count with that query’s usual rate, and emit the risers. The cost is state: a five-minute peak window holds about 10.4M searches, perhaps 4M distinct and mostly one-offs that will never trend. At about 80 bytes each that is 320 MB per window, per language bucket, and one global list means shipping all those counts to one place.

Great: sketches and heavy hitters. Each partition keeps a fixed-size summary per window instead of a counter per query.

• A count-min sketch is a grid of counters, d rows by w columns. Each row has its own hash function; an event adds 1 to one cell per row, and the estimate for a query is the minimum of its d cells. Cormode and Muthukrishnan prove that the estimate never undercounts and, with probability at least 1 − δ, overcounts by at most ε × N, using w = ⌈e/ε⌉ and d = ⌈ln 1/δ⌉ (paper). With the estimates’ 27,183 × 7 counters (0.76 MB), the error in a five-minute peak window is at most about 1,040 searches. Keep items whose estimate crosses a threshold in a small heap, and you have the heavy hitters.
• Space-Saving keeps m counters with their keys. A tracked query increments its counter; an untracked one takes over the smallest counter and inherits its count plus one. Every count overestimates by at most N ÷ m, any query searched more than N ÷ m times is guaranteed to be tracked, and the list adapts on its own when popularity shifts (Metwally et al.). With m = 10,000, the bound is 10.4M ÷ 10,000 ≈ 1,040 — the same as the sketch, but deterministic, and you get the keys for free.

Either way, each partition sends a summary of a few megabytes to a merger once a minute, instead of millions of counts. Count-min sketches built with the same hash functions merge by adding their grids cell by cell. (This counting problem has its own walkthrough: design top-K trending; the sketches are explained in count-min sketch and HyperLogLog.)

Deciding what is trending. Raw volume is not enough — “ind vs pak” is always big. Compare each candidate’s short-window count with what its base score predicts: if “ind vs aus live score” usually gets about 400 searches in five minutes and now gets 16,000, its trend ratio is 40. Promote a query when the ratio is at least 5, the count is well above the sketch’s error (say 2,000, nearly twice the 1,040 bound), and at least 500 distinct people searched it — a HyperLogLog per candidate counts them in about a kilobyte, so a few bots cannot manufacture a trend. Publish the top 20,000 entries once a minute; each fades out about 30 minutes after its ratio drops.

Merging at query time. The trending list is about 20,000 × 50 B = 1 MB, so each server keeps it as a small trie of its own. For each request it looks up the prefix in both structures and inserts at most two trending matches into the base list, ranked by max(base score, boost × recent rate). The cap means even a successful manipulation takes only two of ten slots, and trending items pass the same serve-time block filter. Google may hold back predictions after breaking news when reliable content is unlikely to exist yet (Google, 2020); a “trending and sensitive” classifier belongs here.

End to end: an event reaches Kafka within a second, the one-minute window closes, the merger publishes within 30 seconds, and the CDN’s 60-second cache expires — about three minutes in the worst case, inside the five-minute target.

How do we serve 200k requests a second within 100 ms?

Start from the budget. A phone’s round trip to a nearby edge on a mobile network is perhaps 20–60 ms; parsing and drawing should fit in one 16 ms frame; that leaves the backend about 10 ms at p99. The cheapest request is the one that never crosses the network, so work outwards in.

The client is the first cache.

• Debounce briefly. Send a request only after about 100 ms without a keystroke. A typist at 40 words a minute presses a key every 300 ms (40 × 5 characters = 200 a minute), so the wait rarely delays a normal typist but collapses bursts from fast typists, pastes and autocorrect. A 300 ms debounce would feel sluggish: the point is to answer within the pause.
• Drop stale answers. The response for “iph” can arrive after the one for “ipho”. Cancel in-flight requests when a new one is sent, and draw only a response whose q matches the current text.
• Cache by URL. With max-age=60, backspacing to a prefix you just saw costs nothing — about 10% of requests.
• Filter locally when the list is complete. If “iphone 16 pro m” came back with complete: true (fewer than ten completions exist), every longer prefix is a subset of that list.
• Prefetch on focus. Fetch history and the empty-prefix list (trending searches) when the box gets focus, as Facebook did with each user’s connections.

Facebook dark-launched its new typeahead by making the old one send a query on every keystroke, and found network limits that changed the architecture before launch (Facebook, 2010). Load-test the keystroke pattern, not the search pattern.

The CDN is the second. Because the response carries no user identity, the same URL returns the same bytes for everyone in a bucket, so a CDN can serve it — the reasoning that let Facebook keep non-personalised results in a memcached query cache. Short prefixes are a small, hot set: 52,059 per bucket × about 40 language-region buckets ≈ 2.1M objects of about 1 KB, roughly 2 GB per edge location. A 60-second TTL bounds staleness, stale-while-revalidate keeps latency flat when entries expire, and HTTP/2 or HTTP/3 keeps one warm connection across keystrokes. Skip WebSockets: millions of mostly idle sockets on your servers, and no CDN (see real-time connections).

The origin is the third. Each server keeps an in-process LRU of the 100,000 hottest responses as ready-encoded JSON, which skips the merge and encoding for popular prefixes; misses walk the index in microseconds. The rest is ordinary caching.

Should the index be sharded or copied?

• Bad: shard by first letter or by prefix range. Traffic is wildly uneven across letters — far more queries start with “s” than with “x” — and it moves: a phone launch makes everything under “i” hot for a week. You cannot add capacity to one letter, so the busiest range sets the size of the whole fleet.
• Good: hash the first three characters onto a consistent-hashing ring. Every prefix of three or more characters lives entirely on one shard, so each request goes to exactly one shard, and the hash spreads hot neighbourhoods apart. Prefixes of one or two characters — 37 + 37² = 1,406 per bucket — come from a tiny table copied to every node and cached at the CDN. Hot shards get extra replicas. This is the plan when the index outgrows a server’s RAM (more on sharding).
• Great, here: copy the whole index to every server. At 15 GB it fits, so any server answers any prefix. Adding capacity means adding a replica; losing a server loses capacity, not data; there is no scatter-gather and no hot shard. You pay in RAM — everything on every server, twice during a swap — and in shipping every snapshot everywhere. Elasticsearch gives the same advice for its completion suggester: a single-shard completion index performs best unless heap usage forces a split. When you must split, split first by language and region bucket, which follows traffic and never needs a cross-shard query.

How do we personalise and localise suggestions?

Google lists the signals its predictions consider beyond popularity: the query’s language, where it comes from, trending interest and the person’s past searches (Google Search Help). Facebook split its typeahead into a cacheable global service and a per-user graph service; LinkedIn splits generic from network typeahead. The lesson is the same: keep the shared part and the personal part separate.

Bad: compute personal suggestions on the server. Put the user ID in the request and blend history on the server. Now nothing is cacheable: all 189k requests a second reach the origin instead of 117k, each with a history read.

Good: blend on the server with a history cache. Keep recent history in a fast cache keyed by user. It cuts the database reads, but the responses are still personal and still bypass the CDN.

Great: split by cacheability. Everything shared — national, regional and language signals — goes into one response keyed by URL. Everything personal stays on the device and is merged there: up to two matching history entries first, marked as recent, then the server list without duplicates, cut to ten.

Localisation lives in the index:

• Language buckets. Each query belongs to one bucket by script and language, so buckets partition the 100M queries rather than copying them. Latin-script Hinglish such as “mobile ka cover” lives in en-IN.
• Regional lists. For each state, keep the queries whose share of searches there is well above that state’s share of all searches. If 30% of “kurti chikankari” searches come from Uttar Pradesh, which sends 8% of all searches, its regional lift is 0.30 ÷ 0.08 = 3.75. Keeping about 1M such queries per state × 30 states adds about 3 GB — part of the 15 GB per server. The server answers with the bucket list re-ranked by score × (1 + β × lift).
• Context boosts. A shopping app can boost the category being browsed the same way; Elasticsearch’s context suggester multiplies a suggestion’s weight by category or geo boosts.
• Transliteration. Store extra input keys per suggestion. “कुर्ता” gets the Latin keys “kurta” and “kurtaa”, so typing “kurt” finds it, and the display text follows the user’s script.

History is personal data: on the device by default, synced only on opt-in, deletable everywhere, and never in the global index except through the crowd threshold.

How do we keep suggestions safe and handle typos?

A prediction is read as something the product is saying. Google’s published policies bar violent, sexually explicit, hateful, harassing or dangerous predictions, with extra rules for elections and named people, enforced in two layers: automated systems, and teams that remove what slips through along with close variations (Google Search Help). A legal takedown in one country adds a third shape of rule: scoped to a region.

Bad: a word list applied only at serve time. Filtering each response leaves holes — if four of the ten stored suggestions are blocked, users see six — costs CPU on every request, and leaves the blocked strings sitting in the index and in every cache.

Good: filter at build time. Run classifiers and rules over the candidates before the lists are computed, so a blocked query never takes a slot and lists fill from the next best. But a takedown now waits up to an hour for the next build plus the CDN’s TTL, and the trending path bypasses the build altogether.

Great: both, plus a purge. The build applies the full rule set. Servers hot-load a small urgent list, pushed within 60 seconds, and apply it to base and trending results. Each node stores twelve completions instead of ten (100M lists × 8 B = 0.8 GB more), so dropping two still leaves a full list. The rules service also purges the CDN for every prefix of the blocked query — only 20 prefixes per bucket for a 20-character query. Urgent rules fold into the next build. Match after normalising case, accents, spacing and look-alike digits (“s3x”), so variations are caught too.

Privacy is part of safety. The distinct-user threshold already keeps one person’s query from reaching anyone else. Add pattern filters for things that must never be suggested even if many people type them — phone numbers, email addresses, 10-digit PNRs and 12-digit ID numbers. Public numbers are different: a 5-digit train number such as “12951” → “12951 running status” is searched by thousands of people and is exactly what the box is for.

Typos. Someone types “iphnoe”, or “mobail kavar”.

• Bad: no tolerance. An empty dropdown on the very query the user cares about.
• Good: try every one-edit variant. For an 8-character prefix over 37 symbols there are 8 deletions, 8 × 36 = 288 substitutions, 9 × 37 = 333 insertions and 7 transpositions: 636 lookups, about 636 × 2 µs ≈ 1.3 ms. Acceptable for one edit; two edits multiply that into hundreds of thousands.
• Great: walk the index with an edit budget. A Levenshtein automaton accepts exactly the strings within k edits of the input; intersecting it with the trie or FST explores only branches that can still match. Lucene replaced a scan of every term with this approach and made fuzzy queries about 100 times faster (McCandless, 2011). Elasticsearch’s completion suggester exposes it as fuzzy prefix completion, allowing one edit from 3 characters and two beyond 5 by default.

Run the exact lookup first and fall back to fuzzy matching only when it returns fewer than ten results, then rank fuzzy hits below exact ones. For Hinglish, normalise both the indexed keys and the typed prefix — collapse doubled vowels, map common phonetic pairs such as “ph” and “f” — and let edit distance catch the rest.

The final design

Put the pieces together. The read path is the client, the CDN and the suggest servers; everything that learns, counts or filters runs beside it.

Follow one keystroke, and then one search, through the system:

1. Type. After a 100 ms pause the client sends GET /v1/suggest?q=iph&lang=en&region=IN-MH, unless its own cache or a complete list already has the answer.
2. Edge. The CDN answers if this URL was fetched in the last 60 seconds — almost always for one- to three-character prefixes. A miss goes to the nearest suggest region.
3. Look up. A suggest server checks its cache of hot responses, else walks its radix trie to “iph”, reads the stored list, merges up to two trending matches, drops anything on the urgent list and returns ten with Cache-Control: public, max-age=60. The client puts matching history first.
4. Search. When the user submits, the search service writes a search event — normalised query, hashed user, language, region, suggestion picked — to Kafka.
5. Trend. The trending job counts events with count-min sketches, checks trend ratio and distinct users, and publishes about 20,000 trending queries to every server each minute.
6. Aggregate. Hourly, the batch job counts each user once per query, decays old scores and applies the distinct-user threshold and full block rules.
7. Swap. The builder writes, validates and uploads a snapshot with twelve completions per node; servers download, warm and test it, then swap one pointer, one server first. Rollback is pointing at the previous snapshot.
8. Protect. Block rules feed every build and push an urgent list to servers within 60 seconds, purging the CDN for every prefix of a newly blocked query.

Check it against the requirements. Latency: a lookup costs microseconds and the server about 1–2 ms in total, so p99 is set by the network; over 40% of requests never reach the origin. Throughput: 210k requests a second at peak become about 117k at the origin, which 12 servers handle and 24 handle with room for a cricket final or a lost zone. Freshness: trending within about three minutes, base scores hourly, takedowns within a minute. Availability: the read path depends on nothing but its own memory; if the pipelines stop, servers keep serving the last snapshot, and if the suggest service is down entirely, the search box still works without suggestions. Safety: every suggestion passes a crowd threshold and two filters.

What interviewers look for by level

Follow-up questions

What if the index no longer fits on one server?

Fifty languages, regional variants and a billion candidates can push a server’s copy past a few hundred gigabytes. Before splitting, try an FST — a few times smaller for a little more CPU — and tighter thresholds. Then split by language and region bucket: a natural, traffic-proportional shard that no request ever crosses. Inside a big bucket, hash the first three characters onto a consistent-hashing ring and copy the one- and two-character prefixes everywhere.

What if we need product or people suggestions with pictures and prices?

That is entity typeahead, and it changes two things. Results are IDs hydrated with fresh price, stock and picture at request time, as Facebook’s web tier hydrated and privacy-checked each result ID. And candidates come from a catalogue, not logs, so updates are near real time, as in LinkedIn’s Cleo. Keep query completion as is and add an entity tier: a small per-category index returning a few top entities, shown in their own section of the dropdown. For a shop, this is where typeahead meets product search.

What if users type a word from the middle of the query?

“live score ind” should find “ind vs aus live score”, but a prefix trie matches only from the start, and indexing every word-suffix grows it three- to four-fold yet still misses out-of-order words. Add a second tier: an inverted index from word prefixes to query IDs, each list sorted by score; intersect the lists for the typed words, treating the last as a prefix, and stop at ten hits. LinkedIn’s Cleo matches out-of-order prefixes this way, with a Bloom filter per document to discard non-matches cheaply, and answered in about 20 ms over 150M members; Elasticsearch’s search_as_you_type field does the same with shingles and edge n-grams, scoring in-order matches higher. Use it only to fill a short list, and require two characters per word so “s” is never intersected.

What if a court orders a suggestion removed in one country?

Add a block rule scoped to that country, with the order as its reason. It reaches every server’s urgent list within a minute — applied only to requests from that region — the CDN entries for its prefixes in that country’s buckets are purged, and the next hourly build removes it there for good. Keep an audit trail, and match normalised variants so a change of spacing does not bring it back.

What if bots try to push a query into suggestions?

Manipulation means making a query look popular. Defend on both paths: count distinct users rather than searches, require a minimum number of distinct users and a spread across regions and networks, ignore traffic flagged by your bot detection, and cap trending to two slots per list. Watch for sudden rises concentrated in a few IP ranges or new accounts, and keep a human review queue for trending entries that match commercial or political patterns.

What if users are on a slow 2G connection or offline?

Lean harder on the device. Ship a small on-device index — say the top 10,000 queries for the user’s language as a compact trie or FST of a few hundred kilobytes — refreshed weekly, plus history. Answer instantly from it and replace the list when the network answer arrives, if it arrives in time. Increase the debounce on slow connections so the few requests that are sent are the ones that matter.

How to say it in the interview

“I’ll design query autocomplete for a big search box: 200 million daily users, a billion searches a day, and up to ten suggestions per keystroke in under 100 milliseconds.

The key number: every search becomes about six suggestion requests, so roughly 70 thousand requests a second on average and 210 thousand at peak. So I precompute everything and make serving a lookup.

The index is a radix trie where every node stores its top completions, computed at build time. A lookup walks a few nodes and reads one list — microseconds, even for ‘s’. For 100 million queries it’s about 10 gigabytes, so every server holds a full copy and I scale by adding replicas, not shards.

An hourly batch job counts each user once per query, applies exponential decay with a one-week half-life, keeps queries enough distinct people searched, applies block rules, and builds an immutable snapshot that servers swap in with canaries and one-step rollback. For trending, a stream job counts searches with count-min sketches, finds queries rising many times faster than usual, and pushes a small list every minute that servers merge in — at most two slots.

The client debounces for 100 milliseconds and caches by URL, and the response carries no user identity, so the CDN caches short prefixes. Personal history is merged on the device. Language and region are part of the URL and the index.

Finally, safety: block rules at build time, an urgent list at serve time with a CDN purge, privacy thresholds and number patterns, and fuzzy matching with a Levenshtein automaton only when exact matching comes up short.”

Concepts used in this design

• Search data structures — tries, radix trees and inverted indexes behind every option in the first deep dive.
• Types of search — how prefix, fuzzy and full-text search differ.
• Count-min sketch and HyperLogLog — counting trending queries and distinct users in fixed memory.
• Design top-K trending — the heavy-hitters problem behind the trending path.
• Batch vs stream processing — the hourly path and the one-minute path, and why you need both.
• Kafka — the search-event log both paths read.
• Flink and stream processing — windowed counting for trending.
• Content delivery network — serving short prefixes from the edge.
• Caching 101 — browser, edge and in-process caches, and what makes a response cacheable.
• Hot keys, cache stampede and invalidation — hot prefixes and purging blocked suggestions.
• Consistent hashing — spreading prefixes over shards if the index outgrows a server.
• Database sharding — why range sharding creates hot shards.
• Elasticsearch — the completion suggester and search_as_you_type, if you would rather not build the index yourself.
• Blob storage — where logs and index snapshots live.
• Real-time connections — why plain HTTP beats WebSockets for this traffic.
• Back-of-envelope estimation — turning daily users into keystroke QPS.

References and further reading

1. The Life of a Typeahead Query (Facebook Engineering, 2010)engineering.fb.comBrowser-side bootstrapping and caching, a stateless aggregator over leaf services, a memcached cache for non-personalised results, and the 100 ms “stutter” budget.
2. Cleo: the open source technology behind LinkedIn’s typeahead search (LinkedIn Engineering, 2012)linkedin.comGeneric versus network-aware typeahead; out-of-order prefix matching with a prefix inverted index, per-document Bloom filters and a forward index; about 20 ms on average over 150 million members.
3. How Google autocomplete predictions are generated (Google, 2020)blog.googlePredictions come from common and trending real searches, adjusted for language and location; freshness for rising interest; automated filtering plus enforcement teams.
4. How autocomplete works and its policies (Google Search Help)support.google.comThe signals autocomplete considers (language, location, trending interest, past searches) and the policy categories predictions must not violate.
5. Suggester examples: completion suggester (Elasticsearch reference)elastic.coA heap-resident, FST-backed completion suggester: weighted inputs, size 5 by default, fuzzy prefix options, category and geo contexts with boosts.
6. Search-as-you-type field type (Elasticsearch reference)elastic.coShingle and edge n-gram subfields for prefix and infix completion, queried with a bool_prefix multi_match that rewards in-order matches.
7. Using Finite State Transducers in Lucene (Mike McCandless, 2010)blog.mikemccandless.comAn FST as a compact sorted map that shares prefixes and suffixes: 9.8 million terms in 69 MB, built in about 8 seconds.
8. Lucene’s FuzzyQuery is 100 times faster in 4.0 (Mike McCandless, 2011)blog.mikemccandless.comReplacing a scan of every term with a Levenshtein automaton intersected with the term dictionary; automata built for 1 and 2 edits.
9. An Improved Data Stream Summary: The Count-Min Sketch and its Applications (Cormode and Muthukrishnan)web.archive.orgWidth ⌈e/ε⌉ and depth ⌈ln 1/δ⌉, never-underestimating point queries, and finding heavy hitters with a sketch plus a heap.
10. Efficient Computation of Frequent and Top-k Elements in Data Streams (Metwally, Agrawal and El Abbadi)cs.ucsb.eduThe Space-Saving algorithm: m counters, overestimation at most N/m, and automatic adaptation when popular items change.