Designing for Scale · Typeahead and Search Autocomplete

The problem this post solves

When a user types "sys", the search box should instantly suggest "system design", "systemctl", and "systemd". It must do this before they type the 't'.

This means the backend has an absolute maximum latency budget of 50 milliseconds. A standard database LIKE 'sys%' query on a table with billions of historical searches will take seconds, not milliseconds. It will also lock the database, because users generate a new query for every single keystroke.

This post covers the data structure that makes typeahead possible (the Trie) and the architecture required to build, update, and serve that structure at scale without crushing the backend.

First principles

The Trie Data Structure

A Trie (pronounced "try", from retrieval) is a tree-like data structure where each node represents a character. The path from the root to a node represents a string.

If we insert "sys" (frequency: 10), "system" (frequency: 50), and "sync" (frequency: 20):

To find suggestions for "sy", we traverse to the 'y' node, then run a Depth-First Search (DFS) to find all descendant words, sort them by frequency, and return the top results.

The Optimization: Caching Top Queries at the Node

Running a DFS from the 'y' node still takes time if there are millions of descendants. The optimization is to pre-compute the top $K$ (e.g., top 5) queries for every single node and store them directly on the node itself.

Node 'y' 
Top 5: ["system" (50), "sync" (20), "sys" (10)]
Children: 's', 'n'

Now, when the user types "sy", the system traverses to 'y' (which takes $O(L)$ time, where $L$ is the length of the prefix) and immediately returns the cached array in $O(1)$ time. No DFS, no sorting at read time.

Architecture

We cannot update the Trie in real-time. If every keystroke updates the frequency counter and triggers a re-sorting of the top 5 list at every parent node, the write amplification will destroy the system.

The solution is to separate the read path from the write path entirely. The Trie is read-only. It is rebuilt periodically offline.

The Write Path (Data Gathering)

1. When a user submits a final search query (not a keystroke, but pressing Enter), it is sent to a log aggregator like Kafka.
2. A stream processing system (or an hourly/daily batch job) reads the logs and aggregates the frequencies. "system" was searched 5,000 times today.
3. These aggregated frequencies are stored in a database.

The Build Path (Trie Construction)

1. A background worker periodically (e.g., every hour, or once a day) reads the aggregated database.
2. It builds a completely new Trie in memory.
3. It computes the top 5 suggestions for every node.
4. It swaps the new Trie into the cache, replacing the old one.

The Read Path

The API server simply looks up the prefix in the cached Trie and returns the pre-computed array.

Sharding the Trie

If the Trie grows beyond the memory of a single Redis node, it must be sharded.

Edge Optimization

Because the read path relies on a static, periodically updated data structure, it is a perfect candidate for client-side and edge caching.

1. Browser Caching: The client browser should cache the results for a prefix for a few hours. If the user hits backspace and types "sy" again, the browser should not hit the backend.
2. CDN Caching: The CDN can cache the API responses for the most common prefixes ("a", "s", "sy") for an hour.

Failure modes

Updating the Trie on every query. Attempting to maintain a real-time Trie guarantees lock contention and write amplification. Search trends do not change fast enough to justify real-time updates (outside of extreme breaking news, which is usually handled by a separate, smaller real-time pipeline).

Returning toxic or PII queries. The logs will contain misspellings, hate speech, and users accidentally typing their passwords into the search box. The batch aggregation step must include a rigorous filtering phase before the Trie is built.

What to carry forward