Skip to main content
System Design Mafia
Back to patterns

Design Typeahead Suggestion / Autocomplete

A system that returns the top-K ranked prefix completions as a user types, serving results within the keystroke latency budget through precomputed in-memory trie lookups.

//The Contract

Requirements

Functionalwhat the system must do
  • ✓Given a typed prefix, the service returns the top-K completions ranked by global popularity — the most-searched continuations, not a random match
  • ✓The service ingests search and click events, computing per-query popularity with recency weighting so the ranking tracks real demand over time
  • ✓The client debounces keystrokes and cancels superseded requests so a single word scan fires roughly one suggest call instead of three to five
  • ✓The system supports an optional real-time blending layer that surfaces trending queries between full rebuild cycles
Non-functionalhow well it must do it
  • ≫Latency — p99 per keystroke completes within 100ms, the binding constraint that rules out any per-request ranking or disk access
  • ≫Read-heavy — suggest QPS dwarfs write volume (~500K reads vs. 100K writes at peak), so the read path is optimized over the write path
  • ≫Availability — degrade gracefully by serving stale or fewer results rather than erroring; a shorter suggestion list is acceptable, a failed search box is not
  • ≫Scalability — the serving tier scales linearly by adding more read replicas of the immutable index, and the build pipeline scales independently as a batch job
//Back of the Envelope

Scale Estimates

Rough, order-of-magnitude numbers. The point is to justify the architecture, not to be exact.

Daily searches
5B/day
drives the suggest QPS and corpus growth rate
Searches / sec (peak)
100K
each search fires ~5 debounced suggest calls
Suggest QPS (peak)
500K
every keystroke is a read — debounce is what keeps it tractable
Distinct query strings
100M
~20 chars avg — fits in RAM after radix compression
Trie memory footprint
12 GB
the entire ranked trie fits on one machine — no disk on the hot path
Rebuild interval
1 hr
offline pipeline produces a new version; between rebuilds the index is read-only
//Follow the Data

Request Flows

A diagram shows what exists; a trace shows what happens. Press play on a flow, or click any step, and the diagram above lights up the exact path that request takes.

Flow 01

Suggest a Prefix (Hot Path)

A user types in the search box — the system returns the top-K completions within the keystroke latency budget.

Flow 02

Ingest Signals & Build the Trie (Build Path)

Events from user searches flow through the offline pipeline, producing a fresh ranked trie that is atomically deployed to the serving tier.

//Component Breakdown

Key Components

Every box on the canvas, and the job it does. Click a card to locate it in the diagram; click the node itself for the full deep dive.

client×1
network×3
compute×3
database×4
cache×1
queue×1
//Deep Dive

Architecture Breakdown

Architecture Overview

The Typeahead Suggestion system is split into two decoupled paths: a hot read path that serves ranked prefix completions from memory within the keystroke latency budget, and an offline build path that ingests events, computes popularity, and constructs fresh ranked tries.

Hot Read Path

Each keystroke fires a debounced GET /v1/suggest request. The call flows through the CDN, Load Balancer, and API Gateway to the Suggest Service. The Suggest Service first checks Redis for the precomputed top-K completions of the typed prefix — on cache hit, results return in under a millisecond. On cache miss, the service routes to the appropriate Trie Shard via prefix-based routing. The shard holds a radix-compressed trie where every node stores its own precomputed top-K list, so a lookup is a pointer walk to the prefix node and a memory read of the cached results — no ranking, no sort, no disk. The entire round trip completes within the per-keystroke budget.

Offline Build Pipeline

The Suggest Service asynchronously publishes search and click events to Kafka. The Aggregator Service consumes event batches on a 15-minute schedule, computing per-query popularity scores with recency decay so stale fads fade and rising queries gain rank. Aggregated scores are written to Cassandra. The Trie Builder periodically reads the full popularity table and constructs a fresh radix-compressed ranked trie using bottom-up top-K propagation — each node's top-K is a merge of its children's precomputed lists, never a subtree scan. The completed immutable trie is deployed to every shard via an atomic pointer swap: all shards atomically switch to the new version without locking, while reads in flight finish on the old trie.

Key Design Principles

Rank offline, serve from memory. Precomputing the ranked top-K for every prefix is what makes the per-keystroke latency budget attainable. The decision to rank when data changes (offline) rather than when it is read is the central design principle that shapes everything else.

Immutable trie with atomic swap. The trie is rebuilt entirely off the serving path and swapped in as a single atomic operation. This eliminates read-write contention, keeps the read path lock-free, and provides natural crash isolation — a failed build simply leaves the old trie in place.

Prefix-based sharding with skew awareness. The trie is split by leading characters so each request touches exactly one shard. Hot prefix ranges are sub-sharded further to prevent skew from overwhelming a single node, while cold ranges share a shard efficiently.

//Trade-offs

Design Decisions

An architecture is a record of trade-offs. For every major choice here: what won, what lost, and why the constraints made it so.

01

When to rank — offline or at query time

ChosePrecompute top-K per node during offline build
OverRank at query time: find all matching queries, sort by popularity, return top-K

Ranking at query time fails the latency budget as the corpus grows — a short prefix like c could match millions of queries, and sorting them per keystroke is O(N log N) over a growing corpus with a fixed time budget. By precomputing the ranked top-K for every prefix during the offline build, the hot path becomes O(prefix length) — a pointer walk and a memory read. The trade-off is rebuild-cycle staleness, but popularity shifts over minutes to hours while reads arrive constantly.

02

Data structure for prefix lookup

ChoseIn-memory radix-compressed trie with per-node top-K
OverDatabase table with LIKE prefix query and ORDER BY scoreElasticsearch prefix query

A database WHERE query LIKE 'prefix%' ORDER BY score LIMIT 10 requires a full index scan or a prefix scan plus a sort per query — unacceptably slow at 500K QPS. Elasticsearch adds network overhead and per-query scoring. A radix-compressed trie held in RAM eliminates disk and network I/O: lookup costs one pointer walk per character and returns a pre-sorted list. The 12 GB estimate confirms the trie fits comfortably on a single serving host, and radix compression shrinks it further.

03

Build timing — batch rebuild vs. real-time update

ChoseOffline batch rebuild on a schedule (every hour)
OverReal-time incremental trie updates on every eventContinuous streaming pipeline that updates trie in near-real-time

Incremental updates require mutable shared state and write locks on the trie — they introduce contention on the read path and risk readers seeing half-applied updates. A batch rebuild produces a complete, immutable, internally consistent trie that is swapped in atomically. The 1-hour rebuild interval is acceptable because popularity changes slowly. When trending matters, a small real-time layer blends in recent top queries without touching the heavy trie.

04

Trie distribution — sharding strategy

ChosePrefix-range-based sharding with skew-aware splits
OverConsistent hashing across shardsRandom shard assignment with scatter-gather

Consistent hashing scatters a prefix's completions across multiple shards, requiring a read to query all shards and merge results — O(N shards) per lookup. Prefix-range sharding ensures every prefix lives on exactly one shard: one lookup, one response. Skew-aware sub-sharding splits hot ranges (e.g. s*) across more shards than cold ranges (z*), keeping load balanced without scatter-gather.

05

Trie update mechanism

ChoseImmutable trie with atomic pointer swap
OverIn-place trie mutation with read-write locksCopy-on-write with reference counting

In-place mutation requires every read to acquire a lock or risk seeing a partially updated structure. Readers in a concurrent 500K QPS system contend destructively. An immutable trie built off the serving path and exposed via a single atomic pointer swap eliminates all synchronization: readers see a consistent snapshot without ever taking a lock. The old trie is garbage-collected once all in-flight reads referencing it complete.

//What Breaks First

Bottlenecks & Failure Modes

Reading a system means sensing where it cracks under 10× load. These are the pressure points of this design, and how it holds.

Risk 01

Hot prefix skew

Failure mode

Short prefixes like a, s, or th receive a disproportionate share of suggest traffic because they match enormous numbers of completions and are typed by nearly every user. A single shard holding these ranges can be overloaded while other shards sit idle.

Mitigation

The routing layer supports skew-aware sub-sharding: hot ranges are split across multiple shards (e.g. s-a through s-m on one shard, s-n through s-z on another). The boundary table is updated during each rebuild cycle based on observed traffic patterns.

Risk 02

Cache stampede on trie swap

Failure mode

When a fresh trie is deployed, the Redis cache contains entries built from the old trie's data. If the old and new rankings differ significantly, the first wave of requests after the swap all miss Redis simultaneously and hit the trie shards in a thundering herd.

Mitigation

Cache TTLs are set to a fraction of the rebuild interval (e.g. 15 minutes) so the cache drains gradually rather than all at once. Additionally, the Suggest Service can pre-warm Redis with the new trie's top prefixes before the swap completes.

Risk 03

Rebuild-cycle staleness for trending queries

Failure mode

A query that begins surging minutes after a rebuild finishes will not appear in suggestions until the next build up to an hour later. For rapidly developing events (breaking news, viral moments), hour-old rankings feel noticeably stale.

Mitigation

A lightweight real-time layer blends in: a small in-memory structure tracks recently popular queries over a short sliding window. At query time, the Suggest Service merges the precomputed top-K with the real-time list — both K-length — re-sorts, and keeps the top K. This adds a handful of comparisons per request, not a full ranking.

Risk 04

Full trie build resource contention

Failure mode

The Trie Builder reads the entire Cassandra popularity table and constructs a multi-gigabyte trie in memory. During this window, the builder competes for Cassandra read capacity and network bandwidth with other consumers. A naive implementation can degrade the aggregator's write throughput.

Mitigation

The builder runs on dedicated hosts and throttles its Cassandra read rate to leave headroom for concurrent writes. The build itself is stateless and resumable — if it is interrupted, the old trie continues serving and the builder retries on the next scheduled interval.

//Active Recall

Test Yourself

If you can answer these without scrolling back up, the architecture is yours. Try each one out loud before revealing.

//Go Deeper

Further Reading

Patterns used in this design
Design a Web CrawlerEvent-Driven ArchitectureDesign Twitter for Millions of Users
//A Word

From the Creator

Every great system starts as a sketch on a whiteboard. The ability to zoom out and see the whole picture (how services connect, where data flows, what breaks and why) is what separates engineers who build features from engineers who build systems. This diagram is more than boxes and arrows. It's a map of decisions, trade-offs, and intentional design.

Studying architectures isn't just about passing interviews. It's about training your intuition. The more systems you take apart, the better you get at sensing where a monolith will crack, where a queue belongs, or when a cache is hiding a deeper problem. You start seeing patterns instead of chaos.

So keep reading, keep tracing those edges, keep asking "why this way and not that way." The engineers who truly understand large systems are the ones who never stop being curious about how things fit together. That curiosity is the only ingredient that really matters.

Atharva Arbat@arbat_atharva

//Explore

More Patterns