Chapter 68: Design Typeahead/Autocomplete

Interview Tip: Typeahead is a classic low-latency system design problem. Focus on data structures (trie), ranking algorithms, caching strategies, and real-time updates. The key challenge is serving suggestions in < 100ms at global scale.

1. Requirements

Functional Requirements

Prefix matching: Given a prefix, return top-K suggestions (e.g., "sta" → ["starbucks", "starbucks coffee", "stanford"])
Ranking: Sort suggestions by relevance (frequency, recency, personalization)
Real-time updates: New popular queries should appear in suggestions quickly
Personalization: Tailor suggestions based on user history, location, device
Trending: Boost queries that are currently trending (news events, viral topics)

Non-Functional Requirements

Low latency: Return suggestions in < 100ms (P95)
High availability: 99.99% uptime (critical user-facing feature)
Scalability: Handle billions of queries per day from millions of users
Freshness: Incorporate trending queries within minutes
Multi-language: Support Unicode, diacritics, multiple alphabets

Capacity Estimation

Active users: 500M DAU
Searches per user: 10/day
Total queries: 5B/day = 60K queries/sec
Typeahead requests: ~5 per query (as user types) = 300K RPS
Unique queries: 100M (need to store and rank)
Storage per query: 50 bytes → 100M * 50B = 5GB (trie structure is larger)

Interview Callout: Typeahead generates 5-10x more requests than actual searches because it fires on every keystroke. This makes low latency and caching critical.

2. High-Level Design

graph TB User[User Types Query] --> CDN[CDN/Edge Cache] CDN --> API[API Gateway] API --> TS1[Typeahead Service 1] API --> TS2[Typeahead Service 2] API --> TS3[Typeahead Service 3] TS1 --> Trie[(In-Memory Trie)] TS2 --> Trie TS3 --> Trie TS1 --> Cache[(Redis Cache
Hot Prefixes)] TS2 --> Cache TS3 --> Cache SearchLogs[Search Logs] --> Kafka[(Kafka)] Kafka --> Aggregator[Aggregator Service] Aggregator --> QueryDB[(Query Frequency DB)] QueryDB --> Builder[Trie Builder
Batch Job] Builder --> Trie style Trie fill:#e1f5ff style Cache fill:#ffe1e1 style Kafka fill:#fff5e1 style QueryDB fill:#e1ffe1

Data Flow

User types: Frontend sends prefix to API on every keystroke (debounced)
Lookup: Typeahead service queries in-memory trie for prefix
Ranking: Return top-K suggestions sorted by score
Logging: User's final search query is logged to Kafka
Aggregation: Batch job aggregates query frequencies
Rebuild: Trie is rebuilt periodically with updated frequencies

API Design

GET /api/v1/typeahead?q=sta&limit=10&userId=123&location=US
Response:
{
  "suggestions": [
    { "text": "starbucks", "score": 95000 },
    { "text": "starbucks near me", "score": 78000 },
    { "text": "stanford university", "score": 45000 },
    { "text": "star wars", "score": 32000 },
    { "text": "starbucks menu", "score": 28000 }
  ],
  "latency_ms": 23
}

3. Data Structure: Trie (Prefix Tree)

A trie is the optimal data structure for prefix matching. It stores all queries in a tree where each node represents a character.

Trie Example

Queries: ["star", "starbucks", "starbucks coffee", "stanford"]

         root
          |
          s
          |
          t
          |
          a
          |
          r* (freq=1000)
          |
       +--+--+
       |     |
       b     d (stanford)
       |
       u
       |
       c
       |
       k
       |
       s* (freq=95000)
       |
       (space)
       |
       c
       |
       o
       |
       f
       |
       f
       |
       e
       |
       e* (freq=12000)

* = end of word, freq = query frequency

Trie Node Structure

class TrieNode {
    Map children;  // 26-52 children for a-z, A-Z
    boolean isEndOfWord;
    long frequency;                     // how many times this query was searched
    List topSuggestions;        // pre-computed top-K for this prefix (optimization)
}

Lookup Algorithm

List getTopSuggestions(String prefix, int k) {
    TrieNode node = root;

    // Traverse to prefix node
    for (char c : prefix.toCharArray()) {
        if (!node.children.containsKey(c)) {
            return Collections.emptyList();  // prefix not found
        }
        node = node.children.get(c);
    }

    // Return pre-computed top-K at this node
    return node.topSuggestions.subList(0, Math.min(k, node.topSuggestions.size()));
}

// Time complexity: O(p) where p = prefix length (not dependent on total queries!)

Space Optimization: Compressed Trie

Store common prefixes in a single node to reduce memory.

// Instead of:  s → t → a → r → b → u → c → k → s
// Compress to: "starb" → "ucks"

class CompressedTrieNode {
    String edgeLabel;                   // "starb" instead of single char
    Map children;
    List topSuggestions;
}

Interview Callout: Why trie?

Hash table: Can't do prefix search efficiently
Database LIKE query: Too slow for 100ms requirement
Trie: O(p) lookup where p = prefix length, independent of dataset size

Compressed trie reduces memory by 50-70% for real-world text data.

4. Ranking: Scoring Suggestions

Base Score: Frequency

Most common ranking is by query frequency (how many times users searched this term).

score = log(frequency)  // log to dampen effect of super popular queries

Personalization Boost

Boost queries the user has searched before or queries related to their interests.

if (user.previousSearches.contains(query)) {
    score += 1000;  // strong boost for user's own history
}

if (user.interests.overlap(query.category)) {
    score += 500;   // moderate boost for user's interests
}

Trending Boost

Boost queries that are trending right now (news, events, viral topics).

// Calculate trending score based on recent spike
trendingScore = (frequencyLast1Hour / avgFrequencyLast7Days) * 1000;

if (trendingScore > 5.0) {  // 5x spike
    score += trendingScore;
}

Location Boost

Boost location-specific queries (e.g., "starbucks" → "starbucks near me" for mobile users).

if (query.containsLocation() && user.location.isNear(query.location)) {
    score += 800;
}

Recency Decay

Decay old queries over time to keep suggestions fresh.

daysSinceLastSearch = (currentTime - query.lastSearchedAt) / 86400;
decayFactor = Math.exp(-daysSinceLastSearch / 30);  // half-life of 30 days
score *= decayFactor;

Final Scoring Formula

finalScore =
    log(frequency) * 1.0 +
    personalizedBoost +
    trendingBoost +
    locationBoost -
    recencyDecay +
    qualityScore;  // editorial boost for high-quality results

Interview Callout: Discuss trade-offs:

Pure frequency: Simple but can be stale and generic
Personalization: Better UX but requires user data (privacy concerns)
Trending: Captures zeitgeist but can be noisy (need spam detection)

Production systems use ensemble of signals with ML models to learn optimal weights.

5. Real-Time Updates

Challenge

Trie is large (GBs) and in-memory. Can't rebuild it on every search. How to incorporate new popular queries?

Approach 1: Batch Rebuild (Every Few Hours)

Log all search queries to Kafka
Batch job aggregates queries every 6 hours
Rebuild trie with updated frequencies
Swap in new trie (blue-green deployment)

Pros and Cons

Pros: Simple, predictable, trie is always consistent
Cons: Stale data (6-hour lag), can't capture breaking news/viral trends in real-time

Approach 2: Incremental Updates (Real-Time)

Maintain frequency counters in Redis (hot queries only)
Every minute, check for queries with large spikes
Update trie in-place for these hot queries (lock-free using copy-on-write)
Broadcast trie updates to all servers via pub/sub

Pros and Cons

Pros: Near real-time (1-minute lag), captures trending queries immediately
Cons: Complex, risk of inconsistency across servers, increased memory churn

Hybrid Approach (Recommended)

Base trie: Rebuild every 6 hours with full dataset (stable, high-quality)
Trending overlay: Maintain separate small trie for trending queries (updated every 1 minute)
Query time: Merge results from base trie + trending trie, re-rank

List getSuggestions(String prefix) {
    List baseSuggestions = baseTrie.get(prefix);        // stable results
    List trendingSuggestions = trendingTrie.get(prefix); // hot topics

    // Merge and re-rank
    return mergeAndRank(baseSuggestions, trendingSuggestions, topK=10);
}

Interview Callout: Discuss sampling for efficiency. Don't log every query to Kafka (300K RPS = huge data volume). Sample 1-10% of queries for frequency estimation. For rare queries, even 1% sample is statistically significant.

6. Serving: In-Memory Trie and Pre-Computation

In-Memory Storage

Load entire trie into RAM of each typeahead server
100M queries * 50 bytes = 5GB raw, but trie structure is ~20GB (4x overhead)
Use compressed trie to reduce to ~10GB per server

Pre-Computed Top-K

Instead of traversing the entire subtree on every query, pre-compute top-K suggestions at each node during trie build.

// During trie build, at each node:
void precomputeTopK(TrieNode node, int k) {
    List allQueries = collectAllQueriesInSubtree(node);
    allQueries.sort(byFrequencyDesc);
    node.topSuggestions = allQueries.subList(0, k);
}

// At query time, instant lookup:
return node.topSuggestions;  // O(1)

Trade-offs

Pros: Ultra-fast queries (O(p) traversal + O(1) fetch)
Cons: Increased memory (store top-K at every node), can't dynamically adjust K at query time

Multi-Datacenter Replication

graph TB User1[User in US] --> DC1[US Datacenter] User2[User in EU] --> DC2[EU Datacenter] User3[User in Asia] --> DC3[Asia Datacenter] DC1 --> Trie1[(Trie Replica 1)] DC2 --> Trie2[(Trie Replica 2)] DC3 --> Trie3[(Trie Replica 3)] Builder[Trie Builder
US Central] --> S3[(S3/GCS)] S3 --> Trie1 S3 --> Trie2 S3 --> Trie3 style DC1 fill:#e1f5ff style DC2 fill:#e1f5ff style DC3 fill:#e1f5ff

Build trie once in central location
Serialize to file and upload to S3/GCS
Each datacenter downloads and loads trie into memory
Use GeoDNS to route users to nearest datacenter (lower latency)

7. Scalability: Sharding and Caching

Sharding by Prefix Range

If trie is too large for a single server (> 100GB), shard by first character or prefix range.

// Shard 1: a-f
// Shard 2: g-m
// Shard 3: n-s
// Shard 4: t-z

char firstChar = prefix.charAt(0);
int shard = getShardForChar(firstChar);
return shards[shard].getSuggestions(prefix);

Challenges

Uneven distribution: Queries starting with 's' are much more common than 'z'
Cross-shard queries: Multi-prefix searches require querying multiple shards

Caching Hot Prefixes

Cache suggestions for popular prefixes in Redis/CDN.

// Check cache first
String cacheKey = "typeahead:" + prefix;
List suggestions = redis.get(cacheKey);

if (suggestions == null) {
    suggestions = trie.getSuggestions(prefix);
    redis.setex(cacheKey, 3600, suggestions);  // cache for 1 hour
}

return suggestions;

Cache Hit Rate

80/20 rule: 20% of prefixes account for 80% of traffic ("a", "st", "goo", "fac")
Target 90%+ cache hit rate to offload trie lookups

CDN for Geographic Distribution

Deploy typeahead API at edge locations (CloudFlare, Fastly)
Cache suggestions at CDN edge for ultra-low latency (< 20ms)
Invalidate cache on trie updates

Interview Callout: Calculate capacity:

300K RPS with 90% cache hit rate = 30K trie lookups/sec
Each server can handle ~10K trie lookups/sec (memory-bound)
Need 3 servers per datacenter (for redundancy, 6 total)
Cache (Redis) reduces latency from 50ms to 5ms

8. Advanced Features

Fuzzy Matching and Typo Tolerance

Handle typos and misspellings using edit distance.

// If no results for "starbucsk", try edit distance 1:
// - starbucks (substitute k → k)
// - starbuchs (delete s)

List getSuggestionsWithFuzzy(String prefix) {
    List exact = trie.getSuggestions(prefix);

    if (exact.isEmpty()) {
        // Try fuzzy variants (edit distance 1-2)
        for (String variant : generateFuzzyVariants(prefix)) {
            List fuzzy = trie.getSuggestions(variant);
            if (!fuzzy.isEmpty()) return fuzzy;
        }
    }

    return exact;
}

Multi-Language Support

Use Unicode-aware trie (support Chinese, Arabic, Cyrillic)
Store separate tries per language (or language-agnostic trie with language field)
Handle diacritics (é, ñ, ü) by normalizing input

Query Segmentation

For multi-word queries, segment and suggest next word.

// User types: "new york "
// Suggest next word: "weather", "hotels", "restaurants"

String[] tokens = prefix.split(" ");
String lastToken = tokens[tokens.length - 1];

// Look up in bigram/trigram model
return nextWordSuggestions(tokens[0], lastToken);

Voice Search Integration

Handle phonetic matches (e.g., "starbux" → "starbucks")
Use phonetic algorithms (Soundex, Metaphone) to map sounds to queries

A/B Testing for Ranking

Test different ranking algorithms (frequency vs personalization vs trending)
Measure CTR (click-through rate) on suggestions
Use bandit algorithms to optimize ranking weights

9. Monitoring and Analytics

Key Metrics

Latency: P50/P95/P99 of typeahead API response time (target < 100ms P95)
Cache hit rate: % of queries served from cache (target > 90%)
CTR: % of users who click on a suggestion (measures relevance)
Zero-result rate: % of prefixes with no suggestions (measure coverage)
Trie memory: RAM usage per server, trie size

Query Analysis

Track most popular prefixes (to prioritize caching)
Identify queries with high zero-result rate (add to dictionary)
Detect spam/abusive queries (filter from trie)

Alerts

Alert on latency > 200ms P95 (degraded UX)
Alert on cache hit rate < 80% (cache warming issue)
Alert on sudden drop in CTR (ranking quality issue)

Summary

A production-grade typeahead/autocomplete system requires:

Trie data structure: In-memory prefix tree for O(p) lookups
Pre-computed top-K: Store top suggestions at each trie node for instant retrieval
Multi-signal ranking: Frequency, personalization, trending, location boosts
Hybrid updates: Batch rebuild (6 hours) + real-time trending overlay (1 minute)
Aggressive caching: Cache hot prefixes in Redis/CDN (90%+ hit rate)
Geographic distribution: Replicate trie to multiple datacenters, use GeoDNS
Compressed trie: Reduce memory footprint by 50-70%

The design prioritizes ultra-low latency (< 100ms) through in-memory serving, pre-computation, and aggressive caching, while balancing freshness through a hybrid batch + real-time update model.

System Design Bible

Chapter 68: Design Typeahead/Autocomplete

1. Requirements

Functional Requirements

Non-Functional Requirements

Capacity Estimation

2. High-Level Design

Data Flow

API Design

3. Data Structure: Trie (Prefix Tree)

Trie Example

Trie Node Structure

Lookup Algorithm

Space Optimization: Compressed Trie

4. Ranking: Scoring Suggestions

Base Score: Frequency

Personalization Boost

Trending Boost

Location Boost

Recency Decay

Final Scoring Formula

5. Real-Time Updates

Challenge

Approach 1: Batch Rebuild (Every Few Hours)

Pros and Cons

Approach 2: Incremental Updates (Real-Time)

Pros and Cons

Hybrid Approach (Recommended)

6. Serving: In-Memory Trie and Pre-Computation

In-Memory Storage

Pre-Computed Top-K

Trade-offs

Multi-Datacenter Replication

7. Scalability: Sharding and Caching

Sharding by Prefix Range

Challenges

Caching Hot Prefixes

Cache Hit Rate

CDN for Geographic Distribution

8. Advanced Features

Fuzzy Matching and Typo Tolerance

Multi-Language Support

Query Segmentation

Voice Search Integration

A/B Testing for Ranking

9. Monitoring and Analytics

Key Metrics

Query Analysis

Alerts

Summary