Design Search Autocomplete

Design the suggestion dropdown under a search box. As a user types, the system suggests the most likely complete queries for what they have typed so far, for example typing wea shows "weather today" and "weather radar".

The search engine has hundreds of millions of daily users and every few keystrokes triggers a request, so the suggestion service sees far more traffic than search itself and must answer faster than a person types. Suggestions should reflect what people actually search for, react within minutes when something new starts trending, and never show offensive or dangerous completions.

In 45 minutes, size the traffic, choose a data structure and how it is built and updated, design the serving path, and explain how you keep suggestions both fast and fresh.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Data & Infrastructure · problem 36 of 70

Ask before you design. Try answering each yourself, then compare.

1. How many suggestions, and ranked by what?
   Typical answer

   Up to 10, ranked mainly by recent popularity of the full query; personalisation is a follow-up.

2. Prefix match only, or also typo tolerance and mid-word matches?
   Typical answer

   Prefix match on the normalised query for the core design; spelling correction is out of scope.

3. What scale should we plan for?
   Typical answer

   500 million daily users, about 10 searches each, and roughly 4 suggestion requests per search after client debouncing.

4. How fresh must suggestions be?
   Typical answer

   Trending queries should appear within about 10 minutes; the long tail can update daily.

5. What latency do we need?
   Typical answer

   Under 100 ms end to end at p99, so the server budget is about 20 ms.

6. One language or many?
   Typical answer

   Many languages and regions; each locale gets its own suggestion data.

Requirements

Functional

• Return up to 10 suggested queries for a typed prefix, per locale.
• Rank suggestions by recent popularity, with fast-rising queries surfaced within minutes.
• Filter out offensive, dangerous or legally removed phrases.
• Collect submitted queries to keep the data up to date.

Non-functional

• Server-side p99 under 20 ms; end-to-end under 100 ms.
• About 230,000 suggestion requests per second on average and 500,000 at peak.
• 99.99% availability; serving degrades to stale suggestions, never to errors.
• Trending queries visible within 10 minutes; blocked phrases removed within minutes.

Out of scope

• The search results themselves.
• Spelling correction and personalised history (follow-ups).

Back-of-the-envelope estimates

• Suggestion reads: 500 M users × 10 searches × 4 requests ≈ 20 B a day ≈ 230,000 per second, about 500,000 at peak.
• Query log writes: 5 B searches a day ≈ 58,000 per second, roughly 100 bytes each ≈ 500 GB a day of raw logs.
• Distinct queries: only queries seen enough times to be worth suggesting, about 100 M per large locale after thresholding. At about 25 characters each, with top-10 lists stored as references at every node, a trie is roughly 30 to 60 GB, so it is split into a few shards and replicated.
• Cache: prefixes of 1 to 3 characters are a tiny keyspace (tens of thousands) but a large share of traffic; caching them at the edge removes perhaps 30% to 40% of requests.
• Servers: an in-memory lookup takes microseconds, so a node handles about 20,000 requests per second; 500,000 at peak needs about 25 nodes per replica set plus headroom, per region.

The read rate and latency target drive everything: answers must be precomputed and held in memory.

API

GET /v1/suggest?q=wea&locale=en-US&limit=10
    -> {prefix, suggestions:[{text, kind: popular|trending}], version}
    Cache-Control: public, max-age=60   (short prefixes)
(internal) QueryEvent {queryNorm, locale, ts, sessionHash, resultClicked}

The client debounces keystrokes by about 100 ms, cancels stale requests and caches answers per prefix, which roughly halves server load and keeps typing smooth.

Data model

• Query counts (wide-column store): (locale, query) -> hourly counts, decayed score, distinct_users, written by the aggregator.
• Trie snapshots (object storage): serialised per locale and prefix range, with a version. Each node stores its top-k completions as (score, query id). A base snapshot is rebuilt daily from 30 days of decayed counts; a delta snapshot is rebuilt every 5 minutes from the last few hours.
• Blocklist (relational, small): phrases and patterns with reason and owner, applied at build time and again at serving time for urgent removals.
• Shard map: prefix range to server group, for example a-ca, cb-f, balanced by traffic rather than alphabet.

High-level design

Read path: the search box sends the prefix to the CDN, which answers short, popular prefixes from its cache for about a minute. Misses go to the Suggest Router, which normalises the prefix, checks its Hot Prefix Cache, and forwards to the Suggest Servers shard that owns the prefix range. Each server holds its range of the base trie and the small delta trie in memory, walks to the prefix node, reads both precomputed top-k lists, merges them with a trending boost, applies the live blocklist, and returns. No disk or database is touched.

Write path: when a user submits a search, the Search Service emits a query event to Query Logs. The Query Aggregator normalises queries, counts each user at most once per query per window, drops rare or abusive ones, and upserts windowed counts into Query Counts.

Build path: the Trie Builder reads counts and the Blocklist, builds tries with top-k at every node, and publishes versioned Trie Snapshots: delta every 5 minutes, base daily. Servers load a new snapshot beside the old one and swap a pointer, so serving never pauses.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Top-k at every trie node

A plain trie answers a prefix by walking to its node and then exploring every completion below it, which for a one-letter prefix means millions of nodes. Instead, during the offline build, store at each node the best k completions in its subtree. A lookup is then a walk of length equal to the prefix plus reading a short list. Building is done bottom-up or by offering each query to every node on its path, keeping a bounded list. Memory grows by k entries per node, so store small integer query IDs, cap depth at about 30 characters, and stop storing lists at very deep nodes where few completions exist.

Freshness with a base and a delta

Rebuilding a 50 GB structure every few minutes is wasteful. Split it: a large base trie built daily from long-window decayed counts, and a small delta trie rebuilt every 5 minutes from only the last few hours, containing perhaps a million queries. At serve time, combine the two top-k lists, giving recent counts a boost relative to their window. A query that suddenly spikes appears within one delta cycle. Because both are immutable snapshots, loading is a background file read and an atomic pointer swap, with no locks on the hot path.

Sharding and hot prefixes

Sharding by first letter is badly skewed: far more queries start with 's' than 'x'. Use prefix ranges chosen from traffic data so each shard gets similar load, and replicate each shard many times since the data is read-only. Short prefixes are the hottest keys of all and their answers change slowly, so cache them at the CDN and in the router, and let only longer, rarer prefixes reach the servers. Each replica set lives in every region, keeping the round trip short.

Safety and manipulation

Suggestions are a public, editorial surface. Filter at build time against a maintained blocklist and classifiers for hate, sexual content and dangerous queries, and again at serve time so a removal takes effect in minutes without a rebuild. Count distinct users rather than raw searches and require a minimum number of distinct users before a query can be suggested, which makes it much harder for a small group or a bot to push a phrase. Unusually fast-rising queries can be held for review before entering the delta trie.

Failure modes

• If a suggest server dies, the router sends its prefix range to other replicas; the data is read-only, so nothing is lost.
• If the build pipeline fails, servers keep serving the last good snapshots; suggestions go stale but stay available.
• If a bad snapshot is published, servers validate size and sample queries before swapping, and operators can pin the previous version.
• If the query log stream backs up, trending suggestions lag; serving is unaffected.
• If a region's suggest cluster is overloaded, the router sheds load by returning cached or empty suggestions, since search still works without them.

Core algorithm in code

import heapq


class Node:
    __slots__ = ("children", "top")

    def __init__(self):
        self.children = {}
        self.top = []      # best (score, query) pairs under this prefix, highest first


class SuggestTrie:
    """Trie that stores the top-k completions at every node, built offline."""
    def __init__(self, k=5):
        self.k, self.root = k, Node()

    def build(self, scores, blocklist=()):
        blocked = [b.lower() for b in blocklist]
        for query, score in scores.items():
            q = " ".join(query.lower().split())
            if any(b in q for b in blocked):
                continue
            node = self.root
            self._offer(node, score, q)
            for ch in q:
                node = node.children.setdefault(ch, Node())
                self._offer(node, score, q)

    def _offer(self, node, score, query):
        # keep a sorted list of at most k entries; k is tiny, so insertion is cheap
        node.top.append((score, query))
        node.top.sort(key=lambda t: (-t[0], t[1]))
        del node.top[self.k:]

    def suggest(self, prefix):
        node = self.root
        for ch in " ".join(prefix.lower().split()) if prefix.strip() else "":
            node = node.children.get(ch)
            if node is None:
                return []
        return list(node.top)


def merged(base, delta, prefix, boost, k):
    combined = {}
    for score, q in base.suggest(prefix):
        combined[q] = combined.get(q, 0) + score
    for score, q in delta.suggest(prefix):
        combined[q] = combined.get(q, 0) + boost * score
    return heapq.nlargest(k, ((s, q) for q, s in combined.items()))


daily = {"weather today": 9_000, "weather tomorrow": 6_500, "west coast trail": 1_200,
         "web hosting": 4_000, "webcam test": 2_100, "wedding dresses": 3_300,
         "weather radar": 5_200, "wet hacker leaks": 8_000}
last_hour = {"webb telescope images": 900, "weather radar": 300}

base, delta = SuggestTrie(k=4), SuggestTrie(k=4)
base.build(daily, blocklist=["hacker leaks"])
delta.build(last_hour)
for p in ["we", "wea", "web", "xyz"]:
    print("%-4s base   %s" % (p, [q for _, q in base.suggest(p)]))
print("web  merged", [(round(s), q) for s, q in merged(base, delta, "web", boost=10, k=4)])
print("wea  merged", [(round(s), q) for s, q in merged(base, delta, "wea", boost=10, k=3)])

Trade-offs

• Precomputed top-k per node gives microsecond lookups but multiplies memory and requires offline rebuilds.
• A base plus delta design gives freshness cheaply but needs a merge rule that can be hard to tune.
• Edge caching short prefixes removes much traffic but delays trending changes by the cache TTL.
• Distinct-user thresholds resist manipulation but hide genuinely new, rare queries for a while.
• Range sharding by traffic balances load but needs rebalancing as query patterns shift.

What a strong answer shows

• Quantifies the read rate and concludes answers must be precomputed and served from memory.
• Stores top-k at trie nodes (or an equivalent prefix-to-list map) and explains the memory cost.
• Separates the serving path from collection and building, with versioned snapshots and atomic swaps.
• Addresses freshness with a frequent small build or streaming layer merged with a stable base.
• Handles skew through traffic-based sharding, replication and edge caching of short prefixes.
• Treats filtering and manipulation resistance as requirements.

Mistakes to avoid

• Querying a database with LIKE 'prefix%' on every keystroke.
• Traversing the whole subtree at request time to find the best completions.
• Updating a shared trie in place from the live query stream, causing lock contention and inconsistent reads.
• Sharding by first character and ignoring the skew.
• Counting raw searches, which lets bots push phrases into suggestions.

Follow-ups to expect

• How would you add personalisation? (Merge a small per-user history list client-side or from a user store with the global list.)
• How would you tolerate typos? (Generate candidate prefixes within edit distance 1 for longer prefixes, or a separate fuzzy index.)
• How do you support a new locale with little data? (Fall back to a related locale, lower thresholds, curated seeds.)
• How would you measure quality? (Acceptance rate of suggestions, keystrokes saved, and A/B tests of ranking changes.)

Practice next