Chapter 13 · System Design Fundamentals

Design a Search Autocomplete System

Suggest likely query completions while the user is still typing. The whole problem is shipping the right ranked list in under a hundred milliseconds — on every keystroke, for billions of keystrokes a day. The cleverness lives in the data structure and in when you do the work, not in the lookup.

Autocomplete looks like a trivial lookup and is anything but. It sits in the user's hot path: the box is on every page, and every character they type is a separate request. That flips the usual read/write ratio on its head — reads dwarf writes by orders of magnitude — and it makes latency the single hardest constraint. The design answer is to move all the expensive work off the request path: precompute answers offline, store them so a lookup is a pointer chase, and let a cache cascade absorb the traffic curve.

What the system must do Slide 2

Nail the constraints first, because they are what make an easy-sounding feature hard. The functional surface is small: given a prefix, return the top K matching queries ranked by popularity, updating as the user adds or deletes characters. The non-functional demands are where the design is decided — a strict latency ceiling, freshness measured in hours, and a request rate several times the underlying query rate because every keystroke fires.

A quick envelope (see Chapter 2): 10 M DAU × 10 queries/day × ~6 keystrokes each ≈ 600 M requests/day ≈ 7 K QPS average, 20–30 K at peak. Spelling correction, semantic search, and long-form completion are explicitly out of scope for the first cut.

The trie: a tree of shared prefixes Slide 3

The data structure is the design. A trie (prefix tree) stores strings one character per edge, so every query that shares a prefix shares a path down from the root. Finding "all queries starting with swi" is then just walking three edges — O(P) in the prefix length P — and reading the subtree hanging underneath. That prefix-sharing is the whole reason autocomplete can fit inside a latency budget at all.

Attach a frequency to every terminal Slide 4

A trie tells you which strings exist; it says nothing about which ones people actually search for. To rank suggestions you store a frequency counter on each terminal node — the number of times that exact query was issued in the recent window (often a sliding 30-day count, and newer hits can be weighted up with exponential decay so trends surface). Intermediate nodes hold no count, because they aren't complete queries.

The counts come from an offline aggregation of query logs, never from the live request path. Only the rank order matters, not the absolute value, so once normalised each count can be a small integer. Ranking by popularity is the default; personalisation and locale can rerank on top later.

Naïve lookup: walk, then explore everything below Slide 5

The textbook algorithm has four steps: descend to the prefix node (one edge per character), depth-first search the whole subtree collecting every terminal, then heap-select the top K by frequency and return them. It is correct — and it falls apart precisely when the prefix is short, which is exactly when traffic is heaviest.

The subtree under a single letter like s can hold millions of distinct queries. Doing a full traversal of it on every keystroke, for every user overshoots the latency budget by orders of magnitude. The prefix walk is free; the subtree explosion is the killer.

Cache the answer at every prefix node Slide 6

Turn the expensive read into a cheap one by doing the work ahead of time. Precompute the top K for every prefix and store that list on the node itself. A lookup collapses to: walk to the node, return its cached list. That is O(P) total — constant in the size of the corpus, however many billions of queries sit underneath. This is the same instinct as caching in the Key-Value Store chapter: precompute on writes so reads are trivial.

You bought speed with memory — now prune Slide 7

Nothing is free. Storing K strings at every node multiplies memory by roughly K. A trie of 50 M nodes with K = 10 means ~500 M cached strings — the speed trick is really a speed-for-memory trade. The good news is that memory is a knob, not a cliff: a handful of pruning techniques bring the footprint back to something a fleet can hold in RAM.

Strings can also share a single pooled buffer and be referenced by offset, so a suggestion costs a few bytes of pointer rather than a full copy at every node it appears in.

Build the trie offline from query logs Slide 8

The serving trie is a derived, immutable artifact. A periodic batch job reads raw search logs, aggregates them into query → count, builds a fresh trie with the top-K already precomputed, serialises it to a blob, and publishes it to the serving fleet. The live request path never mutates state — it only reads a read-only structure that some other pipeline produced.

How fresh is fresh enough? Slide 9

Batch rebuilds hand you new trends every few hours, which is fine for most products — most queries don't trend on a minute-by-minute basis. When breaking news or a live event genuinely demands minute-level freshness, layer a streaming path on top rather than making it the default.

Most keystrokes hit the same few hundred prefixes Slide 10

Prefix popularity follows a steep Zipf-style curve: a small set of short prefixes accounts for most traffic. That makes a cache cascade extremely effective. A CDN edge answers the handful of universal, short prefixes; a regional Redis catches longer and per-locale variants; the trie servers only ever see the long tail and any personalised reranks.

Invalidation stays lazy: short TTLs let the edge go a little stale, and a version tag bumped on each fresh trie deploy makes caches refill on their own. Never block a request waiting on a cache — fall through fast.

Shard the trie when one box no longer fits Slide 11

A full trie can outgrow a single machine's RAM. There are two common partitioning schemes, and they trade routing simplicity against load balance — the same tension that shows up whenever you shard.

In practice many systems lean toward the hash / key-value approach precisely because even load and single-hop lookups matter more at serving time than sharing trie edges — the redundancy is a price worth paying. This is the consistent-hashing idea from earlier chapters applied to prefixes.

Principles to carry forward Slide 12

Active recall

Cover the answers. Say each one out loud before you tap to check.

Check yourself