Design search autocomplete (typeahead)

A naive trie lookup walks to the prefix node and then traverses the whole subtree to find the most popular completions. For a one-letter prefix that subtree has millions of entries, which is far too slow per keystroke. The standard fix is to precompute: at build time, store the top K (say 10, sometimes 20 to allow reranking) query ids at every node. A lookup then costs O(length of prefix) to find the node plus O(K) to read the answer, a few microseconds. The memory cost is K ids per node; cap prefix length (~30 characters) and only include queries above a popularity threshold to keep it to tens of GB. Two practical encodings: a hash map from prefix string to a top-K list (simple, slightly more memory), or a compact trie/FST (finite-state transducer, as used in Lucene's suggesters) which shares prefixes and suffixes and is much smaller. Because the index is rebuilt and loaded as a read-only snapshot, there is no locking and no in-place update; freshness comes from rebuilding and from the separate trending layer, not from mutating the trie per query.

Popularity changes slowly for most queries, so a daily (or hourly) batch rebuild is enough. The score should favour recent activity: sum daily counts with exponential decay (for example a half-life of 7 days), so last year's news fades. Use click-through as a quality signal: a query people type often but never click results for may be broken or spam. Filtering is part of the build, not an afterthought: remove bots, PII patterns, adult and hateful content, and legally sensitive terms, and keep a manual blocklist that is also applied at serve time so urgent removals work within a minute. For trends, a streaming job (Flink) counts queries in sliding windows (e.g. last 15 minutes) and compares them with the usual rate for that query; queries whose rate jumps (a new phone, a breaking news name, a match) are written to Redis with a score. At request time, the server merges trending matches for the prefix into the precomputed list. This two-layer design (stable batch index plus small real-time overlay) avoids rebuilding the big index every minute.

The cheapest request is the one never sent. Debounce on the client (~100-150 ms), reuse results within a session (typing 'iph' after deleting back from 'ipho'), and cancel stale requests. Short prefixes are a small set but a large share of traffic, and their answers are the same for everyone, so cache them at the CDN with a TTL of minutes; vary only by locale. Personal suggestions are fetched separately or merged server-side so they never pollute shared caches. Behind the CDN, the whole index (tens of GB) fits on one large-memory server, so the simplest scaling is full replicas behind a load balancer: add replicas for QPS, place them in each region for latency. If the index outgrows a server (many languages, many markets), shard by prefix range or by locale; sharding by first character is skewed ('s' and 'a' are huge), so use ranges chosen from the data or a hash of the first 2-3 characters. Each shard has several replicas. Index loads happen in the background with the old version serving until the swap, and only part of the fleet reloads at a time.

The precomputed list is a candidate set; final ranking blends signals: global decayed popularity, trending boost, the user's own recent searches (strong boost when they match), and context such as the current category page on a shopping app. Keep personalisation light and fast: a user's last 50 queries can be prefix-matched in memory in microseconds. Indian users type in many ways: Hinglish in Latin script ('saree under 500'), Devanagari ('साड़ी'), and inconsistent transliterations ('kurta', 'kurtha'). Handle this by normalising scripts, adding transliteration variants as aliases in the index so a Latin-script prefix can match a Hindi query, and mining query reformulations from logs ('kurtha' followed by 'kurta' means they are the same intent). For typos, exact prefix matching is best for the first 3-4 characters; for longer prefixes, an edit-distance-1 lookup over the FST (Lucene's fuzzy suggester does this) recovers 'iphnoe' to 'iphone'. Measure success with suggestion click-through rate and keystrokes saved, not just latency.

Precomputing makes lookups trivial and fast but uses more memory and makes updates a rebuild. Computing at query time (Elasticsearch completion or edge n-grams with sorting) is flexible but slower and costlier at 150k req/s. Precompute for the global list; compute small personal and trending parts live.

Updating the trie on every query needs locking and makes top-K maintenance complex. A batch snapshot plus a small trending overlay keeps the hot path read-only and still reflects trends within minutes.

Caching shared responses at the CDN removes most load, but personalised responses cannot be shared. Split global and personal suggestions, cache the global part, and merge on the client or in a thin server step.

Full replicas are simplest and avoid fan-out when the index fits in RAM. Shard only when memory forces it, and choose prefix ranges based on traffic, not alphabet letters.

A launch or match sends many users typing the same few prefixes. CDN caching of short prefixes absorbs most of it; make sure the CDN TTL is not so long that trending suggestions are hidden (use a shorter TTL for trending-heavy locales during events).

More markets and languages grow the index past one machine. Shard by locale first (natural boundary), then by prefix range; or prune by a stricter popularity threshold.

Loading a new 20 GB snapshot while the old one is serving needs double memory. Provision for it, or use memory-mapped files so the OS pages the new index in gradually.

The client times out after ~200 ms and shows no suggestions; search still works. Recent searches stored on the device can still be shown.

Validation gates block obviously bad builds; if one slips through, roll back to the previous snapshot version in minutes and apply the serve-time blocklist immediately.

Suggestions fall back to the batch index only; slightly stale but correct. Alert on trending job lag.

Skip the trending and personal merge with a tight timeout and serve the precomputed list.