typeahead

Consider a naive approach: store all terms in a PostgreSQL table with a B-tree index on term. For prefix search, run SELECT term, frequency FROM terms WHERE term LIKE 'har%' ORDER BY frequency DESC LIMIT 10.

Problems:

• Latency: Even with an index, LIKE 'har%' is a range scan. At 50M+ terms, this takes 10–50ms per query. With 460K QPS, the DB would need thousands of cores.
• QPS ceiling: A single PostgreSQL node handles ~5K–10K simple queries/sec. We need 460K.
• No ranking optimization: The DB must scan all matching rows to find the top-10 by frequency.

The solution: pre-compute and cache the results so that lookups are O(1) key-value reads.

Typeahead is uniquely suited for CDN caching because:

1. Prefix distribution follows Zipf's law: A small number of prefixes account for a huge percentage of traffic. The top 1,000 prefixes ('a', 'the', 'sh', 'iph', ...) cover >50% of all requests.
2. Responses are identical for all users (no personalization in the base system). This means the same prefix always returns the same response, making it perfectly cacheable.
3. Small response size (~500 bytes). CDNs can cache billions of small responses efficiently.
4. TTL matches update frequency: If we rebuild the index daily, a 24-hour CDN TTL ensures users always see the latest suggestions while maximizing cache hit rate.

At-scale impact: With a 50% CDN hit rate, we cut origin QPS from 460K to 230K — effectively halving our infrastructure cost for the read path.

Before the request even leaves the browser, two optimizations dramatically reduce server load:

1. Debouncing: Don't fire a request on every keystroke — wait 100–150ms after the user stops typing. If a user types "harr" quickly, instead of firing 4 requests (h, ha, har, harr), we fire 1 (harr). This can reduce QPS by 3–5×.

2. Local result caching (browser memory): Store the last N prefix→suggestions mappings in a JavaScript Map. If the user types har, gets results, then deletes the r and retypes it, the second har request is served from local memory — zero network latency.

Combined, debouncing + browser caching can reduce actual server QPS by 60–80% compared to the theoretical maximum.

Elasticsearch implements typeahead using edge n-gram tokenization. When indexing, each term is broken into all its prefixes:

• "car" → tokens: "c", "ca", "car"
• "cat" → tokens: "c", "ca", "cat"

The inverted index then maps each token to the documents (terms) containing it:

"c"   → ["car", "cat"]
"ca"  → ["car", "cat"]
"car" → ["car"]
"cat" → ["cat"]

This is conceptually identical to our prefix hash table — the difference is that Elasticsearch handles the infrastructure (sharding, replication, relevance scoring) out of the box. Good for rapid prototyping; less control over latency compared to a custom solution.

The prefix hash table is large (~50 GB). Loading it into Redis or into in-memory indexes takes minutes. If we updated in-place, we'd have a window where:

• Some keys are from the old index, some from the new (inconsistent results).
• The loading process competes with serving traffic for CPU and memory.

Blue-green solves both: the standby cluster is fully loaded and warmed before any user traffic touches it. The swap is atomic — one DNS/LB config change.

Raw frequency (total searches all-time) has a problem: stale terms that were popular years ago dominate over currently trending terms. We apply exponential time decay:

$\text{score}(t) = \text{frequency} \times e^{-\lambda \cdot \Delta t}$

Where $\lambda$ is a decay constant and $\Delta t$ is days since last search. A typical $\lambda = 0.01$ gives a half-life of ~70 days — a term unsearched for 70 days has half its original weight.

In the Spark job, we compute this as:

import math
decay_lambda = 0.01
score = frequency * math.exp(-decay_lambda * days_since_last_search)

This naturally promotes trending terms while gracefully aging out stale ones.

After a new index is built, the blue-green deployment warms the standby Redis cluster:

1. Pre-load: The Index Builder writes all prefix→top-K pairs to the standby Redis cluster.
2. Synthetic traffic replay: Replay the last hour of production requests against the standby to warm application-level caches and JIT compilation.
3. Atomic swap: Once warm, the LB switches traffic to the standby cluster.
4. CDN purge: Issue a CDN cache purge for /suggestions* to ensure users see the updated suggestions.

No TTL-based invalidation is needed because we do a full cache replacement on every rebuild.

If the Redis cluster restarts or a new shard is added, all requests suddenly miss the cache and hit the in-memory index — a "thundering herd" on the suggestion services.

Mitigations:

1. Request coalescing: If 100 concurrent requests for the same prefix all miss Redis, only one request is forwarded to the in-memory index; the other 99 wait for the result.
2. Jittered cache TTLs: Add a random offset (±5%) to TTLs so entries don't all expire at the same time.
3. Fallback circuit breaker: If Redis error rate exceeds 10%, bypass it entirely and serve from in-memory (which always has the full index).

When the full index no longer fits on a single machine (or is wasteful to replicate), we shard by prefix range:

The load balancer routes GET /suggestions?q=har to Shard 2 (h is in k–p range). This reduces per-node memory by 5× while maintaining O(1) lookup.

Hot shards (a*, s*, c* are typically the busiest prefixes in English) get more replicas.

For a global product:

• Batch pipeline: Runs in a single region (us-east). Outputs the prefix hash table to S3.
• S3 replication: Cross-region replication to us-west, eu-west, ap-southeast buckets.
• Regional read stack: Each region has its own: CDN PoP → LB → Suggestion Service fleet → Redis cluster. Index is loaded from the local S3 bucket.
• DNS routing: Route53 latency-based routing sends users to the nearest region.

This gives sub-50ms latency globally while the write path remains centralized.

The most practical approach for our architecture: during the index build, generate fuzzy variants for each prefix:

1. For each prefix of length ≤ 5 (where typos most commonly occur), generate all strings within edit distance 1.
2. Map each variant to the same top-K results as the original prefix.
3. Store these additional entries in the prefix hash table.

This increases the index size by ~5× for short prefixes but keeps lookup time at O(1). For longer prefixes (> 5 chars), typos are less common and the original prefix usually contains enough correct characters for a reasonable match.

def generate_edit_distance_1(prefix):
    """Generate all strings within edit distance 1 of the prefix."""
    alphabet = 'abcdefghijklmnopqrstuvwxyz0123456789 '
    results = set()
    # Deletions
    for i in range(len(prefix)):
        results.add(prefix[:i] + prefix[i+1:])
    # Substitutions
    for i in range(len(prefix)):
        for c in alphabet:
            results.add(prefix[:i] + c + prefix[i+1:])
    # Insertions
    for i in range(len(prefix) + 1):
        for c in alphabet:
            results.add(prefix[:i] + c + prefix[i:])
    results.discard(prefix)  # remove original
    return results

Typeahead fuzzy matching (during typing) is different from spell correction (after submission):

• Typeahead fuzzy matching: Must be fast (< 200ms), returns suggestions. Prefix-based.
• Spell correction: Can be slightly slower, corrects the full query. Uses Norvig's algorithm or a trained sequence-to-sequence model.

Google's approach: show typeahead suggestions while typing, and if the user submits a misspelled query, show "Did you mean: ..." on the results page — a separate system.

Global typeahead (same suggestions for everyone) is CDN-friendly and simple. Personalized typeahead ("you searched for 'python' before, so 'py' → 'python tutorial'" instead of 'PyTorch' for an ML engineer) is more useful but breaks cacheability.

Staff candidates should discuss:

• Hybrid approach: global top-7 + 3 personalized slots blended client-side.
• User embedding vectors: store a compact user preference vector, do real-time re-ranking at the service level.
• Privacy: personalized suggestions may leak sensitive search history.

Our design uses daily batch updates. But what if a major product launches or a celebrity endorsement goes viral? The term won't appear in suggestions until tomorrow's batch run.

Approaches to bridge the gap:

• Streaming layer: A Flink job reads the Kafka search log in real-time, maintains a sliding-window frequency counter, and pushes "trending" terms directly to Redis with a short TTL (1 hour).
• Lambda architecture: Batch pipeline for the stable base index + streaming pipeline for real-time delta. The suggestion service merges both at query time.
• Risk: Real-time updates can be gamed (bot search traffic to promote terms). Need rate limiting and anomaly detection on the streaming path.

Supporting typeahead in non-Latin scripts introduces unique challenges:

• Chinese/Japanese/Korean (CJK): No spaces between words. A user typing Chinese characters can't be prefix-matched the same way — need segmentation (word boundary detection) before indexing.
• Arabic/Hebrew: Right-to-left scripts. The prefix is built from the right side.
• Transliteration: Indian users may type Hindi words in Latin characters ("namaste" → suggest Hindi/Devanagari results).
• Index per language: Separate prefix hash tables per language to avoid cross-language pollution. The request includes an Accept-Language header to route to the correct index.