Classic Case Studies

Design Search Autocomplete

In simple words

Like a shopkeeper who has memorised the ten most popular things people ask for, for every first few letters. You say "ma" and they instantly suggest "mangoes, masala, matches". No searching at the counter; the answers were prepared in advance.

Problem Statement

Design search autocomplete (typeahead): as a user types into a search box, show the top 5–10 suggested completions for the current prefix, ranked by popularity, updating on every keystroke. Think Google's search suggestions or an e-commerce search bar.

Functional Requirements

Given a prefix, return the top K (e.g. 10) completions.
Rank by popularity (query frequency), optionally boosted by recency and user context.
Suggestions reflect trending queries within a reasonable time (hours; minutes for trending).
Filter offensive or blocked terms.
Out of scope: spelling correction, full search results.

Non-Functional Requirements

Very low latency: under ~100 ms end-to-end, since it runs per keystroke.
High availability; results may be slightly stale.
Scale: 100M DAU × 10 searches × ~6 keystrokes → ~6B requests/day ≈ 70K/s, peak ~200K/s.

Core Entities

Query log entry: query text, timestamp, (locale, user).
Term frequency: normalised query → count over a window.
Suggestion index: prefix → top K completions.

API Design

GET /v1/suggest?q=how%20to%20ma&limit=10&locale=en-IN
-> 200 { "suggestions": ["how to make tea", "how to make money online", ...] }
   Cache-Control: public, max-age=300

High-Level Design (HLD)

Lookups are pure memory reads of precomputed top-K lists; the index is rebuilt offline from query logs.

SERVING (read path, hot)
browser (debounce ~100 ms, local cache of prefixes)
   -> CDN / edge cache (popular prefixes)
   -> Suggest service (in-memory trie or prefix->topK map, replicated)

BUILDING (offline / near-real-time)
search queries -> log -> [ queue ] -> aggregation (e.g. hourly counts, decayed)
               -> build job: compute top-K per prefix -> new index snapshot
               -> distribute snapshot to suggest servers (swap atomically)
trending path: streaming counts over the last minutes -> small "trending" overlay

Low-Level Design (LLD)

Lookup walks one node per typed character and returns the precomputed list: O(prefix length).

Trie with top-K cached at every node

            (root)
             |
             h
             |
             o  top: [how to make tea, how are you, hotel near me ...]
             |
             w  top: [how to make tea, how are you, how to lose weight ...]
            ...

Naive lookup: walk to the prefix node, then DFS the whole subtree and sort
              -> too slow for short prefixes ("a" has millions of completions)
Optimised:    store the top K completions at EVERY node during the build
              -> lookup = walk len(prefix) nodes + return a precomputed list
                 O(prefix length), independent of subtree size

Memory is the cost: every node stores K references. Limit prefix depth (e.g. 20 characters), drop queries below a frequency threshold, and shard the trie by first characters if it doesn't fit on one machine. An equivalent simpler structure is a key-value map prefix → [top K] for all prefixes of all popular queries, stored in Redis or a fast KV store.

Ranking and freshness

score(q) = sum over time buckets: count_in_bucket * decay^(age_in_buckets)
  e.g. decay 0.9 per day -> last week's burst fades, steady queries persist

Rebuild the main index every few hours from aggregated counts;
overlay "trending now" from a streaming top-K (count-min sketch + heap) per region.

Keeping latency low

Client: debounce keystrokes, cancel in-flight requests, cache results per prefix in the page.
Edge: short prefixes are few and extremely popular; cache them at the CDN for minutes.
Server: everything in memory; replicas behind a load balancer; no database on the read path.

Follow-up Questions

How do you update the trie without downtime?: Build a new immutable snapshot offline, ship it to servers, load it next to the old one and swap a pointer atomically; the old one is freed afterwards. No in-place mutation under load.
How do you personalise suggestions?: Merge the global top-K with a small per-user list (recent searches) and re-rank with user signals on the server; keep the global part cacheable and the personal part small.
How do you keep harmful suggestions out?: Filter at build time with a blocklist and classifiers, plus a fast takedown list checked at serving time so a bad suggestion can be removed in minutes without a rebuild.