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.
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
- Spelling correction, personalization beyond a simple blend, and the search results themselves ( Inverted indexes and full-text search ).
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], plusquery 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) -> countfor the last few hours. - Blocklist: terms and patterns that must never be suggested.
High-level design
- 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.
- 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.
- 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:
# 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-Controlwith 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.
Deep dive 3: Trending and personal blends
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
Try this:
- Pick a one-letter prefix and compare reading the stored top list with walking the whole subtree. How many nodes does each visit?
- Choose a longer prefix. Why does the stored list matter less as the prefix grows?
- 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
| Failure | Impact | Mitigation |
|---|---|---|
| Keystroke storm | Request per letter overwhelms servers | Client debounce, browser and CDN caching |
| Bad index published | Wrong or offensive suggestions | Validation checks before publishing; instant rollback to previous snapshot |
| Offline job fails | Index goes stale | Keep serving the last good snapshot; alert on index age |
| Offensive trending query | Harmful suggestion spreads fast | Blocklist on the trending path; human review for high-volume trends |
| Skewed prefix shards | One shard hot | Shard boundaries by measured traffic; replicate hot shards |
| Personal data in suggestions | Privacy leak | Minimum distinct users per query; no personal data in cached responses |
Trade-offs we made
| Option | Wins when | Loses 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
-
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.
-
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.
-
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.
-
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.
Next up
- Crack the system design round learning path