Design: search autocomplete

The full lesson, with a worked example: Design: search autocomplete. Misspellings get their own walk-through in Shopping search.

Requirements

Functional

• Top suggestions per prefix: 5 to 10 for whatever is typed so far.
• Ranking: mostly by popularity, nudged by the user's city and past searches.
• Freshness: trending terms within minutes, not days.
• Forgiving: common misspellings, and both English and Indian scripts.
• Safe: nothing offensive, dangerous or defamatory, ever.

Non-functional

• Fast: people press a key every 150 to 300 ms, so the round trip must be under about 100 ms, with a p99 not much worse.
• Stale is fine, slow is not: suggestions an hour old are acceptable.
• Optional: if the suggest service fails, the search box still works without suggestions.
• Out of scope (say so): the full search results page and its ranking.

Estimates

• Requests: 50 crore searches a day × about 4 requests each (thanks to waiting for pauses) = 200 crore a day ≈ 23,000 a second, about 1 lakh at the evening peak.
• Reads vs writes: almost all reads. The only writes are search logs, processed in the background.
• Time budget: of 100 ms, the mobile network takes 40 to 60 ms. Servers get well under 50 ms, which rules out real searching at typing time.
• Index size: keep the top 1 crore distinct queries. They share prefixes, giving about 5 crore distinct prefixes. At about 60 bytes each (prefix plus a top-10 list of query ids): 5 crore × 60 ≈ 3 GB. Fits in one machine's memory.
• Consequence: don't shard first. Keep a full copy on each of many servers and spread requests across them.
• Cache payoff: a few lakh hot prefixes cover most requests, so a hit rate of 80 to 90% is realistic.

API

• GET /v1/suggest?q=biryani%20h&lang=en&city=hyd&limit=10: returns the prefix it answered plus a list of suggestions, each with text, kind (popular, trending, recent) and an optional id to deep-link.
• The response carries cache headers by prefix length: say 10 minutes for one or two letters, 1 minute for long prefixes.
• Personal boosts need the user, so personalised calls skip the shared CDN cache, or the app merges the user's recent searches on the phone itself.
• DELETE /v1/users/:id/search-history: let people clear what personalises their list.
• Internal: POST /v1/suggest/blocklist lets trust and safety remove a suggestion everywhere within minutes.

Data model

• search_log events: query, normalisedQuery, userId (hashed), city, ts, clickedResult, orderPlaced. Streamed, then kept in cheap storage.
• query_stats: normalisedQuery → decayed count, distinct users, click rate, last seen. Built by the batch job.
• prefix_index: prefix → ranked list of up to 10 query ids. The served snapshot, about 3 GB, versioned (for example v2026-10-21T14).
• queries: queryId → display text per script.
• trending: city + prefix → a short list of sudden risers, with a few minutes' expiry.
• blocklist and misspelling map (briyani → biryani), applied when building.

Store prefixes up to about 20 to 30 characters and drop queries below a count threshold. Both keep the index small.

High-level design

1. 1

   PhoneCDN edge

   Pause after "bir": suggestions?

2. 2

   CDN edgePhone

   Hit: 5 suggestions in about 30 ms

3. 3

   PhoneCDN edge

   Pause after "biryani h"

4. 4

   CDN edgeSuggest service

   Miss: pass it on

5. 5

   Suggest servicePrefix index

   Top 10 for "biryani h" (about 2 ms)

6. 6

   Suggest servicePhone

   Blended with city and history, about 75 ms

7. 7

   PhoneSearch logs

   Chose "biryani house", clicked a shop

8. 8

   Search logsPrefix index

   Counted in the next rebuild

• Search logs record every finished search and what was clicked next. This is the raw material.
• The offline builder, a batch job, counts queries, removes junk and unsafe terms, and writes the prefix index with every list already ranked. That is precomputation: ranking happens once an hour, not once per keystroke.
• The suggest service loads the snapshot into memory and answers with one lookup, blending in local and personal hints.
• Caches in three layers: on the phone, at the CDN edge in the user's city, and in the service's memory.
• The phone waits for a pause before asking, drops stale answers, and remembers recent ones.

Deep dives

Trie with top-k at each node

A trie is a tree of letters: "b" → "bi" → "bir". Walking every query under "bi" and sorting is far too slow, because there could be lakhs. So the builder stores the top 10 at every node. Answering "bi" is a two-step walk and one read.

Many teams flatten this at serving time into a plain map from prefix to top-10 list in a key-value store or in-process map. The tree is only used to work out the lists.

The client does half the work

• Debounce: wait about 150 ms after the last key. "b-i-r" typed quickly sends one request, not three. That alone can halve load.
• Cancel overtaken requests and tag each answer with its prefix. Show an answer only if it matches what is in the box now, so a slow reply for "bi" cannot overwrite "bir".
• Remember recent answers so backspacing and retyping costs nothing.

Caching close to the user

Popularity is very uneven: every search starts with one of a few dozen letters, so short prefixes are asked constantly. The hot keys that hurt other systems are a gift here, because they are the easiest to cache. An edge answers in 20 to 30 ms without touching your servers. Cache short prefixes longer and long prefixes briefly, so trending terms still get through.

Freshness and ranking

• Time decay: today counts fully, last week half, last year barely. Otherwise "ipl 2019 schedule" stays on top forever.
• Hourly rebuild: build a complete new snapshot, check it (size, a sample of known prefixes, the safety filters), switch every server at once, and keep the old one for rollback. Never update the live index in place.
• Trending layer: stream processing counts the last few minutes per city, spots sharp risers and serves them from a small layer merged at lookup time.
• Blend: the global list gets the most weight; city trends and the user's recent searches get a boost, never a takeover.
• Quality signals: weight queries that led to clicks or orders, and drop ones that return no results.

Safety, abuse and languages

• Safety: a blocklist, extra rules for a person's name paired with sensitive words, and a removal switch that works in minutes. The trending layer gets the strictest checks because it moves fastest.
• Gaming: count distinct users, not raw searches, so a script counts once. Ignore bot traffic and flag unnatural jumps.
• Misspellings: mine the logs for "searched X, got nothing, searched Y" pairs; add close matches within an edit distance of one or two at lower rank.
• Scripts: transliteration maps "बिरयानी", "biryani" and "biriyani" to one entry, so they share one count and show in the script being typed.

Trade-offs

• Fresh vs fast: precomputing makes reads instant but leaves suggestions up to an hour behind. The trending layer narrows the gap at the cost of another moving part.
• Cache time vs freshness: a 10-minute edge cache saves huge load but delays a new term by up to 10 minutes.
• Full copies vs shards: at 3 GB, copies are simplest and every server can answer anything. Shard only when the index outgrows memory.
• Personal vs private: history improves suggestions and also shows them to anyone looking at the screen. Keep boosts small, marked, and never from sensitive topics such as health.
• Coverage vs safety: more suggestions help more people and give more room for something unpleasant to slip through.

Interview talking points

• State the latency budget first: under about 100 ms per keystroke, half of it network.
• The sum: about a lakh requests a second at peak, an index of a few GB.
• The key shift: from "search on each keystroke" to "precompute top-k per prefix, then look up".
• Three cache layers, plus debounce and cancelling on the client.
• Decayed counts, hourly snapshots swapped in whole, and a trending layer.
• Safety filters, anti-gaming by distinct users, misspellings and scripts.
• Keep it away from the main database: the order database should never see a keystroke.

Follow-up questions

Why not walk the trie subtree at query time? Under a short prefix like "a" there could be lakhs of queries to sort on every keystroke. Storing the top 10 at each node turns it into a short walk and one read.

How would you shard it if it grew too big? By prefix range, with the hottest short prefixes copied to every shard. Splitting by first letter alone makes "s" and "a" shards far busier than "x".

How does a new trending term show up within minutes? Count recent searches in a stream per city, detect sharp rises, pass them through the safety filter, and merge them from a small trending layer at lookup time.

Answers arrive out of order. What do you do? Tag each request with its prefix, show only the answer matching the box, and cancel requests that have been overtaken.

How do you stop a seller gaming the suggestions? Count distinct users rather than searches, discard bot-like traffic, flag sudden unnatural jumps, and weight by clicks and orders, which scripts cannot fake cheaply.

How do you measure success beyond latency? The suggestion acceptance rate and keystrokes saved per search, alongside p99 latency and the edge hit rate.