Design Search Autocomplete

Search autocomplete (typeahead) suggests likely completions while a user types a query. For each keystroke, the service returns the top few most relevant queries that start with the current prefix. The service is read-dominated, must answer in tens of milliseconds, and can tolerate suggestions that are minutes or hours stale.

Requirements

Functional

• Given a prefix, return the top 5 to 10 suggestions ranked by popularity.
• Suggestions are based on historical query frequency; personalization and trending are extensions.
• Filter offensive or blocked suggestions.
• Support one language first; multi-language as an extension.

Non-functional

• Latency: responses under about 100 ms end to end, so the display keeps up with typing.
• Availability: high; if autocomplete fails, search still works.
• Scalability: handles a large share of all search traffic, since each search generates several prefix requests.
• Eventual freshness: updates from new query data may lag by hours.

Estimation

Assume 10 million DAU, each performing 10 searches per day, and each query of about 20 characters generating requests for roughly 5 prefixes after client-side debouncing (the client waits a short pause before sending).

• Searches: 10e6 x 10 = 100e6/day, about 1,160/s.
• Autocomplete requests: 100e6 x 5 = 500e6/day, about 5,800/s average; peak 2x, about 11,600/s.
• Distinct queries: assume 100 million distinct queries with an average of 25 bytes each, giving about 2.5 GB of raw query text, plus counts.
• Trie size: order of a few times the raw text once node overhead and top-k caches are included; assume 10 GB. That fits in the memory of a single large machine, so sharding is done for throughput and availability, not capacity.
• Query log ingestion: 100e6 searches/day x 100 bytes = 10 GB/day of logs.

What the numbers imply

• 11,600 requests per second peak is modest: at about 5,000 requests per second per server (in-memory lookups, mostly network and serialization cost), 3 servers suffice, so run 6 or more across zones for availability rather than capacity.
• 10 GB of trie fits in RAM, so every replica holds the whole trie and there is no cross-node hop per request, which keeps latency low and failure isolation simple.
• 10 GB of daily logs is small for a batch job; the trie rebuild takes minutes, so the cadence is limited by freshness needs and snapshot distribution, not compute. Distributing 10 GB at 1 Gbps takes about 80 seconds per server, so stagger swaps.

API design

GET /v1/autocomplete?q=<prefix>&limit=5&lang=en
-> 200 { "prefix": "how t", "suggestions": [
     {"text": "how to tie a tie", "score": 0.93},
     {"text": "how to screenshot on mac", "score": 0.88} ] }

• The endpoint is a cacheable GET; responses set a short Cache-Control: max-age so browsers and CDNs can cache popular prefixes (see content delivery networks).
• Clients debounce input, cancel stale in-flight requests, and cache earlier responses locally: after how has been fetched, a later how can often be answered from it.

Data model

The serving structure is a trie (prefix tree): each node represents a character, and the path from the root spells a prefix. To avoid scanning a subtree per request, each node stores the precomputed top-k completions for its prefix.

A relational LIKE 'prefix%' query works on an indexed column but is too slow and too expensive at this request rate; a purpose-built in-memory structure is used instead.

High-level design

flowchart LR
    Client["Client"] --> CDN["CDN / edge cache"]
    CDN --> LB["Load balancer"]
    LB --> AS["Autocomplete servers (in-memory trie)"]
    AS --> Cache[("Prefix cache")]
    Search["Search service"] --> Log[("Query log")]
    Log --> Agg["Aggregation jobs"]
    Agg --> Counts[("Aggregated counts")]
    Counts --> Builder["Trie builder"]
    Builder --> Snap[("Trie snapshots")]
    Snap --> AS
    Filter["Blocklist"] --> Builder

Two separate paths:

• Online read path: client to edge cache to autocomplete server; the server walks the trie to the prefix node and returns its stored top-k list.
• Offline build path: query logs are aggregated periodically (for example hourly to daily), the trie builder produces a new snapshot, and servers load it and swap it in atomically.

Read flow:

sequenceDiagram
    participant C as Client
    participant E as Edge cache
    participant S as Autocomplete server
    C->>E: GET /autocomplete?q=how t
    alt cache hit
        E-->>C: cached suggestions
    else cache miss
        E->>S: forward
        S->>S: walk trie: h, o, w, space, t
        S->>S: read top-k stored at node
        S-->>E: suggestions
        E-->>C: suggestions (cached briefly)
    end

Deep dive

Trie with precomputed top-k

Without precomputation, finding the top k under a prefix requires traversing the whole subtree, which for a short prefix like a is huge. Storing the top-k list at every node makes lookup O(L) where L is the prefix length, with a constant amount of work for the list. The trade-off is memory: each node holds k references.

Memory reductions:

• Store references (query IDs) to a shared string table, not copies of the strings.
• Compress single-child chains into one edge (a radix tree).
• Store top-k lists only at nodes whose prefix is short or has enough children; deeper nodes with few descendants can compute results on the fly.

A compact version of the idea in Java:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static final int K = 3;

    record Scored(int count, String query) {}

    static final class Node {
        final Map<Character, Node> children = new HashMap<>();
        final List<Scored> top = new ArrayList<>(); // best first, at most K
    }

    static final Comparator<Scored> BEST_FIRST =
            Comparator.comparingInt(Scored::count).reversed().thenComparing(Scored::query);

    static void insert(Node root, String query, int count) {
        var node = root;
        updateTop(node, query, count);
        for (char ch : query.toCharArray()) {
            node = node.children.computeIfAbsent(ch, c -> new Node());
            updateTop(node, query, count);
        }
    }

    static void updateTop(Node node, String query, int count) {
        node.top.add(new Scored(count, query));
        node.top.sort(BEST_FIRST);
        while (node.top.size() > K) {
            node.top.removeLast();
        }
    }

    static List<String> suggest(Node root, String prefix) {
        var node = root;
        for (char ch : prefix.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) {
                return List.of();
            }
        }
        return node.top.stream().map(Scored::query).toList();
    }

    public static void main(String[] args) {
        var root = new Node();
        record Entry(String query, int count) {}
        for (var e : List.of(new Entry("tree", 50), new Entry("trie", 30), new Entry("tried", 20),
                new Entry("true", 90), new Entry("try", 70), new Entry("tea", 10))) {
            insert(root, e.query(), e.count());
        }
        System.out.println(suggest(root, "tr"));
        System.out.println(suggest(root, "tri"));
        System.out.println(suggest(root, "x"));
    }
}

[true, try, tree]
[trie, tried]
[]

This sketch inserts each unique query once; a production builder processes aggregated counts offline and never mutates the live trie.

Building and updating

Updating the live trie for every search is expensive and contentious: it adds writes to a read-optimized structure and makes popularity noisy. Instead:

1. Log every completed search.
2. Aggregate counts over a window (day or week), often with exponential decay so recent queries weigh more.
3. Build a new trie offline; run the blocklist filter and minimum-count threshold (dropping rare queries also reduces size and privacy risk).
4. Publish the snapshot; servers load it in the background and swap a pointer, so requests never see a half-built trie.

For trending queries (breaking news), run a second, small streaming pipeline that counts queries over the last few minutes (stream processing) and merges the results into the response as a separate ranked list. Trie rebuild cadence stays slow, while the trending layer is fast.

Caching and latency

Prefix popularity is heavily skewed: a small set of short prefixes accounts for a large share of requests. Layers of caching:

• Client memory and browser cache (with short max-age).
• CDN or edge cache for popular prefixes.
• Server-side in-memory trie, which is itself the cache for everything else.

Since the trie is in memory, server-side latency is dominated by network and serialization, not lookup.

Sharding

The full trie fits on one machine, so each server holds the entire trie, and capacity is added by replicating servers behind a load balancer. If the data grows past one machine (multi-language, personalization), shard by prefix range (for example first character or first two characters). Naive first-letter sharding is unbalanced (many more queries start with s than x), so shard boundaries are chosen from measured prefix frequency, with a mapping table from prefix range to shard (see sharding and partitioning).

Concrete settings and alternatives. Store K = 10 per node and return 5, so blocklist filtering and personalized merging still leave enough results. Set a minimum count threshold (for example 100 searches by at least 20 distinct users in the window). Edge cache TTL of 5 to 10 minutes for short prefixes (1 to 3 characters), which account for a large share of traffic; longer prefixes are more varied and cache less well, so rely on the in-memory trie. During a swap, keep old and new snapshots side by side (2x memory, or serialize the trie into a flat, memory-mapped file), then switch a pointer. Alternatives to a precomputed trie: a sorted array of queries with binary search on the prefix range (compact, needs a range top-k structure), a finite state transducer (very compact), or a search engine with edge n-grams (flexible and fuzzy, but higher latency and cost). Consistency model: eventual; replicas may briefly serve different snapshot versions, which is acceptable for suggestions.

Ranking beyond frequency

Frequency alone favors old popular queries. Additional signals: recency decay, personalization (the user's own history merged from a small per-user store), locale, and click-through of past suggestions. Personalized results are merged with the global top-k at request time to keep the trie shared.

Bottlenecks and scaling

• Read throughput: stateless servers with the trie in memory scale horizontally; replicas are identical.
• Snapshot distribution: build once, store in object storage, and let each server pull the new version; stagger swaps to avoid load spikes.
• Memory: limit trie depth (for example queries beyond a maximum prefix length are matched up to that length), apply minimum count thresholds, and use compressed nodes.
• Availability: if a server fails, the load balancer routes elsewhere; if all fail, clients degrade to plain search. Keep the previous snapshot as fallback if a build produces bad data.
• Data quality: the blocklist filter is applied in the builder and again at serve time for urgent removals.

Failure modes

• Bad snapshot. Validate before publish: size within about 20 percent of the previous one, sample queries return expected results, blocklist applied. Canary on one replica; keep the last 3 snapshots and roll back by swapping the pointer.
• Server fails during load or swap. The load balancer removes it; clients see a slightly slower response from another replica. A server should not join the pool until its snapshot is loaded and warm.
• All autocomplete servers down. The client hides suggestions and search still works; this is why autocomplete is isolated from the search path.
• Trending pipeline lag. Suggestions stay correct but not fresh; serve the last trending list with a maximum age.
• Thundering herd after a cache flush. Edge and server caches are cheap to rebuild since the trie is in memory; the risk is only the load balancer spike, mitigated by staged rollout.
• At 10x (116,000 requests per second peak, larger vocabulary). The edge cache absorbs the short-prefix majority; add replicas (about 25 servers), and once the trie no longer fits in one machine, shard by measured prefix ranges and replicate hot shards more.

Trade-offs and follow-up questions

• Fresh vs stable suggestions: real-time updates give freshness but add write load and noise; batch rebuilds are simpler and predictable.
• Memory vs latency: precomputed top-k lists use more memory but make lookup cost independent of subtree size.
• How to handle typos? Add fuzzy matching (edit distance, or n-gram index) as a fallback when the exact prefix has few results; this is more expensive and usually a separate path.
• How to support other languages? Use a separate trie per language; for languages without spaces or with large alphabets, tokenize appropriately and use compressed nodes.
• How to avoid leaking private queries? Only include queries issued by many distinct users, and never build suggestions from single-user rare queries.
• How to reduce request volume? Client-side debounce, minimum prefix length of 1 to 2 characters, and reuse of earlier responses.
• What if a breaking-news query must appear within minutes? Merge the streaming trending list (5-minute window) ahead of trie results, subject to the blocklist.
• What if a suggestion must be removed immediately? Push it to a serve-time blocklist checked on every response and purge edge caches for affected prefixes.
• What if the user types fast? Debounce about 100 to 150 ms and cancel stale requests so only the latest prefix is rendered.
• What about personalization at scale? Keep the trie global; merge up to 3 to 5 items from a small per-user recent-searches store at request time.