Design: Autocomplete / Typeahead¶

Difficulty: Senior | Time: 60–75 minutes

1. Problem Statement¶

Design a search-box autocomplete (typeahead) service like Google Search suggestions. As a user types into a search box, the service returns the top-K most likely completions of what they're typing, updated on every keystroke, fast enough to feel instantaneous.

2. Clarifying Questions¶

Practice asking these before designing:

3. Functional Requirements¶

• Given a prefix (partial query string), return the top-K (typically 5-10) most likely full query completions
• Suggestions update as the user types each additional character
• Suggestions reflect real-world query popularity (frequency-ranked)
• Optional: personalization, typo tolerance, trending-query boosts

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Query log volume:
  5B searches/day, average query length 20 characters
  5B / 86,400s ≈ 58,000 searches/second (avg), ~300K/s peak

Autocomplete lookups (far more frequent than searches — one per keystroke):
  Avg query = 20 characters typed → ~15-20 keystrokes trigger a lookup
  (client-side debouncing cuts this down, assume ~8 effective lookups/query after debounce)
  58,000 searches/s × 8 ≈ 460,000 lookups/second (avg), ~2M/s at peak with debounce+multiplier

Distinct query corpus (from logs):
  10B historical distinct queries, but power-law distributed:
  Top 100M queries cover >95% of real traffic — this is the number that matters for the served trie

Trie size:
  100M queries × avg 20 bytes (compressed prefix sharing across a trie is far denser than raw strings)
  Rough serving-index estimate: ~15-25 GB for a compressed trie of the top 100M queries + top-K per node
  Comfortably fits in RAM on a handful of nodes, or shardable across dozens for headroom

Bandwidth:
  Each response: top-10 suggestions × ~30 bytes avg ≈ 300 bytes
  2M lookups/s × 300 bytes ≈ 600 MB/s at peak — meaningful, but CDN/edge-cacheable for hot prefixes

6. API Design¶

GET /api/v1/suggest?q={prefix}&limit=10
Response: {
  "prefix": "syst",
  "suggestions": [
    { "text": "system design interview questions", "score": 0.94 },
    { "text": "system design primer", "score": 0.81 },
    { "text": "systemd service file example", "score": 0.62 },
    ...
  ]
}
Status: 200 OK (empty suggestions array on no match, never an error)

GET /api/v1/suggest?q={prefix}&limit=10&user_id={id}
Response: same shape, blended with personalized signals (recent searches, location)

POST /api/v1/log-selection   (fire-and-forget, async)
Request: { "prefix": "syst", "selected": "system design interview questions", "position": 0 }

7. Deep Dive: The Trie as the Core Data Structure¶

The natural fit for "give me everything that starts with this prefix, ranked" is a trie (prefix tree) — each node represents one character, and a path from root to node spells out a prefix. See DSA Foundations for the trie data structure fundamentals (node structure, insert/search complexity) if you need a refresher; this section focuses on how it's adapted for ranked, served autocomplete at scale rather than the base data structure itself.

A plain trie only tells you whether a prefix exists. For autocomplete we need each node to already know its top-K completions, so a lookup is O(prefix length) to reach the node, then an O(1) read of a precomputed list — not a tree walk over every descendant at query time.

Node structure (serving-optimized trie):
{
  children: Map<char, Node>,
  top_k: [ {query: "system design...", score: 0.94}, ... ]   # precomputed, sorted
}

Why precompute top-K per node instead of walking the subtree live? A prefix like "a" can have millions of descendant queries. Walking that subtree on every keystroke, for every user, at 2M lookups/second, is not viable — even an O(log n) heap-based walk per request is too much aggregate CPU. Precomputing top-K at every node during the offline build turns the online read into a pointer-chase plus a constant-size list copy.

Build (offline, per node, bottom-up):
  top_k(node) = merge(node.own_query_score_if_terminal,
                       top_k(child) for child in node.children)[:K]
  # classic "merge K sorted lists, keep top K" — O(children × K) per node

This offline/online split — and why you can't recompute top-K live — is the single most important idea to say out loud early in this interview.

8. Deep Dive: Offline Build vs. Online Serving¶

9. Deep Dive: Ranking¶

Global vs. personalized: the pragmatic default is to serve the global top-K trie for the vast majority of the latency-critical path, then optionally re-rank or blend in a small number of personalized candidates (from a much smaller, per-user recent-history structure) as a fast secondary step — not to build a separate full trie per user, which doesn't scale.

10. Basic Architecture (Version 1)¶

graph LR
    Client -->|GET /suggest?q=prefix| API[Autocomplete API]
    API --> Trie[In-Memory Trie\nsingle node, RAM-resident]
    Logs[(Query Logs)] -->|nightly batch job| Builder[Trie Builder]
    Builder -->|new trie blob| Trie

This handles moderate scale — one node holding the whole trie, rebuilt nightly. Identify the bottleneck before adding more components.

11. Identify Bottlenecks¶

12. Scaled Architecture (Version 2)¶

graph TD
    subgraph Edge["Edge / CDN"]
        E1[Edge Cache\nhot prefixes]
    end
    subgraph LB["Load Balancer"]
        L[L7 Load Balancer]
    end
    subgraph Serving["Autocomplete Serving Tier (stateless, sharded by prefix)"]
        S1[Shard A-F\nreplica ×3]
        S2[Shard G-M\nreplica ×3]
        S3[Shard N-S\nreplica ×3]
        S4[Shard T-Z\nreplica ×3]
    end
    subgraph Hot["Trending / Hot-Path Layer"]
        HP[Streaming Aggregator\nlast 10-15 min window]
    end
    subgraph Offline["Offline Pipeline"]
        Logs[(Query Logs\nKafka)]
        Batch[Batch Job\nSpark/Flink]
        Blob[(Trie Blob Store\nS3/GCS, versioned)]
    end

    Client --> E1
    E1 -->|cache miss| L
    L --> S1
    L --> S2
    L --> S3
    L --> S4
    S1 -.blend.-> HP
    S2 -.blend.-> HP
    S3 -.blend.-> HP
    S4 -.blend.-> HP
    Logs --> Batch
    Batch --> Blob
    Blob -->|periodic pull + atomic swap| S1
    Blob -->|periodic pull + atomic swap| S2
    Blob -->|periodic pull + atomic swap| S3
    Blob -->|periodic pull + atomic swap| S4
    Logs --> HP

Sharding the trie by prefix: split the root's children across shards (e.g., A-F, G-M, N-S, T-Z, or finer-grained by two-character prefix as the corpus grows). A request for prefix "syst" routes only to the shard owning s*. This is different from consistent-hashing a random key — the shard boundary is chosen along the trie's own structure (alphabetic ranges), so the router just needs a static, small lookup table of prefix-range → shard, not a hash ring. Each shard is independently replicated (×3) for both throughput and availability.

Caching hot prefixes: short, extremely common prefixes ("a", "th", "how") receive a disproportionate share of traffic. Front the serving tier with a CDN/edge cache and an in-process LRU cache on each serving node for the top few thousand prefixes — see Cache Strategies for TTL and invalidation patterns. Since the underlying trie only changes on a batch swap (not per-request), cache TTL can safely be set to the batch refresh interval, and invalidated wholesale on each new trie version rather than per-key.

13. Failure Modes¶

14. Consistency Considerations¶

• Eventual consistency is the entire design, not a compromise. The served trie is a point-in-time snapshot; it's stale by definition between builds. This is fine because "top completions for a prefix" doesn't need to be linearizable — no user is harmed by seeing a suggestion list computed 10 minutes ago.
• Atomic version swap, not incremental mutation. Serving nodes never partially apply a new trie — they load the new version fully off the serving path, then atomically swap the pointer. This avoids ever serving a torn/inconsistent read from a half-updated structure.
• Selection logging is async and best-effort. The log-selection call that feeds click-through ranking doesn't need to be durable per-event — losing a small percentage of these events under load has no user-visible effect and only marginally affects rank quality over the aggregation window.

15. Observability¶

Key metrics:
- suggest_latency_p50/p95/p99 (SLO: p99 < 100ms)
- suggest_empty_rate (percentage of requests returning zero suggestions — signals cold-start gaps)
- trie_age_seconds (time since current trie version was built — freshness signal)
- shard_request_distribution (detect skew — one shard getting disproportionate traffic)
- cache_hit_rate (edge + in-process)
- click_through_rate (selections / impressions, by rank position — feeds ranking quality)

Alerts:
- p99 latency > 150ms
- trie_age_seconds > 6 hours (batch pipeline stalled)
- suggest_empty_rate spikes (possible trie corruption or routing bug)
- any single shard > 2x average request rate (hot shard, needs rebalancing)

16. Cost Analysis¶

Serving tier (12 nodes: 4 shards × 3 replicas, r6g.xlarge, 32GB RAM):  ~$1,800/month
Edge/CDN caching (2M req/s peak, cache-offloaded):                     ~$600/month
Batch pipeline (Spark cluster, runs a few hours/day):                  ~$400/month
Streaming hot-path aggregator (small Flink/Kafka Streams cluster):     ~$300/month
Blob storage (trie versions, S3, with lifecycle cleanup):              ~$50/month
Total:                                                                  ~$3,150/month

Cost per lookup:
  460K/s avg × 2.6M s/month ≈ 1.2 trillion lookups/month
  $3,150 / 1.2e12 ≈ $2.6 per billion lookups (~$0.0000000026 each)

17. Alternative Architectures¶

18. Staff Engineer Extensions¶

19. Interview Follow-ups¶

1. "How would you support typo tolerance (e.g., 'gooogle' → 'google')?" — This is fundamentally a fuzzy-matching problem, not a prefix-matching one. Common approaches: generate a bounded set of edit-distance-1/2 variants of the typed prefix and probe the trie for each (cheap for short prefixes, expensive for long ones), or maintain a secondary phonetic/n-gram index (e.g., BK-tree or a symmetric-delete index) alongside the trie specifically for fuzzy lookups, falling back to it only when the exact-prefix trie returns few or no results.
2. "How do you prevent offensive or manipulated completions?" — A moderation/denylist layer sits between the ranked trie output and the response — filter or demote flagged terms at serve time (fast to update, no rebuild needed) in addition to excluding them at build time from the training corpus.
3. "How would you personalize without a full per-user trie?" — Keep a small, fast per-user recent-search list (a few hundred entries, cached in Redis or client-side) and merge it with the global trie's top-K at request time — a lightweight blend step, not a second trie.
4. "What happens to ranking quality if click-through data is sparse for long-tail prefixes?" — Fall back to raw frequency-only scoring below a minimum-impressions threshold; don't let a low-volume signal (CTR from 3 impressions) dominate over a stable one (frequency from 10,000 occurrences) — this is a general small-sample-size trap worth naming explicitly.

Self-Assessment¶

• [ ] Can I explain why top-K is precomputed per trie node instead of walked live at request time?
• [ ] Can I justify the offline-build/online-serve split and what freshness gap it creates?
• [ ] Can I describe how the trie is sharded and why that differs from hashing a random key?
• [ ] Can I walk through what happens end-to-end when the batch pipeline is delayed for hours?
• [ ] Can I sketch at least one approach to typo tolerance without over-engineering the base design?