Designing a Low‑Latency Typeahead Suggestion System with Trie and Distributed Architecture

Introduction

Typeahead (autocomplete) suggests queries as the user types, using search history, context and popular terms. It speeds up query composition and improves user experience.

Requirements

Functional

The service must return the top N (e.g., 10) most frequent and relevant terms for the current prefix.

Non‑functional

Low latency

Suggestions must be delivered in real time, with end‑to‑end latency under 20 ms (well below the average human keystroke interval of ~160 ms).

Fault tolerance

The system should continue to provide suggestions even if one or more components fail.

Scalability

The architecture must handle a growing number of concurrent users and query volume.

High‑Level Design

When a user types, the request is routed to an application server that reads the top‑N suggestions from an in‑memory cache (Redis) and returns them. New queries are persisted to a database for popularity‑based ranking.

An independent Assembler service collects raw query logs, aggregates prefix frequencies via a MapReduce job, writes the results to a distributed NoSQL store (Cassandra), and rebuilds or incrementally updates a Trie that is served to the suggestion service.

Data Structure

Trie

A Trie stores prefixes efficiently. For example, with the words UNITED, UNIQUE, UNIVERSAL, UNIVERSITY, typing UNIV should return UNIVERSAL and UNIVERSITY. The Trie resides in RAM for fast lookup; a durable copy is kept in a database.

Compressed nodes (path compression) reduce depth and traversal time.

Tracking Hot Searches

Each terminal node stores a counter of how many times the term has been searched. The counters are used to rank suggestions, promoting frequently searched terms.

Trie Partitioning

To support billions of queries per second, the Trie is sharded across multiple servers (e.g., prefixes A‑M on Server 01, N‑Z on Server 03) with replicas for durability.

Query After Partitioning

A load balancer forwards the request to the appropriate application server, which queries the relevant Trie shard.

Trie Updates

Updates are performed offline to avoid blocking reads. Logs are aggregated (e.g., every 15 minutes) via a MapReduce job, frequencies are written to Cassandra, and the Trie is rebuilt or incrementally updated. A primary‑replica/secondary‑replica scheme can be used to keep reads uninterrupted.

Detailed Design

Assembler Service

Collector

Collects raw query logs (phrase, timestamp, metadata) and stores them in HDFS for later processing.

Aggregator

Retrieves logs from HDFS, partitions work among workers, runs MapReduce to compute prefix frequencies, and writes the results to Cassandra.

Trie Builder

Creates or updates Trie shards, stores them in ZooKeeper‑coordinated storage, and persists snapshots in a NoSQL document store (e.g., MongoDB) for recovery. Updated Tries are then served to the suggestion service.

Evaluation

Low Latency

Compress Trie depth to reduce traversal time.

Perform Trie updates offline so the critical path remains read‑only.

Deploy geographically distributed application and database servers.

Use Redis and Cassandra as caching layers.

Partition the Trie appropriately to balance load.

Fault Tolerance

Replication and partitioning provide high resilience; standby servers take over if a node fails.

Scalability

Adding more servers or shards increases capacity linearly with query volume.

Conclusion

By moving resource‑intensive processing to offline pipelines and using an in‑memory, compressed Trie with proper partitioning, replication and caching, the system delivers low‑latency, fault‑tolerant and scalable typeahead suggestions.