Design search autocomplete

Search suggestions for a shopping app, shown before the user types the next letter. The answer is a prefix index that already stores the top 10 suggestions for every prefix. It is rebuilt offline from search logs, kept in memory and cached at the CDN.

Design the search box suggestions for a shopping app with 20 million daily users. As a user types "ata", they should see popular completions such as "atta 5kg" and "atta multigrain", fast enough to feel instant.

Requirements

Functional

  • Return up to 10 suggestions for a typed prefix, ranked by popularity.
  • Suggestions reflect the last few weeks of searches. Trending terms show up within about an hour.
  • Blocked or offensive terms never appear.
  • Support common Hinglish spellings for top queries through a hand-made list of aliases.

Non-functional

  • Server time p99 under 20 ms (99 out of 100 requests are faster). End to end under about 150 ms on 4G, inside the gap between keystrokes.
  • Peak of about 15,000 suggestion requests per second.
  • 99.9% available. If suggestions fail, the search box shows no suggestions and search still works.
  • Freshness: a full rebuild every day, plus an hourly layer for trending terms.

Out of scope

  • Ranking of the search results page itself.
  • Suggestions personalised to each user (a good follow-up).
  • A learned spelling-correction model.

Estimate

  • Searches: 20M users x 3 searches a day = 60M searches a day.
  • Suggestion calls: with a ~100 ms debounce, about 4 calls per search: 60M x 4 = 240M a day = ~2,800/s average; peak ~5x = ~14,000/s.
  • Distinct queries: keep queries seen at least 5 times in 30 days, say ~5M of them, ~20 characters each.
  • Index size: at most 5M x 20 = 100M prefixes, far fewer after sharing, say ~20M. Storing top 10 at each prefix: 20M x 10 x ~16 bytes (id + score) = ~3.2 GB, plus suggestion strings (5M x 20 B = 100 MB). Fits in RAM on one server; replicate the whole index rather than shard it.
  • Hot prefixes: 1 to 3 character prefixes are only tens of thousands of keys but take a large share of traffic, so an edge cache with a 10-minute TTL absorbs much of the load.
  • Bandwidth: 10 suggestions x ~40 bytes = ~0.5 KB per response; 14,000/s x 0.5 KB = ~7 MB/s. Trivial.

API

  • GET /suggest?q=ata&limit=10&locale=en-IN -> 200 {q, suggestions: [{text, kind}]}
  • GET /search?q=atta+5kg -> 200 {results[]} (logs the query for the index builder)
  • PUT /admin/blocklist/{term} -> 204
  • DELETE /admin/blocklist/{term} -> 204

Data model

  • query_log(ts, session_id, query, clicked): stream, then hourly files in object storage
  • query_counts(query, day, count): batch output, 30-day window
  • prefix_index: prefix -> [(suggestion_id, score)] top 10, built as a versioned snapshot file
  • blocklist(term PK, added_by, added_at); aliases(alias PK, canonical_query)

A request, step by step

  1. The app waits about 100 ms after a keystroke (a debounce), then calls GET /suggest with the normalised prefix: lowercased and trimmed. Short prefixes are answered from the CDN cache. The rest go to a suggest server.
  2. The suggest server looks the prefix up in its in-memory index. The index already stores the top 10 for every prefix, so the server returns them directly. No sorting happens at request time.
  3. Each request carries a sequence number. The app shows a response only if it matches the current text. So a slow answer for "at" never replaces the answer for "ata".
  4. Every real search is logged to the query stream. The builder adds up counts over 30 days, giving recent days more weight. It drops rare and blocked queries, adds aliases, builds the prefix index, and publishes a versioned snapshot file.
  5. Suggest servers load the new snapshot in the background and switch to it in one step. An hourly trending layer adds rising queries that the daily build has not seen yet.

Deep dives

The data structure: from LIKE queries to a top-k prefix index

Weak: a SQL query for every keystroke. "SELECT query FROM counts WHERE query LIKE 'ata%' ORDER BY count DESC LIMIT 10" can use the B-tree index to find matching rows. But a short prefix like "a" matches hundreds of thousands of rows, and all of them must be sorted. At 14,000 requests per second, the database cannot keep up.

Good: a trie in memory. A trie is a tree where each step down adds one letter. Walk down to the node for "ata", then search everything below it for the 10 most popular completions.

This is fast for long prefixes but slow for short ones. Everything below "a" is a huge part of the tree.

Great: a trie, or a compact prefix map, with the top 10 stored at every node. A request walks at most about 20 steps, then reads a list that is already built. That takes microseconds, whatever the prefix length. Building the index happens offline, where cost does not matter.

Store it compactly. Keep suggestion ids at each node instead of full strings, or use a finite-state transducer (a compressed structure for sets of strings). Then the whole index fits in a few GB, and every server holds a full copy.

Trade-off: precomputing makes reads very fast but updates expensive. One count changing can change the top 10 of every prefix of that query. That is why the index is rebuilt and swapped, never updated in place on each search.

Freshness: offline build plus a trending layer

Weak: update counts on every search, inside the request. Each search would rewrite the top 10 of up to 20 prefixes, under a lock, on a serving path that should only read.

It also lets a script that runs a thousand searches push any phrase to the top in seconds.

Good: a daily batch build. Add up 30 days of query logs with a time decay, so yesterday counts more than last month. Apply a minimum count and the blocklist. Build the index and publish a snapshot that servers switch to.

This is simple, dependable and easy to roll back: point the servers back at yesterday's version.

Great: the daily batch plus a small streaming layer for trending terms. A stream job counts queries over the last hour. It flags queries that are rising much faster than their usual rate, such as a new phone launch or a festival item.

Those go into a tiny overlay index, merged with the main results at query time. Cap how many trending items can appear. Count unique sessions, not raw searches, so one bot cannot create a fake trend.

Trade-off: you now have two paths to maintain and merge. In return, suggestions react within the hour, while the main index stays a simple, well-tested file that never changes after it is built.

The latency budget and caching

The real time budget is the gap between keystrokes, roughly 100 to 200 ms. On a 4G phone, the network uses most of it.

Weak: call the server on every keystroke and show whatever arrives. You send several times more requests than needed. Responses can also arrive out of order, so the suggestions jump back to an older prefix.

Good: debounce on the client: wait about 100 ms after the last keystroke before calling. Cancel or ignore old responses using a sequence number. Keep the server lookup in memory, so server time is a few milliseconds.

Great: also cache by prefix at every layer. Short prefixes are few and very popular. Cache them at the CDN for about 10 minutes, because they change slowly.

The app can keep the last results and filter them on the phone while the next call is in progress. The results for "at" already include some of the ones for "ata". Serve each user from the nearest region.

Trade-off: caching makes the most popular prefixes up to ten minutes out of date. It also makes blocklist changes slower to take effect. So when a term is blocked, the system must also purge (delete) the affected prefixes from the CDN.

What breaks

  • A bad snapshot is published, for example empty or missing the blocklist. Servers check its size and run spot checks before switching. If the checks fail, they keep the old version. A rollback is one pointer change.
  • Suggest servers are overloaded. The CDN keeps serving cached short prefixes. The app hides suggestions on a timeout, and search still works.
  • The query log pipeline stops. The index only gets older. Alert when the index is more than 36 hours old.
  • An offensive suggestion appears. Add it to the blocklist. The blocklist filters at serving time immediately and purges CDN keys, without waiting for the next build.

What each level is expected to cover

Mid level: Uses a trie with the top results stored at each node. Builds it offline from query logs and serves it from memory on several replicas. Debounces on the client and caches popular prefixes. Does the size estimate that shows the index fits in RAM.

Senior: Also designs the trending layer and protection against abuse. Adds snapshot checks and rollback, and a fast path for the blocklist. Explains how personalisation or more languages would fit on top without changing the serving core.

Common mistakes

  • A LIKE prefix query on the database for every keystroke.
  • Finding the top results at request time by walking everything under the prefix.
  • Updating the index inside each search request.
  • Ignoring responses that arrive out of order on the client.
  • No blocklist, or a blocklist that only takes effect at the next daily build.

Follow-up questions

  • How would you personalise suggestions for a user who mostly buys baby products?
  • How would you handle typos like "aata", or Hindi queries in Devanagari?
  • The index no longer fits in one server's memory. How do you shard it?
  • How do you stop a competitor from pushing a phrase into suggestions?
  • What would you measure to know the suggestions are actually helping?

Lessons behind this answer