Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

System Design HLD-19.10

Design search autocomplete

Design search autocomplete: offline aggregation of query logs, a top-k per prefix index served from memory, browser and CDN caching, and trending blends.

Intermediate 18 min Last reviewed

The problem

You type "sy" into a search box and, before you type the next letter, a list appears: "symptoms of flu", "system design interview", "sydney weather". Every keystroke is a request, the answer must arrive faster than the next keystroke, and the suggestions must reflect what millions of people are searching for, including what started trending an hour ago.

The key insight is that almost none of this work should happen when you type. The suggestions for "sy" are the same for everyone (before personalization) and change slowly, so they can be computed in advance from query logs, stored as a ready-made answer per prefix, and cached at every layer between the index and your browser. The design is mostly about the offline pipeline that builds that index and the caches that serve it.

Requirements

Functional

  • Return up to 10 suggestions for a prefix, ranked by popularity.
  • Suggestions update as people's searches change: daily for the main index, within an hour for trending queries.
  • Filter out offensive, illegal or personal suggestions.

Non-functional

  • Scale: 100 million daily users, 10 searches each a day, about 6 suggestion requests per search after debouncing.
  • Latency: under 100 ms end to end, so the server's share must be a few milliseconds.
  • Availability: if autocomplete fails, search still works; it can degrade silently.

Out of scope

Estimates

  • Requests: 100M x 10 x 6 = 6 billion a day, about 69,000 per second on average and roughly 200,000 at a 3x peak.
  • Cache potential: short prefixes are shared by everyone. There are only 26 one-letter and 676 two-letter lowercase prefixes, and they carry a large share of the traffic, so browser and CDN caches absorb most requests.
  • Index size: index the 10 million most popular queries. Each query of up to 20 characters contributes at most 20 prefixes, so at most 200 million prefixes, and far fewer in practice because prefixes are shared. Storing 10 suggestion ids (4 bytes each) plus overhead per prefix, about 60 bytes, gives at most about 12 GB: it fits in memory on one machine, so we replicate rather than shard at first.
  • Log volume: 1 billion searches a day at about 100 bytes is 100 GB a day of logs for the aggregation job.

API

GET /v1/suggest?q=sy&locale=en-US
  200 OK
  Cache-Control: public, max-age=3600
  { "prefix": "sy", "suggestions": ["symptoms of flu", "system design interview", "sydney weather", ...] }

The response for a prefix and locale is identical for everyone, which is what makes it cacheable by the browser and the CDN. Clients debounce: they wait about 100 to 150 ms after a keystroke before asking, so fast typists do not send a request per letter.

Data model

  • Query counts (offline, in a data warehouse): (query, day) -> count, built from search logs.
  • Suggestion index (online, in memory): prefix -> [top 10 query ids], plus query id -> text. Built as an immutable snapshot by the offline job and loaded by servers. Either a trie with the top list stored at each node ( Typeahead and autocomplete ) or a plain hash map from prefix to list; at this size, the hash map is simpler and just as fast.
  • Trending counts (streaming): (query, 5-minute window) -> count for the last few hours.
  • Blocklist: terms and patterns that must never be suggested.

High-level design

Autocomplete: serving, offline build and trending paths Serving path: the browser checks its cache, then the CDN, then an autocomplete server, which answers from an in-memory prefix index. Offline path: search logs are aggregated daily into query counts with time decay; an index builder filters them, computes the top suggestions per prefix and publishes an index snapshot that servers load. Trending path: a stream processor counts queries in the last hour and the server blends rising queries into the answer. ?q=sy on miss publish load blend Browser debounce + cache CDN per prefix Suggest servers index in memory Search logs Daily aggregation counts + decay Index builder filter, top-k Index snapshot versioned Trending last hour Stream counter 5-min windows Figure 1. The expensive work happens offline. At request time a server only looks up a precomputed list, and most requests never reach it because browsers and the CDN cache answers per prefix.
  1. Serving path After a short debounce the browser asks for the prefix. Its own cache or the CDN usually answers. On a miss, a suggest server looks the prefix up in its in-memory index, a single hash lookup, and returns the stored top 10.
  2. Offline build Every day, a batch job aggregates search logs into decayed counts per query, filters blocked and rare queries, computes the top 10 for every prefix and publishes a versioned snapshot. Servers download it and swap it in atomically.
  3. Trending path A stream processor counts queries in 5-minute windows. Queries rising much faster than their usual rate are stored as trending, and servers blend a few of them into the precomputed list for matching prefixes.

Deep dives

Deep dive 1: Building the index offline

Counting raw searches would make last year's events dominate forever. Weight each day's count by its age instead, for example halving the weight every 7 days, so the score reflects recent popularity. Then, for each query, add it to the candidate list of each of its prefixes and keep the top k. Here is the whole job on a tiny log:

topk.pyruns with python3 (standard library)
# Offline job: turn a query log into top-k suggestions per prefix,
# weighting recent days more (half-life of 7 days).
from collections import defaultdict

log = [  # (days ago, query, searches that day)
    (20, "system design", 900), (2, "system design", 400),
    (1, "system design interview", 500), (0, "system design interview", 600),
    (30, "symphony tickets", 3000), (0, "synonym for fast", 300),
    (0, "symptoms of flu", 700), (1, "symptoms of flu", 650),
    (10, "syntax error", 800), (3, "sydney weather", 450),
]
HALF_LIFE, K, MAX_PREFIX = 7, 3, 10

score = defaultdict(float)
for days_ago, q, n in log:
    score[q] += n * 0.5 ** (days_ago / HALF_LIFE)

index = defaultdict(list)            # prefix -> [(score, query)]
for q, s in score.items():
    for i in range(1, min(len(q), MAX_PREFIX) + 1):
        index[q[:i]].append((s, q))
for p in index:
    index[p] = sorted(index[p], reverse=True)[:K]

for prefix in ("sy", "sym", "sys"):
    tops = ", ".join(f"{q} {s:.0f}" for s, q in index[prefix])
    print(f"{prefix!r:5} -> {tops}")
print("prefixes stored:", len(index), "for", len(score), "queries")

Output

'sy'  -> symptoms of flu 1289, system design interview 1053, system design 452
'sym' -> symptoms of flu 1289, symphony tickets 154
'sys' -> system design interview 1053, system design 452
prefixes stored: 47 for 7 queries

"symphony tickets" had the most searches, 3,000, but 30 days ago, so its score decayed to 154 and it ranks below queries searched this week. Seven queries produced 47 prefixes, which is why the job caps prefix length (here 10 characters): long prefixes are rare, and the client can fall back to the longest stored prefix and filter locally.

At real scale this is a distributed batch job ( Stream processing ): a map step emits (prefix, query, score) and a reduce step keeps the top k per prefix. Before publishing, filter suggestions through the blocklist and drop queries searched by too few distinct users, which removes accidental personal data such as someone's phone number typed into the search box.

Deep dive 2: Serving fast

The server's work is one hash lookup, so its latency is dominated by the network. The real design questions are where answers are cached and how the index reaches servers:

  • Browser cache: as you type "sys" and backspace to "sy", the answer for "sy" is reused. Responses carry Cache-Control with a lifetime of about an hour.
  • CDN: short prefixes are requested by everyone, so the CDN ( Content Delivery Networks ) answers most of them from the edge, near the user.
  • Servers: hold the full index in memory, replicated across many machines and regions. If the index outgrows one machine, shard by prefix range, for example a-f, g-m, with care for skew: far more queries start with "s" than with "x", so shard boundaries follow measured traffic, not the alphabet.
  • Index updates: snapshots are immutable and versioned. A server loads the new one alongside the old, then swaps a pointer, so there is never a half-updated index, and rolling back is loading the previous version.

A daily index misses breaking news. A stream processor counts each query in short windows and compares the last hour with its usual rate. Queries growing sharply are written to a small trending store; at request time the server merges a couple of trending matches into the precomputed list. The blend is cheap because both lists are short.

Personalization works the same way: the client or server merges the user's own recent searches into the shared list. Keep personal data out of the shared, cached response, and add it in a second, uncached step, or on the device itself, so caches never serve one user's history to another.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Pick a one-letter prefix and compare reading the stored top list with walking the whole subtree. How many nodes does each visit?
  2. Choose a longer prefix. Why does the stored list matter less as the prefix grows?
  3. The stored lists cost memory at every node. Using the estimates above, would you store them at every depth or only up to 10 characters?

Bottlenecks and failure modes

FailureImpactMitigation
Keystroke stormRequest per letter overwhelms serversClient debounce, browser and CDN caching
Bad index publishedWrong or offensive suggestionsValidation checks before publishing; instant rollback to previous snapshot
Offline job failsIndex goes staleKeep serving the last good snapshot; alert on index age
Offensive trending queryHarmful suggestion spreads fastBlocklist on the trending path; human review for high-volume trends
Skewed prefix shardsOne shard hotShard boundaries by measured traffic; replicate hot shards
Personal data in suggestionsPrivacy leakMinimum distinct users per query; no personal data in cached responses

Trade-offs we made

OptionWins whenLoses when
Precomputed top-k per prefix (chosen) Constant-time serving, trivially cacheable Index is hours old; memory for every prefix
Compute from the trie at request time Always current, less memory Subtree walks for short prefixes; harder to cache
Daily batch plus trending stream (chosen) Stable main index and fast reaction to news Two pipelines to run and keep consistent
Replicate the whole index (chosen) Any server answers any prefix Each server must hold the full index

Extensions

  • Spelling tolerance: suggest "system design" for "sytem des" using edit-distance candidates.
  • Multiple languages and regions, each with its own index and blocklist.
  • Entity suggestions with images or categories (people, places, products).
  • Learning to rank suggestions by click-through, not just search counts.

In the wild

Where you will see this: web search engines, online shops, maps and app stores all suggest completions as you type, and code editors do the same for symbols. The shape is consistent: precompute popular completions, serve them from memory, cache aggressively at the edge, and blend in fresh or personal signals at request time.

Check yourself

  1. Why can autocomplete responses be cached by a CDN?

    Show answer

    B. Before personalization, the answer for a prefix is the same for everyone and changes slowly Identical answers for all users make each prefix a perfect shared cache key.

  2. A query had 3,000 searches a month ago and none since. Why might it rank lower than a query with 1,000 searches yesterday?

    Show answer

    B. Counts are weighted by age, so old searches count less Time decay keeps suggestions reflecting recent popularity.

  3. How should a new index snapshot reach the servers?

    Show answer

    B. Load it alongside the old one and swap atomically, keeping the old for rollback Immutable, versioned snapshots avoid half-updated indexes and make rollback trivial.

  4. Why should the client debounce keystrokes?

    Show answer

    B. To avoid a request per letter from fast typists, cutting load sharply Waiting about 100 ms after the last keystroke drops most intermediate prefixes.

Recap

  • Do the work offline: aggregate logs with time decay into top-k suggestions per prefix.
  • Serve with one in-memory lookup from immutable, versioned index snapshots.
  • Debounce on the client and cache per prefix in the browser and CDN.
  • Blend trending and personal suggestions at request time, keeping personal data out of shared caches.
  • Filter blocked terms and rare queries before anything is published.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up