Design Search Autocomplete (Typeahead)

Type "ipl" into a search box and, before you finish, the box suggests "ipl schedule" and "ipl points table". That small feature runs on every keystroke of every user, must respond faster than the user can type the next letter, and has to know what millions of other people searched for recently. It is one of the clearest examples of a pattern you will see again in large systems: heavy work done offline, so the online path is a simple lookup.

• How to estimate a per-keystroke workload.
• Why per-keystroke database queries fail, and what to precompute instead.
• Tries and prefix tables with top-K suggestions.
• The offline pipeline from search logs to serving snapshots.
• How client debouncing, client caches and CDNs remove most load.
• How to add trending freshness, shard and replicate the index.
• Privacy and content filtering for suggestions.

Design the autocomplete service for a search box used by a large consumer app (for example a shopping or travel app). As the user types, show up to 10 suggested complete queries for the current prefix, ranked by popularity, including queries that are trending right now.

Functional requirements: return up to 10 ranked suggestions for a prefix and locale; include trending queries quickly; never return blocked or offensive suggestions.

Non-functional requirements

50 million DAU; 2 searches per DAU per day -> 100 million searches/dayTyped characters per search: about 12, but the client debounces (waits ~100 ms after the last  keystroke) and skips requests it can answer from its own cache: assume 4 requests per searchSuggestion requests: 400 million/day -> about 4,600/s average, about 14,000/s peak (factor 3)Without debouncing: 1.2 billion/day -> about 14,000/s average, about 42,000/s peak

Index size (assumptions):

Keep the 20 million most popular distinct queries per locale (a long tail is cut off)Prefixes stored: up to 15 characters; overlapping prefixes are shared, so assume about  60 million distinct prefixesPer prefix: 10 suggestions referenced by id (10 x 4 bytes) + prefix key and overhead (~60 bytes)  -> about 100 bytes x 60 million = about 6 GB, plus the query strings (20M x 30 B = 600 MB)Total: under 10 GB per locale

Conclusions: the whole index fits in memory on one server (with replicas for throughput and availability); request rates are moderate after debouncing and much lower at the origin after caching. The challenge is latency and freshness, not volume.

GET /v1/suggest?q=ipl&locale=en-IN&limit=10200 OKCache-Control: public, max-age=300{ "prefix": "ipl", "suggestions": ["ipl schedule", "ipl points table", "ipl tickets", ...] }

• The prefix is normalised (lower-cased, extra spaces trimmed, Unicode normalised) before lookup and in the cache key.
• Responses are identical for all users (personal recent searches are merged on the device), so they are cacheable by browsers and CDNs. MDN's guide explains how Cache-Control directives such as public and max-age control shared caching (HTTP caching).
• An empty list is a valid answer.

Offline (aggregation) data:

query_counts (locale, query, window_start, searches, distinct_users)   aggregated from search logs; daily and hourly windowsblocklist (locale, term or pattern)

Online (serving) data, one of two structures:

• Prefix table: a hash map prefix -> [top 10 query ids] plus an array of query strings. One hash lookup per request. Simple, fast, easy to shard.
• Trie with cached top-K: a tree where each node is a character, and each node stores the top 10 completions beneath it. One walk down the trie per request (length of the prefix). More compact when prefixes share long beginnings; slightly more complex to build and update. The DSA course's article Tries and Prefix-Based Search explains the data structure.

Both are a materialised view of the aggregated counts, rebuilt by the pipeline (article 27; Microsoft's Materialized View pattern describes this kind of precomputed, read-optimised data (Materialized View pattern)).

Search box --> API --> SELECT query FROM queries                       WHERE query LIKE 'ipl%' ORDER BY searches DESC LIMIT 10

With a B-tree index on query, the LIKE 'prefix%' range scan works (article 13), but the database must still scan every matching query to sort by count: for "i" that is millions of rows, on every keystroke, at 14,000 requests per second.

1. Short prefixes match huge numbers of queries; sorting them per request is far too slow.
2. Database load from per-keystroke queries.
3. Latency: even 50 ms of server time is too slow for typing.
4. Freshness: counts change constantly; recomputing on every search is wasteful.

The fix is to move the expensive part (counting and choosing the top 10 for every prefix) offline, and make the online request a single lookup.

This Java program shows the offline step on a handful of queries with made-up counts: for each prefix of each query (up to 15 characters), keep the 3 most searched queries. The online step is then a single map lookup.

// File: PrefixIndex.javaimport java.util.ArrayList;import java.util.HashMap;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;public class PrefixIndex {    // Offline step: for every prefix of every query, keep the top K queries by count.    static Map<String, List<String>> build(Map<String, Long> counts, int k, int maxPrefixLength) {        Map<String, List<String>> index = new HashMap<>();        for (String query : counts.keySet()) {            for (int len = 1; len <= Math.min(maxPrefixLength, query.length()); len++) {                index.computeIfAbsent(query.substring(0, len), p -> new ArrayList<>()).add(query);            }        }        for (List<String> candidates : index.values()) {            candidates.sort((a, b) -> {                int byCount = Long.compare(counts.get(b), counts.get(a));   // most searched first                return byCount != 0 ? byCount : a.compareTo(b);              // then alphabetical            });            if (candidates.size() > k) {                candidates.subList(k, candidates.size()).clear();            }        }        return index;    }    public static void main(String[] args) {        Map<String, Long> counts = new LinkedHashMap<>();   // query -> searches in the last 7 days        counts.put("india vs australia", 920_000L);        counts.put("ipl schedule", 1_450_000L);        counts.put("ipl points table", 1_100_000L);        counts.put("indigo flight status", 610_000L);        counts.put("income tax slab", 480_000L);        counts.put("iphone price", 700_000L);        counts.put("indian railway pnr status", 830_000L);        Map<String, List<String>> index = build(counts, 3, 15);        // Online step: one lookup per keystroke.        for (String typed : new String[] {"i", "in", "ind", "ip", "ipl p", "xyz"}) {            System.out.println("\"" + typed + "\" -> " + index.getOrDefault(typed, List.of()));        }        System.out.println("prefixes stored: " + index.size());    }}

"i" -> [ipl schedule, ipl points table, india vs australia]"in" -> [india vs australia, indian railway pnr status, indigo flight status]"ind" -> [india vs australia, indian railway pnr status, indigo flight status]"ip" -> [ipl schedule, ipl points table, iphone price]"ipl p" -> [ipl points table]"xyz" -> []prefixes stored: 81

Seven queries produced 81 prefixes; real systems handle millions by building in parallel (for example in a batch-processing framework), and by capping prefix length and dropping rare queries.

Search service --> search events (query, locale, user id hash, time) --> event stream   |                                                                        |   |                        +--------------- hourly / daily ---------------+   v                        vRaw logs in object storage -> Aggregation job: normalise queries, count searches and distinct users                              per window, apply time decay, drop rare and blocked queries                           -> Index builder: prefix -> top 10 per locale                           -> Validate (size, sample checks, blocklist) -> versioned snapshot in object storage                           -> Serving nodes download and swap in the new version

• Time decay: weight recent searches more (for example, last 7 days with older days counting less), so seasonal and stale queries fade.
• Versioned snapshots: each build is a complete, immutable file with a version number. Serving nodes load it into memory alongside the current one and swap atomically, so a request never sees a half-built index; rolling back means swapping to the previous version.
• Validation gates stop a bad build (empty, wildly different size, blocked terms present) from being published.

A daily rebuild misses a query that becomes popular in the last hour ("train accident" news, a sudden match result). Add a fast path:

• A stream processor counts queries per locale over sliding windows of, say, 15 minutes and 1 hour, from the same event stream (an event stream such as Kafka keeps events ordered per partition and retains them for replay (Introduction to Kafka)).
• Queries whose recent rate is far above their usual rate are marked trending, filtered (blocklist, minimum distinct users) and published as a small delta (thousands of queries), every few minutes.
• Serving nodes merge the delta at lookup time: for a prefix, combine the snapshot's top 10 with trending queries matching the prefix, and re-rank.

• Serving nodes hold the index in memory (under 10 GB per locale), behind a load balancer. Each node holds a full copy, so any node can answer any prefix: no routing, simple failover. Add nodes for throughput and zones.
• If the index ever grows beyond one machine (many locales, longer prefixes), shard by hash of the prefix (not by first letter, which is very uneven: far more queries start with "s" than with "x").

• Debounce on the client: send a request only after the user pauses typing for about 100 ms, and cancel in-flight requests when a newer keystroke arrives.
• Client-side cache: keep results for prefixes already fetched in this session; when the user deletes a character, the previous prefix's results are already there.
• Edge caching: responses are the same for everyone, so a CDN caches popular prefixes (a CDN serves requests from edge locations near users (Amazon CloudFront)). Short prefixes, which are the most requested, hit the cache almost always; max-age of a few minutes balances freshness. The origin sees mostly long-tail prefixes.
• Minimum prefix length of one or two characters, depending on the language.

REQUEST PATHDevice (debounce, local cache, merge my recent searches)  -> CDN (popular prefixes cached for minutes)  -> Load balancer -> Suggest servers (in-memory index snapshot + trending delta) -> responseASYNC PATHSearch events -> stream -> (a) raw logs -> daily aggregation -> index build -> validate -> snapshot                         -> (b) streaming counts -> trending delta every few minutesSnapshots and deltas in object storage -> pulled by suggest servers -> atomic swap

Suggestions are eventually consistent by design: the snapshot is hours old, trending deltas are minutes old, CDN copies minutes old. Different servers may briefly serve different versions during a rollout. All of this is acceptable for suggestions. What must be prompt is removal: a takedown of an offensive or harmful suggestion is pushed as a blocklist delta to servers immediately and purged from the CDN.

• Personal data in logs: people search for names, phone numbers, addresses and order ids. Never suggest a query unless it was searched by at least a minimum number of distinct users (a k-anonymity-style threshold), and drop queries matching patterns of personal data (phone numbers, email addresses, ids).
• Offensive and harmful content: curated blocklists and classifiers applied before publishing, with a fast takedown path.
• Manipulation: coordinated searches to push a phrase into suggestions; count distinct users per window, discount new or suspicious accounts, rate-limit search events.
• Raw logs are retained briefly, access-controlled and pseudonymised (hashed user ids).
• Personal suggestions (my recent searches) stay on the device or in the user's own account data, never in the shared index.

"Autocomplete returns up to ten ranked suggestions for each prefix within about 100 ms of a keystroke. With 100 million searches a day and client debouncing, that's roughly 14,000 requests a second at peak before caching.

All heavy work happens offline: search events flow into a stream and logs; a daily job normalises queries, counts searches and distinct users with time decay, drops rare, personal and blocked queries, and builds a prefix-to-top-10 table per locale, under 10 GB. Each build is validated and published as a versioned snapshot that suggest servers load into memory and swap atomically. A streaming job publishes a small trending delta every few minutes, merged at lookup time.

Online, each request is one hash lookup in memory. Most requests never reach us: clients debounce and cache, and the CDN caches popular prefixes for a few minutes because responses are the same for everyone. Servers are full replicas behind a load balancer. If autocomplete fails, search still works. The main risks are privacy and abuse, handled with distinct-user thresholds, blocklists and fast takedowns."

No debouncing: 100M x 12 = 1.2 billion/day -> 13,900/s avg -> about 41,700/s at peakDebounced:     100M x 4  = 400 million/day -> 4,630/s avg -> about 13,900/s at peakWith an 80% CDN hit ratio on the debounced traffic: 20% reaches servers -> about 2,800/s at peak

• Next: Design a Distributed Job Scheduler, which runs pipelines like this one reliably.
• Later: Design a Web Search Engine extends these ideas to full-text search over billions of documents.