Skip to content
All case studies

Typeahead / autocomplete

Return the top k query completions on every keystroke in under 50 ms so suggestions feel instantaneous. The trick is precomputing the top-k list at every trie node offline or in a streaming window, serving reads entirely from memory, and never mutating the trie synchronously on the read path.

Open reference designInteractive lessonPractice an interview
ClientsLoad balanc…Suggest API…Suggest API…Hot-prefix …In-memory t…Sampled que…Stream aggr…
Arrows show permitted calls. Open the canvas to inspect route programs.
Component labels and connections
  • Clients (client) · calls: Load balancer
  • Load balancer (loadBalancer) · calls: Suggest API 1, Suggest API 2
  • Suggest API 1 (service) · calls: Hot-prefix cache, In-memory trie shards, Sampled query log
  • Suggest API 2 (service) · calls: Hot-prefix cache, In-memory trie shards, Sampled query log
  • Hot-prefix cache (cache) · calls: none
  • In-memory trie shards (database) · calls: none
  • Sampled query log (queue) · calls: none
  • Stream aggregators + trie builder (worker) · calls: In-memory trie shards

Requirements

Functional

Non-functional

Worked estimates

  • Keystroke QPS

    ≈ 350k suggest requests/s average, ≈ 700k/s peak

    5B searches/day × ~6 keystrokes/search ÷ 86,400

  • Prefix keyspace

    ≈ 25 GB — the entire compiled trie fits in RAM on a single machine or a few shards

    50M distinct common prefixes × ~500 B (prefix + top-10 completions + scores)

  • Cache hit ratio

    a small front cache + browser local caching absorbs the majority of traffic

    1–3 character prefixes ('a', 'we', 'wha') account for > 60% of requests

  • Log ingestion

    ≈ 58k events/s raw, ≈ 5.8k/s after 1-in-10 sampling

    5B completed searches/day ÷ 86,400 (sampled at 10%)

API

GET /v1/suggest?q={prefix}&limit=10&lang=en

Request: prefix capped at ~50 chars; client debounces ~50–100 ms

Response: 200 { suggestions: [{ text, score }] } + Cache-Control

POST /v1/queries

Request: { query, locale, ts }

Response: 200

Logged when the user submits a search, not on every keystroke.

Data model

prefixes: materialised trie nodes where each prefix maps directly to its pre-sorted top-k suggestions (`O(1)` lookup by prefix key or `O(L)` trie traversal, instead of scanning all subtries).

Query logs flow through a streaming window (e.g. exponentially decayed counts every 5–15 minutes) that rebuilds or patches the trie snapshots and swaps them in atomically.

High-level design

Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.

Deep dives

Trie optimisations: compressed radix trees and cached top-k

A naive trie traverses down to the prefix node in `O(L)` steps and then visits every leaf in the subtree (`O(V)`) to find the top k — far too slow for short prefixes like 's'. Storing the precomputed top-k list directly on every trie node turns lookup into `O(L)` (or `O(1)` in a flat prefix hash table) at a modest memory multiplier. Compressing single-child chains into radix/Patricia trie edges further cuts node count and pointer chasing.

Two-speed updates: immutable snapshots + trending overlay

Full trie rebuilds run hourly or daily from sampled query logs using exponentially decayed frequency (`score = count × λ^age`), producing an immutable image loaded into memory by replicas without locks. For breaking news (earthquakes, sports scores), a lightweight streaming job detects velocity spikes over 1–5 minute windows and writes a small trending overlay merged at query time.

Client-side optimisations and safety filtering

Client debouncing (wait ~50 ms after a keystroke before firing), cancelling in-flight requests when the next character is typed, and caching prefix results in browser memory cut server QPS by half. Safety blocklists live in a separate fast filter applied both during offline trie construction and at serving time so an urgent legal takedown takes effect in seconds without waiting for a full trie rebuild.

Failure scenarios

Breaking news spikes one prefix to 40% of traffic

Scenario and expected result

A major live event causes 40% of users to type the same prefix.

Expected: The hot prefix sits in the front cache (with request coalescing), so the trie shards barely see the spike and p99 stays well below the 100 ms deadline.

Open this scenario

Hot-prefix cache restarts cold

Scenario and expected result

The front cache is killed from t = 1.4 s to 1.7 s and comes back empty.

Expected: While the front cache is down and refilling, misses fall back to the trie store and tail latency more than doubles before settling back to normal once the Zipf head refills.

Open this scenario

Stream aggregator workers pause during trie rebuild

Scenario and expected result

The aggregator workers are killed from t = 1.2 s to 2.2 s.

Expected: Because the read path (`suggest`) and write ingestion (`querylog` queue) are decoupled from the aggregator workers, user-facing suggestions and query logging continue at 100% goodput while trending updates simply lag by a second.

Open this scenario

Alternative designs

Reference

  • Inspect the architecture above and run the same scenario.

Query database with LIKE 'prefix%' on every keystroke

  • Without precomputed top-k lists per prefix and a front cache, every keystroke scans matching rows and sorts them by frequency. At 3,000 RPS with a 100 ms deadline, scanning the store blows the latency budget immediately.
Open this alternative

Reference

  • Inspect the architecture above and run the same scenario.

Update the live trie synchronously on every search

  • Incrementing node weights and bubbling top-k changes up to the root on every search causes severe write contention on short prefixes ('t', 'th', 'the') and locks out readers. Batching updates in a stream processor and swapping immutable trie snapshots eliminates read/write contention.

Reference

  • Inspect the architecture above and run the same scenario.

Shard trie by uniform hash of prefix vs prefix range

  • Range sharding ('a'–'c' on shard 1) concentrates traffic on common starting letters ('s', 'c', 't'). Hashing the prefix (or mapping short 1–2 char prefixes to a replicated front cache and hashing longer prefixes) spreads load evenly across shards.

Clarifying questions

Common mistakes

Self-assessment rubric

requirements / levels 1-4
  1. 1/4 Autocomplete prefixes.
  2. 2/4 Top-k ranked by popularity under low latency.
  3. 3/4 Sub-50 ms p99, read/write asymmetry, freshness vs safety filtering.
  4. 4/4 Separates keystroke read path from completed-query logging and trending velocity.
estimates / levels 1-4
  1. 1/4 None.
  2. 2/4 Keystroke QPS.
  3. 3/4 Keystroke QPS, trie memory footprint, and log sampling rate.
  4. 4/4 Proves the working trie fits in memory and explains why short prefixes dominate hits.
api / levels 1-4
  1. 1/4 GET suggest.
  2. 2/4 Suggest + query log.
  3. 3/4 Prefix length cap, debouncing, and cache headers.
  4. 4/4 Cancellation, locale/personalisation context, and blocklist overrides.
data model / levels 1-4
  1. 1/4 Queries table.
  2. 2/4 Trie structure.
  3. 3/4 Trie with precomputed top-k cached at each node.
  4. 4/4 Radix compression, time-decayed scoring, and immutable snapshot versioning.
high level / levels 1-4
  1. 1/4 API queries DB.
  2. 2/4 In-memory trie + DB.
  3. 3/4 Front cache, replicated in-memory trie shards, async log pipeline.
  4. 4/4 Snapshot build/swap pipeline plus streaming trending overlay.
deep dive / levels 1-4
  1. 1/4 None.
  2. 2/4 Explains trie traversal.
  3. 3/4 O(1) top-k node caching and offline rebuilds vs live lock contention.
  4. 4/4 Exponential decay, hot-prefix sharding, and fast takedown filtering.
wrap-up / levels 1-4
  1. 1/4 Stops.
  2. 2/4 Mentions latency.
  3. 3/4 Tail latency, stale trends, and offensive suggestions as top risks.
  4. 4/4 SLOs on p99 latency and freshness lag with automated rollback of bad trie builds.