Search Autocomplete — Cache Poisoning & Trie Rollback

Every time you type a single character into Google, YouTube, or Amazon's search bar and watch suggestions instantly appear, you're experiencing one of the most latency-sensitive distributed systems in production software. That instant feel isn't magic — it's a carefully engineered pipeline involving in-memory data structures, aggressive multi-layer caching, real-time ranking signals, and sub-50ms response time SLAs enforced globally. Getting it wrong means users feel lag, and lag means they leave. Getting it right means you're invisibly influencing what billions of people search for every day.

The core problem autocomplete solves is bridging the gap between intent and query. Users often don't know exactly what they want to type. A partial string like 'how to fix my' could complete in a hundred directions. The system must predict the most relevant and popular completions in real time, rank them by a blend of global popularity, personal history, and contextual signals — all before the user lifts their finger from the keyboard. It also needs to handle billions of daily queries, top-K ranking, typo tolerance, personalization, and graceful degradation when parts of the system fail.

By the end of this article you'll be able to walk into any senior system design interview and confidently design a production-grade autocomplete system from scratch. You'll understand why a trie beats a relational database for prefix lookups, how to scale it with sharding and caching layers, how ranking signals layer on top of raw prefix matching, and what real failure modes look like in production — including the ones that bite engineers at 3am.

What is a Search Autocomplete System?

A search autocomplete system (also called typeahead) provides real-time search suggestions as the user types. At its core, it's a prefix-matching problem: given a partial input, return the most likely completions. But production reality adds layers: handle billions of unique prefixes daily, rank by multiple signals, support multiple languages, tolerate typos, and do it all under 50ms at p99.

You'll find autocomplete in Google Search, YouTube, Amazon, Twitter, and any large-scale product where reducing friction improves user engagement. The design principles here apply equally to code completion in IDEs and command-line autocomplete.

package io.thecodeforge.autocomplete;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
    int frequency;
    PriorityQueue<String> topK = new PriorityQueue<>(
        (a, b) -> Integer.compare(getFrequency(b), getFrequency(a))
    );

    // For real production: maintain a bounded top-K heap per node
    // Updates require merge of child frequencies on insertion
}

Data Structures: Trie vs Prefix Hashing

Two dominant approaches for prefix matching: the classic trie and prefix hashing. A trie offers deterministic lookups and easy prefix traversal, but memory can balloon. Prefix hashing uses a hash map keyed by prefix strings (e.g., first 3 characters) and stores lists of completions per key. It's simpler and more cache-friendly but loses prefix-sharing benefits.

Real systems often hybridize: use a compressed trie (radix tree) for hot prefixes and fall back to prefix hash tables for rare prefixes. Google's approach, for example, uses a multi-tiered index with a memory-mapped trie for the top million queries and disk-backed hash tables for long-tail completions. Twitter's autocomplete uses a similar hybrid — in-memory trie for trending topics, disk-based for historical queries.

package io.thecodeforge.autocomplete;

import java.util.concurrent.ConcurrentHashMap;
import java.util.List;
import java.util.ArrayList;

public class PrefixHashStore {
    // key: first 3 chars of query, value: sorted list of completions
    private ConcurrentHashMap<String, List<Completion>> store = new ConcurrentHashMap<>();

    public List<Completion> get(String prefix) {
        String key = prefix.length() > 3 ? prefix.substring(0, 3) : prefix;
        return store.getOrDefault(key, List.of());
    }

    public void put(String prefix, List<Completion> completions) {
        String key = prefix.length() > 3 ? prefix.substring(0, 3) : prefix;
        store.put(key, completions);
    }
}

// Note: Updates must be atomic; use replace() with CAS to avoid lost writes

Ranking: What Order to Show Suggestions?

Users don't just want any completion — they want the most relevant one. Relevance is a blend of signals: global popularity (most searched queries with that prefix), personal history (your past searches), recency (trending queries), and context (location, device). Ranking in real time at 50ms is the hard part.

Most systems precompute a ranking score per query-prefix pair offline using MapReduce or Spark jobs. The score is a weighted sum: w1 log(frequency) + w2 (1 / days_since_last_search) + w3 * personal_boost. Real-time personalization adds an extra fetch from user profile cache at query time, merging personal top queries into the global top-K list before returning.

package io.thecodeforge.autocomplete;

import java.util.*;
import java.util.stream.Collectors;

public class Ranker {
    private static final double FREQ_WEIGHT = 0.6;
    private static final double RECENCY_WEIGHT = 0.3;
    private static final double PERSONAL_WEIGHT = 0.1;

    public List<Completion> rank(List<Completion> global, List<Completion> personal, int k) {
        // Merge global and personal completions with personal boost
        Map<String, Double> scores = new HashMap<>();
        for (Completion c : global) {
            scores.put(c.query, FREQ_WEIGHT * c.score);
        }
        for (Completion c : personal) {
            scores.merge(c.query, PERSONAL_WEIGHT * c.score, Double::sum);
        }
        return scores.entrySet().stream()
            .sorted(Map.Entry.<String, Double>comparingByValue().reversed())
            .limit(k)
            .map(e -> new Completion(e.getKey(), e.getValue()))
            .collect(Collectors.toList());
    }
}

// In production: scores are precomputed; real-time merge only for personalization

Caching for Sub-50ms Latency

Autocomplete is the poster child for multi-layer caching. Every microsecond counts. You'll typically see three layers: (1) Browser cache — service worker caches recent autocomplete responses, (2) CDN — edge caches for top 1% of prefixes (e.g., 'a', 'b'), (3) Application cache — Redis or Memcached for hot prefixes not in CDN, (4) In-memory L1 cache in application server — LRU cache with TTL, (5) The trie itself as the source of truth.

Cache invalidation is tricky: when a new query becomes popular (e.g., after a news event), must invalidate all prefixes that contain it. Use a bloom filter to quickly test if a prefix might need invalidation — avoids scanning entire cache.

package io.thecodeforge.autocomplete;

import com.google.common.cache.Cache;
import com.google.common.cache.CacheBuilder;
import java.util.concurrent.TimeUnit;

public class CacheManager {
    // L1 cache: in-memory, 10K entries, 30 second TTL
    private Cache<String, List<Completion>> l1 = CacheBuilder.newBuilder()
        .maximumSize(10_000)
        .expireAfterWrite(30, TimeUnit.SECONDS)
        .build();

    public List<Completion> get(String prefix) {
        List<Completion> result = l1.getIfPresent(prefix);
        if (result != null) return result;
        // fallback to Redis (L2)
        result = redisClient.get(prefix);
        if (result != null) {
            l1.put(prefix, result); // populate L1 on miss
        }
        return result;
    }
}

// L3 (trie) is only hit when both L1 and L2 miss

Sharding and Scaling Across Servers

A single server can't hold the entire autocomplete index for billions of queries. You need to shard. The challenge: prefix lookups cross shards unless you shard intelligently. Common strategy: consistent hashing on the first 2-3 characters of the query. All queries with prefix 'ab' go to shard 7, 'ac' to shard 3, etc. This keeps prefix locality — most lookups hit one shard.

But prefix skew is real: 'a' prefixes are 40% of traffic. Solution: replicate hot shards (e.g., 10 copies of 'a*' shard), and use a load balancer that routes by prefix hash to one of the replicas. For cold prefixes, a single shard per hash range suffices.

To handle high write throughput (ingesting new queries), use a write-ahead log (WAL) before updating the trie, and batch updates to the shard every few seconds. This also handles replica consistency.

package io.thecodeforge.autocomplete;

import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;
import java.util.List;

public class ShardRouter {
    private final List<ShardGroup> shardGroups;
    private static final int REPLICATION_FACTOR = 10;

    public String selectShard(String prefix) {
        int hash = Hashing.murmur3_32()
            .hashString(prefix.substring(0, Math.min(3, prefix.length())), StandardCharsets.UTF_8)
            .asInt();
        // hot shards get multiple nodes via replication factor
        int index = Math.abs(hash) % (shardGroups.size() * REPLICATION_FACTOR);
        int groupIndex = index / REPLICATION_FACTOR;
        ShardGroup group = shardGroups.get(groupIndex);
        // pick replica round-robin
        return group.getReplica();
    }
}

// Consistent hashing preferred for minimizing reshuffling on scale-up

Production Incident: Autocomplete Cache Poisoning

A real incident from a large e-commerce platform: autocomplete started showing offensive suggestions for normal queries. Root cause was a cache poisoning attack — attacker sent malicious queries that got cached, then served to all users. The fix required purging all caches and adding input sanitization before caching. This incident led to a new practice: never cache a query's suggestions without validating the output against toxicity filters.