System Design Primer · llms.txt
Beyond the primer: design questions
Written for this site, not part of The System Design Primer. The sources it draws on are listed under Further reading.
Autocomplete suggests whole queries while you type a prefix: type "how to bo" and you see "how to boil eggs", "how to boost wifi signal" and a few more. It saves keystrokes, steers people toward queries that return good results, and is one of the most latency-sensitive features a search product has, because it runs on nearly every keystroke.
In interviews it's a good test of whether you can separate an offline pipeline (turning query logs into ranked suggestions) from an online serving path (answering a prefix lookup in a few milliseconds), and whether you notice that the read path is so cacheable that most requests never reach your servers. It builds on the primer's cache and CDN chapters, and its offline half looks a lot like the primer's sales rank batch job.
Scope it first:
Research on response times going back decades puts the limit for "feels instantaneous" at about 100 ms. Suggestions that arrive after the user typed two more characters are useless. A rough budget from keystroke to rendered list:
| Step | Budget |
|---|---|
| Client wait before sending (debounce) | 0–50 ms |
| Network round trip to the nearest edge | 20–50 ms |
| Server lookup, p99 | under 10 ms |
| Render | under 10 ms |
The network dominates, which tells you where to spend effort: serve from as close to the user as possible, and avoid the round trip entirely when you can. The server lookup has to be an in-memory read, not a query that ranks anything on the fly.
These numbers are assumptions, chosen for round arithmetic:
About 32 GB fits in the memory of one large server. So you shard for throughput, fault isolation and multiple languages, not because the data is too big. That's worth saying out loud in an interview.
One read endpoint, designed to be cached:
GET /suggest?q=how%20to%20bo&lang=en®ion=us
200 OK
Cache-Control: public, max-age=900
["how to boil eggs", "how to boost wifi signal", "how to book a flight", ...]Normalize the prefix before it becomes part of the URL (lowercase, collapse whitespace, Unicode normalization), so "How To" and "how to" share one cache entry. There's no write API: suggestions come from the search logs, not from this endpoint.
The data model is a mapping from prefix to an ordered list of suggestions. The deep dive below compares two ways to store it. Offline, the pipeline also keeps a table of (query, window, count) aggregates that the index is built from.
Raw logs are too large to rank from directly. Aggregate them in time windows, for example hourly counts per normalized query, with a batch or streaming job (event streaming covers the streaming side).
From the windowed counts, compute a score that favors recent activity. Exponential decay is a common choice: each window's count is weighted by 0.5 ^ (age / half_life). With a 7-day half-life, a search from a week ago counts half as much as one today, and one from four weeks ago counts 1/16. A long half-life gives stable, slowly changing suggestions. A short one reacts faster and is noisier. You can keep two scores and blend them.
Before ranking, filter. Collapse spelling variants and near-duplicates. Drop any query typed by fewer than some minimum number of distinct users: rare queries are mostly noise, and they can contain personal information like names, addresses or order numbers. Then apply the safety filters described below.
Option 1: a trie with the top-k cached at each node. Each node is a character; a path from the root spells a prefix. A plain trie would make you walk the whole subtree under "how to bo" to find the best completions, which could be millions of nodes. So each node also stores its precomputed top 8. A lookup walks len(prefix) nodes and reads one list. Compact variants (radix trees, or the finite state transducers Lucene uses for its completion suggester) cut memory considerably.
Option 2: a flat prefix → top-k table. Precompute the answer for every prefix up to some maximum length and store it in a hash map or key-value store. A lookup is one key read.
| Trie with cached top-k | Prefix → top-k table | |
|---|---|---|
| Lookup | Walk ~20 nodes, read a list | One key read |
| Memory | Pointers per node; compact forms help a lot | Every prefix stored as a key; simple but larger |
| Sharding | By prefix range, so ranges must be balanced by traffic | Any key-based scheme, including hashing |
| Fits in a KV store or CDN | Needs a custom server | Naturally: key = prefix |
| Incremental updates | Change a count, fix lists up the path | Rewrite every affected prefix key |
Both store the top-k per prefix; they differ in how they're laid out and served. At this scale, rebuilding a snapshot offline and swapping it in makes the incremental-update column matter less. The flat table is often the easier interview answer because it's easy to shard, replicate and cache. The trie is the better answer when memory is tight or you want fuzzy matching, which walks neighboring branches.
Building the table is a straightforward batch job:
import heapq
from collections import defaultdict
def build_index(scores, k=8, max_prefix=25):
"""scores: dict of normalized query -> decayed score."""
heaps = defaultdict(list) # prefix -> min-heap of (score, query)
for query, score in scores.items():
for i in range(1, min(len(query), max_prefix) + 1):
h = heaps[query[:i]]
if len(h) < k:
heapq.heappush(h, (score, query))
elif score > h[0][0]:
heapq.heapreplace(h, (score, query))
return {p: [q for _, q in sorted(h, reverse=True)] for p, h in heaps.items()}At 50 million queries you'd run the same logic as a distributed job: emit (prefix, query, score) pairs, group by prefix, keep the top 8 per group.
Ship the result as a versioned, read-only snapshot. Suggest servers load the new version beside the old one and switch atomically, and rolling back is just loading the previous version.
Suggestions are the product putting words in the user's mouth, so the bar is higher than for search results. Most systems layer several defenses:
Filtering offline keeps the serving path fast. The serve-time removal list exists only for urgency.
With 32 GB of index and 83,000 requests a second at peak, the simplest setup is full replicas: every suggest server holds the whole index, and a load balancer spreads requests. If one server handles 20,000 lookups a second (an assumption; in-memory lookups are cheap, and most of the cost is the HTTP handling), five servers carry the peak and a few more give headroom and zone redundancy.
When the index outgrows one machine, for example once you add many languages, shard it:
The read path is ideal for caching: the same prefixes are requested constantly, responses are small, and they can be minutes stale.
Cache-Control: max-age of several minutes. When the user types "pyth", deletes the "h" and types it again, the second request never leaves the machine. See client caching.Cache lifetime is a trade-off between hit rate and freshness. A 15-minute TTL means a removed suggestion can survive at the edge for up to 15 minutes. Urgent removals need a CDN purge as well as an index change.
The client does a lot to cut load and hide latency:
A daily rebuild can't surface a news event that broke an hour ago. A streaming job counts queries in short windows (say 5 minutes) and flags queries whose rate is far above their usual baseline. Those go into a small trending overlay that the builder merges into affected prefixes, or that the suggest service merges at read time. Spikes are also where abuse shows up, since people try to push a phrase into suggestions with fake searches, so trending candidates need the same filters and some resistance to one source generating most of the volume (rate limiting helps there).
Personal signals (your own recent searches, your location) improve relevance but break caching: a response that depends on the user can't be stored at the CDN under a shared key. A common split is to keep the shared suggestions fully cacheable and merge personal ones on the client, from local history or a small per-user call that runs in parallel.
It gives badly uneven shards, because first letters aren't equally common and traffic is even more skewed than the data. With a flat prefix table you can hash the full prefix instead, since every lookup is a single key and no range queries are needed. If you keep a trie, split it into prefix ranges sized by measured traffic rather than by letter, and be ready to re-split. Also question whether you need to shard at all: about 30 GB fits in memory, so replicas may be enough.
Someone searched for a string containing it, and the pipeline kept it. A minimum count of distinct users per query should have dropped it, because a phone number is rarely searched by many different people; pattern filters for phone numbers and similar personal data are a second layer. To remove it now, add it to the serve-time removal list and purge the affected prefixes from the CDN, then make sure the next build excludes it.
The trend detector has to see the spike over at least one short window (say 5 minutes), then the overlay must reach the index. Even after the index changes, the CDN and browsers may keep serving the old response for "cele" for up to 15 minutes. So the worst case is roughly the detection window plus the overlay delay plus the TTL. If that's too slow, shorten the TTL for short, popular prefixes, or purge them when the overlay changes.
Suggest requests are mostly partial strings like "how to bo", which aren't queries anyone wants suggested. Their counts also reflect your own suggestions: people click what you show, which would reinforce whatever is already ranked first. Submitted searches are complete, intentional queries. Even those have some feedback loop from accepted suggestions, which is worth mentioning.
If the server merges personal history into the response, every response becomes unique to a user and can't be cached under a shared URL, so the hit rate collapses and the servers take the full load. Keep the shared suggestions endpoint unchanged and cacheable, and merge personal history on the client from local storage, or fetch it from a separate, uncached endpoint in parallel.
Cache-Control and max-age mean for browsers and shared caches.Previous: Design a chat system · Next: Design a video streaming platform