01. Search Autocomplete — High-Level Design¶

~15 min read · Part 2 of 4 (Overview → HLD → LLD → Q&A)

This file turns the solutioning narrative into concrete boxes and the flows between them. Read the architecture top to bottom, follow a query and a log event through it, then look at what happens when pieces fail.

Architecture¶

                         ┌──────────────┐
        keystrokes ────▶ │  Edge / CDN  │  (caches hot-prefix responses near users)
        (debounced)      └──────┬───────┘
                                │ miss
                                ▼
                         ┌──────────────┐
                         │ Load Balancer │
                         └──────┬───────┘
                                │
                 ┌──────────────┼──────────────┐
                 ▼              ▼              ▼
           ┌──────────┐  ┌──────────┐  ┌──────────┐
           │ Suggest  │  │ Suggest  │  │ Suggest  │   stateless serving tier
           │ service  │  │ service  │  │ service  │   (cache → fan-out → merge)
           └────┬─────┘  └────┬─────┘  └────┬─────┘
                │             │             │
        ┌───────┴───────┐     │      ┌──────┴────────────┐
        ▼               ▼     ▼      ▼                   ▼
  ┌───────────┐   ┌──────────────────────┐        ┌──────────────┐
  │ Prefix    │   │  Trie shards (RAM)    │        │ Real-time    │
  │ result    │   │  shard-a  shard-h  …  │        │ trending     │
  │ cache     │   │  (base top-k per node)│        │ layer (10-min│
  └───────────┘   └──────────▲───────────┘        │ sliding wins)│
                             │                     └──────▲───────┘
                    (loaded from)                         │
                  ┌───────────┴────────────┐              │
                  │  Trie build job (batch) │      ┌───────┴────────┐
                  │  every few hours        │◀─────│  Event bus     │
                  └───────────▲─────────────┘      │  (Kafka)       │
                              │                     └───────▲────────┘
                   ┌──────────┴───────────┐                 │
                   │  Query log store      │◀───── submitted searches
                   │  (aggregated freqs)   │
                   └──────────────────────┘

Reading it top to bottom: debounced keystrokes arrive at the edge, where the hottest prefixes are answered without ever reaching origin. On a miss, the load balancer hands the request to any stateless suggest-service node. That node first checks the prefix result cache; on a cache miss it fans out to the trie shard that owns the prefix, reads the precomputed base top-k, asks the real-time trending layer for any surging candidates, merges the two, and returns the list. Underneath, two feedback loops keep the index current: submitted searches flow through the event bus into both a query log store (which the batch build job turns into a fresh base trie every few hours) and the trending layer (which counts the last few minutes live).

Components¶

Edge / CDN. The outermost cache. Because a hot prefix like new returns the same top-10 for everyone in a locale, the edge can cache the response keyed by (prefix, lang, region) with a short TTL (tens of seconds). This is the cheapest possible way to absorb the flood of common short prefixes near the user.

Load balancer. Spreads requests across a stateless serving tier and health-checks nodes out of rotation. No request is pinned to a node, so capacity is added by adding boxes.

Suggest service (serving tier). Stateless request handlers. Each one runs the read path: check the prefix cache, fan out to the owning trie shard on a miss, query the trending layer, merge and re-rank, and respond. Holding no per-request state lets any node serve any prefix.

Prefix result cache. An in-memory (prefix, lang, region) → top-k map fronting the trie. This is where the read-heavy, skewed load actually lands — the ~95% of traffic aimed at the hottest million prefixes. Short TTLs keep cached lists from drifting too far from the trending layer.

Trie shards (in-RAM prefix index). The base ranking engine: the ~39 GB trie split across ~8–12 machines, each owning a slice of the prefix space and holding, at every node, the precomputed base top-k for that prefix. A lookup is a walk to one node and a read of its list — no per-request ranking.

Real-time trending layer. A streaming aggregator (Flink/Kafka Streams) maintaining sliding-window counts of the last ~10 minutes of queries and exposing the current top surging prefixes. Its output is small and merged into base results at serve time, which is how a spike surfaces in minutes without a trie rebuild.

Event bus (Kafka). A durable log of every submitted search. It decouples ingestion from serving and fans out to two consumers — the query log store and the trending layer — so neither can slow a live query.

Query log store + batch build job. The log store aggregates raw events into per-query frequencies; the periodic build job reads that aggregate, propagates top-k up the trie, and publishes a fresh base trie that the shards load. This is the expensive-but-infrequent half of the freshness tradeoff.

Primary write path (a search is submitted, ranking learns from it)¶

A user submits a full query. The client emits a query_event to the event bus — this is asynchronous and off the autocomplete read path entirely.
The trending layer consumes the event immediately, incrementing that query's count in its current sliding window. Within seconds it can tell that a term is surging.
In parallel the event lands in the query log store, where events are aggregated into per-query frequency counts over longer horizons.
Every few hours the batch build job reads the aggregated frequencies, walks the query set into a trie, and computes each node's top-k by rolling child frequencies up to parents.
The job publishes the new base trie; trie shards load their slices and atomically swap to the new version. The freshly popular query is now baked into the base rankings, and the trending layer's short-term boost for it can decay.

Primary read path (resolve a prefix to suggestions)¶

GET /autocomplete?q=new may be answered entirely at the CDN/edge if this exact (prefix, lang, region) is cached — the common case for short, hot prefixes, and it never touches origin.
On edge miss, the request reaches a suggest service node, which checks the prefix result cache.
Cache hit: return the cached top-k, optionally re-ranked for personalization (see below). This is the overwhelming majority of origin traffic.
Cache miss: the node routes to the trie shard owning new, walks to that node, and reads the precomputed base top-k.
It asks the trending layer whether any completion of new is currently surging; if so, those candidates are merged into the base list by blended score.
If a user context is present, the node re-ranks the small merged candidate set against the user's recent searches — a cheap reorder of ~10–20 items, never a new index lookup.
The node fills the prefix cache with the merged base list (the shared, non-personalized version, so the cache stays reusable) under a short TTL and returns the response.

Storage choices¶

Base index: in-RAM sharded trie. The access pattern is "walk a prefix, read a precomputed list" at single-digit milliseconds under 100k QPS. Only RAM meets the latency budget; SSD-backed lookups at 10–20 ms each would blow p99 once fan-out and merge are added. Sharding by prefix keeps each machine's slice at 3–5 GB.
Hot results: in-memory cache (Redis/local LRU). Chosen for microsecond reads and TTL support, holding the ~1M hottest prefixes. It is an accelerator, not a source of truth — a cold cache just means more trie reads until it warms.
Query logs: append-optimized / columnar store. Events are write-heavy, append-only, and read by aggregation over time, not by key. A columnar or log store (ClickHouse, BigQuery, S3+Spark) fits the batch build far better than the trie, and keeping it separate protects serving latency from analytics load.
Trending state: in-memory streaming store. Sliding-window counts live in the stream processor's state (RocksDB-backed), sized to the last few minutes of distinct queries — small, hot, and disposable on restart because it rebuilds from the retained event log.

Scaling¶

Read path. Three tiers absorb reads in order: edge, then prefix cache, then trie shards. The edge and cache handle the skewed hot prefixes; only cold or long prefixes reach the shards. To scale reads you add edge pops, grow the cache, and add read replicas of each trie shard — all independent horizontal moves. Concretely, the cache's ~95% hit ratio turns 100k QPS into ~5k QPS at the shards; pushing the hit ratio from 95% to 98% more than halves shard load (5k → 2k QPS) but shortens how fresh the cached lists stay, so it trades directly against trending latency.

Write path. Ingestion is asynchronous and cheap — appends to Kafka scale by adding partitions. The batch build is the heavy job, but it runs every few hours off the serving path, so it never contends with live queries. Its cost sets the base-freshness floor: a build that takes ~1 hour means the base rankings are at best ~1 hour stale, which is exactly why the trending layer exists.

Sharding and skew. The trie is partitioned by prefix, but prefix traffic is Zipfian: the shard owning short common prefixes (a–c, say) sees far more than the shard owning x–z. Two levers handle it — replicate hot shards so several replicas share the load of popular prefixes, and let the front cache absorb the very hottest prefixes so they rarely reach any shard at all. The design goal mirrors the URL case: the hottest prefix should be the cheapest to serve, because it lives in edge and cache, not in a shard walk.

Operational signals¶

The healthy signal is prefix cache hit ratio, which should sit around 95% and stay flat as traffic rises — a spike in a single query raises the hit ratio (one prefix, requested endlessly), which is the system working as designed. The first metric to degrade under trouble is p99 suggestion latency: when it climbs while hit ratio holds, misses are getting expensive — a slow or GC-pausing trie shard, or a lagging trending merge — rather than more frequent. The misleading metric is average latency, which stays flat because 95% of responses are fast cache hits, hiding a cold-path that has quietly gone from 5 ms to 150 ms; watch p99, never the mean. The graph an experienced operator opens first during an incident is trie-shard QPS: it should be a flat ~5k/s even at peak, so any climb toward tens of thousands means the cache is failing to absorb hot prefixes and a stampede against a shard is forming.

Failure modes and resilience¶

Trie shard restart / rebuild swap. When a shard swaps to a new base trie or restarts, its slice of the prefix cache can be invalidated at once. Put the threaded scenario on it: if a swap flushes cached entries while 100k QPS is flowing, the ~95% that were hitting cache now miss simultaneously and all fan out to the shards — a jump from ~5k to ~100k QPS against machines built for 5k. Mitigations: swap the trie atomically behind the same process so lookups never see a half-built tree; stagger rebuild swaps across shards and replicas so cache warms incrementally; and apply request coalescing so that many concurrent misses for the same cold prefix collapse into one shard walk rather than thousands.
Trending layer outage. The real-time merge goes away, so results fall back to base rankings only — slightly stale, but the feature stays up. Because trending is additive, its loss degrades freshness, not availability; the stream reprocesses from the retained event log on recovery and catches up.
Batch build job failure. The base trie simply stops updating and keeps serving the last good version. Rankings drift staler over hours, but nothing breaks; alert on build age and re-run. Never let a failed build push a partial trie to the shards.
Event bus lag. Trending falls behind and the log store's aggregates lag, so freshness suffers, but live queries are unaffected because ingestion is off the read path. Events are durably queued and replayed on recovery.
Cache node loss. Reads fall through to the trie shards, latency rises, and shard load spikes toward the 100k figure above. Mitigations: run the cache clustered with replicas, lean on the edge to keep absorbing the hottest prefixes, and coalesce misses during the degraded window.
Poisoned suggestions. Offensive or manipulated terms can be pushed up by coordinated querying. Mitigations (mostly offline): a blocklist applied at build time and at serve time, minimum-frequency and minimum-distinct-user thresholds before a term is eligible, and a fast kill-switch that purges a term from cache and trie immediately.

Where this shows up in production¶

Google Suggest — serves prefix completions from a precomputed, popularity-ranked index with a real-time layer for breaking terms, the canonical two-tier freshness design this study mirrors.
Elasticsearch completion suggester — ships an in-memory FST (finite-state transducer, a compressed trie) precisely because prefix lookups must not touch disk to stay in the millisecond range.
Apache Lucene FSTs — the compression trick under the trie: sharing suffixes as well as prefixes shrinks the in-RAM index enough to fit, which is the memory-vs-latency tradeoff resolved in favor of RAM.
Amazon / e-commerce search bars — blend historical popularity with real-time trending (a product going viral) exactly through a merged serve-time layer over a batch-built base index.
Twitter / X trends — the standalone sibling of the trending layer here: sliding-window counts over a query/hashtag stream, surfacing surges within minutes.
Redis / Memcached at the edge — used as the hot-prefix result cache with short TTLs, the tier that turns 100k QPS into ~5k QPS at the index.
Apache Flink / Kafka Streams — the sliding-window aggregation engine behind the trending layer, maintaining per-window counts in RocksDB-backed state that rebuilds from the log on restart.
DoorDash / food-delivery search — restaurant and dish typeahead built on the same prefix-index-plus-popularity pattern, with locale sharding so a prefix returns region-appropriate results.