Typeahead System Design: How Search Autocomplete Works at Scale

Type "how to" into a search box and suggestions appear before you finish the next word. That feature answers a request on almost every keystroke, for every user, and it has to feel instant: research on response times going back decades puts the limit for "the system reacts instantaneously" at about 0.1 seconds. Nothing in autocomplete is individually hard. The challenge is doing simple things within a tight latency budget at a very high request rate, while keeping the suggestions fresh and free of things you never want to show.

This post designs a typeahead service: requirements and capacity, the top-k prefix index, serving and sharding, the offline build pipeline, trending queries, caching, personalization and filtering, with a diagram of both halves.

Requirements

Functional:

• Return the top 5 to 10 completions for a prefix, ranked mostly by popularity.
• Reflect new trends within minutes, not days.
• Never show suggestions that violate your policies.

Non-functional:

• About 100 ms end to end, which leaves the backend a budget of tens of milliseconds after network time.
• High availability: if suggestions fail, search still works, so degrade gracefully.
• Cheap: this runs on every keystroke.

Capacity

Assume 50 million daily users who each search 10 times a day, with about 6 suggestion requests per search after the client stops sending one per character:

Two observations shape the design. Short prefixes are extremely repetitive: everyone who types "w" asks the same question. And the answer to a prefix changes slowly, so it can be computed ahead of time.

The client does half the work

• Debounce. Wait 100 to 200 ms after the last keystroke before sending a request, so fast typists do not trigger one request per character.
• Cancel stale requests. When a new prefix goes out, abort the previous one, and ignore late responses for an older prefix.
• Cache locally. If "how t" returned ten results that all start with "how to", the client can filter them for "how to" without a request.
• Fall back silently. If the suggest call fails or is slow, show nothing; search must still work.

The top-k prefix index

The classic structure is a trie, where each node is a prefix and its children extend it by one character. Walking the trie and searching the whole subtree for the most popular queries at request time is too slow for popular prefixes. Instead, precompute the answer: store at every prefix node the top k completions, already ranked. A lookup becomes a single read.

Many implementations skip the pointer-based trie entirely and store a flat map from prefix to its top-k list, capped at a maximum prefix length, since very long prefixes are rare and can fall back to a slower path. Building one from aggregated counts is short:

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

The output is read-only and loads into memory on each serving node. If you already run Elasticsearch, its completion suggester provides the same idea as a feature: the documentation describes data structures that enable fast lookups but are costly to build and are stored in memory, which is exactly the trade-off this design makes.

Serving and sharding

The suggest service normalizes the prefix (lowercase, trim, Unicode normalization), reads the top-k list from the index, merges in trending and personal results, filters, and returns. Everything it reads is in memory.

When the index outgrows one machine, shard it. Sharding by first letter looks natural but is badly uneven: far more queries start with "s" than with "x". Hash the prefix instead, or split by ranges of measured traffic, and replicate each shard so a node failure only reduces capacity. Since the index is rebuilt offline, replicas never need to agree on writes; each loads the same snapshot.

The offline build pipeline

1. Collect. Search front ends log every completed query to a stream such as Kafka.
2. Aggregate. A batch job counts queries over a window, for example the last 30 days, with recent days weighted more, and drops rare queries below a threshold to protect privacy and remove noise.
3. Filter. Apply blocklists and policy classifiers before anything becomes a suggestion.
4. Build. Compute the prefix index as above and write it as a versioned snapshot to object storage.
5. Deploy. Serving nodes load the new snapshot side by side, switch atomically and keep the previous version for quick rollback.

Hourly or daily rebuilds keep the main index fresh enough for most queries.

Trending queries

A breaking news story produces a new popular query within minutes, long before the next batch build. Add a small real-time layer: a stream processor counts queries in sliding windows, detects ones rising much faster than their baseline, and writes them to a fast store such as Redis, keyed by prefix. The suggest service merges these with the batch results. Keep this layer small and filtered aggressively; it is where a coordinated attack would try to plant suggestions.

Caching at every layer

Short prefixes are the hottest and the most cacheable, because they are identical for everyone. Personalized results cannot be cached at the CDN, which is one reason to keep personalization light.

Personalization, typos and filtering

• Personal history. Blending a user's own recent queries with global suggestions helps a lot and is cheap if recent queries live on the device or in a small per-user store.
• Typos. Fuzzy matching within one edit of the prefix rescues "pyhton". It is more expensive, so many systems try exact prefixes first and fall back to fuzzy matching only when results are thin.
• Filtering applies twice: offline, before a query enters the index, and online, against a fast blocklist that can be updated within minutes without a rebuild.

The typeahead diagram

How to read it:

• The online frame is the per-keystroke path: browser, CDN cache, API gateway and suggest service.
• The suggest service reads two in-memory prefix shards and the Redis trending store, merges and filters the results.
• The offline frame is the build path: query logs from Kafka, the aggregation job and versioned index snapshots in object storage.
• The dashed edge from object storage to the shards is the snapshot load, the only link between the two halves.
• The Markdown block shows the latency budget and capacity numbers.

Drawing read-heavy systems clearly

• Split online and offline. The two halves have different latency budgets, failure modes and owners, and the diagram should show that at a glance.
• Show every cache layer, with its expiry. In a read-heavy system, caches are most of the architecture.
• Draw the single link between the halves: here, a versioned snapshot. It explains how updates reach users and how rollback works.
• Annotate the latency budget on the online path.

For the general approach, see the system design diagram example. The caching strategies diagram covers cache layers in more depth, and the log aggregation follows the patterns in the data pipeline architecture diagram.

Build it in Archboard

1. Sign in with Google or GitHub and create a diagram.
2. Add two Core Frame nodes: Online, per keystroke, and Offline, hourly build.
3. In the online frame, add a Device node from the Network pack for the browser, a CDN and an API Gateway from the Cloud pack, a Compute node for the suggest service, two Redis nodes from the Data pack for the prefix shards and one more Redis node for trending queries.
4. In the offline frame, add a Kafka node from the Data pack for query logs, a Compute node from the Cloud pack for the aggregation job and an Object Store from the Data pack for index snapshots.
5. Draw the request path left to right, the build path below it, and a dashed edge from the snapshots to the shards.
6. Add a Markdown block from the Core pack with the latency budget and capacity.

The example uses 13 diagram nodes, within the Free plan.

FAQ

What data structure is used for autocomplete? A trie, or a flat map from prefix to results, with the top k completions precomputed at each prefix. Precomputing turns every lookup into a single in-memory read.

How fast does autocomplete need to be? Around 100 ms from keystroke to suggestions feels instant. After network time, that leaves the backend tens of milliseconds, which is why the index lives in memory.

How do suggestions stay up to date? A batch pipeline rebuilds the index from query logs every hour or day, and a real-time layer adds fast-rising queries within minutes.

Should autocomplete requests go out on every keystroke? No. Debounce on the client for 100 to 200 ms, cancel outdated requests and reuse cached results for longer prefixes. This cuts request volume substantially.

How do you keep offensive suggestions out? Filter offline before queries enter the index, apply minimum popularity thresholds, and check results online against a blocklist you can update quickly.

Start free — one seat, no credit card.