Design Search Autocomplete (Typeahead)

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

The client debounces keystrokes (e.g., 50-100ms) and issues a suggest request per settled prefix. Requests hit a CDN or edge cache first: prefixes follow a steep Zipfian distribution, so the top few thousand prefixes (single letters, common words) absorb a huge share of traffic and can be served straight from the edge with a short TTL.

Cache misses go through a load balancer to stateless API gateways, which route the prefix to the correct trie serving shard. Sharding is by prefix range (e.g., 'a'-'aq' on shard 1) with weights adjusted so hot letters do not overload one shard; a lookup table maintained by a coordinator maps prefix ranges to shards.

Each serving node holds its shard of the trie entirely in memory. Critically, each trie node stores a precomputed list of its top-k completions, so a lookup is O(len(prefix)) to walk to the node plus O(1) to read the cached top-k list, rather than a DFS over the subtree at query time.

On the write path, search logs flow through Kafka into an aggregation job (Flink for streaming or Spark for batch) that computes query frequencies over sliding windows. A builder service constructs a new trie snapshot every 30-60 minutes, applies the blocklist, and ships it to serving nodes, which swap the new snapshot in atomically and warm it before taking traffic.

Snapshots are also persisted to blob storage so a restarted node can bootstrap in minutes instead of rebuilding from raw logs. Weekly full rebuilds reconcile any drift from incremental updates.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Scaffold a Fastify server with GET /suggest?q= and an internal POST /queries hook that fires whenever a search is actually submitted.
2. 02Write the ingester: for each prefix (up to 20 chars) of a submitted query, ZINCRBY the query in that prefix's Redis sorted set, then trim the set to its top 50 members to bound memory.
3. 03Implement /suggest as a single ZREVRANGE on the prefix's sorted set, returning the top 10 as JSON.
4. 04Seed the corpus with a bulk import script from a public query log (e.g., AOL dataset) or your own site's search history.
5. 05Add a frontend input with a 75ms debounce that calls /suggest per settled keystroke and renders the dropdown.
6. 06Add a Redis SET blocklist checked at ingest time so banned terms never enter a bucket.
7. 07Add a nightly cron that walks all buckets and multiplies scores by 0.9 (ZUNIONSTORE with a weight) so stale queries decay.
8. 08Load test hot prefixes with autocannon and confirm p99 stays under 20ms.

import Redis from "ioredis";
const redis = new Redis();
const MAX_PREFIX = 20;
const BUCKET_SIZE = 50;

export async function recordQuery(raw: string) {
  const q = raw.trim().toLowerCase();
  if (!q || (await redis.sismember("blocklist", q))) return;
  for (let i = 1; i <= Math.min(q.length, MAX_PREFIX); i++) {
    const key = "sug:" + q.slice(0, i);
    await redis.zincrby(key, 1, q);
    // keep only the best N per bucket so memory stays bounded
    await redis.zremrangebyrank(key, 0, -(BUCKET_SIZE + 1));
  }
}

export async function suggest(prefix: string, limit = 10) {
  const key = "sug:" + prefix.trim().toLowerCase();
  return redis.zrevrange(key, 0, limit - 1); // O(log n + limit)
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.top_k = []  # (score, query) pairs, best first, max 10

def build_trie(query_scores):
    root = TrieNode()
    for query, score in query_scores.items():
        node = root
        for ch in query:
            node = node.children.setdefault(ch, TrieNode())
            # maintain the top-k list at every ancestor node
            node.top_k.append((score, query))
            node.top_k.sort(reverse=True)
            del node.top_k[10:]
    return root

def suggest(root, prefix):
    node = root
    for ch in prefix.strip().lower():
        if ch not in node.children:
            return []
        node = node.children[ch]
    return [q for _, q in node.top_k]  # O(len(prefix)) total